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.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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 170
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Set k-cover algorithms for energy efficient monitoring in wireless sensor networks. https://app.cochat.ai/papers/10.1145/984622.984684
- The paper
- Abrams, Z., Goel, A., & Plotkin, S. (2004). Set k-cover algorithms for energy efficient monitoring in wireless sensor networks. Proceedings of the 3rd international symposium on Information processing in sensor networks. https://doi.org/10.1145/984622.984684
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.