RSU deployment planning based on approximation algorithm in urban VANET

To minimize the number of RSU deployed to cover a specific area,a c street model transforming the area covering problem to streets covering problem was designed,and a greedy-based polynomial (GBP) time approximation algorithm was developed to obtain the optimal RSU deployment for area coverage.For complex urban environments,a Cue model (complex urban environments model) was proposed.In this model,the target area was divided into different partitions.Then,based on shifting strategy,a polynomial time approximation scheme was designed.Theoretical analysis that include the approximation ratio and time complexity of the proposed algorithm were also presented.Simulation results show that GBP can efficiently solve the coverage problem in urban VANET.