{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,19]],"date-time":"2025-10-19T06:03:09Z","timestamp":1760853789157,"version":"build-2065373602"},"reference-count":49,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2014,11,27]],"date-time":"2014-11-27T00:00:00Z","timestamp":1417046400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>In vehicular ad hoc networks, roadside units (RSUs) placement has been proposed to improve the the overall network performance in many ITS applications. This paper addresses the budget constrained and delay-bounded placement problem (BCDP) for roadside units in vehicular ad hoc networks. There are two types of RSUs: cable connected RSU (c-RSU) and wireless RSU (w-RSU). c-RSUs are interconnected through wired lines, and they form the backbone of VANETs, while w-RSUs connect to other RSUs through wireless communication and serve as an economical extension of the coverage of c-RSUs. The delay-bounded coverage range and deployment cost of these two cases are totally different. We are given a budget constraint and a delay bound, the problem is how to find the optimal candidate sites with the maximal delay-bounded coverage to place RSUs such that a message from any c-RSU in the region can be disseminated to the more vehicles within the given budget constraint and delay bound. We first prove that the BCDP problem is NP-hard. Then we propose several algorithms to solve the BCDP problem. Simulation results show the heuristic algorithms can significantly improve the coverage range and reduce the total deployment cost, compared with other heuristic methods.<\/jats:p>","DOI":"10.3390\/s141222564","type":"journal-article","created":{"date-parts":[[2014,11,27]],"date-time":"2014-11-27T10:41:20Z","timestamp":1417084880000},"page":"22564-22594","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["BCDP: Budget Constrained and Delay-Bounded Placement for Hybrid Roadside Units in Vehicular Ad Hoc Networks"],"prefix":"10.3390","volume":"14","author":[{"given":"Peng","family":"Li","sequence":"first","affiliation":[{"name":"Computer School, Wuhan University, Luo-Jia-Shan Road 16, Wuhan 430072, China"},{"name":"College of Computer Science and Technology, Wuhan University of Science and Technology, Heping Road 947, Wuhan 430081, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chuanhe","family":"Huang","sequence":"additional","affiliation":[{"name":"Computer School, Wuhan University, Luo-Jia-Shan Road 16, Wuhan 430072, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qin","family":"Liu","sequence":"additional","affiliation":[{"name":"Computer School, Wuhan University, Luo-Jia-Shan Road 16, Wuhan 430072, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2014,11,27]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1109\/MCOM.2008.4539481","article-title":"A tutorial survey on vehicular ad hoc networks","volume":"46","author":"Hartenstein","year":"2008","journal-title":"IEEE Commun. Mag."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1049\/iet-com.2009.0164","article-title":"Multi-layer clustering routing algorithm for wireless vehicular sensor networks","volume":"4","author":"Liu","year":"2010","journal-title":"IET Commun."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Wu, Y., Zhu, Y., and Li, B. (2012, January 25\u201330). Infrastructure-assisted routing in vehicular networks. Orlando, FL, USA.","DOI":"10.1109\/INFCOM.2012.6195515"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1099","DOI":"10.1109\/TITS.2012.2183124","article-title":"We can deliver messages to far vehicles","volume":"13","author":"Mershad","year":"2012","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"key":"ref_5","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_6","doi-asserted-by":"crossref","first-page":"2549","DOI":"10.1016\/j.comnet.2013.05.002","article-title":"TMA: Trajectory-based Multi-Anycast forwarding for efficient multicast data delivery in vehicular networks","volume":"57","author":"Jeong","year":"2013","journal-title":"Comput. Netw."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1377","DOI":"10.1109\/TMC.2012.115","article-title":"Optimal content downloading in vehicular networks","volume":"12","author":"Malandrino","year":"2013","journal-title":"IEEE Trans. Mobile Comput."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1805","DOI":"10.1016\/j.comnet.2012.12.020","article-title":"MaxCD: Efficient multi-flow scheduling and cooperative downloading for improved highway drive-thru Internet systems","volume":"57","author":"Yang","year":"2013","journal-title":"Comput. Netw."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Ota, K., Dong, M., Chang, S., and Zhu, H. (2014, January 10\u201314). MMCD: Max-throughput and min-delay cooperative downloading for Drive-thru Internet systems. Sydney, Australia.","DOI":"10.1109\/ICC.2014.6883299"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"3947","DOI":"10.1109\/TVT.2014.2308149","article-title":"Multiple Content Dissemination in Roadside-Unit-Aided Vehicular Opportunistic Networks","volume":"63","author":"Li","year":"2014","journal-title":"IEEE Trans. Veh. Technol."},{"key":"ref_11","first-page":"479","article-title":"Enabling efficient WiFi-based vehicular content distribution","volume":"24","author":"Zhang","year":"2013","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1109\/JSAC.2013.SUP.0513048","article-title":"Dynamic Popular Content Distribution in Vehicular Networks Using Coalition Formation Games","volume":"31","author":"Wang","year":"2013","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Luan, T.H., Sherman Shen, X., and Bai, F. (2013, January 14\u201319). Integrity-oriented content transmission in highway vehicular ad hoc networks. Turin, Italy.","DOI":"10.1109\/INFCOM.2013.6567063"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1085","DOI":"10.1109\/TPDS.2010.173","article-title":"Video streaming distribution in VANETs","volume":"22","author":"Soldo","year":"2011","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"708","DOI":"10.1109\/LCOMM.2014.022514.140206","article-title":"Performance Evaluation of IEEE 802.11p-Enabled Vehicular Video Surveillance System","volume":"18","author":"Bellalta","year":"2014","journal-title":"IEEE Commun. Lett."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"3421","DOI":"10.1109\/TVT.2007.907230","article-title":"Optimal Placement of Gateways in Vehicular Networks","volume":"56","author":"Li","year":"2007","journal-title":"IEEE Trans. Veh. Technol."},{"key":"ref_17","unstructured":"Farahmand, F., Cerutti, I., Patel, A.N., Zhang, Q., and Jue, J.P. (December, January 30). Relay Node Placement in Vehicular Delay-Tolerant Networks. New Orleans, LA, USA."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Zheng, Z., Lu, Z., Sinha, P., and Kumar, S. (2010, January 15\u201319). Maximizing the contact opportunity for vehicular internet access. San Diego, CA, USA.","DOI":"10.1109\/INFCOM.2010.5461937"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Bao, Y., and Zhu, Y. (2011, January 5\u20139). On optimal relay placement for urban vehicular networks. Kyoto, Japan.","DOI":"10.1109\/icc.2011.5962852"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1007\/s11036-009-0168-3","article-title":"A resilient and scalable flocking scheme in autonomous vehicular networks","volume":"15","author":"Xiong","year":"2010","journal-title":"Mobile Netw. Appl."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"801","DOI":"10.1049\/iet-com.2009.0132","article-title":"Predictive control for vehicular sensor networks based on round-trip time-delay prediction","volume":"4","author":"Li","year":"2010","journal-title":"IET Commun."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Misra, S., Vasilakos, A.V., Obaidat, M.S., Krishna, P.V., Agarwal, H., and Saritha, V. (2013, January 9\u201313). A fault-tolerant routing protocol for dynamic autonomous unmanned vehicular networks. Budapest, Hungary.","DOI":"10.1109\/ICC.2013.6655097"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Burgess, J., Gallagher, B., Jensen, D., and Levine, B.N. (2006, January 23\u201329). MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks. Barcelona, Spain.","DOI":"10.1109\/INFOCOM.2006.228"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Naumov, V., and Gross, T.R. (2007, January 6\u201312). Connectivity-Aware Routing (CAR) in Vehicular Ad-hoc Networks. Anchorage, AK, USA.","DOI":"10.1109\/INFCOM.2007.223"},{"key":"ref_25","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_26","doi-asserted-by":"crossref","first-page":"743","DOI":"10.1109\/TPDS.2010.103","article-title":"Trajectory-based data forwarding for light-traffic vehicular Ad Hoc networks","volume":"22","author":"Jeong","year":"2011","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1523","DOI":"10.1109\/TMC.2011.189","article-title":"Trajectory-based statistical forwarding for multihop infrastructure-to-vehicle data delivery","volume":"11","author":"Jeong","year":"2012","journal-title":"IEEE Trans. Mobile Comput."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Skordylis, A., and Trigoni, N. (2008, January 27\u201330). Delay-bounded routing in vehicular ad-hoc networks. Hong Kong SAR, China.","DOI":"10.1145\/1374618.1374664"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Liu, J., Yang, Z., and Stojmenovic, I. (2012, January 18\u201321). Receiver Consensus: On-time Warning Delivery for Vehicular Ad-hoc Networks. Macau, China.","DOI":"10.1109\/ICDCS.2012.41"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1109\/TCOMM.2012.122712.120222","article-title":"Delay-Aware Data Delivery in Vehicular Intermittently Connected Networks","volume":"61","author":"Khabbaz","year":"2013","journal-title":"IEEE Trans. Commun."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1016\/j.adhoc.2007.05.003","article-title":"Strategies and techniques for node placement in wireless sensor networks: A survey","volume":"6","author":"Younis","year":"2008","journal-title":"Ad Hoc Netw."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/s10878-006-7140-y","article-title":"On optimal placement of relay nodes for reliable connectivity in wireless sensor networks","volume":"11","author":"Liu","year":"2006","journal-title":"J. Comb. Optim."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1109\/TC.2007.250629","article-title":"Relay node placement in wireless sensor networks","volume":"56","author":"Lloyd","year":"2007","journal-title":"IEEE Trans. Comput."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Zhang, W., Xue, G., and Misra, S. (2007, January 6\u201312). Fault-tolerant relay node placement in wireless sensor networks: Problems and algorithms. Anchorage, AK, USA.","DOI":"10.1109\/INFCOM.2007.193"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1109\/TMC.2009.161","article-title":"Fault-tolerant relay node placement in heterogeneous wireless sensor networks","volume":"9","author":"Han","year":"2010","journal-title":"IEEE Trans. Mobile Comput."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1109\/TNET.2009.2033273","article-title":"Constrained relay node placement in wireless sensor networks: Formulation and approximations","volume":"18","author":"Misra","year":"2010","journal-title":"IEEE\/ACM Trans. Netw. (TON)"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"1399","DOI":"10.1109\/TMC.2011.126","article-title":"Two-tiered constrained relay node placement in wireless sensor networks: Computational complexity and efficient approximations","volume":"11","author":"Yang","year":"2012","journal-title":"IEEE Trans. Mobile Comput."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"1783","DOI":"10.1109\/TPDS.2012.263","article-title":"Minimum-Cost Sensor Placement for Required Lifetime in Wireless Sensor-Target Surveillance Networks","volume":"24","author":"Liu","year":"2013","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1109\/TSC.2012.32","article-title":"A Bare-Metal and Asymmetric Partitioning Approach to Client Virtualization","volume":"7","author":"Zhou","year":"2014","journal-title":"IEEE Trans. Serv. Comput."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"2186","DOI":"10.1109\/TWC.2011.051311.100956","article-title":"Minimizing Cost of Placement of Multi-Radio and Multi-Power-Level Access Points with Rate Adaptation in Indoor Environment","volume":"10","author":"Zhang","year":"2011","journal-title":"IEEE Trans. Wirel. Commun."},{"key":"ref_41","unstructured":"Zhou, K., Jia, X., Xie, L., and Chang, Y. (2011, January 5\u20139). Fault Tolerant AP Placement with QoS Constraint in Wireless Local Area Networks. Houston, TX, USA."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"804","DOI":"10.1109\/JSAC.2012.120514","article-title":"On Maximizing Delay-Constrained Coverage of Urban Vehicular Networks","volume":"30","author":"Zhu","year":"2012","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"956","DOI":"10.1109\/TNET.2011.2170218","article-title":"Sparse WiFi deployment for vehicular internet access with bounded interconnection gap","volume":"20","author":"Zheng","year":"2012","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1109\/TVT.2012.2217159","article-title":"Exploiting Statistical Mobility Models for Efficient WiFi Deployment","volume":"62","author":"Wang","year":"2013","journal-title":"IEEE Trans. Veh. Technol."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"1266","DOI":"10.1109\/TITS.2013.2258153","article-title":"Vehicles Meet Infrastructure: Towards Capacity-Cost Tradeoffs for Vehicular Access Networks","volume":"14","author":"Lu","year":"2013","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"key":"ref_46","unstructured":"Halperin, E. (2005). Municipal Wireless: Partner to Spread Risks and Costs While Maximizing Benefit Opportunities, Jupitermedia Corporation. Technical Report."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0020-0190(99)00031-9","article-title":"The budgeted maximum coverage problem","volume":"70","author":"Khuller","year":"1999","journal-title":"Inf. Process. Lett."},{"key":"ref_48","unstructured":"Krajzewicz, D., Hertkorn, G., R\u00f6ssel, C., and Wagner, P. (2002, January 20\u201324). Sumo (simulation of urban mobility). Las Vegas, NV, USA."},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Karnadi, F.K., Mo, Z.H., and Lan, K.c. (2007, January 11\u201315). Rapid generation of realistic mobility models for VANET. Hong Kong, China.","DOI":"10.1109\/WCNC.2007.467"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/14\/12\/22564\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:10:02Z","timestamp":1760217002000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/14\/12\/22564"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11,27]]},"references-count":49,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2014,12]]}},"alternative-id":["s141222564"],"URL":"https:\/\/doi.org\/10.3390\/s141222564","relation":{},"ISSN":["1424-8220"],"issn-type":[{"type":"electronic","value":"1424-8220"}],"subject":[],"published":{"date-parts":[[2014,11,27]]}}}