Maximizing barrier coverage lifetime with static sensors

Menachem Poss () and Dror Rawitz ()
Additional contact information
Menachem Poss: Bar-Ilan University
Dror Rawitz: Bar-Ilan University

Journal of Scheduling, 2022, vol. 25, issue 5, No 3, 535-545

Abstract: 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 proportion to the sensor radius raised to a constant exponent $$\alpha \ge 1$$ α ≥ 1 . In the Set Once Strip Cover problem (OnceSC), the radius of each sensor can be set once, and the sensor can be activated at any time. $$\textsc {SC} _k$$ SC k and $$\textsc {OnceSC} _k$$ O N C E SC k are variants of SC and OnceSC, respectively, 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$$ α = 1 , and the complexity of the case where $$\alpha >1$$ α > 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$$ α > 1 and that OnceSC is strongly NP-hard for $$\alpha = 1$$ α = 1 . In addition, we show that $$\textsc {OnceSC} _k$$ O N C E SC k , for $$k \ge 2$$ k ≥ 2 , is NP-hard, for any $$\alpha \ge 1$$ α ≥ 1 , even for uniform radii sets. On the positive side, we present (i) a $$5\gamma ^\alpha $$ 5 γ α -approximation algorithm for $$\textsc {OnceSC} _k$$ O N C E SC k , for $$k \ge 1$$ k ≥ 1 , where $$\gamma $$ γ is the maximum ratio between two radii associated with the same sensor; (ii) a 5-approximation algorithm for $$\textsc {SC} _k$$ SC k , for every $$k \ge 1$$ k ≥ 1 ; and (iii) a $$(5+\varepsilon )$$ ( 5 + ε ) -approximation algorithm for Strip Cover, for any constant $$\varepsilon >0$$ ε > 0 . Finally, we present an $$O(n \log n)$$ O ( n log n ) -time algorithm for a variant of $$\textsc {OnceSC} _k$$ O N C E SC k in which all sensors must be activated at the same time.

Keywords: Approximation algorithm; Barrier coverage; Network lifetime; Sensor networks; Strip cover (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-022-00736-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:25:y:2022:i:5:d:10.1007_s10951-022-00736-8

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-022-00736-8

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().