基于加权的无线传感器网络优化覆盖算法

张 品，沈 政，董志远，郑 立

(杭州电子科技大学通信工程学院，杭州310018)

无线传感器网络覆盖［1－2］是指在传感器网络节点能量、无线网络通信带宽、网络计算处理能力等资源普遍受限的情况下，通过具有感知能力的节点的位置分布和节点调度，使感知、监视、传感、通信等各种服务质量得到提高，最终使无线传感器网络资源得到优化分配［3］。但由于实际应用的特殊性，传感器网络一般被部署在沙漠、战场等工作人员不可达到的环境中，需要利用节点的高度冗余来保证网络的容错性和数据的精确性。目前，在处理节点冗余延长网络生命周期和均衡节点能量方面有很多的研究，文献［4－5］通过采用节点“休眠”和“活跃”轮换的方式，在满足覆盖要求的条件下，通过最大化轮换节点集合的数目来保证大规模网络环境下传感节点的有效使用。文献［6］进一步提出一种集中式、利用节点分组工作的DSC(disjoint set covers)算法，该算法将问题抽象成最大流图问题，并对节点进行任务集分配，通过各个节点任务集轮流工作均衡了各节点能耗。但由于该算法分组固定，一旦某节点能量耗尽或有新节点加入网络，将导致工作节点无法对自身所处分组进行自适应调节。文献［7］为了解决固定分组导致工作节点无法自适应调节的问题提出了一种PEAS算法，该算法通过探测邻居节点的工作状态来判断自身节点工作状态，能够减小工作节点数，节约能耗，但该算法容易出现部分节点一直处于工作状态直到节点能量耗尽才更换其它节点工作，导致网络的稳定性和网络节点能量均衡性较差。文献［8－9］在PEAS算法的基础上进一步考虑到传感节点与目标节点之间的关联关系(一个传感节点可以感知多个目标节点以及一个目标节点处于多个传感节点的覆盖范围内)，通过数据挖掘技术建立传感节点与目标节点的关联准则，根据关联准则调度节点轮换工作来均衡网络节点之间的能量，但该算法在关联准则下仅通过简单的比较传感节点能量大小来选取工作节点，可能导致部分节点调度不合理，从而造成资源浪费。

本文首先考虑到传感节点采用休眠和活跃机制分集合轮换覆盖目标节点，可以有效地延长网络生命周期，但固定分组对于集合中某些节点的死亡无法自适应调节，因而新算法只对最小频繁项的目标采用分集合覆盖，考虑到PEAS算法对节点能够自适应调节，但PEAS算法只是随机选取工作节点，可能会不合理的调度节点工作，所以对边缘未覆盖的目标节点采用加权［10－11］覆盖，通过权值来选择工作节点，可以减少每轮的工作节点数和改善网络节点间能耗的均衡性。

1 PEAS算法概述

1.1 问题描述

为了更好地表述问题，假设无线传感器网络的覆盖情况如下，网络中存在M个传感节点hi∈H(i=1，2，3，…，M)分布在 L×L 二维正方形区域内，对N 个目标节点 kj∈K(j=1，2，3，…，N)实现监控。为了实现对目标节点更准确的监测，通常需要在监测目标区域抛撒比较多的传感节点，使得目标节点周围有高度冗余的传感节点对其实现覆盖。目标节点通常会被两个或两个以上的传感节点覆盖，而传感节点可能覆盖多个目标节点(如表1)。如图1所示，由于覆盖目标节点的传感节点都存在冗余，所以监测区域的目标频繁项大于等于2。

图1 无线传感器网络覆盖图

表1 传感节点与目标节点的关系

1.2 PEAS 算法

PEAS算法是一种分布式的状态自确定的算法，在PEAS算法中传感节点有三种状态(如图2所示):覆盖质量探测(Probing)、感知工作状态(Working)和适应性休眠状态(Sleeping)。工作开始后，网络中各传感节点首先进入覆盖质量探测状态，通过广播探测包给邻居工作节点，邻居工作节点通过收集覆盖范围内的目标信息并向发送探测包的传感节点发送回复消息，传感节点通过回复消息来判断其周边覆盖区域内的监控目标是否已完全能够被邻近的工作节点所感知，若存在尚未被感知的目标，则该节点进入感知工作状态;否则，该传感节点关闭通信和感知方式，进入能量消耗较少的适应性休眠状态。但休眠节点并不是一直处于休眠状态，它每隔一段时间后都会被唤醒，传感节点会再次向邻居工作节点发送探测包对该节点周边覆盖区域内的感知情况进行探测，根据邻居节点的回复消息确定下一轮该传感节点的工作状态。

图2 PEAS算法传感节点的状态转换图

在传感节点高冗余的环境下，PEAS算法通过探测监听机制来确定传感节点的状态，能够有效地调度传感节点的工作与休眠，减少工作节点的数目，但PEAS算法在工作开始之前，随机地选取工作节点，然后根据已工作的邻居节点的覆盖信息来判断自身节点是否进入休眠状态，因而传感节点的利用率相对较低。另外，PEAS算法未考虑节点剩余能量对传感网络的影响。在PEAS算法中，当传感器节点一旦被选为工作节点后，则其将一直处于工作状态直到节点的能量耗尽，工作节点在能量较低的情况下仍处于工作状态，必然会导致网络节点间的能量均衡性以及网络的稳定性变差。

2 基于加权的优化覆盖算法

2.1 基本定义

定义1 节点感知半径r

传感节点所能感知目标的最大范围即节点感知半径 r。

定义2 目标频繁项

对于目标节点kj同时处于多少传感节点hi的感知范围之下，目标节点所对应传感节点的数目即为目标频繁项。最小频繁项是指目标节点所对应最少的传感节点数目。

定义3 覆盖度A

定义4 节点关联强度Q

传感节点hi、hk在感知范围内所覆盖目标节点的集合分别为Bi、Bk，则定义关联强度为 Q=Bi∩Bk。Q越大关联强度越大，Q为0表示两传感节点不相关。

2.2 算法思想

基于加权优化覆盖算法首先考虑的是网络中最小频繁项目标对应的传感节点工作状态对网络周期的影响。由于最小频繁项目标处在最少传感节点的覆盖下，如果让最小频繁项目标对应的传感节点同时工作，势必会导致网络的生存周期下降，所以本文对最小频繁项目标采用划分集合的方式进行覆盖，尽量将最小频繁项目标对应的传感节点划分到不同的集合中，保证每个传感节点集合能够独立覆盖所有最小频繁项目标，如果在划分过程中发现有集合不能覆盖最小频繁项目标，则去除该集合。由于划分好的各集合都能够独立覆盖所有最小频繁项目标，所以新算法采用轮换的工作机制，让其中一个集合中的节点处于工作状态，其它集合中的节点处于休眠状态，每隔一段时间，更换工作节点集合，以实现对最小频繁项目标的优化覆盖。对于最小频繁项目标以外未被覆盖的目标节点，考虑到让覆盖目标多的传感节点优先选为工作节点可以减少工作节点的数目，但让覆盖目标多的传感节点一直处于工作状态也会导致该节点过早的死亡，使得网络的稳定性变差。为了避免某些节点持续处于工作状态，需要考虑节点剩余能量对网络稳定性的影响，在节点调度过程中，尽量不让能量低的传感节点继续工作，所以对边缘未被覆盖的目标采用加权覆盖，其权值跟传感节点覆盖目标节点的数目和传感节点的剩余能量有关。由于每轮各节点所处的状态不同，所以各节点的能耗不同，各节点的权值也会发生不同程度的下降。在每轮结束后需要重新计算各传感节点的权值，然后将权值大的传感节点选为工作节点。归一化后的权值计算公式如下:

其中a1、a2是加权系数，根据网络环境不同可选取不同的加权系数，并且其满足约束条件:a1+a2=1。Gi表示传感节点hi所包含目标节点数目，Gmax表示本轮中单个传感节点所包含的最多目标节点数，Ei表示传感节点的剩余能量，Emax表示本轮中传感节点剩余的能量最大值。

2.3 新算法的伪代码

输入:传感器节点集 H={h1，h2，L，hn}，节点数为 n，目标节点集 K={k1，k2，L，ks}，目标数为 s，网络环境目标最小频繁项数N≥2。

输出:实现节点之间覆盖监测目标的节点集集合Gi里的节点处于工作状态时能实现对所有目标的覆盖;

2.4 算法具体实现过程

表2 传感节点与目标节点的关系

步骤1:选取频繁项等于最小频繁项N的目标，将目标频繁项等于N的目标节点放入最小频繁项的目标节点集M中(对应于算法伪代码的第一步)。

表3 最小频繁项目标与关联节点的关系

步骤2:首先将集合M中各目标节点依次取出，然后将各覆盖该目标的传感节点按照能量高低依次放入覆盖监测目标的节点集 G1，G2，…，GN，并判断覆盖该目标的传感节点存放是否导致G1，G2，…，GN独立覆盖前面的目标，如果是，则N=N－1(即使覆盖监测目标的节点集G1，G2，…，GN减少一个)并跳至步骤2进行重新划分;否则，跳至步骤3(对应算法伪代码第二步)。

表4 节点更新后传感节点与目标节点的关系

步骤3:计算各个未加入集合 G1，G2，…，GN的传感节点hi的权值Wi，选择权值最大的节点hj先工作，将hj加入集合Gi，判断Gi中的传感节点能否覆盖所有目标，如果能，则结束;否则，跳至步骤3继续选取新节点加入(对应于算法伪代码第三步)。

过程分析:以表2为例(表2由图1生成)，表2中目标节点的最小频繁项为2，其中频繁项为2的目标节点有 5、6、7、9、10、11、14 将其加入 M 中(如表3)，假设目标节点5对应的传感节点1能量高将其放入G1中，为了避免最小频繁项目标对应的传感节点同时工作，则传感节点2就必须放入G2中，对于目标6中含有传感节点1，由于传感节点1放在G1中，为了实现G1和G2独立覆盖目标1、6，则目标6对应的传感节点5必须放入G2中，同理，可以得到传感节点4、9放入G1中，传感节点7放入G2中，对于目标10我们选择能量高的传感节点8放入G1，传感节点3放入 G2，集合划分完毕，G1={1，4，8，9}，G2={2，3，5，7}能够分别完全覆盖目标节点5、6、7、8、9、10、11、14。并更新目标节点与传感节点的关系表(表2)得到新的目标节点与传感节点的关系表(表4)，计算目标节点12对应的权值最大的传感节点6放入G1(假设传感节点6权值最大传感节点12权值最小)传感节点11放入G2，判断G1和G2是否能够覆盖所有节点，发现G1和G2能够覆盖所有目标节点，此轮结束。

3 仿真实验

为了验证上述算法的有效性，本文将新算法和PEAS算法进行了仿真比较。实验环境:在win7系统下采用matlab2010作为仿真平台。在40×40区域内，随机分布25个目标节点，并且在目标区域部署40个传感节点。传感器节点的感知半径r为6。传感节点的初始能量为［100 mJ，110 mJ］上的随机数。加权系数可以根据不同网络环境选取不同的加权系数，如果传感节点的初始能量的变化范围较大时，可以适当的提高能量的权值系数a2来均衡网络中节点能量，本实验中由于传感节点初始能量的变化范围较小，因而本文选取加权系数a1、a2分别为0.5、0.5。节点的能耗模型参照文献［8、12］，传感节点处于工作状态时单位时间内能耗为1.7 mJ，休眠状态时单位时间内能耗为0.3 mJ。5个单位时间作为一轮，工作节点集每轮结束后交换一次，当传感节点的能量小于50 mJ时判定节点死亡。实验主要对网络生存周期，工作节点数、以及网络能耗进行研究和比较。图3首先给出了覆盖度与节点工作时间的关系图，网络生命周期为目标节点覆盖度为1的时间长度。从图3上可以看到节点随机分布的网络生命周期只有7轮左右即35个单位时间左右网络已经不能维持全覆盖，而PEAS算法采用根据其自身周边覆盖区域的被感知质量决定自身状态的方式，使得网络的生命周期达到了60个单位时间，网络生命周期相对于随机部署算法延长了71.43%。本文提出的新算法的网络生存周期达到了75个单位时间，它相对于PEAS算法又提高了25%，其原因是由于PEAS算法采用随机选取工作节点的方式，使得部分目标对应的某些关键的传感节点经常同时工作，使得网络生命周期下降。

图3 网络覆盖度与工作时间的关系

图4是网络工作节点数与工作时间的关系图，从图上可以清晰的看出随机部署的工作节点在网络生存周期里所需要的工作节点数最多，PEAS在网络生存周期里所需要的工作节点数为10，而新算法的工作节点数在网络生存周期内工作节点的数目主要在区间［6，8］上变动，最大只需要8个，显然低于PEAS算法在网络生存周期内的工作节点数。

图4 网络工作节点数与工作时间的关系

图5是网络中节点剩余能量与工作时间的关系图，从图上可以看到随机部署的算法网络剩余能量下降的最快，所以随机部署算法在工作过程中每轮消耗的能量最多，而PEAS算法网络剩余能量下降的坡度相对比较平缓，所以PEAS算法每轮的能耗比较小，最后看到新算法的曲线在PEAS算法和随机部署的曲线之上，可以说明新算法在工作过程中的能耗最少，网络剩余能量最大。

图5 网络能耗与工作时间的关系

图6是节点能量标准差与工作节点的关系图，从图上可以看到PEAS算法节点能量标准差在整个工作过程中最大，说明PEAS算法的网络节点能量均衡性最差，而新算法能量标准差相对较小，说明新算法的网络节点能量均衡性相对于PEAS算法有了进一步的改善。

图6 节点能量标准差与工作时间的关系

4 结论

本文提出了一种基于加权的无线传感器网络优化覆盖算法。该算法根据目标频繁项大小把目标划分成最小频繁项目标和非最小频繁项目标，然后对最小频繁项目标和非最小频繁项目标分别采用划分集合的方式和加权的方式进行优化覆盖。仿真结果表明:新算法相比PEAS算法，能够有效地减少每轮的工作节点数、均衡网络节点间的能量和延长网络的生命周期。

［1］ Rahman M D，Sajid A H.Uniformity and Efficiency of a Wireless Sensor Network’s Coverage Advanced Information Networking and Applications［C］//AINA，07.2007:506_510.

［2］ Seapahn M，Farinaz K.Worst and Best-Case Coverage in Sensor Networks［C］//IEEE Transactions on Mobile Computing.2005，4(1):84－92.

［3］ 任彦，张思东，张宏科.无线传感器网络中覆盖控制理论与算法［J］.软件学报，2006，17(3):422－433.

［4］ Slijepcevic S，Potkonjak M.PowerEfficientOrganization of Wireless Sensor Networks［C］//Proc.of the IEEE Int’l Conf.on Communications(ICC).Helsinki:IEEE Press，2001.472－476.

［5］ Tian D，Georganzs N D.A Node Scheduling Scheme for Energy Conservation in Large Wireless Sensor Networks［J］.Wireless Communications and Mobile Computing，2003，3(2):271－290.

［6］ Cardei M，Du D Z.Improving Wireless Sensor Network Lifetime Through Power Aware Organization［J］.Wireless Networks，2005，11(3):333－340.

［7］ Ye Fan，Zhong G，Lu S，et al.PEAS:A Robust Energy Conserving Protocol for Long-Lived Sensor Network［C］//Proceedings of 10th IEEE InternationalConferenceon Network Protocols.Paris，France，2002:200－201.

［8］ 刘丽萍，张强，孙雨耕.无线传感器网络多目标关联覆盖［J］.天津大学学报，2009，42(6):483－489.

［9］ 孙喜策，曹峰，王智.一种面向多目标关联覆盖的无线传感器网络节点优化调度算法［J］.信息与控制，2009，38(1):29－36.

［10］张品，姜亚光，陈磊.基于加权优化选取两级簇头的WSN路由协议［J］.传感技术学报，2011，24(3):447－451.

［11］张品，徐智福，孙岩.一种新的基于簇头优化的WSN路由协议［J］.传感技术学报，2009，7(22):1013－1017.

［12］ Chen H H，Yang Y.Network Coverage and Routing Schemes for Wireless Sensor Networks［J］.Computer Communications，2007，30(14－15):2697－2698.