基于链路交点相对位置信息的轻量级覆盖空洞检测算法

韩雨涝，房鼎益

（1.攀枝花学院数学与计算机学院，四川攀枝花 617000；2.西北大学信息科学与技术学院，西安 710127）

0 引言

无线传感器网络（Wireless Sensor Network，WSN）广泛应用于动物保护、森林防火、智慧交通、新型农业和大遗址监测等领域。这些应用大多对网络服务质量（Quality of Service，QoS）要求较高，而无线传感器网络覆盖服务质量是影响网络服务质量重要性能指标之一［1］。大规模传感器网络应用如野外长城遗址状态监测采用节点随机部署，节点对监测区域的不充分感知使得监测区域存在未被感知的区域，该区域称为覆盖空洞（Coverage Hole，CH）［2］。此外，网络运行中节点能量消耗、不合理的休眠调度机制、软硬件故障、受气候（飓风、强降雨等）影响的节点移动和破坏等因素也能产生覆盖空洞。覆盖空洞导致网络不连通，影响路由协议的性能，增加网络数据拥塞，引起覆盖空洞边界节点能量过度消耗，影响数据收集的完整性和连续性，这些都降低了网络服务质量，甚至导致网络不可用。因此应及时对网络中存在的空洞进行检测。

覆盖空洞检测问题是无线传感器网络应用领域热点研究问题之一，得到了国内外学者广泛的关注。文献［3］中提出了一种基于图论的空洞检测算法；但过多的限定条件降低了算法的可用性。文献［4］中通过传感器节点间的协作机制建立局部图，每个节点检测附近关键点实现覆盖空洞的检测和修复；但空洞检测能耗较大，且不一定能实现网络覆盖空洞的完全检测。文献［5］中基于网络连通性检测覆盖空洞，将监测区划分为多个子区域，利用探测信息在网络中传输的距离作为空洞判断的依据，进一步确定空洞的准确区域位置。文献［6］中根据节点剩余能量检测和修复覆盖空洞；但不能实现节点死亡引起的覆盖空洞。文献［7］中提出了一种基于网络同构性的覆盖空洞检测算法，并讨论了空洞检测的准确性和实时性。文献［8］中利用虚拟计算确定边缘节点，以实现覆盖空洞的检测。文献［9］中根据节点位置信息生成Voronoi 图，通过节点到Voronoi 区域边界的距离判断覆盖空洞的位置。上述文献［7-9］对应算法计算复杂度过高，难以大规模应用。文献［10］中提出了一种无需节点位置信息的k重覆盖空洞检测算法，检测过程分为边界节点检测和边界循环检测，通过单重覆盖空洞检测方法的迭代发现所有k重空洞。文献［11］中提出了一种基于置信信息覆盖模型的无线传感器网络空洞检测算法。首先划分监测区域为多个单元，然后计算每个单元的置信信息，最后利用图像技术提取空洞边界的位置。文献［12］中提出了一种基于边界节点的分布式覆盖空洞检测算法（Distributed Coverage Hole Detection algorithm，DCHD），通过节点及其邻居节点的交叉点类型判断边界节点，有效地提高了覆盖空洞的检测效率；但该算法存在节点能量过度消耗的问题，扩大了覆盖空洞区域。文献［13］中提出了一种基于分布式最小极角的覆盖空洞检测算法（Distributed Least Polar Angle algorithm，DLPA），基于边界节点及其邻居节点检测空洞，确定每个空洞位置的边界节点，降低了空洞检测能耗；但该算法不适用于检测复杂空洞。

针对上述空洞检测算法存在通信或计算能耗高、检测时间长、不能实现多种类型空洞联合检测的问题，本文提出了一种基于链路交点相对位置信息的覆盖空洞检测算法（Coverage Hole Detection Algorithm based on Relative Position of Intersections，CHDARPI），主要研究工作包括：

1）定义邻居边界节点间链路的交点相对位置（Relative Position of Intersections，RPI）值，并通过节点未完全覆盖交点数量（Number of Incomplete Coverage Intersections，NICI）值确定空洞检测的发起节点，进而实现连通覆盖空洞的并发检测，有效地提高了空洞检测的速度。

2）将检测消息限定在空洞边界节点内，然后定义节点方向角，并根据节点与其上一跳节点基于NICI 和当前节点的邻居边界节点数量，确定不同场景下检测消息的转发策略，有效地避免了冗余消息传输，降低了网络节点能耗。

1 网络模型

传感器节点在监测区域Z内随机部署构成的无线传感器网络表示为G=（V，E），其中V为节点集合，E为节点间链路集合。每个节点具有唯一的ID，它们的位置信息可通过装载全球定位系统（Global Positioning System，GPS）或已有的传感器网络定位算法［14］获取。节点的感知和通信范围均使用圆盘模型［15］，每个节点感知半径和通信半径同构，分别记为Rs和Rc，假定Rc=2Rs。本文空洞检测算法基于以下定义。

定义1邻居节点。如果监测区域Z内任意节点Ni和Nj满足关系dist(Ni，Nj)≤2Rs，则定义节点Ni和Nj为邻居节点。节点Ni的邻居节点集合表示为：

定义5覆盖空洞类型。如图1 所示空洞A由一组HBN序列对应的空洞圆弧构成，该空洞称为闭合覆盖空洞；如果空洞区域位于HBN序列的外侧，则称为外侧空洞；如图1所示的空洞B是由一组HBN 序列与监测区域的边界线构成，称为栅栏空洞。

图1 覆盖空洞类型Fig.1 Types of coverage holes

定义6顺时针节点序列。给定HBN 序列（Nu，Nm，Nn），当它们的坐标（xu，yu），（xm，ym），（xn，yn）满足如下条件：

则定义该节点序列为顺时针序列。其中：式（7）表示节点Nu，Nm，Nn之间的相邻关系；式（8）表示节点序列为平面上顺时针序列关系。为了便于叙述，将节点Nu的后续节点Nm记为SN（Nu）。

定义7有向链路交点相对位置（RPI）。令Pk为节点Ni和Nj感知圆盘的某个交点。Ni、Nj和Pk的坐标分别为（xi，yi），（xj，yj），（xk，yk）。

2 空洞检测算法CHDARPI设计

2.1 覆盖空洞节点及链路RPI值确定

为了确定网络中HBN 集合H以及链路的RPI 值，首先通过邻居节点发现机制确定每个节点的邻居节点及位置信息，基本思想是：网络中节点向通信范围内的其他节点广播包含自己编号及位置信息的Hello消息，该消息的发送局限于一跳范围之内；邻居节点通过Hello消息获得了发送节点的基本信息；当邻居节点发现周期结束时，在每个节点的邻居信息表中保存了全部邻居的信息。

假定邻居节点Ni和Nj的位置坐标分别为（xi，yi）和（xj，yj），感知圆盘的交点为P1和P2，对应的网络结构如图2所示，连接交点Ni和Nj的线段NiNj的长度记为d。

图2 节点感知圆盘交点Fig.2 Intersections of node sensing disks

交点P1和P2的坐标为：

根据定义2 及推论判断交点的类型。如图2 所示P1为未完全覆盖交点，故节点Ni和Nj为HBN。在此基础上，计算链路的RPI 值。表1 给出了图2 所示节点Ni的邻居信息表结构。其中，邻居节点类型分为完全覆盖节点、未完全覆盖节点和栅栏未完全覆盖节点，依次标记为0、1和2。

表1 邻居信息表Tab.1 Neighbor information table

按照上述方法，确定网络中HBN 集合H以及每条链路的RPI值。

2.2 基于RPI值的覆盖空洞检测

节点发送空洞检测消息（Hole Detection Message，HDM）进行覆盖空洞检测。HDM 消息包含所经路径每个节点的ID及每条链路RPI值。

2.2.1 空洞检测发起节点确定

原则1 将网络中具有最大NICI值的节点作为空洞检测的发起节点。

算法在运行过程中按照式（18）在集合H中选取具有最大NICI值的节点作为空洞检测的发起节点：

选择具有最大NICI 值的节点Ni作为空洞检测的发起节点，是因为该节点具有最多的未完全覆盖交点，是最多覆盖空洞的边界节点，以该节点作为空洞检测的发起节点，有助于覆盖空洞的并发检测，从而降低覆盖空洞的检测时间以及节点能耗。如图3所示节点N13的NICI值最大，具有最多的未完全覆盖交点，是两个覆盖空洞的HBN，以该节点作为覆盖空洞检测的发起节点，能够实现覆盖空洞A和B的并发检测。

图3 基于NICI值的发起节点选择Fig.3 Selection for starting node based on NICI

原则2 当集合H中最大NICI 值的节点有多个时，优先选择其中的栅栏HBN。若集合H中有多个具有相同最大值的栅栏HBN，随机选择即可。

原则2 主要是基于多个节点具有相同NICI 值，虽可并发检测多个覆盖空洞，但栅栏覆盖空洞仅能使用栅栏HBN 作为发起节点进行检测，故为了保证空洞检测的效率，当最大NICI值的节点有多个时，优先选择其中的栅栏HBN。如图4 所示的节点N2和N3有相同的NICI值，此时选择栅栏边界节点N2能并发完成空洞A和B的检测。倘若选择N3则根据本文的空洞检测流程，仅能检测出空洞A，为了检测栅栏覆盖空洞B，需发起下一轮空洞检测，这增加了空洞检测的时间和能耗。

图4 基于栅栏节点的发起节点选择Fig.4 Selection of starting node based on fence nodes

2.2.2 空洞检测过程

为了避免HDM 消息广播引起的节点能量过度消耗，空洞检测的发送节点仅向邻居HBN 发送包含自己ID 的HDM 消息。如图5 所示，空洞检测发起节点N1向N2和N7发送HDM消息。

除了上一跳邻居HBN，转发节点需向其他邻居HBN 发送HDM 消息。在这里定义转发节点Nx的HBN 邻居节点集合为LB（Nx），该集合包含的节点数记为|LB（Nx）|。当收到节点Ni的HDM 消息时，Nx向LB（Nx）中每个节点发送HDM 消息。为了避免冗余数据的传输，Nx对每个邻居节点发送的HDM 消息采取了两种处理模式，最后将处理后的HDM 消息发送到相应的邻居节点。

图5 空洞检测过程Fig.5 Process of hole detection

图6 方向角计算Fig.6 Calculation of direction angle

基于以上方向角的定义，节点Nx转发HDM消息分为以下几种场景：

场景1 转发节点Nx有且仅有一个邻居HBN，即|LB（Nx）|=1，节点Nx向该邻居节点发送包含所经路径每个节点ID 及对应链路RPI 的HDM，即原HDM 信息保持不变，然后将自己的ID 以及信息追加到HDM 消息中，此消息转发模式简称为消息转发模式1，用于检测当前覆盖空洞。如图5所示的节点N7将HDM 消息发送给节点N8，N8仅有一个下一跳邻居HBNN9，此时N8在保持原有HDM 消息的基础上，将自己的ID 以及追加到HDM 消息中，然后将该HDM消息发送给节点N9，用于当前覆盖空洞C的检测。

场景2 转发节点Nx有多个HBN 邻居节点，且其数量大于Nx与其上一跳节点Ni的未完全覆盖交点数量，即：

该场景下NiNx是两个空洞的边界线段，故节点Nx按照消息转发模式1 向这两个邻居节点发送HDM 消息。如图5 所示，=3，节点N5按照模式1 向节点N4和N12发送HDM 消息。N4和N12收到HDM 消息，将它们的ID 及其对应RPI 值追加到HDM 消息的尾部，用于当前覆盖空洞B和C的检测。

某个节点Nk收到两个邻居节点的HDM 消息，分别记为HDM1和HDM2。如果HDM1和HDM2消息的节点序列构成一个环HBN 序列，表示检测到以该环节点序列构成的覆盖空洞。如图5 所示节点N5从两个邻居节点N4和N6分别收到源于节点N1的HDM1和HDM2消息，表示为：

消息HDM1和HDM2中节点序列构成一个环HBN 序列，N1称为该序列的源节点。

为了确定覆盖空洞的类型，将HDM 消息按照定义6 分为顺时针消息和逆时针消息。

在确定HDM1和HDM2分别为逆时针和顺时针消息后，顺时针消息保持不变，逆时针消息中的节点序列按照逆序排列，同时计算新节点序列中每条链路的RPI 值，最终得出逆时针消息HDM1处理后的结果为：

联合HDM1和HDM2中节点ID 和RPI值，构成如下HBN 环节点序列：

当环节点序列中存在两个有序节点Ni和Nj满足式（23）的条件时，该环节点序列构成闭合覆盖空洞，如图5 所示的空洞B和C：

当环节点序列中存在两个有序节点Ni和Nj满足式（24）的条件时，该环节点序列的外侧为外侧覆盖空洞。

当环节点序列中任意两个连续有序节点Ni和Nj满足式（25）的条件时，该环节点序列包围的区域构成闭合覆盖空洞，同时外侧为外侧覆盖空洞。

栅栏空洞检测：当栅栏HBNNi作为空洞检测的发起节点，按照上述流程发送HDM 消息，经历若干HBN 的传输，到达某个栅栏HBNNj，此时HDM 消息经历了一个HBN 序列。如果该节点序列满足定义6 的顺时针序列条件，且该序列存在两个连续节点的链路RPI值为1，则构成栅栏覆盖空洞。如图5所示的栅栏HBNN1通过HDM消息发起空洞检测，经历节点N2，N2按照场景2 中的处理方式转发HDM 消息达到N3，N3是栅栏HBN，且其再无其他邻居HBN。N3的HDM 消息包含如下节点序列：

按照定义6 判断该节点序列为时针序列，且存在链路的RPI为1，故该空洞为栅栏覆盖空洞。

为了避免后续不必要消息传递，降低节点能量开销，在每个覆盖空洞（如Hk）成功检测之后，算法需要更新该空洞链路的RPI 值以及空洞边界节点集合H。Hk中任意节点Ni到Nj间链路的RPI值更新规则为：

按照上述空洞检测过程，可以并发检测到发起节点所在空洞对应的全部连通空洞。对于其他尚未检测的空洞，需在H中重新选择空洞检测的发起节点，按照上述空洞检测过程进行检测，直到集合H为空，表示覆盖空洞检测结束。图7 给出了本文覆盖空洞检测算法的流程。

图7 空洞检测流程Fig.7 Flowchart of hole detection

3 时间复杂度分析

假定网络中传感器节点数量为N，覆盖空洞数量为k，具有不连通覆盖空洞数为m。将算法分解为如下几个阶段，每个阶段的时间复杂度为：

阶段1 邻居节点发现。每个节点向一跳邻居节点发送Hello消息，该阶段时间复杂度为O（N）。

阶段2 链路RPI 计算。计算每对邻居节点间链路的RPI值，该阶段时间复杂度为O（N2）。

阶段3 空洞检测的发起节点确定。该阶段需要比较每个节点的NICI值，对应时间复杂度为O（N）。

阶段4 并发空洞检测。分析可知任意节点Ni最多收到|LNi|个邻居节点的消息，|LNi|＜N。又因HBN数量不超过N，故该阶段最坏情况时间复杂度为O（N2）。

阶段5 判断是否为空洞。每个节点根据HDM消息判断覆盖空洞，该阶段对应的时间复杂度为O（N2）。

阶段6 更新链路RPI 值。该阶段时间复杂度取决于覆盖空洞的数量，对应时间复杂度为O（k）。

阶段7 判断空洞是否检测结束。该阶段时间复杂度取决于非连通覆盖空洞的数量，对应时间复杂度为O（m）。

4 仿真实验与结果分析

4.1 实验设置

使用Matlab 7.0 工具作为仿真实验平台，节点数量依次为100，150，200，250，300，350，400，在400 m×100 m 区域内随机部署，节点感知半径Rs=10 m，通信半径Rc=20 m，发送和接收一个消息能耗均为0.2 J，算法运行过程中除非指定否则覆盖空洞大小和位置不变。采用如下度量评估算法的性能。

1）平均空洞检测时间：检测一个空洞平均所需时间，用总的空洞检测时间除以空洞数量。

2）平均空洞检测能耗：检测一个空洞平均所需能耗，用总的空洞检测能耗除以空洞数量。

4.2 实验结果与分析

4.2.1 空洞数量对算法性能影响

1）平均空洞检测时间。

图8 为不同空洞数量下节点数量与平均空洞检测时间的对比图。可以看出，三种空洞数量下的空洞检测时间随着节点数量的增加而增加，这是因为节点数量的增加，在部署区域面积以及空洞面积固定的情况下，网络节点密度增加，每个空洞将具有更多的HBN，将需要计算更多HBN 的RPI 和NICI值。另外，HDM 传输经历的HBN 也显著增加，增加了并发空洞检测的时间，在空洞数量固定的情况下，最终造成空洞平均检测时间的增加。另外，由图8 也可以发现，在相同节点数量下针对不同空洞数的空洞平均检测时间相差较小，这是因为连通空洞的并发检测使得空洞检测总时间降低，因此在三种不同空洞数量情况下，空洞平均检测时间相差较小，体现了本文算法对连通覆盖空洞并发检测的优势。

2）平均空洞检测能耗。

图9 反映了三种空洞数量下，平均空洞检测能耗随着节点数量的增加而增大，这是因为节点数量增加导致HBN 增多，使得同一规格的覆盖空洞将有更多的节点参与计算以及HDM 消息的传递，造成单个空洞的检测能耗增大，最终导致整个网络节点平均检测能耗的增大。另外，覆盖空洞数量对算法平均检测能耗也有影响。由图9 可以发现，空洞数量越少，空洞检测能耗越低，这是因为当多个覆盖空洞为连通覆盖空洞，部分HBN 可能多次发送HDM 消息，增加了平均覆盖空洞检测的能耗；但从总体趋势来看，覆盖空洞数量对算法的平均检测能耗影响不大，说明了本文算法具有较好的扩展性。

图8 不同空洞数时本文算法节点数量与空洞检测时间的关系Fig.8 Relationship between number of nodes and hole detection time with different hole number for the proposed algorithm

图9 不同空洞数时本文算法节点数量与空洞检测能耗的关系Fig.9 Relationship between number of nodes and energy consumption of hole detection with different hole number for the proposed algorithm

4.2.2 与现有同类算法性能比较

限定覆盖空洞数量为10，从覆盖空洞平均检测时间和检测能耗两方面，比较了CHDARPI 与空洞检测算法DCHD［12］和DLPA［13］的性能。

1）平均空洞检测时间。

图10 给出了三种算法在不同节点数量下的平均覆盖空洞检测时间。相较于算法DLPA 和DCHD，CHDARPI 的平均空洞检测时间分别下降了15.2% 和40.9%，这是因为CHDARPI 使用轻量级的消息广播机制，将HDM 消息仅局限于HBN，且能够实现多个连通覆盖空洞的并发检测，从而降低了覆盖空洞的平均检测时间。

2）平均空洞检测能耗。

图11 反映了三种算法在不同节点数量下的平均覆盖空洞检测能耗。通过与DLPA 和DCHD 对比发现，CHDARPI 的平均空洞检测能耗分别下降了16.7%和28.6%，这是因为CHDARPI 在探测覆盖空洞的过程中：1）将HDM 消息局限于HBN 中传输，缩小了消息传输的范围；2）在并发空洞检测的过程中，根据不同场景对HDM 消息进行了冗余处理，降低了部分节点收发的数据量；3）随着覆盖空洞的不断检测，更新已检测覆盖空洞链路的RPI 值，避免了这部分链路发送冗余HDM消息，减少了网络中HDM消息的数量。

图10 各算法节点数量与空洞检测时间的关系Fig.10 Relationship between number of nodes and hole detection time for different algorithms

图11 各算法节点数量与空洞检测能耗的关系Fig.11 Relationship between the number of nodes and energy consumption of hole detection for different algorithms

5 结语

在无线传感器网络应用中，网络覆盖空洞影响网络性能和服务质量，本文提出了基于链路RPI 的覆盖空洞检测算法（CHDARPI），采用基于NICI 值的空洞检测发起节点选择策略，并根据HDM 消息携带链路的RPI 值判断覆盖空洞及其类型，能够实现多个连通覆盖的并发检测。实验结果验证了CHDARPI 的有效性，与现有同类空洞检测算法相比具有更好的优越性。

本文研究二维平面结构下采用布尔感知模型的无线传感器网络覆盖空洞检测算法，为了进一步提高算法的适用性，下一步工作将研究三维环境下采用概率感知模型的覆盖空洞检测算法。