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

发布时间：2018-10-15 17:41

【摘要】：在恶劣环境下无线传感器网络的节点和通信链路常常会失效,致使网络被分割为很多分离的分区,因此通过布置尽量少的中继节点实现高健壮性的连通恢复对于维持网络的正常运作必不可少.对于一个被分割的无线传感器网络,找到相应的位置布置最少中继节点恢复连通是一个NP难题,在实际应用中只能采用启发式算法.文中提出了一种新的基于四边形斯坦纳树的算法来恢复网络连通.此算法首先探测出各分区并确定各分区的代表节点及其位置,然后寻找合适的四边形连接分割的网络分区,确定这些四边形的斯坦纳点;对无法用四边形连接的各连接部分用三角形斯坦纳树或最小生成树的方法连接;最后沿着斯坦纳树的边在相应位置布置中继节点,实现网络连通的恢复.大量的仿真实验表明文中提出的方法能够减少所需中继节点的数量,恢复后的拓扑结构中节点的连通度更高,容错性更好.
[Abstract]:Nodes and communication links in wireless sensor networks often fail in harsh environments, resulting in the network being divided into many separate partitions. Therefore, it is essential to maintain the normal operation of the network by deploying as few relay nodes as possible to achieve high robust connectivity recovery. For a segmented wireless sensor network, it is a NP problem to find the least relay node in the corresponding location, and only a heuristic algorithm can be used in practical application. In this paper, a new algorithm based on quadrilateral Steiner tree is proposed to restore network connectivity. The algorithm first detects each partition and determines the representative node and its location of each partition, then finds suitable quadrilateral network partition to determine the Steiner points of these quadrilateral. The connection parts that can not be connected by quadrilateral are connected by the method of triangle Steiner tree or minimum spanning tree. Finally the relaying nodes are arranged along the edge of the Steiner tree to realize the restoration of network connectivity. A large number of simulation experiments show that the proposed method can reduce the number of relay nodes needed, and the nodes in the restored topology have higher connectivity and better fault tolerance.
【作者单位】：华中科技大学计算机科学与技术学院;湖北科技学院计算机科学与技术学院;
【基金】：国家自然科学基金(60933012) 国家教育部博士点基金(20110142110062)资助~~
【分类号】：TP212.9;TN929.5

【共引文献】