A General and Specific Utility-Based Adaptive Routing for Delay Tolerant Networks

Abstract

The nonexistence of an end-to-end path poses great challenges in directly adapting the traditional routing algorithms for ad hoc or mobile ad hoc networks (MANETs) to delay tolerant networks (DTNs). In this paper, an adaptive routing protocol that makes use of both self-aware and destination-aware utility metrics to evaluate the potential throughput between every pair of nodes is proposed. We theoretically analyze the nodes’ spraying process and discover the relationship between the initial number of copies and the latency of the message distribution process, by which we can further control the expected latency under a certain level. Compared with Epidemic, Spray And Wait Spray, And Focus and Encounter-based routing, our proposed algorithm is the only one that achieves comparable performance under both Helsinki City Scenario and Cambridge-iMote Scenario.

1. Introduction

Delay/disruption tolerant networks are networks of self-organizing wireless nodes, where end-to-end connectivity is intermittent [1]. The communication model of the Internet is based on some inherent networking assumptions, for example, the existence of a continuous end-to-end path between two nodes, the relatively short round-trip delays, the symmetric data rates, and the low error rates [2]. However, in DTNs these assumptions usually fail, which leads to the fact that the TCP/IP protocol does not work [3]. Hence, many application protocols designed for the Internet architecture cannot operate well in the DTN scenarios such as InterPlanetary interNet (IPN) [4]. In [5], Khabbaz et al. pointed out that we need a new kind of network model when modeling existing and recently emerging wireless networks, especially those deployed in extreme environments (e.g., battlefields, volcanic regions, deep oceans, deep space, developing regions, etc.) where they suffer challenging conditions (e.g., military wars and conflicts, terrorist attacks, earthquakes, volcanic eruptions, floods, storms, hurricanes, severe electromagnetic interferences, congested usage, etc.) resulting in excessive delays, severe bandwidth restrictions, remarkable node mobility, frequent power outages, and recurring communication obstructions. Based on the observation that quite a few terrestrial networks exhibit delay-tolerant properties, albeit different nature: from sparse mobile ad hoc to sensor networks to mobile Internet access, it is found that delay tolerance exists as an important element to describe communication behavior and to design protocols suitable for operation in the corresponding challenged networking environment [6].

Most research achievements on DTNs focus on the design of routing protocols. Since there are some common characteristics between most terrestrial DTNs and mobile ad hoc networks (MANETs), for example, nodes mobility and “store-carry-forward” paradigm, many researches work on routing in DTNs aiming to solve the newly arisen difficulties in MANETs that address the “delay-tolerant” property. Epidemic protocol [7] makes use of naive replication strategy letting each node replicate the message to all encountered nodes, so as to try to achieve the maximum message delivery ratio. However, the buffer size and energy of nodes are limited thus constraining its practical performance. Spray And Wait [8] takes the cost into consideration and confined the maximum number of copies and hop counts of each message. On the foundations of these two classic routing algorithms, many multicopy routing schemes focusing on evaluating contacts opportunities among nodes have been proposed [9–13]. All these research achievements are devoted to efficient utilizing of the possible contacts between pair of nodes, thus making messages delivered through multiple hops between nodes in a “store-carry-forward” paradigm. All of these algorithms essentially utilize various utility metrics to replicate or to forward the message in a gradient way to the destination. In DTNs, the utility metrics can be categorized as follows:

• (i)

  destination-aware utility, which evaluates how well-suited a device is for routing towards a specific destination device,

• (ii)

  self-aware utility, which evaluates the applicability of a device as forwarder in general, irrespective of the message's destination,

• (iii)

  unaware utility, which is a per-message utility of (controlled) flooding, irrespective of any node.

However, as far as our information goes, only [14] takes both self-aware and destination-aware factors into consideration. We denote self-aware utility as the “general utility” and destination-aware utility as the “specific utility”, respectively. Starting from this point, we design a routing protocol capturing both generic and specific utilities (GSUs) of nodes. Based on this principle, we implement an asymmetric message replicas distribution approach “GSU-Spray” to boost the messages dissemination towards their destinations. The primary motivation is to replicate more copies to candidate nodes as quickly as possible. Besides, since network resources in DTNs are highly constrained, we take the buffer resource issues into consideration. Furthermore, the number of replicas for each message is adjusted between nodes in each transmission by referring to the dynamically updated utility metrics. From this perspective, GSU-Spray has the ability to adaptively cater to the various DTN environments. Our contributions are listed as follows.

• (i)

  General and Specific Utility Metrics for Nodes and Messages. We propose general and specific utilities that take the node buffer issue into consideration. On one hand, we utilize each node's contact frequency to all other nodes over a time period to design the general utility. On the other hand, for which a longer connection duration between two nodes usually indicates a higher message transmission throughput, we use both contact frequency and contact duration time between each pair of nodes to define the specific utility which evaluates each node's fitness of being a relay node to the destination node.

• (ii)

  Utility-Based Adaptive Asymmetrical Spray Approach. We design a utility-based spray routing algorithm. We asymmetrically spray the copies of each message by referring to the utility metric. This method dynamically reallocates the network resource for each message, thus adaptively balancing the number of copies between each pair of nodes according to the utility metric.

• (iii)

  Combining Specific Utility and Delegation Scheme to Implement Forwarding. In delegation forwarding (DF) [15], each message updates a threshold value with the maximum value of all encountered node(s)’ utility metrics for the destination. Different from the traditional controlled-flooding strategies, DF only replicates the message if the encountered node has a better utility value than the threshold value cached in this message. This approach is employed in our routing algorithm by letting each message record the maximum specific utility value encountered before, thus lowering the total costs of routing.

• (iv)

  Adjustable Sensitivity of the Contact Duration Time. Rather than simply accumulating every contact duration time for each node, we design a function that integrates an exponential function $e^{-\lambda t}$ in each duration time interval. Consequently, the sensitivity to the contact duration time of the utility metric is controlled by the value of the parameter λ.

• (v)

  Using Markov Chain to Guarantee a Desirable Latency. The distribution process for a certain message can be modeled as a discrete Markov Chain, where each state is denoted by the number of message replicas. We theoretically analyze the replication process of spraying stage in GSU-Spray by building a Markov Chain. Then we discover the relationship between the initial number of copies of a message and the desired latency. By dynamically adjusting the preassigned number of copies of each message, we can keep the expected latency under a certain level.

The paper is organized as follows. Section 2 introduces the network model and describes the routing problem. In Section 3 we put forward details of routing design. Section 4 analyses the spraying process by using a Markov Chain Model. In Section 5 we show the simulation results. In Section 6 we report on previous works in the field of DTNs. Section 7 eventually concludes this paper.

2. Preliminary

The notations relative to our network model are listed in Table 1. To illustrate the general picture of our routing in the network, we use the following model. As stated in the Introduction, we focus on mobile opportunistic networking scenarios where nodes communicate using the DTN bundle protocol [16]. All nodes are willing to cooperate and to assist other nodes in forwarding bundles to their destinations. Moreover, we assume that node $n_s$ holds a variable $L_s(k)$ for each message $m_k$ to record the number of remaining “tickets.” Such ticket denotes how many copies of $m_k$ can be distributed to other nodes by $n_s$ in the spraying stage. Our primary goal is to efficiently allocate the number of tickets between two meeting nodes to accelerate the message distribution process. In the source Spray And Wait routing [8], the source node is the only node to spray the messages to others, while in its binary edition all nodes equally spray the message copies.

Table 1

Mathematical notations for network model.

Notation	Meaning
$n_s$	The node with the EID s
$m_k$	The message identified by k
$\mathrm{\gamma }(s)$	Current resource state of $n_s$ ( $\mathrm{\gamma }(s)\in [\mathrm{0,1}]$ )
$\mathrm{\varphi }(s)$	Total meeting frequency of $n_s$
$L_s(k)$	The number of tickets of message $m_k$ for current node $n_s$
$\mathrm{\tau }(k)$	The delegation threshold for message $m_k$
${\text{TS}}_{s,d}(k)$	Start time of the kth connecting between $n_s$ and $n_d$
${\text{TD}}_{s,d}(k)$	End time of the kth connecting between $n_s$ and $n_d$
$U_{\text{gene}}(s)$	The general utility for $n_s$
$U_{\text{spec}}(s,d)$	The specific utility for $n_s$ and $n_d$
$U_{\text{spray}}(s,d)$	Utility for allocating replicas between $n_s$ and $n_d$ in spraying state
$U_{\text{forward}}(s,d)$	Utility for replicating message from $n_s$ to $n_d$ in forwarding stage

As illustrated in Figure 1, the source Spray And Wait routing shows up a little stiffly, since it only makes use of the contacts between the source node and others to distribute message copies. Binary Spray And Wait is not the optimal choice either, since the source node always equally sprays the message copies with unawareness of each node's capability. Though [8] proves that binary Spray And Wait is optimal when node movement is independent identically distributed (IID), in most cases we do not have such a strict IID movement that the binary distribution method fails to get the optimal choice, as shown in Figure 1.

Figure 1

Message duplication tree formed by spray operations.

In this paper, we propose an adaptive routing scheme to satisfy the various DTNs. Based on the Spray And Wait routing, we adaptively adjust the number of tickets between each pair of nodes during the whole spraying process, so as to efficiently allocate network resources. In addition, since spray-based routing algorithms can only generate limited number of message copies, in forwarding stage, we employ delegation forwarding scheme to further replicate messages to other nodes in order to keep sufficient copies, thus achieving the purpose of improving the delivery performance.

3. Routing Details

In DTN routing, the utility of a node is a measure of its contribution to improve a routing metric such as throughput or delay [17]. Let us briefly review the objectives of DTN routing algorithms. Firstly we should maximize the message delivery ratio. Then the average latency and the overhead ratio should be controlled under an acceptable level. There are two stages in our proposed routing. In the spraying stage, GSU-Spray sprays message copies to others. Different from traditional spray-based routing, our scheme adaptively adjusts the number of message copies between each pair of contacting nodes. For each message, when there is only one copy held by a node, the node then enters the delegation forwarding stage where nodes only replicate the message to other nodes with a higher utility metric value than the delegation threshold. In this stage, when a message is successfully relayed to $n_b$ by $n_a$ , the delegation threshold in each message copy will be updated to the utility of $n_b$ .

In this section, we firstly give the definition of both general metric and specific metric. We then describe how to adaptively spray the message copies to nodes by using both general and specific utility metrics. Finally we combine the specific utility metric with the node state variable γ to implement delegation forwarding. Either stage takes the node buffer space issues into consideration. The relationship of utility metrics dependency is illustrated in Figure 2. $U_{\text{gene}}$ and $U_{\text{spec}}$ represent the general and specific utilities, respectively, and both of them are the atomic utilities, which are updated based on the history records of contact duration and frequency. $U_{\text{spray}}$ is the metric to evaluate a node's capability of spraying message copies, which is composed by both $U_{\text{gene}}$ and $U_{\text{spec}}$ . The other metric $U_{\text{forward}}$ is used in the delegation forwarding stage, by only resorting to the help of $U_{\text{spec}}$ . Then based on these two stages comes our GSU-Spray algorithm.

Figure 2

The relationship of utility metrics dependency.

3.1. Utility-Based Asymmetrical Spraying Stage

One way to increase the performance of routing is to spray message copies to other nodes in the network, so as to raise the parallelism of the message [18]. The first stage of GSU-Spray is to asymmetrically adjust message copies between every pair of nodes. As addressed before that both general and specific utilities should be taken into consideration, we calculate the generic utility and specific utility for node $n_s$ by

$$\begin{array}{cc}& U_{\text{gene}}\left(s\right)=\gamma \left(s\right)\varphi \left(s\right),\hspace{1em}\left(\gamma \left(s\right)\in \left[\mathrm{0,1}\right]\right),\end{array}$$

(1)

$$\begin{array}{cc}& U_{\text{spec}}\left(s,d\right)={\displaystyle \sum }_{i=\mathrm{1}}^{i=n}‍{{\displaystyle \int }}_{{\text{TS}}_{s,d}\left(i\right)}^{\text{T}{\text{D}}_{s,d}\left(i\right)}‍e^{-\lambda t}dt,\hspace{1em}\left(\lambda >\mathrm{0}\right).\end{array}$$

(2)

Equation (1) evaluates a node's capability of being the relay node in a “self-aware” perspective, of which $\varphi (s)$ records the contact frequency between $n_s$ and all other nodes and $\gamma (s)$ reflects the available buffer resource in $n_s$ with the range interval $[\mathrm{0,1}]$ .

Equation (2) is used to calculate the specific utility for each pair of nodes in a “destination-aware” perspective. Different from general utility that reflects the state of a node itself, a specific utility metric measures the qualification of prospective forwarding throughput between a pair of nodes. In (2), ${\text{TS}}_{s,d}(i)$ and ${\text{TD}}_{s,d}(i)$ represent the start time and the end time of ith contact between $n_s$ and $n_d$ , respectively. In addition, we design a function that integrates an exponential function $e^{-\lambda t}$ in each duration time interval, by which the sensitivity of the utility to the contact duration time can be adjusted. As illustrated in Figure 3, a larger λ value leads to a curve decreasing more quickly, which leads to the fact that the utility is less sensitive to the contact duration time. This is because the increment of the contact duration time interval $\mathrm{\Delta }T$ has little influence on the value of ${\int }_{\mathrm{0}}^{\mathrm{\Delta }T}‍e^{-\lambda t}dt$ , thus making our evaluation criteria degenerate near to the metric relying only on nodes’ contact frequency. Nevertheless, the smaller λ value we set, the larger increment shows on the curve of the calculus, which means that the evaluation criteria (2) becomes more sensitive to the nodes’ contact duration time.

Figure 3

The relationship between ${\int }_{\mathrm{0}}^{\mathrm{\Delta }T}‍e^{-\lambda t}dt$ , λ, and $\mathrm{\Delta }T$ .

Table 2 shows the exact function values we obtain by setting different λ and $\mathrm{\Delta }T$ . Though the function gets different values at different λ, the rank stays the same. We can see from the fourth column that the ratio increase is different between the two cases of λ, and it is obvious that compared with the function with a larger λ value the contact duration time $\mathrm{\Delta }T$ has a stronger influence on that than with a smaller λ value.

Table 2

Effects of $\mathrm{\lambda }$ values on node(s)'s sensitivity to the contact duration time.

$\mathrm{\lambda }$	$\mathrm{\Delta }T$	${\int }_{\mathrm{0}}^{\mathrm{\Delta }T}\mathrm{‍}{e}^{-\mathrm{\lambda }t}dt$	Ratio1
$\mathrm{\lambda }=\mathrm{10.0}$	0.20	0.0865
	0.40	0.0982	1.1353
	0.60	0.0997	1.0153
	0.80	0.1000	1.0030
	1.00	0.1000	1.0000
$\mathrm{\lambda }=\mathrm{1.0}$	0.20	0.1813
	0.40	0.3297	1.8185
	0.60	0.4512	1.3685
	0.80	0.5507	1.2205
	1.00	0.6321	1.1478

${}^{\mathit{1}}$ The ratio between ${\int }_{\mathrm{0}}^{\mathrm{\Delta }T}\mathrm{‍}{e}^{-\mathrm{\lambda }t}dt$ in the current line and that in the above line.

The details of the utility-based spraying stage are depicted in Algorithm 1, where our primary goal is to spray message copies to the network as efficiently as possible. We achieve this target by adaptively allocating or reallocating the number of copies for each message when a pair of nodes get into connection. Algorithm 1 takes the information of each pair of nodes (in our case, $n_a$ and $n_b$ ) as input and then outputs the adjusted results, respectively represented as $L_{a_{\text{new}}}$ and $L_{b_{\text{new}}}$ . The two metrics $U_{\text{gene}}$ and $U_{\text{spec}}$ are calculated according to (1) and (2) separately. Since the general metric $U_{\text{gene}}$ is only relative to the state of current node itself, we only need to calculate it once per algorithm running time. Both $n_a$ and $n_b$ compute their own $U_{\text{gene}}$ and then exchange them with each other. Then as shown in lines 2-3, the algorithm obtains $g_a$ and $g_b$ that can reflect the prospective throughput between $n_a$ and $n_b$ . Both $g_a$ and $g_b$ are less than 1 and we always maintain that $g_a+g_b=\mathrm{1}$ . When $L_{a_{\text{new}}}(k)=\mathrm{0}$ , it is undesirable for $n_a$ to continue holding message $m_k$ , and thus $n_a$ deletes the copy of $m_k$ from its buffer. The same rule also works on $L_{b_{\text{new}}}$ and $n_b$ . It should be noted that though the number of replicas decreases in the above case, the number of total prospective spraying copies stays the same, since the responsibility of $n_b$ to spray the message $m_k$ shifts to $n_a$ .

Algorithm 1: Utility-based spraying algorithm.

Input: node information of $n_a$ , $n_b$

Output: $L_{a_{\text{new}}}$ , $L_{b_{\text{new}}}$

   when $n_a$ get in contact with $n_b$

 (1)  local variables declaration: $g_a$ , $g_b$ , $s_a$ , $s_b$ , d

(2)   $g_a\leftarrow \frac{U_{\text{gene}}(a)}{U_{\text{gene}}(a)+U_{\text{gene}}(b)}$

(3)   $g_b\leftarrow \mathrm{1}-g_a$

(4)  for   $m_k\in n_a$ .messageCollection()  do

(5)    $d\leftarrow$  destination  node  of   $m_k$

(6)    $s_a\leftarrow \frac{U_{\text{spec}}\left(a,d\right)}{U_{\text{spec}}\left(a,d\right)+U_{\text{spec}}\left(b,d\right)}$

(7)    $s_b\leftarrow \mathrm{1}-s_a$

(8)    $U_{\text{spray}}\left(a,d\right)\leftarrow \mathrm{\alpha }{g}_a+\left(\mathrm{1}-\mathrm{\alpha }\right)s_a$

(9)    $U_{\text{spray}}\left(b,d\right)\leftarrow \mathrm{\alpha }{g}_b+\left(\mathrm{1}-\mathrm{\alpha }\right)s_b$

(10)  $L_{a_{\text{new}}}\left(k\right)\leftarrow \left(L_{a_{\text{old}}}\left(k\right)+L_{b_{\text{old}}}\left(k\right)\right)\left[\frac{U_{\text{spray}}\left(a,d\right)}{U_{\text{spray}}\left(a,d\right)+U_{\text{spray}}\left(b,d\right)}\right]$

(11)  $L_{b_{\text{new}}}\left(k\right)\leftarrow L_{a_{\text{old}}}\left(k\right)+L_{b_{\text{old}}}\left(k\right)-L_{a_{\text{new}}}\left(k\right)$

(12) end for

(13) return   $\left(L_{a_{\text{new}}},L_{b_{\text{new}}}\right)$ ;

Different from the generic utility metric that is only relative to one node, the specific utility metric $U_{\text{spec}}$ reflects the prospective throughput between one pair of nodes. For the purpose of sending the message to a node “nearer” to its destination, $U_{\text{gene}}$ and $U_{\text{spec}}$ should be combined together. We compute the metric $U_{\text{spec}}$ for all the messages and also maintain two variables $s_a$ and $s_b$ which reflect the prospective throughput of $n_a$ and $n_b$ to $m_k$ 's destination $n_d$ . Both $s_a$ and $s_b$ are less than 1 and we also maintain that $S(a,d)+S(b,d)=\mathrm{1}$ .

3.2. Utility-Based Forwarding Stage

After the spraying operation, the node enters the forwarding stage, at which the primary goal is to effectively deliver messages to their respective destinations. At this stage, the task of each node shifts from reasonably distributing replicas to quickly seeking for the destination node. The corresponding utility is calculated by

$$\begin{array}{cc}& U_{\text{forward}}\left(s,d\right)=\gamma \left(s\right)U_{\text{spec}}\left(s,d\right).\end{array}$$

(3)

As shown in (3), we only take $U_{\text{spec}}$ into account when considering the capability of forwarding. The reason behind this is that, different from the spraying stage that tends to spray copies as efficiently as possible, at the forwarding stage we desire each message copy to be relayed along a way similar to the shortest path to the destination. However, since it is difficult to mathematically get the strict shortest path, we employ the delegation forwarding strategy [15] to make each message replicated in a gradient direction to its destination, while introducing acceptable network costs. Besides, we still value the effect of buffer space by using the coefficient $\gamma (s)$ in (3), in the same way as (1).

Delegation forwarding (DF) [15] caught significant attention in the research community because of its simplicity and impressive performance. The main idea of DF is to replicate the copies of a packet only to the individual that has a higher utility value to the destination. With the increase of the utility level, a message holder's forwarding opportunity is expected to be decreased, which means that the number of copies duplicated for a message and its total number of forwarding operations are expected to be reduced, thus reducing the network cost. Reference [15] analyses that when the total number of nodes is N, delegation forwarding has the cost of $O(\sqrt{N})$ , while the naive method of forwarding achieves the cost of $O(N)$ .

As mentioned above, since delegation forwarding can efficiently reduce the routing costs, we devise the GSU- Spray forwarding strategy by referring the delegation forwarding strategy. Algorithm 2 shows the detailed information of the utility-based delegation forwarding process. The input of the algorithm is the information of $n_a$ and $n_b$ that includes their message collection and the respective utility metrics. The output is a list X with n elements that indicates the expected relay choice of all the n messages. When the algorithms are finished on the two nodes, the messages will be exchanged according to their corresponding list X. To further explain Algorithm 2, we assume that the algorithm is running on $n_a$ . Line 1 initializes the array X with each element to be set $\text{false}$ , which indicates that none of the messages would be replicated to $n_b$ . In lines 2–9, $x_k$ is calculated for each message $m_k$ , according to (3). The highest encountered utility value for each message is recorded by ${\tau }_k$ , which is set to be the larger value of $U_{\text{forward}}(a,d)$ and $U_{\text{forward}}(b,d)$ . Finally, the algorithm returns the array X, which includes the expected replication choice for every message.

Algorithm 2: Utility-based delegation forwarding algorithm.

Input: $n_a$ , $n_b$

Output: $X=\left[x_{\mathrm{1}},x_{\mathrm{2}},\dots ,x_n\right]\hspace{1em}\left(\forall i,x_i\in \left\{\text{true},\text{false}\right\}\right)$

   when $n_a$ gets in contact with $n_b$

(1)  local variables declaration: d

(2)   $X\leftarrow \left[\text{false},\text{false},\dots ,\text{false}\right]$

(3)  for   $m_k\in N_a$ .messageCollection()  do

(4)    $d\leftarrow$  destination  node  of   $m_k$

(5)    $U_{\text{forward}}\left(a,d\right)\leftarrow \mathrm{\gamma }\left(a\right)U_{\text{spec}}\left(a,d\right)$

(6)    $U_{\text{forward}}\left(b,d\right)\leftarrow \mathrm{\gamma }\left(b\right)U_{\text{spec}}\left(b,d\right)$

(7)   if   $U_{\text{forward}}\left(b,d\right)>{\mathrm{\tau }}_k$   then

(8)     $x_k\leftarrow \text{true}$

(9)   end if

(10)  ${\mathrm{\tau }}_k\leftarrow \max \left\{U_{\text{forward}}\left(a,d\right),U_{\text{forward}}\left(b,d\right)\right\}$

(11) end for

(12) return  X;

4. Analysis of Message Spraying Process

In this section, a Markov Chain Model is built to analyze the message spraying process of GSU-Spray. All the notations in this section are listed in Table 3. We assume that the mean contact time interval between any pair of nodes is T. The total time of spraying stage is split into many short time slots, each with the length T. $k·T$ stands for the length of the passed k time intervals. Our primary goal is to get the latency for a message to generate n copies during the spraying process. The Markov Chain is illustrated in Figure 4, where $\pi (n)$ denotes the state that there are n replicas for the message in the whole network, m and c are the average message size and the initial number of maximum copies of each message, respectively, and $\text{END}$ denotes the state that a replica meets the destination and the message transmission is completed. All other states have the opportunity to transfer to the state $\text{END}$ , which means that at least one of the replicas reaches the destination. There are bidirectional transition opportunities between $\pi (n)$ and $\pi (n-\mathrm{1})$ , because GSU-Spray keeps adjusting the number of messages copies between each pair of nodes. As stated in Section 3.1, either $n_a$ or $n_b$ should delete $m_k$ from the buffer if its $L(k)$ value is zero. Finally, there exists a case that after two nodes coming into contact, there is no change in the number of replicas of the message. This happens when both of the nodes do not hold any replica of the message or both of them hold the replica but both $L_{a_{\text{new}}}$ and $L_{b_{\text{new}}}$ are more than zero, which indicates that there is no need for transmission.

Table 3

Mathematical notations for Markov Chain analysis.

Notation	Meaning
T	The mean time interval of all connections
M	Total number of different generated messages
N	Total number of nodes in the network
B	Total buffer size of all nodes in the network
m	The average size of each message replica
c	The initial number of copies for each message
$\mathrm{\pi }(n)$	The state that there are n replicas
END	The state that a replica meets the destination

Figure 4

A Markov Chain that models a message replication process.

We firstly prove four lemmas, and then from these lemmas we get the transition probability of the Markov Chain. Finally we calculate $T(n)$ that represents the latency before generating n replicas of the message by using the transition probability of the Markov Chain. In our analysis, we give the assumption that $\mathrm{0}<\alpha$ and $\beta <\mathrm{1}$ . Besides, we exclude the factors of node energy and define that $\gamma (s)$ = unengaged buffer/total buffer.

Lemma 1.

The transition probability from state $\pi (n)$ to state $\pi (n+\mathrm{1})$ is

$$\begin{array}{cc}& \mathrm{2}·\frac{n}{N}·\frac{N-n-\mathrm{1}}{N-\mathrm{1}}·p^{\mathrm{2}}\left(n<\frac{B}{Mm}\right)·{\left({{\displaystyle \int }}_{\mathrm{0}}^{T·k}‍\frac{\mathrm{1}}{NT}{e}^{-x/NT}dx\right)}^{\mathrm{2}}.\end{array}$$

(4)

Proof.

When there are n nodes with replicas of the message, the probability for some node to hold a replica is $n/N$ . Excluding this node, there are $N-\mathrm{1}$ nodes left, of which there are $N-n-\mathrm{1}$ nodes (here the “ $\mathrm{1}$ ” means the destination node) that currently do not hold any replica of this message. When a node $n_a$ with a replica meets some node $n_b$ with no replica, the total number of replicas increases if and only if we have both $L_{a_{\text{new}}}\ne \mathrm{0}$ and $L_{b_{\text{new}}}\ne \mathrm{0}$ . Otherwise either $n_a$ keeps holding the replica or forwards the replica to $n_b$ and then deletes it from its own buffer. Thus we have the following probability equation:

$$\begin{array}{l}p\left[\pi \left(n\right),\pi \left(n+\mathrm{1}\right)\right]=\mathrm{2}·\frac{n}{N}·\frac{N-n-\mathrm{1}}{N-\mathrm{1}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}·P\left\{L_{a_{\text{new}}}\ne \mathrm{0},L_{b_{\text{new}}}\ne \mathrm{0}\right\},\end{array}$$

(5)

where we have the following:

$$\begin{array}{l}P\left\{L_{a_{\text{new}}}\ne \mathrm{0},L_{b_{\text{new}}}\ne \mathrm{0}\right\}\\ \hspace{1em}=P\left\{U_{\text{spray}}\left(a,d\right)\ne \mathrm{0},U_{\text{spray}}\left(b,d\right)\ne \mathrm{0}\right\}\\ \hspace{1em}=P\left\{\alpha g_a+(\mathrm{1}-\alpha )s_a\ne \mathrm{0},\alpha g_b+(\mathrm{1}-\alpha )s_b\ne \mathrm{0}\right\}\\ \hspace{1em}\hspace{1em}\phantom{hhhhhhhhhhhhhhhhhhhhhhhhh}(\mathrm{0}<\alpha <\mathrm{1})\\ \hspace{1em}=P\left\{U_{\text{gene}}\left(a\right)+U_{\text{spec}}(a,d)\ne \mathrm{0},U_{\text{gene}}\left(b\right)+U_{\text{spec}}\left(b,d\right)\ne \mathrm{0}\right\}\\ \hspace{1em}=P\left\{\gamma \left(a\right)\ne \mathrm{0},\varphi \left(a\right)\ne \mathrm{0}\right\}·P\left\{\gamma \left(b\right)\ne \mathrm{0},\varphi \left(b\right)\ne \mathrm{0}\right\}\\ \hspace{1em}=P\left\{\gamma \left(a\right)\ne \mathrm{0}\right\}·P\left\{\gamma \left(b\right)\ne \mathrm{0}\right\}·P\left\{\varphi \left(a\right)\ne \mathrm{0}\right\}·P\left\{\varphi \left(b\right)\ne \mathrm{0}\right\}\\ \hspace{1em}=P^{\mathrm{2}}\left\{\gamma \left(a\right)>\mathrm{0}\right\}·P^{\mathrm{2}}\left\{\varphi \left(a\right)>\mathrm{0}\right\}.\end{array}$$

(6)

The total buffer size of all nodes is represented as B. We denote the number of different kinds of generated messages as M. Then the average buffer size for each kind of message is $B/M$ . The number of current message replicas is n, and we know that the average size of each message replica is m, so the total size of all generated replicas of the current message can be represented as $m·n$ . We can conclude that the buffer space for the current message runs out if and only if $(n·m)/(B/M)<\mathrm{1}$ . So we have the following:

$$\begin{array}{cc}& P\left\{\gamma \left(a\right)>\mathrm{0}\right\}=P\left\{\frac{n·m}{B/M}<\mathrm{1}\right\}=p\left(n<\frac{B}{Mm}\right).\end{array}$$

(7)

Because the mean time interval between any pair of nodes contacting is T, the mean time for each node to meet any another node is $NT$ , and thus we assume that the waiting time for each node to meet another node obeys the exponential distribution with mean value $\lambda =NT$ . And consequently we have the following:

$$\begin{array}{cc}& P\left\{\varphi \left(a\right)>\mathrm{0}\right\}=p\left(t<Tk\right)={{\displaystyle \int }}_{\mathrm{0}}^{T·k}‍\frac{\mathrm{1}}{NT}{e}^{-t/NT}dt,\end{array}$$

(8)

where k stands for the number of passed time slots since the starting time of spraying and $k·T$ is the whole passed time period. Thus we have

$$\begin{array}{l}P\left\{L_{a_{\text{new}}}\ne \mathrm{0},L_{b_{\text{new}}}\ne \mathrm{0}\right\}=p^{\mathrm{2}}\left(n<\frac{B}{Mm}\right){\left({{\displaystyle \int }}_{\mathrm{0}}^{T·k}‍\frac{\mathrm{1}}{NT}{e}^{-t/NT}dt\right)}^{\mathrm{2}},\\ p\left[\pi \left(n\right),\pi \left(n+\mathrm{1}\right)\right]=\mathrm{2}·\frac{n}{N}·\frac{N-n-\mathrm{1}}{N-\mathrm{1}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}·p^{\mathrm{2}}\left(n<\frac{B}{Mm}\right)·{\left({{\displaystyle \int }}_{\mathrm{0}}^{T·k}‍\frac{\mathrm{1}}{NT}{e}^{-x/NT}dx\right)}^{\mathrm{2}}.\end{array}$$

(9)

Lemma 2.

The transition probability from state $\pi (n)$ to state $\pi (n-\mathrm{1})$ is

$$\begin{array}{l}\mathrm{2}·\frac{n}{N}·\frac{N-n-\mathrm{1}}{N-\mathrm{1}}\\ \hspace{0.17em}\hspace{0.17em}\hspace{1em}·\left[\mathrm{1}-p^{\mathrm{2}}\left(n<\frac{B}{Mm}\right){\left({{\displaystyle \int }}_{\mathrm{0}}^{T·k}‍\frac{\mathrm{1}}{T}{e}^{-x/T}dx\right)}^{\mathrm{2}}\right].\end{array}$$

(10)

Proof.

As stated in the proof process of Lemma 1, when there are two nodes contacting, the probability that one holds a replica and the other does not is $\mathrm{2}·(n/N)·(N-n-\mathrm{1})/(N-\mathrm{1})$ . Then the number of replicas decreases if and only if either $L_{a_{\text{new}}}=\mathrm{0}$ or $L_{b_{\text{new}}}=\mathrm{0}$ . Since $P\{L_{a_{\text{new}}}=\mathrm{0}$ or $L_{b_{\text{new}}}=\mathrm{0}\}=\mathrm{1}-P\{L_{a_{\text{new}}}\ne \mathrm{0}$ and $L_{b_{\text{new}}}\ne \mathrm{0}\}$ , we have thw following:

$$\begin{array}{l}p\left[\pi \left(n\right),\pi \left(n-\mathrm{1}\right)\right]=\mathrm{2}·\frac{n}{N}·\frac{N-n-\mathrm{1}}{N-\mathrm{1}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}·\left[\mathrm{1}-p^{\mathrm{2}}\left(n<\frac{B}{Mm}\right){\left({{\displaystyle \int }}_{\mathrm{0}}^{T·k}‍\frac{\mathrm{1}}{T}{e}^{-x/T}dx\right)}^{\mathrm{2}}\right].\end{array}$$

(11)

Lemma 3.

The transition probability from the state $\pi (n)$ to the state $\text{END}$ is

$$\begin{array}{cc}& \mathrm{2}·\frac{n}{N}·\frac{\mathrm{1}}{N-\mathrm{1}}.\end{array}$$

(12)

Proof.

When two nodes meet, the probability of either node to hold a replica is $n/N$ , and the probability of the other to be the destination node is $\mathrm{1}/(N-\mathrm{1})$ , so we have

$$\begin{array}{cc}& p\left[\pi \left(n\right),\text{END}\right]=\mathrm{2}·\frac{n}{N}·\frac{\mathrm{1}}{N-\mathrm{1}}.\end{array}$$

(13)

Lemma 4.

The transition probability for the state $\pi (n)$ to stay the same is

$$\begin{array}{l}\mathrm{1}-p\left[\pi \left(n\right),\pi (n+\mathrm{1})\right]-p\left[\pi \left(n\right),\pi (n-\mathrm{1})\right]\\ \hspace{1em}\hspace{1em}-p\left[\pi \left(n\right),\text{END}\right].\end{array}$$

(14)

Proof.

Since this concludes all other cases, we can directly get it from the normative theory of probability.

Theorem 5.

The transition probability in the Markov Chain between two states is

$$\begin{array}{l}{p}_{\mathrm{1}}=p\left[\pi \left(n\right),\pi \left(n+\mathrm{1}\right)\right]=\mathrm{2}·\frac{n}{N}·\frac{N-n-\mathrm{1}}{N-\mathrm{1}}\\ \hspace{1em}\hspace{1em}·p^{\mathrm{2}}\left(n<\frac{B}{Mm}\right)·{\left({{\displaystyle \int }}_{\mathrm{0}}^{T·k}‍\frac{\mathrm{1}}{NT}{e}^{-x/NT}dx\right)}^{\mathrm{2}},\\ p_{\mathrm{2}}=p\left[\pi \left(n\right),\pi \left(n-\mathrm{1}\right)\right]=\mathrm{2}·\frac{n}{N}·\frac{N-n-\mathrm{1}}{N-\mathrm{1}}\\ \hspace{1em}\hspace{1em}·\left[\mathrm{1}-p^{\mathrm{2}}\left(n<\frac{B}{Mm}\right){\left({{\displaystyle \int }}_{\mathrm{0}}^{T·k}‍\frac{\mathrm{1}}{NT}{e}^{-x/NT}dx\right)}^{\mathrm{2}}\right],\\ p_{\mathrm{3}}=p\left[\pi \left(n\right),\text{END}\right]=\mathrm{2}·\frac{n}{N}·\frac{\mathrm{1}}{N-\mathrm{1}},\\ p_{\mathrm{4}}=p\left[\pi \left(n\right),\pi \left(n\right)\right]=\mathrm{1}-p\left[\pi \left(n\right),\pi \left(n+\mathrm{1}\right)\right]\\ \hspace{1em}\hspace{1em}-p\left[\pi \left(n\right),\pi \left(n-\mathrm{1}\right)\right]-p\left[\pi \left(n\right),\text{END}\right].\end{array}$$

(15)

Proof.

From Lemmas 1–4, we get it immediately.

The minimum latency before generating n replica of a certain message is represented as $T(n)$ , which is calculated based on Theorem 5. Consider

$$\begin{array}{l}T\left(n\right)=p\left[\pi \left(n-\mathrm{1}\right),\pi \left(n\right)\right]·\left[T\left(n-\mathrm{1}\right)+T\right]\\ \hspace{1em}\hspace{1em}\hspace{1em}+p\left[\pi \left(n\right),\pi \left(n\right)\right]·\left[T\left(n\right)+T\right]\Rightarrow T\left(n\right)\\ \hspace{1em}\hspace{1em}=(p\left[\pi \left(n-\mathrm{1}\right),\pi \left(n\right)\right]·\left[T\left(n-\mathrm{1}\right)+T\right]\\ \hspace{1em}\hspace{1em}\hspace{1em}\phantom{hh}+p\left[\pi \left(n\right),\pi \left(n\right)\right]T)\\ \hspace{1em}\hspace{1em}\hspace{1em}\times {\left(\mathrm{1}-p\left[\pi \left(n\right),\pi \left(n\right)\right]\right)}^{-1}.\end{array}$$

(16)

By solving this recursive equation, we have the following:

$$\begin{array}{cc}& T\left(n\right)=\left\{\frac{\left\{\mathrm{1}-{\left(p_{\mathrm{1}}/(\mathrm{1}-p_{\mathrm{4}})\right)}^{n-\mathrm{1}}\right\}\left\{p_{\mathrm{1}}+p_{\mathrm{4}}\right\}}{\mathrm{1}-p_{\mathrm{4}}-p_{\mathrm{1}}}\right\}T.\end{array}$$

(17)

If we set the initial number of copies for each message c to be less than the constant $B/Mm$ , then we have $c<B/Mm$ , because the inequality $n\le c$ always holds in the spraying process. Consequently, we have $p(n<B/Mm)=\mathrm{1}$ in the meaning of the expected value. And thus given the parameters N and T, we can calculate the transition probability in each time slot and adaptively adjust the value c to guarantee the latency $T(n)$ under an acceptable level.

5. Simulation

The simulation is evaluated by the opportunistic network environment (ONE) [10]. In detail, we evaluate the Epidemic, binary Spray And Wait, Spray And Focus, and Encounter-based routing for performance comparison, using both synthetic mobility model and real trace. The simulation is grouped into the following categories: (1) varying buffer size in Helsinki City Model; (2) varying buffer size in Cambridge-iMote real trace; (3) varying message time-to-live in Helsinki City Model; (4) varying message time-to-live in Cambridge-iMote. The four comparison routing algorithms are listed as follows.

• (1)

  Epidemic [7]: in this routing scheme, packets received at intermediate nodes are forwarded to all the nodes neighbors (except the one who sends the packet) without employing any flooding control strategy.

• (2)

  Spray and Wait (S & W) [8]: spray stage: each node with more than one copy forwards half of the copies to the encountered node with no copy; Wait stage: if the destination is not found in the spray stage, the copy carriers wait for the destination. This algorithm only employs an unaware utility that assigns a maximum number of replicas for each message.

• (3)

  Spray and Focus (S & F) [9]: the spray stage of S & F is the same as in binary S & W that symmetrically distributes the message replicas. The difference is that S & F adopts the focus phase instead of wait phase, decreasing the delivery delay via a utility forwarding approach. The employed utility is only destination aware (specific).

• (4)

  Encounter-Based Routing (EBR) [10]: EBR is an asymmetrical spray-based routing protocol, which takes advantage of the observed mobility property of certain network, assuming the future rate of node encounters can be roughly predicted by historical information. The assumption behind it is that nodes experience a large number of encounters that would have a higher potential to relay the message to final destination. The employed utility for distributing the replicas is only self aware (general).

For simplification, in our simulation, the self-aware variable $\gamma (s)$ for node $n_s$ is set to be unengaged buffer/total buffer. For the purpose of fairness, the initial number of copies for the four algorithms S & W, S & F, EBR, and our proposed routing is set to be the same, which is a recommended value between 10% and 15% of the total number of nodes in each scenario. We compare the five different routing protocols based on the following criteria.

• (1)

  Delivery Ratio: normally, the ultimate goal of routing in DTNs is to achieve great delivery performance. This criteria is the measure of delivery capability for each protocol. When the network resource is sufficient, Epidemic routing usually has the best delivery performance. This is because Epidemic routing always finds the best possible path to the destination. Therefore it represents the baseline for the best possible delivery performance.

• (2)

  Average Latency: end-to-end latency is another important concern in DTN routing design. Long average latency means that the message must occupy valuable buffer space for a longer time, and consequently we desire a low latency value.

• (3)

  Overhead Ratio: it is desirable to have a low overhead ratio, since it reflects the efficiency of message transmission. Overhead ratio is defined to be the number of relay operations (excluding the delivery action) over the number of total delivered messages.

• (4)

  Average Hop Count: we expected to minimize the number of hops that a message must take in order to reach the destination.

5.1. Simulation in Helsinki City Scenario

5.1.1. Performance Evaluation by Varying Buffer Size

In Helsinki City Scenario [19], the nodes are assumed to be users with mobile phones or similar devices, using Bluetooth interface at 250 KBps bandwidth and 10 m transmission range. In this case, the initial free buffer size of each node is set to be small, which ranges from 5 M to 55 M. There are six trams following predefined routes, and there is an extra high-speed interface at 10 MBps bandwidth and 1000 m transmission range for the communication between trams. Two thirds of the remaining nodes are pedestrians and one third are cars. The speed of cars is set to be 10–50 km/h and the speed of trams 25–36 km/h, with the pause time of 10–120 s and 10–30 s, respectively. Both pedestrians and cars randomly choose their destinations on the map and move along the shortest path. The parameters settings are listed in Table 4.

Table 4

Simulation settings of Helsinki City Scenario.

Parameter name	Range (default value)
Number of nodes	126
World size ( $m\times m$ )	$\mathit{4500}\times \mathit{3000}$
Initial tickets number	13
Message TTL (min)	180–480 (300)
Simulation time (hours)	12
Message size (KB)	500–1024
Pedestrian buffer (MB)	5–55 (5)
Tram buffer (MB)	500
Bluetooth range (m)	10
Highspeed range (m)	1000
Bluetooth bandwidth (KBps)	250
Highspeed bandwidth (MBps)	10
Pedestrian speed (m/s)	0.5–1.5
Message interval (s)	35–40
GSU-Spray· $\mathrm{\alpha }$	0.7
GSU-Spray· $\mathrm{\lambda }$	10.0

Regarding the results in Figures 5(a), 5(b), 5(c), and 5(d), GSU-Spray achieves the highest delivery ratio and the lowest average latency. The overhead ratio of GSU-Spray protocol is almost as low as S & W and S & F and is much lower than that of Epidemic and EBR. However the average hop count is higher than Epidemic and EBR when the buffer size is more than 15 M.

Figure 5

Buffer size versus delivery ratio, average latency, overhead ratio, and average hop count (Helsinki City Scenario).

The result in Figure 5(a) shows that GSU-Spray significantly outperforms Epidemic and EBR but has a slightly higher delivery ratio than S & W and S & F. However, in Figure 5(b), it is obvious that the average latency of GSU-Spray is the lowest among all protocols. This is because GSU-Spray adaptively adjusts the number of message copies between each pair of nodes, thus making the message copies have a higher probability to meet the destination. Another reason is that GSU-Spray employs the delegation forwarding method to replicate the message in a gradient way to the destination, thus lowering the average latency of each message. However, from Figure 5(d), we see that the average hop count of GSU-Spray is relatively higher than S & W and is approximately equal to S & F. The reason is that, compared with S & W, our proposed routing employs delegation forwarding instead of waiting in the second stage of routing and this strategy is similar to S & F. When the buffer size is more than 15 M, the average hop count is higher than both Epidemic and EBR. Usually, there is sometimes a trade-off between latency and hop count, and our proposed algorithm tends to give priority to optimize the former criteria.

There are two stages of GSU-Spray protocol. In the spraying stage, the maximum number of replicas for each message is fixed. In the forwarding stage, the delegation forwarding method is employed to control the cost in $O(\sqrt{N})$ . Consequently, GSU-Spray generates much fewer copies for each message than Epidemic that employs the flooding strategy. The smaller number of message copies leads to the fewer relay operations, which leads to the greater efficiency per transmission operation. So GSU-Spray has much lower overhead ratio than Epidemic, as illustrated in Figure 5(c). Though the maximal number of copies of EBR is constrained, the overhead ratio of EBR is also very high. Since the utility function in EBR only considers the encounter rate of nodes, the simulation results show that the relay operation of EBR is relatively inefficient. S & W distributes the copies by using the least relay operations (not the least time), and thus it can be regarded as the lowest bound of overhead for GSU-Spray algorithm. We can see from Figure 5(c) that the overhead ratio of GSU-Spray is almost the same as S & W and S & F. However GSU-Spray outperforms S & W and S & F in both delivery ratio and average latency.

5.1.2. Performance Evaluation by Varying Message TTL

In the simulation of varying message time-to-live, we set the node buffer size (only for cars and pedestrians, not for trams) constant at 5 MB. The result in Figure 6(a) shows that GSU-Spray outperforms the other four routing algorithms in message delivery ratio. As same as illustrated in Figure 5(b), the average latency of GSU-Spray also keeps in the lowest level among all protocols in Figure 6(b). In addition, GSU-Spray performs well in both overhead and average hop count, as shown in Figures 6(c) and 6(d).

Figure 6

Message TTL versus delivery ratio, average latency, overhead ratio, and average hop count (Helsinki City Scenario).

The result in Figure 6(a) shows that GSU-Spray routing significantly outperforms the other protocols. The performances of S & W and S & F are approximately equal. In the forwarding stage, since we employ delegation strategy to confine the average cost of message copies, the number of generated message copies is much smaller than Epidemic, thus avoiding the buffer resource from running out quickly. As a general utility-based routing, EBR has a relatively lower delivery ratio than the others. GSU-Spray has a comparably better performance than S & W and S & F, mostly because it is an asymmetrical spray routing algorithm that utilizes both general and specific utility metrics. Besides, in the second stage of GSU-Spray, the delegation forwarding scheme is employed. And that is also the reason that the average latency of GSU-Spray is the lowest among all protocols, as illustrated in Figure 6(b).

From Figures 6(a), 6(b), 6(c), and 6(d) we know that the message time-to-live property does not have apparent influence on the routing performance. As shown in Figure 6(d), GSU-Spray performs well in average hop count. In this simulation scenario, the bottle neck factor of routing is the buffer size. The simulation result shows that GSU-Spray wins out in three criteria and has the same average hop count performance as S & F. Thus we can conclude that GSU-Spray is a good choice in the network scenario of scare buffer resource.

5.2. Simulation in Cambridge-iMote Trace

To evaluate the performance of our proposed routing algorithm in the real world scenario, we use the Cambridge Haggle trace dataset. This trace includes Bluetooth sightings by groups of users carrying small devices (iMotes) for two months in various locations that we expected many people to visit such as grocery stores, pubs, market places, and shopping centers in and around the city of Cambridge, UK. Mobile users in this experiment mainly consisted of students from Cambridge University who were asked to carry these iMotes with them at all times for the duration of the experiment. In addition to this, the experiment deployed a number of stationary nodes in various locations that we expected many people to visit such as grocery stores, pubs, market places, and shopping centers in and around the city of Cambridge, UK. A stationary iMote was also placed at the reception of the Computer Lab in Cambridge University, in which most of the experiment participants are students. The data was gathered from 36 mobile participants and 18 fixed locations. The settings of this simulation are listed in Table 5.

Table 5

Simulation settings of Cambridge-iMote trace.

Parameter name	Range
Number of nodes	36
Initial tickets number	5
Message TTL (min)	600–2100 (1200)
Simulation time (days)	11.5
Message size (KB)	500–1024
Device buffer (MB)	50–300 (200)
Interface bandwidth (KBps)	250
Message interval (s)	35–40
GSU-Spray· $\mathrm{\alpha }$	0.3
GSU-Spray· $\mathrm{\lambda }$	1.0

5.2.1. Performance Evaluation by Varying Buffer Size

In this real trace simulation, the buffer size is set to be much larger than that in Helsinki City Scenario. Figure 7(a) shows that the delivery ratio of GSU-Spray is the highest among all these protocols. When the buffer size is larger than 75 MB, GSU-Spray wins out EBR in delivery performance. The results show that in social mobile DTN scenarios the contact duration is a more accurate property that reflects the prospective throughput among nodes than contact frequency. Notice that in this real trace simulation, we set the parameter λ to be 1.0, which is nine times less than the value of 10.0 in Helsinki City Scenario, thus raising the metric's sensitivity to contact duration time of GSU-Spray.

Figure 7

Buffer size versus delivery ratio, average latency, overhead ratio, and average hop count (Cambridge-iMote).

Regarding the result in Figure 7(b), GSU-Spray has the highest latency. S & W stays in the lowest latency level, while its delivery performance is unacceptable. The reason is that the messages in statistics are mainly composed of those that can be delivered quickly. A number of messages that cannot be delivered in a short period are dropped during the routing process. From all the four subfigures of Figure 7, we can see that the buffer resource is not the bottle neck factor of routing performance when it is larger than 150 MB, and in this case GSU-Spray still outperforms Epidemic in delivery performance. As illustrated in Figures 7(a) and 7(b), the result data of GSU-Spray is near to that of Epidemic. Our future work in this field is to further reduce the latency of our proposed algorithm.

Now we focus on the comparison of the three algorithms, Epidemic, EBR, and our proposed GSU-Spray. If a high delivery ratio is expected with the need of an acceptable overhead cost, GSU-Spray is expected to be employed. If we want a lower end-to-end latency, it is more desirable to employ EBR, which outperforms Epidemic and GSU-Spray in average latency performance and is simpler and easier to implement.

5.2.2. Performance Evaluation by Varying Message TTL

In the simulation shown by Figure 8, we set the buffer size constant at 200 MB. As shown in Figure 8(a), with the increase of preassigned time-to-live value, the delivery performance of all these algorithms enhances. Our proposed GSU-Spray still keeps a high delivery ratio approximate to Epidemic. As shown in Figure 8(c), the overhead ratio increases more slowly than that of Epidemic. When there is no need for keeping low average hop count, GSU-Spray has an overall good performance in this real trace scenario.

Figure 8

Message TTL versus delivery ratio, average latency, overhead ratio, and average hop count (Cambridge-iMote).

Figure 8(b) depicts that all four algorithms have slight differences in the performance of average latency. Besides, the growth trend of latency keeps the same. When the message TTL is set to be larger, all these algorithms have a relatively higher average latency. Nevertheless the delivery ratio also rises. However, by comparing Figures 8(a) and 8(b), the latency rises much quicker than delivery ratio with the increase of message TTL. Thus we can infer that there are some messages that are hard to be delivered in a short period. Even so, this can be alleviated by using the Markov Model to adaptively adjust the initial number of copies c, as stated in Section 4. In Figure 8(d), GSU-Spray has the highest average hop count value, which is however slightly higher than Epidemic.

In conclusion, by referring to the Helsinki City Scenario, we know that our proposed GSU-Spray has relatively better performance when the buffer resource is scarce. As illustrated in the simulation result of Cambridge-iMote, since the buffer resource is no longer the bottle neck of routing performance, Epidemic and EBR also have good performance. However, when there is no need for keeping low average latency, if we want to promote the delivery performance to a higher level, GSU-Spray is a better choice. What is important is that GSU-Spray is the only routing algorithm that has overall good performance in the two different scenarios.

6. Related Work

Reference [20] presents two multicopy forwarding protocols called optimal opportunistic forwarding (OOF) and OOF-, which maximize the expected delivery rate and minimize the expected delay, respectively, while requiring that the number of forwarding operations per message does not exceed a certain threshold. Reference [21] applies the evolutionary games to noncooperative forwarding control in MDTNs, of which the main focus is on mechanisms to rule the participation of the relays to the delivery of messages in DTNs. Reference [12] provides a reliable data delivery scheme for mobile sensor networks with an enhanced delaying technique. Nodes estimate connectivity and expect interencounter time with sink nodes. Connectivity is estimated based on ratio of past and present connections. When the connectivity is unreliable, nodes delay the transmission for the remaining interencounter duration or per-hop lifetime. Reference [22] theoretically proves that considering both factors leads to higher throughput than considering only contact frequency. To fully exploit a social network for high throughput and low routing delay, the authors propose a social network oriented and duration utility-based distributed multicopy routing protocol for DTNs. In [11], the authors find that it is wise to wait till much better opportunities arise to minimize the communication cost without degrading the delivery ratio and latency. Consequently a universal scheme, named E-Scheme, is proposed to improve routing on the delivery probability metric. In [23], the authors propose a distributed optimal community-aware opportunistic routing (CAOR) algorithm that computes the minimum expected delivery delays of nodes through a reverse Dijkstra algorithm and achieves the optimal opportunistic routing performance. By proposing a home-aware community model, whereby turning an MON into a network that only includes community homes, the computational cost and maintenance cost of contact information are greatly reduced.

7. Conclusion

In this paper, we propose a general and specific utility-based adaptive routing algorithm GSU-Spray for mobile DTNs. Different from the current stochastic routing protocols that forward messages according to a contact frequency-based utility, our proposed algorithm utilizes the contact duration time as the criterion to evaluate the relationship between nodes. Consequently by combining the self-aware and destination-aware utility metric, we design two synthetical metrics to indicate the suitability of a node to be the relay for a certain message, which are employed in the spraying stage and forwarding stage, respectively. When calculating the destination-aware utility, rather than simply accumulating every contact duration time for each node, we design a function by integrating an exponential function $e^{-\lambda t}$ in each duration time interval. Consequently the sensitivity to the contact duration is controlled by the parameter λ. In order to quickly complete the task of message copies spreading, we theoretically analyze the replication process of spraying stage of GSU-Spray and derive a function of the relationship between the expected latency and the number of message copies. Thus the expected latency can be kept under a certain level by dynamically adjusting the preassigned number of copies of each message during the routing process. Simulation results show that GSU-Spray outperforms Epidemic, S & W, S & F, and EBR under the synthetic mobility model and real trace dataset. Observed from the simulation results, GSU-Spray is the only algorithm that achieves comparable performances under the two different scenarios. Our future work will focus on further reducing the average latency of GSU-Spray and evaluating its performance on real-world testbed.