一種能耗優先的WSN路由空洞修復方法研究*

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

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

無線傳感器網絡主要功能是數據采集和轉發,由于無需布線、成本低、精度高等特點使其被廣泛應用于生產生活中的各個領域。如在林業方面,傳感器網絡被用于感知環境數據;在工業方面,傳感器網絡采集設備狀態數據和生產環境數據;在環保方面,傳感器網絡采集環境數據傳輸至服務器端進行監測等[1-4];由于傳感器網絡中采集終端數量龐大,數據在轉發過程中不同節點負載不同,負載重的節點能量容易提前耗盡,從而形成網絡路由空洞。空洞附近的傳感器節點在傳輸數據時需要繞過空洞,大大增加了數據轉發跳數,不利于網絡的長期生存。

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

上述大量的研究都重點關注無線傳感器網絡的感知覆蓋空洞修復問題,但感知空洞修復的理論很難應用在網絡路由空洞修復問題上,即使強行套用理論也會導致路由空洞修復的能耗和復雜度提高,對路由空洞修復問題是極不利的。

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

1 相關模型與假設

該章節首先介紹本文后續研究過程中使用到的相關模型,包括路由空洞模型、節點通訊能耗模型和可移動節點移動能耗模型,然后介紹了相關假設。

1.1 相關模型

1.1.1 路由空洞模型

隨著傳感器網絡的運行,不同節點轉發數據的負載不同,負載重的傳感器節點單位時間內的能耗高,而負載輕的節點單位時間內的能耗較低,因此整個網絡中會出現能耗梯度。當某些能耗高的節點能量耗盡后,就會形成路由空洞,如圖1中節點4、5、6、8所示。在沒出現網絡空洞時,傳感器節點1、2、3的數據轉發路徑如下所示:

節點1:1→4→5→6→7→Sink

節點2:2→4→5→6→7→Sink

節點3:3→8→6→7→Sink

當出現路由空洞以后,傳感器節點4、5、6、8能量耗盡,無法承擔中繼節點的角色,因此數據在網絡中轉發難度會增加,節點1、2、3的數據轉發路徑發生變化,如下所示:

節點1:1→9→10→11→12→7→Sink

節點2:中斷傳輸

節點3:中斷傳輸

傳感器節點1雖然能調整轉發路徑,但需要繞過空洞,轉發的次數明顯增加,而節點2、3無法將數據轉發至Sink節點,因此路由空洞對傳感器網絡的整體性能具有毀滅性的破壞。圖1中網絡路由空洞可用集合Vh={4、5、6、8}表示。

圖1 路由空洞模型圖

1.1.2 節點通訊能耗模型

傳感器節點間通訊能耗模型如圖2所示,該通訊能耗模型能夠科學的描述節點通訊過程中的能量消耗。節點數據的發送和接收能耗如式(1)、式(2)所示,發送數據過程中主要能耗產生在信號發射器和信號放大器兩個部件,且發送能耗與發射距離、數據包大小相關。數據接收能耗主要產生在信號接收電路。

圖2 節點通訊能耗模型

(1)

Erx=kEd

(2)

式(1)、式(2)中Ee表示發射電路和接收電路處理1 bit數據的能耗;k表示發送或接收數據包的大小;εamp1、εamp1表示信號放大電路將信號放大的倍數;d表示發送節點與接收節點的歐氏距離;D表示一個距離界限,如式(3)所示。

(3)

式中:hr、ht分別表示接收節點和發送節點的天線距離地面高度;λ為電磁波波長;L為常數。

1.1.3 節點移動能耗模型

利用可移動傳感器節點對網絡路由空洞進行修復,其能量消耗主要發生在移動過程中且消耗的能量與移動距離呈正比,移動1 m消耗的能量約為3.6 J[10-11]。

1.2 相關假設

①傳感器節點采用電池供電,能量消耗完后無法更換電池或從外界獲得能量。

②可移動節點和靜態節點按一定比例隨機均勻部署,且初始時刻可移動節點不參與網絡數據采集和轉發工作,僅供后續空洞修復使用。

③無線傳感器網絡中的節點已經通過定位算法或GPS等技術手段獲得了物理坐標。

④網絡中靜態傳感器的初始能量為Es,可移動傳感器節點的初始能量為Em,最大可移動距離為R,兩種傳感器節點的通訊半徑相同且都為r。

⑤傳感器網絡每隔固定時間進行一次數據采集,且本文的研究以參考文獻[12]的能耗均衡鏈路式路由協議為背景,進行路由空洞修復以及對整個網絡的性能進行分析。

2 路由空洞定位

當出現網絡路由空洞后,需要定位空洞中能量耗盡的傳感器節點(即死亡節點),才能派遣可移動節點對路由空洞進行修復。本文提出2種網絡空洞的定位方法,如下所示:

①如果傳感器節點本身可以獲取電池的剩余能量,則可將剩余能量值傳輸至服務器端,服務器端可根據節點的剩余能量值判斷即將產生或已經產生的路由空洞。

②如果傳感器節點無法獲取電池的剩余能量,此時定位路由空洞相對復雜。網絡在初始運行時刻,服務器端記錄能夠正常傳回數據的傳感器節點編號集合N0和傳感器節點的數據傳輸路徑集合Path={P1,P2,P3…Pi…Pm},Pi表示節點i的數據傳輸路徑,m為集合N0的元素總數。當網絡采集t輪數據后,服務器端重新統計能正常傳回數據的節點編號集合為Nt,此時可計算出無法正常傳回數據的傳感器節點編號Nd,如式(4)所示。

Nd=N0-Nt

(4)

無法正常傳輸數據至服務器端的節點可能包含兩種情況:(a)該節點能量耗盡;(b)該節點數據傳輸路徑中某些節點能量耗盡導致傳輸中斷。對應到數據傳輸路徑Pi上可分為2種情況,如圖3所示。

圖3 數據傳輸路徑圖

表1 路由空洞定位與修復方法

3 路由空洞修復

第2章節介紹了2種路由空洞定位方法,這2種方法都可在實際的無線傳感器網絡中實現。本章介紹利用可移動節點修復路由空洞,如圖4所示,路由空洞由節點n1～n5組成,通過派遣v1～v5可移動節點到死亡節點位置,替代死亡節點的數據采集和中繼功能,即可修復空洞。如果基于最近原則派遣可移動節點,則5個可移動節點的移動距離之和不一定最短的,因為最近派遣方法容易陷入局部最優問題。為使修復路由空洞的代價之和最小,且在可移動節點移動距離和數量都有限的情況下盡可能修復空洞,研究了一種空洞修復判斷方法和可移動節點最優派遣方法。

圖4 空洞修復過程圖

3.1 空洞修復判斷

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

假設網絡路由空洞為{n1,n2,n3},如圖5所示。當可移動節點的最大移動距離為R時,可移動到死亡節點n1、n2、n3的移動節點集合分別表示為S1={v1,v2}、S2={v2}、S3={v3,v4,v5},當同時滿足以下三個條件時,能夠完全修復路由空洞。

圖5 修復判斷方法圖

①|S1∪S2∪……St|≥t,t為路由空洞中死亡節點總數。

②Si≠?,1≤i≤t。

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

基于上述方法,如果判斷傳感器網絡路由空洞內所有死亡節點都可被移動節點替換,則可完成路由空洞的完全修復,但在不能完全修復的情況下,盡最大可能修復死亡節點。

3.2 最優派遣

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

圖6 移動節點與修復位置情況圖

(5)

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

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

(6)

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

(7)

針對上述三種情況,構建相應的匈牙利代價矩陣后,根據傳統的匈牙利算法步驟即可得到最優的可移動節點派遣方法,使得所有可移動節點派遣到死亡節點位置后移動距離之和最短,從而實現修復路由空洞能耗最低的目的。

4 仿真實驗

通過仿真實驗驗證本文提出的路由空洞修復方法(RVREP)各方面的性能,實驗采用i7處理器、8 G內存的PC機為硬件環境,MATLAB仿真平臺為軟件環境。在初始時刻將靜態傳感器節點和可移動傳感器節點均勻的部署到長、寬都為250m的正方形區域中。傳感器網絡中的節點按照參考文獻[12]提出的能耗均衡鏈路式路由協議進行數據采集和傳輸(因為該方法在碰到路由空洞時會合理的選擇其他轉發路徑),其中Sink節點位于部署區域上邊緣的正中間。實驗過程中隨機的從網絡中選擇num個節點作為死亡節點(即形成網絡路由空洞),實驗相關參數如表2所示。由于在路由空洞方面的研究較少,更重要的是本文算法自身性能的驗證,因此采用貪婪算法GREEDY進行對比,該方法在修復路由空洞時,派遣距離死亡節點最近的可移動節點。

4.1 路由空洞修復率

當路由空洞大小固定的情況下(即死亡節點數量固定),隨著網絡中部署的可移動節點數量增加,理論上路由空洞被完全修復的概率會逐漸提高。本實驗研究路由空洞大小固定時,被完全修復的概率與可移動節點數量之間的關系。首先在部署區域中均勻部署150個靜態傳感器節點,然后隨機部署mn個可移動節點,接著隨機選擇30個靜態節點進入休眠狀態模擬網絡路由空洞,利用可移動節點對路由空洞進行修復。100次獨立重復實驗的平均結果如圖7所示,橫坐標為部署的可移動節點數量,縱坐標為路由空洞被完全修復的概率。本文提出的RVREP方法可基于3.1小節的方法判斷路由空洞能否被完全修復。

表2 實驗參數表

圖7 可移動節點數量結果圖

實驗結果表明隨著部署區域中可移動節點數量增加,本文提出的RVREP方法和貪婪算法GREEDY的完全修復率都快速提高,當可移動節點增加到一定數量時,完全修復率提高速度變緩,因為在初始時刻,修復路由空洞的可移動節點非常緊缺,所以修復率提高速度較快,而當可移動節點數量較多時,可移動節點數量趨于飽和,因此隨著可移動節點數量繼續增加,完全修復率提高速度逐漸變慢。且RVREP方法的完全修復率一直都高于GREEDY方法,當可移動節點數量為70個時,RVREP方法的路由空洞完全修復率已經達到了95%左右,而GREEDY方法僅為69%左右,因為RVREP方法在修復空洞前會綜合考慮空洞附近的可移動節點,實現最優調配,而GREEDY方法只派遣距離最近的可移動節點,會陷入局部最優問題,導致其他死亡節點不能被修復。

當部署區域內可移動節點數量為90個時,網絡路由空洞大小發送變化,則完全修復率也會發生變化,路由空洞越大,則完全修復率越低。實驗結果如圖8所示,橫坐標為路由空洞大小,用死亡節點數量表示,縱坐標為完全修復率。

圖8 路由空洞大小結果圖

圖9 平均能耗圖

實驗結果表明當可移動節點數量固定時,隨著路由空洞大小增加,完全修復率會降低。當路由空洞大小相同時,RVREP方法的完全修復率高于GREEDY方法,主要原因是RVREP方法中采用匈牙利算法修復路由空洞,在盡可能修復的前提下實現最優派遣,而GREEDY方法修復空洞極易陷入局部最優。

4.2 路由空洞修復能耗

可移動節點修復路由空洞過程中消耗的能量越低,則移動節點替代死亡節點后剩余的能量越多,越有利于傳感器網絡的長期生存。為驗證空洞修復能耗,在部署區域中均勻部署150個靜態傳感器節點,同時部署的可移動節點數量大于等于100個,路由空洞大小為30(即路由空洞由30個死亡節點組成),該條件確保了RVREP方法和GREEDY方法的路由空洞完全修復率達到100%左右(可見4.1小節實驗)。可移動節點的移動能耗基于第1節的節點移動能耗模型計算,實驗結果如圖9所示,橫坐標為可移動節點數量,縱坐標為每個可移動節點修復路由空洞的平均能耗。

實驗結果表明隨著可移動節點數量增加,完全修復路由空洞的平均能耗逐漸減低,因為可移動節點數量增加,修復相同的路由空洞所需要移動的平均距離逐漸減低,因此對應的能耗也呈降低趨勢。且本文提出的RVREP方法的平均能耗低于GREEDY方法,因為RVREP方法能夠確保修復路由空洞的移動距離之和最短,而GREEDY方法僅保證修復單個死亡節點的移動距離最短,但不能確保修復整個路由空洞移動節點的移動距離總和最短。同時隨著可移動節點數量增加,兩種方法的能耗趨于接近,因為可移動節點數量增加,密度也會增加,會導致死亡節點附近有足夠的可移動節點用于修復,因此兩種方法的差距逐漸降低。

4.3 網絡生存時間

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

表3 網絡生存時間表

實驗結果表明在不修復路由空洞(修復率為0%)的情況下,傳感器網絡能夠采集2 496輪的數據,而當路由空洞被修復20%的情況下,傳感器網絡在死亡前能夠采集3 054輪數據,當路由空洞被修復為40%時,傳感器網絡采集了3 662輪數據,當路由空洞被修復60%時,能夠采集4 218次,而路由空洞被完全修復時,能夠采集5 747次。路由空洞被完全修復后傳感器網絡的生存時間比不修復延長了2.3倍。

5 總結

本文提出了一種能耗優先的WSN路由空洞修復方法,首先定位出死亡節點,由死亡節點組成路由空洞,然后提出一種路由空洞能否被完全修復的判斷方法,最后利用改進的匈牙利算法派遣可移動節點完成對路由空洞的修復。實驗結果表明提出的路由空洞修復方法能夠有效的完成空洞修復并延長了傳感器網絡的生存時間。后續工作將進一步研究如何利用盡可能少的可移動傳感器節點完成路由空洞的修復。