Efficient Scheduling Strategies for Mobile Sensors in Sweep Coverage Problem

摘要

Nowadays, with the development of micro-electro- mechanical technologies, sweep coverage are more and more popular in wireless sensor networks, which is also applied widely in other scenarios, such as message ferrying and data routing in the ad-hoc network. In order to reduce the sweep cycle and the number of required mobile sensors, we propose the Distance-Sensitive-Route-Scheduling (DSRS) problem, which is the first to consider the effect of sensing range. We prove that DSRS is NP-complete, and consider two different scenarios: the single kissing-point case and the general case. The former case requires a mobile sensor to change its moving direction after visiting a target. Correspondingly, we propose an approximation ROSE to schedule the routes of mobile sensors efficiently. For the latter general case, we present another approximation G- ROSE based on ROSE. We further characterize the non- locality property and design a distributed sweep algorithm D-ROSE, cooperating sensors to guarantee the required sweep requirements with the best effort. Our algorithms is scalable to different sweep coverage problems involving route schedules. We compare our algorithms with several previous algorithms, and the simulation results show that our algorithms greatly outperform other works especially with large sensing range, which can be improved up to 45%.