A novel node sinking algorithm for 3D coverage and connectivity in underwater sensor networks

This paper studies the network deployment problem for an underwater sensor network consisting of anchored nodes, which are first randomly deployed onto the ocean surface and can move only along the z-axis direction. The objective is sink these surface nodes to appropriate depths so as to maximize the three dimensional coverage under the premise of ensuring the underwater network connectivity. Our solution consists of three stages: First, based on an efficient three dimensional sphere packing pattern, we select the first batch of sinking nodes on the surface to sink toward the ideal placement locations. The selection exploits a minimum cost perfect matching of a weighted complete bipartite graph to minimize the total deviation distance. Second, we check the connectivity of the sank nodes. If they cannot form a connected network, we propose two algorithms to restore network connectivity for the underwater network. Third, the remaining surface nodes, if any, are further sank to fix coverage holes by those already sank nodes, while guaranteeing their connectivity to the underwater network. Simulation results show that compared with an optimal solution based on exhaustive search, our algorithm can achieve comparable coverage ratio, while ensuring network connectivity with significantly reduced time complexity; compared with other peer algorithms ensuring network connectivity, our algorithm can achieve higher coverage ratio.