基于节点能耗均衡的WSN 覆盖策略

冯 琳，冉晓旻，梅关林

（信息工程大学 信息系统工程学院，河南 郑州450001）

0 引 言

无线传感器 网 络 （wireless sensor networks，WSN）［1］可以对目标数据进行多目标、多角度地收集，完成探测任务［2］。如何有效组网覆盖是关键前提，组网覆盖问题是指如何确保部署节点形成的覆盖范围达到监测环境的要求［3］，而寻求合适无线传感器的覆盖部署策略是研究组网技术的首要问题，有效解决好节点数目与节点能耗之间矛盾问题［4］，决定着网络工作阶段成本代价、感知能力、通信保障、监控追踪等服务指标的改善［5］。网络生存时间作为衡量无线传感器网络性能好坏的重要指标之一，是当前研究的一大热点。当前应用在各个领域的传感器节点通常采用自供电模式，且它们具有单次部署数量大、单个体积小、布设环境恶劣等特点。组网地理环境复杂，甚至充满极大危险性，对于多次重复布设以及补充布设提出了挑战，因此网络对单次布设所能达到的服务时长依赖性极强。网络的性能会随着节点耗能的死亡而慢慢丧失，在现有条件下，研究如何有效利用初次部署节点发挥最优的网络服务周期至关重要。如何在大规模的网络环境下最有效地利用节点能量，保证节点能耗的均衡性，延长网络生存时间是节能覆盖优化研究的一项重要内容。

网络生存时长是指目标区域在一直满足设定覆盖率这一前提要求下WSN 所能持续工作的最大时长。改善网络节点能耗的均衡性，促使整体节点能耗降低并趋于更强的同步性，即保证所有节点趋于同一时间段耗能完毕，也就是通常说的一致的生存时间。在地理环境复杂、危险性极高的区域进行无线监测网的构建需要付出很高的代价，不允许节点重新补充布设，而且对网络的覆盖性能要求通常比较高，不允许局部节点过早因耗能过度 “死亡”导致覆盖区域盲区出现。因此要求一次性部署完毕后在保证一直满足覆盖要求下最大程度延长网络的生存时长。

无线传感网监测如图1所示。

图1 无线传感网监测

假定模型为事件驱动型网络，节点在执行感知任务时消耗的能量占主导地位，处于休眠状态的节点不具有感知能力，不会引起能量消耗。

1 相关工作及应用模型

1.1 相关工作

针对WSN 覆盖优化中的重难点问题，相关研究人员进行了大量工作。朱艺华等［6］从路由的分流角度出发，研究了如何在数据的分组与转发跳数的基础上进行改善算法以延长网络生存时间。经典方法则从另一个角度提出轮换“活跃”和 “休眠”节点的节能覆盖方法，在不影响网络整体覆盖性能的前提下减少了节点的耗能量，有效的延长了网络的生命周期［7］。也有相关研究通过引入拓扑控制中的功率思想，并用GA 求解数学模型，实现节约能耗的目的［8］。韩志杰等提出了节点自适应传感半径调整算法，在不影响覆盖性能的前提下，从降低节点覆盖的冗余度出发，有效地实现了节点最佳覆盖范围的选择以及对覆盖的控制［9］。LU 等通过比较由于距离Sink节点远近不同而导致的节点能耗差异，得到节点部署的密度函数，在不影响覆盖效果的情况下有效地均衡了整个网络的能量消耗，避免了覆盖空洞的出现［10］。对于异构传感器的研究者采用多条直线采样覆盖的方法，将二维平面的覆盖优化问题转化为对一维直线的覆盖优化问题，通过建立非线性二次优化数学模型求次优解的办法最终实现异构传感器节点的覆盖优化目标［11］。另一方面，改进策略也是优化覆盖性能的重要手段，比较经典的有以节点簇为代表的LEACH 策略以及在它基础上进行改进的HEED 算法等，后者从延长网络生存时长的角度出发，考虑到节点剩余能量、通信代价等因素，提出了一种新的簇头选举方法，该方法的缺点也很明显，要求所有节点的通信半径必须保持一致且WSN 网络节点必须保持均匀分布，实用性不强。还有部分相关文献从其它角度提出网络节能优化算法，但都离不开节点 “活跃”和“休眠”两个状态的有效切换。基于该思想的WSN 节能优化相关策略的关键就是在确保覆盖要求的前提下最大化轮换节点集合数目。

1.2 应用模型

1.2.1 节点感知型

通常采用较多的感知模型有两种，分别为布尔感知模型与概率感知模型，布尔 （0—1）模型是一种明确划分感知范围的模型，概率感知模型对复杂环境中异构传感器具有较强的实用性，在相关文献中该模型得到有效应用［12］。布尔模型简单实用，适合作为节点状态切换优化策略的假设模型。假定节点覆盖的目标区域为二维平面，传感器节点用si表示，（xi，yi）为相对应的节点坐标，则目标点p（xp，yp）被节点si检测的概率为

目标点p 被整个监测区域内的传感器节点同时进行检测的联合检测概率为

式中：sall——对目标节点具有感知能力的传感器节点集合。n——所有被部署的传感器节点。

1.2.2 覆盖模型

（1）区域覆盖率：

感知模型为1.2.1章节中假设模型，考虑到优化目标的性能评价标准，对监测区域进行网格划分 （m×n），并将其离散成对应的像素点。本文中，网络覆盖率定义为满足式 （2）要求的单元格数量与总的单元格数量的比值，即

如果目标区域中的任一像素点都能够被至少一个节点的感知范围所覆盖，则称该区域实现完全覆盖。图2是本文采用的完全覆盖节点部署，为了更好验证后续的效果，初期布设我们假定节点趋于均匀分布，避免节点过度集中的情况出现。该系统中，出现在任何网格点上的目标都能够被检测到。

（2）能量均衡：

1）局部能量Ek：对目标区域进行均匀网格划分，网格数量为k。第k（k∈K）网格的局部能量为该网格中所有节点剩余能量的均值，即

图2 传感器节点覆盖

式中：nk——第k 网格中所包含的节点数量，Ekω——第k网格中节点ω 的剩余能量。

2）能量均衡系数Em：在1）中求得局部能量的基础上分别得到其中的最大值、最小值以及平均值，定义最大值与最小值的差值与平均值的比值代表感知网络的能量均衡系数Em，即

Em的大小能够很好地体现出整个网络不同区域之间节点能耗的均衡性，Em的值越小说明所有节点整体能量消耗越均衡，反之则代表能耗均衡性越差。

（3）网络生存时长：

f3代表对网络生存时间的归一化处理，当网络节点由于耗能导致覆盖率下降到某一设定值时我们认为网络生存时长结束，进行归一化处理后得到f3。

因此下式可以作为一个整体优化目标函数

式中：ω1、ω2、ω3——不同子目标函数对应的权值，其满足关系式ω1＋ω2＋ω3＝1。显然整体目标函数f的值将介于0～1之间，其值越大，说明整体优化效果越好。f1代表式（3）中的覆盖率指标，f2则表示式（5）中的能量均衡系数。

1.2.3 节点假设条件

（1）布设节点均为同构节点，具有相同的性能参数（如初始能量、能耗参数、感知半径、通信半径、节点状态切换能力等），感知模型与覆盖模型满足1.2.1章节所述。

（2）节点能够通过GPS或者其它定位算法等得到自身的位置信息，且每个节点能够准确获取其邻居节点的地理位置信息。

（3）所有节点具有统一的能耗模型，为便于其它优化目标值得获取，假定节点能耗只与其活跃时间有关，其处于活跃状态周期内时每秒耗能为0.1J，且节点能够得到自身的能量剩余量。

2 WSN 覆盖策略

2.1 轮换活跃／休眠节点优化策略

节点 “活跃”和 “休眠”状态的相关定义请见参考文献［7］，“轮换优化策略”的主要思想是通过调整节点状态切换形式达到优化网络生存时长的目的。节点的每个轮换周期都由self－scheduling阶段和working两个阶段组成，在进行判定阶段主要进行的工作分为两步：

（1）各节点首先向满足感知条件的邻居节点进行通告信息的广播，通告信息主要指节点身份、节点位置信息等，对邻居节点进行定义

ri＝rj说明为同构传感器节点，在本文中满足该件。

（2）节点判定自身对目标的感知任务是否可以交给邻居节点代替完成，如若可以则需要产生相应的信息进行通告，之后该节点可以进入 “休眠状态”，判定后找不到替代工作的节点则需要继续执行感知任务。

针对上一段提出的节点轮换活跃与休眠策略，节点自身感知任务能够被邻居节点替代必须满足以下位置条件：

由几何知识，节点方向角为

中心角为

由固有的条件：0＜d（i，j）≤r可得中心角的变化范围：120°≤θj→i＜180°由此可得：一个节点必须至少由3个邻居节点才能覆盖其感知区域，才有条件进入休眠状态。

覆盖盲区产生条件：节点根据之前描述的判定标准判定自身是否可以在下一状态进入休眠，当相邻节点同时满足条件并在下一轮换周期同时执行休眠操作时，产生如图3（b）所示的覆盖盲区。

如在图3 （a）所示，节点e的感知范围完全可以被邻近节点 （a、c、f）完全覆盖替代，同样，节点f的感知区域也能够同时被其邻近节点 （b、d、e）完全覆盖替代，因此判定节点e、f都满足 “休眠”条件，但当这两个节点同时执行休眠任务时就会出现部分区域无法被任何感知节点覆盖的现象，即所谓的 “盲区”，如图3 （b）中虚线包围区域所示。

图3 “盲区”

早期的基于延长网络生存周期的节点活跃／休眠覆盖策略虽然在节约网络节点能量，延长系统生命周期方面有明显改进，但覆盖 “盲点”的出现直接影响了网络的覆盖效果。因此该策略对于一些敏感、危险多发区域的覆盖感知效果鲁棒性较差。

2.2 基于消除盲区的覆盖策略的改进

针对2.1章节中覆盖 “盲区”的出现，文献 ［7］提出一种改进方法，主要思想是在保持原有的感知覆盖效果下最大限度减少网络生存周期中工作节点的数量，既做到了“盲点”消除，又节省了网络节点能量。在判定节点是否向休眠状态转化之前先要经历退避时间：只有经历了该退避时间Td之后节点才能自检，且该退避时间是随机的，当然，周围节点的密度也可以作为计算退避时间Td的重要参考，这样可以对网络中 “活跃”节点的数量进行控制，从而达到减少节点能耗的目的。只有消除覆盖过程中的 “盲区”，才能确保网络功能运转正常，在节点在进行 “休眠”之前加入等待时间Tw，Tw具有一定的随机性，节点在等待时间过程中监听其邻居节点的状态是否发生变化。

该策略实际上是LEACH 策略的一个扩展，它不仅能够有效控制网络中的冗余节点，而且对于节点状态轮换失误、节点失效都具有很好的鲁棒性，因此对网络的覆盖优化改善效果明显。研究结果表明该策略能够有效消除传统策略导致的覆盖 “盲区”，而且网络生存时间较LEACH 策略延长了1.7倍，但是其在如何进一步均衡节点的能耗方面没有涉及，这也是该策略值得改进之处。

3 基于节点能耗均衡的网络生存时间延长策略

现有的无线传感器主要采用自携带电池的方法进行供电，局限于节点自身体积的大小，电池电量有限，且这一问题在短时间内无法根治；感知网络通常应用在山区海岛、战场前沿等布设难度极大的领域，因此如何最小化网络运行过程中发生的能量消耗，优化网络的整体生存时间是进行研究的关键，才能减少节点的重复补充布设，降低网络运行成本。

3.1 网络生存时间的延长

如第一节中介绍，某些特定环境不仅单纯有在保持覆盖率的基础上降低节点耗能有要求，对基于节点能耗均衡性下的网络生存时长的延长提出了更高的标准。在本文中我们定义网络生存时间为从网络建立到由于部分节点耗能完毕而导致网络覆盖率下降到某一设定值时网络所历经的时间周期。

3.2 改进思想及目的

首先对节点剩余能量进行百分比量化，为后续改进节点进入休眠状态前的退避时间Tw做准备，促使剩余能量较少的节点有更大的机率进入休眠状态。该改进策略不仅要求能够消除原有的覆盖盲区，在均衡节点能耗与延长网络生存时间也需要发挥明显作用。

（1）根据式 （7）可计算周围节点的数量，由此周围节点密度决定退避时间Td，显然，密度越小退避时间会相应缩短，利于降低节点的整体能耗

式中：Ni——节点i周围节点的数量；No——所有节点周围节点的最大值；Ta——设定的基础退避值，根据具体的布设场景进行设置。

（2）节点根据计算得到的剩余能量量化值决定Tw的值，从而保证节点能量剩余较少的更早地进入休眠状态，均衡网络的能量消耗。也是本文研究的关键所在

式中：Tw——节点进入休眠状态的等待时间；To——最大等待时间；Em与Eo——节点的剩余能量与初始能量；α——均衡系数，可自行设定。

3.3 覆盖优化流程

根据改进策略的思想得到覆盖优化的具体流程如图4所示。

算法步骤：

（1）按照1.2.2章节中的覆盖模型对目标区域进行部署覆盖，并依据式 （3）计算覆盖率fn；

（2）每个时间轮Tn开始前首先计算当前的覆盖率fn与能量均衡系数fE，并判断fn与标准fo的关系，若fn＜fo，则认为网络生存时间结束；若fn≥fo，则继续下面步骤；

（3）由式 （7）得到节点的邻居节点数量并计算邻居节点密度，根据式 （11）计算得到退避时间Td；

图4 覆盖优化流程

（4）根据2.1 章节中的准则判定可进入休眠状态的节点；

（5）由式 （12）得到等待时间Tw，执行退避时间后节点进入休眠状态；

（6）进入下一次判定循环。

4 仿真与结果分析

本文在MATLAB2009 平台下进行仿真实验，节点在50m×50m 环境下按照图1的覆盖示意图进行区域覆盖部署。传感器感知半径均为5m，通信半径均为10m，节点初始能量均为30J，传感器采集频率为0.2 Hz，不考虑网络中心汇聚节点，采集目的节点为所布设所有节点，假定节点处于活跃状态时耗能为1J／轮 （5s），节点处于休眠状态时耗能可忽略。

图5呈现的是目标区域的节点覆盖效果。为了更好地验证本文策略优化性能，区域要确保实现全覆盖且部分区域达到多重覆盖，这是后面研究覆盖盲区的消除以及节点的能耗均衡共同的重要前提。

针对子目标函数——覆盖率进行仿真，结果如图6 所示。为了简化仿真程序，我们只对布设75个传感器节点的情景进行仿真分析，当区域覆盖率下降到90%时认为网络生存时间终结。

图5 目标区域覆盖效果

图6 覆盖率变化曲线

网络运行初期既没有节点死亡也没有覆盖盲区的出现，区域覆盖率将持续保持100%，如图6 所示的初期平稳直线。随着时间推移，出现节点耗能完毕，导致覆盖率出现下降趋势，如图中从第24×5s开始所示，到150×5s时覆盖率下降到标准以下。当然，在第44×5s之前覆盖率虽然一直保持在100%并不代表这段时间没有节点死亡，只是少数死亡节点并没有影响到整体的覆盖性能。

图7展示的是3种不同方法的覆盖率随时间变化曲线。起始阶段普通轮换机制由于覆盖盲点的出现导致网络初期覆盖率无法保持在100%，如图7 中普通轮换机制曲线所示；本文方法由于对节点进行了均衡能耗处理，覆盖率下降具有一定的规律性且较缓慢，文献 ［7］中的方法虽然也在普通机制的基础上进行了改进，但由于节点能耗均衡性较差，优化效果并不理想，如图7文献［7］算法曲线所示。

图8是另一个子目标函数——均衡值的数据统计，之前已经提到均衡值越小代表节点的能耗均衡性越良好。由于没有采取任何均衡措施，前两种方法得到的均衡值不会有太大差异，从图8普通轮换机制与文献 ［7］算法的均值点可以证实该结论。而本文的均衡值要明显低于前两种方法，随着网络生存时间的推移，均衡差值会越来越大，说明均衡性发挥的作用会越来越明显，正如图8所示。

图7 覆盖率变化对比曲线

图8 均衡值随时间变化统计

图9展示的是网络中死亡节点数量随时间的变化曲线。虽然普通轮换机制休的休眠策略容易导致大量覆盖空洞，影响整体覆盖率，但普通轮换机制使得更多的节点处于休眠状态，死亡节点的数量要少于本文算法与文献 ［7］算法，如图9普通轮换机制曲线所示。本文算法对于节点能耗均衡性使得死亡节点数量要少于文献 ［7］算法，正如图9文献 ［7］算法与本文算法对比曲线所示。

图10是不同策略网络生存时间的对比，分别对节点数量为50、75、100不同情况下的生存时间进行统计。文献［7］法由于时延的引入，降低了活跃节点的数量，对节点的整体能耗降低起到了一定作用，相对应延长了网络的生存时间；而本文方法在时延的基础上加入了能耗均衡性的考虑，将进一步延长网络的生存时间，且当节点数目增大时，节点的能耗均衡所起到的效果会更加明显，正如图10所示当节点数目为100时本文策略下的网络生存时间比节点数量为75时提高效果更优一样。

图9 死亡节点数量变化曲线

图10 网络生存时间对比

5 结束语

针对式 （6）提出的整体优化目标函数对其3个子函数进行了数据采集并分别进行了方法效果对比。在均衡值、网络生存时间以及节点死亡率方面本文提出的策略都表现出了更优良的性能，为一些敏感、偏远、危险的布设区域争取了更多的网络生存时间，避免了多次重复部署的危险性，降低了布设与维护代价。为后期特定场景的针对性需求提供了研究基础，在此基础上我们将对覆盖优化进行更为细致的探讨。当然，文章进行探讨时将节点简单分为活跃于睡眠两种状态，没有考虑节点处理、转发、通信多种状态以及作为Sink节点等多种情况引起的耗能不均衡，节点能耗模型有待进一步细化深入。

［1］XIAO Fu，WANG Ruchuan，SUN Lijuan.Coverage enhancing algorithm for wireless multi－media sensor networks based on three－dimensional perception ［J］.Journal of Electronics，2012，40 （1）：167－172 （in Chinese）.［肖甫，王汝传，孙力娟.一种面向三维感知的无线多媒体传感器网络覆盖增强算法［J］.电子学报，2012，40 （1）：167－172.］

［2］ZHANG Yayun，JI Zhicheng.Virtual force based multiple particle swarm optimization for deployment strategy in wireless sensor networks ［J］.Journal of Jiangnan University （Natural Science Edition），2012，11 （4）：428－431 （in Chinese）. ［张亚云，纪志成.虚拟力导向多粒子群算法的WSNs部署策略 ［J］.江南大学学报（自然科学版），2012，11 （4）：428－431.］

［3］Yadav J，Sandeep M.Coverage in wireless sensor networks：A survey ［J］.International of Electronics and Computer Science Engineering，2013，2 （2）：464－471.

［4］YAO Xiangguang，ZHOU Yongquan，LI Yongmei.Hybrid algorithm with artificial fish swarm algorithm and PSO ［J］.Application Research of Computers，2010，27 （6）：2084－2086（in Chinese）.［姚祥光，周永权，李咏梅.人工鱼群与微粒群混合 优 化 算 法 ［J］.计 算 机 应 用 研 究，2010，27 （6）：2084－2086.］

［5］Siddappa M，Raju C.Survey on efficient coverage and connectivity of wireless networks using intelligent algorithm ［J］.Information Technology and Computer Science，2012，5：39－45.

［6］ZHU Yihua，YANG Chenxi，WU Wandeng，et al.Diffluent traffic routing algorithms trading of network lifetime and number of packet hops for wireless sensor networks［J］.Chinese Journal of Sensors and Actuators，2009，22 （2）：273－279 （in Chinese）.［朱艺华，杨晨曦，吴万登，等.无线传感器网络权衡生存时间与数据分组跳数的分流路由算法 ［J］.传感技术学报，2009，22 （2）：273－279.］

［7］Tian D，Georganas ND.A node scheduling scheme for energy conservation in large wireless sensor networks ［J］.Wireless Communications and Mobile Computing，2003，3 （2）：271－290.

［8］YIN Weili，CHEN Wei.Simulation research for wireless sensor networks based on genetic algorithm ［J］.Computer Simulation，2010，27 （10）：120－123 （in Chinese）. ［殷卫莉，陈巍.遗传算法在无线传感器网络覆盖中仿真研究 ［J］.计算机仿真，2010，27 （10）：120－123.］

［9］HAN Zhijie，WU Zhibin，WANG Ruchuan，et al.Novel coverage control algorithm for wireless sensor network ［J］.Journal on Communications，2011，32 （10）：174－184 （in Chinese）.［韩志杰，吴志斌，王汝传，等.新的无线传感器网络覆盖控制算法 ［J］.通信学报，2011，32 （10）：174－184.］

［10］Lu K，Liu G，Mao R，et al.Relay node placement based on balancing power consumption in wireless sensor networks［J］.IET Wireless Sensor Systems，2011，1 （1）：1－6.

［11］DU Xiaoyu，SUN Lijuan，GUO Jian，et al.Coverage optimization algorithm for heterogeneous WSNs ［J］.Journal of Electronics ＆ Information Technology，2014，36 （3）：696－702 （in Chinese）. ［杜晓玉，孙力娟，郭剑，等.异构无线传感器网络覆盖优化算法 ［J］.电子与信息学报，2014，36（3）：696－702.］

［12］LIU Weiting，FAN Zhouyuan.Coverage optimization of wireless sensor networks based on chaos particle swarm algorithm［J］.Journal of Computer Applications，2011，31 （2）：338－340 （in Chinese）. ［刘维亭，范洲远.基于混沌粒子群的无线传感器网络覆盖控制 ［J］.计算机应用，2011，31 （2）：338－340.］