WSN中引入移動節(jié)點的路由協(xié)議設(shè)計與仿真*

張潤蘭，劉真祥

(1. 貴州大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,貴州 貴陽 550025；2. 貴州電視廣播大學(xué),貴州 貴陽 550004)

?

WSN中引入移動節(jié)點的路由協(xié)議設(shè)計與仿真*

張潤蘭1，劉真祥2

(1. 貴州大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,貴州 貴陽 550025；2. 貴州電視廣播大學(xué),貴州 貴陽 550004)

Foundation Item:Guizhou Province Natural Science Foundation(No[2011]2204); Guizhou University Graduate Innovation Fund Project (No.2015017)

摘要：對于節(jié)點部署不均或者節(jié)點死亡而導(dǎo)致的監(jiān)測盲區(qū)，可通過在WSN中引入移動節(jié)點來修復(fù)。提出一種修復(fù)策略，可較為及時、準(zhǔn)確地修復(fù)監(jiān)測盲區(qū)，同時考慮節(jié)點的能量均衡問題。在LEACH-M分簇路由算法的基礎(chǔ)上，給出了一種按節(jié)點能量分配工作量的能量均衡分簇路由算法LEACH-M-G，并運用MATLAB仿真工具進行了仿真分析。仿真結(jié)果表明，所提出的監(jiān)測盲區(qū)修復(fù)策略、以及LEACH-M-G路由能有效地修復(fù)監(jiān)測盲區(qū)，均衡網(wǎng)絡(luò)能量、延長網(wǎng)絡(luò)生命周期。

關(guān)鍵詞：WSN移動節(jié)點;監(jiān)測盲區(qū);路由協(xié)議仿真

0引言

在無線傳感器網(wǎng)絡(luò)(WSN)的實際應(yīng)用中，由于監(jiān)測區(qū)域地形和環(huán)境的差異，傳感節(jié)點的初始部署難以完全監(jiān)測整個區(qū)域，存在不能被感知的監(jiān)測盲區(qū)。此外，在網(wǎng)絡(luò)運行中，由于簇頭節(jié)點通常要承擔(dān)大量的數(shù)據(jù)轉(zhuǎn)發(fā)工作，可能導(dǎo)致能量過快消耗而過早死亡，也將出現(xiàn)新的監(jiān)測盲區(qū)。解決好監(jiān)測盲區(qū)問題，以提高監(jiān)測覆蓋率、充分利用WSN的性能，一直是WSN應(yīng)用研究的重要內(nèi)容之一[1]。

近年來，業(yè)界對WSN監(jiān)測盲區(qū)問題進行了大量的研究。文獻[2]提出一種節(jié)點優(yōu)化部署方法來實現(xiàn)監(jiān)測區(qū)域的全覆蓋，但對節(jié)點過早死亡而出現(xiàn)的監(jiān)測盲區(qū)不能顧及。對此，文獻[3]提出在傳統(tǒng)的WSN中引入可移動的傳感節(jié)點對選擇性的目標(biāo)進行覆蓋。文獻[4]采用在WSN中加入移動節(jié)點對覆蓋洞問題進行修復(fù)，提出三角形貼片式來逐步增加移動節(jié)點的方法，但在移動節(jié)點數(shù)目有限的網(wǎng)絡(luò)中無法完成修復(fù)。文獻[5-6]提出一種基于向量代數(shù)的分布式方法和基于誤警率的概率探測感知模型來確定節(jié)點的移動方向，通過感知半徑來確定節(jié)點的移動距離，節(jié)約了能量消耗但網(wǎng)絡(luò)延遲較大。文獻[7]中考慮移動節(jié)點的距離和剩余能量來作為選擇移動節(jié)點的標(biāo)準(zhǔn)，基于Voronoi圖的覆蓋增強算法和基于虛擬力的目標(biāo)覆蓋算法進行改進。文獻[8]給出另一種級聯(lián)的移動策略，以避免由于貪婪算法導(dǎo)致的節(jié)點死亡問題，文獻[9]提出改變能量洞的形狀來提高覆蓋率。文獻[10]根據(jù)移動節(jié)點的個數(shù)將網(wǎng)絡(luò)平均劃分成與移動節(jié)點個數(shù)相等的服務(wù)區(qū)。但當(dāng)網(wǎng)絡(luò)中移動節(jié)點很少的情況下，可能導(dǎo)致劃分的網(wǎng)絡(luò)服務(wù)區(qū)較少從而造成網(wǎng)絡(luò)失效。文獻[11]提出在WMN中使用基于免疫算法的QoS路由算法，利用免疫算法的尋優(yōu)能力，實現(xiàn)了WMN的多約束條件下的最優(yōu)路徑選擇。文獻[12]采用LEACH-M實現(xiàn)WSN中移動節(jié)點擔(dān)任簇頭節(jié)點時與其成員幾點間的聯(lián)通性，動態(tài)的劃分傳輸數(shù)據(jù)周期，實現(xiàn)節(jié)約能量的目的。

在這些研究中存在兩方面缺陷：其一是假設(shè)存在冗余移動節(jié)點的條件下提出的；其二是路由協(xié)議沒有考慮WSN能量均衡的問題。基于以往的研究成果，本文提出一種能量均衡的監(jiān)測盲區(qū)修復(fù)策略，以求能更為準(zhǔn)確地修復(fù)監(jiān)測盲區(qū)，同時考慮節(jié)點的能量均衡問題。在LEACH-M分簇路由算法的基礎(chǔ)上，研究按節(jié)點能量分配工作量的能量均衡分簇路由算法，并進行仿真分析驗證。

1LEACH-M基本思想

LEACH-M(Low Energy Adaptive Clustering Hierarchy- Mobile )是在LEACH(Low Energy Adaptive Clustering Hierarchy)協(xié)議的基礎(chǔ)上引入了移動節(jié)點形成的路由協(xié)議。LEACH-M的基本思想是確認(rèn)移動節(jié)點是否能與特定的簇頭節(jié)點通信。在數(shù)據(jù)通信階段采用應(yīng)答機制，在簇成員節(jié)點的通信時間槽內(nèi)，不是簡單地直接發(fā)送數(shù)據(jù)到簇頭，而是等待一個來自簇頭的數(shù)據(jù)發(fā)送請求Request_data。只有收到Request_data，成員節(jié)點才發(fā)送數(shù)據(jù)給所屬簇頭。

2監(jiān)測盲區(qū)修復(fù)策略

此對于一個部署了WSN的監(jiān)測區(qū)域中，假設(shè)存在許多監(jiān)測盲區(qū)和若干移動節(jié)點，為精準(zhǔn)高效修復(fù)監(jiān)測盲區(qū)，可通過移動節(jié)點按以下策略，對已有的監(jiān)測盲區(qū)進行實時修復(fù)。

將監(jiān)測區(qū)域劃分為若干個正方形單元格，如圖1所示。其中，藍色的單元格表示有監(jiān)測盲區(qū)存在，白色單元格表示單元格內(nèi)存在移動節(jié)點。

圖1　監(jiān)測區(qū)域劃分

為避免多個節(jié)點同時移動到同一個盲區(qū)，即出現(xiàn)所謂的“乒乓效應(yīng)”，可在監(jiān)測區(qū)域內(nèi)，構(gòu)造一條移動節(jié)點修復(fù)監(jiān)測盲區(qū)的路徑，保證監(jiān)測區(qū)域的所有盲區(qū)都會被所構(gòu)建的路徑覆蓋，構(gòu)造路徑如圖1所示，移動節(jié)點按照箭頭方向移向盲區(qū)，因為每個移動節(jié)點移動距離較小，比直接一個節(jié)點移動到相隔大于一個劃分區(qū)域的盲區(qū)所消耗的能量要小，故采用按箭頭方向的構(gòu)造路徑方法修復(fù)盲區(qū)并實現(xiàn)均衡負(fù)載的目的。對于圖1所示的監(jiān)測區(qū)域，修復(fù)路徑可設(shè)為：

C1→C2→C3→C4→…→C11→C12→C1→…

按設(shè)定的修復(fù)路徑，如圖1所示，C2區(qū)域存在監(jiān)測盲區(qū)，C1中的節(jié)點沿著路徑移動到C2，而相鄰的C3、C11、C12都不會去修復(fù)這個盲區(qū)，從而避免了“乒乓效應(yīng)”，一定程度上保證了節(jié)點的能量均衡和盲區(qū)修復(fù)效果。

對于圖1所示的監(jiān)測區(qū)域，按上述的盲區(qū)修復(fù)策略，經(jīng)由移動節(jié)點的一個輪次移動修復(fù)，在Matlab仿真軟件環(huán)境下實現(xiàn)監(jiān)測區(qū)域的監(jiān)測全覆蓋，存在盲區(qū)如圖2所示，修復(fù)盲區(qū)如圖3所示。

圖2監(jiān)測盲區(qū)修復(fù)前

圖3　監(jiān)測盲區(qū)修復(fù)后

3改進型分簇路由算法LEACH-M-G

3.1簇頭的選舉

簇頭的選舉將考慮節(jié)點活性、節(jié)點間平均距離、節(jié)點數(shù)偏差三個因素。

(1)節(jié)點活性(Node Activity, NA)，節(jié)點根據(jù)自身的剩余能量、移動速度和方向確定自己在一個區(qū)域內(nèi)的活性。

(3)節(jié)點數(shù)偏差(Deviation of Node Number),δND，定義移動節(jié)點周圍一跳節(jié)點范圍數(shù)與最優(yōu)節(jié)點數(shù)之差。δND=|N-N0|，其中N為移動節(jié)點一跳范圍內(nèi)鄰居節(jié)點數(shù)目，N0為最優(yōu)化節(jié)點數(shù)。

根據(jù)節(jié)點的活性、節(jié)點間距離以及節(jié)點數(shù)偏差三方面的加權(quán)和來決定一個節(jié)點是否成為簇頭，節(jié)點的加權(quán)和F值計算如下：

F=a1*NA+a2/d+a3/δND

(1)

式中：a1，a2，a3為權(quán)重因子,a1+a2+a3=1。根據(jù)網(wǎng)絡(luò)環(huán)境的不同，權(quán)重因子不同。簇頭選擇結(jié)束，當(dāng)所有移動簇頭都將數(shù)據(jù)向基站發(fā)送完以后，為了達到能力均衡的目的，需要從新進行簇頭選擇。每一輪數(shù)據(jù)傳輸周期T，若簇頭的移動速度較快，那么數(shù)據(jù)發(fā)送丟失率就會相應(yīng)的增加，此時就應(yīng)該盡快的實行簇頭更新，以免出現(xiàn)不但浪費了能量，而且數(shù)據(jù)發(fā)送率也低的情況，反之亦然，因此本文采用的傳輸周期T的計算方法如下(2)。

(2)

3.2簇間路由

分簇完成后，成員節(jié)點將消息數(shù)據(jù)發(fā)送給簇頭節(jié)點，簇頭節(jié)點對接收到消息數(shù)據(jù)進行融合處理，然后進行簇間路由。

簇間路由時，基站節(jié)點向成員節(jié)點廣播hello消息包，消息包hello中包括基站節(jié)點的位置、簇頭節(jié)點的ID值、簇間的平均剩余能量E，其格式如圖4所示。接收到hello消息包的簇頭節(jié)點計算簇內(nèi)的平均剩余能量E，并將E值和自身位置信息存入hello消息包，再返回給基站節(jié)點。

基站節(jié)點通過比較各個簇內(nèi)的平均剩余能量，選擇平均剩余能量最大的簇，再次廣播message消息包，消息包message中包含所選簇頭的ID值和生命周期T，其格式如圖4所示。

圖4數(shù)據(jù)包格式

接收到message消息包的簇頭節(jié)點，把message包中的簇頭節(jié)點的ID值和自己的ID值相比，若相同則開始向基站節(jié)點發(fā)送數(shù)據(jù)。否則，丟棄該message包，基站節(jié)點在間隔一段時間后，將再次發(fā)起路由選擇。

4仿真實驗

為驗證監(jiān)測盲區(qū)修復(fù)策略的可行性和LEACH-M-G路由算法的有效性，運用MATLAB仿真工具，對引入移動節(jié)點的WSN網(wǎng)絡(luò)模型進行了仿真分析。

仿真環(huán)境的設(shè)定：100 個靜態(tài)傳感器節(jié)點隨機地分布在400 m×400 m的區(qū)域內(nèi)，20 個移動節(jié)點按照既定的移動路徑在監(jiān)測區(qū)域內(nèi)移動。每一個移動節(jié)點移動的速度上界為v。每次移動節(jié)點從[0，v]隨機選擇一個步長，從[0°，2π]隨機選擇一個角度。移動一個隨機的時間[0，60]s，間隔[0， 300]s?；镜淖鴺?biāo)為(400 m，400 m) 。

移動節(jié)點根據(jù)式(3)計算自己的移動簇頭的F值。為在動態(tài)網(wǎng)絡(luò)環(huán)境下形成相對穩(wěn)定的簇結(jié)構(gòu)，可將節(jié)點活動性因素NA作為最重要影響因子，取a1=0.5,a2=0.3，a3=0.2。

表1　參數(shù)設(shè)置

仿真將從節(jié)點的活動性對網(wǎng)絡(luò)性能的影響，來研究所提出的方法對能耗大小和動態(tài)拓?fù)涞倪m應(yīng)性。如圖5所示，LEACH-M算法在經(jīng)過了1450輪的時候節(jié)點就全部死亡，LEACH-M-G算法明顯優(yōu)于LEACH-M算法。這是由于LEACH-M對移動節(jié)點的處理復(fù)雜，移動節(jié)點從被發(fā)現(xiàn)到與簇頭正常通信需要至少3個TDMA幀，即使節(jié)點已經(jīng)不在原來的感知范圍內(nèi)，簇頭任然繼續(xù)發(fā)送詢問數(shù)據(jù)，這就導(dǎo)致了能量的浪費，縮短網(wǎng)絡(luò)生命周期。而在LEACH-M-G算法中，當(dāng)簇頭發(fā)送hello包給節(jié)點后，在一個時間片內(nèi)沒有收到節(jié)點的回復(fù)消息，則標(biāo)記節(jié)點為移動節(jié)點，并停止對節(jié)點的信息發(fā)送，從而節(jié)省了能量，延長網(wǎng)絡(luò)生命周期。

圖5　LEACH-M和LEACH-M-G的生命周期對比

負(fù)載均衡因子是指網(wǎng)絡(luò)運行中各節(jié)點承擔(dān)工作強度的大小。如圖6所示，負(fù)載均衡因子隨著移動節(jié)點的移動速度增大而減小。這是因為隨著節(jié)點移動速度變化范圍的增大，移動節(jié)點與簇頭節(jié)點之間的速度差異也增大，網(wǎng)絡(luò)中簇頭節(jié)點的能量等級的差異也逐漸增大，因此簇間的負(fù)載均衡程度下降。但從總體趨勢上看，LEACH-M-G算法的負(fù)載均衡程度還是優(yōu)于比LEACH-M。

圖6　負(fù)載均衡因子隨節(jié)點移動速度的變化

如圖7所示，網(wǎng)絡(luò)的生命周期隨著移動節(jié)點速度的增大呈現(xiàn)出先增后減的趨勢。這是因為當(dāng)節(jié)點移動速度過低時，大量的數(shù)據(jù)包無法及時傳輸而致使能耗增加。當(dāng)移動速度過大時，靜態(tài)的節(jié)點與簇頭節(jié)點之間通信時間較短，致使報文分片無法完整傳輸，造成通信機會不必要的浪費，縮短了網(wǎng)絡(luò)生命周期。但從總體運行結(jié)果上看，LEACH-M-G的通信效益優(yōu)于LEACH-M。

圖7生命周期隨移動節(jié)點速度的變化

5結(jié)語

在WSN的實際應(yīng)用中，存在由于節(jié)點部署不均或節(jié)點死亡而導(dǎo)致的監(jiān)測盲區(qū)問題。對此，可在WSN中引入移動節(jié)點，通過移動節(jié)點的實時移動來修復(fù)監(jiān)測盲區(qū)?；谝酝难芯砍晒覀兲岢鲆环N按優(yōu)化移動路徑的監(jiān)測盲區(qū)的修復(fù)策略，可較為及時、準(zhǔn)確地修復(fù)監(jiān)測盲區(qū)，同時考慮節(jié)點的能量均衡問題。在LEACH-M分簇路由算法的基礎(chǔ)上，給出了一種按節(jié)點能量分配工作量的能量均衡分簇路由算法LEACH-M-G，并運用MATLAB仿真工具進行了仿真分析。仿真結(jié)果表明，所提出的監(jiān)測盲區(qū)修復(fù)策略、以及LEACH-M-G路由能有效地修復(fù)監(jiān)測盲區(qū)，均衡網(wǎng)絡(luò)能量、延長網(wǎng)絡(luò)生命周期。

參考文獻：

[1]Yung CChih, Yu LChih, Cheng Cw, et al. An Energy-Balanced Swept-Coverage Mechanism for Mobile WSNs[C]. Wireless Networks. 2013:871-889.

[2]BAI Xi, YUN Z Q, XUAN D, et al. Optimal Patterns for Four-Connectivity and Full Coverage in Wireless Sensor Networks[C].IEEE Transactions on Mobile Computing,2010:435-448.

[3]趙小芳,馮秀芳. 無線傳感器網(wǎng)絡(luò)中基于移動節(jié)點的目標(biāo)覆蓋方法研究[J]. 電腦開發(fā)與應(yīng)用，2010,23(06)：63-65.

ZHAO Xiao-fang, FENG Xiu-fang. Research on Target Coverage based on Mobile Node in Wireless Sensor Network[J] Computer Development & Applications. 2010. 23(06) ：63-65.

[4]王良民,李菲. 基于移動節(jié)點的無線傳感器網(wǎng)絡(luò)覆蓋洞修復(fù)方法[J]. 通信學(xué)報，2011,32(04):1-8.

WANG Liang-min, LI Fei. Resilient Method for Recovering Coverage Holes of Wireless Sensor Networks by using Mobile Nodes[J].Journal on Communications. 2011,32(04):1-8.

[5]黃月,吳成東,張云洲等. 基于移動節(jié)點的無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化[J].東北大學(xué)學(xué)報：自然科學(xué)版,2012,33(02):165-168.

HUANG Yue, WU Cheng-dong, ZHANG Yun-zhou, et al. Coverage Optimization of Wireless Sensor Networks based on Mobile Nodes[J].Journal of Northeastern University(Natural Science), 2012.33(02):165-168.

[6]鄧亞平,吳川平. 基于移動節(jié)點的無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化研究[J]. 計算機應(yīng)用研究,2012,29(08):3137-3139,3144.

DENG Ya-ping, WU Chuan-ping. Research on Coverage Optimization of Wireless Sensor Networks based on Mobile Sensors [J].Application Research of Computers. 2012,29(08) :3137-3139,3144.

[7]劉香愛.馮煙利. 基于能量感知的無線傳感器網(wǎng)絡(luò)覆蓋問題研究[D]. 山東：山東師范大學(xué)，2012.

LIU Xiang-ai, FENG Yan-li. Wireless Sensor Networks based on Energy-Aware Overlay Research[D]. Shandong Normal University, 2012.

[8]JIANG Z, WU J, Agah A, et al. Topology Control for Secured Coverage in Wireless Sensor Networks[C]. IEEE MASS,2007:1-6.

[9]CHANG C, CHANG H, LIU H,et al. On Providing Temporal Full-Coverage by Applying Energy Efficient Hole-Movement Strategies for Mobile WSNs[C]. IEEE WCNC,2007:2278-2783.

[10]黃思宇，高強，費禮等. 無線傳感器網(wǎng)絡(luò)中分區(qū)移動服務(wù)路由機制[J]. 通信技術(shù)，2010,43(03):98-101.

HUANG Si-yu, GAO Qiang, FEI Li, et al. A Routing Mechanism based on Sub-Area Mobile Service in Wireless Sensor Networks[J].Communications Technology, 2010,43(03):98-101.

[11]畢曉君,李美翠. WMN中基于免疫算法的QoS路由研究[J]. 通信技術(shù),2011,44(02):70-72,84.

BI Xiao-jun, LI Mei-cui. Immune Algorithm-based QoS-Constrained Routing for Wireless Mesh Network[J]. Communications Technology, 2011, 44(02):70-72,84.

[12]王璨,駱堅,張大方等.一種基于移動性的無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J].計算機工程與科學(xué)，2012,34(03)：6-12.

WANG Can, LUO Jian, ZHANG Da-fang,et al. A Mobility-based Cluster Routing Wireless Protocol for Mobile Wireless Sensor Networks[J].Computer Engineering & Science. 2012, 34(03):6-12.

張潤蘭(1990—)，女，碩士研究生，主要研究方向為計算機網(wǎng)絡(luò)；

劉真祥(1955—)，男，碩士生導(dǎo)師，主要研究方向為計算機網(wǎng)絡(luò)。

Routing Protocol Design and Simulation of Wireless

Sensor Network with Introduced Mobile Node

ZHANG Run-lan1， LIU Zhen-xiang2

(1.College ofComputer Science and Technology, Guizhou University, Guiyang Guizhou 550025, China;

2.Guizhou Radio & TV University, Guiyang Guizhou 550004, China)

Abstract：Blind spot caused by uneven node deployment or node death, could be restored by introducing mobile node into WSN. A repair strategy is proposed to restore the monitoring blind spots timely and accurately, and this strategy also gives consideration of node energy balance. Based on the LEACH-M clustering routing algorithm, an energy balance clustering routing algorithm LEACH-M-G is proposed which could distribute workload in accordance with node energy.Simulation with MATLAB indicates that the proposed repair strategy for monitoring blind spot and LEACH-M-G route could effectively repair monitoring blind spots, balance the network energy and prolong the network lifecycle.

Key words：WSN with mobile sensor node; monitoring the blind spot; routing protocol simulation

作者簡介：

中圖分類號：TP393.2

文獻標(biāo)志碼：A

文章編號：1002-0802(2015)07-0825-05

基金項目：貴州省自然科學(xué)基金項目(黔科合J字[2011]2204號)；貴州大學(xué)研究生創(chuàng)新基金資助項目(No.2015017)

收稿日期：修回日期：2015-05-27Received date:2015-02-05；Revised date：2015-05-27

doi:10.3969/j.issn.1002-0802.2015.07.015