TY - GEN

T1 - Weak coverage of a rectangular barrier

AU - Dobrev, Stefan

AU - Kranakis, Evangelos

AU - Krizanc, Danny

AU - Lafond, Manuel

AU - Maňnuch, Jan

AU - Narayanan, Lata

AU - Opatrny, Jaroslav

AU - Shende, Sunil

AU - Stacho, Ladislav

N1 - Funding Information:
Research supported by NSERC, Canada.
Publisher Copyright:
© Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

N2 - 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 bar-rier 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(n3/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 posi-tions. We show that the MinSum problem is solvable in O(n log n) time for homogeneous range sensors in arbitrary initial positions for the Man-hattan 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.

AB - 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 bar-rier 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(n3/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 posi-tions. We show that the MinSum problem is solvable in O(n log n) time for homogeneous range sensors in arbitrary initial positions for the Man-hattan 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.

UR - http://www.scopus.com/inward/record.url?scp=85018448074&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85018448074&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-57586-5_17

DO - 10.1007/978-3-319-57586-5_17

M3 - Conference contribution

AN - SCOPUS:85018448074

SN - 9783319575858

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 196

EP - 208

BT - Algorithms and Complexity - 10th International Conference, CIAC 2017, Proceedings

A2 - Fotakis, Dimitris

A2 - Pagourtzis, Aris

A2 - Paschos, Vangelis Th.

PB - Springer Verlag

T2 - 10th International Conference on Algorithms and Complexity, CIAC 2017

Y2 - 24 May 2017 through 26 May 2017

ER -