Abstract
Assume n wireless mobile sensors are initially dispersed in an ad hoc manner in a rectangular region. They are required to move to final locations so that they can detect any intruder crossing the region in a direction parallel to the sides of the rectangle, and thus provide weak barrier coverage of the region. We study three optimization problems related to the movement of sensors to achieve weak barrier coverage: minimizing the number of sensors moved (MinNum), minimizing the average distance moved by the sensors (MinSum), and minimizing the maximum distance moved by the sensors (MinMax). We give an \(O(n^{3/2})\) time algorithm for the MinNum problem for sensors of diameter 1 that are initially placed at integer positions; in contrast we show that the problem is NP-hard even for sensors of diameter 2 that are initially placed at integer positions. We show that the MinSum problem is solvable in \(O(n \log n)\) time for homogeneous range sensors in arbitrary initial positions for the Manhattan metric, while it is NP-hard for heterogeneous sensor ranges for both Manhattan and Euclidean metrics. Finally, we prove that even very restricted homogeneous versions of the MinMax problem are NP-hard.
Research supported by NSERC, Canada.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Andrews, A.M., Wang, H.: Minimizing the aggregate movements for interval coverage. Algorithmica 78(1), 47–85 (2017). doi:10.1007/s00453-016-0153-8
Balister, P., Bollobas, B., Sarkar, A., Kumar, S.: Reliable density estimates for coverage and connectivity in thin strips of finite length. In: ACM International Conference on Mobile Computing and Networking, pp. 75–86 (2007)
Ban, D., Jiang, J., Yang, W., Dou, W., Yi, H.: Strong \(k\)-barrier coverage with mobile sensors. In: Proceedings of International Wireless Communications and Mobile Computing Conference, pp. 68–72 (2010)
Berman, P., Karpinski, M.: On some tighter inapproximability results (extended abstract). In: Wiedermann, J., Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 200–209. Springer, Heidelberg (1999). doi:10.1007/3-540-48523-6_17
Bhattacharya, B., Burmester, M., Hu, Y., Kranakis, E., Shi, Q., Wiese, A.: Optimal movement of mobile sensors for barrier coverage of a planar region. TCS 410(52), 5515–5528 (2009)
Chen, D.Z., Gu, Y., Li, J., Wang, H.: Algorithms on minimizing the maximum sensor movement for barrier coverage of a linear domain. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol. 7357, pp. 177–188. Springer, Heidelberg (2012). doi:10.1007/978-3-642-31155-0_16
Czyzowicz, J., et al.: On minimizing the maximum sensor movement for barrier coverage of a line segment. In: Ruiz, P.M., Garcia-Luna-Aceves, J.J. (eds.) ADHOC-NOW 2009. LNCS, vol. 5793, pp. 194–212. Springer, Heidelberg (2009). doi:10.1007/978-3-642-04383-3_15
Czyzowicz, J., et al.: On minimizing the sum of sensor movements for barrier coverage of a line segment. In: Nikolaidis, I., Wu, K. (eds.) ADHOC-NOW 2010. LNCS, vol. 6288, pp. 29–42. Springer, Heidelberg (2010). doi:10.1007/978-3-642-14785-2_3
Dobrev, S., Durocher, S., Eftekhari, M., Georgiou, K., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J., Shende, S., Urrutia, J.: Complexity of barrier coverage with relocatable sensors in the plane. Theoret. Comput. Sci. 579, 64–73 (2015)
Eftekhari, M., Flocchini, P., Narayanan, L., Opatrny, J., Santoro, N.: Distributed barrier coverage with relocatable sensors. In: Halldórsson, M.M. (ed.) SIROCCO 2014. LNCS, vol. 8576, pp. 235–249. Springer, Cham (2014). doi:10.1007/978-3-319-09620-9_19
Eftekhari, M., Kranakis, E., Krizanc, D., Morales-Ponce, O., Narayanan, L., Opatrny, J., Shende, S.: Distributed algorithms for barrier coverage using relocatable sensors. Distrib. Comput. 29(5), 361–376 (2016)
Eftekhari, M., Narayanan, L., Opatrny, J.: On multi-round sensor deployment for barrier coverage. In: Proceedings of 10th IEEE International Conference on Mobile Ad-hoc and Sensor Systems (IEEE MASS), pp. 310–318 (2013)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., New York (1979)
Habib, M.: Stochastic barrier coverage in wireless sensor networks based on distributed learning automata. Comput. Commun. 55, 51–61 (2015)
Kranakis, E., Krizanc, D., Luccio, F.L., Smith, B.: Maintaining intruder detection capability in a rectangular domain with sensors. In: Bose, P., Gąsieniec, L.A., Römer, K., Wattenhofer, R. (eds.) ALGOSENSORS 2015. LNCS, vol. 9536, pp. 27–40. Springer, Cham (2015). doi:10.1007/978-3-319-28472-9_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, pp. 284–298 (2005)
Li, L., Zhang, B., Shen, X., Zheng, J., Yao, Z.: A study on the weak barrier coverage problem in wireless sensor networks. Comput. Netw. 55, 711–721 (2011)
Mehrandish, M., Narayanan, L., Opatrny, J.: Minimizing the number of sensors moved on line barriers. In: Proceedings of IEEE WCNC, pp. 653–658 (2011)
Yan, G., Qiao, D.: Multi-round sensor deployment for guaranteed barrier coverage. In: Proceedings of IEEE INFOCOM 2010, pp. 2462–2470 (2010)
Dobrev, S., Kranakis, E., Krizanc, D., Lafond, M., Manuch, J., Narayanan, L., Opatrny, J., Stacho, L.: Weak coverage of a rectangular barrier. arXiv 1701.07294 (2017)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Dobrev, S. et al. (2017). Weak Coverage of a Rectangular Barrier. In: Fotakis, D., Pagourtzis, A., Paschos, V. (eds) Algorithms and Complexity. CIAC 2017. Lecture Notes in Computer Science(), vol 10236. Springer, Cham. https://doi.org/10.1007/978-3-319-57586-5_17
Download citation
DOI: https://doi.org/10.1007/978-3-319-57586-5_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-57585-8
Online ISBN: 978-3-319-57586-5
eBook Packages: Computer ScienceComputer Science (R0)