基于区域内随机唤醒机制的WSN覆盖控制方法

邓鑫，张乐君

(哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨150001)

无线传感器网络(WSN)是由大量微型传感器节点构成的，这些微型传感器结构简单，计算能力和电池能量等资源有限。因此通常采用节点高密度部署的方法(20 node/m3)［1］来提高网络的整体工作性能、延长网络生命周期。如果这种高密度部署的传感器节点同时工作，势必会导致无线信息干扰、能量耗费和信息大量冗余等问题，所以节点调度技术就成为了延长网络工作时间、保证网络工作质量的重要技术之一。节点调度技术是指通过调度方法合理转换节点状态，以达到在保证网络需求覆盖质量(QoC)的前提下节省节点能量，延长网络生命周期的目的。

本文利用传感器节点可以通过控制功率来调整通讯半径的特性，给出了控制工作节点间相对距离的方法及网络覆盖度与相对距离的关系，并在此基础上提出了基于限定区域内随机唤醒机制的WSN覆盖控制协议(random wake-up mechanism within a limited region，RWMLR)。

目前针对传感器网络覆盖控制的问题已取得了一定的进展。Hefeeda等利用了几何圆盘覆盖的特性，针对圆盘感知模型提出了基于VC维和ξ-net的随机选择活跃节点的方法，并给出了该方法的集中式和分布式实现方案 RKC 和 DRKC［2］。Zou 等［3］提出了基于蚁群算法的传感器网络的节能覆盖算法。孟凡治等［4］提出了的基于联合感知模型的连通覆盖控制协议，该协议分析了在节点随机部署方式下，网络覆盖质量和网络连通性与工作节点个数、监测区域面积和节点性能参数的关系。Zhang等［5］针对三维区域的覆盖控制问题提出了基于概率模型的覆盖控制算法，该算法能达到覆盖度要求，但是在该算法中传感器节点的能量消耗较大。王换招等［6］分析了传感器感知半径服从正态分布的无线传感器网络冗余度计算模型，以及保证网络覆盖质量所需最少工作节点的计算模型，并且在此基础上提出了一种高效节能的无线传感器网络覆盖保持协议(energy efficient coverage conserving protocol，EECCP)。李超良等［7］提出了一种节点覆盖率和连通率的计算方法，该方法能描述节点感知半径、检测区域边长以及节点数量与覆盖率、网络连通率之间的关系，计算所需节点数量，该方法考虑检测边界对覆盖的影响。文献［8］提出了一种节点判定是否为k重覆盖的算法，并且提出了CCP(coverage configuration protocol)协议，该协议可以根据应用生成不同覆盖度的网络，并且在文中给出了通讯半径大于等于感知半径2倍时，能保证网络的连通性。Zhou等［9］提出了基于多目标优化的能量平衡消耗的传感器网络覆盖控制算法。

上述研究都是在节点的通讯半径固定的基础上展开的，而在文献［10］中指出传感器节点可以通过控制发送功率来改变其通讯半径。本文针对这种由可变通讯半径的传感器节点所组成的高密度均匀部署的传感器网络的覆盖控制问题进行研究。

1 网络模型和相关理论

1.1 网络模型及问题描述

假设传感器网络具有如下性质:

1)网络中所有节点都均匀的随机分布在一个平面区域Z内，并且密度足够大(20 nodes/m2)。

2)每个传感器节点的感知区域为圆形，即若感知半径为RS，其感知区域面积S=πRs2。

3)节点采用布尔感知模型，即在感知范围内的区域都能被传感器所感知，属于有效感知区域。

4)节点通讯半径可通过调节发射功率来放大或缩小，且网络工作时通讯半径大小与节点感知半径大小关系为Rc≥2Rs，以保证网络连通性［8］。

5)所有传感器感知半径相同，能耗模型相同，无GPS系统。

本文要解决在上述网络模型中，如何通过调度节点使得网络在达到要求覆盖度的前提下，生成覆盖区域Z的最小节点集，从而延长网络工作时间。

1.2 相关定义

定义1 邻居节点集:对于任意节点i∈∂，其邻居节点集的定义为V(i)={j∈∂|d(i，j)＜Rc，i≠j}，其中∂为部署在区域Z中所有节点的集合，d(i，j)表示节点i和节点j之间的物理距离，Rc表示节点i的通讯半径。

定义2 冗余覆盖面积:对于全体节点集合中任意工作节点i，它与其邻居节点集中任意工作节点感知区域重合部分的面积即为冗余覆盖面积Sr=Si∩Sj(j∈V(i))，其中Si表示节点i的感知区域面积，Sj表示节点j的感知区域面积。

定义3 网络覆盖度:网络中所有工作节点形成的监测区域总面积占被监测区域Z面积的百分比，称为网络的覆盖度。即

定义4 覆盖目标区域的最小节点集合:由文献［11］可知完全覆盖特定区域的最少圆集合的模型如图1所示。

图1 覆盖区域最小圆集合模型Fig.1 Minimum circle of coverage set model

在感知半径RS相同的条件下，传感器节点间距离为，即每个节点有6个邻居节点时，区域覆盖度为100%且所生成的区域覆盖圆集为最少覆盖圆集，其对应的传感器节点集为覆盖区域的最少节点集。

定义5 限定区域:对于任意节点i∈∂，其工作时产生的外点限定区域为S(K)={K|ε1Rs＜d(K，i)≤ε2Rs}，内点限定区域为S(K)={K|d(K，i)≤ε1Rs}，其中 ε1、ε2为传感器通讯半径参数，且1.5 ≤ε1＜ε2≤2，如图 2所示。

图2 限定区域示意图Fig.2 Limited region schematic

2 网络覆盖质量分析

引理1若2个距离为εRs的邻居节点产生的冗余覆盖面积为Sr，那么

式中:Rs为节点的感知半径，ε为通讯半径参数，并且ε≤2。

证明:如图3所示，阴影部分为传感器节点O1，O2所产生的冗余面积为Sr，O1、O2之间的物理距离为 εRs。

则Sr=2*(S扇ABO2－ SΔABO2)

证毕。

图3 节点冗余面积图Fig.3 Redundant area of working nodes

定理1设网络最低复杂度要求为k，达到最低复杂度要求时，邻居节点距离均为εRs，则

式中:ε为通讯半径参数。

证明:若使网络达到最低复杂度要求则节点间的距离达到最远距离，即εRs。如图4所示A、B、C为网络中3个工作节点，且任意两个不同节点间的物理距离为εRs，图中虚线部分区域为节点间的冗余覆盖区域，网格部分区域为覆盖盲区。

图4 最坏覆盖度示意图Fig.4 Worst coverage degree schematic

则3个工作节点对△ABC区域的覆盖度为:

∵ △ABC为等边三角形，且边长为εRs

又∵式(1)

证毕。

由式(2)的函数图象可知k与ε的关系如图5所示。由式(2)可以得出，当通讯半径参数为2时网络的覆盖度达到最低点，约为90.8%。并且从图中可以看出网络覆盖度随通讯半径参数的增大而降低。因此将网络要求覆盖度视为网络最坏覆盖度来计算网络通讯半径参数，然后按照RWMLR协议所生成的传感器网络覆盖都不小于要求的网络覆盖度。

图5 最坏覆盖度与通讯半径参数关系Fig.5 Relationship between worst coverage degree and transmission parameter

3 RWMLR协议

由定义4可知，若要在保证不同的覆盖质量的前提下利用最少的节点生成网络，则节点间的物理距离应该保持在，左右。由定理1可知，网络覆盖度仅与通讯半径参数有关，因此本协议的目的是根据网络需求的覆盖质量，合理的调整通讯半径参数，使生成的网络中工作节点保持合理的物理距离。

3.1 协议描述

在协议开始工作前，传感器节点根据覆盖度要求由式(2)计算出传感器网络达到最低覆盖度要求时的通讯半径参数。网络初始状态时所有的传感器节点处于休眠状态，在网络中随机选取一个节点转换为工作状态。

开始工作的节点会根据要求覆盖度计算出的通讯半径参数，并以ε1Rs和ε2Rs为通讯半径两次广播Hello包，对其邻居节点区域进行内点区域和外点区域的划分。Hello包中包含3个域:包类型域，节点编号域和节点状态域。收到两个Hello包的区域为内点区域，收到一个Hello包的区域为外点区域。因此外点与工作节点间的距离被限制为d∈［ε1Rs，ε2Rs］。由定理1可知网络的最差覆盖率只与通讯半径参数有关，因此在外点区域内唤醒节点而产生的覆盖度是可控的。工作节点会根据节点的优先级在外点区域内唤醒休眠节点。当工作节点的能量即将耗尽时，工作节点会根据节点优先级在内点区域内唤醒节点。

3.2 节点优先级确定

节点初始优先级为零，若i工作节点，则i的外点集中的节点优先级加1，内点集中的节点优先级减1。如图2所示阴影部分区域中的节点优先级为1，非阴影部分的节点优先级为 －1。

3.3 节点状态转换模型

本协议分为两个阶段，初始化阶段和稳定阶段。网络中每个节点都有6种状态:选举状态(ELECTION)，工作状态(WORK)，失效状态(DEAD)，休眠状态(SLEEP)，预工作状态(PRE_WORK)，预睡眠状态(PRE_SLEEP)。

初始化阶段中，被选定的节点开始工作时会触发其外点限定区域内的节点从SLEEP状态转换为ELECTION状态。ELECTION状态的节点向触发其状态转换的工作节点发选举消息，工作节点选择优先级高的节点并使其转换为PRE_WORK状态，优先级低的节点转为SLEEP状态。处于PRE_WORK状态的节点等待时间T，若在此时间段内被选为工作节点则节点转换为WORK状态;否则将节点状态转换为SLEEP状态。

在稳定阶段中所有工作节点的选取发生在有节点失效的区域。当节点即将失效时会触发其内点限定区域中的节点转为ELECTION状态，剩余过程与初始化阶段节点状态转移相同。因为节点失效与新节点选取都是在小范围区域内进行，从而不影响整个传感器网络的感知工作。网络中的状态转换如图6所示。

图6 网络中节点状态转移图Fig.6 Node state transition diagram

4 RWMLR协议性能分析

为了检验协议的性能，使用omnet++作为仿真实验平台。实验中监控区域大小为20×20 m2，节点的能耗模型为文献［4］中所采用的实验节点能耗模型，即发送接收和休眠状态的能耗比例为20∶4∶0.01。

图7为初始节点规模不同的情况下，网络的覆盖质量和所要求达到的覆盖质量之间的关系。可以看出本文所提出的协议能够保证网络的覆盖质量高于要求的覆盖质量，由于节点的通讯参数是按照所要求的网络最低覆盖度计算出的，因此网络实际覆盖质量会略高于所需要的覆盖质量，但是从图中可以看出随着要求覆盖度的增加，本协议所生成的网络覆盖度与最优覆盖度的差距逐渐减小。

图7 需求覆盖质量与实际覆盖质量的关系Fig.7 Relationship between require coverage degree and real coverage degree

图8 满足不同的QoC网络的工作时间Fig.8 Network working time under different Qocs

如图8所示为在区域中部署5 000个节点时，网络在不同的覆盖质量要求下工作的时间，从图中可以看出在不使用调度策略时，网络中所有的节点始终工作，并且保证网络的覆盖度始终保持在100%，但是在很短的时间内随着节点的能量耗尽网络的覆盖度迅速下降;在使用了本协议调度节点后，网络中的传感器节点轮流工作，降低了冗余覆盖面积，有效的减少了网络中的能量消耗，如图所示达到同样覆盖度的情况下，网络工作时间比不使用调度策略的工作时间延长了约1.3倍。但是由于网络中的节点是随机分布的，不同区域内节点分布不均匀，覆盖度并没有快速下降为0。

为了进一步体现本协议的性能，取不需要地理位置的LDAS［12］协议作为比较。实验结果如图9、图10所示。如图9所示，网络中不同时间阶段工作节点数量LDAS协议普遍高于本文提出的协议。由图10可知其网络覆盖度在达到要求覆盖度的同时也比本文提出的协议高。这是由于LDAS协议判断节点自身冗余度时，没有考虑到其两跳邻居节点对覆盖度做的贡献，因此网络中仍然存在许多的冗余节点。从这两种协议的比较中得出RWMLR协议在保证达到要求的冗余覆盖度的同时，有效的减少了网络中冗余节点的数量，从而延长了网络的工作时间。

图9 工作节点数量对比Fig.9 Comparison of the number of working nodes

图10 获得网络覆盖度对比Fig.10 Comparison between network coverage degrees

5 结束语

本文针对通讯半径可控的传感器节点组成的传感器网络覆盖度进行了分析，给出了覆盖度与通讯半径参数之间的关系，提出了基于限定区域内随机唤醒机制的覆盖控制方法(RWMLR)。仿真实验表明，本协议可以在保证网络覆盖度的前提下，使尽量少的传感器节点进入工作状态，从而减少了网络的整体能耗，延长了网络生命周期。并通过对比实验体现出本协议的优越性。

［1］SHIH E，CHO S H，ICKES N，et al.Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks［C］//Proc of the 7th Int＇l Conf on Mobile Computing and Networking(MobiCom).Rome:ACM Press，2001:272-287.

［2］HEFEEDA M.Randomized k-coverage algorithms for dense sensor networks［C］//INFOCOM 26th IEEE International Conference on Computer Communications.Anchorage，AK，2007:2376-2380.

［3］ZOU Ming，ZHANG Ping.A novel energy efficient coverage control in WSNs based on ant colony optimization［C］//2010 International Symposium on Computer，Communication，Control and Automation.Tainan，China，2010:523-527.

［4］孟凡治，王换招，何晖.基于联合感知模型的无线传感器网络连通性覆盖协议［J］.电子学报，2011，39(4):772-779.MENG Fanzhi，WANG Huanzhao，HE Hui.Connected coverage protocol using cooperative densing model for wireless sensor networks［J］.Acta Electronica Sinica，2011，39(4):772-779.

［5］ZHANG Junqing，WANG Ruchuan.A coverage control algorithm based on probability model for three-dimensional wireless sensor networks［C］//2012 11th International Symposium on Distributed Computing and Applications to Business，Engineering ＆ Science，(s.l.)，2012:169-173.

［6］王换招，孟凡志，李增智.高效节能的无线传感器网络覆盖保持协议［J］.软件学报，2010，12(21):3124-3137.WANG Huanzhao，MENG Fanzhi，LI Zengzhi.Energy efficient coverage conserving protocol for wireless sensor networks［J］.Journal of Software，2010，12(21):3124-3137.

［7］李超良，邢萧飞，刘跃华.一种新型覆盖连通率计算方法［J］.计算机应用，2011，12(31):3204-2306.LI Chaoliang，XING Xiaofei，LIU Yuehua.New method of calculating coverage and connectivity rate［J］.Journal of Computer Applications，2011，12(31):3204-2306.

［8］XING Guoliang，WANG Xiaorui.Integrated coverage and connectivity configuration for energy conservation in sensor networks［J］.ACM Transactions on Sensor Networks，2005，1(1):36-72.

［9］ZHOU Hui，LIANG Tian.Multiobjective coverage control strategy for energy-efficient wireless sensor networks［J］.International Journal of Distributed Sensor Networks，2012:1-10.

［10］JIANG J R，SUNG T M.Maintaining connected coverage for wireless sensor networks［C］//The 28th International Conference on Distributed Computing Systems Workshops.Beijing，China，2008:297-302.

［11］汪学清，杨永田.无线传感器网络中连通与覆盖问题的研究［J］.计算机工程与应用，2006，42(36)，136-139.WANG Xueqing，YANG Yongtian.Research on connectivity and cover age problem of wireless sensor networks［J］.Computer Engineering and Applications，2006，42(36):136-139.

［12］WU K，GAO Y，LI F，et al.Lightweight deployment-aware scheduling for wireless sensor networks［J］.ACM/Kluwer Mobile Networks＆ Applications(MONET)，2005，10(6):837-852.