### 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 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(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 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.

Original language | English (US) |
---|---|

Title of host publication | Algorithms and Complexity - 10th International Conference, CIAC 2017, Proceedings |

Editors | Dimitris Fotakis, Aris Pagourtzis, Vangelis Th. Paschos |

Publisher | Springer Verlag |

Pages | 196-208 |

Number of pages | 13 |

ISBN (Print) | 9783319575858 |

DOIs | |

State | Published - Jan 1 2017 |

Event | 10th International Conference on Algorithms and Complexity, CIAC 2017 - Athens, Greece Duration: May 24 2017 → May 26 2017 |

### Publication series

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

Volume | 10236 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

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

Country | Greece |

City | Athens |

Period | 5/24/17 → 5/26/17 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Weak coverage of a rectangular barrier'. Together they form a unique fingerprint.

## Cite this

*Algorithms and Complexity - 10th International Conference, CIAC 2017, Proceedings*(pp. 196-208). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10236 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-57586-5_17