Performance evaluation and comparative study of main VDTN routing protocols under small- and large-scale scenarios

Abstract

This paper presents a performance evaluation through simulations and a comparative study of main routing protocols dedicated to Vehicular Delay-Tolerant Networks. The assessment is conducted under small- and large-scale scenarios with realistic vehicle mobility patterns as defined in the TAPAS Cologne simulation scenario. Through the literature, several evaluations have been conducted on routing for Vehicular Networks, but with an abstraction or a simplification regarding the delay tolerant aspect. Furthermore, considered scenarios were relatively small and too idealistic compared to the real-world environment and its multiples challenges. Moreover, to the best of our knowledge, this is the first extensive study that compares, in the same realistic simulation environment, the main flag-carriers of various categories of VDTN routing protocols, namely Epidemic, Direct Delivery, Prophet and GeoSpray protocols. Simulation results reveal better performance for the geographical approach advocated by GeoSpray compared to the predictive one of Prophet, under all considered scenarios. Moreover, they highlight the possibility for a minimalist and naive protocol such as Direct Delivery to perform well, under specific network conditions, as when considering an anycast communication scheme. Finally, deeper analysis was undertaken on both GeoSpray and Prophet. The studies reveal the potentialities to increase the performances of GeoSpray to some extent and highlight the difficulties of adapting Prophet settings for optimal performance in realistic scenarios.

Introduction

The rapid population growth and the large expanse of urban areas have led to real-life transportation problems like accidents and traffic jams, which by a domino effect, have resulted in economic and ecologic concerns, namely: a notable increase in goods delivery delays, a waste of precious resources, especially oil, and a rise in pollution. In fact, the World Health Organization (WHO) reported in [1] that more than 1.2 million people die each year due to road injuries, making it the first cause of death among people aged between 15 and 29 years. In the meantime, the Texas Transportation Institute has estimated the cost of congestion to be up to 160 billion dollars with 6.9 billion hours lost and 11.7 billion litres of oil wasted in 471 major urban areas of the United-States in 2014 alone [2].

In order to tackle these problems, researchers proposed a Traffic Information System (TIS) that specifically addresses traffic jams thanks to notification systems based on GPS-capable equipment. Despite the use of TIS which provides directional guidance, the lack of cooperation between vehicles, the limited application scope of TIS along with the development of affordable information technology nowadays, such as cellular networks and Wi-Fi, foster the emergence of enhanced and augmented TIS, called Intelligent Transportation Systems (ITS). These differ ostensibly from their predecessors. Firstly, their application scope is threefold: road safety, road traffic information and any third-party application with multimedia content. Secondly, unlike TIS, they make use of global and on-board sensors to gather information on the state of road traffic. They also introduce the concept of Inter-Vehicle Communication (IVC) which involves a wide range of technology and standards dedicated to communication from a car to any other entity in the network (C2X), like Dedicated Short Range Communication (DSRC) [3] and IEEE 802.11p Wi-Fi standard [4], [5]. With IVC, vehicles play an active role in gathering information, cooperating with other vehicles and finally reporting information to the main system [6].

In this global context, networks constituted by vehicles, commonly named Vehicular Networks or Vehicular Ad-hoc Networks (VANETs) have emerged as a hot research topic with the goal of providing the ITS applications cited before to road network users. However, running such applications over VANETs is a challenging task because routing protocols must overcome relevant problems that arise from vehicular environments. Indeed, the high mobility and speed of vehicles engender a very dynamic network topology with short contact durations, whereas urban environments limit transmission ranges due to physical obstacles and radio interference. Therefore, in a realistic VANET context, it is often hard to establish and maintain an end-to-end path between the sender and the recipient due to network issues like topology partitioning and intermittent connectivity. This severely limits the potential use of the conventional routing approach based on the TCP/IP protocol suite. Consequently, and to overcome these problems, VANETs are extended using main Delay-Tolerant Networks (DTNs) principles, leading to the advent of two categories of vehicular networks. The first ones, conventionally called VANETs, are delay-sensitive and operate only when full connectivity exists to support the end-to-end semantics of existing transport and application network layers. Thus they are strongly adapted to road safety applications where data must be delivered on-time. The latter ones are Vehicular Delay Tolerant Networks (VDTNs)[7], characterised by a good resilience to delay and to network disconnections, thanks to the Store, Carry and Forward (SCF) concept inherited from DTNs, which allows a forwarder to carry messages until it finds a suitable relay. Therefore, VDTNs can support applications with intermittent connectivity, such as road traffic information, or third-party services that range from emails, web access or any time unconstrained applications like multimedia content download or geographic services discovery. This work addresses the VDTN category with a focus on routing protocols that can support road traffic information and the kind of application operating with intermittent connectivity.

Many VDTN routing protocols are proposed in the literature following various forwarding approaches and replication strategies which differ ostensibly regarding the information needed to make the forwarding decision. Nevertheless, in practice, there are still few operational use cases and almost no wide-ranging implementations. In fact, whilst modelling VDTNs and studying their topology & behaviour can be achieved through theoretical approaches like temporal networks, to extract key facts which are able to provide general guidance for researchers, the evaluation of routing protocols dedicated to VDTNs requires a more concrete and straightforward approach, by relying, for instance, on real world experimentation or on realistic and sufficient large-scale testbeds. However, since these experiments are difficult to conduct and existing testbeds are not largely accessible to the research community for large-scale evaluation, computer simulations remain the main tool for large-scale assessment of VDTN routing protocols, especially when multiple simulators and tools exist and are widely available. Regarding the investigated protocols, in many cases, they are envisioned to provide data routing for a specific range of applications/services. Therefore, their evaluation scenarios are limited to the targeted use cases. It is then difficult to extend and reproduce the obtained results to other scenarios, protocols, and applications. In some cases, a simplification of the simulation scenario is introduced with the aim of reducing the processing time, which can be prohibitive when simulating realistic VDTN environments. While such an approach can help to quickly allow observation of general trends in the performance of some protocols, the obtained results have limited and contextual validation, since the evaluation context is not reflective of the characteristics of a realistic vehicular environment.

In [8], the authors identify three key aspects that are essential to ensure the validity, the compatibility and the reproducibility of the assessment through simulations of VDTN routing protocols. The first one is related to the considered network simulation tool. For instance, some simulation frameworks focus mainly on the behaviour of the routing protocol, at the networking layer, and make a partial or total abstraction of other components in the communication stack, the underlying transmission conditions and application traffic patterns. Such approaches are useful for understanding the behaviour of a VDTN routing protocol in an isolated manner but are far from being realistic and cannot be considered to offer a valid overall evaluation. The second and third aspects are related to the specificities of the vehicular environment: namely, the considered vehicles mobility model and the road topology. Indeed, these two aspects have an important impact on the routing protocol performances because they dictate the dynamics of Vehicle-To-Vehicle (V2V) communication. Consequently, in order to avoid overestimating the performances of VDTN routing protocols, the researchers are invited to use realistic road topologies and detailed representations of the vehicular traffic both at microscopic level (individual vehicle physical characteristics and behaviour) as well as macroscopic level (flow patterns based on diurnal cycles, population synthesis and activities). These last two points can be satisfied with real vehicle mobility traces and road topology extracted from real street maps [9].

Another important practical issue that arises when evaluating VDTN routing protocols is related to the availability of implementation codes of these protocols in the same simulation environment. While several VDTN routing protocols were evaluated in different simulation frameworks, each having its own degree of realism and parameter setting, only a limited number of implementation codes are publicly available. Moreover, most of the implementations are dedicated to different simulators. Thus, an important gap that must be addressed is the availability of DTN routing protocol implementations in a common simulation environment.

Through this work, we aim to contribute to the research on VDTN routing protocols by presenting a performance evaluation and a quantitative comparison of main VDTN routing protocols, based on the joint use of realistic simulators/tools and vehicle mobility datasets. To the best of our knowledge, this is the first extensive study that compares, in the same realistic simulation environment, the main flag-carriers of various categories of VDTN routing protocols, namely Epidemic, Direct Delivery, Prophet and GeoSpray protocols. We analyse the obtained results under different simulation scenarios, ranging from small-scale topologies to a realistic large-scale scenario defined in the TAPAS Cologne simulation scenario. We discuss the sensitivity of the results for the considered small-scale vs large-scale scenarios and we extract some key facts and recommendations that can guide future work in order to improve the performance of current VDTN protocols.

The rest of this paper is organised as follows. Taxonomy of VDTN routing protocols and the state of the art on their performance evaluations are presented under Sections 2 and 3, respectively. In Section 4, we describe in detail four VDTN protocols that we selected as representative of proposed forwarding strategies and metrics, replication policies, etc, namely Epidemic [10], Direct-Delivery [11], Prophet protocol [12], [13] and GeoSpray [14]. Then, in Section 5, we discuss various criteria for choosing an adapted simulation tool and we justify our choice for Omnet++ [15] and the vehicular simulation framework Veins [16] from among the plethora of available network simulators. We then describe the architectural design, which forms the basis of our common implementation of the four above-mentioned protocols in the same Omnet++/Veins simulation framework. In Section 6, a performance evaluation of the considered protocols is conducted under a synthetic small-scale scenario as well as under a large-scale scenario provided by the TAPAS-Cologne dataset [9]. We provide a deep analysis of the observed performances of each protocol with respect to different metrics (Delivery Ratio, Overhead, Average Delay and Hop Counts) and discuss the sensitivity of the observations for the considered simulation settings (e.g. small-scale vs. large-scale topologies). After comparing the different protocols, we focus on GeoSpray to reveal the potentiality to increase its performance. Finally, we conclude this paper in Section 7 by summarising some key facts and observations that arise from this study.