{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T17:17:53Z","timestamp":1774718273685,"version":"3.50.1"},"reference-count":34,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2018,8,22]],"date-time":"2018-08-22T00:00:00Z","timestamp":1534896000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61300124"],"award-info":[{"award-number":["61300124"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Science and Technology Research Program of Henan Province","award":["132102210123"],"award-info":[{"award-number":["132102210123"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>As an auxiliary facility, roadside units (RSUs) can well improve the shortcomings incurred by ad hoc networks and promote network performance in a vehicular ad hoc network (VANET). However, deploying a large number of RSUs will lead to high installation and maintenance costs. Therefore, trying to find the best locations is a key issue when deploying RSUs with the set delay and budget. In this paper, we study the delay-bounded and cost-limited RSU deployment (DBCL) problem in urban VANET. We prove it is non-deterministic polynomial-time hard (NP-hard), and a binary differential evolution scheme is proposed to maximize the number of roads covered by deploying RSUs. Opposite-based learning is introduced to initialize the first generation, and a binary differential mutation operator is designed to obtain binary coding. A random variable is added to the traditional crossover operator to increase population diversity. Also, a greedy-based individual reparation and promotion algorithm is adopted to repair infeasible solutions violating given constraints, and to gain optimal feasible solutions with the compromise of given limits. Moreover, after selection, a solution promotion algorithm is executed to promote the best solution found in generation. Simulation is performed on analog trajectories sets, and results show that our proposed algorithm has a higher road coverage ratio and lower packet loss compared with other schemes.<\/jats:p>","DOI":"10.3390\/s18092764","type":"journal-article","created":{"date-parts":[[2018,8,23]],"date-time":"2018-08-23T03:00:46Z","timestamp":1534993246000},"page":"2764","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":37,"title":["Delay-Bounded and Cost-Limited RSU Deployment in Urban Vehicular Ad Hoc Networks"],"prefix":"10.3390","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9632-2543","authenticated-orcid":false,"given":"Huanhuan","family":"Yang","sequence":"first","affiliation":[{"name":"School of Computer Science and Technology, Henan Polytechnic University, Jiaozuo 454000, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zongpu","family":"Jia","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Henan Polytechnic University, Jiaozuo 454000, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guojun","family":"Xie","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Henan Polytechnic University, Jiaozuo 454000, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,8,22]]},"reference":[{"key":"ref_1","first-page":"15","article-title":"DDGP: Distributed Data Gathering Protocol for vehicular networks","volume":"4","author":"Brik","year":"2016","journal-title":"Veh Commun."},{"key":"ref_2","first-page":"685","article-title":"Data Aggergation Scheduling on Wireless Mobile Sensor Networks","volume":"38","author":"Feng","year":"2015","journal-title":"Chin. J. Comput."},{"key":"ref_3","first-page":"524","article-title":"Future Applications of VANETs","volume":"Volume 18","author":"Campolo","year":"2015","journal-title":"Vehicular Ad Hoc Networks"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1909","DOI":"10.1109\/COMST.2014.2320091","article-title":"In-Network Aggregation for Vehicular Ad Hoc Networks","volume":"16","author":"Dietzel","year":"2014","journal-title":"IEEE Commun. Surv. Tutor."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Jo, Y., and Jeong, J. (2016, January 23\u201325). RPA: Road-Side Units Placement Algorithm for Multihop Data Delivery in Vehicular Networks. Proceedings of the 30th International Conference on Advanced Information Networking and Applications Workshops (WAINA), Crans-Montana, Switzerland.","DOI":"10.1109\/WAINA.2016.91"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Alkharasani, N., Zulkarnain, Z., Subramaniam, S., and Hanapi, Z. (2018). An Efficient Framework Model for Optimizing Routing Performance in VANETs. Sensors, 18.","DOI":"10.3390\/s18020597"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Banani, S., Gordon, S., Thiemjarus, S., and Kittipiyakul, S. (2018). Verifying Safety Messages Using Relative-Time and Zone Priority in Vehicular Ad Hoc Networks. Sensors, 18.","DOI":"10.3390\/s18041195"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Izaparedes, C., Mezher, A., Igartua, M.A., and Forn\u00e9, J. (2018). Game-Theoretical Design of an Adaptive Distributed Dissemination Protocol for VANETs. Sensors, 18.","DOI":"10.3390\/s18010294"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"2097","DOI":"10.1109\/TVT.2014.2335232","article-title":"Delay-Constrained Data Aggregation in VANETs","volume":"64","author":"Zhu","year":"2015","journal-title":"IEEE Trans. Veh. Technol."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/j.adhoc.2016.09.021","article-title":"Cost-efficient traffic-aware data collection protocol in VANET","volume":"55","author":"He","year":"2017","journal-title":"Ad Hoc Netw."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1016\/j.pmcj.2011.06.008","article-title":"Delay-bounded data gathering in urban vehicular sensor networks","volume":"8","author":"Palazzi","year":"2012","journal-title":"Pervasive Mob. Comput."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Aslam, B., and Zou, C.C. (2011, January 9\u201312). Optimal roadside units placement along highway. Proceedings of the 2011 IEEE Consumer Communications and Networking Conference (CCNC), Las Vegas, NV, USA.","DOI":"10.1109\/CCNC.2011.5766608"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Aslam, B., Amjad, F., and Zou, C.C. (2012, January 1\u20134). Optimal roadside units placement in urban areas for vehicular networks. Proceedings of the 2012 IEEE Symposium on Computers and Communications (ISCC), Cappadocia, Turkey.","DOI":"10.1109\/ISCC.2012.6249333"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Patil, P., and Gokhale, A. (2013, January 20\u201324). Voronoi-based placement of road-side units to improve dynamic resource management in Vehicular Ad Hoc Networks. Proceedings of the 2013 International Conference on Collaboration Technologies and Systems (CTS), San Diego, CA, USA.","DOI":"10.1109\/CTS.2013.6567260"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"432","DOI":"10.1016\/j.comcom.2009.11.021","article-title":"Planning roadside infrastructure for information dissemination in intelligent transportation systems","volume":"33","author":"Trullols","year":"2010","journal-title":"Comupt. Commun."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"22564","DOI":"10.3390\/s141222564","article-title":"BCDP: Budget constrained and delay-bounded placement for hybrid roadside units in vehicular ad hoc networks","volume":"14","author":"Li","year":"2014","journal-title":"Sensors"},{"key":"ref_17","first-page":"78","article-title":"RSU deployment planning based on approximation algorithm in urban VANET","volume":"39","author":"Zhu","year":"2018","journal-title":"J. Commun."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Mehar, S., Senouci, S.M., Kies, A., and Zoulikha, M.M. (2015, January 9\u201312). An Optimized Roadside Units RSU placement for delay-sensitive applications in vehicular networks. Proceedings of the 12th Annual IEEE Consumer Communications and Networking Conference (CCNC), Las Vegas, NV, USA.","DOI":"10.1109\/CCNC.2015.7157957"},{"key":"ref_19","unstructured":"Chi, J., Jo, Y., Park, H., and Park, S. (2013, January 2\u20135). Intersection-priority based optimal RSU allocation for VANET. Proceedings of the Fifth International Conference on Ubiquitous and Future Networks (ICUFN), Da Nang, Vietnam."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Patra, M., Mishra, S., and Murthy, C.S.R. (2014, January 18\u201321). An Analytic Hierarchy Process Based Approach for Optimal Road Side Unit Placement in Vehicular Ad Hoc Networks. Proceedings of the IEEE 79th Vehicular Technology Conference (VTC), Seoul, Korea.","DOI":"10.1109\/VTCSpring.2014.7022815"},{"key":"ref_21","first-page":"4200","article-title":"A New Comprehensive RSU Installation Strategy for Cost-Efficient VANET Deployment","volume":"66","author":"Kim","year":"2017","journal-title":"IEEE Trans. Veh. Technol."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"7317","DOI":"10.1109\/TVT.2017.2665480","article-title":"Combining Capital and Operating Expenditure Costs in Vehicular Roadside Unit Placement","volume":"66","author":"Nikookaran","year":"2017","journal-title":"IEEE Trans. Veh. Technol."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1109\/MITS.2013.2253159","article-title":"Road Side Unit Deployment: A Density-Based Approach","volume":"5","author":"Barrachina","year":"2013","journal-title":"IEEE Intell. Transp. Syst. Mag."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"2295","DOI":"10.1109\/TCOMM.2012.062512.100550","article-title":"A Cost-Effective Strategy for Road-Side Unit Placement in Vehicular Networks","volume":"60","author":"Wu","year":"2012","journal-title":"IEEE Trans. Commun."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Malandrino, F., Casetti, C., Chiasserini, C.F., and Fiore, M. (2011, January 10\u201315). Content downloading in vehicular networks: What really matters. Proceedings of the IEEE INFOCOM, Shanghai, China.","DOI":"10.1109\/INFCOM.2011.5935197"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1910","DOI":"10.1109\/TVT.2007.901869","article-title":"VADD: Vehicle-Assisted Data Delivery in Vehicular Ad Hoc Networks","volume":"57","author":"Zhao","year":"2008","journal-title":"IEEE Trans. Veh. Technol."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Li, P., Liu, Q., Huang, C., Wang, J., and Jia, X. (2015, January 8\u201312). Delay-bounded minimal cost placement of roadside units in vehicular ad hoc networks. Proceedings of the IEEE International Conference on Communications (ICC), London, UK.","DOI":"10.1109\/ICC.2015.7249375"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"2445","DOI":"10.1109\/TVT.2010.2045234","article-title":"SADV: Static-node-assisted adaptive data dissemination in vehicular networks","volume":"59","author":"Ding","year":"2010","journal-title":"IEEE Trans. Veh. Technol."},{"key":"ref_29","unstructured":"Cormen, T.T., Leiserson, C.E., and Rivest, R.L. (2009). Introduction to Algorithms, The MIT Press. [3rd ed.]."},{"key":"ref_30","unstructured":"Tizhoosh, H.R. (2005, January 28\u201330). Opposition-based learning: A new scheme for machine Intelligence. Proceedings of the International Conference on Computational Intelligence for Modelling, Vienna, Austria."},{"key":"ref_31","first-page":"1","article-title":"A framework of population-based stochastic search algorithm with generalized opposition-based learning","volume":"31","author":"Wang","year":"2012","journal-title":"J. Nanchang Inst. Technol."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Michalewicz, Z. (1996). Genetic Algorithm + Data Structure = Evolution Programs, Springer. [3rd ed.].","DOI":"10.1007\/978-3-662-03315-9"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Das, S., Konar, A., and Chakraborty, U.K. (2005, January 2\u20135). Improved differential evolution algorithms for handling noisy optimization problems. Proceedings of the IEEE Congress on Evolutionary Computation, Edinburgh, UK.","DOI":"10.1109\/CEC.2005.1554892"},{"key":"ref_34","unstructured":"Kong, X.Y., Gao, L.Q., Ouyang, H.B., and Ge, Y.F. (2014). Binary Differential Evolution Algorithm Based on Parameterless Mutation Strategy. J. Northeast Univ., 484\u2013488."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/18\/9\/2764\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:20:25Z","timestamp":1760196025000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/18\/9\/2764"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,22]]},"references-count":34,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2018,9]]}},"alternative-id":["s18092764"],"URL":"https:\/\/doi.org\/10.3390\/s18092764","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,22]]}}}