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