一种增强型事件驱动策略的覆盖空洞补偿算法

孙泽宇，高春玲，曹仰杰2，邢萧飞3，聂雅琳

（1.洛阳理工学院计算机与信息工程学院，河南洛阳 471023； 2.郑州大学软件学院，郑州 450001；3.广州大学计算机与软件教育学院，广州 510006）

一种增强型事件驱动策略的覆盖空洞补偿算法

孙泽宇1，高春玲1，曹仰杰2，邢萧飞3，聂雅琳1

（1.洛阳理工学院计算机与信息工程学院，河南洛阳 471023； 2.郑州大学软件学院，郑州 450001；3.广州大学计算机与软件教育学院，广州 510006）

针对无线传感器网络体系在随机部署过程中出现覆盖空洞的现象，借助于概率模型提出了一种CHCAEDS（基于事件驱动策略的覆盖空洞补偿算法）。该算法首先对随机部署的特性进行验证，给出随机部署表示形式；然后利用概率相关知识对监测区域内覆盖期望和节点数量进行求解，以达到使用最少数量的节点覆盖最大的面积。仿真实验表明，与其他算法相比，CHCAEDS在网络生存周期和算法运行时间上分别提高了12.59%和10.82%。

无线传感器网络；覆盖质量；覆盖空洞；事件驱动策略

0 引 言

随着信息技术的快速进步，无线传感器网络得到前所未有的发展，已被广泛应用于军事国防［1-2］、卫生医疗、交通运输［3-4］、环境监测、灾难救援［5-6］和智能家居等各种工程领域。近几年，国内外专家学者针对无线传感器网络的覆盖问题做了大量研究工作。文献［7］提出一种基于Voronoi（泰森多边形分割法）的有效覆盖区域空洞修补算法，该算法在满足一定覆盖质量的提前下，对覆盖空洞进行合理地增加工作节点以提高当前的覆盖率，同时寻找合理的修补位置信息，以保证整个网络的连通性。文献［8］提出了ETCA（节能目标覆盖算法），其基本思想是利用线性规划原理完成对监测区域的有效覆盖。文献［9］给出了一种ECAPM（基于概率模型的增强型覆盖算法），该算法的基本思想是将节点的能量以链表形式加以表示，同时对链表中的各个节点的能量进行计算，最终完成对监测区域的有效覆盖。

在节点覆盖过程中主要解决以下几个问题：（1）不要求对整个监测区域进行完全覆盖，而是对所关注的目标节点进行有效地覆盖；（2）采用随机投撒方式部署传感器节点时，如何避免在监测区域内出现覆盖空洞现象；（3）如何合理部署节点，抑制节点能量的快速消耗，同时以最少的传感器节点数量完成对监测区域的有效覆盖，以达到延长网络生存周期的目的。

1 覆盖质量

为了进一步研究无线传感器网络覆盖问题，并使问题简单化和易操作化，本文对所提出的CHCAEDS（基于事件驱动策略的覆盖空洞补偿算法）作了如下4种假设：

假设1：初始时刻所有传感器节点的感知半径与通信半径均为圆盘型，各节点能量相同。

假设2：感知半径远小于正方形监测区域的边长，忽略对监测区域的边界效应。

假设3：各节点具有唯一标识码，且不依赖于某种定位算法。

假设4：各节点工作期间，其形态为同形异构，并且时间上也同步。

定义1：当目标节点被有限个传感器节点连续覆盖时，称为有效覆盖；有效覆盖的所有工作节点的覆盖面积与监测区域面积的比值称为有效覆盖率CP。

式中，si和sj分别为第i个和第j个传感器节点的覆盖面积，S为监测区域面积。

定义2：当目标节点被k个传感器节点所覆盖时，称之为k度覆盖。定义3：由覆盖节点组成的集合称之为覆盖集。定理1：随机部署传感器节点服从于节点密度为λ、随机变量为N（s）的泊松分布。

证明：设单个传感器节点的覆盖面积为s，根据概率相关知识中的二项式定理可知，由k个传感器节点共同完成对目标节点覆盖时的联合概率为

式中，p为任意节点覆盖率，即p=|s|/S；N为所有传感器节点数量；CkN为二次式系数。

对于整个监测区域而言，传感器节点密度为

将节点覆盖率和式（3）代入式（2），化简后可得：

当传感器节点数量趋于无穷，即N→∞时，化简式（4）可得：

证明完毕。

监测区域内传感器节点冗余节点的数量直接影响覆盖质量，如何采用最少节点完成对监测区域的有效覆盖，是本文讨论的另一个重点问题。当移动目标在监测区域内被多个传感器节点覆盖N次后，其N+1次覆盖期望值决定于后继覆盖的优劣，因此，本文引入了定理2。

定理2：完成对有效区域覆盖时，所需传感器节点数量最小值为N=S ln（1-p）/（πr2），式中，r为传感器节点的感知半径。

证明：任意节点在监测区域内的覆盖率为p= πr2/S，未被覆盖的概率为q=1-πr2/S。根据定理1可知，在整个监测区域内，没有被任意节点所覆盖的联合概率为

化简后可得：

监测区域内，任意位置被覆盖的概率为

将节点密度λ=N/S代入公式（8），两边取对数得：

因此，当完成对监测区域有效覆盖时，所需最少传感器节点数量为N=S ln（1-p）/（πr2），证明完毕。

2 体系评估

为了更好地体现仿真效果，现对仿真参数作如下说明，如表1所示。

表1 仿真参数说明

实验1：本文采用MATLAB7软件对网络生存周期和算法运行时间进行了仿真实验，以节点密度参数λ作为仿真对象。在网络生存周期实验中，本文采用的监测区域平台分别为100×100和200× 200；在测定算法运行时间的实验中，本文采用的监测区域平台为300×300。仿真实验环境为WIN XP、RAM 2 G和CPU双核1.7 G。

图1～图6分别给出了本文提出的CHCAEDS、ETCA和ECAPM的传感器节点和目标节点数量与网络生存周期以及算法运行时间的对比仿真结果。图1和图3分别给出了监测区域平台为100×100和200×200时传感器节点数量与网络生存周期的对比。从图中可以看出，随着传感器节点数量的增加，网络生存周期也在稳步提升，当传感器节点数量分别为50和150时，CHCAEDS的网络生存周期的平均值高于另外两种算法12.59%。图2和图4分别给出了监测区域平台为100×100和200×200时目标节点数量与网络生存周期的对比。从图中可以看出，当目标节点数量增加时，所需覆盖目标节点的工作传感器节点数量随之增加，网络的能耗加大，因此整个网络的生存周期有所下降，当λ=0.8时，CHCAEDS的下降速度较为平缓，与另外两种算法相比，延长了网络生存周期，其平均值为10.82%。图5和图6分别给出了监测区域平台为300×300时传感器节点和目标节点数量与算法运行时间的对比。从图中可以看出，当传感器节点数量增加时，算法的运行时间也会增加，但CHCAEDS的运行时间小于ECAPM，其原因在于，ECAPM忽略了冗余节点的存在，仅依赖于传感器节点数量的增加来提高对监测区域的覆盖，从而达到有效覆盖的目的；而CHCAEDS则是利用节点之间的转换来达到覆盖的平衡。

图1 100×100传感器节点数量与网络生存周期对比

图2 100×100目标节点数量与网络生存周期对比

实验2：以λ=0.3和0.8为基准参数，对300× 3 00监测区域初始时刻的传感器节点数量和CH-CAEDS优化后的传感器节点数量进行仿真实验。

图3 200×200传感器节点数量与网络生存周期对比

图4 200×200目标节点数量与网络生存周期对比

图5 300×300传感器节点数量与算法运行时间对比

图6 300×300目标节点数量与算法运行时间对比

图7～图10给出了传感器节点在初始时刻与CHCAEDS优化后的布置示意图。从图中可以看出，λ=0.3和λ=0.8时，初始时刻监测区域内存在大量的冗余节点，通过CHCAEDS优化后，抑制了冗余节点的产生，使其转入休眠状态，保存了整个网络的能量，延长了网络生存周期。

图7 λ=0.3时，初始时刻传感节点部署示意图

图8 λ=0.3时，CHCAEDS传感节点部署示意图

图9 λ=0.8时，初始时刻传感节点部署示意图

图10 λ=0.8时，CHCAEDS传感节点部署示意图

3 结束语

本文在对无线传感器网络覆盖问题进行分析的基础上提出了一种覆盖空洞补偿算法。首先，利用概率相关知识给出了部署在监测区域内的传感器节点分布形态；而后对传感器节点覆盖期望值和最少节点数量的函数关系进行求解，给出了覆盖监测区域内所需最少传感器节点数量的求解方法；最后，通过仿真实验验证了CHCAEDS与ETCA、ECAPM在不同监测区域内的网络生存周期和运行时间的对比过程，证明了本文算法的有效性和稳定性。

今后的工作重点将主要集中在具有边界效应的非线性覆盖和参数可调的有效覆盖。

［1］ 孙泽宇，伍卫国，王换招.无线传感器网络中一种增强型覆盖控制算法［J］.电子学报，2015，43（3）：466-474.

［2］ 邢萧飞，谢东青，郑瑾.无线传感器网络k度覆盖控制算法［J］.中南大学学报：自然科学版，2014，45（11）：3832-3839.

［3］ 李猛，丁代荣，郭廷立.一种无线传感器网络节点随机部署策略［J］.计算机工程，2012，38（5）：99-101.

［4］ 孙泽宇，赵国增.基于节点调度策略的能量有效覆盖算法［J］.光通信研究，2012，（6）：52-55.

［5］ 孟凡治，王换招，何晖.基于联合感知模型的无线传感器网络连通性覆盖协议［J］.电子学报，2011，39 （4）：772-779.

［6］ Mini S，Siba K U，Samrat L S.Sensor deployment and scheduling for target coverage problem in wireless sensor networks［J］.IEEE Sensros Journal，2014，14 （3）：636-644.

［7］ 赵春江，吴华瑞，刘强.基于Voronoi的无线传感器网络控制优化策略［J］.通信学报，2013，34（9）：115-122.

［8］ Xing Xiaofei，Wang Guojun，Li Jie.Poly-type target coverage scheme for heterogeneous wireless sensor networks using linear programming［J］.Wireless Communications and Mobile Computing，2014，14（8）：1397-1408.

［9］ Sun Zeyu，Wang Huanzhao，Wu Weiguo.ECAPM：An enhanced coverage algorithm in wireless sensor network based on probability model［J］.International Journal of Distributed Sensor Networks，2015，15（1）：1-11.

An Enhance Event-Driven Strategy Coverage Holes Compensation Algorithms

SUN Ze-yu1，GAO Chun-ling1，CAO Yang-jie2，XING Xiao-fei3，NIE Ya-lin1
（1.School of Computer and Information Engineering，Luoyang Institute of Science Technology，Luoyang 471023，China；2.School of Software，Zhengzhou University，Zhengzhou 450001，China；3.School of Computer Science and Software Education，Guangzhou University，Guangzhou 510006，China）

Coverage holes phenomena is appeared in the process of random deployment of wireless sensor network systems. This paper presents a probabilistic model by means of event-driven policy coverage holes compensation method（Coverage Holes Compensation Algorithms Based on Event-Driven Strategy，CHCAEDS）.Firstly，the characteristics of random deployment are verified and the representation of random deployment is given.Then，based on the probabilistic method，the desired coverage and the number of nodes within the surveillance area are solved in order to achieve maximum coverage area using minimum number of nodes.Finally，the simulation result show that the CHCAEDS can improvethe network life cycle and the algorithm running time by 12.59%and 10.82%when comparing with other algorithms.

wireless sensor networks；coverage quality；coverage holes；event-driven strategy

TP393

A

1005-8788（2016）03-0022-04

10.13756/j.gtxyj.2016.03.008

2016-01-06

国家自然科学基金资助项目（U1304603，61503174）；国家博士后基金资助项目（2014M562153）；河南省科技攻关重点资助项目（142102210471，1421002210568，162102210113）；河南省教育厅自然科学重点基金资助项目（14B520099，16A520063）；广州市自然科学基金资助项目（1201430560）

孙泽宇（1977-），男，吉林长春人。副教授，博士，主要研究方向为无线传感器网络与物联网。