期刊
IEEE TRANSACTIONS ON MOBILE COMPUTING
卷 10, 期 11, 页码 1534-1545出版社
IEEE COMPUTER SOC
DOI: 10.1109/TMC.2010.237
关键词
Sweep coverage; mobile sensors; dynamic coverage; DSWEEP
资金
- Nanyang Technological University of Singapore [SUG COE_ SUG/RSS_20Aug2010_13/14]
- US National Science Foundation [CNS-0832120, CNS-1035894]
- National Natural Science Foundation of China [60828003, 60903224]
- program for the Zhejiang Provincial Key Innovative Research Team
- program for the Zhejiang Provincial Overseas High-Level Talents (One-Hundred Talents Program)
- Tsinghua National Laboratory for Information Science and Technology (TNList)
Many efforts have been made for addressing coverage problems in sensor networks. They fall into two categories, full coverage and barrier coverage, featured as static coverage. In this work, we study a new coverage scenario, sweep coverage, which differs with the previous static coverage. In sweep coverage, we only need to monitor certain points of interest (POIs) periodically so the coverage at each POI is time-variant, and thus we are able to utilize a small number of mobile sensors to achieve sweep coverage among a much larger number of POIs. We investigate the definitions and model for sweep coverage. Given a set of POIs and their sweep period requirements, we prove that determining the minimum number of required sensors (min-sensor sweep-coverage problem) is NP-hard, and it cannot be approximated within a factor of 2. We propose a centralized algorithm with constant approximation ratio 3 for the min-sensor sweep-coverage problem. We further characterize the nonlocality of the problem and design a distributed sweep algorithm, DSWEEP, cooperating sensors to provide efficiency with the best effort. We conduct extensive simulations to study the performance of the proposed algorithms. Our simulations show that DSWEEP outperforms the randomized scheme in both effectiveness and efficiency.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据