基于移动节点的无线传感器网络覆盖空洞修复方法

王 珊， 王庆生， 樊茂森

(太原理工大学 计算机科学与技术学院，山西 太原 030024)

基于移动节点的无线传感器网络覆盖空洞修复方法

王 珊， 王庆生， 樊茂森

(太原理工大学 计算机科学与技术学院，山西 太原 030024)

无线传感器网络(WSNs)一旦产生覆盖空洞，则会严重影响网络性能，针对此问题，提出了一种基于移动节点的覆盖空洞修复算法——联合补丁法，该算法按照预先制定的缝制方案把所需的移动节点“缝制”成一块大的“布”，然后对空洞进行直接修复。首先,在理论上证明了该算法的性能;其次,用Matlab进行仿真实验，并与基于移动节点的三角形逐个贴片修复算法(PATT)在所需节点数和冗余度两方面进行对比；最后，对算法的稳定性进行了分析。最终表明：该算法具有较高的覆盖率和较低的冗余度。

无线传感器网络； 空洞修复； 移动节点

0 引 言

无线传感器网络(wireless sensor networks,WSNs)在军事、防灾害、工业监测等众多领域都有广泛应用[1]。然而在实际运用中，由于部署不合理、故障、攻击或能耗不均使得一些节点提前死亡，导致网络中产生覆盖空洞，从而严重影响采集数据的完整性，因此,对覆盖空洞进行修复是保证网络可靠性的必要手段。

近年来，各专家学者提出了多种覆盖空洞修复方法[2～6]，总体来说可以分为两大类，一类是基于仿生智能算法的修复策略，如蒋丹提出的“一种蚁群算法进行空洞修复”[7]，但此方法容易使同一空洞被多个移动节点发现，从而导致被重复修复，造成极大浪费；另一类是基于几何图形的修复策略，如王良民等人提出的“基于移动节点的三角形逐个贴片修复方法(PATT)”[8]，该方法虽然具有较高的覆盖率，但是冗余度同样较高，这样移动节点利用率便会下降。针对此问题，本文提出了一种新的基于几何图形的空洞修复方法——联合补丁法，它在满足较高覆盖率的同时，具有较低的节点冗余度。

1 基本假设

为方便描述和讨论，下面做如下假设：

1)本文中所有静态节点和移动节点都同构，初始能量、数据处理及通信能力均相同。不同之处在于静态节点能量无法得到补充，而移动节点能量能得到补充，且能在控制下自行移动；

2)传感器节点通信距离Rc为感知距离Rs的2倍，即Rc=2Rs；

3)节点感知范围是以节点为圆心，Rs为半径的圆，并称之为感知圆[9]；

4)覆盖率大于90 %的网络满足可靠性要求[8]。

2 联合补丁法

现有的几何修补方法都是向空洞中逐个添加移动节点进行修复，在这类方法中，可以认为，每添加一个移动节点，就相当于在空洞中缝制了一小块补丁。因此，受上述思维启发，本文提出了一种新的空洞修复方法——联合补丁法，该方法不同之处在于它不是逐个添加移动节点进行修复的，而是根据空洞形状把所有“补丁”缝制成一块大的“布”，然后再把这块“布”移植到空洞中进行直接修复。然而，这些补丁按何种方式进行缝制能具有较好的性能，以下提出了两种缝制方案。

2.1 方案一

图1 方案一

2.2 方案二

图2 方案二

2.3 算法描述

基于以上两种方案，下面以方案二为例描述空洞的修复过程：

1)在已被检测到的空洞多边形上随机选取一点Ai，并在此多边形上求距离Ai最远的一个点Aj；

2)在线段AiAj之间，从Ai开始，按照方案二中同组节点的约束条件逐渐生成节点序列，并称此序列为基准节点序列；

3)if(基准序列上方没有空洞)转向步骤(5)

Else在基准序列上方生成新的节点序列，此时该节点序列仍需满足方案二的约束条件，并称此序列为参考节点序列；

4)if(参考序列上方没有空洞)转向步骤(5)

Else 在参考序列上方生成新的参考序列，并转向步骤(4);

5)if(基准序列下方没有空洞) 修复完成，退出程序

Else在基准序列下方生成新的参考序列;

6)if(参考序列下方没有空洞) 修复完成，退出程序

Else 在参考序列下方生成新的参考序列，并转向步骤(6)。

注：算法中所有基准序列与参考序列之间、参考序列与参考序列之间均需满足方案二的约束条件。

3 算法性能分析

本节对算法的性能进行验证[10]。利用Matlab 2010搭建实验平台，针对修复同样面积的空洞所用移动节点数和冗余度进行实验，并与PATT进行对比，同时对本算法的稳定性进行了分析。为简化实验，把空洞形状模拟成边长为L的正方形(这样便于生成基准节点序列和参考节点序列)，并假设移动节点感知半径为1 m，通信半径为2 m。

3.1 覆盖度分析

图3给出了修复不同空洞面积和所需移动节点数的关系。由图可以看出:随着空洞面积的增加，方案一和方案二所用移动节点数目明显少于PATT，同时方案一少于方案二，且随着空洞面积的增长，这种趋势越来越明显。因此,本算法所需节点数较少。

图3 空洞面积和所需节点个数关系图

3.2 冗余度分析

由图4所示的冗余度关系图可以看出:随着空洞面积的增加，方案一和方案二的冗余度呈下降趋势，而PATT呈上升趋势。方案一冗余度没有达到1，是因为该方案不能对空洞进行全覆盖，但由上一节证明可知，其覆盖率达到90 %以上，故满足有效性要求。同时，该方案在进行空洞修复时，只有小片的盲区分散在网络中，不会出现大片空洞，因此，对一些覆盖率要求不太高的网络，此方案为最佳。

图4 空洞面积与冗余度关系图

而在全覆盖的情况下，可以看出PATT冗余度最终稳定在1.45左右，而方案二稳定在1.25左右，减少了约0.25，即移动节点利用率提高了17.24 %，因此,对于覆盖率要求较高的网络，方案二具有较好性能。

3.3 稳定性分析

由图3可以看出:方案一、方案二和PATT一样，随着空洞面积的增加，所用节点数目呈线性增长趋势，这说明本算法具有很好的稳定性，即不会随着空洞面积大小的变化呈现剧烈波动。

同时，由图4的冗余度分析图可以看出：当空洞面积较小时，两种方案冗余度波动均较大，但随着面积不断增加，当达到1 000 m2时，两种方案开始收敛，最终稳定在一定数值之间，这同样也说明了本算法具有很好的收敛稳定性。

4 结 论

本文采用移动节点进行空洞修复，提出了一种新的算法——联合补丁法，并设计了两种补丁缝制方案，分析了其性能，随后对这两种方案进行了仿真实验，并与传统的PATT进行了对比分析，通过分析可知，本算法可根据实际需要灵活选择修复方案，且所需移动节点数较少，同时具有较高的节点覆盖率和较小的冗余度，因此,该方法是一种性能较好的算法。

[1] 毛晓峰，杨 珉，毛迪林.无线传感器网络应用综述[J].计算机应用与软件，2008,25(3):179-181.

[2] 包 旭,巨永锋. 面向节点失效的无线传感器网络覆盖空洞修复算法[J].计算机测量与控制,2011,19(6):1516-1522.

[3] 杨 凯. 无线传感器网络中覆盖空洞的修复算法研究[D].苏州:苏州大学,2012.

[4] 钱志鸿,王义君. 面向物联网的无线传感器网络综述[J].电子与信息学报,2013,35(1):215-227.

[5] Wang G,Cao G,Porta T. Movement-assisted sensor deployment[J]. IEEE Transaction on Mobile Computing,2006,5(6):640-652.

[6] Hwa chun,Prasan Kumar Sahoo,Chen Yenwen. Computational geometry based distributed coverage hole detection protocol in wireless sensor networks [J]. Journal of Network and Computer Applications,2011,34(5):1743-1756.

[7] 蒋 丹. 无线传感器网络覆盖盲区的发现与修复方法研究[D].沈阳:东北大学,2008.

[8] 王良民,李 菲,秦 颖. 基于移动节点的无线传感器网络覆盖空洞修复方法[J]. 通信学报,2011,32(4):1-8.

[9] 樊茂森,王庆生. 一种基于移动节点的无线传感器网络修复方法[J]. 传感器与微系统,2013,32(9):25-27.

[10] Ali Q I,Abdulmaowjod. Simulation and performance study of wireless sensor networks using Matlab[J]. Energy,Power and Control,2011,7(2):112-119.

Repairing method for coverage hole of WSNs

based on mobile node WANG Shan, WANG Qing-sheng, FAN Mao-sen

(College of Computer Science and Technology，Taiyuan University of Technology,Taiyuan 030024,China)

Once coverage holes appeared in wireless sensor networks(WSNs),performance of network will be severely affected. Aiming at this problem,“joint patch method”, a kind of coverage hole repairing algorithm based on mobile nodes is proposed.This algorithm “sews” all the needed mobile nodes into a large “cloth” ,according to the sewing program,which is pre-established,and then repair the hole directly. Firstly,performance of the algorithm is proved theoretically,and then by using Matlab simulation;both of the number of nodes required and redundancy are compared with PATT algorithms;finally,stability of the algorithm is analyzed. Eventually,it shows that this algorithm has a higher coverage rate and lower redundancy.

wireless sensor networks(WSNs); hole repairing; mobile node

2014—08—05

10.13873/J.1000—9787(2015)04—0134—03

TP 393

A

1000—9787(2015)04—0134—03

王 珊(1989-)，女，山西临汾人，硕士研究生，主要研究领域为无线传感器网络。