1 Introduction

A form of Delay/Disruption Tolerant Networks (DTNs) are those constructed out of vehicles, and thus have scheduled contacts [1] or a space–time graph [2–5]. Thus, their schedule allows other nodes to determine suitable point of contacts and critically, allow them to compute different paths that meet various criteria. For example, bundles can be delivered through routes with the minimum delay or hop count. Moreover, it is possible to determine the remaining time until a pair of nodes meets each other again. Also, contact duration can be computed, and thereby, allowing nodes to determine the amount of data that can be transferred in advance.

To date, the key assumption of past works that use a space–time graph assume nodes are pre-installed with the said graph. Consequently, their main research question is how to compute a suitable route that meets a given criterion over the space–time graph. However, in practice, nodes will have to gradually learn the mobility pattern of nodes upon each contact and update their space–time graph accordingly. For the space–time graph protocols described in [2, 4, 6–9], every node has a fixed mobility pattern for an unspecified time period, meaning the space–time graph is not dynamic. Hence, past works assume that the space–time graph is available in full at each node. Also, in both [8] and [10], all nodes are preloaded with a space–time graph and have a predictable mobility pattern, one that is repeated periodically or fixed for a given time period. This assumption, however, is unrealistic because nodes may have a different mobility pattern at different time periods, and are not likely to have a space–time graph upon system bootup. Moreover, the mobility patterns of nodes may have an expiration time. Although the nodes in [11] start with zero information and gradually learn the network topology, the employed routing algorithm will flood bundles throughout the network if a route is not present in the current space–time graph. This thus increases signalling overheads. Also, when a space–time graph is not complete, a detected route may not be optimal.

Henceforth, this paper presents a mobility based routing protocol (MBRP) whereby each node’s trajectory or mobility pattern has an expiration time. MBRP is the first hybrid routing protocol that uses a space–time graph and heuristics to route bundles. Also, when nodes have an incomplete space–time graph, unlike history based routing protocols [12] that rely on previous encounters to estimate future contacts, MBRP evaluates the reachability of encountered nodes based on recorded mobility patterns. Simulation results show that MBRP achieves up to 150 % improvement as compared to other well-known protocols such as EPIDEMIC, PROPHET, EBR, and MAXPROP.

The remainder of the paper is organized as follows. Section 2 reviews space–time routing protocols. Section 3 outlines the system model and key notations. Section 3 describes the problem. Section 4 presents the simulation set-up. This is then followed by obtained experimental results in Sect. 5. Finally, Sect. 6 concludes the paper.

2 System Model

Consider a DTN with v mobile nodes represented by the set \( \varvec{N} = \{ n_{1} , \ldots ,n_{v} \} \). Every node is equipped with a GPS unit and moves independently with a different speed and has a radio range of R. Nodes are assumed to have unlimited buffer. Also nodes have a semi-deterministic mobility pattern, meaning they visit a sequence of locations in a predictable manner for a given time period. The term “cycle” is used to denote a time period in which a node has a known mobility pattern. Consequently, if nodes repeat their cycle, we say they have a “periodic” mobility pattern. For example, a person may leave his/her home at 7:00 a.m., go to work and return home at 10 p.m. every day. He/she then repeats this routine every day; i.e., they have a cycle of 24 h. A node may also have “dynamic” mobility pattern where once a cycle finishes, a new with a different mobility pattern starts. As an example, the mobility pattern of a taxi changes depending on passengers. In this case, the taxi will set a new trajectory after picking up a new passenger. Nodes move on a grid with w × w cells. Each cell size is 2 × R. This means if two nodes are located in a cell, they are in communication range of one another. Let \( {\complement } = \left\{ {c_{1} , \ldots c_{i} , \ldots ,c_{m} } \right\} \) be the set of all cells, where \( m = \left| C \right| = \, w \times w \). As an example, a DTN that is overlayed on a grid of size 4 × 4 has 16 cells \( {\complement } = \left\{ {c_{1} , \ldots ,c_{16} } \right\} \). Another key assumption is that time is discrete and it is divided into slots of equal length, denoted as \( \varvec{t} = \left\{ {1, \ldots ,T} \right\} \). Moreover, nodes are synchronized in time, which can be achieved via GPS. Based on the space and time information, every node a records its mobility pattern \( MP_{a} \) as a sequence of ordered pairs \( (c_{i} ,t) \), where \( (c_{i} ,t) \) denotes cell i and time t. For example node a may have the following mobility pattern within five time slots t = 5, \( MP_{a} = \left\{ {(c_{5} ,1), (c_{4} ,2),(c_{6} ,3),(c_{2} ,4),(c_{1} ,5)} \right\} \). Node a is called the “owner” of \( MP_{a} \). In addition, each mobility pattern of node i has an expiration time \( EXP_{i} \). Let \( RT_{i} \) be the routing table of node \( n_{i} \). The notation \( RT_{i} \cdot MP_{a} \) is used to denote the mobility pattern of node a in node i’s routing table. Also, let L(t) be the set of contacts at time slot t.

To capture node contacts at different points in time as well as represent the routing table maintained by nodes, a space time graph is used, denoted as \( G(t) = (N,L(t)), \) where \( t = \left\{ {1, \ldots ,T} \right\} \). There are two types of links in a space time graph: spatial and temporal. A spatial link is a directed link between two nodes if they meet each other at the same time t. For example, \( n_{j} \) has a spatial link to \( n_{j} \) in G(3) if \( n_{j} \) is located in the same cell as \( n_{j} \) at time slot 3. This means a bundle can only be forwarded from one node to the other through a spatial link. Temporal links on the other hand capture the connection of the same node \( n_{j} \) across the (t-1)-th and t-th time slots. Every node is connected to itself in every slot, implying it can carry a bundle over all time slots. Nodes are located in one of the cells over time; i.e., \( MP_{{n_{3} }} = \left\{ {(c_{3} ,1), (c_{4} ,2),(v)} \right\} \).

3 The Problem

The main problem is how to forward bundles based on an incomplete routing table information while nodes are learning the space–time graph such that the delivery ratio is maximized and delay is minimized. If a source node generates a bundle for a given destination, it is faced with one of the following forwarding problems: (1) there is no route to a given destination. This means a source has to either wait until a route is available, which incurs delays that may exceed a bundle’s expiration time, or (2) there is at least one route to the given destination. Here, a source needs to decide whether to use available routes, which may be sub-optimal or wait for a better route in the future that has less delay. Notice that the maximum performance is achieved when every node has a complete space–time graph, which they can then use to compute the optimal route to any destinations.

4 Mobility Based Routing Protocol (MBRP)

MBRP considers the trajectory of nodes and the time of last contact between owners in order to minimize delay and maximize delivery ratio concurrently. In addition, MBRP is a quota protocol that limits the number of replicas for each generated bundle. This reduces the number of relay nodes required to deliver bundles. MBRP consists of the following two routing phases: space–time and heuristic. Briefly, in the former phase, each node constructs a space–time graph based on its recorded mobility pattern and contacts. Then, by applying a modified Dijkstra algorithm on the space–time graph, each node finds the fastest path. In the heuristic phase, nodes use recorded mobility patterns to predict subsequent contacts when their space–time graph is incomplete. Recall that a space–time graph is incomplete if a node’s space–time graph does not contain the mobility pattern of all nodes. Also, if at least one recorded mobility pattern expires, the space–time graph becomes incomplete.

Nodes maintain the following data structure. A node’s MP within a time period t is stored in a one dimensional array of size t. Every element i of the array indicates the geographical location of the node at time slot i. Each geographical location is assigned a unique integer number. Specifically, in a grid of size w × w where the grid coordinates x and y are between 1 and w, the unique integer number of each cell is calculated as follows.

$$ s(x, y) = (y - 1) \times w + x $$
(1)

The space–time graph can be represented by a three-dimensional matrix M. Each element (i, j, k) of matrix M represents the time of the k-th contact between nodes i and j. For example, if nodes i and j meet each other two times at t = 4 and t = 10, matrix M is updated to M(i, j, 1) = 4 and M(i, j, 1) = 10. Hence, the number of entries in matrix M is dependent of the number of contacts.

4.1 Space–Time Phase

In this phase, each node uses the space–time graph constructed using learned mobility patterns from each contact to forward bundles via the fastest path. In order to find the fastest path from a source to a destination node, the source node assigns a cost \( l_{i} \) to every link i as follows

$$ l_{i} = T_{i} - T_{i - 1} $$
(2)

where \( T_{i} \) represents the time that the i-th link occurs in the path. For example, node S is connected to node A at t = 1 and then node A is connected to node B at t = 4. In this case, assuming the current time is zero, the delay of the link is one, and the delay of the link between A and B is three. As a result, any bundles on the route from node S to B will take 1 + 3 = 4 time units. Formally, the cost of a route \( \omega \) is calculated as follows,

$$ {\text{Cos}}\;t_{\omega } = \mathop \sum \limits_{i = 1}^{{\left| {L_{\omega } } \right|}} l_{i} $$
(3)

where \( \left| {L_{\omega } } \right| \) represents the number of links on path \( \omega \). In order to store the cost of links, a three-dimensional matrix, called cost matrix (CM), is established where each element (i, j, k) represents the cost of the k-th contact between nodes i and j. Each discovered path may have a different cost. In order to find the fastest path, nodes use a modified Dijkstra algorithm based on the proposed cost function. Algorithm 1 presents the pseudo-code used by nodes to find the fastest path towards a given destination. As mentioned, node i considers the recorded mobility patterns to find contacts (line 3). If a contact is detected, the time of contact is added to matrix M (line 4). Based on matrix M and the proposed cost function (See Eq. 2), a node determines the CM matrix (line 9). Then, CM and a bundle’s destination ID are fed into Dijkstra() in order to find the fastest path \( {\mathcal{L}} \) towards destination d (lines 12–13). Lastly, a single copy of bundle \( M_{b} \) is forwarded over route \( {\mathcal{L}} \) (line 14).

figure c

4.2 Heuristic Phase

The aim of this phase is to route bundles when the space time graph is incomplete. The main idea is to take advantage of knowing the number of ordered pairs to estimate the reachability of nodes. Accordingly, the main observation is that when an encountered node has a large number of ordered pairs, it will be a good bundle carrier. Suppose that node i has recorded \( MP_{j} \) at time t. In this case, node i will mark an ordered pair of a mobility pattern \( MP_{j} \) as “expired” in \( RT_{i} \) if the second element of \( MP_{j} \), namely time, is less than or equal to t. Node i also marks the remaining ordered pairs of \( MP_{j} \) as “valid”, meaning their second element i.e., time, is greater than t. For example, in Fig. 1, when node A meets node B at t = 4, node A is not aware of any new contacts that nodes C and F have had after t = 2 and t = 1 respectively. In this example, node C meets node E at t = 3 but at t = 4 node A will not be aware of this contact given that the said contact occurs after the last contact with node C. Hence, when nodes A evaluates node B based on the number of valid ordered pairs, there are eight valid ordered pairs in node B’s routing table. Also, there is one valid ordered pair in node A’s routing table. Suppose that node A sends a number of replicas to node B. Based on Scenario 1 (see Sect. 4), the bundle is delivered at t = 5. Based on the second scenario, when node B meets node C at t = 6, there is one valid ordered pair in node B’s routing table; i.e., \( \left( {c_{2,1} ,5} \right) \) in \( MP_{A} \). In contrast, node C finds \( MP_{E} \) in its routing table with has two valid ordered pairs: \( (c_{5,3} ,4) \) and \( (c_{5,3} ,5) \).

Fig. 1
figure 1

Network performance when the number of sources and destinations is varied between 10 and 60, a delivery probability, b average delay, c overhead, d DAO

Full size image

In order to calculate the number of valid ordered pairs, every node i establishes a metric called “Contact Time” or \( CT_{j} \) for each encountered node j. This metric represents the last contact time between nodes i and j. For example, when nodes i and j meet each other, they set \( CT_{j} \) and \( CT_{i} \) to the contact time. In addition, they will also exchange \( MP_{j} \) and \( MP_{i} \). Upon contact, both connected nodes count the number of valid ordered pairs that belong to nodes with periodic and dynamic mobility patterns. Specifically, in terms of periodic mobility pattern, node i counts the number of valid ordered pairs as follows,

$$ PMP_{i} = \mathop \sum \limits_{{MP_{k} \in RT_{i} }} \left( {\left| {MP_{k} } \right| - RT_{i} \cdot CT_{k} } \right) $$
(4)

where \( \left| {MP_{k} } \right| \) indicates the total number order pairs of node k’s mobility pattern and \( RT_{i} \cdot CT_{k} \) represents the last contact time that node i recorded for node k. In words, Eq. 4 counts the number of ordered pair of all periodic mobility patterns in node i’s routing table since their last Contact Time up to the time that the cycle finishes. Recall that a cycle is a time period in which a node has a known mobility pattern.

As nodes with a dynamic mobility pattern, e.g., taxis, set a new trajectory in each cycle, these nodes will have more valid order pairs as compared to a node with periodic mobility pattern. Hence, the number of valid order pairs in a dynamic mobility pattern is dependent on the summation of all its cycles’ length, called CL. Specifically, the number of valid ordered pairs for the dynamic case at node i is calculated as follows,

$$ DMP_{i} = \mathop \sum \limits_{{MP_{k} \in RT_{i} }} \left( {CL - RT_{i} \cdot CT_{k} } \right) $$
(5)

In words, Eq. 5 counts the number of order pairs of all learned dynamic mobility patterns since their last Contact Time up to the time that the last cycle finishes. Here, CL is assumed to be equal to the time when the last recorded mobility pattern expires. Based on Eqs. 4 and 5, the total number of valid order pairs, \( VOP_{i} \), in the routing table of node i is computed as,

$$ VOP_{i} = DMP_{i} + PMP_{i} $$
(6)

The next issue is forwarding of bundles. A sender node specifies the number of replicas to be forwarded to an encountered node based on the ratio of the number of valid order pairs in its routing table and the encountered node’s routing table. For two nodes a and b, for the ith bundle \( M_{i} \) that is headed to destination d, node a sends the following number of replicas to node b,

$$ m_{i} \times \frac{{VOP_{b} }}{{VOP_{b} + VOP_{a} }} $$
(7)

where \( m_{i} \) is the available number of replicas for the ith bundle at node a. In words, using Eq. 7, node a compares the number of valid ordered pairs in its routing table and node b’s routing table. If \( VOP_{a} \) is smaller than \( VOP_{b} \), node a does not need to keep a large number of replicas for itself. As a result, if node b has a larger number of valid ordered pairs, more replicas are forwarded to node b.

For example, assume node a has 10 replicas of a bundle \( M_{1} \) and meets node b. Furthermore, assume node a with \( VOP_{a} \) = 10 and \( VOP_{b} \) = 90. Node a sends \( \frac{90}{90 + 10} \) = \( \frac{90}{100} \) of available replicas of \( M_{1} \) to node b. Therefore, node a forwards \( 10 \times \frac{90}{100} = 9 \) replicas of \( M_{1} \) to node b. Now assume \( VOP_{a} \) = 60 and \( VOP_{b} \) = 10, then \( \frac{10}{10 + 90} \)  = \( \frac{10}{100} \) of replicas of \( M_{1} \) to node b. In this case, node a forwards \( 10 \times \frac{10}{100} = 1 \) replica of \( M_{1} \) to node b.

Algorithm 2 presents the steps performed by the heuristic phase. The algorithm is executed by every node i whenever it encounters another node j (line 3). Node i calculates the ratio of \( VOP_{i} \) and \( VOP_{j} \) in order to forward a portion of a bundle’s replicas to node j (line 5–6).

figure d

5 Evaluation

We have evaluated MBRP using the Java based simulator Opportunistic Network Environment (ONE) [13]. This simulator is able to generate vehicle movements using different mobility models [14–16] where nodes can have different cycle lengths. A deterministic network is created where nodes can have a periodic or dynamic mobility pattern in different cycles. MBRP is compared against four well-known protocols. Namely, EBR [17], EPIDEMIC [18], MAXPROP [19], PROPHET [20] and Optimal [2].

Nodes have a periodic mobility pattern and move in an area of approximately 5 × 3 km2 in downtown Helsinki, Finland. Nodes repeat their pattern every 12 h. All experiments adopt ONE’s default settings, whereby 64 % of nodes are pedestrians that move with a speed between 0.5 and 1.5 m/s. The other 32 % are vehicles that move with a speed ranging from 2.7 and 13.9 m/s. Other nodes are trams that move with a speed between 7 and 10 m/s. Note that all nodes have a fixed transmission range of 20 m and they also have a buffer size with a capacity of 20 bundles, except trams, where they have the capacity to store 500 bundles. In all experiments, the bundle size is 100 KB. All nodes have a transmission speed of 250 kBps except trams, which has a transmission speed of 10 MBps. Note, we assume that trams have the ability to store more bundles and have a higher bandwidth as compared to other nodes. This is because, in reality, trams carry a large number of passengers and a large amount of data may be transmitted. Also, based on the benchmark setting of the ONE simulator, trams have a higher transmission speed and larger buffer space than other types of nodes. Each simulation lasts for three simulated cycles, i.e., 36 h, and each data point is an average of 10 runs. In all these experiments, the number of sources/destinations is varied from 10 to 60 in increment of 10.

The routing protocols are evaluated using three well-known performance metrics, namely (1) delivery probability, (2) overhead, and (3) average delay. However, as mentioned in [17, 21], many protocols optimize one metric at the expense of another. For this reason, this work also uses a composite metrics namely, DAO; all of which are introduced by the authors of [17]. This composite metric provides a ratio between delivery probability and conventional metrics. Specifically, Eq. (8) defines DAO that scales the performance of a protocol based on delivery probability (DP), average delay (AD) and overhead (OR).

$$ DAO = DP \times \frac{1}{AD} \times \frac{1}{OR} $$
(8)

5.1 Periodic Mobility Patterns

Figure 1 shows the performance of a DTN where every node has a fixed mobility pattern for each cycle and contacts occur periodically. Nodes do not change their trajectory. This means the space–time graph will reach a steady state once nodes record all mobility patterns. Figure 1a shows that MBRP delivers up to 16 % more bundles as compared to EBR. This is because MBRP is guaranteed to deliver a bundle if a route is discovered. In addition, when there is no route towards a destination, MBRP estimates the future reachability of nodes to select a bundle’s next hop. We see that EBR outperforms MAXPROP, PROPHET and EPIDEMIC. The reason is because EBR limits the number of replicas and hence, there are fewer number of dropped bundles as compared to flooding protocols. However, EBR may fail to deliver a bundle if the destination is located in a low density area. Figure 1a also shows that the Optimal protocol has up to 9 % improvement as compared to MBRP. This is because nodes using MBRP may have an incomplete space–time graph.

In terms of delay, as shown in Fig. 1b, we see that MBRP delivers bundles up to 35 % quicker than MAXPROP. Recall that MBRP sends bundles via the fastest discovered path. Consequently, bundles are delivered on a path with much smaller delays as compared to MAXPROP, PROPHET, and EBR. In terms of overhead, Fig. 1c shows that MBRP and EBR use a small number of relays due to the finite number of replicas. This is because MBRP uses the space–time phase where only a single copy is forwarded and bundle is guaranteed to be delivered. This results a high delivery ratio and low overhead. Lastly, Fig. 1d shows that MBRP performs 150 % better than EBR in terms of DAO.

5.2 Dynamic Mobility Patterns

In this set of experiments, a node changes its mobility pattern once it reaches a random POI. Figure 2a shows MBRP is up to 6 % better than EBR in terms of delivery ratio. Although nodes only have a valid mobility pattern for a given time period, the space–time phase may find a route towards a destination before their recorded mobility patterns expire. This causes MBRP to outperform EBR in terms of delivery ratio. As we can see from Fig. 2a, when the number of source/destination nodes increases, MBRP delivers up to 94 % of bundles. This is because when the number of source/destination nodes increases, the probability that a sender node has a destination’s mobility pattern increases. In other words, MBRP enters the space–time phase frequently. Figure 2b shows that MBRP reduces delays by up to 25 % as compared to MAXPROP. As mentioned, the space–time phase reduces delays as bundles are forwarded via the fastest discovered path. As shown in Fig. 2b, when the number of sources and destinations increases, due to the use of the space–time phase, the delivery delay of bundles decreases. In terms of overheads, Fig. 2c shows that MBRP incurs 14 % less resources usage as compared to EBR. This is because nodes using MBRP only forwards a single copy of each bundle. Finally, Fig. 2d depicts that MBRP performs up to 100 % better than EBR.

Fig. 2
figure 2

Network performance when the number of sources and destinations is varied between 10 and 60, a delivery probability, b average delay, c overhead, d DAO

Full size image

5.3 Mixed Mobility Patterns

Lastly, we consider the scenario where 20 % of nodes have a periodic mobility pattern and the remaining nodes have dynamic mobility patterns. Specifically, 20 % of the nodes have a fixed routing table. Figure 3a shows that compared to EBR, MBRP achieves 7 % improvement in delivery ratios. Also, MBRP’s performance is 5 % less than the optimal protocol. In terms of delay, Fig. 3b shows that MBRP delivers bundles up to 15 % quicker compared to MAXPROP. Figure 3c shows that MBRP consumes less resource as compared to PROPHET. This is because the number of replicas is limited in MBRP. Compared to EBR, Fig. 3c also shows that MBRP has 21 % reduction in overheads. This is due to its use of the space–time phase that forwards a single copy of bundles. Also, in terms of DAO, Fig. 3d shows that MBRP performs up to 105 % better than EBR.

Fig. 3
figure 3

Network performance when the number of sources and destinations is varied between 10 and 60, a delivery probability, b average delay, c overhead, d DAO

Full size image

6 Conclusion

This paper has proposed MBRP, a protocol that considers an incomplete space–time graph to send a single copy of each bundle over the fastest discovered path. In addition, as initially the space–time graph may not be complete, they evaluate the reachability of encountered nodes based on the number of valid (remaining) order pairs of encountered nodes that are recorded in their routing table in order to send a proportional number of replicas to them. Simulation results, over a DTN comprising of nodes with dynamic and periodic mobility patterns show that compared to EBR, MBRP achieved up to 105 % improvement in a service quality metric called DAO which comprises of delivery, delay and overhead.