Dynamic vehicle routing for data gathering in wireless networks

We consider a dynamic vehicle routing problem in wireless networks where messages arriving randomly in time and space are collected by a mobile receiver (vehicle or a collector). The collector is responsible for receiving these messages via wireless communication by dynamically adjusting its position in the network. Our goal is to utilize a combination of wireless transmission and controlled mobility to improve the delay performance in such networks. We show that the necessary and sufficient condition for the stability of such a system is given by ρ <; 1 where ρ is the average system load. We derive a fundamental lower bound for the delay in the system. We develop algorithms that are stable for all loads ρ <; 1 and that have asymptotically optimal delay scaling. We show that the combination of mobility and wireless transmission results in a delay scaling of Θ(1/1-ρ) [theta (1/1-p)] with the system load ρ in contrast to the (1/(1-ρ)2) [1/(1-p) superscript 2)] delay scaling in the corresponding system where the collector visits each message location.National Science Foundation (U.S.) (Grant CNS-0626781)National Science Foundation (U.S.) (Grant CNS-0915988)United States. Army Research Office. Multidisciplinary University Research Initiative (Grant W911NF-08-1-0238