# Adaptive Configuration of Mobile Roadside Units for the Cost-Effective Vehicular Communication Infrastructure

Authors: Jaeho Lee; Sanghyun Ahn
Journal: Wireless Communications and Mobile Computing
 (2019)

---

## Abstract

In this paper, we target to figure out an adaptive and efficient mechanism that deploys roadside units (RSUs), which are the major components of the vehicle-to-infrastructure (V2I) communication, so that vehicles on the road can have satisfactory connectivity to the vehicular communication infrastructure in a cost-effective way. Only with the conventional fixed RSUs (fRSUs), the coverage requirement of vehicles from the perspective of V2I communications cannot be easily met because of high vehicular mobility compared to the static nature of fRSUs and the high deployment and operational expenditure of fRSUs. Recently, mobile RSUs (mRSUs) mounted on public and commercial vehicles like buses are considered as the substitutes or the supplements of fRSUs. The research on mRSUs is in its early stage and mostly focuses on the deployment of mRSUs from a static viewpoint. In this paper, we consider the environment with densely deployed mRSUs, such as the city environment, thanks to low cost, in which multiple active mRSUs generate lots of control messages to form the mRSU backbone network. To overcome this inefficiency, we propose a mechanism in which each mRSU adaptively and effectively determines its own state, active or inactive, according to the states of its neighboring mRSUs and vehicles. For the NP-hardness proof, we formulate the problem as a 0-1 integer linear programming problem. We evaluate the performance of our mechanism in terms of the ratio of vehicles covered by active mRSUs and the control message overhead compared with the case of nonadaptive mRSU configuration (i.e., the case of all mRSU being active).


---

## Body

## 1. Introduction

The vehicular communication infrastructure plays the role of the backbone of the intelligent transportation system (ITS) and the main component of the vehicular communication infrastructure is the roadside unit (RSU) [1–3]. Each RSU provides the vehicle-to-infrastructure (V2I) communication to the vehicles in its coverage area. RSUs may be mounted on fixed roadside structures such as traffic signal controllers. Installing and maintaining RSUs require high capital expenditure (CAPEX) and operational expenditure (OPEX), resulting in sparsely placed RSUs which incur frequent handovers between RSUs and, much worse, intermittent disconnections to RSUs. Vehicles not covered by any RSUs can overcome the disconnection via vehicle-to-vehicle (V2V) communications. Even though the V2V communication can be a means of providing the indirect connectivity to the vehicular communication infrastructure, i.e., RSUs, the multihop wireless communication via vehicles causes unstable communication quality and longer delay.Therefore, optimal placement of fixed RSUs (fRSUs) has been studied by some researchers from the perspective of cost, coverage, etc. [4–7], but it still has the limitation caused by high CAPEX and OPEX. In order to overcome this limitation, mobile RSUs (mRSUs) can be utilized in addition to the fixed RSUs (fRSUs) [8–13]. Public and commercial vehicles, such as buses and trucks, can be easily equipped with both the dedicated short-range communication (DSRC) [14] and the cellular communication [15, 16] modules, resulting in lower CAPEX and OPEX compared to fRSUs because public and commercial vehicles are well managed by their operational institutes. The DSRC operates in the unlicensed band of 5.850~5.925 GHz based on the IEEE 802.11p defined specifically for vehicular communications, but it has the drawback of being not adequate for time-sensitive or critical applications especially in the densely deployed vehicular communication environment. On the other hand, the cellular communication technology has been advanced to 4G-LTE and 5G which can meet the real-time requirements of various time-stringent applications. Therefore, the vehicles equipped with both DSRC and 4G or 5G modules can play the role of mRSUs with using the DSRC module for V2V and V2I communications with no extra communication cost except for device installation cost and the cellular communication module for the global Internet connectivity or for the applications with strict timing requirements. In recent years, 3GPP has been standardizing the cellular V2X (C-V2X) based on LTE and 5G. The communication range of C-V2X is almost twice of DSRC and the response time is almost 1/3 of DSRC. C-V2X supports both direct (V2V and V2I) and wide area cellular network (V2N) communication modes which can be integrated into a single chipset, so C-V2X can be solely installed in mRSUs.With the help of mRSUs deployed on the road, vehicles can communicate with anything in the Internet via more stable V2I communications in a cost-effective and flexible way, resulting in rare disconnections. Moreover, because mRSUs move on the road along with other vehicles, vehicles can easily sustain its connectivity to a specific mRSU at their will, maintaining high V2I communication quality. Recently, the deployment and the routing issues of mRSUs have been studied by researchers [8–13], but the study on mRSUs is still in its early stage and there are many issues left to be resolved.Thanks to low CAPEX and OPEX, mRSUs are expected to be easily deployed and, as a result, vehicles may be covered by multiple mRSUs, especially in the urban environment. In order to have the global Internet connectivity, vehicles are required to make association with mRSUs and, for that, mRSUs periodically advertise their existence to their neighboring mRSUs and vehicles. If there are too many mRSUs in an area, too many control messages will be generated for the maintenance of the mRSU backbone network and, in turn, cause traffic congestion and collisions. This drawback can be resolved if only a subset of mRSUs is activated without deteriorating the connectivity to vehicles. Up to our knowledge, this issue has not been addressed so far by any researchers, and the previous work on mRSUs focuses on how to optimally deploy mRSUs and on how to route data packets based on the already deployed mRSUs.In this paper, we will focus on the issue of optimal maintenance of the mRSU backbone network. For that, we define the mRSU backbone network problem as a 0-1 integer linear programming problem and propose an adaptive mRSU configuration mechanism in which each mRSU determines whether it turns on or off its mRSU functionality based on the information collected from its neighboring mRSUs and vehicles. For the performance evaluation of the proposed mechanism, we carry out simulations using the vehicular network simulation framework Veins 4.6 [16] based on SUMO [17] and OMNet++ [18] and compare ours with the ideal case (i.e., the lower bound case in which each ON-state mRSU covers vehicles in its full capacity) and the nonadaptive case (i.e., the case in which all mRSUs are active).The rest of the paper is organized as follows. In Section2, we describe the related work on the deployment issue of RSUs. In Section 3, the adaptive mRSU configuration problem is formulated as a 0-1 integer linear programming problem for the proof of the NP-hardness of the problem and, then, our adaptive mRSU configuration mechanism is explained in detail. The performance evaluation of our mechanism is given in Section 4. Finally, Section 5 concludes this paper.


## 2. Related Work

In the vehicular communication environment, RSUs provide the global Internet connectivity to vehicles. A vehicle can be associated with an RSU once it moves into the coverage area of the RSU and, then, gets the connectivity to the global Internet through the RSU. Thus, the way that RSUs are deployed is the most important factor that affects the quality of the global Internet connectivity of vehicles. In this section, we will go over the previous work on the deployment of fRSUs and, then, that of mRSUs.The main issue of the fRSU deployment is the cost effectiveness because of the high fRSU installation and maintenance cost. Papers [4, 5] are similar in that roads are divided into cells [4] and zones [5] and both of them use the number of vehicles in a cell/zone as the affecting factor of determining the number of fRSUs to be placed in the cell/zone. In [4], the cell with more vehicles is deployed with more fRSUs so that more vehicles can be accommodated by fRSUs. On the other hand, [5] places more fRSUs in a zone with less vehicles because less vehicles imply worse for V2V communications (that is, V2I communications based on fRSUs are more in need). In [6], fRSUs are placed so that more intersections can be covered by less fRSUs because intersections are the best places for the collection of road traffic information and the intersections interconnected by fRSUs allow communications among them through fRSUs. Paper [7] divides roads into segments and chooses the segments with low vehicle density (i.e., the segments with worse V2V communication quality) as the candidates for fRSU placement. Due to high deployment cost of fRSUs, it is impractical to cover all the vehicles with only a given number of fRSUs, so mRSUs can be attractive candidates for substituting or complementing fRSUs.The concept of the mobile gateway is proposed in [8] and mobile gateways are specific vehicles with cellular communication capabilities for the global Internet connectivity. However, the deployment issue of mRSUs has not been considered in [8]. Papers [9–11] propose to use buses as the mobile communication infrastructure as shown in Figure 1, where vehicles are connected to buses to get the global Internet connectivity without using V2V communications. They focus only on routing through the mobile communication infrastructure and do not consider the deployment issue of mRSUs.Figure 1
Vehicular communication backbone network based on the mobile communication infrastructure.In [12, 13], the authors classify RSUs into three types, fRSUs (D-Type 1), mRSUs not controllable by an organization (D-Type 2), and mRSUs controllable by an organization (D-Type 3), and try to maximize the communication coverage by placing the optimal number of RSUs of each type at the optimal places within the given budget. Once the number of RSUs of each type and the places are decided, D-Type 3 RSUs are placed in the areas not covered by D-Type 1 and 2 RSUs. The equal portion of the budget is allotted to D-Type 1 and 2 RSUs, respectively, and the remaining budget, the largest portion, to D-Type 3 RSUs. This budget allotment implies that mRSUs are better solutions for the extension of communication coverage than fRSUs. Table 1 summarizes the features of the abovementioned mechanisms.Table 1
Previous work on RSUs.
RSU Type Year Reference Main Features fRSU 2014 [4] (i) Roads are divided into cells(ii) More fRSUs are deployed in a cell with more vehicles  fRSU 2013 [5] (i) Roads are divided into zones(ii) Less fRSUs are deployed in a zone with more vehicles  fRSU 2013 [6] (i) More intersections are covered by less fRSUs  fRSU 2015 [7] (i) Roads are divided into segments(ii) More fRSUs are deployed in a cell with less vehicles  mRSU 2011 [8] (i) Certain vehicles are used as mobile gateways (mRSUs) to extend the coverage of fRSUs(ii) A position-based routing protocol based on V2V and V2I communications is proposed(iii) No deployment issue of mRSUs is covered  mRSU 2010 [9] (i) Buses (mRSUs) form mobile infrastructure(ii) A position-based routing protocol is proposed based on the transmission quality of each road segment(iii) No deployment issue of mRSUs is covered  mRSU 2010 [10] (i) Buses (mRSUs) form mobile infrastructure(ii) Each vehicle registers with a bus(iii) A position-based routing protocol is proposed based on the transmission quality of each road segment(iv) No deployment issue of mRSUs is covered  mRSU 2013 [11] (i) Buses (mRSUs) form mobile infrastructure(ii) Each vehicle registers with a bus or fRSU that can have the longest registration time(iii) No deployment issue of mRSUs is covered  fRSU 2016 [12] (i) Two types of mRSUs are defined according to whether the mRSU is controllable by an organization or not(ii) According to the RSU types and the given budget, the placement of RSUs is determined (iii) Uncontrollable mRSUs are given with the largest portion of the budget mRSU 2017 [13]As we can see in the previous work on RSUs, mRSUs can be more easily deployed than fRSUs thanks to low CAPEX and OPEX of mRSUs. Especially in a city environment with well-developed public and commercial transportation systems, some spots may have densely deployed mRSUs like WiFi jungles. The environment with densely deployed mRSUs is different from the WiFi jungle in that mRSUs form a wireless backbone network (from now on, we call this the mRB network) as shown in Figure1. If there are too many mRSUs, the overhead of maintaining the mRB network will be overwhelming. Besides, the management of the mRB network will be intricate due to the high-speed mobility of mRSUs. To the best of our knowledge, this issue has not been considered by the previous work on mRSUs. Therefore, in this paper, we propose a mechanism that allows mRSUs to adaptively form the mRB network in a distributed manner by having each mRSU determine whether to activate or inactivate its mRSU functionality according to its nearby situation such as its neighboring mRSU and vehicle status.


## 3. Adaptive Mobile RSU Backbone Network Configuration

### 3.1. System Environment and Problem Description

For the sake of simplicity, we assume that the maximum capacity of each mRSU is the same asC in the unit of vehicles. An mRSU can be in one of the states, ON or OFF, which is set according to the states and the remaining capacities of its neighboring mRSUs and the status of its neighboring vehicles. In order to have the global Internet connectivity, a vehicle has to associate with an ON-state mRSU whose remaining capacity is enough to accommodate the vehicle. The problem that we aim to solve is to find the optimal mRB network composed of the minimum number of ON-state mRSUs. The notations needed for the problem formulation are listed in Table 2.Table 2
Notations for the definition of the optimal mRB network problem.
Notation Description V The set of all the vehicles;V=v1,…,vα  M The set of all the mRSUs;M=m1,…,mβ  y j The binary variable indicating the state of mRSUmj; yj=1,ifmjisON0,otherwise  x i j The binary variable indicating the association relationship between vehiclevi and mRSU mj; xij=1,ifviisassociatedwithmj0,otherwiseV is the vehicle set with α vehicles and M is the mRSU set with β mRSUs. xij is the binary variable indicating whether vehicle vi is associated with mRSU mj, and yj is the binary variable indicating whether mRSU mj is ON. The problem of finding the optimal mRB network composed of the minimum number of mRSUs with the ON state can be defined as follows:(1)min∑∀jyj(2)Subjectto:∑∀i,jxij=V,wherei∈1,…,αandj∈1,…,β(3)∑∀jxij=1,foreachi(4)∑∀ixij≤C,foreachj(5)xij∈0,1(6)yj=1,if∑∀ixij>00,otherwiseEquation (1) is the objective function and (5) and (6) are about binary variables xij and yj, respectively. xij=1 indicates that vehicle vi is associated with mRSU mj. yj indicates the state of mRSU mj; that is, yj is 1 if there exists at least one vehicle associated with mj (i.e., mj is ON). Equations (2) and (3) mean that each vehicle in V must be associated with only one mRSU. Equation (4) is the constraint that an mRSU can associate with vehicles within its maximum capacity C.Because the optimal mRB network problem is formulated as a 0-1 integer linear programming problem, the problem is NP-hard [19]. Thus, we propose a heuristic mechanism that adaptively configures the mRB network in the following subsection.


### 3.2. Adaptive State Determination of mRSUs

In Section3.1, we mentioned that the possible states of an mRSU are ON and OFF. By adjusting the state of each mRSU, the total number of active mRSUs is controlled so that unnecessary mRSUs can turn off its functionality. mRSUs and vehicles periodically broadcast their own information to 1-hop neighboring mRSUs. For the prevention of the frequent state changes, we introduce one more state, T_OFF (Tentative_OFF) (for the T_OFF state, yk=0). The initial state of each mRSU is ON and, later on, according to the network situation, it may change its state to T_OFF before it proceeds to the OFF state. In the T_OFF state, the mRSU acts as if it is in the ON state except for not accepting new association requests. After a given time interval, if the condition for the state change from T_OFF to OFF is not met, it returns back to the ON state. On the other hand, the state change from OFF to ON is done immediately once the corresponding condition is satisfied. This immediate state change to ON is to reduce the possibility of disconnections to the mRB network. The conditions for state changes will be defined later in this subsection.Table3 summarizes the operation of mRSUs according to the state and, along with that, we define several message types. The mRSU_Information (mR_INFO) message is periodically (with the period of τM) broadcast by an mRSU to its neighboring mRSUs to inform them of its state, the number of its associated vehicles, the number of its neighboring vehicles, etc. The mRSU_Service_Available (mR_SA) message is periodically (with the period of τS) broadcast by an mRSU to its neighboring vehicles to advertise that it is an active mRSU and ready to receive association requests. The mRSU_Service_Unavailable (mR_SU) message is sent by an mRSU to its neighboring vehicles to force its associated vehicles to make new association with other mRSUs. The Vehicle_Information (V_INFO) message is periodically (with the period of τV) broadcast by a vehicle to its neighboring mRSUs to let them know of its status like the associated mRSU and the mRSU bloom filter. The mRSU bloom filter is the bloom filter [20] with the compressed information of the neighboring mRSUs of the vehicle and this information is used in the state change decision. With the bloom filter, we can keep the size of the V_INFO message constant, independent of the number of the neighboring mRSUs. For association, a vehicle sends a Vehicle_Association_Request (V_AR) message to an mRSU and the mRSU accepts the request by sending back an mRSU_Association_Response (mR_AR) message. Then, the vehicle confirms it by sending a Vehicle_Association_Confirm (V_AC) message to the mRSU.Table 3
The operation of an mRSU according to its state.
State Operation ON (i) Periodically broadcast an mR_SA message to its neighboring vehicles (ii) Receive V_INFO messages from its neighboring vehicles (iii) Periodically broadcast an mR_INFO message to its neighboring mRSUs (iv) Accept the association requests from its neighboring vehicles  T_OFF (i) Broadcast an mR_SU message to its associated vehicles (ii) Receive V_INFO messages from its neighboring vehicles (iii) Periodically broadcast an mR_INFO message to its neighboring mRSUs (iv) Ignore any association requests from its neighboring vehicles (v) Overhear and collect the V_AC messages from its associated vehicles  OFF (i) Receive V_INFO messages from its neighboring vehicles (ii) Periodically broadcast an mR_INFO message to its neighboring mRSUs (iii) Ignore any association requests from its neighboring vehiclesFor the state determination procedure, the additional notations are defined in Table4.Table 4
Notations for the adaptive state determination of mRSUs.
Notation Description V j N The set of all the neighboring vehicles of mRSUmj  V j A The set of all the associated vehicles of mRSUmj; VjA⊆VjN,VjA=∑∀ixij  V j A - The set of all the neighboring vehicles of mRSUmj which are not associated with any mRSUs; VjA-⊆VjN,VjA-=VjN-∑∀vi∈VjN∑∀kxik×yk  f i The mRSU bloom filter of vehiclevi  M j N The set of the neighboring mRSUs of mRSUmj  M i F N The set of the mRSUs included infi  M i j N The set of the mRSUs included in bothMiFN and MjN; vi∈VjN  θ A The threshold used for the state change from ON to OFF  c j R The number of vehicles that can be additionally associated with mRSUmj; the remaining capacity of mj; cjR=C-VjA  C k N R The set ofcjR’s of the neighboring mRSU mj’s of mRSU mk  p i k The transferability of vehiclevi to a new mRSU from mRSU mk in the case that mk changes its state to OFF; vi∈VkA,pik=1,if∑∀mj∈MikNyj×cjR>θpforj≠k0,otherwise  θ p The threshold for determining the value ofpik  δ The parameter controlling the probability of an OFF-state mRSU to become the ON-state;δ is a positive integer; the larger δ is, the higher the probability is  τ M The broadcast period of the mR_INFO message  τ A The time spent for association;τA<τM  τ S The broadcast period of the mR_SA message;τS<τM  τ V The broadcast period of the V_INFO message;τV<τM  t 0 The start time of the ON or OFF stateThe state determination factors of an mRSU are the number of its associated vehicles and the transferability of its associated vehicles. Each mRSU checks the state change condition for everyτM interval. mRSU mk compares the number of its associated vehicles, VkA, with the threshold θA and, if VkA<θA, mk compares its remaining capacity ckR with the largest remaining capacity of its neighboring mRSUs, MaxsetCkNR. If ckR>MaxsetCkNR, mk computes the transferability pik of each of its own associated vehicles, vi, which indicates whether vi can be newly associated with another RSU. If all of its associated vehicles have the possibility of transferring to the other mRSUs (i.e., ∑∀vi∈VkNpik=VkA), mk changes its state to T_OFF and broadcasts an mR_SU message. Then, during the time interval τA, it overhears Vehicle_Association_Confirm (V_AC) messages to check whether all of its associated vehicles have made new associations with the other mRSUs (i.e., ∑∀vi∈VkAxik=0). If ∑∀vi∈VkAxik=0, it changes its state to OFF. Otherwise (i.e., if ∑∀vi∈VkAxik>0), it goes back to the ON state and broadcasts an mR_SA message to its neighboring vehicles. The conditions, CD1~CD4, for state changes at mRSU mk are summarized in Table 5. MaxsetCkNR in CD1 is the function that returns the largest cjR in CkNR.Table 5
Conditions for state changes of mRSUmk.
State Change Condition CD1 ON→T_OFF T ≥ t 0 + τ M   a n d   M k N ≠ ∅   a n d   V k A < θ A   a n d   c k R > M a x s e t C k N R   a n d    ∑ ∀ v i ∈ V k N p i k = V k A  CD2 T_OFF→OFF T ≥ t 0 + τ M + τ A   a n d   ∑ ∀ v i ∈ V k A x i k = 0  CD3 T_OFF→ON T ≥ t 0 + τ M + τ A   a n d   ∑ ∀ v i ∈ V k A x i k > 0  CD4 OFF→ON T ≥ t 0 + τ M   a n d   ∑ ∀ m j ∈ M k N y j × c j R < V k A -   a n d   u n i f 1 ,  1 + M k N - ∑ ∀ m j ∈ M k N y j δ × V k A - - ∑ ∀ m j ∈ M k N y j × c j R / C = 1The state of mRSUmk is changed from OFF to ON if Conditions (i) and (ii) are satisfied.Condition (i). If the total remaining capacity of its neighboring ON-state mRSUs, ∑∀mj∈MkNyj×cjR, is less than the number of its nonassociated neighboring vehicles, VkA-; that is,mk may become ON if the neighboring ON-state mRSUs cannot accommodate all the nonassociated vehicles of mk and Condition (ii) is satisfied.Condition (ii). If the outcome value of the discrete uniform distribution between 1 and the ratio of one (i.e., including mk) plus the number of the OFF-state neighboring mRSUs, 1+MkN-∑∀mj∈MkNyj, to the number of the OFF-state mRSUs required to accommodate the nonassociated vehicles not covered by the ON-state neighboring mRSUs, VkA-∑∀mj∈MkNyj×cjR, times δ is equal to 1. In other words, if Condition (i) is satisfied, the state of mk can be ON with the probability of 1/1+MkN-∑∀mj∈MkNyj/δ×VkA--∑∀mj∈MkNyj×cjR/C; the larger δ is, the higher the possibility of mk becoming the ON state is.Figure2 shows the state change from the left to the right along the time axis for each scenario. In the figure, the white and the black solid line bars mean the ON and the OFF states, respectively, and the white dotted line bar implies the T_OFF state.Figure 2
Scenarios of state changes.The state transition diagram of the mRSU is shown in Figure3. In the figure, T is the current time at the start and r is the count of the τM-periods during which the mRSU keeps staying in the ON state. r and θC prevent a new ON-state mRSU from a premature state change from ON to OFF and at least (θC+1)τM-periods are required for a new ON-state mRSU to check the condition for T_OFF.Figure 3
State transition diagram of mRSUmk.There can be multiple ON-state neighboring mRSUs and, in that case, the vehicle chooses the mRSU with the smallest remaining capacity in order to minimize the number of ON-state mRSUs. If there is no neighboring ON-state mRSU, the vehicle makes indirect association via V2V communications. We call the association through V2V communication the indirect association and the association through V2I communication the direct association.


## 3.1. System Environment and Problem Description

For the sake of simplicity, we assume that the maximum capacity of each mRSU is the same asC in the unit of vehicles. An mRSU can be in one of the states, ON or OFF, which is set according to the states and the remaining capacities of its neighboring mRSUs and the status of its neighboring vehicles. In order to have the global Internet connectivity, a vehicle has to associate with an ON-state mRSU whose remaining capacity is enough to accommodate the vehicle. The problem that we aim to solve is to find the optimal mRB network composed of the minimum number of ON-state mRSUs. The notations needed for the problem formulation are listed in Table 2.Table 2
Notations for the definition of the optimal mRB network problem.
Notation Description V The set of all the vehicles;V=v1,…,vα  M The set of all the mRSUs;M=m1,…,mβ  y j The binary variable indicating the state of mRSUmj; yj=1,ifmjisON0,otherwise  x i j The binary variable indicating the association relationship between vehiclevi and mRSU mj; xij=1,ifviisassociatedwithmj0,otherwiseV is the vehicle set with α vehicles and M is the mRSU set with β mRSUs. xij is the binary variable indicating whether vehicle vi is associated with mRSU mj, and yj is the binary variable indicating whether mRSU mj is ON. The problem of finding the optimal mRB network composed of the minimum number of mRSUs with the ON state can be defined as follows:(1)min∑∀jyj(2)Subjectto:∑∀i,jxij=V,wherei∈1,…,αandj∈1,…,β(3)∑∀jxij=1,foreachi(4)∑∀ixij≤C,foreachj(5)xij∈0,1(6)yj=1,if∑∀ixij>00,otherwiseEquation (1) is the objective function and (5) and (6) are about binary variables xij and yj, respectively. xij=1 indicates that vehicle vi is associated with mRSU mj. yj indicates the state of mRSU mj; that is, yj is 1 if there exists at least one vehicle associated with mj (i.e., mj is ON). Equations (2) and (3) mean that each vehicle in V must be associated with only one mRSU. Equation (4) is the constraint that an mRSU can associate with vehicles within its maximum capacity C.Because the optimal mRB network problem is formulated as a 0-1 integer linear programming problem, the problem is NP-hard [19]. Thus, we propose a heuristic mechanism that adaptively configures the mRB network in the following subsection.


## 3.2. Adaptive State Determination of mRSUs

In Section3.1, we mentioned that the possible states of an mRSU are ON and OFF. By adjusting the state of each mRSU, the total number of active mRSUs is controlled so that unnecessary mRSUs can turn off its functionality. mRSUs and vehicles periodically broadcast their own information to 1-hop neighboring mRSUs. For the prevention of the frequent state changes, we introduce one more state, T_OFF (Tentative_OFF) (for the T_OFF state, yk=0). The initial state of each mRSU is ON and, later on, according to the network situation, it may change its state to T_OFF before it proceeds to the OFF state. In the T_OFF state, the mRSU acts as if it is in the ON state except for not accepting new association requests. After a given time interval, if the condition for the state change from T_OFF to OFF is not met, it returns back to the ON state. On the other hand, the state change from OFF to ON is done immediately once the corresponding condition is satisfied. This immediate state change to ON is to reduce the possibility of disconnections to the mRB network. The conditions for state changes will be defined later in this subsection.Table3 summarizes the operation of mRSUs according to the state and, along with that, we define several message types. The mRSU_Information (mR_INFO) message is periodically (with the period of τM) broadcast by an mRSU to its neighboring mRSUs to inform them of its state, the number of its associated vehicles, the number of its neighboring vehicles, etc. The mRSU_Service_Available (mR_SA) message is periodically (with the period of τS) broadcast by an mRSU to its neighboring vehicles to advertise that it is an active mRSU and ready to receive association requests. The mRSU_Service_Unavailable (mR_SU) message is sent by an mRSU to its neighboring vehicles to force its associated vehicles to make new association with other mRSUs. The Vehicle_Information (V_INFO) message is periodically (with the period of τV) broadcast by a vehicle to its neighboring mRSUs to let them know of its status like the associated mRSU and the mRSU bloom filter. The mRSU bloom filter is the bloom filter [20] with the compressed information of the neighboring mRSUs of the vehicle and this information is used in the state change decision. With the bloom filter, we can keep the size of the V_INFO message constant, independent of the number of the neighboring mRSUs. For association, a vehicle sends a Vehicle_Association_Request (V_AR) message to an mRSU and the mRSU accepts the request by sending back an mRSU_Association_Response (mR_AR) message. Then, the vehicle confirms it by sending a Vehicle_Association_Confirm (V_AC) message to the mRSU.Table 3
The operation of an mRSU according to its state.
State Operation ON (i) Periodically broadcast an mR_SA message to its neighboring vehicles (ii) Receive V_INFO messages from its neighboring vehicles (iii) Periodically broadcast an mR_INFO message to its neighboring mRSUs (iv) Accept the association requests from its neighboring vehicles  T_OFF (i) Broadcast an mR_SU message to its associated vehicles (ii) Receive V_INFO messages from its neighboring vehicles (iii) Periodically broadcast an mR_INFO message to its neighboring mRSUs (iv) Ignore any association requests from its neighboring vehicles (v) Overhear and collect the V_AC messages from its associated vehicles  OFF (i) Receive V_INFO messages from its neighboring vehicles (ii) Periodically broadcast an mR_INFO message to its neighboring mRSUs (iii) Ignore any association requests from its neighboring vehiclesFor the state determination procedure, the additional notations are defined in Table4.Table 4
Notations for the adaptive state determination of mRSUs.
Notation Description V j N The set of all the neighboring vehicles of mRSUmj  V j A The set of all the associated vehicles of mRSUmj; VjA⊆VjN,VjA=∑∀ixij  V j A - The set of all the neighboring vehicles of mRSUmj which are not associated with any mRSUs; VjA-⊆VjN,VjA-=VjN-∑∀vi∈VjN∑∀kxik×yk  f i The mRSU bloom filter of vehiclevi  M j N The set of the neighboring mRSUs of mRSUmj  M i F N The set of the mRSUs included infi  M i j N The set of the mRSUs included in bothMiFN and MjN; vi∈VjN  θ A The threshold used for the state change from ON to OFF  c j R The number of vehicles that can be additionally associated with mRSUmj; the remaining capacity of mj; cjR=C-VjA  C k N R The set ofcjR’s of the neighboring mRSU mj’s of mRSU mk  p i k The transferability of vehiclevi to a new mRSU from mRSU mk in the case that mk changes its state to OFF; vi∈VkA,pik=1,if∑∀mj∈MikNyj×cjR>θpforj≠k0,otherwise  θ p The threshold for determining the value ofpik  δ The parameter controlling the probability of an OFF-state mRSU to become the ON-state;δ is a positive integer; the larger δ is, the higher the probability is  τ M The broadcast period of the mR_INFO message  τ A The time spent for association;τA<τM  τ S The broadcast period of the mR_SA message;τS<τM  τ V The broadcast period of the V_INFO message;τV<τM  t 0 The start time of the ON or OFF stateThe state determination factors of an mRSU are the number of its associated vehicles and the transferability of its associated vehicles. Each mRSU checks the state change condition for everyτM interval. mRSU mk compares the number of its associated vehicles, VkA, with the threshold θA and, if VkA<θA, mk compares its remaining capacity ckR with the largest remaining capacity of its neighboring mRSUs, MaxsetCkNR. If ckR>MaxsetCkNR, mk computes the transferability pik of each of its own associated vehicles, vi, which indicates whether vi can be newly associated with another RSU. If all of its associated vehicles have the possibility of transferring to the other mRSUs (i.e., ∑∀vi∈VkNpik=VkA), mk changes its state to T_OFF and broadcasts an mR_SU message. Then, during the time interval τA, it overhears Vehicle_Association_Confirm (V_AC) messages to check whether all of its associated vehicles have made new associations with the other mRSUs (i.e., ∑∀vi∈VkAxik=0). If ∑∀vi∈VkAxik=0, it changes its state to OFF. Otherwise (i.e., if ∑∀vi∈VkAxik>0), it goes back to the ON state and broadcasts an mR_SA message to its neighboring vehicles. The conditions, CD1~CD4, for state changes at mRSU mk are summarized in Table 5. MaxsetCkNR in CD1 is the function that returns the largest cjR in CkNR.Table 5
Conditions for state changes of mRSUmk.
State Change Condition CD1 ON→T_OFF T ≥ t 0 + τ M   a n d   M k N ≠ ∅   a n d   V k A < θ A   a n d   c k R > M a x s e t C k N R   a n d    ∑ ∀ v i ∈ V k N p i k = V k A  CD2 T_OFF→OFF T ≥ t 0 + τ M + τ A   a n d   ∑ ∀ v i ∈ V k A x i k = 0  CD3 T_OFF→ON T ≥ t 0 + τ M + τ A   a n d   ∑ ∀ v i ∈ V k A x i k > 0  CD4 OFF→ON T ≥ t 0 + τ M   a n d   ∑ ∀ m j ∈ M k N y j × c j R < V k A -   a n d   u n i f 1 ,  1 + M k N - ∑ ∀ m j ∈ M k N y j δ × V k A - - ∑ ∀ m j ∈ M k N y j × c j R / C = 1The state of mRSUmk is changed from OFF to ON if Conditions (i) and (ii) are satisfied.Condition (i). If the total remaining capacity of its neighboring ON-state mRSUs, ∑∀mj∈MkNyj×cjR, is less than the number of its nonassociated neighboring vehicles, VkA-; that is,mk may become ON if the neighboring ON-state mRSUs cannot accommodate all the nonassociated vehicles of mk and Condition (ii) is satisfied.Condition (ii). If the outcome value of the discrete uniform distribution between 1 and the ratio of one (i.e., including mk) plus the number of the OFF-state neighboring mRSUs, 1+MkN-∑∀mj∈MkNyj, to the number of the OFF-state mRSUs required to accommodate the nonassociated vehicles not covered by the ON-state neighboring mRSUs, VkA-∑∀mj∈MkNyj×cjR, times δ is equal to 1. In other words, if Condition (i) is satisfied, the state of mk can be ON with the probability of 1/1+MkN-∑∀mj∈MkNyj/δ×VkA--∑∀mj∈MkNyj×cjR/C; the larger δ is, the higher the possibility of mk becoming the ON state is.Figure2 shows the state change from the left to the right along the time axis for each scenario. In the figure, the white and the black solid line bars mean the ON and the OFF states, respectively, and the white dotted line bar implies the T_OFF state.Figure 2
Scenarios of state changes.The state transition diagram of the mRSU is shown in Figure3. In the figure, T is the current time at the start and r is the count of the τM-periods during which the mRSU keeps staying in the ON state. r and θC prevent a new ON-state mRSU from a premature state change from ON to OFF and at least (θC+1)τM-periods are required for a new ON-state mRSU to check the condition for T_OFF.Figure 3
State transition diagram of mRSUmk.There can be multiple ON-state neighboring mRSUs and, in that case, the vehicle chooses the mRSU with the smallest remaining capacity in order to minimize the number of ON-state mRSUs. If there is no neighboring ON-state mRSU, the vehicle makes indirect association via V2V communications. We call the association through V2V communication the indirect association and the association through V2I communication the direct association.


## 4. Performance Evaluation

We carried out simulations by using the vehicular network simulation framework Veins [16] based on SUMO [17] and OMNet++ [18]. The simulation network is configured as the 2,500m-long 4-lane road with vehicles moving at the speed of 50~70km/h and mRSUs at 55~65km/h. The intervehicle distance (including mRSUs) is set to 45m and the maximum capacity of an mRSU is 10 vehicles. The total number of vehicles generated during the simulation time is 300 and that of mRSUs, NmRSU, is varied to 30, 60, and 90. We have executed 10 simulation runs from which the average value is taken. The simulation parameters are listed in Table 6.Table 6
Simulation parameters.
Parameter Value Network size 100m× 2,500m  Transmission range of an mRSU 250m  Transmission range of a vehicle 250m  Total number of vehicles generated during the simulation 300  Total number of mRSUs generated during the simulation (NmRSU) 30, 60, 90, 120, 150  Speed of an mRSU 55~65km/h  Speed of a vehicle 50~70km/h  Maximum number of vehicles associated with an mRSU(C) 10  θ A 5  θ p 2  θ C 1  τ M 3,000ms  τ A 1,500ms  τ S 1,000ms  τ V 1,000ms  Δ 2Our proposed mechanism is compared with the ideal case and the all mRSU ON case. The ideal case is the case that the total number of ON-state mRSUs is computed by dividing the total number of vehicles by the maximum mRSU capacity (i.e.,V/C). The ideal case is infeasible, but we use it for comparisons because it gives the lower bound of the number of the ON-state mRSUs. In the all mRSU ON case, all mRSUs are in the ON state throughout the simulation. The performance factors considered are the number of ON-state mRSUs, the number of the vehicles associated with mRSUs, the ratio of the total association time to the total simulation time, the message transmission overhead, and the number of mRSU state changes.Figure4 shows the number of mRSUs and vehicles throughout the simulation for various NmRSUs, 30, 60, and 90. As NmRSU increases, the number of directly associated vehicles increases almost up to the total number of vehicles (that is, almost all the vehicles are directly associated with mRSUs). Throughout the simulation, overall, the number of ON-state mRSUs of the proposed mechanism is very close to that of the ideal case, which implies that ours performs very well in optimizing the number of ON-state mRSUs. We can see the difference between the total number of mRSUs and the number of ON-state mRSUs of our mechanism more clearly when NmRSU is 90 (Figure 4(c)).Figure 4
The number of mRSUs and vehicles throughout the simulation: (a)NmRSU=30, (b) NmRSU=60, and (c) NmRSU=90.
(a) (b) (c)Figure5 gives the results obtained by averaging the number of ON-state mRSUs for various NmRSUs, 30, 60, 90, 120, and 150. In Figure 5(a), we can see that the average number of ON-state mRSUs of ours is slightly larger than that of the ideal case and is kept steady even for larger NmRSUs. Figure 5(b) plots the ratio of the number of ON-state mRSUs to the total number of mRSUs, which indicates that the ratio decreases for increased NmRSUs. This again confirms that the number of ON-state mRSUs does not increase even for increased NmRSUs.Figure 5
The number of ON-state mRSUs for variousNmRSUs.
(a) (b)Figure6(a) shows the performance of the proposed mechanism in terms of the ratio of the number of associated vehicles to the total number of vehicles for various NmRSUs. We can see that most vehicles are directly associated with the ON-state mRSUs except for NmRSU=30. When NmRSU is 30, mRSUs are insufficient to handle all the vehicles, so only 76% of vehicles are directly associated with mRSUs and 22% of vehicles are indirectly associated with mRSUs via V2V communications. This situation is verified by the graphs in Figures 6(b) and 6(c) which give the results compared with the all mRSU ON case. Ours performs almost the same as the all mRSU ON case for all NmRSUs. For NmRSU=30, both mechanisms give 76% direct associations and, for the other NmRSU values, ours gives 97% direct association and the all mRSU ON case 99% direct association. This means that our mechanism performs almost the same as the all mRSU ON case with less ON-state mRSUs.Figure 6
The number of associated vehicles for variousNmRSUs.
(a) (b) (c)Figure7(a) shows the association time and the operation time per vehicle of the proposed mechanism. Except for the case of NmRSU=30, vehicles are directly associated with mRSUs during almost all the operation time. For NmRSU=30, the ratio of the direct association time to the operation time is 84% and the ratio of the indirect association time to the operation time is 13%. For the other NmRSUs, the ratio of the direct association is about 98%. Thus, we can affirm that the proposed mechanism performs well with an enough number of given mRSUs because vehicles tend to have direct association during the operation time in such cases.Figure 7
The association time for variousNmRSUs.
(a) (b)Figures8(a) and 8(b) show the number of message transmissions for various NmRSUs for the proposed mechanism and the all mRSU ON case. The proposed mechanism outperforms the all mRSU ON case for all NmRSUs. As NmRSU increases, we can see the performance difference more clearly; the all mRSU ON case generates 1.2 times more than ours when NmRSU=30 and 1.8 times when NmRSU=150. Moreover, the proposed mechanism keeps the control message transmission overhead almost the same even for larger NmRSUs. This indicates that our mechanism finds the near-optimal (minimum) subset of mRSUs, from the given mRSU set with any size, which covers almost all of the vehicles. Figures 8(c), 8(e), and 8(g) are the graphs showing the message transmission overhead per message type of the proposed mechanism for NmRSU= 30, 60, and 90, respectively. In all cases, V_INFO message transmissions are the major overhead which is about 80% of all the messages transmitted. As NmRSU increases, the message overhead also increases.Figure 8
The message transmission overhead for variousNmRSUs and the number of transmissions per message type.
(a) (b) (c) (d) (e) (f) (g) (h)Figure9 shows the number of state changes, from ON to OFF and from OFF to ON, for various NmRSUs. When NmRSU=30, there is no state change due to the lack of mRSUs; that is, all the mRSUs are kept in the ON state all the time. When NmRSU=60, the number of state changes from ON to OFF is almost the same as that from OFF to ON. In this case, OFF-state mRSUs tend to change to the ON state because of the situation with insufficient mRSUs compared to the cases of NmRSU>60. When NmRSU>60, the number of state changes from ON to OFF increases due to overprovisioned mRSUs.Figure 9
The number of state changes for variousNmRSUs.From the abovementioned simulation results, we can verify the validity of our proposed mechanism from the perspective of the ratio of associated vehicles and the control message overhead. Also, we can observe that our mechanism performs very close to the ideal case in terms of optimizing the number of active mRSUs.In order to see the performance of our mechanism from the perspective of mobility (dynamics) of vehicles and mRSUs, we have carried out simulations for various vehicle speeds and mRSU speeds. Figures10(a) and 10(b) show the number of direct associations per vehicle during the driving time and the ratio of the direct association time to the driving time per vehicle, respectively, for the vehicle speeds of 55~65km/h and 65~75km/h with the mRSU speed of 55~65km/h. On the average, a vehicle moving at higher speed experiences more associations because it passes by more mRSUs, but as we can see in Figure 10(b), the ratio of the direct association time to the driving time is almost the same for both vehicle speed ranges for NmRSU>30, which implies that our mechanism performs well even for fast vehicles. When NmRSU is 30 (i.e., when less mRSUs are deployed), the possibility of a fast vehicle being directly associated with an mRSU is slightly higher than a slow vehicle by making direct associations with more mRSUs.Figure 10
The number of direct associations and the ratio of direct association time to the driving time for various vehicle speeds andNmRSUs.
(a) (b)For the performance evaluation of our mechanism in terms of mRSU mobility, we have carried out simulations for various mRSU speeds, 50~55km/h, 55~60km/h, and 65~70km/h (to see the performance difference more clearly, we take 65~70km/h instead of 60~65km/h) for the vehicle speed of 50~70km/h. Figure11 shows the ratio of the direct association time to the driving time of a vehicle for various NmRSUs. We can see that the moving speed of mRSUs does not affect the direct association time (i.e., the coverage time) of vehicles, except for NmRSU=30. In the environment with less mRSUs, fast mRSUs lower the possibility of direct association of vehicles.Figure 11
The ratio of the direct association time to the driving time per vehicle for various mRSU speeds andNmRSUs.Figure12 shows the ratio of the ON-state mRSUs to the total mRSUs for various NmRSUs. We can see that the possibility of a fast mRSU in the ON state is higher than a slow mRSU for NmRSU>30. The network with fast mRSUs is more dynamic, resulting in more activated mRSUs to provide stable connectivity to vehicles.Figure 12
The ratio of ON-state mRSUs to the total mRSUs for various mRSU speeds andNmRSUs.From the results in Figures10–12, we can assert that our mechanism maintains its coverage capability even in the dynamic network environment by turning on more mRSUs.For the performance evaluation of our mechanism, we have carried out simulations for a straight road without intersections and traffic signals in order to see the effectiveness of our mechanism in configuring the mRB network adaptively. Because the major concern of our mechanism is the adaptive configuration of mRSUs according to the information of neighboring vehicles and mRSUs, our mechanism lacks consideration of intersections and traffic signals which are critical components of urban road environments. Therefore, as future work, we plan to enhance our mechanism so that the enhanced version can effectively work on the real urban road situations.


## 5. Conclusion

In recent years, for the provision of the cost-effective V2I communication infrastructure, mRSUs have been introduced and the studies on mRSUs are mostly about the deployment in static situations and the routing in the mRSU based communication infrastructure. In this paper, we considered the city environment with densely deployed mRSUs thanks to low installation and maintenance cost of mRSUs and figured out the problems caused by too many ON-state mRSUs. For the resolution of these problems, we first formulated the optimal mRB network problem as a 0-1 integer linear programming problem to prove the NP-hardness of the problem. Then, we proposed an adaptive mechanism that allows each mRSU to determine whether to enable or disable its mRSU functionality based on the information collected from its neighboring mRSUs and vehicles. For the operation of the proposed mechanism, we defined four conditions for mRSU state transitions. In order to validate the performance of our mechanism, we compared ours with the ideal case (i.e., the lower bound case) and the all mRSU ON case (i.e., the nonadaptive mechanism) by performing simulations. From the simulation results, we proved that our mechanism outperforms the all mRSU ON case from the perspective of the message overhead. Also, we observed that ours performs almost the same as the all mRSU ON case in terms of connectivity and as the ideal case in terms of the number of ON-state mRSUs.In this paper, we evaluated the performance of our mechanism for a simple road layout in order to see how well our mechanism operates in configuring the mRB network adaptively. But, in urban road scenario, there are many additional factors to be considered such as direction, traffic signals, etc., which requires more deliberate control of mRSUs. Thus, we leave the issue of enhancing our mechanism in the urban road environment for further study.



---

*Source: 6594084-2019-07-25.xml*