{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T15:36:48Z","timestamp":1763480208080,"version":"build-2065373602"},"reference-count":40,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2018,2,10]],"date-time":"2018-02-10T00:00:00Z","timestamp":1518220800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"The Key Projects of National Key Research and Development Program","award":["2016YFC0801800"],"award-info":[{"award-number":["2016YFC0801800"]}]},{"name":"The Natural Science Foundation of China","award":["51474015"],"award-info":[{"award-number":["51474015"]}]},{"name":"The National Science&amp;Technology Pillar Program of China","award":["2013BAK06B03"],"award-info":[{"award-number":["2013BAK06B03"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>Barrier coverage has been widely used to detect intrusions in wireless sensor networks (WSNs). It can fulfill the monitoring task while extending the lifetime of the network. Though barrier coverage in WSNs has been intensively studied in recent years, previous research failed to consider the problem of intrusion in transversal directions. If an intruder knows the deployment configuration of sensor nodes, then there is a high probability that it may traverse the whole target region from particular directions, without being detected. In this paper, we introduce the concept of crossed barrier coverage that can overcome this defect. We prove that the problem of finding the maximum number of crossed barriers is NP-hard and integer linear programming (ILP) is used to formulate the optimization problem. The branch-and-bound algorithm is adopted to determine the maximum number of crossed barriers. In addition, we also propose a multi-round shortest path algorithm (MSPA) to solve the optimization problem, which works heuristically to guarantee efficiency while maintaining near-optimal solutions. Several conventional algorithms for finding the maximum number of disjoint strong barriers are also modified to solve the crossed barrier problem and for the purpose of comparison. Extensive simulation studies demonstrate the effectiveness of MSPA.<\/jats:p>","DOI":"10.3390\/s18020534","type":"journal-article","created":{"date-parts":[[2018,2,12]],"date-time":"2018-02-12T10:50:38Z","timestamp":1518432638000},"page":"534","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Achieving Crossed Strong Barrier Coverage in Wireless Sensor Network"],"prefix":"10.3390","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5440-4906","authenticated-orcid":false,"given":"Ruisong","family":"Han","sequence":"first","affiliation":[{"name":"School of Electronic and Information Engineering, Beijing Jiaotong University, Beijing 100044, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei","family":"Yang","sequence":"additional","affiliation":[{"name":"School of Electronic and Information Engineering, Beijing Jiaotong University, Beijing 100044, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Li","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Electronic and Electrical Engineering, University of Leeds, Leeds LS2 9DX, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,2,10]]},"reference":[{"key":"ref_1","unstructured":"Kumar, S., Lai, T.H., and Arora, A. (September, January 28). Barrier coverage with wireless sensors. Proceedings of the 11th Annual International Conference on Mobile Computing and Networking, Cologne, Germany."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1109\/TMC.2009.147","article-title":"Local barrier coverage in wireless sensor networks","volume":"9","author":"Chen","year":"2010","journal-title":"IEEE Trans. Mobile Comput."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"876","DOI":"10.1109\/JSEN.2014.2310180","article-title":"A survey on barrier coverage problem in directional sensor networks","volume":"15","author":"Tao","year":"2015","journal-title":"IEEE Sensors J."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"619","DOI":"10.1016\/j.jnca.2011.11.016","article-title":"A survey on coverage and connectivity issues in wireless sensor networks","volume":"35","author":"Zhu","year":"2012","journal-title":"J. Netw. Comput. Appl."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1007\/s11036-005-1564-y","article-title":"The coverage problem in a wireless sensor network","volume":"10","author":"Huang","year":"2005","journal-title":"Mobile Netw. Appl."},{"key":"ref_6","unstructured":"Kumar, S., Lai, T.H., and Balogh, J. (October, January 26). On k-coverage in a mostly sleeping sensor network. Proceedings of the 10th Annual International Conference on Mobile Computing and Networking, Philadelphia, PA, USA."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1161","DOI":"10.1109\/TMC.2010.78","article-title":"Maximizing the lifetime of a barrier of wireless sensors","volume":"9","author":"Kumar","year":"2010","journal-title":"IEEE Trans. Mobile Comput."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Gage, D.W. (1992, January 22\u201324). Command control for many-robot systems. Proceedings of the AUVS-92, Huntsville, AL, USA.","DOI":"10.21236\/ADA422540"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Balister, P., Bollobas, B., Sarkar, A., and Kumar, S. (2007, January 9\u201314). Reliable density estimates for coverage and connectivity in thin strips of finite length. Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking, Montr\u00e9al, QC, Canada.","DOI":"10.1145\/1287853.1287863"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Kumar, S., Lai, T.H., Posner, M.E., and Sinha, P. (2007, January 10\u201314). Optimal sleep-wakeup algorithms for barriers of wireless sensors. Proceedings of the 4th International Conference on Broadband Communications, Networks and Systems, Raleigh, NC, USA.","DOI":"10.1109\/BROADNETS.2007.4550452"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Chen, A., Kumar, S., and Lai, T.H. (2007, January 9\u201314). Designing localized algorithms for barrier coverage. Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking, Montr\u00e9al, QC, Canada.","DOI":"10.1145\/1287853.1287862"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Chen, A., Lai, T.H., and Xuan, D. (2008, January 26\u201330). Measuring and guaranteeing quality of barrier-coverage in wireless sensor networks. Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing, Hong Kong, China.","DOI":"10.1145\/1374618.1374674"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Liu, B., Dousse, O., Wang, J., and Saipulla, A. (2008, January 26\u201330). Strong barrier coverage of wireless sensor networks. Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing, Hong Kong, China.","DOI":"10.1145\/1374618.1374673"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"711","DOI":"10.1016\/j.comnet.2010.10.008","article-title":"A study on the weak barrier coverage problem in wireless sensor networks","volume":"55","author":"Li","year":"2011","journal-title":"Comput. Netw."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/1978802.1978811","article-title":"Coverage problems in sensor networks: A survey","volume":"43","author":"Wang","year":"2011","journal-title":"ACM Comput. Surveys"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Meguerdichian, S., Koushanfar, F., Qu, G., and Potkonjak, M. (2001, January 16\u201321). Exposure in wireless ad-hoc sensor networks. Proceedings of the 7th Annual International Conference on Mobile Computing and Networking, Rome, Italy.","DOI":"10.1145\/381677.381691"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Wu, Y., Yin, J., Li, M., En, Z., and Xie, Z. (2008, January 15\u201318). Efficient algorithms for probabilistic k-coverage in directional sensor networks. Proceedings of the 2008 International Conference on Intelligent Sensors, Sensor Networks and Information Processing (ISSNIP 2008), Sydney, NSW, Australia.","DOI":"10.1109\/ISSNIP.2008.4762053"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Yang, G., and Qiao, D. (2009, January 19\u201325). Barrier information coverage with wireless sensors. Proceedings of the IEEE INFOCOM 2009, Rio de Janeiro, Brazil.","DOI":"10.1109\/INFCOM.2009.5062002"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Si, P., Wu, C., Zhang, Y., Jia, Z., Ji, P., and Chu, H. (2017). Barrier coverage for 3d camera sensor networks. Sensors, 17.","DOI":"10.3390\/s17081771"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Zhuang, Y., Wu, C., Zhang, Y., and Jia, Z. (2017). Compound event barrier coverage in wireless sensor networks under multi-constraint conditions. Sensors, 17.","DOI":"10.3390\/s17010025"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"724","DOI":"10.1109\/TWC.2013.121813.130198","article-title":"Curve-based deployment for barrier coverage in wireless sensor networks","volume":"13","author":"He","year":"2014","journal-title":"IEEE Trans. on Wirel. Commun."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Saipulla, A., Westphal, C., Benyuan, L., and Jie, W. (2009, January 19\u201325). Barrier coverage of line-based deployed wireless sensor networks. Proceedings of the IEEE INFOCOM 2009, Rio de Janeiro, Brazil.","DOI":"10.1109\/INFCOM.2009.5061914"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Wang, Y., and Cao, G. (2011, January 17\u201319). Barrier coverage in camera sensor networks. Proceedings of the Twelfth ACM International Symposium on Mobile Ad Hoc Networking and Computing, Paris, France.","DOI":"10.1145\/2107502.2107518"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"He, S., Chen, J., Li, X., Shen, X., and Sun, Y. (2012, January 25\u201330). Cost-effective barrier coverage by mobile sensor networks. Proceedings of the 2012 IEEE INFOCOM, Orlando, FL, USA.","DOI":"10.1109\/INFCOM.2012.6195829"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Saipulla, A., Liu, B., Xing, G., Fu, X., and Wang, J. (2010, January 20\u201324). Barrier coverage with sensors of limited mobility. Proceedings of the Eleventh ACM International Symposium on Mobile Ad Hoc Networking and Computing, Chicago, IL, USA.","DOI":"10.1145\/1860093.1860121"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1443","DOI":"10.1109\/TMC.2013.118","article-title":"Achieving k-barrier coverage in hybrid directional sensor networks","volume":"13","author":"Wang","year":"2014","journal-title":"IEEE Trans. Mobile Comput."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"7364","DOI":"10.1109\/JSEN.2016.2566808","article-title":"Adaptive barrier coverage using software defined sensor networks","volume":"16","author":"Kong","year":"2016","journal-title":"IEEE Sensors J."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/j.adhoc.2017.06.004","article-title":"Cost-effective barrier coverage formation in heterogeneous wireless sensor networks","volume":"64","author":"Wang","year":"2017","journal-title":"Ad Hoc Netw."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"314","DOI":"10.1016\/j.comnet.2016.11.014","article-title":"Achieving location error tolerant barrier coverage for wireless sensor networks","volume":"112","author":"Wang","year":"2017","journal-title":"Comput. Netw."},{"key":"ref_30","unstructured":"Han, R., Zhang, L., and Wei, Y. (2016, January 20\u201323). Maximizing strong barriers in lifetime-heterogeneous directional sensor network. Proceedings of the 13th International Symposium on Wireless Communication Systems (ISWCS 2016), Poznan, Poland."},{"key":"ref_31","unstructured":"Li, Z., Jian, T., and Weiyi, Z. (December, January 30). Strong barrier coverage with directional sensors. Proceedings of the IEEE Global Telecommunications Conference, 2009 (GLOBECOM 2009), Honolulu, HI, USA."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/j.jnca.2017.01.010","article-title":"Constructing event-driven partial barriers with resilience in wireless mobile sensor networks","volume":"82","author":"Kim","year":"2017","journal-title":"J. Netw. Comput. Appl."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"1859","DOI":"10.1109\/LCOMM.2017.2697858","article-title":"Heterbar: Construction of heterogeneous reinforced barrier in wireless sensor networks","volume":"21","author":"Kim","year":"2017","journal-title":"IEEE Commun. Lett."},{"key":"ref_34","unstructured":"Garey, M.R., and Johnson, D.S. (1990). Computers and intractability: A guide to the theory of np-completeness. W. H. Freeman and Company."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"497","DOI":"10.2307\/1910129","article-title":"An automatic method of solving discrete programming problems","volume":"28","author":"Land","year":"1960","journal-title":"Econometrica"},{"key":"ref_36","unstructured":"Clausen, J. (1997). Branch and bound algorithms-principles and examples. Parallel Comput. Optimizat., Available online: http:\/\/janders.eecg.toronto.edu\/1387\/readings\/b_and_b.pdf."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1016\/j.jnca.2014.07.038","article-title":"Heuristic methods to maximize network lifetime in directional sensor networks with adjustable sensing ranges","volume":"46","author":"Mohamadi","year":"2014","journal-title":"J. Netw. Comput. Appl."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numerische Mathematik"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1145\/321694.321699","article-title":"Theoretical improvements in algorithmic efficiency for network flow problems","volume":"19","author":"Edmonds","year":"1972","journal-title":"J. ACM (JACM)"},{"key":"ref_40","first-page":"107","article-title":"A simple algorithm to optimize maximum independent set","volume":"12","author":"Balaji","year":"2010","journal-title":"Advanc. Model. Optim."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/18\/2\/534\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T14:54:32Z","timestamp":1760194472000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/18\/2\/534"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,10]]},"references-count":40,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2018,2]]}},"alternative-id":["s18020534"],"URL":"https:\/\/doi.org\/10.3390\/s18020534","relation":{},"ISSN":["1424-8220"],"issn-type":[{"type":"electronic","value":"1424-8220"}],"subject":[],"published":{"date-parts":[[2018,2,10]]}}}