葉曉涵，李德識

(武漢大學(xué) 電子信息學(xué)院，湖北 武漢 430072)

0 引 言

水下無線傳感器網(wǎng)絡(luò)(underwater wireless sensor networks，UWSN)在環(huán)境監(jiān)測、國防監(jiān)控與海洋資源探測中有著廣泛應(yīng)用[1]，其中水下路由算法是實現(xiàn)UWSN網(wǎng)絡(luò)連接和傳輸?shù)年P(guān)鍵技術(shù)之一[2]。

由于UWSN一般選用聲信號作為傳播媒介[3]，而聲信號在水中的傳播速度約為1500 m/s，使得水下通信面臨傳播時延長、多普勒效應(yīng)明顯等問題[4]，這為UWSN帶來了嚴(yán)峻的挑戰(zhàn)，并且陸地傳感網(wǎng)路由不能直接被UWSN應(yīng)用[5]，因此需要設(shè)計適合于UWSN的水下路由算法。

眾多的水下路由算法所側(cè)重關(guān)注的UWSN問題不同，如傳輸效率[6]、傳輸時延[7]等。水下節(jié)點能量資源緊張，節(jié)點充能或更換較為復(fù)雜，因此網(wǎng)絡(luò)負(fù)載和能量的均衡性問題成為水下路由算法的關(guān)鍵問題之一[8]。

目前在UWSN領(lǐng)域中已有部分水下路由算法的研究成果，如文獻(xiàn)[9，10]更多地關(guān)注了數(shù)據(jù)通信的效率問題，在報文轉(zhuǎn)發(fā)時未能實現(xiàn)負(fù)載的均衡分配。在水下無線傳感網(wǎng)領(lǐng)域關(guān)注負(fù)載均衡分配的算法中[11-13]，文獻(xiàn)[11,12]通過集中式地獲取全局的拓?fù)浜拓?fù)載信息，以平衡整體網(wǎng)絡(luò)的能量消耗為目標(biāo)，集中規(guī)劃節(jié)點的負(fù)載分配，文獻(xiàn)[13]中節(jié)點通過多次報文傳遞，調(diào)整源節(jié)點上傳數(shù)據(jù)的速率，改善局部網(wǎng)絡(luò)的擁塞情況。然而，由于UWSN節(jié)點很難使用定位功能得知全局拓?fù)浞植夹畔14]，且水下環(huán)境動態(tài)變化，全局信息多次更新同步會帶來巨大的控制信令消耗[11,12]，而局部流量控制需要相鄰近的節(jié)點多次交互負(fù)載信息，并通過多跳傳遞調(diào)整源節(jié)點速率[13]，水下聲信號的長時延會使得頻繁交互產(chǎn)生巨大的信道資源消耗和傳輸延時。因此上述水下負(fù)載均衡路由算法在UWSN的應(yīng)用中會受到限制，UWSN需要具有分布式?jīng)Q策能力和少信息交互需求的負(fù)載均衡路由算法。

在面對負(fù)載分配類型的決策問題時，強化學(xué)習(xí)算法能很好地通過單個智能體與環(huán)境的交互，使其具有獨自決策的能力，同時通過學(xué)習(xí)過往交互信息，減少了每次決策時所需的交互信息量[15]。

基于上述分析，本文提出一種基于強化學(xué)習(xí)的分布式水下負(fù)載均衡路由算法。首先，通過強化學(xué)習(xí)模型構(gòu)建單個智能體分布式負(fù)載分配決策的過程，單個節(jié)點依據(jù)隱含了其它節(jié)點負(fù)載信息的父節(jié)點剩余帶寬情況，學(xué)習(xí)整體網(wǎng)絡(luò)負(fù)載分布趨勢和如何分配負(fù)載，從而避免全局信息的同步更新；其次，通過歷史交互信息學(xué)習(xí)如何分配負(fù)載，減少了當(dāng)前分配時節(jié)點的交互需求，以此避免局部的頻繁交互；此外，引入演化博弈論模型加快強化學(xué)習(xí)的收斂速度，從而在高延遲、低帶寬的水聲信道中提升算法效率。

1 網(wǎng)絡(luò)場景與問題模型

1.1 網(wǎng)絡(luò)場景與初始拓?fù)浣?/h3>

假設(shè)水下無線傳感網(wǎng)絡(luò)場景[16]如圖1所示，布設(shè)在水下的傳感節(jié)點具有水聲通信和數(shù)據(jù)采集能力，匯聚節(jié)點具有水聲通信和無線電通信能力，被布設(shè)在水面。場景中節(jié)點具有一致的水聲通信范圍，同時傳感節(jié)點以固定速率采集和產(chǎn)生數(shù)據(jù)，將數(shù)據(jù)通過一跳或多跳的水聲通信方式傳遞到水面匯聚節(jié)點，匯聚節(jié)點再將數(shù)據(jù)通過無線電通信發(fā)送至岸上中心，完成傳感數(shù)據(jù)的收集。

節(jié)點布設(shè)后，為了便于數(shù)據(jù)傳輸時選擇路由路徑，網(wǎng)絡(luò)需要建立節(jié)點間的拓?fù)溥B接。為了降低拓?fù)鋸?fù)雜性，傳感節(jié)點僅保存到匯聚節(jié)點最少跳數(shù)的路由路徑，因此傳感節(jié)點可根據(jù)到匯聚節(jié)點的跳數(shù)距離劃分層級，避免同層節(jié)點之間的拓?fù)溥B接，構(gòu)成了多層樹狀拓?fù)?，如圖1所示。

1.2 問題描述與建模

節(jié)點傳輸數(shù)據(jù)時，通過多層拓?fù)溥B接從下層往上層發(fā)送傳感數(shù)據(jù)。節(jié)點需要發(fā)送的負(fù)載量包括了自身采集的數(shù)據(jù)以及下層子節(jié)點上傳的數(shù)據(jù)。如圖1所示，若節(jié)點與多個上層節(jié)點連接(如6號節(jié)點連接了2號、3號節(jié)點)，節(jié)點可選擇將負(fù)載按一定比例分配發(fā)往不同的上層節(jié)點，但節(jié)點總發(fā)送帶寬有限，若某節(jié)點需要發(fā)送的負(fù)載量過多或者超過了發(fā)送帶寬，則會導(dǎo)致該節(jié)點的剩余帶寬不足、能量消耗增加，網(wǎng)絡(luò)產(chǎn)生擁塞或丟包。如3號節(jié)點若接收6-10號節(jié)點的大部分負(fù)載，會導(dǎo)致3號發(fā)送帶寬不足并產(chǎn)生擁塞，而4號帶寬仍寬裕，并且3號節(jié)點能量消耗遠(yuǎn)多于4號節(jié)點。

因此本文所需解決的問題是每個節(jié)點在獲取父節(jié)點的剩余帶寬的情況(簡稱為帶寬情況)后，如何進(jìn)行合理比例的負(fù)載分配，使空閑網(wǎng)絡(luò)分擔(dān)更多的網(wǎng)絡(luò)負(fù)載，改善網(wǎng)絡(luò)整體性能。

在上述問題中，父節(jié)點計算得出一個預(yù)先設(shè)定長度的時間片中的剩余帶寬后，若節(jié)點以此為依據(jù)分配負(fù)載，則同一父節(jié)點下的多個子節(jié)點的不同分配決策會導(dǎo)致父節(jié)點帶寬情況發(fā)生轉(zhuǎn)變，并且由于節(jié)點的分配決策是在當(dāng)前帶寬情況的基礎(chǔ)上影響負(fù)載在網(wǎng)絡(luò)中的分布，所以帶寬情況的轉(zhuǎn)變僅與當(dāng)前分配決策和當(dāng)前帶寬情況有關(guān)，因此負(fù)載分配決策問題具有馬爾科夫性質(zhì)。與此同時，強化學(xué)習(xí)中智能體與環(huán)境交互的過程需要以馬爾科夫決策過程為建?；A(chǔ)。

基于上述分析，本文將所需解決的負(fù)載分配問題建模為馬爾科夫決策過程(Markov decision process，MDP)。在MDP中，節(jié)點在某個狀態(tài)下(父節(jié)點帶寬情況)，采取某個動作(負(fù)載分配決策)，所處狀態(tài)會以一定概率轉(zhuǎn)移到另一個狀態(tài)，并在轉(zhuǎn)移過程中得到表征該動作收益的反饋

MDPi:,i=1,2,…,n

(1)

式(1)表示節(jié)點ID為i的MDP問題，其中xi為節(jié)點i的狀態(tài)，ai為節(jié)點i的動作，P為狀態(tài)的轉(zhuǎn)移概率，在本文負(fù)載分配問題中P未知，ui為節(jié)點i的獎賞反饋。

如果節(jié)點知曉某個狀態(tài)下不同分配決策可獲得收益的期望值，則可以參考期望值進(jìn)行負(fù)載分配。針對MDP問題中動作的期望收益值，Q-Learning算法可以在狀態(tài)轉(zhuǎn)移概率P未知的情況下，實現(xiàn)無模型的強化學(xué)習(xí)，并以狀態(tài)-動作值函數(shù)(Q函數(shù))表示期望收益值，并且Q-Learning使用表結(jié)構(gòu)表示Q函數(shù)時，計算消耗資源少，適合用于智能傳感器中。因此本文通過強化學(xué)習(xí)中Q-Learning算法解決負(fù)載分配問題，并對MDP問題中的3個要素：狀態(tài)、動作、獎賞反饋，進(jìn)行具體的建模：

(1)狀態(tài)空間

節(jié)點所連接的多個父節(jié)點的剩余帶寬狀態(tài)共同構(gòu)成了節(jié)點的狀態(tài)，為了約束狀態(tài)空間的大小，拓?fù)浣r控制單個節(jié)點擁有父節(jié)點的個數(shù)不超過兩個，因此可定義式(1)中

(2)

(3)

式中：Bw_mj(t)為節(jié)點j在時間片t的剩余帶寬，e為閾值參數(shù)。Bw_mj(t)可以通過負(fù)載量和發(fā)送帶寬計算

Bw_mj(t)=Bwj-Trafj(t)

(4)

Bwj為節(jié)點j的發(fā)送帶寬，Trafj(t)為節(jié)點j需要在t時間片發(fā)送的負(fù)載量。因此式(3)可表示剩余帶寬在不同區(qū)間內(nèi)的父節(jié)點帶寬的寬裕程度，分別定義為：過度寬裕、寬裕、小型擁塞、中型擁塞、大型擁塞。

(2)動作空間

節(jié)點的動作為節(jié)點負(fù)載分配的比例，因此定義式(1)中

(5)

(6)

式(6)表示節(jié)點的負(fù)載分配比例可從式中的范圍進(jìn)行取值。

(3)獎賞反饋

子節(jié)點負(fù)載分配后，父節(jié)點的帶寬情況會發(fā)生變化，節(jié)點的狀態(tài)也會隨之發(fā)生轉(zhuǎn)變。本文算法的目標(biāo)為平衡父節(jié)點的負(fù)載量，并且節(jié)點狀態(tài)可表征父節(jié)點的負(fù)載量情況，因此本文通過下一時間片的節(jié)點狀態(tài)獲取獎賞反饋，作為當(dāng)前時間片負(fù)載分配動作所獲得收益的表征。本文將狀態(tài)與反饋之間進(jìn)行如下轉(zhuǎn)換

(7)

其中，j和k為節(jié)點i的父節(jié)點ID，R為算法參數(shù)，表示獎賞反饋的基數(shù)。式(7)中分式(a)-(c)表示當(dāng)兩個父節(jié)點的帶寬情況不均衡時，如一個帶寬寬裕，而另一個出現(xiàn)不同程度擁塞，節(jié)點對應(yīng)的狀態(tài)轉(zhuǎn)換為負(fù)向反饋，反之，分式(d)-(g)表示當(dāng)兩者情況接近一致時，節(jié)點的狀態(tài)轉(zhuǎn)換為正向反饋。

2 基于強化學(xué)習(xí)的負(fù)載均衡路由

本文路由算法主要包括兩個部分：一個是對Q-Lear-ning中狀態(tài)-動作值函數(shù)(Q函數(shù))的學(xué)習(xí)，Q函數(shù)表示不同狀態(tài)下采取不同動作的收益期望值，學(xué)習(xí)收斂后可用以指導(dǎo)負(fù)載分配的比例選擇；另一個是基于演化博弈論的Q-Learning探索策略，探索策略指在學(xué)習(xí)過程中對動作空間的動作進(jìn)行嘗試與探索的方法與規(guī)則，適當(dāng)?shù)奶剿鞑呗钥梢约涌焖惴ㄌ剿魇諗康乃俣?。本?jié)最后對Q函數(shù)收斂速度與獎賞參數(shù)大小之間的關(guān)系進(jìn)行了分析。

2.1 Q函數(shù)的計算與負(fù)載分配

強化學(xué)習(xí)的目的是使節(jié)點得到在當(dāng)前狀態(tài)下應(yīng)當(dāng)選取何種動作的策略，Q-Learning將Q函數(shù)作為一種確定性策略，每一個狀態(tài)-動作對都可通過Q函數(shù)映射到一個值，表征該狀態(tài)下該動作的收益期望值，并使用映射表的形式對Q函數(shù)進(jìn)行表達(dá)，如圖2所示。

圖2 Q函數(shù)的狀態(tài)-動作映射表

圖2中的x表示狀態(tài)，a表示動作，value為一個狀態(tài)-動作對所對應(yīng)的Q函數(shù)的值。Q函數(shù)學(xué)習(xí)收斂后，節(jié)點通過查找當(dāng)前狀態(tài)下具有最大Q函數(shù)值的動作，選擇當(dāng)前狀態(tài)下最優(yōu)的分配比例。

在算法初始時，節(jié)點i具有初始的探索策略Si(0)，本文采取的探索策略將在2.2節(jié)中進(jìn)行描述，為學(xué)習(xí)過程中每個時間片節(jié)點選取決策動作時所依據(jù)的規(guī)則方法。

在每個時間片t內(nèi)，節(jié)點根據(jù)一跳的信息交互獲取父節(jié)點的剩余帶寬，并根據(jù)式(2)、式(3)構(gòu)成自身的狀態(tài)，xi(t)，再通過當(dāng)前探索策略Si(t)與狀態(tài)xi(t)選取當(dāng)前時間片段采取的動作ai(t)，然后在下一時間t+1內(nèi)，根據(jù)獲取的狀態(tài)xi(t+1)與式(7)計算t時間片采取動作ai(t)所獲得的獎賞反饋ui(t)，并根據(jù)Q-Learning算法更新Q函數(shù)，如式(8)所示

(8)

上述的負(fù)載分配路由算法具體流程如算法1所示，包括學(xué)習(xí)中和學(xué)習(xí)后兩個過程，學(xué)習(xí)中節(jié)點使用探索策略進(jìn)行對動作空間的探索和學(xué)習(xí)，并更新Q函數(shù)；學(xué)習(xí)后節(jié)點使用Q函數(shù)，選擇當(dāng)前狀態(tài)下具有最大Q函數(shù)值的動作作為當(dāng)前的負(fù)載分配決策動作。

算法1：負(fù)載分配路由算法

輸入：節(jié)點IDi

初始時刻t

初始Q值表Qt(x,a)

初始化探索策略Si(t)

設(shè)定訓(xùn)練輪數(shù)上限T

流程：

(1)初始時均勻分配負(fù)載，進(jìn)行負(fù)載傳輸；

(2)t=t+1；

repeat

(4)根據(jù)探索策略Si(t)，選取負(fù)載分配動作ai(t)，并按照比例傳輸負(fù)載；

(5)t′=t+1；

(7)根據(jù)xi(t′)與式(7)計算t時刻獎賞ui(t)；

(8)根據(jù)式(8)更新Q值；

(9)更新xi(t)=xi(t′)，t=t′

untilt>T或 Q函數(shù)收斂

repeat

(10)獲取t時刻及節(jié)點狀態(tài)xi(t)

(12)t=t+1

end

2.2 基于演化博弈論的Q-Learning探索策略

當(dāng)Q函數(shù)收斂后，可作為指導(dǎo)動作選擇的確定性策略，但如果在學(xué)習(xí)時每次僅選用Q函數(shù)值最大的動作，算法難以獲得其它動作可能取得的收益信息，容易限于局部最優(yōu)，因此在學(xué)習(xí)過程中仍需要對動作空間中其它動作進(jìn)行嘗試與探索。Q-Learning中常用的對動作探索策略為ε貪心探索策略，但ε作為一個固定值，在學(xué)習(xí)前期和學(xué)習(xí)后期對于動作空間進(jìn)行探索的概率都一致，并且對于期望收益不同的動作進(jìn)行探索的概率也一致，可能會造成對已知收益較低的動作進(jìn)行多次重復(fù)探索，對收益較高的動作探索不足，使得算法收斂變慢。

本文為了加快學(xué)習(xí)收斂速度，通過演化博弈論，將探索策略建模為博弈論中的混合策略，通過概率對動作進(jìn)行探索，并通過收益的期望值對探索策略中的概率值進(jìn)行調(diào)整。

在演化博弈中，一個群體中具有多個個體，每個個體具有相同的動作空間，選取不同動作的個體比例構(gòu)成該群體的一種混合策略，根據(jù)學(xué)習(xí)過程中得到的獎賞反饋，將具有更高獎賞收益動作的個體比例逐漸增加，反之減少，直到混合策略達(dá)到均衡狀態(tài)[17]。本文將每個節(jié)點視為演化博弈中具有混合策略和多個虛擬個體的決策群體，將每個節(jié)點的探索策略建模為混合策略并利用表征動作收益期望值的Q函數(shù)有方向地調(diào)節(jié)探索策略。

由式(5)、式(6)可知動作空間中有5種動作，定義探索策略為

Si={p1,pm,…,p5}

(9)

式中：Si為節(jié)點i的探索策略，pm為動作空間A中第m個動作aim被探索選中的概率，同時滿足條件

∑aim∈Apm=1

(10)

算法1以式(9)作為探索策略選取動作ai(t)時，根據(jù)動作所對應(yīng)的概率來進(jìn)行隨機選取，以概率的形式對動作空間進(jìn)行探索。

在初始時，節(jié)點的探索策略被設(shè)置為均勻概率分布，如式(11)所示

(11)

在學(xué)習(xí)開始后，概率根據(jù)演化博弈論進(jìn)行調(diào)整，遵循復(fù)制者動態(tài)方程，即動作選取的概率對時間的導(dǎo)數(shù)與該動作收益期望以及整體混合策略的收益期望相關(guān)

(12)

式中：E(R(am))表示第m個動作的收益期望，E(R(Si))表示混合策略的收益期望。

在本文中，Q值作為不同動作的收益期望的一種量化，并且訓(xùn)練過程的時間維度為離散的時間片段，因此在Q函數(shù)進(jìn)行式(8)的更新后，同時對探索策略的概率進(jìn)行如式(13)的演化

Δpm=[Q(x,am)-∑ak∈Apk×Q(x,ak)]×pm

(13)

式中：Δpm表示第m個動作對應(yīng)與探索策略中的概率的變化值，Q(x,am)表示第m個動作在當(dāng)前狀態(tài)下的Q值，∑ak∈Apk×Q(x,ak)表示當(dāng)前狀態(tài)下所有動作取得Q值的期望。因此探索策略的總體演化為

Si={p1+Δp1,p2+Δp2,…,p5+Δp5}

(14)

式(14)表示負(fù)載分配路由算法每次Q函數(shù)迭代后，每個動作被探索到的概率都依據(jù)式(13)、式(14)進(jìn)行改變。

2.3 獎賞參數(shù)R對Q函數(shù)收斂速度的影響分析

在式(13)中，更新速度Δpm與Q值有關(guān)，且在式(7)、式(8)中，參數(shù)R對Q值的計算有著很大的影響。為了更好選擇參數(shù)，本文分析了更新速度Δpm與參數(shù)R的關(guān)系。

假設(shè)每次選擇時均選中了同一個動作決策，并且該動作恰好可以帶來正向獎賞，狀態(tài)同時也轉(zhuǎn)移至同一狀態(tài)。在該假設(shè)中每次嘗試都使得探索策略往同一個方向改進(jìn)，可以計算得理論上的最大更新速度。

設(shè)初始狀態(tài)的Q值為0，因為狀態(tài)轉(zhuǎn)移至同一狀態(tài)，我們使用Qt表示Qt(xi(t),ai(t))，且由于均選中同一動作，可以得知

(15)

可以根據(jù)式(8)、式(15)得到Q值的迭代公式

Q1=αR

(16)

Qt=(1-α)Qt-1+α(u+γQt-1)=
αR+(1-α+αγ)Qt-1=
Q1+kQt-1

(17)

其中，k=1-α+αγ。

通過迭代式(17)可以計算得序列的通項公式

Qt=(1+k1+k2+…+kt-1)Q1

(18)

根據(jù)式(13)、式(18)可得概率隨時間的變化值為

(19)

式中:Δpm,t為第m個動作的探索概率在時間t時的變化值，pm,t為第m個動作在時間t時的探索概率。

本文通過式(19)建立策略更新速率與獎賞參數(shù)R之間的關(guān)系，并設(shè)置不同的參數(shù)取值進(jìn)行分析，如圖3所示。

圖3 參數(shù)R對收斂速度的影響

圖3中算法初始參數(shù)設(shè)定為，pm,0=0.2，α=0.7，γ=0.1，并通過式(19)計算收斂速度的理論值。圖中的縱軸為選中的動作被探索的概率，當(dāng)概率為1時，算法結(jié)束探索。通過圖3可得出，隨著R值增大，算法的收斂速度變快。在實際應(yīng)用中，并不能保證每次都選中最優(yōu)的正向決策，因此收斂更新的速率會慢于式(19)中的Δpm,t。

3 仿真與結(jié)果分析

首先，為了驗證本文算法的性能并分析直觀的迭代學(xué)習(xí)過程，以圖1的示例場景對算法進(jìn)行仿真，并與其它算法進(jìn)行比較。設(shè)單位時間片表示為T，節(jié)點產(chǎn)生數(shù)據(jù)的數(shù)率為5 kb/T，節(jié)點發(fā)送帶寬為20 kb/T。其它算法分別為：DBR[9](節(jié)點不考慮負(fù)載均衡，根據(jù)深度信息轉(zhuǎn)發(fā)報文)；L2-LBMT[18](節(jié)點使用固定的負(fù)載均衡決策，每個節(jié)點決策不同)；Average Alloc(節(jié)點使用平均分配的負(fù)載均衡方案，每個節(jié)點決策相同)。仿真結(jié)果如圖4所示。

圖4 網(wǎng)絡(luò)傳輸效率

圖4展示了每一個時間片內(nèi)的網(wǎng)絡(luò)傳輸效率，即網(wǎng)絡(luò)吞吐量與網(wǎng)絡(luò)節(jié)點生成總負(fù)載量的比率，反映了網(wǎng)絡(luò)的擁塞情況，傳輸效率越高，則網(wǎng)絡(luò)的丟包率越少、吞吐量越高。圖中本文算法(QL+EVO)的傳輸效率在初始時有所波動，然后逐漸上升并收斂穩(wěn)定在高于其它算法的效率值。這是由于本文算法中節(jié)點在初期進(jìn)行探索不同分配決策，造成了效率波動，但節(jié)點在算法收斂后，采取期望收益最佳的決策，使得整體網(wǎng)絡(luò)傳輸效率提高。

為了分析基于演化博弈論的探索策略對算法學(xué)習(xí)收斂速度的影響，我們在圖1場景下仿真比較本文算法與使用ε貪心探索策略的Q-Learning算法(QL Only)，結(jié)果如圖5所示。

圖5 收斂速度比較

圖5中，本文算法的傳輸效率更快地進(jìn)入收斂狀態(tài)，并且具有與QL Only 一致的網(wǎng)絡(luò)性能，原因在于演化博弈論指導(dǎo)探索策略朝著收益更高的方向進(jìn)行更新，減少了已知收益不佳的動作被探索的概率，提高了學(xué)習(xí)利用效率。圖4、圖5中的實驗結(jié)果表明本文的算法較之其它算法有著更好的性能表現(xiàn)與更快的收斂速度。

其次，為了驗證圖3中對參數(shù)R與算法收斂速度關(guān)系的分析，本文選取不同的R值在圖1場景中對算法進(jìn)行仿真，得到如圖6所示結(jié)果。

圖6 不同獎賞參數(shù)的實際性能

在圖6中，算法的收斂趨勢與圖3相近，R值越大，算法收斂速度越快。但如果R取值過大，如在本次實驗設(shè)置下R取0.4時，由于迭代次數(shù)減少，過早結(jié)束探索，算法容易陷入局部解。

再次，為了評估算法在不同場景下的適用性，本文隨機生成了具有不同節(jié)點個數(shù)、不同層數(shù)的網(wǎng)絡(luò)場景進(jìn)行算法仿真。由于隨機生成的場景中節(jié)點分布可能十分不均勻，導(dǎo)致網(wǎng)絡(luò)即使進(jìn)行全局最優(yōu)的負(fù)載分配時，網(wǎng)絡(luò)傳輸效率仍然較低，不利于統(tǒng)一評價不同場景中的算法性能，因此本文通過算法性能與全局最優(yōu)性能的比率作為評估指標(biāo)。

計算全局最優(yōu)值時，本文根據(jù)全局信息將問題轉(zhuǎn)換為最大流問題。將每個源節(jié)點替換為一個輸出節(jié)點、一個輸入節(jié)點和一個源節(jié)點。輸入和輸出節(jié)點中通過一條容量為節(jié)點帶寬限制的有向邊連接，源節(jié)點和輸入節(jié)點通過一條容量為節(jié)點數(shù)據(jù)生成數(shù)率的有向邊連接。原拓?fù)渲械倪呥B接子節(jié)點的輸出節(jié)點和父節(jié)點的輸入節(jié)點，并具有無限制的容量。

本文使用程序隨機生成了具有20、30、50個傳感節(jié)點的網(wǎng)絡(luò)場景，分別構(gòu)成4、4、5層的拓?fù)鋵蛹墸瑢τ诓煌膱鼍吧闪?0種不同的拓?fù)浣Y(jié)構(gòu)，并對每種拓?fù)浣Y(jié)構(gòu)進(jìn)行了5次實驗，取多次實驗的平均值。結(jié)果如圖7所示。

圖7 傳輸效率性能比較

圖7中簡單例子場景為圖1所示場景，結(jié)果表明，本文算法在不同規(guī)模的拓?fù)浣Y(jié)構(gòu)下的多次實驗中取得了比其它算法更高的傳輸效率，并且性能接近于最優(yōu)值。這是由于算法通過強化學(xué)習(xí)，可以使節(jié)點在不同場景拓?fù)渲?，自適應(yīng)地采取適合當(dāng)前拓?fù)涞呢?fù)載分配決策。此外，分析多次實驗結(jié)果的中位數(shù)可以發(fā)現(xiàn)，通過與最優(yōu)值比較歸一化，中位數(shù)等于1，表示本文算法可以在多數(shù)的場景拓?fù)湎氯〉米顑?yōu)值。

最后，本文在上述多場景中評估算法在能量消耗方面的性能。本文設(shè)定節(jié)點發(fā)送單位數(shù)據(jù)的能量消耗一致，通過網(wǎng)絡(luò)中節(jié)點能量消耗的方差，評價算法能量消耗的均衡性能。實驗將仿真中具有最高方差的算法結(jié)果歸一化至1，如圖8所示。

圖8 能量消耗性能比較

圖8中本文算法取得了較低的能量消耗方差，但是略高于Average Alloc算法的方差，這是由于本文算法同時關(guān)注負(fù)載的均衡性能與負(fù)載的傳輸效率性能，因此能量消耗均衡性略差于平均負(fù)載分配的算法，但仍優(yōu)于其它算法，平衡了節(jié)點間的能量消耗，有利于延長網(wǎng)絡(luò)的生存時間。

4 結(jié)束語

針對水下無線傳感網(wǎng)環(huán)境多變、全局信息更新獲取困難、交互信息消耗大的特點，本文提出了一種基于強化學(xué)習(xí)的分布式水下負(fù)載均衡路由算法。

本文將負(fù)載均衡問題建模為強化學(xué)習(xí)模型，建立了問題模型的狀態(tài)空間、動作空間等強化學(xué)習(xí)和馬爾科夫決策過程的要素。通過對歷史網(wǎng)絡(luò)狀態(tài)信息的學(xué)習(xí)，使節(jié)點具有分布式負(fù)載分配決策能力，同時有效減少了信息交互。本文聯(lián)合了強化學(xué)習(xí)與演化博弈論對算法的探索策略進(jìn)行調(diào)整，加快了強化學(xué)習(xí)的探索收斂速度。

通過對不同的場景進(jìn)行的仿真驗證，本文提出的算法提高了網(wǎng)絡(luò)傳輸效率，優(yōu)化了網(wǎng)絡(luò)能量消耗的均衡性，本文的下一步工作在于將算法應(yīng)用于大規(guī)模的動態(tài)場景，提高算法的適用性。