Connectivity Recovery Based on Boundary Nodes and Spatial Triangle Fermat Points for Three-Dimensional Wireless Sensor Networks

In recent years, wireless sensor networks have been widely used, especially in three-dimensional environments such as underwater and mountain environments. However, in harsh environments, wireless sensor networks may be damaged and split into many isolated islands. Therefore, restoring network connectivity to transmit data effectively in a timely manner is particularly important. However, the problem of finding the minimum relay nodes is NP-hard, so heuristics methods are preferred. This paper presents a novel connectivity recovery strategy based on boundary nodes and spatial triangle Fermat points for three-dimensional wireless sensor networks. The isolated islands are represented as the boundary nodes, and the connectivity recovery problem is modeled as a graph connectivity problem. Three heuristics algorithms-the variant Kruskal algorithm, the variant Prim algorithm, and the spatial triangle Fermat point algorithm-are proposed to solve this problem. The variant Kruskal algorithm and the variant Prim algorithm connect the isolated islands by constructing the minimum spanning tree to link all the boundary nodes and placing relay nodes along the edges of this tree. We derive an accurate formula to determine the coordinates of spatial triangle Fermat points. Based on this formula, the spatial triangle Fermat point algorithm constructs a Steiner tree to restore network connectivity. Extensive simulation experiments demonstrate that our proposed algorithms perform better than the existing algorithm.