Energy Efficient Algorithms for k-Sink Minimum Movement Target Coverage Problem in Mobile Sensor Network

Energy consumption is a fundamental and critical issue in wireless sensor networks. Mobile sensors consume much more energy during the movement than that during the communication or sensing process. Thus how to schedule mobile sensors and minimize their moving distance, while keeping the coverage requirement has great significance to researchers. In this paper, we study the target coverage problem in mobile sensor networks where all the targets need to be covered by sensors continuously. Our goal is to minimize the moving distance of sensors to cover all targets in the surveillance region, which is in Euclidean space. Here initially all the sensors are located at k base stations. Thus, we define this problem as k-Sink Minimum Movement Target Coverage. To solve this problem, we propose a polynomialtime approximation scheme, named Energy Effective Movement Algorithm (EEMA). We prove that the approximation ratio of EEMA is 1 + epsilon and the time complexity is n(O(1/epsilon 2)). We also propose a distributed version of EEMA (D-EEMA) for largescale networks where EEMA is not efficient enough in practice. Finally, we conduct experiments to validate the efficiency and effectiveness of EEMA and D-EEMA.