Routing Protocols for Vehicular Delay Tolerant Networks: A Survey

Abstract

Recently, the delay tolerant networks (DTN) have been utilized in various operational communication paradigms. This includes the communication scenarios that are subject to disruption and disconnection as well as the scenarios with high delay and frequent partitioning, that is, vehicular ad hoc networks (VANETs). Due to the several characteristics match, new research paradigm named as vehicular delay tolerant networks (VDTNs) is introduced. Through relays and store-carry-forward mechanisms, messages in VDTNs can be delivered to the destination without an end-to-end connection for delay-tolerant applications. However, the choice of routing algorithms in VDTNs is still under study. The main objective of routing protocols in VDTNs is to maximize the probability of delivery at the destination while minimizing the end-to-end delay. Until now, many routing protocols have been proposed to meet requirements of varying applications. In this paper, we, therefore, provide a detailed study of recently proposed routing schemes for VDTNs. We also perform comparative analysis on the basis of unique criterion such as forwarding metrics with their implementations. In addition, open challenges and future directions are provided to make room of interest for the research community.

1. Introduction

Over the past few years several vehicular network architectures have been proposed, such as vehicular ad hoc networks (VANETs), vehicle to vehicle (V2V) architectures, and vehicle to infrastructures (V2I) architectures [1]. VANETs are temporal networks which are self-organized by vehicles to route the packets. However, it is not easy to establish end-to-end path between source and destination by utilizing only V2V communication, because the communication range of vehicle is limited and movement of vehicle is very fast. Even if the communication between vehicles and infrastructures can be possible, network partition still exists where there is no infrastructure. Thus, most of the studies assume that the vehicles are always connected to the networks; thus they could not overcome the network partition problem [2].

There are various causes of network partition in vehicular networks. When node density is sparse, the network partition may occur. The other reason of network partition can be intensive number of nodes in small area. In addition, due to the data congestion, the network partition can also occur. In some cases the high mobility of vehicles can cause the network partition. Hence the successful establishment of an end-to-end path between a source and destination node is not guaranteed in vehicular networks [3].

On other hand, the DTN Research Group (DTNRG) lead by the Internet Research Task Force (IRTF) proposed an architecture with communication protocol named as bundle protocol. In DTNs, a message oriented overlay layer called bundle layer is added [4]. The bundle layer exists above the transport (or other) layers of the networks and provides interconnectivity between layers. Application data units are transformed by the bundle layer into one or more protocol data units called bundles, which are forwarded by DTN nodes according to the bundle protocol. The idea is to bundle together all the information required for a transaction, minimizing the number of round-trip exchanges, which is useful when the round-trip time is very large. To help routing and scheduling decisions, the bundles follow store-carry-forward mechanisms. In delay tolerant networks (DTNs), it is common that there is no end-to-end path between source and destination. The DTNs are defined as those networks which embrace the concept of occasionally connected networks that may suffer from frequent partitions. In a real environment the vehicles are distributed over a wide area and move randomly, and the network is easily partitioned. These characteristics of vehicular networks are similar to DTNs. Hence, vehicular networks can be treated as DTNs and defined as vehicular delay tolerant networks (VDTNs) [5, 6].

Generally, the bundle protocol of DTN does not provide details of routes for data packets between the nodes. It deals only with the forwarding phase. Since, enabling end-to-end connectivity in vehicular networks is a significant issue and needs to be addressed by appropriate routing approaches, therefore, a number of studies have been carried out for applicable routing protocols based on different schemes, such as model-based schemes, epidemic schemes, and estimation schemes [7]. A very simple protocol is direct delivery, in which the node originating a message carries it until it meets its final destination. In first contact routing, the nodes forward messages to the first node they encounter, which results in a random walk search for the destination node. Epidemic routing [8] replicates messages to all encountered peers that still do not have them. If message storage space is unlimited and contacts between nodes are long enough, epidemic routing minimizes the delivery delay and maximizes the delivery ratio. However, those resources are usually limited, epidemic wastes storage and bandwidth in comparison with other protocols. For instance, surround routing [9] tries to minimize the storage consumption and overhead by also sending messages to all the nodes, but only the nodes that surround the final recipient will keep the copies longer than others. Spray-and-wait [10] generates n copies of a message. In normal mode, a node gives one copy to each contact; in binary mode, half of the copies are forwarded to a contact. Once only a single copy is left, it is forwarded only to the final recipient. Spray-and-wait is another example of protocol that limits message replication as compared with epidemic routing. The PRoPHET (probabilistic routing protocol using history of encounters and transitivity) [11] protocol transfers the message to a neighbor if it estimates that the neighbor has a higher likelihood of being able to deliver the message to the final destination based on past node encounter history. Similarly, MORA (multiobjective robotic assistance) [12] learns from the structure of the node movement patterns and uses this information to improve the message routing. Moreover, to further increase the delivery ratio, MORA introduces autonomous agents that adapt their movement based on the variations in network capacity and demand. Conclusively we can say that some schemes try to choose paths through denser areas, which may cause congestion. Others store data in fixed relay nodes until a vehicle going to an adequate destination passes by, which may take some time. Additionally more researches try to forward the data along the direction to the destination, which may also take some time. Finally, some schemes combine trajectory information and traffic statistics to find the best path, which may be complex. Table 1 summarizes the properties of the traditional routing protocols representing VDTNs.

Table 1

Summary of VDTN routing protocols.

Scheme name	Number of message copies	Type	Message replication	Target
Direct delivery	Single	Direct	None	Node moves and delivers the packet directly
First contact	Single	Probabilistic	Low	Packet is delivered in result of random walk search to its destination
Epidemic routing	Multiple	Blind flooding	High	Enormous data propagation
Surround routing	Multiple	Limited flooding	Moderate	Packets only flooded to the nodes near to the destination
Spray-and-wait	Multiple	Controlled flooding	Moderate	Limited copies of packet are generated
PRoPHET	Multiple	Probabilistic	Moderate	Packet forwarded on the basis of encounter history

Mostly, the VDTNs are characterized by generally short contacts between nodes and a highly dynamic network topology, where routing is a particularly a challenging problem [13]. Mostly routing protocols that need to exchange control information during contacts to update routing tables or other information databases have less time to transfer data bundles. For example, PRoPHET requires some overhead for maintaining the estimates of meeting probabilities. On the other hand, routing protocols that do not maintain such control information generally have to create more bundle copies to achieve the same delivery performance. This represents an efficiency compromise, as more copies spend more storage and transmission resources, contributing to congestion. As the network topology is highly dynamic, nodes have to take into account that any information maintained may be outdated soon. Moreover, applying store-carry-forward approach directly to vehicular networks may cause a lot of packets replications which may lead to data congestion especially when vehicles are dense [14]. So, there is also a compromise between the value of information exchanged and the cost of keeping it updated. There are other research challenges related to routing such as the optimal placement of relay nodes, traffic differentiation, and congestion control [15]. It is worth mentioning that the performance of most of the introduced routing protocols highly depends on the level of cooperation and autonomy of the nodes. By default, most of the protocols assume full node cooperation and little attention have been devoted to study the effect of reduced levels of cooperation. In fact, by applying and fine-tuning simple knowledge-based cooperation mechanisms, the routing performance can be considerably improved [16].

In addition, it is not the only purpose of routing protocol to overcome the network partition problem. There are a lot of important issues to design routing protocols, such as data delivery rates, data transfer time between source and destination, energy efficiency, bandwidth consumption [17]. The application is also important because there is no routing protocol that can satisfy all these issues. Thus most of proposed routing protocols are designed for specific applications [18]. However, these protocols are not suitable for applications having packets with different importance and requirements. In order to deal with this issue, some researchers provided adaptive routing protocols with different metrics [19].

Hence, we conclude that vehicular DTNs have been investigated for different applications with a large number of proposed routing algorithms.

1.1. Motivation

From the literature, we can easily find out some quality survey papers in various areas of VANETs [20]. However, the focus of those surveys is mostly built around routing issues in VANETs without taking DTN characteristics into account. Later, some authors in [21] took the initiative to provide the performance of VDTNs routing protocols. However, any comparative analysis has not been performed. Hence, the current literature still lacks in thorough studies providing more insight on the routing issues in vehicular DTNs. In this paper, we, therefore, provide a comprehensive review of vehicular delay tolerant networks (VDTNs) routing protocols. Furthermore, we also perform a comparative analysis of selected protocols while defining some metrics such as forwarding metrics, infrastructure-assisted, location-information, topology assumptions, implementation, and main objectives. Moreover, we summarize the future research directions in this demanding paradigm.

The rest of this paper is organized as follows. In Section 2, we present the detail of selected DTN routing schemes proposed for VANETs. Section 3 provides the comparative analysis of vehicular DTN protocols. Open issues and future directions are given in Section 4. Finally, Section 5 concludes this paper.

2. VDTN Routing Protocols

As mentioned before, the routing protocols in VANETs aim to establish end-to-end connectivity between network nodes, which is quite different from the case of the delay tolerant environment. Thus, routing protocols in VDTNs use the store-carry-forward paradigm of DTNs to deliver data. This paradigm is based on the premise that the end-to-end network path may exist over time. However, the bundle protocol, which is the base of DTN, does not address routing problems without any establishment of routes between nodes. For that purpose, several projects are working for VDTN research independently from VANETs and we, therefore, categorize proposed forwarding mechanisms for VDTNs as shown in Figure 1. The VDTN stack consists of flooding, random/probabilistic, infrastructure/incentive-based, and information-based forwarding. Due to the promising and reliable performance of V2I architecture, we will focus on infrastructure and information-based routing protocols in the following section.

Figure 1

Classification in VDTN forwarding.

2.1. MaxProp (Maximum Priority)

MaxProp is a routing protocol designed for vehicular DTNs. The MaxProp protocol is based on a store-carry-forward mechanism which is usually utilized in a DTN environment. However, the authors in [22] proposed an algorithm which enables the nodes to assign the priority to the packets. On the basis of the given priorities, each node can decide either to transmit or drop the packet. In VDTNs, the transmission duration and opportunities for each node are limited, since the nodes move fast in sparse areas. Moreover, the buffer of node is also limited in a real environment. Therefore, to decide the priority of packets in a buffer of nodes is important when performing efficient routing.

In MaxProp, when two nodes communicate, they exchange packets in a specific order. If the node currently in contact is the destination node of some packets, these packets are transmitted first. Secondly, the routing information is exchanged which includes the estimated probability of meeting any node. The calculation of the probability is based on the number of encounters between two nodes. In the end, an acknowledgement of delivered data is transmitted.

In addition, MaxProp also introduced a mechanism to handle old data within the network. In MaxProp, each packet stores a hop list of nodes that the packet already traversed. This hop list enables each node to identify the age of packets. The packets with lower hop list values are considered new packets and thus higher priority is assigned to them as shown in Figure 2. In case of any node encounter, the packets with the highest priority are transmitted first and the remaining packets are transmitted later. On the other hand, the packets which have the lowest priority (i.e., higher hop list count) will be deleted first in case a buffer is full.

Figure 2

The priority of packet in MaxProp.

2.2. PBRS (Probabilistic Bundle Relaying Scheme)

The road-side units (RSUs) support communications between vehicles and infrastructures for numerous applications. However, in real environments, RSUs cannot cover all the roadside areas because of the deployment cost. Thus, communications over relaying vehicles are considered one of the solutions to support the uncovered areas by RSUs. Some typical researches utilized store-and-forward techniques for relaying data between RSUs and vehicles. The RSU transmits its data to the incoming vehicles which enter its transmission range. In this case, if an RSU transmits its data to all the vehicles which are passing by it, a lot of replicated packets are generated in the network. Therefore, PBRS [23] proposed a decision-based scheme which makes RSUs determine whether or not to release its data to a vehicle on the basis of certain criterion. Figure 3 shows the vehicular delay tolerant network which is considered in PBRS. The source RSU S has data to forward to the destination RSU D. However, there is no end-to-end path between S and D. The Vehicles passing by S makes S become aware of the speed of those vehicles. PBSR calculates the release probability by utilizing the speed of vehicles. When a vehicle $V_i$ enters a communication range of S, the S holds its data until the vehicle moves out of the range or a next vehicle $V_{i+\mathrm{1}}$ enters the coverage area. If the $V_{i+\mathrm{1}}$ is faster than $V_i$ and $V_{i+\mathrm{1}}$ is considered to reach D before the $V_i$ does, S transmits its data to $V_{i+\mathrm{1}}$ .

Figure 3

VDTN in PBRS.

2.3. ASCF (Adaptive Carry-Store-Forward)

ACSF also assumes that RSUs cannot cover all the roadside areas like PBRS. ACSF utilized a store-and-forward technique for relaying data. However, it focused on the outage time of a target vehicle in an uncovered area. In the ACSF scheme, a message forwarding mechanism was proposed for reducing the outage time for vehicles [24].

Figure 4 shows the deployment of vehicles and RSUs considered in ACSF. The authors implemented ACSF for two RSUs partially deployed and leaving uncovered area between them. Here, the uncovered area means the road segment which is not in the transmission range of any RSU(s). In Figure 4, it is shown that the vehicles move from left to right side of the road. After the entrance of $V_{\mathrm{0}}$ in the covered area of ${\text{RSU}}_{\mathrm{1}}$ , it starts communicating data with ${\text{RSU}}_{\mathrm{1}}$ . Since $V_{\mathrm{0}}$ is moving, after some time it will be entering into the uncovered area. However, the vehicles $V_j$ and $V_k$ can still be used as a relay to receive the remaining data from ${\text{RSU}}_{\mathrm{1}}$ and forward it to $V_{\mathrm{0}}$ . For this purpose, ${\text{RSU}}_{\mathrm{1}}$ selects the node which provides longer connectivity to $V_{\mathrm{0}}$ , thus decreasing the outage time. The outage time can be calculated by the moving speed of each node. Since RSU can be easily aware of its transmission range and the moving speed of nodes moving in it, RSU can calculate when $V_{\mathrm{0}}$ moves out of its communication range. Before node $V_0$ leaves the coverage area, ${\text{RSU}}_{\mathrm{1}}$ selects the relay node with a maximum connectivity time with $V_{\mathrm{0}}$ . ACSF assumes that $V_{\mathrm{0}}$ is required to adjust its speed in an uncovered area for a longer connection with a relaying vehicle selected by ${\text{RSU}}_{\mathrm{1}}$ .

Figure 4

Communication in ASCF.

2.4. FFRDV (Fastest-Ferry Routing in DTN-Enabled VANET)

FFRDV is a protocol which was proposed for sparse ad hoc networks to support a highway road environment where vehicles are moving with high speeds and few traffic lights [25]. In FFRDV, the roads are divided into logical blocks based on geographic information. Each vehicle can get its current location by GPS and it shares its location and speed with other vehicles in the same block by hello messages. When an emergent event occurs, FFRDV selects message ferries which have the responsibility of relaying data according to velocity based strategy.

First, the vehicle which senses an event becomes an initial ferry. It selects the fastest vehicle within its block as a next ferry. Second, if the ferry enters a new block Bi, it broadcasts a hello message to find a new ferry. Any nodes, which are able to receive a new data, send a response message, including their current speed. The ferry node compares the speeds and finds the fastest vehicle $V_k$ . If $V_k$ is faster than it, it sends the data to $V_k$ or it holds the data. This mechanism is performed repeatedly block by block.

2.5. DARCC (Distance-Aware Routing with Copy Control)

The routing decision aims to determine how to replicate or forward message copies to the suitable nodes. DARCC applies this concept of DTN routing to vehicular environments [26]. The vehicles in DARCC determine whether to transmit data or not to their encountering vehicles with 2 principles. If the location of the destination of data is available, the data is forwarded to the vehicle that is closer to the destination. Otherwise, DARCC prefers spreading the data to different direction to increase the probability to meet destination.

Figure 5 shows the concept of DARCC, where each vehicle in DARCC is equipped with a GPS, thus the vehicle can calculate its current motion vector. The motion vector is the speed of vehicle and its moving direction. The vehicle A turns left in junction during certain time t, then its motion vector of time t is calculated like arrow in the Figure 5. Each vehicle periodically broadcasts a beacon message including its location, current motion vector, and the list of the messages it has. If the vehicles are moving in different directions, the replication helps to perform the successful delivery, because the other vehicles may reach its destination on its way before the source. Thus, the vehicles A and B replicate their packets to each other, respectively.

Figure 5

Concept of DARCC.

2.6. DAWN (Density Adaptive Routing with Node Awareness)

The authors of DAWN in [27] assume an urban sensing applications. As shown in Figure 5, there are N fixed sensor in roadside, and one base station for data gathering. The sensors are regularly deployed and the base station is located at the center of the network area. The data packets are generated at the sensors, and each packet includes its origin location and generation time. The vehicles and mobile nodes are more like travelling in the random cells. When the vehicles moves into new cell they collect the data packet from sensors and store it in its buffer. If two vehicles meet, they replicate their packets to each other.

The data forward strategy in DAWN is decided by the density of the cell. If density is low the forward strategy is the same as epidemic, that is, a node replicates all the data it has to encounter nodes. On the other hands, if the density of cell increases, the throughput is restricted by congestion due to the limitation of wireless channel capacity. Therefore, in DAWN the UIV (utility incremental value) is proposed to give priorities to the packets. The packets with higher UIVs should be transmitted with higher priority (Figure 6). The UIV is estimated by each node to maximize the probability of packets to be delivered to the base station before deadline.

Figure 6

Network model in DAWN.

2.7. GeOpps (Geographical Opportunistic Routing)

Geographic routing is one of the most promising approaches for efficient routing, which takes location information of the vehicle into account. Geographical opportunistic routing for vehicular networks (GeOpps) aims to enhance the performance of single-copy routing protocol in VDTNs [28]. It exploits the geolocation of vehicles to forward the geographical bundle opportunistically towards the final destination location. Thus, the vehicle that is heading towards or near the destination location of the bundle becomes the next bundle carrier. The closest point where a vehicle carries the bundle is called nearest point and used to compute minimum estimated time of delivery (METD) as follows:

$$\begin{array}{cc}& \text{METD}=\text{time}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{to}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{nearest}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{point}+\frac{\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{remaining}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{distance}\mathrm{\hspace{0.17em}\hspace{0.17em}}}{\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{average}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{speed}\mathrm{\hspace{0.17em}\hspace{0.17em}}}.\end{array}$$

(1)

A vehicle with the lowest METD is the candidate bundle forwarder/carrier. GeOpps assumes that the bundle carrier always find another vehicle when it arrives at the nearest point. In some cases, it might be practical to handover bundle(s) to the vehicle moving slowly to a destination rather than the vehicle that will just reach the nearest point faster. To achieve this, GeOpps assigns weights according to varying speed of vehicles and their remaining distances to the nearest points. However, it does not provide a method to optimally calculate these weights.

2.8. GeoSpray (Geographical Spray in VDTN)

GeoSpray [29] uses the principles of single-copy single-path GeOpps to perform multicopy multipath bundle routing approach. Multicopy routing schemes are noted for their high delivery ratios, low bundle delivery delays, and high overheads due to duplicated copies. Thus, GeoSpray adopts the replication approach of the spray-and-wait protocol [7] to limit the number of copies. Initially, it uses a multiple copy scheme, which spreads a limited copies of the bundle to exploit diverse paths. Afterwards, it switches to a single-copy forwarding scheme. GeoSpray clears the delivered bundles from vehicles’ storage by propagating the delivery information. As a result, it achieves better delivery ratio than GeOpps at the cost of high replication overhead. However, this overhead is less than the epidemic protocol and similar to spray-and-wait.

3. Comparative Analysis

In this section, the comparative analysis of the previously discussed VDTN routing protocols is presented. We compare and analyze the above mentioned schemes based on the following metrics.

3.1. Forwarding Metric

Most of VDTN routing protocols utilize the store-carry-forward mechanism. Hence, these protocols usually do not make any end-to-end path between source and destination vehicles. In epidemic routing which is one of the most famous store-carry-forward routing, the vehicles replicate all the data they have to all vehicles they encounter. However, in above mentioned schemes, the vehicles which have data should determine whether or not to forward data to encountering nodes with some criteria. Therefore, we define these criteria as forwarding metrics in VDTNs. The forwarding metric is one of the most significant features for distinguishing routing protocols.

3.2. Infrastructure Assisted

As mentioned in Section 1, the infrastructures such as RSUs have been installed to support the vehicle-to-vehicle (V2V) communications for increasing reliability, reducing transmission delay, and so forth. Therefore, some VDTN routing protocols assumed that the infrastructures can support the V2V communication in a whole roadside area, thus improving routing performances. However, this assumption is impractical since the installation of infrastructures costs so much. In the real world, the infrastructures are installed in limited roadside areas and they can support the V2V communications within their coverage (the localization of the RSUs is still a part of research but out of scope in this paper). Therefore, some VDTN routing protocols such as [22, 25, 27] are designed to be well-operated without any support of the infrastructures. Moreover, some VDTN routing protocols assumed that the support of infrastructures can be provided in the limited area. Since the routing performance depends on the existence of infrastructure, it is an important metric when analyzing VDTN routing protocols.

3.3. Location Information

In most of the routing protocols, including VDTN routing protocols, the packet should be forwarded from the source node to the direction of the destination node. Therefore, if the source node can distinguish whether the encounter node is near to the destination node or not, it can perform the routing efficiently.

Nowadays, since a lot of vehicles include equipped GPS devices, the various VDTN routing protocols which use the GPS-based location information are proposed. However, if the source node does not know the location of the destination node, the source node cannot calculate the distance between an encounter vehicle and the destination node based on the location information. Hence, some VDTN routing protocols which does not require GPS location information are proposed [22]. Moreover, in some VDTN routing protocols, not only the GPS information but also map information are used to determine optimal next forwarder. Therefore, the location information is considered as a promising metric to classify VDTN routing protocols.

3.4. Topology Assumptions

In Section 3.2, we also described that assumption about existences of infrastructures is an important metric for analyzing VDTN metric. In fact, besides the existence of infrastructures, various VDTN routing protocols also have their assumptions such as network models, mobility model, and traffic characteristics. In particular, topology assumptions such as location of encounter vehicles is one of the most important assumptions since various routing performances such as routing overhead or coverage of the proposed schemes highly depend on the assumptions. In addition, although some VDTN routing protocols can achieve high performance improvement over the particular topologies, it cannot achieve the performance improvement over another topologies. Hence, even though the topology assumptions are not costly, they are still important metrics for analyzing the VDTN routing protocols.

3.5. Implementation

As mentioned in the previous sections, VDTN routing protocols have own assumptions such as infrastructure existence, location information, and topology assumptions, and some assumptions are impractical in real-world. Hence, even if some VDTN routing protocols can improve routing performance academically, it cannot achieve the improvement in real-world. Hence, performance measurement methods of each proposed routing protocol such as test-bed based measurement, numerical analysis, and simulation based analysis is one way to verify the practicality of the proposed VDTN routing protocols. Hence, we classify the VDTN routing protocols according to the implementation.

3.6. Target

In common VDTN routing protocols, when the source node meets another node (viz. encounter node), it should determine whether or not to transmit its packet to the encounter node. At this point of time, the source node calculates a “cost” based on forwarding metric which is described in Section 3.1. The source node transmits its packet if the cost of encounter node is low. Hence, the forwarding metric can represent the target of routing protocol, but it is not at all times. For example, when the source node wants to transmit its packet to the destination as soon as possible, the speed of encounter vehicle can be used as the forwarding metric. In addition, even if the source node wants to maintain connectivity with the selected encounter vehicle, the speed of encounter vehicle also can be used as the forwarding metric. Therefore, not only the forwarding metric but also the target of protocols is an important metric to analyze VDTN routing protocols.

Table 2 shows the comparative analysis of the VDTN protocols discussed in this survey. In PBRS, a velocity of node is utilized to calculate the release probability. If several nodes are in the communication range of RSU, the node with higher speed tends to reach destination faster than slower speed node. For this reason, faster nodes get higher release probability in PBSR. Thus, we call this forwarding metric velocity-based probability in the table. Similarly, in ACSF [24], the maximum hop counts are two between the source and destination. The only RSUs are the only source nodes in this scheme. Due to the limitation of communication range, the connectivity between an RSU and a vehicle cannot be maintained. In order to overcome this problem, a relaying vehicle is selected. When multiple vehicles are available for relaying, the one which can maximize the connectivity is selected. The velocity of relaying vehicle and target vehicle is important factor to keep the connectivity. Unlike PBRS, the fastest node is not important in ACSF, because it is easy to maintain the connection if the speeds of the two nodes are similar.

Table 2

Comparative analysis of VDTN routing schemes.

Scheme name	Forwarding metrics	Infrastructure assisted	Location information	Topology assumption	Implementation	Target
MaxProp [22]	Hop count historical data	No	No	30 Buses in 1502 miles; 60 days of trace	Real environment (UMass DieselNet)	Gives priority to packets in buffer
PBRS [23]	Velocity-based probability	Yes	Yes	20 km one way road vehicle; interarrival time: 5–120 seconds	Java-based simulator	Reduce packet replication
ACSF [24]	Minimum outage time of node	Yes	Yes	Not available	Numerical analysis	Maximum connectivity
FFRDV [25]	Velocity of node	No	Yes	1500 m × 1500 m area; average speed of node 60 km/h	Network Simulator 2	Minimize intermittent nodes
DARCC [26]	Location of destination moving direction of nodes	Yes	Yes	100 vehicles in 3000 m × 3000 m area; each road has 4 lanes; average speed of node 60 km/h	Opportunistic Network Environment (One) simulator	Reduce packet replication
DAWN [27]	Density of nodes	No	Yes	5000 taxi in Beijing city 30 days of trace 25 × 25 Manhattan grid	Simulation with real environment data	Optimize channel usage
GeOpps [28]	Density of nodes	Yes	Yes	260,000 vehicles 15 km × 15 km area	OMNet++	Optimize delivery ratio, delay, and overhead
GeoSpray [29]	Density of nodes and different data size	Yes	Yes	100 mobile nodes with an average speed of 50 km/h city of Helsinki, time: 6 hrs	VDTNsim	Optimized routing with minimum delay

DARCC [26] and DAWN [27] utilize packet replication mechanism like epidemic routing. Packet replication is a useful technique to increase delivery ratio in DTNs, but it may result in a waste of network resources. Thus, to control the amount of replicated packets appropriately is a significant issue in these protocols. First, DARCC assumes two situations. If the location of the destination is available, the data is forwarded to the vehicle that is closer to the destination. The data is forwarded to the node which is moving in different direction to spread the data over a wide area with a small number of replicated packets. On the other hand, DAWN focuses on the density of nodes in the cell. If the density increases, the congestion also increases. DAWN reduces packet replication only if the channel is congested. It tries to maximize the local channel capacity if the throughput does not fall due to the congestion.

Performance evaluation of the given schemes also varies. Some of them such as MaxProp and DAWN were tested in real test bed environments. In MaxProp, the authors utilized 30 buses to cover a wide area of 150 square miles in their test bed. Furthermore, the MaxProp had a realistic assumption that the nodes had no network global information (global information here includes location of other nodes). In addition, there was a limited infrastructure support assumed for QoS. Similarly, DAWN consisted of a database, based on a real environment for its test bed with 30 days GPS records of 27848 taxis in Beijing city for simulations. However, the remaining schemes were simulated using the Network Simulator 2 (NS-2). Also, the Opportunistic Network Environment (ONE) simulator was considered for the performance evaluation of the VDTNs routing protocols.

4. Open Issues and Future Directions

In this section, we describe open issues and challenges for VDTN routing protocols. The need to address the emerging number of services in the vehicles has given rise to an increase in research in vehicular communication. The key challenge is routing due to the dynamic topology changes. Many protocols have been discussed in the previous sections. However, there still exist some challenges and open issues that need to be investigated.

• (i)

  Most of routing protocols assume either the highway scenario or the urban scenarios. The protocol which is designed for such environments may not show efficient performance in a more complex environment. For example, the vehicles may enter the urban area after passing highway. Therefore, variety environments should be taken into account at the same time.

• (ii)

  In most studies for VDTNs, the buffer management of vehicles is overlooked. Only the size of buffer is described, but how it can be managed is not described. The buffer management is important in DTN, because a lot of DTN protocols are based on store-carry-forward mechanism. Therefore, reallocating buffer space and maximum use of other resources can also be addressed.

• (iii)

  Most of the routing protocols utilize the location information of nodes. The location information acquisition is not easy when the destination node is mobile. For the stationary node, every node is aware of the nodes location. Hence, location information can be an efficient metric for routing. Another issue is the implementation of the routing protocols in the real world scenarios. Better performance can be predicted from the protocols applied in the real world scenarios.

• (iv)

  There always exists a tradeoff between delivery ratio, end-to-end delay, and network resource usage while applying different approaches in the vehicular networks. Thus, a completely different algorithm with existing methods can be expected to minimize the tradeoff through, for example, artificial intelligence-aware routing.

• (v)

  In addition, a few researchers have focused on integrating the new promising paradigm, that is, information centric networking (ICN) into VANETs [30]. Recently, content centric networking (CCN) has been proposed for the future internet. Since CCN is at its early stage, many issues are still unidentified and open. Therefore, the feasibility of applying the CCN concept to vehicular communications (named as vehicular CCN, that is, VCCN) needs to be investigated. In addition, a number of challenges still require attention in VCCN, such as naming, name resolution, routing, content storing, management and policy of forwarding information base and pending interest table management, security, and trust issues.

• (vi)

  The content routing is one of the actively researched parts of VCCN [31]. Request and response forwarding between consumer and provider nodes is the responsibility of the routing scheme. The simplest routing scheme which has been used in the CCN is the breads-crumb technique. However, we need efficient routing schemes to fulfill requests effectively and efficiently for the purpose of achieving QoS in dynamic topologies such as VANETs.

5. Conclusion

In this paper, we have performed a detailed survey of recent developments in vehicular DTNs with more emphasis on routing. To the best of our knowledge, this is the first work to present the comparative analysis of selected vehicular DTN (VDTNs) routing protocols with respect to unique metrics such as implementation, infrastructure assisted or not, and more. In addition, we provide a list of open challenges and future directions. Finally with this paper, we aim to motivate further research interest for existing routing constraints in VDTNs.