extended-abstract

Set it and forget it - approximating the set once strip cover problem

Authors:

Dror RawitzAuthors Info & Claims

SPAA '13: Proceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures

Pages 105 - 107

https://doi.org/10.1145/2486159.2486162

Published: 23 July 2013 Publication History

Abstract

In the Set Once Strip Cover problem n wireless sensors are deployed over a one-dimensional region. Each sensor has a battery that drains in inverse proportion to a radius that can be set just once, but activated at any time. The problem is to find an assignment of radii and activation times that maximizes the length of time during which the entire region is covered. We show that this problem is NP-hard. We also show that the approximation ratio of Round Robin, the algorithm in which the sensors take turns covering the entire region, is 3/2 in both Set Once Strip Cover and the more general Strip Cover problem, in which each radius may be set finitely-many times. Moreover, we show that the more general class of duty cycle algorithms, in which groups of sensors take turns covering the entire region, can do no better. Finally, we give an polynomial time algorithm that solves the related Set Radius Strip Cover problem, in which sensors must be activated immediately.

References

[1]

Z. Abrams, A. Goel, and S. A. Plotkin. Set k-cover algorithms for energy efficient monitoring in wireless sensor networks. In IPSN, pages 424--432, 2004.

Digital Library

[2]

G. Aloupis, J. Cardinal, S. Collette, S. Langerman, D. Orden, and P. Ramos. Decomposition of multiple coverings into more parts. Discrete & Computational Geometry, 44(3):706--723, 2010.

Digital Library

[3]

A. Bar-Noy and B. Baumer. Maximizing network lifetime on the line with adjustable sensing ranges. In ALGOSENSORS, volume 7111 of LNCS, pages 28--41, 2011.

Digital Library

[4]

A. Bar-Noy, B. Baumer, and D. Rawitz. Set it and forget it: Approximating the set once strip cover problem. http://arxiv.org/abs/1204.1082.

Digital Library

[5]

A. Bar-Noy, B. Baumer, and D. Rawitz. Changing of the guards: Strip cover with duty cycling. In SIROCCO, volume 7355 of LNCS, pages 36--47, 2012.

Digital Library

[6]

A. Bar-Noy, T. Brown, M. Johnson, and O. Liu. Cheap or Flexible Sensor Coverage. In DCOSS, pages 245--258, 2009.

Digital Library

[7]

A. Buchsbaum, A. Efrat, S. Jain, S. Venkatasubramanian, and K. Yi. Restricted strip covering and the sensor cover problem. In SODA, pages 1056--1063, 2007.

Digital Library

[8]

M. Cardei and D. Du. Improving wireless sensor network lifetime through power aware organization. Wireless Networks, 11(3):333--340, 2005.

Digital Library

[9]

M. Cardei and J. Wu. Coverage in wireless sensor networks. Handbook of Sensor Networks, 2004.

[10]

M. Cardei, J. Wu, and M. Lu. Improving network lifetime using sensors with adjustable sensing ranges. Int. J. Sensor Networks, 1(1/2):41--49, 2006.

Digital Library

[11]

M. Cardei, J. Wu, M. Lu, and M. Pervaiz. Maximum network lifetime in wireless sensor networks with adjustable sensing ranges. In WiMob (3), pages 438--445, 2005.

[12]

E. W. Chambers, S. P. Fekete, H.-F. Hoffmann, D. Marinakis, J. S. B. Mitchell, V. Srinivasan, U. Stege, and S. Whitesides. Connecting a set of circles with minimum sum of radii. In WADS, volume 6844 of LNCS, pages 183--194, 2011.

Digital Library

[13]

M. Gibson and K. Varadarajan. Decomposing coverings and the planar sensor cover problem. In FOCS, pages 159--168, 2009.

Digital Library

[14]

S. Kumar, T.-H. Lai, and A. Arora. Barrier coverage with wireless sensors. Wireless Networks, 13(6):817--834, 2007.

Digital Library

[15]

N. Lev-Tov and D. Peleg. Polynomial time approximation schemes for base station coverage with minimum total radii. Computer Networks, 47(4):489--501, 2005.

Digital Library

[16]

J. Pach. Covering the plane with convex polygons. Discrete & Computational Geometry, 1(1):73--81, 1986.

Digital Library

[17]

J. Pach and G. Tóth. Decomposition of multiple coverings into many parts. Computational Geometry: Theory and Applications, 42(2):127--133, 2009.

Digital Library

[18]

M. A. Perillo and W. B. Heinzelman. Optimal sensor management under energy and reliability constraints. In WCNC, pages 1621--1626, 2003.

[19]

A. Saipulla, C. Westphal, B. Liu, and J. Wang. Barrier coverage of line-based deployed wireless sensor networks. In INFOCOM, pages 127--135, 2009.

[20]

S. Slijepcevic and M. Potkonjak. Power efficient organization of wireless sensor networks. In ICC, pages 472--476, 2001.

[21]

Y. Taniguchi, T. Kitani, and K. Leibnitz. A uniform airdrop deployment method for large-scale wireless sensor networks. IJSNet, 9(3/4):182--191, 2011.

Digital Library

[22]

L. Wang and Y. Xiao. A survey of energy-efficient scheduling mechanisms in sensor networks. Mobile Networks and Applications, 11(5):723--740, 2006.

Digital Library

Cited By

Poss MRawitz D(2017)Maximizing Barrier Coverage Lifetime with Static SensorsAlgorithms for Sensor Systems10.1007/978-3-319-72751-6_15(198-210)Online publication date: 31-Dec-2017
https://doi.org/10.1007/978-3-319-72751-6_15
Bar-Noy ABaumer B(2015)Average Case Network Lifetime on an Interval with Adjustable Sensing RangesAlgorithmica10.1007/s00453-013-9853-572:1(148-166)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1007/s00453-013-9853-5
Bar-Noy ARawitz DTerlecky P(2015)“Green” Barrier Coverage with Mobile SensorsAlgorithms and Complexity10.1007/978-3-319-18173-8_2(33-46)Online publication date: 16-May-2015
https://doi.org/10.1007/978-3-319-18173-8_2
Show More Cited By

Index Terms

Set it and forget it - approximating the set once strip cover problem
1. Networks
  1. Network types
    1. Mobile networks
    2. Wireless access networks
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Recommendations

Set It and Forget It: Approximating the Set Once Strip Cover Problem

We consider the Set Once Strip Cover problem, in which n wireless sensors are deployed over a one-dimensional region. Each sensor has a fixed battery that drains in inverse proportion to a radius that can be set just once, but activated at any time. The ...
Maximizing barrier coverage lifetime with static sensors
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 ... $_{}$ $_{}$ $_{}$ $^{}$ $_{}$ $_{}$ $_{}$
Minimum k, ω-angle barrier coverage in wireless camera sensor networks

Barrier coverage is an important issue in wireless sensor networks, which guarantees to detect any intruder attempting to cross a barrier or penetrating a protected region monitored by sensors. However, the barrier coverage problem in wireless camera ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '13: Proceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures

July 2013

348 pages

ISBN:9781450315722

DOI:10.1145/2486159

General Chair:
Guy Blelloch
Carnegie Mellon University, USA
,
Program Chair:
Berthold Vöcking
RWTH Aachen University, Germany

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Extended-abstract

Conference

SPAA '13

Sponsor:

SPAA '13: 25th ACM Symposium on Parallelism in Algorithms and Architectures

July 23 - 25, 2013

Québec, Montréal, Canada

Acceptance Rates

SPAA '13 Paper Acceptance Rate 31 of 130 submissions, 24%;

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
85
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Poss MRawitz D(2017)Maximizing Barrier Coverage Lifetime with Static SensorsAlgorithms for Sensor Systems10.1007/978-3-319-72751-6_15(198-210)Online publication date: 31-Dec-2017
https://doi.org/10.1007/978-3-319-72751-6_15
Bar-Noy ABaumer B(2015)Average Case Network Lifetime on an Interval with Adjustable Sensing RangesAlgorithmica10.1007/s00453-013-9853-572:1(148-166)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1007/s00453-013-9853-5
Bar-Noy ARawitz DTerlecky P(2015)“Green” Barrier Coverage with Mobile SensorsAlgorithms and Complexity10.1007/978-3-319-18173-8_2(33-46)Online publication date: 16-May-2015
https://doi.org/10.1007/978-3-319-18173-8_2
Bar-Noy ABaumer BRawitz DBlelloch GVöcking B(2013)Set it and forget it - approximating the set once strip cover problemProceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures10.1145/2486159.2486162(105-107)Online publication date: 23-Jul-2013
https://dl.acm.org/doi/10.1145/2486159.2486162
Bar-Noy ARawitz DTerlecky P(2013)Maximizing Barrier Coverage Lifetime with Mobile SensorsAlgorithms – ESA 201310.1007/978-3-642-40450-4_9(97-108)Online publication date: 2013
https://doi.org/10.1007/978-3-642-40450-4_9
Bar-Noy ABaumer BRawitz D(2012)Changing of the Guards: Strip Cover with Duty CyclingStructural Information and Communication Complexity10.1007/978-3-642-31104-8_4(36-47)Online publication date: 2012
https://doi.org/10.1007/978-3-642-31104-8_4

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents