LDM (Layered Deployment Model): A Novel Framework to Deploy Sensors in an Irregular Terrain

Chandan Kr. Bhattacharyya, Swapan Bhattacharya

.

DOI: 10.4236/wsn.2011.36022                

Abstract

Deployment of sensors in any irregular terrain with 100% coverage and connectivity is a challenging issue in the field of Wireless Sensor Networks. Traditional deployments often assume homogeneous environments, which ignore the effect of terrain profile as well as the in-network obstacles situated randomly like buildings, trees, roads and so on. Proper deployment of sensors in such irregular region and its corresponding routing is one of the most fundamental challenges of Wireless Sensor Networks. In this work, we have considered that the terrain is irregular in shape and there may be obstacles within the terrain in any random position with any random shape, which is the reality in real world. With this novel framework, we have shown that an opti-mum deployment can be achieved in such irregular terrain without compromising coverage as well as con-nectivity between the sensor nodes for effective routing.

Keywords

Wireless Sensor Networks, Sensor Deployment, Shortest Path, Routing, Irregular Terrain

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	L. Zhao and Q. L. Liang, “Fuzzy Deployment for Wire-less Sensor Networks,” Proceedings of the 2005 IEEE International Conference on Computational Intelligence for Homeland Security and Personal Safety, 2005, pp. 79-83. doi:10.1109/CIHSPS.2005.1500615
[2]	Y. C. Wang, C. C. Hu and Y. C. Tseng, “Efficient De-ployment Algorithms for Ensuring Coverage and Connectivity of Wireless Sensor Networks,” Proceedings of First International Conference on Wireless Internet, 2005, pp. 114-121. doi:10.1109/WICON.2005.13
[3]	G. Wang, G. Cao and T. L. Porta, “Movement-Assisted Sensor Deployment,” IEEE Transactions on Mobile Computing, Vol. 5, No. 6, 2006, pp. 640-652. doi:10.1109/TMC.2006.80
[4]	S. H. Yang, M. L. Li and J. Wu, “Scan-Based Movement- Assisted Sensor Deployment Methods in Wireless Sensor Networks,” Proceedings of Parallel and Distributed Sys-tems, IEEE Transactions Publication, Vol. 18, No. 8, 2007, pp. 1108-1121. doi:10.1109/TPDS.2007.1048
[5]	Can Fang Chor Ping Low, “Unified Framework for Movement-Assisted Sensor Deployment,” Proceedings of Wireless Communications and Networking Conference, 31 March 2008-3 April 2008, pp. 2057-2062.
[6]	M. de Berg, M. van Kreveld, M. Overmars and O. Schwarzkopf, “Computational Geometry, Algorithm and Application,” 2nd Edition, Springer, 2000.
[7]	Q. Fang, J. Gao and L. J. Guibas, “Locating and Bypass-ing Holes in Sensor Networks,” Proceedings of Mobile Networks and Applications, Vol. 11, No. 2, 2006, pp. 187-200. doi:10.1007/s11036-006-4471-y
[8]	F. Reitsma and S. Engel, “Searching for 2D Spatial Net-work Holes,” Proceedings of International Conference on Computational Science and Its Applications, 2004, pp. 1069-1078.
[9]	S. Funke and Christian Klein, “Hole Detection or: How much Geometry Hides in Connectivity?” Proceedings of the Twenty-Second Annual Symposium on Computational Geometry, Sedona, 2006, pp. 377-385.
[10]	B. D. Ying and Z. Z. Hou, “Irregular-Location Based Key Pre-Distribution Scheme for Distribution Sensor Net-works,” Proceedings of 1st International Conference on Information Science and Engineering, 2009, pp. 4042- 4046. doi:10.1109/ICISE.2009.698
[11]	B. Xiao, L. Chen, Q. J. Xiao and M. L. Li, “Reliable An-chor-Based Sensor Localization in Irregular Areas,” Pro-ceedings of IEEE Transactions on Mobile Computing, 2010, pp. 60-72.
[12]	S. K. Udgata, S. L. Sabat and S. Mini, “Sensor Deploy-ment in Irregular Terrain Using Artificial Bee Colony Algorithm,” Proceedings on Nature & Biologically In-spired Computing, 2009, pp. 1309-1314.
[13]	G. Takahara, K. Xu and H. Hassanein, “Efficient Cover-age Planning for Grid-Based Wireless Sensor Networks,” Proceedings of IEEE International Conference on Com-munications, 2007, pp. 3522-3526.
[14]	C. Y. Chang, C. T. Chang, Y. C. Chen and H. R. Chang, “Obstacle-Resistant Deployment Algorithms for Wireless Sensor Networks,” Proceedings of IEEE Transactions on Vehicular Technology, 2009, pp. 2925-2941.
[15]	T. L. Chin, “Sensor Deployment for Collaborative Target Detection in the Presence of Obstacles,” Proceedings of IEEE Global Telecommunications Conference, 2009, pp. 1-5.
[16]	K. N. Xu, G. Takahara and H. Hassanein,“On the Ro-bustness of Grid-Based Deployment in Wireless Sensor Networks,” Proceedings of The 2006 International Con-ference on Wireless Communications and Mobile Com-puting, 2006, pp. 1183-1188.
[17]	F. Zhao, J. Shin and J. Reich, “Information-Driven Dy-namic Sensor Collaboration for Tracking Applications,” Signal Processing Magazine, Vol. 19, No. 2, 2002, pp. 61-72. doi:10.1109/79.985685
[18]	Y. Rachlin, R. Negi and P. Khosla, “Sensing Capacity for Target Detection,” Information Theory Workshop, 2004, pp. 147-152.
[19]	Z. H. Yuan and G. F. Wang, “Sensor Deployment Strat-egy for Collaborative Target Detection with Guaranteed Accuracy,” Proceedings of the 4th International Confer-ence on Mobile Ad-hoc and Sensor Networks, 10-12 De-cember 2008, pp. 68-71. doi:10.1109/MSN.2008.14
[20]	Z. Y. Wu, H. T. Song, S. F. Jiang and X. M. Xu, “A Grid-Based Stable Routing Algorithm in Mobile Ad Hoc Networks,” First Asia International Conference on Mod-elling & Simulation, 27-30 March 2007, pp. 181-186.
[21]	Y. R. Tsai, “Coverage-Preserving Routing Protocols for Randomly Distributed Wireless Sensor Networks,” IEEE Transactions on Wireless Communications, Vol. 6, No. 4, 2007, pp. 1240-1245. doi:10.1109/TWC.2007.348320
[22]	J. Zhang and H. Shi, “Energy-Efficient Routing for 2D Grid Wireless Sensor Networks,” Proceedings of Inter-national Conference on Information Technology: Re-search and Education, 11-13 August 2003, pp. 311-315.
[23]	C. Kr. Bhattacharyya, S. Bhattacharyya, “Neighbor- Assisted Sensor Deployment in an Irregular Space: A Unified Framework,” Proceedings of the 15th Asia- Pacific IEEE International Conference on Communica-tions, 2009, Shanghai, 8-10 October 2009, pp. 834-837.