|Computers, Materials & Continua |
A Robust Emergency Messages Routing Scheme for Urban VANETs
1Department of Computer Science, University of Engineering and Technology, Taxila, Pakistan
2Telecommunications and Networking Research Center, GIK Institute of Engineering Sciences and Technology, Topi, 23640, Pakistan
*Corresponding Author: Mumtaz Ali Shah. Email: email@example.com
Received: 11 December 2021; Accepted: 14 January 2022
Abstract: Vehicular ad-hoc networks (VANETs) play an essential role in enhancing transport infrastructure by making vehicles intelligent and proficient in preventing traffic fatalities. Direction-based greedy protocols pick the next route vehicle for transmitting emergency messages (EMs) depending upon the present location of adjacent vehicles towards sink vehicles by using an optimal uni-directional road traffic approach. Nevertheless, such protocols suffer performance degradation by ignoring the moving directions of vehicles in bi-directional road traffic where topological changes happen continuously. Due to the high number of vehicles, it is essential to broadcast EMs to all vehicles to prevent traffic delays and collisions. A cluster-based EM transmitting technique is proposed in this paper. For urban VANETs, this paper pioneers the clustering of bi-directional road traffic for robust and efficient routing of EMs. In this regard, this paper introduces a routing protocol, namely, the bi-directional urban routing protocol (BURP). In addition to the paths and relative locations of vehicles, BURP takes account of the distance parameter by using the Hamming distance function to determine the direction of motion of vehicles and communicates EMs through the cluster head (CH). A modified k-medoids algorithm is presented for the clustering of bi-directional road traffic. A median method is presented for selecting CH to ensure the long-running of a cluster. Simulation results show that BURP provides enhanced throughput, a maximized packet delivery ratio, low energy consumption, and network delay relative to eminent routing protocols.
Keywords: Vehicular ad hoc networks; bi-directional road traffic; routing protocol; emergency message broadcasting; direction-based greedy forwarding
The number of vehicles in urban transport has increased enormously, creating a pressing need for deploying vehicular ad hoc networks (VANETs) . Smart cities, infotainment, detection of travel paths, journey time forecast, and prevention of traffic accidents are the main applications of VANETs. Avoiding traffic casualties is of utmost concern among such applications, as about 1.25 million people die in road accidents each year, while about 20–50 million people are injured or disabled [2,3].
To evade such undesirable circumstances, clustering techniques are adopted in VANETs to disseminate EMs among vehicles (hereinafter nodes). In clustering, identical nodes are grouped and managed by a cluster head (CH) node. The role of clustering is to give sufficient reaction time for nodes to take preventive measures in case of an emergency. EMs are transmitted among the CHs of clusters, and CHs further send the EMs to their member nodes. This helps in reducing transmission overhead by minimizing broadcast overflows. A clustering technique can be built on either a vehicle-to-infrastructure (V2I) model or a vehicle-to-vehicle (V2V) model. Due to the cost of organizing and upholding road-side units (RSUs), V2I models have higher capital and working overhead .
However, most of the V2V clustering techniques presented are designed for uni-directional road traffic in which the direction of nodes is ignored. Such clustering techniques fail to perform in bi-directional scenarios where nodes move in opposite directions causing unstable clusters. A novel clustering technique, namely, probabilistic direction-aware cooperative collision avoidance (P-DACCA), is presented in  for bi-directional highways. Nevertheless, P-DACCA cannot cater to bi-directional road traffic in urban VANETs, which consist of intersections and roundabouts, allowing the mobility of nodes in various directions.
This paper presents a robust clustering protocol, called bi-directional urban routing protocol (BURP), for routing EMs in VANETs as an extension of P-DACCA. The goal of BURP is to create dependable and stable clusters in bidirectional urban VANETs. We introduce an improved k-medoids algorithm that integrates the Hamming distance function as an additional parameter to provide a delicate procedure to create stable clusters. After clustering, the next step is to select a center node as a CH. A median method determines a CH based on an even or odd number of nodes in a cluster.
BURP makes the following contributions:
• A routing protocol is presented to disseminate EMs in bi-directional road traffic through stable clustering for urban VANETs.
• A modified k-medoids algorithm is presented for clustering in bi-directional road traffic.
• A median method is presented for selecting CHs to ensure the long-running of a cluster.
1.3 Paper Organization
The remainder of this work is presented in the following sequence. Section 2 describes related work. Section 3 offers the proposed BURP protocol, and Section 4 evaluates its performance. Finally, Section 5 concludes the paper with directions for future work. Tab. 1 presents a summary of the related work, Tab. 2 shows a list of notations used in this paper, and Tab. 3 presents simulation parameters.
2 Related Work
Creating clusters of nodes instead of each node transmitting the message is vital for efficiently disseminating EMs in VANETs. A CH is responsible for transferring EMs to all other clusters. In VANETs, unexpected vehicular mobility, whether in node speed or node movements in diverse directions, enforces additional constraints on cluster formation strategies .
The works in [6–8,9] present efficient EMs dissemination protocols using cluster-based dissemination methods in an emergency. The technique entails selecting a broadcasting node further away from the origin. The authors in  devised a protocol to eliminate the issues in transmitting EMs using the clustering method. The protocol is applied to properly place distinct nodes in a cluster formation to prevent message collision. A CH is chosen based on certain features of the nodes in a cluster and is responsible for managing intra-cluster transmission and preventing intrusion with neighboring clusters. The disadvantage of this technique is that selecting a new CH takes time, which diminishes the protocol's efficacy.
A learning automata-based opportunistic data aggregation and forwarding (LAODAF) protocol is presented in  for warning propagation in VANETs. The learning automata is placed in the nearby RSU. The RSU gathers and sends the data from various areas and EMs generation. However, delay occurrences degrade the network performance. The authors in  present a novel clustering method, namely, efficient cluster head selection (ECHS), to choose suitable CHs. ECHS selects a centralized node as an ideal CH in the cluster. Hence, CH will remain associated with neighbors for a possibly long time. The impact of node mobility on single-hop cluster durability is studied stochastically in . A stochastic mobility model is used to account for time fluctuations in inter-vehicle distances. To simulate the time changes of a system of distance headways, the authors present a discrete-time taken Markov chain.
An affinity dissemination concept is used in the clustering technique presented in . Due to the high-speed mobility of nodes in VANETs, determining the cluster numbers in advance is difficult. This technique is a many-pass asynchronous procedure that decides whether or not a node should associate with a cluster based on responsibility and availability messages. Contrarily, nodes receive messages that are at the minimum a one-time step elder, which is a significant disadvantage . Hierarchical clustering [14–16] is another widely used clustering technique. This technique can be employed for data transmission or routing with the broader network coverage, even though at the penalty of additional processing transmission overheads. Furthermore, due to the high mobility of nodes in VANETs, it is difficult to identify the morphological cuts in hierarchical clustering for cluster creation, regardless of whether a grouping or division technique is used.
The authors in  present an unclear logic-based technique for creating clusters with a long lifespan. Three parameters are taken into consideration in this technique. Firstly, it combines node relative speeds to their associated CHs. Secondly, it examines a node's number of current links inside a cluster, and thirdly, it considers node safety. This protocol can only be used in uni-directional environments. In the bi-directional settings, however, selecting member nodes with the same speeds with respective CHs may be ineffective because these nodes may travel in opposite directions. This reduces the time it takes for a node to associate with the cluster.
Moreover, the authors of  take connection dependability into account during clustering. However, this strategy assumes fixed advent rates for nodes on a highway, which is unrealistic. An enhanced multi-hop clustering algorithm is presented in . This algorithm improves the transmission procedure for clustering by offering internet connectivity by RSU gateways. However, the increased infrastructure deployment and maintenance expenses remain a drawback of this algorithm. The work in  presents a comparative length-based clustering algorithm that performs poorly in a natural highway environment due to a lack of route assessment. Likewise, to limit the numeral of clusters, the authors in  adopt an optimization-based grey-wolf clustering technique. The approach has a significant computational overhead when identifying aging and weaker nodes.
An eminent clustering protocol, namely, low energy adaptive clustering hierarchy (LEACH) has various multi-hop and single-hop variations suggested in the literature . Quadrature-low energy adaptive cluster hierarchy (FCM-QLEACH)  and LEACH-fuzzy inference system (LEACH-FIS)  are the two current VANET-specific variants. All LEACH variants are energy efficient, which is the primary advantage, but their performance is limited by significant clustering overhead . The authors in  present a similarity function-based normalized multi-dimensional parameter-based affinity propagation clustering (NMDPAPC). In addition, the center-based stable-clustering protocol (CBSC)  achieves clustering by identifying nodes located in the path of a given node's desired location. Nevertheless, in the bi-directional road traffic situation, both CBSC and NMDP-APC may cluster nodes that move in different directions, compromising the cluster firmness. The benefit of this technique is that it provides a maximum packet delivery ratio (PDR) while minimizing communication overhead .
The authors in  propose a new method for data propagation in VANETs based on probabilistic broadcasting. The technique employs directional clustering, which assists in resolving challenges such as extended delay, huge collision rates, and false information sharing in message broadcasting. When a cluster member receives an EM, it sends that to CH along with a determined probability depending on the number of times the same EM is collected during a given period. When a CH receives an EM from its member, it continues to pass it to the clusters traveling in the direction of a target. In , the authors show how spread power control is critical for avoiding saturated channel circumstances and making excellent usage of a channel for safety-related needs. To manage the burden of periodic EMs on the channel, the authors present a disseminated power control approach that depends on a solid fairness criterion, referred to as distributed fair power adjustment for vehicular environments (D-FPAV). The scheme has two advantages: i) more bandwidth is accessible for higher-priority data, such as EMs, and ii) different nodes’ beacons are processed with “equal rights” ensuring the best probable reception within the given bandwidth restrictions . However, high computation degrades the performance of this approach.
A novel position-based routing protocol for VANETs, called traffic dynamism-balanced routing protocol (TDBRP) was presented in  to provide intelligent transportation with increased traffic control and security. An effective junction selection algorithm (EJSA) has been proposed based on traffic dynamism for constructing an ideal route among nodes for efficiently forwarding EMs. EJSA and route framing among junctions are based on information gathered from two-hop neighbors, reducing end-to-end latency and improving the PDR . The authors in  present stable clustering, critical to the network's scalability and robustness. A stable CH guarantees that intra-cluster and inter-cluster communication is kept to a minimum . A deep learning approach is used; namely, long short-term memory (LSTM), trained to detect noise conditions and numerous signals. The use of LSTM significantly reduces the false rate. However, with a high computational requirement, the use of RSUs increases the delay and minimizes the network throughput. Moreover, this is not suitable for bi-directional road traffic [33,34].
A P-DACCA scheme for bi-directional road traffic is designed to avoid collisions on highways. The authors propose a modified k-medoids algorithm for clustering by adding the Hamming distance function as an extra direction-awareness measure. After clustering, reciprocal speeds and distances between nodes are calculated concerning their predicted states. The system then calculates the accident probability concerning the node's expected condition and issues a premature EM once the probability increases a predetermined threshold. However, the additional computation overhead limits its performance. As a result, this scheme is helpful in bi-directional highway scenarios. In bi-directional urban scenarios, P-DACCA is incapable of accommodating continual topological changes. We propose a bi-directional urban routing protocol (BURP) to overcome this issue. BURP is a V2V clustering-based protocol in which CHs are selected using the median for a stable, reliable, and long lifespan of a cluster. Efficient dissemination of EMs is carried out through CHs.
3 Proposed Work
In VANETs architecture, timely dissemination of EMs is critical and necessitates an efficient routing scheme. We first present the system model for bi-directional urban VANETs in the following subsection. The proposed protocol, including dynamic cluster formation, CH selection, and EM dissemination.
3.1 System Model
Fig. 1 shows an overview of the VANETs architecture in a bi-directional urban setting. All nodes moving in the same direction are grouped into numerous clusters, as depicted in Fig. 1. All CHs must be synchronized with each other such that any information from one CH can update all other CHs. When a node needs to broadcast an EM to all nodes, it is sent to its CH. Then the CH transmits to all the nodes associated with it and broadcasts to all other CHs. All CHs broadcast this message to their associated nodes. The proposed protocol makes the following assumptions:
There are two types of vehicles in the proposed protocol: namely, ordinary vehicles (OVs) and CH vehicles. A CH maintains a list of all member nodes connected in a cluster and manages the cluster. A CH can easily manage the aforementioned responsibilities because storage and processing problems are nonexistent in VANETs. Contrarily, OV is any member of the cluster other than CH. The entry list of CHs against each member node of the cluster consists of the node-id, current position, expected-state, and current speed. Any node may be in one of the following states:
• When a node approaches the roundabout, as shown in Fig. 1, it may either join the existing cluster of the same direction or create its cluster containing the nodes in the same direction.
• A node moving with the same speed and direction will keep moving in the same cluster. With time, the speed of the node increases or decreases, which may cause a change in its cluster. In this way, maximum cluster stability is achieved with minimized packet loss.
• While moving beside the roundabout, a node may alter its direction and begin traveling in a different direction. This will bring a change to the cluster for that particular node.
The following subsections present the details of cluster formation in the proposed protocol, including the joining and leaving of nodes from a cluster and the merging and splitting of clusters. The better choice for clustering in the proposed protocol is a k-medoids algorithm. However, the basic k-medoids algorithm is not suitable for clustering bi-directional road traffic. We consider the direction component for bi-directional road traffic in our proposed protocol. Therefore, we present a modified version of the basic k-medoids algorithm for the proposed protocol for clustering. The rest of this section describes different phases involved in the clustering method for the roundabout consisting of bi-directional road traffic using our modified k-medoids algorithm. The revised version of the k-medoids algorithm proposed in this work applies two metrics for creating a cluster: the Euclidean distance and the Hamming distance function. The Euclidean distance calculates the corresponding distance for the candidate node among all the neighboring CHs as
where Ed denotes the Euclidean distance calculated between the candidate node and CHs and the coordinates (x1, y1) and (x2, y2), respectively. For instance, in Fig. 2, the actual position of candidate node A is (14, 3), cluster head B is (8, 3) in cluster C1 and cluster head C is (27, 1) in cluster C2, we can compute the Euclidean distance between nodes A and B and nodes A and C as
Thus, A will join cluster head B of cluster C1 because its distance is shorter than the cluster head C of cluster 2. After calculating the Euclidean distance, the next metric is the Hamming distance function, which covers the bi-directional feature of the road traffic flow. This bi-directional feature of the road traffic permits the nodes to move in both directions. The importance of the Hamming distance function is that it gives the difference between any two objects based on the provided metric. In this work, it is calculated considering the difference in directions between the CH and the candidate node. If the candidate node and the CH have the same direction, the outcome is 1, and if they have the opposite direction, the result is 0 , i.e.,
Here, the Hamming distance function is denoted by Hd, and direction is represented by η regardless of the type of a node i.e., OV or CH.
Depending on these metrics, the association of a candidate node with a cluster holds great importance. For instance, in Fig. 3, assume that the distance between Node A and Cluster C2:CH is 3 m, and Cluster C3:CH is 4 m. By considering only the distance element, the node will register with cluster C2. This should not occur, as Node A and cluster C2 are moving in different directions. Joining C2 has no significance for Node A or cluster C2, destabilizing cluster C2. This work proposes (3), which computes the final distance by combining the relative distance with the direction element to deal with this issue. Applying this principle, the distance between cluster C2:CH and Node A becomes infinity, while cluster C3:CH and Node A remain the same, i.e., 3 m. Therefore, Node A is associated with cluster C3. Hence, the Hamming distance function used in the proposed version of the k-medoids algorithm yields an accurate and stable cluster by attaching a candidate node to a cluster in the same direction. Hence,
where ψ represents the related distance in two consecutive nodes.
The association of a candidate node with a cluster is based on the minimum distance from the CH. The distance is calculated by (3) with each nearby CH. A CH with a minimum distance is computed by (4), and a candidate node is assigned to this cluster. Hence, the status of the candidate node becomes a member node.
where CHmin denotes the least distance CH, Ni is the ithcandidate node and CHi is the ith cluster in the sample space. Algorithm 1 provides phases for a candidate node to be associated with a specific cluster using the proposed variant of the k-medoids algorithm. Algorithm 1 takes M, S, and K as inputs, where S and M are the set of candidate nodes and set of CHs, respectively, and K is the total number of clusters. The output of Algorithm 1 contains K clusters created or changed by the addition of N nodes, where N is the set of member nodes in the cluster.
3.2 Cluster Head Selection
In our proposed protocol, CH is the node with the shortest distance from all the other nodes in the cluster. This reduces the latency in transmission by reducing the number of hops. The selection procedure of CH continues iteratively until a cluster is converged. This convergence process is achieved when no change is observed in two consecutive repetitions . The CH selection process is completed when the first candidate node approaches the roundabout to form its cluster, as explained in the preceding subsection. As the clusters become populated with nodes, the proposed variant of the k-medoids algorithm calculates the median of all clusters. This median is calculated by using (5), also called k-medoids. This k-medoids is a newly selected CH for the cluster. Thus,
where Mc represents the set of CHs, n is the number of nodes in a cluster.
Algorithm 2 affords phases for selecting the CH in a specific cluster using the proposed k-medoids algorithm. Algorithm 2 uses K and N as inputs. The output of this algorithm contains Mc CHs.
In the proposed protocol, we use the Euclidean distance for a node to join a cluster and the Hamming distance function to find the direction of the node. A median method is used to select a center node as the CH in a cluster. This ensures the long-running of a cluster. As a result, a stable and reliable cluster is formed, and EMs are disseminated only by CH in a minimal amount of time.
4 Simulation Results
In this section, we analyze the performance of the proposed routing protocol using the network simulator NS-3.30. Furthermore, we use the simulation of urban mobility (SUMO) to gain trace files analogous to node mobility. The simulation scenario was created to manage EM dissemination in emergencies in an urban bi-directional road traffic model. To provide evidence for the performance of our proposed BURP, the achieved results are evaluated in comparison with EE-FMDRP , EMDV  and, TDBRP . Tab. 3 lists the essential simulation parameters and their values for the performance evaluation of the protocols as mentioned above. Nodes move at random and have omnidirectional antennas.
The movement of the nodes remains bi-directional, with variable acceleration, having the lower and upper limits of 0 m/s and 40 m/s, respectively. The performance assessment metrics consist of throughput, transmission delay, packet delivery ratio, energy consumption rate, and transmission overhead, which are extensively used in the state-of-the-art to measure VANETs protocols for the reliable distribution of EMs [29,30].
4.1 Transmission Delay
The time taken for an EM to reach the destination node from a source node is commonly referred to as the transmission delay. The results for transmission delay as a function of time are shown in Fig. 4a. BURP protocol has a delay of 1.6 milliseconds in the beginning. However, as time goes by, the graph shows that the proposed protocol constantly balances the delay, and it can be shown that the protocol achieves the shortest packet transmission latency. As a result, the BURP becomes a better VANET routing protocol for smart transportation. The total number of transmitting and receiving operations grow as the number of hops in EE-FMDRP, EMDV, and TDBRP increase for the rebuilding process of the path. Because transmitting and receiving processes are time-consuming, increasing the number of these processes degrades the performance of EE-FMDRP, EMDV, and TDBRP. However, BURP reduces this delay by transmitting and receiving operations only among the CHs of a cluster. Therefore, the proposed BURP protocol achieves lower transmission latency than other evaluated protocols, as shown in the graph. The transmission delay can be computed as
where represent the transmission delay, is the delay experienced by a single packet, and represents the total number of packets received .
4.2 Transmission Overhead
The next vital metric to consider when analyzing the performance of a VANETs protocol is transmission overhead. Transmission overhead is the ratio of the total number of beacon messages distributed to the number of information packets forwarded. The transmission overload results are shown in Fig. 4b. The BURP protocol chooses CHs for transmitting EMs, and the CHs are responsible for transmitting within the cluster. Therefore, the proposed protocol avoids the unnecessary delivery of EMs to other nodes in the network. Hence, the process is more energy-efficient. As a result, the proposed protocol achieves the lowest transmission overhead compared with the other protocols. The transmission overhead can be calculated as
where shows the transmission overhead, refers to the total packets sent by all nodes, and total packets received at the destination.
4.3 Throughput Analysis
Fig. 5a shows the results of throughput analysis, which is referred to as the ratio of data packets reaching the target nodes per second to the total number of data packets disseminated by source nodes. The total number of data packets successfully received by a destination node is measured as throughput of the network, a crucial parameter for performance evaluation. The throughput of a network is affected by dropped packets and end-to-end delays. This metric can be calculated as
where denotes the achieved network throughput, refers to the received packets by a destination node, and shows the total number of transmitted packets .
The transmitting and receiving processes increase the number of hops in EEFMDRP, EMDV, and TDBRP for the rebuilding process of the path. As sending and receiving operations are time-consuming, growing the number of these operations degrade the performance of EE-FMDRP, EMDV, and TDBRP. However, BURP decreases the time by sending and receiving processes only among the CHs of clusters. As a result, EMs are delivered to the target nodes in minimal time. Therefore, the proposed protocol has a higher throughput than the others, as indicated in Fig. 5a. As shown in Fig. 5a, the proposed protocol obtains a high throughput value and increases with time.
4.4 Packet Delivery Ratio
The protocol's efficiency has been assessed by calculating the PDR, defined as the ratio of packets successfully reaching the destinations to those transmitted by sources nodes. In urban VANETs, the network connectivity remains greater due to higher network density, which reduces packet loss. In the proposed protocol, EMs are transmitted and received by CHs, which reduces the number of transmissions in the network, and the packet loss. Figs. 5b and 6a show the results of the evaluation. In both results, the graphs clearly show that BURP achieves higher rates of data packet delivery ratio than the other protocols. This demonstrates the efficacy of the proposed protocol in EM dissemination. The PDR metric can be computed as
where denotes the packet delivery ratio, represents packets dropped, and shows the total number of transmitted packets .
4.5 Energy Consumption
Energy consumption is another key metric to consider while evaluating a protocol's performance. The energy usage rate is the ratio of a node's total energy used to the number of data packets gained. The evaluation has been conducted in this case based on the nodes’ mobility speeds. The outcomes are presented in Fig. 6b. The result shows that energy is consumed efficiently by avoiding unnecessary message dissemination to every node in the network. The CHs communicate with other CHs of the clusters in the network. Then cluster heads communicate with their members in a cluster. As a result, the proposed BURP consumes less energy than the other protocols. The energy consumption can be computed as
where shows total energy consumed, shows the total number of packets transmitted, and represented the total number of packets received.
This work proposes an energy-efficient fast message transmission routing protocol for broadcasting EMs in urban VANETs timely and reliable. To avoid accidents and collisions, the protocol comprises an intelligent clustering technique by selecting appropriate intermediates CHs for effectively forwarding EMs to the nodes. Further, to avoid unnecessary transmission, only CHs can transmit the EM to other CHs, and the CHs also transmit the EM to their members. Our findings reveal that creating stable clusters, statistically selecting CHs, taking into account the direction component, and controlling EM transmissions lead to reduced delay, transmission overhead, packet loss, and energy consumption, and increases throughput in bi-directional urban VANETs. The simulation results show that BURP outperforms other eminent VANETs routing protocols by a significant margin. Our future work includes assessing the impact of channel qualities on EM dissemination for highway environments. BURP will be extended to highways scenario with GPS-less localization in the future. Furthermore, future directions include studying the impact of channel conditions on the delivery of warning messages and secure transmission.
Funding Statement: The authors received no specific funding for this research.
Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.
|This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.|