Research On Routing Algorithms For Wireless Vehicular Ad-hoc Networks

According to the statistics released in January 2017 by the Ministry of Public Security and the traffic management bureau of China,the number of automobiles reached 290 million at the end of 2016 in China.The large number of vehicles brings big pressure to the national transportation system and results in serious safety problems.As the rapid development and popularity of the intelligent vehicular on-board units,governmental,industrial and university research efforts have created significant opportunities for applying vehicular ad hoc networking techniques to the improvement of transportation safety and environment.For example,some intelligent transportation system(ITS)projects all over the world are the U.S.IntelliDrive(sm),and VSC,Japanese Smartway,ASV and ITS-safety2010,and European SAFESPOT.Moreover,the applications supported by the vehicular ad hoc networks have been extended to driving assist,infortainment,crowdsensing and urban mornitoring.Inspired by the promising applications and potential benefits of vehicular ad hoc networks,research interests arise on networking and other surrounding technologies.Routing is one of the most important technologies,which supports efficient information transmission.Efficient routing algorithm design is highly challenging as well because of the unique characteristics of vehicular ad hoc networks,including large network scale,highly dynamic network topology,and the opportunistic and unreliable wireless inter-vehicle communication.From the aspect of different application requirements,this dissertation classifies the stateof-the-art routing algorithms for vehicular ad hoc networks and provides a comprehensive survey.First,to improve transportation safety and avoid accidents,broadcast routing algorithms are used.The research on existing broadcast schemes are comprehensive and in-depth due to the significant importance of the safety message transmission.Second,for the applications of traffic management,navigation and infortainment,unicast and multicast are used.The state-ofthe-art unicast algorithms apply road network,real-time traffic density,roadside units,vehicle locations and trajectories to improve the multi-hop unicast performance.However,the fairness among multiple sources has not been studied by existing unicast algorithms.As to multicast,it is more adaptive and efficient than unicast and broadcast,while more complex and harder to develop.Most of the existing multicast algorithms are based on fixed data transmitting topology designed for traditional ad hoc networks,which are not fit for highly dynamic vehicular ad hoc networks.Finally,the routing algorithms for sensing data routing and collecting make use of roadside units,architectural data transmission,network coding,data priority,data aggregation,and cellular network to improve data collection performance.Existing studies lack the trade-off between data quality and transmission overhead.In summary,there are several problems for the state-of-the-art routing algorithms,i.e.,the poor performance of fixed transmission topology based multicast algorithms,unfairness among multiple sources,lack of trade-off between data quality and transmission overhead.Accordingly,this dissertation includes the following three research results.(1)Vehicular trajectory based multicast algorithm,proposes a“multicast metric”to measure the delivery ability of a vehicle for the multiple destinations of a given multicast message.It is highly challenging to compute the multi-hop delivery probability in a distributed manner based on merely the vehicular trajectories.The proposed algorithm computes the multicast metric of a vehicle by estimating the probabilities of inter-vehicle encounters based on vehicular travel time formulation and vehicular encounter patterns analysis.Based on trace-driven simulations,we evaluate the performance of the proposed algorithm and the results demonstrate its efficacy.(2)Network coding based multi-source convergecast algorithm,reveals the unfairness of the throughput among multiple sources.To improve the fairness,there exist several challenges,i.e.,the contact graph construction and the inter-vehicle contacts allocation,and the network throughput optimization with minimized throughput diversity among multiple sources.The proposed bisection method(BM)based algorithm allocates inter-vehicle contacts to achieve the lexicographical max-min throughput among multiple sources.The strength of the BM algorithm is the ?-approximation to the optimum.Based on the allocation,the throughput is significantly improved and the lexicographical max-min fairness is achieved.(3)Compressive sensing based routing and data retrieval algorithm,reveals the sparsity of real-world vehicular sensing data after Haar wavelet transform.Based on compressive sensing theory,the proposed algorithm recovers sensing datasets based on a small set of measurements.It is highly challenging to decide the required number of measurements since the sparsity of datasets is unknown and time-varying.This work formulates the upper bound of the data recovery error given the distance between successively recovered coefficient vectors based on incrementally collected measurements.The proposed algorithm provides the customized data recovery accuracy and stops the data retrieval process when the designed termination condition is met.The tunable data accuracy adjusts the trade-off between the data quality and transmission overhead.Problem formulations,performance analysis and trace-driven simulations of the three routing algorithms are provided as well to demonstrate the efficacy of the proposed solutions.