无线传感器网络边界节点识别研究进展综述

赵利辉，刘文怡，张　斌，谭秋林

(中北大学 a.电子测试技术国家重点实验室;

b.仪器科学与动态测试教育部重点实验室,山西 太原 030051)



无线传感器网络边界节点识别研究进展综述

赵利辉a，b，刘文怡a，b，张斌a，谭秋林a，b

(中北大学a.电子测试技术国家重点实验室;

b.仪器科学与动态测试教育部重点实验室,山西 太原 030051)

边界节点的识别是无线传感器网络研究中的一个基本问题，是识别覆盖空洞的关键，也是优化网络覆盖的基础和数据可靠传输的保障。在综述边界节点识别算法的基础上，提出了基于节点可用信息和技术策略的算法分类方法，在归纳各类算法技术特点的基础上对比分析了不同算法的优点及存在的问题，并对未来的研究方向进行了总结与展望。

无线传感器网络；边界节点；覆盖空洞；综述

无线传感器网络(WSN)是由大量成本低、体积小整合了传感、无线通信、数据存储和处理等单元的微型传感器节点，以相互协作的方式构成的一种无线多跳自组织型网络。WSN可以通过飞机抛洒或炮射等方式部署于危险区域中执行各种监测任务，在战场监测、环境监测、结构安全监测、危化品监测、森林火灾预防和火山喷发等领域展现出了极大的潜在应用价值，也成为当前WSN研究中的热点问题。与传统网络相比，WSN的独特性在于：1)WSN生存周期受节点能量的限制；2)节点的通信距离、存储空间和计算能力受节点能量和结构的限制；3)节点结构、部署模式和应用环境使其容易形成覆盖空洞。而前面所提及的如战场监测等应用都要求WSN有良好的网络覆盖和可靠的网络服务质量(QualityofService，QoS)，以便能对监测区域进行及时和有效的监测。然而覆盖空洞的出现严重影响网络的QoS，其不仅导致WSN出现监测盲区，还会引发数据融合故障，网络负载失衡，加剧节点工作负荷等一系列衍生问题，直接威胁了WSN的生命周期。

许多研究者为解决覆盖空洞问题进行了不懈的努力，提出很多基于边界节点识别的覆盖空洞检测识别算法，本文针对WSN边界节点识别问题的最新研究进展进行了综述，根据不同研究方法所采用的节点信息类型和技术策略对算法进行了分类、对比、分析和总结，对其存在的问题、优缺点进行了归纳和总结，最后探讨了未来研究的方向。

1　模型、定义与标准

为方便描述，本节给出文中涉及到的网络模型、定义和评价标准。

1.1网络模型

1.2定义

覆盖空洞：本文的覆盖空洞是指WSN监测区域中不能被任一节点的传感区域覆盖的监测盲区。

边界节点：本文的边界节点包含两类，一类是位于WSN内部且处于覆盖空洞边缘的节点，另一类则是指位于WSN最外层边缘能够标识监测区域轮廓的节点。

当前节点：本文特指那些初始化完成准备执行边界节点识别算法的节点，表示为S。

邻居集：给定一个节点si，如果有节点sj满足式(1)，则称sj为si的k跳邻居节点，所有k跳邻居节点的集合称为si的k跳邻居集，表示为Nk(si)，1跳邻居集也可表示为Nk(si)，di,j表示节点间的欧氏距离

(k-1)×rc≤di,j≤k×rc(k=1,2，3，…,n)

(1)

1.3算法评估标准

边界节点是识别覆盖空洞和优化网络覆盖的关键问题，也可以提升路由效率，确保数据聚合，延长网络生命周期。因而，合理的评估标准对于准确评价边界节点识别算法的性能至关重要。本文提出的评估标准如下：

1) 识别精度，是衡量算法性能的首要标准，也是识别覆盖空洞的关键。识别精度常受网络节点配置、节点可用信息和系统模型的限制。

2) 节点度，是评估算法优劣的重要标准。其限定了算法的适用领域，直接影响了算法的识别精度和网络部署成本。

3) 节点信息类型，不同的边界节点识别方案对网络资源的需求也不同，本文的节点信息类型包括网络中节点的位置信息、节点度统计信息和拓扑结构信息等，是划分算法类型的标准之一。

4) 能量有效性，是WSN中节点提供监测、通信和数据传输等服务所消耗的能量。其直接关系到WSN的生存周期，是导致节点失效的直接原因和衡量算法优劣的重要标准。

5) 通信开销，是指WSN的节点在数据收集、融合和消息传递过程中其无线通信模块的能量消耗，本文的通信开销评估模型为文献[1-2]所述模型。

6) 算法复杂度，是衡量算法优劣的一个重要尺度，算法复杂度包括时间复杂度、消息复杂度和空间复杂度等。

7) “闭环”策略，即判断当前结点的邻居节点能否构造一个围绕当前结点的闭合环路来识别该节点是否为边界节点的策略，如果“闭环”存在则节点为内部节点，否则为边界节点。是一种常用的边界节点识别方法，也是本文划分算法类型的标准之一。

8) 算法模型，是依据算法执行过程中是否依赖一个或多个中心节点，将边界节点识别方法分为集中式算法和分布式算法两类。

2　边界节点识别方案

边界节点的检测与识别是覆盖空洞识别和修补的关键，也与网络覆盖、拓扑控制、节能通信、路由协议设计、入侵检测和目标定位等应用密切相关。为了全面认识边界节点识别问题，总结当前的研究成果，本文根据目前研究中采用的节点信息类型、算法模型和技术策略对边界节点识别方案进行了归纳、分析、对比和总结。

2.1边界节点识别方法分类

根据研究中采用的节点信息的不同，可将边界节点识别方法分为基于计算几何、基于统计方法和基于拓扑方法的边界节点识别方法3类。根据算法模型的不同将边界节点识别方法分为集中式算法和分布式算法。根据边界节点识别算法是否采用“闭环”策略可将其分类为基于闭环的方法和基于非闭环的方法。图 1给出了边界节点的识别方法分类图。

图1　算法分类

2.2基于节点信息的边界节点识别方法

2.2.1基于计算几何的边界节点识别算法

基于计算几何方法的识别算法的共同特点是假设节点的位置(或距离)信息已知，利用典型的几何工具分析节点间的几何特性实现边界节点的识别。其中的代表性算法包括：

1)周界搜索算法

Martincic等在文献[3]中提出一种称为“周界搜索”的分布式边界节点识别算法，简称为DPD(本文中周界是指节点传感范围的外围边界)。DPD是一种分布式算法(见图2)，可被WSN中的任意一个节点自主执行。假设节点正在执行DPD，则DPD首先计算N(S)和N2(S)在以S为圆心的坐标系中的绝对角并按绝对角升序排列所有邻居节点，然后以绝对角最小的邻居节点为起始节点利用深度搜索算法查找是否存在一个“闭环”能将节点包围，如果这样的“闭环”存在，则节点为内部节点，否则为边界节点。

图2　DPD算法示意图

Khedr等在文献[4]中也提出了基于“周界搜索”的边界节点识别算法，简称为PD。与DPD不同的是其采用了Barycentric坐标技术，且不需要计算每个邻居节点相对于节点S的绝对角。PD将节点分布区域分为4类即4个不同的象区Qi(i=1,2,3,4)，然后通过检测Qi之间的连通性判断节点S是否为边界节点，即：如果有两个象区为空则S为边界节点；如果3个或全部象区不为空则检测象区间的连通性；如果各个象区相互连通，节点S为内部节点，否则为边界节点。

Huang等在文献[5]中提出一种基于节点传感区域周界覆盖扫描的算法用于检测WSN中节点的覆盖问题。陈和孙等[6]在PD和文献[5]的基础上提出一种“高效的边缘检测算法”，简称EBD。EBD首先以S为圆心生成笛卡尔坐标系，并判断处于该坐标系中的N(S)是否能将∂C(S)完全覆盖，如果可以，则S为内部节点，否则为边界节点。执行过程中，如果N(S)仅处于以S为圆心的笛卡尔坐标系的两个象区中，则S为边界节点，如图3a所示；否则计算节点S与各邻居节点的传感区域的交点确认其∂C(S)的覆盖情况，如果其能被邻居节点的传感区域完全覆盖，S为内部节点，如图3b所示。

图3　PD、EBD周界扫描算法原理

优点：基于周界搜索的算法简单高效，可应用于各种规模的网络，节点正确识别率高、错误率和漏检率低；仿真结果表明算法通信开销小，能量消耗少；在节点位置较精确的情况下，算法鲁棒性好，扩展性好，如Huang等的算法已扩展到三维领域。

缺点：需配置定位或测距设备，锚节点能量消耗高，上述算法均没有评估同质节点网络中锚节点因素的影响和环境干扰带来的位置误差的影响。

2)三角形搜索算法

三角形搜索算法是对Deogun提出的好邻居搜索算法[7](ChooseGoodNeighbor，CGN)及其改进算法的总称，CGN是一种分布式算法，可以被WSN网络中任意一个节点执行。CGN同周界搜索算法一样采用“闭环”的思想，差异体现在：1)CGN的“闭环”是三角形而其他周界搜索算法是多边形结构；2)CGN通过利用海伦公式(式(2))分别计算图4a中△ABC，△ABP，△ACP和△BCP的面积，然后通过检测他们之间是否符合式(3)判定节点是否为边界节点，而周界搜索算法则是通过检测被检测节点的邻居节点能否构成一个“闭环”来检测该节点是否为边界节点。如图4b所示，CGN在判断节点P是否为边界节点时首先选择节点P的最近邻居做为三角形顶点A，然后以dP,A为半径搜索顶点B，B需满足条件：1)B∈N(P)；2)B∈N(A)；3)在所有节点A的一跳邻居节点中距离dA,B最大。然后以条件min(|dA,C-dB,C|∧dP,C)选择顶点C，以符合条件min(dA,D-dB,C|)，max(dD,C)和dD,C>dD,P∧dD,C>dP,C的节点为D，在构成的三角形中，如果P位于△ABC或△ABD内，则P为内部节点，否则为边界节点。

图4　三角形搜索算法示意图

为了简化CGN构建三角形的过程，Simek等在文献[8]提出一种BRC算法，该方法与CGN的差异在于三角形顶点C的选择过程，即BRC将P的一跳邻居除顶点A和B以外的节点作为一个集合CSet，如图4c所示，CSet={C1,C2,…,C10}，如果CSet中的任一节点能够和节点A与B构成的△ABC满足式(3),则节点P为内部节点，否则为边界节点

(2)

S△ABC=S△ABP+S△BCP+S△ACP

(3)

优点：在周界搜索算法的基础上，CGN和BRC简化了“闭环”的构造，节点自我识别过程所需信息少且精确。

缺点：仿真结果表明，节点位置不规则的情况下并不能构建如图 4a所示的规则三角形，尤其在三角形为钝角且其相对的边长较大的情况下该算法常常失效。

3) 三角形特性搜索算法

Ma等在文献[9]中基于节点间的三角形几何特性提出一种分布式边界节点识别算法，简称为CDCH。其具体执行过程为：

(1)令N=N(S)∪N2(S)，其中表示一跳和二跳邻居的合集。

(2)计算中每个节点在以S为圆心的笛卡尔坐标系中的绝对角并升序排列。

(3)抽取中的一对相邻节点A和B与S组成三角形△SAB，并计算△SAB外接圆的半径。

(4)如果△SAB及R满足任意下述条件则S为边界节点：

①A，B∈N(S),△SAB为钝角三角形且R≤Rs；

②A，B∈N2(S),△SAB为锐角三角形且R>Rs；

③A,B∈N2(S)且∠ASB≥90°；

④如果A∈N(S)∧B∈N2(S)或相反情况，△SAB为锐角三角形且R>Rs；

⑤如果A∈N(S)∧B∈N2(S)或相反情况且∠ASB≥90°；

⑥△SAB外接圆圆心不能被任何节点的传感区域覆盖。虽然CDCH算法需要分析多种三角形特性，但其一个明显的优点是解决了多边形“闭环”不能识别三角形覆盖空洞的问题。

此外，Li等基于Delaunay三角形[10]的空圆特性在文献[11]提出一种边界节点识别算法，简称为CHB。该算法一个显著的优点是无须像CDCH一样需要枚举三角形外接圆的各种特性，能够以一种统一且容易的模式识别出边界节点，而且能够识别出位于三角形覆盖空洞边缘的节点。

优点：算法充分发掘了三角形的几何特性，相比其他算法，CDCH和CHB能识别出位于三角形覆盖空洞的边界节点，解决了其他算法无法识别三角形覆盖空洞的问题，提高了识别精度。

缺点：要求节点位置信息或距离信息，需要为节点配置定位或距离测量装置如GPS等；WSN部署成本高，节点体积大，易受环境因素干扰，且上述算法均没有评估地形干扰、定位或测量误差对识别精度的影响；配置定位装置的节点能量消耗大，影响其生存周期。

2.2.2基于统计的方法

Fekete在文献[12]中利用处于WSN边缘节点的平均连通度低于网络内部节点的平均连通度的特点,提出一种基于节点连通度统计信息的边界节点识别方法，简称NTR。该方法通过经验值预设一个节点度阈值α，节点度大于α的节点为内部节点，否则为边界节点。此后，Fekete等又在文献[13]中提出一种称为“限制压力中心”的算法，简称为RSC算法，其数学模型为式(4)。RSC通过统计在WSN内各节点到目标节点的最短路径经过节点v的次数获得节点v的限制压力度，而整个网络的限制压力度阈值获取方法和节点的判别方法与NTR相同

(4)

式中：σst(v)表示WSN中经过节点v的最短路径。

优点：不依赖节点的位置信息，因而无需装配定位装置；降低了部署成本，不受环境因素干扰。

缺点：该算法要求极高的网络密度，要求网络节点平均连通度达到100或以上；在稀疏网络中不具可行性，识别效果极差。

2.2.3基于拓扑的方法

基于拓扑的边界节点识别方法也被称为基于连接信息的边界节点识别方法，其优点是不依赖节点位置信息，对节点平均连通度要求低，这使其在稀疏网络中也能取得较高的识别精度[14]。因而该方法在许多应用尤其是易受环境干扰的应用中赢得了广泛的关注。

1)基于轮廓的边界节点识别方法

Funke等认为WSN可以按节点位置划分为层层环绕的轮廓，如图5a所示，而边界节点显然不会存在于一个闭合的轮廓上，基于这种思想,Funke等设计了一种基于轮廓构建的边界节点识别算法简称为DHD[15]。DHD在构建轮廓时首先选择WSN的最大独立集节点作为种子节点集合，然后选取最大独立集中的每一个节点作为种子节点(如图5所示)，并收集该节点的各跳邻居信息，并为不同跳的邻居节点构建环绕种子节点的轮廓，如果轮廓是闭合的则该层轮廓上不存在边界节点，否则该层轮廓的两个端点即为边界节点，如图5b中的节点v3和v4。

图5　DHD边界节点识别方法示意图

优点：不依赖节点位置信息，在大型网络中的识别结果较优。

缺点：该算法是一种集中和分布式融合的算法，在同质网络中会由于种子节点能量消耗大而引起其失效导致覆盖空洞的产生且通信开销大；每一个种子节点都要建立数量不等的分层轮廓，因而识别过程时间消耗过大；鲁棒性差，稀疏和稠密部署的网络中识别错误率都比较高且在不同网络环境下识别精度变化起伏大；无法识别三角形等较小的覆盖空洞。

2) 改进的轮廓检测算法

针对DHD算法存在的缺点，Chu和Ssu改进了“轮廓”的构建过程，同时基于单纯复形理论提出一种分布式的边界节点识别算法简称为DBD[16]。如图6a所示，S为待执行DBD的节点，虚线框内节点为S的2跳节点，DBD判断节点S是否为边界节点的过程是：选取节点t作为起始节点开始构建S的2跳“轮廓”，图中不同形状的节点分别代表节点t的不同跳邻居，t节点依次在其不同跳邻居中选取距其跳距离最近的节点，如图6b所示，连接这些节点如图6c所示，显然节点S的轮廓不闭合，因而节点S为边界节点。如果此时假设节点S的“轮廓”是闭合的，则DBD开始对该“轮廓”区域进行分解，根据单纯复形理论，三角面是最小不可分割的面，如果“轮廓”区域能够完全分解为由2跳和1跳邻居节点构成的三角面，则该节点是内部节点，否则为边界节点。

优点：同DHD相比，该算法仅需被检测节点的3跳邻居信息，大幅度减少了通信开销；优化了“轮廓”的构建过程；完全分布式的算法设计可以使WSN中的每个节点都可以自主判断是否为边界节点。

缺点：“轮廓”三角面分解过程复杂度较高；无法识别三角形等较小的覆盖空洞；特定环境下错误识别率高。

图6　DBD边界节点识别方法示意图

3) 基于割点和最近公共祖先的算法

Wang等在文献[14]中提出一种基于拓扑的边界识别算法简称为BRT。基于最短路径树、割点对和最近公共祖先思想，能够直接识别覆盖空洞和网络外层边界。具体过程是：BRT首先选取网络中任意一节点(位于网络边缘的节点优先)作为根节点,利用泛洪算法生成网络的最短路径树T。接着，在T中寻找具有最近公共祖先的割点对，如图 7所示，节点p和q是具有共同公共祖先r的割点对，其中dp,r和dq,r需大于指定阈值δ，以p到r，q到r的路径和边pq构成一个粗糙内部边界R，并通过不断寻找p到r，q到r中间节点间的最短路径对R进行“修剪”获得精确的覆盖空洞边界，最后通过寻找距离R最远的“极值”点作为WSN的外层边界节点。

图7　BRT算法示意图

优点：算法在节点平均连通度较低(≥7)的情况下也取得了较好的识别精度；能够较精确地识别WSN覆盖空洞和外层边界，并能识别凹、凸和多孔的覆盖空洞。

缺点：根节点的选取对识别结果影响较大；无法识别三角形等较小的覆盖空洞；泛洪算法的大量使用加重了整个网络的通信开销，增加了节点的能量消耗，影响了网络的生命周期。

4) 结构搜索法

Kröller在文献[17]中利用QUDG模型提出一种称为DBR的算法，DBR算法通过搜索WSN中的模式即“flower”结构来识别内部节点，通过不断扩张内部节点从而达到识别边界节点的目的。需要注意的是,DBR要求网络平均节点度要大于20，这是“flower”结构存在的必要条件。为克服DBR对节点连通度要求高的问题，Sauth等在文献[18]中改进了“模式”的结构，新的算法简称为OBR，然而由于“模式”的限制，在稀疏网络中仍存在较高的错误率和漏检率。

优点：该算法不需要考虑节点部署模型和位置信息。

缺点：该算法节点连通度要求高；无法识别三角形等较小的覆盖空洞；不适用于稀疏和小规模网络。

5) 基于跳信息的边界节点识别方法

在所述及的基于拓扑方法的边界节点识别算法中，通信开销过大是一个普遍存在的问题，针对该问题Khan等提出一种基于节点之间跳距离的边界节点识别算法简称为HBH[19]，通过该算法WSN中的每一个节点都能自主判断是否为边界节点。该算法仍然采用了“闭环”思想作为节点判别自己是否为边界节点的依据。区别在于其“闭环”路径的构造方法通信量小。HBH构建“闭环”路径的具体方法是，以被检测节点的任意一个2跳邻居节点作为起始节点，如图 8所示，通过按序持续搜索“扩展节点”避免了大量的广播带来的通信代价过高的问题降低了网络的通信成本，延长了网络生命周期。

优点：该算法为分布式算法，WSN中每个节点能自动识别自己是否为边界节点；相比其他拓扑算法，在邻居信息收集和“闭环”路径构建过程都减少了通信开销。

缺点：在稀疏网络中存在错误节点识别率高的问题；无法识别三角形等较小的覆盖空洞；没有给出明确的覆盖空洞节点聚类方法。

图8　HBH算法示意图

本节基于节点的可用信息对当前主要的边界节点

识别算法进行了分类、总结和对比，结果如表1所示。从中可以看出各类算法都有各自的优点，但也存在一些亟待改进的地方。基于计算几何的方法虽然识别精度高,算法设计简单，但是由于要求配置定位设备，不仅加大了部署成本,而且增加了能量消耗。基于统计的识别方法不需要节点知道其位置信息，但是要求节点部署必须服从一定的概率分布模型，这提高了部署的难度，而且其极高的节点连通度要求也限制了其实际应用范围。基于拓扑的方法不需要节点位置信息，而且在较低节点连通度环境下也取得了很好的识别结果，但其问题是通信开销过大。

表1边界节点识别方法对比分析

检测方法核心思想优点缺点涉及文献计算几何方法WSN每个节点都知道其位置信息,利用节点间的几何特性识别WSN中的边界节点1)识别方法简单,计算容易2)仅需1跳邻居即可识别1)需配备GPS等定位装置,部署成本高2)容易受环境干扰3)能量消耗大[3-4,6-9,11]统计方法假定WSN中的节点服从某种概率分布,且WSN内部节点的节点度明显高于边界节点1)不需要配备GPS2)不需要节点位置信息1)节点连通度要求高2)节点必须服从统一概率分布3)要求网络密度大[12-13]拓扑方法利用节点之间的连接信息和网络拓扑特性实现边界节点的识别1)不需要假设节点服从某种概率分布2)不需要节点位置信息3)节点度要求低1)通信开销大2)稀疏网络识别精度低3)至少需要2跳邻居[14-19]

2.3基于计算模型的分类方法

2.3.1集中式边界节点识别算法

集中式算法是指边界节点识别算法的执行主要依赖于一个或多个具有核心功能的节点，除这些核心节点外网络中的其他节点不能判断自己是否为边界节点。文献[15]中，网络中的节点并不能独立判断自己是否为边界节点，而是依赖于网络的最大独立集成员节点。此外，Grist和Muhammed在文献[20]中也提出一种基于代数拓扑空间理论的集中式边界节点识别算法，但是其复杂度过高。

优点：集中式能够优化网络的全局设计，使协议设计最优化。

缺点：由于WSN特殊的结构属性，其有限的存储和数据处理能力并不适合数据的集中收集和处理，尤其是在介质均匀的WSN；由于集中式算法过于依赖中心节点，当中心节点出现故障时很容易导致整个网络功能的中断和失效；集中式算法需要将数据聚合到中心节点执行，因而会增大通信开销，导致节点能量消耗增大，进而影响整个网络的生存周期。

2.3.2分布式算法

分布式边界节点识别算法是指WSN中的多个节点通过相互协作实现边界节点的检测与识别，通常表现为WSN中的每一个节点通过收集其跳邻居信息，然后通过基于计算几何、统计或拓扑等方法检测自己是否为边界节点。如文献[3-4，6-9，11-14，16-19]中提出的算法都属于分布式算法。

优点：分布式算法可以依赖WSN的局部信息实现边界节点的识别，网络中部分节点失效不会影响整个网络的功能。

缺点：相较集中式算法，分布式算法设计要复杂。

2.4基于“闭环” 的分类方法

结合前文所述，“闭环”策略是边界节点识别算法中使用频率极高的技术，本文据此将边界节点识别算法分为基于“闭环”的边界节点识别算法，如文献[3-4，6-8，15-16，19]和非“闭环”的边界节点识别算法，如文献[9，11-14，17-18，20]。

优点：基于“闭环”的算法设计简单、复杂度低，尤其基于几何结构的“闭环”算法仅需1跳邻居节点即可识别被检测节点是否为边界节点，在不同的应用场景中均取得较好的识别效果。

缺点：基于“闭环”的边界节点识别算法虽然设计简单，但在实际实施中也面临巨大的挑战，尤其是基于拓扑方法的“闭环”算法，特定条件下是一个完全NP难问题，如图9a和图9b所示，节点的一跳邻居节点和构成了一个“闭环”，但算法由于极难区分图9a和图9b两种情况而将识别为内部节点，造成错误识别。

图9　闭环错误识别原理图

3　边界节点识别算法比较及存在的问题分析

3.1边界节点识别算法比较

表2从识别精度、节点度、算法模型、节点信息、能量有效性、通信开销、复杂度、传感和通信模型及是否采用闭环策略9个维度对本文综述的算法进行了对比和总结，从中可以全面认识当前主要算法的差异和特点。

3.2存在的问题

虽然学者们针对不同的应用场景提出多种类型的边界节点识别算法，但通过前文的分析可以发现其仍然存在以下问题，亟待解决。

1)传感和通信模型对边界节点识别的影响。本文所述的边界节点识别算法中，传感和通信模型基本遵循圆盘覆盖模型，然而实际应用中WSN节点受其应用环境(如地形阻挡)的影响，其传感和通信模型很难服从理想的圆盘模型，虽然文献[14]强调不需要完全服从圆盘模型，但其并未作出具体验证和评估。因而，这是未来研究中一个必须面对的问题。

表2边界节点识别算法比较

算法识别精度节点度算法模型节点信息类型能量有效性通信开销复杂度传感和通信模型闭环策略DPDHighLowDistributedGeographicalMediumLowLowUDGYESPDHighLowDistributedGeographicalLowLowLowUDGYESEBDHighLowDistributedGeographicalLowLowLowUDGYESCGNHighLowDistributedGeographicalMediumLowLowUDGYESBRCHighLowDistributedGeographicalMediumLowLowUDGYESCDCHHighLowDistributedGeographicalMediumLowLowUDGNOCHBHighLowDistributedGeographicalMediumLowLowUDGNONTRLowStrongDistributedStatisticalMediumHighLowUDGNORSCLowStrongDistributedStatisticalMediumHighLowUDGNODHDHighMediumCentralizedTopologicalMediumMediumLowUDGYESDBDHighMediumDistributedTopologicalMediumMediumLowUDGYESBRTHighLowDistributedTopologicalLowHighMediumNon-UDGNODBRMediumHighDistributedTopologicalLowHighHighQUDGNOOBRMediumMediumDistributedTopologicalLowHighHighd-QUDGNOHBHHighMediumDistributedTopologicalLowLowMediumUDGYESCHDMediumMediumCentralizedTopologicalLowHighHighUDGNO

2)应用领域问题。目前边界节点识别的研究中，WSN部署环境主要假设为一个在二维平面环境，然而WSN已被大量应用于建筑物、水下和地下等三维环境中，针对三维环境的边界节点识别技术目前研究较少，仅在文献[21]等极少数文献中针对该问题进行了讨论，因而三维环境中的边界节点识别是一个必须解决的问题。

3)动态拓扑和移动性问题。综述的文献中，大多是基于节点静止的环境进行算法设计的，然而实际的无线传感器网络拓扑结构是一个动态变化的过程，这是由其结构特性决定的，同时为了弥补WSN随机部署的缺陷在一些应用中通常采用移动节点对WSN中覆盖空洞进行修补，然而在目前的文献中大多数没有对网络结构的动态变化进行考虑和优化设计，这也是实际应用必须解决的一个主要问题。

4)基于边界节点识别的覆盖空洞识别和修补技术。边界节点一个主要的应用是为覆盖空洞的识别提供支撑，然而综述的文献中除文献[14]外，其他文献均未给出明确的覆盖空洞识别算法。而且在一个大型WSN中可能存在多个覆盖空洞，因而如何识别复杂环境下的覆盖空洞并对其进行修补是一个亟待解决的问题。

4　小结

本文综述了无线传感器网络边界节点识别技术的研究现状，通过节点识别过程中采用的节点可用信息、算法模型和技术策略对当前主要的研究方法进行了分类，并描述了各算法的技术路线和适用范围，对各算法的优、缺点进行了对比、分析和总结。最后，本文对当前该领域亟待解决的问题进行了探讨，对未来的研究方向进行了展望。

[1]SMARAGDAKISG，MATTAI，BESTAVROSA.SEP：astableelectionprotocolforclusteredheterogeneouswirelesssensornetworks[EB/OL].[2016-01-10].https://www.researchgate.net/publication/228885310_SEP_A_Stable_Election_Protocol_for_Clustered_Heterogeneous_Wireless_Sensor_Networks.

[2]HEINZELMANWB，CHANDRAKASANAP，BALAKRISHNANH.Anapplication-specificprotocolarchitectureforwirelessmicrosensornetworks[J].IEEEtransactionsonwirelesscommunications，2002，1(4)：660-670.

[3]MARTINCICF，SCHWIEBERTL.Distributedperimeterdetectioninwirelesssensornetworks[EB/OL].[2016-1-10].http://newslab.cs.wayne.edu/perimeter.pdf.

[4]KHEDRAM，OSAMYW，AGRAWALDP.Perimeterdiscoveryinwirelesssensornetworks[J].Journalofparallelanddistributedcomputing，2009，69(11)：922-929.

[5]HUANGCF，TSENGYC.Thecoverageprobleminawirelesssensornetwork[J].Mobilenetworksandapplications，2005，10(4)：519-528.

[6]陈成涛，孙燕. 高效的无线传感器网络边缘检测算法[J].计算机工程与设计，2011，32(9)：2984-2988.

[7]DEOGUNJS，DASS，HAMZAHS，etal.Analgorithmforboundarydiscoveryinwirelesssensornetworks[C]//InHighPerformanceComputing-HiPC2005.[S.l.]：SpringerBerlinHeidelberg，2005：343-352.

[8]SIMEKM，MORAVEKP，KOMOSNYD，etal.Distributedrecognitionofreferencenodesforwirelesssensornetworklocalization[J].Radioengineering，2012，21(1)：89-98.

[9]MAHC，KUMARSP，CHENYW.Computationalgeometrybaseddistributedcoverageholedetectionprotocolforthewirelesssensornetworks[J].Journalofnetworkandcomputerapplications，2011，34(5)：1743-1756.

[10]LIXY，CALINESCUG，WANPJ，etal.Localizeddelaunaytriangulationwithapplicationinadhocwirelessnetworks[J].IEEEtransactionsonparallelanddistributedsystems，2003，14(10)：1035-1047.

[11]LIW，ZHANGW.Coverageholeandboundarynodesdetectioninwirelesssensornetworks[J].Journalofnetworkandcomputerapplications，2015，48：35-43.

[12]FEKETESP，KROLLERA，PFISTERERD，etal.Neighborhood-basedtopologyrecognitioninsensornetworks[C]//AlgorithmicAspectsofWirelessSensorNetworks. [S.l.]：Springer，2004：123-136.

[13]FEKETESP，KAUFMANNM，KROLLERA，etal.Anewapproachforboundaryrecognitioningeometricsensornetworks[C]//Proc. 17thCanadianConferenceonComputationalGeometry. [S.l.]：arXiv，2005：82-85.

[14]WANGY，GAOJ，MITCHELLJS.Boundaryrecognitioninsensornetworksbytopologicalmethods[C]//Proc. 12thAnnualInternationalConferenceonMobileComputingandNetworking. [S.l.]：ACM，2006：122-133.

[15]FUNKES.Topologicalholedetectioninwirelesssensornetworksanditsapplications[C]//Proc. 2005JointWorkshoponFoundationsofMobileComputing.NewYork，NY，USA：ACM，2005：44-53.

[16]CHUWC，SSUKF.Location-freeboundarydetectioninmobilewirelesssensornetworkswithadistributedapproach[J].Computernetworks，2014，70(10)：96-112.

[17]KRÖLLERA，FEKETESP，PFISTERERD，etal.Deterministicboundaryrecognitionandtopologyextractionforlargesensornetworks[C]//Proc.SeventeenthAnnualACM-SIAMSymposiumonDiscreteAlgorithm. [S.l.]：SocietyforIndustrialandAppliedMathematics，2006：1000-1009.

[18]SAUKHO，SAUTERR，GAUGERM，etal.Onboundaryrecognitionwithoutlocationinformationinwirelesssensornetworks[J].ACMtransactionsonsensornetworks(TOSN)，2010，6(3)：1-35.

[19]KHANIM，JABEURN，ZEADALLYS，etal.Hop-basedapproachforholesandboundarydetectioninwirelesssensornetworks[J].IETwirelesssensorsystems，2012，2(4)：328-337.

[20]GHRISTR，MUHAMMADA.Coverageandhole-detectioninsensornetworksviahomology[C]//Proc. 4thinternationalsymposiumonInformationprocessinginsensornetworks. [S.l.]：IEEE，2005：254-260.

[21]ZHOUH，WUH，JINM.Arobustboundarydetectionalgorithmbasedonconnectivityonlyfor3Dwirelesssensornetworks[C]//Proc.INFOCOM.[S.l.]：IEEE，2012：1602-1610.

赵利辉(1979— )，博士生，研究方向为无线传感器网络；

刘文怡(1970— )，教授，博士生导师，主要研究方向为测试测量技术及仪器、无线传感器等；

张斌(1979— )，博士生，研究方向为无线传感器网络；

谭秋林(1979— )，教授，博士生导师，主要研究方向为红外气体传感技术、恶劣环境下无线无源传感技术。

责任编辑：许盈

Surveyonboundarynoderecognitioninwirelesssensornetwork

ZHAOLihuia,b,LIUWenyia,b,ZHANGBina,TANQiulina,b

(a. National Key Laboratory for Electronic Measurement Technology；b. Key Laboratory of Instrumentation Science & Dynamic Measurement of Ministry of Education, North University of China, Taiyuan 030051, China)

Identifyingboundarynodesisfundamentalintheresearchofwirelesssensornetworks.Itplaysacriticalroleinidentifyingcoverageholes,laysafoundationforoptimizingnetworkcoverageandguaranteesdatatransmission.Inthispaper,thestatequoofthealgorithmsofidentifyingboundarynodesarereviewed,methodsofcategorizingthealgorithmsbasedontheavailableinformationofnodesandtherelevantstrategiesoftechnologyarepresented,andtheadvantagesanddisadvantagesofthedifferentalgorithmsarecomparativelyanalyzed.Furthermore,theupcomingworkisproposed.

wirelesssensornetworks;boundarynode;coverageholes;survey

TN915

ADOI：10.16280/j.videoe.2016.08.012

国家自然科学基金项目(51275491)；国家自然科学基金重点项目(61471324)

2016-02-25

文献引用格式：赵利辉，刘文怡，张斌，等. 无线传感器网络边界节点识别研究进展综述[J].电视技术，2016，40(8)：62-70.

ZHAOLH，LIUWY，ZHANGB，etal.Surveyonboundarynoderecognitioninwirelesssensornetwork[J].Videoengineering，2016，40(8)：62-70.