Energy-Efficient Algorithms for k-Barrier Coverage In Mobile Sensor Networks
Keywords:k-barrier coverage, energy-efficient relocation, mobile sensor network
AbstractBarrier 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.
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.
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.