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

Authors

  • 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

Keywords:

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

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

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

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

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

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

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

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

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

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

Eugene Lawler. Combinatorial Optimization:Networks and Matroids. Holt, Renehart and Winston Press, NewYork, 1976.

Published

2010-12-01

Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.