Improved Approximation Algorithms for Connected Sensor Cover

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
so that
sensing coverage and network connectivity
are maintained.
We show that the greedy algorithm
that provides complete coverage has an
approximation factor of $\Omega(\log n)$,
where $n$ is the number of sensor nodes.
Then we present algorithms
that provide approximate coverage while
the number of nodes selected is a constant
factor far from the optimal solution.

Joint work with Stefan Funke, Zvi Lotker and Michael Segal.