Energy-Efficient Algorithms for k-Barrier Coverage In Mobile Sensor Networks

  • Dongsong Ban National University of Defense Technology School of Computer Changsha, Hunan, P.R.China
  • Wei Yang National University of Defense Technology School of Computer Changsha, Hunan, P.R.China
  • Jie Jiang National University of Defense Technology School of Computer Changsha, Hunan, P.R.China
  • Jun Wen National University of Defense Technology School of Computer Changsha, Hunan, P.R.China
  • Wenhua Dou National University of Defense Technology School of Computer Changsha, Hunan, P.R.China

Abstract

Barrier coverage is an appropriate coverage model for intrusion detection by constructing sensor barriers in wireless sensor networks. In this paper, we focus on the problem how to relocate mobile sensors to construct k sensor barriers with minimum energy consumption. We first analyze this problem, give its Integer Linear Programming(ILP) model and prove it to be NP-hard. Then we devise an approximation algorithm AHGB to construct one sensor barrier energy-efficiently, simulations show that the solution of AHGB is close to the optimal solution. Based on AHGB, a Divide-and-Conquer algorithm is proposed to achieve k-barrier coverage for large sensor networks. Simulations demonstrate the effectiveness of the Divide-and-Conquer algorithm.

References

[1] Chen, S. Kumar and T. H. Lai. Designing Localized Algorithms for Barrier Coverage. In Proc. of Mobicom07, ACM, pp:63-74, 2007.

[2] S. Kumar, T. H. Lai and A. Arora. Barrier Coverage With Wireless Sensors. In Proc. of Mobicom05, ACM, pp:284-298, 2005.
http://dx.doi.org/10.1145/1080829.1080859

[3] Benyuan Liu, Olivier Dousse and Jie Wang. Strong Barrier Coverage of Wireless Sensor Networks. In Proc. of Mobihoc08, ACM, pp:411-420, 2008.

[4] Anwar Saipulla, Benyuan Liu and Jie Wang. Barrier Coverage of Line-Based Deployed Wireless Sensor Networks In Proc. of INFOCOM09, IEEE, pp:127-135, 2009.
http://dx.doi.org/10.1109/infcom.2009.5061914

[5] Guanqun Yang and Daji Qiao. Barrier Information Coverage with Wireless Sensors.In Proc.of INFOCOM09, IEEE, pp:918-926, 2009
http://dx.doi.org/10.1109/infcom.2009.5062002

[6] B. Bhattacharya, M. Burmester, Y. Hu, E. Kranakis and Q. Shi. Optimal Movement of Mobile Sensors for Barrier Coverage of a Planar Region. In Proc.of COCOA, pp:103-115, 2008.
http://dx.doi.org/10.1007/978-3-540-85097-7_10

[7] Guanqun Yang, Wei Zhou and Daji Qiao. Defending Against Barrier Intrusions with Mobile Sensors. In Proc.of WASA07, pp: 113-120, 2007
http://dx.doi.org/10.1109/wasa.2007.21

[8] CX Shen, WF Cheng, XK Liao and SL Peng. Barrier coverage with mobile sensor. In Proc. of I-SPAN08, IEEE, pp.99-104, 2008.
http://dx.doi.org/10.1109/i-span.2008.8

[9] Eugene Lawler. Combinatorial Optimization:Networks and Matroids. Holt, Renehart and Winston Press, NewYork, 1976.
Published
2010-12-01
How to Cite
BAN, Dongsong et al. Energy-Efficient Algorithms for k-Barrier Coverage In Mobile Sensor Networks. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 5, n. 5, p. 616-624, dec. 2010. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/2217>. Date accessed: 11 aug. 2020. doi: https://doi.org/10.15837/ijccc.2010.5.2217.

Keywords

k-barrier coverage, energy-efficient relocation, mobile sensor network