Hindawi Publishing Corporation International Journal of Distributed Sensor Networks Article ID 325027 Review Article Routing Protocols for Vehicular Delay Tolerant Networks: A Survey Hyunwoo Kang,1 Syed Hassan Ahmed,2 Dongkyun Kim,2 and Yun-Su Chung1 1 2 . Electronics and Telecommunication Research Institute (ETRI), Daegu 711-883, Republic of Korea School of Computer Science & Engineering, Kyungpook National University, Daegu 702-701, Republic of Korea Correspondence should be addressed to Dongkyun Kim; dongkyun@knu.ac.kr Received 7 September 2014; Revised 30 October 2014; Accepted 5 November 2014; Published 26 November 2014 Academic Editor: Álvaro Marco Copyright © Hyunwoo Kang et al. his is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Recently, the delay tolerant networks (DTN) have been utilized in various operational communication paradigms. his 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. hrough 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. he 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 endto-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. hus, most of the studies assume that the vehicles are always connected to the networks; thus they could not overcome the network partition problem [2]. here are various causes of network partition in vehicular networks. When node density is sparse, the network partition may occur. he 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]. he 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. he 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 2 and scheduling decisions, the bundles follow store-carryforward mechanisms. In delay tolerant networks (DTNs), it is common that there is no end-to-end path between source and destination. he DTNs are deined as those networks which embrace the concept of occasionally connected networks that may sufer from frequent partitions. In a real environment the vehicles are distributed over a wide area and move randomly, and the network is easily partitioned. hese characteristics of vehicular networks are similar to DTNs. Hence, vehicular networks can be treated as DTNs and deined 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 signiicant 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 diferent 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 inal destination. In irst contact routing, the nodes forward messages to the irst 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 inal recipient will keep the copies longer than others. Spray-and-wait [10] generates � 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 let, it is forwarded only to the inal recipient. Spray-and-wait is another example of protocol that limits message replication as compared with epidemic routing. he 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 inal 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 ixed 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 traic statistics to ind the best path, which may be International Journal of Distributed Sensor Networks complex. Table 1 summarizes the properties of the traditional routing protocols representing VDTNs. 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. his represents an eiciency 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. here are other research challenges related to routing such as the optimal placement of relay nodes, traic diferentiation, 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 efect of reduced levels of cooperation. In fact, by applying and inetuning 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. here are a lot of important issues to design routing protocols, such as data delivery rates, data transfer time between source and destination, energy eiciency, bandwidth consumption [17]. he application is also important because there is no routing protocol that can satisfy all these issues. hus most of proposed routing protocols are designed for speciic applications [18]. However, these protocols are not suitable for applications having packets with diferent importance and requirements. In order to deal with this issue, some researchers provided adaptive routing protocols with diferent metrics [19]. Hence, we conclude that vehicular DTNs have been investigated for diferent applications with a large number of proposed routing algorithms. 1.1. Motivation. From the literature, we can easily ind 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 International Journal of Distributed Sensor Networks 3 Table 1: Summary of VDTN routing protocols. Scheme name Number of message copies Type Message replication Target Direct delivery Single Direct None First contact Single Probabilistic Low Epidemic routing Multiple Blind looding High Surround routing Multiple Limited looding Moderate Spray-and-wait PRoPHET Multiple Multiple Controlled looding Probabilistic Moderate Moderate Node moves and delivers the packet directly Packet is delivered in result of random walk search to its destination Enormous data propagation Packets only looded to the nodes near to the destination Limited copies of packet are generated Packet forwarded on the basis of encounter history 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 deining some metrics such as forwarding metrics, infrastructure-assisted, locationinformation, topology assumptions, implementation, and main objectives. Moreover, we summarize the future research directions in this demanding paradigm. he 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 diferent from the case of the delay tolerant environment. hus, routing protocols in VDTNs use the store-carry-forward paradigm of DTNs to deliver data. his paradigm is based on the premise that the endto-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. he VDTN stack consists of looding, random/probabilistic, infrastructure/incentivebased, 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. 2.1. MaxProp (Maximum Priority). MaxProp is a routing protocol designed for vehicular DTNs. he 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 VDTN forwarding Flooding Random/ probabilistic Navigation - Moving vector - Geolocation - Moving direction Information based Infrastructure based Incentive based Network resources Social network - Optimization - Various traic - Congestion - Similarity - Social graph - Friendship Figure 1: Classiication in VDTN forwarding. areas. Moreover, the bufer of node is also limited in a real environment. herefore, to decide the priority of packets in a bufer of nodes is important when performing eicient routing. In MaxProp, when two nodes communicate, they exchange packets in a speciic order. If the node currently in contact is the destination node of some packets, these packets are transmitted irst. Secondly, the routing information is exchanged which includes the estimated probability of meeting any node. he 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. his hop list enables each node to identify the age of packets. he 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 irst 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 irst in case a bufer is full. 2.2. PBRS (Probabilistic Bundle Relaying Scheme). he roadside units (RSUs) support communications between vehicles 4 International Journal of Distributed Sensor Networks Packets toward the encounter node High priority: transmit irst Routing information based on historical data V0 Acknowledgements of delivered data Vk Vj Packets with short hop list Low priority: delete irst Other packets Figure 2: he priority of packet in MaxProp. Source RSU Coverage area Destination RSU Uncovered area Coverage area Figure 3: VDTN in PBRS. and infrastructures for numerous applications. However, in real environments, RSUs cannot cover all the roadside areas because of the deployment cost. hus, 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. he 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. herefore, PBRS [23] proposed a decisionbased 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. he source RSU � has data to forward to the destination RSU �. However, there is no end-to-end path between � and �. he Vehicles passing by � makes � become aware of the speed of those vehicles. PBSR calculates the release probability by utilizing the speed of vehicles. When a vehicle �� enters a communication range of �, the � holds its data until the vehicle moves out of the range or a next vehicle ��+1 enters the coverage area. If the ��+1 is faster than �� and ��+1 is considered to reach � before the �� does, � transmits its data to ��+1 . 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 Uncovered area by RSU RSU1 RSU2 Figure 4: Communication in ASCF. 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. he 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 let to right side of the road. Ater the entrance of �0 in the covered area of RSU1 , it starts communicating data with RSU1 . Since �0 is moving, ater some time it will be entering into the uncovered area. However, the vehicles �� and �� can still be used as a relay to receive the remaining data from RSU1 and forward it to �0 . For this purpose, RSU1 selects the node which provides longer connectivity to �0 , thus decreasing the outage time. he 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 �0 moves out of its communication range. Before node �0 leaves the coverage area, RSU1 selects the relay node with a maximum connectivity time with �0 . ACSF assumes that �0 is required to adjust its speed in an uncovered area for a longer connection with a relaying vehicle selected by RSU1 . 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 traic 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 ind a new ferry. Any nodes, which are able to receive a new data, send a response message, including their current speed. he ferry node compares the speeds and inds the fastest vehicle �� . If �� is faster than it, it sends the International Journal of Distributed Sensor Networks 5 The motion vector of vehicle A Vehicle A Vehicle B Vehicle C Figure 5: Concept of DARCC. data to �� or it holds the data. his mechanism is performed repeatedly block by block. 2.5. DARCC (Distance-Aware Routing with Copy Control). he 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]. he 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 diferent 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. he motion vector is the speed of vehicle and its moving direction. he vehicle � turns let in junction during certain time �, then its motion vector of time � 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 diferent directions, the replication helps to perform the successful delivery, because the other vehicles may reach its destination on its way before the source. hus, the vehicles � and � replicate their packets to each other, respectively. 2.6. DAWN (Density Adaptive Routing with Node Awareness). he authors of DAWN in [27] assume an urban sensing applications. As shown in Figure 5, there are � ixed sensor in roadside, and one base station for data gathering. he sensors are regularly deployed and the base station is located at the center of the network area. he data packets are generated at the sensors, and each packet includes its origin location and generation time. he 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 bufer. If two vehicles meet, they replicate their packets to each other. he 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 Sensors Base station Mobile nodes Figure 6: Network model in DAWN. 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. herefore, in DAWN the UIV (utility incremental value) is proposed to give priorities to the packets. he packets with higher UIVs should be transmitted with higher priority (Figure 6). he UIV is estimated by each node to maximize the probability of packets to be delivered to the base station before deadline. 2.7. GeOpps (Geographical Opportunistic Routing). Geographic routing is one of the most promising approaches for eicient 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 inal destination location. hus, the vehicle that is heading towards or near the destination location of the bundle becomes the next bundle carrier. he closest point where a vehicle carries the bundle is called nearest point and used to compute minimum estimated time of delivery (METD) as follows: METD = time to nearest point + remaining distance average speed (1) A vehicle with the lowest METD is the candidate bundle forwarder/carrier. GeOpps assumes that the bundle carrier 6 always ind 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. hus, 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. Aterwards, 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. International Journal of Distributed Sensor Networks 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. herefore, if the source node can distinguish whether the encounter node is near to the destination node or not, it can perform the routing eiciently. 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. herefore, the location information is considered as a promising metric to classify VDTN routing protocols. 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. herefore, we deine these criteria as forwarding metrics in VDTNs. he forwarding metric is one of the most signiicant features for distinguishing 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 traic 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.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. herefore, 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). herefore, some VDTN 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. International Journal of Distributed Sensor Networks 7 Table 2: Comparative analysis of VDTN routing schemes. Scheme name MaxProp [22] Forwarding metrics Infrastructure Location assisted information Topology assumption Implementation 2 30 Buses in 150 miles; 60 days Real environment of trace (UMass DieselNet) 20 km one way road vehicle; Java-based interarrival time: 5–120 simulator seconds Target Gives priority to packets in bufer Hop count historical data No No Velocity-based probability Yes Yes Minimum outage time of node Yes Yes Velocity of node No Yes DARCC [26] Location of destination moving direction of nodes Yes Yes DAWN [27] Density of nodes No Yes 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 diferent 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 PBRS [23] ACSF [24] FFRDV [25] Not available Numerical analysis 1500 m × 1500 m area; average Network Simulator speed of node 60 km/h 2 100 vehicles in 3000 m × Opportunistic 3000 m area; each road has 4 Network lanes; average speed of node Environment 60 km/h (One) simulator 5000 taxi in Beijing city 30 Simulation with days of trace 25 × 25 real environment Manhattan grid data 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. he 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. herefore, 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. hus, 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. he 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 Reduce packet replication Maximum connectivity Minimize intermittent nodes Reduce packet replication Optimize channel usage relaying, the one which can maximize the connectivity is selected. he 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. 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. hus, to control the amount of replicated packets appropriately is a signiicant 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. he data is forwarded to the node which is moving in diferent 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 8 International Journal of Distributed Sensor Networks 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. 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. 4. Open Issues and Future Directions In this section, we describe open issues and challenges for VDTN routing protocols. he need to address the emerging number of services in the vehicles has given rise to an increase in research in vehicular communication. he 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. he protocol which is designed for such environments may not show eicient performance in a more complex environment. For example, the vehicles may enter the urban area ater passing highway. herefore, variety environments should be taken into account at the same time. (ii) In most studies for VDTNs, the bufer management of vehicles is overlooked. Only the size of bufer is described, but how it can be managed is not described. he bufer management is important in DTN, because a lot of DTN protocols are based on store-carryforward mechanism. herefore, reallocating bufer space and maximum use of other resources can also be addressed. (iii) Most of the routing protocols utilize the location information of nodes. he 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 eicient 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) here always exists a tradeof between delivery ratio, end-to-end delay, and network resource usage while applying diferent approaches in the vehicular networks. hus, a completely diferent algorithm with existing methods can be expected to minimize the tradeof through, for example, artiicial intelligenceaware 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 unidentiied and open. herefore, the feasibility of applying the (vi) he 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. he simplest routing scheme which has been used in the CCN is the breads-crumb technique. However, we need eicient routing schemes to fulill requests efectively and eiciently 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 irst 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. Conflict of Interests he authors declare that there is no conlict of interests regarding publication of this paper. Acknowledgments his research was supported by the MSIP (Ministry of Science, ICT & Future Planning), Korea, under the C-ITRC (Convergence Information Technology Research Center) support program (NIPA-2014-H0401-14-1004) supervised by the NIPA (National IT Industry Promotion Agency). his research was also supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (2012R1A1A4A01009954). References [1] S. Kumar, S. H. Ahmed, U. Qasim et al., “Analyzing link and path availability of routing protocols in vehcular ad-hoc networks,” Journal of Basic and Applied Scientiic Research, vol. 4, no. 2, pp. 189–206, 2014. [2] S. Sagar, S. H. Ahmed, Z. A. Khan et al., “Link and path duration of routing protocols in mobile ad-hoc networks and vehcular ad-hoc networks,” Journal of Basic and Applied Scientiic Research, vol. 4, no. 2, pp. 144–158, 2014. International Journal of Distributed Sensor Networks [3] A. H. Syed, S. H. Bouk, and D. Kim, “Reducing scanning latency in WiMAX enabled VANETs,” in Proceedings of the Conference on Research in Adaptive and Convergent Systems (RACS ’14), pp. 161–165, ACM, 2014. [4] J. Li and C. Chigan, “Achieving robust message dissemination in VANET: challenges and solution,” in Proceedings of the IEEE Intelligent Vehicles Symposium (IV ’11), pp. 845–850, 2011. [5] J. Schleich, G. Danoy, B. Dorronsoro, and P. Bouvry, An Overlay Approach for Optimising Small-World Properties in VANETs, Springer, Berlin, Germany, 2013. [6] P. R. Pereira, A. Casaca, J. J. P. C. Rodrigues, V. N. G. J. Soares, J. Triay, and C. Cervelló-Pastor, “From delay-tolerant networks to vehicular delay-tolerant networks,” IEEE Communications Surveys and Tutorials, vol. 14, no. 4, pp. 1166–1182, 2012. [7] F. Warthman, Delay-Tolerant Networks (DTNs) A Tutorial, DTN Research Group Internet Drat, 2003. [8] A. Bujari, C. E. Palazzi, D. Maggiorini, C. Quadri, and G. P. Rossi, “A solution for mobile DTN in a real urban scenario,” in Proceedings of the IEEE Wireless Communications and Networking Conference Workshops (WCNCW ’12), pp. 344–349, Paris, France, April 2012. [9] D. Câmara, N. Frangiadakis, C. Bonnet, and F. Filali, “Vehicular delay tolerant networks,” in Handbook of Research on Mobility and Computing: Evolving Technologies and Ubiquitous Impacts, pp. 356–367, IGI Global, 2011. [10] V. N. G. J. Soares, F. Farahmand, and J. J. P. C. Rodrigues, “A layered architecture for vehicular delay-tolerant networks,” in Proceedings of the IEEE Symposium on Computers and Communications (ISCC ’09), pp. 122–127, July 2009. [11] M. P. Singh, A. J. Deen, and P. K. Shukla, “A comprehensive survey of routing strategies for vehicular Ad-hoc networks,” Wireless Communication, vol. 5, no. 8, pp. 328–333, 2013. [12] V. N. G. J. Soares, F. Farahmand, and J. J. P. C. Rodrigues, “Improving vehicular delay-tolerant network performance with relay nodes,” in Proceedings of the Next Generation Internet Networks (NGI ’09), pp. 1–5, Aveiro, Portugal, July 2009. [13] F. Farahmand, I. Cerutti, A. N. Patel, Q. Zhang, and J. P. Jue, “Relay node placement in vehicular delay-tolerant networks,” in Proceedings of the Global Telecommunications Conference (GLOBECOM ’08), pp. 1–5, IEEE, 2008. [14] G. Wang, B. Wang, and Y. Gao, “Dynamic spray and wait routing algorithm with quality of node in delay tolerant network,” in Proceedings of the International Conference on Communications and Mobile Computing (CMC ’10), pp. 452–456, IEEE, April 2010. [15] A. Sérgio de Sousa Vieira, J. Gonçalves Filho, J. Celestino Jr., and A. Patel, “VDTN- ToD: routing protocol VANET/DTN based on trend of delivery,” in Proceedings of the 9th Advanced International Conference on Telecommunications (AICT ’13), pp. 135–141, 2013. [16] Y. Zhu, B. Xu, X. Shi, and Y. Wang, “A survey of social-based routing in delay tolerant networks: positive and negative social efects,” IEEE Communications Surveys & Tutorials, vol. 15, no. 1, pp. 387–401, 2013. [17] J. N. G. Isento, J. J. P. C. Rodrigues, J. A. F. F. Dias, M. C. G. Paula, and A. Vinel, “Vehicular delay-tolerant networks? A novel solution for vehicular communications,” IEEE Intelligent Transportation Systems Magazine, vol. 5, no. 4, pp. 10–19, 2013. [18] J. A. F. F. Dias, J. J. P. C. Rodrigues, J. N. G. Isento, and J. Niu, “he impact of cooperative nodes on the performance of vehicular delay-tolerant networks,” Mobile Networks and Applications, vol. 18, no. 6, pp. 867–878, 2013. 9 [19] K. Xing, W. Wu, L. Ding, L. Wu, and J. Willson, “An eicient routing protocol based on consecutive forwarding prediction in delay tolerant networks,” International Journal of Sensor Networks, vol. 15, no. 2, pp. 73–82, 2014. [20] J. A. Dias, J. J. P. C. Rodrigues, L. Shu, and S. Ullah, “A reputation system to identify and isolate selish nodes in vehicular delaytolerant networks,” in Proceedings of the 13th International Conference on ITS Telecommunications (ITST ’13), pp. 133–138, IEEE, November 2013. [21] A. P. Silva, S. Burleigh, C. M. Hirata, and K. Obraczka, “A survey on congestion control for delay and disruption tolerant networks,” Ad Hoc Networks, 2014. [22] J. Burgess, B. Gallagher, D. Jensen, and B. N. Levine, “MaxProp: routing for vehicle-based disruption-tolerant networks,” in Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM ’06), vol. 6, pp. 1–11, Barcelona, Spain, April 2006. [23] M. J. Khabbaz, W. F. Fawaz, and C. M. Assi, “Probabilistic bundle relaying schemes in two-hop vehicular delay tolerant networks,” IEEE Communications Letters, vol. 15, no. 3, pp. 281– 283, 2011. [24] D. Wu, G. Zhu, and D. Zhao, “Adaptive carry-store forward scheme in two-hop vehicular delay tolerant networks,” IEEE Communications Letters, vol. 17, no. 4, pp. 721–724, 2013. [25] D. Yu and Y.-B. Ko, “FFRDV: fastest-ferry routing in DTNenabled vehicular Ad Hoc networks,” in Proceedings of the 11th International Conference on Advanced Communication Technology (ICACT ’09), pp. 1410–1414, February 2009. [26] W.-Z. Lo, J.-S. Gao, and S.-C. Lo, “Distance-aware routing with copy control in vehicle-based DTNs,” in Proceedings of the IEEE 75th Vehicular Technology Conference (VTC ’12), pp. 1–5, IEEE, June 2012. [27] Q. Fu, L. Zhang, W. Feng, and Y. Zheng, “DAWN: a density adaptive routing algorithm for vehicular delay tolerant sensor networks,” in Proceedings of the 49th Annual Allerton Conference on Communication, Control, and Computing, pp. 1250–1257, Monticello, Ill, USA, 2011. [28] I. Leontiadis and C. Mascolo, “GeOpps: geographical opportunistic routing for vehicular networks,” in Proceedings of the IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks (WOWMOM ’07), pp. 1–6, June 2007. [29] V. N. G. J. Soares, J. J. P. C. Rodrigues, and F. Farahmand, “GeoSpray: a geographic routing protocol for vehicular delaytolerant networks,” Information Fusion, vol. 15, no. 1, pp. 102–113, 2014. [30] S. H. Bouk, S. H. Ahmed, and D. Kim, “Vehicular information centric networking: research challenges,” in Proceedings of the Korean Institute of Communications and Information Workshop (KICS ’14), 2014. [31] G. Grassi, D. Pesavento, G. Pau, R. Vuyyuru, R. Wakikawa, and L. Zhang, “VANET via named data networking,” in Proceedings of the IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS ’14), 2014.