侯睿，何柳婷

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

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

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

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

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

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

2 通信模型

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

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

P=PtA,

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

a=αddk,

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

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

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

ET(l,d)=lPtαddk.

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

ER(l,d)=lPr,

其中Pr為常數(shù).

3 EUCRL路由算法

3.1 計算節(jié)點的競爭半徑

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

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

3.2 簇頭的選舉

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

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

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

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

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

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

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

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

在路由選擇中，每個節(jié)點在做出動作后將被賦予一個Q值，其計算公式如下：

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

同時，因為水下環(huán)境復(fù)雜多變，拓撲結(jié)構(gòu)可能隨時間而不斷變化，本文通過根據(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í)率，是一個權(quán)衡上一次學(xué)習(xí)結(jié)果和這一次學(xué)習(xí)結(jié)果的量，γ∈(0,1)為折損因子.

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

(1)

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

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

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

4 實驗與分析

4.1 實驗配置

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

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

4.2 實驗結(jié)果與分析

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

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

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

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

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

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

4.2.2 算法比較

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

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

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

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

5 結(jié)語

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