Evolving Graphs for Vehicular Ad Hoc Networks: A Comprehensive Study

This paper explores the use of evolving graphs (EG) to enhance routing in Vehicular Ad hoc Networks (VANETs). VANETs aim to improve road traffic efficiency and safety through inter-vehicle communication, but their dynamic topologies pose challenges for data forwarding and routing. The report reviews existing research on VANET connectivity, topology features, and routing protocols, highlighting the limitations of previous approaches in modeling the evolution of VANETs and determining reliable routes. It proposes the use of evolving graphs to capture the dynamic behavior of VANETs, modeling vehicles as vertices and communication links as edges. The EG model maintains a reliable graph comprising motor-vehicles and their corresponding MRJ values, using performance metrics such as packet delivery ratio, average end-to-end delay, routing requests ratio, and link failures. The paper concludes that EG for VANETs increases road efficiency and safety by providing proper signals to drivers and enabling reliable route selection, outperforming related protocols.

EVOLVING GRAPHS FOR VEHICULAR AD HOC NETWORKS 1
EVOLVING GRAPHS FOR VEHICULAR AD HOC NETWORKS
By (Student’s Name)
Name of the Class
(Professor Name)
(Institutional Affiliation)
(Date)

EVOLVING GRAPHS FOR VEHICULAR AD HOC NETWORKS 2
Abstract
Currently, vehicular ad hoc networks also known as VANET has pulled in more attention
than before due to its ability to enhance road traffic efficiency, effectiveness and safety. There
have been wide exploration by a computer scientist on inter-vehicle communication, data
forwarding, and routing but it has never been easy for these researchers to design a well-
organized data and information forwarding procedure and routing due to the evolution of
Vehicular ad hoc networks topologies.
Introduction
In the current century, traffic is an issue and it has become one of the issues to be solved
in both developing and developed countries. VANET and MANET has that ability to transfer
data and information among wireless devices which are installed on cars and vehicles aiming at
improving transportation information collection, on-road information vehicles, and transportation
warning. This has increased lots of researches in this field. One of the major field where there is
a concrete application of VANET is in Inter-vehicle communication due to its assistance in the
ITS (Intelligent Transportation System). Among one of the very first researches was done by
JSK in Japan and later by the Europeans under the banner CarTALK project which tried to solve
some issues related to safe driving and what they referred to as conformable driving. The very
recent study was on IETF which proposed communication between Wireless Access in Vehicular
Environment. Other researches done are C2C-CC and VII (MHEiza, 2013, p. 1498).
Even though there are many pieces of research done on VANET, there is a lack of study
of the dynamic evolving graph for vehicular Adhoc networks that is one of the major aim of this
paper. The research project is ordered as; a literature review of some of the related works and

EVOLVING GRAPHS FOR VEHICULAR AD HOC NETWORKS 3
how one can use evolving graphs theory so as to model VANET communication graphs.
Evolving graphs assists in capturing evolving features of vehicular network topology. It also
helps in determining the reliable routes preemptively. Specifically, this research paper proposes
evolving graphs for VANET to facilitate Quality of Service which helps in the routing process.
Previous research
Most of the researches have focused more on connectivity nodes, Harri and Fiore (2015)
which resulted on the vehicular topology features like duration of the nodes, the degree of
circulation of the nodes, the size of the clusters and the clustering coefficient. Article by Lilu
Zhang (2015) has outlined how Chou and Lan generated real scenario using what they referred to
as SUMO which helped them to prove the influence of the driver behavior and traffic light. What
they never considered is how one can model the evolution of VANET (Y Zhang, 2015). Gao and
others applied what they referred to as a complex network model so as to get topology features
of the public transportation but they one unable to determine reliable routes. This is where now
evolving graphs come into play so as to facilitate QoS. Other work done was the use of vehicle-
heading based protocol which was grouped according to velocity vectors. In here the researchers
were able to predict some of the possible breakage routes. This study used the DSDV protocol
for the purpose of proposing the routing protocol. Prediction-based routing was another study
which took advantage of predictive mobility patterns of those cars on highways (Monteiro, 2016,
p. 62).
Evolving graphs for VANET
Evolving graphs aims at representing a formal abstraction of dynamic networks via
formalization of a time domain. The major aim of Evolving Graphs (EG) is to understand all the
topological properties for VANET. In here vehicles are modeled as vertices whereas the

EVOLVING GRAPHS FOR VEHICULAR AD HOC NETWORKS 4
communication links of these vehicles are modeled as edges in the graphs. With this one is able
to capture the dynamic behavior of VANET. Different from other researches, EG maintains an
array which is referred to as a reliable graph which comprises all motor-vehicles and their
corresponding MRJ values. Evolving Graph model begin by initializing the voyage value for the
source car and the RD for the other vehicles (Kirtiga, et al., 2014). The pseudo-code for EG is;
inputting A the source vehicle then output array referred to as RG which gives the most reliable
route and then setting all the variables which have been unvisited. There are four performance
metrics which are considered in EG for VANET which are the packet delivery ration which
represents the successfully delivered packets, the average end-to-end commonly known as E2E,
the routing requests ratio, and the link failures (Zhang, 2015).
The basic EG for VANET is said to be an indexed sequence of λ subgragh of a certain
graph, where the subgraph at a certain index resembles to the network connection at a certain
time interval as shown by the indexed number as viewed in the figure below. From the figure it
is evident that the edges are labelled with a corresponding time interval. In addition the edges D,
C, and A are not valid journey since D and C exists in the past only in respect to edge A and D.
From the figure above it is very easy to find D, C, E, and G and also A, B, E, and G which are
valid routes (G Pallis, 2016) .

EVOLVING GRAPHS FOR VEHICULAR AD HOC NETWORKS 5
Figure one: A basic EG for VANET (Hashem, 2015)
Analysis
As highlighted from the previous section it is evident that one of the advantages with EG
for VANET is that they increase road efficiency and safety by providing what this paper refer to
as proper signal for those drivers on the road. Also they increase evaluation of what this paper
would refer to as evaluation of communication. Lastly, EG for VANET provides a reliable route
to all the drivers which enables then to avoid rod accidents and traffics (MERAJ, 2015)

EVOLVING GRAPHS FOR VEHICULAR AD HOC NETWORKS 6
Conclusion
This paper has proposed EG for VANET. As viewed from the paper the EG model
provides a more reliable-based routing scheme for VANET. If a network needs connection then
it goes ahead to broadcast a routing request to neighboring vehicles. This outdo the related
protocols highlighted in the previous research section.

EVOLVING GRAPHS FOR VEHICULAR AD HOC NETWORKS 7
References
G Pallis, D. K. M. D., 2016. On the structure and evolution of vehicular networks. Evolving
Graph for VANET, II(2), pp. 47-89.
Hashem, M., 2015. An Evolving Graph-Based Reliable Routing Scheme for VANETs. VANET,
IV(2), pp. 1493-1504.
Kirtiga, R. et al., 2014. Reliable graph based routing in VANET environment. EG for VANET,
V(2), pp. 10-34.
MERAJ, A., 2015. An Evolving Graph-Based Reliable RoutingScheme for VANETs.
International Journal of Advanced Research in Computer and Communication Engineering,
4(2), pp. 132-178.
MHEiza, 2013. An evolving graph-based reliable routing scheme for VANETs. VANET, 2(12),
pp. 1493-1504.
Monteiro, J., 2016. The use of evolving graph combinatorial model in routing protocols for
dynamic networks. EG for VANETs, I(1), pp. 34-79.
Y Zhang, H. Z. W. S. C. P., 2015. Connectivity analysis for vehicular ad hoc network based on
the exponential random geometric graphs. 2014 IEEE proceedings, VII(9), pp. 37-89.
Zhang, L., 2015. Modeling the Dynamic Evolution of the Vehicular Ad Hoc Networks under the
City Scenario. International Journal for sensor Networks, III(4), pp. 167-209.

EVOLVING GRAPHS FOR VEHICULAR AD HOC NETWORKS 8