# A Novel Real Time Framework for Cluster Based Multicast Communication in Vehicular Ad Hoc Networks

Authors: Waqar Farooq; Muazzam Ali Khan; Saad Rehman
Journal: International Journal of Distributed Sensor Networks
 (2016)

---

## Abstract

In a vehicular ad hoc network (VANET), the vehicles communicate with each other to develop an intelligent transport system (ITS) which provides safety and convenience while driving. The major challenge of VANET is that the topology changes dynamically due to the high speed and unpredictable mobility of vehicles resulting in an inefficient real time message dissemination, especially in emergency scenarios such as in the accident event where it can cause high level of destruction. To the best of our knowledge, there is no such mechanism in existing literature which can handle real time multicast communication in VANET for both urban and highway scenarios. In this paper, we propose a novel real time vehicular communication (RTVC) framework which consists of a VANET cluster scheme (VCS) and VANET multicast routing (VMR) to achieve efficient vehicle communication within both urban and highway scenarios. The RTVC framework develops stable communication links and achieves high throughput with low overhead despite high mobility by combining the multicast routing with a unique cluster based scheme. In VCS, the cluster head (CH) is elected upon cluster threshold value (CTV) to disseminate the messages within the cluster members (CMs) and to other cluster heads by intercluster communication, which reduces the network overhead. In addition, the vehicles cluster head election (VCHE) procedure is proposed to reduce the number of CHs and CMs switches which results in lower overhead of maintaining the clusters. Moreover, another novelty of the framework is that the CTV of VCHE can be adjusted by speed adjustment factor (SAF) to achieve the desired cluster stability depending upon the required VANET application. The simulation results illustrate that the proposed framework has achieved the goal of stable, efficient, and real time communication despite highly dynamic environment of VANET.


---

## Body

## 1. Introduction

The fatalities and serious injuries due to road crashes are increasing every year at a fast pace. According to the Department of Transport, Great Britain, the reported deaths in traffic accidents at United Kingdom during 2014 were 1775. In addition to this, the number of seriously injured people was reported as 22,807 in the same year [1]. Besides this, according to the World Health Organization (WHO), every year 1.24 million people pass away due to vehicular accidents [2].It is possible to reduce the number of accidents by informing drivers in advance about the risk area by using intelligent transport system (ITS) which is one of the key applications of vehicular ad hoc network (VANET). In VANET, the vehicles communicate with each other by vehicle to vehicle communication (V2V), vehicle to road side units (V2R), and vehicle to infrastructure (V2I). The vehicles are equipped with wireless sensing devices to develop intervehicular communication (IVC) without deployment of infrastructure. Hence, VANET has got significant research attention since it develops wireless communication among vehicles to convey emergency messages to other incoming vehicles (IVs) which are approaching towards the risk area to avoid multivehicle collision as shown in Figure1. The main motivation of developing the VANET routing protocols is to reduce the human casualties and multicar collisions by managing the topology of high speed vehicles at real time. In VANET, the vehicles communicate with each other at 5.9 GHz by using IEEE 802.11p standard which is also known as Wireless Access in Vehicular Environment (WAVE). The IEEE 802.11p is an amendment of IEEE 802.11 with the channel bandwidth of 10 MHz [3].Figure 1
Message dissemination to incoming vehicles (IVs) in vehicular ad hoc networks.The physical and Medium Access Control (MAC) layers have been enhanced in IEEE 802.11p standard to meet the challenges of delivering messages successfully with low latency and at high mobility within the range of 100 to 1000 meters. The MAC-802.11p is based upon Enhanced Distributed Channel Access (EDCA) of IEEE 802.11e. EDCA is developed upon Carrier Sense Multiple Access Collision Avoidance (CSMA/CA) mechanism in which the transmitting vehicle senses the medium before transmission. In IEEE 802.11p standard, the Contention Window (CW) is defined at each node to specify the time period for which a sender needs to wait before starting transmission. The CW interval increases continuously till maximum value, if the transmission medium remains busy. The 802.11p band consists of seven channels in which the six channels are service channels (SCH) and the remaining one is control channel (CCH). The service channels are used for nonsafety applications and the control channel is used for transmission of safety messages, system management messages, and control messages [4–6].VANET based ITS informs the drivers about the road conditions like possible traffic jams, accidents, landslides, oil slippery, snow falling conditions, and so forth to enhance traffic safety, providing comfort and convenience while driving. The congestion is reduced by controlling the traffic flow with time. The drivers are assisted to find the parking spaces directly rather than creating traffic jams during search for parking. The drivers can change their routes based on prior information of ITS which reduces time and fuel and increases the safety of passengers. In addition to safety applications, VANET provides support of nonsafety applications also which includes weather updates, news, internet, multimedia, and maps [7–9].In VANET, it is difficult to maintain stable communication links with other vehicles due to dynamic topology. Hence, it incurs high communication overhead and delay during message transmission. The emergency messages need to be distributed within risk area which covers several kilometers because of high vehicular speed at highways. Therefore, an efficient scheme is required which can disseminate the messages to all the approaching vehicles towards the risk region with minimum delay and transmission overhead despite vehicles dynamic speed. The network partition occurs due to high mobility of vehicles which causes network disconnections. Besides this, the network load and delay increase in dense and congested traffic [10–12]. Hence, the most challenging task in VANET is to develop a scheme in which the vehicles can organize and arrange themselves dynamically to achieve efficient and real time communication for passenger’s safety while travelling. The protocols developed for mobile ad hoc network (MANET) are not appropriate for VANET due to the high speed and random movements of vehicles.In this paper, we propose a real time vehicular communication (RTVC) framework which addresses all the issues of VANET as discussed above. RTVC consists of two components, namely, VANET cluster scheme (VCS) and VANET multicast routing (VMR) protocol. The main aim and uniqueness of novel RTVC framework are to achieve the stable communication between vehicles within both urban and highway scenarios, which has been achieved by proposed VCS, whereas the RTVC framework achieves the real time message delivery with high throughput to multiple desired vehicles by using our VMR protocol which is based upon the multicast approach. The VMR protocol described in Section4 develops a backbone network by using the forward and backward tracking approach. This approach provides all the possible routes towards destination vehicle. In multicasting, the message copies are transmitted to multiple specified vehicles simultaneously reducing the transmission and control overhead. Consequently, multicasting improves the efficiency of message transmission even within highly mobile network [13–15]. The uniqueness of proposed protocol also lies in its several applications of safety and convenience which can be used within both urban and highway scenarios.The remaining paper is organized in the following sections. The introduction of VANET is described in Section1 along with its importance and applications. In Section 2, the literature survey has been made to demonstrate the existing VANET multicast routing protocols. The hierarchal structure of VANET has been proposed in Section 3 along with the detailed design. In Section 4, the VMR is demonstrated in combination with the VCS. Section 5 demonstrates the performance of RTVC framework by extensive simulations. Finally, the conclusion is drawn in Section 6.


## 2. Related Work

Farooq et al. [10] reviewed all the VANET multicast routing protocols in detail and identified their deficiencies. There are only few multicast routing protocols developed for VANET, in which only two of them protocols consist of cluster based routing, but none of them considered the speed limit parameter to form the clusters. Hence, these approaches are facing network fragmentation, overhead, and delay due to unstable cluster formations. There has not been any multicast VANET routing protocol developed which provides efficient real time communication within both highway and urban scenarios. Thus, there is a need for such a protocol which works efficiently in both scenarios, because traffic enters and leaves highways or urban areas unpredictably. The cluster base protocols developed for multicast communication in VANET are summarized as follows.In COIN [10, 16], the vehicle speed is kept low to maintain the radio connection between vehicles and to achieve the cluster stability. However, the vehicles speed varies rapidly according to the road conditions which results in frequent disconnections, network partitioning, and clusters instability. Moreover, this approach is not scalable for highway scenarios due to high speed limits of highways. Beside this, the cluster formation and election scheme do not work efficiently during dynamic movement and speed variations of vehicles. In CBDRP [17], the cluster formation is based upon single parameter of similar direction. Beside this, the location is used in cluster head election scheme which may not be available at the required time or cause delay in updating location. Hence, the cluster formation and election increase the clusters instability, while the number of cluster rises. Therefore, this protocol has no efficient performance within urban and highway scenarios. The remaining multicast routing protocols for VANET, other than cluster based approach, are summarized as follows.In [18, 19], the author proposed intervehicle geocast (IVG) protocol in which the vehicle location is used which may not be available at the required time as discussed in CBDRP. In addition, the transmission delay rises in congested traffic due to increase in the number of multicast groups. In [10, 20], the author developed cached geocast in which the tables are constructed to maintain the record of neighboring nodes which increases the overall transmission overhead. Moreover, this approach requires extra processing time to maintain the cache record. Another multicast VANET routing protocol is developed in [21], namely, abiding geocast which lacks in reliability because the lifetime assigned to message is short. In [22], the Gvgrid protocol consumes a lot of time in constructing routes within dynamic and dense areas. Hence, its performance is not efficient within urban areas.In [19, 23], DRG protocol experiences more network overhead and delay in dense networks because a greater number of geocast messages are kept alive for longer periods within Zone of Relevance (ZOR). In [24], the author developed robust vehicular routing protocol (ROVER), which consists of two routing phases. The protocol experiences network overhead due to control packets transmissions in the first phase of ROVER routing. In [3], the network overhead increases due to maintenance of neighbor trajectory tables. In [25], the protocol needs continuous connection to get position which may be unavailable at the required time as mentioned in CBDRP and IVG above. Moreover, the vehicles connection fails, in case of sudden speed variation. Hence, its performance is not efficient in highway scenarios where vehicles speed is very high. In DTSG [10, 26], the author proposed a time stable protocol which faces network overhead in maintaining record of messages, setting their delivery time and in management of stability phases. In [27], the cooperative adaptive cruise control (CACC) is developed in which the vehicles positions are estimated which results in high network overhead. Moreover, the network partitioning occurs at highways due to variable speed and dynamic movements of vehicles. In [28], the response time of vehicles increases in dense and congested traffic area [10].


## 3. VANET Hierarchical Structure

It is apparent that there is a need to design a structure in which the vehicles can adjust themselves dynamically to achieve a real time and stable communication. The major challenges are to maintain the message dissemination efficiently despite high mobility and dynamic topology. The foremost causes of topology changes are due to the vehicular speed mismatch and lack of vehicular coordination. The stable connections can be maintained within such a highly dynamic vehicular topology by developing the clusters of vehicles having similar speed. The cluster head is elected according to the real time vehicular scenario which performs the intracluster and intercluster communication efficiently with strong coordination. Thus, the cluster based approach can adapt itself at high mobility according to the road trajectories. In hierarchical approach, the network overhead and delay reduce due to logical organization of nodes [29].The working of VMR protocol is discussed in Section4, whereas the algorithm of VANET cluster scheme (VCS) is proposed in this section. The working of VCS consists of VANET cluster formation (VCF) and vehicles cluster maintenance (VCM). VCF is further subdivided to form stable clusters as shown in Figure 2.Figure 2
VANET cluster scheme (VCS) classification.There are only two cluster based routing protocols developed for VANET multicast communication till date [10]. However, these protocols are incapable of forming stable clusters within highly dynamic scenario like VANET [16, 17]. In addition, VCS adapts itself according to the dynamic movement of vehicles and can be optimized accordingly by SAF approach as proposed in Section 3.1.2. VCF is based upon three different speed settings formulated in cluster speed limit (CSL) in Section 3.1. In CSL, the vehicles coordination is established based upon the average speed as proposed in Section 3.1.1.Once the clusters of vehicles are formed, cluster head (CH) is elected based on the cluster threshold value (CTV) formulated in Section3.1.2. The CTV is proposed to elect that vehicle as CH which remains for extended time period within that cluster to achieve higher cluster stability. So, VCF yields a high throughput but with low overhead despite variation in density of vehicles which is an important design goal of the VCS.


### 3.1. VANET Cluster Formation (VCF)

The first phase of the VCS is to develop clusters based on slow, medium, and fast lane vehicles. The clusters of each lane are calledC
S, C
M, and C
F as shown in Figure 3. The VCHE procedure is repeated upon leaving of old CH. The CH communication is not limited to 1 hop because it accepts the vehicles memberships which fall into the Dedicated Short Range Communication (DSRC) range [30, 31]. Hence, n-clusters cover n-hop cluster members. The cluster formation is based upon CSL, CVT, CC, and VCHE which are described as follows and shown in Figure 4.Figure 3
VANET cluster scheme (VCS).Figure 4
VANET cluster organization and intercluster communication.In Figure4, the clusters are shown in each lane of road with their CHs. All clusters are labeled with their speed limits of C
S
L
F, C
S
L
M, and C
S
L
S. Similarly, the clusters of fast, medium, and slow lane are shown as C
F, C
M, and C
S. V
2 is elected as CH from C
F cluster with C
S
L
F and transmits the message to V
10 which is CH of C
M with C
S
L
M. Similarly, the V
16 of C
S with C
S
L
S received message from V
10 as shown in Figure 4. Hence, the same procedure of forwarding the messages remains in progress until all the vehicles are informed.


#### 3.1.1. Cluster Speed Limit (CSL)

The CSL is proposed in VCF to develop efficient communication even within high mobility, such as in the VANET scenario in which the decision needs to be taken rapidly. The aim of adding a speed parameter in CSL is to achieve the stable cluster formation. In addition to this, the CSL balances the network load by distributing the traffic among several clusters.In the CSL, the maximum speed limit is supposed to be 120 km/h and it is based upon three different speed limits that can also be represented as road lanes, which are given as follows and shown in Figure4:(1)
Clusters of slow lane (C
S): C
S
L
S < 60 km/h.
(2)
Clusters of medium lane (C
M): 60 ≤ C
S
L
M < 90 km/h.
(3)
Clusters of fast lane (C
F): 90 ≤ C
S
L
F ≤ 120 km/h.C
S
L
S is specified to be <60 km/h for constructing clusters of slow lane vehicles only, which develops stable clusters and elects the CHs of longer lifetime. Similarly, the C
S
L
M limit is defined to handle the medium speed vehicles only, which reduces the CMs and CHs switching even within high mobility. The C
S
L
F range is specified from 90 km/h to 120 km/h to handle only high speed vehicles of fast lane within the same cluster. As a result of specifying CSL for each road lane, the cluster formation becomes stable due to arrangement of vehicles within similar speed clusters. Secondly, the VCHE procedure becomes efficient due to predefined speed ranges for cluster formation.If the average speed (V
a
v
g
s
p
d) of vehicles matches with the range of C
S, C
M, or C
F, then it becomes the member of that cluster. The V
a
v
g
s
p
d is computed upon each vehicle which is based on the speed reading of the last 2 minutes. V
a
v
g
s
p
d is computed to reduce the number of CMs and CHs switches which enhances the cluster stability. Besides this, there are some other promising advantages of developing clusters based upon CSL which are as follows:(1)
In some scenarios, there is need to address only high speed vehicles or some specified lane vehicles such as during road maintenance or lights repairing and at sharp turns and steeps.
(2)
In most cases, heavy vehicles need to be informed about several warnings or rules like bridge height, road conditions, overloading limits, and so forth.


#### 3.1.2. Cluster Threshold Value (CTV)

The CH is elected to control and manage the CMs despite high mobility and dynamic road trajectories. Therefore, the CH lifetime should be long enough to reduce the network overhead and to increase the cluster stability. The network overhead reduces upon the less number of CHs’ switching. Therefore, the CTV values are specified for each road lane to elect the CH with longer lifetime.The CTV is used to take the decision upon VCHE, CM joining, and CM leaving which is based upon an average speed of the vehicle (V
a
v
g
s
p
d) within slow, medium, and fast lane as specified below:CTV CASE-1:C
T
V
S = Avgspeed (C
S
L
S) = 30
±
u.
CTV CASE-2:C
T
V
M = Avgspeed (C
S
L
M) = 75
±
u.
CTV CASE-3:C
T
V
F = Avgspeed (C
S
L
F) = 105
±
u,whereu is the speed adjustment factor (SAF). The appropriate value of u for most of the applications can be considered as from 1 to 10. In addition, the speed adjustment factor (SAF) can be varied according to the requirement, to achieve the desired cluster stability depending upon the VANET applications as given in following scenarios.SAF Emergency Scenario. In case of emergency message dissemination, the first incoming vehicle (IV) can be selected as CH by increasing the value of u. Similarly, by decreasing the value of u, the slow speed vehicle can be selected as CH. The VCHE procedure is completed rapidly upon satisfaction of CTV criteria.SAF Vehicular Speed Scenario. In C
S, the vehicles of speed less than 20 km/h and greater than 55 km/h also exist. The VCHE procedure is based upon the value of C
T
V
S. The C
T
V
S calculations are based upon the average speed of C
S
L
S which is 30
±
u as shown in CTV CASE-1. Then, SAF “u” can be increased from 1 to 10 to achieve the desired stability within the cluster. Hence, if u is increased to 5, then the resultant C
T
V
S for VCHE becomes 35 km/h which lies in between the 20 km/h and 55 km/h. Hence, the elected CH of speed nearly 35 km/h is able to maintain the stable communication links with all vehicles of C
S.The SAF is varied as follows to develop stable clusters at highways:(1)
ForC
T
V
F, increase the value of u for fast lane vehicles to elect the CH from the front vehicles.
(2)
ForC
T
V
M, maintain u
=
5 for medium lane vehicles to elect the CH from the middle of the cluster.
(3)
ForC
T
V
S, reduce the value of u for slow lane vehicles to elect the CH from the last vehicles.The role of CTV in achieving cluster stability and to enhance VCF performance during VCHE is as follows:(a)
The processing time in speed computation of vehicles for cluster head election is reduced by specifying the CTV threshold values in the algorithm.
(b)
The VCHE process is expedited by electing the CH from first IVs.
(c)
The cluster stability is also enhanced by maintaining the status of CH until it leaves the cluster itself.


#### 3.1.3. Clusters Construction

In this section, we develop a model for constructing the clusters which are based upon the CSL and CTV. LetC
F, C
M, and C
S be the clusters among three lanes of road as shown below:(1)
C
F
=
f
1
∈
α
f
1
∣
θ
1
f
2
∈
α
f
2
∣
θ
2
⋮
f
n
∈
α
f
n
∣
θ
n
,where f
1, f
2, and f
n are the cluster members of C
F. α
f
1 is the average speed of cluster member (CM) f
1 on fast lane f with direction θ. The direction parameter is considered only to represent the movement of vehicles in specified lane. Similarly, α
f
n is the speed of vehicle n on fast lane f with direction θ. The CSL for α
f is “90 ≤ C
S
L
F ≤ 120” as discussed in Section 3.1.1.Similarly, the cluster formation for medium lane is given as follows:(2)
C
M
=
m
1
∈
α
m
1
∣
θ
1
m
2
∈
α
m
2
∣
θ
2
⋮
m
n
∈
α
m
n
∣
θ
n
,where m
1, m
2, and m
n are the cluster members of C
M. α
m
1 is the average speed of cluster member (CM) m
1 on medium lane m with direction θ. Similarly, α
m
n is the speed of vehicle n on medium lane m with direction θ. The CSL for α
m is “60 ≤ C
S
L
M < 90” as discussed in Section 3.1.1.Moreover, the cluster formation for slow lane is given as follows:(3)
C
S
=
s
1
∈
α
s
1
∣
θ
1
s
2
∈
α
s
2
∣
θ
2
⋮
s
n
∈
α
s
n
∣
θ
n
,where s
1, s
2, and s
n are the cluster members of C
S. α
s
1 is the speed of cluster member (CM) s
1 on slow lane s with direction θ. Similarly, α
s
n is the average speed of vehicle on slow lanes with direction θ. The CSL for α
s is “C
S
L
S < 60.”


#### 3.1.4. Vehicles Cluster Header Election (VCHE)

VCF elects the CH efficiently by using the CSL scheme as proposed in Section3.1.1. Unlike in literature protocols [10], the parameters such as distance, location, or both are used in all VANET multicast routing protocols causing network overhead and delay during message dissemination. It is possible to develop efficient communication by using average speed parameter only, as proposed in CSL scheme of RTVC framework. In order to achieve high stability in VANET clustering, the cluster head status is maintained till the CH leaves that cluster itself. Therefore, the lifetime of CH is longer which reduces the overall network overhead of electing CHs after every few milliseconds. Besides this, the CTV value is also specified above in Section 3.1.2 to achieve the cluster stability. The procedure of VCHE is outlined as follows.Every vehiclev maintains a list of all neighbor vehicles by multicast advertisement which is discussed in Section 4. The neighbor list consists of vehicle ID and its average speed. The VCHE process is initiated as soon as the neighbor vehicles list becomes ready. Each vehicle v performs the following steps:(a)
Find the neighbor vehicles and theirV
a
v
g
s
p
d.
(b)
CompareV
a
v
g
s
p
d of all vehicles with the CTV values.
(c)
Elect the vehicle as CH as soon as its average speed is similar or most near to the specifiedC
T
V
±
u value by stopping the comparison process with remaining vehicles.
(d)
By selecting, the first appropriate vehicle as CH enhances the processing speed of CH election process and reduces the network overhead.
(e)
The CH continues to functions as CH till it remains part of that cluster.The VCHE procedure is initiated only first time during cluster creation. The CH withdraws its status only in case of leaving cluster. The VCHE process is not initiated again in case of new vehicle joining. Hence, it reduces the delay and processing overhead of VCS. The pseudocode for VCHE procedure is given in Algorithm1 and the VCS flowchart is represented in Figure 5.Algorithm 1:VCHE procedure.
For allV
a in Λ (n) do             //for all vehicles within the ad hoc network
if STATUS = NONE then//when no cluster head is elected, nor cluster created
vehicle_speed = compute_vehicles_avgspeed (V
a) //all vehicles average speed of the last 2 minutes is computed
if vehicle_speed = CSLF then        //if speed lies within range of fast lane
CHF = CTVF              //Cluster head of fast lane is elected
set STATUS = HEADF        //set the status of fast lane cluster
else if vehicle_speed = CSLM then       //keep computing the speed
CHM = CTVM            //if speed lies within range of medium lane
set STATUS = HEADM       //Cluster head of medium lane is elected
else if vehicle_speed = CSLS then,
CHS = CTVS
set STATUS = HEADS
end if
else ifV
a.STATUS = HEADF
H
E
A
D
M
H
E
A
D
S    //if the cluster head is elected within any three lanes
Process maintain_clusterhead ()        //maintain the cluster head
Process join_member ()        //provide cluster members membership
Process leave_member ()         //leave members when vehicles exceed the CSL
else
set V
a.STATUS = NONE       //if no CH is elected, then set CH status to NONE
end ifFigure 5
VANET cluster scheme (VCS).


### 3.2. Vehicles Cluster Maintenance (VCM)

Cluster formation in VANET requires periodic maintenance for efficient communication among vehicles because the vehicles keep joining and leaving clusters due to the highly dynamic VANET scenario. There are three major types in which the VANET topology requires maintenance, which are vehicle joining, leaving, and merging. Hence, there is a need to specify such maintenance scheme which is fast enough to get the decision and response rapidly despite vehicles high speed. If the new incoming vehicle (IV) average speed lies within range of CSL, then it is added into the CMs list which is maintained by the respective CH as shown in Algorithm2. The CMs joining delay is also monitored to maintain the efficiency of the proposed protocol.Algorithm 2:Cluster joining.
For allV
n in Λ (n) do
if speed (IVs) =
=
C
T
V
F
C
T
V
M
C
T
V
S        //if speed of incoming vehicles (IVS) matches with any CTV range
CH_send_join_request (C
F
C
M
C
S, cluster_headI
D, T
1) //CH sends join request to CM with its CH_ID at T
1
join_ack_CM (C
F
C
M
C
S, Cluster_memberI
D, T
2)   //CM sends acknowledgement of joining with its CM_ID at T
2
CM_join_delay (T
2
-
T
1)               //calculates Cluster Member joining delay
end ifSimilarly, if the vehicle speed goes beyond the range of CSL, then it leaves the current CH and joins another CH after fulfilling the requirements of that CSL. In addition to this, when two clusters of the same CSL come in contact, then both merge into a single cluster. The incoming CHs or CMs leave their present status and join the new CH as cluster members as shown in Algorithm3. The merging of V
18 with C
M is shown in Figure 4 also.Algorithm 3:Cluster merging.
For allV
n in Λ (n) do
if CHI
V
S (C
F
C
M
C
S) ← received (multicast advertisement (CHN
E
X
T))   //if CH of IVS received multicast advertisement of
CH ahead
if CHI
V
S (CTV) == CHA
H
E
A
D (CTV) then         //if CH of IVS threshold matches with the CTV of
CH ahead
CHI
V
S = CM (CHA
H
E
A
D)          //then CH of IVS become member of CH ahead
CHI
V
S (CMs) = CMs (CHA
H
E
A
D)      //Cluster members of IVS become member of
CH ahead
Merge (CHI
V
S, CHA
H
E
A
D)           //CH of IVS merge with CH ahead
end if
end if


### 3.3. Neighbor Cluster Discovery

The destination vehicles can be multihop away from the cluster of source vehicle. Hence, packets are sent through intermediate clusters by intercluster communication. Therefore, all clusters are connected with each other to achieve multihop routing within clusters as shown in Figure4.Those vehicles which listen to the neighboring cluster members (CMs) or cluster heads (CHs) are called gateways. Sometimes, there are multiple gateways existing between the two clusters. CHs also maintain the record of gateways for intercluster communication. Therefore, a set consisting of gateway vehicles (GVs) is built to achieve multihop routing and intercluster communication. Letm
v
j be the set of member vehicles of cluster head H
j. Similarly, m
v
k be the set of vehicles of neighboring cluster head H
k. H
j maintains a set of gateway vehicles G
V
j such that(4)
G
V
j
H
j
=
x
∈
m
v
j
∈
Λ
V
x
.Similarly, for gateway of cluster head H
k
(5)
G
V
k
H
k
=
y
∈
m
v
k
∈
Λ
V
y
,where Λ
(
V
x
) is the set of neighbors of vehicle V
x. A member vehicle V
x of cluster head H
j belongs to the gateway vehicle G
V
j of cluster head H
j. Similarly, H
k or some vehicle V
y of H
k exists in the neighbor set of V
x. Each cluster maintains the list of neighboring clusters and gateways to route packet after cluster formation. The cluster maintenance along with routing is discussed in Section 4.


## 3.1. VANET Cluster Formation (VCF)

The first phase of the VCS is to develop clusters based on slow, medium, and fast lane vehicles. The clusters of each lane are calledC
S, C
M, and C
F as shown in Figure 3. The VCHE procedure is repeated upon leaving of old CH. The CH communication is not limited to 1 hop because it accepts the vehicles memberships which fall into the Dedicated Short Range Communication (DSRC) range [30, 31]. Hence, n-clusters cover n-hop cluster members. The cluster formation is based upon CSL, CVT, CC, and VCHE which are described as follows and shown in Figure 4.Figure 3
VANET cluster scheme (VCS).Figure 4
VANET cluster organization and intercluster communication.In Figure4, the clusters are shown in each lane of road with their CHs. All clusters are labeled with their speed limits of C
S
L
F, C
S
L
M, and C
S
L
S. Similarly, the clusters of fast, medium, and slow lane are shown as C
F, C
M, and C
S. V
2 is elected as CH from C
F cluster with C
S
L
F and transmits the message to V
10 which is CH of C
M with C
S
L
M. Similarly, the V
16 of C
S with C
S
L
S received message from V
10 as shown in Figure 4. Hence, the same procedure of forwarding the messages remains in progress until all the vehicles are informed.


### 3.1.1. Cluster Speed Limit (CSL)

The CSL is proposed in VCF to develop efficient communication even within high mobility, such as in the VANET scenario in which the decision needs to be taken rapidly. The aim of adding a speed parameter in CSL is to achieve the stable cluster formation. In addition to this, the CSL balances the network load by distributing the traffic among several clusters.In the CSL, the maximum speed limit is supposed to be 120 km/h and it is based upon three different speed limits that can also be represented as road lanes, which are given as follows and shown in Figure4:(1)
Clusters of slow lane (C
S): C
S
L
S < 60 km/h.
(2)
Clusters of medium lane (C
M): 60 ≤ C
S
L
M < 90 km/h.
(3)
Clusters of fast lane (C
F): 90 ≤ C
S
L
F ≤ 120 km/h.C
S
L
S is specified to be <60 km/h for constructing clusters of slow lane vehicles only, which develops stable clusters and elects the CHs of longer lifetime. Similarly, the C
S
L
M limit is defined to handle the medium speed vehicles only, which reduces the CMs and CHs switching even within high mobility. The C
S
L
F range is specified from 90 km/h to 120 km/h to handle only high speed vehicles of fast lane within the same cluster. As a result of specifying CSL for each road lane, the cluster formation becomes stable due to arrangement of vehicles within similar speed clusters. Secondly, the VCHE procedure becomes efficient due to predefined speed ranges for cluster formation.If the average speed (V
a
v
g
s
p
d) of vehicles matches with the range of C
S, C
M, or C
F, then it becomes the member of that cluster. The V
a
v
g
s
p
d is computed upon each vehicle which is based on the speed reading of the last 2 minutes. V
a
v
g
s
p
d is computed to reduce the number of CMs and CHs switches which enhances the cluster stability. Besides this, there are some other promising advantages of developing clusters based upon CSL which are as follows:(1)
In some scenarios, there is need to address only high speed vehicles or some specified lane vehicles such as during road maintenance or lights repairing and at sharp turns and steeps.
(2)
In most cases, heavy vehicles need to be informed about several warnings or rules like bridge height, road conditions, overloading limits, and so forth.


### 3.1.2. Cluster Threshold Value (CTV)

The CH is elected to control and manage the CMs despite high mobility and dynamic road trajectories. Therefore, the CH lifetime should be long enough to reduce the network overhead and to increase the cluster stability. The network overhead reduces upon the less number of CHs’ switching. Therefore, the CTV values are specified for each road lane to elect the CH with longer lifetime.The CTV is used to take the decision upon VCHE, CM joining, and CM leaving which is based upon an average speed of the vehicle (V
a
v
g
s
p
d) within slow, medium, and fast lane as specified below:CTV CASE-1:C
T
V
S = Avgspeed (C
S
L
S) = 30
±
u.
CTV CASE-2:C
T
V
M = Avgspeed (C
S
L
M) = 75
±
u.
CTV CASE-3:C
T
V
F = Avgspeed (C
S
L
F) = 105
±
u,whereu is the speed adjustment factor (SAF). The appropriate value of u for most of the applications can be considered as from 1 to 10. In addition, the speed adjustment factor (SAF) can be varied according to the requirement, to achieve the desired cluster stability depending upon the VANET applications as given in following scenarios.SAF Emergency Scenario. In case of emergency message dissemination, the first incoming vehicle (IV) can be selected as CH by increasing the value of u. Similarly, by decreasing the value of u, the slow speed vehicle can be selected as CH. The VCHE procedure is completed rapidly upon satisfaction of CTV criteria.SAF Vehicular Speed Scenario. In C
S, the vehicles of speed less than 20 km/h and greater than 55 km/h also exist. The VCHE procedure is based upon the value of C
T
V
S. The C
T
V
S calculations are based upon the average speed of C
S
L
S which is 30
±
u as shown in CTV CASE-1. Then, SAF “u” can be increased from 1 to 10 to achieve the desired stability within the cluster. Hence, if u is increased to 5, then the resultant C
T
V
S for VCHE becomes 35 km/h which lies in between the 20 km/h and 55 km/h. Hence, the elected CH of speed nearly 35 km/h is able to maintain the stable communication links with all vehicles of C
S.The SAF is varied as follows to develop stable clusters at highways:(1)
ForC
T
V
F, increase the value of u for fast lane vehicles to elect the CH from the front vehicles.
(2)
ForC
T
V
M, maintain u
=
5 for medium lane vehicles to elect the CH from the middle of the cluster.
(3)
ForC
T
V
S, reduce the value of u for slow lane vehicles to elect the CH from the last vehicles.The role of CTV in achieving cluster stability and to enhance VCF performance during VCHE is as follows:(a)
The processing time in speed computation of vehicles for cluster head election is reduced by specifying the CTV threshold values in the algorithm.
(b)
The VCHE process is expedited by electing the CH from first IVs.
(c)
The cluster stability is also enhanced by maintaining the status of CH until it leaves the cluster itself.


### 3.1.3. Clusters Construction

In this section, we develop a model for constructing the clusters which are based upon the CSL and CTV. LetC
F, C
M, and C
S be the clusters among three lanes of road as shown below:(1)
C
F
=
f
1
∈
α
f
1
∣
θ
1
f
2
∈
α
f
2
∣
θ
2
⋮
f
n
∈
α
f
n
∣
θ
n
,where f
1, f
2, and f
n are the cluster members of C
F. α
f
1 is the average speed of cluster member (CM) f
1 on fast lane f with direction θ. The direction parameter is considered only to represent the movement of vehicles in specified lane. Similarly, α
f
n is the speed of vehicle n on fast lane f with direction θ. The CSL for α
f is “90 ≤ C
S
L
F ≤ 120” as discussed in Section 3.1.1.Similarly, the cluster formation for medium lane is given as follows:(2)
C
M
=
m
1
∈
α
m
1
∣
θ
1
m
2
∈
α
m
2
∣
θ
2
⋮
m
n
∈
α
m
n
∣
θ
n
,where m
1, m
2, and m
n are the cluster members of C
M. α
m
1 is the average speed of cluster member (CM) m
1 on medium lane m with direction θ. Similarly, α
m
n is the speed of vehicle n on medium lane m with direction θ. The CSL for α
m is “60 ≤ C
S
L
M < 90” as discussed in Section 3.1.1.Moreover, the cluster formation for slow lane is given as follows:(3)
C
S
=
s
1
∈
α
s
1
∣
θ
1
s
2
∈
α
s
2
∣
θ
2
⋮
s
n
∈
α
s
n
∣
θ
n
,where s
1, s
2, and s
n are the cluster members of C
S. α
s
1 is the speed of cluster member (CM) s
1 on slow lane s with direction θ. Similarly, α
s
n is the average speed of vehicle on slow lanes with direction θ. The CSL for α
s is “C
S
L
S < 60.”


### 3.1.4. Vehicles Cluster Header Election (VCHE)

VCF elects the CH efficiently by using the CSL scheme as proposed in Section3.1.1. Unlike in literature protocols [10], the parameters such as distance, location, or both are used in all VANET multicast routing protocols causing network overhead and delay during message dissemination. It is possible to develop efficient communication by using average speed parameter only, as proposed in CSL scheme of RTVC framework. In order to achieve high stability in VANET clustering, the cluster head status is maintained till the CH leaves that cluster itself. Therefore, the lifetime of CH is longer which reduces the overall network overhead of electing CHs after every few milliseconds. Besides this, the CTV value is also specified above in Section 3.1.2 to achieve the cluster stability. The procedure of VCHE is outlined as follows.Every vehiclev maintains a list of all neighbor vehicles by multicast advertisement which is discussed in Section 4. The neighbor list consists of vehicle ID and its average speed. The VCHE process is initiated as soon as the neighbor vehicles list becomes ready. Each vehicle v performs the following steps:(a)
Find the neighbor vehicles and theirV
a
v
g
s
p
d.
(b)
CompareV
a
v
g
s
p
d of all vehicles with the CTV values.
(c)
Elect the vehicle as CH as soon as its average speed is similar or most near to the specifiedC
T
V
±
u value by stopping the comparison process with remaining vehicles.
(d)
By selecting, the first appropriate vehicle as CH enhances the processing speed of CH election process and reduces the network overhead.
(e)
The CH continues to functions as CH till it remains part of that cluster.The VCHE procedure is initiated only first time during cluster creation. The CH withdraws its status only in case of leaving cluster. The VCHE process is not initiated again in case of new vehicle joining. Hence, it reduces the delay and processing overhead of VCS. The pseudocode for VCHE procedure is given in Algorithm1 and the VCS flowchart is represented in Figure 5.Algorithm 1:VCHE procedure.
For allV
a in Λ (n) do             //for all vehicles within the ad hoc network
if STATUS = NONE then//when no cluster head is elected, nor cluster created
vehicle_speed = compute_vehicles_avgspeed (V
a) //all vehicles average speed of the last 2 minutes is computed
if vehicle_speed = CSLF then        //if speed lies within range of fast lane
CHF = CTVF              //Cluster head of fast lane is elected
set STATUS = HEADF        //set the status of fast lane cluster
else if vehicle_speed = CSLM then       //keep computing the speed
CHM = CTVM            //if speed lies within range of medium lane
set STATUS = HEADM       //Cluster head of medium lane is elected
else if vehicle_speed = CSLS then,
CHS = CTVS
set STATUS = HEADS
end if
else ifV
a.STATUS = HEADF
H
E
A
D
M
H
E
A
D
S    //if the cluster head is elected within any three lanes
Process maintain_clusterhead ()        //maintain the cluster head
Process join_member ()        //provide cluster members membership
Process leave_member ()         //leave members when vehicles exceed the CSL
else
set V
a.STATUS = NONE       //if no CH is elected, then set CH status to NONE
end ifFigure 5
VANET cluster scheme (VCS).


## 3.1.1. Cluster Speed Limit (CSL)

The CSL is proposed in VCF to develop efficient communication even within high mobility, such as in the VANET scenario in which the decision needs to be taken rapidly. The aim of adding a speed parameter in CSL is to achieve the stable cluster formation. In addition to this, the CSL balances the network load by distributing the traffic among several clusters.In the CSL, the maximum speed limit is supposed to be 120 km/h and it is based upon three different speed limits that can also be represented as road lanes, which are given as follows and shown in Figure4:(1)
Clusters of slow lane (C
S): C
S
L
S < 60 km/h.
(2)
Clusters of medium lane (C
M): 60 ≤ C
S
L
M < 90 km/h.
(3)
Clusters of fast lane (C
F): 90 ≤ C
S
L
F ≤ 120 km/h.C
S
L
S is specified to be <60 km/h for constructing clusters of slow lane vehicles only, which develops stable clusters and elects the CHs of longer lifetime. Similarly, the C
S
L
M limit is defined to handle the medium speed vehicles only, which reduces the CMs and CHs switching even within high mobility. The C
S
L
F range is specified from 90 km/h to 120 km/h to handle only high speed vehicles of fast lane within the same cluster. As a result of specifying CSL for each road lane, the cluster formation becomes stable due to arrangement of vehicles within similar speed clusters. Secondly, the VCHE procedure becomes efficient due to predefined speed ranges for cluster formation.If the average speed (V
a
v
g
s
p
d) of vehicles matches with the range of C
S, C
M, or C
F, then it becomes the member of that cluster. The V
a
v
g
s
p
d is computed upon each vehicle which is based on the speed reading of the last 2 minutes. V
a
v
g
s
p
d is computed to reduce the number of CMs and CHs switches which enhances the cluster stability. Besides this, there are some other promising advantages of developing clusters based upon CSL which are as follows:(1)
In some scenarios, there is need to address only high speed vehicles or some specified lane vehicles such as during road maintenance or lights repairing and at sharp turns and steeps.
(2)
In most cases, heavy vehicles need to be informed about several warnings or rules like bridge height, road conditions, overloading limits, and so forth.


## 3.1.2. Cluster Threshold Value (CTV)

The CH is elected to control and manage the CMs despite high mobility and dynamic road trajectories. Therefore, the CH lifetime should be long enough to reduce the network overhead and to increase the cluster stability. The network overhead reduces upon the less number of CHs’ switching. Therefore, the CTV values are specified for each road lane to elect the CH with longer lifetime.The CTV is used to take the decision upon VCHE, CM joining, and CM leaving which is based upon an average speed of the vehicle (V
a
v
g
s
p
d) within slow, medium, and fast lane as specified below:CTV CASE-1:C
T
V
S = Avgspeed (C
S
L
S) = 30
±
u.
CTV CASE-2:C
T
V
M = Avgspeed (C
S
L
M) = 75
±
u.
CTV CASE-3:C
T
V
F = Avgspeed (C
S
L
F) = 105
±
u,whereu is the speed adjustment factor (SAF). The appropriate value of u for most of the applications can be considered as from 1 to 10. In addition, the speed adjustment factor (SAF) can be varied according to the requirement, to achieve the desired cluster stability depending upon the VANET applications as given in following scenarios.SAF Emergency Scenario. In case of emergency message dissemination, the first incoming vehicle (IV) can be selected as CH by increasing the value of u. Similarly, by decreasing the value of u, the slow speed vehicle can be selected as CH. The VCHE procedure is completed rapidly upon satisfaction of CTV criteria.SAF Vehicular Speed Scenario. In C
S, the vehicles of speed less than 20 km/h and greater than 55 km/h also exist. The VCHE procedure is based upon the value of C
T
V
S. The C
T
V
S calculations are based upon the average speed of C
S
L
S which is 30
±
u as shown in CTV CASE-1. Then, SAF “u” can be increased from 1 to 10 to achieve the desired stability within the cluster. Hence, if u is increased to 5, then the resultant C
T
V
S for VCHE becomes 35 km/h which lies in between the 20 km/h and 55 km/h. Hence, the elected CH of speed nearly 35 km/h is able to maintain the stable communication links with all vehicles of C
S.The SAF is varied as follows to develop stable clusters at highways:(1)
ForC
T
V
F, increase the value of u for fast lane vehicles to elect the CH from the front vehicles.
(2)
ForC
T
V
M, maintain u
=
5 for medium lane vehicles to elect the CH from the middle of the cluster.
(3)
ForC
T
V
S, reduce the value of u for slow lane vehicles to elect the CH from the last vehicles.The role of CTV in achieving cluster stability and to enhance VCF performance during VCHE is as follows:(a)
The processing time in speed computation of vehicles for cluster head election is reduced by specifying the CTV threshold values in the algorithm.
(b)
The VCHE process is expedited by electing the CH from first IVs.
(c)
The cluster stability is also enhanced by maintaining the status of CH until it leaves the cluster itself.


## 3.1.3. Clusters Construction

In this section, we develop a model for constructing the clusters which are based upon the CSL and CTV. LetC
F, C
M, and C
S be the clusters among three lanes of road as shown below:(1)
C
F
=
f
1
∈
α
f
1
∣
θ
1
f
2
∈
α
f
2
∣
θ
2
⋮
f
n
∈
α
f
n
∣
θ
n
,where f
1, f
2, and f
n are the cluster members of C
F. α
f
1 is the average speed of cluster member (CM) f
1 on fast lane f with direction θ. The direction parameter is considered only to represent the movement of vehicles in specified lane. Similarly, α
f
n is the speed of vehicle n on fast lane f with direction θ. The CSL for α
f is “90 ≤ C
S
L
F ≤ 120” as discussed in Section 3.1.1.Similarly, the cluster formation for medium lane is given as follows:(2)
C
M
=
m
1
∈
α
m
1
∣
θ
1
m
2
∈
α
m
2
∣
θ
2
⋮
m
n
∈
α
m
n
∣
θ
n
,where m
1, m
2, and m
n are the cluster members of C
M. α
m
1 is the average speed of cluster member (CM) m
1 on medium lane m with direction θ. Similarly, α
m
n is the speed of vehicle n on medium lane m with direction θ. The CSL for α
m is “60 ≤ C
S
L
M < 90” as discussed in Section 3.1.1.Moreover, the cluster formation for slow lane is given as follows:(3)
C
S
=
s
1
∈
α
s
1
∣
θ
1
s
2
∈
α
s
2
∣
θ
2
⋮
s
n
∈
α
s
n
∣
θ
n
,where s
1, s
2, and s
n are the cluster members of C
S. α
s
1 is the speed of cluster member (CM) s
1 on slow lane s with direction θ. Similarly, α
s
n is the average speed of vehicle on slow lanes with direction θ. The CSL for α
s is “C
S
L
S < 60.”


## 3.1.4. Vehicles Cluster Header Election (VCHE)

VCF elects the CH efficiently by using the CSL scheme as proposed in Section3.1.1. Unlike in literature protocols [10], the parameters such as distance, location, or both are used in all VANET multicast routing protocols causing network overhead and delay during message dissemination. It is possible to develop efficient communication by using average speed parameter only, as proposed in CSL scheme of RTVC framework. In order to achieve high stability in VANET clustering, the cluster head status is maintained till the CH leaves that cluster itself. Therefore, the lifetime of CH is longer which reduces the overall network overhead of electing CHs after every few milliseconds. Besides this, the CTV value is also specified above in Section 3.1.2 to achieve the cluster stability. The procedure of VCHE is outlined as follows.Every vehiclev maintains a list of all neighbor vehicles by multicast advertisement which is discussed in Section 4. The neighbor list consists of vehicle ID and its average speed. The VCHE process is initiated as soon as the neighbor vehicles list becomes ready. Each vehicle v performs the following steps:(a)
Find the neighbor vehicles and theirV
a
v
g
s
p
d.
(b)
CompareV
a
v
g
s
p
d of all vehicles with the CTV values.
(c)
Elect the vehicle as CH as soon as its average speed is similar or most near to the specifiedC
T
V
±
u value by stopping the comparison process with remaining vehicles.
(d)
By selecting, the first appropriate vehicle as CH enhances the processing speed of CH election process and reduces the network overhead.
(e)
The CH continues to functions as CH till it remains part of that cluster.The VCHE procedure is initiated only first time during cluster creation. The CH withdraws its status only in case of leaving cluster. The VCHE process is not initiated again in case of new vehicle joining. Hence, it reduces the delay and processing overhead of VCS. The pseudocode for VCHE procedure is given in Algorithm1 and the VCS flowchart is represented in Figure 5.Algorithm 1:VCHE procedure.
For allV
a in Λ (n) do             //for all vehicles within the ad hoc network
if STATUS = NONE then//when no cluster head is elected, nor cluster created
vehicle_speed = compute_vehicles_avgspeed (V
a) //all vehicles average speed of the last 2 minutes is computed
if vehicle_speed = CSLF then        //if speed lies within range of fast lane
CHF = CTVF              //Cluster head of fast lane is elected
set STATUS = HEADF        //set the status of fast lane cluster
else if vehicle_speed = CSLM then       //keep computing the speed
CHM = CTVM            //if speed lies within range of medium lane
set STATUS = HEADM       //Cluster head of medium lane is elected
else if vehicle_speed = CSLS then,
CHS = CTVS
set STATUS = HEADS
end if
else ifV
a.STATUS = HEADF
H
E
A
D
M
H
E
A
D
S    //if the cluster head is elected within any three lanes
Process maintain_clusterhead ()        //maintain the cluster head
Process join_member ()        //provide cluster members membership
Process leave_member ()         //leave members when vehicles exceed the CSL
else
set V
a.STATUS = NONE       //if no CH is elected, then set CH status to NONE
end ifFigure 5
VANET cluster scheme (VCS).


## 3.2. Vehicles Cluster Maintenance (VCM)

Cluster formation in VANET requires periodic maintenance for efficient communication among vehicles because the vehicles keep joining and leaving clusters due to the highly dynamic VANET scenario. There are three major types in which the VANET topology requires maintenance, which are vehicle joining, leaving, and merging. Hence, there is a need to specify such maintenance scheme which is fast enough to get the decision and response rapidly despite vehicles high speed. If the new incoming vehicle (IV) average speed lies within range of CSL, then it is added into the CMs list which is maintained by the respective CH as shown in Algorithm2. The CMs joining delay is also monitored to maintain the efficiency of the proposed protocol.Algorithm 2:Cluster joining.
For allV
n in Λ (n) do
if speed (IVs) =
=
C
T
V
F
C
T
V
M
C
T
V
S        //if speed of incoming vehicles (IVS) matches with any CTV range
CH_send_join_request (C
F
C
M
C
S, cluster_headI
D, T
1) //CH sends join request to CM with its CH_ID at T
1
join_ack_CM (C
F
C
M
C
S, Cluster_memberI
D, T
2)   //CM sends acknowledgement of joining with its CM_ID at T
2
CM_join_delay (T
2
-
T
1)               //calculates Cluster Member joining delay
end ifSimilarly, if the vehicle speed goes beyond the range of CSL, then it leaves the current CH and joins another CH after fulfilling the requirements of that CSL. In addition to this, when two clusters of the same CSL come in contact, then both merge into a single cluster. The incoming CHs or CMs leave their present status and join the new CH as cluster members as shown in Algorithm3. The merging of V
18 with C
M is shown in Figure 4 also.Algorithm 3:Cluster merging.
For allV
n in Λ (n) do
if CHI
V
S (C
F
C
M
C
S) ← received (multicast advertisement (CHN
E
X
T))   //if CH of IVS received multicast advertisement of
CH ahead
if CHI
V
S (CTV) == CHA
H
E
A
D (CTV) then         //if CH of IVS threshold matches with the CTV of
CH ahead
CHI
V
S = CM (CHA
H
E
A
D)          //then CH of IVS become member of CH ahead
CHI
V
S (CMs) = CMs (CHA
H
E
A
D)      //Cluster members of IVS become member of
CH ahead
Merge (CHI
V
S, CHA
H
E
A
D)           //CH of IVS merge with CH ahead
end if
end if


## 3.3. Neighbor Cluster Discovery

The destination vehicles can be multihop away from the cluster of source vehicle. Hence, packets are sent through intermediate clusters by intercluster communication. Therefore, all clusters are connected with each other to achieve multihop routing within clusters as shown in Figure4.Those vehicles which listen to the neighboring cluster members (CMs) or cluster heads (CHs) are called gateways. Sometimes, there are multiple gateways existing between the two clusters. CHs also maintain the record of gateways for intercluster communication. Therefore, a set consisting of gateway vehicles (GVs) is built to achieve multihop routing and intercluster communication. Letm
v
j be the set of member vehicles of cluster head H
j. Similarly, m
v
k be the set of vehicles of neighboring cluster head H
k. H
j maintains a set of gateway vehicles G
V
j such that(4)
G
V
j
H
j
=
x
∈
m
v
j
∈
Λ
V
x
.Similarly, for gateway of cluster head H
k
(5)
G
V
k
H
k
=
y
∈
m
v
k
∈
Λ
V
y
,where Λ
(
V
x
) is the set of neighbors of vehicle V
x. A member vehicle V
x of cluster head H
j belongs to the gateway vehicle G
V
j of cluster head H
j. Similarly, H
k or some vehicle V
y of H
k exists in the neighbor set of V
x. Each cluster maintains the list of neighboring clusters and gateways to route packet after cluster formation. The cluster maintenance along with routing is discussed in Section 4.


## 4. VANET Multicast Routing (VMR)

The goal of RTVC framework is to achieve efficient and real time routing among vehicles in urban and highway scenarios despite highly dynamic topology. RTVC framework fulfills this by developing clusters among vehicles based upon average speed and direction as mentioned in VCS, to achieve stability while routing messages. VANET multicast routing (VMR) protocol is proposed to deliver packets from source cluster to the destination vehicle in two phases. In the first phase, the route is established from source vehicle to its CH called forward tracking. Similarly, in the second phase the route is formed from CH to the destination vehicles through intermediate cluster heads called backward tracking.The proposed and novel VMR protocol performs multicast communication among clusters through multicast advertisements in VANETs to handle highly dynamic topology. This multicast advertisement is used to elect CHs according to the procedure specified in VCHE. In addition, the multicast advertisement maintains the cluster and manage the joining and leaving of cluster member vehicles. VMR has reduced the network overhead by distributing the routing load among several clusters. The aim of adopting the multicast approach is to disseminate the messages from a single vehicle or node to several vehicular clusters efficiently despite dynamic topology. Therefore, the goal of achieving a high packet delivery ratio within a highly dynamic environment of VANET has become possible by combining multicast advertisement and multicast message dissemination. Moreover, the stability is achieved by developing clusters based upon average speed and direction parameters.In VMR, the receivers elect the CH based on the procedure as discussed in Section3.1.4. In VANET applications, such as in case of an accident or in any emergency scenario, the source disseminates the messages to IVs. The IVs have a CH to disseminate the messages, among other CHs and within CMs. The CMs are connected with their respective CHs along all the shortest paths.


### 4.1. Multicast Advertisement

The CH transmits advertisements within CMs to develop a multicast link record (MLR) among all member vehicles. Therefore, the data packets are routed from source to destination by using MLR. All CM vehicles also save the data in MLR which is delivered by multicast advertisement. In case of new advertisement by the same CH, the old advertisement is replaced by the new one in MLR, which is differentiated by the sequence number. The entry of advertisement is saved along with the time and neighbor from which it has been received. Therefore, all the new advertisements are differentiated by the time and sequence number.The cluster maintains the MLR of all vehicles because the vehicle topology varies continuously. All the neighbors joining and leaving along with the CH election decisions are based upon the MLR. The MLR fields consist of cluster ID, sequence number, average speed, and direction of vehicles. All nodes share the multicast advertisement to develop MLR at each node and select the CH according to the VCF procedure as specified in Section3.1. In addition, the MLR also stores the route information of all cluster member vehicles at each CM. The new cluster head is elected when the old CH left the cluster due to exceeding or decreasing the speed beyond CSL. This information is disseminated through periodic multicast advertisements after every 5 seconds. The CH leaving information is also disseminated by multicast advertisements in which the current status of CH is updated as missing. Then, the new VCHE procedure is initiated based upon VCS. Similarly, the joining and leaving of vehicles can be found from the MLR which is maintained at each vehicle by using multicast advertisements of that CH.When multiple advertisements are received, then the vehicles join that CH whose multicast advertisement has similar CSL; otherwise multicast advertisement is ignored. The IVs are allowed to join any cluster upon satisfying the CSL criteria as discussed in Section3.1. The new VCHE process is not repeated until the current header leaves the cluster itself. Therefore, the extra processing and computation overhead of rotating the CH responsibility, among other CMs, is reduced which results in reducing the overhead and delay. Moreover, the approach of computing distance between vehicles is not adopted which results in reduction of network overhead and delay during message dissemination.In case the multicast advertisement is not received for 5 seconds, then it means the network partition has occurred. Therefore, the CH needs to be elected after network partition. Similarly, if the vehicles do not find any neighbor with similar CSL, then the single vehicle considers itself as a CH. Moreover, the incoming vehicle needs to join that CH upon fulfilling the CSL criteria.


### 4.2. Multicast Packet Delivery

In VMR, the IVs are informed about the risk ahead or for any other required application by multicast packet delivery. For example, in case of accident, the message is transmitted simultaneously to IVs and to opposite lane vehicles. Hence, the IVs can adjust their speed according to the instructions specified in warning message. The first approaching vehicle disseminates the message to the incoming CHs of all lanes. The CHs transmit the message further to their CMs and other incoming CHs. The direction parameter is used to determine the vehicles of opposite lane. When there is no approaching vehicle towards the risk area, then the vehicles of opposite lane are used to deliver the message to IVs as shown in Figure6. The emergency message dissemination is demonstrated below in Section 4.3.Figure 6
Message delivery by opposite lane vehicles.


### 4.3. Emergency Alert Messages (EAMs) Dissemination by Multicast Communication

EAMs are generated in case of an accident or in any other emergency situation on the road. The EAMs are generated by the accident vehicles (AVs) which are disseminated according to the following scheme:(1)
The EAMs are disseminated to the first incoming vehicles (FIVs) by VMR.
(2)
FIVs disseminate EAMs to all the incoming CHs and CMs.
(3)
CHs disseminate the messages to other incoming CHs by intercluster communication.
(4)
The EAMs are also disseminated towards the opposite lane to inform the IVs before their arrival in risk area (RA) as shown in Figure7.Figure 7
Emergency alert messages (EAMs) delivery by multicast communication.Hence, the EAM scheme works efficiently within both urban and highway areas. In urban area, the speed difference between all vehicles is very low which increase the cluster size. Beside this, the vehicles remain mostly withinC
S
L
S or within C
S
L
M which increases the cluster stability. Hence, the RTVC performance enhances upon the parallel increase of cluster size and stability within urban scenario.


## 4.1. Multicast Advertisement

The CH transmits advertisements within CMs to develop a multicast link record (MLR) among all member vehicles. Therefore, the data packets are routed from source to destination by using MLR. All CM vehicles also save the data in MLR which is delivered by multicast advertisement. In case of new advertisement by the same CH, the old advertisement is replaced by the new one in MLR, which is differentiated by the sequence number. The entry of advertisement is saved along with the time and neighbor from which it has been received. Therefore, all the new advertisements are differentiated by the time and sequence number.The cluster maintains the MLR of all vehicles because the vehicle topology varies continuously. All the neighbors joining and leaving along with the CH election decisions are based upon the MLR. The MLR fields consist of cluster ID, sequence number, average speed, and direction of vehicles. All nodes share the multicast advertisement to develop MLR at each node and select the CH according to the VCF procedure as specified in Section3.1. In addition, the MLR also stores the route information of all cluster member vehicles at each CM. The new cluster head is elected when the old CH left the cluster due to exceeding or decreasing the speed beyond CSL. This information is disseminated through periodic multicast advertisements after every 5 seconds. The CH leaving information is also disseminated by multicast advertisements in which the current status of CH is updated as missing. Then, the new VCHE procedure is initiated based upon VCS. Similarly, the joining and leaving of vehicles can be found from the MLR which is maintained at each vehicle by using multicast advertisements of that CH.When multiple advertisements are received, then the vehicles join that CH whose multicast advertisement has similar CSL; otherwise multicast advertisement is ignored. The IVs are allowed to join any cluster upon satisfying the CSL criteria as discussed in Section3.1. The new VCHE process is not repeated until the current header leaves the cluster itself. Therefore, the extra processing and computation overhead of rotating the CH responsibility, among other CMs, is reduced which results in reducing the overhead and delay. Moreover, the approach of computing distance between vehicles is not adopted which results in reduction of network overhead and delay during message dissemination.In case the multicast advertisement is not received for 5 seconds, then it means the network partition has occurred. Therefore, the CH needs to be elected after network partition. Similarly, if the vehicles do not find any neighbor with similar CSL, then the single vehicle considers itself as a CH. Moreover, the incoming vehicle needs to join that CH upon fulfilling the CSL criteria.


## 4.2. Multicast Packet Delivery

In VMR, the IVs are informed about the risk ahead or for any other required application by multicast packet delivery. For example, in case of accident, the message is transmitted simultaneously to IVs and to opposite lane vehicles. Hence, the IVs can adjust their speed according to the instructions specified in warning message. The first approaching vehicle disseminates the message to the incoming CHs of all lanes. The CHs transmit the message further to their CMs and other incoming CHs. The direction parameter is used to determine the vehicles of opposite lane. When there is no approaching vehicle towards the risk area, then the vehicles of opposite lane are used to deliver the message to IVs as shown in Figure6. The emergency message dissemination is demonstrated below in Section 4.3.Figure 6
Message delivery by opposite lane vehicles.


## 4.3. Emergency Alert Messages (EAMs) Dissemination by Multicast Communication

EAMs are generated in case of an accident or in any other emergency situation on the road. The EAMs are generated by the accident vehicles (AVs) which are disseminated according to the following scheme:(1)
The EAMs are disseminated to the first incoming vehicles (FIVs) by VMR.
(2)
FIVs disseminate EAMs to all the incoming CHs and CMs.
(3)
CHs disseminate the messages to other incoming CHs by intercluster communication.
(4)
The EAMs are also disseminated towards the opposite lane to inform the IVs before their arrival in risk area (RA) as shown in Figure7.Figure 7
Emergency alert messages (EAMs) delivery by multicast communication.Hence, the EAM scheme works efficiently within both urban and highway areas. In urban area, the speed difference between all vehicles is very low which increase the cluster size. Beside this, the vehicles remain mostly withinC
S
L
S or within C
S
L
M which increases the cluster stability. Hence, the RTVC performance enhances upon the parallel increase of cluster size and stability within urban scenario.


## 5. RTVC Performance Evaluation

An extensive simulation has been performed to evaluate the performance of RTVC framework by using network simulator ns-2.34 [32] and traffic microsimulator SUMO [33]. The main aim of the proposed RTVC framework is to disseminate the messages efficiently despite highly dynamic nature of VANET by using cluster based multicast routing. The performance of RTVC can be judged by analyzing the following parameters such as a packet delivery ratio, cluster stability, delay, throughput, and number of CHs and CMs switches.The RTVC simulation has been performed on a three-lane highway and two-lane urban scenarios to show that it works efficiently within both scenarios. The simulation has been conducted upon 100 vehicles for 15 minutes as shown in Table1. The arrival of vehicles follows the realistic traffic scenario with dynamic mobility at several points. The traffic congestion is varied to get the results within all types of scenarios such as 5–100 vehicles within single lane and within single cluster at a specific time depending upon the vehicles speed. The performance of VCS is also examined by varying the cluster size (CS) and vehicle speed (V
s
p
d) in parallel. Moreover, the performance is also evaluated upon vehicle joining, leaving, and merging with other clusters. In addition, the cluster stability and network overhead parameters are also analyzed within both urban and highway scenarios.Table 1
RTVC framework simulation parameters.
Parameters
Values
Number of lanes for highway scenario
3
Number of lanes for urban scenario
2
Maximum number of vehicles
100
Vehicular density
5–100 vehicles/km
Transmission range
300–1000 meters
Periodic multicast advertisement
5 seconds
MAC protocol
IEEE 802.11p
PHY-modulation
OFDM
Channel bandwidth
10 MHz
Control channel (CCH)
1
Service Channel (SCH)
6
IEEE 802.1p data rate
3–27 Mbps
Antenna model
Omnidirectional
Frequency
5.850–5.925 GHz
MAC transmission mechanism
CSMA/CA
Maximum vehicle speed
120 km/h
Connection type
TCP
Application type
FTP
Radio propagation model
Two-ray groundThe RTVC performance is compared with multicast ad hoc on demand distance vector (MAODV) and dynamic source routing (DSR) protocols at high mobility. MAODV is a tree based multicast routing protocol developed for mobile ad hoc network (MANET). In this protocol, the group leader maintains the tree by transmitting hello messages at periodic intervals and the acknowledgement is transmitted back to the origin. The reply is lost when the intermediate node moves to another location which causes extra processing overhead [34].Dynamic Source Routing (DSR) protocol is developed for wireless mesh networks which establishes route on demand. It is based upon source routing in which the routing information is continuously updated and maintained at each wireless node. DSR also generates route reply upon successful message delivery. DSR is beaconless and does not require periodic control messages, which save the bandwidth in ad hoc wireless networks [35]. The simulation results of MAODV and DSR are based upon vehicles dynamic mobility and unpredictable movements.Routing Overhead. It is computed by finding the ratio of control packets sent to the total received data packets at the destination. The overhead is computed with respect to mobility, number of CMs, and number of clusters as shown in Figure 8. The RTVC has very low overhead as compared to MAODV and DSR due to cluster based approach and multicast communication. The overhead slightly rises till 40% during 60 km/h because the cluster size increases at average speed. Similarly, it starts to decrease till 120 km/h because the cluster size decreases at high mobility. On the other hand, the MAODV and DSR have experienced high overhead as the mobility increases as shown in Figure 8(a).Figure 8
(a) RTVC overhead with respect to mobility, (b) RTVC overhead with respect to CMs, and (c) RTVC overhead with respect to number of clusters.
(a)
(b)
(c)The overhead of RTVC framework seen to rise slightly as the number of CMs increases as shown in Figure8(b). Additionally, the overhead remains below 5% even during 12 adjacent clusters’ communication as shown in Figure 8(c). The MAODV and DSR are not evaluated with respect to CHs and CMs because these are noncluster based routing protocols.Packet Delivery Ratio (PDR). The packet delivery ratio is calculated to get the number of packets which are delivered actually to the number of packets expected to be received at the destination as shown below: (6)
P
D
R
=
∑
T
o
t
a
l
N
u
m
b
e
r
o
f
S
u
c
c
e
s
s
f
u
l
D
e
l
i
v
e
r
e
d
P
a
c
k
e
t
s
∑
T
o
t
a
l
N
u
m
b
e
r
o
f
T
r
a
n
s
m
i
t
t
e
d
P
a
c
k
e
t
s
f
r
o
m
S
o
u
r
c
e
.It shows the efficiency of protocol in delivering the data packets within a highly mobile environment like VANET. The PDR is calculated with respect to vehicle mobility, number of cluster members, and number of clusters within various lanes as shown in Figure9. The PDR is measured by varying the speed up to 120 km/h. The PDR of RTVC framework is above 89%, even in case of high mobility due to the combination of multicast communication and cluster based approach, whereas the PDR of MAODV and DSR is continuously declining with the increase of vehicle mobility as shown in Figure 9(a). Similarly, the PDR of RTVC framework is not affected by increasing the number of cluster members and number of clusters within various lanes due to stable cluster formation as proposed in VCS and shown in Figures 9(b) and 9(c).Figure 9
Packet delivery ratio of RTVC with respect to mobility, (b) packet delivery ratio of RTVC with respect to CMs, and (c) packet delivery ratio of RTVC with respect to number of clusters.
(a)
(b)
(c)Vehicle Density. The performance of RTVC is not affected by the vehicular density. At high vehicular density, the performance enhances because the cluster size increases due to similar speed of vehicles within congested traffic. Moreover, in case of low density the vehicles are organized in several clusters which are based upon CSL scheme depending upon the vehicle speed. Hence, the overhead is distributed upon the CHs which also enhance the RTVC performance.In addition to this, the PDR remains above 80% within urban areas where the speed limit is less than 70 km/h due to increase in cluster size as shown in Figure10(a), whereas PDR slightly decreases till 80% at highway scenarios where vehicular density is above 80 vehicles/km as shown in Figure 10(b). On the other hand, the PDR of MAODV and DSR reduce continuously due to high vehicular density as shown in Figures 10(a) and 10(b).Figure 10
(a) RTVC vehicle density within urban area with respect to PDR, (b) RTVC vehicle density within highway scenario with respect to PDR, (c) RTVC vehicle density with respect to CH switches, and (d) RTVC vehicle density with respect to CMs switches.
(a)
(b)
(c)
(d)In RTVC, the CH switches are less than 7 vehicles within an urban scenario where cluster size increases due to low mobility as shown in Figure10(c). Similarly, the CMs switches are less than 40 vehicles in urban area where clusters are more stable due to similar and slow speed of vehicles as shown in Figure 10(d). The simulation results of vehicular density illustrate that the RTVC framework has efficient performance within both high and low vehicular density. Hence, its performance is efficient in both urban and highway scenarios.Cluster Stability. The performance of protocol enhances when the cluster stability increases. The cluster stability in RTVC framework is achieved by proposing a VCF scheme which is based upon CSL. The clusters in VANET become unstable only due to speed mismatch between vehicles. Therefore, the RTVC framework handles the cluster formation by CSL in such a way that the maximum stability could be achieved.It is calculated by computing the number of CH switches and by tracking the number of CM vehicles, which left the cluster or merge with other clusters. The number of CHs and CMs switches is computed with respect to mobility to analyze the stability of RTVC. The number of CH switches rise as the mobility increase, which is 14 CH switches at 120 km/h as shown in Figure11(a). The CH switches reduce at slow speed of vehicles which are 6 CH switches at 60 km/h as shown in Figure 11(a).Figure 11
(a) RTVC mobility with respect to cluster head switches and (b) RTVC mobility with respect to cluster members switches.
(a)
(b)It shows that the stability increases in the urban scenario where cluster size increases due to congested traffic. Similarly, the CH switches are seen to rise on highways where vehicular mobility is high. Similarly, there are 44 CMs switches at 120 km/h in RTVC framework which is shown in Figure11(b). Cluster maintenance overhead is caused by the leaving, joining, and merging of vehicles with other clusters. The overhead is seen to be lower in VCS by reducing the CHs and CMs switches as shown below in Figures 11(a) and 11(b).Throughput. Throughput is measured to find the rate of successful delivered messages within a network which is represented as data packets delivered per second as shown in [36](7)
T
h
r
o
u
g
h
p
u
t
=
∑
D
e
l
i
v
e
r
e
d
P
a
c
k
e
t
s
∑
T
o
t
a
l
S
i
m
u
l
a
t
i
o
n
T
i
m
e
∗
P
a
c
k
e
t
S
i
z
e
.The throughput of RTVC framework is calculated as more than 80% due to organization of similar speed and same direction vehicles into stable clusters. Additionally, the multicast communication is used for efficient packet delivery. The throughput decreases slightly by increasing the mobility, number of CMs, or clusters because the CMs switches rise in all these cases. The throughput of MAODV and DSR is affected a lot due to high vehicular mobility as shown in Figure12(a).Figure 12
(a) RTVC throughput with respect to mobility, (b) RTVC throughput with respect to number of CMs, and (c) RTVC throughput with respect to number of clusters.
(a)
(b)
(c)Delay. The delay shows the time difference between the packet transmission and successful delivery at destination as shown below:(8)
D
e
l
a
y
=
∑
R
e
c
e
i
v
e
d
P
a
c
k
e
t
s
“
T
R
"
-
T
r
a
n
s
m
i
t
t
e
d
P
a
c
k
e
t
s
“
T
T
"
∑
S
u
m
o
f
A
l
l
D
e
l
i
v
e
r
e
d
P
a
c
k
e
t
s
.The delay is computed by varying the vehicular mobility and cluster size. It rises slightly at 60 km/h as compared to other speed values because the cluster size increases at an average speed ranges as shown in Figure13(a). The delay incurred in joining cluster is also shown in Figure 13(b) which increases in parallel with the vehicular mobility. The CMs joining delay rises to 2.4 ms at an average speed of 60 km/h due to increase of cluster size. Similarly, the delay in joining a cluster slightly rises to 3.6 ms at the mobility of 120 km/h due to continuous joining and leaving of CMs at high mobility, which does not affect the performance of the proposed framework. The joining delay of CMs is found to be low due to the joining approach adopted in VCM as discussed in Algorithm 2. On the other hand, the delay is seen to rise quickly as the vehicular mobility increases in MAODV and DSR as shown in Figure 13(a). Besides this, the delay rises continuously in the RTVC framework by increasing the number of CMs and number of clusters because the ratio of joining and leaving vehicular clusters increases significantly in these cases as shown in Figures 13(c) and 13(d). The delay rises to 5 ms at 50 CMs/cluster, which does not affect the performance of the RTVC as shown in Figure 13(c). Moreover, the delay has risen to 4.5 ms at 12 adjacent clusters which is not considered as too high as shown in Figure 13(d).Figure 13
(a) RTVC delay with respect to mobility, (b) RTVC CMs joining delay with respect to mobility, (c) RTVC delay with respect to number of CMs, and (d) RTVC delay with respect to number of clusters.
(a)
(b)
(c)
(d)The simulation has been performed several times to analyze the occurrence of possible variation in results as shown in Table2. The variations are shown in limits with minimum and maximum values in the form of percentage. The results show that the variation is very small because the topology has been already varied dynamically during simulation by considering all possible scenarios such as change in speed, road lanes, cluster size, and vehicular density.Table 2
RTVC framework simulation results variations.
Metrics
Overhead variation(Min–Max)%
PDR variation (Min–Max)%
Cluster stabilityvariation (Min–Max)%
Delay variation(Min–Max)%
High mobility
0.1–6
0.1–3
0.1–3
0.1–5
Number of CMs
0.1–7
0.1–4
0.1–4
0.1–6
Number of clusters
0.1–6
0.1–4
0.1–3
0.1–4


## 6. Conclusion

In VANET, the topology is highly dynamic in nature due to the unpredictable mobility of vehicles. Therefore, there is a need to develop such a framework which is capable of handling the high mobility of vehicles within any kind of scenario whether that is urban or highway. Thus, a novel RTVC framework is proposed which consists of VCS and VMR components. The stability is achieved by configuring the vehicles hierarchically to form clusters based upon the CSL, similar direction, and CTV. The RTVC framework effectively handles and adapts itself according to the dynamic VANET environment by VCS. The proposed VCF scheme delivers high efficiency and cluster stability with low overhead. The clusters need continuous maintenance due to CMs joining, leaving, and merging with other clusters which is handled by VCM scheme. The cluster stability needs to be adjusted according to the dynamic VANET scenario which has been achieved by the SAF approach as proposed in CTV. The efficient and real time message dissemination has been achieved by combining the multicast routing with the cluster based approach. After extensive simulations, it has been analyzed that the RTVC framework has incurred low delay and overhead but with high stability and throughput.



---

*Source: 8064908-2016-04-19.xml*