Sage Journals: Discover world-class research

Abstract

Delay/Disruption Tolerant Networks (DTNs) have been attracting great interest from research community, where data communication naturally does not require contemporaneous end-to-end connectivity. Although they are suffering from a large variation of network topology, numerous previous routing protocols proposed for DTNs still make effort to qualify delivery potential, via network topology information. Geographic routing is an alternative, conceptually, by relying on the geographic information instead of topological information. In the literature, since this technique branch has not been extensively investigated in DTNs, our paper identifies the motivation and challenges for applying geographic routing in DTNs with the state of the art. Also, we highlight the future research directions for this branch.

1. Introduction

Originated from Interplanetary Networks (IPNs), the Delay/Disruption Tolerant Network (DTN) [1] architecture is suitable for a variety of Intermittently Connected Networks (ICNs) (the term Delay/Disruption Tolerant Networks (DTNs) is also used exchangeably), where there is no contemporaneous end-to-end path towards destination during most of the time, due to the large variation of network topology and sparse network density. In DTNs, the connectivity is maintained when pairwise nodes come into the transmission ranges of each other. Each node receives a message among its current neighbors, stores this message, and waits for the future encounter opportunities with other nodes to relay the message, which is known as Store-Carry-Forward (SCF) mechanism. It is highlighted that routing in DTNs relies on the SCF behavior arising from nodal mobility to asymmetrically relay the message, rather than that in Mobile Ad Hoc NETworks (MANETs) [2] requiring the contemporaneous end-to-end connectivity.

Thanks to the existing tutorials and surveys on DTNs [3–5], the high delay and high bit error rate are more concerned for IPNs (referred to as DTNs for deep space scenario) even when the connectivity exists. Meanwhile, DTNs envisioning for terrestrial scenarios suffer more from the frequent communication disruption, for example, Pocket Switched Networks [6] (PSNs) (PSNs make use of both human mobility and its connectivity to relay the message between mobile users' devices), Underwater Sensor Networks (UWSNs) [7], sparse Vehicular Ad Hoc NETworks (VANETs) [8–10], and Airborne Networks (ANs) [11]. Note that since the design of routing protocols in DTNs is application specific, we focus on terrestrial scenarios of DTNs because geographic routing [12] is mainly applied for mobile networks.

Geographic routing, also called position based routing, requires that each node can determine its own location and that the source is aware of the location of destination. Different from topological routing, geographic routing exploits the geographic information instead of topological connectivity information for message relay, to gradually approach and eventually reach the intended destination. According to literature [3], we observe that previous routing protocols in DTNs, mainly, have adopted historically topological information to predict the future encounter opportunity. In contrast, the focus of this paper is to highlight the research vision and potential for applying geographic routing in DTNs, which has not been addressed yet. The major contributions are as follows: (i)

To identify the research motivation and challenges for bringing geographic routing protocols in DTNs.

(ii)

To provide an up-to-date review on well known geographic routing protocols in DTNs, following our original technique taxonomy.

(iii)

To highlight potential future directions leading the ongoing research in this explicit field.

2. Motivation and Challenges for Geographic Routing in DTNs

2.1. Motivation for Geographic Routing in DTNs

Under the mobile scenario, the variation of network topology arising from nodal mobility is mainly the challenge for routing in DTNs. However, it is difficult to obtain the most recent network topological information given such condition. Up to now, numerous pervious works in the literature have mainly adopted the historical network topology information, to predict the possibility that pairwise nodes would meet in the future.

In terms of research vacancy, based on our observation in Figure 1 conducted from [3], there have been 7 up-to-date geographic routing protocols reviewed compared to other numerous topological based protocols in [3]. Following the guidance from previous surveys [4, 5], the reason for this lack of attention is that researchers just paid attention to the limitation of traditional topological routing protocols such as Dynamic Source Routing (DSR) [13] when it is brought in DTNs.

Figure 1

Proportion of topological and geographic routing protocols reviewed in [3].

In terms of research feasibility [15], geographic routing inherently is without the requirement of contemporaneous end-to-end connectivity. This is because only the one-hop geographic information (e.g., distance and direction towards destination) is exploited. Therefore, geographic routing can adapt to topological variation by its geometric relaying behavior, which is more reliable for message delivery especially for VANETs scenarios [16, 17]. As already shown in Figure 2(a), we observe that traditional geographic routing protocol Greedy Perimeter Stateless Routing (GPSR) [12] outperforms topological protocol DSR, in terms of message delivery ratio in MANETs.

Figure 2

Comparison results between DSR and GPSR, in [14].

2.2. Challenges for Geographic Routing in DTNs

Conventional geographic routing protocols designed for MANETs assume that the location of destination is always available for all nodes in networks, such that they would make individual routing decisions for message delivery towards destination. However, applying geographic routing in DTNs further brings following challenges as shown in Figure 3.

Figure 3

Challenges for geographic routing in DTNs.

(i) Reliability for Message Relaying. In MANETs, the message is greedily relayed towards destination via the continuously connected path within a short time. However, in DTNs, the network node which is currently closer to the destination may not be so in future. This is because it may not encounter others within a short time, particularly concerning the high mobility in sparse network. It is worthy noting that, in DTNs (refer to Figure 2(b)), GPSR begins to perform worse than DSR in sparse networks.

(ii) Locating Mobile Destination. Concerning the mobility of destination, this challenge limits the feasibility of applying a centralized location server to track the real-time location of mobile destination in sparse networks. This happens due to the fact that there is a long delay to request/reply to the information from location server in DTNs, while the obtained location information may be outdated and inaccurate for making routing decision.

(iii) Difficulty for Handling the Local Maximum Problem. This problem implies that if a better relay node is unavailable, the message carrier will keep on carrying its message. In light of this, the message delivery is delayed or even degraded if a better relay node is never met. Using distance metric as an example, any node closer to destination is generally qualified with a better delivery potential. However, a message cannot be relayed if any encountered node is farther away from destination.

Conventional geographic routing protocols in MANETs rely on the high network density, which is infeasible in DTNs because there are insufficient number of encountered nodes to help in handling this problem. Particularly, Figure 2(b) also shows its importance in sparse networks, where GPSR (without addressing this problem) suffers more from a performance degradation, as compared to the original GPSR.

Our review finds that the mobility prediction has been covered in literature, whereas the second and third challenges have not been adequately addressed. In addition to above challenges identified for geographic routing in DTNs, other factors (e.g., limited buffer space, bandwidth [18], and energy) also play important roles in general routing performance in DTNs. Different from our previous work [3] which is a review for general routing protocols in DTNs addressing unicasting, multicasting, and anycasting issues, this paper turns to exploit geographic routing in DTNs, with identified motivation, challenges, and state of the art based on an original taxonomy and further potential directions.

3. Taxonomy and Review on Geographic Routing in DTNs

We classify the existing geographic routing protocols in DTNs into three classes, depending on the awareness of destination. Following our original taxonomy in Figure 4, the detail of each class is discussed in this section.

Figure 4

Taxonomy on geographic routing protocols in DTNs.

3.1. Destination Unawareness Class

Protocols in this branch aim to achieve efficient message replication (in this paper, the term “replication” means that a copy of message is generated through routing procedure) using geometric utility, without the requirement to track where the destination is.

Vector Routing. The key insight of Vector Routing [19] is to replicate the message according to an encounter angle $ω \in [0, π]$ between pairwise encountered nodes. This protocol intends to replicate a smaller number of messages given a small value of ω, because pairwise encountered nodes moving with a similar direction would result in redundant replication. Even though these two nodes are moving with quite different direction, it is also redundant to replicate a large number of messages given that $ω = π$ , because the encountered node is currently moving with a previous trajectory of message carrier. Results show the low routing overhead of Vector Routing compared to blind flooding protocol [20].

However, Vector Routing is inefficient given the case shown in Figure 5. At $T_{1}$ time slot, the message in node A is replicated to B according to the policy of Vector Routing, as their encounter angle is $π / 2$ . Even if the moving directions of nodes A and C are consistent, node B still replicates the message received from node A to C at $T_{2}$ time slot. This procedure brings replication redundancy, as message copies are carried by both nodes A and C with the same moving direction. Since Vector Routing only handles each message identically, a huge overhead will occur if there are large number of messages for replication.

Figure 5

Drawback of Vector Routing.

RoRo-LT. In RoRo-LT [21], the LT stands for location at corresponding time, such that a long term observation (for several weeks) from such spatiotemporal history can predict future locations. Basically, the self-periodicity measures how similar that current routine of a node is compared to its historical habit. If a high similarity is matched, the current routine is used to predict its mobility. With the estimated future trajectories of pairwise encountered nodes, the message carried by node A would be replicated to an encountered node B, only if they are predicted to be distant from each other in a near future. This is different from Vector Routing which determines how many messages are replicated depending on mobility of pairwise encountered nodes.

However, results show that RoRo-LT does not perform well, although using the knowledge from a certain increased depth (or referred to as number of weeks). This certainly indicates the limitation of routing protocols in “Destination Unawareness” class. Driven by this limitation, the following protocols discuss the importance of tracking the message destination on the routing performance.

3.2. Destination Awareness Class

3.2.1. Stationary Destination

By knowing the location of stationary destination in advance, protocols under this branch focus more on exploring various geometric metrics to select relay.

MOVE. Motion Vector (MOVE) [22] forwards (the term “forward” refers to the policy that a copy of message will not be generated through routing process) the message towards its destination, mainly based on the nodal moving direction. Furthermore, based on the consistent moving direction between pairwise encountered nodes, the distance is adopted to identify the node which does not extensively contribute to message delivery (further away from the destination). As an example shown in Figure 6 where node A is the message carrier, the condition $(D i s t_{A, D} > D i s t_{B, D})$ makes message forwarding decision to node B, if both nodes A and B are moving away from D. In contrast, the condition $(D i s t_{A, D}^{p} > D i s t_{B, D}^{p})$ is applied, if both nodes A and B are moving towards D.

Figure 6

Illustration of geometric utilities for MOVE And AeroRP.

One disadvantage of MOVE is that it does not consider the factor of nodal moving speed, since the node with a faster proximity to destination is able to reduce delivery delay. In addition, MOVE does not address the local maximum problem, where the relay node with a closer distance to the destination may not be always available. Therefore, additional delay or unsuccessful message delivery would occur, if an appropriate relay node is not met.

GeOpps. Assisted by the navigation system to calculate a suggested route towards the destination, the core of GeOpps [23] is to select the nearest point (NP) along the suggested route where the NP is the nearest point to destination. With message forwarding policy, the metric Minimum Estimated Time of Delivery (METD) as calculated in the following is used to qualify relay node:

\begin{matrix} METD = ETA + \frac{D i s t_{N P, D}}{Average  Moving  Speed} . \end{matrix}

(1)

Here, the ETA is the estimated time traveling from the location of current node to the NP, while

D i s t_{N P, D}

is denoted as the distance from the NP to destination. By considering the nodal moving speed, GeOpps achieves a lower delivery latency comparing with MOVE. This protocol is further extended as GeoSpray [24], by controlling the number of message copies for replication. Besides, GeoSpray further tackles the limited network resources including bandwidth and buffer space, by prioritizing messages for transmission and storage.

It is observed that the selection of NP is an important factor for GeOpps, where running algorithm to find the NP requires the knowledge of underlying road topology. This brings scalability concern in large scale road system, as it would need a longer time to find the NP, and thus increases the computation complexity. Besides, the local maximum problem that the node with a lower value of METD may be currently unavailable is not addressed in GeOpps. Particularly, due to nodal mobility, missing a communication opportunity brings additional calculation of NP for next encounter.

MPAD. Mobility Prediction Based Adaptive Data (MPAD) gathering [25] is designed for mobile sensor networks. Under such scenario, the message gathering is a major challenge, because traditional protocols mainly rely on a large number of densely deployed sensor nodes to construct a contemporaneous end-to-end path towards sink node. Considering mobility prediction, MPAD adopts a metric as an intersection between the moving path of corresponding node and the transmission range of sink node, as the moving direction of node A shown in Figure 7. If the above condition is not met, the communication angle calculated by the two tangents between node A and sink node is adopted as backup metric. Here, a closer distance to the sink node indicates a larger communication angle and thus increases the potential for message delivery.

Figure 7

Illustration of geometric utility in MPAD.

MPAD does not consider the factor of message lifetime for making routing decision, because it is important for message gathering before expiration specially in sensor network. The message that is close to expiration deadline should be greedily replicated, regardless of the relay node selection policy. In other words, the message with short lifetime is still suggested for replication, although its carrier is further away from sink node.

AeroRP. Envisioning for ANs, AeroRP [26] selects the relay node to forward the message, by jointly considering distance and moving direction as well as speed. As the example shown in Figure 6, the metric Time-To-Intersect (TTI) for node A to approach node D is calculated as $T T I_{A, D} = D i s t_{A, D} / (S p e e d_{A} \times \cos ϕ_{A, D})$ , where $S p e e d_{A}$ is the current moving speed of node A.

Since AeroRP only considers the case that pairwise encountered nodes are moving towards the destination, its routing policy is limited in case the message carrier is moving away from destination even if its encountered node is moving towards destination. Here, according to its routing policy, the message will not be forwarded. This is because the negative value of TTI is invalid for making routing decision. Due to the very sparse network density and high speed in ANs, failing to relay a message due to such limitation degrades routing performance.

DGR. Delegation Geographic Routing (DGR) [27] overcomes the limitation of routing decision in AeroRP, by comparing the TTI of historically encountered node with that of currently encountered node, instead of comparing that between the current encountered node and message carrier. Therefore, any failure of routing decision due to the inconsistent moving directions between pairwise encountered nodes is overcome. Such operation is implemented via Delegation Forwarding (DF) [28] optimization policy, by always recording the TTI of selected relay node after successful message transmission. Thus, with the update of its level, the number of copies duplicated for a message is expected to be decreased.

DGR also addresses the local maximum problem, where the heuristic approach is presented as

\begin{matrix} T_{M}^{e l a} + T_{M}^{T T I} > T_{M}^{i n i} . \end{matrix}

(2)

Here,

T_{M}^{e l a}

and

T_{M}^{i n i}

are the elapsed time since message generation and the initial message lifetime, respectively, while

T_{M}^{T T I}

is the recorded TTI in message. This inequality implies that the message will expire, if the remaining message lifetime

T_{M}^{i n i} - T_{M}^{e l a}

is shorter than

T_{M}^{T T I}

. In this context, rather than just keeping the message that is close to expiration, a message copy is replicated to increase the possibility of encountering other relay nodes.

3.2.2. Considering Mobile Destination via Real-Time Geographic Information

Protocols under this branch consider the mobility of destination. However, they ignore the feasibility to track mobile destination in sparse networks. Here, a centralized location server is still assumed to support real-time location request/reply.

DAER. Distance Aware Epidemic Routing (DAER) [29] assumes that the real-time location of mobile destination can be collected from a centralized location service system, regardless of the delay in exchanging such information in sparse networks. Any encountered node with a closer distance to destination than the message carrier itself is replicated with a message copy. Upon a successful message transmission, the original message carrier moving away from destination would discard its message in local buffer. This operation aims to prevent additional message replication redundancy away from destination, which reduces the routing overhead.

The major concern is how to obtain the real-time location of destination given the identified challenges in Section 2. Along with that, DAER does not predict the nodal mobility, due to only relying on a distance metric. As such, a high speed may contribute to faster proximity to destination and vice versa. Considering the encountered node with a closer distance to destination may not be always available; such local maximum problem needs to be addressed.

POR. As an extension based on DAER [29], the routing decision in Packet Oriented Routing (POR) [30] takes the balance between the distance and messages replicated along this distance into account. The idea behind this is to select a longer distance for replicating less messages, so as to enhance the transmission reliability. Results show the advantage of POR over DAER, particularly given limited transmission bandwidth.

However, POR still faces the limitation of design assumption in DAER, in terms of relying on the centralized location server and mobility prediction as well as local maximum problem handling.

3.2.3. Considering Mobile Destination via Historical Geographic Information

Protocols under this branch tackle the limitation in former branch. Instead of assuming that the real-time location of mobile destination can be always tracked, the historical geographic information is applied under this branch to estimate where the destination would be.

LAROD-LoDiS. The main contribution of Location Aware Routing for Delay (LAROD) tolerant networks-Location Dissemination Service (LoDiS) [31] is the design of a location service system in sparse networks, by maintaining a local database of nodal locations. Such information is updated using broadcast gossip together with routing overhearing. Depending on an estimated replication area to limit routing redundancy, the message is replicated towards the location of destination using the distance metric.

One concern for LAROD-LoDiS is that the current location of destination may differ from the recorded information, which influences the reliability of routing decision. If using an obsolete location information, the routing decision making would be inaccurate and even degrade routing performance. Besides, the local maximum problem in terms of distance factor and mobility prediction concerning direction and speed are not addressed.

geoDTN. As designed for PSNs scenario, geoDTN [32] records the historical nodal movement information and calculates an intersection area in which any two nodes encountered in the past, as a metric to score the encounter possibility. This is common in reality that two people may move within the same area because of their social habits. In detail, the distance model of geoDTN adopts the minimum distance to the destination if the scores of pairwise nodes are below a predefined threshold value. Considering the local maximum problem that the node with a closer distance to destination is unavailable, geoDTN randomly forwards the message based on a predefined probability in the rescue model. If both pairwise nodes are with higher scores than the predefined threshold value, the node with a higher score is selected as relay.

However, there are several predefined parameters defined in geoDTN, which affect the scalability. In particular, the predefined probability value in rescue model for handling the local maximum problem should adapt to the network condition. It is important that this probability should become larger when the message is close expiration, while an infrequent nodal encounter also enlarges such value.

AaR. Referring to Location Aided Routing (LAR) [33], Approach and Roam (AaR) [34] technique adopts the historical geographic information of destination to estimate its movement range, via its moving speed and location recorded in the past. The key insight is to make faster message replication towards this estimated movement range via the Approach phase and to guarantee message replication within this range for a longer duration via the Roam phase.

Since AaR consists of two routing phases, the local maximum problem in Approach phase implies that the relay node which approaches the movement range of destination faster than current message carrier is unavailable. Meanwhile, the unavailability of relay node which roams in this range with a longer time is considered as the local maximum problem in Roam phase. Such two problems are both handled based on the similar idea proposed in DGR [27], by considering the message lifetime and nodal mobility. Further effort is also paid in Converge-and-Diverge (CaD) [35], which reduces routing overhead via DF optimization policy [28].

3.3. Hybrid Class

Protocols under this branch combine the advantage of those in “Destination Unawareness” class, when the location of destination is unavailable in initial stage, and those with the historical geographic information in “Destination Awareness” class when an approximate location of destination is found.

HVR. History Based Vector Routing (HVR) [36] enables each mobile node to record the historical geographic information including location and moving speed of other encountered nodes. This information is used for relay node selection, by calculating the overlapped area between the circle estimated for destination and the transmission range of node. As an example shown in Figure 8, where $t_{c u r}$ is the current time and W is the estimation time window, assuming that a constant speed of node D is $S p e e d_{D}$ , the radius $R_{D}^{'}$ for node D estimated at $(t_{c u r} + W)$ time slot is calculated as $S p e e d_{D} * (t_{c u r} + W - t_{A, D})$ ; here, $t_{A, D}$ is the historical encounter time for node D recorded by node A. In light of this, the one with a larger overlapped area with destination is selected as the relay node. In addition, HVR adopts Vector Routing [19] for message replication if the historical geographic information of destination is unavailable.

Figure 8

Illustration of geometric estimation in HVR.

Although HVR is more reliable than other approaches considering the mobile destination, one concern is that there may not be an overlapped area for calculation, because of a quite long distance between the corresponding node and destination. Therefore, the routing decision has limitation when both pairwise encountered nodes do not have the overlapping with the movement range estimated for destination, even if they have the knowledge about destination. In addition to this, HVR does not discuss the local maximum problem that the relay node with a larger overlapped area may be unavailable.

GSaR. Geographic-Based Spray-and-Relay (GSaR) [37] delivers messages given a limited number of L replications, where the initial value of L is predefined based on scenario and distributed to the selected relay node. This protocol assumes that when network nodes are sufficiently mobile, only generating a small number of message copies is able to achieve successful delivery. Given the historical location and moving speed as well as encounter time recorded in the past, the movement range of destination is estimated by referring to [34]. Here, with L copies allowed for each message, GSaR decouples routing decision threefold: (1) to expedite message copies being replicated towards this range in order to reduce delivery delay; (2) to prevent message copies being replicated away from this range in order to reduce routing overhead; (3) to postpone message copies being replicated out of this range in order to increase delivery probability. (4) As a back-up scheme, if the above historical geographic information of destination is unavailable, messages are replicated considering the relative moving direction between pairwise nodes as well as their moving speeds.

4. Comparison and Analysis

Table 1 illustrates the reviewed geographic routing protocols in DTNs, where their years of publication and the application scenarios are highlighted. In addition, the concerns regarding limited bandwidth, buffer space, and energy are discussed, because DTNs are generally assumed with limited network resources. Details regarding how these factors affect routing performance have already been introduced in [3].

Table 1

Comparison among geographic routing protocols in DTNs.

Name of protocol	Application scenario	Year	Knowledge for routing decision	Relay policy	Bandwidth	Buffer space	Energy	Local maximum problem
Destination Unawareness class
Vector Routing [19]	VANETs	2008	Encounter angle, and moving Speed	Replication	Yes	Not discussed	Not discussed	Not applicable
RoRo-LT [21]	PSNs	2013	Distance	Replication	Not discussed	Not discussed	Not discussed	Not applicable

Destination Awareness class
(1) Stationary destination
MOVE [22]	VANETs	2005	Distance, moving direction	Forwarding	Not discussed	Yes	Not discussed	Not discussed
GeOpps [23]	VANETs	2007	Selection of the NP, moving speed, and distance	Forwarding	Not discussed	Not discussed	Not discussed	Not discussed
GeoSpray [24]	VANETs	2014	Selection of the NP, moving speed, and distance	Replication	Yes	Yes	Not discussed	Not discussed
MPAD [25]	UWSNs	2008	Moving direction, communication angle	Replication	Yes	Yes	Not discussed	Not discussed
AeroRP [26]	ANs	2011	Moving direction, distance, moving speed	Forwarding	Not discussed	Yes	Not discussed	Not discussed
DGR [27]	VANETs	2013	Moving direction, distance, and moving speed	Replication	Not discussed	Not discussed	Not discussed	Yes
(2) Mobile destination via real-time geographic information
DAER [29]	VANETs	2007	Distance	Replication	Yes	Yes	Not discussed	Not discussed
POR [30]	VANETs	2008	Distance, message size	Replication	Yes	Not discussed	Not discussed	Not discussed
(3) Mobile destination via historical geographic information
LAROD-LoDiS [31]	ANs	2011	Distance, replication area	Replication	Yes	Not discussed	Not discussed	Not discussed
geoDTN [32]	PSNs	2011	Distance, movement area	Forwarding	Not discussed	Not discussed	Yes	Yes
AaR [34]	VANETs	2014	Moving speed, moving direction, and movement area	Replication	Yes	Yes	Not discussed	Yes
CaD [35]	VANETs	2013	Moving speed, moving direction, and movement area	Replication	Yes	Not discussed	Not discussed	Yes

Hybrid class
HVR [36]	VANETs	2009	Movement area, moving speed, and encounter angle	Replication	Not discussed	Not discussed	Not discussed	Not discussed
GeoSaR [37]	VANETs	2015	Moving speed, moving direction, movement area, and encounter angle	Replication	Yes	Yes	Yes	Yes

We further define the term “not discussed” for the bandwidth concern, if either a reviewed protocol does not define the message priority for transmission, or the performance evaluation addresses the varied traffic load. A similar judgment is applied for the concern on buffer space and energy as well. Here, a quantified comparison among reviewed protocols is unable to be provided, due to their design for different application scenarios. Also, the algorithm complexity is out of discussion due to subjectivity.

Apart from the knowledge required for making routing decision, in what policy that messages are relayed is discussed, given that reviewed protocols are either forwarding based via single message copy or replication based via multiple message copies. Here, using forwarding policy is more efficient because there are no more additional message copies existing in the network. Even with more redundancy, using replication policy is more reliable in sparse networks. This is because generating additional message copies increases the possibility that at least any one of them could be delivered. Consequently, there is a tradeoff between achieving the highest delivery ratio and the least redundancy.

The motivation of “Destination Unawareness” based protocols is to geometrically replicate messages, in case the destination cannot be tracked. In this branch, handling the “local maximum problem” is “not applicable,” as the qualification of relay node is unrelated to message destination. Here, the routing decision should focus more on estimating the delivery potential [21] for each message, rather than addressing the number of messages [19]. For example, messages may have different sizes where the one with a smaller size requires shorter time for transmission and vice versa. Depending on this condition, different moving directions or larger distance variation between pairwise encountered nodes enables a good chance for message replication.

In spite of this, tracking where the destination is (or approximately would be) plays a crucial role in driving high delivery ratio, as addressed in “Destination Awareness” branch. Regarding those considered stationary destination and mobile destination via real-time geographic information, even if the destination can be tracked to guide routing decision, it is still essential to explore the mobility (e.g., jointly considering distance, moving direction, and speed) of nodes and predict a future encounter opportunity. Relatively, those protocols applying historical geographic information tackle a practical concern, by taking the freshness of the location of destination into account. For example, relaying the message towards an obsolete location where mobile destination was located would however degrade routing performance. Therefore, identifying the dynamic changed status of mobile destination should be further investigated.

Further to above two branches, integrating the efforts in “Destination Unawareness” branch as a backup and that in “Destination Awareness” branch as the core intelligence can substantially enhance the reliability of routing decision as investigated in Hybrid Class.

5. Future Directions

Thanks to the success of Global Positioning System (GPS) technique, geographic routing protocols in DTNs have a huge potential than those topological protocols [38, 39], particularly for VANETs, UWSNs, and ANs scenarios because of their highly dynamic characteristics. In this section, we detail a list of future directions which are worthwhile studying.

Handling the Local Maximum Problem. Although it has been identified and initially tackled in literature, the local maximum problem is still an important issue for further investigation. In [26], a heuristic approach concerning the nodal mobility and message lifetime is proposed and has been proven through analysis and simulation. However, such approach is locally estimated at each node, without an overview of other copies of a certain message in networks. On the one hand, the local maximum problem should be handled more greedily, if all message copies are close to expiration deadline. On the other hand, more attention should be paid to nodal encounter prediction, if the message can still exist in network for certain time. Therefore, apart from the knowledge of message carrier itself, it is also essential to obtain an accurate (ideally) or approximate (practically) knowledge about how many copies of a message have been replicated. In order to further optimally handle the local maximum problem, an intelligent approach should be to jointly consider the number of copies of a message and its lifetime as well as individual nodal mobility.

Concern on QoS Awareness. Since it is difficult to provide an end-to-end QoS support in DTNs, appropriate message scheduling for transmission and buffer management is crucial given the limited bandwidth and buffer space. These two factors determine the number of messages that can be successfully transferred and received by relay nodes. Besides, since the nodes running out of energy cannot involve communication anymore, necessary energy saving approaches have been proposed, via an intelligent beacon control for nodal discovery [40]. Specifically, a frequent beacon broadcasting to discover neighbor nodes is energy costly, while that with infrequent broadcasting however may miss the communication opportunities with neighbor nodes. Note that the beacon control also has influence on the information updating (directly related to making routing decision) that happens between pairwise nodes.

Concern on Coding Technique. As reviewed in [3], network coding [41] and erasure coding [42] techniques have been applied for routing protocols in DTNs. In particular, the network coding enables efficient bandwidth usage, by encoding messages into a chunk block for transmission, while erasure coding compensates the communication failure, by encoding the original message into a certain number of smaller size blocks for transmission. Since none of them have been explicitly applied for geographic routing protocols in DTNs, these two well known coding techniques should be paid attention. Here, the nature of GeoSpray [24] could provide an initial guide on how to geometrically transmit those coded blocks using erasure coding technique.

Assistance of Additional Infrastructure. Considering that the nodal mobility may be limited within certain area, the assistance from additional infrastructure, for example, Message Ferry (MF)/gateway mentioned in [3], is able to help relaying the message. Here, MF is a mobile entity that moves with dedicated route, whereas gateway is a deployed stationary entity. Both of them are able to bridge the communication among disconnected network islands, via trajectory controlling and location deployment. In this context, integrating them for specific scenario is worthwhile investigating.

Concern on Application Scenario. Combining routing protocols reviewed in this paper with those conventionally designed for MANETs can adapt to the variation of network density. Initial observation in [43, 44] shows that it is intelligent to switch from MANETs to DTNs based communication mode when networks become sparse. In spite of the fact that only the topological based routing protocol has been discussed in that work, such observation is also applicable to geographic routing protocol. Such intelligence has been addressed by [44, 45] which combine the geographic routing intelligences in MANETs and DTNs. Besides, given the application scenario highlighted in Table 1, the protocol design for PSNs is still inadequately investigated compared to others. Even if there has been effort on linking geographic distance with users for fixed online social networks, such issue for mobile networks is still a challenge. Besides, the influence of heterogeneous mobility [46] should be addressed.

Concern on Security and Privacy. The information exchange for updating the historical geographic information requires security and privacy consideration. One major concern is the spoofing attack because the malicious node is able to create routing loops and generate false error information after information update. Besides, overhearing the message passing through neighboring nodes might emulate selective forwarding by jamming the relayed message. Further to security concern, it is also privacy [47] sensitive to release nodal geographic information to any encountered node. Particularly, the location information should be released among friends who have common daily habits in PSNs.

6. Conclusion

Different from MANETs, the sparse network density is the main challenge for communication in DTNs. Motivated by the lack of attention on investigating geographic routing protocols in DTNs, we identified its challenges together with an original taxonomy and further reviewed the state of the art. Following the highlighted future research directions, we hope our paper would motivate the research interest for this type of routing protocol, because of its persistent potential for academic research as well as a range of application scenarios in real world.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

This work was supported in part by by the National Natural Science Foundation (61102105), the Postdoctoral Start Foundation of Heilongjiang Province (LBH-Q12117), the Foundation for Innovative Research of Harbin (2015RAQXJ008), and the Fundamental Research Funds for the Central Universities (HEUCF1408).

References

Caini

Cruickshank

Farrell

Marchese

Delay-and disruption-tolerant networking (DTN): an alternative solution for future satellite networking applications

Proceedings of the IEEE 2011 99 11 1980 1997

10.1109/jproc.2011.2158378

2-s2.0-80054986166

Ruiz

Bouvry

Survey on broadcast algorithms for mobile ad hoc networks

ACM Computing Surveys 2015 48 1 1 35

10.1145/2786005

Cao

Sun

Routing in delay/disruption tolerant networks: a taxonomy, survey and challenges

IEEE Communications Surveys and Tutorials 2013 15 2 654 677

10.1109/surv.2012.042512.00053

2-s2.0-84877579052

Khabbaz

M. J.

Assi

C. M.

Fawaz

W. F.

Disruption-tolerant networking: a comprehensive survey on recent developments and persisting challenges

IEEE Communications Surveys & Tutorials 2012 14 2 607 640

10.1109/surv.2011.041911.00093

2-s2.0-84860886202

Zhang

Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: overview and challenges

IEEE Communications Surveys and Tutorials 2006 8 1 24 37

10.1109/comst.2006.323440

2-s2.0-84878989879

Wei

Liang

A survey of social-aware routing protocols in delay tolerant networks: applications, taxonomy and design-related issues

IEEE Communications Surveys and Tutorials 2014 16 1 556 578

10.1109/surv.2013.042313.00103

2-s2.0-84894654409

Kartha

J. J.

Jacob

Delay and lifetime performance of underwater wireless sensor networks with mobile element based data collection

International Journal of Distributed Sensor Networks 2015 2015 22

128757

10.1155/2015/128757

Pereira

P. R.

Casaca

Rodrigues

J. J. P. C.

Soares

V. N. G. J.

Triay

Cervelló-Pastor

From delay-tolerant networks to vehicular delay-tolerant networks

IEEE Communications Surveys and Tutorials 2012 14 4 1166 1182

10.1109/SURV.2011.081611.00102

2-s2.0-84872146396

Saini

Alelaiwi

Saddik

A. E.

How close are we to realizing a pragmatic VANET solution? A meta-survey

ACM Computing Surveys 2015 48 2 1 40

10.1145/2817552

10.

Rodrigues

Soares

Farahmand

Stationary relay nodes deployment on vehicular opportunistic networks

Mobile Opportunistic Networks: Architectures, Protocols and Applications 2011 56 6 227 243

11.

Jonson

Pezeshki

Chao

Smith

Fazio

Application of delay tolerant networking (DTN) in airborne networks

Proceedings of the IEEE Military Communications Conference (MILCOM ′08)

November 2008

San Diego, Calif, USA

IEEE

1 7

10.1109/milcom.2008.4753464

2-s2.0-62349117273

12.

Karp

Kung

H. T.

GPSR: Greedy Perimeter Stateless Routing for wireless networks

Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MOBICOM ′00)

August 2000

Boston, Mass, USA

243 254

2-s2.0-0034547115

13.

Johnson

D. B.

Maltz

D. A.

Dynamic source routing in Ad Hoc wireless networks

Mobile Computing 1996 353, no. 1

Berlin, Germany

Springer Mobile Computing

153 181 The Kluwer International Series in Engineering and Computer Science

10.1007/978-0-585-29603-6_5

14.

Karp

Challenges in geographic routing: sparse networks, obstacles, and traffic provisioning

Proceedings of the DIMACS Workshop on Pervasive Networking

May 2001

Piscataway, NJ, USA

DIMACS Center, Rutgers University

15.

Cadger

Curran

Santos

Moffett

A survey of geographical routing in wireless Ad-Hoc networks

IEEE Communications Surveys and Tutorials 2013 15 2 621 653

10.1109/surv.2012.062612.00109

2-s2.0-84877257737

16.

Soares

V. N. G. J.

Rodrigues

J. J. P. C.

Dias

J. A.

Isento

J. N.

Performance analysis of routing protocols for vehicular delay-tolerant networks

Proceedings of the 20th International Conference on Software, Telecommunications and Computer Networks (SoftCOM ′12)

September 2012

Croatia, Croatia

1 5

2-s2.0-84870598786

17.

Soares

V. N. G. J.

Rodrigues

J. J. P. C.

Farahmand

Performance assessment of a geographic routing protocol for vehicular delay-tolerant networks

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC ′12)

April 2012

Paris, France

2526 2531

10.1109/wcnc.2012.6214224

2-s2.0-84864351555

18.

Han

Dianati

Tafazolli

Liu

Shen

A novel distributed asynchronous multichannel mac scheme for large-scale vehicular ad hoc networks

IEEE Transactions on Vehicular Technology 2012 61 7 3125 3138

10.1109/TVT.2012.2205596

2-s2.0-84866497070

19.

Kang

Kim

Vector routing for delay tolerant networks

Proceedings of the 68th IEEE Vehicular Technology Conference (VTC-Fall ′08)

September 2008

Calgary, Canada

IEEE

1 5

10.1109/vetecf.2008.21

2-s2.0-58149125099

20.

Vahdat

Becker

Epidemic routing for partially-connected Ad Hoc networks

2000

Duke University Technical Report

21.

Turkes

Scholten

Havinga

RoRo-LT: social routing with next-place prediction from self-assessment of spatiotemporal routines

Proceedings of the 10th International Conference on Ubiquitous Intelligence and Computing and 10th International Conference on Autonomic and Trusted Computing (UIC/ATC ′13)

December 2013

Vietri sul Mare, Italy

IEEE

201 208

10.1109/uic-atc.2013.96

2-s2.0-84894202530

22.

LeBrun

Chuah

C.-N.

Ghosal

Zhang

Knowledge-based opportunistic forwarding in vehicular wireless Ad Hoc networks

Proceedings of the IEEE 61st Vehicular Technology Conference (VTC ′05)

May 2005

Stockholm, Sweden

2289 2293

10.1109/VETECS.2005.1543743

23.

Leontiadis

Mascolo

GeOpps: geographical opportunistic routing for vehicular networks

Proceedings of the IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks (WOWMOM ′07)

June 2007

Espoo, Finland

1 6

10.1109/wowmom.2007.4351688

2-s2.0-47749113660

24.

Soares

V. N. G. J.

Rodrigues

J. J. P. C.

Farahmand

GeoSpray: a geographic routing protocol for vehicular delay-tolerant networks

Information Fusion 2014 15 1 102 113

10.1016/j.inffus.2011.11.003

2-s2.0-84885959091

25.

Zhu

Cao

Liu

Zheng

Gong

Chen

A mobility prediction-based adaptive data gathering protocol for delay tolerant mobile sensor network

Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM ′08)

December 2008

New Orleans, La, USA

730 734

10.1109/glocom.2008.ecp.146

2-s2.0-67249132081

26.

Peters

Jabbar

Cetinkaya

E. K.

Sterbenz

J. P. G.

A geographical routing protocol for highly-dynamic aeronautical networks

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC ′11)

March 2011

Cancun, Mexico

IEEE

492 497

10.1109/wcnc.2011.5779182

2-s2.0-79959299007

27.

Cao

Sun

Wang

Cruickshank

Ahmad

A reliable and efficient geographic routing scheme for delay/disruption tolerant networks

IEEE Wireless Communications Letters 2013 2 6 603 606

10.1109/wcl.2013.081413.130511

2-s2.0-84891524732

28.

Erramilli

Crovella

Chaintreau

Diot

Delegation forwarding

Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc ′08)

May 2008

Hong Kong

251 259

10.1145/1374618.1374653

2-s2.0-57349185558

29.

Huang

H.-Y.

Luo

P.-E.

Shu

M.-Y.

Performance evaluation of SUVnet with real-time traffic data

IEEE Transactions on Vehicular Technology 2007 56 6 3381 3396

10.1109/tvt.2007.907273

2-s2.0-36749083390

30.

Shu

Huang

M.-Y.

DTN routing in vehicular sensor networks

Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM ′08)

December 2008

New Orleans, La, USA

IEEE

752 756

10.1109/glocom.2008.ecp.150

2-s2.0-67449093165

31.

Kuiper

Nadjm-Tehrani

Geographical routing with location service in intermittently connected MANETs

IEEE Transactions on Vehicular Technology 2011 60 2 592 604

10.1109/tvt.2010.2091658

2-s2.0-79951909073

32.

Link

J. Á. B.

Schmitz

Wehrle

GeoDTN: geographic routing in disruption tolerant networks

Proceedings of the 54th Annual IEEE Global Telecommunications Conference (GLOBECOM ′11)

December 2011

Houston, Tex, USA

IEEE

1 5

10.1109/glocom.2011.6134040

2-s2.0-84857203560

33.

Y.-B.

Vaidya

N. H.

Location‐aided routing (LAR) in mobile ad hoc networks

Wireless Networks 2000 6 4 307 321

10.1023/A:1019106118419

34.

Cao

Sun

Cruickshank

Yao

Approach-and-Roam (AaR): a geographic routing scheme for delay/disruption tolerant networks

IEEE Transactions on Vehicular Technology 2014 63 1 266 281

10.1109/tvt.2013.2272547

2-s2.0-84893345899

35.

Cao

Sun

Wang

Yao

Cruickshank

Converge-and-diverge: a geographic routing for delay/disruption-tolerant networks using a delegation replication approach

IEEE Transactions on Vehicular Technology 2013 62 5 2339 2343

10.1109/tvt.2013.2238958

2-s2.0-84879247810

36.

Kang

Kim

HVR: history-based vector routing for delay tolerant networks

Proceedings of the 18th Internatonal Conference on Computer Communications and Networks (ICCCN ′09)

August 2009

San Francisco, Calif, USA

IEEE

1 6

10.1109/icccn.2009.5235291

2-s2.0-70449127829

37.

Cao

Sun

Wang

Riaz

Cruickshank

Liu

Geographic-based spray-and-relay (GSaR): an efficient routing scheme for DTNs

IEEE Transactions on Vehicular Technology 2015 64 4 1548 1564

10.1109/tvt.2014.2331395

38.

Cao

Wang

Sun

Cruickshank

A reliable and efficient encounter-based routing framework for delay/disruption tolerant networks

IEEE Sensors Journal 2015 15 7 4004 4018

10.1109/jsen.2015.2410297

39.

Wei

Dong

Ota

CAMF: context-aware message forwarding in mobile social networks

IEEE Transactions on Parallel and Distributed Systems 2015 26 8 2178 2187

10.1109/tpds.2014.2346212

40.

Amendola

De Rango

Massri

Vitaletti

Efficient neighbor discovery in RFID based devices over resource-constrained DTN networks

Proceedings of the 1st IEEE International Conference on Communications (ICC ′14)

June 2014

Sydney, Australia

3842 3847

10.1109/icc.2014.6883920

2-s2.0-84906991548

41.

Lin

Liang

Performance modeling of network coding in epidemic routing

Proceedings of the 1st International MobiSys Workshop on Mobile Opportunistic Networking

June 2007

San Juan, Puerto Rico, USA

ACM

67 74

10.1145/1247694.1247709

2-s2.0-35448931598

42.

Wang

Jain

Martonosi

Fall

Erasure-coding based routing for opportunistic networks

Proceedings of the ACM SIGCOMM Workshop on Delay-Tolerant Networking (WDTN ′05)

August 2005

Philadelphia, Pa, USA

229 236

10.1145/1080139.1080140

2-s2.0-84871996186

43.

Lakkakorpi

Pitkänen

Ott

Adaptive routing in mobile opportunistic networks

Proceedings of the 13th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM ′10)

October 2010

Bodrum, Turkey

101 109

10.1145/1868521.1868539

2-s2.0-78650222759

44.

Cheng

P.-C.

Weng

J.-T.

Tung

L.-C.

Lee

K. C.

Gerla

Härri

GeoDTN+Nav: a hybrid geographic and DTN routing with navigation assistance in urban vehicular networks

Proceedings of the International Symposium on Visual Computing (ISVC ′08)

November 2008

Las Vegas, Nev, USA

45.

Zhao

Fan

Wang

Hybrid position-based and DTN forwarding for vehicular sensor networks

International Journal of Distributed Sensor Networks 2012 2012 10

186146

10.1155/2012/186146

2-s2.0-84862284420

46.

Cao

Wei

Min

Weng

Yang

Sun

A geographic multi-copy routing scheme for DTNs with heterogeneous mobility

IEEE Systems Journal, http://arxiv.org/abs/1601.03555

47.

Anyigor Ogah

C. P.

Cruickshank

Sun

Chandrasekaran

Cao

Asuquo

P. M.

Al Tawqi

Privacy-enhanced group communication for vehicular delay tolerant networks

Proceedings of the 9th IEEE International Conference on Next Generation Mobile Applications, Services and Technologies

September 2015

Cambridge, UK

IEEE

193 198

10.1109/NGMAST.2015.67

A Survey on Geographic Routing Protocols in Delay/Disruption Tolerant Networks

Abstract

1. Introduction

2. Motivation and Challenges for Geographic Routing in DTNs

2.1. Motivation for Geographic Routing in DTNs

2.2. Challenges for Geographic Routing in DTNs

3. Taxonomy and Review on Geographic Routing in DTNs

3.1. Destination Unawareness Class

3.2. Destination Awareness Class

3.2.1. Stationary Destination

3.2.2. Considering Mobile Destination via Real-Time Geographic Information

3.2.3. Considering Mobile Destination via Historical Geographic Information

3.3. Hybrid Class

4. Comparison and Analysis

5. Future Directions

6. Conclusion

Footnotes

Conflict of Interests

Acknowledgments

References