WSN中引入移動節點的路由協議設計與仿真*

張潤蘭，劉真祥

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

?

WSN中引入移動節點的路由協議設計與仿真*

張潤蘭1，劉真祥2

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

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

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

關鍵詞：WSN移動節點;監測盲區;路由協議仿真

0引言

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

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

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

1LEACH-M基本思想

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

2監測盲區修復策略

此對于一個部署了WSN的監測區域中，假設存在許多監測盲區和若干移動節點，為精準高效修復監測盲區，可通過移動節點按以下策略，對已有的監測盲區進行實時修復。

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

圖1　監測區域劃分

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

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

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

對于圖1所示的監測區域，按上述的盲區修復策略，經由移動節點的一個輪次移動修復，在Matlab仿真軟件環境下實現監測區域的監測全覆蓋，存在盲區如圖2所示，修復盲區如圖3所示。

圖2監測盲區修復前

圖3　監測盲區修復后

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

3.1簇頭的選舉

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

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

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

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

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

(1)

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

(2)

3.2簇間路由

分簇完成后，成員節點將消息數據發送給簇頭節點，簇頭節點對接收到消息數據進行融合處理，然后進行簇間路由。

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

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

圖4數據包格式

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

4仿真實驗

為驗證監測盲區修復策略的可行性和LEACH-M-G路由算法的有效性，運用MATLAB仿真工具，對引入移動節點的WSN網絡模型進行了仿真分析。

仿真環境的設定：100 個靜態傳感器節點隨機地分布在400 m×400 m的區域內，20 個移動節點按照既定的移動路徑在監測區域內移動。每一個移動節點移動的速度上界為v。每次移動節點從[0，v]隨機選擇一個步長，從[0°，2π]隨機選擇一個角度。移動一個隨機的時間[0，60]s，間隔[0， 300]s。基站的坐標為(400 m，400 m) 。

移動節點根據式(3)計算自己的移動簇頭的F值。為在動態網絡環境下形成相對穩定的簇結構，可將節點活動性因素NA作為最重要影響因子，取a1=0.5,a2=0.3，a3=0.2。

表1　參數設置

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

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

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

圖6　負載均衡因子隨節點移動速度的變化

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

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

5結語

在WSN的實際應用中，存在由于節點部署不均或節點死亡而導致的監測盲區問題。對此，可在WSN中引入移動節點，通過移動節點的實時移動來修復監測盲區。基于以往的研究成果，我們提出一種按優化移動路徑的監測盲區的修復策略，可較為及時、準確地修復監測盲區，同時考慮節點的能量均衡問題。在LEACH-M分簇路由算法的基礎上，給出了一種按節點能量分配工作量的能量均衡分簇路由算法LEACH-M-G，并運用MATLAB仿真工具進行了仿真分析。仿真結果表明，所提出的監測盲區修復策略、以及LEACH-M-G路由能有效地修復監測盲區，均衡網絡能量、延長網絡生命周期。

參考文獻：

[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]趙小芳,馮秀芳. 無線傳感器網絡中基于移動節點的目標覆蓋方法研究[J]. 電腦開發與應用，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]王良民,李菲. 基于移動節點的無線傳感器網絡覆蓋洞修復方法[J]. 通信學報，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]黃月,吳成東,張云洲等. 基于移動節點的無線傳感器網絡覆蓋優化[J].東北大學學報：自然科學版,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]鄧亞平,吳川平. 基于移動節點的無線傳感器網絡覆蓋優化研究[J]. 計算機應用研究,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]劉香愛.馮煙利. 基于能量感知的無線傳感器網絡覆蓋問題研究[D]. 山東：山東師范大學，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]黃思宇，高強，費禮等. 無線傳感器網絡中分區移動服務路由機制[J]. 通信技術，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]. 通信技術,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]王璨,駱堅,張大方等.一種基于移動性的無線傳感器網絡分簇路由協議[J].計算機工程與科學，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—)，女，碩士研究生，主要研究方向為計算機網絡；

劉真祥(1955—)，男，碩士生導師，主要研究方向為計算機網絡。

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

文獻標志碼：A

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

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

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

doi:10.3969/j.issn.1002-0802.2015.07.015