Resource Placement And Optimization Algorithm Design For Hybrid Vehicular Ad-hoc Networks

Hybrid vehicular ad-hoc networks is made up of wireless sensor networks for data collection and vehicular ad-hoc networks for data transmission.With the advent of the era of Internet +,in order to rapidly and efficiently collect/transmit data from large areas,hybrid vehicular ad-hoc networks has gradually become a hot topic in the field of mobile Internet.In this thesis,we study the resource deployment and optimization problems in hybrid vehicular ad-hoc networks with the goal of reducing the delay of information transmission and energy consumption of nodes,and improving the efficiency of network transmission.Then,solutions are introduced respectively for optimal roadside unit placement problem,optimal gateway placement problem,and optimal virtual backbone construction problem under their corresponding scenarios.First,vehicles move in uniform linear motion along highways.Once a vehicle enters into a road segment,it will not leave at once.The self-organization vehicular ad-hoc networks is unstable.It is important to analyze the delay of information transmission accurately and optimally place roadside units along highways.In this thesis,we construct the mobile topology model of the vehicle network by clustering the vehicles on the road segment,based on which to formulate the delay model of information transmission.The relationship of delay,road length,vehicles speed and traffic density can be obtained through the transformation delay model.Given the delay bound and highway constraints,the optimal number of roadsides can be calculated accurately.Second,the urban area is divided into irregular grid areas by road,and vehicles move randomly into another road at the intersections.Statistically,the event of in/out a road segment obeys the Poisson distribution.In this thesis,we transform the roads topology into a network model,and formulate the relationship between the information transmission delay and road length.Three greedy algorithms are designed to compute preliminary solutions,and then a genetic algorithm is introduced to ameliorate the solutions.Experiments show that the proposed solution has obvious advantages over No LP,NN,RR,Thresh and Sort LP algorithms.Third,buses move along scheduled routes according to the time table in urban environment.In the hybrid vehicular ad-hoc networks,the bus ad-hoc networks and sensor networks are heterogeneous,and gateways are needed to connect the two different networks.Taking into account of minimizing delay and deployment cost,optimal gateways placement algorithm and minimum number of gateways placement algorithm are designed to cover all the urban areas.The number of buses in the whole area is limited.To satisfy the delay bound of information transmission in bus ad-hoc networks,we designed an optimal RSUs placement algorithm.Through the rigorous theoretical derivation,it proves that all the three approximation algorithms can obtain the approximate optimal solutions.Fourth,there is no fixed routes when information is transmitted in wireless multi-hop networks.In order to avoid network congestion,reducing the delay of information transmission and energy consumption while extending the network lifetime,virtual backbone is commonly constructed.Information is transmitted through the virtual backbone.The existing work mainly focuses on minimizing the virtual backbone network,dynamic planning virtual backbone network,constructing multi-gateway multi-path virtual backbone networks.In this thesis,we propose a virtual backbone construction scheme based on strong connected dominating set.For any pair of nodes in the network,the shortest path length through the virtual backbone does not exceed the constant times of the shortest path length in the original network.Based on this construction,the centralized virtual backbone construction approximate algorithm and the distributed virtual backbone approximate algorithm are designed respectively.After rigorous theoretical derivation,we can get the approximate ratio of the algorithm and the value of the constant.Numerical experiments prove that the average path length of the nodes through the virtual backbone constructed by our algorithm has obvious advantages over the improved contrast algorithms.