Abstract
In order to detect intruders that attempt to pass through a rectangular domain, sensors are placed at nodes of a regular spaced grid laid out over the rectangle. An intruder that steps within the sensing range of a sensor will be detected. It is desired that we prevent potential attacks in either one dimension or two dimensions. A one-dimensional attack succeeds when an intruder enters from the top (North) side and exits out the bottom (South) side of the domain without being detected. Preventing attacks in two dimensions requires that we simultaneously prevent the intruder from either entering North and exiting South or entering East (left side) and exiting West (right side) undetected.
Initially, all of the sensors are working properly and the domain is fully protected, i.e., attacks will be detected, in both dimensions (assuming the grid points are such that neighboring sensors have overlapping sensing ranges and include all four boundaries of the domain). Over time, the sensors may fail and we are left with a subset of working sensors. Under these conditions we wish to (1) determine if one or two-dimensional attack detection still persists and (2) if not, restore protection by adding the least number of sensors required to ensure detection in either one or two dimensions.
Ideally, the set of currently working sensors would provide some amount of fault-tolerance. In particular, it would be advantageous if for a given k, the set of sensors maintains protection (in one or two dimensions) even if up to k of the sensors fail. This leads to the problems of (1) deciding if a subset of the sensors provides protection with up to k faults and (2) if not, finding the minimum number of grid points to add sensors to in order to achieve k fault-tolerance.
In this paper, we provide algorithms for deciding if a set sensors provides k-fault tolerant protection against attacks in both one and two dimensions, for optimally restoring k-fault tolerant protection in one dimension and for restoring protection in two dimensions (optimally for \(k=0\) and approximately otherwise).
Research supported in part by NSERC grant, and by MIUR project Security Horizons. Work partially done while the first two authors were visiting Ca’ Foscari University.
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
References
Balister, P., Bollobas, B., Sarkar, A., Kumar, S.: Reliable density estimates for coverage and connectivity in thin strips of finite length. In: Proceedings of MobiCom 2007, pp. 75–86. ACM (2007)
Borradaile, G., Klein, P.: An \(O(n\log n)\) algorithm for maximum \(st\)-flow in a directed planar graph. J. ACM 56(2), 30 (2009). Art. 9
Borradaile, G., Nayyeri, A., Zafarani, F.: Towards single face shortest vertex-disjoint paths in undirected planar graphs. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, pp. 227–238. Springer, Heidelberg (2015)
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, pp. 421–430. ACM (2008)
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)
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: Ruiz, P.M., Garcia-Luna-Aceves, J.J. (eds.) ADHOC-NOW 2009. LNCS, vol. 5793, pp. 194–212. Springer, Heidelberg (2009)
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: Wu, K., Nikolaidis, I. (eds.) ADHOC-NOW 2010. LNCS, vol. 6288, pp. 29–42. Springer, Heidelberg (2010)
Dobrev, S.: Personal communication
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. In: Spirakis, P.G., Serna, M. (eds.) CIAC 2013. LNCS, vol. 7878, pp. 170–182. Springer, Heidelberg (2013)
Henzinger, M.R., Klein, P., Rao, S., Subramanian, S.: Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci. 55(1, part 1), 3–23 (1997). 26th Annual ACM Symposium on the Theory of Computing (STOC 1994) (Montreal, PQ, 1994)
Huang, C.F., Tseng, Y.C.: The coverage problem in a wireless sensor network. In: Proceedings of the 2nd ACM International Conference on Wireless Sensor Networks and Applications, WSNA 2003, pp. 115–121. ACM (2003)
Karp, R.: On the complexity of combinatorial problems. Networks 5, 45–68 (1975)
Kumar, S., Lai, T.H., Arora, A.: Barrier coverage with wireless sensors. In: Proceedings of MobiCom 2005, pp. 284–298. ACM (2005)
Meguerdichian, S., Koushanfar, F., Potkonjak, M., Srivastava, M.B.: Coverage problems in wireless ad-hoc sensor networks. In: Proceedings of INFOCOM, vol. 3, pp. 1380–1387 (2001)
Mehrandish, M., Narayanan, L., Opatrny, J.: Minimizing the number of sensors moved on line barriers. In: Proceedings of IEEE WCNC 2011, pp. 1464–1469 (2011)
Park, T., Shi, H.: Extending the lifetime of barrier coverage by adding sensors to a bottleneck region. In: 12th IEEE Consumer Communications and Networking Conference (CCNC). IEEE (2015)
Robertson, N., Seymour, P.D.: Graph minors. VI. Disjoint paths across a disc. J. Comb. Theory Ser. B 41(1), 115–138 (1986)
Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. J. Comb. Theory Ser. B 63, 65–110 (1995)
Suurballe, J.W.: Disjoint paths in a network. Networks 4, 125–145 (1974)
Xie, H., Li, M., Wang, W., Wang, C., Li, X., Zhang, Y.: Minimal patching barrier healing strategy for barrier coverage in hybrid wsns. In: International Symposium on Personal, Indoor, and Mobile Radio Communication (PIMRC), pp. 1558–1563. IEEE (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Kranakis, E., Krizanc, D., Luccio, F.L., Smith, B. (2015). Maintaining Intruder Detection Capability in a Rectangular Domain with Sensors. In: Bose, P., Gąsieniec, L., Römer, K., Wattenhofer, R. (eds) Algorithms for Sensor Systems. ALGOSENSORS 2015. Lecture Notes in Computer Science(), vol 9536. Springer, Cham. https://doi.org/10.1007/978-3-319-28472-9_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-28472-9_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-28471-2
Online ISBN: 978-3-319-28472-9
eBook Packages: Computer ScienceComputer Science (R0)