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:
To identify the research motivation and challenges for bringing geographic routing protocols in DTNs. To provide an up-to-date review on well known geographic routing protocols in DTNs, following our original technique taxonomy. 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.
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.
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.
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.
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
However, Vector Routing is inefficient given the case shown in Figure 5. At
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
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:
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.
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
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
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
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].
Comparison among geographic routing protocols in DTNs.
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).