Vehicular Disruption Tolerant Networks

Introduction

Traditional networks suppose the existence of some path between end-points, short end-to-end round-trip delay time and small loss ratio. Today, however, new applications, environments and types of devices are challenging these assumptions. In Disruption Tolerant Networks, also called sometimes opportunistic networks, an end-to-end path from source to destination may not exist. In this environment nodes can still connect and exchange information, but in an opportunistic way. Delay Tolerant Networks have been developed as an approach to building architecture models which are tolerant to long delays and/or disconnected 25 Vehicular Disruption Tolerant Networks 26 network partitions when delivering data to destinations. This chapter discusses the characteristics of these architectures, and many of the protocols developed to ensure packet delivery in these networks. We henceforth use DTN to refer to Delay Tolerant Networking, Disruption Tolerant Networks and Opportunistic Networks. For Vehicular DTN, the acronym VDTN is used. The vehicular network research eld, and more specically the VDTN research eld, have attracted great attention in the last few years. Initiatives such as the i2010 Intelligent Car Initiative Intelligent Car (2009) aim to decrease the number of accidents and CO2 emissions in Europe, utilizing sensors and vehicle-to-vehicle (V2V) communication. As part of these projects, cars equipped with wireless devices will exchange trac and road safety information with nearby cars and/or roadside units. In fact, according to the ETSI 102 638 technical report [41], by 2017 20% of the running vehicles will have wireless communication capabilities. The same report estimates that by 2027 almost 100% of the vehicles will be equipped with communication devices. The design of the core Internet protocols is based on a number of assumptions: these include the existence of some path between endpoints, short endto-end round-trip delay time, and the perception of packet switching as the right abstraction for end-to-end communications. Furthermore, the eciency of these protocols is based on assumptions about the resources available to the nodes and the properties of the links between them. Traditionally nodes are considered to be xed, energy unconstrained, connected by low loss rate links, and communication occurs through the exchange of data between two or more nodes. Today, however, new applications, environments and types of devices are challenging these assumptions and call for new architectures and modes of node operation. Some of these challenges are: intermittent and/or scheduled links, very large delays, high link error rates, energy-constrained devices, with heterogeneous underlying network architectures and protocols in the protocol stack, and most importantly, the absence of an end-to-end path from a source to a destination. Applications on the following environments may pose such challenges: spacecrafts, planetary/interplanetary, military/tactical, disaster response, mobile sensors, vehicular environments, satellite and various forms of large scale ad hoc networks. The variety of these applications, the impossibility of having a xed wired Internet infrastructure everywhere, and the inclusion of mobility in most of these applications, make these challenges more dicult to surmount. This leads us to a new approach of designing networks, taking into account several constraints and characteristics, using DTN. 3.2 Background 27 3.2 Background VDTNs have evolved from DTNs and are formed by cars and supporting xed nodes. Fall [42] is one of the rst authors to dene and discuss DTNs’ potential. According to his denition, a DTN consists of a sequence of timedependent opportunistic contacts. During these contacts, messages are forwarded from their source towards their destination. This is illustrated in Figure 3.1. In the rst contact the origin sends the message to A in time t1, then A holds the message until it is delivered to the destination in the contact at time t2. Figure 3.1: A representation of two communication opportunities in a VDTN Contacts are characterized by their start and end times, capacity, latency, end points and direction. The routing algorithm can use these pieces of information to decide the most appropriate route(s) to deliver a message from its source to its destination. However, routing in a network where the edges among the mobile nodes depend on and vary in time is not a straightforward task. One needs to nd an eective route, both in time and space. All nodes along the path should consider the nodes’ movement pattern and the possible communication opportunities for message forwarding. Unfortunately, it is not always easy to determine future communication opportunities or even forecast the mobility patterns of the nodes in the network. Cerf et al. [26] characterizes contacts as: • Persistent: When they are always available, i.e. a Cable modem. • On-Demand: When they require an action to start, but after that they work as persistent contacts, for example, a dial-up connection. • Intermittent scheduled: When the parties involved agree to meet at a specic location for a determined period of time, i.e., low earth satellite communication window. • Intermittent opportunistic: Contacts that occur unexpectedly, for example, a car passing by in a non scheduled manner. • Intermittent predicted: When the contacts are not based on a schedule, but on predictions. A prediction is a contact that is likely to happen, based on the history or other kind of information. However, there are no guarantees predicted contacts will actually happen. For example, when people are commuting to work, it is probable that at the same time the same contacts are available, because people normally go at the same time and take the same routes. Forwarding and routing strategies may vary signicantly according to the type of contacts a node, or a network, is expected to encounter. In the case of a DTN with intermittent contact opportunities, the main priority is to maximize the probability of message delivery, and to minimize the end-to-end delay. For networks with more stable and consistent contact opportunities, it is important to discover an ecient path while trying to save as much as possible of the network resources. In a scenario with deterministic message routing and persistent, on-demand or intermittent but scheduled contacts, we may have a chance to achieve optimal performance of the network and manage eciently the available resources, i.e. spectrum and node energy. However, this is not frequently the case for mobile networks. Under unpredictable intermittent network conditions, where the mobility obscures present and future topology, nodes can only forward packets randomly based on the likelihood they will eventually arrive to their destination. Then, the problem of delivering messages to their nal destination is paramount and dominates that of resource utilization. In this case, ooding and epidemic message-forwarding are popular approaches. Between the two extremes, deterministic contacts and fully opportunistic ones, a broad range of strategies may be used to balance message delivery and resource optimization. Another issue to keep in mind is the duration and bandwidth of contacts. In a vehicular network, the number of contacts may be high, but the duration of each one can often be expected to last only seconds, especially between cars moving in opposite lanes. This signicantly limits the amount of information exchanged between nodes. In 2002 the Internet Research Task Force (IRTF) [63], started a new group called Delay-Tolerant Networking Research Group (DTNRG) [40]. The group was rst linked to the Interplanetary Internet Research Group 

Challenges and techniques 

 (IPNRG) , however, it soon became clear that the main characteristics of DTNs, i.e. non-interactive, asynchronous communication, would be useful in a broader range of situations. The main aim of DTNRG is to provide architectural and protocol solutions to enable interoperation among nodes in extreme and performance-challenged environments where the end-to-end connectivity may not exist. E.g. public safety, underwater, sensor and adhoc networks and extremely degraded connectivity, such as country side networks, to name a few. 3.3 Challenges and techniques The conditions of DTN operation lead to an architecture that challenges the traditional concepts of most of the network layers. In this section we present some of the major challenges faced by DTN protocols at dierent network layers. Standard network modeling techniques are also challenged and new ways to model nodes and connections should be created to evaluate the considered protocols. Therefore this section also discusses the dierent network modeling, trac modeling, transport layer issues, routing and data dissemination strategies.

Routing 

The challenges that DTNs need to overcome have lead the research to heavily focus on routing issues. Routing is considered to be the problem of choosing forwarding strategies that enable messages to pass from the source to the destination. The issues presented in this section pertain to most of the network layers and techniques developed for DTNs. For the case of VDTNs, store-and-forward, or store-carry-and-forward techniques are used [99]. This means that the nodes which receive a message, store it for some time, possibly carry it to another location, and afterwards forward it to other nodes. This is not new, in the Internet nodes also often momentarily buer packets as well. However, in this case, nodes try to decrease as much as possible these time intervals. On the other hand, in DTN the storing is used to overcome absence of end-to-end connectivity, and to enable waiting until ecient connections are present. In the store-and-forward mechanism each intermediate node is in charge of verifying the integrity of the message before forwarding it. In general, this technique helps us cope with intermittent connectivity, especially in the wilderness or environments requiring high mobility, and may be preferable in situations of long delays in transmission and variable or high error rates. Mundur and Seligman [79] identify mainly two classes of routing algorithms for DTNs. The rst class is based on epidemic routing, in which nodes use opportunistic contact to infect other nodes with the message to be delivered. For this group, the need of network knowledge is minimal. The routing algorithms have no control of node mobility and the forwarding process occurs in a fortuitous way. The second class of algorithms utilizes topology information and the algorithms may control node mobility. For Mundur and Seligman [79], this case is characterized by islands of well-connected nodes with intermittent connectivity with other nodes. 

Routing issues

 Fall and Jain, Fall and Patra [64] present an interesting list of routing issues for DTNs: • Routing objective: Although the main objective of a routing algorithm is message delivery and DTNs are, by denition, tolerant to delay, that does not mean we should not try to decrease the delay as much as possible. Algorithms should attempt to nd a good tradeo between decreasing the end-to-end delay and saving network resources. • Reliability: The protocols should be reliable and provide some form of mechanism to inform the nodes that their messages reached the destination. Acknowledged message delivery is an important enhancement of the oered set of services. • Security: In all types of networks, security is an important factor. However, in DTNs the packets may cross a diverse path to reach the destination and stay for a relatively long time at each intermediate node. The reliability and intentions of the often numerous intermediate nodes may not be always the best ones. Mechanisms to provide message authentication and privacy of the messages’ content are of supreme importance. • Resource allocation: Normally the main routing objectives of maximizing the message delivery ratio and minimizing resource allocation are conicting. The easiest way to guarantee the message delivery in the smallest amount of time is ooding the network with the message. However, this means a high use of network bandwidth, nodes memory and processing power. These may lead to other problems such as packet collisions, packet drops because of full message queues and surely the waste of the limited amount of energy of the nodes.