# Roadside Unit Deployment Mechanism Based on Node Popularity

Authors: Ming Mao; Peng Yi; Zhen Zhang; Liang Wang; Jinchuan Pei
Journal: Mobile Information Systems
 (2021)

---

## Abstract

Internet of Vehicles (IoV) can significantly improve the driving conditions of vehicles, but the mobility characteristics of vehicles put forward higher requirements for the robustness of the IoV system. As an important component of the IoV, the deployment of RoadSide Unit (RSU) directly influences the service performance of the IoV system to vehicles, and reasonable RSU deployment can save resource costs and improve system operating efficiency. This paper proposes an RSU deployment mechanism based on the popularity of road intersections, which uses three traffic parameters, vehicle contact time, intersection connectivity, and intersection coverage capacity, as the main reference indicators. Meanwhile, an improved hotspot discovery algorithm (IHDA) is utilized to introduce inhibition distance during deployment to reduce interference between RSUs. The simulation results demonstrate that, compared with the existing typical deployment methods, this program can improve the coverage time ratio and the contacts of vehicles per trip.


---

## Body

## 1. Introduction

In recent years, the Vehicular Ad hoc Network (VANET) has received great attention from the industry due to its huge development potential. Communications of Vehicle-to-Vehicle (V2V) are running based on On-Board Units (OBUs), and interactions of Vehicle-to-Infrastructure (V2I) are running based on RoadSide Units (RSU). One of the principal applications involving the V2I network is the vehicle safety application in the network. Therefore, the original intention of VANET is to improve driving safety. With the progress of the Internet of vehicles technology, VANET has developed into a wide range of commercial application platforms, including remote starting, status diagnosis, Internet access service, digital map downloading, real-time video relay, and value-added advertising.As one of the core components to realize collaborative distributed application management in VANET, RSU plays a significant role in data transmission and routing delays, such as traffic directory, data dissemination, security management, location server, and service agent. In Software Defined Vehicular Networks (SDVN) in [1], RSUs serve as the SDN switches and need to forward data packets from the terminal vehicles. RSU acts as a SDN switch, serves the controller in [2], and forwards flow rules to the on-board switch. Due to the frequent changes in the network topology caused by the high mobility of vehicles, the modification of the flow rules is a time-critical task. Therefore, it is necessary to further improve the communication contact between the RSU and the vehicle.The deployment location of RSUs will affect all elements associated with communication, and its reasonable planning can significantly improve the safety level of roads. Although the reasonable allocation of RSUs is of great significance to improve the quality of VANET services, due to budgetary factors, the high budget caused by the intensive deployment of RSUs will become a major obstacle to popularize VANET services. On the other hand, the interference caused by the RSU deployment with a high density will also reduce the performance of message propagation. Barrachina et al. [3] believed that optimizing the deployment budget of RSU is also an extremely challenging task.The RSU deployment (RD) problem can be considered as an extension of the node placement (NP-hard) problem that is widely studied in the field of wireless sensor networks [4]. It has been transformed into the placement of nodes in the network area under constraints. The difference is that vehicles in VANET can only move on prescribed roads, so the deployment factors considered are more complicated. At present, research on the RSU deployment problem has made definite progress. In summary, the existing research focuses on the following aspects: (1) the RSU deployment problem is summarized as an NP-hard maximum coverage problem [5, 6]. (2) The distribution of RSU is affected by many factors such as traffic characteristics, infrastructure availability, topological and topographic characteristics, and the specific requirements of operators [7]. (3) There are also studies considering the deployment of mobile RSU to facilitate message forwarding and fast message routing in the store-and-forward mode [8].Since the RSU is deployed fixedly, its transmit power is better than that of a mobile station, and its coverage area is larger. Although the deployment of RSU on public vehicles can improve the performance of the IoV [9], Subject to various factors (such as transmission power, path planning, and government policies), large-scale deployment of RSU on mobile public transportation is still impossible in the short term. Therefore, research on fixed RSU deployment will still be the current mainstream.This paper proposes an RSU deployment scheme that comprehensively considers the characteristics of the vehicle’s road network and the capacity of the intersection. The contributions of our paper are as follows.First, we model the road network as a collection of nodes and edgesG (V, E). At the same time, we believe that the intersection is the location where the traffic converges [5]. Therefore, we choose the intersections as candidate locations for RSU deployment. We transform the RSU deployment problem into an intersection coverage problem and prove that the node coverage problem is NP hard.Secondly, we comprehensively consider vehicle contact time, intersection connectivity, and intersection coverage capability. Then, based on different road communication requirements, while limiting the number of RSU deployments, we maximize the coverage ratio, ensure the service efficiency of RSUs for vehicles, and improve system robustness.Finally, we propose an algorithm that considers the inhibition distance to ensure that the RSUs do not interfere with each other caused by excessive overlap to improve the operating efficiency of the IoV system and verify its performance in the RSU deployment experiment.The rest of the paper is organized as follows. Section2 provides relevant information about RSU deployment in VANET. Then, the proposed RSU deployment model is explained in detail in Section 3. Section 4 proposes two algorithms to accomplish RSU deployment, while Section 5 provides the details of simulation environment, analyzes the simulation results, and discusses the performance of RSU deployment strategy. Finally, conclusions are drawn in Section 6.


## 2. Related Work

### 2.1. RSU Coverage Problem

Owing to the high mobility of vehicles, the optimal deployment of RSU is more complicated than wireless networks. At present, the issue of service coverage for VANET has received widespread attention. With the continuous development and change of application requirements, some specific optimization goals have been proposed on the coverage issue, and a feasible simplified solution has been provided for the coverage model of VANET.Spatial coverage is built on the analysis and research of the spatial attributes of a given road system. Brij [10] pointed out that placing the RSU at the center of the intersection, rather than the corner, can cover more road areas, which can increase the data dissemination rate in the operation area by 15%. However, Kafsi et al. [11] pointed out that even if most vehicles gather at congested intersections, isolated vehicles are more likely to appear in the middle of the road segment. Therefore, placing the RSU in the middle of the road will be a more effective strategy to avoid isolated vehicles from being uncovered.Some studies have carried out extensive research from the perspective of time coverage, with the main optimization goal covering the communication between high-speed moving vehicles and fixed RSUs. Magsino and Ho [12] transformed this problem into maximizing the total amount of information shared in the Internet of Vehicles. It includes the total amount of information transmission from the vehicle to the infrastructure and the total amount of information transmission from the infrastructure to the vehicle. The constraints are set as the number of RSUs, the space mean speed threshold, and junction’s transmission density threshold to maximize the amount of information shared between the vehicle and the RSU fog calculation hotspot. Gao et al. [13] also researched the one-dimensional RSU deployment (D1RD) problem, given n RSUs with different coverage radius under constraints. Two greedy-based algorithms (called Greedy2P3 and Greedy2P3E, respectively) were proposed to optimize communication delay, limit deployment consumption, and improve network performance.Other types of time coverage focus on the contact between OBU and RSU. Trullols et al. [5] sought to maximize the number of vehicles in contact with RSU and convert their problem into a maximum coverage problem. Although the linear programming problem is NP-hard, the authors still use heuristic algorithms of different complexity to solve it. It converts this problem through derivation, that is, to ensure that most vehicles are covered by one or more RSUs for a long enough time during driving. Lochert et al. [14] proposed a landmark-based aggregation scheme to save travel time in the vehicle road network. They distribute information about travel time between important points and landmark locations and estimate the travel time that a given active RSU location vector can save. Finally, these estimates are used as fitness indicators in genetic algorithms to solve the central application optimization of RSU deployment. Results and Discussion.


### 2.2. NP-Hard Proof of Node Coverage Group Optimization Problem

As RSU deployment attaches great importance to cost control, service providers all hope to minimize the number of RSUs under the premise of ensuring performance. The solution to this problem is NP-hard, and the proof process is briefly described as follows:Definition 1.
The collection of adjacent points: the set of neighboring nodes is defined as(1)Ni=j∈V|dij≤R,i∈V,j≠i,where V is the set of nodes, dij represents the distance between node i and j, and R is the communication transmission radius of the node.Definition 2.
Node coverage grouping: givenn nodes, divide all nodes into groups G (n) according to the node coverage R (each node is the same), and there is at least one node i in each group, and for all other nodes j in the group, there is dij ≤ R.
There are many methods to divide givenn nodes into the above node coverage groups. The worst case consists of n groups. The more the groups, the greater the data overhead incurred to complete the process. The problem of node coverage optimization is to minimize the number of node coverage packets under the condition of limited transmission distance, which is(2)MinimizeGn.Theorem 1.
The optimization of node coverage grouping is an NP-hard problem.Proof.
The optimization of node coverage grouping is to solve the minimum number of all node grouping sets, which can be simplified to iteratively find the group with the largest coverage node until each node belongs to a group. This problem is comparable to the clique problem [15], which is to find the set with the maximum number of nodes (under constraints) in a given topological graph G (containing n nodes). This problem has been proven to be an NP-hard problem [16], and the fastest known time complexity of the algorithm is O (20.249n) = O (21.1888n) [17]. Therefore, the optimization of node coverage grouping is as difficult as iteratively applying the maximum clique algorithm to find the connectivity group with the largest number of nodes until all nodes are grouped. Therefore, the optimization of node coverage grouping is also an NP-hard problem.


## 2.1. RSU Coverage Problem

Owing to the high mobility of vehicles, the optimal deployment of RSU is more complicated than wireless networks. At present, the issue of service coverage for VANET has received widespread attention. With the continuous development and change of application requirements, some specific optimization goals have been proposed on the coverage issue, and a feasible simplified solution has been provided for the coverage model of VANET.Spatial coverage is built on the analysis and research of the spatial attributes of a given road system. Brij [10] pointed out that placing the RSU at the center of the intersection, rather than the corner, can cover more road areas, which can increase the data dissemination rate in the operation area by 15%. However, Kafsi et al. [11] pointed out that even if most vehicles gather at congested intersections, isolated vehicles are more likely to appear in the middle of the road segment. Therefore, placing the RSU in the middle of the road will be a more effective strategy to avoid isolated vehicles from being uncovered.Some studies have carried out extensive research from the perspective of time coverage, with the main optimization goal covering the communication between high-speed moving vehicles and fixed RSUs. Magsino and Ho [12] transformed this problem into maximizing the total amount of information shared in the Internet of Vehicles. It includes the total amount of information transmission from the vehicle to the infrastructure and the total amount of information transmission from the infrastructure to the vehicle. The constraints are set as the number of RSUs, the space mean speed threshold, and junction’s transmission density threshold to maximize the amount of information shared between the vehicle and the RSU fog calculation hotspot. Gao et al. [13] also researched the one-dimensional RSU deployment (D1RD) problem, given n RSUs with different coverage radius under constraints. Two greedy-based algorithms (called Greedy2P3 and Greedy2P3E, respectively) were proposed to optimize communication delay, limit deployment consumption, and improve network performance.Other types of time coverage focus on the contact between OBU and RSU. Trullols et al. [5] sought to maximize the number of vehicles in contact with RSU and convert their problem into a maximum coverage problem. Although the linear programming problem is NP-hard, the authors still use heuristic algorithms of different complexity to solve it. It converts this problem through derivation, that is, to ensure that most vehicles are covered by one or more RSUs for a long enough time during driving. Lochert et al. [14] proposed a landmark-based aggregation scheme to save travel time in the vehicle road network. They distribute information about travel time between important points and landmark locations and estimate the travel time that a given active RSU location vector can save. Finally, these estimates are used as fitness indicators in genetic algorithms to solve the central application optimization of RSU deployment. Results and Discussion.


## 2.2. NP-Hard Proof of Node Coverage Group Optimization Problem

As RSU deployment attaches great importance to cost control, service providers all hope to minimize the number of RSUs under the premise of ensuring performance. The solution to this problem is NP-hard, and the proof process is briefly described as follows:Definition 1.
The collection of adjacent points: the set of neighboring nodes is defined as(1)Ni=j∈V|dij≤R,i∈V,j≠i,where V is the set of nodes, dij represents the distance between node i and j, and R is the communication transmission radius of the node.Definition 2.
Node coverage grouping: givenn nodes, divide all nodes into groups G (n) according to the node coverage R (each node is the same), and there is at least one node i in each group, and for all other nodes j in the group, there is dij ≤ R.
There are many methods to divide givenn nodes into the above node coverage groups. The worst case consists of n groups. The more the groups, the greater the data overhead incurred to complete the process. The problem of node coverage optimization is to minimize the number of node coverage packets under the condition of limited transmission distance, which is(2)MinimizeGn.Theorem 1.
The optimization of node coverage grouping is an NP-hard problem.Proof.
The optimization of node coverage grouping is to solve the minimum number of all node grouping sets, which can be simplified to iteratively find the group with the largest coverage node until each node belongs to a group. This problem is comparable to the clique problem [15], which is to find the set with the maximum number of nodes (under constraints) in a given topological graph G (containing n nodes). This problem has been proven to be an NP-hard problem [16], and the fastest known time complexity of the algorithm is O (20.249n) = O (21.1888n) [17]. Therefore, the optimization of node coverage grouping is as difficult as iteratively applying the maximum clique algorithm to find the connectivity group with the largest number of nodes until all nodes are grouped. Therefore, the optimization of node coverage grouping is also an NP-hard problem.


## 3. RSU Deployment Model

We useG (V, E) to represent the city network topology, where E is the road section connecting two adjacent intersections, and V represents the intersection, V=N. First, make the following assumptions: (1) the performance of the RSUs in this experiment is the same (the communication coverage radius is the same); (2) the maximum number of RSUs that can be deployed is k, and the deployment cost of each RSU is the same; (3) once the vehicle is in coverage range, it can receive the services from RSU.If we know the whole network topology, the important parameters of each node can be obtained according to different service target requirements, such as traffic flow, commercial districts, and hospitals. We define the following traffic parameters as model indicators.


### 3.1. Vehicle Contact Time

If there arek RSUs to be deployed, the number of vehicles entering the RSUs’ service range and their contact time should be maximized. In this paper, the traffic density is defined as the number of vehicles passing through the intersection within the counting time Di. Using Qij to represent the contact time of the jth vehicle at intersection i, the Q of the entire road network can be expressed as a matrix with N rows and D columns (D = argMAX1≤i≤NDi). Here, we use the concept of Maximum Coverage with Time Threshold Problem (MCTTP) [18]. That is, each vehicle receives at least RSU service time φ. The vehicle contact time at the intersection i can be expressed as(3)Ti=∑j=1Diminφ,Qij,The meaning of this formula is that if the contact time between intersectioni and the covered vehicle exceeds φ, the vehicle will not increase the total revenue of intersection i.


### 3.2. Intersection Connectivity

We use node betweenness centrality (BC) [19] to reflect the connectivity of intersections. Node betweenness centrality represents the frequency measurement of the node, which is on the shortest path between other pairs of nodes in the network. Its size can reflect a certain extent whether the node is in the center position between other nodes on the communication path. Its definition is as follows:(4)Bi=∑s,t∈Vlis,tqs,t.If nodei is on the geodetic path from node s to t, li (s, t) = 1; otherwise, 0. q (s, t) represents the total number of geodetic paths from node s to node t.The node with the highest connectivity does not necessarily reflect optimum. This is because connectivity is only one of the factors considered from the perspective of graph theory. People still consider the road condition information of the connected road segment passing through the node when traveling. The obvious example is that although a certain intersection is often a traffic jam as a transportation junction, based on the quality and reliability of the surrounding roads at that location, it is still considered as the preferred choice for travel. Therefore, we introduce the concept of the road condition coefficient. For the convenience of subsequent experiments, the road condition coefficients are set to four conditions: backbone road, general trunk road, branch road, and auxiliary road. The road condition coefficientεij is set to 1, 0.75, 0.5, and 0.25, respectively.We define the intersection connectivity as follows:(5)Hi=Bivi∑j∈Viεij,where V (i) represents the set of adjacent nodes of node i, and tij represents the road condition coefficient of the road between intersection i and its adjacent intersection j.


### 3.3. Intersection Coverage Capacity

Since the coverage of all RSUs in this experiment is equidistant, if RSUs are deployed at intersections with relatively concentrated location distances, there will be more intersections under their coverage range, and the number of RSUs used will be less. We introduce the definition of intersection coverage capacity as follows:(6)Fi=N∑j∈Vgij.In the formula above,gij is the length of the geodetic path from node i to other nodes j, and N is the total number of intersections in the network. It can be seen that the larger the Fi, the stronger its ability to cover other nodes.


### 3.4. Normalization of Indicators

Since the above three indicators are not in the same order of magnitude, if they are directly added linearly, the experimental conclusions are likely to be unreasonable. Therefore, the above indicators need to be normalized.The normalization formula ofTi is as follows:(7)ti=Ti−TminTmax−Tmin.This method is also called linear normalization or dispersion normalization, which is a linear transformation of the original data, so that the result value is mapped to a range between zero and one, or a custom interval. Max is the maximum value of the sample data, and min is the minimum value of the sample data. In the same way, the normalized valueshi of Hi and fi of Fi can be obtained.


### 3.5. Intersection Popularity

Since our goal is to cover more intersections to ensure service efficiency, the coverage results obtained by different trade-offs of the three indicators will also be different. Therefore, we define the popularity of intersections in the road network as follows:(8)OPi=wtti+whhi+wffi,where wt is the weight of the normalized contact time ti, and wh and wf are the weights of the normalized hi and fi, respectively. wq+wh+wf=1.


## 3.1. Vehicle Contact Time

If there arek RSUs to be deployed, the number of vehicles entering the RSUs’ service range and their contact time should be maximized. In this paper, the traffic density is defined as the number of vehicles passing through the intersection within the counting time Di. Using Qij to represent the contact time of the jth vehicle at intersection i, the Q of the entire road network can be expressed as a matrix with N rows and D columns (D = argMAX1≤i≤NDi). Here, we use the concept of Maximum Coverage with Time Threshold Problem (MCTTP) [18]. That is, each vehicle receives at least RSU service time φ. The vehicle contact time at the intersection i can be expressed as(3)Ti=∑j=1Diminφ,Qij,The meaning of this formula is that if the contact time between intersectioni and the covered vehicle exceeds φ, the vehicle will not increase the total revenue of intersection i.


## 3.2. Intersection Connectivity

We use node betweenness centrality (BC) [19] to reflect the connectivity of intersections. Node betweenness centrality represents the frequency measurement of the node, which is on the shortest path between other pairs of nodes in the network. Its size can reflect a certain extent whether the node is in the center position between other nodes on the communication path. Its definition is as follows:(4)Bi=∑s,t∈Vlis,tqs,t.If nodei is on the geodetic path from node s to t, li (s, t) = 1; otherwise, 0. q (s, t) represents the total number of geodetic paths from node s to node t.The node with the highest connectivity does not necessarily reflect optimum. This is because connectivity is only one of the factors considered from the perspective of graph theory. People still consider the road condition information of the connected road segment passing through the node when traveling. The obvious example is that although a certain intersection is often a traffic jam as a transportation junction, based on the quality and reliability of the surrounding roads at that location, it is still considered as the preferred choice for travel. Therefore, we introduce the concept of the road condition coefficient. For the convenience of subsequent experiments, the road condition coefficients are set to four conditions: backbone road, general trunk road, branch road, and auxiliary road. The road condition coefficientεij is set to 1, 0.75, 0.5, and 0.25, respectively.We define the intersection connectivity as follows:(5)Hi=Bivi∑j∈Viεij,where V (i) represents the set of adjacent nodes of node i, and tij represents the road condition coefficient of the road between intersection i and its adjacent intersection j.


## 3.3. Intersection Coverage Capacity

Since the coverage of all RSUs in this experiment is equidistant, if RSUs are deployed at intersections with relatively concentrated location distances, there will be more intersections under their coverage range, and the number of RSUs used will be less. We introduce the definition of intersection coverage capacity as follows:(6)Fi=N∑j∈Vgij.In the formula above,gij is the length of the geodetic path from node i to other nodes j, and N is the total number of intersections in the network. It can be seen that the larger the Fi, the stronger its ability to cover other nodes.


## 3.4. Normalization of Indicators

Since the above three indicators are not in the same order of magnitude, if they are directly added linearly, the experimental conclusions are likely to be unreasonable. Therefore, the above indicators need to be normalized.The normalization formula ofTi is as follows:(7)ti=Ti−TminTmax−Tmin.This method is also called linear normalization or dispersion normalization, which is a linear transformation of the original data, so that the result value is mapped to a range between zero and one, or a custom interval. Max is the maximum value of the sample data, and min is the minimum value of the sample data. In the same way, the normalized valueshi of Hi and fi of Fi can be obtained.


## 3.5. Intersection Popularity

Since our goal is to cover more intersections to ensure service efficiency, the coverage results obtained by different trade-offs of the three indicators will also be different. Therefore, we define the popularity of intersections in the road network as follows:(8)OPi=wtti+whhi+wffi,where wt is the weight of the normalized contact time ti, and wh and wf are the weights of the normalized hi and fi, respectively. wq+wh+wf=1.


## 4. RSU Deployment Strategy

From the theoretical derivation process of the above, deploying RSUs at intersections with high popularity can improve the robustness of the IoV service. Therefore, our goal is as follows: in the case of meeting the budget constraintk, preferentially select the intersection with high popularity as the RSU deployment location.


### 4.1. Hotspot Discovery Algorithm

The basic idea of our algorithm is based on the greedy strategy. It preferentially selects intersections with higher node popularity as RSU locations for deployment, deletes intersections within its coverage from the set of candidate nodes, and then repeats the above work until the number of RSU deployments reachesk. Finally, output the GOP set as the RSU placement location (Algorithm 1).Algorithm 1:Hotspot discovery algorithm (HDA)
Input:k, VOutput: RSU deployment location set GOP(1)
GOP ⟵ Ø,γ ⟵ 0,(2)
Sort the OPi values of the node set V in descending order to obtain the set OP(3)
whileγ ≠ k do(4)
Ui = arg max{OP}(5)
GOP ⟵ GOP∪Ui(6)
RGOPi = intersections covered by GOPi(7)
OP ⟵ OP-Ui-RGOPi,(8)
γ ⟵ γ + 1(9)
end while(10)
return GOP


### 4.2. Improved Hotspot Discovery Algorithm

Given the number of RSUs, if the number of RSUs arranged in the same geographic area is large, it will cause mutual interference and decrease the coverage of RSUs in remote areas. Babu et al. [20] proposed that, for a road network with an area of A × A, the entire area can be divided into k blocks (k is the number of RSUs). Subject to the shape and structure of the road network, they cannot ensure that k deployments could be found when the inhibition distance is too long. So, they set the distance to A/2k. However, this method is too extensive, and the distributed arrangement is contrary to the deployment idea based on the popularity of nodes.As shown in Figure1(a), since most of the road network is horizontal or vertical, assuming that the vehicle is traveling at a constant speed on the road connecting two adjacent RSUs, so we can use travel time to indicate distance. During the driving process between two RSUs, the inhibition distance is expressed by the overlap time coverage ratio Oijt = L1/L2, that is, the length of the overlap divided by the distance between the two centers. Rizk et al. [21] pointed out that as the vehicle moves away from the center of the RSU, the coverage signal gradually attenuates, and appropriate overlap can ensure the switching time between the vehicle and the RSU. As shown in Figures 1(b) and 1(c), the value range of Oijt is from 0 to 1.Figure 1
Schematic diagram of inhibition distance (a)Oijt = L1/L2 (b) Oijt = 0 (c) Oijt = 1.
(a)(b)(c)We propose an improved hotspot discovery algorithm (IHDA) considering inhibition distance. The algorithm first sorts the OPi values of the node set V in descending order to form a set OP, selects the intersection with the highest OPi value as the candidate RSU deployment position, adds it to the deployment position set GOP, and, at the same time, removes the intersections within the coverage of the RSU signal from the set of candidate nodes and updates the set of candidate nodes.Then, compare the nodes in the candidate node set with the selected node GOPi to see if the constraints are met. Then, the node with the highest OPi value will be selected from the candidate node set as the RSU deployment location again, until the number of RSU deployments reaches k (Algorithm 2).Algorithm 2:Improved hotspot discovery algorithm (IHDA).
Input:k, V, ρOutput: RSU deployment location set GOP(1)
GOP ⟵ Ø,γ ⟵ 0, RGOP ⟵ Ø(2)
Sort the OPi values of the node set V in descending order to obtain the set OP(3)
whileγ ≠ k do(4)
Ui = arg max {OP}(5)
GOP ⟵ GOP∪Ui(6)
RGOPi = intersections covered by GOPi(7)
OP ⟵ OP-Ui-RGOPi,(8)
for ∀OPi ∈ OP,(9)
for ∀GOPj ∈ GOP(10)
ifOijt > ρ(11)
OP ⟵ OP-OPi(12)
end if(13)
end for(14)
end for(15)
γ ⟵ γ + 1(16)
end while(17)
return GOP


## 4.1. Hotspot Discovery Algorithm

The basic idea of our algorithm is based on the greedy strategy. It preferentially selects intersections with higher node popularity as RSU locations for deployment, deletes intersections within its coverage from the set of candidate nodes, and then repeats the above work until the number of RSU deployments reachesk. Finally, output the GOP set as the RSU placement location (Algorithm 1).Algorithm 1:Hotspot discovery algorithm (HDA)
Input:k, VOutput: RSU deployment location set GOP(1)
GOP ⟵ Ø,γ ⟵ 0,(2)
Sort the OPi values of the node set V in descending order to obtain the set OP(3)
whileγ ≠ k do(4)
Ui = arg max{OP}(5)
GOP ⟵ GOP∪Ui(6)
RGOPi = intersections covered by GOPi(7)
OP ⟵ OP-Ui-RGOPi,(8)
γ ⟵ γ + 1(9)
end while(10)
return GOP


## 4.2. Improved Hotspot Discovery Algorithm

Given the number of RSUs, if the number of RSUs arranged in the same geographic area is large, it will cause mutual interference and decrease the coverage of RSUs in remote areas. Babu et al. [20] proposed that, for a road network with an area of A × A, the entire area can be divided into k blocks (k is the number of RSUs). Subject to the shape and structure of the road network, they cannot ensure that k deployments could be found when the inhibition distance is too long. So, they set the distance to A/2k. However, this method is too extensive, and the distributed arrangement is contrary to the deployment idea based on the popularity of nodes.As shown in Figure1(a), since most of the road network is horizontal or vertical, assuming that the vehicle is traveling at a constant speed on the road connecting two adjacent RSUs, so we can use travel time to indicate distance. During the driving process between two RSUs, the inhibition distance is expressed by the overlap time coverage ratio Oijt = L1/L2, that is, the length of the overlap divided by the distance between the two centers. Rizk et al. [21] pointed out that as the vehicle moves away from the center of the RSU, the coverage signal gradually attenuates, and appropriate overlap can ensure the switching time between the vehicle and the RSU. As shown in Figures 1(b) and 1(c), the value range of Oijt is from 0 to 1.Figure 1
Schematic diagram of inhibition distance (a)Oijt = L1/L2 (b) Oijt = 0 (c) Oijt = 1.
(a)(b)(c)We propose an improved hotspot discovery algorithm (IHDA) considering inhibition distance. The algorithm first sorts the OPi values of the node set V in descending order to form a set OP, selects the intersection with the highest OPi value as the candidate RSU deployment position, adds it to the deployment position set GOP, and, at the same time, removes the intersections within the coverage of the RSU signal from the set of candidate nodes and updates the set of candidate nodes.Then, compare the nodes in the candidate node set with the selected node GOPi to see if the constraints are met. Then, the node with the highest OPi value will be selected from the candidate node set as the RSU deployment location again, until the number of RSU deployments reaches k (Algorithm 2).Algorithm 2:Improved hotspot discovery algorithm (IHDA).
Input:k, V, ρOutput: RSU deployment location set GOP(1)
GOP ⟵ Ø,γ ⟵ 0, RGOP ⟵ Ø(2)
Sort the OPi values of the node set V in descending order to obtain the set OP(3)
whileγ ≠ k do(4)
Ui = arg max {OP}(5)
GOP ⟵ GOP∪Ui(6)
RGOPi = intersections covered by GOPi(7)
OP ⟵ OP-Ui-RGOPi,(8)
for ∀OPi ∈ OP,(9)
for ∀GOPj ∈ GOP(10)
ifOijt > ρ(11)
OP ⟵ OP-OPi(12)
end if(13)
end for(14)
end for(15)
γ ⟵ γ + 1(16)
end while(17)
return GOP


## 5. Performance Evaluation

In this section, we will apply the two proposed RSU deployment algorithms in the simulated network and traffic flow environment to seek the best RSU deployment parameters. We will test the performance of the proposed deployment scheme by comparing it with the related deployment schemes in terms of coverage time ratio and contact times. We select part of the road network of Zhengzhou City in Henan Province (as shown in Figure2) as the test environment. The topological area of the road network is 10 km × 10 km, which is transformed into an urban road network using SUMO [22] (as shown in Figure 3). It includes 1174 intersections. The statistical data of vehicle trajectory information is provided by the intelligent traffic management data analysis, research, and judgment comprehensive application platform. The data information of 7:00–9:00 every day from June 1 to 10, 2020, was statistically analyzed, and a total number of 51079 vehicles were captured. The simulation code is written in C++ language (Visual Studio 2015), and the running hardware environment is Lenovo RD650 server (Intel Xeon-e5-2600v4 dual processor, 16G DDR4 memory, 4TB SAS ST hard disk, windows server2008R2 operating system).Figure 2
Electronic map.Figure 3
Initial road network.


### 5.1. Comparison Scheme and Index

Centrality based RSU deployment approach-degree centrality (CDA-DC) [23]: this scheme is a RSU deployment method based on graph theory, which only considers the degree centrality of nodes. The higher the DC value of a node, the more the roads connected with the intersection, which can provide more opportunities for vehicles to pass. Therefore, it is also more likely to be selected as the RSU deployment location.Budgeted Continuous Coverage (BCC) [24]: budget continuous coverage method aims to maximize the coverage rate of RSU to the road and regional communication scale under the given RSU budget constraints.Random: to identify the performance of other deployment schemes clearly, we also test the performance of the random placement method in the experiment. This method does not consider any parameters related to node popularity and randomly deploys according to the number of RSUs required in the experiment.To ensure the reliability of the experimental results, 25 random experimental seeds have been carried out for each experimental scene, and the average value has been taken.We use five metrics to evaluate the performance of the RSU deployment mechanism:Coverage ratio: since the number of RSUs is given, the coverage ratio of all intersections will also change according to the change of traffic parameters. This index can be obtained by the ratio of the number of covered intersections to the total number of intersections in the road network after RSUs deployment (depicted as formula (9)).Coverage time ratio: it is the ratio of the time spent in the RSU coverage range to the total time spent during the whole road network movement in the experimental road network. The higher the value, the greater the chance that the RSU could provide service to the vehicle (depicted as formula (10)).Contacts per trip: it is the average number of vehicle contacts with RSUs during one trip. The more the number of vehicle contacts, the faster the frequency of updating the routing strategy, and the higher the forwarding efficiency.Packet delivery ratio: it is obtained by dividing the number of data packets received by the RSU by the number of data packets sent from the source vehicle.Average end-to-end delay: it refers to the time it takes for a data packet to be transmitted from the source node to the destination node.(9)Coverage ratio=number of covered intersectionstotal number of intersections,(10)Coverage time ratio=time spent in the RSU coverage rangetotal time spent during the whole road network movement.


### 5.2. Analysis of Experimental Parameters

To test the impact of three traffic parameter weights on the deployment environment, we first set the RSU communication transmission distance as 300 m, and the number of RSUs available as 100, 200, 300, and 400, respectively, to analyze the performance of HDA. When the value range ofwq/wh/wf is 1/0/0, 0.8/0.1/0.1, 0.6/0.2/0.2, 0.4/0.3/0.3, 0.2/0.4/0.4, and 0/0.5/0.5, respectively, the variation of coverage ratio is shown in Figure 4.Figure 4
Coverage ratio under different traffic parameter weights.The horizontal axis shows only the value ofwq/wh/wf, and the vertical axis shows the change of coverage ratio. It can be seen that when HDA method is used, the coverage ratio changes caused by traffic parameter changes are consistent under different RSU number limits. The maximum coverage ratio is obtained when wq/wh/wf is 0.6/0.2/0.2. When n = 400, the coverage ratio reaches 92%.Then, we test the optimal inhibition distance. We set thewq/wh/wf value as 0.6/0.2/0.2, the RSU communication transmission distance is set to 300 m, and the number of RSUs that can be deployed is 50, 100, 150, 200, 250, and 300, respectively. IHDA method is used to compare the change of intersection coverage ratio with different inhibition distance coefficients.Whenρ = 0, the inhibition distance coefficient does not affect RSU deployment, which is equivalent to HDA. From Figure 5, we can see that the coverage ratio can be further improved by adjusting the inhibition coefficient. It is clear that setting the inhibition distance coefficient too large or too small will reduce the RSU coverage ratio. All different deployment budgets achieve the best coverage ratio when ρ is around 0.15. When the number of RSUs is 300, the IHDA coverage ratio is 24% higher than HDA.Figure 5
Coverage ratio under differentρ.


### 5.3. Performance Comparison

We compare four deployment methods (IHDA, BCC, CDA-DC, and Random) in the same experimental environment. The RSU communication transmission distance is still set to 300 m, the inhibition distance coefficientρ is set to 0.15, and the number of RSU is 100, 200, 300, and 400, respectively. The experimental results are shown in Figures 6 and 7.Figure 6
Coverage time ratio under different RSU budget.Figure 7
Contacts per trip under different RSU budget.As the number of RSUs increases, the coverage time ratio continues to rise. When the RSUs number is 300, the contact time ratio of IHDA is 18% and 16% higher than that of CDA-DC and BCC, respectively. When the number of RSUs is 400, it has increased by 15% and 11%, respectively, indicating that IHDA has a greater opportunity to provide services to vehicles than other schemes. When RSUs number is 300, compared with CDA-DA and BCC, the average number of IHDA contacts increases by 0.9 and 1.4 times, respectively; when the number is 400, it increases by 0.6 and 0.3 times, respectively. This is due to the increasing number of RSUs. With the vehicle coverage ratio increasing constantly, the coverage ratio gap of the entire road network between different schemes continues to decrease, so the gap in the number of contacts is also gradually decreasing.The packet delivery ratio and average end-to-end delay are shown in Figures8 and 9. It can be seen that as the number of RSUs increases, the packet delivery ratio of the three coverage algorithms gradually increases. The reason for this is that when the number of RSUs is small, the three deployment methods cannot provide enough opportunities for all vehicles to enter the coverage area. In this case, packet loss is mainly caused by unreachable routings. With the increase in the number of RSUs, the coverage and density have been improved, and the communication quality has been significantly enforced. As the number of RSUs increases, the service range becomes larger, and the end-to-end delay gradually decreases. When the number of RSUs is 400, the end-to-end delay of IHDA is approximately the same as that of BCC. The reason for this is that BCC takes guaranteeing the scale of communication as its main goal, so it has demonstrated relatively outstanding performance in terms of communication quality.Figure 8
Packet delivery ratio under different RSU budget.Figure 9
Average end-to-to delay under different RSU budget.


## 5.1. Comparison Scheme and Index

Centrality based RSU deployment approach-degree centrality (CDA-DC) [23]: this scheme is a RSU deployment method based on graph theory, which only considers the degree centrality of nodes. The higher the DC value of a node, the more the roads connected with the intersection, which can provide more opportunities for vehicles to pass. Therefore, it is also more likely to be selected as the RSU deployment location.Budgeted Continuous Coverage (BCC) [24]: budget continuous coverage method aims to maximize the coverage rate of RSU to the road and regional communication scale under the given RSU budget constraints.Random: to identify the performance of other deployment schemes clearly, we also test the performance of the random placement method in the experiment. This method does not consider any parameters related to node popularity and randomly deploys according to the number of RSUs required in the experiment.To ensure the reliability of the experimental results, 25 random experimental seeds have been carried out for each experimental scene, and the average value has been taken.We use five metrics to evaluate the performance of the RSU deployment mechanism:Coverage ratio: since the number of RSUs is given, the coverage ratio of all intersections will also change according to the change of traffic parameters. This index can be obtained by the ratio of the number of covered intersections to the total number of intersections in the road network after RSUs deployment (depicted as formula (9)).Coverage time ratio: it is the ratio of the time spent in the RSU coverage range to the total time spent during the whole road network movement in the experimental road network. The higher the value, the greater the chance that the RSU could provide service to the vehicle (depicted as formula (10)).Contacts per trip: it is the average number of vehicle contacts with RSUs during one trip. The more the number of vehicle contacts, the faster the frequency of updating the routing strategy, and the higher the forwarding efficiency.Packet delivery ratio: it is obtained by dividing the number of data packets received by the RSU by the number of data packets sent from the source vehicle.Average end-to-end delay: it refers to the time it takes for a data packet to be transmitted from the source node to the destination node.(9)Coverage ratio=number of covered intersectionstotal number of intersections,(10)Coverage time ratio=time spent in the RSU coverage rangetotal time spent during the whole road network movement.


## 5.2. Analysis of Experimental Parameters

To test the impact of three traffic parameter weights on the deployment environment, we first set the RSU communication transmission distance as 300 m, and the number of RSUs available as 100, 200, 300, and 400, respectively, to analyze the performance of HDA. When the value range ofwq/wh/wf is 1/0/0, 0.8/0.1/0.1, 0.6/0.2/0.2, 0.4/0.3/0.3, 0.2/0.4/0.4, and 0/0.5/0.5, respectively, the variation of coverage ratio is shown in Figure 4.Figure 4
Coverage ratio under different traffic parameter weights.The horizontal axis shows only the value ofwq/wh/wf, and the vertical axis shows the change of coverage ratio. It can be seen that when HDA method is used, the coverage ratio changes caused by traffic parameter changes are consistent under different RSU number limits. The maximum coverage ratio is obtained when wq/wh/wf is 0.6/0.2/0.2. When n = 400, the coverage ratio reaches 92%.Then, we test the optimal inhibition distance. We set thewq/wh/wf value as 0.6/0.2/0.2, the RSU communication transmission distance is set to 300 m, and the number of RSUs that can be deployed is 50, 100, 150, 200, 250, and 300, respectively. IHDA method is used to compare the change of intersection coverage ratio with different inhibition distance coefficients.Whenρ = 0, the inhibition distance coefficient does not affect RSU deployment, which is equivalent to HDA. From Figure 5, we can see that the coverage ratio can be further improved by adjusting the inhibition coefficient. It is clear that setting the inhibition distance coefficient too large or too small will reduce the RSU coverage ratio. All different deployment budgets achieve the best coverage ratio when ρ is around 0.15. When the number of RSUs is 300, the IHDA coverage ratio is 24% higher than HDA.Figure 5
Coverage ratio under differentρ.


## 5.3. Performance Comparison

We compare four deployment methods (IHDA, BCC, CDA-DC, and Random) in the same experimental environment. The RSU communication transmission distance is still set to 300 m, the inhibition distance coefficientρ is set to 0.15, and the number of RSU is 100, 200, 300, and 400, respectively. The experimental results are shown in Figures 6 and 7.Figure 6
Coverage time ratio under different RSU budget.Figure 7
Contacts per trip under different RSU budget.As the number of RSUs increases, the coverage time ratio continues to rise. When the RSUs number is 300, the contact time ratio of IHDA is 18% and 16% higher than that of CDA-DC and BCC, respectively. When the number of RSUs is 400, it has increased by 15% and 11%, respectively, indicating that IHDA has a greater opportunity to provide services to vehicles than other schemes. When RSUs number is 300, compared with CDA-DA and BCC, the average number of IHDA contacts increases by 0.9 and 1.4 times, respectively; when the number is 400, it increases by 0.6 and 0.3 times, respectively. This is due to the increasing number of RSUs. With the vehicle coverage ratio increasing constantly, the coverage ratio gap of the entire road network between different schemes continues to decrease, so the gap in the number of contacts is also gradually decreasing.The packet delivery ratio and average end-to-end delay are shown in Figures8 and 9. It can be seen that as the number of RSUs increases, the packet delivery ratio of the three coverage algorithms gradually increases. The reason for this is that when the number of RSUs is small, the three deployment methods cannot provide enough opportunities for all vehicles to enter the coverage area. In this case, packet loss is mainly caused by unreachable routings. With the increase in the number of RSUs, the coverage and density have been improved, and the communication quality has been significantly enforced. As the number of RSUs increases, the service range becomes larger, and the end-to-end delay gradually decreases. When the number of RSUs is 400, the end-to-end delay of IHDA is approximately the same as that of BCC. The reason for this is that BCC takes guaranteeing the scale of communication as its main goal, so it has demonstrated relatively outstanding performance in terms of communication quality.Figure 8
Packet delivery ratio under different RSU budget.Figure 9
Average end-to-to delay under different RSU budget.


## 6. Conclusions

Designing the RSU plane in the popularity-based VAENT network brings many challenges to decision makers. Even if the number of RSUs required during the operation of the road network is known, their location will affect the key performance of many aspects of the final system architecture. Aiming at the problem of RSU service coverage in the IoV, this paper proposes a deployment mechanism based on node popularity to improve system performance. The coverage ratio is maximized by adjusting the weights of the three traffic parameters and adding the inhibition distance coefficient. We selected a real road network environment for simulation and analyzed the performance of the model using four important parameters: coverage time ratio, contacts per trip, packet delivery ratio, and average end-to-end delay. The simulation results show that, compared with other typical RSU deployment solutions, it can improve the service capability of the IoV for vehicles using the same deployment budget. With the gradual popularization of SDVN, in future research, we will continue to test its performance according to the role that RSU may be assigned in SDVN, including deployment schemes and additional functional tests.



---

*Source: 9980093-2021-06-24.xml*