Done-self study
AboRedha
RoadSideUnitDeploymentDensitybased.pdf
IEEE IntEllIgEnt transportatIon systEms magazInE • 30 • FALL 2013
1939-1390/13/$31.00©2013IEEE
map—© wikimedia commons, button—istockphoto.com/oleg_b
Javier Barrachina, Piedad Garrido, Manuel Fogue, and Francisco J. Martinez University of Zaragoza, Spain E-mails: {barrachina, piedad, m.fogue, f.martinez} @unizar.es
Juan-Carlos Cano, Carlos T. Calafate, and Pietro Manzoni Universitat Politècnica de València, Spain E-mails: {jucano, calafate, pmanzoni}@disca.upv.es
Road Side Unit Deployment: A Density-Based Approach
Digital Object Identifier 10.1109/MITS.2013.2253159
Abstract—Currently, the number of vehicles increases every year, raising the probability of having acci- dents. When an accident occurs, wireless technologies enable vehicles to share warning messages with other vehicles by using vehicle to vehicle (V2V) communications, and with the emergency services by using vehicle to infrastructure (V2I) communications. Regarding vehicle to infrastructure communications, Road Side Units (RSUs) act similarly to wireless LAN access points, and can provide communications with the infrastructure. Since RSUs are usually very expensive to install, authorities limit their number, especially in suburbs and areas of sparse population, making RSUs a precious resource in vehicular environments. In this paper, we propose a Density-based Road Side Unit deployment policy (D-RSU), specially designed to obtain an efficient system with the lowest possible cost to alert emergency services in case of an accident. Our approach is based on deploying RSUs using an inverse proportion to the expected density of vehicles. The obtained results show how D-RSU is
able to reduce the required number of RSUs, as well as the accident notification time.
Date of publication: 23 July 2013
IEEE IntEllIgEnt transportatIon systEms magazInE • 30 • FALL 2013 IEEE IntEllIgEnt transportatIon systEms magazInE • 31 • FALL 2013
I. Introduction
N owadays, mobility requirements make transporta- tion systems a fundamental and relevant aspect of our lives. Hence, transportation infrastructure invest- ments represent a considerable fraction of the total
Governments investments around the globe. Moreover, the emergence of modern Intelligent Transportation Systems (ITS) based on vehicular networks, which add wire- less communication capabilities to the current vehicles, requires the deployment of efficient roadside communica- tion infrastructures. These infrastructure assets require a high deployment costs, and they are generally funded and managed by national governments.
In addition, the number of vehicles on the roads dras- tically increases every year, and traffic accidents repre- sent a serious drama in our society. Therefore, safety also
acquires a special relevance when accounting for transportation systems [12]. Governments increasingly are establishing restrictive regulations to
improve safety on roads, so that current roads are designed to be safer. Moreover, the automotive industry adds new safety elements inside vehicles, (e.g. air bags, stability control systems, antilock brake systems, etc.). However, the number of
accidents still increases every year all over the world, being the number of fatalities also higher.
A close look at the accidents shows that many of the deaths occurred during the time between the accident and the arrival of medi-
cal assistance. The so called golden hour after a car crash is the time within which medical or surgical intervention by a specialized trauma team has the greatest chance of saving lives. If more than 60 minutes have elapsed by the time the patient arrives to the operating table, the chances
of survival fall sharply. Typical arrival of medical help takes about 15 minutes, but initial access and treatment only starts 25 minutes after the accident. Transportation of the injured to the hospital usually takes place only 50 minutes later. Therefore, time is critical to the survival of the injured in a severe inci-
dent. Hence, any technology capable of providing a fast and efficient rescue operation after a traffic accident will increase the probability of survival of the injured, and so reducing the injury severity.
Wireless technologies, through vehicular networks, enable peer-to-peer mobile communications among vehicles (V2V), as well as communications between vehicles and infrastructures (V2I) [14], which allow to avoid collisions among vehicles [15]. In addition, using these technologies, crashed vehicles are able to alert nearby vehicles, as well as to notify emergency services when an accident occurs.
The combination of V2V and V2I communications can propel our communication capabilities. Regarding traf- fic safety, by adding infrastructure to vehicular networks, two benefits are provided: (i) infrastructure can provide Internet access to vehicles, allowing them to communi- cate with the emergency services immediately, thereby reducing notification times in case of an accident, and (ii) infrastructure access points can rebroadcast messages delivered by vehicles in low vehicle density scenarios (allowing messages to arrive to more vehicles).
A Road Side Unit (RSU) is a communication node installed within the infrastructure. Therefore, the capac- ity of vehicles to communicate with an infrastructure depends on the number and radio coverage of existing
IEEE IntEllIgEnt transportatIon systEms magazInE • 32 • FALL 2013
RSUs in the nearby area. However, Roadside Units are usu- ally very expensive to install. Hence, authorities tend to limit their number, especially in suburbs and sparse popu- lation areas, making RSUs a precious resource in vehicular environments.
In this work, we propose a density-based approach for RSU deployment in urban scenarios and compare it with other alternative deployment policies to obtain an efficient system. Our aim is to reduce the deployment cost by mini- mizing the required number of RSUs, as well as to reduce the warning notification time (i.e., the time required to notify emergency services and other vehicles). Specifically, we tested these deployment policies by simulating a urban scenario where vehicles want to alert both the emergency services and the nearby vehicles.
This paper is organized as follows: Section II reviews the related work regarding vehicular networks using infra- structure. In Section III we present three different RSU deployment policies (i.e., Minimum Cost, Uniform Mesh, and D-RSU). Section IV introduces the simulation environ- ment to assess our D-RSU proposal. Section V shows the obtained results. Finally, Section VI concludes this paper.
II. Related Work Vehicular networks have been studied for several years but, although there are many studies regarding V2V communi- cations, only a few focused on V2I communications, too.
Regarding V2I communications, Wu et al. [17] proposed a novel mechanism, called Distributed Sorting Mechanism (DSM), to improve the efficiency of communication between vehicles and RSUs. In their work, every vehicle can individually calculate its own priority of communica- tion, in order to reduce the time required to compete and obtain the channel. Authors also consider that vehicles moving away from the coverage of communication can appropriately adjust their priorities. However, the specific deployment strategy of the RSUs in a specific area is an
issue than remains untackled, and only the communica- tion process towards a single RSU is addressed.
Mershad et al. [13] studied how to exploit RSUs to route data packets between any source and destination in vehicu- lar networks, developing an approach called Roadside Units as Message Routers in VANETs (ROAMER). They evaluated the RSU backbone routing performance via simulation, and compared their scheme to existing solutions, proving the feasibility and efficiency of their scheme in terms of query delay, packet delivery ratio, and overall traffic overhead. Nonetheless, in this work RSUs are deployed using a fixed infrastructure density depending on the coverage area, without exploiting road layout or vehicle density.
Fogue et al. [5] presented eNOTIFY, a novel proposal based on the combination of V2V and V2I communica- tion capabilities, designed to improve the responsiveness of emergency services by reducing the required time to rescue the passengers involved in a car accident, and automatically managing and optimizing the medical and rescue needed resources.
Furthermore, other authors studied how to place RSUs. Lochert et al. [9] proposed a genetic algorithm which was able to identify good positions for static RSUs in order to cope with the highly partitioned nature of a vehicular network in an early deployment stage for the city of Brunswick. They defended a tailored tool chain to optimize the placement with respect to an application-centric objective function. However, for all their simulations, they only used a reduced average equipment density of 0.25 equipped vehicles per radio range.
Kchiche and Kamoun [6] provided an analysis of the infra- structure deployment problem. Authors considered that the use of RSUs becomes essential for communications among vehicles in low density scenarios. They proved that centrality and equidistance are key factors for optimizing end-to-end delays and ensuring stable performances. However, their simulations were made using only a density of 200 vehicles in a total route-length of about 75 km. In addition, the potential RSU locations are determined by the user, and the proposed algorithm is only able to choose among the predefined posi- tions, i.e., it requires additional knowledge from the user for all the possible scenarios, which is not feasible.
Lee and Kim [8] proposed a roadside unit placement scheme for vehicular networks, aiming at improving con- nectivity and reducing the disconnection interval for the given number of roadside units, the transmission range, and the overlap ratio on the road network of Jeju island. Performance measurement results obtained using the real- life movement history data in Jeju city showed that about 72.5% of connectivity can be achieved when deploying 1,000 RSUs, being the transmission range 300 m, while the disconnection time is mostly kept below 10 seconds. The policy followed to deploy the RSUs is based on the minimi- zation of the overlapped coverage area, but the presence of
FIG 1 Example of 8 RSUs deployed following the minimum cost deployment policy.
IEEE IntEllIgEnt transportatIon systEms magazInE • 32 • FALL 2013 IEEE IntEllIgEnt transportatIon systEms magazInE • 33 • FALL 2013
obstacles and blind spots is not considered. Therefore, the results might not be valid for urban environments.
To the best of our knowledge, few proposals studied the RSU deployment problem, optimizing the placement of RSUs to maximize performance and reduce the deployment cost. Furthermore, these proposals have been tested in very simple scenarios with very specific traffic densities. Crucial factors such as the vehicle density, the presence of obstacles block- ing the radio signal, or non-uniform RSU placement have not been considered, reducing the utility of the obtained results.
III. RSUs Deployment Policies Roadside Units are usually expensive to install. Therefore, authorities limit their number, especially in suburbs and areas of sparse population, making RSUs a precious resource in vehicular environments. Moreover, given the current economic situation, authorities and transport agencies tend to reduce the infrastructure investments related to transportation systems.
Therefore, the selected deployment policy is of utmost importance when adding infrastructure for vehicular net- works. Authorities could place RSUs in a homogeneous way (uniformly) trying to maximize the coverage area, or fol- lowing a non uniform deployment approach (e.g., group- ing RSUs in specific parts of an area) trying to reduce the deployment cost.
Similarly to the traffic lights or the traffic luminous panels, before deploying RSUs, authorities should make a preliminary study which involves gathering important data (regarding the economic impact, or the number of potential users) to decide where and how to deploy the infrastructure stations. We consider that Governments should also pay particular attention to accounting for the expected density of vehicles in order to optimize the infra- structure deployments, thereby reducing the economic cost, without reducing the time required by vehicles to get access to RSUs in case of emergency.
In the following Subsections we present in detail three different RSUs deployment policies: (i) the Minimum Cost, (ii) the Uniform Mesh, and (iii) the Downtown-based (D-RSU).
A. Minimum Cost Deployment Policy In the Minimum Cost deployment policy, we consider that authorities only account for reducing the economic cost of the infrastructure deployment, without considering whether RSUs will be placed to maximize the coverage area, or not. This policy consists on distributing RSUs with the minimum possible cost. In real environments, this policy would place RSUs in locations that already have Internet access, or where their installation is easy, regardless of their position in the map. Figure 1 shows an example of this deployment policy.
The total cost of this policy is the lowest, since authori- ties can place RSUs in sites where there are already
Internet access (e.g., nearby government buildings, traf- fic luminous panels, etc.). However, this deployment pol- icy can provoke that some areas remain isolated, without infrastructure coverage.
B. Uniform Mesh Deployment Policy The Uniform Mesh deployment policy consists on distribut- ing RSUs uniformly on the map, regardless of the expected average traffic density, or the roadmap topology.
The advantage of this deployment policy is that it achieves a more uniform coverage area since the distance between RSUs is basically the same, preventing RSUs to be positioned too closely, or too sparsely. An example of this deployment policy is shown in Figure 2.
The Uniform Mesh policy tends to reduce the probabil- ity of having shadow areas in the map, where vehicles can remain isolated (without the possibility of alerting emer- gency services in case of an accident).
This deployment policy has a higher cost than the pre- vious one, because authorities have to provide Internet access in all the places where the RSUs are positioned.
FIG 2 Example of 8 RSUs deployed following the uniform mesh deployment policy.
FIG 3 Example of 8 RSUs deployed following the D-RSU deployment policy.
IEEE IntEllIgEnt transportatIon systEms magazInE • 34 • FALL 2013
C. D-RSU Deployment Policy In vehicular scenarios, traffic is not uniformly distributed; there are zones that usually have a higher vehicle density. For example, in the cities, these zones are usually located in the downtown area, business areas, or industrial areas, where the higher density of vehicles makes them move more slowly than in the outskirts, but it also increases the number of potential nodes of a vehicular network based on V2V communications.
In the D-RSU deployment polity, RSUs are placed using an inverse proportion to the expected density (i.e., more resources must be deployed in areas where less number of vehicles are usually expected, and authorities must deploy less RSUs in areas which are characterized by a high den- sity of vehicles). For example, if authorities have in mind to deploy a total number of 100 RSUs in a city, and they consider that the expected traffic density in an specific area of this city is about 60% of the vehicles, according to the D-RSU deploy- ment policy, they should install 40% of RSUs there, and the rest of the RSUs should be deployed in the rest of the area.
This deployment policy allows vehicles located in less dense areas to have a better Internet access capabilities thanks to the higher density of deployed RSUs. In contrast, we consider that areas which support a high density of vehicles do not require a high number of RSU, since V2V communications can complement the infrastructure (i.e., high reliable V2V scenarios do not require a great infra- structure without reducing performance). Figure 3 shows an example of this deployment policy.
Similar to the Uniform Mesh deployment policy, D-RSU has a higher economical cost than the Minimum Cost deployment policy, since authorities need to provide Internet access in all the places where the RSUs are positioned.
IV. Simulation Environment Simulations were done using the ns-2 simulator, where the PHY and MAC layers have been modified to follow the IEEE 802.11p standard, which defines enhancements to the 802.11 required to support Intelligent Transportation System (ITS) applications. We assume that all the nodes of our network have two different interfaces: (i) an IEEE 802.11n interface tuned at the frequency of 2.4 GHz for V2I communications, and (ii) an IEEE 802.11p interface tuned at the frequency of 5 GHz for V2V communications. This assumption is reasonable due to the low price of this type of devices with respect to the total price of a vehicle.
In our simulations, vehicles can operate in two different modes: (a) warning, and (b) normal. Vehicles in warning mode inform other vehicles about their status by sending warning messages periodically (every second). These mes- sages have the highest priority at the MAC layer. Normal mode vehicles enable the diffusion of these warning pack- ets and, every second they also send beacons with infor- mation such as their positions, speed, etc. These periodic messages have lower priority than warning messages and are not propagated by other vehicles. As for the RSUs, they mainly provide Internet access to vehicles, but they also enable the diffusion of the warning messages.
To increase the realism of our simulations, we use CityMob for Roadmaps (C4R)1 [2], a mobility generator based on SUMO. C4R includes all the original characteris- tics from SUMO (collision-free vehicle movements, multi- lane streets, etc.). In addition, it is able to define attraction and repulsion points which simulate areas with different vehicle densities in real cities [10].
Our simulations use a scenario of km ,4 2 obtained from the city of Madrid (Spain). We selected this scenario based on the results obtained after evaluating several maps from different parts of the world [3], achieving a classification of road topologies depending on their street and junction densities. The city of Madrid presents a rep- resentative road layout, close to the average values found
1C4R is available at http://www.grc.upv.es/software/.
Selected city map Madrid (Spain)
Total streets 1387
Total junctions 715
Average street length 83.08 m
Average lanes/street 1.27
Table 1. Main features of the selected map.
FIG 4 Fragment of the city of Madrid (Spain) used in our simulations.
IEEE IntEllIgEnt transportatIon systEms magazInE • 34 • FALL 2013 IEEE IntEllIgEnt transportatIon systEms magazInE • 35 • FALL 2013
in our classification, and thus it is a good example of a typical metropolitan area. Figure 4 shows the topology of the map, and Table 1 includes the main features of the selected city.
Since our proposal is focused on the use of an infrastruc- ture to notify emergency services when an accident occurs, the warning messages exchanged between vehicles and RSUs are built according the Vehicular Accident Ontology (VEACON) [1], specially designed for sharing and reusing knowledge about the vehicles involved in road accidents. We simulated several front impact scenarios with two cars involved. The first vehicle is a family car with two occu- pants, and expressing all the information required pro- duces a message of 13 KBytes. The second car is a minivan with eight occupants, which required up to 18 KBytes to code the data for all passengers. Each simulation run lasted for 300 seconds. All results represent an average of 20 exe- cutions with different scenarios (maximum error of 10% with a degree of confidence of 90%). Table 2 shows the parameters used in the performed simulations.
V. Simulations Results In this section, we first study the required number of RSUs per square kilometer to have a feasible warning notifica- tion system, where crashed vehicles can properly alert
the emergency services, as soon as possible. Then, we also show the impact of the RSUs deployment policy in the obtained results when varying the number of RSUs, and the density of vehicles in the scenario. Our aim is to deter- mine which policy fits better in the studied conditions.
In our simulations, we measure notification times (the minimum, the maximum, and the average time that a warning message requires to reach an RSU), and the per- centage of accidents that have been successfully notified (i.e., that have already reached an RSU, thereby consider- ing that emergency services have been correctly notified).
Parameter Value
Density of vehicles (veh./ km2 ) 25, 50, 75, 100, 125, and 150
Number of RSUs 1, 2, 4, 8, and 16
Simulated city Madrid
Simulated area 2000 m # 2000 m
Number of crashed vehicles 2
Downtown size 1000 m # 1000 m
Downtown probability 0.7
Warning message size 13 and 18 KB
Packets sent by vehicles 1 per second
Warning message priority AC3
Normal message priority AC1
Mobility generator C4R [2]
Mobility models Krauss [7] and downtown [10]
MAC/PHY 802.11p
Radio propagation model RAV [11]
Maximum transmission range 400 m
Broadcast storm reduction scheme eMDR [4]
Table 2. Parameter values for the simulations.
Vehicles/ km2 RSUs
Min. Notif. Time (s)
Max. Notif. Time (s)
Avg. Notif. Time (s)
Accident Notif. (%)
25
1 0.476 31.003 13.974 75
2 0.563 30.422 12.389 85
4 0.676 26.701 9.650 85
8 0.273 11.257 3.222 95
16 0.230 15.753 2.935 100
50
1 0.827 33.125 9.937 100
2 0.476 33.919 8.209 100
4 0.363 12.958 3.471 100
8 0.125 10.949 2.640 100
16 0.333 21.281 1.922 100
75
1 0.777 9.546 4.683 100
2 0.543 13.053 4.453 100
4 0.852 6.782 3.000 100
8 0.272 10.111 1.931 100
16 0.241 10.460 1.328 100
100
1 0.999 11.594 3.551 100
2 0.564 11.833 2.983 100
4 0.550 11.604 3.078 100
8 0.265 1.762 1.081 100
16 0.295 1.712 0.946 100
125
1 0.598 9.277 3.503 100
2 0.567 7.489 2.984 100
4 0.273 7.478 2.793 100
8 0.360 6.112 1.581 100
16 0.272 5.751 1.433 100
Table 3. Simulation results for the uniform mesh deployment policy when varying the density of vehicles and RSUs.
IEEE IntEllIgEnt transportatIon systEms magazInE • 36 • FALL 2013
A. Study of Required Number of RSUs Table 3 shows the obtained results for the Uniform Mesh deployment policy when varying the number of RSUs deployed (1, 2, 4, 8, and 16), and the density of vehicles (25, 50, 75, 100, and 125) in the selected scenario.
As shown, when the density becomes very small (i.e., vehicles/km ,25 2 which is clearly infrequent in urban sce-
narios), and there are eight or less RSUs (two or less RSUs per square kilometer), about 5–25% of the total accidents are not correctly notified to the emergency services (i.e., no warn- ing message effectively reaches an RSU). However, when increasing the density of vehicles vehicles/km ,50 2$^ h all the accidents are correctly notified, making it possible
to provide precise information about the incident to reduce the response time of emergency services, thereby improv- ing the assistance to people injured.
Regarding the average notification time, it ranges from 0.946 seconds vehicles/km100 2^ and 16 RSUs) to 13.974 seconds vehicles/km25 2^ and 1 RSU). As expected, the system requires less time to reach an RSU when increasing the number of RSUs, although we observe that in high density situations vehicles/km ,25 2^ h specifically when 8 and 16 RSUs are deployed, the system requires more time to reach an RSU than in scenarios where vehicles/km100 2 are simulated. This could be explained due to redundancy, contention, and packet
Minimum Cost
Uniform Mesh
D-RSU
Vehicular Density (veh./km2) 25
0.0
A ve
ra g e N
o tif
ic a tio
n T
im e (
s)
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
50 75 100 125 150
FIG 5 Comparison of the average notification time for the studied deployment policies when using 8 RSUs.
Minimum Cost
Uniform Mesh
D-RSU
Vehicular Density (veh./km2) 25
0.0
A ve
ra g e N
o tif
ic a tio
n T
im e (
s)
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
50 75 100 125 150
FIG 6 Comparison of the average notification time for the studied deployment policies when using 16 RSUs.
Vehicles/ km2 25 50 75 100 125 150
RSUs 8 16 8 16 8 16 8 16 8 16 8 16
Minimum cost
Min. notif. time (s) 0.394 0.293 0.228 0.211 0.460 0.520 0.308 0.456 0.390 0.360 0.306 0.356
Max. notif. time (s) 11.366 11.238 21.479 21.155 6.150 6.093 2.917 3.449 6.111 6.628 5.717 4.116
Avg. notif. time (s) 3.417 3.333 3.816 3.468 2.234 1.590 1.359 1.248 1.543 1.501 1.672 1.421
Accident notif. (%) 95 95 100 100 100 100 100 100 100 100 100 100
Uniform mesh
Min. notif. time (s) 0.273 0.230 0.125 0.333 0.272 0.241 0.265 0.295 0.360 0.272 0.302 0.228
Max. notif. time (s) 11.257 15.753 10.949 21.281 10.111 10.460 1.762 1.712 6.112 5.751 6.207 3.736
Avg. notif. time (s) 3.222 2.935 2.640 1.922 1.931 1.328 1.081 0.946 1.581 1.433 1.551 1.227
Accident notif. (%) 95 100 100 100 100 100 100 100 100 100 100 100
D-RSU Min. notif. time (s) 0.234 0.268 0.238 0.197 0.400 0.471 0.480 0.372 0.381 0.190 0.385 0.251
Max. notif. time (s) 11.161 11.040 17.400 20.516 6.282 6.263 1.832 2.061 1.723 1.800 3.459 3.339
Avg. notif. time (s) 3.268 3.333 3.491 3.071 1.609 1.091 0.783 0.771 0.720 0.688 1.145 1.100
Accident notif. (%) 95 95 100 100 100 100 100 100 100 100 100 100
Table 4. Simulation results for the three different deployment policies when varying the density of vehicles and RSUs.
IEEE IntEllIgEnt transportatIon systEms magazInE • 36 • FALL 2013 IEEE IntEllIgEnt transportatIon systEms magazInE • 37 • FALL 2013
collisions caused by simultaneous forwarding (usually known as the broadcast storm problem [16]).
Since we are interested in safety issues, it is extremely important to be sure that all the accidents will be correctly notified to the emergency services. Hence, according to the obtained results, we consider that authorities must deploy at least four RSUs per square kilometer (16 RSUs in our example).
B. Performance of the Different RSUs Deployment Policies Table 4 shows the obtained results for the studied deploy- ment policies, when varying the density of vehicles (25, 50, 75, 100, 125 and 150), and the number of RSUs deployed (8 and 16) in the studied scenario. For each deployment policy, we show the minimum, the maximum, and the aver- age notification times (i.e., the time required for a warning message to reach an RSU), as well as the percentage of suc- cessfully accident notifications via the infrastructure.
As shown in Table 4, the warning notification system works well in all the different scenarios, since all the acci- dents are correctly notified to the emergency services (i.e.,
at least a warning message reaches an RSU). Only when the density becomes very small vehicles/km ,25 2^ h some acci- dents (only 5% of the amount total) are not reported to the emergency services.
Regarding the average notification time, Figures 5 and 6 graphically depict that, in small density scenarios
vehicles/km ,50 2#^ h the Uniform Mesh deployment pol- icy yields better results than the other policies. When simulating 16 RSUs, it reduces the average notification time compared to the Minimum Cost and the D-RSU (up to 44.58% and 37.41%, respectively). The Uniform Mesh policy works better in small densities, since RSUs are uniformly deployed in the map, increasing the probabil- ity that isolated vehicles have a nearby RSU. However, in
Uniform Mesh (16 RSUs) D-RSU (8 RSUs)
Vehicular Density (veh./km2) 25
0.0
A ve
ra g e N
o tif
ic a tio
n T
im e (
s)
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
50 75 100 125 150
FIG 7 Comparison between the uniform mesh using 16 RSUs and D-RSU using 8 RSUs.
Uniform Mesh (16 RSUs) D-RSU (16 RSUs)
Trade-Off Point
Uniform Mesh (16 RSUs) D-RSU (8 RSUs)
Trade-Off Point
25 0
0.5
1
1.5
2
2.5
3
3.5
4
50 75 100 125
A ve
ra g e N
o tif
ic a tio
n T
im e (
s)
Vehicular Density (veh./km2)
(a)
25 0
0.5
1
1.5
2
2.5
3
3.5
4
50 75 100 125
A ve
ra g e N
o tif
ic a tio
n T
im e (
s)
Vehicular Density (veh./km2)
(b)
FIG 8 Best deployment policy when the vehicular density is greater or equal than: (a) 70 vehicles per km ,2 and (b) 90 vehicles per km .2
INPUT: vehicleDensity : density of vehicles in the selected area map: road topology of the selected area downtownCoordinates: coordinates (latitude, longitude) of the
subareas with high vehicle density downtownPercentage: percentage of vehicles present in each
downtown area OUTPUT: numRSU: number of RSUs to be deployed in the selected
map area
numRSU = 4 * areaKm2 (map); // 4 RSUs/Km2 if (vehicleDensity is < 70 vehicles/Km2 ) then use UniformMesh(map, numRSU); else if (vehicleDensity is < 90 vehicles/Km2 ) then use D-RSU(map, numRSU, downtownCoordinates,
downtownPercentage); else numRSU = numRSU / 2; use D-RSU(map, numRSU, downtownCoordinates,
downtownPercentage);
Algorithm 1. Pseudocode of the RSU Deployment Algorithm.
IEEE IntEllIgEnt transportatIon systEms magazInE • 38 • FALL 2013
higher density scenarios vehicles/km ,75 2$^ h our D-RSU deployment policy yields better performance results, since it requires less time to inform emergency services when an accident occurs. It reduces the average notification time up to 54.16% and 51.99%, compared to the Minimum Cost and to the Uniform Mesh, respectively.
These results suggest us that using the Minimum Cost approach is not a good idea, since accidents must be cor- rectly notified in the minimum possible time.
Finally, Figure 7 shows a comparison between the D-RSU with only 8 RSUs, and the Uniform Mesh with 16 RSUs. As shown, in high density scenarios (when more than 100 vehi- cles per km2 are simulated), D-RSU achieves better notifica- tion times even if half of RSUs have been deployed. This shows that using D-RSU allows to severely reduce the overall cost of deploying the infrastructure, without losing performance.
C. Our Proposed Deployment Algorithm Figure 8 shows the average notification time for differ- ent vehicular densities when using our D-RSU and the Uniform Mesh deployment policies. We highlighted the trade-off point which remarks the specific densities when the D-RSU outperforms the Uniform Mesh policy.
As shown in Figure 8a, in scenarios where vehicle density is lower than 70 vehicles per km ,2 the Uniform Mesh deploy- ment policy yields the best performance. Instead, if density is higher than 70 vehicles per km ,2 the D-RSU deployment pol- icy is the best approach. In addition, if traffic density exceeds 90 vehicles per km ,2 the D-RSU deployment policy is also the best approach, even when reducing the number of required RSUs to a half (see Figure 8b). Based on these results, we pro- pose the RSU deployment algorithm showed in Algorithm 1.
VI. Conclusions In this paper we present D-RSU, a density-based approach for Road Side Unit deployment in urban scenarios. D-RSU takes into account that the density of vehicles is not uniformly distributed in vehicular scenarios. D-RSU consists on plac- ing RSUs according an inverse proportion to the expected density. This distribution allows that vehicles driving in less dense areas have better Internet access by increasing the number of nearby available RSUs, whereas in areas with high density of vehicles, V2V communications can comple- ment the infrastructure to provide a reliable warning notifi- cation system without reducing its performance.
To assess our proposal, we compare D-RSU with two other deployment policies: the Minimum Cost, and the Uniform Mesh. Simulations show that the Uniform Mesh deployment policy is more adequate for areas in which less than 70 vehicles per km2 are expected. However, when the traffic density expected is greater or equal to 70 vehicles per km ,2 D-RSU is the best deployment policy. In addition, if there are more than 90 vehicles per km ,2 D-RSU obtains better results than the other approaches in terms of warning
notification time, while reducing the required number of RSUs to half.
According to the obtained results, we propose an RSU deployment algorithm which decides the optimum deployment policy based on the expected vehicle density. Since the density of vehicles is a time-varying factor, in the future we plan to make our approach adaptive, i.e., we will propose an adaptive RSU deployment algorithm capable of enabling or disabling the RSUs based on the density detected at that moment.
Acknowledgments This work was partially supported by the Ministerio de Educación y Ciencia, Spain, under Grant TIN2011- 27543-C03-01, as well as by the Fundación Universitaria Antonio Gargallo (FUAG), and the Caja de Ahorros de la Inmaculada (CAI).
About the Authors Javier Barrachina received his B.Sc. degree in Computer Science from the University of Zaragoza in 2011. Currently, he is an M.Sc. student from the National Distance University of Spain (UNED), and a Ph.D. candi- date in the Intelligent Networks and
Information Technologies (iNiT) research group. His research interests include VANET simulation, Intelligent Transportation Systems, virtual agents, ontologies, traffic safety, vehicle-to-vehicle (V2V), and vehicle-to-infrastruc- ture (V2I) communications.
Piedad Garrido graduated in Com- puter Science and Documentation at the Technical University of Valencia in 1997 and 1999, respectively. She received her Ph.D. degree in Documentation from the University Carlos III of Madrid in 2008. She is an assistant professor in
the Department of Computers and Systems Engineering at the University of Zaragoza in Spain. Her current research interests include Intelligent Transportation Systems, virtual agents, ontologies, traffic safety, vehicle-to-vehicle (V2V), and vehicle-to-infrastructure (V2I) communications.
Manuel Fogue received his B.Sc. and M.Sc. degrees in Computer Science from the University of Zaragoza in 2007 and the University Jaume I of Castellon in 2009, respectively. In both cases, he graduated with honors. He received his Ph.D. degree in Computer Engineering
from the University Zaragoza in 2012. He is a member of the Intelligent Networks and Information Technologies (iNiT) research group. His research interests include
IEEE IntEllIgEnt transportatIon systEms magazInE • 38 • FALL 2013 IEEE IntEllIgEnt transportatIon systEms magazInE • 39 • FALL 2013
VANET simulation, Intelligent Transportation Systems, traffic safety, vehicle-to-vehicle (V2V), and vehicle-to- infrastructure (V2I) communications.
Francisco J. Martinez graduated in Computer Science and Documentation at the Technical University of Valencia in 1996 and 1999, respectively. He received his Ph.D. degree in Computer Engineering from the Technical University of Valencia in 2010, and
received an Extraordinary Doctorate Award. He is an asso- ciate professor in the Department of Computers and Systems Engineering at the University of Zaragoza in Spain. He is the leader of the Intelligent Networks and Information Technologies (iNiT) research group. His current research interests include VANET simulation, Intelligent Transportation Systems, traffic safety, vehicle-to-vehicle (V2V), and vehicle-to-infrastructure (V2I) communications. He is member of the IEEE.
Juan-Carlos Cano received his M.Sc. and a Ph.D. in computer science from the Technical University of Valencia (UPV) in 1994 and 2002, respectively. From 1995 to 1997 he worked as a pro- gramming analyst at IBM’s manufac- turing division in Valencia. He is a full
professor and the Head of the Department of Computer Engineering at the UPV in Spain. His current research inter- ests include power aware routing protocols, quality of ser- vice for mobile ad hoc networks, and pervasive computing.
Carlos T. Calafate graduated with honors in Electrical and Computer Engineering at the University of Oporto (Portugal) in 2001. He received his Ph.D. degree in Computer Engineering from the Technical University of Valencia (UPV) in 2006, where he has worked
since 2005. He is an associate professor in the Department of Computer Engineering at the UPV in Spain. He is a mem- ber of the Computer Networks research group (GRC). His research interests include mobile and pervasive computing, security and QoS on wireless networks, as well as video cod- ing and streaming.
Pietro Manzoni received his MS degree in computer science from the “Universitá degli Studi” of Milan, Italy, in 1989, and the Ph.D. degree in com- puter science from the Polytechnic University of Milan, Italy, in 1995. He is a full professor in the Department
of Computer Engineering at the Technical University of Valencia (UPV) in Spain. His research activity is related to wireless networks protocol design, modeling, and imple- mentation. He is member of the IEEE.
References [1] J. Barrachina, P. Garrido, M. Fogue, F. J. Martinez, J.-C. Cano, C. T. Calafate, and P. Manzoni. (2012). VEACON: A vehicular accident ontol- ogy designed to improve safety on the roads. J. Netw. Comput. Applicat. [Online]. 359(6), pp. 1891–1900. Available: http://dx.doi.org/10.1016/j. jnca.2012.07.013 [2] M. Fogue, P. Garrido, F. J. Martinez, J.-C. Cano, C. T. Calafate, and P. Manzoni. (2012, Mar.). A realistic simulation framework for vehicular networks. presented at 5th Int. ICST Conf. Simulation Tools Techniques (SIMUTools 2012). Desenzano, Italy, pp. 37– 46. [Online]. Available: http:// dx.doi.org/10.4108/icst.simutools.2012.247682 [3] M. Fogue, P. Garrido, F. J. Martinez, J.-C. Cano, C. T. Calafate, and P. Manzoni. (2012). An adaptive system based on roadmap profil- ing to enhance warning message dissemination in vanets. IEEE/ACM Trans. Netw. [Online]. PP(99), p. 1. Available: http://dx.doi.org/10.1109/ TNET.2012.2212206 [4] M. Fogue, P. Garrido, F. J. Martinez, J.-C. Cano, C. T. Calafate, and P. Manzoni. (2012, Dec.). Evaluating the impact of a novel message dis- semination scheme for vehicular networks using real maps. Transp. Res. Part C: Emerging Technol. [Online]. 25, pp. 61–80. Available: http://dx.doi. org/10.1016/j.trc.2012.04.017 [5] M. Fogue, P. Garrido, F. J. Martinez, J.-C. Cano, C. T. Calafate, P. Man- zoni, and M. Sanchez, “Prototyping an automatic notification scheme for traffic accidents in vehicular networks,” in Proc. IFIP Wireless Days, Oct. 2011, pp. 1–5. [6] A. Kchiche and F. Kamoun, “Centrality-based access-points deployment for vehicular networks,” in Proc. IEEE 17th Int. Conf. Telecommunications, Apr. 2010, pp. 700 –706. [7] D. Krajzewicz, G. Hertkorn, C. Rossel, and P. Wagner, “SUMO (Simula- tion of Urban MObility)—An open-source traffic simulation,” in Proc. 4th Middle East Symp. Simulation Modelling, Sharjah, United Arab Emirates, Sept. 2002, pp. 183–187. [8] J. Lee and C. Kim, “A roadside unit placement scheme for vehicular telematics networks,” in Advances in Computer Science and Information Technology (Lecture Notes in Computer Science), vol. 6059, T.-H. Kim and H. Adeli, Eds. Berlin, Germany: Springer-Verlag, 2010, pp. 196–202. [9] C. Lochert, B. Scheuermann, C. Wewetzer, A. Luebke, and M. Mauve, “Data aggregation and roadside unit placement for a VANET traffic infor- mation system,” in Proc. 5th ACM Int. VehiculAr Inter-NETworking, New York, 2008, pp. 58–65. [10] F. J. Martinez, J.-C. Cano, C. T. Calafate, and P. Manzoni. CityMob: A mobility model pattern generator for VANETs. presented at IEEE Vehicular Networks Applications Workshop (Vehi-Mobi, held with ICC). Beijing, Chi- na, May 2008, pp. 370 –374. [Online]. Available: http://dx.doi.org/10.1109/ ICCW.2008.76 [11] F. J. Martinez, M. Fogue, C. Toh, J.-C. Cano, C. T. Calafate, and P. Man- zoni. (2013). Computer simulations of VANETs using realistic city topolo- gies. Wireless Pers. Commun. J. [Online]. 69(2), pp. 639–663. Available: http://dx.doi.org/10.1007/s11277-012-0594-6 [12] F. J. Martinez, C. K. Toh, J.-C. Cano, C. T. Calafate, and P. Manzoni. (2010). Emergency services in future intelligent transportation sys- tems based on vehicular communication networks. IEEE Intell. Transp. Syst. Mag. [Online]. 2(2), pp. 6–20. Available: http://dx.doi.org/10.1109/ MITS.2010.938166 [13] K. Mershad, H. Artail, and M. Gerla, “ROAMER: Roadside Units as mes- sage routers in VANETs,” Ad Hoc Netw., vol. 10, no. 3, pp. 479– 496, 2012. [14] J. Santa, R. Toledo-Moreo, and A. F. Gomez-Skarmeta, “A novel vehicle communication paradigm based on cellular networks for improving the safety in roads,” in Proc. Int. J. Intelligent Information Database Systems, 2008, vol. 2, pp. 240 –257. [15] J. Santa, R. Toledo-Moreo, M. A. Zamora-Izquierdo, B. Ubeda, and A. F. Gomez-Skarmeta, “An analysis of communication and navigation issues in collision avoidance support systems,” in Transportation Research Part C. Emerging Technologies, vol. 18. Amsterdam, The Netherlands: Elsevier, 2010, pp. 351–366. [16] Y.-C. Tseng, S.-Y. Ni, Y.-S. Chen, and J.-P. Sheu, “The broadcast storm problem in a mobile ad hoc network,” Wireless Netw., vol. 8, no. 2, pp. 153– 167, 2002. [17] T.-Y. Wu, S. Guizani, W.-T. Lee, and K.-H. Liao, “Improving RSU service time by distributed sorting mechanism,” Ad Hoc Netw., vol. 10, no. 2, pp. 212–221, 2012.
