Abstract
Because of the excessive cost of Road Side Units (RSUs), optimal RSU deployment is of crucial importance to VANETs. Since existing models of the RSU Deployment (RD) problem lack ability to describe curve-shaped roads with non-uniform statistics, a more realistic model with this ability for the RD problem was proposed recently. However, our understanding of the RD problem with the new model is still far from satisfactory. Even to the simpler one-dimensional RD (D1RD) problem, properties are not analyzed, optimal algorithms are not proposed yet. In this paper, we focus on the D1RD problem with the new model. We firstly analyze the properties of the optimal solutions of the D1RD problem. We then propose an efficient technique named Dynamic Limiting (DynLim) technique, which reduces solution search space size considerably by adjusting search space limits dynamically. Finally, an optimal algorithm named OptDynLim is proposed based on DynLim, and its optimality is proved. Numerical simulations validate the correctness of our analyses and show that DynLim can usually reduce solution search space size by more than 99%.
Funding Information
  • National Natural Science Foundation of China (61671169, 61571150, 61572442)

This publication has 19 references indexed in Scilit: