能耗均衡與節能的自適應水下路由協議

趙德騰，王 敏，2+，劉 淳

(1.云南師范大學 信息學院，云南 昆明 650500；2.云南師范大學 民族教育信息化教育部重點實驗室，云南 昆明 650500)

0 引 言

近些年，隨著人類社會對海洋資源勘探和開發的興趣越來越大，水下傳感器網絡(underwater sensor networks，UWSNs)作為一種新型的無線傳感器網絡，在諸多水下應用中發揮重要作用[1，2]。UWSNs是由大量傳感器節點，包括普通節點和目的節點(又稱sink節點)組成的無線自組網絡，主要通過聲波傳輸數據。相比于陸地環境，水下條件惡劣[3，4]，更換節點電池的難度很大[5，6]，均衡和降低節點能耗[7，8]以延長網絡壽命[9]尤為重要。

為了降低網絡能耗，Xie P等提出了VBF，該協議采用源節點到sink節點的路由管道限制可轉發數據包的節點，有效減少了網絡中的重復數據包，從而降低了網絡能耗，但是提前預定的路由管道半徑，不能很好地適應不同規模的網絡。為了均衡節點能耗，Xiao X等提出了LE-VBF，通過感知相鄰節點的能量信息，根據節點的剩余能量來決定是否參與傳輸，如果該節點的剩余能量超過其鄰居節點的平均剩余能量，則轉發數據包，否則，丟棄數據包，但是相鄰節點間的頻繁通信會產生較高的能耗和數據碰撞。Wei B等提出了ES-VBF，該協議按照節點剩余能量與原始能量的比值采用不同函數設置發包等待時間，比值較高的節點優先發包，以均衡節點能耗，但無法均衡采用同一函數設置發包等待時間的節點之間的能耗。為了降低能耗和提高投遞率，文獻[10]提出了依賴于環境大小、節點傳輸范圍和節點總數的可變管道，根據網絡密度按比例改變路由管道半徑，從而在節點密集的網絡中降低能耗，在節點稀疏的網絡中提高投遞率，但由于網絡中的節點分布是不均勻的，可能無法達到較好的效果。Yu H等提出了AHH-VBF，通過逐跳改變路由管道的方向和半徑，保證節點稀疏區域的傳輸可靠性，減少節點密集區域的重復數據包，但每一跳的計算量較大。ALRP[11]將節點通信范圍內面向sink節點方向的區域作為候選轉發區域，在候選轉發區域內，越靠近sink節點的節點，被選為下一跳轉發節點的可能性越大，ALRP不需要尋找最優管道半徑，但是候選轉發區域的大小固定，難以適應不同規模的網絡。

為了增加協議的動態適應性，部分研究人員將強化學習(reinforcement learning，RL)應用到UWSNs[12-14]，利用Q學習算法，將網絡中的狀態與采取的行為構建成一張Q表來存儲Q值，然后根據Q值來選取能夠獲得最大收益的動作，具有較強的適應性，但每次都需要更新和存儲Q值，增加了復雜性，能耗較大[15]，這對計算能力和能量有限且難以更換電池的UWSNs來說是一個挑戰。

為了進一步均衡和降低UWSNs的能耗，以延長網絡壽命。本文提出能耗均衡與節能的自適應水下路由協議(energy consumption balanced and energy saving adaptive underwater routing protocol，ECBES)。首先，構建雙區非均勻分層拓撲。其次，基于能耗均衡因子，利用拓撲和節點剩余能量計算出節點轉發優先級，實現自適應轉發節點選擇。與此同時，利用策略迭代思想逐步確定最優候選轉發區域。

1 網絡模型

本文UWSNs由多個普通節點和單個sink節點組成。普通節點分為兩種，一種固定在水底，另一種在監測區域中隨機移動。普通節點具有唯一的ID號，可以感知自己的位置以及進行簡單的信息處理。普通節點的計算能力、數據傳輸能力、原始能量大小完全相同。sink節點的能量看作無限，其位于水面，用來接收水下傳來的數據包，并最終將數據包傳遞到陸地基站。sink節點配備了聲學調制解調器和無線電調制解調器，聲學鏈路用于水下通信，無線電鏈路用于地面通信。網絡模型如圖1所示。

圖1 網絡模型

2 ECBES的設計

2.1 問題描述

傳統路由協議一般通過比較節點剩余能量的大小，選擇高剩余能量的節點轉發數據包，以此來均衡能耗，但是容易陷入局部最優，從而導致不同區域間節點的剩余能量相差較大。同時，節點的候選轉發區域大小固定，難以適應不同規模的網絡，若候選轉發區域太大，不斷運動的低優先級節點可能無法收到抑制發包的消息，從而產生大量的重復數據包，導致高能耗。

本文針對傳統水下路由協議能耗不均衡和能量有限的問題，提出能耗均衡與節能的自適應水下路由協議ECBES。

2.2 數據包包頭

ECBES的數據包包頭包括數據包唯一標識(ID)、節點三維位置(position)、節點所處層次(layers)、節點剩余能量(residual energy)以及統計變量range(i)_count字段(僅存在于首輪數據包，在2.5.1節中具體介紹)。包頭格式如圖2所示。

圖2 數據包包頭

2.3 雙區非均勻分層拓撲構建

為了從全局角度緩解能耗不均，減少部分節點因能量耗盡而提前死亡的情況，ECBES構建水下雙區非均勻分層拓撲。圖3是以sink節點為中心的拓撲縱向剖面圖，圖中的監測區域被縱向劃分為主區和副區，水平方向上采用非均勻分層，其中主區用以sink節點為球心的若干球面進行劃分，副區采用平行分層。

圖3 拓撲縱向剖面

如圖3所示，為避免數據轉發集中于某些路徑和區域，造成能耗不均，主區和副區節點采用不同的轉發方向，主區節點優先朝sink節點方向轉發，副區節點優先向副區的上層轉發，并在接近水面時，改朝sink節點方向轉發，以緩解縱向上的節點能耗不均。此外，靠近水面的層中參與轉發的節點更易集中于sink節點附近，需要有更多節點參與數據轉發，以緩解橫向上的節點能耗不均，因此靠近水面的層，體積較大，則候選轉發節點數多。同時考慮到主區和副區節點轉發方向的特點，主區用以sink節點為球心的若干球面進行劃分，副區采用平行分層。

2.4 基于能耗均衡因子的自適應轉發節點選擇

為了均衡網絡能耗，ECBES從全局拓撲和節點剩余能量兩方面計算節點轉發優先級，并根據優先級和隨機小數設置動態等待時間，以抑制低優先級節點轉發數據包，并降低同等優先級節點的重復數據包。

2.4.1 節點轉發優先級

ECBES的節點轉發優先級取決于：①層次大小，使數據包往sink節點方向或較淺方向傳輸；②是否與上一跳節點同區，避免數據轉發集中于某些路徑和區域；③剩余能量大小，均衡局部節點間的能耗。在同一剩余能量情況下，所屬分層的層次越小，轉發優先級越高，在同一分層情況下，與上一跳節點同區的節點，轉發優先級較高。

ECBES將節點通信范圍內，面向sink節點的上半球區域作為節點的候選轉發區域。如圖4所示，節點A1和A2的候選轉發區域為虛線半球區域，其被雙區非均勻分層拓撲分割，其中的阿拉伯數字是不考慮節點剩余能量情況下，各區域節點的轉發優先程度，數字越小，轉發優先級越高。

圖4 轉發節點選擇

計算出節點轉發優先級Pselect之后，與一個隨機數RN∈[β，1) 進行比較，β的最小取值為0，Pselect大則成為候選轉發節點，否則丟棄。因此Pselect越大，成為轉發節點的可能性越大，其值考慮能耗均衡，在ECBES中通過能耗均衡因子α1和α2來綜合設置。Pselect的計算如式(1)所示

(1)

其中，α1考慮全局拓撲層面的能耗均衡，其值如式(2)所示，α2考慮局部節點間的能耗均衡，其值如式(3)所示。α1的取值考慮節點所屬分層層次、與上一跳節點是否同區，α2的取值考慮上下兩跳節點的剩余能量

(2)

其中，layer為候選轉發節點所屬的分層層次，layerlast為上一跳節點所屬的分層層次，K為非負實數。特別地，當處于主區一層的節點收到來自副區二層節點傳來的數據包時α1為1.0

(3)

其中，E為候選轉發節點的剩余能量，Elast為上一跳節點的剩余能量，λ1和λ2為候選轉發節點與上一跳節點剩余能量之比的閾值，剩余能量之比大于λ1的節點在局部區域相對于其它節點能量充足，小于λ2的節點則能量不足，放棄轉發資格。

2.4.2 動態等待時間

為了抑制低優先級節點轉發數據包，并降低同等優先級節點的重復數據包，ECBES根據節點轉發優先級和隨機小數設置動態等待時間T。優先級Pselect越大，動態等待時間T越小，同等優先級的節點通過隨機小數Trn來區分。在動態等待時間T內，如果收到其它節點傳來相同的數據包，則取消等待時間并丟棄該包，否則，時間T到期發包。動態等待時間T的計算如式(4)所示

(4)

此外，每一個轉發節點建立已發送列表，將發送過的數據包ID寫入已發送列表，每次收到數據包后進行對比，如果已發送過此包，則直接丟棄，以防止節點循環轉發此包。

2.5 基于策略迭代思想的候選轉發區域優化

候選轉發區域的大小與網絡規模以及網絡中節點的分布情況有關，需要根據網絡動態設置。ECBES基于策略迭代思想，通過有限次迭代確定最優候選轉發區域。

ECBES將節點通信范圍內，面向sink節點的上半球區域作為節點原始候選轉發區域，如圖5中平面S以上的半球區域，平面S稱為原始候選轉發平面。為了能夠盡快找到最優候選轉發區域，加速收斂，ECBES通過分析首輪數據包傳遞期間節點候選轉發區域各分區域中節點參與轉發數據包的比例，確定次優候選轉發區域，并將其作為初始策略，通過多次迭代，確定最優候選轉發區域，以較低的實現復雜度減少不同網絡規模中重復轉發的數據包，降低網絡的整體能耗。

圖5 節點轉發模型

本節共有兩個算法，分別為：次優候選轉發區域確定算法和最優候選轉發區域確定算法。表1對本節算法所用到的部分參數進行介紹。

表1 算法參數

2.5.1 次優候選轉發區域確定

在原始候選轉發區域的基礎上，ECBES進一步確定次優候選轉發區域。對于首輪數據包的傳遞，節點的轉發優先級設定參考文獻[11]，即在候選轉發區域內越靠近sink節點的節點轉發優先級越高(僅限首輪，其余輪次采用2.4.1節所計算的優先級)。

首輪數據包傳遞期間，range(i)_count字段用來統計原始候選轉發區域各個分區域(range(i)區域)中的節點參與轉發數據包的次數。range(i)區域劃分如圖5所示，每個range(i)代表一個區域范圍，候選轉發節點收到數據包后根據距離上一跳節點原始候選轉發平面的距離d_initial確定自己處于哪一區域，并對數據包包頭中對應的range(i)_count字段值加1。

首輪數據包傳遞結束后，sink節點利用收到的數據包中的range(i)_count信息，計算各個range(i)區域中節點參與轉發數據包的比例，并與閾值TH∈[0，1) 進行比較，最終確定次優候選轉發區域。range(i)區域節點轉發比例的計算如式(5)所示

(5)

從range(n)_ratio開始向下對每個區域轉發比例逐一進行累加，當累加值大于閾值TH時，參與累加的區域即為次優候選轉發區域，如圖5所示，以平面S’為底面的球冠區域即為次優候選轉發區域。確定次優候選轉發區域后，sink節點將此信息廣播到網絡中。算法1以圖5為示例，給出次優候選轉發區域確定的主要步驟。

算法1：次優候選轉發區域確定

輸入：(原始候選轉發區域)

輸出：(次優候選轉發區域)

范圍：(首輪數據包傳遞期間)

(1)/*候選轉發節點收到數據包后的處理方案*/

(2)若候選轉發節點C收到A發來的數據包, 如圖5所示, 則計算節點C到節點A的原始候選轉發平面的距離

(3)根據計算出的d_initialCA確定節點C所屬的區域range(i)之后, 將數據包包頭中對應的range(i)_count字段值加1

(4)/*sink節點收到數據包后的處理方案*/

(5)IF (condition1)

(6) 讀取包中的range(i)_count信息并存儲

(7)ELSE

(8) 丟棄數據包

(9)IF (condition2)

(10) 計算各range(i)區域中節點參與轉發數據包的比例

(11) IF (range(n)_ratio>TH)

(12) range(n)為次優候選轉發區域

(13) ELSE IF (range(n)_ratio+range(n-1)_ratio>TH)

(14) range(n)+range(n-1)為次優候選轉發區域

(15) ……

(16) ELSE IF(range(n)_ratio+…+range(2)_ratio>TH)

(17) range(n)+…+range(2)為次優候選轉發區域

(18) ELSE

(19)原始候選轉發區域為次優候選轉發區域

2.5.2 最優候選轉發區域確定

策略迭代思想是通過不斷迭代獲得最優策略的一種思想。為了加快收斂，ECBES將上一節中確定的次優候選轉發區域作為初始策略。

算法2：最優候選轉發區域確定

輸入：(次優候選轉發區域)

輸出：(最優候選轉發區域)

范圍：(第2輪及以后數據包傳遞期間)

(1) /*節點的候選轉發區域設置方案*/

(3) /*sink節點收到數據包后的處理方案*/

(4)IF (condition1)

(5)pk_count本輪++

(6)ELSE

(7) 丟棄數據包

(8)IF (condition2)

(9) IF (pk_count本輪!

(10)pk_count上輪=pk_count本輪

(11)pk_count本輪=0

(12) ELSE

(13) 結束, 上一輪候選轉發區域確定為最優候選轉發區域

3 實驗結果與分析

3.1 仿真設置

本文通過仿真軟件OPNET 14.5對VBF、ES-VBF、ALRP和ECBES的節點死亡率、數據包投遞率、網絡能耗以及端到端時延進行實驗分析。仿真物理層采用水聲信道。發包節點固定在水底，每輪發包間隔15 s，總共發包15輪。移動節點分布在240m×240m×120m的監測區域內，隨水流進行0～3 m/s的隨機水平移動。主要實驗參數見表2。

表2 仿真參數

本實驗設置主區為一個底面半徑60 m，高120 m的圓柱區域，監測區域其余部分為副區，主區分為4層，分別用半徑60 m，90 m和120 m的同心球隔開。副區分層為以主區同心球分層與主副區邊界交點為界限的平行分層，拓撲縱向剖面圖如圖3所示。候選轉發區域分區數n=4， 分別為range(1)、range(2)、range(3)、range(4)，每個區域厚度為10 m，迭代步長H為2 m，最多迭代次數為4。

3.2 性能評估

在本小節中，將對UWSNs路由協議VBF、ES-VBF、ALRP和ECBES進行性能評估。評估指標包括節點死亡率、數據包投遞率、網絡能耗以及端到端時延。

3.2.1 節點死亡率

圖6為VBF、ES-VBF、ALRP和ECBES仿真完成后的節點死亡率隨節點個數增加的變化曲線。結果表明，ECBES在不同節點個數下均沒有出現節點死亡。當節點個數低于500時，VBF、ES-VBF、ALRP的節點死亡率為0，當節點個數增加到500時，出現節點死亡，且隨著節點個數的增加，節點死亡率也在增加。原因是節點的廣播特性導致隨著節點個數的增加，節點間通信的機會和次數也大大增加，從而導致部分節點因能量耗盡而死亡。

圖6 不同節點個數下的節點死亡率

VBF和ES-VBF均采用源節點到sink節點的路由管道限制可轉發數據包的節點，這導致管道內外節點能耗不均，管道內的節點能耗較大。雖然ES-VBF按照節點剩余能量與原始能量的比值采用兩種不同函數設置發包等待時間，剩余能量超過原始能量60%的節點優先發包，但是無法均衡采用同一函數設置發包等待時間的節點間的能耗，而且剩余能量很低的節點雖然轉發優先級低，但在動態網絡中，可能無法抑制其轉發數據包。ALRP中的節點根據其當前位置決定轉發方向，始終面向sink節點方向傳遞數據包，導致網絡各區域間能耗不均。

ECBES在不同節點個數下的節點死亡率均為0。主要原因是ECBES在全局利用雙區非均勻分層拓撲均衡能耗，在局部節點間通過上下兩跳節點剩余能量的大小關系均衡能耗，且為了緩解動態網絡中可能無法抑制低能量節點轉發數據包的情況，設定當候選轉發節點與上一跳節點剩余能量的比值低于0.3時，主動放棄數據包的轉發。

3.2.2 數據包投遞率

圖7為VBF、ES-VBF、ALRP和ECBES的數據包投遞率隨節點個數增加的變化曲線。結果表明，當節點個數增加時，4個協議的數據包投遞率逐漸增加。從圖7可知，節點個數在700～800時，ECBES的數據包投遞率明顯高于其它3個協議，主要是因為ECBES在數據包傳遞期間沒有節點死亡，因此，所有節點都處于正常工作狀態。

圖7 不同節點個數下的數據包投遞率

3.2.3 網絡能耗

圖8為VBF、ES-VBF、ALRP和ECBES的網絡能耗隨節點個數增加的變化曲線。結果表明，當節點個數增加時，4個協議的網絡能耗逐漸增加。原因是節點的廣播特性導致隨著節點個數的增加，節點間通信的機會和次數也大大增加，從而導致能耗增加。

圖8 不同節點個數下的網絡能耗

VBF和ES-VBF均采用冗余傳輸，即允許有限多個節點轉發數據包，這會產生不必要的能耗。ALRP雖然采用單個節點轉發數據包，但每一跳節點的候選轉發區域太大，占到了節點通信范圍的一半，在動態網絡中難以抑制部分重復數據包的轉發，從而造成較高的能耗。

從圖8可知，ECBES在不同節點個數下的網絡能耗基本都低于其它3個協議。由圖7與圖8對比可知，ECBES在投遞率基本不低于其它3個協議的同時，能耗大大降低。主要原因是ECBES利用策略迭代思想確定最優候選轉發區域，保證投遞率的同時減少了不同網絡規模中重復數據包的轉發，降低了網絡的整體能耗。

3.2.4 端到端時延

圖9是不同節點個數下4個協議的端到端時延。VBF、ES-VBF、ALRP和ECBES在節點個數為100～300時，sink節點未收到數據包，因此沒有端到端時延數據。從圖中可知，ECBES在4個協議中保持了不錯的端到端時延。主要是因為ECBES將網絡劃分為雙區非均勻分層拓撲，使得各個節點的負載相對均衡，從而降低了排隊的可能性以及根據不同的情況對發包等待時間進行動態調整，去除了多余的等待時間。

圖9 不同節點個數下的端到端時延

4 結束語

本文針對水下傳感器網絡(UWSNs)中節點能耗不均衡和能量有限的問題，提出了能耗均衡與節能的自適應水下路由協議ECBES。在雙區非均勻分層拓撲的基礎上，基于能耗均衡因子計算出節點轉發優先級，實現自適應轉發節點選擇，均衡網絡能耗。同時，利用策略迭代思想逐步確定最優候選轉發區域，減少了重復數據包的轉發，降低了網絡的整體能耗。

本文基于OPNET分析對比了4個協議在不同節點數量下的節點死亡率、數據包投遞率、網絡能耗以及端到端時延。仿真結果表明，ECBES相比于VBF、ES-VBF和ALRP，在不同節點數量下，節點死亡率均最低，在保證數據包投遞率的同時，能耗最少。

在未來的研究中，將嘗試多sink節點的架構來進一步擴展和研究本文所提出的方案，以擴展使用場景。