Towards Efficient Routing in Vehicular

Ad Hoc Networks
Moez Jerbi*, Sidi-Mohammed Senouci* and Yacine Ghamri-Doudane**
*France Telecom R&D, Core Network Laboratories, Lannion, France
**Networks and Multimedia Systems Research Group, ENSIIE, Evry, Cedex, France
Based on a localization system like the GPS (Global
Positioning System), our solution aims to efficiently relay data
Abstract— Multi-hop data delivery through Vehicular Ad- in the network considering the real time road traffic variation
hoc Networks is challenging since it must efficiently handle rapid and the characteristics of city environments. GyTAR assumes
topology changes and a fragmented network. This paper proposes then the existence of an accurate traffic-information system
a new intersection-based geographical routing protocol called
that it requires. To this end, we also propose in this work a
GyTAR (improved Greedy Traffic Aware Routing protocol) and
capable to find robust routes within city environments. GyTAR
completely decentralized mechanism for the estimation of
consists of two modules: (i) dynamic selection of the junctions traffic density in city-roads called IFTIS for Infrastructure-
through which a packet must pass to reach its destination, and (ii) Free Traffic Information System. Note that, although it has
an improved greedy strategy used to forward packets between been designed to operate with GyTAR, IFTIS is a completelty
two junctions. GyTAR assumes the existence of an accurate independent component which could be used for any other
traffic-information system that it requires to select paths with purpose requiring road density estimation. Indeed, IFTIS could
high connectivity. To address this issue, we also propose a be adopted, for instance, to be used in real-time traffic
completely decentralized mechanism for the estimation of traffic congestion warning systems, leveraging on the proposed
density in city-roads called IFTIS for Infrastructure-Free Traffic
distributed mechanism that provides updated traffic
Information System. The proposed routing protocol shows
significant performance improvement in a comparative simulation
information to drivers.
study with other routing approaches.
The rest of the paper is structured as follows. Section 2
Index Terms— Vehicular Ad hoc Network, Greedy Routing, presents existing approaches on routing in VANET and details
Vehicular Traffic Estimation, Performance Measurements the principles of GyTAR. Section 3 describes the mechanism
used in IFTIS to provide the information about vehicular
I. INTRODUCTION traffic between two junctions. Section 4 presents simulation
setting and results. Finally, conclusion and future work are
Inter-vehicle communication is a fast growing research summarized in Section 5.
topic in the academic sector and industry. Through this kind of
communication, vehicles are able to communicate with each II. IMPROVED GREEDY TRAFFIC AWARE ROUTING PROTOCOL
other by using wireless technology like WLAN. As a result,
they can be organized in vehicular ad hoc networks A. Routing in VANET
(VANETs). VANETs are an instantiation of mobile ad hoc Recently, some routing protocols specific to VANETs have
networks (MANETs). MANETs have no fixed infrastructure been proposed. In the following, we present the most
and instead rely on ordinary nodes to perform routing of important ones: GSR, A-STAR, and GPCR.
messages and network management functions. However, 'GSR' [1] (Geographic Source Routing) has been recently
vehicular ad hoc networks behave in different ways than proposed as a promising routing strategy for vehicular ad hoc
conventional MANETs. Driver behavior, mobility constraints, networks in city environments. It combines position-based
and high speeds create unique characteristics of VANETs. routing with topological knowledge. The simulation results,
These characteristics have important implications for with the use of realistic vehicular traffic in city environments,
designing decisions in these networks. Thus, numerous show that GSR outperforms topology-based approaches (DSR
research challenges need to be addressed for inter-vehicule and AODV) with respect to delivery rate and latency. In
communications to be widely deployed. For example, routing another study [2], the same authors have shown, for highway
in conventional mobile ad hoc networks is a challenging task scenarios, that routing approaches using position information,
because of the network's dynamic topology changes. e.g., obtained from on-board GPS receivers, can very well deal
Numerous studies and proposals of routing protocols have with the mobility of the vehicles.
been conducted to relay data in such a context; however these 'A-STAR'[3] (Anchor-based Street and Traffic Aware
solutions can not be applied to the vehicular environment due Routing) is a position-based routing scheme designed
to the specific constraints and characteristics of VANETs. specifically for IVC in city environments. It features the novel
In this work, we present a novel geographical routing use of city bus route information to identify anchor paths of
protocol for vehicular networks in city environments called higher connectivity so that more packets can be delivered to
GyTAR: improved Greedy Traffic Aware Routing protocol.
their destinations successfully. A new recovery strategy for junction considering the traffic density and the curvemetric4
packets routed to a local optimum1 was also proposed, distance to the destination. The best destination junction (the
consisting of the computation of a new anchor path from the junction with the highest score) is the geographically closest
local maximum to which the packet is routed. junction to the destination vehicle having the highest vehicular
The Greedy Perimeter Coordinator Routing (GPCR) traffic. To formally define this score, we need the following
protocol [4] has been designed to deal with the challenges of notations:
city scenarios. It does not require any global or external - J: the next candidate junction.
information such as a static street map. The main idea of - I: the current junction
GPCR is to forward data packets using a restricted greedy - Dj: the curvemetric distance from the candidate
forwarding procedure. That means when choosing the next junction J to the destination.
hop, a coordinator node (a node on a junction) is preferred to a - Di: the curvemetric distance from the current junction
non-coordinator node, even if it is not the closest node to to the destination.
destination. - Dp = Dj/Di (Dp determines the closeness of the
In summary, existing data delivery schemes use a candidate junction to the destination point)
position-based routing strategy, which scales better in a highly - Between junction I and junction J:
dynamic and fragmented network as VANET. In addition,
Nv : total number of vehicles between I and J,
most of the current routing proposals are spatial aware since
Nc : number of cells5 between I and J,
spatial information such us streets map of a city is utilized to
Navg: average number of vehicles per cell (Navg =
assist in making routing decisions. Nv/Nc),
In the following sub-sections, we give detailed description
Ncon: constant which represents the ideal
of our approach and present its added value compared to other connectivity degree we can have within a cell.
existing vehicular routing protocols. - α, β: used as weighting factors for the distance and
B. GyTAR Assumptions vehicular traffic respectively (with α + β = 1).
Hence, score (J) = α × [ 1 - Dp] + β × [ min (Navg/Ncon , 1) ]
GyTAR considers that each vehicle in the network knows
its own position thanks to the use of GPS2. Furthermore, a
sending node needs to know the current geographical position
of the destination in order to make the routing decision. This
information is assumed to be provided by a location service
like GLS (Grid Location Service) [7]. Moreover, we consider
that each vehicle can determine the position of its neighboring
junctions3 through pre-loaded digital maps, which provides a
street-level map. The presence of such kind of maps is a valid
assumption when vehicles are equipped with on-board
navigation system. We also assume that every vehicle is aware Figure 1. Selecting junctions in GyTAR.
of the vehicular traffic (number of vehicles between two Figure 1 shows an example of how the next junction is
junctions). This information can be provided by IFTIS: a selected on a street. Once vehicle A receives a packet, it
completely decentralized mechanism for the estimation of computes the score of each neighboring junction. Considering
traffic density in a road traffic network which will be described its curvemetric distance to the destination and the traffic
in section III. density, junction (2) will have the highest score. Then, it will
be chosen as the next anchor.
C. GyTAR Overview
GyTAR is a new intersection-based geographical routing 2) Forwarding data between two junctions
protocol capable to find robust routes within city Once the destination junction is determined, the improved
environments. It consists of two modules: greedy strategy is used to forward packets towards the selected
junctions. For that, all data packets are marked by the location
1) Junction selection of this junction. Each vehicle maintains a neighbor table in
In GyTAR, the different junctions the packet has to which, the position, velocity and direction of each neighbor
traverse in order to reach the destination are chosen vehicle are recorded. This table is updated through hello
dynamically and one by one, considering both vehicular traffic messages exchanged periodically by all vehicles. Thus, when a
variation and distance to destination: when selecting the next packet is received, the forwarding vehicle computes the new
destination junction, a node (the sending vehicle or an predicted position of each neighbor using the recorded
intermediate vehicle in a junction) looks for the position of the information (velocity, direction and the latest known position),
neighboring junctions using the map. A score is given to each and then selects the next hop neighbor (i.e. the closest to the
destination junction).
1
Situation where there is no neighbor of the forwarding node s, which is
4
closer to destination than s itself. This term describes the distance measured when following the geometric
2
The popularity of GPS on vehicles in today's world makes this shape of a road.
5
assumption acceptable. The cell is determined based on the wireless transmission range of
3
A place where two or more roads join or meet. vehicles.
 Figure 3 –Relaying Local Density Information between groups.

In the following sub-section, we introduce the distributed

mechanism for the estimation of road-traffic density.
B. Generating, Forwarding & Analysing CDP

Figure 2. Forwarding data between two junctions using improved greedy

1) What is a CDP?
strategy. The Cells' Density6 data Packet (CDP) provides the cell
density of a given road. As illustrated in Fig. 4, CDP also
This approach is illustrated in Figure 2, where vehicle (1), contains fields identifying the road ID, transmission time7, and
which is moving in the same direction as the forwarding the list of route anchors (position of cells center).
vehicle with a speed greater than vehicle (2), will receive the
forwarded packet since at time (t2), it is the closest to the next Cells Data Packet (CDP)
Road ID Time
junction. However, without using prediction, the forwarding Cell ID Cell 's Center (Position) Cell's Density
vehicle would choose vehicle (4) as the next hop instead of Figure 4 - CDP message format –
vehicle (1) since it was the closest to the destination junction at
2) Who generates the CDP?
time t1 (last time the neighbors table was updated).
The CDP is generated by vehicles which have already been
group leaders. In other words, only a vehicle which has already
3) Recovery strategy updated a CDP message will generate the new CDP. It only
Despite the improved greedy routing strategy, the risk does so when it reaches a road intersection (i.e. before leaving
remains that a packet gets stuck in a local optimum. Hence, a the road). This is to control the generation of CDP messages,
recovery strategy is required. The repair strategy of GyTAR is avoiding scalability issues. When initiating the CDP, such
based on the idea of "carry and forward": the forwarding vehicle records the road ID, the transmission time and a list of
vehicle of the packet in a recovery mode will carry the packet anchors through which the packet has to pass while traveling
until the next junction or until another vehicle, closer to the to the other intersection. Then, it sends it backward..
destination junction, enters/reaches its transmission range.
3) How the CDP is forwarded backward and who updates it?
III. INFRASTRUCTURE-FREE TRAFFIC INFORMATION SYSTEM The CDP header includes a limited list of anchors
IFTIS is a completely decentralized mechanism for the corresponding to the position of the cells’ centers. Then, the
estimation of traffic density in a road traffic network. This CDP is forwarded towards the first anchor on the basis of
decentralized approach revolves around the core idea of greedy forwarding (the forwarding vehicle selects among all
information relaying between groups of vehicles rather than its neighbors the closest vehicle to the next anchor). When it is
individual vehicles. More precisely, vehicles are arranged into reached, the group leader (closest vehicle to the cell center)
location-based groups. Local density information is then updates the CDP by including the density of the corresponding
relayed between groups using Cells' Density Packet (CDP). cell (the number of its neighbors which belong to the
corresponding road8) and then forwards it towards the next
A. Group Formation anchor, and so on. When the last anchor (the destination
Each road (section of street between two intersections) is intersection) is reached, the CDP is propagated to vehicles
dissected into small fixed area cells, each defining a group. which are around the intersection. The IFTIS algorithm is
Note that the cell size depends on the transmission range of illustrated in Fig 5.
vehicles (around 300m) and the cell ID depends on the road Arriving at the traffic junction, the CDP packet contains the
ID. Cells, and hence groups, overlap in such a way that any information of the cell-density of all the traffic groups in the
vehicle moving from one cell to the next belongs at least to road. Having this information is advantageous for determining
one group. The closest vehicle to the cell center is considered if the cell is over-populated, for example, due to a traffic jam
as group leader for a given duration. This is illustrated in
Figure 3 where group leaders are vehicles which are within the 6
By density, we mean the number of vehicles within the cell.
7
small circle around the cell center. Note that all the vehicles are synchronized by GPS.
8
This information is already available in the neighbor table (built and
updated thanks to the periodic exchange of hello messages by all vehicles)
or accident. Perhaps, the overall traffic density will not be high
for the road, but for a particular cell, the density level maybe Table 1: Simulation setup
very high, indicating some traffic problem. SIMULATION / SCENARIO MAC / ROUTING
Simulation Time 200s MAC protocol 802.11 DCF
Map Size 2500 x 2000 m2 Channel Capacity 2 Mbps
Notation: Our own realistic
CDP: the CDP packet to forward Mobility Model Trans. Range ~266 m
mobility model
fv: the forwarding vehicle, Number of 15 CBR
Ibegin: intersection at the beginning of the road section 16 Traffic Model
intersections connections
Iend: intersection at the end of the road section Number of roads 26 Packet sending rate 0.1 – 1 second
Ni1:number of vehicles on cell i moving from Ibegin to Iend,
Weighting factors
Ni2:number of vehicles on cell i moving from Iend to Ibegin, Number of vehicles 100-300 (0.5;0.5)
(α;β)
Algorithm: Vehicle velocity
A vehicle fv receives the packet CDP: 30-50±5 Km/h Data packet size 128 bytes
(city)
if fv is not around Ibegin
then
if fv is a group leader // fv is in the red zone of Cell i The algorithms are compared under various data
then transmission rates and various vehicle densities. Detailed
Update CDP analysis of the simulation results are given in the following.
- Fill the density of cell i Ni = Ni1 + Ni2;
- NextAnchor = center of cell i+1
End if
Select next Hop & forward CDP
- fv selects neighbors (N)moving towards Ibegin
- if ∃ v ∈ N closer to NextAnchor
- then
fv forwards CDP to v
else // fv is the closest vehicle to NextAnchor
Store CDP and carry it
else //the CDP reaches Ibegin
Broadcast CDP around Ibegin
end if
Figure 5 - Algorithm: Forwarding CDP Packet –
Figure 6 –Delivery ratio Vs Packet Sending Rate (300 nodes).
4) Analyzing CDP
The CDP packets are received by the vehicles traversing
through the junctions. These vehicles analyze the CDP packet In Fig. 6, we present the obtained packet delivery ratio of
and calculate the density for the respective road from which the four studied protocols. Figure 6 shows that GyTAR
the CDP was received. The CDP packet is analyzed with achieves the highest packet delivery ratio for the different
respect to the group density information recorded in the packet CBR rates (a relative improvement of over 9% than GSR).
by each group leader. The analysis of the information from This is mainly because in GyTAR, the path is determined
each group (for example, the mean and variance of the cells progressively following road traffic density and urban
density) will provide the overall density of the road. environment characteristics. Hence, a packet will move
successively closer towards the destination along streets where
Hence, when using GyTAR as routing protocol, vehicles there are enough vehicles to provide connectivity. While in
around a junction receive CDP and based on the analysis of its GSR, a complete sequence of waypoints is computed before
content, they calculate the score corresponding to the road the packet is originally transmitted by the source and without
density. considering the vehicular traffic. Consequently, some data
packets can not reach their destination due to a problem of
IV. SIMULATION RESULTS connectivity on some sections of streets.
To evaluate the performance of our proposed protocol, we LAR achieves a lower delivery ratio than GyTAR because
used the Qualnet simulator [5]. We implemented two versions: it uses a route discovery mechanism. Consequently, some data
B-GyTAR (Basic GyTAR without local recovery: a packet is packets can not reach their destination because it is very
simply dropped when it encounters a local maximum difficult to maintain an end-to-end connection in the vehicular
situation), and GyTAR with the recovery method. We also environment (frequent topology change and network
implemented a version of the position-based vehicular routing fragmentation).
protocol GSR [1] since there is not any publicly available
implementation of the protocol. B-GYTAR and GyTAR are
then compared to GSR and LAR [6]. All the key parameters of
our simulation are summarized in the following table:
 [5] Scalable Network Technologies Inc., Qualnet simulator,
http://www.scalable-networks.com.
[6] Y. Ko and N. Vaidya, "Locaton-aided routing (LAR) in mobile ad hoc
networks", ACM/IEEE MOBICOM'98, Dallas, USA, August 1998, p.
66-75.
[7] J. Li, J. Jannotti, D. De Couto, D. Karger, and R. Morris, "A scalable
location service for geographic ad hoc routing", ACM/IEEE
MOBICOM'2000, pp. 120.130, 2000.

Figure 7 –End-to-End Delay Vs Nodes Number (5 packets/ second).

As shown in Figure 7, GyTAR and B-GyTAR achieve a

much lower end–to-end delay than LAR and GSR in all
configurations. This is because in GyTAR, the number of hops
involved to deliver packets is reduced due to the improved
greedy strategy used to forward packets between two
junctions, and also because GyTAR does not need to keep
track of an end-to-end route before sending data packets: the
route is discovered progressively when relaying data packets
from source to destination. In contrast, the geographical
routing protocol LAR uses a route discovery mechanism which
causes longer delays.
Delay of GSR is higher than GyTAR because packets
whose delivery was suspended are stored in the buffer for
longer time than in GyTAR's suspension buffer.

V. CONCLUSION AND FUTURE WORK

In this paper, we proposed GyTAR, a novel routing
algorithm for vehicular ad hoc networks, and we measured its
performance in comparison to other algorithms existing in the
literature. Simulation results show significant performance
improvement in terms of packet delivery ratio, end-to-end
delay.
We also proposed IFTIS, a completely distributed traffic
information system, capable to monitor the city traffic
condition and distribute such information to vehicles around
junctions.
We are currently studying the impact of IFTIS approach in
vehicular ad hoc routing protocols like GyTAR to analyze the
performance gains.
REFERENCES
[1] C. Lochert, H. Hartenstein, J. Tian, D. Herrmann, H. Füßler, M. Mauve,
"A Routing Strategy for Vehicular Ad Hoc Networks in City
Environments", IEEE Intelligent Vehicles Symposium (IV2003), pp.
156-161, Columbus, OH, USA, June 2003.
[2] H. Füßler, M. Mauve, H. Hartenstein, M. Käsemann, and D. Vollmer,
"Location-based routing for vehicular ad hoc networks", student poster,
ACM Mobicom ’02, Atlanta, Georgia, USA, 2002.
[3] B.-C. Seet, G. Liu, B.-S. Lee, C. H. Foh, K. J. Wong, K.-K. Lee, "A-
STAR: A Mobile Ad Hoc Routing Strategy for Metropolis Vehicular
Communications". NETWORKING 2004, 989-999.
[4] C. Lochert, M. Mauve, H. Füßler, H. Hartenstein, "Geographic Routing
in City Scenarios", MobiCom 2004.