The DOI matches its Crossref record; 12 of the 12 references it cites were found in a registry or an index.
Set k-cover algorithms for energy efficient monitoring in wireless sensor networks
Open accessAbstract
Wireless sensor networks (WSNs) are emerging as an effective means for environment monitoring. This paper investigates a strategy for energy efficient monitoring in WSNs that partitions the sensors into covers, and then activates the covers iteratively in a round-robin fashion. This approach takes advantage of the overlap created when many sensors monitor a single area. Our work builds upon previous work in [13], where the model is first formulated. We have designed three approximation algorithms for a variation of the SET K-COVER problem, where the objective is to partition the sensors into covers such that the number of covers that include an area, summed over all areas, is maximized. The first algorithm is randomized and partitions the sensors, in expectation, within a fraction 1-1 e (~.63) of the optimum. We present two other deterministic approximation algorithms. One is a distributed greedy algorithm with a 1 2 approximation ratio and the other is a centralized greedy algorithm with a 1-1 e approximation ratio. We show that it is NP-Complete to guarantee better than 15 16 of the optimal coverage, indicating that all three algorithms perform well with respect to the best approximation algorithm possible in polynomial time, assuming P ≠ NP. Simulations indicate that in practice, the deterministic algorithms perform far above their worst case bounds, consistently covering more than 72% of what is covered by an optimum solution. Simulations also indicate that the increase in longevity is proportional to the amount of overlap amongst the sensors. The algorithms are fast, easy to use, and according to simulations, significantly increase the longevity of sensor networks. The randomized algorithm in particular seems quite practical.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
No free lunch theorems for optimization
Wolpert, D. H., & Macready, W. G. (1997) · IEEE Transactions on Evolutionary Computation · doi:10.1109/4235.585893 · Cited by 14,237
Motwani, R., & Raghavan, P. (1995) · Cambridge University Press eBooks · doi:10.1017/cbo9780511814075 · Cited by 5,123
(2011) · SpringerReference · doi:10.1007/springerreference_57547 · Cited by 3,190
Some optimal inapproximability results
Håstad, J. (2001) · Journal of the ACM · doi:10.1145/502090.502098 · Cited by 1,902
A Simple Parallel Algorithm for the Maximal Independent Set Problem
Luby, M. (1986) · SIAM Journal on Computing · doi:10.1137/0215074 · Cited by 1,147
Power efficient organization of wireless sensor networks
Slijepcevic, S., & Potkonjak, M. (2002) · International Conference on Communications · doi:10.1109/icc.2001.936985 · Cited by 1,028
The design of an acquisitional query processor for sensor networks
Madden, S., Franklin, M. J., Hellerstein, J. M., & Hong, W. (2003) · Proceedings of the 2003 ACM SIGMOD international conference on Management of data · doi:10.1145/872757.872817 · Cited by 927
Location in distributed ad-hoc wireless sensor networks
Savarese, C., Rabaey, J. M., & Beutel, J. (2002) · 2001 IEEE International Conference on Acoustics, Speech, and Signal Processing. Proceedings (Cat. No.01CH37221) · doi:10.1109/icassp.2001.940391 · Cited by 690
A node scheduling scheme for energy conservation in large wireless sensor networks
Tian, D., & Georganas, N. D. (2003) · Wireless Communications and Mobile Computing · doi:10.1002/wcm.116 · Cited by 271
2001 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2001)
弘典, 安., & 光太郎, 大. (2002) · Journal of the Robotics Society of Japan · doi:10.7210/jrsj.20.155 · Cited by 172
A discrete-time battery model for high-level power estimation
Benini, L., Castelli, G., Macii, A., et al. (2000) · Design, Automation and Test in Europe Conference (DATE) · doi:10.1145/343647.343694 · Cited by 154
Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses
Guruswami, V. (2003) · Algorithmica · doi:10.1007/s00453-003-1072-z · Cited by 36
Cited by
Coverage problems in sensor networks: A survey
Wang, B. (2011) · ACM Computing Surveys · doi:10.1145/1978802.1978811 · Cited by 540
Metadata
- Authors
- Abrams, Z., Goel, A., & Plotkin, S.
- Venue
- Proceedings of the 3rd international symposium on Information processing in sensor networks
- Publisher
- ACM
- Published
- 2004-04-26
- Pages
- 424-432
- OpenAlex
- W2102199239
- Cited by
- 362
- References
- 12
- FWCI
- 12.53
- Type
- conference paper
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.