  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 "Power Efficient Organization of Wireless Sensor
Networks" by Slijepcevic and Potkonjak, 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.
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.
