无线传感器网络最小覆盖能量优化算法*

高洁，吴延红，白建侠，李琦

（1.山东华宇工学院基础部，山东德州253000；2.天津大学仁爱学院数学教学部，天津301636）

无线传感器网络最小覆盖能量优化算法*

高洁1*，吴延红1，白建侠2，李琦1

（1.山东华宇工学院基础部，山东德州253000；2.天津大学仁爱学院数学教学部，天津301636）

在无线传感器网络中，位于基站周围的节点由于负责所有探测数据的转发任务而能量消耗水平较高。为了均衡基站周围节点的能量消耗，提出一种合理有效的节点轮换休眠机制。使得网络中大量冗余节点处于休眠状态，从而减少基站周围重要节点的负载。基于这种想法提出了冗余节点判定定理，基于Voronoi图寻找最大可休眠节点集，设计了最小连通覆盖算法（FBSW）寻找网络中可休眠的冗余节点，有效地延长网络的生命周期。仿真结果证明，该算法的运行复杂度优于贪婪算法，由于冗余节点轮换休眠，整个网络的能量节约了20.01%以上。

无线传感器网络；Voronoi图；最小连通覆盖集；休眠节点；能量均衡；

EEACC：7230doi：10.3969/j.issn.1004-1699.2016.09.024

无线传感器网络是指由大量节点以某种概率分布模型随机布撒在监测区域内，通过无线通信方式组成的多跳自组织网络系统［1］。无线传感器技术已经从最早的军事国防应用逐步扩展到农业、环境监测、生物医疗、交通管理、危险区域远程管理乃至家居等诸多领域［2-9］。对于实际应用的高密度网络，存在大量的可休眠冗余节点，可以设计冗余节点识别算法，在不影响网络覆盖和连通性的要求下使得部分节点轮换休眠，这样既减少了向重要节点发送数据流的流量，又节省重要节点的能量。对于重要节点能量消耗水平较高，可以在重要节点周围布撒中继节点，帮助重要节点分担转发大量数据流的任务，可以保证重要节点的使用寿命。目前解决此问题的方法主要集中在设计有效的MAC协议、识别冗余节点并使其休眠以保证延长重要节点的生命周期，设计合理的网络拓扑结构和节点轮换休眠［10-20］。

从研究方法上，文献［10］将网络中节点的剩余能量作为点的权值。利用改进的贪婪算法寻找最小加权独立集。保证最小加权独立集中的冗余节点首先休眠，而网络中工作的节点剩余能量水平相对较高，并且满足整个网络的全覆盖。文献［11］针对路径覆盖节点控制策略问题，利用路径覆盖的特点，提出了一种基于层级结构的节点覆盖控制方法。通过对节点监测目标的先后顺序，在保障不丢失监测目标的前提下，建立了节点层级模型和关联模型，设计了以开启节点数目和均衡能耗为优化目标的覆盖控制策略文献［12］。将传感器节点与目标覆盖区域的虚拟力操作和节点之间的虚拟力操作按节约能耗的约束同时进行，从而达到覆盖控制技术的优化目的。文献［13］通过将网络区域划分为若干等宽的子区域，每个子区域内的所有节点形成一个链，由链首节点负责与基站通信。针对链首节点能量消耗太大有可能过早死亡的问题，提出采用链首节点轮换的方法来均衡和降低能量消耗。文献［14］利用冗余节点的思想，让部分锚节点和已经定位的盲节点进入睡眠，从而降低节点规模和冗余定位信息，保证了节点低能耗下的精确定位.voronoi图理论常常用在无线传感器网络研究。文献［15］的工作主要集中于利用Vo⁃ronoi划分确定网络的覆盖集的边界。文献［16］基于Voronoi图构造节点的最大独立集提出冗余节点休眠的思想。利用最少数量的节点达到网络的全覆盖，并提出利用构造最小生成树寻找节点最大独立集的多项式时间近似算法。文献［17］利用Voronoi划分和Delaunay三角剖分对传感器网络进行分割，判别重复覆盖目标区域的冗余传感器节点，采用节点到sink点的跳数对节点分层，进而提出选择休眠节点的方法。文献［18］提出一种基于Voronoi图的无线传感器网络覆盖算法，先找出最大可能盲点，然后重新部署节点，以达到用最少的节点获得最大的监测面积。文献［19-21］均利用Voronoi划分网络，设计寻找网络最小连通覆盖集的算法，解决网络全覆盖问题。文献［22］利用Voronoi寻找泰森多边形解决网络覆盖控制问题。本文的思想为寻找网络中可休眠的冗余节点，采用节点轮换休眠的方式，在减少基站周围重要节点负载的前提下，同时降低单个节点的能量消耗，使得网络中的节点能量消耗更加均衡，有效延长了网络的生命周期。与文献［16-22］的思想不同的是：节点在休眠后，需要等待再次唤醒。每一轮在保证网络全覆盖的前提下，总是能量最少的节点先休眠。保证网络的能量得到最大程度的均衡。基于这种想法本文提出了冗余节点判定定理，设计了FBSW算法寻找网络中可休眠的冗余节点，有效地延长网络的生命周期。仿真结果证明本文给出的算法是合理有效的。

1　预备知识

定义1［23］（Voronoi划分）给定二维平面R2上的一个有限点集S=｛s1，s2，…，sn｝。与之相关联的Voronoi区域表示为：

本文中以传感器节点集作为Voronoi图的产生点集，用Vor（V）表示。Vor（V）构成网络目标区域G的一个划分，用Vor（V，G）表示。

定义2［23］（完全覆盖）给定无线传感器网络G=（V，E）和目标区域G′，设覆盖点集为V′⊆V。

Rs为节点的探测半径，称为关于vi的探测区域，C（V′）表示关于覆盖节点集V′的有界Voronoi划分区域集合。若满足

当G′=G时，称C（V′）为G的完全覆盖集。

定义3［23］（冗余节点）将网络图G进行Voronoi划分，若删除节点vi，对网络图G进行第2轮Voronoi划分，C（V′）=那么vi称为网络G的冗余节点。

在以后的讨论中，E（vi）（V，R）表示C（vi）（V，R）的边界集，其中包括网络的边界；V（vi）（V，R）表示C（vi）（V，R）的顶点集，包括Voronoi区域的顶点和与G的区域边界相交的点；N（vi）（V，R）表示vi节点的邻居节点集。

图1　无线传感器网络的Voronoi划分

在提出冗余节点的划分定理之前，首先引入以下3则引理：

引理1［23-24］对于任意vj∈V-vi-N（vi）（V，R），则有C（vi）（Vvi，R）=C（vi）（V，R）.

定义4（类凸多边形区域）由于网络W区域是以R为半径的圆心区域，W为以顶点集V为产生点集的Voronoi区域均为有界区域，若Voronoi区域的顶点与网络W的边界不相交，则这样的Voronoi区域为凸多边形区域，否则称为类凸多边形区域。

引理2如果类凸多边形区域顶点均包含于圆上，则类凸多边形区域包含于圆上。

引理3［23-24］C（vi）（V，R）⊆S（vi）（V，R）的充分必要条件是V（vi）（V，R）⊆S（vi）（V，R）。

首先根据以上3则引理，提出基于Voronoi的冗余节点判定定理。

2　基于Voronoi划分的冗余节点检测算法

2.1冗余节点判定定理

定理1节点vi∈V是冗余节点，当且仅当∀vj∈N（vj）（V，R）时，删除vi并对网络G进行二次Voronoi划分后，对于任意点p∈V（vj）（V/vi，R）-V（vj）（V，R），均满足d（p，vj）≤Rs。

证明假设节点vi∈V是冗余节点。对于任意vj∈N（vi）（V，R），删除vi并对网络G进行二次Voronoi划分后，存在p∈V（vj）（V/vi，R）-V（vj）（V，R），使得d（p，vj）＞Rs。即p∉S（vj）。根据引理3，则有C（vi）（V，R）⊄S（vi）（V，R）。这与vi∈V是冗余节点矛盾，所以假设不成立。那么当节点vi∈V是冗余节点，当对于任意点vj∈N（vj）（V，R），删除vi后对网络G进行二次Voronoi划分，对于任意点，均满足d（p，vj）≤Rs。

反之，存在vj∈N（vi）（V，R），若删除节点vi且对网络进行二次Voronoi划分后，对于任意点p∈V（vj）（V/vi，R）-V（vj）（V，R），均满足d（p，vj）≤Rs。所以对于任意点vj∈N（vj）（V，R），存在V（vj）（N（vi），R）⊆S（vj）（N（vi），R），根据引理2、引理3，可得C（vj）（N（vi），R）⊆S（vj）（N（vi），R）。根据引理1，对于任意点vk∈V-vi-N（vi）（V，R），满足C（vi）（Vvi，R）=C（vk）（V，R）。所以C（vi）（V，vi，R）⊆S（vi）（V，vi，R）等价那么vi是冗余节点。

利用此定理可找到网络中的冗余节点，其算法步骤如下。

识别冗余节点算法（IRN算法）

输入：无线传感器网络G=（V，E），节点集V=｛vi｝（i=1，2，…，n）。

输出：冗余节点集VR

步骤1初始冗余节点集VR为空。

步骤2构造Voronoi图Vor（V，G），如果V不为空，根据定理1寻找冗余节点vi。

步骤3当vi为冗余节点，则vi加入到冗余节点集VR中，从节点集V中删除vi

步骤4集合V不为空，则返回到步骤2，否则算法结束。

2.2冗余节点分类

定理1给出了判定网络中冗余节点的依据。但不得不注意到，同时删除互为邻居的冗余节点可能会形成网络中新的探测漏洞，造成不必要的损失。所以，并非所有的冗余节点都可以休眠。为此，将冗余节点进一步分类［24］。

定义5（绝对冗余节点和相对冗余节点）若vi是网络中的冗余节点，当vi的邻居节点集N（vi）（V，R）中只存在非冗余节点时，这样的vi被称为绝对冗余节点。否则为相对冗余节点。

由以上定义可知，由于绝对冗余节点的邻居节点均为非冗余节点，因此删除绝对冗余节点不会影响网络的完全覆盖。而直接删除相对冗余节点可能会给网络带来新的覆盖空洞。但相对冗余节点集中仍存在很大一部分节点可以休眠且并不影响网络的完全覆盖，如果保留所有的相对冗余节点，同样会造成网络能量的不必要消耗。由此，问题转化为寻找相对冗余节点中的大量可休眠冗余节点。

同时删除网络中绝对冗余节点和必须节点及其相关联的边，删除与距离基站Maxd（vi，BS）以内的S2中的节点及相关联的边，剩余部分为相对冗余节点及其相关联的边组成的G的子图G′。那么，只需在G′中寻找最大可休眠节点集。

节点分类算法（CRN算法）如下：

输入：冗余节点集VR=｛v1，v2，…，vn｝，标记ARV为绝对冗余节点集，RRV为相对冗余节点集

输出：分类节点集ARV和RRV

步骤1初始ARV和RRV为空

步骤2对于冗余节点vi∈VR，当vi的邻居节点集N（vi）（V，R）中只存在非冗余节点时，vi属于ARV，否则属于RRV。

步骤3将vi从VR中删除，当VR不为空，返回到步骤2，否则算法结束。

2.3FBSW算法

本文算法的核心思想是寻找最大可休眠冗余节点集合，在不影响网络覆盖的前提下使得最大可休眠冗余节点集合中节点休眠，由此设计了最大权最小覆盖的启发式算法FBSW。

输入：无线传感器网络G=（V，E）

输出：最大可休眠的节点集合为I（v）

步骤1寻找冗余节点集VR。

步骤2如果VR不为空，寻找相对冗余节点集RRV。

步骤3如果相对冗余节点集RRV不为空，标记相对冗余节点为顶点的图G（RRV（v）），RRV（v）=｛（vi，wi，di）｝（i=1，2，…，n），di为节点度.wi节点剩余最大能量.I（v）为可休眠节点集。

①初始I（v）为空，绝对冗余节点数为a

②选择具有最小度的节点集，比较其中节点的剩余能量，选择节点vi为能量最少的节点作为初始可休眠的节点。

③从G（RRV（v））中去掉vi、相应的边E（vi）及连接节点N（vi），则相对冗余节点集中将删除vi和连接节点N（vi），同时vi加入到可休眠节点集I（v）。

④若RRV（v）不为空，则返回到②，否则算法继续。

步骤4如果绝对冗余节点集ARV不为空，则I（v）中还将包含绝对冗余节点集；

步骤5V中删除I（v），若V不为空，则返回步骤2，否则算法结束。

利用算法，可以寻找到网络G中同时休眠的最大冗余节点集。特别的，当网络的规模较大时，网络中的瓶颈节点负载会大大减少。而同时以最少的节点数达到了完全覆盖目的。

2.4算法复杂度分析

定理算法FBSW的复杂度为O（n3logn）。

证明假设本文中构造Voronoi图的方法为分治法，那么其复杂度为O（nlogn）［25］，算法IRN算法第3步的的时间复杂度为O（nlogn），第4步循环最大时间消耗为O（n3logn），所以算法IRN的最大时间开销不过O（n3logn）。CRN算法的时间开销最多为O（n3）。寻找最大休眠冗余节点集的FBS算法，第3步开始是一个大循环，但其中的嵌套循环均可在常数时间内完成。所以此算法的时间复杂度为O（n）。最终算法FBSW调用了以上3个子算法，那么其算法复杂度为（O（n3logn）+ O（n3）+O（n）），所以，算法FBSW的时间复杂度为O（n3logn）。

3　仿真模拟

本文利用Matlab 7.0作为仿真工具，运行环境是内存为512 MB，操作系统为Windows XP的PC机。

3.1定理仿真

本文中定理1是算法设计的基础，下面将定理1进行仿真，证明其的确是有效的。仿真环境，模拟网络范围为120×180的矩形区域，随机布撒19个节点，并记标记节点半径。

图2中选择3个节点的坐标分别为（120，62），（121，65），（130，77），当感知半径为15时，显然节点（121，65）为冗余节点，这个节点是可以休眠的。节点之间的距离显然比感知半径要小，并且区域被完全覆盖。

图2　冗余节点示意图

图3删除冗余节点示意图

图3表示删除坐标为（120，65）的节点后，仍然在感知半径为15的环境下，区域仍然被完全覆盖，所以当节点之间的距离小于感知半径时，节点是可以被删除的。并且删除后，网络区域仍然被覆盖。

3.2算法仿真

在算法仿真实验中，仿真的网络区域为半径R= 10的圆形区域。

由于本算法在贪婪算法基础上进行改进，下面做了与贪婪算法运行时间的对照。

表1列出在不同探测半径随机节点数目分别为200、300、400的情况下两种算法运行时间的比较。可以看到，FBSW算法的运行时间远小于贪婪算法。这表明FBSW算法的复杂度优于贪婪算法。

表1　FBSW算法与Greedy算法运行时间对照

由表2可以看出，当探测半径增大且节点与基站的距离增大时，能量节约率呈现增加的趋势。也就是说，如果加大节点的工作功率，网络中节点的能量消耗将得到大幅度的降低。

表2　递增探测半径能量节约率

由表3可以得到，当节点的探测半径为1，随着节点与基站的距离增大，节点的能量节约率基本保持在21%以上。那么整个网络的能量消耗率将降低21%以上。

表3　不同位置相同探测半径节点对应可休眠节点数与能量节约率

通过FBSW算法，单个节点的能量平均可以节省至少21.01%。这表明FBSW算法可以有效地平衡整个网络的能量消耗并延缓了单个节点的能量消耗时间。

图4表示运行FBSW算法前后的网络平均能量消耗情况比较。运行条件为目标半径R=10，节点探测半径r=1，节点总数为1 024。并假设r≥4时，不存在可休眠冗余节点。图中红色虚线条表示原始网络节点平均能量消耗情况，蓝色实线条表示利用FBSW算法使得节点平均能量消耗较原始网络有大幅度的减少，使得网络中节点能量消耗趋于均衡。

图4　运行FBSW算法前后平均负载比较R=10，r=1，n=1024

图5　算法运行前后能量消耗比较R=10，r=1，n=1225

图5同样表示运行FBSW算法前后的网络平均能量消耗情况比较。运行条件为目标半径R=10，节点探测半径r=1，节点总数为1 024。网络中均存在可休眠的冗余节点。红色虚线条表示网络中原始节点平均能量消耗情况。蓝色实线条表示运行FBSW算法后，网络中节点的平均能量消耗情况。那么，网络的平均能量消耗明显降低。

4　结语

本文基于Voronoi划分的方法，提出了冗余节点判定方法并用数学推理证明其正确性。设计了求最小覆盖集的启发式算法FBSW。算法FBSW包含三个子算法，分别为识别冗余节点的IRN算法、对冗余节点分类的CRN算法和构造最大独立集的FBS算法。最后用仿真结果说明在同等条件的网络中，算法FBSW比贪婪算法运行时间更短，重要节点的能量被节约至少21.01%。本算法适用于节点较多的大型网络，具有一定的实用价值。

［1］任丰原，黄海宁，林闯.无线传感器网络［J］.软件学报，2003，14（7）：1282-1291.

［2］孙利民，李建中，陈渝，等.无线传感器网络［M］.北京：清华大学出版社，2005.

［3］崔洋，郭坤亮，何丽莉，等.基于无线传感器网络的传统发酵过程监测系统［J］.仪器仪表学报，2010，31（7）：1490-1495.

［4］王骥，沈玉利，林菁.基于无线传感器网络生理参数采集系统设计［J］.电子测量与仪器学报，2009，23（2）：94-99.

［5］曾梅梅，蒋华，王鑫.一种新的无线传感器网络恶意节点追踪方法［J］.传感技术学报，2013，26（1）：122-127.

［6］李明.基于差分算法的异构无线传感器网络多重覆盖节点调度方案［J］.传感技术学报，2012，25（6）：826-830.

［7］Tan Li，Chen Yucheng，Yang Minh，et al.Priority Coverage Algo⁃rithm and Performance Simulation for Node Deployment in Direc⁃tional Sensor Networks［J］.Sensor Letters，2014，12（2）：275-280.

［8］Xiao Yang L，Kai Liang W，Yanmin Z，et al.Mobility Increases the Surface Coverage of Distributed Sensor Networks［J］.Comput⁃er Networks，2013，57：2348-2361.

［9］Wei L，Wei Z.Coverage Hole and Boundary Nodes Detection in Wireless Sensor Networks［J］.Journal of Network and Computer Application，2015，45：35-43.

［10］阳娣兰，谢政，陈挚，等.无线传感器网络中能耗均衡的覆盖控制算法［J］.计算机工程与科学，2008，30（12）：15-18.

［11］底欣，张百海.传感器网络层级结构路径覆盖控制方法［J］.仪器仪表学报，2011，32（11）：2416-2422.

［12］田一鸣，陆阳，魏臻，等.无线传感器网络虚拟力覆盖控制及节能优化研究［J］.电子测量与仪器学报，2009，23（11）：65-71.

［13］吕红芳，张浩.链首节点轮换的无线传感器网络路由算法研究［J］.电子测量与仪器学报，2013，27（7）：610-616.

［14］叶启明.无线传感器网络定位算法的睡眠调度技术研究［J］.广州石油化工学院学报，2014，24（4）：34-37.

［15］So A M C，Ye Y Y.On Solving Coverage Problems in a Wireless Sensor Network Using Voronoi Diagrams［J］.Internet and Net⁃work Economics，2005，3828：584-593.

［16］蒋杰，方力，张鹤颖，等.无线传感器网络最小连通覆盖集问题求解算法［J］.软件学报，2006，17（2）：175-184.

［17］马震，刘云，沈波.一种无线传感器网络的能耗平衡覆盖模型［J］.电子与信息学报，2008，30（9）：2250-2253.

［18］杨海雳，赵静.基于Voronoi图的无线传感器网络覆盖算法研究［J］.信息通信，2015，7：28-30.

［19］陆克中，孙宏元.无线传感器网络最小覆盖集的贪婪近似算法［J］.软件学报，2010，10（21）：2656-2665.

［20］秦泽峰，谭瑛，赵静，等.基于Voronoi图的无线传感器网络覆盖算法研究［J］.太原科技大学学报，2013，34（3）：185-189.

［21］陈业纲，徐则同.无线传感器网络最小连通覆盖的节能算法［J］.计算机仿真，2014，31（3）：324-350.

［22］方伟，宋鑫宏.基于Voronoi图盲区的无线传感器网络覆盖控制部署策略［J］.物理学报，2014，63（22）：220701-1-10.

［23］CARBUNAR B，GRAMA A，VITEK J.Distributed and Dynamic Voronoi Overlays for Coverage Detection and Distributed Hash Ta⁃bles in Ad-Hoc Networks［C］//Proceedings of the Tenth Interna⁃tional Conference on Parallel and Distributed Systems.2004，7：549-556.

［24］周培德.计算几何［M］.北京：清华大学出版社，2000.

［25］徐玖平，胡志能.中级运筹学［M］.北京：科学出版社，2008.

高洁（1983-），女，2007年于山东大学威海分校获得学士学位，2010年于华东理工大学获得硕士学位，现为山东华宇工学院基础部讲师，主要研究方向为为通信网络可靠性和优化算法，jiegao_1983@ 163.com；

吴延红（1982-），女，研究生（硕士），毕业于南开大学，现为山东华宇工学院基础部讲师，研究方向为小波分析与信号处理。

The Minimum Coverage Energy Optimization Algorithms in Wireless Sensor Network

GAO Jie1*，WU Yanhong1，BAI Jianxia2，LI Qi1
（1.Foundation Department，Shandong Huyu University of Technology，Dezhou Shandong 253000，China；2.Mathematics department，Ren’ai College of Tianjin University，Tianjin 301636，China）

Nodes around the base station are charged with the task for transferring a large of data to the base station in wireless sensor networks.Therefore，these nodes consume more energy than others.In order to balance the energy consumption of nodes around the base station，this paper puts forword a reasonable and effective node rotation mech⁃anism.A large number of redundant nodes turn to dormancy so that the load of nodes is reduced around the base sta⁃tion.A redundant nodes decision theorem is proposed based on the mechanism.The maximum dormant node set is found based on the Voronoi diagram.The Minimum Connected Coverage algorithm（FBSW）is proposed to find out the redundant nodes which can be dormant and to prolong the network lifetime.The Simulation results show that the operation complexity of the FBSW algorithm is superior to the Greedy algorithm.On account of the redundant nodes which turn to dormancy，the energy of the network is saved by 21.01%.

the wireless sensor networks；Voronoi；the minimum connected coverage set；inactive nodes；energy bal⁃ance

TK393.03；TP212.9

A

1004-1699（2016）09-1435-06

项目来源：国家自然科学基金项目（11471167）

2015-12-29修改日期：2016-05-03