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

侯向丹， 楊聰敏， 劉洪普

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

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)的廣泛定義是指由大量體型小、成本相對較低，但處理能力和能量受限的普通無線傳感器節(jié)點組成的網(wǎng)絡(luò)[1,2]。WSNs的發(fā)展過程中，根據(jù)匯聚節(jié)點的移動性主要分為兩大方向，即靜態(tài)傳感器網(wǎng)絡(luò)與動態(tài)傳感器網(wǎng)絡(luò)，靜態(tài)傳感器網(wǎng)絡(luò)中匯聚節(jié)點的位置是固定不變的，如經(jīng)典的LEACH協(xié)議。動態(tài)傳感器網(wǎng)絡(luò)中的匯聚節(jié)點在工作過程中是可以移動的，比如λ-flooding協(xié)議就是比較經(jīng)典的基于移動Sink的路由算法[3]?；趧討B(tài)傳感器網(wǎng)絡(luò)的研究中，關(guān)于最短路徑樹的局部拓?fù)浣Y(jié)構(gòu)更新成為了新的研究方向。

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

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

1 協(xié)議算法的目標(biāo)與設(shè)計

1.1 算法目標(biāo)

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

1.2 算法設(shè)計

RE-RouA算法主要包括4個階段：虛擬匯聚節(jié)點的選?。粩?shù)據(jù)收集樹的構(gòu)造；路由更新；數(shù)據(jù)傳輸。

1.2.1 虛擬匯聚節(jié)點選取

虛擬匯聚節(jié)點的主要作用是將普通節(jié)點的數(shù)據(jù)收集后轉(zhuǎn)發(fā)給移動匯聚節(jié)點，或者將移動Sink的命令進(jìn)行下發(fā)，起到一個臨時匯聚節(jié)點的作用。

ERouA算法在選取虛擬匯聚節(jié)點時只參考了節(jié)點的信號強(qiáng)弱，選出信號最強(qiáng)的節(jié)點作為虛擬匯聚節(jié)點，RE-RouA算法將節(jié)點的剩余能量與信號強(qiáng)弱共同作為選取虛擬匯聚節(jié)點的參考條件，采用加權(quán)函數(shù)的方式進(jìn)行選取，使得整個算法得到了進(jìn)一步優(yōu)化。

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

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

圖1 選擇虛擬匯聚節(jié)點流程

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

1.2.2 數(shù)據(jù)收集樹構(gòu)造

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

RE-RouA算法將剩余能量較大的節(jié)點放在了數(shù)據(jù)收集樹的中間節(jié)點位置。剩余能量小的節(jié)點放在葉子節(jié)點位置，與ERouA算法中只考慮距離的構(gòu)建方法相比，該算法可有效延長網(wǎng)絡(luò)壽命。

圖2 數(shù)據(jù)收集樹模型

1.2.3 路由更新

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

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

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

在路由更新階段，本文將ERouA算法進(jìn)行了擴(kuò)展與完善，在其基礎(chǔ)上增加了更新條件與算法，使算法整體得到有效優(yōu)化。

1.2.4 數(shù)據(jù)傳輸

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

2 算法仿真

2.1 仿真環(huán)境

本文使用MATLAB 進(jìn)行試驗仿真，在200 m×200 m的仿真區(qū)域內(nèi)隨機(jī)投放200個傳感器節(jié)點，并且設(shè)置3個移動Sink進(jìn)行數(shù)據(jù)收集，每個節(jié)點的初始能量設(shè)置為0.5 J。

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

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

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

圖3 生命周期對比

如圖4所示，將4種算法的網(wǎng)絡(luò)剩余能量進(jìn)行了統(tǒng)計對比，隨著時間的增加網(wǎng)絡(luò)的剩余能量會逐漸減少，本文算法在相同時間內(nèi)網(wǎng)絡(luò)剩余的能量是最多的，網(wǎng)絡(luò)能量耗盡所需時間也是最長的，對于無線傳感器網(wǎng)絡(luò)的節(jié)能有顯著效果。在相同的網(wǎng)絡(luò)工作環(huán)境下，本文算法可以有效節(jié)約能量，從而延長網(wǎng)絡(luò)的壽命。

如圖5所示，WSNs從100個節(jié)點數(shù)到800個節(jié)點數(shù)的不同規(guī)模情況下，分別運行相同時間后，網(wǎng)絡(luò)剩余節(jié)點數(shù)的比較情況可見，RE-RouA算法中剩余節(jié)點的數(shù)目隨著網(wǎng)絡(luò)規(guī)模的增加而增加。在同一時間段，網(wǎng)絡(luò)的規(guī)模越大，節(jié)點的死亡率越低，說明RE-RouA算法有效增加了網(wǎng)絡(luò)壽命。

3 結(jié) 論

仿真實驗的結(jié)果表明：在WSNs路由協(xié)議過程加入節(jié)點剩余能量的方法有效，對于延長網(wǎng)絡(luò)生命周期效果顯著。