Sage Journals: Discover world-class research

Abstract

Multicopy forwarding schemes have been employed in delay tolerant network (DTN) to improve the delivery delay and delivery rate. Much effort has been focused on reducing the routing cost while retaining high performance. This paper aims to provide an optimal joint expected delay forwarding (OJEDF) protocol which minimizes the expected delay while satisfying a certain constant on the number of forwardings per message. We propose a comprehensive forwarding metric called joint expected delay (JED) which is a function of remaining hop-count (or ticket) and residual lifetime. We use backward induction to calculate JED by modeling forwarding as an optimal stopping rule problem. We also present an extension to allow OJEDF to run in delay constrained scenarios. We implement OJEDF as well as several other protocols and perform trace-driven simulations. Simulation results confirm that OJEDF shows superiority in delay and cost with acceptable decrease of delivery rate.

1. Introduction

A delay tolerant network (DTN) [1] is a sparse mobile multihop network where a complete path from the source to the destination may not exit most of the time. A DTN can be viewed as a collection of time-varying and separate node clusters. Under this condition, conventional mobile ad hoc network (MANET) or wireless sensor network (WSN) routing will become impractical because of frequent disruption and high packet loss. The Delay-Tolerant Networking Research Group (DTNRG) [2] is concerned with architecture and relevant protocols in order to provide interoperable communications with and among extreme and performance-challenged environments. In DTNs, the messages can be forwarded asynchronously using the store-carry-forward routing mechanism which relies on the contact opportunities between nodes [3].

Routing in DTN has been an active research area in recent years. Epidemic [4] exchanges the copies whenever contact occurred within pair of nodes. Epidemic can guarantee the maximized delivery rate and the minimized end-to-end delay under ideal conditions. However, unrestrained flooding is impractical because of huge consumption of energy, buffer and bandwidth. Much literature has been focused on reducing the number of copies of each message while retaining a high routing performance. Previous works proposed a variety of metrics, including movement trend [5], delivery probability [6], encounter frequency [7], the distance to destination [8], end-to-end delay [9], energy [10], signal to noise ratio (SNR) [11], and comprehensive utility [12]. These metrics are used to make decision for forwarding in order to optimize certain performance such as expected delay and delivery rate.

In this paper, we propose optimal joint expected delay forwarding whose main idea is similar to that of optimal probabilistic forwarding (OPF) [13]. This means that optimal stopping rule [14] is used again. Different from maximizing the delivery rate in OPF, we concentrate on optimizing the expected delay of each message with the constraint on the maximum of copies per message. The problem is how to forward the copies of each message in each discrete time slot in order to minimize the expected delay when the number of copies is given. To solve this problem, we firstly employ the comprehensive dynamic forwarding metric called joint expected delay (JED) which is a function of two important states of a message copy: remaining hop-count and residual lifetime. Then, we propose the forwarding rules to decide whether to forward the copies. Based on the hop-count constraint forwarding scheme, we propose a general ticket constraint OJEDF which can be viewed as a development of Spray and Wait [15] with special spray metric. We also extend OJEDF in delay constrained scenarios.

We performed simulations using St. Andrews encounter trace [16] and Illinois encounter trace [17] to evaluate the routing performance of OJEDF against several DTN routing protocols, including Spray and Wait, ProphetV2 [7], and Epidemic, in terms of average delay, delivery rate, and the number of forwardings for each message. Simulation results confirmed that OJEDF improves the average delay and cost with acceptable decrease of delivery rate.

This paper is organized as follows. Section 2 summarizes the related works. Section 3 introduces preliminaries on optimal joint expected delay forwarding and presents the motivation and assumption of OJEDF. Section 4 proposes the calculation algorithms of our delivery metric JED and optimal forwarding rule in hop-count constraint OJEDF and ticket constraint OJEDF, respectively. Section 5 proposes an extension of OJEDF which makes it work in delay constrained scenarios. Section 6 presents our simulation methods and results. Finally, the paper is concluded in Section 7.

2. Related Works

The single-copy routing protocols such as MobiSpace [18] and CAR [19] are energy efficient but always have large delay. Due to uncertainty in nodal mobility and network partition, DTN routing algorithms usually spawn and keep multiple copies for the same message in different nodes. Epidemic is the first distribution routing protocol for DTN, and it gains good delivery delay. However, Epidemic wastes a lot of energy and suffers from severe contention.

Much literature has aimed to balance the delay and energy. Some restricted flooding or spray mechanisms disseminate a small number of message copies to potential relay nodes, and then each copy finds routing to the destination independently. These mechanisms can obtain better delay performance without a lot of resource consumption.

Spray and Wait is a multicopy routing without any routing knowledge. Spray and Wait combines the speed of Epidemic routing with the simplicity and thriftiness of direct transmission. This mechanism “sprays” a number of copies into the network and then “waits” till one of these nodes meets the destination. Spray and Focus [20] replaced the direct transmission in wait phase with utility-based single-copy strategy and proposed the utility transfer mechanism to disseminate the history contact information. Thrasyvoulos was absorbed in utility-based spraying [21] and proposed three potential utility functions: last-seen-first spraying, most-mobile-first spraying, and most-social-first spraying. Jindal proposed distance utility-based spray strategy [22] which utilized dynamic programming to calculate the optimal relay node. An adaptive distributed spray mechanism (AMR) was performed in [23] which determined the depth of spray tree by relay nodes. But AMR is just efficient in random waypoint model and sometimes can produce at most $M / 2$ copy redundancy (M is the number of nodes). In addition, theoretical analyses of expected delay in single-copy case and multicopy case were proposed in [24, 25], respectively.

Different from Spray and Wait, delegation forwarding [26] forwards the messages based on different delivery probability metrics. Delegation forwarding maintains a forwarding threshold τ when contact of node pairs occurred. Forwarding threshold indicates the quality of node such as cost, delivery rate, and average delay. RAPID [27] treats DTN routing as a resource allocation problem that translates the routing metric into per-packet utilities such as minimizing average delay, minimizing missed deadlines, and minimizing maximum delay.

Some routing protocols aimed to achieve the desired performance with different levels of prior knowledge about the network. OPF [28] was proposed to maximize the delivery rate of each message when mean inter-meeting times between all pairs of nodes were known. Cyclic MobiSpace [29] assumes that each node has full contact information to other nodes, and it optimizes minimum expected delay.

3. Preliminaries

3.1. Hop-Count Constrained Forwarding and Ticket Constrained Forwarding

We consider two constraint patterns related to the number of message copies: hop-count constrained forwarding and ticket constrained forwarding.

In hop-count pattern, a maximal remaining hop-count K was defined in source node. The remaining hop-count decreased progressively when forwarding occurred. The calculation of the remaining hop-count for the copies of each message is independent. Figure 1 depicts the forwarding process with $K = 3$ in node A. Ticket pattern uses the total number of copies L which can be redistributed in each forwarding. Figure 2 depicts the ticket constrained forwarding process with $L = 8$ in node A using binary spray [9].

Figure 1

An illustration of hop-count constrained forwarding with $K = 3$ .

Figure 2

An illustration of ticket constrained forwarding with $L = 8$ .

3.2. Motivation

Many routing protocols in DTNs forward the messages based on the specific routing metrics by means of comparing the direct forwarding qualities of node pairs. However, such forwarding strategy ignores the time dimensionality which is an important character in DTNs. In fact, the forwarding decision only relied on the direct forwarding qualities of node pairs and cannot stand for the optimal choice in whole time dimensionality of delivery.

In this paper, we optimize the expected delay of each message based on the comprehensive forwarding metric ${JED}_{i, d, K, Tr}$ for each copy in i for destination d with remaining hop-count K (or L tickets) and residual time-to-live Tr. We use backward induction to calculate JEDs by modeling forwarding as an optimal stopping rule problem. Our contributions are as follows. (1)

We propose a comprehensive forwarding metric JED which is related to the time dimensionality and the number of copies for each message.

(2)

We propose the backward induction algorithms to calculate JEDs with hop-count constraint and ticket constraint, respectively.

(3)

We solve the delay restraint optimal cost forwarding by the extension of OJEDF.

3.3. Assumption

To model our optimal forwarding problem as an optimal stopping rule problem, we have the following assumptions. (1)

Like other probabilistic forwarding protocols, nodal mobility exhibits long-term regularities and each node knows the matrix $M_{n \times n}$ which contains the mean inter-meeting times ${MIT}_{i, j}$ between all pairs of nodes ${i, j}$ . This matrix can be estimated from contact history.

(2)

Time dimensionality in whole forwarding process is discrete. OJEDF employs a discrete residual time-to-live Tr with time slot size U for each message copy. So we can state the next time-slot as $Tr - 1$ .

(3)

JEDs are exponentially distributed. Therefore, the JED of two copies with ${JED}_{1}$ and ${JED}_{2}$ can be calculated by

\begin{matrix} \frac{1}{1 / JE D_{1} + 1 / JE D_{2}} . \end{matrix}

(1)

Proof.

Let ${JED}_{1} = 1 / a$ and ${JED}_{2} = 1 / b$ , and let the joint probability density function be $f (x) = a e^{- a x} \cdot b e^{- b x}$ . Then, the expected value is

\begin{array}{l} \begin{array}{l} E (X) = \int_{- \infty}^{+ \infty} x f (x) d x = \int_{0}^{+ \infty} x a b e^{- (a + b) x} d x \\ = - \frac{a b}{a + b} \int_{0}^{+ \infty} x d e^{- (a + b) x} \\ = - \frac{a b}{a + b} x e^{- (a + b) x} |_{0}^{+ \infty} + \int_{0}^{+ \infty} e^{- (a + b) x} d x \\ = - \frac{1}{a + b} e^{- (a + b) x} |_{0}^{+ \infty} = \frac{1}{a + b} = \frac{1}{1 / JE D_{1} + 1 / JE D_{2}} . \end{array} \end{array}

(2)

Similarly, the meeting probability of two nodes in any time slot with size U can be estimated by

\begin{matrix} P_{i, j} = 1 - \exp (- \frac{U}{{MIT}_{i, j}}) . \end{matrix}

(3)

4. Optimal Joint Expected Delay Forwarding (OJEDF)

4.1. OJEDF with Hop-Count Constraint

Without loss of generality, we consider a copy in node i with destination d, remaining hop-count $K (K \geq 1)$ , and residual time-to-live Tr. Upon meeting with $j, i$ can either forward the copy to j or not. Since we assume the forwarding process is discrete, the JED in the next time slot can be stated as ${JED}_{i, d, K, Tr - 1}$ in no forwarding case. As an alternative, the copy can be forwarded and is logically regarded as being replaced by two new copies, both of which have $K - 1$ remaining hop-count. If the copy is forwarded, the JED of the copy in node j will be ${JED}_{j, d, K - 1, Tr - 1}$ and that of the copy in node i will become ${JED}_{i, d, K - 1, Tr - 1}$ . The joint JED can be calculated using formula (1). Consequentially, the forwarding option depends on the comparison of ${JED}_{i, d, K, Tr - 1}$ and the joint JEDs of ${JED}_{i, d, K - 1, Tr - 1}$ and ${JED}_{j, d, K - 1, Tr - 1}$ . The copy is forwarded only if

\begin{matrix} {JED}_{i, d, K, Tr - 1} > \frac{1}{1 / {JED}_{i, d, K - 1, Tr - 1} + 1 / {JED}_{j, d, K - 1, Tr - 1}} . \end{matrix}

(4)

We only consider unicast forwarding. When a node contacts with several nodes at the same time slot, the copy is forwarded to the node j which has the minimum ${JED}_{j, d, K - 1, Tr - 1}$ .

The forwarding metric ${JED}_{i, d, K, Tr}$ equals the sum of the weighted expected delay in forwarding case and not forwarding case. In forwarding case, node i has the opportunity to meet the relay node $j, K, \dots$ with probability $P_{i, j}$ , $P_{i, K}, \dots$ , respectively. So the joint expected delay that node i meets one of the nodes $j, K, \dots$ in time-slot Tr and then forwards the copy to it is

\begin{array}{l} P_{i, j} \times \frac{1}{1 / {JED}_{i, d, K - 1, Tr - 1} + 1 / {JED}_{j, d, K - 1, Tr - 1}} + (1 - P_{i, j}) \\ \times P_{i, K} \times \frac{1}{1 / {JED}_{i, d, K - 1, Tr - 1} + 1 / {JED}_{k, d, K - 1, Tr - 1}} + \dots . \end{array}

(5)

If node i did not meet any relay node, the copy was kept in node i with joint expected delay

{JED}_{i, d, K, Tr - 1}

and probability

P_{i, N}^{'} = 1 - P_{i, j} - (1 - P_{i, j}) \times P_{i, K} - \dots

. Algorithm 1 shows the calculation of

{JED}_{i, d, K, Tr}

in hop-count based forwarding using the backward induction.

Algorithm 1: The calculation of ${JED}_{i, d, K, Tr}$ in hop-count based forwarding.

$(1)$ ${JED}_{i, d, K, Tr} ∶ = 0$

$(2)$ $P_{i, N}^{'} ∶ = 1$

$(3)$ for each relay node j ( $j \neq i$ ∩ $j \neq d$ ){

$(4)$ $D_{i, j} = {JED}_{i, d, K - 1, Tr - 1} \times {JED}_{j, d, K - 1, Tr - 1}$ /( ${JED}_{i, d, K - 1, Tr - 1} + {JED}_{j, d, K - 1, Tr - 1}$ )}

$(5)$ Append all $D_{i, j}$ in a priority queue Q in ascending order

$(6)$ While (Q is not empty){

$(7)$ if ( $j ∶ = ServeQueue (Q)$ and $D_{i, j} < {JED}_{i, d, K - 1, Tr - 1}$ ){

$(8)$ ${JED}_{i, d, K, Tr} ∶ = {JED}_{i, d, K, Tr} + P_{i, N}^{'} \times P_{i, j} \times D_{i, j}$

$(9)$ $P_{i, N}^{'} ∶ = P_{i, N}^{'} - P_{i, N}^{'} \times P_{i, j}}}$

$(10)$ ${JED}_{i, d, K, Tr} ∶ = {JED}_{i, d, K, Tr} + P_{i, N}^{'} \times {JED}_{i, d, K, Tr - 1}$

Specially, the copy only can be delivered to the destination when the remaining hop-count $K = 0$ , and we set ${JED}_{i, d, 0, Tr} = {MIT}_{i, d}$ . For each pairs of nodes ${i, d ∣ i = d}$ , we let ${JED}_{i, d, K, Tr} = δ$ (δ is a very small number such as $10 e - 6$ ) in order to make the formula (1) calculable.

In our OJEDF, Tr is only used to define the finite upper bound on the number of stages which is essential for modeling OJEDF as optimal stopping rule problem. So it is feasible to calculate the JEDs of the previous stage using the backward induction method even when ${JED}_{i, d, K, Tr} > Tr$ . This implies that the OJEDF rule depicted in formula (4) is valid when ${JED}_{i, d, K, Tr} > Tr$ . However, this kind of JEDs cannot be employed in delay constrained scenarios which we will introduce in Section 5 since it is impossible to deliver the message within residual time-to-live.

As an example, a matrix $M_{8 \times 8}$ including discrete mean inter-meeting times (normalized by time-slot size U) between each pair of nodes was defined in Table 1. The JEDs calculated by OJEDF using Algorithm 1 were shown in Figure 3 with $K = 3$ (enough to forward each message to all nodes), maximum $Tr = 30$ , $i = 0$ , $d = 1$ , and $U = 1$ . In Figure 3, the JEDs are decreased with increasing K and Tr. It means that a message has smaller expected delay when more remaining hop-count and residual time can be used to accomplish delivery. As a result, we can make forwarding options based on formula (4) when node i meets potential relay nodes with different remaining hop-count K and residual time-to-live Tr. Figures 4(a), 4(b), and 4(c) show the forwarding options based on OJEDF with $K = 1$ , $K = 2$ , and $K = 3$ . We can see that the message forwarding tends to be more cautious when the remaining hop-count declines gradually along with the forwarding process.

Table 1

The mean intermeeting times matrix.

	0	1	2	3	4	5	6	7
0	0	20	33	42	20	50	60	35
1	20	0	45	50	30	40	25	10
2	33	45	0	30	40	55	60	20
3	42	50	30	0	60	45	37	27
4	20	30	40	60	0	35	29	100
5	50	40	55	45	35	0	23	80
6	60	25	60	37	29	23	0	26
7	35	10	20	27	100	80	26	0

Figure 3

The JEDs calculated by OJEDF in hop-count based forwarding.

Figure 4

(a) Forwarding options based on OJEDF in hop-count based forwarding with $K = 1$ . (b) Forwarding options based on OJEDF in hop-count based forwarding with $K = 2$ . (c) Forwarding options based on OJEDF in hop-count based forwarding with $K = 3$ .

4.2. OJEDF with Ticket Constraint

Another copy constraint pattern is ticket constraint which is more precise than hop-count constraint since it replaces the remaining hop-count K with the number of tickets L. Without loss of generality, we consider a copy in node i with destination d, the number of tickets $L (L > 1)$ , and residual time-to-live Tr. When node i meets any relay node j, the forwarding option depends on ${JED}_{i, d, L, Tr - 1}$ and the joint JED of ${JED}_{i, d, L 1, Tr - 1}$ and ${JED}_{j, d, L 2, Tr - 1}$ $(L 1 + L 2 = L)$ . We define $D_{i, j_MIN} = \min (1 / (1 / {JED}_{i, d, L 1, Tr - 1} + 1 / {JED}_{j, d, L 2, Tr - 1}))$ , and the copy is forwarded only if ${JED}_{i, d, L, Tr - 1} > D_{i, j_MIN}$ .

Algorithm 2 shows the backward induction algorithm to calculate ${JED}_{i, d, L, Tr}$ for ticket based forwarding. Specially, the copy only can be delivered to the destination when the number of tickets $L = 1$ , and we set ${JED}_{i, d, 1, Tr} = {MIT}_{i, d}$ .

Algorithm 2: The calculation of ${JED}_{i, d, L, Tr}$ in ticket based forwarding.

$(1)$ ${JED}_{i, d, L, Tr} ∶ = 0$

$(2)$ $P_{i, N}^{'} ∶ = 1$

$(3)$ for each relay node j ( $j \neq i \cap j \neq d$ ){

$(4)$ $D_{i, j} = {JED}_{i, d, L 1, Tr - 1} \times {JED}_{j, d, L 2, Tr - 1}$ / $({JED}_{i, d, L 1, Tr} + {JED}_{j, d, L 2, Tr - 1})}$

$(5)$ Append all $D_{i, j}$ in a priority queue Q in ascending order

$(6)$ while (Q is not empty){

$(7)$ if ( $j ∶ =$ ServeQueue(Q) and $D_{i, j} < {JED}_{i, d, L, Tr - 1}$ ){

$(8)$ ${JED}_{i, d, L, Tr} ∶ = {JED}_{i, d, L, Tr} + P_{i, N}^{'} \times P_{i, j} \times D_{i, j}$

$(9)$ $P_{i, N}^{'} ∶ = P_{i, N}^{'} - P_{i, N}^{'} \times P_{i, j}}}$

$(10)$ ${JED}_{i, d, L, Tr} ∶ = {JED}_{i, d, L, Tr} + P_{i, N}^{'} \times {JED}_{i, d, L, Tr - 1}$

We use the same matrix defined in Table 1. The JEDs calculated by OJEDF in ticket based forwarding were shown in Figure 5 with $L = 4$ , maximum $Tr = 30$ , $i = 0$ , and $d = 1$ . As a result, we can make forwarding options based on formula (4) when node i meets potential relay nodes with the different number of ticket L and residual time-to-live Tr. Figures 6(a), 6(b), and 6(c) show the forwarding options based on OJEDF with $L = 1$ , $L = 2$ , and $L = 3$ .

Figure 5

The JEDs calculated by OJEDF in ticket based forwarding.

Figure 6

(a) Forwarding options based on OJEDF in ticket based forwarding with $L = 2$ . (b) Forwarding options based on OJEDF in ticket based forwarding with $L = 3$ . (c) Forwarding options based on OJEDF in ticket based forwarding with $L = 4$ .

5. An Extension of OJEDF for Delay Constrained Scenarios

We have solved the optimal joint expected delay problem with the constraint of remaining hop-count or ticket of messages. As a further consideration, we extend OJEDF to run in delay constrained DTN applications. For example, electronic notice in campus networks [30] and village networks [31] and short-term weather information in large national parks [32] must be forwarded with constrained delay. On the other hand, as the access networks, configuration and forecast for QoS are also necessary in order to provide acceptable service (such as e-mail) in DTNs.

Since JED is a function of remaining hop-count (or the number of tickets) and residual lifetime, the OJEDF can also be used to estimate the minimum hop-count K or the minimum tickets L to meet the constrained delay. We give a simple hop-count estimation algorithm with constrained delay based on JED in Algorithm 3. We define the K_MAX as the maximum of hop-count which equals $⌈ \log_{2} M ⌉$ (M is the number of nodes) which is large enough to spray copies to all of the nodes in hop-count based forwarding. The constrained delay (CD) and initial time-to-live TTL $({TTL}_{init})$ must be defined in advance. Both of them are normalized by time-slot U and satisfy ${TTL}_{init} \geq CD$ . Similarly, Algorithm 4 shows the ticket estimation algorithm in which the maximum of tickets L_MAX equals M.

Algorithm 3: Hop-count estimation algorithm.

$(1)$ $K_MAX ∶ = ⌈ \log_{2} M ⌉$

$(2)$ CD $∶ =$ Constrained Delay

$(3)$ for ( $K = 0$ ; $K \leq K_MAX$ ; $K + +$ ){

$(4)$ for ( $TTL = CD$ ; $TTL \leq {TTL}_{init}$ ; $TTL + +$ ){

$(5)$ Calculate ${JED}_{i, d, K, TTL}$ , using Algorithm 1; }

$(6)$ if ( ${JED}_{i, d, K, TTL} \leq CD$ )

$(7)$ return K; }

$(8)$ return false;

Algorithm 4: Ticket estimation algorithm.

$(1)$ $L_MAX ∶ = M$

$(2)$ $CD$ $∶ =$ Constrained Delay

$(3)$ for ( $L = 1$ ; $L \leq L_MAX$ ; $L + +$ ) {

$(4)$ for ( $TTL = CD$ ; $TTL \leq {TTL}_{init}$ ; $TTL + +$ ){

$(5)$ Calculate ${JED}_{i, d, L, TTL}$ using Algorithm 2; }

$(6)$ if ( ${JED}_{i, d, L, TTL} \leq CD$ )

$(7)$ return L; }

$(8)$ return false;

We can get the minimum of hop-count with different constrained delay for each destination node using Algorithm 3. Assuming that the message was generated in node 0 and the mean inter-meeting times matrix was in Table 1, Figure 7 showed the minimum of hop-count with $TTL = 29$ . The ticket estimation was shown in Figure 8 with the same parameters.

Figure 7

The minimum of hop-count with $TTL = 29$ .

Figure 8

The minimum of tickets with $TTL = 29$ .

6. Simulation

We evaluated OJEDF with hop-count constraint (OJEDF-H) and OJEDF with ticket constraint (OJEDF-T) against Spray and Wait (SNW), ProphetV2 (PRO2), and Epidemic (EP) using St. Andrews encounter trace and Illinois encounter trace. We implemented the above protocols in The ONE [33] which was developed by the Helsinki University of Technology. We obtained the performance indicators including average delay (only of the copies delivered successfully), the delivery rate, and the average number of copies for each message (no acknowledgment mechanism) from The ONE. The simulation parameters were shown in Table 2 (only the default values without any special instruction).

Table 2

Settings for simulation.

Parameters	Values for St. Andrews trace	Values for Illinois trace	Remarks
Time slot for OJEDF-H	70 s	176 s	Only for OJEDF-H
Time slot for OJEDF-T	140 s	245 s	Only for OJEDF-T
Mean self-meeting time δ	0.000001 s	0.000001 s	Only for OJEDF
Remaining hop-count initialization constant	3	2	Only for OJEDF-H
Number of tickets for OJEDF-T	6	4	Only for OJEDF-T
Time unit for PRO2	30 s	30 s	Only for PRO2
Delivery predictability initialization constant	0.5	0.5	Only for PRO2
Delivery predictability transitivity scaling constant β	0.9	0.9	Only for PRO2
Delivery predictability aging constant γ	0.999885791	0.999885791	Only for PRO2
Number of tickets for SNW	6	6	Only for SNW
Binary mode	True	True	Only for SNW
Number of nodes	25	7
Time-to-live	90 min	500 min
Number of external encounter events	591	7017
Default connections	False	False
Message size	500 kB	50 kB
Interval of message generator	25 s–35 s	250 s–350 s
Buffer size	5 M	1 M
Simulation times	20	20
End time of simulation	5369 s	240000 s

6.1. Simulation Using St. Andrews Encounter Trace

St. Andrews encounter trace set up a mobile sensor network comprising mobile IEEE 802.15.4 sensors (T-mote invent devices) carried by human users and Linux-based basestations that bridge the 802.15.4 sensors to the wired network. St. Andrews encounter trace deployed 27 T-mote invent devices among 22 undergraduate students, 3 postgraduate students, and 2 members of the staff of the University of St. Andrews from the participants' Facebook friend lists. Participants were asked to carry the devices whenever possible.

Due to the limit of buffer and the queue of external events, we only employ the encounter data from time 0 to 5369. We optimize the original data in order to remove the reduplicative records and invalid users. The reduplicative records are the same encounter records in the same time, and the invalid users mean the users who never appeared before time 5369. As a result, we get 25 valid users and 591 external encounter events. The final encounter data must be formatted into standard external event queue data which can be read by The ONE.

We get the performance with different message overload. The intervals of message generator varied from 10 s to 50 s.

Figure 9(a) showed the average delay with different intervals of message generator. The average delay increased with the increasing intervals. When the message overload was high, the multihop forwardings were difficult due to the constrained buffer size. As a result, the average delay was low. The average delay increased with the decreased message overload since the multihop forwardings became common. There was no copy control in EP and PRO2, so the average delay of them was high compared with that of SNW and OJEDF due to the constrained buffer size set in simulation. We can see from Figure 9(a) that the average delay of PRO2 was lower than that of SNW and OJEDF when the interval of message generator was long enough. This is because the buffer size becomes sufficient in low message overload, and the average delay is low when there is no copy control in PRO2. OJEDF which optimizes the joint expected delay can be viewed as an improvement of SNW. The average delay rates of OJEDF-H and OJEDF-T were 8.89% and 14.05% lower than that of SNW, respectively.

Figure 9

(a) Average delay with different interval for message generator using St. Andrews encounter trace. (b) Delivery rate with different interval for message generator using St. Andrews encounter trace. (c) Number of forwardings with different interval for message generator using St. Andrews encounter trace.

Figure 9(b) showed the delivery rate with different intervals of message generator. The delivery rate increased when the overload decreased. All of the delivery rates are lower than 50%. This is because only 244 contacts occurred between 25 users in the first 5369 s. This is a very low contact probability. OJEDF did not forward the copies to the node first encountered but forwarded based on the expected delay. So the delivery rates of OJEDF-H and OJEDF-T were 14.20% and 13.61% lower than that of SNW in average, respectively. Most of the time, the delivery rate of OJEDF is higher than that of EP and PRO2.

We also got the number of forwardings with different intervals of message generator. We can see form Figure 9(c) that the numbers of forwardings of OJEDF-H and OJEDF-T were much lower than those of EP, PRO2, and SNW. OJEDF only forwarded the messages to the optimal node, and the numbers of forwardings of OJEDF-H and OJEDF-T were 34.86% and 36.00% lower than that of SNW, respectively.

We also compared the performance with different TTLs (from 10 minutes to 90 minutes).

Figure 10(a) showed the average delay. The average delay means the delivery delay of messages which were delivered successfully, so the average delay was low when TTL was low. The average delay rates of EP and PRO2 were higher than those of SNW and OJEDF. OJEDF outperformed other protocols in terms of the average delay with all TTLs. Specially, the average delay rates of OJEDF-H and OJEDF-T were 9.24% and 18% lower than that of SNW, respectively.

Figure 10

(a) Average delay with different TTLs using St. Andrews encounter trace. (b) Delivery rate with different TTLs using St. Andrews encounter trace. (c) Number of forwardings with different TTLs using St. Andrews encounter trace.

Figure 10(b) showed the delivery rate with different TTLs. With increasing TTL, more messages were unable to be forwarded due to the restraint of buffer size. As a result, the delivery rate of EP and PRO2 trended to decrease. On the contrary, the delivery rate of SNW and OJEDF increased with increasing TTL. The delivery rates of OJEDF-H and OJEDF-T were 4.9% and 3.8% lower than that of SNW, respectively.

Figure 10(c) showed the number of forwardings with different TTLs. OJEDF outperformed all protocols in terms of the number of forwardings with all TTLs. Specially, the numbers of forwardings of OJEDF-H and OJEDF-T were 34.69% and 37.66% lower than that of SNW, respectively.

6.2. Simulation Using Illinois Encounter Trace

Illinois encounter trace is the dataset of MACs of Bluetooth and Wi-Fi access points collected by the University of Illinois Movement (UIM) framework using Google Android phones. The set of Bluetooth and WiFi traces were collected by 28 users for 3 weeks in 2010. These people are staff, faculties, graduates, and undergraduates at the University of Illinois. Each UIM experiment phone encompasses a Bluetooth scanner and a Wi-Fi scanner capturing both Bluetooth MAC addresses and Wi-Fi access point MAC addresses in proximity to the phone.

To unify the network interface in simulator, we only used the Bluetooth trace. Considering the constraint of buffer and external event queue, only 7017 external encounter events from February 26, 2010 07:00:42 to February 26, 2010 22:59:57 were employed. We found seven different MAC addresses in this period.

We tested the performance with different message overload. The intervals of message generator were varied from 100 s to 500 s. Figures 11(a), 11(b), and 11(c) showed the simulation results using Illinois encounter trace. Like the results in St. Andrews encounter trace, EP and PRO2 still have higher average delay than other copy constrained algorithms. The average delay rates of OJEDF-H and OJEDF-T were 6.09% and 12.14% lower than that of SNW, respectively. The delivery rate increased when the overload decreased. All of the delivery rates are lower than 21%. This is because about 38.08% of the total 7017 contacts occurred between user 3 and user 4 or between user 4 and user 6. These unevenly distributed contacts led to low delivery rate when we only employed the encounter trace in one day. Different from Saint Andrews encounter trace, we set a big buffer relative to message size, so the delivery rates of EP and PRO2 were higher than those of OJEDF-H and OJEDF-T. The delivery rates of OJEDF-H and OJEDF-T were 15.55% and 9.66% lower than that of SNW in average, respectively. OJEDF still had the least forwardings for each message. The numbers of forwardings of OJEDF-H and OJEDF-T were 10.90% and 11.86% lower than that of SNW, respectively.

Figure 11

(a) Average delay with different interval for message generator using Illinois encounter trace. (b) Delivery rate with different interval for message generator using Illinois encounter trace. (c) Number of forwardings with different interval for message generator using Illinois encounter trace.

We compared the performance with different TTLs. Large TTLs (from 100 minutes to 500 minutes) were used in our simulations. Firstly, the valid encounters lasted for 230301 seconds at 02-26-2010 in Illinois encounter trace. Secondly, the encounters were unevenly distributed between seven persons. As a result, many copies need more time to find useful encounters during all simulation time and to meet the destinations ultimately.

Figures 12(a), 12(b), and 12(c) showed the performance of different algorithms with different TTLs using Illinois encounter trace. The average delay rates of EP and PRO2 were lower than that of SNW. This profited from flooding based diffusion and sufficient buffer. OJEDF outperformed all protocols in terms of the average delay with all TTLs. The average delay rates of OJEDF-H and OJEDF-T were 47.93% and 52.76% lower than that of SNW, respectively. The delivery rates of all protocols increased with increasing TTLs in Illinois encounter trace scenario. The delivery rates of OJEDF-H and OJEDF-T were 28.61% and 21.91% lower than that of SNW, respectively. But the numbers of forwardings of OJEDF-H and OJEDF-T were 11.65% and 12.37% lower than that of SNW, respectively.

Figure 12

(a) Average delay with different TTLs using Illinois encounter trace. (b) Delivery rate with different TTLs using Illinois encounter trace. (c) Number of forwardings with different TTLs using Illinois encounter trace.

6.3. Summary of Simulation

Simulation results confirm that OJEDF outperforms all protocols in terms of average delivery delay and forwarding cost using both St. Andrews encounter trace and Illinois encounter trace. The delivery delay and the number of forwardings of OJEDF-H are 18% and 23% lower than those of SNW while decreasing only 15% delivery rate. OJEDF-T is more accurate than OJEDF-H in terms of copy control. The delivery delay and the number of forwardings of OJEDF-T are 24% and 25% lower than those of SNW while decreasing only 12% delivery rate.

7. Conclusion

In this paper, we provide an optimal forwarding protocol which minimizes the expected delay while satisfying the constant on the number of forwardings per message. We propose the optimal joint expected delay forwarding which makes optimal forwarding decisions by modeling forwarding as an optimal stopping rule problem. We firstly employ the comprehensive dynamic forwarding metric called joint expected delay (JED) which is a function of two important states of a message copy: remaining hop-count and residual lifetime. Then we propose the forwarding rules to decide whether to forward the copies. Based on the hop-count constraint forwarding scheme, we propose a general ticket constraint OJEDF which can be viewed as a development of Spray and Wait with special spray metric. We also present an extension to allow OJEDF to run in delay constrained scenarios. We implemented OJEDF as well as several other protocols and performed trace-driven simulations. Simulation results verified the efficiency of OJEDF.

In the future, we will perform simulations on the extended version of OJEDF, that is, estimating the minimum hop-count or tickets to meet the constrained delay. We will also do research on the expansibility and adaptability of OJEDF when only partial routing information is known.

Footnotes

Acknowledgments

This research was supported in part by the National Natural Science Foundation of China (61100199), the Scientific and Technological Support Project (social development) of Jiangsu Province (BE2013666), the Natural Science Key Fund for Colleges and Universities in Jiangsu Province (12KJA520002), the Special Fund of postdoctor (2013T60553), the Jiangsu Provincial Natural Science Foundation of China (BK2011692), the Postdoctoral Foundation (20110491453), the Jiangsu Planned Projects for Postdoctoral Research Funds (1101126c), the talents project of Nanjing University of Posts and Telecommunications (NY210077), and the Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions (yx002001).

References

Cerf

Burleigh

Hooke

Torgerson

Durst

Scott

Fall

Weiss

Delay Tolerant Networking Architecture

DTN Research Group, 2007, http://tools.ietf.org/html/rfc4838

Kevin

Stephen

The Delay-Tolerant Networking Research Group (DTNRG)

2010, http://www.dtnrg.org/wiki/Home

Xiong

Y.-P.

Sun

L.-M.

Niu

J.-W.

Liu

Opportunistic networks

Journal of Software 2009 20 1 124 137

2-s2.0-61749099144

10.3724/SP.J.1001.2009.00124

Amin

David

Epidemic routing for partially connected ad hoc networks

CS-2000-06, Department of Computer Science, Duke University, Durham, NC, USA, 2000

Bromage

M. K.

Koshimoto

J. T.

Obraczka

TAROT: trajectory-assisted routing for intermittently connected networks

Proceedings of the Annual International Conference on Mobile Computing and Networking Workshops (MobiCom '09) and 4th ACM Workshop on Challenged Networks (CHANTS '09)

September 2009

9 17

2-s2.0-70350676529

10.1145/1614222.1614225

Burns

Brock

Levine

B. N.

MV routing and capacity building in disruption tolerant networks

Proceedings of the IEEE Computer and Communications Societies (INFOCOM '05)

March 2005

398 408

2-s2.0-25844501977

Lindgren

A. D.

Schelèn

Probabilistic routing in intermittently connected networks

Mobile Computing and Communications Review 2003 7 3 19 20

10.1145/961268.961272

F.-L.

Liu

Gong

H.-G.

Chen

G.-H.

J.-P.

Zhu

J.-Q.

Relative distance-aware data delivery scheme for delay tolerant mobile sensor networks

Journal of Software 2010 21 3 490 504

2-s2.0-77950992948

10.3724/SP.J.1001.2010.03459

Jones

E. P. C.

Ward

P. A. S.

Practical routing in delay-tolerant networks

Proceedings of the ACM Conference on Computer Communications (SIGCOMM '05)

2005

10.

Guo

Wang

Cui

J.-H.

Prediction assisted single-copy routing in underwater delay tolerant networks

Proceedings of the 53rd IEEE Global Communications Conference (GLOBECOM '10)

December 2010

2-s2.0-79551616433

10.1109/GLOCOM.2010.5683232

11.

Singh

J. P.

Bambos

Srinivasan

Clawin

Yan

Proposal and demonstration of link connectivity assessment based enhancements to routing in mobile ad-hoc networks

Proceedings of the IEEE 58th Vehicular Technology Conference (VTC '03)

October 2003

2834 2838

2-s2.0-4143053452

12.

Mascolo

Musolesi

SCAR: context-aware adaptive routing in delay tolerant mobile sensor networks

Proceedings of the ACM International Wireless Communications and Mobile Computing Conference (IWCMC '06)

July 2006

533 538

2-s2.0-34247324001

10.1145/1143549.1143656

13.

Liu

An optimal probabilistic forwarding protocol in delay tolerant networks

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

2009

14.

Thomas

S. F.

Optimal Stopping and Applications

2008, http://www.math.ucla.edu/~tom/Stopping/Contents.html

15.

Spyropoulos

Psounis

Raghavendra

C. S.

Spray and wait: an efficient routing scheme for intermittently connected mobile networks

Proceedings of the ACM Conference on Computer Communications (SIGCOMM '05)

August 2005

252 259

2-s2.0-29244491141

16.

Bigwood

Rehunathan

Bateman

Henderson

Bhatti

Exploiting self-reported social networks for routing in ubiquitous computing environments

Proceedings of the 4th IEEE International Conference on Wireless and Mobile Computing, Networking and Communication (WiMob '08)

October 2008

484 489

2-s2.0-56749091843

10.1109/WiMob.2008.86

17.

Long

Quang

Klara

3R: fine-grained encounter-based routing in delay tolerant networks

Proceedings of the IEEE International Symposium on a World of Wireless Mobile and Multimedia Networks (WoWMoM '11)

2011

18.

Leguay

Friedman

Conan

DTN routing in a mobility pattern space

Proceedings of the ACM Conference on Computer Communications (SIGCOMM '05)

August 2005

276 283

2-s2.0-29244446789

19.

Musolesi

Hailes

Mascolo

Adaptive routing for intermittently connected mobile Ad Hoc Networks

Proceedings of the IEEE International Symposium on a World of Wireless Mobile and Multimedia Networks (WoWMoM '05)

2005

20.

Spyropoulos

Psounis

Raghavendra

C. S.

Spray and focus: efficient mobility-assisted routing for heterogeneous and correlated mobility

Proceedings of the 5th Annual IEEE International Conference on Pervasive Computing and Communications Workshops (PerCom '07)

March 2007

79 85

2-s2.0-34547699980

10.1109/PERCOMW.2007.108

21.

Spyropoulos

Turletti

Obraczka

Utility-based message replication for intermittently connected heterogeneous networks

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

June 2007

2-s2.0-47749146868

10.1109/WOWMOM.2007.4351693

22.

Jindal

Psounis

Optimizing multi-copy routing schemes for resource constrained intermittently connected mobile networks

Proceedings of the 40th Asilomar Conference on Signals, Systems, and Computers (ACSSC '06)

November 2006

2142 2146

2-s2.0-47049085299

10.1109/ACSSC.2006.355147

23.

Zhuoqun

Lingfen

Ifeachor

E. C.

Adaptive multi-copy routing for intermittently connected mobile ad hoc networks

Proceeding of the IEEE Global Telecommunications Conference (GLOBECOM '06)

December 2006

2-s2.0-50949122061

10.1109/GLOCOM.2006.950

24.

Spyropoulos

Psounis

Raghavendra

C. S.

Efficient routing in intermittently connected mobile networks: the single-copy case

IEEE/ACM Transactions on Networking 2008 16 1 63 76

2-s2.0-40749157530

10.1109/TNET.2007.897962

25.

Spyropoulos

Psounis

Raghavendra

C. S.

Efficient routing in intermittently connected mobile networks: the multiple-copy case

IEEE/ACM Transactions on Networking 2008 16 1 77 90

2-s2.0-40749113163

10.1109/TNET.2007.897964

26.

Erramilli

Crovella

Chaintreau

Diot

Delegation forwarding

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

May 2008

251 259

2-s2.0-57349185558

10.1145/1374618.1374653

27.

Balasubramanian

Levine

Venkataramani

DTN routing as a resource allocation problem

Proceedings of the ACM Conference on Computer Communications (SIGCOMM '07)

August 2007

373 384

2-s2.0-36949009831

10.1145/1282380.1282422

28.

Liu

An optimal probabilistic forwarding protocol in delay tolerant networks

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

2009

29.

Liu

Cardei

Message forwarding in cyclic MobiSpace: the multi-copy case

Proceedings of the IEEE 6th International Conference on Mobile Adhoc and Sensor Systems (MASS '09)

October 2009

413 422

2-s2.0-74249097196

10.1109/MOBHOC.2009.5336973

30.

Chaintreau

Hui

Crowcroft

Diot

Gass

Scott

Pocket Switched Networks: real-world mobility and its consequences for opportunistic forwarding

2005 UCAM-CL-TR-617

Computer Laboratory, University of Cambridge

31.

Pentland

Fletcher

Hasson

DakNet: rethinking connectivity in developing nations

IEEE Computer 2004 37 1 78 4

2-s2.0-0742285890

10.1109/MC.2004.1260729

32.

Beaufour

Leopold

Bonnet

Smart-tag based data dissemination

Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications (WSNA '02)

September 2002

68 77

2-s2.0-0036983338

33.

Ari

Jörg

Teemu

The ONE simulator for DTN protocol evaluation

Proceedings of the 2nd International Conference on Simulation (Simutools '09)

2009

	0	1	2	3	4	5	6	7
0	0	20	33	42	20	50	60	35
1	20	0	45	50	30	40	25	10
2	33	45	0	30	40	55	60	20
3	42	50	30	0	60	45	37	27
4	20	30	40	60	0	35	29	100
5	50	40	55	45	35	0	23	80
6	60	25	60	37	29	23	0	26
7	35	10	20	27	100	80	26	0

	0	1	2	3	4	5	6	7
0	0	20	33	42	20	50	60	35
1	20	0	45	50	30	40	25	10
2	33	45	0	30	40	55	60	20
3	42	50	30	0	60	45	37	27
4	20	30	40	60	0	35	29	100
5	50	40	55	45	35	0	23	80
6	60	25	60	37	29	23	0	26
7	35	10	20	27	100	80	26	0

Optimal Joint Expected Delay Forwarding in Delay Tolerant Networks

Abstract

1. Introduction

2. Related Works

3. Preliminaries

3.1. Hop-Count Constrained Forwarding and Ticket Constrained Forwarding

3.2. Motivation

3.3. Assumption

Proof.

4. Optimal Joint Expected Delay Forwarding (OJEDF)

4.1. OJEDF with Hop-Count Constraint

Algorithm 1: The calculation of JED i , d , K , Tr in hop-count based forwarding.

4.2. OJEDF with Ticket Constraint

Algorithm 2: The calculation of JED i , d , L , Tr in ticket based forwarding.

5. An Extension of OJEDF for Delay Constrained Scenarios

Algorithm 3: Hop-count estimation algorithm.

Algorithm 4: Ticket estimation algorithm.

6. Simulation

6.1. Simulation Using St. Andrews Encounter Trace

6.2. Simulation Using Illinois Encounter Trace

6.3. Summary of Simulation

7. Conclusion

Footnotes

Acknowledgments

References

Algorithm 1: The calculation of ${JED}_{i, d, K, Tr}$ in hop-count based forwarding.

Algorithm 2: The calculation of ${JED}_{i, d, L, Tr}$ in ticket based forwarding.

	0	1	2	3	4	5	6	7
0	0	20	33	42	20	50	60	35
1	20	0	45	50	30	40	25	10
2	33	45	0	30	40	55	60	20
3	42	50	30	0	60	45	37	27
4	20	30	40	60	0	35	29	100
5	50	40	55	45	35	0	23	80
6	60	25	60	37	29	23	0	26
7	35	10	20	27	100	80	26	0