科研之友
微信
新浪微博
Facebook
分享链接
摘要
Connectivity has significance in both of data collection and aggregation for Wireless Sensor Networks (WSNs). Once the connectivity is lost, relay nodes are deployed to build a Steiner Minimal Tree (SMT) such that the inter-component connection is reestablished. In recent years, there has been a growing interest in connectivity restoration problems. In previous works, the deployment area of a WSN is assumed to be flat without obstacles. However, such an assumption is not realistic. In addition, most of the existing strategies chose the representative of each component, which serves as the starting point of relay node deployment during the connectivity restoration, either in a random way or in the shortest-distance based manner. In fact, both ways of representative selection could potentially increase the length of the SMT such that more relay nodes are required. In this paper, a novel connectivity restoration strategy is proposedObstacle-Avoid connectivity restoration strategy based on Straight Skeletons (OASS), which employs both the polygon based representative selection with the presence of obstacles and the straight skeleton based SMT establishment. The OASS is proved to be a 3-opt approximation algorithm with the complexity of O(nlogn), and the approximation ratio can reduce to 332 while it satisfies a certain condition. The theoretical analysis and simulations show that the performance of the OASS is better than other strategies in terms of the relay count and the quality of the established topology (i.e., distances between components, delivery latency and balanced traffic load) as well.
- 出版日期2017-10
- 单位福建师范大学; 福建工程学院
