# Travel Matrix Enabled Delta-Based Roadside Units Deployment for Vehicular Ad Hoc Networks: A Case of Kigali City

Authors: Evariste Twahirwa; Moyukh Laha; James Rwigema; Raja Datta
Journal: Journal of Advanced Transportation
 (2022)

---

## Abstract

Placements of Road Side Units (RSUs) are an important issue of vehicular networks in urban areas. The merged cost of procurement, installation, and maintenance of intelligent RSUs is high, and therefore, cost-effective deployment strategies are necessary. In this article, we propose a scheme that optimally deploys intelligent roadside units using a travel matrix scheme based on the classical delta strategy where urban vehicles are involved in RSUs communication in the course of their travel times. Four (4) vehicular communication modes are studied, namely, (a) travel matrix based on delta RSUs deployment communication, (b) road intersection-based RSUs deployment communication, (c) road segmentation, and (d) free vehicle-to-vehicle communication. A baseline algorithm is suggested to determine the optimal locations of RSUs in terms of their geographical positions. A travel matrix technique is proposed to trace vehicles’ routeways and travel times in some points of interest (POI). Our intention is to seek an approach that reduces the required number of RSUs and ensures greater network performance effectiveness in terms of packets delivery ratio, throughput, message delay, and jitter; from our study, travel matrix delta-based placement of RSUs becomes the best in our case study scenario. The simulation results indicate that the travel matrix deployment is a suitable deployment scheme in the case study area since it can reduce the number of RSUs while enhancing the vehicular communication abilities under different vehicle density scenarios.


---

## Body

## 1. Introduction

Vehicular ad hoc network (VANET) is a subclass of mobile ad hoc networks (MANET) that consists of dynamic and/or stationary vehicles connected by the wireless network through specialized protocols like IEEE 802.11p based onDedicated Short-Range Communication (DSRC). With the development of the smart city and the Internet of Things (IoT), VANET and Intelligent Transport Systems (ITS) at large have gained a lot of popularity with IoT and its frameworks [1]. IoT is a materialization of the connected world where physical entities are equipped with sensing, processing, and communication capabilities. These entities interact with each other following user-defined rules. IoT network has seamlessly introduced several opportunities that initiate value-added services, which presently accelerate the development of smart city [2]. With the advancement of smart city and smart infrastructures, vehicles have continued to gain a paramount consideration for IoT [3] and the services they render to the smart city are very clear [4]. Despite a multitude of components that constitute an integral smart city ecosystem, ITS plays a vital role beyond vehicles communicating to the infrastructures and has demonstrated prominent improvement to the lives of urban commuters, mainly in the aspects of city traffic control [5].From the existing literature, we find that the combined costs of procurement, deployment, and maintenance of RSUs are prohibitively high. For instance, according to the study in the U.S. Department of Transportation in 2018, a singleDedicated Short-Range Communication (DSRC) RSU needs USD 1300, USD 850, and USD 2000 for procurement, deployment, and configuration, respectively [6]. Therefore, intelligent RSU deployment strategies are very crucial to minimize the number of RSUs and still satisfy the desired network performance. RSU deployment is usually density-based, where RSUs are strategically positioned considering the number of vehicles in a particular region of interest [7]. In a city, at any given time, the vehicles are not evenly distributed. For instance, traffic densities in downtown, commercial, and industrial zones are much higher than those in the outskirts, and an inverse proportion deployment strategy is preferred in these circumstances [8]. In addition, a coalition of various placement schemes may be opted to leverage the trade-offs between deployment cost and enhanced network performance.The authors of [9, 10] proposed a genetic algorithm for RSUs deployment using a method named delta deployment. Their goal is to meet a deployment that allows a specific number of vehicles to have access to RSUs during a certain percentage of their trip time. Their work assumes that not every time all the vehicles need to be connected to the RSUs; instead, some transport agencies may require a certain number of vehicles to connect to the RSUs for a certain percentage of their trip time. Our work is closer to theirs in a way that we employ a delta-deployment strategy to minimize the deployment cost of roadside units in urban scenarios. Even though RSUs deployment optimization has been extensively studied in various ways, such as formulating deployments as linear integer programs optimization problems and RSU-vehicle contact duration problems, the delta-deployment strategy still needs improvement and investigative contributions. In [11], a graph-based roadside unit placement model is suggested, all the urban and VANETs limitations are employed for a weighted graphic representation to solve the Steiner tree formulation problem. Whereas different dimensional deployment problems of hybrid VANET-sensor networks are presented in [12], the purpose of the study is to reduce the total distance and the total number of hops from the sensing nodes to the nearest roadside. As far as our knowledge goes, research works have been conducted for joint optimization of the placement of RSUs considering cost minimization and Quality of Service. However, the body of knowledge regarding RSUs deployment strategy based on the delta deployment stills needs contribution. Our study compares delta deployments using typical urban traffic flows, RSUs deployment at road intersections, and free intervehicular communications. The best solution could be adopted for the physical placement of the RSUs for different traffic scenarios in an urban area.Delta-Δ deployment is a good metric that ensures minimum installation costs and at the same time guarantees good network performance. A deployment is Δβ1β2 if at any moment β2 percentage of all available vehicles needs to be in contact with roadside infrastructures during β1 percentage of their travel times. Suppose in vehicular communication 95% of the vehicles need to communicate with RSUs for 95% of their travel times. Then its delta deployment will be expressed as Δ0.950.95 [13]. This metric can be adopted by network designers for new network setups and to make economic decisions for network infrastructures. Δ-installation strategy may also help compare and contrast the performance of different vehicular communication networks and their quality.The main contributions of this article are listed as follows:(1)
We use a travel matrix technique to trace the routeways of all vehicles in the case study area and the length of time each vehicle spends in every point of interest (POI) in the city. This approach is very crucial as it gives us the length of time a vehicle spends in the target area(2)
We utilize a classical delta-deployment strategy to model the optimal placement of RSUs in urban scenarios ensuring basic network performance. The scheme reduces the number of RSUs while improving network effectiveness in the case study area.(3)
We demonstrate a sequence of simulations environments that are convenient for vehicular networks modeling and simulations, where output from one tool could be employed as an input in the next tool.(4)
Through simulations, we show that delta-deployment minimizes a significant number of roadside units in wide-area placement. The deployment studied in this research work considers a small scale area; however, the methodology is applicable to wider urban scenarios.


## 2. Related Work

Several works have been proposed for RSUs deployment mechanisms that ensure coverage and connectivity. The authors of [14] suggested RSU deployment alongside road infrastructure for vehicular communications in urban scenarios. Their work aims at improving the network connectivity and coverage of maximum vehicles using a minimum number of RSUs. The work in [15] proposed a genetic algorithm known as the Genetic Algorithm for Roadside Unit Deployment (GARSUD) to automatically establish RSUs in optimal locations to enhance traffic warning notifications delivery in a variety of terrain layouts. The work in [16] postulated an optimization technique that employs a mixed-integer linear programming method for the deployment of RSUs by emphasizing vehicular communications. The researchers here aim to provide network coverage and meet computational demand. Whereas [17] introduced the optimal installation of RFID-integrated VANETs for ITS, the authors’ contribution is to investigate the deployment of base stations and RFID-reader-embedded roadside units to obtain a good network architecture by taking into account communication, coverage, and connectivity requirements. Optimal cost-effective placement of roadside units in VANET has been studied and algorithms have been proposed in the literature.In [18], a novel algorithm that guarantees low-cost wide-area urban deployment of RSUs by ensuring the use of the selected roadside unit and intervehicle communication between any two adjacent points of the highway. In contrast, in [19], the authors discussed an optimal and greedy algorithm for one-dimensional roadside unit placement and their new model involves the curved and nonuniformity nature of the roads. Their research work considers the characteristics of the one-dimensional RSU deployment problem and designed an optimal deployment algorithm. Reference [20] revealed a delay-bound and cost-effective RSU positioning in urban vehicular ad hoc networks. Here, the authors showed it as a nondeterministic polynomial-time hard problem and intended to augment the number of roads covered by the deployed RSUs using the binary differential evolution method. The results show improvement on road coverage ratio, packet loss ratio with controlled delay, and downsized deployment budget. Reference [21] proposed an optimal mechanism to determine the RSUs stations in urban vehicular networks by employing analytic binary integer programming and balloon expansion analogy to propose a heuristic method, whereas a budgeted maximum coverage-based mmWave RSUs deployment in urban vehicular ad hoc network is suggested in [22].In [23], the authors put forward an effective RSU deployment scheme that covers a possible big number of intersections aiming at maximizing network connectivity while utilizing a small number of RSUs. Their deployment algorithm helps find an optimal number and deployable locations of RSUs to cover all intersections of interest. Liang et al. [24] showed an optimal deployment strategy in a 2D vehicular network where the work formulates RSUs placement as an integer linear program optimization problem that seamlessly finds the trade-off between coverage and cost considering signal propagation impaired by the presence of buildings and other terrain obstructions on RSU antenna. Authors in [25] formulated the RSU placement problem for urban and highway scenarios as binary integer programming where the aim is to reduce the placement and servicing expenses on RSUs. In particular, several researches have been conducted regarding vehicular infrastructure deployment using delta-metric. In [9], delta genetic algorithms were proposed to estimate the minimum required infrastructure to supplement vehicular networks. The findings of the study have proved that delta deployment needs fewer RSUs while ensuring a similar deployment efficiency. The work of [13] suggested a delta-r greedy heuristic algorithm to find out the solution of RSUs allocation to meet delta-deployment metric. In contrast, in [26], a novel greedy randomized adaptive search procedure (GRASP) heuristic was proposedto solve the RSUs placement problem for vehicular networks with mutihop transmission and synchronous communication. The scheme supports both vehicle-to-vehicle and vehicle-to-infrastructure communication. Reference [27] proposed a Gamma-Reload Deployment strategy to deploy roadside units along with road networks of complex topology by creating islands of coverage for data dissemination. From the literature, we observe that the placement of the roadside units in urban areas for vehicular environments requires a big number of RSUs. This explains why sophisticated studies ensure a minimized number of RSUs and, at the same time, improve the network performance.


## 3. Methodology

In Figure1, we show the methodological description that governs our RSUs deployment process. The routes of interest and the pathways of all vehicles under consideration are obtained from an open street map (OSM) [28]. Thereafter, we convert the OSM map to the simulation of urban mobility (SUMO) [29] environment whose output is convenient for both optimization and network simulation processes. Under the CPLEX optimization environment [30], Δ-parameters are introduced to obtain the optimal solution, presenting the number of RSUs, and their corresponding geographical positions. Finally, we do the network performance analysis using Network Simulator 3 NS3[31] to evaluate the target network performance metrics.Figure 1
The architecture of RSUs deployment process.


### 3.1. Area of Interest Demonstration

In Figures2 and 3, we portray the topology of the region of interest. Initially, we extract the target area from an OSM as a dataset. Most importantly, our area of interest is represented in a grid cell form and partitioned into several grid cells to simplify deployment simulation activities, as explained in the later sections of this article. In the context of SUMO, the nodes demonstrate roads intersections, while edges represent roads in the target area.Figure 2
OSM map.Figure 3
SUMO map.OSM has anapplication program interface(API) that allows us to import/export geographical data to its repository. It provides essential features that facilitate urban mobility simulation, including roads, buildings, and waterways. We convert our OSM file into a net.xml file that virtually generates routes in the map and configures it with the SUMO. With the python scripts, we are able to extract and execute the exact real number of vehicles in real maps, i.e., our area under consideration.Our study scope highly depends on the traffic volumes; this elucidates why we rely on the traffic flow information from the case study area. Although the SUMO map presents both main roads and lanes that link residential areas with major roads, our simulation explicitly considers the arterial roads with heavy traffic volumes. As it is essential to know the traveling time of the vehicles and the routes they follow, here we introduce a travel matrix that depicts the vehicle’s travel route and travel time.Our simulation studies consider the main road junctions for roadside units deployment. In Figure4, we depict the SUMO map that clearly highlights the major road junctions, which could serve as the target deployable pints for roadside infrastructure for vehicular communication.Figure 4
Main road intersections.


### 3.2. Road Segmentation for RSUs Deployment

The deployment of roadside units for vehicular use appears in different modes. In Figure5, we demonstrate a RSUs placement method based on the transmission range of the RSU transmitter TX. Considering a road of length X and a transmitter with a range of TX, we simplify the road coverage by the roadside units. While several other methods consider partitioning the area with roads included into a number of grid points for RSUs deployment, this particular method will place the RSUs randomly along the road based on their transmission range.Figure 5
Road segmentation for RSUs deployment.


### 3.3. Traffic Flows Representation

The traffic flow is observed from six different routes that convert the area of interest. For simplicity, the estimation of vehicles at a certain instance is assumed as the summation of vehicles from all six routes, as shown in Figure6. The road traffic information was collected from the city of Kigali (Rwanda) on a working day. Figure 7 demonstrates the average vehicle densities at different time slots.Figure 6
Routes in the case study area.Figure 7
Vehicle densities.The total number of vehicles in the considered areaVtotal is calculated as follows:(1)VTotal=∑r=1RVr,where VTotal is the total number of vehicles in the area of interest at a moment, R is the collection of routes in the same area, and Vr is the the number of vehicles in route r.Figures8–13 indicate the traffic flow from all the six routes that cover the target area. All routes were surveyed for 24 hours of the day. All moving entities are recorded in our dataset that includes bikes, motorcycles, and other vehicles (cars, minibus, bus, and trucks). However, only cars, minibuses, buses, and trucks are considered in our cases since our proposal suits these vehicles. The collected information gives us a proper picture of the traffic sizes and traffic volumes in the respective routes. At every time interval, we have done the simulation based on the average number of vehicles available.Figure 8
Traffic flow: route A.Figure 9
Traffic flow: route B.Figure 10
Traffic flow: route C.Figure 11
Traffic flow: route D.Figure 12
Traffic flow: route E.Figure 13
Traffic flow: route F.It may be noted that the deployment process may incur reasonable additional variable costs based on the terrain complexity of grid cells. However, in this work, for simplicity, we have considered that all grid cells are assumed to be of uniform topology. Our model considers the substantial cost of roadside units in terms of their numbers with a logical understanding that once the number of roadside units is reduced, the overall cost, including procurement, configuration, and servicing costs, is also reduced. Our deployment simulations use a scenario of6km2 whose week traffic flow information is known and presented above. Moreover, we employ python scripts to model the dimensions of the simulated area in a macroscopic simulation of the urban mobility network of roads and other urban structures. This clearly grants us the exact locations of every physical feature, including the position obtained optimal positions of the RSUs.


### 3.4. RSUs Delta-Based Deployment Algorithm

In this section, we give more details about our baseline Algorithm1. The realistic traffic sizes are randomly moved in the road sections M. Other urban features that greatly affect the performance of vehicular communications are included in these models. Additional features include buildings, trees, waterways, and parks. This demonstrates a virtual realization of the actual network once deployed at the designated urban points. Here, Vβ1,β2 are the percentages of vehicles that require delta connection and the required percentage of trip time connection, respectively; Vr is the instantaneous number of vehicles in road r. n is the number of iterations through which our simulation is carried out.Algorithm 1: RSUs Deployment Algorithm.
(1)
InputsM,∑r=1RVr,n,savg,Δparameters(2)
Output←S1, S2,S3(3)
Fori←0ton ⊳ Represent the number of iterations(4)
Generate SUMO Solution:S1 ⊳ S1 Contains Trace file(5)
IncorporateS1 in CPLEX Optimization(6)
Generate CPLEX Optimization Solution:S2(7)
UseS1 & S2 in NS3 to get QoS solution: S3(8)
Output←S3 ⊳ The solution S3 provides us with the desired Network QoS Metrics(9)
End for(10)
return OutputOur baseline algorithm shown below plays a key role in determining the RSU optimal positions. The algorithm runs our solution in sequential order. The input step loads the number of vehiclesvr, road network M, delta parameters Δparameters, the vehicles average speed Savg, and the iterations number n for the algorithm. While SUMO provides the traffic flow simulations in the target area, our integer linear problem is solved using CPLEX and the results from these two models are fed to the network simulating environment to understand how the network performs after the deployment. This provides the testing of the virtual network performance and thereby increases the level of confidence for the physical placement of the RSUs in the predetermined points. In the next section, we present the delta-deployment problem and use it to solve our deployment problem using the typical traffic flow in the case study area.In Table1, we explain the key notations that are used in the model. The core of this model is to determine a minimal number of RSUs that allow a desired percentage of moving vehiclesβ2 to stay intact with RSUs for the planned travel time percentageβ1. This is based on the fact that not all the time all vehicles need to communicate to the roadside units, and even if they do, the drivers may decide otherwise. Further, a vehicle may be under the coverage area of more than one RSU; however, for simplicity, a vehicle can utmost be connected to one RSU at an instant. In our model, all RSUs are assumed to be deployable in a 2-dimensional plane, each at a point. The coverage separation of any two grid cells is represented as Euclidean distance. If, for instance, a vehicle at grid cell Ixi,yi communicates to a RSU placed at a point Jxj,yj. The Euclidean distance between these points d is represented as follows: di,j = i−j = xi−xj2+yi−yj2. The distance affects the communication signal status:(2)Pvi,j=1,ifdi,j≤r0,Otherwise.Table 1
Notations used in the Optimization Problem (Parameters used and their descriptions).
SymbolDescriptionFCFixed cost of a Road Side Unitβ1:The percentage of travel time that a vehicle will be connectedβ2:The percentage of vehicles required to be connectedttn:Total travel time of a vehicle nVThe number of vehicles availabletinThe time taken by vehiclen in grid cell ixi:A binary variable that is 1 if a road side unit is placed at grid cell otherwise 0VnBinary variable for a vehiclen travel beta1 and belong to beta2In equation (2), we define a connectivity probability of a vehicle vi to a roadside unit deployed at a point j using a Boolean coverage model. We assume that the roadside units are placed in a 2-dimensional plane having equal communication range (r). di,j is the Euclidean distance between the vehicle vi and roadside unit placed at point j. The connectivity probability of vehicle v is its probability of getting connected. In the following equations (3)–(8), we present the objective function and constraints it is subjected to. The objective function is to minimize the number of roadside units.(3)Min∑i∈CFCxi,(4)s.t.(5)∑i∈Ctinttnxi≥β1vn,∀nεV,(6)∑n∈Vvn≥β2V,∀nεV,(7)xiε0,1,∀i,(8)vnε0,1,∀n.The objective function of this model equation (3) minimizes the deployment cost of the RSUs. Here FC signifies the fixed cost of a roadside unit where the constraints are mainly the number of vehicles available, the percentage of vehicles that need to be connected, and the percentage of connectivity during the trips. We have considered the actual vehicle densities from the area of interest. Equation (5) ensures that if a vehicle is connected to RSU for β1 time, it belongs to the solution, whereas equation (6) makes sure that a required percentage of the vehicles (β2) is connected to RSUs. The rest are Boolean variables 7 and 8; xi is 1 if a particular partition is a candidate for roadside unit placement and 0 otherwise. Likewise, vn is 1 if a vehicle n is connected during the percentage of its travel time and 0 otherwise. To ensure maximum reasonable connectivity of the mobile vehicles, we have considered that 95% of the available vehicles are connected in each simulation instance, during 95% of their trip time, i.e., β1 and β2 = 95%. In the following subsection, we introduce a simulation technique that traces the travel time of each vehicle from the POI. Since the movement of the vehicles is random in the target areas, not all vehicles traverse all the POIs; hence, their travel times are 0 s.


### 3.5. Travel Matrix

In this subsection, we introduce a travel matrix technique that assists us in tracing the paths and the time (in seconds) every vehicle under study spent in each POI. Since there are no publicly available mobility data in terms of time slots the vehicles spend in grid cells, we have used real traffic sizes of urban mobility in the simulations and have used python scripts to obtain their random mobility files that contain the routes each vehicle follows in terms of geographical coordinates.The elements of the travel matrix in row onetc1v1, tc2v1tc3v1, …, tcNv1 show the travel history of vehicle v1 and the amount of time it spends in grid cells c1, c2, c3, and cN, respectively. The travel history of every vehicle is extracted from the mobility file and the grid cells that vehicles traverse are obtained as well. Travel information retrieved from the mobility files is used to get the amount of time it takes to traverse each POI. As mentioned, we realize that not each of the vehicles passes in all of the grid cells and therefore the travel times in such grid cells are considered to be 0 s. This information is very important to calculate the percentage of time that vehicles could be connected to the roadside unit placed at a certain grid cell i. For instance, the total travel times of six vehicles v1, v2, v3, v4,v5, v6 are given in Figure 14.Figure 14
Vehicle paths.The change of position of all the vehicles under study is recorded in a mobility file that keeps track of the geographical coordinates of vehicles and their traveling times, as shown in Figure15. For instance, node 0 (vehicle) at 0th second of simulation is at position P(x, y) = (740.24, 654.54), which is set to P(x, y) = (740.24, 654.54) as its new position at the 21th second. The travel matrix keeps a record of all the vehicles under consideration, and the summation of all the time slots each of the vehicles spent in various POIs results in its total travel time. The other important parameters are the uplink and the downlink signal strengths between the vehicle and the deployed infrastructures. Studying the signal strength between the vehicles and RSUs determines the dimensions of the gridcells of which some are deployable candidates of RSUs.Figure 15
Vehicle positions in the mobility file.


## 3.1. Area of Interest Demonstration

In Figures2 and 3, we portray the topology of the region of interest. Initially, we extract the target area from an OSM as a dataset. Most importantly, our area of interest is represented in a grid cell form and partitioned into several grid cells to simplify deployment simulation activities, as explained in the later sections of this article. In the context of SUMO, the nodes demonstrate roads intersections, while edges represent roads in the target area.Figure 2
OSM map.Figure 3
SUMO map.OSM has anapplication program interface(API) that allows us to import/export geographical data to its repository. It provides essential features that facilitate urban mobility simulation, including roads, buildings, and waterways. We convert our OSM file into a net.xml file that virtually generates routes in the map and configures it with the SUMO. With the python scripts, we are able to extract and execute the exact real number of vehicles in real maps, i.e., our area under consideration.Our study scope highly depends on the traffic volumes; this elucidates why we rely on the traffic flow information from the case study area. Although the SUMO map presents both main roads and lanes that link residential areas with major roads, our simulation explicitly considers the arterial roads with heavy traffic volumes. As it is essential to know the traveling time of the vehicles and the routes they follow, here we introduce a travel matrix that depicts the vehicle’s travel route and travel time.Our simulation studies consider the main road junctions for roadside units deployment. In Figure4, we depict the SUMO map that clearly highlights the major road junctions, which could serve as the target deployable pints for roadside infrastructure for vehicular communication.Figure 4
Main road intersections.


## 3.2. Road Segmentation for RSUs Deployment

The deployment of roadside units for vehicular use appears in different modes. In Figure5, we demonstrate a RSUs placement method based on the transmission range of the RSU transmitter TX. Considering a road of length X and a transmitter with a range of TX, we simplify the road coverage by the roadside units. While several other methods consider partitioning the area with roads included into a number of grid points for RSUs deployment, this particular method will place the RSUs randomly along the road based on their transmission range.Figure 5
Road segmentation for RSUs deployment.


## 3.3. Traffic Flows Representation

The traffic flow is observed from six different routes that convert the area of interest. For simplicity, the estimation of vehicles at a certain instance is assumed as the summation of vehicles from all six routes, as shown in Figure6. The road traffic information was collected from the city of Kigali (Rwanda) on a working day. Figure 7 demonstrates the average vehicle densities at different time slots.Figure 6
Routes in the case study area.Figure 7
Vehicle densities.The total number of vehicles in the considered areaVtotal is calculated as follows:(1)VTotal=∑r=1RVr,where VTotal is the total number of vehicles in the area of interest at a moment, R is the collection of routes in the same area, and Vr is the the number of vehicles in route r.Figures8–13 indicate the traffic flow from all the six routes that cover the target area. All routes were surveyed for 24 hours of the day. All moving entities are recorded in our dataset that includes bikes, motorcycles, and other vehicles (cars, minibus, bus, and trucks). However, only cars, minibuses, buses, and trucks are considered in our cases since our proposal suits these vehicles. The collected information gives us a proper picture of the traffic sizes and traffic volumes in the respective routes. At every time interval, we have done the simulation based on the average number of vehicles available.Figure 8
Traffic flow: route A.Figure 9
Traffic flow: route B.Figure 10
Traffic flow: route C.Figure 11
Traffic flow: route D.Figure 12
Traffic flow: route E.Figure 13
Traffic flow: route F.It may be noted that the deployment process may incur reasonable additional variable costs based on the terrain complexity of grid cells. However, in this work, for simplicity, we have considered that all grid cells are assumed to be of uniform topology. Our model considers the substantial cost of roadside units in terms of their numbers with a logical understanding that once the number of roadside units is reduced, the overall cost, including procurement, configuration, and servicing costs, is also reduced. Our deployment simulations use a scenario of6km2 whose week traffic flow information is known and presented above. Moreover, we employ python scripts to model the dimensions of the simulated area in a macroscopic simulation of the urban mobility network of roads and other urban structures. This clearly grants us the exact locations of every physical feature, including the position obtained optimal positions of the RSUs.


## 3.4. RSUs Delta-Based Deployment Algorithm

In this section, we give more details about our baseline Algorithm1. The realistic traffic sizes are randomly moved in the road sections M. Other urban features that greatly affect the performance of vehicular communications are included in these models. Additional features include buildings, trees, waterways, and parks. This demonstrates a virtual realization of the actual network once deployed at the designated urban points. Here, Vβ1,β2 are the percentages of vehicles that require delta connection and the required percentage of trip time connection, respectively; Vr is the instantaneous number of vehicles in road r. n is the number of iterations through which our simulation is carried out.Algorithm 1: RSUs Deployment Algorithm.
(1)
InputsM,∑r=1RVr,n,savg,Δparameters(2)
Output←S1, S2,S3(3)
Fori←0ton ⊳ Represent the number of iterations(4)
Generate SUMO Solution:S1 ⊳ S1 Contains Trace file(5)
IncorporateS1 in CPLEX Optimization(6)
Generate CPLEX Optimization Solution:S2(7)
UseS1 & S2 in NS3 to get QoS solution: S3(8)
Output←S3 ⊳ The solution S3 provides us with the desired Network QoS Metrics(9)
End for(10)
return OutputOur baseline algorithm shown below plays a key role in determining the RSU optimal positions. The algorithm runs our solution in sequential order. The input step loads the number of vehiclesvr, road network M, delta parameters Δparameters, the vehicles average speed Savg, and the iterations number n for the algorithm. While SUMO provides the traffic flow simulations in the target area, our integer linear problem is solved using CPLEX and the results from these two models are fed to the network simulating environment to understand how the network performs after the deployment. This provides the testing of the virtual network performance and thereby increases the level of confidence for the physical placement of the RSUs in the predetermined points. In the next section, we present the delta-deployment problem and use it to solve our deployment problem using the typical traffic flow in the case study area.In Table1, we explain the key notations that are used in the model. The core of this model is to determine a minimal number of RSUs that allow a desired percentage of moving vehiclesβ2 to stay intact with RSUs for the planned travel time percentageβ1. This is based on the fact that not all the time all vehicles need to communicate to the roadside units, and even if they do, the drivers may decide otherwise. Further, a vehicle may be under the coverage area of more than one RSU; however, for simplicity, a vehicle can utmost be connected to one RSU at an instant. In our model, all RSUs are assumed to be deployable in a 2-dimensional plane, each at a point. The coverage separation of any two grid cells is represented as Euclidean distance. If, for instance, a vehicle at grid cell Ixi,yi communicates to a RSU placed at a point Jxj,yj. The Euclidean distance between these points d is represented as follows: di,j = i−j = xi−xj2+yi−yj2. The distance affects the communication signal status:(2)Pvi,j=1,ifdi,j≤r0,Otherwise.Table 1
Notations used in the Optimization Problem (Parameters used and their descriptions).
SymbolDescriptionFCFixed cost of a Road Side Unitβ1:The percentage of travel time that a vehicle will be connectedβ2:The percentage of vehicles required to be connectedttn:Total travel time of a vehicle nVThe number of vehicles availabletinThe time taken by vehiclen in grid cell ixi:A binary variable that is 1 if a road side unit is placed at grid cell otherwise 0VnBinary variable for a vehiclen travel beta1 and belong to beta2In equation (2), we define a connectivity probability of a vehicle vi to a roadside unit deployed at a point j using a Boolean coverage model. We assume that the roadside units are placed in a 2-dimensional plane having equal communication range (r). di,j is the Euclidean distance between the vehicle vi and roadside unit placed at point j. The connectivity probability of vehicle v is its probability of getting connected. In the following equations (3)–(8), we present the objective function and constraints it is subjected to. The objective function is to minimize the number of roadside units.(3)Min∑i∈CFCxi,(4)s.t.(5)∑i∈Ctinttnxi≥β1vn,∀nεV,(6)∑n∈Vvn≥β2V,∀nεV,(7)xiε0,1,∀i,(8)vnε0,1,∀n.The objective function of this model equation (3) minimizes the deployment cost of the RSUs. Here FC signifies the fixed cost of a roadside unit where the constraints are mainly the number of vehicles available, the percentage of vehicles that need to be connected, and the percentage of connectivity during the trips. We have considered the actual vehicle densities from the area of interest. Equation (5) ensures that if a vehicle is connected to RSU for β1 time, it belongs to the solution, whereas equation (6) makes sure that a required percentage of the vehicles (β2) is connected to RSUs. The rest are Boolean variables 7 and 8; xi is 1 if a particular partition is a candidate for roadside unit placement and 0 otherwise. Likewise, vn is 1 if a vehicle n is connected during the percentage of its travel time and 0 otherwise. To ensure maximum reasonable connectivity of the mobile vehicles, we have considered that 95% of the available vehicles are connected in each simulation instance, during 95% of their trip time, i.e., β1 and β2 = 95%. In the following subsection, we introduce a simulation technique that traces the travel time of each vehicle from the POI. Since the movement of the vehicles is random in the target areas, not all vehicles traverse all the POIs; hence, their travel times are 0 s.


## 3.5. Travel Matrix

In this subsection, we introduce a travel matrix technique that assists us in tracing the paths and the time (in seconds) every vehicle under study spent in each POI. Since there are no publicly available mobility data in terms of time slots the vehicles spend in grid cells, we have used real traffic sizes of urban mobility in the simulations and have used python scripts to obtain their random mobility files that contain the routes each vehicle follows in terms of geographical coordinates.The elements of the travel matrix in row onetc1v1, tc2v1tc3v1, …, tcNv1 show the travel history of vehicle v1 and the amount of time it spends in grid cells c1, c2, c3, and cN, respectively. The travel history of every vehicle is extracted from the mobility file and the grid cells that vehicles traverse are obtained as well. Travel information retrieved from the mobility files is used to get the amount of time it takes to traverse each POI. As mentioned, we realize that not each of the vehicles passes in all of the grid cells and therefore the travel times in such grid cells are considered to be 0 s. This information is very important to calculate the percentage of time that vehicles could be connected to the roadside unit placed at a certain grid cell i. For instance, the total travel times of six vehicles v1, v2, v3, v4,v5, v6 are given in Figure 14.Figure 14
Vehicle paths.The change of position of all the vehicles under study is recorded in a mobility file that keeps track of the geographical coordinates of vehicles and their traveling times, as shown in Figure15. For instance, node 0 (vehicle) at 0th second of simulation is at position P(x, y) = (740.24, 654.54), which is set to P(x, y) = (740.24, 654.54) as its new position at the 21th second. The travel matrix keeps a record of all the vehicles under consideration, and the summation of all the time slots each of the vehicles spent in various POIs results in its total travel time. The other important parameters are the uplink and the downlink signal strengths between the vehicle and the deployed infrastructures. Studying the signal strength between the vehicles and RSUs determines the dimensions of the gridcells of which some are deployable candidates of RSUs.Figure 15
Vehicle positions in the mobility file.


## 4. Simulation Result Analysis

### 4.1. Optimization with CPLEX

We have simulated the network usingNetwork Simulator-3 (NS-3) and Simulation of Urban Mobility (SUMO) to study the vehicle-to-infrastructure and infrastructure-to-vehicle communications. While SUMO is used to generate road traffic flow, NS-3 is used for network performance simulations. Initially, we have modeled the optimal placement of the RSUs using the IBM ILOG-CPLEX Optimization tool through its solver to obtain optimal solutions in terms of the number of RSUs and their optimal locations. The locations of RSUs are indicated by the geographical coordinates x1,y1, x2,y2,x3,y3, …, xn,yn. In the CPLEX solution, as shown in Figure 16, 1 represents that a grid is a candidate for RSU deployment, else 0.Figure 16
Optimal locations of roadside units.As mentioned, the above string of 1 s and 0 s denotes the optimal positions of RSUs in the area of interest and the ones that are not selected. The entire area is divided into a number of grids with each grid‘s centroid coordinates recorded. Here each grid is individually represented by its geographical coordinatesx and y. The coordinates of the grids represented by ones are considered for optimal placements of the RSUs. Figure 17 shows the optimal solution, whereas Figure 18 shows the variations of β1, β2 and the the number of RSUs.Figure 17
Optimal solution from the solver.Figure 18
beta1, beta2 vs. RSUs.In Figure19, we demonstrate the distribution of RSUs using the delta deployment and the main intersection-based deployment schemes are demonstrated, respectively. The delta-deployment method follows the placement of RSUs in the optimal locations obtained from the ILOG-CPLEx solution. The locations are geographically represented by the x,y coordinates. The intersection-based deployment method assumes the placement of RSUs at 13 identified road intersections in the area of study, whereas the delta-deployment places RSUs based on the CPLEX solution.Figure 19
Optimal solution and delta-dimension values.In the delta-deployment method, the target area is partitioned into a total of 24 small square grid cells each of an area of0.25km2 (500 m by 500 m). Here only 10 of these are identified as the optimal positions for RSUs deployment according to our traffic flow simulations with all β1 and β2 set to 95%.Based on the delta-deployment method, all is fine if RSU is exactly deployed at the center of the chosen grid cell. To ensure this, we have employed the center geometry theorem of a square since all grids are equal in size and have the same shape. For simplicity, we assume that all road sections in the same grid cell are covered by the RSU placed at the grid cell only. All vehicles connected to RSUi in candidate grid cell Ci operate based on the principle stated in equation (2). Considering Figure 20, for example, RSU deployed at point C is expected to connect all vehicles that follow the road sections in the grid cell during β1 percentage of their travel time. This mechanism would flexibly allow planners to decide how many RSUs transceivers would be active at a time, based on the expected traffic flows. In real cases, urban traffic drastically changes according to the city’s business nature. In this study, we utilize RSUs antennas that have longer transmission ranges than the half-length of grid cells’ dimensions, i.e., 350m and 250m, respectively. This ensures that all road portions in a grid cell are covered once the RSU is deployed at the grid cell centroid.Figure 20
Square grid cell centroid.


### 4.2. Network Simulation Setup

In Table2, we present the simulation setup. We evaluate the effectiveness of our deployment strategies by simulations. Vehicles communicate with stationary RSUs through the IEEE 802.11p standard. The transmission power is kept at 25 dBm. We have simulated a small area of 6km2 with dimensions 2km by 3km of downtown Kigali city. We have solved our deployment model using CPLEX (version 12.8) that gave outputs after 10 msecs for all instances with various values of β1 and β2. Using SUMO, we extracted the main roads with heavy traffic. The main roads are demonstrated here as line segments, while city buildings are demonstrated as polygonal shapes.Table 2
Simulation parameters (parameters used and their values).
ParametersParameter valueVehicle densities30,60,90,120,150 vehiclesRSUs10,13,18.Routing protocolAODVMAC layer protocolIEEE 802.11pTraffic generatorSUMOMobility modelLog distance path lossAntenna height5MTransmission power25dBmSimulation area6kM2NS33.6


### 4.3. Network Performance Analysis

In this subsection, we discuss the effectiveness of the network performance and investigate four important performance metrics to evaluate our network, i.e.,overall success packets delivery ratio in %, throughput in Kbps, message delay in seconds, and, finally, jitter in nanoseconds. The purpose of the study is to improve the performance of the optimally deployed roadside units so that we save the costs related to a big number of RSUs and connect a desired number of vehicles. We introduce four (4) vehicular communication modes: (a) road intersection RSUs placement communication, (b) travel matrix based on delta-deployment communication, (c) road segmentation RSUs placement communication, and (d) infrastructure-free vehicle-to-vehicle communication. In all the simulation instances, the delta-enabled scheme has shown good performance in terms of high message success rate, throughput, low jitter, and message delays. In this study, we have employed the IEEE802.11p media access control protocol that is convenient for dedicated short-range communication and dynamic topology vehicular communications (DSRC). Particularly, the message success rate is a measure of packets' reachability, i.e., overall data packets that successfully reach the receivers from the transmitters. Travel matrix-based deployment communication shows better results than the rest methods for all four (4) network metrics.We start by carrying out a study that learns the performance of the travel matrix based on the classical delta deployment compared to other approaches using five (5) different traffic volumes. Figure21 shows the overall packets delivery ratio that counts for the message loss in both uplink and downlink, i.e., packets sent by vehicles to RSUs and RSUs to the vehicles, respectively. We can see from the figure that TM-enabled delta deployment performs better with the increasing vehicular densities while it requires a fewer number of RSUs. Under the same vehicular densities, the travel matrix requires only ten (10) RSUs and thirteen (13) main road intersections were identified from the case study area. 13 RSUs are placed for this study to compare this placement scheme with others. Another generic placement method has been conducted, i.e., road segmentation. The six main roads from the same case study area have been segmented, and eighteen (18) RSUs are deployed based on the transmitter radius coverage. The communication networks supported by the previous method are compared for network performance effectiveness, and finally, free V2V communication is studied to motivate the need for RSUs placement from the case study area.Figure 21
Packets delivery ratio (%).PDR% is the % ratio of the data packets arriving at the receivers to those generated at the sources. In all our traffic flow volumes of the day, PDR% is greater in the delta-deployment method than that in the other three methods. Figure22 shows the network throughput that measures the rate at which bits are successfully delivered over the network channel.Figure 22
Throughput (kbps).Additionally, message transmission time variation metrics are also studied in terms of jitter and delay, as shown in Figures23 and 24, respectively. Likewise, delta deployment has demonstrated good results as it yields less message delay than intersection-based deployment and free intervehicle communication. It is worth mentioning that the traffic sizes considered in the delta deployment were equally considered for the other two strategies. While the study considers a small part of the urban area, a significant number of RSUs could be saved for the entire city deployment. The model also enables the vehicle owners to participate in vehicular networking during the time length of their choices.Figure 23
Jitter (ns).Figure 24
Delay (Secs).Interestingly, travel matrix-based delta deployment requires fewer RSUs (10) than the intersection-based deployment that places 13 RSUs. If we assume the installation of DSRC-RSUs mentioned in [6], keeping other features, such as grid cell accessibility complexity constant and delta deployment, could need a budget of USD 41,500 in our case of study. While intersection-based deployment would need a larger budget of USD 53,950, road segmentation will require 74,700. The delta-deployment strategy is less expensive, but, at the same time, it outperforms other methods in terms of communication effectiveness, as presented above. In conclusion, based on our typical traffic volumes and case study area, the delta-placement scheme becomes cost-effective and is more efficient in terms of operation. From the analysis of the results, we realize that connecting only a number of vehicles that wish to be involved in the communication for some specific duration will ensure good communication from the case study area. The results from this study demonstrate that the travel matrix supported that delta-based roadside deployment from the case study could yield a fewer number of the required infrastructure and still ensure good communication compared to other methods presented in this research work. The study could support policymakers, such as urban transport officials and communication infrastructure planners.


## 4.1. Optimization with CPLEX

We have simulated the network usingNetwork Simulator-3 (NS-3) and Simulation of Urban Mobility (SUMO) to study the vehicle-to-infrastructure and infrastructure-to-vehicle communications. While SUMO is used to generate road traffic flow, NS-3 is used for network performance simulations. Initially, we have modeled the optimal placement of the RSUs using the IBM ILOG-CPLEX Optimization tool through its solver to obtain optimal solutions in terms of the number of RSUs and their optimal locations. The locations of RSUs are indicated by the geographical coordinates x1,y1, x2,y2,x3,y3, …, xn,yn. In the CPLEX solution, as shown in Figure 16, 1 represents that a grid is a candidate for RSU deployment, else 0.Figure 16
Optimal locations of roadside units.As mentioned, the above string of 1 s and 0 s denotes the optimal positions of RSUs in the area of interest and the ones that are not selected. The entire area is divided into a number of grids with each grid‘s centroid coordinates recorded. Here each grid is individually represented by its geographical coordinatesx and y. The coordinates of the grids represented by ones are considered for optimal placements of the RSUs. Figure 17 shows the optimal solution, whereas Figure 18 shows the variations of β1, β2 and the the number of RSUs.Figure 17
Optimal solution from the solver.Figure 18
beta1, beta2 vs. RSUs.In Figure19, we demonstrate the distribution of RSUs using the delta deployment and the main intersection-based deployment schemes are demonstrated, respectively. The delta-deployment method follows the placement of RSUs in the optimal locations obtained from the ILOG-CPLEx solution. The locations are geographically represented by the x,y coordinates. The intersection-based deployment method assumes the placement of RSUs at 13 identified road intersections in the area of study, whereas the delta-deployment places RSUs based on the CPLEX solution.Figure 19
Optimal solution and delta-dimension values.In the delta-deployment method, the target area is partitioned into a total of 24 small square grid cells each of an area of0.25km2 (500 m by 500 m). Here only 10 of these are identified as the optimal positions for RSUs deployment according to our traffic flow simulations with all β1 and β2 set to 95%.Based on the delta-deployment method, all is fine if RSU is exactly deployed at the center of the chosen grid cell. To ensure this, we have employed the center geometry theorem of a square since all grids are equal in size and have the same shape. For simplicity, we assume that all road sections in the same grid cell are covered by the RSU placed at the grid cell only. All vehicles connected to RSUi in candidate grid cell Ci operate based on the principle stated in equation (2). Considering Figure 20, for example, RSU deployed at point C is expected to connect all vehicles that follow the road sections in the grid cell during β1 percentage of their travel time. This mechanism would flexibly allow planners to decide how many RSUs transceivers would be active at a time, based on the expected traffic flows. In real cases, urban traffic drastically changes according to the city’s business nature. In this study, we utilize RSUs antennas that have longer transmission ranges than the half-length of grid cells’ dimensions, i.e., 350m and 250m, respectively. This ensures that all road portions in a grid cell are covered once the RSU is deployed at the grid cell centroid.Figure 20
Square grid cell centroid.


## 4.2. Network Simulation Setup

In Table2, we present the simulation setup. We evaluate the effectiveness of our deployment strategies by simulations. Vehicles communicate with stationary RSUs through the IEEE 802.11p standard. The transmission power is kept at 25 dBm. We have simulated a small area of 6km2 with dimensions 2km by 3km of downtown Kigali city. We have solved our deployment model using CPLEX (version 12.8) that gave outputs after 10 msecs for all instances with various values of β1 and β2. Using SUMO, we extracted the main roads with heavy traffic. The main roads are demonstrated here as line segments, while city buildings are demonstrated as polygonal shapes.Table 2
Simulation parameters (parameters used and their values).
ParametersParameter valueVehicle densities30,60,90,120,150 vehiclesRSUs10,13,18.Routing protocolAODVMAC layer protocolIEEE 802.11pTraffic generatorSUMOMobility modelLog distance path lossAntenna height5MTransmission power25dBmSimulation area6kM2NS33.6


## 4.3. Network Performance Analysis

In this subsection, we discuss the effectiveness of the network performance and investigate four important performance metrics to evaluate our network, i.e.,overall success packets delivery ratio in %, throughput in Kbps, message delay in seconds, and, finally, jitter in nanoseconds. The purpose of the study is to improve the performance of the optimally deployed roadside units so that we save the costs related to a big number of RSUs and connect a desired number of vehicles. We introduce four (4) vehicular communication modes: (a) road intersection RSUs placement communication, (b) travel matrix based on delta-deployment communication, (c) road segmentation RSUs placement communication, and (d) infrastructure-free vehicle-to-vehicle communication. In all the simulation instances, the delta-enabled scheme has shown good performance in terms of high message success rate, throughput, low jitter, and message delays. In this study, we have employed the IEEE802.11p media access control protocol that is convenient for dedicated short-range communication and dynamic topology vehicular communications (DSRC). Particularly, the message success rate is a measure of packets' reachability, i.e., overall data packets that successfully reach the receivers from the transmitters. Travel matrix-based deployment communication shows better results than the rest methods for all four (4) network metrics.We start by carrying out a study that learns the performance of the travel matrix based on the classical delta deployment compared to other approaches using five (5) different traffic volumes. Figure21 shows the overall packets delivery ratio that counts for the message loss in both uplink and downlink, i.e., packets sent by vehicles to RSUs and RSUs to the vehicles, respectively. We can see from the figure that TM-enabled delta deployment performs better with the increasing vehicular densities while it requires a fewer number of RSUs. Under the same vehicular densities, the travel matrix requires only ten (10) RSUs and thirteen (13) main road intersections were identified from the case study area. 13 RSUs are placed for this study to compare this placement scheme with others. Another generic placement method has been conducted, i.e., road segmentation. The six main roads from the same case study area have been segmented, and eighteen (18) RSUs are deployed based on the transmitter radius coverage. The communication networks supported by the previous method are compared for network performance effectiveness, and finally, free V2V communication is studied to motivate the need for RSUs placement from the case study area.Figure 21
Packets delivery ratio (%).PDR% is the % ratio of the data packets arriving at the receivers to those generated at the sources. In all our traffic flow volumes of the day, PDR% is greater in the delta-deployment method than that in the other three methods. Figure22 shows the network throughput that measures the rate at which bits are successfully delivered over the network channel.Figure 22
Throughput (kbps).Additionally, message transmission time variation metrics are also studied in terms of jitter and delay, as shown in Figures23 and 24, respectively. Likewise, delta deployment has demonstrated good results as it yields less message delay than intersection-based deployment and free intervehicle communication. It is worth mentioning that the traffic sizes considered in the delta deployment were equally considered for the other two strategies. While the study considers a small part of the urban area, a significant number of RSUs could be saved for the entire city deployment. The model also enables the vehicle owners to participate in vehicular networking during the time length of their choices.Figure 23
Jitter (ns).Figure 24
Delay (Secs).Interestingly, travel matrix-based delta deployment requires fewer RSUs (10) than the intersection-based deployment that places 13 RSUs. If we assume the installation of DSRC-RSUs mentioned in [6], keeping other features, such as grid cell accessibility complexity constant and delta deployment, could need a budget of USD 41,500 in our case of study. While intersection-based deployment would need a larger budget of USD 53,950, road segmentation will require 74,700. The delta-deployment strategy is less expensive, but, at the same time, it outperforms other methods in terms of communication effectiveness, as presented above. In conclusion, based on our typical traffic volumes and case study area, the delta-placement scheme becomes cost-effective and is more efficient in terms of operation. From the analysis of the results, we realize that connecting only a number of vehicles that wish to be involved in the communication for some specific duration will ensure good communication from the case study area. The results from this study demonstrate that the travel matrix supported that delta-based roadside deployment from the case study could yield a fewer number of the required infrastructure and still ensure good communication compared to other methods presented in this research work. The study could support policymakers, such as urban transport officials and communication infrastructure planners.


## 5. Conclusion

In this article, optimal deployment of RSUs and network performance analysis study is presented based on a travel matrix strategy that connects a specific number of vehicular entities in the identified POIs, road segmentation, and intersection-based deployment plus V2V communication. The research work further introduces a baseline procedural algorithm that guides the RSUs deployment process. CPLEX-solver is employed to optimally determine the best geographical positions for RSUs deployment where the optimal number of RSUs is obtained through integer linear programming (ILP) formulation. The network effectiveness of three communication forms with different traffic volumes is evaluated here and compared with infrastructure-free vehicular communication. Interestingly, all the results using all the different traffic volumes showed that the delta method outperforms the rest requiring fewer RSUs. As future work, we would like to carry out a study that encompasses cost-effective intelligent RSUs for monitoring intravehicular contexts, driver and passengers behaviors, driving patterns, and other related vehicular contextual information using the intelligent RSUs. From the results discussion, we observe that travel matrix delta-based RSUs placement mechanism is the suitable RSUs deployment method in the case study area.



---

*Source: 2809184-2022-03-12.xml*