Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
Maximizing Barrier Coverage Lifetime with Static Sensors
verfasst von : Menachem Poss, Dror Rawitz
Erschienen in: Algorithms for Sensor Systems
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We study variants of the Strip Cover problem (SC) in which sensors with limited battery power are deployed on a line barrier, and the goal is to cover the barrier as long as possible. The energy consumption of a sensor depends on its sensing radius: energy is drained in inverse proportion to the sensor radius raised to a constant exponent \(\alpha \ge 1\). In the Set Once Strip Cover (OnceSC) the radius of each sensor can be set once, and the sensor can be activated at any time. \(\textsc {SC} _k\) and \(\textsc {OnceSC} _k\) are variants of SC and OnceSC, resp., in which each sensor is associated with a set of at most k predetermined radii.
It was previously known that OnceSC is NP-hard when \(\alpha = 1\), and the complexity of the case where \(\alpha >1\) remained open. We extend the above mentioned NP-hardness result in two ways: we show that OnceSC is NP-hard for every \(\alpha > 1\) and that OnceSC is strongly NP-hard for \(\alpha = 1\). In addition, we show that \(\textsc {OnceSC} _k\), for \(k \ge 2\), is NP-hard, for any \(\alpha \ge 1\), even for uniform radii sets. On the positive side, we present (i) a \(5\gamma ^\alpha \)-approximation algorithm for \(\textsc {OnceSC} _k\), for \(k \ge 1\), where \(\gamma \) is the maximum ratio between two radii associated with the same sensor; (ii) a 5-approximation algorithm for \(\textsc {SC} _k\), for every \(k \ge 1\); and (iii) a \(5 \cdot 2^\alpha \)-approximation algorithm for Strip Cover. Finally, we present an \(O(n \log n)\)-time algorithm for a variant of \(\textsc {OnceSC} _k\) in which all sensors must be activated at the same time.