Improved approximation algorithms for connected sensor cover

摘要: Wireless sensor networks have recently posed many new system building challenges. One of the main problems is energy conservation since most sensors are devices with limited battery life and it infeasible to replenish via replacing batteries. An effective approach for scheduling sleep intervals some sensors, while remaining stay active providing continuous service. In this paper we consider problem selecting a set minimum cardinality so that sensing coverage network connectivity maintained. We show greedy algorithm provides complete has an approximation factor no better than Ω(log n), where n number nodes. Then present algorithms provide approximate nodes selected constant far from optimal solution. Finally, how connect already coverage.