
A Cluster-based Delay Tolerant Routing Algorithm
for Vehicular Ad Hoc Networks
Jun Zheng, Hui Tong, and Yuying Wu
National Mobile Communications Research Laboratory
Southeast University
Nanjing, Jiangsu 210096, China
Email: junzheng@seu.edu.cn
Abstract—This paper proposes a Cluster-based On-demand
DElay tolerant routing (CODE) algorithm for VANETs. The
CODE algorithm considers a higyway scenario and performs
route discovery for data dissemination based on a cluster-based
routing structure. To build the routing structure, CODE first
configures vehicles moving on the highway into clusters and uses
the relative speeds of vehicles in cluster-head election. A vehicle
moving at a speed closer to the average speed of all vehicles has a
higher probability to be elected as cluster head. The purpose is to
maintain the stability of a cluster in order to achieve a good data
delivery performance. Based on this routing structure, an on-
demand delay tolerant route discovery mechanism is employed to
find an available route for disseminating data packets from a
source node to a destination node. Simulation results show that
the proposed CODE algorithm has a better cluster stability, and
can achieve a better performance in terms of end-to-end delay,
packet loss ratio, and routing overhead as compared with
existing LID and HD algorithms.
Keywords—cluster; delay tolerant; routing; vehicular ad hoc
network
I. I
NTRODUCTION
Routing is a critical issue in vehicular ad hoc networks
(VANETs). A VANET consists of vehicles moving on roads
and roadside units deployed along roads, which are connected
to form a network in an ad hoc manner to provide a variety of
potential applications [1]. In many VANET applications, a
vehicle needs to disseminate data to a destination via other
vehicles or roadside units. To implement this, an efficient
routing algorithm must be employed to find an optimal
multihop route for disseminating the data. Due to the high
mobility of vehicles, however, the topology of a VANET may
change frequently and the network connectivity is often
intermittent, which presents a big challenge for the design of a
routing algorithm. To address this challenge, routing has been
extensively studied for VANETs.
Cluster-based hierarchical routing is a routing paradigm
for mobile ad hoc networks (MANETs). Compared with a
MANET, a VANET has a higher mobility, especially in a
highway scenario, where vehicles are sparsely distributed and
move at a high speed. The relative positions and speeds of
vehicles moving on a highway change more slowly than those
of vehicles moving on an urban road. On the other hand,
vehicles on a highway move almost in the same direction
within a certain area. For these reasons, the movement of
vehicles on a highway is relatively stable, which makes cluster-
based hierarchical routing possible in a VANET.
Cluster-based hierarchical routing has received much
attention and has been considered a promising solution to the
problem [2]. In [3], Joe and Shin have shown through
theoretical analysis that clustering-based routing is more
energy efficient than flat routing. In [4], Yu and Chong gave
several benefits of clustering for MANETs. For example,
clustering can facilitate the spatial reuse of spectrum resources,
and thus increase the network capacity. With clustering, cluster
heads and gateways form a virtual backbone for routing, which
can effectively reduce the routing overhead. However, these
efforts mainly consider MANETs. The potentiality of this
routing paradigm for VANET remains to be explored [5],
which is the motivation for this work.
In this paper, we explore cluster-based routing for
VANET and propose a Cluster-based On-demand DElay
tolerant routing (CODE) algorithm for a highway scenario. The
CODE algorithm performs route discovery for data
dissemination based on a cluster-based routing structure. To
build the routing structure, CODE first configures vehicles
moving on the highway into clusters and uses the relative
speeds of vehicles in cluster-head election. A vehicle moving
at a speed closer to the average speed of all vehicles has a
higher probability to be elected as cluster head. The purpose is
to maintain the stability of a cluster in order to achieve a good
packet delivery performance [6-9]. Based on this routing
structure, an on-demand delay tolerant route discovery
mechanism is employed to find an available route for
disseminating data packets from a source node to a destination
node. Simulation results show that CODE has a better cluster
stability than existing LD and HD algorithms, and can achieve
a better performance in terms of end-to-end delay, packet loss
ratio, and routing overhead.
The remainder of the paper is organized as follows.
Section II reviews related work. Section III presents the
proposed CODE algorithm. Section IV shows the simulation
results to evaluate the performance of the CODE algorithm.
Section V concludes this paper.
II. R
ELATED
W
ORK
Clustering has widely studied for MANETs. Several typical
clustering algorithms have been proposed for cluster head
This work was supported by the National Natural Science Foundation o
China under Grant No. 61372105 and the Six Talent Peaks Project in Jiangs
Province under Grant No. 2013-DZXX-010.
978-1-5090-5932-4/17/$31.00 ©2017 IEEE