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 re...

Full description

Saved in:
Bibliographic Details
Published in:IEEE/ACM transactions on networking 2017-12, Vol.25 (6), p.3616-3627
Main Authors: Gao, Xiaofeng, Chen, Zhiyin, Wu, Fan, Chen, Guihai
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Algorithms
Approximation
Approximation algorithms
Energy consumption
Euclidean geometry
Euclidean space
Mathematical analysis
Mobile communication
Mobile computing
Mobile sensor networks
Polynomials
PTAS algorithm
Remote sensors
Sensors
Surveillance
target coverage
Wireless sensor networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 polynomial-time approximation scheme, named Energy Effective Movement Algorithm (EEMA). We prove that the approximation ratio of EEMA is 1 + ε and the time complexity is n O(1/ε 2 ) . We also propose a distributed version of EEMA (D-EEMA) for large-scale networks where EEMA is not efficient enough in practice. Finally, we conduct experiments to validate the efficiency and effectiveness of EEMA and D-EEMA.
ISSN:1063-6692
1558-2566
DOI:10.1109/TNET.2017.2756925