A Fast Sensor Relocation Algorithm in Wireless Sensor Networks

Authors: Yu-Chen Kuo, Shih-Chieh Lin

Abstract:

Sensor relocation is to repair coverage holes caused by node failures. One way to repair coverage holes is to find redundant nodes to replace faulty nodes. Most researches took a long time to find redundant nodes since they randomly scattered redundant nodes around the sensing field. To record the precise position of sensor nodes, most researches assumed that GPS was installed in sensor nodes. However, high costs and power-consumptions of GPS are heavy burdens for sensor nodes. Thus, we propose a fast sensor relocation algorithm to arrange redundant nodes to form redundant walls without GPS. Redundant walls are constructed in the position where the average distance to each sensor node is the shortest. Redundant walls can guide sensor nodes to find redundant nodes in the minimum time. Simulation results show that our algorithm can find the proper redundant node in the minimum time and reduce the relocation time with low message complexity.

Keywords: Coverage, distributed algorithm, sensor relocation, wireless sensor networks.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1063166

References:

[1] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, A Survey on Sensor Networks, IEEE Communication. Magazine, pp. 102-114, August 2002.
[2] N. Ahmed, S. S. Kanhere and S. Jha, The Holes Problem in Wireless Sensor Networks A Survey, ACM SIGMOBILE Mobile Computing and Communications Review, vol. 9, no. 2, pp. 4-18, April 2005.
[3] A. Ghosh and S. K. Das, Coverage and connectivity issues in wireless sensor networks A survey, Pervasive and Mobile Computing, vol. 4, no. 3, pp. 303-304, 2008.
[4] G. Wang, G. Cao, T. Porta, and W. Zhang, Sensor Relocation in Mobile Sensor Networks, Proceedings of IEEE INFOCOM, March 2005.
[5] X. Li, N. Santoro, and I. Stojmenovic, Mesh-Based Sensor Relocation for Coverage Maintenance in Mobile Sensor Networks, Proceedings of the 4th Int. Conf. on Ubiquitous Intelligence and Computing (UIC) (LNCS 4611), pp. 696-708, 2007.
[6] T. Le, N. Ahmed, S. Jha, Location-free Fault Repair in Hybrid Sensor Networks, Proceedings of the first ACM Int. Conf. Integrated Internet Ad Hoc and Sensor Networks, vol. 138, no. 23, May 2006.
[7] B. Hofmann-Wellenhof, H. Lichtenegger, and J. Collins, Global Positioning System: Theory and Practice, Fourth Edition, Springer Verlag, 1997.
[8] J. Borenstein and Y. Koren, Obstacle Avoidance with Ultrasonic Sensors, IEEE Journal of Robotics and Automation, vol. 4, no. 2, pp. 213-218, 1988.
[9] Q. Li and D. Rus, Global Clock Synchronization in Sensor Networks, IEEE Transactions on Computers, vol. 5, no. 2, February 2006.
[10] B. Sundararaman, U. Buy, and AD. Kshemkalyni, Clock Synchronization for Wireless Sensor Networks: A Survey, Ad-Hoc Networks, vol. 3, no. 3, pp. 281-323, May 2005.
[11] D. Niculescu and B. Nath, Ad Hoc Positioning System (APS) Using AoA, Proceedings of IEEE INFOCOM, 2003.
[12] J. Ash and L. Potter, Sensor network localization via received signal strength measurements with directional antennas, Proceedings of the Forty-Second Annual Allerton Conference on Communication, Control, and Computing, pp. 18611870, September 2004.
[13] N. Patwari, A.O. Hero III, J. Ash, R.L. Moses, S. Kyperountas, and N.S. Correal, Locating the Nodes, IEEE Signal Processing Magazine, vol. 22, no. 4, pp. 5469, July 2005.