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
International Workshop on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS 2010)
Peter Sanders, Dennis Schieferdecker