Routing protocols in Vehicular Delay Tolerant Networks: A comprehensive survey

Abstract

This article presents a comprehensive survey of routing protocols proposed for routing in Vehicular Delay Tolerant Networks (VDTN) in vehicular environment. DTNs are utilized in various operational environments, including those subject to disruption and disconnection and those with high-delay, such as Vehicular Ad-Hoc Networks (VANET). We focus on a special type of VANET, where the vehicular traffic is sparse and direct end-to-end paths between communicating parties do not always exist. Thus, communication in this context falls into the category of Vehicular Delay Tolerant Network (VDTN). Due to the limited transmission range of an RSU (Road Side Unit), remote vehicles, in VDTN, may not connect to the RSU directly and thus have to rely on intermediate vehicles to relay the packets. During the message relay process, complete end-to-end paths may not exist in highly partitioned VANETs. Therefore, the intermediate vehicles must buffer and forward messages opportunistically. Through buffer, carry and forward, the message can eventually be delivered to the destination even if an end-to-end connection never exists between source and destination. The main objective of routing protocols in DTN is to maximize the probability of delivery to the destination while minimizing the end-to-end delay. Also, vehicular traffic models are important for DTN routing in vehicle networks because the performance of DTN routing protocols is closely related to population and mobility models of the network.

Introduction

Intelligent Transportation Systems (ITS), are advanced applications aiming to provide innovative services related to different modes of transport and traffic management, through vehicular communication, to improve road safety and to provide more comfort for conductors. Cars equipped with wireless devices can exchange traffic and road safety information with nearby cars and/or roadside units. Vehicular Networks have become a popular research topic during the last years, due to the important applications that can be realized in such an environment. In [1], the authors have divided such applications into two major categories: safety applications that increase vehicle safety on the roads, and user applications that provide value added services, such as entertainment. Inter-vehicle communication (IVC) can increase the safety, efficiency, and convenience of transportation systems involving planes, trains, automobiles, and robots [2]. In vehicular networks, messages between vehicles can be used to detect different levels of traffic jams [3], and thus traffic congestion can be reduced with the help of vehicle-to-vehicle communication [4]. Recently, the authors in [5] presented how IVC can reduce the number of secondary collisions caused by an accident, through dissemination of warning messages. A more recent survey of other applications and use cases can be found in [6], where the authors classified them into three categories: (1) Active road safety applications, (2) Traffic efficiency and management applications, and (3) Infotainment applications.

Direct communication between vehicles may be established via mobile ad hoc networks (MANETs), which do not rely on fixed infrastructure. Research on MANETs covers application requirements and communication protocols for everything from sensor networks to hand-held computers and vehicular systems [2]. Vehicular Ad-Hoc Networks (VANET) is a technology that uses vehicles as nodes. Thus, MANETs that span airplanes, trains, cars, and robots are called VANETs. However, VANETs exhibit bipolar behavior depending on network topology: fully connected topology with high traffic volume or sparsely connected topology when traffic volume is low [7]. Thus, one can distinguish between two different categories of vehicular networks: VANETs as presented above and Vehicular Delay Tolerant Networks (VDTNs) which are vehicular networks in sparse traffic (Fig. 1), and where Delay Tolerant Network (DTN) protocols can be applied. In order to guarantee the feasibility of many applications through vehicular networks, it is imperative to design networking protocols that can overcome relevant problems that arise from vehicular environments.

Furthermore, Internet protocols do not work well for some environments [8], due to some fundamental assumptions built into the Internet architecture such as the existence of an end-to-end path between source and destination for the duration of a communication session, short end-to-end round-trip delay time [9], and the perception that packet switching is the most appropriate abstraction for interoperability and performance.

The high mobility and speed of nodes in vehicular environments is responsible for a highly dynamic network topology that is different from the traditional concept of the Internet. These nodes can exhibit short contact durations, or move in an unpredictable way [10]. The links may be short lived, with high link error rates, and the absence of an end-to-end path from source to destination. As a result, networks in such environments can be partitioned, due to the large distances involved and to variable node densities and sparse traffic, resulting in discontinuities along the path from source to destination [11].

Many conventional routing protocols were designed for VANETs in the case of a fully interconnected environment, aiming to establish end-to-end connectivity among network nodes [12]. However, these protocols cannot be used when the traffic quiets down. End-to-end connections via intermediate nodes cannot be established any more [13]. Thus, this category of routing protocols fails to deliver data in sparse traffic, partitioned networks, and opportunistic vehicular networks.

In an attempt to address this problem, vehicular networks may deliver data using the store-carry-and-forward (SCF) paradigm of DTNs [8] rather than a simple carry-and-forward method. Consequently, asynchronous, long and variable length messages, called bundles, can be opportunistically routed towards the destinations through intermittent connections, assuming that end-to-end network path is not necessarily currently available, but rather that such a path exists over time. Thus, DTNs in vehicular environment are called Vehicular Delay Tolerant Networks (VDTNs) [14]. In vehicular DTNs, contacts between nodes appear without any previous knowledge [13], and therefore the challenges that DTNs need to overcome have led to significant research focused on routing.

We particularly acknowledge some related and excellent surveys on DTN [15], [16]. For example, the survey in [15] covers the literature until mid 2010. In this paper, we update these surveys by providing the advances in VDTN forwarding algorithms from mid 2010 to February 2013, the date used in writing this paper. Some previous algorithms are provided as background for better readability.

The remainder of this paper is organized as follows. Section 2 is an overview of DTNs focusing on routing protocols used in such networks. Section 3 deals with the unsuitability of VANET routing protocols for VDTNs. Section 4 provides a detailed description of VDTNs, related routing protocols and discusses challenges and open issues. Finally Section 5 concludes the paper and suggests further research works.