无线传感器网络中基于几何方法的覆盖洞检测

王旭吾，卢坤

(1.湖北汽车工业学院 科技学院，湖北 十堰442002；2.哈尔滨工程大学，黑龙江 哈尔滨 150001)

无线传感器网络中基于几何方法的覆盖洞检测

王旭吾1，卢坤2

(1.湖北汽车工业学院 科技学院，湖北 十堰442002；2.哈尔滨工程大学，黑龙江 哈尔滨 150001)

提出了一个基于几何方法的覆盖洞检测算法，用以在网络运行过程中找出覆盖洞，仿真结果表明：此算法在能量消耗和检测时间方面优于TBRA算法。

无线传感器网络；覆盖洞；覆盖洞检测

0 引言

近年来，随着微电子控制系统、嵌入式处理器和无线通信技术的快速发展，使得无线传感器网络得到越来越广泛的应用，也成为当前最热门的研究领域之一。无线传感器网络由大量的传感器节点构成，每个传感器节点具有监测、处理或者传送环境信息的功能。无线传感器网络的应用包括栖息地和环境监测、森林火灾检测、战场监视、智能空间和工业诊断等［1］。其中在安全和军事上的应用总是需要目标区域能够被网络完整的覆盖［2］。在无线传感器网络中，由于节点的随机部署、节点能量的过早耗尽以及恶劣环境中部分网络被1破坏，都会导致在网络中形成覆盖洞。覆盖洞的出现会影响网络现有的覆盖率和连通性，从而影响网络的服务质量。因此，在无线传感器网络中检测和修复覆盖洞，是网络服务质量的一个重要组成部分［3］。

无线传感器网络的覆盖可分为3种类型：无限制覆盖，无障碍覆盖，扫描覆盖［4］。在这 3种类型中，无限制覆盖着重于目标区域的覆盖范围最大化，适用于大多数的监控应用。

无线传感器网络中的覆盖问题，通常被称为k-覆盖问题［5］。k-覆盖的意思是感知区域内的每一个点至少被k个传感器覆盖，其中k是一个预定义的非负整数。文献［4］介绍了一种算法，通过计算感知圆域的重叠区域，来分析覆盖问题。WSN应用中更常见的问题涉及一个特殊情况，即k=1。本文中只针对于这一种情况，即感知区域内的每个点至少被一个传感器节点覆盖。

目前大多数覆盖洞检测算法是集中式的，Wang［6］基于现有计算几何中的Voronoi图原理实现了覆盖洞检测，文献［7］中提出了一个无线传感器网络中基于覆盖率的洞检测方法，文献［8］中使用连接信息来识别边界节点，Rao［9］则采用了虚拟坐标的方式实现覆盖洞的测定，这些方法都需要整个网络的概述。然而，随着传感器节点的数目明显变大，这些算法将变得非常费时。因此，对于大型网络，必须采用分布式的洞检测方法，它可以把网络分成更小的子网络，并同时处理这些子网络，从而确定覆盖洞。在分布式算法中，网络中的每一个传感器节点能够进行一些有限的计算，来确定该节点是否是一个洞边界节点。然后用户可以很容易地通过收集洞边界节点的信息，来确定覆盖洞。

1 相关工作

1.1 网络模型

假设无线传感器网络中随机分布有N个传感器节点，目标区域是矩形区域。假设每个传感器节点具有唯一的ID，且具有等同的感知和通信能力，其感知范围和通信范围分别是以r和R为半径的圆域，且R=2r［10］。传感器节点知道自己的地理位置［11］，并向其通信半径范围内的邻居节点周期性的广播其位置信息。节点在收到新的信息后，就会更新其内存里邻居的位置信息。由于节点是随机部署的，假设任意3个节点的感知圆交于一点的概率为0。此外，没有2个节点部署在同一点，且每个节点至少有2个邻居。

同时假设通信模式是二进制的，即传感器节点在通信半径R的圆域内能被检测出，反之不能被检测出；感知模式是二进制的，这意味着在感知半径r圆域内的区域能被覆盖，反之不能被覆盖。

1.2 网络模型

定义1：感知圆与感知圆域 传感器节点可以检测到其感知半径内任一点的信息，那么节点感知半径内的区域就称为传感器的感知圆域，其边界就是感知圆。

定义2：覆盖洞 无线传感器网络中某个连通的区域如果不被任何传感器节点的感知圆域覆盖，那么这个区域就是一个覆盖洞。如图1所示，阴影部分是一个覆盖洞。

定义3：洞边界 假设网络中的覆盖洞都不在监测区域的边界上，那么每一个覆盖洞都与被覆盖区域有分界线，此分界线称之为洞边界。

图1 覆盖洞

定义4：洞边界节点 网络中每个洞边界都是由多条弧线构成，其中每条弧线都属于某个传感器节点的感知圆，那么这些对应的传感器节点就称为洞边界节点。如图2所示，洞H1的洞边界的弧线分别属于节点S1～S9的感知圆，那么节点S1～S9就是H1的洞边界节点。一个节点可以是多个覆盖洞的洞边界节点，如图2所示，节点S6分别是H1和H2的洞边界节点。

定义5：感知圆缺口 每个洞边界节点的感知圆上，属于洞边界的那一段弧未被任何节点的感知圆域覆盖，就称为感知圆缺口，如图2所示，逆时针弧ab就是节点S2的一个感知圆缺口。

定义6：洞边界交点 无线传感器网络中，如果存在2个洞边界节点互为邻居，那么这2个节点的交点至少有1个不被这2个节点之外的第3个节点的感知圆域覆盖，则称这样的交点为洞边界交点。如图2所示，点a、b就是2个洞边界交点。

图2 洞边界节点

由无线传感器网络的覆盖条件可知，如果网络中存在覆盖洞，那么它肯定是由洞边界节点围成的。而围成覆盖洞的洞边界节点肯定存在感知圆缺口。那么，找出网络中所有的感知圆缺口，就能确定网络中的洞边界节点，进而就能判定网络中的覆盖洞。

2 覆盖洞检测算法

2.1 感知圆缺口的判定

在无线传感器网络中，为了保证节点间通信和对监测区域的覆盖，相邻节点间的距离需小于通信半径R。此时，两节点的感知圆会产生2个交点，每个节点的感知圆都有一段弧被另一个节点的感知圆域覆盖。假设每个传感器节点都知道自己和其邻居节点的坐标，那么，通过几何方法，节点可以计算出每个邻居的感知圆域对其感知圆的覆盖，进而就能得到每个节点是否有感知圆缺口。

定义7：覆盖区间 如图3所示，网络中一个节点S1的感知圆被其邻居节点S2的感知圆域覆盖，被覆盖的部分是一条圆弧m，圆弧的2个端点分别为点A，B。不失一般性，假设A，m，B按逆时针方向相连，以节点S1的位置为原点建立直角坐标系。以X轴正方形为0弧度，X轴正方向逆时针到S1A，S1B的最小弧度角分别为a，b，那么区间［a，b］就称为节点S2对节点S1的覆盖区间。

图3 覆盖区间

算法1覆盖区间计算算法

Step1：输入节点S1、S2的位置坐标（x1，y1）、（x2，y2）；

Step2：分别列出以（x1，y1）、（x2，y2）为圆心，r为半径的圆的方程，组成方程组，解出方程组的2组解（p1，q1）、（p2，q2），并计算

如果ni＞0，则

如果ni＜0，则

如果ni=0，那么当mi＞0时，ki=0，mi＜0时，ki=π；

Step4：计算 k4=min（k1，k2），k5=max（k1，k2），如果k4＜k3＜k5，那么a=k4，b=k5；否则，a=k5，b=k4+2π；

Step5：输出［a，b］即为节点 S2对节点 S1的覆盖区间。

对于网络中的某一个节点S0，其邻居分别为S1，S2，...，Sn，这些邻居对S0的覆盖区间分别为［a1，b1］，［a2，b2］，...，［an，bn］。 那么，节点 S0的边界圆上未被这些区间的并集包含的区间就是未被覆盖的区间，这样就确定了感知圆缺口。

算法2感知圆缺口判定算法

Step1：任意选择一个节点作为源节点S0；

夕阳透过玻璃窗，使整个房子变成了暖调子，炉上飘着烟，两老正忙着把拉长的面一片一片地揪下来，扔进飘着肉香的锅里。才让抽着烟，给我们讲述他和张伟的故事。此时此刻我只有一个心愿，回去一定要帮他找到张伟。

Step2：创建节点 S0的邻居节点列表 L=｛S1，S2，...，Sn｝；

Step3：计算邻居Si对S0的覆盖区间 ［ai，bi］，如果存在s，t，使得as≤at且bs≥bt，则把节点St从邻居列表L中删除。L中剩下的节点，bmax=max（bi），若bmax＞bi+2π，则从L中删掉Si。把L中剩下的节点按照对应的ai从小到大排序，得到一个新的列表L1={T1，T2，...，Tm}，其中节点Tj对应的覆盖区间为［aj，bj］；

Step4：依次判断不等式

的正确性，当不等式不成立时，说明存在感知圆缺口［bj，aj+1］，其对应的2个顺时针邻居分别为 Tj，Tj+1。最后判断bm≥a1+2π的正确性，不等式如果不成立，则存在感知圆缺口，当bj＜2π时，缺口为［bj，a1+2π］，否则缺口为［bj-2π，a1］，对应的2个顺时针邻居分别为Tm，T1；

Step5：输出存在感知圆缺口的节点S0，它的感知圆缺口［m1，n1］，［m2，n2］，...［mk，nk］，以及缺口分别对应的成对顺时针邻居节点［R1，T1］，［R2，T2］，...［Rk，Tk］。

2.2 覆盖洞检测算法

通过感知圆缺口判定算法，网络中的节点可以分布式的判定自己是否有感知圆缺口。有感知圆缺口的节点肯定是洞边界节点，找出网络中所有的洞边界节点后，检测覆盖洞的思想如下：以一个洞边界节点为初始节点，对于它的一个感知圆缺口对应的成对顺时针邻居，后面的那个邻居就是下一跳洞边界节点。然后再找这个节点的成对顺时针邻居，保证前一个邻居是上一跳的洞边界节点，那么后一个邻居就是下一跳洞边界节点。重复这个过程，直到回到初始节点。

Step1：通过算法2确定网络中所有的洞边界节点，放入列表 L={S1，S2，...，Sn}，假设节点 Si最多只有3个感知圆缺口，对应的成对顺时针邻居分别为［Ria，Tia］，［Rib，Tib］，［Ric，Tic］，缺口数量不到3个时按顺序出现；

Step2：创建覆盖洞列表L1，初始为空，R为当前的洞边界节点，S为当前的顺时针成对邻居的后一个。令R=S1并将S1放入L1，T=T1a；

Step3：找出Si=T，将Si放入L1。找出Rij=R，则令T=Tij，R=Si；

Step4：重复Step3直至T=S1。此时列表L1中的元素就是顺时针围成一个覆盖洞的洞边界节点。

重复利用算法3，当所有的洞边界节点都被放入覆盖洞列表，就检测出了网络中所有的覆盖洞。

3 仿真结果

为了评估所提出覆盖洞检测算法的性能，利用Matlab7.0进行了仿真实验。在200m×200m的区域内，部署600个节点，感知半径r为5 m，通信半径R为10 m，覆盖洞数量分别为1，2，3，4，5，6，7，8时，与文献［8］中的TBRA算法在数据包开销和仿真时间方面进行了比较。实验结果如图4所示，结果表明，当覆盖洞的数量较多时，此算法在能量消耗和检测时间方面都优于TBRA算法。

图4 不同算法的实验结果比较

4 结论

提出了一个基于几何方法的覆盖洞检测算法，以在网络运行过程中找出覆盖洞。首先通过几何方法计算节点的邻居对其的覆盖区间，识别有感知圆缺口的节点，从而可以确定网络中所有的洞边界节点，再找出所有洞边界节点的相邻情况，就可以检测出网络中的覆盖洞。

［1］I.Akyildiz，W.Su，Y.Sankarasubramaniam，E.Cayirci. Wireless sensor networks:a survey［J］.Computer Networks，2002，39（4）：393-422.

［2］Meguerdichian.S，Koushanfar.F，Potkonjak.M，Srivastava.M.B.Coverage problems in wireless ad-hoc sensor networks［C］.Proc.INFOCOM 2003，2003：1380-1387.

［3］Martínez.J，Garcí.A，Corredor.I，López.L，Hernández. V，Dasilva.A.QoS in wireless sensor networks:survey and approach［C］.Proc.IEEE/ACM EATIS 2007，2007：1-8.

［4］Huang.C，Tseng.Y.The coverage problem in a wireless sensor network［C］.Proc.WSNA′03，2003：115-121.

［5］Habib.M.A，and Sajal.K.D.On computing conditional fault-tolerance measures for k-covered wireless sensor networks［C］.Proc.MSWiM 2006，2006：309-316.

［6］Wang.G，Cao.G，and La.Porta.T.Movement-assisted sensor deployment.Proceedings of the IEEE Conference on Computer Communications［C］.Hong Kong，China，2004：2469-2479.

［7］Shakkottai S，Srikant R and Shroff N.Unreliable sensor grids:Coverage，connectivity and diameter［C］.Proceedings of the IEEE Conference on Computer Communications.San Francisco，USA，2003：1073-1083.

［8］Y.Wang，J.Gao and J.S.B.Mitchell.Boundary Recognition in Sensor Networks by Topological Methods［C］. Proc.of MobiCom 2006，2006：122-133.

［9］Rao.A，Ratnasamy.S，Papadimitriou.C，Shenker.S，Stoica.I.Geographic routing without location information［C］.Proceedings ofthe 9th AnnualInternational Conference on Mobile Computing and Networking，SanDiego，CA，USA，2003：96-108.

［10］苏瀚，汪芸.传感器网络中无需地理信息的空洞填补算法［J］.计算机学报，2009，32（10）：158-170.

［11］B.Karp，H.T.Kung.Greedy Perimeter Stateless Routing for Wireless Networks ［C］.Proc.ACM/IEEE International Conference on Mobile Computing and Networking［C］.USA，Aug，2000:243-254.

Coverage Hole Detection in Wireless Sensor Networks Based on Geometric Method

Wang Xuwu1,Lu Kun2
（1.Science and Technology College,Hubei University of Automotive Technology,Shiyan 442002,China; 2.Harbin Engineering University,Harbin 150001,China）

A coverage hole detection algorithm based on the geometric method was presented to identify the coverage holes in network running.The simulation results show that the proposed algorithm is superior to TBRA algorithm in terms of the energy consumption and detection time.

wireless sensor networks;coverage holes;coverage holes detection

TP212；TP393

A

1008－5483（2014）01－0059－04

2014-02-26

王旭吾（1984-），女，湖北武汉人，硕士，主要从事应用数学方面的研究。

10.3969/j.issn.1008-5483.2014.01.0015