Optimal Roadside Units Placement in Urban Areas for Vehicular Networks

ABSTRACT

The most important component of a vehicular ad hoc network (VANET), besides VANET-enabled vehicles, is
roadside units (RSUs). The effectiveness of a VANET largely depends on the density and location of these RSUs. During the initial stages of VANET, it will not be possible to deploy a large number of RSUs either due to the low market penetration of VANET-enabled vehicles or due to the deployment cost of RSUs. There is, therefore, a need to optimally place a limited number of RSUs in a given region in order to achieve maximum performance. In this paper, we present two different optimization methods for placement of a limited number of RSUs in an urban region: an analytical Binary Integer Programming (BIP) method and a novel Balloon Expansion Heuristic (BEH) method. BIP method utilizes branch and bound approach to find an optimal analytical solution whereas BEH method uses balloon expansion analogy to find an optimal or near optimal solution. Our evaluations show that both methods perform optimally or near optimally compared with the exhaustive method. Further, BEH method is more versatile and performs better than BIP method in terms of
computational cost and scalability.

INTRODUCTION

A vehicular ad hoc network (VANET) relies on three types of communication for its setup and provision of services: vehicle to vehicle (V2V) communication, vehicle to infrastructure (V2I) communication and infrastructure to infrastructure (I2I) communication. All VANET applications depend on either one or more of these communication types. V2V communication depends on the number and location of vehicles, V2I communication depends on the number and location of roadside units (RSUs) and I2I communication depends on availability of interconnecting network between RSUs. During the initial deployment stages of VANET, there will be very small number of vehicles and RSUs due to the low market penetration of VANET-enabled vehicles or due to the deployment cost of RSUs. Given a small number of RSUs, there is, therefore a need to optimally place these RSUs in a given region/scenario in order to achieve maximum performance. Information flow in most VANET applications is either from vehicles to infrastructure or from infrastructure to vehicles. Our focus, in this paper, is on applications that depend on information flow from vehicles to nfrastructure (or RSUs), such as collection of information from vehicles about traffic/road conditions, traffic accidents, etc.

چکیده

مهمترین جزء یک شبکه عادی خودرو (VANET)، علاوه بر وسایل نقلیه فعال VANET، واحد های کنار جاده ای (RSU) است. اثربخشی VANET عمدتا بستگی به تراکم و مکان این RSU ها دارد. در مراحل اولیه VANET، نمی توان تعداد زیادی از RSU ها را به دلیل نفوذ بازار در وسایل نقلیه فعال VANET یا به علت هزینه های راه اندازی RSU، مستقر کرد. بنابراین، به منظور دستیابی به حداکثر کارایی، نیاز به بهینه سازی تعداد محدودی از RSU ها در یک منطقه مشخص وجود دارد. در این مقاله دو روش بهینه سازی برای قرار دادن تعداد محدودی از RSU ها در یک منطقه شهری ارائه می شود: یک روش برنامه ریزی عدد انتگرال تحلیلی (BIP) و یک روش ریاضی بولون انبساطی هورستیک (BEH). روش BIP با استفاده از رویکرد شعبه و محدود برای پیدا کردن یک راه حل تحلیلی مطلوب، در حالی که روش BEH با استفاده از روش انطباق گسترش بالون برای یافتن یک راه حل بهینه یا نزدیک بهینه است. ارزیابی های ما نشان می دهد که هر دو روش به طور مطلوب یا نزدیک به مطلوب در مقایسه با روش جامع انجام می شود. علاوه بر این، روش BEH چند منظوره تر و بهتر از روش BIP است هزینه محاسباتی و مقیاس پذیری است.

مقدمه

یک شبکه اختصاصی خودرو (VANET) برای تنظیم و ارائه خدمات خود به سه نوع ارتباط متکی است: ارتباطات وسیله نقلیه وسیله نقلیه (V2V)، ارتباطات وسیله نقلیه به زیرساخت (V2I) و ارتباطات زیربنایی به زیرساخت (I2I). تمام برنامه های VANET به یکی یا بیشتر از این نوع ارتباط متصل می شوند. ارتباط V2V به تعداد و مکان وسایل نقلیه بستگی دارد، ارتباط V2I بستگی به تعداد و مکان واحد های کنار جاده ای (RSU) دارد و ارتباطات I2I بستگی به دسترسی شبکه های متصل کننده بین RSU ها دارد. در مراحل ابتدایی نصب VANET تعداد خودروها و RSU ها بسیار کم است به دلیل نفوذ کم بازار وسایل نقلیه فعال VANET و یا به دلیل هزینه های راه اندازی RSU. با توجه به تعداد کمی از RSU ها، وجود دارد، بنابراین برای به حداکثر رساندن این نیاز، این RSU ها به طور مطلوب در یک منطقه / سناریو داده می شود. جریان اطلاعات در بیشتر برنامه های VANET از وسایل نقلیه به زیرساخت ها یا از زیرساخت ها به وسایل نقلیه است. تمرکز ما در این مقاله کاربردی است که به جریان اطلاعات از وسایل نقلیه به nfrastructure (یا RSU) بستگی دارد، مانند جمع آوری اطلاعات از وسایل نقلیه در مورد شرایط ترافیک / جاده، تصادفات رانندگی و غیره.

Year: 2012

Publisher : IEEE

By : Baber Aslam, Faisal Amjad and Cliff C. Zou