Optimal Deployment with Self-Healing Movement Algo-rithm for Particular Region in Wireless Sensor Network

Fan ZHU, Hongli LIU, Shugang LIU, Jie ZHAN

.

DOI: 10.4236/wsn.2009.13028                

Abstract

Optimizing deployment of sensors with self-healing ability is an efficient way to solve the problems of cov-erage, connectivity and the dead nodes in WSNs. This work discusses the particular relationship between the monitoring range and the communication range, and proposes an optimal deployment with self-healing movement algorithm for closed or semi-closed area with irregular shape, which can not only satisfy both coverage and connectivity by using as few nodes as possible, but also compensate the failure of nodes by mobility in WSNs. We compute the maximum efficient range of several neighbor sensors based on the dif-ferent relationships between monitoring range and communication range with consideration of the complex boundary or obstacles in the region, and combine it with the Euclidean Minimum Spanning Tree (EMST) algorithm to ensure the coverage and communication of Region of Interest (ROI). Besides, we calculate the location of dead nodes by Geometry Algorithm, and move the higher priority nodes to replace them by an-other Improved Virtual Force Algorithm (IVFA). Eventually, simulation results based-on MATLAB are presented, which do show that this optimal deployment with self-healing movement algorithm can ensure the coverage and communication of an entire region by requiring the least number of nodes and effectively compensate the loss of the networks.

Keywords

Optimal Deployment, Self-Healing Movement, Particular Region, Euclidean Minimum Spanning Tree (EMST), Improved Virtual Force Algorithm (IVFA)

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	F. Akyildz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A survey on sensor networks,” IEEE Communications Magazine, Vol. 40, No. 8, pp. 102–114, August 2002.
[2]	A. Sekhar, B. S. Manoj, and C. S. R. Murthy, “Dynamic coverage maintenance algorithms for sensor networks with limited mobility,” Pervasive Computing and Communications, PerCom 2005, Third IEEE International Conference, pp. 51–60, March 8–12, 2005.
[3]	G. Wang, G. Cao, T. La Porta, and W. Zhang, “Sensor relocation in mobile sensor networks,” Proceedings of the 24th International Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM05) Miami, FL, March 2005.
[4]	N. Heo and P. K. Varshney, “Energy-efficient deployment of intelligent mobile sensor networks,” IEEE Transactions on Systems, Man, and Cybernetics—Part A: Systems and Humans, Vol. 35, No. 1, pp. 78–92, 2005.
[5]	S. Shakkottai, R. Srikant, and N. Shroff, “Unreliable sensor grids: Coverage, connectivity and diameter,” Proceedings of IEEE Infocom, San Francisco, March 2003.
[6]	S. S. Dhillon, K. Chakrabarty, and S. S. Iyengar, “Sensor placement for grid coverage under imprecise detections,” In Proceedings of the Fifth International Conference on Information Fusion, pp. 1580–1588, 2002.
[7]	K. Kar and S. Banerjee, “Node placement for connected coverage in sensor networks,” Proceedings of the Workshop on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt’ 03), Sophia Antipolis, France, 2003.
[8]	S. Ganeriwal, A. Kansal, and M. B. Srivastava, “Self aware actuation for fault repair in sensor networks,” Robotics and Automation, Proceedings, ICRA’04, IEEE International Conference, Vol. 5, pp. 5244–5249, April 26–May 1, 2004.
[9]	J. Chen, S. Li, and Y. Sun, “Novel deployment schemes for mobile sensor networks,” Sensors, No. 7, pp. 2907– 2919, 2007.
[10]	Y. Zou and C. Krishnendu, “Sensor deployment and target localization based on virtual forces,” INFOCOM 2003, Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies, IEEE, Vol. 2, pp. 1293–1303, March 30–April 3, 2003.
[11]	H. N. Shu and Q. L. Liang, “Fuzzy optimization for distributed sensor deployment,” Wireless Communications and Networking Conference, IEEE, Vol. 3, pp. 1903– 1908, March 13–17, 2005.
[12]	X. L. Wu, J. S. Cho, B. J. d’Auriol, and S. Y. Lee, “Optimal deployment of mobile sensor networks and its maintenance strategy,” Computer Science, Advances in Grid and Pervasive Computing, Springer, Berlin, pp. 112–123, June 21, 2007.
[13]	D. Pompili, T. Melodia, and I. F. Akyildiz, “Deployment analysis in underwater acoustic wireless sensor networks,” Proceedings of the ACM International Workshop on Under-Water Networks (WUWNet), Los Angeles, CA, September 2006.
[14]	A. Savvides, C. C. Han, and M. B. Srivastava, “Dynamic fine-grained localization in ad-hoc networks of sensors,” ACM MobiCom, Rome, Italy, pp. 166–179, July 2001.
[15]	S. Borbash and M. McGlynn, “Birthday protocols for low energy deployment and flexible neighbor discovery in ad hoc wireless networks,” ACM MobiHoc, Long Beach, USA, 2001.
[16]	W. B. Heinzelman, A. P. Chandrakasan, and H. Balak- rishnan, “An application specific protocol architecture for wireless microsensor networks,” IEEE Transactions on Wireless Communications, Vol. 1, No. 4, pp. 660–670, 2002.
[17]	M. Younis and K. Akkaya, “Strategies and techniques for node placement in wireless sensor networks,” A Survey in ELSEVIER Ad Hoc Networks, No. 6, pp. 621–655, 2008.
[18]	Y. Zou, “Coverage-driven sensor deployment and energy-efficient information processing in wireless sensor network,” Duke University, 2004.