2015 IEEE Global Communications Conference (GLOBECOM) · 2015 · 18 citations · 19 references
ComputingComputer ScienceAlgorithmsOptimizationSchedulingApproximation AlgorithmsCombinatorial OptimizationCoverage ControlScheduling OptimizationSensor NetworksWireless Sensor NetworksCoverage SchedulingEnergy ConsumptionGreedy ApproximationGreedy HeuristicsMinimum Energy RequirementOptimization-based Coverage Control
Sweep coverage is the problem of scheduling mobile sensors to cover a set of PoIs (Points of Interest) periodically. To improve the monitoring efficiency, multiple mobile sensors can cooperate with each other together to finish the task. With limited unrenewable battery power, how to schedule multiple mobile sensors to visit all PoIs with minimum energy consumption is a challenging problem. In this paper, we introduce an optimization problem to minimize the makespan of mobile sweep routes (M <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> SR) and prove its NP-hardness on 2D plane. We then design a greedy algorithm named GD-Sweep and an approximation named BS-Sweep to solve M <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> SR. We prove theoretically that BS-Sweep is a constant-factor approximation with approximation ratio of 6, while exhibit numerically that GD-Sweep performs better according to various simulation results. Compared with previous literature, our design can reduce the length of sweep routes more efficiently.
19
Integrated coverage and connectivity configuration in wireless sensor networks
Xiaorui Wang, Guoliang Xing, Yuanfang Zhang et al. · 2003 · 1.3K citations · Full text
Barrier coverage with wireless sensors
Santosh Kumar, Ten H. Lai, Anish Arora · 2005 · 647 citations
Designing localized algorithms for barrier coverage
Chen Ai, Santosh Kumar, Ten H. Lai · 2007 · 259 citations