Set K-Cover Algorithms for Energy Efficient Monitoring in Wireless Sensor Networks

Details Set K-Cover Algorithms for Energy Efficient Monitoring in Wireless Sensor Networks Set K-Cover Algorithms for Energy Efficient Monitoring in Wireless Sensor Networks

2003-11-20

arxiv.org/abs/cs/0311030v1

Computer Science

Data Structures and Algorithms

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Set K-Cover Algorithms for Energy Efficient Monitoring in Wireless Sensor Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Set K-Cover Algorithms for Energy Efficient Monitoring in Wireless Sensor Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Set K-Cover Algorithms for Energy Efficient Monitoring in Wireless Sensor Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-112302