An Efficient Relay Sensor Placing Algorithm for Connectivity in Wireless Sensor Networks

Abstract

Randomly deployed sensor networks often make initial communication gaps inside the deployed area, even in an extremely high-density network. How to add relay sensors such that the underlying graph is connected and the number of relay sensors added is minimized is an important problem in wireless sensor networks. This paper presents an Efficient Relay Sensor Placing Algorithm (ERSPA) for solving such a problem. Compared with the minimum spanning tree algorithm and the greedy algorithm, ERSPA achieves better performance in terms of the number of relay sensors added. Simulation results show that the average number of relay sensors added by the minimal spanning tree algorithm is approximately two times that of the ERSPA algorithm.