Complexity of Barrier Coverage with Relocatable Sensors in the Plane

Stefan Dobrev, Stephane Durocher, Mohsen Eftekhari Hesari, Konstantinos Georgiou, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, Sunil M. Shende, Jorge UrrutiaCIAC 2013 · DOI

TL;DR

This paper investigates the computational complexity of ensuring that sensors can detect intruders crossing a barrier. They show that while some scenarios with restricted sensor movement are computationally tractable, general cases involving arbitrary sensor movement and complex barrier configurations are NP-hard, highlighting the inherent difficulty in robust sensor network deployment.

What Problem Does This Paper Address?

Imagine a security perimeter, like a fence or a border, that needs to be monitored by sensors. The goal is to ensure that any intruder attempting to cross this barrier is detected. This is known as "barrier coverage." Sensors are typically placed in a circular area around them. In this paper, the researchers tackle the problem of deploying and potentially repositioning these sensors to guarantee that the entire barrier is covered.

They consider two main scenarios:

  1. Area Coverage: Sensors monitor a region, and an intruder is detected anywhere within that region.
  2. Barrier Coverage: Sensors monitor a specific line or perimeter (the barrier), and an intruder is detected only when crossing it. Barrier coverage is generally more cost-effective as it requires fewer sensors.

The core challenge lies in determining the optimal placement of sensors. Sensors can be initially scattered in the plane and then instructed to move to specific locations on the barrier. The paper focuses on three key problems:

  • Feasibility: Can we cover all barriers with the given sensors?
  • MinMax: What's the minimum possible value for the largest distance any sensor has to move to achieve coverage?
  • MinSum: What's the minimum possible total distance all sensors have to move to achieve coverage?

They also explore different sensor movement strategies:

  • Arbitrary Movement: Sensors can move to any point on the barrier.
  • Perpendicular Movement: Sensors move to the closest point on the barrier.

Methods

The paper employs a combination of theoretical computer science techniques, primarily focusing on computational complexity analysis. They use reductions from known NP-complete problems (like 3-partition and monotone 3-SAT) to prove that certain barrier coverage problems are also NP-hard. This means that for these problems, there's likely no efficient (polynomial-time) algorithm to find the optimal solution as the problem size grows.

For scenarios where problems are tractable, they propose polynomial-time algorithms. These often involve:

  • Dynamic Programming: For the MinSum problem with perpendicular movement, they develop a recursive formulation that can be solved efficiently using memoization or tabulation.
  • Binary Search: For the MinMax problem with parallel barriers, they use binary search on the possible sensor movement distances to find the optimal solution.
  • Greedy Approaches: In some cases, a greedy strategy of covering the leftmost uncovered point on a barrier with the most suitable sensor can lead to an efficient solution.

The paper also introduces a lemma that establishes necessary and sufficient conditions for coverage in specific barrier configurations, which is crucial for proving the efficiency of their algorithms.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity and algorithmic design rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Arbitrary Movement is Hard: The most significant finding is that allowing sensors to move to any position on a barrier makes the problem NP-hard, even for a single barrier and Euclidean distance. This suggests that practical sensor deployment might need to rely on more constrained movement strategies.
  • Perpendicular Movement is Tractable (Mostly): When sensors are restricted to moving to the closest point on a barrier (perpendicular movement), many problems become computationally tractable. This is a key insight for designing practical systems.
  • Parallel Barriers are Easier: Covering multiple parallel barriers with perpendicular movement is generally solvable in polynomial time for feasibility, MinMax, and MinSum problems. This is because the coverage requirements for each barrier can be analyzed somewhat independently.
  • Perpendicular Barriers are Tricky: The complexity dramatically increases when dealing with perpendicular barriers. Even the basic feasibility problem becomes NP-complete in this scenario, indicating a fundamental difficulty in coordinating sensors across orthogonal boundaries.
  • The Importance of Sensor Range and Position: The paper highlights how sensor ranges and initial positions significantly impact the complexity. Integer positions and limited sensor sizes can sometimes simplify problems, but not always enough to overcome the inherent hardness of certain configurations.

Key Results

  • NP-Hardness:
    • Feasibility, MinMax, and MinSum problems are NP-hard when sensors can move to arbitrary positions on one or more barriers.
  • Feasibility, MinMax, and MinSum problems are NP-hard for two perpendicular barriers, even with restricted sensor movement (perpendicular) and integer sensor positions.
  • Polynomial-Time Solvability:
    • MinSum and MinMax problems for a single barrier with perpendicular movement are solvable in $O(n^2)$ and $O(n \log n)$ time, respectively.
  • Feasibility, MinSum, and MinMax problems for $k$ parallel barriers with perpendicular movement are solvable in polynomial time, with specific complexities like $O(kn)$ for feasibility and $O(kn^{k+1})$ for MinSum.
  • MinMax for two parallel barriers with perpendicular movement is solvable in $O(n \log n)$ time.
  • Special Case Algorithm: An $O(n^{1.5})$ algorithm is provided for a restricted case of two perpendicular barriers forming a "non-overlapping arrangement."

Limitations and Future Work

  • Open Questions: The paper explicitly states that characterizing the exact conditions under which barrier coverage problems are polytime solvable remains an open question, especially for non-parallel barriers.
  • Approximation Algorithms: Given the NP-hardness results for arbitrary movement and perpendicular barriers, the paper suggests that approximation algorithms would be a valuable direction for future research.
  • Fixed Number of Ranges: It's an open question whether the MinMax problem becomes polynomial if there's a fixed, small number of possible sensor ranges.
  • Practical Deployment: While the paper provides theoretical insights, translating these into practical, real-world sensor network deployments would require further work, considering factors like sensor communication, energy constraints, and dynamic environments.

Summary updated

BibTeX
@inproceedings{dobrev2013complexity,
  author = {Stefan Dobrev and Stephane Durocher and Mohsen Eftekhari Hesari and Konstantinos Georgiou and Evangelos Kranakis and Danny Krizanc and Lata Narayanan and Jaroslav Opatrny and Sunil M. Shende and Jorge Urrutia},
  title = {{Complexity of Barrier Coverage with Relocatable Sensors in the Plane}},
  booktitle = {CIAC},
  year = {2013},
  doi = {10.1007/978-3-642-38233-8\_15},
}
Figure