Set k-cover algorithms for energy efficient monitoring in wireless sensor networks

By Zoë Abrams, Ashish Goel, Serge A. Plotkin. Third International Symposium on Information Processing in Sensor Networks, 2004. IPSN 2004, 2003

396 citations recorded by the source corpus.

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 by Slijepcevic and Potkonjak (2001), 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) (/spl sim/ .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 /spl ne/ 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.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/2b1adc0cb4647f0ae9d58c48b33b75e7dce680bb

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

Connected sensor cover: self-organization of sensor networks for efficient query execution (2003, background): “Recent work in [16] considers a similar problem of partitioning the sensor network into k “covers” to maximize the sum of the coverage.”
Coverage problems in sensor networks: A survey (2011, background): “Likewise, the problem of disjoint set K-cover problem for minimum coverage breach [Abrams et al. 2004; Cheng et al. 2007; Deshpande et al.”
Optimal Value of Information in Graphical Models (2009, background): “Abrams, Goel, and Plotkin (2004) present an efﬁcient approximation algorithm with theoretical guarantees for this problem.”