基于拓扑的WSNs边界节点检测算法设计*

张 姿，黄廷磊，吴拱星

（1．中国科学院 电子学研究所，北京 100190;2．桂林电子科技大学计算机科学与工程学院，广西桂林 541004）

0 引言

实际应用中，大量传感器部署后，无线传感器网络（WSNs）经常处于无人值守的状态［1～3］。因此，电池的损耗、动物的损坏、偶然事件的发生造成部分节点失效，便形成了空洞，影响网络的连通性。为了尽量减少空洞对网络连通的影响，准确识别空洞的边界有助于保持数据业务流、防止数据损失，避免额外的能量消耗，防止空洞的扩展，并确定替代的通信路径。因此，边界检测算法的研究具有非常重要的意义。

目前，在WSNs边界节点检测算法研究方面许多学者已经进行了大量的研究工作，并且提出了许多有效的算法。根据算法使用的核心技术，可将目前的边界识别算法分为基于地理位置信息的算法、基于统计信息的算法和基于拓扑信息的算法［4，5］。本文主要研究基于拓扑信息的边界节点检测算法。

基于拓扑信息的边界节点检测算法利用网络的拓扑连接信息寻找隐藏的网络几何信息，从而确定网络节点的分布。Ghrist R等人在文献［6］提出了一种基于拓扑信息的边界识别算法，算法利用节点同源且方向不可延续检测网络的洞。该种算法是比较有代表性的一种识别方法，但也是集中式算法，不大符合传感器网络的应用发展。Saukh Olga等人在文献［7］提出一种新的基于拓扑信息的算法，作者提供的算法没有过多的条件限制，具有比较普遍的应用价值。该算法通过寻找被取名为“flower”和“flower”的组合结构来检测网络的边界节点。算法的执行严格地依赖于“flower”结构。但是在某些特定应用场合，“flower”不总是存在的。针对实际应用，Funke S等人在文献［8］提出了一种非常有代表性算法，后续很多基于拓扑信息的边界节点检测算法都受该算法启发。该算法对节点度的要求比较高;为了获得比较好的检测效果，网络的平均节点度要求至少是15。Wang Yue等人在文献［9］提出了一种比较准确的检测算法，并且作者在论文中给出了算法可行性的理论证明。本文将文献［9］提出的算法称之为边界节点检测（BRSN-TM）算法。

1 BRSN-TM算法

1）构建最短路径树

在网络中选择一个节点作为最短路径树的根节点，命名为R节点，然后利用贪婪算法在网络中构建以R为根节点的最短路径树。

2）识别算法的“cut”节点对

网络中洞的分布信息隐藏在最短路径树的结构上，这个结构具体地说就是最短路径树上的“cut”节点对。“cut”节点对是一对邻居节点，这对邻居节点的在最短路径树上的共同祖先节点明显比其他邻居点的共同祖先节点远。

3）确定环

确定一个环，这个环包围网络中的洞。网络的一个包围洞的环是由“cut”2个节点到达共同祖先的2条最短路径，加上“cut”2个节点的连线组成。算法确定的这个环可以当成网络的内边界，只是这个内边界比较粗糙，但是已经基本具备内边界的特性。

4）确定网络外边界和网络内边界

确定的环不会紧贴网络的内边界，通过对网络节点泛洪，重新求精网络的内外边界，从而达到准确识别网络的内外边界的目的。

2 改进的BRSN-TM算法

针对BRSN-TM算法构造最短路径树的通信量大，本文从降低通信量与提高边界节点检测的准确性2个方面来考虑，提出了改进的 BRSN-TM（ABRSN-TM）算法。ABRSNTM算法引入网络纬度线取代最短路径树用于检测网络中洞结构;针对网络中洞的个数比较多时，BRSN-TM算法构造包围所有洞的环非常复杂，ABRSN-TM采用构造多个环分别包围网络中的单洞;针对BRSN-TM洪泛识别具有边界特性的节点时通信量大，并且算法需要节点间的同步，ABRSN-TM算法设计了一种利用环上节点动态替换方法，把环转换为网络的边界。经过以上几点的改进，降低了算法交换数据量，并且提高边界节点检测的准确性与时效性。

1）选取算法领导节点

算法领导节点的作用是作为边界节点检测算法发起节点并且领导网络所有节点同步于算法，算法的开始将选择一个节点作为网络边界节点检测算法的领导节点，本文采用竞争选取领导节点。

2）确定网络的信标节点

这一步算法在网络中寻找2个信标节点，确定2个信标节点应具有2个特征:第一，两节点要起到信标节点的作用;第二，两节点应该位于网络中的某一方向相反的两端。所以，充当信标节点的节点应该尽量跨越网络中的大部分特性区域。这里的特性主要指网络中洞的分布。通过领导节点L来寻找具有以上特性的2个信标节点。首先，以领导节点L为信标节点，在网络中利用贪婪算法确定网络中每一节点到达L节点的最短跳数;然后，选取到达L节点跳数最大的节点为信标节点，标号为N;同样地以节点N为信标节点，寻找到达节点N最远的节点，标号为S。从上述的方法可知，节点N和节点S满足信标节点的2个要求。

3）划分网络的纬度线

在完成网络的信标节点选取后，网络中所有的节点同时已获取了自身节点到2个信标节点的跳数坐标。在网络中划分一些等距线，类似于地球上的纬度线，因此，本文把这些等距线称为纬度线。纬度线为到达两信标节点的距离比值恒定的节点的集合。连续的纬度线定义为纬度线段，每段纬度线段上选取一个头节点，每个头节点代表纬度线段向领导节点发送一条注册消息。网络纬度线条数设定与纬度线间的间隔有关。如果纬度线间的宽度比较大，有可能使网络中比较小的洞未能被检测出来。但是如果网络中纬度线间的宽度划分太小，使网络的纬度线比较密集，那么，将增加网络的通信压力。如果希望比较准确地设置网络中纬度线的条数，可以先对洞的大小进行定义。然后利用洞的大小计算纬度线的条数，从而确定节点到达两信标节点的预设距离比值。网络中的纬度线的数量可用公式（1）计算

式中TH为纬度线加密系数，可取0，1，2等值，用于适当增加网络中的纬度线条数;Dh为洞的直径定义为网络中洞的边界节点中相隔距离最大的2个节点之间的跳数;Dn为网络中任意节点间距离最远的两节点的跳数距离定义为网络的规模。

4）确定网络中洞的分布情况

改进的边界节点检测算法的核心思想是通过网络中洞的分布情况来寻找网络中包围洞的环。如果网络中存在洞，那么，纬度线将被洞分割成多段;如果纬度线所跨越的地理区域不存在洞，那么，纬度线将是连续的。把连续的整段纬度线称为纬度线段。每段纬度线段上选取一个头节点，每个头节点代表纬度线段向领导节点发送一条注册消息。

节点ID值最小的节点被选为头节点，每个头节点发出包含自身ID和纬度线号的注册信息给领导节点。领导节点接收每个头节点的注册信息，并且对信息中的纬度线号进行计数。如果出现重复的纬度线标示符，那么说明该纬度线被网络中的洞切断。

5）构造包围洞的环

根据Jordan曲线理论，二维平面内一条封闭的曲线把平面分成2部分:曲线内部和曲线外部。确定了网络中洞的大概位置，该算法构造一个环，这个环包围网络中特定的洞。这里所提及的环就是网络中由节点的连接组成的一条封闭的二维曲线。这里设想构造出一个环把网络分成两部分:环内部为包围特定洞的部分和环外为不包含洞的部分。步骤（4）已经确定洞在纬度线3和纬度线7之间，并且也在纬度线4，5，6的各自的2个头节点对之间。那么，利用最短路径算法，使网络中这8个头节点找到各自邻近的2个邻近头节点的最短路径，这些最短路径连接就形成了一个包围洞的环。网络中包围洞的环如图1所示。包围空洞的环命名为S，组成S的节点集合为{s1，s2，s3，…，sn}。

图1 网络包含洞的环Fig 1 Ring of network containing hole

6）环的求精

组成S的节点集合{s1，s2，s3，…，sn}，它们的一跳邻居节点集合分别是

Hops1（1），Hops2（1），Hops3（1），…，Hopsn（1）。

随意选取S上的一个节点，假设s1，转发Hops1（1）给它的所有1跳邻接节点。每个邻接节点找到自己1跳的邻接节点中，同时也是s1的1跳邻接节点的集合。总结如下

任何a∈Hops1（1）:LinkedTOHopS1（1）（a）=

式中LinkedTOHopS1（1）（a）是指在节点s1的1跳邻接表中同时也是节点a的1跳邻接节点的集合。为了演示这个算法，设已识别包围空洞的环为S3，图2所示。本文以s31为例。

图2 包含空洞的环转换成网络内界的过程Fig 2 Process of ring containing hole transform into inner boundary of network

表1显示了算法的运算过程。因为s31，s32，s3j都属于环S3的节点，根据其邻居关系推出s41，s42，s4p是属于新环S4;s21，s22是属于新环S2。将S环上的其他节点依次按照上述步骤，就将形成完整的S4，S2。然后，将形成的S4，S2;按照上述动态方法，形成新的环;在新形成的环，按照迭代方法，直到找到网络的内外边界，如图3所示。

表1 s31的1跳邻居节点之间的相互通信的链接Tab 1 Mutual communication links between the 1-hop neighbours of s31

图3 网络的内外边界Fig 3 Inner boundary and outer boundary of network

3 仿真

为了验证改进的基于拓扑方法的边界节点检测算法的性能，用NS2进行了仿真实验［10］。在软件的环境中设置各种不同的参数验证算法的可行性，为了评估ABRSN-TM算法的优化性能，在统一的平台上对 ABRSN-TM算法和BRSN-TM算法进行一系列的仿真，然后对比实验结果。实验过程中，网络的节点数、网络区域、节点通信范围、洞的类型、洞的数量等参数在未加说明的情况下采用如下初始值。节点数为3500;网络区域形状为正方形;传感器区域规模为1000 m×1000m;通信范围为30m;平均节点度为9;洞的形状为类圆。

1）节点度对算法检测准确率的影响

在这组实验中，通过调整网络中节点的数目，使网络的节点度在6，9，12，15变化。另外，在实验之前，根据边界节点的定义对网络节点的位置进行标定，标定的边界节点作为模板用于对算法识别效果的衡量标准。在不同节点度的环境下执行ABRSN-TM和BRSN-TM算法各50次，取得算法的检测准确率并取平均值。

如图4，节点度为6时，ABRSN-TM算法和BRSN-TM算法边界节点识别的准确率都比较低。特别在BRSN-TM算法中，由于网络稀疏，从而致使稀疏区域的一些非边界的节点被误选为边界节点。实验结果显示了随着节点度提高，边界节点检测算法的识别准确率不断地提高。从仿真结果可知，无论节点度高或者低，ABRSN-TM算法在识别准确率上都有5%的提高。因此，在网络低节点度的情况下，ABRSN-TM算法拥有比BRSN-TM算法更高的识别准确率。

图4 不同节点度识别准确率Fig 4 Recognition accuracy of different nodes of degree

2）洞的个数对通信量的影响

在这组实验中，使网络中洞的个数由1个变化到8个，其他参数使用默认值。然后在不同空洞数量下执行ABRSN-TM和BRSN-TM算法各50次，得出算法的识别边界节点的通信量并计算平均值。图5空洞的个数比较少时，BRSN-TM算法的通信量是比较少的。但是当网络的洞的个数大于3时，BRSN-TM算法的通信量就超过了ABRSN-TM算法的通信量。所以，当网络的洞比较少时，改进的算法是未能降低BRSN-TM算法的通信量。

图5 不同算法的通信量Fig 5 Communication traffic of different algorithm

4 结束语

本文针对BRSN-TM算法构造最短路径树的通信量大，从降低通信量和提高边界节点检测的准确性2个方面来考虑，在ABRSN-TM算法中引入网络纬度线取代最短路径树用于检测网络中的洞结构;采用构造多个环分别包围网络中的单洞;设计了一种利用环上节点动态替换方法，把环转换为网络的边界。实验验证:ABRSN-TM算法在网络的低节点度的情况下，能获得比较高的检测准确率，并且在网络中洞的个数比较多的情况下，算法的通信量和速度性能得到了提高。

［1］ Simek Bocek M，Moravek J．Optimization of boundary recognition algorithms for wireless sensor network applications［C］∥34th International Conference on Digital Object Identifier，Telecommunications and Signal Processing（TSP），2011:189 －194．

［2］ Khan I M，Jabeur N，Zeadally S．Hop-based approach for holes and boundary detection in wireless sensor networks［J］．The Institution of Engineering and Technology，2012，2（4）:328 －337．

［3］ 王新民，肖亚辉，顾晓婕．基于混合优化的移动传感器网络反隐身研究［J］．传感技术学报，2012，25（1）:94 －98．

［4］ Whitehouse K，Culler D．A robustness analysis of multi-hop ranging-based localization approximations［J］．Proc of 5th International Conference on Information Processing in Sensor Networks，2006:317－325．

［5］ Khan Mokhtar I，Merabti H．A new self-detection scheme for sensor network boundary recognition［C］∥34th IEEE Int'l Conference on Local Computer Networks，LCN 2009，2009:241 －244．

［6］ Ghrist R，Muhammad A．Coverage and hole-detection in sensor networks via homology［C］∥Proc 4th Internat Sympos on Information Processing in Sensor Networks，2005:254 －260．

［7］ Saukh Olga，Sauter Robert，Gauger Matthias，et al．On Boundary Recognition without Location Information in Wireless Sensor Networks［C］∥2008 International Conference on Information Processing in Sensor Networks，2008:207 －215．

［8］ Funke S，Klein C．Hole detection or:How much geometry hides in connectivityc［C］∥Proc 22nd ACM Sympos on Computational Geometry，2006:377 －385．

［9］ Wang Y，Gao J，Mitchell J S B．Boundary recognition in sensor networks by topological methods［C］∥The 12th Annual International Conference on Mobile Computing and Networking，MobiCom’06，Los angeles，USA，2006:122 －133．

［10］黄化吉，冯穗力．NS网络模拟和协议仿真［M］．北京:人民邮电出版社，2010．