Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19] [ 20] [ 21] [ 22] [ 23] [ 24]

¡@

Journal of Information Science and Engineering, Vol. 27 No. 1, pp. 381-392 (January 2011)

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

JYH-HUEI CHANG
Department of Computer Science
National Chiao Tung University
Hsinchu, 300 Taiwan

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.

Keywords: relay sensor, connectivity, algorithm, sensor networks, Delaunay

Full Text (¥þ¤åÀÉ) Retrieve PDF document (201101_24.pdf)

Received December 25, 2008; revised April 7, June 23 & August 13, 2009; accepted August 20, 2009.
Communicated by Tsan-sheng Hsu.