A survey on barrier coverage with sensors

Abstract

For various applications, sensors are deployed to monitor belt regions to guarantee that every movement crossing a barrier of sensors will be detected in real-time with high accuracy and minimize the need for human support. The barrier coverage problem is introduced to model these requirements, and has been examined thoroughly in the past decades. In this survey, we state the problem definitions and systematically consider sensing models, design issues and challenges in barrier coverage problem. We also review representative algorithms in this survey. Furthermore, we provide discussions on some extensions and variants of barrier coverage problems.

Keywords

sensor network / barrier coverage

References

[1] Akyildiz I F, Su W, Sankarasubramaniam Y, Cayirci E. Wireless sensor networks: a survey. Elsevier Computer Networks, 2002, 38(4): 393–422

[2] Yick J, Mukherjee B, Ghosal D. Wireless sensor network survey. Elsevier Computer Networks, 2008, 52(12): 2292–2330

[3] Kumar S, Lai T H, Arora A. Barrier coverage with wireless sensors. In: Proceedings of the 11th Annual International Conference on Mobile Computing and Networking. 2005, 284–298

[4] Liu B, Dousse O, Wang J, Saipulla A. Strong barrier coverage of wireless sensor networks. In: Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing. 2008, 411–420

[5] Huang C F, Tseng Y C. The coverage problem in a wireless sensor network. Springer Mobile Networks and Applications, 2005, 10(4): 519–528

[6] Schrijver A. Combinatorial Optimization. Springer, 2003

[7] He J, Shi H. A distributed algorithm for finding maximum barrier coverage in wireless sensor networks. In: Proceedings of Global Telecommunications Conference. 2010, 1–5

[8] Barr S, Liu B, Wang J. Barrier coverage for underwater sensor networks. In: Proceedings of the IEEE Military Communications Conference. 2008, 1–7

[9] Kong L, Zhu Y, Wu M Y, Shu W. Mobile barrier coverage for dynamic objects in wireless sensor networks. In: Proceedings of the 9th IEEE International Conference on Mobile Ad Hoc and Sensor Systems. 2012, 29–37

[10] Saipulla A, Liu B, Wang J. Barrier coverage with airdropped wireless sensors. In: Proceedings of the IEEE Military Communications Conference. 2008, 1–7

[11] Cardei M, Wu J. Energy-efficient coverage problems in wireless ad-hoc sensor networks. Computer Communications, 2006, 29(4): 413–420

[12] Mao X, Liu Y, Tang S, Liu H, Han J, Li X Y. Finding best and worst k-coverage paths in multihop wireless sensor networks. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(12): 2396–2406

[13] Chen A, Li Z, Lai T H, Liu C. One-way barrier coverage with wireless sensors. In: Proceedings of IEEE INFOCOM. 2011, 626–630

[14] Liu B, Towsley D. A study of the coverage of large-scale sensor networks. In: Proceedings of the 2004 IEEE International Conference on Mobile Ad-hoc and Sensor Systems. 2004, 475–483

[15] He S, Chen J, Li X, Shen X S, Sun Y. Leveraging prediction to improve the coverage of wireless sensor networks. IEEE Transactions on Parallel and Distributed Systems, 2012, 23(4): 701–712

[16] He S, Chen J, Li X, Shen X, Sun Y. Cost-effective barrier coverage by mobile sensor networks. In: Proceedings of IEEE INFOCOM. 2012, 819–827

[17] Chen A, Kumar S, Lai T H. Designing localized algorithms for barrier coverage. In: Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking. 2007, 63–74

[18] Akyildiz I F, Stuntebeck E P. Wireless underground sensor networks: research challenges. Ad Hoc Networks, 2006, 4(6): 669–686

[19] Guvensan M A, Yavuz A G. On coverage issues in directional sensor networks: a survey. Ad Hoc Networks, 2011, 9(7): 1238–1255

[20] Dutta P K, Arora A, Bibyk S B. Towards radar-enabled sensor networks. In: Proceedings of the 5th International Conference on Information Processing in Sensor Networks. 2006, 467–474

[21] Patrascu A C. Optimizing distributed sensor placement for border patrol interdiction using microsoft excel. Technical Report. 2007

[22] Somasundara A A, Ramamoorthy A, Srivastava M B. Mobile element scheduling with dynamic deadlines. IEEE Transactions on Mobile Computing, 2007, 6(4): 395–410

[23] Dantu K, Rahimi M H, Shah H, Babel S, Dhariwal A, Sukhatme G S. Robomote: enabling mobility in sensor networks. In: Proceedings of the 4th International Symposium on Information Processing in Sensor Networks. 2005, 404–409

[24] Sun Z, Wang P, Vuran M C, Al-Rodhaan M, Al-Dhelaan A, Akyildiz I F. Bordersense: border patrol through advanced wireless sensor networks. Ad Hoc Networks, 2011, 9(3): 468–477

[25] Kansal A, Kaiser W J, Pottie G J, Srivastava M B, Sukhatme G. Reconfiguration methods for mobile sensor networks. ACM Transactions on Sensor Networks, 2007, 3(4): 22

[26] Tsai Y R. Sensing coverage for randomly distributed wireless sensor networks in shadowed environments. IEEE Transactions on Vehicular Technology, 2008, 57(1): 556–564

[27] He S, Gong X, Zhang J, Chen J, Sun Y. Barrier coverage in wireless sensor networks: from lined-based to curve-based deployment. In: Proceedings of IEEE INFOCOM. 2013, 470–474

[28] Goldenberg D K, Bihler P, Yang Y R, Cao M, Fang J, Morse A S, Anderson B D O. Localization in sparse networks using sweeps. In: Proceedings of the 12th Annual International Conference on Mobile Computing and Networking. 2006, 110–121

[29] Luo J, Shukla H V, Hubaux J P. Non-interactive location surveying for sensor networks with mobility-differentiated ToA. In: Proceedings of the 25th IEEE International Conference on Computer Communications. 2006

[30] Wang Z, Chen H, Cao Q, Qi H, Wang Z. Fault tolerant barrier coverage for wireless sensor networks. In: Proceedings of the IEEE Conference on Computer Communications. 2014

[31] Kumar S, Lai T H, Balogh J. On k-coverage in a mostly sleeping sensor network. In: Proceedings of the 10th Annual International Conference on Mobile Computing and Networking. 2004

[32] Yang G, Qiao D. Multi-round sensor deployment for guaranteed barrier coverage. In: Proceedings of IEEE INFOCOM. 2010, 2462–2470

[33] Eftekhari M, Narayanan L, Opatrny J. On multi-round sensor deployment for barrier coverage. In: Proceedings of the 10th IEEE International Conference on Mobile Ad-Hoc and Sensor Systems. 2013, 310–318

[34] Czyzowicz J, Kranakis E, Krizanc D, Lambadaris I, Narayanan L, Opatrny J, Stacho L, Urrutia J, Yazdani M. On minimizing the maximum sensor movement for barrier coverage of a line segment. In: Proceedings of the International Conference on Ad-Hoc Networks and Wireless. 2009, 194–212

[35] Chen D Z, Gu Y, Li J, Wang H. Algorithms on minimizing the maximum sensor movement for barrier coverage of a linear domain. Discrete & Computational Geometry, 2013, 50(2): 374–408

[36] Li S, Shen H. Minimizing the maximum sensor movement for barrier coverage in the plane. In: Proceedings of the IEEE Conference on Computer Communications. 2015, 244–252

[37] Czyzowicz J, Kranakis E, Krizanc D, Lambadaris I, Narayanan L, Opatrny J, Stacho L, Urrutia J, Yazdani M. On minimizing the sum of sensor movements for barrier coverage of a line segment. In: Proceedings of International Conference on Ad-Hoc Networks and Wireless. 2010, 29–42

[38] Han K, Xiang L, Luo J, Liu Y. Minimum-energy connected coverage in wireless sensor networks with omni-directional and directional features. In: Proceedings of the 13th ACM International Symposium on Mobile Ad-Hoc Networking and Computing. 2012, 85–94

[39] Tao D, Tang S, Zhang H, Mao X, Ma H. Strong barrier coverage in directional sensor networks. Computer Communications, 2012, 35(8): 895–905

[40] Bendimerad N, Kechar B. Coverage enhancement in wireless videobased sensor networks with rotating capabilities. In: Amine A, Otmane A M, Bellatreche L, eds. Modeling Approaches and Algorithms for Advanced Computer Applications. Springer International Publishing, 2013, 105–114

[41] Zhang L, Tang J, Zhang W. Strong barrier coverage with directional sensors. In: Proceedings of Global Telecommunications Conference. 2009, 1–6

[42] Saipulla A, Liu B, Xing G, Fu X, Wang J. Barrier coverage with sensors of limited mobility. In: Proceedings of the 11th ACM International Symposium on Mobile Ad-Hoc Networking and Computing. 2010, 201–210

[43] Hesari M E, Kranakis E, Krizanc D, Ponce O M, Narayanan L, Opatrny J, Shende S M. Distributed algorithms for barrier coverage using relocatable sensors. In: Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing. 2013, 383–392

[44] Bar-Noy A, Rawitz D, Terlecky P. Maximizing barrier coverage lifetime with mobile sensors. In: Proceedings of European Symposium on Algorithms. 2013, 97–108

[45] Saipulla A, Westphal C, Liu B, Wang J. Barrier coverage with linebased deployed mobile sensors. Ad Hoc Networks, 2013, 11(4): 1381–1391

[46] Hu Y, Han S, Wang X, Gan X. Critical sensing range for camera sensor networks. In: Proceedings of IEEE INFOCOM. 2014, 970–978

[47] Kumar S, Lai T H, Balogh J. On k-coverage in a mostly sleeping sensor network. Wireless Networks, 2008, 14(3): 277–294

[48] Yamamoto K, Ozaki H, Suzuki T, Wada T, Mutsuura K, Okada H. Barrier coverage constructions for border security systems using wireless sensors. In: Proceedings of the 40th International Conference on Parallel Processing Workshops. 2011, 50–56

[49] Kumar S, Lai T H, Posner M E, Sinha P. Maximizing the lifetime of a barrier of wireless sensors. IEEE Transactions on Mobile Computing, 2010, 9(8): 1161–1172

[50] Kim D, Kim J, Li D, Kwon S S, Tokuta A O. On sleep-wakeup scheduling of non-penetrable barrier-coverage of wireless sensors. In: Proceedings of Global Communications Conference. 2012, 321–327

[51] Chang C Y, Hsiao C Y, Chang C T. The k-barrier coverage mechanism in wireless visual sensor networks. In: Proceedings of the IEEE Wireless Communications and Networking Conference. 2012, 2318–2322

[52] Chen A, Lai T H, Xuan D. Measuring and guaranteeing quality of barrier-coverage in wireless sensor networks. In: Proceedings of the 9th ACM International Symposium on Mobile Ad-Hoc Networking and Computing. 2008, 421–430

[53] Lee C, Shin D, Bae S W, Choi S. Best and worst-case coverage problems for arbitrary paths in wireless sensor networks. Ad Hoc Networks, 2013, 11(6): 1699–1714

[54] Tao D, Mao X F, Tang S J, Zhang H T, Ma H D, Xie H J. Strong barrier coverage using directional sensors with arbitrarily tunable orientations. In: Proceedings of the 7th International Conference on Mobile Ad-hoc and Sensor Networks. 2011, 68–74

[55] Wang Y, Cao G. On full-view coverage in camera sensor networks. In: proceedings of IEEE INFOCOM. 2011, 1781–1789

[56] Wang Y, Cao G. Barrier coverage in camera sensor networks. In: Proceedings of the 12th ACM International Symposium onMobile Ad Hoc Networking and Computing. 2011

[57] Ma H, Yang M, Li D, Hong Y, Chen W. Minimum camera barrier coverage in wireless camera sensor networks. In: Proceedings of IEEE INFOCOM. 2012, 217–225

[58] Yang C, Zhu W, Liu J, Chen L, Chen D, Cao J. Self-orienting the cameras for maximizing the view-coverage ratio in camera sensor networks. Pervasive and Mobile Computing, 2014, 17: 102–121

[59] Yu Z, Yang F, Teng J, Champion A C, Xuan D. Local face-view barrier coverage in camera sensor networks. In: Proceedings of the 2015 IEEE Conference on Computer Communications. 2015, 684–692

[60] Gong X, Zhang J, Cochran D. When target motion matters: Doppler coverage in radar sensor networks. In: Peoceedings of IEEE INFOCOM. 2013, 1169–1177

[61] Gong X, Zhang J, Cochran D, Xing K. Barrier coverage in bistatic radar sensor networks: cassini oval sensing and optimal placement. In: Proceedings of the 14th ACM international Symposium on Mobile Ad Hoc Networking and Computing. 2013, 49–58

[62] Noori M, Movaghati S, Ardakani M. Characterizing the path coverage of random wireless sensor networks. EURASIP Journal on Wireless Communications and Networking, 2010, 2010(1): 1–11

[63] Li L, Zhang B, Shen X, Zheng J, Yao Z. A study on the weak barrier coverage problem in wireless sensor networks. Computer Networks, 2011, 55(3): 711–721

[64] Li J, Chen J, Lai T H. Energy-efficient intrusion detection with a barrier of probabilistic sensors. In: Proceedings of IEEE INFOCOM. 2012, 118–126

[65] Zhao L, Bai G, Jiang Y, Shen H, Tang Z. Optimal deployment and scheduling with directional sensors for energy-efficient barrier coverage. International Journal of Distributed Sensor Networks, 2014, 2014: 1–9

[66] Kong L, Liu X, Li Z, Wu M Y. Automatic barrier coverage formation with mobile sensor networks. In: Proceedings of the 2010 IEEE International Conference on Communications. 2010, 1–5

[67] Ban D, Jiang J, Yang W, Dou W, Yi H. Strong k-barrier coverage with mobile sensors. In: Proceedings of the 6th ACM International Wireless Communications and Mobile Computing Conference. 2010, 68–72

[68] Bhattacharya B K, Burmester M, Hu Y, Kranakis E, Shi Q, Wiese A. Optimal movement of mobile sensors for barrier coverage of a planar region. Theoretical Computer Science, 2009, 410(52): 5515–5528

[69] Keung G Y, Li B, Zhang Q. The intrusion detection in mobile sensor network. In: Proceedings of the 11th ACM International Symposium on Mobile Ad Hoc Networking and Computing. 2010, 11–20

[70] Silvestri S. Mobibar: barrier coverage with mobile sensors. In: Proceedings of Global Telecommunications Conference. 2011, 1–6

[71] He S, Chen J, Li X, Shen X S, Sun Y. Mobility and intruder prior information improving the barrier coverage of sparse sensor networks. IEEE Transactions on Mobile Computing, 2014, 13(6): 1268–1282

[72] Wang Z, Liao J, Cao Q, Qi H, Wang Z. Barrier coverage in hybrid directional sensor networks. In: Proceedings of the 10th IEEE International Conference on Mobile Ad-Hoc and Sensor Systems. 2013, 222–230

[73] Wang Z, Liao J, Cao Q, Qi H, Wang Z. Achieving k-barrier coverage in hybrid directional sensor networks. IEEE Transactions on Mobile Computing, 2014, 13(7): 1443–1455

[74] Lai Y L, Jiang J R. Barrier coverage with optimized quality for wireless sensor networks. In: Proceedings of the 5th International Symposium on Wireless Personal Multimedia Communications. 2012, 192–196

[75] He J, Shi H. Constructing sensor barriers with minimum cost in wireless sensor networks. Journal of Parallel and Distributed Computing, 2012, 72(12): 1654–1663

[76] Ma H, Li D, Chen W, Zhu Q, Yang H. Energy efficient k-barrier coverage in limited mobile wireless sensor networks. Computer Communications, 2012, 35(14): 1749–1758

[77] Fan H, Li M, Sun X, Wan P J, Zhao Y. Barrier coverage by sensors with adjustable ranges. ACM Transactions on Sensor Networks (TOSN), 2014, 11(1): 14

[78] Dobrev S, Durocher S, Hesari M E, Georgiou K, Kranakis E, Krizanc D, Narayanan L, Opatrny J, Shende S M, Urrutia J. Complexity of barrier coverage with relocatable sensors in the plane. Theoretical Computer Science, 2015, 579: 64–73

[79] Medagliani P, Leguay J, Ferrari G, Gay V, Lopez-Ramos M. Energyefficient mobile target detection in wireless sensor networks with random node deployment and partial coverage. Pervasive and Mobile Computing, 2012, 8(3): 429–447

[80] Chen J, Li J, Lai T H. Trapping mobile targets in wireless sensor networks: an energy-efficient perspective. IEEE Transactions on Vehicular Technology, 2013, 62(7): 3287–3300

[81] Tan X, Wu G. New algorithms for barrier coverage with mobile sensors. In: Proceedings of International Workshop on Frontiers in Algorithmics. 2010, 327–338

RIGHTS & PERMISSIONS

2016 Higher Education Press and Springer-Verlag Berlin Heidelberg