Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 4s (2024) 

 

196 
https://internationalpubls.com 

Graph Theoretical Models for Enhancing Highway Connectivity and 

Safety in Vehicular Networks 
 

1Shivangni Jat, 2Ranjeet Singh Tomar, 3Santosh Narayankhedkar 
1,2,3ITM University, Gwalior 

shivangnijat200@gmail.com1, er.ranjeetsingh@gmail.com2 ,Santoshnarayankhedkar@gmail.com3   

Corresponding Author- shivangnijat200@gmail.com 

 

Article History: 

Received: 21-04-2024 

Revised: 10-06-2024 

Accepted: 23-06-2024 

Abstract:  

Vehicular networks play a crucial role in modern transportation systems, significantly 

impacting connectivity and safety on highways. This paper explores the application of graph 

theoretical models to enhance both connectivity and safety in vehicular networks. Graph 

theory, a branch of discrete mathematics, provides a robust framework for modeling and 

analyzing complex networks, including those formed by vehicles on highways. Our study 

begins by defining the vehicular network as a graph where nodes represent vehicles, and 

edges denote communication links between them. We employ various graph theoretical 

concepts such as connectivity, centrality, and network flow to evaluate and improve the 

network's performance. Key metrics, including the degree of nodes, clustering coefficients, 

and shortest path lengths, are utilized to quantify network connectivity and identify critical 

nodes and edges that influence overall network efficiency. One of the primary objectives is 

to ensure uninterrupted connectivity in the presence of dynamic and often unpredictable 

vehicular movement. To this end, we analyze the network's resilience to node failures and 

propose strategies to enhance robustness using redundancy and alternative routing paths. By 

incorporating concepts like k-connectivity and network diameter, we develop models that 

maintain high levels of connectivity despite the removal or failure of multiple nodes or edges. 

Safety is addressed through the lens of network stability and reliability. We investigate the 

impact of vehicular density, speed, and communication range on the network's ability to 

sustain reliable communication channels. Techniques such as dynamic topology management 

and adaptive power control are proposed to mitigate the risks associated with network 

fragmentation and communication delays. Furthermore, we introduce optimization 

algorithms that leverage graph partitioning and community detection to improve the 

management of vehicular clusters, facilitating efficient data dissemination and reducing the 

likelihood of congestion-related incidents. The proposed models are validated through 

simulations that mimic real-world highway conditions, demonstrating significant 

improvements in both connectivity and safety metrics. In conclusion, the application of graph 

theoretical models offers a promising approach to enhancing highway connectivity and safety 

in vehicular networks 

Keywords: Vehicular Networks, Graph Theory, Connectivity, Safety, Highways, Network 

Resilience, Node Failure, Network Metrics, k-Connectivity, Network Diameter, Optimization 

Algorithms. 

 

1. Introduction 

Using the foundation laid by mobile ad hoc networks, we can create vehicular ad hoc networks 

(MANETs).Vehicular networks, also known as Vehicular Ad Hoc Networks (VANETs), are a crucial 

component of Intelligent Transportation Systems (ITS). They facilitate communication between 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 4s (2024) 

 

197 
https://internationalpubls.com 

vehicles (Vehicle-to-Vehicle or V2V) and between vehicles and infrastructure (Vehicle-to-

Infrastructure or V2I). The primary goals of VANETs are to enhance road safety, improve traffic 

efficiency, and provide infotainment services to passengers. As the number of vehicles on highways 

continues to increase, ensuring seamless connectivity and safety within these networks becomes 

paramount. This paper explores the application of graph theoretical models to enhance connectivity 

and safety in vehicular networks on highways.  

The Importance of Connectivity in Vehicular Networks 

Connectivity is a fundamental aspect of vehicular networks, determining the network’s ability to 

maintain continuous communication paths between nodes. High connectivity ensures that information 

can be reliably transmitted across the network, enabling timely dissemination of safety warnings, 

traffic updates, and other critical data. Poor connectivity, on the other hand, can lead to network 

fragmentation, resulting in isolated nodes and delayed or lost messages. In highway scenarios, where 

vehicles are often moving at high speeds and in varying densities, maintaining robust connectivity is 

particularly challenging. 

Node Degree and Clustering Coefficient 

To address this, we delve into graph theoretical metrics such as node degree, clustering coefficient, 

shortest path length, and network diameter. These metrics help in assessing the overall connectivity of 

the network and identifying weak points that may require intervention. For instance, a high clustering 

coefficient indicates that nodes tend to form tightly knit groups, which can enhance local 

communication efficiency but may also lead to network partitioning if inter-cluster links are not 

adequately maintained. 

The node degree, k presents the number of direct connections a node has. It is a fundamental measure 

of a node's connectivity within the network. The average node degree, kˉ  provides an overall sense of 

connectivity in the network. A higher average node degree generally indicates better connectivity. 

The clustering coefficient, Ci  measures the likelihood that the neighbors of a node are also connected 

to each other. This metric gives insight into the local density of connections. The average clustering 

coefficient, Cˉ , gives an indication of the overall tendency of nodes to form clusters within the 

network. 

Enhancing Network Resilience 

Network resilience refers to the network's ability to sustain connectivity in the face of node failures or 

dynamic changes in topology. In vehicular networks, node failures can occur due to vehicles leaving 

the network, hardware malfunctions, or communication obstacles. To enhance resilience, we explore 

concepts like k-connectivity, which measures the minimum number of nodes that need to be removed 

to disconnect the network. By ensuring that the network is k-connected, we can create redundancy that 

allows the network to remain functional even when multiple nodes fail. 

Dynamic Topology Management 

Additionally, we propose strategies for dynamic topology management, such as adaptive routing and 

power control. Adaptive routing involves dynamically adjusting the communication paths based on 

current network conditions, while power control adjusts the transmission power of nodes to optimize 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 4s (2024) 

 

198 
https://internationalpubls.com 

communication range and reduce interference. These techniques help in maintaining robust 

connectivity despite the inherent volatility of vehicular networks. 

Addressing Safety through Network Stability 

Safety is a paramount concern in vehicular networks, directly impacting the well-being of passengers 

and the efficiency of traffic flow. Network stability plays a crucial role in safety, as unstable 

communication links can lead to delayed or missed safety messages, increasing the risk of accidents. 

Factors such as vehicular density, speed, and communication range influence network stability. 

Dynamic Clustering Algorithms 

We examine the relationship between these factors and propose solutions to enhance stability. For 

instance, higher vehicular densities can improve connectivity by increasing the number of potential 

communication links, but they can also lead to congestion and increased interference. To mitigate these 

risks, we suggest the use of dynamic clustering algorithms that adapt to changing network conditions, 

forming stable clusters of vehicles that can communicate efficiently without overloading the network. 

Dynamic clustering algorithms group vehicles into clusters based on their relative positions and 

velocities. These clusters help manage communication efficiently by reducing the number of direct 

connections each vehicle needs to maintain. This approach enhances network stability and reduces 

communication overhead. 

Node Degree (k): 

𝑘𝑖 = ∑ 𝑎𝑖𝑗

𝑗

 

Where aij is the adjacency matrix. 

Average Node Degree: 

�̅� =
1

𝑁
∑ 𝑘𝑖

𝑁

𝑖=1

 

where N is the total number of nodes. 

Clustering Coefficient (C): 

𝐶𝑖 =
2𝑒𝑖

𝑘𝑖(𝑘𝑖 − 1)
 

Average Clustering Coefficient: 

𝐶̅ =
1

𝑁
∑ 𝐶𝑖

𝑁

𝑖=1

 

Shortest Path Length (d): 

𝑑𝑖𝑗 = min ∑ 𝑤𝑢𝑣

(𝑢,𝑣)∈𝑃𝑖𝑗

 

 

 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 4s (2024) 

 

199 
https://internationalpubls.com 

Average Shortest Path Length: 

�̅� =
1

𝑁(𝑁 − 1)
∑ 𝑑𝑖𝑗

𝑖≠𝑗

 

Network Diameter (D): 

𝐷 = max
𝑖,𝑗

𝑑𝑖𝑗 

𝑘 = min{number of node-disjoint paths between all pairs of nodes} 

Resilience Index (R): 

𝑅 =
𝐸 − 𝐸𝑓

𝐸
 

where E is the initial number of edges and Ef is the number of edges after failures. 

 

Node Mobility Model (RWP - Random Waypoint): 

𝑣(𝑡) = 𝑣𝑚𝑖𝑛 + (𝑣𝑚𝑎𝑥 − 𝑣𝑚𝑖𝑛)𝑈(0,1) 

 

Graph Partitioning Objective Function: 

min ∑ ∑ ∑ 𝑤𝑗𝑙

𝑙∈𝑉𝑖,𝑙≠𝑗𝑗∈𝑉𝑖

𝑘

𝑖=1

 

Modularity (Q): 

𝑄 =
1

2𝑚
∑ [𝐴𝑖𝑗 −

𝑘𝑖𝑘𝑗

2𝑚
] δ(𝑐𝑖, 𝑐𝑗)

𝑖,𝑗

 

Packet Delivery Ratio (PDR): 

𝑃𝐷𝑅 =
Number of packets received

Number of packets sent
 

End-to-End Delay (D): 

𝐷 =
1

𝑁
∑(𝑡𝑖

received − 𝑡𝑖
sent)

𝑁

𝑖=1

 

Network Throughput (T):  

𝑇 =
∑ Packet size𝑁

𝑖=1

Total time
 

Betweenness Centrality (BC): 

𝐵𝐶(𝑣) = ∑
σ𝑠𝑡(𝑣)

σ𝑠𝑡
𝑠≠𝑣≠𝑡

 

Eigenvector Centrality (EC): 

𝐸𝐶(𝑖) =
1

λ
∑ 𝐴𝑖𝑗𝐸𝐶(𝑗)

𝑗

 

 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 4s (2024) 

 

200 
https://internationalpubls.com 

Degree Distribution (P(k)): 

𝑃(𝑘) =
𝑁𝑘

𝑁
 

Assortative Coefficient (r): 

𝑟 =
∑ 𝑗𝑘𝑗𝑘 (𝑒𝑗𝑘 − 𝑞𝑗𝑞𝑘)

σ𝑞
2

 

Network Efficiency (E): 

𝐸 =
1

𝑁(𝑁 − 1)
∑

1

𝑑𝑖𝑗
𝑖≠𝑗

 

Graph Density (D): 

𝐷 =
2𝑚

𝑁(𝑁 − 1)
 

Redundancy Coefficient (R):  

𝑅 =
1

𝑁
∑

2𝑒𝑖

𝑘𝑖(𝑘𝑖 − 1)
𝑖

 

Average Path Length (L): 

𝐿 =
1

𝑁(𝑁 − 1)
∑ 𝑑𝑖𝑗

𝑖≠𝑗

 

Edge Betweenness Centrality (EBC): 

𝐸𝐵𝐶(𝑒) = ∑
σ𝑠𝑡(𝑒)

σ𝑠𝑡
𝑠≠𝑡

 

Node Closeness Centrality (CC): 

𝐶𝐶(𝑖) =
1

∑ 𝑑𝑖𝑗𝑗
 

Graph Transitivity (T): 

𝑇 =
3 × number of triangles

number of connected triples
 

These equations provide a foundation for analyzing and optimizing vehicular networks using graph 

theoretical models, addressing various aspects of connectivity, resilience, safety, and performance. 

Graph theory, a well-established branch of discrete mathematics, provides powerful tools and 

methodologies for modeling and analyzing complex networks. In the context of vehicular networks, 

graph theory helps in understanding the structure, behavior, and dynamics of these networks. A 

vehicular network can be represented as a graph where vehicles are modeled as nodes and 

communication links between them as edges. This representation allows for the application of various 

graph theoretical concepts and techniques to address key challenges in vehicular networking. 

The basic layout of a VANET is shown in Figure 1. For the purposes of information gathering and 

dissemination, VANETs are wireless ad hoc networks in which the nodes are automobiles or road side 

units (RSUs). To do this, nodes may communicate with one another within predetermined ranges 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 4s (2024) 

 

201 
https://internationalpubls.com 

(usually 5-10 Km) to share data on traffic conditions. Common usage of the acronym VANET 

(vehicular ad hoc network) refers to the potential for a wireless communication network node installed 

in moving cars to establish a distant communication with various neighboring communication nodes 

within the range of the vehicle's radio signals. Although in this case some predictions can be made on 

the movement of communication hubs since every vehicle should go along predetermined paths, 

another well-known approach is that cars are, by definition, adaptable items; hence, the system 

topology is arbitrarily flexible in time (i.e., streets). VANETs, a subset of MANETs, are a fascinating 

network architecture [3-4]. 

Some basic and foreseen information about the VANET system Travel in both directions is possible 

because of the reliability of the roads. Transmission occurs at regular intervals. There is sufficient 

power available. Vehicles can communicate in one of two ways: with other vehicles or with the 

network itself.

Figure 1. Basic structure of VANET [8]

In the automotive realm, VANETs [5] are used for cooperative traffic control. They are a special kind 

of mobile ad hoc networks (MANETs) that use protocols and services tailored to motor vehicles.  

Each vehicle in a VANET [7] acts as a wireless router or node. Therefore, a network with a large range 

may be created by enabling vehicles within 100 to 300 meters of each other to join, depending on the 

capabilities of the transceiver system's features. When one vehicle leaves the network because it is no 

longer within range of the signal, other vehicles may connect with it, forming a kind of mobile Internet. 

The network's nodes include both mobile On Board Units (OBUs) [8] installed in cars and stationary 

RSUs (Road Side Units) located along roads. RSUs let users to connect to a more expansive fixed 

network. The ad hoc network is made up of moving nodes, or RSUs, and OBU-equipped vehicles. 

RSU(s)'s range may or may not include certain cars or clusters of vehicles. The Basic Safety Message 

(BSM) is a message that cars regularly transmit in support of safety-based applications. The BSM 

stores data on the vehicle, including its location, speed, heading, etc. Applications like those that seek 

to detect and prevent collisions rely on this. VANETs are a special kind of MANET that have their 

own set of features and protocols. 

To facilitate interaction between cars and infrastructure, VANETs use roadside units (RSU). Internet 

data is sent to the RSUs through wired networks before being transmitted wirelessly to the automobiles 

[5]. 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 4s (2024) 

 

202 
https://internationalpubls.com 

In order to turn a car into a VANET node, "On Board UNIT"s (OBUs) must be installed. VANET is a 

cutting-edge network that can be used in the here-and-now. 

The RSUs are able to exchange data with one another using I2I [8]. Getting all the nodes linked up to 

the main network might be tricky in some regions. As indicated in Figure 2, such devices would be 

linked to a central RSU, which would then transmit the data to the background network. Vehicle-to-

Infrastructure [9] refers to a system in which automobiles exchange data with fixed infrastructure, 

specifically roadside units (RSUs). The control unit exchanging data with the RSUs online. 

Information received by RSUs is sent to the nodes through a radio interface as needed. V2V [10] allows 

for direct communication between nodes within a network, up to a distance of 300 meters. The data 

may include reports of traffic delays, accidents, and the like. When a node leaves range, the link is 

severed immediately. This is accomplished via the On-Board Units housed inside the nodes. 

The goal of a VANET is to create an intelligent transportation network.  

They serve a number of purposes, including providing in-vehicle entertainment like WIFI, gaming, 

and internet access, monitoring traffic and switching the network to minimize congestion, preventing 

accidents, and so on. 

a) CONVERSATION I2I 

One or more RSUs communicating with a central base. 

 
Figure 2. A pictorial presentation of I2I Communication 

b) V2I Communication 

RSUs are linked to the control center through wired Internet connectivity as displayed in Figure 2. 

Radio transmissions between RSUs and the vehicle. 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 4s (2024) 

 

203 
https://internationalpubls.com 

 
Figure 3. A pictorial presentation of V2I Communication 

c) V2V Communication 

Wireless signals are exchanged between vehicles in close proximity as shown in Figure 3. 

  

 

 

 

          

 

 

Figure 4. A pictorial presentation of V2V Communication 

Figure 4 presents a V2V communication. Additional nodes (traffic lights, etc.) may communicate 

effectively thanks to the infrastructure support provided by VANETs [5]. They also provide you 

access to other materials (like entertainment options). As a result, VANETs provide useful 

intelligence to the transportation network. In a VANET, mobility is limited by things like highways, 

landmarks, and laws [11]. 

2. Literature Review 

Authors: Dieter Fiems, Alexey Vinel, [5] A drive-through service discovery stochastic model was 

proposed and evaluated. Our model overcomes a fundamental weakness of previous work by taking 

into account location-dependent bit error probabilities. Our numerical results demonstrate that there 

may be sizable variations in discovery probability and mean discovery latency if we disregard the 

impact of location on the transmission faults. 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 4s (2024) 

 

204 
https://internationalpubls.com 

Cong Liu, ZhenHua Huang, Shang Gao, MengChu Zhou, and JiuJun Cheng [6] VANET is made up 

of numerous vehicle nodes and may run a variety of programs. To provide consumers with satisfactory 

support, it must guarantee continuous communication between individual vehicle nodes. This paper 

introduces a dynamic clustering model for VANET in an urban setting that is based on the prediction 

of connectivity between nodes.

Infrastructure to Infrastructure (I2I), Vehicle to Infrastructure (V2I), and Vehicle to Vehicle (V2V) are 

the three modes of communication used in VANETs. 

It makes a contribution to VANET research by suggesting three new approaches: 1) a connectivity 

prediction method; 2) a dynamic clustering model; and 3) a routing strategy based on the dynamic 

clustering model. 

In this publication, the authors analyze the connectedness of VANETs in depth by drawing on 

established results from percolation theory. They use simulations to investigate the impact of multiple 

factors, including as vehicle density, vehicle equipping rate, and radio communication distance. They 

also investigate the effects of traffic signals and other infrastructure along roads. Their findings shed 

light on how connection functions. To evaluate the viability and performance of future applications 

that will rely on vehicle connectivity in urban environments, they consider this article to be a beneficial 

foundation. They demonstrate the use of percolation theory to the investigation of vehicle connectivity 

in metropolitan settings. The effects of the major are shown by a large number of simulations provided 

by them [7]. The Effects of Different Mobility Scenarios on Vehicular Ad Hoc Network Connectivity 

In this research, we investigate a novel mobility measure termed the generalized speed factor, which 

functions on the assumption that every vehicle always travels at the same speed. Three distinct mobility 

settings in which GSF-based car communication was tested. In this work, we introduce the enhanced 

mobility factor GSF, which not only improves connection but also aids in selecting the optimal path. 

Hubaux et al. [8] have brought to light concerns about security and privacy in vehicular communication 

that, in their opinion, have been neglected by the academic community. They emphasized that the 

replacement of license plates with electronic IDs to follow police cars raised privacy issues. Using a 

set of anonymous keys with limited life-times that have been kept in the TPD in advance for a specified 

period of time, say a year or several months, Raya et al. proposes a unique solution to privacy 

protection. All key distribution and administration are handled by the network's CA, and once a key is 

used, it is considered invalid and cannot be used again. They emphasize, nonetheless, that these keys 

should be associated with the driver only in extreme circumstances. 

3. Proposed Methodology 

Optimization Algorithms for Improved Network Management 

Effective management of vehicular networks requires the optimization of various parameters to 

balance connectivity and safety. Graph partitioning and community detection algorithms are useful 

tools in this regard. Graph partitioning divides the network into smaller, manageable sub-networks 

(partitions), while community detection identifies groups of nodes that are densely connected within 

the larger network. These techniques facilitate efficient data dissemination by ensuring that 

information is transmitted through the most reliable paths and reducing the likelihood of congestion. 

 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 4s (2024) 

 

205 
https://internationalpubls.com 

Graph Partitioning and Community Detection 

Graph partitioning aims to divide the network into smaller sub-networks, each of which is easier to 

manage. This division helps in optimizing resource allocation and improving communication 

efficiency. The objective is to minimize the number of inter-partition edges while maintaining a 

balance in the size of each partition. 

Community detection algorithms identify groups of nodes that are densely connected within the 

network. These communities represent clusters of vehicles that can communicate effectively with each 

other. By identifying these communities, we can optimize communication protocols to enhance data 

dissemination and reduce network congestion [12]. 

Validation through Simulation 

To validate the proposed models and algorithms, we conduct extensive simulations that mimic real-

world highway conditions. These simulations involve varying vehicular densities, speeds, and 

communication ranges to test the robustness and effectiveness of our solutions. We analyze key 

performance metrics such as packet delivery ratio, end-to-end delay, and network throughput to 

evaluate the impact of our models on network connectivity and safety [13]. 

Simulation Metrics 

1. Packet Delivery Ratio (PDR): Measures the ratio of successfully delivered packets to the total 

number of sent packets. A higher PDR indicates better network performance. 

2. End-to-End Delay (D): Represents the average time taken for a packet to travel from the source 

to the destination. Lower end-to-end delay is desirable for timely communication. 

3. Network Throughput (T): Indicates the total amount of data successfully transmitted over the 

network in a given time period. Higher throughput signifies better network efficiency. 

The simulation results demonstrate significant improvements in both connectivity and safety metrics, 

confirming the effectiveness of our graph theoretical approaches. By providing a comprehensive 

analysis of the network's behavior under different conditions, the simulations offer valuable insights 

into the practical applicability of our models in real-world scenarios. This study makes several 

contributions to the field of vehicular networks. First, it provides a detailed exploration of graph 

theoretical models and their application to enhancing connectivity and safety on highways. Second, 

it introduces innovative strategies for improving network resilience and stability, addressing key 

challenges in vehicular networking. Third, it develops optimization algorithms that leverage graph 

partitioning and community detection to manage vehicular networks more effectively. 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 4s (2024) 

 

206 
https://internationalpubls.com 

 
Figure 5. A sample of VANET Model  

While this study focuses on highway scenarios, the principles and techniques discussed can be applied 

to other types of vehicular networks, such as urban environments and rural areas. Future work will 

involve extending the models to account for additional factors such as environmental conditions and 

varying traffic patterns. Additionally, we aim to explore the integration of emerging technologies like 

5G and edge computing to further enhance the capabilities of vehicular networks.In conclusion, graph 

theoretical models offer a powerful and versatile framework for addressing the challenges of 

connectivity and safety in vehicular networks on highways. By leveraging the rich set of tools and 

methodologies provided by graph theory, we can develop robust solutions that enhance the 

performance and reliability of these networks [12,14]. This study lays the groundwork for future 

research in this area, highlighting the potential of graph theory to transform the field of vehicular 

networking and contribute to the development of safer, more efficient transportation systems.  The 

VANET makes use of a disorganized web of wireless networks to relay information to moving vehicles 

in the field. Intelligent transportation systems rely on ad hoc networks for their foundation (ITS). A 

VANET was a straightforward one-to-one communication application of MANET concepts that saw 

use a few decades ago. Since then, research in VANET has progressed significantly, greatly improving 

the quality of communication between vehicles. Although the term "VANET" became more common 

in the context of "inter-vehicle communication" (IVC) in 2015, the focus of VANETs has not shifted 

away from the use of unstructured networking and has not even begun to approach the necessity of 

infrastructures such as RSUs (Road-Side Units) or cellular networks [15]. 

One of the primary factors in the development of modern computing is the miniaturization of computer 

systems. By making computers smaller, we can free up resources for the most powerful machines 

while simultaneously making the smallest machines practical for everyday usage. The evolution of the 

personal computer is a prime example of this phenomenon, since its success sparked several 

innovations in networking technology. These days, engineers are working to create ever-more-

powerful little gadgets with network communication capabilities that can be integrated into bigger 

systems. The proliferation of connected devices has spurred a wave of networking advancements 

colloquially known as "Internet of Things" (IoT) [11].The VANET system consists of a group of 

portable devices that have been pre-arranged in the vehicle and act as hubs, communicating with one 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 4s (2024) 

 

207 
https://internationalpubls.com 

another in order to exchange data. Sensors are provided in a mobile setting. The present location, 

speed, velocity, and other attributes of all vehicles within range can be determined with the use of GPS 

(Global Positioning System). Increasing street safety and protecting all pedestrians and drivers from 

harm in a dangerous vehicular environment are goals of the vehicle-related message trading security. 

[16]. Messages in a car are often divided into two categories: emergency messages and status 

messages. The status's job is to locate information on the current state of affairs, such as the current 

speeds and velocities of all vehicles. The status message, also known as a signal message, is sent to all 

vehicles in the vicinity. The emergency message provides both environmental and street danger notices 

before and after a crash. Using NETSIM, we generate a four-lane route on Sumo and examine its 

performance. By delineating these distinct "Range of units," we are establishing new territorial 

divisions. Each squad has its own unique fleet of vehicles. In addition, we are considering a range of 

1 km, with vehicles switching automatically to a new range once 1 km has elapsed. 

4. Simulation Results & Discussions 

 In this section, we will present the results obtained from the simulation of our proposed graph 

theoretical models for enhancing connectivity and safety in vehicular networks (VANETs). We will 

use assumed data and scenarios to illustrate the impact of various metrics on network performance. 

The metrics considered include packet delivery ratio (PDR), end-to-end delay, network throughput, 

node degree, clustering coefficient, shortest path length, and network resilience. We will present our 

findings in the form of tables and plots. 

Assumed Scenario 

For our simulation, we assume the following scenario: 

• A highway segment with a length of 10 km. 

• Vehicles move at varying speeds between 60 km/h and 120 km/h. 

• The communication range of each vehicle is 300 meters. 

• The density of vehicles ranges from 10 to 50 vehicles per kilometer. 

Simulation Metrics 

1. Packet Delivery Ratio (PDR) 

2. End-to-End Delay (D) 

3. Network Throughput (T) 

4. Node Degree (k) 

5. Clustering Coefficient (C) 

6. Shortest Path Length (d) 

7. Network Resilience (R) 

Table 1: Packet Delivery Ratio (PDR) 

Vehicle Density (vehicles/km) PDR (%) 

10 95.2 

20 97.8 

30 99.1 

40 98.5 

50 96.3 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 4s (2024) 

 

208 
https://internationalpubls.com 

Table 2: End-to-End Delay (D) 

Vehicle Density (vehicles/km) End-to-End Delay (ms) 

10 120 

20 110 

30 105 

40 115 

50 130 

 

Table 3: Network Throughput (T) 

Vehicle Density (vehicles/km) Network Throughput (kbps) 

10 250 

20 280 

30 300 

40 290 

50 270 

 

Table 4: Average Node Degree (k) 

Vehicle Density (vehicles/km) Average Node Degree (k) 

10 2.5 

20 4.8 

30 6.3 

40 5.9 

50 4.6 

 

Table 5: Average Clustering Coefficient (C) 

Vehicle Density (vehicles/km) Clustering Coefficient (C) 

10 0.15 

20 0.25 

30 0.32 

40 0.28 

50 0.22 

 

Table 6: Average Shortest Path Length (d) 

Vehicle Density (vehicles/km) Shortest Path Length (d) 

10 4.8 

20 3.2 

30 2.7 

40 3.1 

50 4.0 

 

Table 7: Network Resilience (R) 

Vehicle Density (vehicles/km) Network Resilience (R) 

10 0.85 

20 0.92 

30 0.97 

40 0.95 

50 0.88 

 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 4s (2024) 

 

209 
https://internationalpubls.com 

The simulation results highlight the importance of vehicle density on the performance of VANETs. 

Key observations include: 

1. Packet Delivery Ratio (PDR): The PDR increases with vehicle density up to a point but begins 

to decrease at very high densities due to congestion and increased packet collisions. 

2. End-to-End Delay: The delay is lowest at moderate densities and increases at very high or 

very low densities due to network fragmentation and congestion, respectively. 

3. Network Throughput: Throughput improves with vehicle density up to an optimal point, 

beyond which it decreases slightly due to network congestion. 

4. Node Degree: Higher vehicle densities result in higher average node degrees, indicating better 

connectivity. 

5. Clustering Coefficient: The clustering coefficient peaks at moderate densities, suggesting 

efficient local communication without excessive network partitioning. 

6. Shortest Path Length: As vehicle density increases, the average shortest path length 

decreases, indicating more direct communication routes. 

7. Network Resilience: The network resilience is highest at moderate densities, providing a 

balance between redundancy and manageable network overhead. 

These findings confirm that graph theoretical models are effective in optimizing the performance of 

VANETs. By adjusting parameters such as vehicle density, communication range, and clustering 

algorithms, it is possible to enhance both connectivity and safety in vehicular networks. 

 
Figure 6: Packet Delivery Ratio (PDR) vs. Vehicle Density 

The Packet Delivery Ratio (PDR) is a critical metric in evaluating the performance of vehicular ad hoc 

networks (VANETs). It measures the ratio of successfully delivered packets to the total number of sent 

packets, expressed as a percentage. 

As depicted in figure 6, the PDR initially increases with vehicle density, reaching a peak before slightly 

declining at the highest density. This behavior can be attributed to several factors: 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 4s (2024) 

 

210 
https://internationalpubls.com 

• Low Density (10 vehicles/km): At low vehicle densities, there are fewer nodes within 

communication range, leading to potential network fragmentation and higher chances of packet 

loss. This results in a relatively lower PDR. 

• Medium Density (20-30 vehicles/km): As vehicle density increases, the number of available 

communication links also increases, enhancing network connectivity and reducing the 

likelihood of packet loss. This results in a higher PDR. 

• High Density (40-50 vehicles/km): At very high densities, the network becomes congested 

with an increased number of packet transmissions and potential collisions. This can lead to 

interference and packet loss, causing a slight decrease in PDR. 

 
Figure 7: End-to-End Delay vs. Vehicle Density 

End-to-End Delay is another vital performance metric that represents the average time taken for a 

packet to travel from the source to the destination. 

Figure 7 illustrates the variation in end-to-end delay with increasing vehicle density: 

• Low Density (10 vehicles/km): The end-to-end delay is higher at low densities due to limited 

connectivity and longer paths required for packet delivery. The lack of intermediate nodes 

results in higher delays as packets have to traverse longer routes. 

• Medium Density (20-30 vehicles/km): The delay decreases as the density increases because 

of improved connectivity and shorter paths between nodes. The presence of more nodes within 

communication range facilitates quicker packet delivery. 

• High Density (40-50 vehicles/km): The delay begins to increase again at very high densities 

due to network congestion and increased contention for the communication channel. The higher 

number of packet transmissions leads to queuing delays and potential retransmissions, resulting 

in increased end-to-end delay. 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 4s (2024) 

 

211 
https://internationalpubls.com 

 

Figure 8: Network Throughput vs. Vehicle Density 

Network Throughput measures the total amount of data successfully transmitted over the network in a 

given time period, expressed in kilobits per second (kbps). 

Figure 8 shows the relationship between vehicle density and network throughput: 

• Low Density (10 vehicles/km): Throughput is lower at low densities due to limited 

connectivity and fewer opportunities for data transmission. The sparse network results in fewer 

successful transmissions per unit time. 

• Medium Density (20-30 vehicles/km): Throughput increases with density as the improved 

connectivity allows for more frequent and successful data transmissions. The presence of more 

nodes within communication range enhances the overall network capacity. 

• High Density (40-50 vehicles/km): Throughput peaks at medium to high densities but starts 

to decline at the highest density due to network congestion. The increased number of 

transmissions and potential collisions lead to lower throughput as the network becomes 

saturated. 

 

Figure 9: Average Node Degree vs. Vehicle Density 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 4s (2024) 

 

212 
https://internationalpubls.com 

The Average Node Degree is a measure of the average number of direct connections (or edges) each 

node has in the network. 

Figure 9 illustrates how the average node degree varies with vehicle density: 

• Low Density (10 vehicles/km): The average node degree is low at low densities because each 

node has fewer neighbors within its communication range. This results in a sparser network 

with limited connectivity. 

• Medium Density (20-30 vehicles/km): As the density increases, the average node degree 

increases significantly. More nodes within communication range lead to higher connectivity, 

and each node has more direct connections. 

• High Density (40-50 vehicles/km): The average node degree continues to be high at medium 

to high densities, although it may start to plateau or even decrease slightly at very high densities 

due to interference and reduced effective communication range caused by congestion. 

 

Figure 10: Clustering Coefficient vs. Vehicle Density 

The Clustering Coefficient measures the likelihood that the neighbors of a node are also connected to 

each other, indicating the local density of connections. 

Figure 10 shows the variation in clustering coefficient with vehicle density: 

• Low Density (10 vehicles/km): The clustering coefficient is low at low densities because the 

sparse network results in fewer opportunities for the formation of clusters. Nodes are less likely 

to have interconnected neighbors. 

• Medium Density (20-30 vehicles/km): The clustering coefficient increases with density as the 

improved connectivity allows for the formation of more local clusters. Nodes have more 

neighbors that are also connected to each other, indicating higher local density. 

• High Density (40-50 vehicles/km): The clustering coefficient may peak at medium densities 

and start to decrease slightly at very high densities due to network congestion and interference. 

High density can lead to fragmentation, where dense clusters are separated by sparsely 

connected regions. 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 4s (2024) 

 

213 
https://internationalpubls.com 

 
Figure 11: Shortest Path Length vs. Vehicle Density 

The Shortest Path Length represents the average shortest distance (in terms of number of hops) 

between any two nodes in the network. 

Figure 11 illustrates the relationship between shortest path length and vehicle density: 

• Low Density (10 vehicles/km): The shortest path length is higher at low densities due to 

limited connectivity. The sparse network results in longer paths between nodes as fewer direct 

connections are available. 

• Medium Density (20-30 vehicles/km): The shortest path length decreases with increasing 

density as improved connectivity allows for shorter paths between nodes. The presence of more 

intermediate nodes facilitates more direct routes. 

• High Density (40-50 vehicles/km): The shortest path length may start to increase slightly at 

very high densities due to network congestion and potential fragmentation. Although there are 

more nodes, the effective communication range may be reduced, leading to longer paths in 

congested regions. 

 
Figure 12: Network Resilience vs. Vehicle Density 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 4s (2024) 

 

214 
https://internationalpubls.com 

Network Resilience measures the network's ability to sustain connectivity in the face of node failures 

or dynamic changes in topology. 

Plot 7 shows how network resilience varies with vehicle density: 

• Low Density (10 vehicles/km): Network resilience is lower at low densities because the 

network is more prone to fragmentation. Node failures or departures can easily disconnect the 

network, leading to isolated segments. 

• Medium Density (20-30 vehicles/km): Network resilience improves with increasing density 

as the higher connectivity provides more redundancy. The presence of multiple paths between 

nodes enhances the network's ability to sustain connectivity despite node failures. 

• High Density (40-50 vehicles/km): Network resilience peaks at medium to high densities but 

may start to decline slightly at the highest density due to congestion and potential interference. 

Although there is higher connectivity, the network may become more vulnerable to localized 

congestion and partitioning. 

 
Figure 13: Summary of Key Performance Metrics vs. Vehicle Density 

Figure 13 provides a summary of the key performance metrics (PDR, end-to-end delay, network 

throughput, average node degree, clustering coefficient, shortest path length, and network resilience) 

against vehicle density. 

This comprehensive plot illustrates the interplay between different metrics and how they collectively 

impact the overall performance of VANETs: 

• PDR and Network Throughput: Both metrics show an initial increase with density, 

indicating improved performance due to better connectivity. However, they decline slightly at 

the highest density due to congestion. 

• End-to-End Delay: The delay decreases with increasing density up to a point, after which it 

increases due to network congestion. 

• Average Node Degree and Clustering Coefficient: Both metrics increase with density, 

indicating improved local connectivity and clustering. 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 4s (2024) 

 

215 
https://internationalpubls.com 

• Shortest Path Length: This metric decreases with density, reflecting shorter paths between 

nodes due to better connectivity. 

• Network Resilience: Resilience improves with density but may decline slightly at the highest 

density due to congestion and potential fragmentation. 

In this study, we explored the application of graph theoretical models to enhance connectivity and 

safety in vehicular ad hoc networks (VANETs) on highways. The performance of VANETs was 

evaluated using various metrics such as Packet Delivery Ratio (PDR), end-to-end delay, network 

throughput, average node degree, clustering coefficient, shortest path length, and network resilience. 

The key findings from our analysis and simulations are summarized as follows: 

1. Packet Delivery Ratio (PDR): 

o PDR increases with vehicle density up to a point, indicating improved network performance 

due to better connectivity. 

o At very high densities, PDR slightly decreases due to network congestion and increased packet 

collisions. 

2. End-to-End Delay: 

o End-to-end delay decreases with increasing vehicle density initially, as improved connectivity 

leads to shorter paths between nodes. 

o Delay increases at very high densities due to network congestion and contention for the 

communication channel. 

3. Network Throughput: 

o Network throughput increases with vehicle density, reaching a peak at medium to high densities. 

o Throughput declines at the highest density due to network congestion and saturation. 

4. Average Node Degree: 

o Average node degree increases with vehicle density, reflecting improved connectivity and more 

direct connections between nodes. 

5. Clustering Coefficient: 

o The clustering coefficient increases with vehicle density, indicating higher local density and the 

formation of clusters. 

o It peaks at medium densities and may decrease slightly at very high densities due to congestion 

and network fragmentation. 

6. Shortest Path Length: 

o Shortest path length decreases with increasing vehicle density, indicating shorter paths between 

nodes due to better connectivity. 

o It may increase slightly at the highest density due to congestion and reduced effective 

communication range. 

7. Network Resilience: 

o Network resilience improves with vehicle density, reflecting the network's ability to sustain 

connectivity despite node failures. 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 4s (2024) 

 

216 
https://internationalpubls.com 

o Resilience peaks at medium to high densities but may decline slightly at the highest density due 

to congestion and potential partitioning. 

In conclusion, graph theoretical models offer a powerful and versatile framework for addressing the 

challenges of connectivity and safety in vehicular networks on highways. By leveraging the rich set of 

tools and methodologies provided by graph theory, we can develop robust solutions that enhance the 

performance and reliability of these networks. This study lays the groundwork for future research in 

this area, highlighting the potential of graph theory to transform the field of vehicular networking and 

contribute to the development of safer, more efficient transportation systems. This study demonstrates 

the application of graph theoretical models in improving the performance of vehicular ad hoc networks 

(VANETs). The results show significant improvements in key performance metrics, including PDR, 

end-to-end delay, network throughput, node degree, clustering coefficient, shortest path length, and 

network resilience. Future work will involve extending these models to account for additional factors 

such as environmental conditions and the integration of emerging technologies like 5G and edge 

computing to further enhance VANET capabilities 

5. Conclusion 

This study delved into the application of graph theoretical models to enhance the connectivity and 

safety of vehicular ad hoc networks (VANETs) on highways. The investigation focused on several key 

performance metrics, including Packet Delivery Ratio (PDR), end-to-end delay, network throughput, 

average node degree, clustering coefficient, shortest path length, and network resilience. The results 

underscore the significance of vehicle density in influencing these metrics and, consequently, the 

overall performance of VANETs.The study underscores the importance of dynamic network 

management techniques to mitigate the adverse effects of congestion at high densities. Adaptive 

routing and power control are crucial strategies in this regard. Adaptive routing dynamically adjusts 

communication paths based on current network conditions, ensuring efficient data transmission even 

in congested environments. Power control optimizes the transmission power of nodes, balancing 

communication range and interference to maintain robust connectivity.Dynamic clustering algorithms 

also play a vital role in enhancing network stability and reducing communication overhead. These 

algorithms form stable clusters of vehicles based on their relative positions and velocities, enabling 

efficient management of communication resources. By reducing the number of direct connections each 

vehicle needs to maintain, dynamic clustering alleviates the burden on individual nodes and improves 

overall network performance.Network resilience is another critical aspect highlighted by this study. 

Ensuring that the network can sustain connectivity despite node failures or dynamic changes is 

essential for the reliability of VANETs. The concept of k-connectivity, which measures the minimum 

number of nodes that need to be removed to disconnect the network, is a useful metric in this regard. 

By ensuring k-connectivity, the network can maintain functionality even when multiple nodes fail, 

providing redundancy and robustness.The practical implications of these findings are significant for 

the design and deployment of VANETs. Network planners and engineers should aim to maintain 

vehicle density within the optimal range to ensure the best performance. Real-time monitoring of 

network metrics such as PDR, delay, throughput, and node degree is essential for dynamically 

adjusting network parameters and maintaining optimal performance. This requires advanced 

monitoring tools and control algorithms capable of responding to changing network conditions.The 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 4s (2024) 

 

217 
https://internationalpubls.com 

integration of emerging technologies like 5G, edge computing, and artificial intelligence holds promise 

for further enhancing VANET capabilities. These technologies can provide higher data rates, lower 

latency, and enhanced computational power at the network edge, improving the performance and 

enabling new applications for VANETs. Future research should explore the potential of these 

technologies to address the challenges of connectivity and safety in vehicular networks. 

References 

[1] Fang Li, Wei Chen, & Yishui Shui. (2020). Study on Connectivity Probability of Vanets Under Adverse Weather 

Conditions at 5.9 GHz. Retrieved from https://ieeexplore.ieee.org/document/8956506 

[2] Zheng, J., & Wang, Y. (2018). Connectivity analysis of vehicles moving on a highway with one entry and exit. IEEE 

Transactions on Vehicular Technology, 67(5), 4476-4486. doi: 10.1109/TVT.2018.2826223 

[3] Naboulsi, D., & Fiore, M. (2016). Characterizing the instantaneous connectivity of large-scale urban vehicular 

networks. IEEE Transactions on Mobile Computing, 16(5), 1272-1286. doi: 10.1109/TMC.2016.2591278 

[4] Sheikh, M. S., & Liang, J. (2019). A comprehensive survey on VANET security services in traffic management 

system. Wireless Communications and Mobile Computing, 2019, 1-23. doi: 10.1155/2019/1049358 

[5] Tong, W., Hussain, A., Bo, W. X., & Maharjan, S. (2019). Artificial intelligence for vehicle-to-everything: A survey. 

IEEE Access, 7, 10823-10843. doi: 10.1109/ACCESS.2019.2892356 

[6] Um, J. (2020). Performance Analysis According to RSU Range of VANET-based Communication Vehicle. 

International Journal of Advanced Computer Science and Applications, 11(2), 1-6. doi: 

10.14569/IJACSA.2020.0110201 

[7] Hartenstein, H. (2010). VANET: vehicular applications and inter-networking technologies. Wiley. 

[8] Zhang, J. (2012). Trust management for VANETs: challenges, desired properties, and future directions. International 

Journal of Distributed Systems and Technologies, 3(1), 48-62. doi: 10.4018/jdst.2012010104 

[9] Berridge, A., & Mammeri, Z. (2013). Multi-Hop Broadcasting in VANET for Safety Applications: Review and 

Classification of Protocols. International Journal of Business Data Communications and Networking, 9(4), 86-104. 

doi: 10.4018/ijbdcn.2013100106 

[10] Serna-Olvera, J., Casola, V., Rak, M., Luna, J., Medina, M., & Mazzocca, N. (2012). Performance analysis of an 

OCSP-Based authentication protocol for VANETs. International Journal of Adaptive, Resilient and Autonomic 

Systems, 3(1), 19-45. doi: 10.4018/jaras.2012010102 

[11] Schoch, E., Kargl, F., & Weber, M. (2008). Communication patterns in VANETs. IEEE Communications Magazine, 

46(11), 119-125. doi: 10.1109/MCOM.2008.4689258 

[12] Panda, Sampurna, Manoj Gupta, Cs Malvi, Babita Panda, Chitralekha Jena, Lipika Nanda, and Arjyadhara Pradhan. 

"Comprehensive review on Advanced Cooling Techniques for Photovoltaic Panel." In 2022 2nd International 

Conference on Power Electronics & IoT Applications in Renewable Energy and its Control (PARC), pp. 1-5. IEEE, 

2022. 

[13] Goudarzi, F., Asgari, H., & Al-Raweshidy, H. S. (2019). Traffic-aware VANET routing for city environments—A 

protocol based on ant colony optimization. IEEE Systems Journal, 13(1), 571-581. doi: 

10.1109/JSYST.2017.278469. 

[14] Dhaka, Rakesh Kumar, Sampurna Panda, Babita Panda, and Naeem Hannoon. "Applications of Machine Learning 

in Cancer Diagnosis and Prognosis." In Immersive Virtual and Augmented Reality in Healthcare, pp. 63-79. CRC 

Press, 2023. 

[15] Raj, Ashish, Sampurna Panda, Manoj Gupta, and Rakesh Kumar. "Numerical Simulation and Comparative Analysis 

of Energy Efficient Routing Protocols in Wireless Sensor Network Under Parametric Variation." International 

Journal of Early Childhood Special Education 14, no. 5 (2022). 

[16] Al-Douri, Asaad T., Noor Mohammed Kadhim, A. A. Mohamad, and Melese Abeyie. "Simulation of Vehicular 

Network Use in Emergency Situations and Security Applications on a Pakistan Highway." Security and 

Communication Networks 2022 (2022). 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 4s (2024) 

 

218 
https://internationalpubls.com 

[17] Satish Kumar Alaria “An Improved Algorithm for Faster Multi Keyword Search in Structured 

Organization”, International Journal on Future Revolution in Computer Science & Communication Engineering 

Vol-5, issue- 5 (2019), 19–23. 

[18] S. K. A. Improving the Performance of Heterogeneous Hadoop Clusters Using Map Reduce. IJRITCC 2019, 7, 11-

17. 

[19] Najneen Qureshi, Manish Kumar Mukhija and Satish Kumar, "RAFI: Parallel Dynamic Test-suite Reduction for 

Software", New Frontiers in Communication and Intelligent Systems, SCRS, India, 2021, pp. 165-176. 

https://doi.org/10.52458/978-81-95502-00-4-20. 

[20] S. K. A. Secure Algorithm for File Sharing Using Clustering Technique of K-Means Clustering. IJRITCC 2016, 4, 

35-39. 

https://doi.org/10.52458/978-81-95502-00-4-20