Research On Trajectory-Based Routing For Vehicular Ad Hoc Networks

A vehicular network is a network of vehicles which communicate with each othervia wireless communications. Vehicular networks have many appealing applicationssuch as driving safety, Internet access, intelligent transport, and infrastructure moni-toring. Efcient data delivery is a great challenge in vehicular networks because offrequent network disruption, fast topological change and mobility uncertainty. The ve-hicular trajectory knowledge plays a key role in data delivery. Existing algorithms havelargely made predictions on the trajectory with coarse-grained patterns such as spatialdistribution or/and the inter-meeting time distribution, which has led to poor data de-livery performance. In this paper, wemine the extensivetrace datasets of vehiclesin anurbanenvironmentthroughconditionalentropyanalysis,wefndthatthereexistsstrongspatio-temporalregularity. Byextractingmobilepatternsfromhistoricaltraces, wede-velop accurate trajectory predictions by using multiple order Markov chains. Based onan analytical model, we theoretically derive packet delivery probability with predictedtrajectories. We then propose routing algorithms taking full advantage of predictedvehicle trajectories.Moreover, Deploying roadside access points (APs) or an infrastructure can im-prove data delivery. Our empirical results from real trace driven simulations showthat deploying APs produces up to5x performance gain in delivery ratio and reducesdelivery delay by as much as35%with simple routing. However, we also fnd thatbufer resources at the APs become a critical factor and poor bufer allocation leads tomarginalperformancegainforinter-vehiclerouting. Motivatedbythisimportantobser-vation, we investigate the optimal infrastructure-assisted routing for inter-vehicle datadelivery. It remains a challenging issue for two major reasons. First, the addition of APs dramatically changes delivery opportunities between vehicles, which has not beenwell understood by existing work. Second, packet forwarding and bufer allocation areinter-dependent and should be addressed together. To tackle the challenges, we frstcharacterize packet delivery probability as a function of predicted vehicle trajectoriesandAPlocations. Then, weformulatethecoexistingproblemofpacketforwardingandbufer allocation as an optimization problem and show that it is a knapsack problem.We design a global algorithm to solve this optimization problem.Combining the two motivations above, we propose a distributed algorithm forpacket forwarding and bufer allocation in which each vehicle and the APs make de-cisions locally. We evaluate the algorithms with extensive trace driven simulations,based on the trace datasets collected in Shanghai. The results demonstrate that ouralgorithm considerably outperforms other algorithms in terms of delivery probabilityand delivery efciency.