基于网格划分的无线传感器网络多重覆盖算法*

刘志坤，刘 忠，夏清涛，李朝旭

（海军工程大学电子工程学院，武汉 430033）

基于网格划分的无线传感器网络多重覆盖算法*

刘志坤，刘 忠，夏清涛，李朝旭

（海军工程大学电子工程学院，武汉 430033）

为了延长无线传感器网络的工作周期，在满足网络覆盖性能的前提下，可利用调度算法让一部分节点进入休眠以节省能量。提出了一种基于网格划分的无线传感器网络多重覆盖算法，新算法包括冗余节点判断和节点调度两部分。将节点覆盖区域划分为多个网格，通过判断各个网格是否满足覆盖要求，进而判断节点是否冗余。新算法给出了边界冗余节点判据，在调度过程中能够克服边界效应的影响，同时通过冗余节点能量比较，避免了休眠冲突和覆盖盲区的产生。仿真结果表明，与传统的CPNSS算法相比，新算法对冗余节点的判断更为准确，在网络工作集和平均覆盖度两项性能评价指标上均优于传统调度算法，且对网络节点数量增加造成的影响不敏感，能够有效地减少网络冗余，起到了提升网络性能的效果。

无线传感器网络，多重覆盖，网格，冗余

引言

无线传感器网络在工业控制、环境监测、医疗卫生、智能家居、战场监测等诸多民用和军事领域有着广泛的应用［1-2］。在这些应用中，各个传感器节点分别采集其周围的信息，将这些数据发送并整合，从而获得整个区域内的完整状况。因此，覆盖问题是该领域的基础性问题之一。根据节点散布方式不同，覆盖可分为确定覆盖和随机覆盖两种［3］。确定覆盖常用于友好型环境，比如室内［4］。而在污染区域或是战场等恶劣环境中，由于难以准确布放节点，大多采用飞机、舰船等进行随机散播，称之为随机覆盖。

对于随机覆盖，为了保证网络覆盖质量，必须采用高密度节点部署，以免出现覆盖盲区，这样做的后果是在覆盖区域内出现大量冗余节点。这些冗余节点如果处于工作状态，不但浪费了整个网络的能量，缩短了网络的存活周期，而且会带来通信干扰等一系列问题［5］。通常较合理的做法是采用节点调度控制算法，仅保留能够保证网络连通度和覆盖质量的部分节点处于工作状态，让其他节点进入休眠状态以节省能量，从而延长网络寿命。调度控制算法研究的关键之处在于冗余节点的判别［6-12］。

通过文献［6-12］的分析，发现存在的缺陷主要集中于两点：一是给出的冗余节点判据不准确，二是集中式算法不适合大规模网络。例如文献［6］没有考虑节点覆盖区域可能出现过多的覆盖重叠，导致工作节点数量过多。文献［7］给出的冗余节点判据为必要而非充分条件，因此，会出现覆盖盲点。同时，该协议没有考虑节点由休眠状态转入工作状态对网络覆盖度的贡献，因此，导致覆盖效率偏低，产生节点冗余。文献［8-9］的冗余判据则为充分非必要条件，同样会导致多余的工作节点。文献［10］则需要集中式计算并且无法保证对目标区域的完全覆盖。文献［11］则仅给出了集中式算法。基于上述的研究，本文提出一种基于网格划分的分布式k-覆盖调度算法，简称 GPSA（Grid Plotting based Scheduling Algorithm）。

1 模型及相关定义

1.1 网络模型

假设目标区域为二维平面，区域中已随机布放足够多的节点，通过合理的调度算法选出其中部分节点工作即可以满足k重覆盖要求，其他节点可进入休眠状态，在必要的时候再被唤醒。节点的感知模型采用常见的0-1模型（布尔模型）［13］：传感器节点的感知区域为以节点为圆心，探测距离为半径的圆。网络中所有节点为同构节点，具有相同的探测半径和通信半径，并且满足通信半径大于两倍的探测半径，文献［7］证明了在此条件下，网络的连通性问题包含在覆盖性问题之中，不需要单独作考虑。网络通过同步时钟保持时间同步，网络中的节点位置通过GPS设备或者自定位算法［14］获得，本文中作为已知条件使用。节点在部署后不再移动，也不允许外界进行维护。

1.2 相关定义

定义2：对于区域A中的节点si和任意其他节点sj，sj与si之间的欧式距离小于等于它们的探测距离之和，即d（si，sj）≤rsi+rsj，则称节点sj为si的邻节点。由于本文假设网络节点同构，因此，满足d（si，sj）≤2rs即可。

定义3：区域A中的任何一点至少可以被k个节点感知到，则称区域A被k覆盖。

定义4：区域A内的节点si，其覆盖圆域内的任何一点都可以被其他k个节点感知到，则称节点si为k重覆盖要求下的冗余节点。

2 节点调度算法GPSA

对于传感器网络而言，如果非冗余节点进入休眠状态，网络的覆盖水平会下降，而冗余节点进入休眠后，不仅不会降低覆盖水平，而且可以提升网络性能。因此，为了保证网络的覆盖质量，首先应甄别出冗余节点，而后采用合理的调度算法使之进入休眠状态。

2.1 冗余节点判定准则

本文给出一种基于网格划分的冗余节点判定法则。具体描述如下：

设网络要求k覆盖，对节点si的覆盖圆作以其坐标（xi，yi）为中心，2rs为边长的外切正方形，而后对其采用正方形网格划分，计算节点si与各网格中心点Oi的距离，若在rs之内，将此网格中心点放入集合M，依次检测M中的元素是否被k覆盖。显然，节点si只可能与其邻节点存在覆盖重叠部分，因此，只需判断M中的元素是否被si的邻节点k覆盖即可。如果存在某网格未被k个邻节点覆盖，则认为节点si非冗余节点，如果M中所有点均被k个邻节点覆盖，则判断si为冗余节点。

显然有一部分网格在节点si的覆盖范围之外，因此，不需要检测，如下页图1所示，标注T的网格是需要进行覆盖检测的。网格是否需要检测的判据是：网格中心到节点的距离小于等于节点的探测半径。设网格中心坐标为（gx，gy），则判决式为：

网格划分得越小，结果越准确，但计算越复杂，因此，网格的大小可以根据实际情况确定，以满足具体应用要求为准。

该判定准则不仅对普通节点有效，进一步完善后同样适用于处于监测区域边界的节点，这是很多传统算法无法实现的。如下页图2所示，以目标矩形区域的左下顶点为坐标原点O，矩形的下边界和左边界为x轴和y轴，以上述方法对边界节点s1的覆盖圆进行网格划分后，处于目标区域外的网格中心坐标为（x1i，y1i），则x1i和y1i必然有负值或者大于区域的最大边界值xmax或ymax的情况出现。因此，只需在找出待检测网格中心后，删除集合中坐标值为负值或者大于区域的最大边界值xmax或ymax的点，即可得到最终的待检测网格集合。

图1 检测网格示意图

图2 边界节点冗余判别示意图

2.2 调度算法

以冗余节点判断准则为基础，下一步可以建立节点调度协议，使各个节点尽可能处于合理的状态，提升网络的监测效率。

在GPSA算法中，节点存在4种状态：工作状态、待工作状态、休眠状态和待休眠状态。第一步是初始化阶段，此阶段节点刚刚随机部署完毕，所有节点处于工作状态，各节点广播自己的位置信息，获取邻节点的位置信息，建立自己的邻节点集合，为节省能量，广播半径取两倍探测半径，这是因为两倍探测半径距离之外不可能存在邻节点。第2阶段是节点状态判定阶段，主要是通过冗余节点判定准则找出冗余节点。第3阶段是退避阶段，如果所有节点同时作出判定，很可能会出现覆盖盲点。如图3所示，节点s1和节点s1根据冗余节点判定准则均认为自身为冗余节点（单重覆盖的情况下），但如果同时进入休眠状态，则会出现覆盖盲区，如图3（b）所示，因此，需要引入退避机制，从两者之中选出一个进入休眠，另一个则保留作为工作节点。本文采用一种基于能量选择的策略［11］：在分别判定自身位冗余节点之后，节点s1和节点s2进入待休眠状态，等待Tw时间段再确定是否进入休眠状态，在Tw时间内分别向各自的邻节点广播一个包含自身能量信息的Quit消息，收到邻节点的Quit消息后，s1和s2将比较当前各自的能量，能量较低的进入休眠状态，并广播一个Sleep消息，使其邻节点更新邻节点集合，能量较高的则继续工作。如果直到Tw溢出都没有收到Quit消息，则进入休眠状态。进入休眠状态的节点，设置休眠计时器Ts，当Ts溢出，则转入待工作状态，广播一个ASK消息，索取邻节点信息，收到ASK消息的节点则再次广播自身的位置信息，并更新自己的邻节点集合。

图3 冗余节点休眠冲突

整个调度过程如图4所示。

图4 调度算法示意图

3 仿真及性能评估

因为在假设中已承认目标区域内节点密度足够大，因此，本文主要采用工作集和平均覆盖度两项指标来评估算法的性能。工作集是指为满足监测要求，由调度算法从网络中选出的工作节点的数量。工作集越小，传感器网络总体能耗就越小，通信冲突越少，调度算法的性能越好。平均覆盖度是指工作集中，能够监测到区域内发生的任一事件源的节点数量［15］。平均覆盖度越低，说明冗余节点数量越少，调度算法的性能越出色。在仿真中平均覆盖度的计算方法为：将目标区域划分为单元格，假设每个单元格的中心有1个事件发生，计算能够覆盖该单元格中心的节点数量，即为该事件的覆盖度。将所有事件的覆盖度之和取平均，即得到网络平均覆盖度。

将本文提出的GPSA算法与文献［6］中提出的经典算法CPNSS进行仿真比较，仿真工具采用Matlab7.1进行，为了便于算法比较，参数设置与文献［6］相同，具体为：区域大小为50 m×50 m，节点数取100个～300个，节点的探测半径为10 m，通信半径为20 m。在相同条件下取10次仿真的均值作为最终的结果进行比较。

图5是不同调度算法下的工作集数量（单重覆盖需求）。可以看出，在部署节点总数相同的条件下，GPSA算法的工作集均小于CPNSS算法，也就是说GPSA算法较之CPNSS算法可以用更少的节点满足区域监测要求。同时发现，随着节点部署数量的增加，CPNSS算法的工作集在缓慢增大，分析主要有两点原因造成：一是由于该算法没有考虑边界节点的影响，随着随机部署节点数量的增加，靠近区域边界的节点数也在增加，这部分节点不会被判定为冗余节点，从而导致了整个工作集的增大。另一个可能的原因是，由于其判据为充分非必要条件，因此，节点部署总数越多，漏判的数量也会有所增大。而GPSA算法由于其判据相对精确且考虑了边界效应，因此，工作集大小受节点数量影响较小，相对保持稳定。

图5 节点数与工作集的关系

图6 节点数与网络平均覆盖度的关系

图6是不同调度算法下的网络平均覆盖度（单重覆盖需求）。在初始情况下，即没有进行任何节点调度，所有节点均处在活跃状态时，部署100个节点时网络的平均覆盖度高达11.283，并且随着节点数量的增大而急剧增加，说明网络处于高度冗余覆盖状态。经CPNSS算法调度之后，部分节点进入休眠状态，100个节点时网络的平均覆盖度降低到4.727，网络的冗余程度得到了明显的改善，随着节点总数增加到了300个，网络平均覆盖度缓慢增加到了7.182，说明CPNSS调度算法能够有效地降低冗余度。而经过本文GPSA算法对网络进行优化后，网络的平均覆盖度得到了进一步降低，并且对部署节点数量增加造成的影响不敏感，说明该算法对网络中冗余节点的判别非常准确，其降低网络冗余效果最优。

对于满足不同覆盖要求情况下，两种算法的工作集大小进行比较，网络中节点的数量为600个，网络的覆盖要求从1重增加到3重，其他仿真条件不变，结果如表1所示。从表1可以看出，随着覆盖重数的增加，CPNSS算法和GPSA算法的工作集都会增大。对于不同的覆盖重数，GPSA算法得到的工作集均小于CPNSS算法的结果。

表1 重覆盖下的节点工作集大小

4 结 论

本文提出的GPSA调度算法，通过对每个节点覆盖区域进行网格划分，能较准确地找出网络中的冗余节点并使之休眠，可以克服边界效应，同时该算法考虑到了节点能量这一因素，保护了低能量节点，均衡了节点能耗，避免了由休眠节点造成的覆盖盲区，从而在不影响网络监测性能的前提下，降低了网络整体能耗，延长了网络存活期。仿真试验表明，该算法优于经典的CPNSS算法。

［1］Akyildiz I F，Su W，Sankarasubramaniam Y，et al.Wireless Sensor Networks:a Survey ［J］.Computer Networks，2002，38（4）:393-422.

［2］李建中，高 宏.无线传感器网络的研究进展［J］.计算机研究与发展，2008，45（1）：1-15.

［3］王 伟，林 峰，周激流.无线传感器网络覆盖问题的研究进展［J］.计算机应用研究，2010，27（1）：32-35.

［4］霍宏伟，郜 帅，牛延超，等.基于室内传播模型的无线传感器网络节点部署策略研究［J］.中国工程科学，2008，10（9）：64-69.

［5］王换招，孟凡治，李增智.高效节能的无线传感器网络覆盖保持协议［J］.软件学报，2010，21（12）：3124-3137.

［6］ Tian D I，Georganas N D.A Coverage-preserving Node Scheduling Scheme for Large Wireless Sensor Networks［C］// Proceedings of ACM Workshop on Wireless Sensor Networks and Applications.New York:ACM，2002:124-128.

［7］Wang X R，Xing G L，Zhang Y F.Integrated Coverage and Connectivity Configuration in Wireless Sensor Networks［C］// Proceedings of the 1st ACM Conference on Embedded Networked Sensor Systems.New York:ACM，2003:234-236.

［8］Huang C F，Tseng Y C.A Survey of Solutions to the Coverage Problems in Wireless Sensor Networks［J］.Journal of Internet Technology，Special Issue on Wireless ad Hoc Sensor Networks，2004，12（3）:2356-2359.

［9］孙 超，赵路路，张 影，等.无线传感器网络分簇拓扑的覆盖区域节点调度优化算法研究［J］.传感技术学报，2010，23（1）：116-121.

［10］鲍喜荣，张 石，薛定宇.基于改进的Voronoi划分的集中式算法的无线传感器网络覆盖问题研究［J］.信息与控制，2009，38（5）：620-623.

［11］陶 洋，曾晓玲，罗 卫.无线传感器网络中覆盖控制算法研究及改进［J］.计算机应用，2010，30（6）：1459-1462.

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

［13］Onur E，Ersoy C，Delic H.How Many Sensors for an Acceptable Breach Probability Level［J］.Computer Communications，2006，29（2）：172-182.

［14］刘志坤，刘 忠，唐小明.基于改进型粒子群优化的节点自定位算法［J］.中南大学学报（自然科学版），2012，43（4）：1371-1376.

［15］陶 洋，林艳芬，黄宏成.无线传感器网络中的覆盖优化算 法 研 究 ［J］.计 算 机 工 程 ，2011，37（1）：119-121，124.

Multi-coverage Algorithm Based on Grid-plotting in WSN

LIU Zhi-kun，LIU Zhong，XIA Qing-tao，LI Chao-xu
（School of Electronic Engineering，Naval University of Engineering，Wuhan 430033，China）

In order to prolong the lifetime of Wireless Sensor Netwoks（WSN）while keeping the coverage performance，the scheduling algorithm can make some nodes sleep and the energy is saved.A multi-coverage algorithm based on grid-plotting in WSN is proposed，it contains two parts which are redundant node judging and node scheduling.The node coverage area is divided into grids and the redundant nodes are determined through judging each grid can satisfy the coverage requirement or not. The boundary redundant node judging rule is given and the boundary effect influence can be overcome in the scheduling process.Besides，the off-duty conflict and coverage blind area are avoided. Simulation results show that，compares with CPNSS，the new algorithm can judge redundant nodes more correctly and has better performance on two evaluating indicators:on-duty node number and average coverage degree.It's not sensitive to the influence of the increase of node number and can reduce the redundancy of network effectively.It achieves the purpose of improving the performance of network.

wireless sensor networks，multi-coverage，grid，redundancy

TP393.1

A

1002-0640（2014）11-0080-04

2013-08-05

2013-11-07

国家自然科学基金（60972160）；“十二五”国防科技预研基金；海军工程大学自然科学基金资助项目（201300000446）

刘志坤（1984- ），男，山东寿光人，博士，讲师。研究方向：系统工程、水下自组织网络。