We study the problem of maximizing the lifetime of a sensor network assigned to monitor a given area. Our main result is a linear time dual approximation algorithm that comes arbitrarily close to the optimal solution if we additionally allow the sensing ranges to increase by a small factor. The best previous result is superlinear and has a logarithmic approximation ratio. We also provide the first proof of the NP completeness of this specific problem.
Lifetime Maximization of Monitoring Sensor Networks
| Conference: | International Workshop on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS 2010) |
Year: | 2010 |
|---|---|---|---|
| Location: | Bordeaux, France |
Links: | |
| Date: | July 2010 |
||
| Author(s): | Peter Sanders, Dennis Schieferdecker |
||
