侯睿，何柳婷

(中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢 430074)

由于全世界海洋面積約占地球表面積的71%，并且在海洋當(dāng)中蘊(yùn)含著豐富的資源，近些年，水聲通信越來越成為了一個(gè)新的研究熱點(diǎn).水聲傳感器網(wǎng)絡(luò)(UASN, Underwater Acoustic Sensor Network)[1,2]是水下聲學(xué)通信技術(shù)結(jié)合無線傳感器網(wǎng)絡(luò)(WSN,Wireless Sensor Network)[3]所產(chǎn)生的一個(gè)新的研究方向.目前該技術(shù)廣泛應(yīng)用于海洋的定期監(jiān)測以及海洋數(shù)據(jù)采集等方面.但是，由于水下環(huán)境復(fù)雜多變，使得傳感器節(jié)點(diǎn)更換新的電池或者再次充電非常困難，因此如何降低UASN能量消耗，已經(jīng)成為該領(lǐng)域的熱點(diǎn)問題.目前針對(duì)UASN能耗優(yōu)化方面，已經(jīng)有不少關(guān)于聚類算法以及路由算法方面的研究.

1 相關(guān)研究工作

近些年，聚類算法已經(jīng)廣泛應(yīng)用于無線傳感器網(wǎng)絡(luò)中.文獻(xiàn)[4]提出了一種低能耗自適應(yīng)集群分層型協(xié)議(Low Energy Adaptive Clustering Hierarchy, LEACH)，它是針對(duì)無線傳感器網(wǎng)絡(luò)的第一個(gè)分簇路由算法，其采用隨機(jī)分簇策略和周期性簇頭輪換機(jī)制，將整個(gè)傳感器網(wǎng)絡(luò)分成若干個(gè)大小均等的簇，使得網(wǎng)絡(luò)中的所有節(jié)點(diǎn)能量消耗均衡，從而延長網(wǎng)絡(luò)的生命周期.但是，由于簇頭的選擇是隨機(jī)的，這樣低能量的節(jié)點(diǎn)被選為簇頭，很容易造成節(jié)點(diǎn)的過早死亡.文獻(xiàn)[5]提出了一種能量高效的非均勻分簇算法(Energy-Efficient Unequal Clustering, EEUC).在EEUC算法中，每個(gè)節(jié)點(diǎn)先根據(jù)一個(gè)預(yù)先確定的門限，隨機(jī)確定自身能否成為備選簇頭.備選簇頭節(jié)點(diǎn)根據(jù)接收sink節(jié)點(diǎn)信號(hào)強(qiáng)度，選出不同范圍的簇，并在簇內(nèi)選擇能量最大的成為簇頭節(jié)點(diǎn).該算法雖然在一定程度上延長了網(wǎng)絡(luò)生命周期，但實(shí)際操作中比較困難，不利于實(shí)施.文獻(xiàn)[6]提出了一種能量平衡的不等層分簇(Energy-balanced Unequal Layering Clustering, EULC)路由算法，它根據(jù)節(jié)點(diǎn)的深度網(wǎng)絡(luò)被劃分為不同寬度的層，較淺的層的寬度比較深的層要小.并且通過根據(jù)節(jié)點(diǎn)與sink節(jié)點(diǎn)的距離來調(diào)整傳輸功率，從而緩解了“熱點(diǎn)”問題.“熱點(diǎn)”問題是指在網(wǎng)絡(luò)中，一些節(jié)點(diǎn)可能在數(shù)據(jù)傳輸中過多地消耗能量而導(dǎo)致過早死亡，從而使整個(gè)網(wǎng)絡(luò)癱瘓，無法正常工作的問題.

針對(duì)路由算法方面的研究，傳統(tǒng)的路由算法雖然能很好地提高網(wǎng)絡(luò)性能，但由于其處理多個(gè)約束的能力和較高的計(jì)算復(fù)雜度仍然受到限制.近年來，已有許多基于智能算法的路由方案被提出用于地面無線傳感器網(wǎng)絡(luò)，但這些算法很少被應(yīng)用于UASN中.近幾年，增強(qiáng)學(xué)習(xí)領(lǐng)域的研究有了很大的發(fā)展.目前，已經(jīng)有一些針對(duì)單個(gè)節(jié)點(diǎn)的路徑優(yōu)化方案被提出，文獻(xiàn)[7]發(fā)現(xiàn)基于增強(qiáng)學(xué)習(xí)的路由優(yōu)化不僅要考慮到達(dá)目的地的跳數(shù)，還要考慮流量阻塞的貢獻(xiàn)，考慮每個(gè)節(jié)點(diǎn)的隊(duì)列長度對(duì)延遲的影響，從而確定最佳路由路徑.文獻(xiàn)[8]提出了一種基于機(jī)器學(xué)習(xí)的高效壽命擴(kuò)展水下傳感器網(wǎng)絡(luò)自適應(yīng)路由算法(Q-learning based Energy-efficient and Lifetime-extended Adaptive Routing, QELAR)，該算法將Q學(xué)習(xí)技術(shù)應(yīng)用于UASN的分布式路由算法中，以平衡傳感器節(jié)點(diǎn)之間的工作負(fù)載，降低網(wǎng)絡(luò)開銷，提高能源效率，延長網(wǎng)絡(luò)壽命.但是，目前基于增強(qiáng)學(xué)習(xí)的路由優(yōu)化算法主要運(yùn)用于單個(gè)節(jié)點(diǎn)的路徑優(yōu)化上，用在集群之間的路徑優(yōu)化研究非常少.

針對(duì)現(xiàn)有的水聲傳感器網(wǎng)絡(luò)聚類算法在簇的形成以及路由優(yōu)化方面的不足，本文設(shè)計(jì)了一種基于增強(qiáng)學(xué)習(xí)的能量消耗非均勻分簇算法(Energy-consumption of Unequal Clustering based on Reinforcement Learning, EUCRL).該算法首先根據(jù)水聲傳感器網(wǎng)絡(luò)的深度和剩余能量把傳感器節(jié)點(diǎn)分成大小不同的簇.同時(shí)在數(shù)據(jù)傳輸階段利用增強(qiáng)學(xué)習(xí)和ε-greedy策略對(duì)簇間的傳輸路徑進(jìn)行決策和學(xué)習(xí)，選出全局最優(yōu)路徑.實(shí)驗(yàn)結(jié)果表明本文方法可以有效減少數(shù)據(jù)傳輸所帶來的能量消耗.

2 通信模型

為了能夠準(zhǔn)確模擬水下環(huán)境，首先需要對(duì)水聲通信進(jìn)行建模，本文采用文獻(xiàn)中經(jīng)典的水聲通信模型[9]，模型中的參數(shù)定義如下：

發(fā)送節(jié)點(diǎn)的最低發(fā)送功率表示為：

P=PtA,

其中Pt為一個(gè)數(shù)據(jù)包被節(jié)點(diǎn)接收的正常功率，A為傳輸功率隨傳輸距離的衰減量，與傳輸距離、工作頻率以及數(shù)據(jù)的發(fā)送方式有關(guān)，A可表示為：

a=αddk,

其中k為能量擴(kuò)散因子，與信號(hào)傳播條件有關(guān)(在實(shí)際應(yīng)用中常取k=1.5)，d是傳輸距離，衰減系數(shù)α=10a(f)/10，它由吸收損耗a(f)決定，與頻率有關(guān)，a(f)表示為：

其中f為節(jié)點(diǎn)的工作頻率.

當(dāng)傳輸距離為d時(shí)，節(jié)點(diǎn)發(fā)送長度為lbit的數(shù)據(jù)包的能耗為：

ET(l,d)=lPtαddk.

節(jié)點(diǎn)接收長度為lbit的數(shù)據(jù)包的能耗為：

ER(l,d)=lPr,

其中Pr為常數(shù).

3 EUCRL路由算法

3.1 計(jì)算節(jié)點(diǎn)的競爭半徑

在聚類算法中，簇頭節(jié)點(diǎn)距離基站越近，需要轉(zhuǎn)發(fā)其他簇頭節(jié)點(diǎn)的數(shù)據(jù)就越多，能耗越大.為了平衡簇頭節(jié)點(diǎn)的能耗，本文使靠近基站的簇范圍更小，也就是在靠近基站的區(qū)域選舉更多的簇頭.因此引入競爭半徑Ri，它綜合考慮了節(jié)點(diǎn)的剩余能量、與基站之間的距離等因素，以控制簇頭節(jié)點(diǎn)的分布，其計(jì)算公式如下：

式中dmax,dmin分別為網(wǎng)絡(luò)中節(jié)點(diǎn)距離基站的最大、最小距離，R0為預(yù)先設(shè)定的最大競爭半徑，Eavg為網(wǎng)絡(luò)中存活節(jié)點(diǎn)的平均剩余能量，λ,μ∈(0,1)是自適應(yīng)系數(shù).

3.2 簇頭的選舉

本文在選舉簇頭時(shí)，綜合考慮節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)到基站的距離以及節(jié)點(diǎn)度因素，選出綜合屬性值最高的節(jié)點(diǎn)為簇頭，具體計(jì)算公式如下：

其中Eres為節(jié)點(diǎn)的剩余能量，Eint為節(jié)點(diǎn)的初始能量，Ni為節(jié)點(diǎn)度.

3.3 簇間數(shù)據(jù)傳輸

在本算法中，簇內(nèi)節(jié)點(diǎn)采用單跳的方式進(jìn)行數(shù)據(jù)傳輸，簇間采用單跳和多跳結(jié)合的方式進(jìn)行數(shù)據(jù)傳輸.在簇間數(shù)據(jù)傳輸中，使用增強(qiáng)學(xué)習(xí)中的Q學(xué)習(xí)方法對(duì)路由進(jìn)行選擇，每個(gè)簇頭從候選中繼簇頭中選擇Q值最大的作為下一跳，以此不斷地將數(shù)據(jù)轉(zhuǎn)發(fā)至基站.增強(qiáng)學(xué)習(xí)具體工作原理如圖1所示，每個(gè)傳感器節(jié)點(diǎn)相當(dāng)于一個(gè)智能體Agent，當(dāng)節(jié)點(diǎn)做出路由動(dòng)作action后，環(huán)境將返回Agent一個(gè)獎(jiǎng)勵(lì)值，發(fā)送方節(jié)點(diǎn)將會(huì)更新自己的狀態(tài).

圖1 增強(qiáng)學(xué)習(xí)工作原理Fig.1 Working principle of reinforcement learning

簇頭i的候選中繼節(jié)點(diǎn)集合定義如下：

si-j={sj|d(sj,sink)

其中d(si,sink)，d(sj,sink)分別表示簇頭si，sj到基站的距離，若d(sj,sink)

在路由選擇中，每個(gè)節(jié)點(diǎn)在做出動(dòng)作后將被賦予一個(gè)Q值，其計(jì)算公式如下：

Q(si,ai)=R(si,ai)+γmaxQ(si+1,ai+1).

同時(shí)，因?yàn)樗颅h(huán)境復(fù)雜多變，拓?fù)浣Y(jié)構(gòu)可能隨時(shí)間而不斷變化，本文通過根據(jù)如下Q值更新公式調(diào)整數(shù)據(jù)傳輸路線：

Q(si,ai)←Q(si,ai)+α[R(si,ai)+

γmaxQ(si+1,ai+1)-Q(si,ai)],

其中α為學(xué)習(xí)率，是一個(gè)權(quán)衡上一次學(xué)習(xí)結(jié)果和這一次學(xué)習(xí)結(jié)果的量，γ∈(0,1)為折損因子.

在該算法中，定義了節(jié)點(diǎn)的獎(jiǎng)勵(lì)函數(shù)，其中節(jié)點(diǎn)間距離和鄰居節(jié)點(diǎn)剩余能量都被考慮用于適當(dāng)?shù)穆酚蓻Q策中.獎(jiǎng)勵(lì)函數(shù)R(si,ai)定義如下：

(1)

其中down(j)為鄰居節(jié)點(diǎn)j與sink節(jié)點(diǎn)間的距離，Eres(j)為鄰居節(jié)點(diǎn)j的剩余能量.

在簇間數(shù)據(jù)傳輸中，簇頭節(jié)點(diǎn)首先利用增強(qiáng)Q學(xué)習(xí)算法從備選中繼簇頭中選擇Q值最大的節(jié)點(diǎn)為下一跳節(jié)點(diǎn).除此之外，本文在增強(qiáng)學(xué)習(xí)的基礎(chǔ)上采用一種基于ε-greedy的策略.該策略的使用，使節(jié)點(diǎn)保持(1-ε)的概率直接選擇具有最大Q值的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)，同時(shí)有ε的概率隨機(jī)選擇下一跳節(jié)點(diǎn).這樣做的目的是：水下環(huán)境復(fù)雜多變，所以選擇的具有最大Q值的路徑在數(shù)據(jù)傳輸中不一定是全局最優(yōu)路徑.通過利用ε-greedy策略可以很好地平衡隨機(jī)和貪婪的比率，讓網(wǎng)絡(luò)跳出局部最優(yōu)，實(shí)現(xiàn)真正意義上的全局最優(yōu)，并加快網(wǎng)絡(luò)收斂速度.

基于增強(qiáng)學(xué)習(xí)的ε-greedy策略路由決策π(s)選擇定義如下：

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)配置

為了驗(yàn)證EUCRL算法的有效性，本文利用Matlab[10]構(gòu)建水聲傳感器網(wǎng)絡(luò)仿真環(huán)境，設(shè)定節(jié)點(diǎn)在網(wǎng)絡(luò)中隨機(jī)分布，sink節(jié)點(diǎn)為所有數(shù)據(jù)包傳輸?shù)哪康牡?實(shí)驗(yàn)具體參數(shù)配置見表1.

表1 仿真參數(shù)的配置Tab.1 Configuration of simulation parameters

4.2 實(shí)驗(yàn)結(jié)果與分析

本文實(shí)驗(yàn)分為兩部分.第一部分實(shí)驗(yàn)，是對(duì)(1)式獎(jiǎng)勵(lì)函數(shù)中的加權(quán)因子α，β對(duì)網(wǎng)絡(luò)性能的影響進(jìn)行實(shí)驗(yàn)，并分析加權(quán)因子α，β的設(shè)置對(duì)網(wǎng)絡(luò)中包的到達(dá)率以及能量消耗的影響.第二部分實(shí)驗(yàn)是本文算法與LEACH,QELAR的對(duì)比實(shí)驗(yàn)，通過實(shí)驗(yàn)結(jié)果驗(yàn)證本文算法的有效性.

4.2.1α，β對(duì)網(wǎng)絡(luò)性能的影響

圖2為加權(quán)因子α對(duì)網(wǎng)絡(luò)中數(shù)據(jù)包到達(dá)率以及能量消耗的影響.如圖所示，隨著α的增加，數(shù)據(jù)包的到達(dá)率逐漸增高.但是，由于選擇出的下一跳時(shí)沒有充分考慮節(jié)點(diǎn)的剩余能量，因此網(wǎng)絡(luò)中的能量消耗越來越高.

圖2 α對(duì)網(wǎng)絡(luò)性能的影響Fig.2 Effect of α on network performance

如圖3所示，加權(quán)因子β反應(yīng)了節(jié)點(diǎn)剩余能量對(duì)于路由選擇的重要程度.隨著β的增加，節(jié)點(diǎn)逐漸傾向于選擇剩余能量較大的節(jié)點(diǎn)作為下一跳，而忽略了節(jié)點(diǎn)間距離這一約束條件，這樣將增加所選路徑不是最短路徑的可能.因此，根據(jù)實(shí)驗(yàn)結(jié)果可以看出，隨著β的增加，節(jié)點(diǎn)的能量消耗逐漸變大，而數(shù)據(jù)包的到達(dá)率卻逐漸減小.

圖3 β對(duì)網(wǎng)絡(luò)性能的影響Fig.3 Effect of β on network performance

4.2.2 算法比較

如圖4所示，通過對(duì)比LEACH,QELAR和EUCRL三種算法，可以看出本文所提出的能耗優(yōu)化EUCRL算法可以有效平衡水下傳感器網(wǎng)絡(luò)的能量消耗，并延長了網(wǎng)絡(luò)生命周期.

圖4 網(wǎng)絡(luò)能耗情況對(duì)比Fig.4 Comparison of network energy consumption

圖5為EUCRL，LEACH，QELAR三種算法基站接收節(jié)點(diǎn)數(shù)據(jù)包個(gè)數(shù)的對(duì)比情況.如圖所示，在節(jié)點(diǎn)未出現(xiàn)死亡之前，三種算法節(jié)點(diǎn)發(fā)送到基站的數(shù)據(jù)包數(shù)相同，但由于本文EUCRL算法使用非均勻分簇使得均衡能耗效果優(yōu)于其他兩種算法，并且節(jié)點(diǎn)死亡輪數(shù)晚于其他兩種算法, 所以由實(shí)驗(yàn)結(jié)果可以看出本文所提出的EUCRL算法可以有效提高網(wǎng)絡(luò)中數(shù)據(jù)包的接收率.

圖5 sink節(jié)點(diǎn)接收數(shù)據(jù)量情況對(duì)比Fig.5 Comparison of the amount of data received by sink node

5 結(jié)語

本文針對(duì)水下通信提出了一種基于增強(qiáng)學(xué)習(xí)的非均勻分簇的水聲傳感器網(wǎng)絡(luò)能耗優(yōu)化算法.該方法通過對(duì)水下傳感器進(jìn)行非均勻分簇，使簇頭分布更加合理，有效平衡了水下傳感器網(wǎng)絡(luò)的能量消耗；同時(shí)，通過利用增強(qiáng)學(xué)習(xí)和ε-greedy策略對(duì)簇間路徑的學(xué)習(xí)及預(yù)測，顯著降低了數(shù)據(jù)傳輸路徑的復(fù)雜度，減少了數(shù)據(jù)傳輸時(shí)的能量消耗，延長了網(wǎng)絡(luò)壽命.