Sweep Coverage with Mobile Sensors
Authors:
- 19 September 2011
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Mobile Computing
- Vol. 10 (11) , 1534-1545
Abstract
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.Keywords
This publication has 29 references indexed in Scilit:
- Designing localized algorithms for barrier coverage2007
- Distributed algorithms for dynamic coverage in sensor networks2007
- The Coverage Problem in a Wireless Sensor NetworkMobile Networks and Applications, 2005
- Mobility improves coverage of sensor networks2005
- Clock synchronization for wireless sensor networks: a surveyAd Hoc Networks, 2005
- Improving Wireless Sensor Network Lifetime through Power Aware OrganizationWireless Networks, 2005
- Power efficient organization of wireless sensor networks2002
- Coverage problems in wireless ad-hoc sensor networks2002
- Mobile Sensor Network Deployment using Potential Fields: A Distributed, Scalable Solution to the Area Coverage Problem2002
- Coordinated path planning for multiple robotsRobotics and Autonomous Systems, 1998