IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 65, NO.

4, APRIL 2016 2621

Multihop-Cluster-Based IEEE 802.11p and LTE

Hybrid Architecture for VANET Safety
Message Dissemination
Seyhan Ucar, Student Member, IEEE, Sinem Coleri Ergen, Member, IEEE, and Oznur Ozkasap, Member, IEEE

Abstract—Several vehicular ad hoc network (VANET) studies 802.11p and LTE interface to link the VANET to the LTE network.
have focused on communication methods based on IEEE 802.11p, Using various key metrics of interest, including DPDR, delay,
which forms the standard for wireless access for vehicular environ- control overhead, and clustering stability, we demonstrate the
ments. In networks employing IEEE 802.11p only, the broadcast superior performance of the proposed architecture compared with
storm and disconnected network problems at high and low vehicle both previously proposed hybrid architectures and alternative
densities, respectively, degrade the delay and delivery ratio of routing mechanisms, including flooding and cluster-based routing
safety message dissemination. Recently, as an alternative to the via extensive simulations in ns-3 with the vehicle mobility input
IEEE 802.11p-based VANET, the usage of cellular technologies from the Simulation of Urban Mobility. The proposed architecture
has been investigated due to their low latency and wide-range also allows achieving higher required reliability of the application
communication. However, a pure cellular-based VANET commu- quantified by the DPDR at the cost of higher LTE usage measured
nication is not feasible due to the high cost of communication by the number of CHs in the network.
between the vehicles and the base stations and the high number
of handoff occurrences at the base station, considering the high Index Terms—Clustering, IEEE 802.11p, Long-Term Evolution
mobility of the vehicles. This paper proposes a hybrid architecture, (LTE), message dissemination, safety application, vehicular ad hoc
namely, VMaSC–LTE, combining IEEE 802.11p-based multihop networks (VANETs).
clustering and the fourth-generation (4G) cellular system, i.e., I. I NTRODUCTION
Long-Term Evolution (LTE), with the goal of achieving a high
data packet delivery ratio (DPDR) and low delay while keep-
ing the usage of the cellular architecture at a minimum level.
In VMaSC–LTE, vehicles are clustered based on a novel ap-
T HE VEHICULAR ad hoc netwok (VANET) is expected to
significantly improve the safety of transportation systems
by providing timely and efficient data dissemination about
proach named Vehicular Multihop algorithm for Stable Clustering
(VMaSC). The features of VMaSC are cluster head (CH) selection events such as accidents, road conditions, and traffic jams be-
using the relative mobility metric calculated as the average relative yond the driver’s knowledge [3]. Driver behavior, constraints on
speed with respect to the neighboring vehicles, cluster connection mobility, and high speeds create unique characteristics, such as
with minimum overhead by introducing a direct connection to the rapid but somewhat predictable topology changes, uneven net-
neighbor that is already a head or a member of a cluster instead of
connecting to the CH in multiple hops, disseminating cluster mem- work density, and frequent fragmentation for VANETs. Meet-
ber information within periodic hello packets, reactive clustering ing the strict delay and packet delivery requirements of safety
to maintain the cluster structure without excessive consumption applications in such a dynamic network determines the feasi-
of network resources, and efficient size- and hop-limited cluster bility of the deployment of such applications. Table I shows the
merging mechanism based on the exchange of cluster information specifications of various VANET safety applications extracted
among CHs. These features decrease the number of CHs while
increasing their stability, therefore minimizing the usage of the from [4] and [5]: The update rate refers to the packet generation
cellular architecture. From the clustered topology, elected CHs rate of the nodes; the maximum dissemination distance is
operate as dual-interface nodes with the functionality of the IEEE defined as the distance within which the safety message needs
to be disseminated; maximum delay is the maximum tolerable
delay for safety message dissemination. The packet delivery
Manuscript received May 26, 2014; revised February 24, 2015; accepted
March 29, 2015. Date of publication April 8, 2015; date of current version ratio of the safety application, which is defined as the ratio of
April 14, 2016. This work was conducted through the Turk Telekom Research the nodes that successfully receive packets within the maximum
project under Grant 11315-07. S. Coleri Ergen was also supported by Bilim dissemination distance, on the other hand, mostly ranges from
Akademisi—The Science Academy, Turkey, through the BAGEP program. A
preliminary version of the clustering algorithm used in this work appeared in 90% to 100%, depending on the application type and network
the IEEE Wireless Communications and Networking Conference, Shanghai, scenario, although it is not explicitly provided in the safety
China, April 7–10, 2013. An efficient data aggregation algorithm exploiting application specifications.
the clustering algorithm in this work appeared at the International Conference
on Connected Vehicles and Expo, Vienna, Austria, November 3–7, 2014. The Up to now, several VANET studies have focused on com-
review of this paper was coordinated by Prof. W. Song. munication methods based on IEEE 802.11p, which forms
S. Ucar and O. Ozkasap are with the Department of Computer Engineering, the standard for Wireless Access for Vehicular Environments.
Koç University, Istanbul 34450, Turkey (e-mail: [email protected]; oozkasap@
ku.edu.tr). IEEE 802.11p provides data rates ranging from 6 to 27 Mb/s
S. Coleri Ergen is with the Department of Electrical and Electronics Engi- at a short radio transmission distance, i.e., around 300 m.
neering, Koç University, Istanbul 34450, Turkey (e-mail: [email protected]). Disseminating safety information over a large area requires an
Color versions of one or more of the figures in this paper are available online
at http://ieeexplore.ieee.org. intelligent multihop broadcast mechanism handling two major
Digital Object Identifier 10.1109/TVT.2015.2421277 problems: broadcast storm [6] and disconnected network [7].
0018-9545 © 2015 IEEE. Translations and content mining are permitted for academic research only. Personal use is also permitted, but republication/redistribution
requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
2622 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 65, NO. 4, APRIL 2016

TABLE I
VANET S AFETY A PPLICATION R EQUIREMENTS

TABLE II
R ELATED W ORK ON H YBRID A RCHITECTURES IN VANET S

The broadcast storm problem occurs at high vehicle traffic to 100 km in the radio access network (RAN). Despite the high
density, where the packet delay and the number of collisions rate coupled with wide-range communication, however, a pure
at the medium-access-control layer dramatically increase as LTE-based architecture is not feasible for vehicular commu-
the number of vehicles attempting to transmit simultaneously nication due to the high cost of LTE communication between
increases. Probabilistic flooding [6] and clustering [8]–[20] are the vehicles and the base stations, a high number of handoff
commonly used to address the broadcast storm problem. On occurrences at the base station considering the high mobility
the other hand, the disconnected network problem occurs at of vehicles, and overload of the base station by the broadcast
low vehicle traffic density, where the number of nodes is not of a high number of vehicles at high vehicle traffic density
sufficient to disseminate the information to all the vehicles in a [24]–[26].
certain region. Store–carry–forward, where the vehicles in the Hybrid architectures have been recently proposed to ex-
opposite lane are used for message dissemination, is commonly ploit both the low cost of IEEE 802.11p and the wide-range
utilized to address the disconnected network problem [7], [21]. low-latency communication of the cellular technologies, as
The solutions addressing both broadcast storm and discon- summarized in Table II. Some of these works [27], [30],
nected network problems, however, have been shown to provide [35] focus on the usage of the hybrid architecture for more
network delays varying from a few seconds to several minutes efficient clustering: Lequerica et al. in [27] demonstrate the
and the percentage of the vehicles successfully receiving the usage of the cellular communication signaling in the hybrid
packets going down to 60% [22]. architecture, Remy et al. in [30] exploit the usage of the
Recently, as an alternative to the IEEE 802.11p-based centralized architecture of the cellular communication to reduce
VANET, the usage of cellular technologies has been investi- the clustering overhead, and Benslimane et al. in [35] propose
gated. The key enabler of such usage is the standardization a new protocol based on the selection of a route with the
of the advanced content broadcast/multicast services by the longest lifetime to connect to the wired network for services
Third-Generation Partnership Project (3GPP), which provides such as driver information systems and Internet access. On
efficient message dissemination to many users over a geograph- the other hand, the authors in [32]–[34] propose cluster-based
ical area at fine granularity. The use of the third-generation hybrid architecture for message dissemination. In this hybrid
mobile cellular system, which is called the Universal Mobile architecture, the cluster members (CMs) communicate with the
Communication System (UMTS), in the safety application of cluster head (CH) by using IEEE 802.11p, and the CHs com-
vehicles has already been experimented in Project Cooperative municate with the base station by using cellular technologies.
Cars (CoCars) [23]. The traffic hazardous warning message The goal is to minimize the number of CHs communicating
has been shown to be disseminated in less than 1 s. The with the cellular network. Decreasing the number of clusters
fourth-generation cellular system, which is called Long-Term reduces the cost of using cellular infrastructure by lowering
Evolution (LTE), is an evolution of UMTS increasing capacity both the amount of communication with the base stations
and speed using a different radio interface together with core and the frequency of handoff occurrences at the base station.
network improvements. The LTE specification provides down- Efficient clustering, however, should not only minimize the
link peak rates of 300 Mb/s, uplink peak rates of 75 Mb/s, number of CHs but maintain the stability of the cluster-based
transfer latency of less than 5 ms, and transmission range up topology with minimum overhead as well. None of the proposed
UCAR et al.: MULTIHOP-CLUSTER-BASED IEEE 802.11P AND LTE HYBRID ARCHITECTURE FOR VANET SAFETY MESSAGE DISSEMINATION 2623

hybrid architectures, nevertheless, perform any stability analy- in message dissemination in terms of metrics such as packet
sis. Moreover, Taleb and Benslimane in [32] do not consider delivery ratio and delay (see Table III).
the delay performance of the message dissemination in the In this paper, we propose a hybrid architecture, namely,
network. Although Benslimane et al. in [33] and Sivaraj et al. in VMaSC–LTE, combining IEEE 802.11p-based multihop clus-
[34] provide the delay performance of the hybrid architecture, tering and LTE, with the goal of achieving high data packet
they do not include the effect of multihop clustering on the delivery ratio (DPDR) and low delay while keeping the usage
number of CHs and clustering stability. Furthermore, none of of the cellular infrastructure at a minimum level via minimizing
the previous hybrid architectures compare their performance the number of CHs and maximizing clustering stability. The
to that of IEEE 802.11p-based alternative routing mechanisms, original contributions of this paper are listed as follows.
such as flooding and cluster-based routing.
In the literature, VANET clustering has been performed with • We propose a multihop-cluster-based IEEE 802.11p–LTE
different purposes, such as load balancing, quality-of-service hybrid architecture for the first time in the literature.
support, and information dissemination in high-density vehic- The features of the multihop clustering algorithm used in
ular networks [38]. Stable clustering with a minimum num- this hybrid architecture, which is called VMaSC, are CH
ber of CHs and minimum overhead requires efficient cluster selection using the relative mobility metric calculated as
joining, maintenance, and merging mechanisms together with the average relative speed with respect to the neighbor-
an efficient clustering metric, considering the high mobility ing vehicles, cluster connection with minimum overhead
of vehicles. Clustering metrics used in the VANET literature by introducing a direct connection to the neighbor that
include direction [8], [11]–[13], packet delay variation [10], lo- is already a head or a member of a cluster instead of
cation difference [9], [14], [16], [20], speed difference [18], and connecting to the CH in multiple hops, disseminating
combination of location and speed differences [15], [17], [19]. CM information within periodic hello packets, reactive
Although a metric combining the location and speed of the clustering to maintain the cluster structure without exces-
neighboring vehicles is a better measure of their link dura- sive consumption of network resources, and efficient size-
tion compared with a metric considering their speed only, and hop-limited cluster merging mechanism based on the
all vehicles may not have localization capability. Calculating exchange of cluster information among CHs. Combining
packet delay variation, on the other hand, requires very accu- all of these features in a multihop-cluster-based hybrid
rate synchronization among the vehicles with low-level time architecture, using minimum overhead cluster connection,
stamping of the packets due to the random access protocol used and size- and hop-limited cluster merging mechanism are
by IEEE 802.11p. Moreover, cluster joining in both one-hop unique characteristics of VMaSC.
and multihop VANETs is direct to the CH. However, joining • We perform an extensive analysis of the performance
the cluster through a CM and informing the CH later via of the multihop-cluster-based IEEE 802.11p–LTE hybrid
periodic hello packets can decrease clustering connection time architecture over a wide range of performance metrics,
and overhead significantly. Such efficient mechanisms have including DPDR, delay, control overhead, and cluster-
been proposed in mobile ad hoc networks, which, however, ing stability, in comparison to both previously proposed
usually assume stationarity of the nodes during clustering [39]. hybrid architectures and alternative routing mechanisms,
In addition, cluster maintenance is achieved through either peri- including flooding and cluster-based routing over a large-
odic reclustering [8]–[10], [12], [16], [17], where the clustering scale highway, using a realistic vehicle mobility model for
procedure is periodically executed, or reactive clustering [14], the first time in the literature.
[15], [18], where clustering is triggered only when the CH has • We illustrate the tradeoff between the reliability of the
lost connection to all its members or the CM cannot reach its application measured by the DPDR and the cost of
cluster. Reactive clustering is more efficient since the reclus- the LTE usage determined by the number of CHs in the
tering procedure is activated only when the cluster structure is network for the first time in the literature.
destroyed without excessive periodic packet transmission over- The rest of this paper is organized as follows. Section II
head. Furthermore, the previously proposed cluster merging describes the system model. Section III presents the proposed
mechanisms are activated either when the distance between two multihop clustering scheme. Section IV delineates the data-
neighboring CHs is less than a certain threshold [12], [15], forwarding approach in the IEEE 802.11p–LTE hybrid archi-
[18] or when the CHs remain connected for a time duration tecture. The comparison of the proposed hybrid architecture
greater than a predetermined value [19], [20]. However, cluster to the previously proposed hybrid architectures and alternative
merging can result in very-large-size merged clusters, where the routing mechanisms is given in Section V. Finally, concluding
CH becomes a bottleneck due to the high number of packets remarks and future work are given in Section VI.
of its CMs and a large number of hops, which increases the
delay of packet transmissions. To solve the cluster-head bot-
II. S YSTEM M ODEL
tleneck and large-delay problems, cluster merging should limit
both the size and the number of hops in the resulting merged The envisioned IEEE 802.11p–LTE hybrid architecture is
cluster. Moreover, the previously proposed multihop clustering shown in Fig. 1. The vehicles form a multihop clustered topol-
algorithms only focus on providing clustering stability through ogy in each direction of the road. The vehicles within the
metrics such as CH duration, CM duration, and CH change but transmission range of a CH, which is denoted by R and shown
do not analyze the performance of their proposed algorithm by a dotted line around the CH in the figure, become a CM
2624 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 65, NO. 4, APRIL 2016

TABLE III
R ELATED W ORK ON VANET C LUSTERING

Fig. 1. IEEE 802.11p–LTE hybrid architecture.

and directly communicate with their corresponding CH. The The LTE infrastructure is responsible for disseminating the
vehicles that are multihops away from the CH become multihop generated data within a VANET inside a geographical region.
CMs and transfer data packets to the CM to which they are The LTE part of the system consists of a RAN, where each
connected to reach their corresponding CH. cell is managed by an eNodeB and the evolved packet core
The vehicle information base (V IB) of a vehicle consists (EPC), which consists of a server gateway (SGW) and packet
of a repository storing the information of the vehicle and its data network gateways (PGWs) [40]. eNodeB is a complex
neighboring vehicles within a predetermined maximum number base station that handles radio communications with multiple
of hops, which is denoted by M AX_HOP . V IB is used devices in the cell and carries out radio resource management
in determining the members and heads of the clusters in the and handover decisions. SGW provides the functionality of
network. routing and forwarding data packets to neighboring eNodeBs,
The vehicles possess two communication interfaces: IEEE whereas PGW is responsible for setting the transfer paths of
802.11p and LTE. CMs can only communicate with the mem- vehicle data packets, quality-of-service control, and authenti-
bers of the cluster they belong to via IEEE 802.11p, whereas cation. eNodeBs are connected to EPC over a wired network.
CH communicates with both CMs via IEEE 802.11p and EPC has global information of the location of eNodeBs. When
eNodeB via LTE. a CH sends the data packet to the eNodeB it is connected to
UCAR et al.: MULTIHOP-CLUSTER-BASED IEEE 802.11P AND LTE HYBRID ARCHITECTURE FOR VANET SAFETY MESSAGE DISSEMINATION 2625

over a radio network, the packet is sent to the EPC over the TABLE IV
N OTATION
wired network. The EPC then determines all the eNodeBs that
cover an area within the safety dissemination region of the data
packet and sends the packet to them. When an eNodeB receives
a data packet for dissemination, the packet is multicast to all the
CHs that are within the coverage of eNodeB.
The objective of the proposed hybrid architecture is to effi-
ciently forward data packets over a certain geographical region
with small delay and high percentage of vehicles successfully
receiving packets while minimizing the number of CHs and
maximizing the clustering stability to minimize the overhead
on the vehicles and eNodeB.

III. V EHICULAR M ULTIHOP A LGORITHM FOR S TABLE

C LUSTERING (VMaSC)
The features of the proposed multihop clustering algorithm
VMaSC are as follows.
1) It provides stable CH selection by the use of the relative
mobility metric calculated as the average relative speed
with respect to the neighboring vehicles in a multihop
clustered vehicular network.
2) It provides cluster connection with minimum overhead
by introducing a direct connection to the neighbor that
is already a head or a member of a cluster, instead of
connecting to the CH in multiple hops, and disseminating
CM information within periodic hello packets.
3) It provides reactive clustering to maintain the cluster
structure without excessive packet transmission overhead.
4) It provides minimum intercluster interference by mini-
mizing the overlap of clusters in space through prioritiz-
ing the connections to existing clusters and introducing
efficient size- and hop-aware cluster-merging mecha-
nisms based on the exchange of cluster information
among the CHs.
A preliminary version of VMaSC and its integration with
data aggregation appeared previously in [1] and [2], respec-
tively. connect to any existing cluster and when there is no
Fig. 1 shows a sample multihop clustered network topology. potential neighboring vehicle that can connect to it.
Next, we describe the states of the vehicles, V IB generation • CLUSTER MEMBER (CM ) is the state of the vehicle in
and update, cluster state transitions, cluster formation, cluster which the vehicle is attached to an existing cluster.
merging, and intercluster interference. The notation used is
presented in Table IV. B. V IB Generation and Update
V IB at each node includes the information of the vehicle
A. States of Vehicles itself and its neighboring vehicles within M AX_HOP hops.
Each vehicle operates under one of the following five states The vehicle information includes its direction, its velocity, its
at any given time. current clustering state, the number of hops to the CH if it is a
CM, the ID of the vehicle through which the node is connected
• INITIAL (IN ) is the starting state of the vehicle. to the cluster, the ID of the vehicles that use the node to connect
• STATE ELECTION (SE) is the state of the vehicle in to the CH, its clustering metric, and the source ID and sequence
which the vehicle makes a decision about the next state number of the data packets that are recently generated.
based on the information in V IB. V IB is updated upon any change in the vehicle’s own
• CLUSTER HEAD (CH) is the state of the vehicle in information or reception of a periodic HELLO_P ACKET
which the vehicle is declared to be a cluster head. from any of the neighbors within M AX_HOP hops.
• ISOLATED CLUSTER HEAD (ISO − CH) is the state HELLO_P ACKET includes the vehicle information for
to which the vehicle makes a transition when it cannot its direction, its velocity, its current clustering state, the
2626 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 65, NO. 4, APRIL 2016

CMs since the condition to switch from CH to SE is the lack

of a CM connected to CH. If the number of the members of
CH denoted by M EM BER_CH is zero for the duration
CH_T IM ER, the CH changes its state to SE to decrease
the number of clusters in the network by connecting to another
cluster. The vehicle in state ISO − CH transitions to state CH
if a CM is connected after ISO_CH_T IM ER and to state SE
when the node is no longer isolated, meeting the SE_BACK
condition. SE_BACK refers to the condition of discovering a
node in either the CM or the CH state that does not exist in the
V IB. If none of the transitions can be made in state SE, then
the vehicle stays in SE for a duration denoted by SE_T IM ER
and reruns Algorithm 1.
A vehicle changes state from CH to CM if it receives a
M ERGE_RESP from another CH, demonstrating the suc-
Fig. 2. VMaSC state transition diagram.
cess of cluster merging, as explained in detail in Section III-E.
The vehicle transitions from state CM to SE if it has lost
number of hops to the CH if it is a CM, and the ID of the connection to the neighboring node through which it is con-
vehicle through which the node is connected to the cluster. nected to the cluster named P AREN T . If the CM vehicle
HELLO_P ACKET is retransmitted to the neighbors within does not receive any packet from its P AREN T for duration
M AX_HOP hops. The entries of V IB are deleted if not up- CM _T IM ER, it assumes to have lost the connection.
dated for a certain time, which is denoted by V IB_T IM ER.
The clustering metric denoted by AV GREL_SP EEDi for
vehicle i is calculated as
N (i) D. Cluster Formation
j=1 |Si − Sij |
AV GREL_SP EEDi = (1) As shown in detail in Algorithm 1, a vehicle in the SE state
N (i) first tries to connect to the existing clusters to minimize the
where N (i) is the number of same-direction neighbors within number of CHs. The vehicle gives priority to the neighboring
M AX_HOP hops for vehicle i, ij is the ID of the jth neigh- CHs over the neighboring CMs for connection to decrease the
boring node of vehicle i, and Si is the speed of vehicle i. The delay of the data packets transmitted to the CH over a smaller
lower the average relative speed, the less mobile is the vehicle number of hops.
compared with its neighbors. Therefore, the vehicle with the The vehicle first scans the neighboring CHs in the order of
lowest average relative speed is elected as the CH. increasing average relative mobility. If the number of members
of the CH is less than the maximum number of members al-
lowed and the vehicle has not tried connecting to that CH before
C. Cluster State Transitions
with T RY _CON N ECT set to false, it sends a JOIN _REQ
Fig. 2 shows the possible state transitions of a vehicle. packet (lines 1–4). If it receives JOIN _RESP from the
The vehicle starts in state IN and stays in this state for a corresponding CH within a given amount of time denoted by
duration denoted by IN _T IM ER. The periodic exchange of JOIN _T IM ER, the vehicle transitions to state CM and
HELLO_P ACKET in this state helps the vehicle build its exits the SE algorithm (lines 5–7). Otherwise, the vehicle sets
own V IB. The vehicle then transitions to state SE, in which the T RY _CON N ECTCH flag to true in order not to try
it makes the decision about its next state, as described in connecting to that CH again (line 9). T RY _CON N ECT flags
Algorithm 1 in Section III-D. of vehicles are initially set to false.
A vehicle transitions from state SE to state CM if it re- If none of the neighboring vehicles are a CH or the vehicle
ceives a JOIN _RESP from a CH or a CM. Receiving a cannot connect to any of the neighboring CHs, then the vehicle
JOIN _RESP shows the success of the join request. A vehicle tries to connect to a CH in multiple hops through a CM
transitions from state SE to CH if CH_CON DIT ION is (lines 10–19). The order in which the CMs are scanned is
satisfied. CH_CON DIT ION refers to the condition where determined based on the average relative mobility. Similar to
the vehicle cannot connect to any neighboring CH or CM, there the connection to CH, if the number of members of the CM
is at least one neighboring vehicle in state SE, and the vehicle is less than the maximum number of members allowed and
has minimum average relative speed among all the neighboring the vehicle has not tried connecting to that CM before with
vehicles in state SE. The vehicle in state SE transitions to T RY _CON N ECT set to false (lines 10–12), and the vehicle
state ISO − CH if the ISO_CH_F ORW ARD condition is is within M AX_HOP hops away from the corresponding CH
met. ISO_CH_F ORW ARD refers to the condition where (line 13), the vehicle sends the JOIN _REQ packet to this
the vehicle cannot connect to any neighboring CH or CM and CM (line 14). Depending on the reception of JOIN _RESP ,
there is no neighboring vehicle in state SE. The vehicle in state the vehicle then either transfers to state CM or sets the
ISO − CH similarly behaves as that in state CH. A separate T RY _CON N ECT flag of the CM to true (lines 15–19). If
ISO − CH state is included to differentiate the CHs with no the vehicle receives multiple JOIN _RESP s, then it prefers
UCAR et al.: MULTIHOP-CLUSTER-BASED IEEE 802.11P AND LTE HYBRID ARCHITECTURE FOR VANET SAFETY MESSAGE DISSEMINATION 2627

and number of clusters in the network: As M ERGE_T IM ER

increases, the cluster stability increases at the cost of increase
in the number of clusters. If the CHs stay neighbors for
M ERGE_T IM ER, they share their CLU ST ER_IN F O
and their average relative speed with each other. Both CHs
then check the feasibility of the merged cluster formed when
the CH with higher average relative speed gives up its CH role
and connects to the CH with lower average relative speed. A
feasible merged cluster requires that both clusters have the same
cluster direction; the number of members of the CH and CMs
in the merged cluster be less than M AXM EM BER_CH
and M AXM EM BER_CM , respectively; and the number
of hops in the merged cluster be less than M AX_HOP .
Limiting the maximum number of vehicles and the number
of hops in the merged cluster eliminates CH bottleneck and
longer hierarchical routes, respectively. If the merged cluster
is determined to be feasible, then the CH with higher average
relative speed sends M ERGE_REQ to the less mobile CH. If
this CH receives M ERGE_RESP , it gives up its CH role and
informs its CMs about the merge operation. Otherwise, the CHs
continue to function as CHs. If the vehicle receives multiple
M ERGE_RESP s, then it prefers the CH with the smallest
average relative mobility.

F. Intercluster Interference
Intercluster interference occurs when the clusters overlap in
space. Intercluster interference leads to higher medium con-
tention and inefficient flooding. VMaSC minimizes overlapping
clusters via two methods. 1) The vehicles in the SE state try to
join an existing cluster first before declaring themselves as CH
or ISO − CH. 2) The CHs that are within the transmission
range of each other merge their clusters if the resulting merged
cluster is considered feasible. Moreover, the data packets of the
CMs are unicast to their P AREN T to decrease the medium
CH over CM and the vehicle with the smallest average relative contention and increase the efficiency of the flooding. Further-
mobility among multiple CHs and CMs. more, the packets of each cluster are only broadcast within
If the vehicle cannot connect to any CH or CM, the vehicle that cluster identified with a unique ID, avoiding unnecessary
checks the neighboring vehicles in the SE state. If there is no flooding among multiple clusters.
such vehicle, it transitions to state ISO − CH (lines 20–22). If
there are vehicles in the SE state in its V IB and the vehicle has
G. Theoretical Analysis of VMaSC Clustering
the smallest average relative speed, it makes a transition to the
CH state and broadcasts the CH_ADV packet (lines 23–26). Here, we provide the theoretical analysis of the relative speed
Otherwise, the vehicle stays in state SE for SE_T IM ER metric used in VMaSC clustering.
duration and reruns Algorithm 1. Let us assume that two neighboring vehicles 1 and 2 have
average speed values v1 and v2 and average acceleration values
a1 and a2 , respectively. Assume that these vehicles move on a
E. Cluster Merging
1-D road, and they communicate with each other only if they
Since the vehicles do not send the JOIN _REQ messages are within the transmission range of each other called rt . Let
to the CH in multiple hops, the CH learns about the vehicles the location of vehicles 1 and 2 on the road in the moving
within its cluster via HELLO_P ACKET . The CH keeps the direction be l1 and l2 with difference denoted by r12 equal
information about its cluster, including the ID and P AREN T to l1 − l2 . r12 is a random variable that takes values within
node of its CMs and its cluster direction within a data structure the [−rt , rt ] interval. The intervehicle distance has been shown
named CLU ST ER_IN F O. to have an exponential distribution at low vehicle density and
When two CHs become neighbors, they first check whether a lognormal distribution at high vehicle density [7]. In this
they stay neighbors for a certain time period denoted by case, it should also be conditioned on the fact that its value
M ERGE_T IM ER. The value of M ERGE_T IM ER is in the [−rt , rt ] range. We represent the distribution of r12
should be chosen to balance the tradeoff between cluster stability by P (r12 ) without making any assumption on its distribution,
2628 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 65, NO. 4, APRIL 2016

except that it is limited to the [−rt , rt ] range and symmetric By using the symmetry of the distribution f (δ12 ) around 0, this
around 0. Since the vehicles exchange their speed information probability can be simplified as
with each other, we assume that v1 and v2 are predetermined. ⎛
∞ rt −|(v1 −v2)T +δ12 T /2|
2
The average acceleration values of the vehicles a1 and a2 ,
⎜
however, are assumed to be random variables. Most theoret- ⎝ P (τ )dτ
ical analyses related to clustering in the literature assume no 0 −rt
vehicle acceleration, i.e., a1 = a2 = 0 [41]–[43]. The Freeway ⎞
rt −|(v1 −v2 )T −δ12 T 2 /2|
mobility model, on the other hand, assumes that a1 and a2 
⎟
are independent random variables with uniform distribution in + P (τ )dτ ⎠ f (δ12 )dδ12 . (5)
the interval [−a, a], where a is determined by the maximum −rt
acceleration and deceleration of the vehicles, while also enforc-
ing the minimum and maximum speed values for the vehicles By using the fact that both |(v1 − v2 )T + δ12 T 2 /2| and
and the minimum safety distance between any two vehicles, |(v1 − v2 )T − δ12 T 2 /2| are lower bounded by ||(v1 − v2 )T | −
generating a possibly nonzero correlation on the values of the |δ12 T 2 /2|| and upper bounded by |(v1 − v2 )T | + |δ12 T 2 /2|,
accelerations a1 and a2 , whereas the Reference Point Group the probability that the two vehicles are in the communication
Mobility Model determines the speed of each vehicle by ran- range of each other is lower bounded by
domly deviating from the speed of a vehicle in their group as rt −|(v1 −v
∞ 2 )T |−δ12 T /2
2

a function of a predetermined speed and angle deviation ratio

[44], [45]. To encompass all these different mobility models 2 P (τ )f (δ12 )dτ dδ12 (6)
while preserving the tractability of the analysis, we assume that 0 −rt
the distribution of the difference between a1 and a2 , δ12 , which
and upper bounded by
is denoted by f (δ12 ), is symmetric around 0 and a decreasing
function of δ12 for δ12 > 0. rt −||(v1 −v2 )T |−δ12 T 2 /2|
∞ 
Let us first condition on the values of a1 and a2 . At any
time T , if r12 + (v1 − v2 )T + (a1 − a2 )T 2 /2 is less than rt in 2 P (τ )f (δ12 )dτ dδ12 . (7)
magnitude, the two vehicles can communicate with each other. 0 −rt

To have a more stable link among the CMs, at any given time
To maximize both the lower bound and the upper bound of this
T , we need to maximize the probability that the vehicles can
probability, we need to again minimize the relative speed of the
communicate with each other, which is given by
vehicles |v1 − v2 |.
 
P −rt < r12 + (v1 − v2 )T + (a1 − a2 )T 2 /2 < rt
rt IV. DATA D ISSEMINATION IN H YBRID A RCHITECTURE

= P −rt − r12 < (v1 − v2 )T + (a1 − a2 )T 2 /2
The goal of the proposed multihop-cluster-based IEEE
−rt 802.11p–LTE hybrid architecture is to disseminate the data gen-
< rt − r12 |r12 = τ ) P (τ )dτ (2) erated in the network to all the vehicles within a geographical
area with small delay and high DPDR. LTE is used in this
where P (−rt − r12 < (v1 − v2 )T + (a1 − a2 )T 2 /2 < rt −
architecture to provide the connectivity of the nodes even when
r12 |r12 = τ ) takes a value of 1 or 0, depending on the values
the IEEE 802.11p-based network is disconnected within the
of τ, v1 − v2 , a1 − a2 , rt , and T parameters. By using the
dissemination distance and improve the delay and reliability
symmetry of the distribution P (r12 ) around 0, this probability
performance of the transmissions when the IEEE 802.11p-
can be simplified as
based network has high node density, leading to high medium-
rt −|(v1 −v2 )T +(a1 −a2 )T 2 /2| access contention.

Data forwarding at a vehicle depends on its clustering
P (τ )dτ. (3)
state. If its clustering state is SE, the vehicle broadcasts
−rt
DAT A_P ACKET so that it reaches a member of a cluster
If a1 = a2 , then to maximize this connection probability, we in the network. If the clustering state of the vehicle generating
need to minimize the relative speed of the vehicles given by or receiving a DAT A_P ACKET is CM (CH), the vehicle
|v1 − v2 |. On the other hand, if a1 = a2 , the probability that runs Algorithm 2 (Algorithm 3). The data flow is as follows.
the two vehicles are in the communication range of each other
1) unicast from CM to its CH (if the vehicle is a CM);
is given by
2) broadcast from CH to all its members and to the eNodeB;
∞ 3) unicast from eNodeB to EPC;
 
P −rt < r12 +(v1 − v2 )T +δ12 T 2 /2 < rt f (δ12 )dδ12 4) multicast from EPC to the neighboring eNodeBs covering
−∞ a part of the geographical area targeted for the dissemina-
rt −|(v1 −v2 )T +δ12 T 2 /2| tion of the DAT A_P ACKET ;
∞  5) multicast from eNodeBs to the CHs within their
= P (τ )f (δ12 )dτ dδ12 . (4) coverage;
−∞ −rt 6) broadcast from the CHs to all its members.
UCAR et al.: MULTIHOP-CLUSTER-BASED IEEE 802.11P AND LTE HYBRID ARCHITECTURE FOR VANET SAFETY MESSAGE DISSEMINATION 2629

As provided in Algorithm 2, if the CM generates or receives V. P ERFORMANCE E VALUATION

a DAT A_P ACKET , then it checks its V IB to determine The goal of the simulations is to compare the performance
whether the packet has already been received (lines 2–3). If of the proposed multihop-cluster-based IEEE 802.11p–LTE
the CM receives the packet for the first time, then it checks hybrid architecture to the previously proposed VANET multi-
the source of the packet. If it is coming from its parent vehicle hop clustering algorithms NHop [10] and MDMAC [17], the
(P AREN Tcurr ) in the cluster, then it multicasts the packet hybrid architectures built with the usage of these clustering
to all its children CHILDRENcurr (lines 4–5). Otherwise, algorithms NHop and MDMAC, and flooding-based message
the packet is from either one of its children or another vehicle dissemination.
that is in the SE state. The vehicle then unicasts the packet The simulations are performed in the Network Simulator ns3
to its parent vehicle for the dissemination of the packet to the (Release 3.17) [46] with the realistic mobility of the vehicles
corresponding CH (lines 6–7) and updates its V IB for the generated by Simulation of Urban Mobility (SUMO) [29].
packet (line 8). The software for the implementation of VMaSC and VMaSC-
Likewise, as provided in Algorithm 3, if the CH generates LTE is available in [48]. SUMO, which is generated by the Ger-
or receives a DAT A_P ACKET for the first time, it checks man Aerospace Center, is an open-source, space-continuous,
the source of the packet (lines 1–3). If the packet is coming and discrete-time traffic simulator that is capable of model-
from eNodeB, the CH broadcasts DAT A_P ACKET to all ing the behavior of individual drivers. The acceleration and
the members of its cluster (lines 4–5). Otherwise, the packet overtaking decision of the vehicles is determined by using the
comes from itself, one of its children or another vehicle in distance to the leading vehicle, traveling speed, dimension of
the SE state. In that case, it broadcasts the packet to the vehicles, and profile of acceleration–deceleration.
members of its cluster, creates an LT E_DAT A_P ACKET The road topology consists of a two-lane and two-way road
containing the data of the received packet, forwards the of length 5 km. The vehicles are injected into the road according
LT E_DAT A_P ACKET to the eNodeB (lines 6–8), and to a Poisson process with a rate equal to two vehicles per
updates its V IB for the packet (line 9). second. The total simulation time is 355 s. The clustering
Upon reception of the LT E_DAT A_P ACKET from a process starts at the 55th second when all the vehicles have
CH, the eNodeB multicasts the packet to all the CHs within entered the road. All of the performance metrics are evaluated
its coverage and forwards it to the EPC via a wired network. for the remaining 300 s. Two classes of vehicles with different
The EPC then determines all the eNodeBs that cover an area maximum speed ranges are used in the simulation to create a
within the dissemination region of the corresponding packet. realistic scenario with different types of vehicles on the road,
The eNodeBs that receive an LT E_DAT A_P ACKET from such as passenger cars, buses, and trucks. The first vehicle class
the EPC then multicast it to all the CHs under their coverage, has a maximum speed of 10 m/s, whereas the maximum speed
which again disseminate the data to their CMs. of the second vehicle class is considered as a variable ranging
from 10 to 35 m/s. Considering the injection of the vehicles
into the road and their maximum speed constraint, the average
number of the neighbors of the vehicles ranges from 10 to 18 at
different times for different scenarios.
Tables V and VI list the simulation parameters of the VANET
and LTE networks, respectively. The maximum number of hops
within a cluster is chosen in the range [1,3] since the number of
hops above three reduces the clustering stability considerably
due to the increase in the number of HELLO_P ACKET s
disseminated within the maximum number of hops, increase
in the number of retransmitted packets lost due to higher
contention, and increase in the number of connections lost
among the CMs due to higher packet collisions. The YANS
channel model [47] used throughout the simulation is based
on first deciding whether a packet can be received at the
beginning of the packet transmission considering the physical
layer and the signal-to-interference-plus-noise ratio (SINR)
level and then determining the successful reception of the
packet probabilistically at the end of the packet transmission
by calculating the packet error rate as a function of the SINR
level, modulation type, transmission rate, and error-correcting
code.
We first compare the stability of the proposed clustering algo-
rithm VMaSC with the previously proposed multihop VANET
clustering algorithms. We then examine the delay and DPDR
performance of the proposed hybrid architecture compared with
both previously proposed cluster-based hybrid architectures and
2630 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 65, NO. 4, APRIL 2016

TABLE V
ns-3 S IMULATION PARAMETERS FOR VANET

Fig. 3. Average CH duration of the clustering algorithms as a function of

maximum vehicle velocities for different maximum numbers of hops.

TABLE VI
ns-3 S IMULATION PARAMETERS FOR LTE

Fig. 4. Average CM duration of the clustering algorithms as a function of

alternative mechanisms, including flooding and pure VANET maximum vehicle velocities for different maximum numbers of hops.
cluster-based data forwarding.

A. VANET Clustering
Here, VMaSC is compared with multihop-clustering algo-
rithms NHop [10] and MDMAC [17], the characteristics of
which are summarized in Table III. The performance met-
rics used for comparison are CH duration, CM duration, CH
change rate, clustering overhead, and number of vehicles in the
SE state.
1) CH Duration: CH duration is defined as the time period
from when a vehicle changes state to CH to when a vehicle
transitions from state CH to state SE or CM .
Fig. 3 shows the average CH duration of the clustering
algorithms as a function of maximum vehicle velocities for
different maximum numbers of hops, whereas Fig. 6(a) shows Fig. 5. CH change rate of the clustering algorithms as a function of maximum
the cumulative distribution function (cdf) of the CH duration vehicle velocities for different maximum numbers of hops.
of VMaSC for different maximum numbers of hops and differ-
ent maximum vehicle velocities. The average CH duration of within each cluster increases the average CH duration and,
VMaSC is higher than that of NHop and MDMAC under all hence, clustering stability. The main reason is that the CH has
conditions, which is mainly due to the efficient cluster main- a higher chance of finding a member to serve as the number
tenance mechanism based on reactive reclustering in VMaSC. of hops increases. Moreover, vehicles collect more informa-
Moreover, increasing the maximum number of hops allowed tion on surrounding vehicles at higher hops, which eventually
UCAR et al.: MULTIHOP-CLUSTER-BASED IEEE 802.11P AND LTE HYBRID ARCHITECTURE FOR VANET SAFETY MESSAGE DISSEMINATION 2631

Fig. 6. CDF of (a) CH duration, (b) CM duration, and (c) CH change rate of VMaSC for different maximum numbers of hops and vehicle velocities.

contributes to better assignment of the roles CH and CM to

the vehicles. Furthermore, the average CH duration, in general,
decreases as the vehicle velocity increases since higher vehicle
velocity results in higher dynamicity of the network topology.
The cdf of the CH duration, on the other hand, shows that the
variation around the average CH duration of VMaSC is small,
demonstrating its stability.
2) CM Duration: CM duration is defined as the time interval
from joining an existing cluster as a member in the CM state to
leaving the connected cluster by transitioning to the SE state.
Fig. 4 shows the average CM duration of the clustering
algorithms as a function of maximum vehicle velocities for
different maximum numbers of hops, whereas Fig. 6(b) shows
the cdf of the CM duration of VMaSC for different maximum
numbers of hops and different maximum vehicle velocities.
Similar to the CH duration, the average CM duration of VMaSC Fig. 7. Clustering overhead of the clustering algorithms for different maxi-
is higher than that of NHop and MDMAC under all conditions, mum numbers of hops as a function of maximum vehicle velocities.
which, again, is mainly due to the efficient cluster maintenance
mechanism as well as the low-overhead and low-delay cluster- rate by leaving the CH state only when there is no member
joining mechanism of VMaSC. The CM duration increases as to serve, whereas NHop and MDMAC use periodic clustering
the maximum number of hops increases since collecting more maintenance, which causes unnecessary CH change in the net-
information on surrounding vehicles at a higher number of hops work. Moreover, VMaSC avoids unnecessary state transitions
enables the selection of better CH for connection. The cdf of the from CH to CM by ensuring the connectivity of two clusters
CM duration, on the other hand, shows that the variation around for M ERGE_T IM ER before merging them. Furthermore,
the average value of the CM duration of VMaSC is minimal, similar to CH and member duration, increasing the number
similar to that of the CH duration. of hops allowed in the clusters decreases the CH change rate
3) CH Change Rate: CH change rate is defined as the and, thus, increases the stability of VMaSC. The cdf of the
number of state transitions from CH to another state per CH change rate, on the other hand, shows that the variation
unit time. around the average CH change rate of VMaSC is again small,
Fig. 5 shows the CH change rate of the clustering algorithms demonstrating its stability.
as a function of maximum vehicle velocities for different 4) Clustering Overhead: Clustering overhead is defined as
maximum numbers of hops, whereas Fig. 6(c) shows the cdf the ratio of the total number of clustering related packets to the
of the CH change rate of VMaSC for different maximum total number of packets generated in the VANET.
numbers of hops and different maximum vehicle velocities. Fig. 7 shows the clustering overhead of the algorithms as
The CH change rate of VMaSC is lower than that of NHop a function of maximum vehicle velocities for different maxi-
and MDMAC in all cases, which again proves the higher mum numbers of hops. The clustering overhead of VMaSC is
stability attained by VMaSC. VMaSC reduces the CH change smaller than that of NHop and MDMAC. The first reason is
2632 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 65, NO. 4, APRIL 2016

Fig. 8. Number of vehicles in the SE state for (a) one-hop, (b) two-hop, and (c) three-hop VMaSC clustering.

better cluster stability of VMaSC with higher cluster head and that integrate the VANET clustering algorithms NHop and
member duration. Another reason is the efficient mechanism MDMAC with LTE; and a recently proposed hybrid archi-
for connection to the cluster through the neighboring CM tecture named CMGM–LTE. CMGM–LTE is the adaptation
instead of connecting to the CH in multiple hops. The VMaSC of the clustering-based multimetric adaptive gateway manage-
also eliminates the overhead of periodic active clustering by ment mechanism (CMGM) proposed for UMTS [33] to LTE.
timer-based cluster maintenance. Moreover, as the maximum CMGM–LTE uses a clustering metric defined as a function
velocity of the vehicles increases, the increase in the clustering of the received signal strength from base stations, direction of
overhead of NHop and MDMAC is steeper than that of VMaSC, movement, and intervehicular distance, and a periodic-cluster-
which illustrates the stability of VMaSC in highly dynamic update-based maintenance mechanism with no any cluster
networks. Furthermore, the clustering overhead of the protocols merging.
increases as the maximum number of hops increases since the The performance metrics are DPDR, delay, and the cost of
HELLO_P ACKET ’s are rebroadcast over multiple hops to using LTE infrastructure.
the neighbors within M AX_HOP . 1) DPDR: This metric is defined as the ratio of the number
5) Number of Vehicles in the SE State: Fig. 8 shows the of vehicles successfully receiving data packets to the total
number of vehicles in the SE state of VMaSC as a function of number of vehicles within the target geographical area for the
simulation time for different maximum numbers of hops and dissemination of the data packet. The average is taken over all
different maximum vehicle velocities. The number of nodes the data packets sent by the vehicles in the simulation.
in the SE state is larger at higher vehicle velocities when the Fig. 9 shows the DPDR of different algorithms at different
maximum number of hops is small. This is expected since the maximum velocities for one-, two-, and three-hop-based clus-
connections in the network break with higher probability as tering mechanisms. The DPDR of VMaSC–LTE is above all
the relative vehicle velocities increase. The difference between the other algorithms in all cases. The reasons for the superior
the number of nodes in the SE state at higher and lower vehicle DPDR performance of VMaSC–LTE over the other hybrid
velocities and the variation in the number of nodes in the SE architectures, namely, CMGM–LTE and MDMAC–LTE, are
state over time, however, decreases as the number of hops better clustering stability, minimal clustering overhead, and
increases. The reasons for this decrease are 1) the suitability minimal overlap among clusters. Higher clustering stability
of a larger set of neighboring vehicles at a higher maximum results in stable connections among CMs and a smaller number
number of hops, allowing better cluster selection for CMs, and of nodes in the SE state. Minimal clustering overhead and
2) the suitability of a larger number of CMs, decreasing the minimal overlap among clusters, on the other hand, decrease
probability of losing all members and transitioning to the SE the medium-access contention, thus increasing the success
state for CHs. probability of the transmissions. The reason for the superior
performance of the clustering-based hybrid architectures over
pure clustering-based data forwarding and pure flooding, on
B. VANET–LTE Hybrid Architectures
the other hand, is the efficiency of LTE-based communica-
The performance of the proposed VANET–LTE hybrid ar- tion among clusters in hybrid architectures. Hybrid archi-
chitecture, namely, VMaSC–LTE, is compared with that of tecture decreases the number of transmissions in the IEEE
flooding; pure VANET cluster-based data-forwarding mecha- 802.11p-based network by providing LTE-based intercluster
nisms, including VMaSC, NHop, and MDMAC, where the CHs communication, which, in turn, decreases the medium-access
relay information over the IEEE 802.11p network instead of contention. Moreover, the DPDR of VMaSC–LTE does not
eNodeBs; hybrid architectures NHop–LTE and MDMAC–LTE considerably change when the maximum velocity increases,
UCAR et al.: MULTIHOP-CLUSTER-BASED IEEE 802.11P AND LTE HYBRID ARCHITECTURE FOR VANET SAFETY MESSAGE DISSEMINATION 2633

Fig. 9. DPDR of data dissemination algorithms at different maximum velocities for (a) one-hop-, (b) two-hop-, and (c) three-hop-based clustering.

Figs. 11 and 12 show the average and maximum delay of

different algorithms at different maximum velocities for one-,
two-, and three-hop-based clustering mechanisms, respectively.
When we consider these results together with Fig. 9, we ob-
serve that there is a tradeoff between DPDR and delay for
flooding and pure cluster-based algorithms: Flooding provides
lower delay than cluster-based algorithms, whereas cluster-
based algorithms achieve a higher DPDR than flooding. LTE-
based hybrid architectures, on the other hand, achieve both low
delay and high DPDR at the cost of using the infrastructure.
Among the hybrid architectures, VMaSC–LTE achieves the
lowest delay. Furthermore, the DPDR and delay analysis at
different numbers of maximum hops allowed within clusters
shows that increasing the maximum number of hops increases
Fig. 10. DPDR of VMaSC and VMaSC–LTE at different vehicle densities. the DPDR at the cost of slight increase in the delay.
3) LTE Cost: The LTE cost metric indicates the cost of using
demonstrating the robustness of the clustering algorithm to the LTE infrastructure to improve the data delivery performance of
increasing dynamicity of the network. Furthermore, the DPDR the hybrid architecture and is measured by the number of CHs
of VMaSC–LTE slightly improves as the maximum number in the network. The number of CHs depends on both the number
of hops increases, which, again, is due to higher clustering of hops used in the clustering algorithm and the constraint on
stability, as demonstrated in Section V-A. the maximum number of members that CH and CM can admit,
Fig. 10 shows the DPDR of VMaSC and VMaSC–LTE at which is denoted by M EM BERCH and M EM BERCM ,
different vehicle densities. The performance of pure cluster- respectively. We assume that the value of M EM BERCH
based data-forwarding mechanism VMaSC is poor at low and varies from 1 to 10; however, the value of M EM BERCM is
high vehicle densities due to the disconnected network and kept constant at 1 in the simulation.
broadcast storm problems, respectively. We observe that LTE- Table VII shows the number of clusters, i.e., number of CHs,
based hybrid architecture VMaSC–LTE improves the perfor- for different M EM BERCH and number of hops values. As
mance greatly, providing a high DPDR that is stable at all M EM BERCH increases, the number of clusters, in general,
vehicle traffic densities. decreases. The number of clusters, however, may increase back
2) Delay: The delay metric is defined as the average latency when the number of hops and M EM BERCH are high, e.g.,
of the data packets that travel from their source to the vehicles M EM BERCH = 10 at a two-hop scenario, due to the higher
within the target geographical area of dissemination. The av- clustering overhead at the CHs, higher contention around CHs,
erage is taken over both the packets and the destinations. On and larger number of CMs affected when a link within the clus-
the other hand, the maximum delay metric is defined as the ter breaks. When both the number of hops and M EM BERCH
maximum latency of the data packets that travel from their are high in a cluster, the number of vehicles connected or
source to the vehicles within the target geographical area of sending a request for connection to the CH is higher. Moreover,
dissemination. the number of packets traveling to the CH is larger. Therefore,
2634 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 65, NO. 4, APRIL 2016

Fig. 11. Average delay of data dissemination algorithms at different maximum velocities for (a) one-hop-, (b) two-hop-, and (c) three-hop-based clustering.

Fig. 12. Maximum delay of data dissemination algorithms at different maximum velocities for (a) one-hop-, (b) two-hop-, and (c) three-hop-based clustering.

TABLE VII hops. We observe that the DPDR increases up to 100 as

N UMBER OF C LUSTERS (LTE C OST ) OF VMaSC–LTE FOR D IFFERENT
M EM BERCH AND N UMBER OF H OPS VALUES M EM BERCH decreases. The main reason for this behavior
is the decrease in the clustering overhead and contention
in the IEEE 802.11p-based network with the decrease in
M EM BERCH . This demonstrates the adaptive usage of
the VMaSC–LTE architecture depending on the reliability
requirement of the application. As the reliability requirement
of the application increases, the value of the M EM BERCH
parameter needs to decrease at the cost of creating a larger
number of clusters, thus increasing the cost of LTE usage.
there exists a lot of contention around the CH. This results in
the loss of packets around the CH and, thus, loss of connections
VI. C ONCLUSION
to the parent node in the routing path to the CH. When the
connection of a vehicle to its parent node breaks, the vehicle In this paper, we have introduced a novel architecture
and all of its children transition back to the SE state, thus VMaSC–LTE that integrates 3GPP/LTE networks with IEEE
increasing the clustering overhead further and possibly creating 802.11p-based VANET networks. In VMaSC–LTE, vehicles
an unnecessarily higher number of clusters. are clustered in a multihop-based novel approach named
Fig. 13 shows the dependence of the DPDR on VMaSC with the features of CH selection using the relative
M EM BERCH for different numbers of maximum allowed mobility metric calculated as the average relative speed with
UCAR et al.: MULTIHOP-CLUSTER-BASED IEEE 802.11P AND LTE HYBRID ARCHITECTURE FOR VANET SAFETY MESSAGE DISSEMINATION 2635

802.11p-based network with the decrease in the number of

CMs. This demonstrates the adaptive usage of the VMaSC–LTE
architecture depending on the reliability requirement of the
application. As the required reliability of the application in-
creases, the number of CMs needs to decrease at the cost of
creating a larger number of clusters, thus increasing the cost of
LTE usage.
As future work, we aim to investigate the use of VMaSC–
LTE in urban traffic scenarios and extend the VMaSC–LTE
architecture with data aggregation and calculation of the clus-
tering metric with additional information such as the most
probable path information of the vehicles.

R EFERENCES
[1] S. Ucar, S. C. Ergen, and O. Ozkasap, “VMaSC: Vehicular multi-hop
algorithm for stable clustering in vehicular ad hoc networks,” in Proc.
WCNC, 2013, pp. 2381–2386.
[2] S. Ucar, S. C. Ergen, and O. Ozkasap, “VeSCA: Vehicular stable cluster-
Fig. 13. DPDR of VMaSC–LTE for different M EM BERCH and number based data aggregation,” in Proc. ICCVE, Vienna, Austria, Nov. 2014.
of hops values. [3] R. Chen, W.-L. Jin, and A. Regan, “Broadcasting safety information in
vehicular networks: Issues and approaches,” IEEE Netw., vol. 24, no. 1,
pp. 20–25, Jan./Feb. 2010.
respect to the neighboring vehicles, cluster connection with [4] The CAMP Vehicle Safety Communications Consortium, “Vehicle safety
minimum overhead by introducing a direct connection to the communications project task 3 final report: Identify intelligent vehicle
neighbor that is already a head or a member of a cluster instead safety applications enabled by DSRC,” CAMP, Farmington Hills, MI,
USA, Dept. Transp., HS 809 859, Jun. 2010.
of connecting to the CH in multiple hops, disseminating CM [5] The CAMP Vehicle Safety Communications Consortium, “Intelligent
information within periodic hello packets, reactive clustering to Transport Systems (ITS); Vehicular communications; Basic set of appli-
maintain the cluster structure without excessive consumption of cations; definitions,” ETSI, Sophia Antipolis, France, ETSI TR 102 861,
Jun. 2010.
network resources, and efficient size- and hop-limited cluster- [6] N. Wisitpongphan et al., “Broadcast storm mitigation techniques in vehic-
merging mechanism based on the exchange of cluster informa- ular ad hoc networks,” IEEE Wireless Commun., vol. 14, no. 6, pp. 84–94,
tion among CHs. In the constructed clusters, CHs activate the Dec. 2007.
[7] N. Wisitpongphan, F. Bai, P. Mudalige, V. Sadekar, and O. Tonguz, “Rout-
LTE interface to connect the VANET to LTE. ing in sparse vehicular ad hoc wireless networks,” IEEE J. Sel. Areas
Extensive simulations in ns-3 with the vehicle mobility Commun., vol. 25, no. 8, pp. 1538–1556, Oct. 2007.
input from SUMO demonstrate the superior performance of [8] T. Song, W. Xia, T. Song, and L. Shen, “A cluster-based direc-
tional routing protocol in VANET,” in Proc. 12th IEEE ICCT, 2010,
VMaSC–LTE over both previously proposed hybrid architec- pp. 1172–1175.
tures and alternative routing mechanisms, including flooding [9] B. Wiegel, Y. Gunter, and H. Grossmann, “Cross-layer design for packet
and cluster-based routing. We observe that the DPDR per- routing in vehicular ad hoc networks,” in Proc. 66th IEEE VTC Fall, 2007,
pp. 2169–2173.
formance of pure cluster-based data-forwarding mechanism is [10] Z. Zhang, A. Boukerche, and R. Pazzi, “A novel multi-hop clustering
poor at low and high vehicle densities due to the disconnected scheme for vehicular ad-hoc networks,” in Proc. 9th ACM Int. Symp.
network and broadcast storm problems, respectively. The LTE- Mobility Manage. Wireless Access, 2011, pp. 19–26.
[11] N. Maslekar, M. Boussedjra, J. Mouzna, and L. Houda, “Direction based
based hybrid architecture, however, improves the performance clustering algorithm for data dissemination in vehicular networks,” in
greatly, providing a high DPDR that is stable at all vehi- Proc. IEEE VNC, 2009, pp. 1–6.
cle traffic densities. Moreover, despite the tradeoff between [12] H. Su and X. Zhang, “Clustering-based multichannel MAC protocols for
QoS provisionings over vehicular ad hoc networks,” IEEE Trans. Veh.
DPDR and delay observed for flooding and pure cluster-based Technol., vol. 56, no. 6, pp. 3309–3323, Nov. 2007.
algorithms, the proposed architecture has been demonstrated [13] M. Venkata, M. Pai, R. Pai, and J. Mouzna, “Traffic monitoring and
to achieve both low delay and high DPDR at the cost of routing in VANETs—A cluster based approach,” in Proc. 11th Int. Conf.
ITST, 2011, pp. 27–32.
using the LTE infrastructure. Among the hybrid architectures, [14] Y. Zhang and J. M. Ng, “A distributed group mobility adaptive cluster-
VMaSC–LTE achieves the lowest delay and highest DPDR due ing algorithm for mobile ad hoc networks,” in Proc. IEEE ICC, 2008,
to better clustering stability, minimal clustering overhead, and pp. 3161–3165.
[15] Z. Y. Rawashdeh and S. Mahmud, “A novel algorithm to form stable
minimal overlap among clusters. The DPDR and delay analysis clusters in vehicular ad hoc networks on highways,” EURASIP J. Wireless
at different numbers of maximum hops allowed within clusters Commun. Netw., vol. 2012, no. 1, p. 15, Jan. 2012.
shows that increasing the maximum number of hops up to three [16] A. Daeinabi, A. G. Pour Rahbar, and A. Khademzadeh, “VWCA: an
efficient clustering algorithm in vehicular ad hoc networks,” J. Netw.
increases the DPDR at the cost of slight increase in the delay. Comput. Appl., vol. 34, no. 1, pp. 207–222, Jan. 2011.
We have also defined the LTE cost metric as the cost of using [17] G. Wolny, “Modified DMAC clustering algorithm for VANETs,” in Proc.
LTE infrastructure to improve the data delivery performance ICSNC, 2008, pp. 268–273.
[18] Z. Wang, L. Liu, M. Zhou, and N. Ansari, “A position-based clustering
of the hybrid architecture. The LTE cost is measured by the technique for ad hoc intervehicle communication,” IEEE Trans. Syst.,
number of CHs in the network. We observe that the DPDR Man, Cybern. C, Appl. Rev., vol. 38, no. 2, pp. 105–110, pp. 201–208,
increases up to 100 as the number of members allowed in the Mar. 2008.
[19] B. Hassanabadi, C. Shea, L. Zhang, and S. Valaee, “Clustering in vehic-
clusters decreases. The main reason for this behavior is the ular ad hoc networks using affinity propagation,” Ad Hoc Netw., vol. 13,
decrease in the clustering overhead and contention in the IEEE no. Part B, pp. 535–548, Feb. 2014.
2636 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 65, NO. 4, APRIL 2016

[20] E. Souza, I. Nikolaidis, and P. Gburzynski, “A new Aggregate Local [48] VMaSC, VMaSC. [Online]. Available: https://bitbucket.org/sucar/vmasc-
Mobility ALM; Clustering algorithm for VANETs,” in Proc. IEEE ICC, clustering
May 2010, pp. 1–5.
[21] O. Tonguz, N. Wisitpongphan, F. Bai, P. Mudalige, and V. Sadekar,
“Broadcasting in VANET,” in Proc. Mobile Netw. Veh. Environ., 2007, Seyhan Ucar (S’14) received the B.S. degree in
pp. 7–12. computer engineering from Izmir Institute of Tech-
[22] O. Tonguz, N. Wisitpongphan, and F. Bai, “DV-CAST: A distributed ve- nology, Izmir, Turkey, in 2011 and the M.S. de-
hicular broadcast protocol for vehicular ad hoc networks,” IEEE Wireless gree in computer science and engineering from Koç
Commun., vol. 17, no. 2, pp. 47–57, Apr. 2010. University, Istanbul, Turkey, in 2013, where he is
[23] Project Cooperative Cars, CoCar. [Online]. Available: http://www.aktiv- currently working toward the Ph.D. degree in com-
online.org/english/aktiv-cocar.html puter science and engineering with the Wireless
[24] LTE-Connected Cars, ng Connect Program. [Online]. Available: http:// Networks Laboratory under the supervision of
ngconnect.org Prof. S. Coleri Ergen and Prof. O. Ozkasap.
[25] H. Abid, T.-C. Chung, S. Lee, and S. Qaisar, “Performance analysis His research interests are cross-layer design for
of LTE smartphones-based vehicle-to-infrastructure communication,” in intervehicle communication, distributed algorithms,
Proc. 9th Int. Conf. UIC/ATC, 2012, pp. 72–78. and hybrid architectures for vehicular ad hoc networks.
[26] G. Araniti, C. Campolo, M. Condoluci, A. Iera, and A. Molinaro, “LTE
for vehicular networking: A survey,” IEEE Commun. Mag., vol. 51, no. 5,
pp. 148–157, May 2013.
[27] I. Lequerica, P. Ruiz, and V. Cabrera, “Improvement of vehicular commu-
nications by using 3G capabilities to disseminate control information,”
IEEE Netw., vol. 24, no. 1, pp. 32–38, Jan./Feb. 2010.
[28] Traffic and Network Simulation Environment, TranNS. [Online].
Available: http://trans.epfl.ch/
[29] Simulation of Urban MObility, SUMO. [Online]. Available: http://http:// Sinem Coleri Ergen (S’98–M’05) received the B.S.
sumo.sourceforge.net/ degree in electrical and electronics engineering from
[30] G. Remy, S. M. Senouci, F. Jan, and Y. Gourhant, “LTE4V2X: LTE for Bilkent University, Ankara, Turkey, in 2000 and the
a centralized VANET organization,” in Proc. IEEE GLOBECOM, 2011, M.S. and Ph.D. degrees in electrical engineering and
pp. 1–6. computer science from the University of California,
[31] M. Fiore, J. Harri, F. Filali, and C. Bonnet, “Vehicular mobility simulation Berkeley, CA, USA, in 2002 and 2005, respectively.
for VANETs,” in Proc. 40th ANSS, 2007, pp. 301–309. From 2006 to 2009, she was a Research Sci-
[32] T. Taleb and A. Benslimane, “Design guidelines for a network architecture entist with the Wireless Sensor Networks Berkeley
integrating VANET with 3G & beyond networks,” in Proc. IEEE GLOBE- Lab, under the sponsorship of Pirelli and Telecom
COM, 2010, pp. 1–5. Italia. Since September 2009, she has been an As-
[33] A. Benslimane, T. Taleb, and R. Sivaraj, “Dynamic clustering-based adap- sistant Professor with the Department of Electrical
tive mobile gateway management in integrated VANET—3G heteroge- and Electronics Engineering, Koç University, Istanbul, Turkey. Her research
neous wireless networks,” IEEE J. Sel. Areas Commun., vol. 29, no. 3, interests are in wireless communications and networking, with applications in
pp. 559–570, Mar. 2011. machine-to-machine communications, control systems, and intelligent trans-
[34] R. Sivaraj, A. Gopalakrishna, M. Chandra, and P. Balamuralidhar, “QoS- portation systems.
enabled group communication in integrated VANET–LTE heterogeneous Dr. Coleri Ergen received the Science Academy Young Scientist Award
wireless networks,” in Proc. 7th IEEE WiMob Comput., Netw. Commun., (BAGEP) in 2014, the Turk Telekom Collaborative Research Award in 2011
2011, pp. 17–24. and 2012, the Marie Curie Reintegration Grant in 2010, the Regents Fellowship
[35] A. Benslimane, S. Barghi, and C. Assi, “An efficient routing protocol from the University of California, Berkeley in 2000, and the Bilkent University
for connecting vehicular networks to the Internet,” Pervasive Mobile Full Scholarship from Bilkent University in 1995.
Comput., vol. 7, no. 1, pp. 98–113, Feb. 2011.
[36] F. Karnadi, Z. H. Mo, and K.-C. Lan, “Rapid generation of realistic
mobility models for VANET,” in Proc. IEEE WCNC, Mar. 2007,
pp. 2506–2511.
[37] J. Ng and Y. Zhang, “A mobility model with group partitioning for wire-
less ad hoc networks,” in Proc. 3rd ICITA, 2005, vol. 2, pp. 289–294.
[38] R. S. Bali, N. Kumar, and J. J. Rodrigues, “Clustering in vehicular ad hoc
networks: Taxonomy, challenges and solutions,” Veh. Commun., vol. 1, Oznur Ozkasap (M’15) received the B.S., M.S., and
no. 3, pp. 134–152, Jul. 2014. Ph.D. degrees in computer engineering from Ege
[39] J. Yu and P. Chong, “3hBAC (3-hop between adjacent clusterheads): A University, Izmir, Turkey, in 1992, 1994, and 2000,
novel non-overlapping clustering algorithm for mobile ad hoc networks,” respectively.
in Proc. IEEE PACRIM Commun., Comput. Signal Process., 2003, vol. 1, From 1997 to 1999, she was a Graduate Research
pp. 318–321. Assistant with the Department of Computer Science,
[40] A. Damnjanovic et al., “A survey on 3GPP heterogeneous networks,” Cornell University, Ithaca, NY, USA, where she
IEEE Wireless Commun., vol. 18, no. 3, pp. 10–21, Jun. 2011. completed the Ph.D. dissertation. She is currently an
[41] S. Yousefi, E. Altman, R. El-Azouzi, and M. Fathy, “Analytical model for Associate Professor with the Department of Com-
connectivity in vehicular ad hoc networks,” IEEE Trans. Veh. Technol., puter Engineering, Koç University, Istanbul, Turkey,
vol. 57, no. 6, pp. 3341–3356, Nov. 2008. which she joined in 2000. Her research interests
[42] M. Rudack, M. Meincke, and M. Lott, “On the dynamics of ad-hoc include distributed systems, multicast protocols, peer-to-peer systems, bioin-
networks for inter vehicle communications,” in Proc. ICWN, Las Vegas, spired distributed algorithms, mobile ad hoc networks, energy efficiency, cloud
NV, USA, 2002, pp. 40–48. computing, and computer networks.
[43] R. S. Rao, S. K. Soni, N. Singh, and O. Kaiwartya, “A probabilistic Dr. Ozkasap served as an Area Editor for the Computer Networks journal,
analysis of path duration using routing protocol in VANETs,” Int. J. Veh. Elsevier Science, as a Management Committee Member of the European COST
Technol., vol. 2014, 2014, Art. ID. 495 036. Action IC0804: Energy efficiency in large-scale distributed systems, and as a
[44] F. Bai, N. Saragopan, and A. Helmy, “The important framework for member of the European COST Action 279: Analysis and Design of Advanced
analyzing the impact of mobility on performance of routing protocols for Multiservice Networks supporting Mobility, Multimedia, and Internetworking.
adhoc networks,” Ad Hoc Netw., vol. 1, no. 4, pp. 383–403, Nov. 2003. She served as the Publications Chair of the ACM Conference on Online Social
[45] S. Al-Sultan, M. M. Al-Doori, A. H. Al-Bayatti, and H. Zedan, “A com- Networks (COSN) in 2014 and as the Cochair of the NSF United States/Middle
prehensive survey on vehicular ad hoc network,” J. Netw. Comput. Appl., East Workshop on Trustworthiness in Emerging Distributed Systems and Net-
vol. 37, pp. 380–392, Jan. 2014. works in 2012. She received the Turk Telekom Collaborative Research Awards
[46] Network simulator, ns-3. [Online]. Available: http://www.nsnam.org/ in 2012, the Career Award from TUBITAK (The Scientific and Technological
[47] M. Lacage and T. R. Henderson, “Yet another network simulator,” in Proc. Research Council of Turkey) in 2004, and the TUBITAK/NATO A2 Ph.D.
Workshop Ns-2—IP Netw. Simul., 2006, p. 12. Research Scholarship Abroad in 1997.