Title :
A Route Scheduling Algorithm for the Sweep Coverage Problem
Author :
Zhiyin Chen ; Shuang Wu ; Xudong Zhu ; Xiaofeng Gao ; Jian Gu ; Guihai Chen
Author_Institution :
Dept. of Comput. Sci. & Eng., Shanghai Jiao Tong Univ., Shanghai, China
fDate :
June 29 2015-July 2 2015
Abstract :
In order to decrease the sweep cycle and the number of mobile sensors required, we propose a route scheduling problem in this paper which is the first to consider the effect of sensing range. We prove that the Distance-Sensitive-Route Scheduling(DSRS) problem is NP-hard, and consider two different scenarios: the single kissing-point case and the general case. For different cases, We propose three corresponding approximation algorithms ROSE, G-ROSE, D-ROSE.
Keywords :
approximation theory; mobility management (mobile radio); optimisation; telecommunication network routing; telecommunication scheduling; wireless sensor networks; D-ROSE; DSRS problem; G-ROSE; NP-hard problem; ROSE; approximation algorithm; distance sensitive route scheduling; mobile sensors; sweep coverage problem; sweep cycle; Approximation algorithms; Approximation methods; Conferences; Mobile communication; Scheduling; Scheduling algorithms; Sensors;
Conference_Titel :
Distributed Computing Systems (ICDCS), 2015 IEEE 35th International Conference on
Conference_Location :
Columbus, OH
DOI :
10.1109/ICDCS.2015.91
