侯向丹， 楊聰敏， 劉洪普

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

0 引 言

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

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

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

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

1.1 算法目標(biāo)

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

1.2 算法設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

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

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

1.2.3 路由更新

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

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

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

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

2 算法仿真

2.1 仿真環(huán)境

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

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

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

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

圖3 生命周期對(duì)比

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

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

3 結(jié) 論

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