Mobile sensors cover more area over a fixed period of time than do the same number of stationary sensors. However, the quality of coverage (QoC) achieved by mobile sensors depends on the velocity, mobility pattern, number of mobile sensors deployed, and the dynamics of the phenomenon being sensed. The gains attained by mobile sensors over static sensors and the optimal motion strategies for mobile sensors are not well understood. In this paper, we consider the following event capture problem: the events of interest arrive at certain points in the sensor field and disappear according to known arrival and departure time distributions. An event is said to be captured if it is sensed by one of the mobile sensors before it fades away. We analyze how the QoC scales with velocity, path, and number of mobile sensors. We characterize cases where the deployment of mobile sensors has no advantage over static sensors, and find the optimal velocity pattern that a mobile sensor should adopt. We also present algorithms for two motion planning problems: 1) for a single sensor, what is the sensor trajectory and the minimum speed required to satisfy a bound on the event loss probability and 2) for sensors with fixed speed, what is the minimum number of sensors required to satisfy a bound on the event loss probability. When the robots are restricted to move along a line or a closed curve, our algorithms return the optimal velocity for the minimum velocity problem. For the minimum sensor problem, the number of sensors used is within a factor of 2 of the optimal solution. For the case where the events occur at arbitrary points on a plane, we present heuristic algorithms for the aforementioned motion planning problems and bound their performance with respect to the optimal.
Bibliographical noteFunding Information:
Manuscript received July 24, 2006; revised January 14, 2007. This paper was recommended for publication by Associate Editor G. Sukhatme and Editor K. Lynch upon evaluation of the reviewer’s comments. The work of N. Bisnik and A. A. Abouzeid was supported in part by the National Science Foundation (NSF) under Grant CNS-322956 and Grant CNS-546402. The work of V. Isler was supported in part by the NSF CCF-0634823. A preliminary version of this paper was presented at the Twelfth Annual International Conference on Mobile Computing and Networking (ACM MOBICOM), Los Angeles, CA, September 23–29, 2006.
- Mobile robot motion planning
- Mobile sensor networks
- Robot sensing systems