Shorten the Trajectory of Mobile Sensors in Sweep Coverage Problem
Yuchen Feng, Xiaofeng Gao, Fan Wu, Guihai Chen · 2015 IEEE Global Communications Conference (GLOBECOM) · 2015
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 (M3SR) 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 M3SR. 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.