A survey on barrier coverage with sensors

doi:10.1007/s11704-016-5532-4

Frontiers of Computer Science

2016, Vol. 10

Issue (6): 968-984 https://doi.org/10.1007/s11704-016-5532-4

本期目录

A survey on barrier coverage with sensors

Fan WU¹(

),Yang GUI¹,Zhibo WANG²,Xiaofeng GAO¹,Guihai CHEN¹

¹. Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240, China
². School of Computer,Wuhan University,Wuhan 430072, China

全文: PDF(511 KB)

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.

Key words： sensor network barrier coverage

收稿日期: 2015-12-09 出版日期: 2016-10-11

Corresponding Author(s): Fan WU

引用本文:

. [J]. Frontiers of Computer Science, 2016, 10(6): 968-984.
Fan WU,Yang GUI,Zhibo WANG,Xiaofeng GAO,Guihai CHEN. A survey on barrier coverage with sensors. Front. Comput. Sci., 2016, 10(6): 968-984.

链接本文:

https://academic.hep.com.cn/fcs/CN/10.1007/s11704-016-5532-4
https://academic.hep.com.cn/fcs/CN/Y2016/V10/I6/968

1	Akyildiz I F, Su W, Sankarasubramaniam Y, Cayirci E. Wireless sensor networks: a survey. Elsevier Computer Networks, 2002, 38(4): 393–422 https://doi.org/10.1016/S1389-1286(01)00302-4
2	Yick J, Mukherjee B, Ghosal D. Wireless sensor network survey. Elsevier Computer Networks, 2008, 52(12): 2292–2330 https://doi.org/10.1016/j.comnet.2008.04.002
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 https://doi.org/10.1145/1080829.1080859
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 https://doi.org/10.1145/1374618.1374673
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 https://doi.org/10.1007/s11036-005-1564-y
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 https://doi.org/10.1109/glocom.2010.5683255
8	Barr S, Liu B, Wang J. Barrier coverage for underwater sensor networks. In: Proceedings of the IEEE Military Communications Conference. 2008, 1–7 https://doi.org/10.1109/milcom.2008.4753077
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 https://doi.org/10.1109/mass.2012.6502499
10	Saipulla A, Liu B, Wang J. Barrier coverage with airdropped wireless sensors. In: Proceedings of the IEEE Military Communications Conference. 2008, 1–7 https://doi.org/10.1109/milcom.2008.4753650
11	Cardei M, Wu J. Energy-efficient coverage problems in wireless ad-hoc sensor networks. Computer Communications, 2006, 29(4): 413–420 https://doi.org/10.1016/j.comcom.2004.12.025
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 https://doi.org/10.1109/TPDS.2012.329
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 https://doi.org/10.1109/infcom.2011.5935241
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 https://doi.org/10.1109/TPDS.2011.180
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 https://doi.org/10.1109/infcom.2012.6195829
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 https://doi.org/10.1145/1287853.1287862
18	Akyildiz I F, Stuntebeck E P. Wireless underground sensor networks: research challenges. Ad Hoc Networks, 2006, 4(6): 669–686 https://doi.org/10.1016/j.adhoc.2006.04.003
19	Guvensan M A, Yavuz A G. On coverage issues in directional sensor networks: a survey. Ad Hoc Networks, 2011, 9(7): 1238–1255 https://doi.org/10.1016/j.adhoc.2011.02.003
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 https://doi.org/10.1145/1127777.1127848
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 https://doi.org/10.1109/TMC.2007.57
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 https://doi.org/10.1109/ipsn.2005.1440957
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 https://doi.org/10.1016/j.adhoc.2010.09.008
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 https://doi.org/10.1145/1281492.1281497
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 https://doi.org/10.1109/TVT.2007.905624
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 https://doi.org/10.1109/infcom.2013.6566817
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 https://doi.org/10.1145/1161089.1161103
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 https://doi.org/10.1109/infocom.2006.190
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 https://doi.org/10.1109/infocom.2014.6848126
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 https://doi.org/10.1145/1023720.1023735
32	Yang G, Qiao D. Multi-round sensor deployment for guaranteed barrier coverage. In: Proceedings of IEEE INFOCOM. 2010, 2462–2470 https://doi.org/10.1109/infcom.2010.5462074
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 https://doi.org/10.1109/mass.2013.85
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 https://doi.org/10.1007/978-3-642-04383-3_15
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 https://doi.org/10.1007/s00454-013-9525-x
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 https://doi.org/10.1109/infocom.2015.7218388
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 https://doi.org/10.1007/978-3-642-14785-2_3
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 https://doi.org/10.1145/2248371.2248386
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 https://doi.org/10.1016/j.comcom.2012.01.022
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 https://doi.org/10.1007/978-3-319-00560-7_15
41	Zhang L, Tang J, Zhang W. Strong barrier coverage with directional sensors. In: Proceedings of Global Telecommunications Conference. 2009, 1–6 https://doi.org/10.1109/glocom.2009.5425893
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 https://doi.org/10.1145/1860093.1860121
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 https://doi.org/10.1007/978-3-642-40450-4_9
45	Saipulla A, Westphal C, Liu B, Wang J. Barrier coverage with linebased deployed mobile sensors. Ad Hoc Networks, 2013, 11(4): 1381–1391 https://doi.org/10.1016/j.adhoc.2010.10.002
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 https://doi.org/10.1007/s11276-006-9958-8
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 https://doi.org/10.1109/icppw.2011.31
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 https://doi.org/10.1109/TMC.2010.78
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 https://doi.org/10.1109/wcnc.2012.6214180
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 https://doi.org/10.1145/1374618.1374674
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 https://doi.org/10.1016/j.adhoc.2013.03.005
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 https://doi.org/10.1109/msn.2011.74
55	Wang Y, Cao G. On full-view coverage in camera sensor networks. In: proceedings of IEEE INFOCOM. 2011, 1781–1789 https://doi.org/10.1109/infcom.2011.5934977
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 https://doi.org/10.1145/2107502.2107518
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 https://doi.org/10.1109/infcom.2012.6195602
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 https://doi.org/10.1016/j.pmcj.2014.04.002
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 https://doi.org/10.1109/INFOCOM.2015.7218437
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 https://doi.org/10.1145/2491288.2491305
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 https://doi.org/10.1155/2010/716565
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 https://doi.org/10.1016/j.comnet.2010.10.008
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 https://doi.org/10.1109/infcom.2012.6195479
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 https://doi.org/10.1109/ICC.2010.5501990
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 https://doi.org/10.1145/1815396.1815413
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 https://doi.org/10.1016/j.tcs.2009.07.007
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 https://doi.org/10.1145/1860093.1860096
70	Silvestri S. Mobibar: barrier coverage with mobile sensors. In: Proceedings of Global Telecommunications Conference. 2011, 1–6 https://doi.org/10.1109/glocom.2011.6133536
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 https://doi.org/10.1109/TMC.2013.129
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 https://doi.org/10.1109/mass.2013.12
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 https://doi.org/10.1109/TMC.2013.118
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 https://doi.org/10.1016/j.jpdc.2012.07.004
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 https://doi.org/10.1016/j.comcom.2012.04.021
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 https://doi.org/10.1145/2629518
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 https://doi.org/10.1016/j.tcs.2015.02.006
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 https://doi.org/10.1016/j.pmcj.2011.02.004
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 https://doi.org/10.1109/TVT.2013.2254732
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 https://doi.org/10.1007/978-3-642-14553-7_31

[1]

Supplementary Material

Download

Viewed

Full text

Abstract

Cited

Shared

Discussed