面向节点失效问题的无线传感器网络拓扑自愈算法  

Topology self-cure algorithm aiming at node failure problem in wireless sensor networks

作　　者：刘林峰[1] 吴家皋[1,2] 邹志强[1] 陈行[2] 钮麟[2] 

机构地区：[1]南京邮电大学计算机学院,南京210003 [2]东南大学计算机网络和信息集成教育部重点实验室,南京210096

出　　处：《东南大学学报（自然科学版）》2009年第4期695-699,共5页Journal of Southeast University：Natural Science Edition

基　　金：国家自然科学基金重大研究计划资助项目(90604003);国家自然科学基金资助项目(40801149);国家高技术研究发展计划(863计划)资助项目(2009AA12Z219)

摘　　要：为了解决节点失效问题,建立了无线传感器网络模型,对节点失效问题进行了形式化描述和分析,并结合传感器网络拓扑需求归纳出拓扑愈合的约束:网络连通、路径代价降低和度约束.该问题属于NP-hard问题,因此设计了一种近似的拓扑愈合算法TCS-CA,通过恢复失效节点的单跳邻居间可达性来实现拓扑的自愈.该算法包括3个执行阶段:单跳邻居的连通恢复、子集合并和全局连通恢复,依次执行这些阶段后能够逐步愈合拓扑.仿真实验结果表明,当选取合适的β,λ等参数时TCS-CA算法不仅能恢复网络拓扑的连通性,还能有效地延长WSN生命期,与TCS算法相比最高可获得约13%的生命期增率.In order to solve the node failure problem, a model of wireless sensor networks is constructed firstly. Then the node failure problem is described formally and analyzed. Some ideal characteristics （wireless sensor network connectivity, path cost decrease, degree constraint） have been concluded for topology. Because this problem belongs to NP-hard problem, an approximate topology self-cure algorithm called TCS-CA is proposed. The main idea of the TCS-CA is to recover the connectivity of nodes which are one-hop neighbors of the failure node. The TCS-CA is composed of three phases： connectivity recovery of one-hop neighbors, sub-set incorporation, and connectivity recovery of WSN. After the executions of the phases, the WSN topology can be recovered gradually. The simulation experiments show that a well-constructed topology and effectively prolonged network lifetime can be acquired when some parameters such as β and λ are chosen properly. Compared with the TCS, the TCS-CA can obtain 13% lifetime increment at most.

关 键 词：无线传感器网络 节点失效问题 自愈算法 拓扑控制 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]