Inter-contact times (ICTs) between moving vehiclesare one of the key metrics in vehicular networks, and they are also central to forwarding algorithms and the end-to-end delay. Recent study on the tail distribution of ICTs based on theoretical mobility models and empirical trace data shows that the delaybetween two consecutive contact opportunities drops exponentially. While theoretical results facilitate problem analysis, how to design practical opportunistic forwarding protocols in vehicular networks, where messages are delivered in carry-and-forward fashion, is still unclear. In this paper, we study three large sets of Global Positioning System (GPS)traces of more than tenthousandpublic vehicles, collected from Shanghai and Shenzhen, two metropolises in China. By mining the temporal correlation and the evolution of ICTs between each pair of vehicles, we usehigher order Markov chains to characterize urban vehicular mobility patterns, which adapt as ICTs between vehicles continuously get updated. Then, the next hop for message forwarding is determinedbased on the previous ICTs. With our message forwarding strategy, it can dramatically increase delivery ratio (up to 80%) and reduce end-to-end delay (up to 50%) while generating similar network traffic comparing to current strategiesbased on the delivery probability or the expected delay.

PDF