2012 · 74 citations · 21 references
ComputingComputer ScienceAlgorithmsOptimizationSchedulingApproximation AlgorithmsCoverage ControlDistributed Sensor NetworksSensor NetworksWireless Sensor NetworksBest ApproximationMaximum CoverageNetwork LifetimeNode SchedulingPolynomial-time Approximation SchemeTarget CoverageWireless Sensor Deployment
When a large amount of sensors are randomly deployed into a field, how can we make a sleep/activate schedule for sensors to maximize the lifetime of target coverage in the field? This is a well-known problem, called Maximum Lifetime Coverage Problem (MLCP), which has been studied extensively in the literature. It is a long-standing open problem whether MLCP has a polynomial-time constant-approximation. The best-known approximation algorithm has performance ratio 1 + ln n where n is the number of sensors in the network, which was given by Berman et. al [1]. In their work, MLCP is reduced to Minimum Weight Sensor Coverage Problem (MWSCP) which is to find the minimum total weight of sensors to cover a given area or a given set of targets with a given set of weighted sensors. In this paper, we present a polynomial-time (4 + ∈)-approximation algorithm for MWSCP and hence we obtain a polynomial-time (4 + ξ)-approximation algorithm for MLCP, where ∈ >; 0, ξ >; 0.
21
Coverage problems in wireless ad-hoc sensor networks
Saro Meguerdichian, Farinaz Koushanfar, Miodrag Potkonjak et al. · 2002 · 1.7K citations
Energy-aware wireless microsensor networks
Vijay Raghunathan, Curt Schurgers, Sung Min Park et al. · IEEE Signal Processing Magazine · 2002 · 1.7K citations
Energy-efficient target coverage in wireless sensor networks
Mihaela Cardei, My T. Thai, Yingshu Li et al. · 2005 · 987 citations