Abstract
In this paper, we address the problem of low-latency routing in a vehicular highway network. To
cover long highways while minimizing the number of required roadside access points, we utilize vehicle-to-vehicle communication to propagate data in the network. Vehicular networks are highly dynamic, and
hence routing algorithms that require global network state information or centralized coordination are
not suitable for such networks. Instead, we develop a novel distributed routing algorithm that requires
minimal coordination among vehicles, while achieving a highly efficient throughput-delay tradeoff.
Specifically, we show that the proposed algorithm achieves a throughput that is within a factor of 1=e
of the throughput of an algorithm that centrally coordinates vehicle transmissions in a highly dense
network, and yet its end-to-end delay is approximately half of that of a widely studied ALOHA-based
randomized routing algorithm. We evaluate our algorithm analytically and through simulations and
compare its throughput-delay performance against the ALOHA-based randomized routing.
Refereed
Yes
