一种可自维护的无线传感器网络拓扑控制算法*

王艳丽，侯宪春，王志林，王东方，宋可凡

（佳木斯大学 理学院，黑龙江 佳木斯 154007）

无线传感器网络具有灵活部署的特点，非常适合应用于环境监测、救灾和军事领域[1-2]。无线传感器网络一般具有规模大、自组织、随机部署、环境复杂和节点资源有限等特点，这决定了拓扑控制在无线传感器网络研究中具有十分重要的作用。首先，拓扑控制能够保证网络的覆盖质量和连通质量；其次，拓扑控制能够降低通信干扰，提高 MAC（Media Access Control）协议的效率，为数据融合和路由协议提供良好的拓扑基础；此外，拓扑控制能够提高网络的可靠性和可扩展性等其他性能。因此，对无线传感器网络拓扑控制的研究具有十分重要的意义。特别是当用于温室、救灾等环境监测时，节点的随时开机和关机、无线装置发送功率的变化、无线信道间的相互干扰以及自然故障和遭恶意攻击引起的节点失效、链路故障频繁发生，网络拓扑随时间频繁变化。这就需要设计专门的可生存机制适应网络结构的快速变化，以便通信能正常进行。因此利用拓扑控制技术设计容错的拓扑结构是一个非常重要的网络可生存研究课题[3]。

1 无线传感器网络拓扑控制算法现状

大量无线传感器网络的拓扑控制算法已经被提出，参考文献[4]提出了LNT/LLT和LMN/LMA等基于节点度的算法，该算法给定了节点度的上限和下限需求，周期性动态调整节点的发射功率。参考文献[5]提出了一种分布式计算RNG图的算法。CBTC算法根据节点的方向性信号获得本地信息构造拓扑[6]。参考文献[7]提出了LMA算法，其基本思想是：给定邻居节点个数的上限和下限，动态调整节点的发射功率，使得该节点的度数落在上限和下限内，其指出，如果每个节点的邻居个数在范围内就可以保证整个网络的连通性。参考文献 [8]在LMA的基础上，提出了K-Neigh算法，该算法对邻居个数的范围进行了研究，得到邻居个数K值与网络连通的关系。其进行了大量仿真实验，当节点数n在50～500之间时，当最少邻居个数K为9，则网络以接近概率1连通；假如允许5%左右节点不连通，则最少邻居个数为6。K-Neigh算法仅需距离信息，不需要知道邻居节点的具体位置或方向信息。由于采用广播的形式，分组能够到达其发送半径覆盖范围内的所有邻居节点，采用物理层能量检测技术和距离估计机制即可获得K-Neigh算法所需的距离信息，不需要额外设备的支持。仿真实验表明，K-Neigh算法在能耗和节点度等性能上都有提高。虽然K-Neigh算法简单且实用，但是未考虑拓扑容错问题[9-12]，会使得网络可靠性无法保证，势必带来网络的健壮性下降，不能有效处理节点、无线信道的失效以及多径路由问题，这就需要考虑具有容错特性的拓扑控制问题。

针对上述问题，本文提出了一种可自维护的无线传感器网络拓扑控制算法SMTC（Self-Maintainable Toplogy Control），并对该算法的性能进行了分析。

2 SMTC算法

本文提出的拓扑控制算法SMTC具有自维护功能的容错拓扑结构，该算法由信息收集、拓扑构建、功率设置和拓扑维护4个阶段组成。

2.1 信息收集

在信息收集阶段，每个节点需要收集其最大发送半径范围内的节点信息。利用邻节点发现协议[13]，各节点以最大功率周期性地广播Hello包，Hello包中包括节点ID和位置信息，节点u在收集邻近节点的Hello包后，构建近邻节点列表，同时按照到近邻节点的距离进行排序，在消息通告结束后，每个节点u获得k最近邻节点列表 KN（u）。

2.2 拓扑构建

在信息收集完成后，每个节点u可以建立其最大功率拓扑结构，用一个无向有权图=（V（u），E（u））来表示，其中 V（u）=KN（u）∪{u}。 节点 u 在得到了最大功率拓扑图后，执行Dijkstra算法[14]求出以它为根的最短路径树。为了保证中所有的边都能存在于最终拓扑图中，u分别记录每个中间节点v的儿子节点集合，记为 SNu（v），并通过 Hello 消息将集合 SNu（v）告知节点v，也就是希望u的邻居节点v必须和节点集SNu（v）相连，从而保证了 u到每个节点的路径都存在于最终的拓扑图中。

2.3 功率设置

每个节点以最大发送功率通告其k最近邻节点列表，在收到其他节点发送的近邻节点列表后，每个节点进行有向边双向化处理，更新KN（u）。根据参考文献[15]中的定理2，不经过拓扑边对称化处理仍然能保证网络高概率连通。最后，节点设置其发送功率仅覆盖到KN（u）中距离自己最远的邻节点。

2.4 拓扑维护

在无线传感器网络运行过程中，自然环境和恶意攻击引起的故障和失效会不断发生，因此无线传感器网络必须具备持久抗毁的能力，否则一旦出现少量节点失效，而网络又缺乏恢复的能力，就会降低网络拓扑结构的可靠性，甚至会出现网络拓扑分割的恶劣情况。因此，如何在检测到节点失效时及时有效地重构网络拓扑以恢复网络的抗毁能力，是拓扑维护算法要解决的问题。使拓扑控制算法具备拓扑维护功能的具体过程如下：节点 u在设置功率后，启动 KN（u）中所有邻节点的定时器，每个节点以最大发送功率周期性地发送心跳包，确认连接是否正常。当节点u在收到其他邻节点发送的心跳包后，重置KN（u）中该邻节点的定时器。如果 KN（u）中的某个邻节点的定时器超时，则节点u认为网络出现故障，节点u重新运行k邻居拓扑控制算法的信息收集和功率设置步骤。这样保证了节点重新连接新的k个最近邻节点后，新的拓扑结构仍然是多连通的，维持了网络拓扑的可靠性。

3 仿真与分析

本文对SMTC算法生成的网络拓扑结构的抗毁性进行仿真评估，研究其拓扑结构对于不同打击模式的鲁棒性和脆弱性。实验假设网络初始节点数n=300，它们随机分布在1 000 m×1 000 m的区域中，去除的节点数占原始网络总节点数的比例从0.1变化到0.8。在仿真中考虑了两种情况：一是随机故障，即完全随机地去除网络中的一部分节点；二是蓄意攻击，有意识地去除网络中一部分介数最高的节点。可以用最大连通子图的相对大小和剩余子图的平均大小与失效节点比例的变化关系来度量网络的鲁棒性。图1和图2中数据是500次实验的平均值，两条曲线分别对应SMTC算法以及KNeigh算法[15]生成的拓扑图。

图1（a）和图 1（b）显示了随机故障情况下，最大连通子图的相对大小和剩余子图的平均大小与失效节点比例的关系曲线。

图2（a）和图 2（b）显示了蓄意攻击情况下，最大连通子图的相对大小和剩余子图的平均大小与失效节点比例的关系曲线。

从图1和图2可以看出，当失效节点比例较小时，SMTC算法生成的拓扑图对于随机故障和蓄意攻击都具有极高的鲁棒性。这种对少量节点失效的高度鲁棒性，来自于网络的高连通性。随着失效节点比例的增加，生成的拓扑图对于随机故障和蓄意攻击的容忍能力存在明显的差异。与蓄意攻击相比，网络拓扑对于随机节点故障拓扑结构具有良好的鲁棒性，而除最大连通子图外的其他子图的平均大小的增长要缓慢很多。

针对频繁发生的自然故障和遭恶意攻击引起的无线传感器网络可生存性问题，提出了一种可自维护的拓扑控制算法，该分布式算法能构建并维护容错拓扑结构，且简单、开销小。仿真结果表明，在节点失效时，新的容错拓扑控制算法能够保证网络的抗毁性，使得无线传感器网络具有持续可生存的能力。下一步的工作是研究认知网络的自适应容错拓扑控制技术。

[1]SANTI P.Topology control in wireless ad hoc and sensor networks[J].ACM Comp.Surveys，2005，37（2）：164-194.

[2]石军锋，钟先信，陈帅，等.无线传感器网络结构及特点分析[J].重庆大学学报（自然科学版），2005，28（2）：16-19.

[3]路纲，周明天，牛新征，等.无线网络邻近图综述[J].软件学报，2008，19（4）：888-911.

[4]RAMANATHAN R，ROSALES H R.Topology control of multihop wireless networks using transmit power adjustment[C].Proceedings of IEEE INFOCOM，2002：404-413.

[5]JAROMCZYK J W，TOUSSAINT G T.Relative neighborhood graphs and their relatives[J].Proceedings of the IEEE， 1992，80（9）： 1502-1517.

[6]LI L， HALPERM J Y， BAHL P， et al.Analysis of a cone-based distributed topology control algorithm for wireless multi-hop Networks[C].Proceedings of ACM Symposium on Principles of Distributed Computing（PODC），2001：264-273.

[7]KUVISEH M， KARL H， WOLISZ A， et al.Distributed algorithm for transmission power control in wireless sensor networks[C].IEEE Wireless Communication and Networking WCNC， 2003（1）：558-563.

[8]BLOUGH D， LEONCINI M， RESTA G， et al.The kneigh protocol for symmetrie topology control in ad hoc networks[C].Procedingsofthe 4th ACM International Symposium on Mobile Ad Hoc Networking&Computing，2003：141-152.

[9]时锐，刘宏伟，董剑，等.自组织容错拓扑控制的研究[J].电子学报，2005，3（11）：1978-1982.

[10]Li Xiangyang， Wan Pengjun， Wang Yu， et al.Fault tolerant deployment and topology control in wireless networks[C].Proceedings of Fourth ACM Symposium on Mobile Ad Hoc Networking and Computing（MOB IHOC），2003：117-128.

[11]LI N， HOU J C.FLSS： a fault-tolerant topology control algorithm for wireless networks[C].Proceedings of the 10th Annual International Conference on Mobile Computing and Networking（MOB ICOM），2004： 275-286.

[12]BAHRAMGIRI M，HAJIAGHAYI M，MIRROKNI V S.Fault-tolerant and 3-dimensional distributed topology control algorithms in wireless multi-hop networks[C].Proceedings of 11th International Conference on Computer Comm and Networks （ ICCCN）， 2002： 392-397.

[13]OGIER R，LEWIS M，TEMPLIN F.Topology dissemination based on reverse-path forwarding （TBRPF）[S].MANET Internet Draft，2003.

[14]殷人昆，陶永雷，谢若阳，等.数据结构[M].北京：清华大学出版社，1999.

[15]BLOUGH D M，LEONCINI M，RESTA G，et al.The kneighbors approach to interference bounded and symmetric topology control in ad hoc networks[J].IEEE Transactions on Mobile Computing， 2006，5（9）：1267-1282.