基于四边形斯坦纳树的无线传感器网络连通恢复  

Quadrilateral Steiner Tree Based Connectivity Restoration for Wireless Sensor Networks

作　　者：陈洪生[1,2] 石柯[1] 

机构地区：[1]华中科技大学计算机科学与技术学院,武汉430074 [2]湖北科技学院计算机科学与技术学院,湖北咸宁437005

出　　处：《计算机学报》2014年第2期457-469,共13页Chinese Journal of Computers

基　　金：国家自然科学基金(60933012);国家教育部博士点基金(20110142110062)资助~~

摘　　要：在恶劣环境下无线传感器网络的节点和通信链路常常会失效,致使网络被分割为很多分离的分区,因此通过布置尽量少的中继节点实现高健壮性的连通恢复对于维持网络的正常运作必不可少.对于一个被分割的无线传感器网络,找到相应的位置布置最少中继节点恢复连通是一个NP难题,在实际应用中只能采用启发式算法.文中提出了一种新的基于四边形斯坦纳树的算法来恢复网络连通.此算法首先探测出各分区并确定各分区的代表节点及其位置,然后寻找合适的四边形连接分割的网络分区,确定这些四边形的斯坦纳点;对无法用四边形连接的各连接部分用三角形斯坦纳树或最小生成树的方法连接;最后沿着斯坦纳树的边在相应位置布置中继节点,实现网络连通的恢复.大量的仿真实验表明文中提出的方法能够减少所需中继节点的数量,恢复后的拓扑结构中节点的连通度更高,容错性更好.In the harsh environment, wireless sensor networks damage that causes many nodes/links to fail simultaneously and the network to get splitted into multiple disjoint partitions. Therefore, linking the separated partitions by placing the least number of relay nodes to re-establish a strongly connected network topology is necessary to maintain the functional network operations. However, the problem of finding the minimum relay nodes is NP-hard and hence heuristics methods are preferred. In this paper, we present a novel quadrilat- eral Steiner tree algorithm to address this problem. First, the disjointed partitions are detected and their locations are determined. Then the appropriate quadrilaterals are selected to connect the separated partitions and the Steiner nodes of these quadrilaterals are found. The disioint islands which are not connected by these selected quadrilaterals are connected with the triangle Steiner tree or minimum spanning tree method. Finally, relay nodes are placed to the appropriate position according to the edges of Steiner tree to restore network connectivity. Extensive simulation experiments demonstrate the beneficial aspects of the resulting topology with respect to number of relaying nodes, degree of connectivity and fault resilience.

关 键 词：无线传感器网络 连通恢复 四边形斯坦纳树 启发式算法 拓扑结构 

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