科研之友
微信
新浪微博
Facebook
分享链接
摘要
Sweep coverage plays an important role in many applications like data gathering, sensing coverage, and devices control. In this paper, we deal with the sweep coverage problem with multiple mobile sensors to periodically cover n targets in the surveillance region. We propose three constant-factor approximations, namely, CycleSplit, HeteroCycleSplit, and PathSplit, to minimize the longest sweep period of mobile sensors under different scenarios, respectively. CycleSplit deals with the minperiod sweep coverage problem (MPSC), in which each mobile sensor works independently along a predetermined trajectory cycle. It has an approximation ratio of (5 -2/(n - m + 1)), which improves the best known approximation ratio of 5. HeteroCycleSplit is a 5 alpha - approximation. It computes the sensor routes for heterogeneous velocitymin-period sweep coverage problem (HVMPSC), where each mobile sensor has a different velocity. PathSplit is a 2-approximation for connected path minperiod sweep coverage problem (CPMPSC). It solves a variant problem of sweep coverage where we need to cover all the given edges. Besides, we also propose an optimal algorithm DP-MPSC for min-period sweep coverage problem in 1-D case. Finally, we provide various numerical experiments and comparisons with several previous work to validate the efficiency of our design.
- 出版日期2018-4
- 单位上海交通大学
