# A Two-Level Communication Routing Algorithm Based on Vehicle Attribute Information for Vehicular Ad Hoc Network

Authors: Chenguang He; Guanqiao Qu; Liang Ye; Shouming Wei
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Recently, the research on the vehicular ad hoc network (VANET) has been paid more attention by researchers with the quick development of the autonomous driving technology. In the VANET, vehicles can communicate with everything through the route established by routing algorithms. However, the topology of the VANET changes fast because the vehicles move fast. Also, as the number of vehicles increases, the probability of data collision and the transmission latency will also increase when communicating. Therefore, the VANET needs a stable, low-latency, and efficient route for vehicles to communicate with each other. However, the existing routing algorithms are either unable to aggregate data or are not suitable for the large-size VANET. In this paper, we consider the vehicle attribute information comprehensively and cluster the vehicles on the road by using the cluster algorithm we propose. We dynamically select the cluster heads at each moment according to their attribute information. We consider all kinds of nodes in the network and the vehicle nodes will communicate with each other through the cluster heads under the two-level communicating algorithm we propose. Compared with the existing cluster routing algorithm, the algorithm we propose is much more suitable for the large-size VANET because the cluster heads do not need a gateway to help them communicate. In the simulation part, we set some real street scenes in Simulation of Urban Mobility (SUMO) and the vehicles can move by the traffic rules like in the real world, which is more suitable for the VANET. After analysing the communication performance in Network Simulator version 2 (NS2), we can get a conclusion that the algorithm proposed is superior to the traditional routing algorithm. The route established by the algorithm we propose is much more stable and efficient. And the latency is also lower than the former.


---

## Body

## 1. Introduction

Recently, there is an unprecedented proliferation in the area of autonomous driving technologies, therefore, causing the great need of traffic for reliable and safe services [1]. Autonomous vehicles can exchange information gathered from local sensors and the cooperative communication mechanism permits the coordination of vehicles, improving traffic efficiency, and people comfort [2]. Therefore, vehicle communication is an important part of intelligent transportation systems and self-driving systems due to the fact that information can be exchanged between vehicles and everything. Vehicle-to-everything (V2X) includes vehicle-to-vehicle (V2V), vehicle-to-pedestrian (V2P), vehicle-to-infrastructure (V2I), and vehicle-to-network (V2N) communications [3, 4]. In vehicular ad hoc network (VANET), a special kind of mobile ad hoc network (MANET), V2X communications can provide vehicles with the key information such as the map about the road, the situation about neighbor vehicles, and the information about traffic. Vehicles and drivers can decide an appropriate driving path. Besides, vehicles can download messages about weather from the internet and some information from other applications to enhance the comfort when driving. Therefore, V2X communication is a very promising technology in vehicular ad hoc network.In VANET, it is important to develop a stable and efficient route to support V2X communications in any time. Services in VANET such as those about vehicle-safety-related communication require V2X messages should be delivered reliably and fast [5]. Actually, besides information about safety, every information should be transmitted in time and correctly by using this route.The routes used for communication are established by a routing protocol, such as AODV (Ad hoc On-demand Vector Routing), DSDV (Destination-Sequenced Distance Vector), and DSR (Dynamic Source Routing). The traditional routing protocols used in VANET can be classified into two kinds of protocols. One is proactive routing protocol, the other one is reactive routing protocols. However, no one kind of these traditional routing protocols is suitable for all VANET scenarios [6]. Also, because vehicles drive in a high speed, the topology in VANET can be very complicated soon [7]. Packets should be delivered in a low latency; otherwise, the information in packet would be useless. Moreover, because some packets may contain important safety information and some information may be about video and audio, the communication route should be stable so that vehicles can receive and decode information in packets successfully. Also, the spectrum resource is more and more precious in the 5th-generation mobile networks. Too many V2X communications at the same time and sensor networks in a small area on the road can cause the link congestion and consume too much energy, respectively, which breach the concept of green communication [8]. Like the communication in the industrial internet of things (IIOT), it is important to allocate the power and resources for the integrated network to decrease the system cost [9]. As a result, VANET needs an efficient communication mechanism to prevent network congestion in order to ensure the reliability of communication between vehicles and other devices. Also, communication with data aggregation can save bandwidth resources and support a large-scale vehicular network [10].Therefore, V2X communications in VANET need a stable, low-latency, and efficient route to exchange information.


## 2. Related Work

Reference [11] introduces an edge computing solution to enhance the efficiency of content delivery. In the architecture proposed, the intelligence at the wireless edge (i.e., base stations and autonomous vehicles) can be made full use of for coordinated content delivery. An edge server is added at each BS to serve as an agent between cloud servers and vehicles for content delivery. Also, the resources at BSs are greater than those on vehicles. Not only can those be utilized to cache contents for all kinds of services usually required but also it can be used to compute the data from vehicles and servers. Therefore, when the density of vehicles grows, this architecture can reduce the burden on cellular network and decrease the transmission delay.Moreover, [12] points out that vehicles may pass through several RSUs due to the high driving speed and the sending back of the computation data output needs to be transmitted through several MEC (mobile edge computing) servers in the traditional communication architecture used edge servers. However, in order to improve the transmission efficiency of the wireless backhauls, the task-input file cannot be transferred between the RSUs. Therefore, this paper introduces a method that data packets can be transferred to the MEC in the farther road in advance by using V2V and V2I communications to reduce the latency of the computation off load.Reference [13] introduces an algorithm based on ant colony optimization (ACO) to avoid congestion accidents when communicating. ACO takes inspiration from the foraging behavior of ants. Ants can mark some favorable paths that could be followed by other members [14]. The iteration count value in each RSU in all the subsets will decrease by time and increase when a vehicle passes by. The shortest route will be found by comparing all RSUs’ iteration counts and the larger the iteration count is, shorter the route is. Thus, after finding the shortest path in each subset, they are connected together between the source and destination to make sure the message can be sent efficientlyThe adaptive quality-of-service (QoS) based routing protocol proposed in [15] can choose the interactions which packets pass to select the route which can fulfill the best QoS by using an ACO-based algorithm. The ACO-based algorithm can explore the available candidate paths by using forward ants and choose the optimal route by using backward ants between two terminal intersections. The local QoS models for the local road segment can be used to estimate real-time pheromone, which can alleviate network congestions and have an efficient communication.In order to avoid congestions and increase the efficiency when communicating, it is important to aggregate data in communications. Vehicles communicating by clusters is one of these methods. Reference [16] points out that the cluster heads (CHs) can perform cooperative spectrum sensing to get available spectrum, which can efficiently deduce the average total throughput and balance the whole system energy. Also, reference [17] implements major routing mechanisms in cluster-based routing protocol (CBRP). In each cluster, there is a cluster head (CH) serving as the relay node which is responsible for forwarding data packets between the source and destination. It maintains a less overlapping 1-hop cluster-head-based cluster structure. Each node can send out “Hello” message including its own information to its 1-hop neighbors. In order to have a greater cluster, the CH’s neighboring CHs could be 2 or 3 hops away and the other nodes in the CH’s route table would be cluster members (CMs). If the destination node is not in the route table of source node, the source node will send a route request (RREQ) to discover the route. The data from the source node and destination node will be transferred through the cluster head and cluster gateway (CGW). CGWs are the cooperative nodes that include their neighboring cluster information and know their 3-hop neighboring CHs. This kind of structure is more stable and efficient than traditional routing protocols and can increase the network traffic load or size.The mobility prediction-based clustering (MPBC) scheme proposed in [18] is designed for ad hoc networks with high-speed nodes which can improve the scalability and stability. The node will periodically exchange “Hello” messages between its neighbors to estimate their relative speeds. In the start of clustering, the node with the smaller speed and the greater number of neighbors in the cluster will be easier to become the CH. During the time when the network maintains the cluster, it will use mobility prediction strategies to extend the connection lifetime for each node and make the clusters more stable. When a CM is going to run out of the limited transmission range, it will choose the cluster that it may stay in for the longest time. When two CHs and their own clusters come into each other’s coverage area, the CH with the smallest relative speed will become the new cluster head of these two clusters. This scheme has longer connection time and can increase the network stability and scalability.In summary, V2X communications in VANET need to establish routes before communicating. The proactive routing protocols such as AODV only find the route to destination when the source needs to communicate. Although this can save the overhead of the network, the transmission delay is high. The reactive routing protocols such as DSDV will maintain all available routes in each node’s routing table by exchanging messages periodically. Although, it is helpful to decrease the communication delay, the overhead of the network is higher. Due to the fact that the VANET has the characteristics of high data capacity, low-latency demand, and high nodes’ speed, it is important to improve the structure of the network or the traditional routing protocols in order to provide VANET with a stable, low-latency, and efficient route for vehicles to communicate with each other.However, although the network added with MEC servers may decrease the transmission delay when communicating, it does not solve the problem of congestions when lots of vehicles communicate with each other in a small area on the road. It is necessary to aggregate data or find a better route for the high number of vehicles in V2X communications to possibly avoid data congestion. Although the routing algorithms added with ACO may find a better route from source to destination, it has the characteristics of high complexity. Because the route in ACO needs much time to accumulate, it is not suitable to use in the VANET whose topology and surrounding scene change rapidly, which is not beneficial for routes to be formed. Finally, although CBRP aggregates the communication data and decreases the possibility of data congestion in a certain degree in V2X communications by clustering the vehicles on the road compared with the traditional routing protocols, the CH is selected only according to the mobility and the number of neighboring vehicles in the limited distance. It does not consider all nodes’ characters comprehensively when selecting the CH. Also, the size of CBRP’s cluster is 1 hop to 2 hop. It is designed for MANET and is not suitable for VANET for the size of cluster in VANET is much bigger than 2 hop. If the cluster size were to be as small as 2 hop, the overhead of the whole network will increase fast as the number of clusters and CHs grows. And the CGW will make the structure more complex.In this paper, we propose a two-level cluster algorithm and a two-level communication routing algorithm. And the major contributions of this paper are as follows.Firstly, the two-level cluster algorithm proposed considers the vehicle nodes’ attribute information comprehensively. It clusters the vehicles on the road with a limited distance threshold and periodically selects the CHs according to the vehicle attribute information such as the vehicle type, the number of neighboring vehicles, the total distance, and the speed at the same time. The first level of network is CH, and the second level is CM. Therefore, it can aggregate the communication data more efficiently and possibly avoid data congestion. Also, this algorithm takes the condition of each node into account.The two-level communication routing algorithm is based on the cluster information from the two-level cluster algorithm. In order to communicate more efficiently, the algorithm does not have the CGW. The algorithm is based on AODV; thus, it could have a bigger size of cluster and a lower overhead which is different from CBRP and more suitable for VANET. After vehicles are clustered, the source vehicle node will communicate with the destination vehicle node through this algorithm.The existing researches on VANET routing algorithms are mostly set on the background of nodes that can move randomly in the scene set, which does not conform to the truth that vehicles can only move in such particular lanes according to the traffic rules under the limited legal speed. This paper utilizes Simulation of Urban Mobility (SUMO) to simulate vehicles’ movements on real road lanes in the real world under the traffic rules to truly show the advantages of the routing algorithm proposed.The rest of this paper is listed below. Section3 describes the two-level cluster algorithm. Section 4 introduces the two-level communication routing algorithm. Section 5 discusses the communication performance results of the routing algorithm proposed and traditional routing algorithm. Section 6 concludes this paper based on the results above.


## 3. Two-Level Cluster Algorithm

In this section, we introduce a cluster algorithm which can cluster the vehicles on the road and select the CHs based on vehicle attribute information. The cluster algorithm executed by vehicles can aggregate communication data with the help of CHs.


### 3.1. The Vehicle Attribute Information

In the exiting cluster algorithms, CHs are selected by only one kind of nodes’ attribute information. Therefore, these algorithms are not suitable to be used in VANET due to the fact that the vehicle nodes in VANET have much more specific information which is different from the nodes in ordinary MANETs.The vehicle attribute information we use in this algorithm is below.The first one is the vehicle typeCi of the vehicle node i. The common three kinds of vehicle type on the road are the buses, the trucks, and the cars. Ci is an important attribute information that differentiates vehicles nodes in VANET from nodes in MANET. The CH serving as buses is the most stable because the buses’ trace is the most stable among these three types of vehicles. The CH serving as cars can cause the least shadow fading when vehicles communicate because the cars’ volume is the smallest, and the trucks’ volume is the biggest among these three types of vehicles. We consider the impact of each kind of vehicle on communication and set the value of Ci in Table 1.Table 1
The value ofCi.
TypeValueBus1Car2Truck3The second one is the number of neighboring vehiclesNi,t. It is the number of neighboring vehicles in the limited distance threshold of the vehicle node i at time t. Once the distance between the source nodes and the destination nodes surpasses the limited distance threshold, the destination nodes cannot decode the packets from source nodes correctly. The limited distance threshold th is 300 m and the size of each cluster is no more than this threshold.The third one is the total distanceDi,t. It is the total distance between vehicle node i and its each neighboring node j. Use the following formula (1) to obtain the total distance Di,t.
(1)Di,t=∑i=1n∑j=1,j≠inxi,t−xj,t2+yi,t−yj,t2,wheren is the total number in the whole scene. xi,t is the coordinate on the x axis of the vehicle node i at time t. xj,t is the coordinate on the x axis of the vehicle node j at time t. yi,t is the coordinate on the y axis of the vehicle node i at time t. yj,t is the coordinate on the y axis of the vehicle node j at time t.The fourth one is the speedMi,t of a vehicle node. It is the distance movement per unit time of the vehicle node i at time t within the algorithm execution interval tim. Because the tim is short, the distance movement per unit time can be approximately regarded as the speed. Use the following formula (2) to obtain the speed Mi,t of a vehicle.
(2)Mi,t=xi,t−xi,t−tim2+yi,t−yi,t−tim2tim,wherexi,t−tim is the coordinate on x axis of the vehicle node i at time t−tim. yi,t−tim is the coordinate on the y axis of the vehicle node i at time t−tim.These four kinds of attribute information in the algorithm proposed are important due to the fact that not only they represent the properties of the vehicles but also they measure the connectivity between different vehicles. It is beneficial for vehicles to communicate through clusters.


### 3.2. Cluster the Vehicles on the Road

In this part, the cluster algorithm will firstly judge the current timet is whether smaller the stop time. If the current time t is 0, it will increase the current time by tim after regarding the current coordinate as the initial coordinate. The algorithm is executed from node zero. During the execution of the cluster algorithm in each interval, it will firstly calculate the distance between a node and the other nodes in the scene. And the nodes will be clustered into a same cluster when the distance between nodes is less than the th. If a node has no neighbors within the th, there will be only one node in this cluster. The algorithm will keep clustering the nodes until all the nodes are clustered. After clustering the nodes, the algorithm will calculate the number of neighboring vehicle nodes Ni,t, the total distance Di,t, and the speed Mi,t of a vehicle node in each cluster at time t. After that, it will select the CHs and the CMs in each cluster at current time t and increase the current time by tim. The details about selecting CHs and CMs will be introduced in the next part. Finally, if the current time t+tim is smaller than the stop time, the algorithm will be executed again.The details about this part are shown in Algorithm1.Algorithm 1: How to cluster the vehicles on the road.
Operation Flow1:Input: the current time, the stop time, and the attribute information2:While the current time is smaller than the stop time3:if the current time is 04:     regard the current coordinate as the initial coordinate5:     increase the current time bytim6:    get the current coordinate of each node7:    calculate the distance between a node and other nodes in the scene8:    cluster the vehicles on the road9:    calculate the number of neighboring vehicle nodes10:      calculate the total distance among each node11:      calculate the speed of a vehicle node in each cluster12:      select the CHs in each cluster at timet13:      increase the current time bytim14:End


### 3.3. Select CHs in Each Cluster

This part is about how the cluster algorithm selects the CHs in each cluster at timet in part 3.2. It will firstly calculate the weighted count wi,t of the vehicle node i at time t based on the four kinds of attribute information above. Use the following formula (3) to calculate the wi,t.
(3)wi,t=λ1×Ci+λ2×Mi,t+λ3×Di,t−λ4×Ni,t,where λi is the weight of each attribute information.From Table1, we can infer that the CH served as the node with the smaller value of Ci may cause the less negative effect when vehicles communicate. Also, the lower the speed of a vehicle node is, the more stable the route established through this node is. Therefore, the CH served as the node with the smaller speed may be beneficial for communication. Moreover, the smaller the total distance Di,t is, the closer the node is to the center of the cluster. Therefore, the route established through the CH served as the node with the smaller total distance may have the lower communication latency. Finally, the more the number of neighboring vehicles Ni,t is, the more neighboring nodes can be covered in the cluster. Therefore, the CH served as the node with the greater number of neighboring vehicles can aggregate more data packets when communicating and the route established through this node can be more efficient. In conclusion, the cluster algorithm will select the node with the smallest weighted count wi,t to be the CH in each cluster at time t.When selecting the CHs at timet, the algorithm will firstly check whether the sequence number of the node is greater than the total number of the nodes. If so, the algorithm will stop and the latest cluster information will be used in the two-level communication routing algorithm next.If the sequence number of the node is smaller than the total number of the nodes, the cluster algorithm will check whether the node has been classified as a CM or CH in any cluster at timet. If the node has been a CM or CH at time t, the cluster algorithm will check the next node. Otherwise, the algorithm will check if the node has neighboring nodes or not at time t. If it has no neighboring nodes, it will be selected to be the CH of itself at time t. If it has neighboring nodes connected to itself and not in any cluster either, the algorithm will compare the weighted count wi,t among these nodes in the cluster and select the node with the smallest weighted count to be the CH in this cluster and the other nodes will become the CMs in this cluster at time t. After that, the algorithm will check the next node and will be executed again.After checking all nodes and selecting CHs in all clusters at timet, the algorithm will increase the current time by tim. If the current time t+tim is still smaller than the stop time, the algorithm in part 3.2 will be executed again.The details in this part which is about selecting the CHs in each cluster at timet is shown in Algorithm 2.Algorithm 2: How the cluster algorithm selects the CHs in each cluster.
Operation Flow1:Input: the weighted count wi,t2:While the sequence number of the node is smaller than the total number3:if the node has not been a CM or CH in any cluster at time t4:if the node has neighboring nodes which are connected to itself and are not in any cluster either at time t5:    compare the weighted count among these nodes in the cluster6:    select the CH and the CMs in this cluster at timet7:else8:    select itself to be the CH9:else10:   continue11:EndThe model in this section about cluster algorithm is shown in Figure1.Figure 1
The model of the cluster algorithm.In Figure1, there are three kinds of vehicles, i.e., cars, buses, and trucks. Also, there are three clusters on the road at current time t. The cluster head is labelled by “CH” in each cluster while others are cluster members in each cluster.


## 3.1. The Vehicle Attribute Information

In the exiting cluster algorithms, CHs are selected by only one kind of nodes’ attribute information. Therefore, these algorithms are not suitable to be used in VANET due to the fact that the vehicle nodes in VANET have much more specific information which is different from the nodes in ordinary MANETs.The vehicle attribute information we use in this algorithm is below.The first one is the vehicle typeCi of the vehicle node i. The common three kinds of vehicle type on the road are the buses, the trucks, and the cars. Ci is an important attribute information that differentiates vehicles nodes in VANET from nodes in MANET. The CH serving as buses is the most stable because the buses’ trace is the most stable among these three types of vehicles. The CH serving as cars can cause the least shadow fading when vehicles communicate because the cars’ volume is the smallest, and the trucks’ volume is the biggest among these three types of vehicles. We consider the impact of each kind of vehicle on communication and set the value of Ci in Table 1.Table 1
The value ofCi.
TypeValueBus1Car2Truck3The second one is the number of neighboring vehiclesNi,t. It is the number of neighboring vehicles in the limited distance threshold of the vehicle node i at time t. Once the distance between the source nodes and the destination nodes surpasses the limited distance threshold, the destination nodes cannot decode the packets from source nodes correctly. The limited distance threshold th is 300 m and the size of each cluster is no more than this threshold.The third one is the total distanceDi,t. It is the total distance between vehicle node i and its each neighboring node j. Use the following formula (1) to obtain the total distance Di,t.
(1)Di,t=∑i=1n∑j=1,j≠inxi,t−xj,t2+yi,t−yj,t2,wheren is the total number in the whole scene. xi,t is the coordinate on the x axis of the vehicle node i at time t. xj,t is the coordinate on the x axis of the vehicle node j at time t. yi,t is the coordinate on the y axis of the vehicle node i at time t. yj,t is the coordinate on the y axis of the vehicle node j at time t.The fourth one is the speedMi,t of a vehicle node. It is the distance movement per unit time of the vehicle node i at time t within the algorithm execution interval tim. Because the tim is short, the distance movement per unit time can be approximately regarded as the speed. Use the following formula (2) to obtain the speed Mi,t of a vehicle.
(2)Mi,t=xi,t−xi,t−tim2+yi,t−yi,t−tim2tim,wherexi,t−tim is the coordinate on x axis of the vehicle node i at time t−tim. yi,t−tim is the coordinate on the y axis of the vehicle node i at time t−tim.These four kinds of attribute information in the algorithm proposed are important due to the fact that not only they represent the properties of the vehicles but also they measure the connectivity between different vehicles. It is beneficial for vehicles to communicate through clusters.


## 3.2. Cluster the Vehicles on the Road

In this part, the cluster algorithm will firstly judge the current timet is whether smaller the stop time. If the current time t is 0, it will increase the current time by tim after regarding the current coordinate as the initial coordinate. The algorithm is executed from node zero. During the execution of the cluster algorithm in each interval, it will firstly calculate the distance between a node and the other nodes in the scene. And the nodes will be clustered into a same cluster when the distance between nodes is less than the th. If a node has no neighbors within the th, there will be only one node in this cluster. The algorithm will keep clustering the nodes until all the nodes are clustered. After clustering the nodes, the algorithm will calculate the number of neighboring vehicle nodes Ni,t, the total distance Di,t, and the speed Mi,t of a vehicle node in each cluster at time t. After that, it will select the CHs and the CMs in each cluster at current time t and increase the current time by tim. The details about selecting CHs and CMs will be introduced in the next part. Finally, if the current time t+tim is smaller than the stop time, the algorithm will be executed again.The details about this part are shown in Algorithm1.Algorithm 1: How to cluster the vehicles on the road.
Operation Flow1:Input: the current time, the stop time, and the attribute information2:While the current time is smaller than the stop time3:if the current time is 04:     regard the current coordinate as the initial coordinate5:     increase the current time bytim6:    get the current coordinate of each node7:    calculate the distance between a node and other nodes in the scene8:    cluster the vehicles on the road9:    calculate the number of neighboring vehicle nodes10:      calculate the total distance among each node11:      calculate the speed of a vehicle node in each cluster12:      select the CHs in each cluster at timet13:      increase the current time bytim14:End


## 3.3. Select CHs in Each Cluster

This part is about how the cluster algorithm selects the CHs in each cluster at timet in part 3.2. It will firstly calculate the weighted count wi,t of the vehicle node i at time t based on the four kinds of attribute information above. Use the following formula (3) to calculate the wi,t.
(3)wi,t=λ1×Ci+λ2×Mi,t+λ3×Di,t−λ4×Ni,t,where λi is the weight of each attribute information.From Table1, we can infer that the CH served as the node with the smaller value of Ci may cause the less negative effect when vehicles communicate. Also, the lower the speed of a vehicle node is, the more stable the route established through this node is. Therefore, the CH served as the node with the smaller speed may be beneficial for communication. Moreover, the smaller the total distance Di,t is, the closer the node is to the center of the cluster. Therefore, the route established through the CH served as the node with the smaller total distance may have the lower communication latency. Finally, the more the number of neighboring vehicles Ni,t is, the more neighboring nodes can be covered in the cluster. Therefore, the CH served as the node with the greater number of neighboring vehicles can aggregate more data packets when communicating and the route established through this node can be more efficient. In conclusion, the cluster algorithm will select the node with the smallest weighted count wi,t to be the CH in each cluster at time t.When selecting the CHs at timet, the algorithm will firstly check whether the sequence number of the node is greater than the total number of the nodes. If so, the algorithm will stop and the latest cluster information will be used in the two-level communication routing algorithm next.If the sequence number of the node is smaller than the total number of the nodes, the cluster algorithm will check whether the node has been classified as a CM or CH in any cluster at timet. If the node has been a CM or CH at time t, the cluster algorithm will check the next node. Otherwise, the algorithm will check if the node has neighboring nodes or not at time t. If it has no neighboring nodes, it will be selected to be the CH of itself at time t. If it has neighboring nodes connected to itself and not in any cluster either, the algorithm will compare the weighted count wi,t among these nodes in the cluster and select the node with the smallest weighted count to be the CH in this cluster and the other nodes will become the CMs in this cluster at time t. After that, the algorithm will check the next node and will be executed again.After checking all nodes and selecting CHs in all clusters at timet, the algorithm will increase the current time by tim. If the current time t+tim is still smaller than the stop time, the algorithm in part 3.2 will be executed again.The details in this part which is about selecting the CHs in each cluster at timet is shown in Algorithm 2.Algorithm 2: How the cluster algorithm selects the CHs in each cluster.
Operation Flow1:Input: the weighted count wi,t2:While the sequence number of the node is smaller than the total number3:if the node has not been a CM or CH in any cluster at time t4:if the node has neighboring nodes which are connected to itself and are not in any cluster either at time t5:    compare the weighted count among these nodes in the cluster6:    select the CH and the CMs in this cluster at timet7:else8:    select itself to be the CH9:else10:   continue11:EndThe model in this section about cluster algorithm is shown in Figure1.Figure 1
The model of the cluster algorithm.In Figure1, there are three kinds of vehicles, i.e., cars, buses, and trucks. Also, there are three clusters on the road at current time t. The cluster head is labelled by “CH” in each cluster while others are cluster members in each cluster.


## 4. Two-Level Communication Routing Algorithm

In this section, we introduce a two-level communication routing algorithm based on the cluster information above. The source node will communicate with the destination node with the help of the reliable CHs in the clusters.The society is stepping into the era of big data, and the spectrum resources are facing serious shortage. Therefore, it is important to guarantee the spectrum access probability of each user in the network [19]. And the algorithm we propose in this section is beneficial for aggregating the data when communicating and saving the precious spectrum resource. Therefore, it can provide the communication with a stable and efficient route.In the exiting routing algorithms such as AODV, DSR, and DSDV, all nodes are in one level; it can cause data packet congestion and even loss when the number of communicating vehicles increases. Also, these routing algorithms can also waste the communication resource because of the lack of data aggregation. Therefore, these routing algorithms need to effectively aggregate the data when communicating.In the exiting cluster routing algorithms such as CBRP, the size of clusters is small and it is suitable for MANETs with small scene. It is not suitable for VANETs because the scene in VANETs may be much greater and much more complex. Also, the CGWs in CBRP may cause the waste of communication resource when communicating. Therefore, these cluster routing algorithms need to be improved in order to adapt to the scene in VANETs.Therefore, we propose a two-level communication routing algorithm based on an existing routing algorithm and the cluster information obtained from the section above to fit in with the needs of the VANETs and the data aggregation.


### 4.1. Route Discovery and Maintenance in AODV

AODV is an on-demand route algorithm. The nodes do not need to maintain the route to destination all the time. The node will discover and maintain the route only when the source node communicates with the destination node. Although AODV uses a broadcast route discovery mechanism like DSR, AODV establishes the route table entries at intermediate nodes dynamically, which can effectively decrease the overhead in packets. Also, AODV utilizes the sequence numbers of packets like DSDV; however, each node in AODV maintains a monotonically increasing sequence number counter [20]. Therefore, the two-level communication routing algorithm proposed is based on AODV.In AODV, the source node will only broadcast RREQ (route request) targeting the destination node when a source node needs a route to destination node. An intermediate node will firstly set up a reverse path to the source node and regard the previous hop of the RREQ as the next hop of this reverse path. If the intermediate node has a valid route to the destination node or the node is the destination node, it will send a RREP (route reply) to the source node via the reverse path. Otherwise, the intermediate node will rebroadcast the RREQ and the other nodes will discard the duplicate copies of the RREQ. A forward path will be successfully established to transfer data packets after the source node receives the RREP from the destination node [21].When a route is broken, the nodes in this route will be notified with RRER (route error) packets which are intended to inform all sources using this failed route and the source nodes will discovery a new route if it is needed [22].


### 4.2. The Two-Level Communication Routing Algorithm

In this part, we will introduce the two-level communication routing algorithm based on AODV and the cluster information.In this algorithm, when the nodeindex receives a RREQ, it will firstly drop this RREQ if it is the source of this RREQ. Otherwise, the node index will set up a valid reverse path rt0 or update the exiting rt0 to the source node. The previous hop of the RREQ is the next hop of this reverse path. In AODV, the node index is the node that is currently executing the algorithm.After the establishment or the update of thert0, the algorithm will read the cluster information from the cluster algorithm in the above section. The algorithm will regard the ith CH as clusteri0 and regard the jth CM in the ith cluster as clusterij. Also, it will regard the CH of index as CHindex.The initial part of the two-level communication routing algorithm is shown in Algorithm3.Algorithm 3: The initial part of the two-level communication routing algorithm.
Operation Flow1:Input: cluster information2:If the node index is the source of the RREQ it received3:  discard this RREQ4:else5:  set up a reverse route or update the exiting reverse route6:  read the cluster information from the cluster algorithm7:EndAfter that, the nodeindex will check whether itself is the destination of the RREQ. And it will regard the prehop of this RREQ as ih−>saddr.Situation 1.
If theindex is the destination of the RREQ, the algorithm will denote the CH of the pre-hop of this RREQ as CH_dst_prehopih−>saddr.Situation 1.1.
If now theih−>saddr is the source of this RREQ, which means that the hop count of the RREQ is only one. Therefore, in order to communicate effectively, the destination node index will send a RREP to the source node directly if they are in the same cluster. If they are not in the same cluster, the algorithm will free this RREQ.Situation 1.2.
If now theih−>saddr is not the source of this RREQ, it means that this RREQ is broadcasted by intermediate nodes. The destination node index will only send a RREP in the following situations.Situation 1.2.1.
The destination nodeindex is the CHindex and at the same time the ih−>saddr is CH_dst_prehopih−>saddr.It means that the node index is the CH of index and the ih−>saddr is the CH of ih−>saddr. It ensures that only the CH can successfully receive and forward the RREQ.Situation 1.2.2.
ih−>saddr is the CHindex. It means that the ih−>saddr is the CH of index. It ensures that the destination node will only receive the RREQ from its CH when the destination node is not a CH.The operation flow about how the destination nodes send the RREP to establish the route is shown in Algorithm4.Algorithm 4: How destination nodes send RREP.
Operation Flow1:Input: cluster information2:If the ih−>saddr is the source of the RREQ it received3:if the ih−>saddr and the node index are in the same cluster4:        nodeindex sends RREP5:        free this RREQ6:else7:        free this RREQ8:else9:if the destination node index is the CHindex and the ih−>saddr is the CH_dst_prehopih−>saddr10:     node index sends RREP11:     free this RREQ12:else13:ifih−>saddr is the CHindex14:       nodeindex sends RREP15:       free this RREQ16:EndAll kinds of situations about the destination node replying a RREP are shown in Figure2. The nodes in the same cluster have the same color.Situation 2.
If theindex is not the destination of the RREQ but the intermediate node has a valid route to the destination, the node index will send a RREP to the source node and also send a GRAT_RREP to the destination node.Situation 3.
If the intermediate nodeindex does not have a valid route to the destination, the algorithm will denote the source node of this RREQ as CH_srcrq−>rq_src and it will also regard the CH of ih−>saddr as CH_relay_prehopih−>saddr. In Situation 3, only the intermediate node which is the CH can broadcast the RREQ successfully.Situation 3.1.
If theih−>saddr is the source node, it means that the intermediate node index is the first intermediate node. The intermediate node index will only broadcast this RREQ in the following situations. It ensures that the first intermediate node can only broadcast the RREQ from the source node which is the CH or the CM of the first intermediate node.Situation 3.1.1.
The source node is the CH of itself.Situation 3.1.2.
The source node and the intermediate nodes are in the same cluster.Situation 3.2.
If theih−>saddr is not the source node, it means that this RREQ reaches the intermediate node index through other intermediate nodes. The intermediate node index will only broadcast the RREQ it received when the ih−>saddr is the CH, namely, the CH_relay_prehopih−>saddr. It ensures that only the intermediate node as the CH can broadcast the RREQ to find the route to the destination from the second intermediate node.Figure 2
All kinds of situations about the destination node replying a RREP.The operation flow about how the intermediate nodes broadcast the RREQ they revive is shown in Algorithm5.Algorithm 5: How intermediate nodes broadcast RREQ.
Operation Flow1:Input: cluster information2:If the intermediate node index has the valid route to the destination3:   nodeindex sends RREP and GRAT_RREP4:   free this RREQ5:else6:if the intermediate node index is the CH7:if the ih−>saddr is the source node8:if the source node is the CH9:       broadcast this RREQ10:         free this RREQ11:else12:if the source node and the node index are in the same cluster13:         broadcast this RREQ14:         free this RREQ15:else16:         free this RREQ17:else18:if the ih−>saddr is the CH of itself19:       broadcast this RREQ20:       free this RREQ21:else.22:       free this RREQ23:else24:    free this RREQ25:EndAll kinds of situations about the intermediate node broadcasting the RREQ are shown in Figure3. The nodes in the same cluster have the same color.Figure 3
All kinds of situations about the intermediate node broadcasting the RREQ.The two-level communication routing algorithm we propose considers all kinds of situations of the source nodes, the destination nodes, and the intermediate nodes.The source node will communicate with the destination node through the CH on the route. The model of this algorithm is shown in Figure4. The communication with the same color is the same.Figure 4
The model of the two-level communication routing algorithm.


## 4.1. Route Discovery and Maintenance in AODV

AODV is an on-demand route algorithm. The nodes do not need to maintain the route to destination all the time. The node will discover and maintain the route only when the source node communicates with the destination node. Although AODV uses a broadcast route discovery mechanism like DSR, AODV establishes the route table entries at intermediate nodes dynamically, which can effectively decrease the overhead in packets. Also, AODV utilizes the sequence numbers of packets like DSDV; however, each node in AODV maintains a monotonically increasing sequence number counter [20]. Therefore, the two-level communication routing algorithm proposed is based on AODV.In AODV, the source node will only broadcast RREQ (route request) targeting the destination node when a source node needs a route to destination node. An intermediate node will firstly set up a reverse path to the source node and regard the previous hop of the RREQ as the next hop of this reverse path. If the intermediate node has a valid route to the destination node or the node is the destination node, it will send a RREP (route reply) to the source node via the reverse path. Otherwise, the intermediate node will rebroadcast the RREQ and the other nodes will discard the duplicate copies of the RREQ. A forward path will be successfully established to transfer data packets after the source node receives the RREP from the destination node [21].When a route is broken, the nodes in this route will be notified with RRER (route error) packets which are intended to inform all sources using this failed route and the source nodes will discovery a new route if it is needed [22].


## 4.2. The Two-Level Communication Routing Algorithm

In this part, we will introduce the two-level communication routing algorithm based on AODV and the cluster information.In this algorithm, when the nodeindex receives a RREQ, it will firstly drop this RREQ if it is the source of this RREQ. Otherwise, the node index will set up a valid reverse path rt0 or update the exiting rt0 to the source node. The previous hop of the RREQ is the next hop of this reverse path. In AODV, the node index is the node that is currently executing the algorithm.After the establishment or the update of thert0, the algorithm will read the cluster information from the cluster algorithm in the above section. The algorithm will regard the ith CH as clusteri0 and regard the jth CM in the ith cluster as clusterij. Also, it will regard the CH of index as CHindex.The initial part of the two-level communication routing algorithm is shown in Algorithm3.Algorithm 3: The initial part of the two-level communication routing algorithm.
Operation Flow1:Input: cluster information2:If the node index is the source of the RREQ it received3:  discard this RREQ4:else5:  set up a reverse route or update the exiting reverse route6:  read the cluster information from the cluster algorithm7:EndAfter that, the nodeindex will check whether itself is the destination of the RREQ. And it will regard the prehop of this RREQ as ih−>saddr.Situation 1.
If theindex is the destination of the RREQ, the algorithm will denote the CH of the pre-hop of this RREQ as CH_dst_prehopih−>saddr.Situation 1.1.
If now theih−>saddr is the source of this RREQ, which means that the hop count of the RREQ is only one. Therefore, in order to communicate effectively, the destination node index will send a RREP to the source node directly if they are in the same cluster. If they are not in the same cluster, the algorithm will free this RREQ.Situation 1.2.
If now theih−>saddr is not the source of this RREQ, it means that this RREQ is broadcasted by intermediate nodes. The destination node index will only send a RREP in the following situations.Situation 1.2.1.
The destination nodeindex is the CHindex and at the same time the ih−>saddr is CH_dst_prehopih−>saddr.It means that the node index is the CH of index and the ih−>saddr is the CH of ih−>saddr. It ensures that only the CH can successfully receive and forward the RREQ.Situation 1.2.2.
ih−>saddr is the CHindex. It means that the ih−>saddr is the CH of index. It ensures that the destination node will only receive the RREQ from its CH when the destination node is not a CH.The operation flow about how the destination nodes send the RREP to establish the route is shown in Algorithm4.Algorithm 4: How destination nodes send RREP.
Operation Flow1:Input: cluster information2:If the ih−>saddr is the source of the RREQ it received3:if the ih−>saddr and the node index are in the same cluster4:        nodeindex sends RREP5:        free this RREQ6:else7:        free this RREQ8:else9:if the destination node index is the CHindex and the ih−>saddr is the CH_dst_prehopih−>saddr10:     node index sends RREP11:     free this RREQ12:else13:ifih−>saddr is the CHindex14:       nodeindex sends RREP15:       free this RREQ16:EndAll kinds of situations about the destination node replying a RREP are shown in Figure2. The nodes in the same cluster have the same color.Situation 2.
If theindex is not the destination of the RREQ but the intermediate node has a valid route to the destination, the node index will send a RREP to the source node and also send a GRAT_RREP to the destination node.Situation 3.
If the intermediate nodeindex does not have a valid route to the destination, the algorithm will denote the source node of this RREQ as CH_srcrq−>rq_src and it will also regard the CH of ih−>saddr as CH_relay_prehopih−>saddr. In Situation 3, only the intermediate node which is the CH can broadcast the RREQ successfully.Situation 3.1.
If theih−>saddr is the source node, it means that the intermediate node index is the first intermediate node. The intermediate node index will only broadcast this RREQ in the following situations. It ensures that the first intermediate node can only broadcast the RREQ from the source node which is the CH or the CM of the first intermediate node.Situation 3.1.1.
The source node is the CH of itself.Situation 3.1.2.
The source node and the intermediate nodes are in the same cluster.Situation 3.2.
If theih−>saddr is not the source node, it means that this RREQ reaches the intermediate node index through other intermediate nodes. The intermediate node index will only broadcast the RREQ it received when the ih−>saddr is the CH, namely, the CH_relay_prehopih−>saddr. It ensures that only the intermediate node as the CH can broadcast the RREQ to find the route to the destination from the second intermediate node.Figure 2
All kinds of situations about the destination node replying a RREP.The operation flow about how the intermediate nodes broadcast the RREQ they revive is shown in Algorithm5.Algorithm 5: How intermediate nodes broadcast RREQ.
Operation Flow1:Input: cluster information2:If the intermediate node index has the valid route to the destination3:   nodeindex sends RREP and GRAT_RREP4:   free this RREQ5:else6:if the intermediate node index is the CH7:if the ih−>saddr is the source node8:if the source node is the CH9:       broadcast this RREQ10:         free this RREQ11:else12:if the source node and the node index are in the same cluster13:         broadcast this RREQ14:         free this RREQ15:else16:         free this RREQ17:else18:if the ih−>saddr is the CH of itself19:       broadcast this RREQ20:       free this RREQ21:else.22:       free this RREQ23:else24:    free this RREQ25:EndAll kinds of situations about the intermediate node broadcasting the RREQ are shown in Figure3. The nodes in the same cluster have the same color.Figure 3
All kinds of situations about the intermediate node broadcasting the RREQ.The two-level communication routing algorithm we propose considers all kinds of situations of the source nodes, the destination nodes, and the intermediate nodes.The source node will communicate with the destination node through the CH on the route. The model of this algorithm is shown in Figure4. The communication with the same color is the same.Figure 4
The model of the two-level communication routing algorithm.


## 5. Simulation Results

In this section, vehicles will communicate with each other through the two-level communication routing algorithm and the traditional AODV routing algorithm by the help of NS2 (Network Simulator version 2). And we choose some real street scenes to simulate the movement of vehicles in real world by using SUMO (Simulation of Urban Mobility). SUMO is an open-source traffic simulator. We compare the communication performance of the two-level communication routing algorithm proposed with that of the traditional routing algorithm in order to verify the reasonability and superiority of the algorithm proposed.We choose three kinds of real street scenes, namely, the one-lane road, the two-lane road, and the two-lane intersection. The specific situation is shown in Figure5.Figure 5
Three kinds of real street scenes.
(a)
The one-lane road(b)
The two-lane road(c)
The two-lane road intersectionThe parameters of the communication are shown in Table2.Table 2
The parameters of the communication.
ParameterValueThe number of vehicles10, 20, 30, 40, 50, 60, 70The type of vehicles3The maximum of the limited speed on lanes (m/s)5, 7.5, 10, 12.5, 15, 17.5, 20The size of the scene1100m×1100mThe stop time (s)300.0MAC protocol802.11Routing algorithmAODV, the algorithm we proposeTransport layer protocolTCPThe rate of communication nodes0.5Algorithm execution intervaltim (s)1The limited distance thresholdth (m)150Use the following formulas (4), (5), and (6) to calculate the rate of packet loss L, the average transmission delay T, and the proportion of normalized routing overhead O, respectively.
(4)L=ThetotalnumberofpacketsreceivedThetotalnumberofpacketssent,(5)T=ThedurationbetweenthefirstandthelastpacketThetotalnumberofpacketssent,(6)O=ThenumberofroutingpacketsThetotalnumberofpacketssent.Figure6 shows the communication performance of the two routing algorithms on the condition that the maximum of the limited speed is 15 m/s.Figure 6
The communication performance of the two routing algorithms on the condition that the maximum of the limited speed is 15 m/s.
(a)
The rate of packet loss(b)
The average transmission delay(c)
The proportion of normalized routing overheadFigure7 shows the communication performance of the two routing algorithms on the condition that the number of vehicles is 60.Figure 7
The communication performance of the two routing algorithms on the condition that the maximum of the number of vehicles is 60.
(a)
The rate of packet loss(b)
The average transmission delay(c)
The proportion of normalized routing overheadIn the real-world scenes, the distance among the vehicles is close like the distance in the real world. Also, the vehicles move according to traffic rules in the real world. Moreover, there will always be the same traffic jam or smoothness which is similar to the real world, as well as there will often be a large number of vehicles that are close communicating at the same time. Therefore, the real-world scenes we set are more suitable to simulate the communication in VANET than the random moving scenes used in other researches. Although, the data fluctuates slightly, it is conceivable because the curves have the same trend since the two algorithms use the same files when simulating.From the curves above, the following conclusions can be drawn.


### 5.1. The Rate of Packet Loss

On the condition that the maximum of the limited speed on the lane is same, the rate of packet loss of the algorithm we propose is much more stable as the number of vehicles increases. And the rate is also smaller than the traditional AODV. The average value is reduced about 1.5%.On the condition that the number of vehicles is the same, the rate of packet loss of the algorithm we propose is smaller than the traditional AODV. The average value is reduced about 1%.Therefore, the route established by the two-level communication algorithm we propose is much more stable than the traditional routing algorithm.


### 5.2. The Average Transmission Delay

On the condition that the maximum of the limited speed on the lane is same, the average transmission delay is smaller than the traditional AODV.On the condition that the number of vehicles is same, the average transmission delay is smaller than the traditional AODV.The average value is both reduced about 100 ms in both conditions.Therefore, the route established by the two-level communication algorithm we propose has a lower latency than the traditional routing algorithm.


### 5.3. The Proportion of Normalized Routing Overhead

Compared to traditional AODV, the proportion of normalized routing overhead of the two-level communication routing algorithm is much more stable and smaller on the both conditions. The average value is both reduced about 0.3 in the both conditions.Therefore, the route established by the two-level communication algorithm we propose is much more efficient than the traditional routing algorithm.Above all, the two-level communication algorithm is better than the traditional routing algorithm in real street scenes. This algorithm establishes a route which has a low rate of packet loss and average transmission delay to communicate with low routing overhead and meets the need of a stable low-latency and efficient route for communication in VANET.


## 5.1. The Rate of Packet Loss

On the condition that the maximum of the limited speed on the lane is same, the rate of packet loss of the algorithm we propose is much more stable as the number of vehicles increases. And the rate is also smaller than the traditional AODV. The average value is reduced about 1.5%.On the condition that the number of vehicles is the same, the rate of packet loss of the algorithm we propose is smaller than the traditional AODV. The average value is reduced about 1%.Therefore, the route established by the two-level communication algorithm we propose is much more stable than the traditional routing algorithm.


## 5.2. The Average Transmission Delay

On the condition that the maximum of the limited speed on the lane is same, the average transmission delay is smaller than the traditional AODV.On the condition that the number of vehicles is same, the average transmission delay is smaller than the traditional AODV.The average value is both reduced about 100 ms in both conditions.Therefore, the route established by the two-level communication algorithm we propose has a lower latency than the traditional routing algorithm.


## 5.3. The Proportion of Normalized Routing Overhead

Compared to traditional AODV, the proportion of normalized routing overhead of the two-level communication routing algorithm is much more stable and smaller on the both conditions. The average value is both reduced about 0.3 in the both conditions.Therefore, the route established by the two-level communication algorithm we propose is much more efficient than the traditional routing algorithm.Above all, the two-level communication algorithm is better than the traditional routing algorithm in real street scenes. This algorithm establishes a route which has a low rate of packet loss and average transmission delay to communicate with low routing overhead and meets the need of a stable low-latency and efficient route for communication in VANET.


## 6. Conclusion

In this paper, we cluster the vehicles on the roads by comprehensively considering their most attribute information. We also carefully select the CH in each cluster every time.The vehicles can communicate with each other by using the two-level communication routing algorithm proposed in VANET. We consider all kinds of nodes in the VANET. Therefore, the source nodes will successfully communicate with the destination nodes through the CHs. The algorithm proposed is based on the routing algorithm AODV and the cluster information. Not only can it aggregate the communication data and save more precious communication resources than traditional one-level algorithms but also it can be more suitable for the VANETs, which have a much bigger size than the MANETs, compared with the existing cluster routing algorithms.Also, because the vehicles move by the traffic rules in the real world, the real street scenes we set in the simulation is more suitable than the random moving scenes in other researches on VANET communication. From the simulation results, we can get the conclusion that the rate of packet loss, the average transmission delay, and the proportion of normalized routing overhead are all superior to the traditional routing algorithm. The route established by the algorithm we propose is much more stable and much more efficient than the traditional routing algorithm. And it also has a lower latency. Therefore, the algorithm we propose meets the need of a stable low-latency and efficient route for communication in VANET.



---

*Source: 6692741-2021-02-25.xml*