 Advances in Technology Innovation, vol. 5, no. 1, 2020, pp. 56-63 Efficient RSU Selection Approaches for Load Balancing in Vehicular Ad Hoc Networks Chi-Fu Huang * , Jyun-Hao Jhang Department of Computer Science and Information Engineering, National Chung-Cheng University, Chiayi, Taiwan Received 12 April 2019; received in revised form 23 April 2019; accepted 04 August 2019 DOI: https://doi.org/10.46604/aiti.2020.4080 Abstract Due to advances in wireless communication technologies, wireless transmissions gradually replace traditional wired data transmissions. In recent years, vehicles on the move can also enjoy the convenience of wireless communication technologies by assisting each other in message exchange and form an interconnecting network, namely Vehicular Ad Hoc Networks (VANETs). In a VANET, each vehicle is capable of communicating with nearby vehicles and accessing information provided by the network. There are two basic communication models in VANETs, V2V and V2I. Vehicles equipped with wireless transceiver can communicate with other vehicles (V2V) or roadside units (RSUs) (V2I). RSUs acting as gateways are entry points to the Internet for vehicles. Naturally, vehicles tend to choose nearby RSUs as serving gateways. However, due to uneven density distribution and high mobility nature of vehicles, load imbalance of RSUs can happen. In this paper, we study the RSU load-balancing problem and propose two solutions. In the first solution, the whole network is divided into sub-regions based on RSUs’ locations. A RSU provides Internet access for vehicles in its sub-region and the boundaries between sub-regions change dynamically to adopt to load migration. In the second solution, vehicles choose their serving RSUs distributedly by taking their future trajectories and RSUs’ loading information into considerations. From simulation results, the proposed methods can improve packet delivery ratio, packet delay, and load balance among RSUs. Keywords: VANET, RSU, load balance, routing 1. Introduction Vehicular ad hoc networks (VANETs) [1-2] attract a lot of attention in recent years due to lots of potential applications [3-5]. A VANET consists of many highly mobile vehicles. Each vehicle is able to communicate with nearby vehicles and share information through the network. VANETs can be regards as a particular type of traditional mobile ad-hoc networks (MANETs). Many technologies of VANETs inherit from MANETs, such as multi-hop relays and routing protocols. However, VANETs have some different characteristics. The moving paths and speeds are constrained by the pre-existing road map. Taking vehicles’ speeds and moving directions into considerations can predict the future positions of vehicles. Besides, we usually assume vehicles have no energy constraint. There are two basic communication models in VANETs [6], Vehicle-to-Infrastructure (V2I), and Vehicle-to-Vehicle (V2V), as shown in Fig 1. V2I communication relies on fixed infrastructures, such as roadside units (RSUs), to communicate vehicles. RSUs connect to each other through a wired network and form a backbone network. RSUs also act as gateways, which are entry points to the Internet for vehicles. Because of huge deployment and maintenance cost, it is nearly impossible to * Corresponding author. E-mail address: cfhuang@cs.ccu.edu.tw Tel.: +886-5-2720411; Fax: +886-5-2720859 Advances in Technology Innovation, vol. 5, no. 1, 2020, pp. 56-63 57 deploy a large amount of RSUs such that each vehicle can directly connect to a RSU. To extend the service ranges of RSUs, vehicles utilize V2V communication to connect to RSUs. In V2V communication, vehicles form a self-organized network without any centralized system. Vehicles communicate with each other directly and achieve long-distance communications through multi-hop relays to connect to RSUs. With RSUs sparsely deployed, a critical issue is how vehicles establish routing paths to delivery their packets to/from RSUs [7]. Traditional routing protocols of MANETs are not suitable for VANETs due to high mobility of vehicles and consequent control overhead. Geographic routing [8] is suitable for VANETs due to its low control overhead. The main idea of geographic routing is to choose the vehicle geographically closest to the destination as the next hop to relay packets. Naumove et al. [9] proposed the Advanced Greedy Forwarding (AGF) algorithm and Preferred Group Broadcasting Algorithm (PGB) to improve GPSR performance in VANET. Context-Aware Routing (CAR) [10] based on AGF and PGB could find a route that maximizes the chance of successful delivery. In GyTAR [11], data packets are forwarded through the selected intersections by a greedy carry-and-forward scheme.. Fig. 1 Basic communication models in VANETs Vehicles tend to choose nearby RSUs as their entry points to Internet. The distance between a vehicle and its servicing gateway affects network performance significantly. The longer distance can result in a higher end-to-end delay and a lower packet delivery ratio. How to deploy RSUs becomes a critical issue [12]. Intersections are good places to deploy RSUs. Because when approaching an intersection, vehicles decelerate, which increases the connection time between vehicles and RSUs. Other criterions to deploy RSUs include the area with high vehicular density is preferred, and the distances between any two RSUs should be large enough. However, the vehicular density varies from time to time due to the high mobility nature of vehicles. If each vehicle connect to its closet RSU, it is possible that some RSUs are overloaded but some are idle. Such load imbalance among RSUs can prevent the network from fully utilizing RSUs’ bandwidths [13-15]. In this paper, we study how to balance the loads of RSUs providing Internet access for vehicles in an urban environment. There are serval criteria in our design. First, current and future loads of RSUs are primary concerns when choosing a serving RSU. Second, we should not ask a vehicle to choose a faraway RSU as its serving gateway, even if the RSU is with a very light load. Third, the length of routing path between a vehicle and its serving RSU changes as the vehicle moves. Therefore, a vehicle should consider its future trajectory when choosing a serving RSU. In this paper, we first propose a RSU-based method, which divides the whole map into several sub-regions. There is only one RSU residences in each sub-region to provide Internet access service for all vehicles in its sub-region. The boundaries between sub-regions change dynamically to react to load migrations of RSUs. This centralized method is inspired by the cell breathing for WLAN [16], which adjusts the beacon transmission range of access points (APs) to balance the loads of APs. To be more scalable, we proposed a distributed vehicle-based method, which allows vehicles choose their serving RSU distributedly. We design a criterion for vehicles to Advances in Technology Innovation, vol. 5, no. 1, 2020, pp. 56-63 58 choose their service RSUs based on their future locations, which can prevent vehicles from changing their serving RSUs frequently. The main contributions of this paper are listed as follows. 1. We design two methods to balance the loads among RSUs for different scenarios. The simulation results shows that both our methods can balance the loads among RSUs. 2. With simulation verifications, both of our RSU-based and vehicle-based methods can improve the packet delivery ratio and the end-to-end delay. It is because an overloaded RSU increases the average queuing delay. In the worst case, the RSU may need to drop packets from its queue. 3. The proposed vehicle-based method considers both the driving directions and the future locations of vehicles, which can prevent vehicles from changing their serving RSUs frequently. 4. We assist vehicles to choose a suitable RSU with vehicular density, load conditions of RSUs, and routing length to improve the overall network performance. The rest of this paper is organized as follows. Section 2 presents the system model and define the load-balancing RSU selection problem. In Section 3, we describes the proposed methods. Section 4 demonstrates the efficiency of the proposed methods through simulations. Section 5 discusses the future works and concludes this paper. 2. System Model and Problem Definition In an urban environment, there are N intersections and P road segments. We assume there are total M RSUs deployed at a portion of N intersections to provide Internet access for vehicles, where N M . To formulate the problem, we translate the city map into a graph G (V, E) as shown in Fig. 2, where V is the set of intersections, V’ is the set of intersections with RSU deployed, and E is the set of road segments. For each edge e in E, there is a weight representing its traffic density. Except the distance, there are several concerns need to be address when choosing a serving RSU. First, the queuing delay of packets increases as the load of a RSU increases. Therefore, the load index ( iL ) of RSU i is an important factor to be considered, where Li is the ratio of the remaining bandwidth to the total bandwidth of RSU i. Second, due to the finite queue length of a RSU, an overloading RSU increases the packet dropping rate. Third, a vehicle should take its driving direction and future position into consideration in addition to its current position. Otherwise, a vehicle will change its serving RSU frequently. Fig. 2 The city map translates into a graph G (V, E) Balancing the loads among RSUs is important. It can improve not only the packet queuing delay but also the packet delivery ratio for vehicles. We call the problem of how to assign each vehicle to a suitable serving RSU as the Load-Balancing Advances in Technology Innovation, vol. 5, no. 1, 2020, pp. 56-63 59 RSU Selection (LBRS) problem. To evaluate how balance we can achieve, a load-balance index (LBI) of the whole network is defined as {Li {Li} L 1 M {Li} max min BI ,where i . max     (1) The value of LBI is between 0 and 1. A lower LBI implies a more balanced condition. Note that, even if a me thod can minimize LBI value but assign vehicles to distancing RSUs, it cannot be a good solution. It would increase the end-to-end delay and decrease delivery ratio. Therefore, our goal is to assign each vehicle to a serving RSU such that the LBI of the whole network as small as possible without violating the principle of distance criteria. 3. The proposed RSU-Based and Vehicle-Based Schemes In this section, two types of schemes, called RSU-based and Vehicle-based schemes, are presented to solve the LBRS problem. The RSU-based schemes divides the urban environment into M non-overlapped cells according to the number of RSUs. Only one RSU residences in a cell to provide Internet access service for vehicles in this cell. Boundaries between cells define the service ranges of RSUs and change dynamically to balance the loads among RSUs. In Vehicle-based scheme, vehicles choose their serving RSU according to the load index, trajectories, and path lengths to RSUs, independently and distributedly. 3.1. RSU-based mechanism In a VANET, due to high mobility of vehicles and the rapidly changing topology, a long delivery path based on multi-hop relays from a vehicle to a RSU may disconnect frequently. To choose a near gateway, we utilize Voronoi Diagram [16] to partition the network and define the serving ranges of RSUs. Given a plane and a set A of sits on the plane, the Voronoi diagram partitions the plane into numerous cells such that each cell contains exactly one site, denoted as s , in A. The cell contains all points that are closer to s than to any other site in A. In this paper, sites in A are RSUs and points are vehicles driving on the roads. We utilize the Voronoi diagram to partition the city map into M cells, and each cell contains exactly one RSU. Besides, vehicles driving on the roads assist each other in packet forwarding from vehicles to RSUs. The distribution of road segments and their lengths are the factors to be concerned, rather than a plane and the Euclidian distance. Fig. 3 An example of the Map-based Voronoi diagram resulted from Fig. 2 A Map-based Voronoi Diagram considering a city map rather than a plane works as follows. We modify the partition algorithm of the Voronoi diagram. Instead of the perpendicular bisectors, we find the midpoints of the shortest paths between each pair of RSUs. The network is then partitioned by connecting those midpoints. An example is shown in Fig. 3. A vehicle in a cell will chooses the RSU in the same cell as its serving gateway, and change to another RSU when driving into another cell. Notice that vehicles will not change their serving RSU before their session ends. Advances in Technology Innovation, vol. 5, no. 1, 2020, pp. 56-63 60 Next, we further take the load indexes of RSUs and vehicular densities of road segments into consideration. The boundaries between RSUs adjust dynamically to adapt to loads and densities changes. To distinguish from the above method, we call this method as the Weighted Map-based Voronoi Diagram. We make the following modifications. First, we consider the weighted road lengths by the vehicular density of a load segment, instead of the actual lengths. Next, when calculating a midpoint, we select the point where the weighted path lengths from the point to two RSUs are inversely proportional to their load indexes. RSUs calculates the boundaries periodically to maintain the load balance among RSUs. The last boundary information is disseminated to vehicles by Geocast. Once a vehicle receives an updated boundaries information, it selects its serving RSU accordingly. 3.2. Vehicle -based mechanism In this type of solution, vehicles utilize their future trajectories and the last load indexes of RSUs to choose their serving gateways distributedly. We call this scheme as the Trajectory-based scheme since trajectories of vehicles play a major role in the design. Compared to the previous methods, there are no clear boundaries defining the serving ranges of RSUs. Moreover, this solution does not need the density information of road segments, since each vehicle select its RSU individually. Fig. 4 A vehicle samples its future trajectory with intersections to calculate a favor value of each RSU In this scheme, vehicles obtain the load index information from RSUs by Geocast periodically. Vehicles are aware of their future trajectories, which can be acquired from the GPS navigation system. Intersections on a vehicle’s trajectory are selected as representative points, as shown in Fig. 4. The path lengths from each representative point i to a nearby RSU j are estimated and denoted as  D i, j . An exponential decay function  H i is used to decay the influences of distancing intersections. Then, the vehicle calculates a favor value jF for each RSU j as,     0 1 D L j n ii F H i i, j       (2) where 0 , 1   . A vehicle selects the RSU with the largest favor value as its serving RSU. When a vehicle receives new load indexes of RSUs or arrives at a new intersection, the vehicle calculate the favor values of all RSUs to decide the best serving RSU. As mention above, vehicle will not change its serving RSU before its current session ends. Moreover, we use a predefined threshold to prevent a vehicle from changing its’ serving RSU frequently to avoid the Ping-Pong effect. 4. Simulation Results We develope simulations to compare the network performance of the proposed schemes. The simulations adopte a 6 * 6 grid network in a 6 km * 6 km area where the length of each segment is 1 km. There are 6 RSUs randomly deployed on different intersections. We generate 300 vehicles and the trajectory of each vehicle is the shortest path between a random Advances in Technology Innovation, vol. 5, no. 1, 2020, pp. 56-63 61 source and destination intersections. Communication ranges of vehicles and RSUs are the same, which is 350 m. To test heterogeneity and homogeneity of RSUs, we set RSUs with different bandwidths to the Internet, randomly between 5 ~ 20 Mbps in case 1 and equally 10 Mbps in case 2. Fig. 5 Packet Delivery Ratio with different request rates Fig. 6 End to End delay with different request rates We first compare the performance of the delivery ratio among Voronoi Diagram, Map-based Voronoi Diagram, Weighted Map-based Voronoi Diagram, and the distributed Trajectory-based method. The results are shown in Fig. 5. It illustrates the average successful packet delivery ratio among different request rates from source vehicles to a destination RSUs. At a low bit rate, the Weighted Map-based Voronoi Diagram and the Trajectory-based method have a lower delivery ratio due to the longer routing length. However, when the request bit rate increases, the delivery ratio of Voronoi Diagram and Map-based Voronoi Diagram decrease fast because some RSUs are over-loaded and dropping packets from their queues. Our proposed methods can relieve the problem of packet dropping and achieve better load balance. As shown in Fig 6, we compare the end-to-end delay of packets. In a low traffic condition, both of Weighted Map-based Voronoi Diagram and the Trajectory-based methods have a longer transmission delay resulted from choosing a farer serving RSU. However, when the request rate increases, both methods can benefit from the shorter queuing delay and reduce the overall end-to-end delay. In the following experiments, we evaluate the load balance effects of the proposed methods in homogeneous and heterogeneous RSU bandwidth settings. As shown in Fig. 7, both of Weighted Map-based Voronoi Diagram and the Trajectory-based methods can relieve the load unbalance problem among RSUs. The Weighted Map-based Voronoi Diagram method needs to monitor the load information of all RSUs and make the decisions of serving range of each RSU in a central server. Therefore, it is reasonable that it can achieve a better load-balanced status than Trajectory-based method. From Fig. 8, we find that some RSUs are overloaded when the request bit rate increases; however, our Weighted Map-based Voronoi Diagram and the Trajectory-based methods can eliminate this problem. (a) Heterogeneous bandwidths (case 1) (b) Homogeneous bandwidths (case 2) Fig. 7 The load balance index with different bandwidth settings of RSUs Advances in Technology Innovation, vol. 5, no. 1, 2020, pp. 56-63 62 (a) Heterogeneous bandwidths (case 1) (b) Homogeneous bandwidths (case 2) Fig. 8 The maximum load index among RSUs with different bandwidth settings of RSUs 5. Conclusions and Future works In this paper, we discuss the load unbalancing problem among RSUs in VANETs resulted from the uneven distribution of vehicles and heterogeneity of RSUs. Then, we proposed two schemes to solve the problem from different aspects. The first one is a centralized RSU-based method, and the second one is a distributed vehicle-based method. Both of the proposed methods can balance the loads among RSUs and improve the overall packet delivery ratio and latency. In the Weighted Map -based Voronoi Diagram, we divides the map into several cells and take the routing length, vehicular density, load indexes of RSUs into considerations. This centralized solution can balance the loads among RSUs better than the distributed method. However, it needs the vehicular density information and vehicles may change their serving RSU more frequently. Therefore, we propose a scalable distributed solution, called Trajectory-based method, without the demand of the vehicular density information. Moreover, it considers the future locations of vehicles when choosing serving RSU. As a result, it can prevent vehicles from changing their serving RSU frequently. In the future, we tend to use the historical records of vehicular density in a day to analysis the expected delivery ratio and delay to replace the routing length in the current design. In addition, we want to design a reservation mechanism. We will utilize the future trajectory of vehicles to calculate the suitable future serving RSU and reserve bandwidth. This may be able to achieve a better quality of service of vehicles and meanwhile maintain load balancing among RSUs. Acknowledgement The study is sponsored by Minister of Science and Technology, Taiwan under Grant No. MOST 107-2221-E-194-015. References [1] F. Cunha, L. Villas, A. Boukerche, G. Maia, A. Viana, R. A. F. Mini, and A. A. F. Loureiro, “Data communication in VANETs: protocols, applications and challenges,” Ad Hoc Networks, vol. 44, pp. 90-103, July 2016. [2] M. K. Priyan and G. U. Devi, “A survey on internet of vehicles: applications, technologies, challenges and opportunities,” International Journal of Advanced Intelligence Paradigms, vol. 12, no. 1-2, pp. 98-119, 2019. [3] C. Englund, L. Chen, A. Vinel, and S. Y. Lin, “Future applications of VANETs,” In Vehicular Ad Hoc Networks; C. Campolo, A. Molinaro, and R. Scopigno, Eds., Springer International Publishing: Switzerland, pp. 525-544, 2015. [4] H. Zhu, K. V. Yuen, L. Mihaylova, and H. Leung, “Overview of environment perception for intelligent vehicles,” IEEE Transactions on Intelligent Transportation Systems, vol. 18, no. 10, pp. 2584-2601, October 2017. [5] C. F. Huang and Y. H. Chen, “Message-efficient route planning based on comprehensive real-time traffic map in VANETs”, Proceedings of Engineering and Technology Innovation, vol. 9, pp. 25-31, 2018. [6] E. Uhlemann, “Introducing connected vehicles,” IEEE Vehicular Technology Magazine, vol. 10, no. 1, pp. 23-31, March 2015. [7] I. Wahid, A. A. Ikram, M. Ahmad, S. Ali, and A. Ali, “State of the art routing protocols in VANETs: a review,” Procedia Computer Science, vol. 130, pp. 689-694, 2018. Advances in Technology Innovation, vol. 5, no. 1, 2020, pp. 56-63 63 [8] S. Boussoufa-Lahlah, F. Semchedine, and L. Bouallouche-Medjkoune, “Geographic routing protocols for vehicular ad hoc networks (VANETs): a survey,” Vehicular Communications, vol. 11, pp. 20-31, January 2018. [9] V. Naumov, R. Baumann, and T. Gross, “An evaluation of inter-vehicle ad hoc networks based on realistic vehicular traces,” Proc. of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 2006, pp. 108-119. [10] V. Naumov and T. Gross, “Connectivity-aware routing (CAR) in vehicular ad-hoc networks,” IEEE INFOCOM 2007-26th IEEE International Conference on Computer Communications, 2007, pp. 1919-1927. [11] M. Jerbi, S. M. Seouci, R. Meraihi, and Y. Ghamri-Doudane, “An improved vehicular ad hoc routing protocol for city environments,” IEEE International Conference on Communications, May 2007, pp. 3972-3979. [12] P. Prithviraj and G. Aniruddha, “Maximizing vehicular network connectivity through an effective placement of road side units using voronoi diagrams,” IEEE 13th International Conference on Mobile Data Management, July 2012, pp. 274-275. [13] U. F. Mohd and P. Mohammed, “Integration of vehicular roadside access and the internet: challenges & a review of strategies,” IEEE 2012 International Conference on Devices, Circuits and Systems, March 2012, pp. 568-571. [14] G. N. Alia, P. H. J. Chong, S. K. Samantha, and E. Chan, “Efficient data dissemination in cooperative multi-RSU vehicular ad hoc networks (VANETs),” Journal of Systems and Software, vol. 117, pp. 508-527, July 2016. [15] Y. Dai, D. Xu, S. Maharjan, and Y. Zhang, “Joint load balancing and offloading in vehicular edge computing and networks,” IEEE Internet of Things Journal (Early Access), vol. 6, no. 3, pp. 4377-4387, June 2019. [16] Y. Bejerano and S. J. Han, “Cell breathing techniques for load balancing in wireless LANs,” IEEE Transactions on Mobile Computing, vol. 8, no. 6, pp. 735-749, June 2009. [17] F. Aurenhammer, “Voronoi diagrams: a survey of a fundamental geometric data structure,” ACM Computing Survey, vol. 23, no. 3, pp. 345-405, September 1991. Copyright© by the authors. Licensee TAETI, Taiwan. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY-NC) license (https://creativecommons.org/licenses/by-nc/4.0/).