Improved Approximation Algorithms for Connected Sensor Cover
Stefan Funke, Alex Kesselman, Fabian Kuhn, Zvi Lotker, Michael Segal
Wireless sensor networks have recently
posed many new system building challenges.
One of the main problems is energy conservation
since most of the sensors are devices with limited battery life and it
is infeasible to replenish energy via replacing batteries.
An effective approach for energy conservation
is scheduling sleep intervals for some
sensors, while the remaining sensors stay active
providing continuous service.
In this paper we consider the problem
of selecting a set of active sensors
of minimum cardinality
that maintains
sensing coverage and network connectivity.
We study different variations of this problem.
The main contribution of this paper
is a thorough investigation of algorithms for
covering an area with sensors that have fixed
locations.
PDF