陶建林,方 凱,苗春雨,葉章龍*

(1.浙江工業(yè)職業(yè)技術(shù)學(xué)院,浙江 紹興 312000;2.衢州學(xué)院電氣與信息工程學(xué)院,浙江 衢州 324000;3.浙江師范大學(xué)數(shù)理與信息工程學(xué)院,浙江 金華 32100)

無(wú)線傳感器網(wǎng)絡(luò)主要功能是數(shù)據(jù)采集和轉(zhuǎn)發(fā),由于無(wú)需布線、成本低、精度高等特點(diǎn)使其被廣泛應(yīng)用于生產(chǎn)生活中的各個(gè)領(lǐng)域。如在林業(yè)方面,傳感器網(wǎng)絡(luò)被用于感知環(huán)境數(shù)據(jù);在工業(yè)方面,傳感器網(wǎng)絡(luò)采集設(shè)備狀態(tài)數(shù)據(jù)和生產(chǎn)環(huán)境數(shù)據(jù);在環(huán)保方面,傳感器網(wǎng)絡(luò)采集環(huán)境數(shù)據(jù)傳輸至服務(wù)器端進(jìn)行監(jiān)測(cè)等[1-4];由于傳感器網(wǎng)絡(luò)中采集終端數(shù)量龐大,數(shù)據(jù)在轉(zhuǎn)發(fā)過(guò)程中不同節(jié)點(diǎn)負(fù)載不同,負(fù)載重的節(jié)點(diǎn)能量容易提前耗盡,從而形成網(wǎng)絡(luò)路由空洞?？斩锤浇膫鞲衅鞴?jié)點(diǎn)在傳輸數(shù)據(jù)時(shí)需要繞過(guò)空洞,大大增加了數(shù)據(jù)轉(zhuǎn)發(fā)跳數(shù),不利于網(wǎng)絡(luò)的長(zhǎng)期生存。

目前在WSN空洞修復(fù)方面的研究已經(jīng)取得豐厚的成果,其中主要是針對(duì)區(qū)域覆蓋研究中的空洞修復(fù),即派遣移動(dòng)節(jié)點(diǎn)到空洞位置,利用新增節(jié)點(diǎn)的感知區(qū)域完成空洞的感知覆蓋。如張清國(guó)等人提出了一種基于蜂窩結(jié)構(gòu)的覆蓋優(yōu)化算法,利用蜂窩結(jié)構(gòu)計(jì)算移動(dòng)節(jié)點(diǎn)的候選目標(biāo)位置完成空洞修復(fù)[4]。穆天圓等人提出一種基于Voronoi圖的蜂群優(yōu)化算法指導(dǎo)網(wǎng)絡(luò)空洞的修復(fù),通過(guò)評(píng)價(jià)空洞大小代替輪盤賭選擇方式來(lái)實(shí)現(xiàn)跟隨蜂的開(kāi)采過(guò)程,達(dá)到混合網(wǎng)絡(luò)最優(yōu)覆蓋的效果[5]。劉洲洲等人提出一種基于混合粒子群優(yōu)化算法的空洞修復(fù)方案,將模擬退火算法和粒子群優(yōu)化算法融合得到一種混合算法,該方法能夠有效求解空洞修復(fù)問(wèn)題[6]。Khalifa B等人提出一種分布式的網(wǎng)絡(luò)空洞修復(fù)方法,綜合考慮節(jié)點(diǎn)間覆蓋冗余度、剩余能量和移動(dòng)距離三種因素,選擇最優(yōu)節(jié)點(diǎn)進(jìn)行空洞修復(fù)[7]。Ying X等人通過(guò)研究節(jié)點(diǎn)調(diào)度方法和三角形覆蓋修復(fù)方法,降低網(wǎng)絡(luò)能量消耗,延長(zhǎng)了網(wǎng)絡(luò)的生存時(shí)間[8]。Rafiei A等人研究了基于Voronoi和虛擬力的節(jié)點(diǎn)重定位算法用于修復(fù)網(wǎng)絡(luò)空洞,實(shí)驗(yàn)結(jié)果表明該方法能夠有效修復(fù)網(wǎng)絡(luò)空洞[9]。

上述大量的研究都重點(diǎn)關(guān)注無(wú)線傳感器網(wǎng)絡(luò)的感知覆蓋空洞修復(fù)問(wèn)題,但感知空洞修復(fù)的理論很難應(yīng)用在網(wǎng)絡(luò)路由空洞修復(fù)問(wèn)題上,即使強(qiáng)行套用理論也會(huì)導(dǎo)致路由空洞修復(fù)的能耗和復(fù)雜度提高,對(duì)路由空洞修復(fù)問(wèn)題是極不利的。

網(wǎng)絡(luò)路由空洞是指某些傳感器節(jié)點(diǎn)死亡后該位置無(wú)中繼節(jié)點(diǎn)為其他節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù),從而導(dǎo)致數(shù)據(jù)傳輸中斷或增加了傳輸代價(jià)。本文研究的路由空洞修復(fù)問(wèn)題首先提出兩種路由空洞查找方法,然后提出一種路由空洞能否被完全修復(fù)的判斷方法,最后利用匈牙利算法派遣可移動(dòng)節(jié)點(diǎn)完整空洞修復(fù),本文提出的方法能夠保證修復(fù)路由空洞過(guò)程中可移動(dòng)節(jié)點(diǎn)消耗的能量總和最少。

1 相關(guān)模型與假設(shè)

該章節(jié)首先介紹本文后續(xù)研究過(guò)程中使用到的相關(guān)模型,包括路由空洞模型、節(jié)點(diǎn)通訊能耗模型和可移動(dòng)節(jié)點(diǎn)移動(dòng)能耗模型,然后介紹了相關(guān)假設(shè)。

1.1 相關(guān)模型

1.1.1 路由空洞模型

隨著傳感器網(wǎng)絡(luò)的運(yùn)行,不同節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)的負(fù)載不同,負(fù)載重的傳感器節(jié)點(diǎn)單位時(shí)間內(nèi)的能耗高,而負(fù)載輕的節(jié)點(diǎn)單位時(shí)間內(nèi)的能耗較低,因此整個(gè)網(wǎng)絡(luò)中會(huì)出現(xiàn)能耗梯度。當(dāng)某些能耗高的節(jié)點(diǎn)能量耗盡后,就會(huì)形成路由空洞,如圖1中節(jié)點(diǎn)4、5、6、8所示。在沒(méi)出現(xiàn)網(wǎng)絡(luò)空洞時(shí),傳感器節(jié)點(diǎn)1、2、3的數(shù)據(jù)轉(zhuǎn)發(fā)路徑如下所示:

節(jié)點(diǎn)1:1→4→5→6→7→Sink

節(jié)點(diǎn)2:2→4→5→6→7→Sink

節(jié)點(diǎn)3:3→8→6→7→Sink

當(dāng)出現(xiàn)路由空洞以后,傳感器節(jié)點(diǎn)4、5、6、8能量耗盡,無(wú)法承擔(dān)中繼節(jié)點(diǎn)的角色,因此數(shù)據(jù)在網(wǎng)絡(luò)中轉(zhuǎn)發(fā)難度會(huì)增加,節(jié)點(diǎn)1、2、3的數(shù)據(jù)轉(zhuǎn)發(fā)路徑發(fā)生變化,如下所示:

節(jié)點(diǎn)1:1→9→10→11→12→7→Sink

節(jié)點(diǎn)2:中斷傳輸

節(jié)點(diǎn)3:中斷傳輸

傳感器節(jié)點(diǎn)1雖然能調(diào)整轉(zhuǎn)發(fā)路徑,但需要繞過(guò)空洞,轉(zhuǎn)發(fā)的次數(shù)明顯增加,而節(jié)點(diǎn)2、3無(wú)法將數(shù)據(jù)轉(zhuǎn)發(fā)至Sink節(jié)點(diǎn),因此路由空洞對(duì)傳感器網(wǎng)絡(luò)的整體性能具有毀滅性的破壞。圖1中網(wǎng)絡(luò)路由空洞可用集合Vh={4、5、6、8}表示。

圖1 路由空洞模型圖

1.1.2 節(jié)點(diǎn)通訊能耗模型

傳感器節(jié)點(diǎn)間通訊能耗模型如圖2所示,該通訊能耗模型能夠科學(xué)的描述節(jié)點(diǎn)通訊過(guò)程中的能量消耗。節(jié)點(diǎn)數(shù)據(jù)的發(fā)送和接收能耗如式(1)、式(2)所示,發(fā)送數(shù)據(jù)過(guò)程中主要能耗產(chǎn)生在信號(hào)發(fā)射器和信號(hào)放大器兩個(gè)部件,且發(fā)送能耗與發(fā)射距離、數(shù)據(jù)包大小相關(guān)。數(shù)據(jù)接收能耗主要產(chǎn)生在信號(hào)接收電路。

圖2 節(jié)點(diǎn)通訊能耗模型

(1)

Erx=kEd

(2)

式(1)、式(2)中Ee表示發(fā)射電路和接收電路處理1 bit數(shù)據(jù)的能耗;k表示發(fā)送或接收數(shù)據(jù)包的大小;εamp1、εamp1表示信號(hào)放大電路將信號(hào)放大的倍數(shù);d表示發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)的歐氏距離;D表示一個(gè)距離界限,如式(3)所示。

(3)

式中:hr、ht分別表示接收節(jié)點(diǎn)和發(fā)送節(jié)點(diǎn)的天線距離地面高度;λ為電磁波波長(zhǎng);L為常數(shù)。

1.1.3 節(jié)點(diǎn)移動(dòng)能耗模型

利用可移動(dòng)傳感器節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)路由空洞進(jìn)行修復(fù),其能量消耗主要發(fā)生在移動(dòng)過(guò)程中且消耗的能量與移動(dòng)距離呈正比,移動(dòng)1 m消耗的能量約為3.6 J[10-11]。

1.2 相關(guān)假設(shè)

①傳感器節(jié)點(diǎn)采用電池供電,能量消耗完后無(wú)法更換電池或從外界獲得能量。

②可移動(dòng)節(jié)點(diǎn)和靜態(tài)節(jié)點(diǎn)按一定比例隨機(jī)均勻部署,且初始時(shí)刻可移動(dòng)節(jié)點(diǎn)不參與網(wǎng)絡(luò)數(shù)據(jù)采集和轉(zhuǎn)發(fā)工作,僅供后續(xù)空洞修復(fù)使用。

③無(wú)線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)已經(jīng)通過(guò)定位算法或GPS等技術(shù)手段獲得了物理坐標(biāo)。

④網(wǎng)絡(luò)中靜態(tài)傳感器的初始能量為Es,可移動(dòng)傳感器節(jié)點(diǎn)的初始能量為Em,最大可移動(dòng)距離為R,兩種傳感器節(jié)點(diǎn)的通訊半徑相同且都為r。

⑤傳感器網(wǎng)絡(luò)每隔固定時(shí)間進(jìn)行一次數(shù)據(jù)采集,且本文的研究以參考文獻(xiàn)[12]的能耗均衡鏈路式路由協(xié)議為背景,進(jìn)行路由空洞修復(fù)以及對(duì)整個(gè)網(wǎng)絡(luò)的性能進(jìn)行分析。

2 路由空洞定位

當(dāng)出現(xiàn)網(wǎng)絡(luò)路由空洞后,需要定位空洞中能量耗盡的傳感器節(jié)點(diǎn)(即死亡節(jié)點(diǎn)),才能派遣可移動(dòng)節(jié)點(diǎn)對(duì)路由空洞進(jìn)行修復(fù)。本文提出2種網(wǎng)絡(luò)空洞的定位方法,如下所示:

①如果傳感器節(jié)點(diǎn)本身可以獲取電池的剩余能量,則可將剩余能量值傳輸至服務(wù)器端,服務(wù)器端可根據(jù)節(jié)點(diǎn)的剩余能量值判斷即將產(chǎn)生或已經(jīng)產(chǎn)生的路由空洞。

②如果傳感器節(jié)點(diǎn)無(wú)法獲取電池的剩余能量,此時(shí)定位路由空洞相對(duì)復(fù)雜。網(wǎng)絡(luò)在初始運(yùn)行時(shí)刻,服務(wù)器端記錄能夠正常傳回?cái)?shù)據(jù)的傳感器節(jié)點(diǎn)編號(hào)集合N0和傳感器節(jié)點(diǎn)的數(shù)據(jù)傳輸路徑集合Path={P1,P2,P3…Pi…Pm},Pi表示節(jié)點(diǎn)i的數(shù)據(jù)傳輸路徑,m為集合N0的元素總數(shù)。當(dāng)網(wǎng)絡(luò)采集t輪數(shù)據(jù)后,服務(wù)器端重新統(tǒng)計(jì)能正常傳回?cái)?shù)據(jù)的節(jié)點(diǎn)編號(hào)集合為Nt,此時(shí)可計(jì)算出無(wú)法正常傳回?cái)?shù)據(jù)的傳感器節(jié)點(diǎn)編號(hào)Nd,如式(4)所示。

Nd=N0-Nt

(4)

無(wú)法正常傳輸數(shù)據(jù)至服務(wù)器端的節(jié)點(diǎn)可能包含兩種情況:(a)該節(jié)點(diǎn)能量耗盡;(b)該節(jié)點(diǎn)數(shù)據(jù)傳輸路徑中某些節(jié)點(diǎn)能量耗盡導(dǎo)致傳輸中斷。對(duì)應(yīng)到數(shù)據(jù)傳輸路徑Pi上可分為2種情況,如圖3所示。

圖3 數(shù)據(jù)傳輸路徑圖

表1 路由空洞定位與修復(fù)方法

3 路由空洞修復(fù)

第2章節(jié)介紹了2種路由空洞定位方法,這2種方法都可在實(shí)際的無(wú)線傳感器網(wǎng)絡(luò)中實(shí)現(xiàn)。本章介紹利用可移動(dòng)節(jié)點(diǎn)修復(fù)路由空洞,如圖4所示,路由空洞由節(jié)點(diǎn)n1～n5組成,通過(guò)派遣v1～v5可移動(dòng)節(jié)點(diǎn)到死亡節(jié)點(diǎn)位置,替代死亡節(jié)點(diǎn)的數(shù)據(jù)采集和中繼功能,即可修復(fù)空洞。如果基于最近原則派遣可移動(dòng)節(jié)點(diǎn),則5個(gè)可移動(dòng)節(jié)點(diǎn)的移動(dòng)距離之和不一定最短的,因?yàn)樽罱汕卜椒ㄈ菀紫萑刖植孔顑?yōu)問(wèn)題。為使修復(fù)路由空洞的代價(jià)之和最小,且在可移動(dòng)節(jié)點(diǎn)移動(dòng)距離和數(shù)量都有限的情況下盡可能修復(fù)空洞,研究了一種空洞修復(fù)判斷方法和可移動(dòng)節(jié)點(diǎn)最優(yōu)派遣方法。

圖4 空洞修復(fù)過(guò)程圖

3.1 空洞修復(fù)判斷

可移動(dòng)節(jié)點(diǎn)數(shù)量和移動(dòng)距離都有限,并不一定網(wǎng)絡(luò)中所有死亡節(jié)點(diǎn)都可被移動(dòng)節(jié)點(diǎn)替換,因此在修復(fù)空洞前需要研究一種路由空洞能否被移動(dòng)節(jié)點(diǎn)完全修復(fù)的判斷方法。當(dāng)可移動(dòng)節(jié)點(diǎn)與死亡節(jié)點(diǎn)之間的距離d小于等于可移動(dòng)節(jié)點(diǎn)的最大移動(dòng)距離R時(shí),該可移動(dòng)節(jié)點(diǎn)可用于替換死亡節(jié)點(diǎn)。

假設(shè)網(wǎng)絡(luò)路由空洞為{n1,n2,n3},如圖5所示。當(dāng)可移動(dòng)節(jié)點(diǎn)的最大移動(dòng)距離為R時(shí),可移動(dòng)到死亡節(jié)點(diǎn)n1、n2、n3的移動(dòng)節(jié)點(diǎn)集合分別表示為S1={v1,v2}、S2={v2}、S3={v3,v4,v5},當(dāng)同時(shí)滿足以下三個(gè)條件時(shí),能夠完全修復(fù)路由空洞。

圖5 修復(fù)判斷方法圖

①|(zhì)S1∪S2∪……St|≥t,t為路由空洞中死亡節(jié)點(diǎn)總數(shù)。

②Si≠?,1≤i≤t。

③|Seti∪Setj| ≥ 2,1≤i,j≤t,i≠j。

基于上述方法,如果判斷傳感器網(wǎng)絡(luò)路由空洞內(nèi)所有死亡節(jié)點(diǎn)都可被移動(dòng)節(jié)點(diǎn)替換,則可完成路由空洞的完全修復(fù),但在不能完全修復(fù)的情況下,盡最大可能修復(fù)死亡節(jié)點(diǎn)。

3.2 最優(yōu)派遣

匈牙利算法一般用于人員最優(yōu)指派問(wèn)題,假設(shè)w個(gè)工人去完成w個(gè)任務(wù),每個(gè)工人可同時(shí)能做若干種任務(wù),但每個(gè)任務(wù)只能派遣1個(gè)工人,而每個(gè)工人對(duì)不同任務(wù)的熟練程度不同,即完成時(shí)間不同。匈牙利算法能夠最優(yōu)的指派人員去做相應(yīng)的工作,使完成所有工作花費(fèi)的時(shí)間總和最短。將可移動(dòng)節(jié)點(diǎn)派遣修復(fù)路由空洞問(wèn)題類比到人員指派問(wèn)題,派遣x個(gè)可移動(dòng)節(jié)點(diǎn)去修復(fù)y個(gè)死亡節(jié)點(diǎn),且x與y的值不一定相等,因此利用“加邊補(bǔ)零法”對(duì)傳統(tǒng)的匈牙利算法進(jìn)行改進(jìn),使之適用于不完全指派問(wèn)題[13-16]。本文的路由空洞修復(fù)問(wèn)題可分為三種情況,分別是xy,如圖6中(a)、(b)、(c)所示。

圖6 移動(dòng)節(jié)點(diǎn)與修復(fù)位置情況圖

(5)

式中:Cost(1,1)=d1,表示可移動(dòng)節(jié)點(diǎn)v1移動(dòng)到死亡節(jié)點(diǎn)n1的代價(jià)為d1,Cost(1,2)=+∞表示可移動(dòng)節(jié)點(diǎn)v1無(wú)法移動(dòng)到死亡節(jié)點(diǎn)n2處,因此代價(jià)是無(wú)窮大。Cost(2,1)=0、Cost(2,2)=0表示虛擬節(jié)點(diǎn)移動(dòng)到死亡節(jié)點(diǎn)n1和n2的代價(jià)都為0。

圖6(b)中路由空洞存在2個(gè)死亡節(jié)點(diǎn)n1和n2,且可移動(dòng)節(jié)點(diǎn)數(shù)量也為2,可移動(dòng)節(jié)點(diǎn)v1可以移動(dòng)到n1位置,距離為d1,而不能移動(dòng)到n2位置(超出可移動(dòng)節(jié)點(diǎn)的最大可移動(dòng)距離R),因此規(guī)定v1移動(dòng)到n2的距離為+∞;節(jié)點(diǎn)v2可同時(shí)移動(dòng)到n1和n2位置,距離分別是d2和d3,利用移動(dòng)節(jié)點(diǎn)與死亡節(jié)點(diǎn)的距離作為路由空洞修復(fù)的代價(jià),構(gòu)建匈牙利算法的代價(jià)矩陣,如式(6)所示。

(6)

圖6(c)中路由空洞存在2個(gè)死亡節(jié)點(diǎn)n1和n2,而可移動(dòng)節(jié)點(diǎn)有3個(gè),因此需要虛擬一個(gè)死亡節(jié)點(diǎn),如圖中虛擬死亡節(jié)點(diǎn)n′所示。根據(jù)“加邊補(bǔ)零法”,所有可移動(dòng)節(jié)點(diǎn)與虛擬死亡節(jié)點(diǎn)n′的距離都為0,假設(shè)可移動(dòng)節(jié)點(diǎn)與死亡節(jié)點(diǎn)的距離大于移動(dòng)節(jié)點(diǎn)的最大移動(dòng)距離R時(shí),該移動(dòng)節(jié)點(diǎn)與死亡節(jié)點(diǎn)的距離為+∞。構(gòu)建的匈牙利算法代價(jià)矩陣如式(7)所示。

(7)

針對(duì)上述三種情況,構(gòu)建相應(yīng)的匈牙利代價(jià)矩陣后,根據(jù)傳統(tǒng)的匈牙利算法步驟即可得到最優(yōu)的可移動(dòng)節(jié)點(diǎn)派遣方法,使得所有可移動(dòng)節(jié)點(diǎn)派遣到死亡節(jié)點(diǎn)位置后移動(dòng)距離之和最短,從而實(shí)現(xiàn)修復(fù)路由空洞能耗最低的目的。

4 仿真實(shí)驗(yàn)

通過(guò)仿真實(shí)驗(yàn)驗(yàn)證本文提出的路由空洞修復(fù)方法(RVREP)各方面的性能,實(shí)驗(yàn)采用i7處理器、8 G內(nèi)存的PC機(jī)為硬件環(huán)境,MATLAB仿真平臺(tái)為軟件環(huán)境。在初始時(shí)刻將靜態(tài)傳感器節(jié)點(diǎn)和可移動(dòng)傳感器節(jié)點(diǎn)均勻的部署到長(zhǎng)、寬都為250m的正方形區(qū)域中。傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)按照參考文獻(xiàn)[12]提出的能耗均衡鏈路式路由協(xié)議進(jìn)行數(shù)據(jù)采集和傳輸(因?yàn)樵摲椒ㄔ谂龅铰酚煽斩磿r(shí)會(huì)合理的選擇其他轉(zhuǎn)發(fā)路徑),其中Sink節(jié)點(diǎn)位于部署區(qū)域上邊緣的正中間。實(shí)驗(yàn)過(guò)程中隨機(jī)的從網(wǎng)絡(luò)中選擇num個(gè)節(jié)點(diǎn)作為死亡節(jié)點(diǎn)(即形成網(wǎng)絡(luò)路由空洞),實(shí)驗(yàn)相關(guān)參數(shù)如表2所示。由于在路由空洞方面的研究較少,更重要的是本文算法自身性能的驗(yàn)證,因此采用貪婪算法GREEDY進(jìn)行對(duì)比,該方法在修復(fù)路由空洞時(shí),派遣距離死亡節(jié)點(diǎn)最近的可移動(dòng)節(jié)點(diǎn)。

4.1 路由空洞修復(fù)率

當(dāng)路由空洞大小固定的情況下(即死亡節(jié)點(diǎn)數(shù)量固定),隨著網(wǎng)絡(luò)中部署的可移動(dòng)節(jié)點(diǎn)數(shù)量增加,理論上路由空洞被完全修復(fù)的概率會(huì)逐漸提高。本實(shí)驗(yàn)研究路由空洞大小固定時(shí),被完全修復(fù)的概率與可移動(dòng)節(jié)點(diǎn)數(shù)量之間的關(guān)系。首先在部署區(qū)域中均勻部署150個(gè)靜態(tài)傳感器節(jié)點(diǎn),然后隨機(jī)部署mn個(gè)可移動(dòng)節(jié)點(diǎn),接著隨機(jī)選擇30個(gè)靜態(tài)節(jié)點(diǎn)進(jìn)入休眠狀態(tài)模擬網(wǎng)絡(luò)路由空洞,利用可移動(dòng)節(jié)點(diǎn)對(duì)路由空洞進(jìn)行修復(fù)。100次獨(dú)立重復(fù)實(shí)驗(yàn)的平均結(jié)果如圖7所示,橫坐標(biāo)為部署的可移動(dòng)節(jié)點(diǎn)數(shù)量,縱坐標(biāo)為路由空洞被完全修復(fù)的概率。本文提出的RVREP方法可基于3.1小節(jié)的方法判斷路由空洞能否被完全修復(fù)。

表2 實(shí)驗(yàn)參數(shù)表

圖7 可移動(dòng)節(jié)點(diǎn)數(shù)量結(jié)果圖

實(shí)驗(yàn)結(jié)果表明隨著部署區(qū)域中可移動(dòng)節(jié)點(diǎn)數(shù)量增加,本文提出的RVREP方法和貪婪算法GREEDY的完全修復(fù)率都快速提高,當(dāng)可移動(dòng)節(jié)點(diǎn)增加到一定數(shù)量時(shí),完全修復(fù)率提高速度變緩,因?yàn)樵诔跏紩r(shí)刻,修復(fù)路由空洞的可移動(dòng)節(jié)點(diǎn)非常緊缺,所以修復(fù)率提高速度較快,而當(dāng)可移動(dòng)節(jié)點(diǎn)數(shù)量較多時(shí),可移動(dòng)節(jié)點(diǎn)數(shù)量趨于飽和,因此隨著可移動(dòng)節(jié)點(diǎn)數(shù)量繼續(xù)增加,完全修復(fù)率提高速度逐漸變慢。且RVREP方法的完全修復(fù)率一直都高于GREEDY方法,當(dāng)可移動(dòng)節(jié)點(diǎn)數(shù)量為70個(gè)時(shí),RVREP方法的路由空洞完全修復(fù)率已經(jīng)達(dá)到了95%左右,而GREEDY方法僅為69%左右,因?yàn)镽VREP方法在修復(fù)空洞前會(huì)綜合考慮空洞附近的可移動(dòng)節(jié)點(diǎn),實(shí)現(xiàn)最優(yōu)調(diào)配,而GREEDY方法只派遣距離最近的可移動(dòng)節(jié)點(diǎn),會(huì)陷入局部最優(yōu)問(wèn)題,導(dǎo)致其他死亡節(jié)點(diǎn)不能被修復(fù)。

當(dāng)部署區(qū)域內(nèi)可移動(dòng)節(jié)點(diǎn)數(shù)量為90個(gè)時(shí),網(wǎng)絡(luò)路由空洞大小發(fā)送變化,則完全修復(fù)率也會(huì)發(fā)生變化,路由空洞越大,則完全修復(fù)率越低。實(shí)驗(yàn)結(jié)果如圖8所示,橫坐標(biāo)為路由空洞大小,用死亡節(jié)點(diǎn)數(shù)量表示,縱坐標(biāo)為完全修復(fù)率。

圖8 路由空洞大小結(jié)果圖

圖9 平均能耗圖

實(shí)驗(yàn)結(jié)果表明當(dāng)可移動(dòng)節(jié)點(diǎn)數(shù)量固定時(shí),隨著路由空洞大小增加,完全修復(fù)率會(huì)降低。當(dāng)路由空洞大小相同時(shí),RVREP方法的完全修復(fù)率高于GREEDY方法,主要原因是RVREP方法中采用匈牙利算法修復(fù)路由空洞,在盡可能修復(fù)的前提下實(shí)現(xiàn)最優(yōu)派遣,而GREEDY方法修復(fù)空洞極易陷入局部最優(yōu)。

4.2 路由空洞修復(fù)能耗

可移動(dòng)節(jié)點(diǎn)修復(fù)路由空洞過(guò)程中消耗的能量越低,則移動(dòng)節(jié)點(diǎn)替代死亡節(jié)點(diǎn)后剩余的能量越多,越有利于傳感器網(wǎng)絡(luò)的長(zhǎng)期生存。為驗(yàn)證空洞修復(fù)能耗,在部署區(qū)域中均勻部署150個(gè)靜態(tài)傳感器節(jié)點(diǎn),同時(shí)部署的可移動(dòng)節(jié)點(diǎn)數(shù)量大于等于100個(gè),路由空洞大小為30(即路由空洞由30個(gè)死亡節(jié)點(diǎn)組成),該條件確保了RVREP方法和GREEDY方法的路由空洞完全修復(fù)率達(dá)到100%左右(可見(jiàn)4.1小節(jié)實(shí)驗(yàn))?？梢苿?dòng)節(jié)點(diǎn)的移動(dòng)能耗基于第1節(jié)的節(jié)點(diǎn)移動(dòng)能耗模型計(jì)算,實(shí)驗(yàn)結(jié)果如圖9所示,橫坐標(biāo)為可移動(dòng)節(jié)點(diǎn)數(shù)量,縱坐標(biāo)為每個(gè)可移動(dòng)節(jié)點(diǎn)修復(fù)路由空洞的平均能耗。

實(shí)驗(yàn)結(jié)果表明隨著可移動(dòng)節(jié)點(diǎn)數(shù)量增加,完全修復(fù)路由空洞的平均能耗逐漸減低,因?yàn)榭梢苿?dòng)節(jié)點(diǎn)數(shù)量增加,修復(fù)相同的路由空洞所需要移動(dòng)的平均距離逐漸減低,因此對(duì)應(yīng)的能耗也呈降低趨勢(shì)。且本文提出的RVREP方法的平均能耗低于GREEDY方法,因?yàn)镽VREP方法能夠確保修復(fù)路由空洞的移動(dòng)距離之和最短,而GREEDY方法僅保證修復(fù)單個(gè)死亡節(jié)點(diǎn)的移動(dòng)距離最短,但不能確保修復(fù)整個(gè)路由空洞移動(dòng)節(jié)點(diǎn)的移動(dòng)距離總和最短。同時(shí)隨著可移動(dòng)節(jié)點(diǎn)數(shù)量增加,兩種方法的能耗趨于接近,因?yàn)榭梢苿?dòng)節(jié)點(diǎn)數(shù)量增加,密度也會(huì)增加,會(huì)導(dǎo)致死亡節(jié)點(diǎn)附近有足夠的可移動(dòng)節(jié)點(diǎn)用于修復(fù),因此兩種方法的差距逐漸降低。

4.3 網(wǎng)絡(luò)生存時(shí)間

當(dāng)傳感器網(wǎng)絡(luò)中大量節(jié)點(diǎn)死亡后,網(wǎng)絡(luò)的路由結(jié)構(gòu)會(huì)發(fā)生巨變,導(dǎo)致某些路由空洞附近的傳感器節(jié)點(diǎn)數(shù)據(jù)傳輸中斷、另外一些節(jié)點(diǎn)的數(shù)據(jù)轉(zhuǎn)發(fā)負(fù)載加重。這對(duì)整個(gè)網(wǎng)絡(luò)的能耗均衡性是巨大的破壞,最終導(dǎo)致傳感器網(wǎng)絡(luò)的生存時(shí)間大大降低。本實(shí)驗(yàn)以能耗均衡鏈路式路由協(xié)議為背景,分析網(wǎng)絡(luò)的生存時(shí)間。由于傳感器網(wǎng)絡(luò)每隔固定時(shí)間進(jìn)行一輪數(shù)據(jù)采集,因此在數(shù)據(jù)采集過(guò)程中所有節(jié)點(diǎn)的能耗相同,因此忽略采集能耗,但數(shù)據(jù)傳輸過(guò)程中每個(gè)節(jié)點(diǎn)的能耗不同,本文利用第1章節(jié)介紹的節(jié)點(diǎn)通訊能耗模型進(jìn)行傳感器網(wǎng)絡(luò)通訊能耗分析。在部署區(qū)域中均勻部署150個(gè)靜態(tài)傳感器節(jié)和100個(gè)可移動(dòng)傳感器節(jié)點(diǎn),在路由空洞大小為40的情況下,實(shí)驗(yàn)對(duì)比了不同修復(fù)率情況下的傳感器網(wǎng)絡(luò)生存時(shí)間(以傳感器網(wǎng)絡(luò)數(shù)據(jù)采集輪數(shù)表示)。對(duì)路由空洞進(jìn)行一定比例的修復(fù)后,隨著網(wǎng)絡(luò)的運(yùn)行,新產(chǎn)生的死亡節(jié)點(diǎn)數(shù)量達(dá)到網(wǎng)絡(luò)中靜態(tài)傳感器節(jié)點(diǎn)的10%(不包括修復(fù)前已死亡的傳感器節(jié)點(diǎn)),則認(rèn)為網(wǎng)絡(luò)死亡。實(shí)驗(yàn)結(jié)果如表3所示。

表3 網(wǎng)絡(luò)生存時(shí)間表

實(shí)驗(yàn)結(jié)果表明在不修復(fù)路由空洞(修復(fù)率為0%)的情況下,傳感器網(wǎng)絡(luò)能夠采集2 496輪的數(shù)據(jù),而當(dāng)路由空洞被修復(fù)20%的情況下,傳感器網(wǎng)絡(luò)在死亡前能夠采集3 054輪數(shù)據(jù),當(dāng)路由空洞被修復(fù)為40%時(shí),傳感器網(wǎng)絡(luò)采集了3 662輪數(shù)據(jù),當(dāng)路由空洞被修復(fù)60%時(shí),能夠采集4 218次,而路由空洞被完全修復(fù)時(shí),能夠采集5 747次。路由空洞被完全修復(fù)后傳感器網(wǎng)絡(luò)的生存時(shí)間比不修復(fù)延長(zhǎng)了2.3倍。

5 總結(jié)

本文提出了一種能耗優(yōu)先的WSN路由空洞修復(fù)方法,首先定位出死亡節(jié)點(diǎn),由死亡節(jié)點(diǎn)組成路由空洞,然后提出一種路由空洞能否被完全修復(fù)的判斷方法,最后利用改進(jìn)的匈牙利算法派遣可移動(dòng)節(jié)點(diǎn)完成對(duì)路由空洞的修復(fù)。實(shí)驗(yàn)結(jié)果表明提出的路由空洞修復(fù)方法能夠有效的完成空洞修復(fù)并延長(zhǎng)了傳感器網(wǎng)絡(luò)的生存時(shí)間。后續(xù)工作將進(jìn)一步研究如何利用盡可能少的可移動(dòng)傳感器節(jié)點(diǎn)完成路由空洞的修復(fù)。