On Stochastic Analysis of Greedy Routing in Vehicular Networks

Even the greedy routing is widely used in wireless networks, its theoretical study is still limited in vehicle environments. In this paper, we theoretically analyze the performance of the greedy routing under three typical vehicle scenarios, i.e., the single-lane road, the multilane road, and the multilevel road. We first propose the analytical model by analyzing characteristics of traffic environments, which contain the width and multilevel features of roads. Specifically, we prove that the road-width is ignorable under certain conditions, whereas the data measured in an outdoor experiment reveal that the multilevel feature is non-ignorable because its existence dramatically degrades the transmission range. Based on the model, we analyze the routing length of the greedy routing for all scenarios in the following three aspects. 1) We derive the distribution function for the first one-hop progress. 2) We prove that routing increments are history-dependent and give one sufficient condition that ensures these increments are approximately i.i.d. 3) We calculate the routing length described by the h-hop coverage and hop count using the renewal theory. Finally, simulations are conducted to verify the accuracy of our analysis.