基于剩余能量的局部更新路由算法*

2019-12-20 00:52:34侯向丹楊聰敏劉洪普

傳感器與微系統 2019年1期

侯向丹，楊聰敏，劉洪普

(1.河北工業大學計算機科學與軟件學院，天津 300400；2.河北省大數據計算重點實驗室，天津 300400)

0 引言

無線傳感器網絡(wireless sensor networks,WSNs)的廣泛定義是指由大量體型小、成本相對較低，但處理能力和能量受限的普通無線傳感器節點組成的網絡[1,2]。WSNs的發展過程中，根據匯聚節點的移動性主要分為兩大方向，即靜態傳感器網絡與動態傳感器網絡，靜態傳感器網絡中匯聚節點的位置是固定不變的，如經典的LEACH協議。動態傳感器網絡中的匯聚節點在工作過程中是可以移動的，比如λ-flooding協議就是比較經典的基于移動Sink的路由算法[3]。基于動態傳感器網絡的研究中，關于最短路徑樹的局部拓撲結構更新成為了新的研究方向。

目前，已經有很多基于局部拓撲結構的路由算法被提出，效果比較好的協議包括AVRP[4],ERouA[5],λ-flooding[6]等,這些算法的整體思想是在整個網絡部署區域內構建不同數量的最短路徑樹，在AVRP協議中雖然構建了多棵最短路徑樹，但每次更新路由時都是更新整棵樹的路由，能量消耗依然很大。λ-flooding協議中，雖然提出了對最短路徑樹進行局部更新，但只適用于一個移動Sink的情況，使用時局限性很大。ERouA協議中改進了λ-flooding協議的單移動Sink問題，是一個基于局部路由更新的多移動Sink算法。以上協議在一定程度上有效延長了網絡的壽命，但在工作過程中沒有考慮節點的剩余能量問題[7]，如果某個節點的剩余能量很少，卻由于篩選條件單一被選為虛擬匯聚節點或者中間節點，那么很快此節點就會由于能量耗盡而死亡，進一步導致網絡生命周期結束[8]。

綜合AVRP,λ-flooding,ERouA 3種算法的特點，本文在ERouA算法的基礎上提出一種基于剩余能量的局部更新路由算法(RE-RouA)，將節點的剩余能量融入到算法過程中，在算法的虛擬匯聚節點選取階段、數據收集樹的構造階段、路由更新階段均進行了有效的改進。

1 協議算法的目標與設計

1.1 算法目標

RE-RouA算法的目標是在保證網絡延時不變的基礎上延長節點的死亡時間，延長網絡的生命周期。具體從以下3方面對ERouA進行改進：1)在選取虛擬匯聚節點階段增加選擇條件，利用加權函數選出最優虛擬匯聚節點；2)在數據收集樹構造階段，將節點剩余能量與閾值進行比較，為節點選擇合適的位置；3)在路由更新階段增加了觸發更新的條件，并提出相應的更新方案。

1.2 算法設計

RE-RouA算法主要包括4個階段：虛擬匯聚節點的選取；數據收集樹的構造；路由更新；數據傳輸。

1.2.1 虛擬匯聚節點選取

虛擬匯聚節點的主要作用是將普通節點的數據收集后轉發給移動匯聚節點，或者將移動Sink的命令進行下發，起到一個臨時匯聚節點的作用。

ERouA算法在選取虛擬匯聚節點時只參考了節點的信號強弱，選出信號最強的節點作為虛擬匯聚節點，RE-RouA算法將節點的剩余能量與信號強弱共同作為選取虛擬匯聚節點的參考條件，采用加權函數的方式進行選取，使得整個算法得到了進一步優化。

RE-RouA中虛擬匯聚節點的選取條件主要有2個：1)節點有足夠多的剩余能量，因為虛擬匯聚節點在工作過程中需要接收來自鄰居節點的大量數據，且轉發這些數據，將會使虛擬匯聚節點的能量消耗比普通節點大得多，所以保證所選節點有足夠的剩余能量可供使用就顯得尤為重要。2)要確保所選節點與其相對應的移動Sink之間的距離不要太遠，否則會失去算法的優化意義。因此，RE-RouA算法提出采用加權函數來平衡這兩個因素的權重，找到一個合適的權值系數，從而得到一個效果較好的平衡點。

虛擬匯聚節點的選取流程如圖1所示。

圖1 選擇虛擬匯聚節點流程

其中，i為移動會聚集點，移動匯聚節點的個數可以任意選取，為方便說明本文假設i=1，2，3；j為節點i的鄰居節點且j=1，2，…，n；dis(i，j)為移動會聚節點i到節點鄰居節點j的距離，用距離表示節點j的信號強弱，距離與信號強弱成反比；E(j)為節點j的剩余能量；F(i，j)為i與j的適應度值，且F(i，j)=αdis(i，j)+βE(j)；α，β為實驗系數。

1.2.2 數據收集樹構造

ERouA算法中建樹的方法是在每一個數據收集域中投放一個移動匯聚節點，如圖2所示為一棵數據收集樹，對應一個移動匯聚節點。ERouA算法中某節點將被作為葉子節點或中間節點是隨機的，但由于中間節點所需的能量更多，同時為了延長網絡的使用壽命，RE-RouA算法提出將節點的剩余能量也作為一個節點選取的特征。即構造數據收集樹時以所選出的虛擬匯聚節點為根節點，所有節點均實時計算自己的剩余能量，并與能量閾值θ1進行比對，若剩余能量大于θ1，則該節點在構造最短路徑樹時可作為中間節點，否則該節點只能作為葉子節點進行數據收集。

RE-RouA算法將剩余能量較大的節點放在了數據收集樹的中間節點位置。剩余能量小的節點放在葉子節點位置，與ERouA算法中只考慮距離的構建方法相比，該算法可有效延長網絡壽命。

圖2 數據收集樹模型

1.2.3 路由更新

在ERouA算法的數據收集域中，移動匯聚節點在一定時間間隔內不能收到虛擬匯聚節點反饋的ACK包時，移動Sink會重新選擇新的虛擬匯聚節點，此時新一輪的局部路由更新將被觸發。但由于數據收集樹的中間節點要為葉子節點以及其他中間節點進行數據收集轉發，所以能量消耗會較大，如果中間節點的剩余能量較少，會加速節點死亡，導致網絡生命周期受影響。RE-RouA算法增加了局部更新的觸發條件以及更新方法。當中間節點的能量不足時同樣會觸發路由更新，經過局部調整將此中間節點放到葉子節點。具體過程如下：將數據收集樹的中間節點的剩余能量與能量閾值θ2進行比較，若節點的剩余能量小于能量閾值θ2，同樣會觸發局部的路由更新，這是本文提出的第二個觸發局部更新的條件，目的是確保中間節點的剩余能量可以完成中間轉發的任務，保證網絡的壽命。在路由局部更新階段如果更新是由虛擬匯聚節點的改變所觸發的，則采用ERouA中的方法進行更新。具體算法為：

1)while nodeireceiving a routing update packet from nodejdo

2)if KNTv(j,v)+d(i,j)

3) if((dTu(v,u)+dTu(i,u))/(KNTv(j,v)+d(i,j)))>λthen

4) KNTv(i,v)←KNTv(j,v)+d(i,j)

5) Pi←j

6) Forwarding the routing update packet to its neghbors

7) else

8) Discard the routing update packet

9) end if

10)else

11) Discard the routing update packet

12)end if

13)end while

如果是由中間節點k的剩余能量不足觸發的局部更新，將按照本文提出的方法進行更新，此時需要分兩種情況進行更新。若中間節點k的子節點全部都是葉子節點，則此節點k與其子節點一起作為其父節點的新的子節點。若中間節點k的子節點還有后繼節點，則將此節點k的非葉子子節點作為其父節點的新的子節點，節點k與其葉子子節點一起作為其父節點的葉子節點。

在路由更新階段，本文將ERouA算法進行了擴展與完善，在其基礎上增加了更新條件與算法，使算法整體得到有效優化。

1.2.4 數據傳輸

在數據傳輸階段，每個數據收集域分別進行各自的收集傳輸，葉子節點將自身收集到的數據沿著數據收集樹向上傳播到他的父節點，各中間節點不僅收集子節點發來的數據，同時也要收集自己的數據，進行轉發。直到將數據發送到虛擬匯聚節點，由虛擬匯聚節點轉發給移動Sink，進一步傳遞到用戶處進行處理分析。

2 算法仿真

2.1 仿真環境

本文使用MATLAB 進行試驗仿真，在200 m×200 m的仿真區域內隨機投放200個傳感器節點，并且設置3個移動Sink進行數據收集，每個節點的初始能量設置為0.5 J。

2.2 仿真結果與分析

本文使用MATLAB 進行仿真實驗，將RE-RouA算法與ERouA，λ-flooding，AVRP 3種算法進行了對比。

如圖3所示，隨著實驗輪數的增加死亡節點數呈遞增趨勢，本文算法在相同輪數的情況下死亡節點數最少，節點全部死亡的時間最晚，且初次出現死亡節點的時間最晚，綜合比較本文算法在延長網絡生命周期方面效果較好。由于WSNs的傳感器節點能量是固定不可再生的，尤其是在環境惡劣的情況下更換電池更為困難，所以提高網絡的壽命在WSNs研究中尤為重要。本文在提高網絡壽命方面有著較好效果。