1 Introduction

In 1998, the Inter-Planetary Network (IPN) launched a project for establishing connectivity between randomly located nodes on different solar system planets. After that IPN are considered as a special challenged network due to excessive delay and frequent disruption leading to the evolution of DTNs. It promises to enable communication from source to destination without end-to-end connectivity. Intermittent connectivity is the main challenge of DTN, due to this the waiting time may vary from seconds to days. Therefore, contact schedules are the most important characteristics of DTN, which strongly depend upon the application area. For example, consider a city scenario where buses are considered as nodes, and there is a schedule for every bus. However, it cannot be followed because of traffic, accidents, or equipment failure. Many DTN applications that exist in real life suffer from disconnections and are not able to send data for extended intervals of time [1,2,3,4,5,6,7,8,9,10,11,12,13,14]. DTNs have some important key properties that show a great deal of discrepancy from the standard networks. Thus, it underpins the requirements of novel routing protocols Some of the key characteristics of DTNs and the associated challenges faced by the routing protocols are discussed as follows:

  • Disconnection and varied mobility patterns In DTN it is impossible to have an end-to-end connection as well as a deterministic mobility pattern of the nodes. Thus, the routing protocols should be robust enough to handle dynamic topological patterns of mobile nodes. Due to node mobility, any two nodes in the networks may not meet with each other for a long time and the transmission rate of data is at low level. It may also be possible that nodes may not last long because of the environment at dangers or power exhaustion. In such cases also, the delivery time of a message may exceed the lifetime of a sending node. Therefore, the routing protocols need to handle data loss and delay in transmission efficiently.

  • Long Queuing Delay In standard network, queuing time rarely exceeds a second as the packets are discarded immediately. In contrast, for DTN disconnection is common, the queuing time could be larger than that in standard networks. Therefore, nodes need to store messages for a long period of time.

  • Limited Resource DTN nodes have limited memory, processing capability and power, and thus they require designing of resource efficient protocols.

Generally routing in DTN is classified as deterministic routing and stochastic routing [15]. Stochastic routing protocols randomly floods the message to the node and has no knowledge about the network. Deterministic routing means we can predict the future movement of nodes and connection they made on the basis of some characteristics. The first proposed protocol was an epidemic protocol [16] based on flooding. Then the research is moved in the direction to reducing overhead introduced by flooding based protocols and also to maintain delivery probability. Most of the routing protocols are extensions of flooding and use historical information nodes for relay prediction.

In this paper, we differentiated DTNs protocols on the basis of the knowledge they used to predict the future relay node. DTN routing protocols are classified into four types: encounter based, time based, infrastructure based and hybrid & others. Encounter based routing protocol represents the categories of protocols which differentiate on the basis of encounter property. Encounter based protocols are further divided into flooding and prediction based. Flooding represents the category of protocols, which shows messages with zero knowledge of node’s encounter history. The prediction based routing consider encounter information as a measure of relay selection. The prediction of relay node is based on encounter information. This category defines the relay selection prediction on the basis of their time metric. Time metric represents the interval, duration, inter-meeting time or inter-contact time etc. Infrastructure based protocols can also be differentiated on the basis of how they use the location information of nodes like route information or measuring distance between nodes. Hybrid and others category belongs to those protocols which have more than one type of information for relay selection or does not belong to any category.

This paper theoretically analyzes some protocols that belong to each category on the basis of relay selection, copy control, buffer size and energy etc. It has been observed that in some cases encounter based prediction may not be a good assumption of relay, for example, there is a possibility that a node is highly mobile and encounters so many nodes within a short period of time and if a message is not sent in that spell then transfer of message can fail. This drawback of encounter based protocol introduces the time based relay selection. We also examine the performance of different protocols like epidemic [16], Spray aNd Wait (SNW) [17], Probabilistic ROuting Protocol using History of Encounters and Transitivity (PROPHET) [18], Encounter Based Routing (EBR) [19], Contact Duration Based Routing (CDBR) influenced from the Social Network Oriented and Duration Utility based Distributed Multi-copy routing (SEDUM) [20], Inter-Contact Routing (ICR) [21] for various factor such as number of nodes, buffer size, number of initial copies, message size etc. Further, we used basic ICR without implementing buffer management scheme. Their performance is also experimentally validated via metrics like overhead, delivery probability, goodput and number of dropped messages using THE ONE simulator of DTNs [22].

Thus, the major contributions of the paper are as follows:

  • We categorize state-of-the-art routing protocols on the basis of information they use for relay selection like encounter, time, infrastructure etc.

  • We also provide the theoretical comparison of different protocols on the basis of different parameters like relay selection, copy control, buffer size and energy with the analysis of their key characteristics.

  • Different protocols like epidemic, SNW, PROPHET, EBR, CDBR, ICR are compared experimentally on various factors such as number of nodes, number of initial copies, buffer size and message size on the basis of performance metrics like overhead, delivery probability, goodput and number of dropped messages.

The rest of the paper is organized as Sect. 2 provides the overview of the state-of-the-art DTNs routing protocols with their proposed categorization. Section 3 gives the theoretical as well as the experimental comparative study of some of leading routing protocols. Finally, Sect. 4 concluded the article with some future directions.

2 Overview of Routing Protocol in DTNs

In this section, we will discuss state-of-the-art routing algorithms proposed for DTNs as well as introduce some of the preliminaries. The Inter-Planetary Network (IPN) launched a project for establishing connectivity between randomly located nodes on different solar system planets. Then they realized IPN is a special case of challenges networks where due to excessive propagation delay and frequent disruption traditional routing protocols are failed. A significant amount of work has been done by researchers in the area of DTN routing [23,24,25,26,27,28]. Most of these algorithms collect the knowledge of nodes encounter, duration of encounter, relative location of nodes for better relay selection and try to reduce overhead in the network.

2.1 Types of DTN Routing

In this section, we will discuss the major body of the work done for DTNs routing by categorizing it under four categories. This section specifies previous work done in DTN routing algorithm on the basis of information they used for relay selection. As mentioned, the proposed classification is as follows:

  • Encounter based routing

  • Time based routing

  • Infrastructure based routing

  • Hybrid & Others routing

Figure 1 shows the categorization along with sub-categories of the routing protocols diagrammatically. Now, we will discuss some of the prevalent routing algorithms in each of the categories in detail.

Fig. 1
figure 1

Categorization of DTN routing

Full size image

2.1.1 Encounter Based Routing

Encounter based routing protocol represents the categories of protocols that are based on how the protocol uses the history of the encounter between the nodes to forward the messages. When two nodes come within the range of each other they are considered to have been encountered and history of such encounters is maintained at the node. In these protocols, nodes transfer information to each other without having complete knowledge of the network topology. However, an appropriate relay node can be selected by using the history of encounters.

This category can be further subdivided as:

  • Flooding Based Routing Flooding based category defines the routing protocols when there is zero knowledge about the encounter history. This means these protocols do not use any strategy for relay selection. The simplest approach used by this category is flood the message to the node that come into the contact without any prediction.

  • Encounter Prediction Based This category defines the relay selection prediction on the basis of the encounter history. Thus, these protocols harness the encounter behavior of the nodes to determine the best nodes to forward the message further.

Some of the seminal work in these sub-categories are discussed below.

2.1.1.1 Flooding Based Routing

Vahdat and Becker in [16] introduced an epidemic routing protocol. This protocol is a flooding protocol that creates multiple replicas of the message and transfers messages when a node come into the contact with other nodes. Epidemic protocol is a naïve technique of routing where high delivery probability can be achieved, but at the cost of huge amount of resource consumption like bandwidth, buffer space, power etc. Here, only pair-wise connectivity is required for eventual message delivery. Figure 2 illustrates the unknown message transfer in epidemic protocol between two nodes \( A \) and \( B \) that are in close proximity of each other. Node A transmits summary vector \( SV_{A} \) (which is a compact representation of all the messages being stored at \( A \)) to \( B \) which then replies with \( SV_{B} \) (which is the result of differing operation between \( SV_{B} \) and message buffered at \( B \)) and finally \( A \) transmits requested message to \( B \). Simulation results show that epidemic routing delivers all transmitted messages with unlimited buffer size. If there is no space in the buffer, FIFO scheme is employed to drop few messages from the queue. However owing to excessive number of copies of messages in the network, this algorithm is bound to consume huge amount of resources such are power, buffer capacity and bandwidth.

Fig. 2
figure 2

Message transfer in Epidemic protocol when two nodes A and B come into the range of each other [16]

Full size image

Another protocol is direct delivery (DD) which transfer message only when it comes in the contact of the destination node. Since, this protocol makes no intermediate forwarding of the message; it suffers from low delivery probability. Two-Hop-Relay [29] reproduces each message to first \( N \) encountered nodes; subsequently this message is transferred by these \( N \) nodes via direct encounter to destination node. Spray and wait [17] is another flooding based protocol. It uses the combined approach of epidemic and direct algorithm. It has two phases in the protocol– one is spray and other is wait. In the spray stage, the source node sprays replicas of the message to a predefined number of distinct relays, and then in the wait stage, these relays perform direct transmissions to the destination (if the message is not already transmitted in spray phase).

2.1.1.2 Encounter Prediction Based

First contact (FC) [23] routing protocol, chooses the next hop randomly from the entire existing neighbor, however if no such contact is available then the source node waits until the neighbor becomes available. This is one hop prediction based algorithm and all neighbors are assumed to be equally capable of forwarding the message to the destination. PROPHET protocol [18] is one of the most widespread encounter prediction based routing. It maintains transitive delivery prediction vector for the encountered nodes and then employ this knowledge for relay selection between nodes. For every node A, a probabilistic metric delivery predictability p(A, B). is computed which denotes the likelihood that the node A will successfully deliver message to every known destination B As, it can be observed in the given equation, delivery predictability increases with frequent contact and ages over time if no contacts are made.

$$ p\left( {A,B} \right) = \left\{ {\begin{array}{*{20}l} {p_{{\left( {A,B} \right)old}} + (1 - p_{{\left( {A,B} \right)old}} )p_{0} } \hfill & {if\;A\;and\;B\;meets} \hfill \\ {p_{{\left( {A,B} \right)old}} *\gamma^{\text{k}} } \hfill & {\text{otherwise}} \hfill \\ \end{array} } \right. $$

where \( p_{0} \in \left( {0,1} \right) \) is an initialization constant and \( \varUpsilon \in \left( {0,1} \right) \) is an aging constant, k is number of time units that have elapsed since the last time matrix was aged. A message dedicated to node D is to be forwarded to A or B is decided on the basis of delivery predictability; if p(A, D) > p(B, D) the next recipient of the message is A.

MaxProp [30] computes maximum delivery probability based on contact frequency and messages stored. In this algorithm, each node maintains a vector of total number of nodes in the network. On encounter of a node with another, these vectors are exchanged among them, which are then used for the estimation of shortest path to the destination node. Delegation forwarding (DF) [31] decides a threshold value, which is equal to the utility metric of the destination node. This protocol adopts a simplistic approach of transferring the messages to the node that have higher utility value as compared to certain threshold value instead of selecting relay node by comparing utility metrics of all the nodes.

Encounter Based Routing (EBR) [19] protocol can be considered as an extension of spray and wait protocol and is based on the past encounter experience of nodes. It predicts future rate of node encounters on the basis of past data. Every node in EBR maintains encounter value (EV) and current window counter (WC). Here, encounter value is past encounter rate and window counter is number of encounters in the current time window. It is observed that if a node is encountered more frequently to the destination then it has a better chance to deliver a message. In Fig. 3, an encounter between nodes A. and B. is shown where they are exchanging number of copies of messages according to their EV. Since, EV. of Node B. is three times greater than EV of node A. Therefore, node A sends three copies of the message out of four for to node B and on the other hand node B sendsnly two copies out of eight to node A. In this fashion, EBR limits the number of copies of a message in thneorkSpyropoulos et al. [17] proposed two phase algorithms namely Spray-and-focus (SNF) and Spray-and-wait(SNW). SNF belongs to time based routing where the source node sprays the message to few relay nodes that replicate the message to some other nodes using a single-copy utility-based scheme, instead of waiting for direct delivery to the destination. In SNW protocol, the source node sprays half of the copies to the connected node. When only one copy is left, protocol switches to the direct transmission phase. Fresher encounter search (FRESH) proposed by Dubois et al. [32] is based on recent encounters. The message is transferred by the sender to the node that has the most recent encounter with the destination node.

Fig. 3
figure 3

EBR routing scheme

Full size image

Social feature based routing algorithms [33,34,35,36,37,38,39,40,41] use the metrics that are based on encounter history, mobility pattern, hop distance of nodes etc. Thus, social feature based protocols are categorized according to the property they use and some of them fall under different categories explained further. Bulut and Szymanski (2010) [42] takes into account the notion of friendship between the nodes for proper delivery of messages in DTNs. It is based on the core idea that the nodes have strong friendship between them if they encounter each other frequently. Social pressure metric quantifies the quality of friendship and can be calculated from their encounter histories.

2.1.2 Time Based Routing

This category defines the relay selection prediction based on any time related metric such as the interval, contact duration, inter-meeting time or inter-contact time etc. In contact duration based routing (CDBR), the contact time duration between node A and node B is defined as a possible contact duration over a time period T given as:

$$ C\left( {A,B} \right) = \frac{1}{n - 1}\mathop \sum \limits_{B = 1,B \ne A}^{n} \frac{{D\left( {A,B} \right)}}{T} $$

where C(A, B) specifies the average probability that an arbitrarily selected node A in the network encountered node B with in time T. D(A, B) records the cumulative contact duration of nodes A and B up to time T [20].

Social network oriented and duration utility-based distributed multicopy routing protocol (SEDUM) achieves a high throughput in a dynamic setting as instead of using only contact frequency for the delivery utility in probabilistic routing, it also considers cumulative contact duration within time period [20]. Contact frequency f of node A to a node B is the number of times they encountered over a time period T. Duration utility \( DU\left( {A,B} \right) \) between nodes A and B measures the transmission capacity between them and is given as

$$ DU\left( {A,B} \right) = \frac{{\left( {\mathop \sum \nolimits_{k = 1}^{fT} t_{k} \left( {A,B} \right)} \right)}}{T} $$

where \( t_{k} \left( {A,B} \right) \) is the contact duration of kth encounter.

Uddin et al. [21] proposed Inter-contact routing protocol that was developed for the recurrent mobility pattern networks. It uses inter-contact delay and variance to evaluate the delivery utility of encountered nodes, which is further used to predict relay node in the network. Each vertex AB in inter-contact graph represents an encounter between nodes A and B and is associated with two routing tables, one at node A and other at node B. Considering that a node B comes in contact with node A, node B re-computes its optimal paths to each of the destination W and shares it with node A. For every neighbour \( L \in N_{B} \) set of neighbours of B, mean delay, variance and cost are computed as below and then the optimal path is determined.

$$ \begin{aligned} & delay_{L} = \delta \left( {BA \to BL} \right) + d_{B} \left( {BL \mapsto W} \right) \\ & var_{L} = \sigma^{2} \left( {BA \to BL} \right) + \sigma_{B}^{2} \left( {BL \mapsto W} \right) \\ & cost_{L} = delay_{L} + 1.65\surd var_{L} \\ & L^{*} = argmin_{{L \in N_{B} , L \ne A}} cost_{L} \\ \end{aligned} $$

where \( \delta \left( {BA \to BL} \right) \) is average delay lapsed at node B during encounter with nodes A and L and \( \sigma^{2} \left( {BA \to BL} \right) \) is delay variance. \( d_{B} \left( {BL \mapsto W} \right) \) is the path delay to destination \( W \) and \( \sigma_{B}^{2} \left( {BL \mapsto W} \right) \) is respective path delay variance

Later, the algorithm determines the delivery probability \( P_{C} \) through each of node A’s neighbours C as follows.

$$ \begin{aligned} & P_{C} = P\left\{ {0 < delay \le TTL /delay > 0} \right\} \\ & P_{C} = \frac{{\emptyset \left( {\frac{{TTL - delay_{C} }}{{\sqrt {var_{C} } }}} \right) - \emptyset \left( {\frac{{ - delay_{C} }}{{\sqrt {var_{C} } }}} \right)}}{{1 - \emptyset \left( {\frac{{ - delay_{C} }}{{\sqrt {var_{C} } }}} \right)}} \\ \end{aligned} $$

This protocol uses recurrent contacts and forms a network view to lessen the number of copies in the network. A multiple Inter-Contact Routing (ICR) protocol minimizes the energy required for communication. This protocol is designed for Disaster Response Network (DRN). Recurrence exists in DRN only because of the fact that movement of entities is not entirely random. There are some regularities such as medical supplies are delivered to evacuation camps; fire trucks originate at fire stations and police vehicles patrols given route. Therefore, there are a number of static points that exist, and which are used as message handover in this protocol. This classifies messages into two classes, namely “urgent” and “regular” and, therefore, it reserves energy for important traffic. ICR shows low overhead so it is good to use in energy constrained environment.

Spyropoulos et al. [43] proposed seek-and-focus protocol, which is based on latest encounter time. This protocol initially seeks a relay node based on delivery utility and then moves to focus phase if a better relay node with the latest encounter time for destination node comes into range. In Space and Time routing protocol [44] next hop selection is based on the information of the current and future neighbors. Further, in this protocol, space timing graph which depicts the mobility of the nodes is used.

Chen et al. [45] use last contact age and aggregate contact time to predict relay node. Age of last contact gives an idea about the closeness between nodes and aggregate contact time marks the importance of a node in the network. Niu ei al. [46] proposed a social feature based algorithm Predict and Spread (PreS) based on the mobility pattern of nodes. They use time homogeneous Markov chains to model the node mobility. Resource allocation routing for DTN paradigm (RAPID) [47] protocol models the routing problem as a resource allocation problem and attempts to optimize delivery delay of the message. To utilize the resources optimally, less number of copies of a message are forwarded in the network. Delay Tolerant Link State Routing (DTLSR) [48] extends the concept of link state routing to dynamic DTN setting. It uses the Dijkstra algorithm to calculate shortest path using expected delay (MEED) metric proposed by Jones et al. [24]. DTN hierarchical routing (DHR) [49] considers the static and mobile nodes in the recurrent scenario. To mitigate the problem dynamism in DTNs, DHR utilizes the time variant and time invariant hierarchical information.

2.1.3 Infrastructure Based Routing

This category represents the routing protocols, which use the infrastructure information for routing decisions. These protocols used location information of nodes, routes they follow, map information, moving direction of nodes etc. for better decision power to decide forwarding node. Now, we will discuss the algorithms developed based on distance and route information.

2.1.3.1 Distance Based

Distance based protocols use nodes location co-ordinates to compute distance between nodes and to analyze the direction of movement. MOvement of VEhicle (MOVE) protocol proposed by Lebrun et al. [50], uses the moving direction of nodes. MOVE considers a node which is moving towards the destination node as the relay node. As the movement of the vehicles are predictable in a vehicular network, MOVE protocol can be a good choice.

Distance Aware Epidemic Routing (DAER) [51] protocol is a distance based protocol that uses the distance from the destination to evaluate the utility metric. By limiting the number of copies in the network, this protocol induces less overhead. Mobility Prediction based Adaptive Data (MPAD) [52] also considers static and mobile both type of nodes. It considers the sink node are static nodes. This protocol uses the intersection of moving direction and transmission range of sink nodes for routing decision. Dhurandher et al. [53] proposed a history-based prediction routing (HBPR) protocol. It uses the moving direction of node as a metric for relay selection. Markov predictors and perpendicular distance of neighboring nodes from the line of sight of the source and destination are employed for making the decision. In another location based routing approach, each node contains the trace history file of movements of other nodes which helps in relay selection. It also has a beacon message facility that contains node ID, location and timestamp to inform other nodes about its presence.

2.1.3.2 Route or Map Based

These types of protocols utilized route or map information where nodes move. World Model Based Routing (WMBR) proposed by Becker and Schiele [54] which takes the advantage of world models to select relay node and find location of the destination node. It uses the fact that the mobile devices that are carried by the human beings tend to follow the recurrent pattern of motion. WMBR uses this information to create the user profiles, which further help in selection of relay nodes. Message ferrying (MF) [55] is another example of this category. This type of routing monitors the trajectory of nodes for performance improvement. It utilizes a special node that has some degree of storage capacity.

2.1.4 Hybrid and Others Routing

The protocols other than those under the specified categories and that utilized information of more than one category come under hybrid and others category. Predict and relay (PER) routing estimates the movement activities of node and filled transition matrix with probability to visit a place [56]. PER also uses time probability distribution matrix that is used to calculate the utility metric representing the probability of reaching the destination.

Mei and Stefa [57] intend to present an innovative reputation based incentive approach for routing. In this proposed scheme, disobedient nodes are recognized and further uninvolved in DTN routing. They developed two versions: (i) Epidemic forwarding (ii) Delegation forwarding. In epidemic forwarding, messages are transferred to primarily encountered nodes and in Delegation forwarding messages are transferred according to the node’s forwarding capabilities.

Simbet [33] is a protocol that applies similarity and betweenness properties for relay selection. Simbet falls in this category because between-ness is a property of distance (shortest path) and similarity measures the common neighbours.When a node A interacts with another node B, A calculates its relative similarity \( SimUtil_{A} \left( {\text{D}} \right) \) and betweenness utility \( BetUtil_{A} \) to the node B for message delivery to the destination node D as given by following equations:

$$ SimUtil_{A} \left( {\text{D}} \right) = \frac{{Sim_{A} \left( D \right)}}{{Sim_{A} \left( D \right) + Sim_{B} \left( D \right)}} $$

where \( Sim_{X} \left( Y \right) \) is the similarity between nodes X and Y. It represents the number of common nodes both the nodes X and Y have interacted. Given \( N_{X} \) and \( N_{Y} \) as the sets of nodes that came in contact with node X and Y respectively, \( Sim_{X} \left( Y \right) \) can be computed as:

$$ Sim_{X} \left( Y \right) = \left| {N_{X} \cap N_{Y} } \right| $$

Similarly, Betweeness utility \( BetUtil_{A} \) can be computed as

$$ BetUtil_{A} = \frac{{Bet_{A} }}{{Bet_{A} + Bet_{B} }} $$

Here \( Bet_{A} \) is betweeness centrality of node A which measures how important a node is for interconnection and is computed as:

$$ Bet_{A} = \mathop \sum \limits_{ij} \frac{1}{{CM_{ij}^{{\prime }} }};\;CM^{{\prime }} = CM_{A}^{2} *\left( {1 - CM_{A} } \right) $$

where \( CM_{A} \) is the contact history matrix of node A. Then it computes the SimBet utility of node A which is based on the weighted combination of both of the above mentioned utilities as given below:

$$ SimBetUtil_{A} \left( D \right) = \alpha SimUtil_{A} \left( D \right) + \left( {1 - \alpha } \right)BetUtil_{A} $$

Here α is a factor which shows the relative importance of the two utilities.

Neighbourhood contact history routing (NECTAR) [58] is a hybrid approach depended on hop count of pairwise encountered nodes and their encounter duration. Using these metrics, NECTAR calculates the neighborhood index. It also uses threshold to define message’s lifetime; below threshold value messages are transferred by epidemic approach otherwise neighbourhood index is used to replicate messages in a controlled manner. A data diffusion approach is suggested by Zhang et al. [59] make use of the “homophily” phenomenon omnipresent in social networks. Data diffusion schemes try to transfer data to each node in the network. To this end, they use the contact probability between the nodes. Basically, protocol applies friendship for selecting appropriate relay and homophily for electing suitable data item to buffer.

Relay selection in Context Aware Routing (CAR) [60] depends on Kalman filter based prediction method and utility. This prediction is based on the mobility of nodes. This protocol assumes that highly mobile nodes meet many other nodes. It also uses the past co-location of nodes with the assumption that it will meet the recipient again in future. To implement these issues, it uses degree of connectivity and future host co-location as follows. Change degree of connectivity of node A is represented as \( U_{{cd_{A} }} \left( t \right). \)

$$ U_{{cd_{A} }} \left( t \right) = \frac{{\left| {N_{A} \left( {t - T} \right) \cup N_{A} \left( t \right)} \right| - \left| {N_{A} \left( {t - T} \right) \cap N_{A} \left( t \right)} \right|}}{{\left| {N_{A} \left( {t - T} \right) \cup N_{A} \left( t \right)} \right|}} $$

Here \( N_{A} \left( t \right) \) represents the set of neighbours of node \( A \) at time \( t \) and \( N_{A} \left( {t - T} \right) \) represents the set of neighbours at time \( \left( {t - T} \right) , \) so that \( \left| {N_{A} \left( {t - T} \right) \cup N_{A} \left( t \right)} \right| \) shows the total number of nodes which appears in time interval \( \left[ {t - T,t} \right] \) and \( \left| {N_{A} \left( {t - T} \right) \cap N_{A} \left( t \right)} \right| \) shows the neighbours which appears in both set \( N_{A} \left( t \right) \) and \( N_{A} \left( {t - T} \right). \) Higher value of \( U_{{cd_{A} }} \left( t \right) \). represents that node A recently changed a large number of neighbours.The co-location \( U_{{coloc_{A,B} }} \left( t \right) \) is represented as follows:

$$ U_{{coloc_{A,B} }} \left( t \right) = \left\{ {\begin{array}{*{20}l} 1 \hfill & {if\;node\;A\;is\;colocated\;with\;B} \hfill \\ 0 \hfill & {otherwise} \hfill \\ \end{array} } \right. $$

These values are fed into Kalman filter predictors, which yield the predictions \( U_{{cd_{A} }} \left( t \right) \). and \( U_{{coloc_{A,B} }} \left( t \right) \) of these utilities at time t + T. These predictions are then combined into a single utility value using results from multi-criteria decision theory as follows:

$$ U_{A,B} = w_{{cd_{A} }} U_{{cd_{A} }} \left( t \right) + w_{{coloc_{A,B} }} U_{{coloc_{A,B} }} \left( t \right). $$

where \( U_{{A,{\text{B}}}} \) represents how good a node A is for delivering messages to B.

Sensor context-aware adaptive routing (SCAR) [61] is another hybrid type protocol, which takes advantage of context-aware routing (CAR) [60] with SNW. It uses utility metric of CAR in spray phase and only transfers message to the node if its utility value is higher than the threshold value. HiBOp [62] is another protocol that uses the same concept like CAR/SCAR. The only difference is that is also considers the potential of those nodes which have not been encountered. Meeting and Visit (MV) utilizes the pair wise encountered frequency onodes and a dedicated place of encounter [63]. Wang et al. [64] proposed two coding schemes for DTN: one is erasure coding and the other one is network schemes. Erasure coding encodes the original messages into number of blocks. Network Coding Scheme uses information theory approach. It combines some packets to create a new packet for sending it as a new packet. Minimizing Relay node and Hop count (MRH) algorithm searches the optimal path based on traffic requirement and hop count. Another form of MRH that uses shortest delay to destination is Minimizing relay node and delivery time (MRD) algorithm [65].

based Multicast Opportunistic Routing Protocol (Agent-based MORP) is a stateless approach for minimizing energy by reducing retransmission in the network [66]. It divides relay regions and provide routing route on demand. Resource management is very important in some of the DTN applications like disaster or disrupted networks. Gao et al. and Poersch et al. have worked in this direction. Gao et al. chooses some node that is easily accessed by other nodes in the network called network central location (NCL) nodes to store data. For selecting NCL nodes, probabilistic selection metric is used. Poersch et al. proposed a scheme in which nodes periodically promote their resources [67, 68].

Context information predication for routing in OppNets (CiPRO) [69] uses hash value to control messages. When two nodes are encountered, sender sends a control message to all first hop neighbours that have information about the name, address, workplace, nationality, hobbies etc. This information is used to find encounter probability of nodes towards the destination. Angelakis et al. [70] proposed a probabilistic routing protocol for intermittently connected mobile ad hoc network (PROPICMAN), which is based on the message delivery probability of nodes. The sender sends a message header to two hop neighbours and according to the information received their delivery probability is calculated. The prediction of delivery probability depends on nodes recurrent pattern with different time. Savita and Lobiyal [71] proposed a protocol based on location information of destination node. They also incorporate inter-contact delay for better delivery probability. Prioritized epidemic (PREP) proposed by Ramanathan et al. [72] resolves the disadvantage of epidemic protocol by prioritizing the messages. When load increases in the network, epidemic starts to drop important messages that affect the delivery ratio as it does not implement any scheme to prioritize messages. PREP determines the overhead cost to a destination and expiry time of message, which help in deciding which message is to be dropped.

LCTEE [73] protocol emphasizes on contact duration utility instead of frequency based utility. The contact duration utility between node A and B in time period T is given as

$$ U\left( {A,B} \right) = \mathop \sum \limits_{k = 1 }^{N} \frac{{t_{k} \left( {A,B} \right)}}{T} \in \left( {0,1} \right) $$

where \( t_{k} \left( {A,B} \right) \) is the contact duration of kth encounter between nodes A and B and N is the total number of encounters. Encounter node is selected as a relay node if it has higher utility value. LCTEE also uses location information of destination node to directionalize the message forwarding towards the destination node. Each message has limited number of copies to be transferred according to the contact utility of encountered node. The protocol also proposed an additional threshold based buffer management scheme to further improve the LCTEE performance. Savita et al. [73] claims that duration based protocols are able to revels communication in better ways as compare to frequency based protocols.

Table 1 summarizes the key characteristics of the routing protocols with the categories in which they fall.

Table 1 Characteristics of different category protocols
Full size table

3 Protocols Analysis and Simulation Results

In this section, we will compare the state-of-the-art algorithm theoretically as well as experimentally.

3.1 Theoretical Comparative Analysis

For proper examination of the different routing algorithms, they are theoretically compared on the basis of the following mentioned parameters:

  • Relay selection This characteristic specifies whether any criterion is used for relay selection or not. In Table 2, for an algorithm, if node selects a relay node on the basis of some criterion than we fill yes in the table otherwise fill no.

    Table 2 Comparison among the different category protocols
    Full size table

  • Routing decision For optimally deciding the relay nodes, algorithms use various parameters like Encounter probability, frequency, similarity between nodes etc.

  • Copy control As DTNs have a non-deterministic environment; multiple copies of messages are forwarded in the network for ensuring high delivery rate of the messages. However, this may lead to additional overhead, hence establishing a control replication mechanism becomes crucial. In Table 2, copy control column shows whether the protocols enforce any control on replication mechanism or not.

  • Buffer size Buffer management is crucial for overhead minimization. In column buffer size in Table 2, we have specified whether an algorithm seeks to limit the buffer size.

  • Energy consumption Since DTNs are energy-constraint networks, routing algorithms must consider the energy parameter in the design or evaluation.

From the Table 2, we can observe that for all routing algorithms, routing decision is made on the basis of certain criteria such as encounter history or topological information for enhancing their performance, except in flooding based approaches. Encounter based approaches use encounter history such as encounter frequency, average number of encountered nodes, and probability of encounter to predict future encounter opportunity. Time based approaches employ various time related criteria such as time elapsed between two meetings, the duration of the contact etc. Infrastructure based algorithms use topological informations such as location of the nodes, distance between the nodes, and the path followed etc. Hybrid approaches combine various time based, encounter based or infrastructure based metrics to make predictions.

Copy control mechanism is adopted by most of the algorithms except epidemic and prophet to utilize resources and to reduce overhead. It is very crucial to identify optimal number of copies as very less or very more number of copies may result in additional delivery delay with limited bandwidth. As DTNs are resource thrift networks, number of copies should be such that an effective trade-off between delivery performance and resource consumption is maintained.

Most algorithms used limited buffer size as unlimited buffer size is an ideal but unachievable scenario in case of DTNs. Thus, it becomes vital to prioritize messages in order of their impact on delivery probability. Effective queuing policy must be adopted to store important messages and drop the less important ones.

A DTN device needs to function with limited energy due unavailability of power suppliers easily. Energy is required for reception, storage and transmission of messages. Thus, the protocols should try to store and transmit few messages, and make less routing decisions to conserve energy. From Table 2, it is evident that there is need of energy efficient routing protocols to be designed.

3.2 Experimental Protocol Analysis

For our experimental analysis, we have evaluated the performance of the following protocols belonging to different suggested category such as Epidemic, Spray and Wait (SNW), Prophet, Encounter based routing (EBR), Inter Contact Routing (ICR), Contact Duration Based Routing (CDBR) that belong to different suggested category. We have used the simulator THE ONE (Opportunistic Network Environment). The simulation parameters considered for comparative analysis are summarized in Table 3.

Table 3 Simulation parameters
Full size table

We have used Random Map-Based Movement (MBM) and Shortest Path Map-Based Movement (SPMBM) for mobility models as specified in The ONE simulator default settings. Interpersonal communication can be established via Bluetooth interface (Transmit speed 250 kBps and Transmit range = 10 mts) or High speed long range interface (Interface type: Simple broadcast, Transmit speed 10 MBps and Transmit range = 1000 mts).

The performance of various algorithms is evaluated based on following metrics:

  • Delivery Ratio It is the ratio of the number of messages delivered to the number of messages generated. Higher the value of this metric, better the performance.

  • Overhead It is the ratio of how many message transmissions are required for delivery to the total number of messages delivered in the network. Overhead should be minimized for better performance.

  • Goodput Goodput is the average rate of packet reception over the experiment period. Higher value indicates better performance.

  • Dropped Messages The number of messages dropped from the buffer. For better performance, the number of dropped messages should be less.

Now, we will analyze how various factors such as number of nodes, buffer size, initial number of copies and message size, which affect the performance of the competing algorithm.

3.2.1 Number of Nodes

This simulation compared different protocols by measuring overhead, delivery ratio and other parameters with varying numbers of node. Figure 4a represents the delivery ratio with varying number of nodes. For smaller networks (less number of nodes), all the algorithms are giving almost comparable performance. For large number of nodes (> 60), it was being observed that SNW, Prophet and ICR are showing comparable performance among themselves and consistently outperform the other protocols. The performance of Epidemic deteriorates due to no relay selection and no control of messages copies as shown in Table 2. It is to be noted that as number of nodes for the fixed area increases, the probability of delivering of messages also increases, due to availability of more nodes for message transmission. Figure 4b shows the overhead incurred with respect to varying number of nodes. The overhead of the protocols also increases with the increase in the density of the network as there are more number of relayed messages. From the results, it is evident that Epidemic, Prophet and CDBR suffer from high overhead because they are relaying multiple copies of message in the network. On the other hand, SNW, EBR and ICR do not flood the network with multiple message copies, thus they have less overhead. Figure 4c shows the goodput obtained by all the six algorithms. It has been observed here also, that SNW, ICR and Prophet outperforms the other algorithms. It can be seen in Fig. 4d that as number of nodes increases, the number of dropped messages also increases rapidly for Epidemic, Prophet and CDBR algorithms as they relayed multiple message copies leading to more dropped messages. For SNW, EBR and ICR, the number of dropped messages remains low as the number of message copies in the network is low.

Fig. 4
figure 4

a Delivery ratio versus number of nodes b overhead versus number of nodes c goodput versus number of nodes d dropped messages versus number of nodes

Full size image

3.2.2 Buffer Size

In this simulation, we analyze all the above-mentioned performance parameters with varying buffer size as shown in Fig. 5. Figure 5a shows that as the increase in buffer size positively affects the performance of the routing algorithms. However, all protocols perform persistent after a defined buffer size (> 20 here). It can be observed that SNW and ICR algorithms are performing better than the other algorithms. The overhead for varying buffer sizes is shown in Fig. 5b. The overhead incurred in Epidemic and Prophet significantly reduce by the increase in the buffer size. SNW, ICR and CDBR are slightly affected by increase buffer size. However, there is very marginal improvement in the overhead in EBR protocol. Figure 5c shows goodput achieved by all the algorithms for varying buffer size. Similar to the delivery probability, goodput also improves by allocating larger buffer size. Here also, ICR and SNW outperform the other algorithms. Moreover, EBR and epidemic are also giving quite good performance in certain cases. In Fig. 5d the number of dropped messages are plotted against buffer sizes. It can be observed that the number of dropped messages are quite high for Epidemic and Prophet, whereas it is comparatively very low for EBR. We can see that when the size of the buffer is appropriately large, the number of messages dropped from the buffer remains almost constant for all the algorithms except ICR for which it further reduces. Overall, ICR and SNW are good performers with high delivery ratio and low overheads.

Fig. 5
figure 5

a Delivery ratio versus buffer size b overhead versus buffer size c goodput versus buffer size d dropped messages versus buffer size

Full size image

3.2.3 Initial Number of Copies

If we consider multi-copy protocols, they have high overhead because of huge number of copies. On the other hand, less number of copies adversely affect the delivery ratio. It shows the effect of number of copies in the performance of routing protocol. This simulation analyzes the value of overhead for varying number of copies in the network. As shown in Fig. 6, there has been a constant performance of Epidemic, Prophet, and CDBR with varying number of initial copies because these protocols have no copy control mechanism also suggested by Table 2. On the other hand, SNW and ICR have different values with varying number of initial copies. Figure 6a plots delivery ratio vs number of initial copies. In SNW and ICR, the delivery ratio is slightly improving with more number of initial copies. It can be observed that ICR and SNW protocols maintain decent delivery ratio as compared to other approaches. Figure 6b shows the relation between overhead and number of copies. In all the protocols, Epidemic and Prophet have high overhead incurred whereas EBR has achieved marginal overheads. Similar to delivery ratio, ICR and SNW have achieved better goodput than other competing algorithms as shown in Fig. 6c. In Fig. 6d, number of dropped messages are plotted against the initial number of copies. Akin to overhead, Epidemic and Prophet have dropped significantly larger number of messages and EBR has dropped comparatively low number of messages.

Fig. 6
figure 6

a Delivery ratio versus number of initial copies b overhead versus number of initial copies c goodput versus number of initial copies d dropped messages versus number of initial copies

Full size image

3.2.4 Message Size

In Fig. 7, we have examined the association of various parameters with varying message size. Figure 7a plots the delivery ratio for different message sizes. It is evident here that the performance of all the algorithms suffer to deliver the larger size messages. However, for smaller size messages, SNW and ICR outperform the other competing algorithms. As shown in Fig. 7b, overhead is reduced for Prophet and Epidemic algorithms as the message size is increased. As far as other algorithms are concerned, their overhead is not much affected by increasing message size. Figure 7c and d plot goodput and number of dropped messages against message size respectively. Goodput follows the trend similar to delivery ratio. For this metric also, ICR and SNW are the better performers than others. It is seen in the Fig. 7d that the number of dropped messages significantly reduces as the message size increases for Epidemic and Prophet. For SNW, CDBR and ICR, there is slight reduction in the dropped messages with increasing message size. However, the number of dropped messages in EBR does not seem to be visibly affected by increased message size.

Fig. 7
figure 7

a Delivery ratio versus message size b overhead versus message size c goodput versus message size d dropped messages versus message size

Full size image

4 Conclusions

Although an extensive research is dedicated to this domain, it still faces several open challenges. This article highlights the major findings and identifies some open research challenges to be taken as future research directions in this area. To this end, we first analyse the existing protocols theoretically. State of the art routing algorithms in DTNs use a prior knowledge such as encounter frequency, encounter duration, topological information etc. to predict reliable relay nodes. From the theoretical analysis, it has been concluded that only few protocols consider energy consumption aspect. We have also conducted extensive experimental analysis. It is challenging to compare the performance of various routing algorithms as all of them are designed for certain specific environment aiming to optimize different objectives. As mentioned, Epidemic obtains 100% delivery probability with infinite buffer size. However, in our simulation results, Epidemic loses its performance due to limited buffer size. SNW and ICR showed decent performance by achieving higher delivery ratio and goodput with less incurred overhead in the above-mentioned simulation settings. Plenty of research work has also contributed into further improving resource utilization (energy, buffer, bandwidth etc.) [12, 13, 74,75,76]. Moreover, we have observed that there is a dire need of protocols that consider the aspects like energy consumption, proper relay prediction and effective buffer management.