葉曉涵，李德識(shí)

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

0 引 言

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

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

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

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

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

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

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

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

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

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

1.2 問題描述與建模

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

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

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

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

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

(1)

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

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

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

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

(2)

(3)

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

Bw_mj(t)=Bwj-Trafj(t)

(4)

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

(2)動(dòng)作空間

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

(5)

(6)

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

(3)獎(jiǎng)賞反饋

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

(7)

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

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

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

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

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

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

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

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

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

(8)

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

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

輸入：節(jié)點(diǎn)IDi

初始時(shí)刻t

初始Q值表Qt(x,a)

初始化探索策略Si(t)

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

流程：

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

(2)t=t+1；

repeat

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

(5)t′=t+1；

(7)根據(jù)xi(t′)與式(7)計(jì)算t時(shí)刻獎(jiǎng)賞ui(t)；

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

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

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

repeat

(10)獲取t時(shí)刻及節(jié)點(diǎn)狀態(tài)xi(t)

(12)t=t+1

end

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

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

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

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

由式(5)、式(6)可知?jiǎng)幼骺臻g中有5種動(dòng)作，定義探索策略為

Si={p1,pm,…,p5}

(9)

式中：Si為節(jié)點(diǎn)i的探索策略，pm為動(dòng)作空間A中第m個(gè)動(dòng)作aim被探索選中的概率，同時(shí)滿足條件

∑aim∈Apm=1

(10)

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

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

(11)

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

(12)

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

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

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

(13)

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

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

(14)

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

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

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

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

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

(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)可以計(jì)算得序列的通項(xiàng)公式

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

(18)

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

(19)

式中:Δpm,t為第m個(gè)動(dòng)作的探索概率在時(shí)間t時(shí)的變化值，pm,t為第m個(gè)動(dòng)作在時(shí)間t時(shí)的探索概率。

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

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

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

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

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

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

圖4展示了每一個(gè)時(shí)間片內(nèi)的網(wǎng)絡(luò)傳輸效率，即網(wǎng)絡(luò)吞吐量與網(wǎng)絡(luò)節(jié)點(diǎn)生成總負(fù)載量的比率，反映了網(wǎng)絡(luò)的擁塞情況，傳輸效率越高，則網(wǎng)絡(luò)的丟包率越少、吞吐量越高。圖中本文算法(QL+EVO)的傳輸效率在初始時(shí)有所波動(dòng)，然后逐漸上升并收斂穩(wěn)定在高于其它算法的效率值。這是由于本文算法中節(jié)點(diǎn)在初期進(jìn)行探索不同分配決策，造成了效率波動(dòng)，但節(jié)點(diǎn)在算法收斂后，采取期望收益最佳的決策，使得整體網(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)行更新，減少了已知收益不佳的動(dòng)作被探索的概率，提高了學(xué)習(xí)利用效率。圖4、圖5中的實(shí)驗(yàn)結(jié)果表明本文的算法較之其它算法有著更好的性能表現(xiàn)與更快的收斂速度。

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

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

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

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

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

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

圖7 傳輸效率性能比較

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

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

圖8 能量消耗性能比較

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

4 結(jié)束語

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

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

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