OptDynLim: An Optimal Algorithm for the One-Dimensional RSU Deployment Problem With Nonuniform Profit Density
- 28 May 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Industrial Informatics
- Vol. 15 (2) , 1052-1061
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%.Keywords
Funding Information
- National Natural Science Foundation of China (61671169, 61571150, 61572442)
This publication has 19 references indexed in Scilit:
- A hybrid genetic algorithm for deploying RSUs in VANETs based on inter-contact time2017
- Roadside Infrastructure Planning Scheme for the Urban Vehicular NetworksTransportation Research Procedia, 2017
- A New Comprehensive RSU Installation Strategy for Cost-Efficient VANET DeploymentIEEE Transactions on Vehicular Technology, 2016
- Optimal RSUs deployment with delay bound along highways in VANETJournal of Combinatorial Optimization, 2016
- Deployment of roadside units based on partial mobility informationComputer Communications, 2015
- GeoCover: An efficient sparse coverage protocol for RSU deployment over urban VANETsAd Hoc Networks, 2015
- BCDP: Budget Constrained and Delay-Bounded Placement for Hybrid Roadside Units in Vehicular Ad Hoc NetworksSensors, 2014
- Road Side Unit Deployment: A Density-Based ApproachIEEE Intelligent Transportation Systems Magazine, 2013
- Optimal roadside units placement in urban areas for vehicular networks2012
- A Roadside Unit Placement Scheme for Vehicular Telematics Networks2010