# Efficient and Reliable Cluster-Based Data Transmission for Vehicular Ad Hoc Networks

Authors: Xiang Ji; Huiqun Yu; Guisheng Fan; Huaiying Sun; Liqiong Chen
Journal: Mobile Information Systems
 (2018)

---

## Abstract

Vehicular ad hoc network (VANET) is an emerging technology for the future intelligent transportation systems (ITSs). The current researches are intensely focusing on the problems of routing protocol reliability and scalability across the urban VANETs. Vehicle clustering is testified to be a promising approach to improve routing reliability and scalability by grouping vehicles together to serve as the foundation for ITS applications. However, some prominent characteristics, like high mobility and uneven spatial distribution of vehicles, may affect the clustering performance. Therefore, how to establish and maintain stable clusters has become a challenging problem in VANETs. This paper proposes a link reliability-based clustering algorithm (LRCA) to provide efficient and reliable data transmission in VANETs. Before clustering, a novel link lifetime-based (LLT-based) neighbor sampling strategy is put forward to filter out the redundant unstable neighbors. The proposed clustering scheme mainly composes of three parts: cluster head selection, cluster formation, and cluster maintenance. Furthermore, we propose a routing protocol of LRCA to serve the infotainment applications in VANET. To make routing decisions appropriate, we nominate special nodes at intersections to evaluate the network condition by assigning weights to the road segments. Routes with the lowest weights are then selected as the optimal data forwarding paths. We evaluate clustering stability and routing performance of the proposed approach by comparing with some existing schemes. The extensive simulation results show that our approach outperforms in both cluster stability and data transmission.


---

## Body

## 1. Introduction

Vehicular ad hoc network (VANET) is the foundation for the intelligent transportation systems (ITSs), which aims at achieving seamless Internet connectivity between vehicles on the road [1]. With the developments of intelligent vehicle and new generation wireless communication techniques, vehicles equipped with wireless interfaces are able to provide ITS services [2] such as traffic monitoring, vehicle navigation [3], nearby information services, and mobile vehicular cloud computing.Therefore, the creation of a stable network and communication management is the most challenging task due to the high mobility and uneven spatial distribution of vehicles in VANETs. The clustering technology is testified to be a promising solution to improve routing reliability and scalability by organizing similar vehicles into several virtual groups, called clusters [4]. Each cluster has a capital vehicle, named cluster head, which is responsible for managing communication in the cluster. Vehicles of a cluster can communicate directly via an intracluster communication, while vehicles in different clusters may achieve intercluster communication through cluster heads.The originally notable clustering algorithms were designed for mobile ad hoc networks (MANETs) [4], such as the popular lowest identifier (LID) [5] and Mobility Clustering (MOBIC) [6]. Later, several other algorithms were designed for clustering in MANET. Recently, some of those algorithms were implemented in VANETs. However, due to the characteristic mobility and channel conditions of VANET, these approaches should be adapted according to the unique properties.Clustering algorithms proposed for VANETs are used in communication networks to partition similar vehicles into clusters [7]. Therefore, clustering techniques can effectively limit the channel contention among cluster members to ensure fair channel access. Moreover, under the management of the cluster head, clustering algorithms can provide spatial reuse of resources such as bandwidth [8]. Given the high mobility of VANETs, how to select the cluster head and how to improve cluster stability become tough challenges.Based on VANETs technology, numerous applications have been developed for the ITS. A typical kind of application is to disseminate safety messages among vehicles, including accident warning and congestion information [9, 10]. Another kind of application, infotainment, is also important for successful VANET deployment [11]. Infotainment services provide more pleasurable experience for both drivers and passengers with various applications, such as nearby information access and multimedia application [12].To serve the infotainment services in urban VANET, this paper proposes a new LREL-based clustering scheme with the purpose of establishing a stable virtual network for data transmission. In order to form stable clusters, we propose an LLT-based neighbor sampling scheme to filter out unstable neighbor vehicles. Different from previous clustering schemes which focus on vehicular mobility, we propose new metric link reliability (LREL) for cluster head selection. The cluster heads are selected in a distributed way. In addition, we propose a routing protocol by using the proposed clustering architecture. We select bridge nodes at intersections to connect clusters in street scenarios. The bridge node acts as the routing path decision maker by monitoring the delay to incur for data transmission over road segments.The contributions of this paper are mainly listed as follows:(i)
We propose an LLT-based neighbor sampling scheme to filter out the redundant unstable neighbors. A stable neighbor set is selected as a basis of clustering procedures.(ii)
We propose a new LREL-based clustering approach with the purpose of establishing a stable virtual network for efficient and reliable data transmission in urban VANET.(iii)
We propose a routing protocol for urban VANET by utilizing the structure constructed by LRCA. The protocol constructs routing path via the bridge node at intersection.(iv)
We analyze the performance of the proposed scheme by considering clustering performance metrics and routing metrics, including packet delivery ratio, end-to-end delay, and control overhead and clustering stability, by comparing with some existing cluster-based schemes.The rest of the paper is organized as follows: Section2 gives a brief description of related works. Section 3 describes the system model. Section 4 presents the proposed link reliability-based clustering scheme. Section 5 shows the data transmission utilizing the proposed clustering architecture. Next, Section 6 shows simulation results of the proposed scheme. Finally, conclusions are presented in Section 7.


## 2. Related Work

The original clustering algorithms are proposed in the late 1980s. Since then, a large amount of cluster-oriented researches have been introduced to MANETs in general and VANETs in particular [4]. Vehicle clustering is a potential approach to improve the scalability of networking protocols for VANET scenarios. For cluster-based routing protocols, cluster heads take responsibilities for the discovery and maintenance of routing paths, which reduce the control overhead to a great extent [13]. Due to the high-speed mobility of vehicles, network topology changes frequently [14]. Under this circumstance, the cluster maintenance cost increases significantly. Therefore, how to form the stable clusters and maintain their stability during communication are a vital issue in clustering techniques for VANETs.Many clustering algorithms designed for VANETs have been proposed based on mobility metrics for cluster formation mechanisms. The mobility features, including speed, direction, and location of vehicles, are very important for VANET clustering procedures. Kayis and Acarman [15] proposed a passive clustering algorithm based on predefined speed intervals. They organize the vehicles within the same speed interval into groups. However, the speed interval is not a good metric for assessment because two vehicles with very similar speed around the interval gap might be divided into different clusters. Chen et al. [16] used the distance-based criteria in the cluster construction algorithms. Furthermore, they employ a central server to manage the cluster merging and splitting events. Shea et al. [17] proposed a distributed mobility-based clustering algorithm based on a data clustering technique called affinity propagation. They use the metric of vehicular position and mobility in cluster creation procedure by combining the current and future positions.Some other clustering mechanisms have been proposed for VANET based on a sum of weighted values. Wang et al. [18] proposed a priority-based clustering approach. The priority is calculated according to the estimated travel duration and speed deviation. Almalag Mohammad et al. [19] presented a lane-based clustering algorithm which selects the vehicle as the cluster head with the highest cluster head level (CHL). CHL is a hybrid metric combining the condition of traffic flow, relative speed, and relative position of the vehicle. Morales et al. [20] proposed the clustering algorithm based on the destination of vehicles. According to their mechanism, vehicles with similar destinations are more likely to form a cluster. The weighted metric is computed as the combination of the current position, relative speed, relative destination, and final destination of vehicles.Clustering algorithms for VANET can be categorized into two classes of one-hop clustering and multihop clustering. The aforementioned algorithms [16, 17, 19, 20] are based on single-hop clusters in which the cluster members are one-hop away from the CH. Vehicles only join the clusters where the CH is in its local vicinities. One-hop cluster topology can reduce the cluster re-affiliation and decrease cluster maintenance overhead because fewer information exchanges are required [21]. However, the transmission range and density of vehicles affect the size of cluster. In a high vehicular density, data collision may happen in the clusters. On the contrary, a vehicle may fail to detect neighbors in very low density. Recently, plenty of works have been proposed for multihop clustering algorithms. Wolny [22] proposed MDMAC, which is a modification of DMAC. MDMAC is able to form k-hop clusters by introducing the TTL (time-to-live) parameter in message delivery. Zhang et al. [23] proposed a multihop clustering scheme for VANETs. The multihop clusters are constructed based on the relative mobility between vehicles in multihop distance. Ucar et al. [9] proposed a novel multihop clustering scheme, known as VMaSC, which selects CHs based on relative mobility with respect to its neighbors. VMaSC reduces overhead during cluster formation by introducing a direct connection to the neighbor which is already a cluster head or a cluster member, instead of connecting to the CH multihops away. Further, the VMaSC claims to be the first multihop clustering algorithm which is analyzed under a realistic scenario. Ziagham and Noorimehr [24] proposed a single-hop clustering approach named MOSIC based on the changes of relative vehicular mobility. It uses the Gauss–Markov mobility (GMM) model for mobility predication and makes vehicle be able to prognosticate its mobility relative to its neighbors.In recent years, some researchers build up semiclusters for VANET scenarios. Zhang et al. [25] proposed a novel variant of cluster, which called the microtopology (MT). The MT acts as a basic component of routing paths which consists of vehicles and wireless links among vehicles along the street. Togou et al. [26] proposed SCRP, which is an approximate cluster-based routing protocol based on connected dominating set (CDS). SCRP selects a small number of vehicles as dominating vehicles to form a virtual backbone in the network. Lin et al. [27] designed a moving-zone-based architecture for data delivery in VANETs. Similar to cluster formation, the moving zone is self-organized by vehicles which have similar movement patterns. Rivoirard et al. [28] proposed the chain-branch-leaf (CBL) clustering scheme which combines the information on road configuration, vehicle mobility, and link quality. CBL builds a stable vehicular network infrastructure by selecting vehicles with lower speed in the same traffic direction to form a stable backbone of branch nodes named Chain.Data transmission over vehicular networks poses a number of challenges and has been widely studied. He et al. [29] proposed a SDN-based wireless communication solution to manage the network resources, which can schedule different network resources and minimize communication cost. Zeng et al. [30] proposed a channel prediction-based scheduling strategy for cooperative data dissemination in VANET, which reduces communication overhead and the data dissemination delay. Zhu et al. [31] proposed a distributed data replication algorithm with the idea of letting the data carrier distribute the data dissemination tasks to multiple nodes to speed up the dissemination process.In the literature, clustering algorithms have been proposed for the purpose of load balancing, quality-of-service support, and data transmission in VANET scenario [2]. The built up clusters can serve as a hierarchical infrastructure-like overlay on top of an underlying ad hoc network, which can be used to route packets [4]. There have been some routing-oriented clustering algorithms which include both clustering and routing algorithms. For example, Song et al. [32] proposed a cluster-based directional routing protocol for VANETs which considers moving directions for cluster head selection. Ohta et al. [33] formed the clusters using position and direction information of vehicles. Unlike these researches, we consider the reliability of links between vehicles. We put up a new metric, named LREL, for cluster head selection. In addition, we propose a LLT-based neighbor sampling scheme to filter out unstable neighbors, which can reduce unnecessary message exchanges.


## 3. System Model

The prominent characteristics of VANET, including the high mobility and the uneven spatial distribution of vehicles, lead to frequent changes in the topologies and disconnections of the network. To solve these problems, we propose a clustered VANET structure to provide reliable connectivity for a group of vehicles. Figure1 shows the general system architecture for vehicular service scenarios where vehicles are grouped into multiple moving clusters. Each cluster contains a capital vehicle (cluster head) which is responsible for managing information about the cluster members as well as data transmission.Figure 1
Cluster-based VANET architecture for vehicular service scenarios.In this paper, we propose a comprehensive cluster-based data transmission approach with pure vehicle-to-vehicle (V2V) communication type being considered. We assume that each vehicle has a unique identity and is equipped with an onboard unit (OBU). The GPS service is available for obtaining basic information, including vehicle’s current location, velocity, and moving direction. Vehicles exchange their information with one another through beacon messages. The beacon message is broadcasted and collected at every beacon interval, which includes vehicle’s identifier, current position, current velocity, moving direction, vehicle’s current state, and cluster head’s identifier if it is a cluster member.In the proposed cluster algorithm, each vehicle may be in one of the following four states:(i)
Initial node (IN): Initial state of the vehicles which do not belong to any cluster.(ii)
Cluster head (CH): The state in which the vehicle acts as the leader of a cluster.(iii)
Cluster member (CM): The state in which the vehicle is attached to an existing CH.(iv)
Candidate cluster member (CCM): The state in which the vehicle intends to be a CM of an existing cluster before receiving a confirmation message.The transitions among these states are triggered by different events. The details of the state transition process are presented in the following section. The notation used in this paper is presented in Table1.Table 1
Notations.
Notation
Description
IN
Initial node
CH
Cluster head
CM
Cluster member
CCM
Candidate cluster member
R
Communication range
V
i
Vehiclei; i is the ID of vehicle
LLT
i
j
Link lifetime betweenVi and Vj
LREL
i
Link reliability metric ofVi
PN
i
Potential neighbor set ofVi
SN
i
Stable neighbor set ofVi
SN
i
j
Entry ofVj in SNi
State
V
i
State ofVi
IN_TIMER
Initial timer for gathering information
JOIN_TIMER
Join response timer
CH_TIMER
Cluster head selection timer
CH_ACK
Cluster head acknowledgement message
JOIN_REQ
Join request message
JOIN_RESP
Join response message
MERGE_REQ
Cluster merging request message
MERGE_RESP
Cluster merging response message
MERGE_ACK
Cluster merging acknowledgment message
CM_LIST
i
Cluster member list inVi
NUM_CM
V
i
Number of vehicles inCM_LISTi
MAX_CM
Maximum number of vehicles a CH can serve
N
pm
Potential merged cluster size
δ
s
Time threshold for neighbor sampling
δ
m
Time threshold for cluster merging
δ
i
Time threshold for isolated CH


## 4. Vehicle Clustering

This paper proposes a link reliability-based clustering algorithm (LRCA) for urban VANETs. The LRCA is designed to provide efficient and reliable data transmission across the urban VANETs. Before clustering, we propose a novel LLT-based neighbor sampling strategy to filter out the redundant unstable neighbors. The proposed clustering scheme mainly composes of three parts: cluster head selection, cluster formation, and cluster maintenance. The general procedural flow of our proposed clustering algorithm is presented in Figure2.Figure 2
The general procedural flow of LRCA.


### 4.1. LLT-Based Neighbor Sampling

In VANET, vehicles exchange and collect information about their one-hop vicinities through periodic beacon messages. After receiving the beacons, each vehicle constructs the potential neighbor (PN) set [34]. However, not all the vehicles in PN are ideal for clustering. In order to improve the stability of clusters, this paper introduces an LLT-based neighbor sampling process to select a stable neighbor (SN) set from PN.Link lifetime (LLT) [35], also called link expiration time (LET), represents the predicted duration time that two adjacent vehicles remain connected. Equation (1) defines LLT calculation. Δvij and Δdij represent the difference of velocity and distance between Vi and Vj, respectively. R denotes the transmission range of a vehicle. The LLT is introduced to evaluate the link sustainability. The link is more sustainable with a larger LLT value.(1)LLTij=Δvij⋅R−Δvij⋅ΔdijΔvij2.The detail of the sampling process is presented in Algorithm1. At the beginning, the system starts a timer (IN_TIMER) for gathering information. The vehicle in SN is defined as the neighboring vehicle which is going to have a constant connection for a predetermined time threshold δs. For each vehicle Vi, it maintains a set of stable neighbors SNi, which contains several entries SNij of vehicle Vj.Algorithm 1: LLT-based neighbor sampling.
Input: PNi;
Output: SNi;
(1)
while IN_TIMER>0 do
(2)
for each vehicle Vj∈PNi do
(3)
if Vi receives a Beacon message from Vj then
(4)
Vi calculates LLTij;
(5)
end if
(6)
if LLTij>δs then
(7)
if Vj∈SNi then
(8)
Vi updates SNij
(9)
else
(10)
Vi adds a new SNij to SNi
(11)
end if
(12)
end if
(13)
end for
(14)
end while


### 4.2. Link Reliability Metric

The link reliability model for communication links between two vehicles in urban VANET is given in [36]. The network connectivity status is mainly determined by the velocity distribution over the vehicular traffic flow. The basic link reliability model is defined as the conditional probability in the following equation which describes the probability of the continuous link connectivity between two vehicles over a specified time duration:(2)rl=Plcontinues  tot+LLTlis  available  att,where rl represents the reliability of the link and l is the particular link between two vehicles. LLT indicates the prediction interval of link duration from time t. Equation (2) shows that if the link l is available at time t, the link will be available until t+LLT.The velocity of vehicles is the main parameter to calculate the link reliability. In this paper, we assume that the velocity satisfies anormal distribution [37]. Then the probability density function of the velocity gv can be calculated as(3)gv=1σ2πe−v−μ2/2σ2,where μ and σ denote the mean and standard variation, respectively. Let Δvij be the relative velocity between vehicles Vi and Vj, that is, Δvij=vi−vj. Since vi and vj satisfy the normal distribution, Δvij should also obey the law of normal distribution. Let fT be the probability density function of the communication duration T. fT can be calculated as(4)fT=4RσΔvij2π1T2e2R/T−μΔvij2/2σΔvij2,forT≥0,where μΔvij and σΔvij denote the mean and the standard variation of relative velocity between vi and vj , respectively. Then, we can obtain the link reliability value rlij by integrating fT in (4) from time t to t+T, as shown in the following equation:(5)rtlij=∫tt+LLTfTdT,if  LLT>0,0,otherwise.By using the Gauss error function Erf [38], the integral in (5) can be obtained as follows:(6)rtlij=Erf2R/t−μΔvijσΔvij2−Erf2R/t+LLT−μΔvijσΔvij2,when    LLT>0.The Erf function is calculated as follows:(7)Erfx=2π∫0xe−η2dη,−∞<x<+∞.For a particular vehicle, it may have connections with multiple vehicles in the surrounding zone. The network connectivity could be diverse due to the complex traffic conditions. Therefore, we only consider those vehicles in the SN while defining the metric LREL:(8)LRELit=∑vj∈SNirtlij.


### 4.3. Cluster Head Selection

This section describes the method whereby a CH is selected. We assess the fitness of a vehicle to act as a cluster head based on link reliability. The calculation of LREL has been presented in the previous section.As shown in Algorithm2, a vehicle Vi in the IN state firstly tries to join an existing cluster by listening to the CH_ACK message or beacon message from a CH during the time period CH_TIMER. If Vi fails to join an existing cluster when CH_TIMER expires, Vi calculates a weighted metric, LRELi, according to (8). Then Vi compares LRELi with the neighbors in SNi. If it turns out that Vi has the highest value of LREL, Vi broadcasts CH_ACK information to claim itself to be a CH.Algorithm 2: Cluster head selection.
Input: Set of IN
Output: Set of CCM,  CH
(1)
for each vehicle Vi where StateVi=IN do
(2)
Vi starts CH_TIMER
(3)
while CH_TIMER>0 do
(4)
if Vi receives CH_ACK or Beacon from CHj then
(5)
StateVi←CCM
(6)
goto Cluster Formation
(7)
end if
(8)
end while
(9)
if Vi does not receive CH_ACK then
(10)
Vi calculates LRELi
(11)
if LRELi≥MAXVm∈SNiLRELm then
(12)
StateVi←CH
(13)
Vi broadcasts CH_ACK
(14)
end if
(15)
end if
(16)
end for


### 4.4. Cluster Formation

As shown in Algorithm3, the vehicle in the IN state will join a cluster if it receives the CH_ACK message or beacon message from a CH. The vehicle first transfers its state to CCM, then sends a JOIN_REQ message to the corresponding CH, and starts a join response timer (JOIN_TIMER). On reception of the JOIN_RESP message, the vehicle changes the state from CCM to CM. If the vehicle does not receive any response message, the vehicle resets its state to IN. A special case is that a vehicle Vi in the IN state receives messages from multiple CHs. In this case, the vehicle selects CHj which has the highest LLTij.Algorithm 3: Cluster formation.
Input: Set of IN,  CCM
Output: Set of CM
(1)
for each vehicle Vi where StateVi=IN do
(2)
if Vi receives CH_ACK or Beacon from CHj then
(3)
StateVi=CCM
(4)
Vi unicasts JOIN_REQ to Vj
(5)
Vi starts JOIN_TIMER
(6)
while JOIN_TIMER>0 do
(7)
if Vi receives JOIN_RESP then
(8)
StateVi←CM
(9)
end if
(10)
end while
(11)
if Vi does not receive JOIN_RESP then
(12)
StateVi←IN
(13)
end if
(14)
end if
(15)
end for
(16)
for each vehicle Vj where StateVj=CH do
(17)
if Vj receives JOIN_REQ from Vi then
(18)
if NUM_CMVj<MAX_CM then
(19)
Vj adds Vi into CM_LISTj
(20)
Vj unicasts JOIN_RESP to Vi
(21)
end if
(22)
end if
(23)
end forThe vehicle which is in the CH state maintains aCM_LIST to store the information of CMs. When the CH receives a JOIN_REQ message from the surroundings, the CH first checks the total number of members in the CM_LIST. If the number of CMs is less than a maximum number of members allowed (MAX_CM), the CH generates a JOIN_RESP message and unicasts it to the vehicle from which the JOIN_REQ message is received. At the meantime, the CH builds an entry of the vehicle and adds it to the CM_LIST.


### 4.5. Cluster Maintenance

Because of the high mobility of vehicles in VANET, the role of vehicles may keep changing frequently, which brings extra maintenance overhead. In our proposed scheme, the CH resigns from CH role and transfers to the IN state when losing all of its CMs. Otherwise, it remains as CH until the cluster merging process happens. Therefore, we only consider cluster merging (Algorithm4) and vehicle leaving events in the cluster maintenance procedure.Algorithm 4: Cluster merging.
Input: Two subclusters
Output: The merged cluster
(1)
if LLTij≥δm then
(2)
if LRELi≥LRELj then
(3)
CHj sends MERGE_REQ to CHi
(4)
if CHi receives MERGE_REQ then
(5)
CHi estimates Npm
(6)
if Npm≤MAX_CM then
(7)
CHi sends MERGE_RESP to CHj
(8)
end if
(9)
end if
(10)
if CHj receives MERGE_RESP then
(11)
CHj broadcasts MERGE_ACK
(12)
StateVj←CM
(13)
end if
(14)
end if
(15)
end if


### 4.5.1. Cluster Merging

As time passes, clusters moving on the road may overlap with one another. When two moving clusters get closer to one another, the overlapping area of these two clusters becomes larger. Heavily overlapped moving clusters introduce redundant in intracluster management and communication overhead. Under the circumstances, the two clusters have potential to be merged. Instead of starting the cluster merging procedure immediately, the merging procedure begins if the two CHs (CHi and CHj) detect that they will stay neighbors for a certain time threshold δm(LLTij≥δm). This is because if two clusters just passing by one another quickly, the overlap of the two clusters is temporary and would not affect the overall performance in the long run. Once the cluster merging process begins, the two CHs share their cluster information and the CH with lower LREL (CHj) sends MERGE_REQ to the higher CH (CHi).Upon reception ofMERGE_REQ, CHi estimates the potential merged cluster size (Npm). If Npm≤MAX_CM, cluster merging is permitted and CHi then sends MERGE_RESP to CHj. If CHj receives MERGE_RESP, CHj gives up the leadership and broadcasts MERGE_ACK to inform its CMs about the merge operation. Otherwise, the CHs remain the role as CHs. On reception of MERGE_ACK, CMs which also in the SNi of CHi automatically become cluster members of CHi. The remaining vehicles then search new clusters and join in.


### 4.5.2. Leaving a Cluster

During every beacon period, each CH monitors the connections with its CMs dynamically. If a CH does not receive thebeacon message from its CM for at least two beacon interval, the CH is considered to loss the connection with the CM. Every time when a CH receives a beacon message from its CM, it updates the CMs related information in its CM_LIST. When the disconnection occurs, CH deletes the entry of the CM from the CM_LIST. The vehicle which lost the connection with CH then transfers its state to IN and tries to find a new cluster. When a CH losses all of its CMs to become an isolated CH for a certain time δi, the CH resigns from CH role and turns to IN.


## 4.1. LLT-Based Neighbor Sampling

In VANET, vehicles exchange and collect information about their one-hop vicinities through periodic beacon messages. After receiving the beacons, each vehicle constructs the potential neighbor (PN) set [34]. However, not all the vehicles in PN are ideal for clustering. In order to improve the stability of clusters, this paper introduces an LLT-based neighbor sampling process to select a stable neighbor (SN) set from PN.Link lifetime (LLT) [35], also called link expiration time (LET), represents the predicted duration time that two adjacent vehicles remain connected. Equation (1) defines LLT calculation. Δvij and Δdij represent the difference of velocity and distance between Vi and Vj, respectively. R denotes the transmission range of a vehicle. The LLT is introduced to evaluate the link sustainability. The link is more sustainable with a larger LLT value.(1)LLTij=Δvij⋅R−Δvij⋅ΔdijΔvij2.The detail of the sampling process is presented in Algorithm1. At the beginning, the system starts a timer (IN_TIMER) for gathering information. The vehicle in SN is defined as the neighboring vehicle which is going to have a constant connection for a predetermined time threshold δs. For each vehicle Vi, it maintains a set of stable neighbors SNi, which contains several entries SNij of vehicle Vj.Algorithm 1: LLT-based neighbor sampling.
Input: PNi;
Output: SNi;
(1)
while IN_TIMER>0 do
(2)
for each vehicle Vj∈PNi do
(3)
if Vi receives a Beacon message from Vj then
(4)
Vi calculates LLTij;
(5)
end if
(6)
if LLTij>δs then
(7)
if Vj∈SNi then
(8)
Vi updates SNij
(9)
else
(10)
Vi adds a new SNij to SNi
(11)
end if
(12)
end if
(13)
end for
(14)
end while


## 4.2. Link Reliability Metric

The link reliability model for communication links between two vehicles in urban VANET is given in [36]. The network connectivity status is mainly determined by the velocity distribution over the vehicular traffic flow. The basic link reliability model is defined as the conditional probability in the following equation which describes the probability of the continuous link connectivity between two vehicles over a specified time duration:(2)rl=Plcontinues  tot+LLTlis  available  att,where rl represents the reliability of the link and l is the particular link between two vehicles. LLT indicates the prediction interval of link duration from time t. Equation (2) shows that if the link l is available at time t, the link will be available until t+LLT.The velocity of vehicles is the main parameter to calculate the link reliability. In this paper, we assume that the velocity satisfies anormal distribution [37]. Then the probability density function of the velocity gv can be calculated as(3)gv=1σ2πe−v−μ2/2σ2,where μ and σ denote the mean and standard variation, respectively. Let Δvij be the relative velocity between vehicles Vi and Vj, that is, Δvij=vi−vj. Since vi and vj satisfy the normal distribution, Δvij should also obey the law of normal distribution. Let fT be the probability density function of the communication duration T. fT can be calculated as(4)fT=4RσΔvij2π1T2e2R/T−μΔvij2/2σΔvij2,forT≥0,where μΔvij and σΔvij denote the mean and the standard variation of relative velocity between vi and vj , respectively. Then, we can obtain the link reliability value rlij by integrating fT in (4) from time t to t+T, as shown in the following equation:(5)rtlij=∫tt+LLTfTdT,if  LLT>0,0,otherwise.By using the Gauss error function Erf [38], the integral in (5) can be obtained as follows:(6)rtlij=Erf2R/t−μΔvijσΔvij2−Erf2R/t+LLT−μΔvijσΔvij2,when    LLT>0.The Erf function is calculated as follows:(7)Erfx=2π∫0xe−η2dη,−∞<x<+∞.For a particular vehicle, it may have connections with multiple vehicles in the surrounding zone. The network connectivity could be diverse due to the complex traffic conditions. Therefore, we only consider those vehicles in the SN while defining the metric LREL:(8)LRELit=∑vj∈SNirtlij.


## 4.3. Cluster Head Selection

This section describes the method whereby a CH is selected. We assess the fitness of a vehicle to act as a cluster head based on link reliability. The calculation of LREL has been presented in the previous section.As shown in Algorithm2, a vehicle Vi in the IN state firstly tries to join an existing cluster by listening to the CH_ACK message or beacon message from a CH during the time period CH_TIMER. If Vi fails to join an existing cluster when CH_TIMER expires, Vi calculates a weighted metric, LRELi, according to (8). Then Vi compares LRELi with the neighbors in SNi. If it turns out that Vi has the highest value of LREL, Vi broadcasts CH_ACK information to claim itself to be a CH.Algorithm 2: Cluster head selection.
Input: Set of IN
Output: Set of CCM,  CH
(1)
for each vehicle Vi where StateVi=IN do
(2)
Vi starts CH_TIMER
(3)
while CH_TIMER>0 do
(4)
if Vi receives CH_ACK or Beacon from CHj then
(5)
StateVi←CCM
(6)
goto Cluster Formation
(7)
end if
(8)
end while
(9)
if Vi does not receive CH_ACK then
(10)
Vi calculates LRELi
(11)
if LRELi≥MAXVm∈SNiLRELm then
(12)
StateVi←CH
(13)
Vi broadcasts CH_ACK
(14)
end if
(15)
end if
(16)
end for


## 4.4. Cluster Formation

As shown in Algorithm3, the vehicle in the IN state will join a cluster if it receives the CH_ACK message or beacon message from a CH. The vehicle first transfers its state to CCM, then sends a JOIN_REQ message to the corresponding CH, and starts a join response timer (JOIN_TIMER). On reception of the JOIN_RESP message, the vehicle changes the state from CCM to CM. If the vehicle does not receive any response message, the vehicle resets its state to IN. A special case is that a vehicle Vi in the IN state receives messages from multiple CHs. In this case, the vehicle selects CHj which has the highest LLTij.Algorithm 3: Cluster formation.
Input: Set of IN,  CCM
Output: Set of CM
(1)
for each vehicle Vi where StateVi=IN do
(2)
if Vi receives CH_ACK or Beacon from CHj then
(3)
StateVi=CCM
(4)
Vi unicasts JOIN_REQ to Vj
(5)
Vi starts JOIN_TIMER
(6)
while JOIN_TIMER>0 do
(7)
if Vi receives JOIN_RESP then
(8)
StateVi←CM
(9)
end if
(10)
end while
(11)
if Vi does not receive JOIN_RESP then
(12)
StateVi←IN
(13)
end if
(14)
end if
(15)
end for
(16)
for each vehicle Vj where StateVj=CH do
(17)
if Vj receives JOIN_REQ from Vi then
(18)
if NUM_CMVj<MAX_CM then
(19)
Vj adds Vi into CM_LISTj
(20)
Vj unicasts JOIN_RESP to Vi
(21)
end if
(22)
end if
(23)
end forThe vehicle which is in the CH state maintains aCM_LIST to store the information of CMs. When the CH receives a JOIN_REQ message from the surroundings, the CH first checks the total number of members in the CM_LIST. If the number of CMs is less than a maximum number of members allowed (MAX_CM), the CH generates a JOIN_RESP message and unicasts it to the vehicle from which the JOIN_REQ message is received. At the meantime, the CH builds an entry of the vehicle and adds it to the CM_LIST.


## 4.5. Cluster Maintenance

Because of the high mobility of vehicles in VANET, the role of vehicles may keep changing frequently, which brings extra maintenance overhead. In our proposed scheme, the CH resigns from CH role and transfers to the IN state when losing all of its CMs. Otherwise, it remains as CH until the cluster merging process happens. Therefore, we only consider cluster merging (Algorithm4) and vehicle leaving events in the cluster maintenance procedure.Algorithm 4: Cluster merging.
Input: Two subclusters
Output: The merged cluster
(1)
if LLTij≥δm then
(2)
if LRELi≥LRELj then
(3)
CHj sends MERGE_REQ to CHi
(4)
if CHi receives MERGE_REQ then
(5)
CHi estimates Npm
(6)
if Npm≤MAX_CM then
(7)
CHi sends MERGE_RESP to CHj
(8)
end if
(9)
end if
(10)
if CHj receives MERGE_RESP then
(11)
CHj broadcasts MERGE_ACK
(12)
StateVj←CM
(13)
end if
(14)
end if
(15)
end if


## 4.5.1. Cluster Merging

As time passes, clusters moving on the road may overlap with one another. When two moving clusters get closer to one another, the overlapping area of these two clusters becomes larger. Heavily overlapped moving clusters introduce redundant in intracluster management and communication overhead. Under the circumstances, the two clusters have potential to be merged. Instead of starting the cluster merging procedure immediately, the merging procedure begins if the two CHs (CHi and CHj) detect that they will stay neighbors for a certain time threshold δm(LLTij≥δm). This is because if two clusters just passing by one another quickly, the overlap of the two clusters is temporary and would not affect the overall performance in the long run. Once the cluster merging process begins, the two CHs share their cluster information and the CH with lower LREL (CHj) sends MERGE_REQ to the higher CH (CHi).Upon reception ofMERGE_REQ, CHi estimates the potential merged cluster size (Npm). If Npm≤MAX_CM, cluster merging is permitted and CHi then sends MERGE_RESP to CHj. If CHj receives MERGE_RESP, CHj gives up the leadership and broadcasts MERGE_ACK to inform its CMs about the merge operation. Otherwise, the CHs remain the role as CHs. On reception of MERGE_ACK, CMs which also in the SNi of CHi automatically become cluster members of CHi. The remaining vehicles then search new clusters and join in.


## 4.5.2. Leaving a Cluster

During every beacon period, each CH monitors the connections with its CMs dynamically. If a CH does not receive thebeacon message from its CM for at least two beacon interval, the CH is considered to loss the connection with the CM. Every time when a CH receives a beacon message from its CM, it updates the CMs related information in its CM_LIST. When the disconnection occurs, CH deletes the entry of the CM from the CM_LIST. The vehicle which lost the connection with CH then transfers its state to IN and tries to find a new cluster. When a CH losses all of its CMs to become an isolated CH for a certain time δi, the CH resigns from CH role and turns to IN.


## 5. Routing Protocol of LRCA

The goal of our proposed LRCA architecture is to delivery data packets to a specified destination in the vehicular networks. For example, if a vehicle is heading for a particular shopping district, this vehicle can obtain the parking information nearby or promotion information from merchants in advance by sending inquires to the vehicles around the shopping district.In LRCA, clusters span over every road segment. In order to connect them in street scenarios, we propose a bridge node selection scheme to nominate special nodes at intersections. Moreover, these selected bridge nodes are responsible for assessing the network condition over each road segment connected to the intersection.


### 5.1. Bridge Node Selection at Intersections

For each intersection, the vehicle which will stay longer at the intersection zone is preferred to be selected as the bridge node. In this case, those vehicles stopped by the red light will be the ideal candidates. If there is only one vehicle, we nominate the vehicle as the bridge node directly; if there are more vehicles, we randomly select a vehicle as the bridge node for the sake of simplicity; if there is no vehicle stopping at the intersection, we will select the vehicle which is approaching the intersection center with the lowest velocity.For example, as shown in Figure3, V0 will be selected as the bridge node because it is stopping at the intersection. In other case, assume that the vehicle V0 does not exist. The rest of the vehicles within the intersection zone are all candidates (i.e., ζ=V1,V2,V3,V4,V5). Among them, V1 and V5 are going past the intersection center while V2, V3, and V4 are approaching the intersection center. We discard V1 and V5 from ζ because they are on the way leaving the intersection zone. Afterwards, the bridge node is selected from the remaining candidates ζ=V2,V3,V4. The vehicle in ζ which has the minimum velocity is then chosen as the bridge node.Figure 3
Bridge node selection at intersections.When the bridge node is about to drive out of the intersection zone, a new bridge node will be selected to guarantee the connectivity in intersection scenarios.


### 5.2. Road Segment Evaluation

When calculating the routing path, we cannot simply adopt traditional shortest path algorithms (e.g.,Dijkstra’s algorithm) because when the packet carrier arrives at an intersection, it is not guaranteed that it can meet another vehicle moving towards the most preferred direction [39]. In order to evaluate the network condition of road segments, we put forward a distributed procedure named road segment evaluation (RSE) which is dynamically initiated by aforementioned bridge nodes.RSE is triggered when a bridge node is selected at an intersection (Ii) by sending a light-weight control packet (PRSE) to the adjacent intersection (Ij). Thereafter, PRSE transverses the road segment (RSij) via relaying forwarders and gathers information regarding connectivity, delay, and hop count at each intermediate forwarder. When PRSE reaches the target intersection, the bridge node at that junction calculates the delivery delay (dp) as follows:(9)dp=trc−TRSE,where trc and TRSE designate the received time and the generation time of PRSE, respectively. dp can indicate the network condition in the road because it experiences similar transmission and queuing delay in addition to interference and fading conditions in Rij. Then, dp is compared to a threshold TMij which is calculated as below:(10)TMij=2⋅tdM⋅RSijR+tcf,where tdM is a constant parameter representing the maximum acceptable delay per forwarder, including the transmission delay and queuing delay, RSij denotes the length of RSij, and tcf is a constant parameter representing the maximum tolerable time using carry-and-forward. For a disconnected road segment, PRSE is dropped when a forwarder detects that dp is larger than TMij. In case a bridge node has not received the PRSE for a certain time, that is, dp>TMij, the bridge node deduces that Rij is disconnected. Afterwards, the bridge node assigns weight to RSij:(11)wij=dp/TMij,dp≤TMij,∞,otherwise.


### 5.3. Route Construction

The protocol is designed for transmitting data with the lowest delivery delay and the highest stability in terms of connectivity. In particular, we assume that a vehicle generates aDATA_PACKET in the form of <Vsrc,M,Ldest>, where Vsrc denotes the identity of the sender vehicle, M is the message, and Ldest is the location of message destination.As shown in Algorithm5, the protocol consists of two phases, that is, inter- and intrasegment phases. The intersegment phase deals with the routing path decision at intersections, while the intrasegment phase focuses on packet forwarding within a road segment. When the DATA_PACKET is generated, Vsrc forwards it to the nearest bridge node.Algorithm 5: Routing protocol.
(1)
Initialization:DATA_PACKET≤Vsrc,M,Ldest>
(2)
if the current forwarder Vc arrives at an intersection then
(3)
Vc delivers DATA_PACKET to the bridge node VBi
(4)
VBi calculates Mij and selects the RSij with the minimum Mij
(5)
VBi delivers DATA_PACKET to a vehicle on RSij
(6)
else
(7)
if Vc is a CH then
(8)
if Ldest inside the cluster range then
(9)
MulticastDATA_PACKET to its CMs and Done
(10)
else
(11)
UnicastDATA_PACKET to a CM closest to the target intersection Ij
(12)
end if
(13)
else
(14)
if DATA_PACKET is from its CH then
(15)
UnicastDATA_PACKET to a CM or CH closest to Ij
(16)
else
(17)
UnicastDATA_PACKET to its CH
(18)
end if
(19)
end if
(20)
end ifFor the intersegment phase, when the current forwarder arrives at an intersectionIi, it delivers DATA_PACKET to the bridge node at that intersection. Once received, the bridge node obtains the destination and calculates the routing metric as below:(12)Mij=SPjSPi⋅wij,where Mij is combination of both geographic information and routing path delay. In (12), SPj/SPi denotes the geographical process where SPi represents the shortest path between current intersection and Ldest, and SPj represents the shortest path between the next candidate intersection and Ldest. The road segment RSij with the minimum Mij is considered to be the optimal routing path. Then, the bridge node delivers the DATA_PACKET to a vehicle on the selected road.For the intrasegment phase, if the current forwarder is a CH (Steps 6–11), it checks whetherLdest is inside its cluster range. If so, the CH will broadcast the DATA_PACKET to its CMs directly. If not, the CH will look for a good relay vehicle for the message propagation. The CH aims at finding a CM which is closest to the target intersection. The CH first computes the intersection point (PInter) of the route path and communication range as shown in Figure 4. Then, the CM which is closest to PInter and moves towards the target intersection is considered to be a good relay vehicle (VR) for the message propagation. To find such a vehicle, the CH calculates the distance (dIR) between PInter and its CMs. Afterwards, the CH selects the CM with minimum dIR as the relay vehicle and then unicasts the DATA_PACKET to this CM.Figure 4
Computation of a good relay node.In another case, if the current forwarder is a CM (Steps 12–17), it checks the source of the packet. If the packet does not come from its CH, the CM will unicast the packet to its CH directly. If the packet comes from its CH, the CM will be responsible for sending the packet to vehicles in nearby clusters. The CM first checks the neighbor list to find a neighbor CH which is moving towards the target intersection. If there are multiple such CHs, the CM selects the CH with the shortest distance to the target intersection. Then, theDATA_PACKET will be delivered to the selected CH. If the CM fails to find a CH in the neighbor list, the CM will select a one-hop neighbor which is closest to the next intersection as the next propagation vehicle.


## 5.1. Bridge Node Selection at Intersections

For each intersection, the vehicle which will stay longer at the intersection zone is preferred to be selected as the bridge node. In this case, those vehicles stopped by the red light will be the ideal candidates. If there is only one vehicle, we nominate the vehicle as the bridge node directly; if there are more vehicles, we randomly select a vehicle as the bridge node for the sake of simplicity; if there is no vehicle stopping at the intersection, we will select the vehicle which is approaching the intersection center with the lowest velocity.For example, as shown in Figure3, V0 will be selected as the bridge node because it is stopping at the intersection. In other case, assume that the vehicle V0 does not exist. The rest of the vehicles within the intersection zone are all candidates (i.e., ζ=V1,V2,V3,V4,V5). Among them, V1 and V5 are going past the intersection center while V2, V3, and V4 are approaching the intersection center. We discard V1 and V5 from ζ because they are on the way leaving the intersection zone. Afterwards, the bridge node is selected from the remaining candidates ζ=V2,V3,V4. The vehicle in ζ which has the minimum velocity is then chosen as the bridge node.Figure 3
Bridge node selection at intersections.When the bridge node is about to drive out of the intersection zone, a new bridge node will be selected to guarantee the connectivity in intersection scenarios.


## 5.2. Road Segment Evaluation

When calculating the routing path, we cannot simply adopt traditional shortest path algorithms (e.g.,Dijkstra’s algorithm) because when the packet carrier arrives at an intersection, it is not guaranteed that it can meet another vehicle moving towards the most preferred direction [39]. In order to evaluate the network condition of road segments, we put forward a distributed procedure named road segment evaluation (RSE) which is dynamically initiated by aforementioned bridge nodes.RSE is triggered when a bridge node is selected at an intersection (Ii) by sending a light-weight control packet (PRSE) to the adjacent intersection (Ij). Thereafter, PRSE transverses the road segment (RSij) via relaying forwarders and gathers information regarding connectivity, delay, and hop count at each intermediate forwarder. When PRSE reaches the target intersection, the bridge node at that junction calculates the delivery delay (dp) as follows:(9)dp=trc−TRSE,where trc and TRSE designate the received time and the generation time of PRSE, respectively. dp can indicate the network condition in the road because it experiences similar transmission and queuing delay in addition to interference and fading conditions in Rij. Then, dp is compared to a threshold TMij which is calculated as below:(10)TMij=2⋅tdM⋅RSijR+tcf,where tdM is a constant parameter representing the maximum acceptable delay per forwarder, including the transmission delay and queuing delay, RSij denotes the length of RSij, and tcf is a constant parameter representing the maximum tolerable time using carry-and-forward. For a disconnected road segment, PRSE is dropped when a forwarder detects that dp is larger than TMij. In case a bridge node has not received the PRSE for a certain time, that is, dp>TMij, the bridge node deduces that Rij is disconnected. Afterwards, the bridge node assigns weight to RSij:(11)wij=dp/TMij,dp≤TMij,∞,otherwise.


## 5.3. Route Construction

The protocol is designed for transmitting data with the lowest delivery delay and the highest stability in terms of connectivity. In particular, we assume that a vehicle generates aDATA_PACKET in the form of <Vsrc,M,Ldest>, where Vsrc denotes the identity of the sender vehicle, M is the message, and Ldest is the location of message destination.As shown in Algorithm5, the protocol consists of two phases, that is, inter- and intrasegment phases. The intersegment phase deals with the routing path decision at intersections, while the intrasegment phase focuses on packet forwarding within a road segment. When the DATA_PACKET is generated, Vsrc forwards it to the nearest bridge node.Algorithm 5: Routing protocol.
(1)
Initialization:DATA_PACKET≤Vsrc,M,Ldest>
(2)
if the current forwarder Vc arrives at an intersection then
(3)
Vc delivers DATA_PACKET to the bridge node VBi
(4)
VBi calculates Mij and selects the RSij with the minimum Mij
(5)
VBi delivers DATA_PACKET to a vehicle on RSij
(6)
else
(7)
if Vc is a CH then
(8)
if Ldest inside the cluster range then
(9)
MulticastDATA_PACKET to its CMs and Done
(10)
else
(11)
UnicastDATA_PACKET to a CM closest to the target intersection Ij
(12)
end if
(13)
else
(14)
if DATA_PACKET is from its CH then
(15)
UnicastDATA_PACKET to a CM or CH closest to Ij
(16)
else
(17)
UnicastDATA_PACKET to its CH
(18)
end if
(19)
end if
(20)
end ifFor the intersegment phase, when the current forwarder arrives at an intersectionIi, it delivers DATA_PACKET to the bridge node at that intersection. Once received, the bridge node obtains the destination and calculates the routing metric as below:(12)Mij=SPjSPi⋅wij,where Mij is combination of both geographic information and routing path delay. In (12), SPj/SPi denotes the geographical process where SPi represents the shortest path between current intersection and Ldest, and SPj represents the shortest path between the next candidate intersection and Ldest. The road segment RSij with the minimum Mij is considered to be the optimal routing path. Then, the bridge node delivers the DATA_PACKET to a vehicle on the selected road.For the intrasegment phase, if the current forwarder is a CH (Steps 6–11), it checks whetherLdest is inside its cluster range. If so, the CH will broadcast the DATA_PACKET to its CMs directly. If not, the CH will look for a good relay vehicle for the message propagation. The CH aims at finding a CM which is closest to the target intersection. The CH first computes the intersection point (PInter) of the route path and communication range as shown in Figure 4. Then, the CM which is closest to PInter and moves towards the target intersection is considered to be a good relay vehicle (VR) for the message propagation. To find such a vehicle, the CH calculates the distance (dIR) between PInter and its CMs. Afterwards, the CH selects the CM with minimum dIR as the relay vehicle and then unicasts the DATA_PACKET to this CM.Figure 4
Computation of a good relay node.In another case, if the current forwarder is a CM (Steps 12–17), it checks the source of the packet. If the packet does not come from its CH, the CM will unicast the packet to its CH directly. If the packet comes from its CH, the CM will be responsible for sending the packet to vehicles in nearby clusters. The CM first checks the neighbor list to find a neighbor CH which is moving towards the target intersection. If there are multiple such CHs, the CM selects the CH with the shortest distance to the target intersection. Then, theDATA_PACKET will be delivered to the selected CH. If the CM fails to find a CH in the neighbor list, the CM will select a one-hop neighbor which is closest to the next intersection as the next propagation vehicle.


## 6. Performance Evaluation

The proposed approach is compared with three previously proposed clustering-based schemes NHop [23], VMaSC [9], and MOSIC [24], and a nonclustering-based approach GeoSVR [40]. Among them, NHop and VMaSC are the two most cited multihop clustering algorithms and MOSIC is a latest single-hop clustering approach which has been introduced in Section 2. Since our proposed LRCA and the MOSIC are both single-hop clustering algorithms, the one-hop NHop and VMaSC are implemented in the simulation. GeoSVR is a high-cited nonclustering-based routing protocol which combines node location with the digital map. Meanwhile, it selects the routing path based on vehicular density to avoid local maximum and sparse connectivity.The simulations are implemented in the Network Simulator NS-2 (v-2.35) [41] with the mobility of vehicles generated by SUMO [42]. As shown in Figure 5, the simulation scenario is a 5100m×4800m ordinary urban environment which is extracted from the OpenStreetMap [43] of Shanghai China. The number of simulated vehicles is set to 1500, and we run the simulation for 100 seconds to let all the injected vehicles move around the map for a while. After 100 seconds, the simulation runs for another 500 seconds to evaluate the total performance metrics. In the simulation, we evaluate the metrics at the transmission ranges of 200 and 500 m. Meanwhile, we vary the maximum allowable velocity of vehicles from 10 to 30 m/s and the maximum acceleration and deceleration are set to 5 m2/s. The reported result is the average of 10 times repeated run. The details of simulation parameters and values are listed in Table 2.Figure 5
Simulation scenario of Shanghai China with SUMO.Table 2
Simulation parameters.
Notation
Description
Simulation area
5100 m × 4800 m
Maximum velocity
10, 15, 20, 25, 30m/s
Maximum acceleration
5m/s2
Transmission range
200, 500 m
MAC protocol
IEEE 802.11p
Data rate
2Mbps
MAX_CM
10
HELLO_PACKET period
200ms
HELLO_PACKET size
64bytes
DATA_PACKET generation rate
10, 20, 30, 40, 50packet/s
DATA_PACKET size
1024bytes
IN_TIMER
1 s
CH_TIMER
2 s
JOIN_TIMER
2 s
δ
s
2 s
δ
m
2 s
δ
i
1 s


### 6.1. Clustering Performance

To evaluate the performance of the proposed clustering algorithm, we focus on the stability of cluster, where cluster stability means lower changes in the CHs and lower changes in the CMs. Therefore, good clustering algorithm should be designed to minimize the rate of CH change and gain long term of CH duration, as well as cluster member duration.Consequently, the following performance metrics are used for comparison:(i)
Cluster head duration: It is defined as the average time from a vehicle becoming a CH to transferring to another state.(ii)
Cluster member duration: It is defined as the average time from a vehicle joining a cluster to leaving the cluster.(iii)
Cluster head change rate: It is defined as 1−SCHt∩SCHt−1/SCHt∪SCHt−1, where SCHt and SCHt−1 represent the current CH set and previous CH set, respectively. s denotes the number of elements in the corresponding set.The results in Figures6–8 evaluate the clustering stability for different maximum allowable velocities and transmission ranges by comparing the proposed LRCA with VMaSC, NHop, and MOSIC, from the aspects of the average CH lifetime, the average CM lifetime, and the CH change rate.Figure 6
CH duration for different maximum allowable velocities and transmission ranges.Figure 7
CM duration for different maximum allowable velocities and transmission ranges.Figure 8
CH change rate for different maximum allowable velocities and transmission ranges.Figures6 and 7 show the performance of CH and CM duration for different maximum allowable velocities and transmission ranges, respectively. Results show that the average CH and CM duration will decrease when the maximum allowable velocity of vehicles increases. This is because when the vehicles move faster, the vehicular network topology becomes more dynamic and eventually makes it difficult for vehicles to maintain a relatively stable condition with their neighbor vehicles for a long period. VMaSC-1hop acquires the longest CH lifetime and CM lifetime when the maximum velocity is 10 m/s. But both the CH duration and CM duration of VMaSC-1hop decrease rapidly when the maximum allowable velocity increases. When the maximum velocity is bigger than 15 m/s, LRCA performs better against VMaSC (VMaSC-1hop), NHop (NHop-1hop), and MOSIC in terms of both CH and CM duration. This is because in our scheme, we construct stable clusters by employing LLT-based neighbor sampling scheme to pick out stable neighbors. In addition, the CH duration and CM duration are larger at a high-transmission range. The main reason is that the vehicles can communicate with more neighbor nodes and create higher correlation of connectivity behavior when the transmission range is higher. As the transmission range increases from 200 to 500 m, the link duration increases for all the simulated clustering algorithms.Figure8 shows the performance of the CH change rate for different maximum allowable velocities and transmission ranges. From the results, we can observe that the CH change rate increases with the increment of maximum allowable velocity and decreases as the transmission range increases. The reason is that the increment of maximum allowable velocity accelerates the change of network topology. Afterwards, some CMs may move out of the cluster or cluster merging may happen, which may result in cluster head changes. On the contrary, the higher transmission range provides much more connectivity of the vehicles within a cluster, which reduces the changes in the cluster head. The CH change rate for NHop-1hop is closer to MOSIC at both low- and high-transmission range when the maximum allowable velocity is between 10 and 15 m/s. However, the CH change rate for NHop-1hop increases rapidly as the velocity increases. Our proposed LRCA acquires the lowest CH change rate against VMaSC-1hop, NHop-1hop, and MOSIC in both cases of transmission range. We reduce the CH change rate by changing the CH state to other clustering state only when cluster merging happens or it losses all the CMs to become an isolated CH. In addition, to avoid unnecessary state transitions, we put up two time thresholds δm and δi before merging two clusters and before transferring an isolated CH to the IN state.As shown above, mostly, the LRCA gains longer duration of both CH and CM and performs the lowest CH change rate at both low- and high-transmission range. Therefore, the proposed LRCA indicates the better performance of clustering stability than that of VMaSC (VMaSC-1hop), NHop (NHop-1hop), and MOSIC.


### 6.2. Routing Performance

The routing performance of our proposed LRCA is compared with three cluster-based routing mechanisms including NHop, VMaSC, and MOSIC, which have been discussed in the related work above, and a nonclustering approach called GeoSVR. We aim at achieving efficient and reliable data delivery with high packet delivery ratio and low network latency.From the simulation results above, we can learn that clusters acquire more stability at a high-transmission range. Hence, we set the transmission range to 500 m when evaluating the routing performance here. To evaluate the effect of different parameters on the routing performance, we vary the parameters of the data packet generation rate and maximum allowable velocity in the simulation. The default value of the maximum allowable velocity and the data packet generation rate are set to 20m/s and 30 packet/s, respectively.Furthermore, we evaluate the routing performance using the following performance metrics:(i)
Packet delivery ratio (PDR): This metric is defined as the ratio of the average number of data packets successfully received by destinations, compared to the total number of generated packets.(ii)
End-to-end delay (E2ED): This metric represents the average delay between the time a packet generated by the source and the time of this packet reached to the destination.(iii)
Normalized routing overhead (NRO): This metric is calculated as the ratio of the size of total generated packets to the size of the data packets successfully received by the destinations.Figure9 shows the performance of the packet delivery ratio for varying maximum allowable velocity. It is observed that LRCA achieves higher packet delivery ratio than other schemes. By selecting stable neighbors according to link lifetime (LLT), LRCA builds up a stable clustered virtual network which can provide the stable connections between cluster members, and meanwhile increase the bandwidth availability and reduce data collision. Moreover, the results show that the packet delivery ratio of all protocols decreases when lifting upper limitation of allowable velocity. Because the maximum allowable velocity increases, the network topology changes rapidly, leading to an increment of packet loss ratio. The packet delivery ratio of GeoSVR is very close to that of MOSIC in the low-speed scenario. However, the packet delivery ratio of GeoSVR decreases significantly when the maximum allowable velocity is greater than 20 m/s, which indicates that the clustering-based routing approaches achieve more stability than the nonclustering-based ones, especially in the high-dynamic scenario.Figure 9
Packet delivery ratio for varying maximum allowable velocity.Figure10 shows the performance of the packet delivery ratio for varying data generation rate. Obviously, the packet delivery ratio of all the simulated protocols decreases when the data generation rate increases. This is because the vehicles need to store and carry the data packets when encountering network partitions. However, the size of packet buffer is limited, leading to subsequent packets being dropped when the buffer is full. Results show that our proposed LRCA achieves better performance of the packet delivery ratio than the other protocols. In LRCA, the bridge node selects the optimal routing path for data delivering considering the latency of each road segment, which decreases the cases of packet carrying by setting a time threshold parameter for the carry-and-forward mode as shown in (10).Figure 10
Packet delivery ratio for varying data generation rate.Figure11 shows the performance of average end-to-end delay for varying maximum allowable velocity. The increment of velocity results in frequent changes of network topology. Thus, the results show that the end-to-end delay increases in high-speed scenario. The proposed scheme achieves significant reduction of end-to-end delay in comparison with other schemes. This is because LRCA builds up stable clusters which can guarantee the sufficient connectivity and reliable linking. Therefore, the retransmission times and transmission delay are reduced, which results in reduction of end-to-end delay. Another reason is that with the help of the stable connected clusters, packets can be delivered to the next hop with short MAC layer contention, which leads to short network latency. GeoSVR achieves lower delivery delay against VMaSC, MOSIC, and NHop when the maximum speed is less than 25 m/s. The GeoSVR obtains a better result by using the optimal forwarding path and the restricted forwarding algorithm. However, the end-to-end delay of GeoSVR increases significantly when the maximum velocity comes to 30 m/s. This shows that the GeoSVR may not be quite suitable for high-speed VANET scenario.Figure 11
End-to-end delay for varying maximum allowable velocity.Figure12 shows the performance of average end-to-end delay for varying data generation rate. When varying the data generation rate from 10 to 50 packet/s, the queuing delay in the buffer with relay nodes raises, which eventually affects the end-to-end delay. Consequently, the results show that the end-to-end delay of all the simulated protocols tends to increase with the increase of the data generation rate. In LRCA, the routing decision is made based on the estimated delay information over each road segment, which includes both delays due to packet carrying and packet relaying on links. LRCA acquires the lowest delivery delay by selecting the route paths with the lowest delay and highest geographical process as shown in (12). GeoSVR selects road segments with high vehicular density as routing paths to reduce the probability of store-and-carry events. That is why GeoSVR achieves lower end-to-end delay than VMaSC, MOSIC, and NHop when the data generation rate is less than 30 packet/s. But the GeoSVR suffers from data congestion when the data generation rate is high due to the strategy forwarding data over dense roads. Therefore, the end-to-end delay is much higher when the data generation rate is high.Figure 12
End-to-end delay for varying data generation rate.Figure13 shows the performance of normalized routing overhead for varying maximum allowable velocity. The proposed scheme shows the lowest overhead in comparison with others. Besides, the overhead of clustering schemes is much lower than that of the nonclustering scheme GeoSVR. This is because the clustering approaches can reduce intervehicle communications. The experiment results also show that the overhead of NHop-1hop increases when the vehicles move faster, while the overhead of LRCA does not significantly increase when the maximum velocity increases. This is benefit from the neighbor sampling strategy to filter out unstable neighbors and reduce unnecessary message exchanges. Moreover, the LRCA provides the stable connections for data delivery which can reduce the number of packet retransmissions.Figure 13
Normalized routing overhead for varying maximum allowable velocity.Figure14 shows the performance of normalized routing overhead for varying data generation rate. Results show that LRCA achieves the lowest overhead and the clustering-based protocols acquire much lower overhead than the nonclustering scheme GeoSVR. The overhead of our proposed LRCA barely increases when raising the data generation rate, while other clustering methods more or less increase. LRCA reduces redundant message exchanges by selecting stable neighbor vehicles and reduces data packet retransmissions by selecting the route path with more connectivity.Figure 14
Normalized routing overhead for varying data generation rate.


## 6.1. Clustering Performance

To evaluate the performance of the proposed clustering algorithm, we focus on the stability of cluster, where cluster stability means lower changes in the CHs and lower changes in the CMs. Therefore, good clustering algorithm should be designed to minimize the rate of CH change and gain long term of CH duration, as well as cluster member duration.Consequently, the following performance metrics are used for comparison:(i)
Cluster head duration: It is defined as the average time from a vehicle becoming a CH to transferring to another state.(ii)
Cluster member duration: It is defined as the average time from a vehicle joining a cluster to leaving the cluster.(iii)
Cluster head change rate: It is defined as 1−SCHt∩SCHt−1/SCHt∪SCHt−1, where SCHt and SCHt−1 represent the current CH set and previous CH set, respectively. s denotes the number of elements in the corresponding set.The results in Figures6–8 evaluate the clustering stability for different maximum allowable velocities and transmission ranges by comparing the proposed LRCA with VMaSC, NHop, and MOSIC, from the aspects of the average CH lifetime, the average CM lifetime, and the CH change rate.Figure 6
CH duration for different maximum allowable velocities and transmission ranges.Figure 7
CM duration for different maximum allowable velocities and transmission ranges.Figure 8
CH change rate for different maximum allowable velocities and transmission ranges.Figures6 and 7 show the performance of CH and CM duration for different maximum allowable velocities and transmission ranges, respectively. Results show that the average CH and CM duration will decrease when the maximum allowable velocity of vehicles increases. This is because when the vehicles move faster, the vehicular network topology becomes more dynamic and eventually makes it difficult for vehicles to maintain a relatively stable condition with their neighbor vehicles for a long period. VMaSC-1hop acquires the longest CH lifetime and CM lifetime when the maximum velocity is 10 m/s. But both the CH duration and CM duration of VMaSC-1hop decrease rapidly when the maximum allowable velocity increases. When the maximum velocity is bigger than 15 m/s, LRCA performs better against VMaSC (VMaSC-1hop), NHop (NHop-1hop), and MOSIC in terms of both CH and CM duration. This is because in our scheme, we construct stable clusters by employing LLT-based neighbor sampling scheme to pick out stable neighbors. In addition, the CH duration and CM duration are larger at a high-transmission range. The main reason is that the vehicles can communicate with more neighbor nodes and create higher correlation of connectivity behavior when the transmission range is higher. As the transmission range increases from 200 to 500 m, the link duration increases for all the simulated clustering algorithms.Figure8 shows the performance of the CH change rate for different maximum allowable velocities and transmission ranges. From the results, we can observe that the CH change rate increases with the increment of maximum allowable velocity and decreases as the transmission range increases. The reason is that the increment of maximum allowable velocity accelerates the change of network topology. Afterwards, some CMs may move out of the cluster or cluster merging may happen, which may result in cluster head changes. On the contrary, the higher transmission range provides much more connectivity of the vehicles within a cluster, which reduces the changes in the cluster head. The CH change rate for NHop-1hop is closer to MOSIC at both low- and high-transmission range when the maximum allowable velocity is between 10 and 15 m/s. However, the CH change rate for NHop-1hop increases rapidly as the velocity increases. Our proposed LRCA acquires the lowest CH change rate against VMaSC-1hop, NHop-1hop, and MOSIC in both cases of transmission range. We reduce the CH change rate by changing the CH state to other clustering state only when cluster merging happens or it losses all the CMs to become an isolated CH. In addition, to avoid unnecessary state transitions, we put up two time thresholds δm and δi before merging two clusters and before transferring an isolated CH to the IN state.As shown above, mostly, the LRCA gains longer duration of both CH and CM and performs the lowest CH change rate at both low- and high-transmission range. Therefore, the proposed LRCA indicates the better performance of clustering stability than that of VMaSC (VMaSC-1hop), NHop (NHop-1hop), and MOSIC.


## 6.2. Routing Performance

The routing performance of our proposed LRCA is compared with three cluster-based routing mechanisms including NHop, VMaSC, and MOSIC, which have been discussed in the related work above, and a nonclustering approach called GeoSVR. We aim at achieving efficient and reliable data delivery with high packet delivery ratio and low network latency.From the simulation results above, we can learn that clusters acquire more stability at a high-transmission range. Hence, we set the transmission range to 500 m when evaluating the routing performance here. To evaluate the effect of different parameters on the routing performance, we vary the parameters of the data packet generation rate and maximum allowable velocity in the simulation. The default value of the maximum allowable velocity and the data packet generation rate are set to 20m/s and 30 packet/s, respectively.Furthermore, we evaluate the routing performance using the following performance metrics:(i)
Packet delivery ratio (PDR): This metric is defined as the ratio of the average number of data packets successfully received by destinations, compared to the total number of generated packets.(ii)
End-to-end delay (E2ED): This metric represents the average delay between the time a packet generated by the source and the time of this packet reached to the destination.(iii)
Normalized routing overhead (NRO): This metric is calculated as the ratio of the size of total generated packets to the size of the data packets successfully received by the destinations.Figure9 shows the performance of the packet delivery ratio for varying maximum allowable velocity. It is observed that LRCA achieves higher packet delivery ratio than other schemes. By selecting stable neighbors according to link lifetime (LLT), LRCA builds up a stable clustered virtual network which can provide the stable connections between cluster members, and meanwhile increase the bandwidth availability and reduce data collision. Moreover, the results show that the packet delivery ratio of all protocols decreases when lifting upper limitation of allowable velocity. Because the maximum allowable velocity increases, the network topology changes rapidly, leading to an increment of packet loss ratio. The packet delivery ratio of GeoSVR is very close to that of MOSIC in the low-speed scenario. However, the packet delivery ratio of GeoSVR decreases significantly when the maximum allowable velocity is greater than 20 m/s, which indicates that the clustering-based routing approaches achieve more stability than the nonclustering-based ones, especially in the high-dynamic scenario.Figure 9
Packet delivery ratio for varying maximum allowable velocity.Figure10 shows the performance of the packet delivery ratio for varying data generation rate. Obviously, the packet delivery ratio of all the simulated protocols decreases when the data generation rate increases. This is because the vehicles need to store and carry the data packets when encountering network partitions. However, the size of packet buffer is limited, leading to subsequent packets being dropped when the buffer is full. Results show that our proposed LRCA achieves better performance of the packet delivery ratio than the other protocols. In LRCA, the bridge node selects the optimal routing path for data delivering considering the latency of each road segment, which decreases the cases of packet carrying by setting a time threshold parameter for the carry-and-forward mode as shown in (10).Figure 10
Packet delivery ratio for varying data generation rate.Figure11 shows the performance of average end-to-end delay for varying maximum allowable velocity. The increment of velocity results in frequent changes of network topology. Thus, the results show that the end-to-end delay increases in high-speed scenario. The proposed scheme achieves significant reduction of end-to-end delay in comparison with other schemes. This is because LRCA builds up stable clusters which can guarantee the sufficient connectivity and reliable linking. Therefore, the retransmission times and transmission delay are reduced, which results in reduction of end-to-end delay. Another reason is that with the help of the stable connected clusters, packets can be delivered to the next hop with short MAC layer contention, which leads to short network latency. GeoSVR achieves lower delivery delay against VMaSC, MOSIC, and NHop when the maximum speed is less than 25 m/s. The GeoSVR obtains a better result by using the optimal forwarding path and the restricted forwarding algorithm. However, the end-to-end delay of GeoSVR increases significantly when the maximum velocity comes to 30 m/s. This shows that the GeoSVR may not be quite suitable for high-speed VANET scenario.Figure 11
End-to-end delay for varying maximum allowable velocity.Figure12 shows the performance of average end-to-end delay for varying data generation rate. When varying the data generation rate from 10 to 50 packet/s, the queuing delay in the buffer with relay nodes raises, which eventually affects the end-to-end delay. Consequently, the results show that the end-to-end delay of all the simulated protocols tends to increase with the increase of the data generation rate. In LRCA, the routing decision is made based on the estimated delay information over each road segment, which includes both delays due to packet carrying and packet relaying on links. LRCA acquires the lowest delivery delay by selecting the route paths with the lowest delay and highest geographical process as shown in (12). GeoSVR selects road segments with high vehicular density as routing paths to reduce the probability of store-and-carry events. That is why GeoSVR achieves lower end-to-end delay than VMaSC, MOSIC, and NHop when the data generation rate is less than 30 packet/s. But the GeoSVR suffers from data congestion when the data generation rate is high due to the strategy forwarding data over dense roads. Therefore, the end-to-end delay is much higher when the data generation rate is high.Figure 12
End-to-end delay for varying data generation rate.Figure13 shows the performance of normalized routing overhead for varying maximum allowable velocity. The proposed scheme shows the lowest overhead in comparison with others. Besides, the overhead of clustering schemes is much lower than that of the nonclustering scheme GeoSVR. This is because the clustering approaches can reduce intervehicle communications. The experiment results also show that the overhead of NHop-1hop increases when the vehicles move faster, while the overhead of LRCA does not significantly increase when the maximum velocity increases. This is benefit from the neighbor sampling strategy to filter out unstable neighbors and reduce unnecessary message exchanges. Moreover, the LRCA provides the stable connections for data delivery which can reduce the number of packet retransmissions.Figure 13
Normalized routing overhead for varying maximum allowable velocity.Figure14 shows the performance of normalized routing overhead for varying data generation rate. Results show that LRCA achieves the lowest overhead and the clustering-based protocols acquire much lower overhead than the nonclustering scheme GeoSVR. The overhead of our proposed LRCA barely increases when raising the data generation rate, while other clustering methods more or less increase. LRCA reduces redundant message exchanges by selecting stable neighbor vehicles and reduces data packet retransmissions by selecting the route path with more connectivity.Figure 14
Normalized routing overhead for varying data generation rate.


## 7. Conclusion

In this paper, we propose a new link reliability-based clustering algorithm (LRCA) to provide efficient and reliable data transmission in urban VANET. In LRCA, vehicles are grouped with stable neighbor vehicles which are selected by the LLT-based neighbor sampling scheme. Further, we introduce a cluster-based routing protocol to provide the efficient and reliable data transmission in vehicular networks. In contrast to those protocols proposed for safety critical applications, the routing approach in this paper is designed to support infotainment services in VANET which are not stringent in delay constraints. To transmit data packets through stable paths, we introduce bridge nodes at intersections to make routing decisions. The bridge node evaluates the network condition over road segments and assigns weights to them. Then the road segment with minimum weight is selected to construct the overall routing path. The simulation results show that the proposed LRCA acquires better clustering stability in terms of long cluster head duration, long cluster member duration, and low rate of cluster head change. The proposed routing protocol performs better than the previous proposed schemes, which demonstrates the advantages of the proposed LRCA. In the future work, we will further improve the route strategy to minimize the end-to-end delay and satisfy the requirements of real-time applications in VANET.



---

*Source: 9826782-2018-07-30.xml*