Optimal Control of Epidemic Routing in Delay Tolerant Networks with Selfish Behaviors

Abstract

Most routing algorithms in delay tolerant networks (DTN) need nodes serving as relays for the source to carry and forward message. Due to the impact of selfishness, nodes have no incentive to stay in the network after getting message (e.g., free riders). To make them be cooperative at specific time, the source has to pay certain reward to them. In addition, the reward may be varying with time. On the other hand, the source can obtain certain benefit if the destination gets message timely. This paper considers the optimal incentive policy to get the best trade-off between the benefit and expenditure of the source for the first time. To cope with this problem, it first proposes a theoretical framework, which can be used to evaluate the trade-off under different incentive policies. Then, based on the framework, it explores the optimal control problem through Pontryagin's maximum principle and proves that the optimal policy conforms to the threshold form in certain cases. Simulations based on both synthetic and real motion traces show the accuracy of the framework. Through extensive numerical results, this paper demonstrates that the optimal policy obtained above is the best.

1. Introduction

With the increasing of mobile operating systems, such as iPhone OS, Android, and Windows Phone OS, mobile phones have already evolved from simple voice communication means into powerful devices able to provide a variety of services to users. For example, they can transfer the videos or music in a peer-to-peer (P2P) way through the short-range communication technologies (Bluetooth, WiFi, etc.) in them. Due to the limited communication range or mobility nature, it is hard to maintain the continuous end-to-end path between them as for classic Internet P2P applications [1]. Obviously, such network belongs to delay tolerant networks (DTN), in which end-to-end path between communication nodes may not exist [2]. In particular, the concept of DTN is proposed to support many new emerging networking applications, and other classic examples include deep-space exploration [3], military networks [4], and vehicular networks [5].

Because the communication opportunity is uncertain, message propagation in DTN often needs the help from others. In particular, nodes in DTN adopt a store-carry-forward communication strategy. This strategy exploits the opportunistic connectivity and node mobility to relay and carry messages. In other words, when the next hop is not available for the current node, it will store the message in its buffer, carry the message along the movement, and forward it until a new communication opportunity arises. Obviously, this method needs nodes working in a cooperative way. That is, nodes should stay in the network and forward message to others after getting message. However, nodes have no incentive to stay in the network after getting message due to the selfish nature [6, 7]. In particular, nodes may leave the network at once when it receives message, and these nodes can be seen as free riders [6, 7]. For example, users may make their communication devices (e.g., Bluetooth) off to save their limited energy. If all nodes in the network become free riders, other nodes can get message only from the source, and this is similar to the direct transmission protocol [8], which is very inefficient. In fact, the source can obtain certain benefit if other nodes get message timely. For example, if the source is the advertiser, it is good for it to make other nodes (consumers) get the message (advertisement) timely. In addition, such benefit may be varying with time. For example, the sooner the nodes get message, the more the benefit will be. Therefore, the source has the incentive to push the message to other nodes timely. To achieve this goal, it has to pay certain reward to the relay nodes to make them be cooperative. In addition, such reward may be varying with time too. For example, the longer the time nodes stay in the network, the more the energy may be used, so nodes may ask for more rewards. In fact, nodes (e.g., phone, PDA) are often devices that can be manipulated by humans [9, 10], and the buffer space or the forwarding ability of nodes can be seen as goods. Therefore, the event that the source requests help from other nodes can be seen as the event that the source buys certain goods from humans. The things that are used to buy goods by the source may be virtual currency [11] or discount of service [12] and so forth. Therefore, the message propagation process can be seen as the commodities trading process, and humans want to maximize its reward in this process. Therefore, these humans may adjust the price of their goods according to the market state. For example, if the remaining lifetime of message is shorter, they may think that the source is eager to transmit the message as soon as possible, so they think that their goods (e.g., the forwarding service) are important for the source. In this case, they may increase the price. On the other hand, if the remaining lifetime of the message is long, they may think that the source may be not eager to transmit the message quickly and is not willing to pay too many fees. In this case, they may help the source with only a little reward. Therefore, the price of the goods (e.g., the forwarding service) may be varying with time. In this environment, whether to make nodes be cooperative at specific time is an important problem for the source. For example, suppose that node j is willing to help the source by charging m nuggets (price of the goods) at time $t_1$ , but it only requires n nuggets at time $t2$ . If $m>n$ and $t1<t2$ , the source can pay less nuggets when it requires help from node j at time $t2$ , but this may decrease the message propagation speed, so it may be not good for the source. On the other hand, if the source uses fewer nuggets to make node j be cooperative, the remaining nuggets are more, so the source may have enough nuggets to make more nodes be cooperative and this is good for the source. Therefore, the optimal policy of the source is related to time. In this case, how to maximize the total income of the source is not a simple problem and this will be our main contribution.

The main contribution of this paper can be summarized as follows.

• (i)

We consider the optimal incentive policy to get the best trade-off when the reward is varying with time for the first time.

(ii)

We propose a unifying framework through a continuous time Markov process, which can be used to evaluate the trade-off between the benefit and expenditure of the source under different incentive policies.

(iii)

Then based on the framework, we formulate an optimization problem. Through Pontryagin's maximum principle, we explore the optimal control problem and prove that the optimal policy conforms to the threshold form in some cases. By comparing the simulation results with the theoretical results, we show that our theoretical framework is very accurate. In addition, we compare the performance of the optimal policy with other policies through extensive numerical results and find that the optimal policy obtained by our model is the best.

2. Related Works

In fact, our work is similar to the optimal controlling problem for epidemic routing algorithm (ER), such as the works in [13, 14]. These works mainly study how to maximize the average delivery ratio when the energy is limited, and the energy consumption for forwarding the message once is not related to time. Therefore, these methods cannot be used to solve the optimization problem in our paper, in which the reward that the relay nodes require is related to time. On the other hand, the work in [15] studies similar problem as that in this paper, but it tries to get the optimal forwarding policy when the total fees are limited. However, we study the trade-off between the income and expenditure, so they are different.

There are many other selfish behaviors, such as individual selfishness and social selfishness [16, 17]. At present, some works study the impact of these selfish behaviors. For example, Li et al. study the impact of social selfishness on the epidemic routing protocol [17]. Then, they explore the impact of both individual selfishness and social selfishness on multicasting in DTN [18]. However, these selfish behaviors depend on the social relations between nodes. For example, the social selfishness denotes the selfish behavior between friends. Therefore, the distribution of friends may have certain impact. Existing studies have shown that the number of friends of nodes may be different. In particular, the distribution of friends may conform to a power law distribution [19]. Therefore, if we consider those selfish behaviors, we have to classify the nodes according to their number of friends, and this will be a controlling problem with multiple parameters. Such interesting problem is an extension of our work, and we will study it deeply in the future.

3. Network Model

Suppose that there are one source S, N relay nodes, and a destination node D. At time 0, only the source has message, and it wants to make the destination obtain the message before the maximal lifetime T. To achieve this goal, the source needs the help from others. However, it has to pay certain reward every time it makes a relay node be cooperative, so it may not do this all the time. Note that only the relay nodes that have message can forward it to others, so the source only makes these nodes be cooperative. In other words, the source is not willing to pay reward to nodes that do not have message. In this paper, we assume that the source makes a relay node (e.g., node m) that has message cooperative with probability $\mu (t)$ at time t, and then m can get the required reward denoted by $\alpha (t)$ . As shown in previous section, the function $\alpha (t)$ may be varying with time. On the other hand, the source can obtain certain benefit denoted by $\beta (t)$ if the destination gets message at time t. In addition, we assume that all of the relay nodes are willing to receive message. In fact, if they get message, they may get certain reward from the source, so they have incentive to receive message and this assumption is rational.

Nodes in the network can communicate with each other only when they come into the transmission range of each other, which means a communication contact, so the mobility rule of nodes is critical. In this paper, we assume that the occurrence of contacts between two nodes follows a Poisson distribution. This assumption has been used in wireless communications for many years. At present, some works show that this assumption is only an approximation to the message propagation process. For example, the work in [20] reveals that nodes encounter with each other according to the power law distribution. However, it also finds that if you consider long traces, the tail of the distribution is exponential. Furthermore, a more recent work in [21] studies the vehicles’ dataset in large-scale urban environment and finds that the intermeeting time can be modeled by a three-segmented distribution. Though the first and second parts of the contact intervals do not obey the exponential distribution, it also recognizes that the tail obeys the exponential distribution. In addition, the work in [22] shows that individual intermeeting time can be shaped to be exponential by choosing an approximate domain size with respect to the given time scale. Moreover, there are also some works, which describe the intermeeting time of human or vehicles by exponential distribution and validate their model experimentally on real motion traces [23, 24]. For this reason, the exponential model is still widely used in many existing works, such as [25–27]. In this paper, we also use such model and assume that the intermeeting time between two nodes follows an exponential distribution with parameter λ. Simulations based on both synthetic and real motion traces show that our theoretical framework based on such assumption is very accurate.

Besides the intermeeting time, many other factors can have certain impact on the routing performance, such as the contact duration, bandwidth, and message size. If the bandwidth is big enough, the message may be transmitted successfully in one contact. However, if the bandwidth is too small, it may be hard to transmit the message to one contact, even though the contact duration is long. At present, some works find that the distribution of the contact duration may conform to the Pareto distribution [28, 29]. However, the Pareto distribution is hard to be used to analyze the routing performance theoretically. Therefore, most of the previous works which explore the routing performance based on the theoretical method ignore the impact of the contact duration and assume that a contact is long enough to transmit the message, such as [13–17]. In this paper, we use the same assumption. Note that the assumption is rational when the message is small or the bandwidth is very big.

The commonly used variables of this paper can be seen in Table 1.

Table 1

The list of commonly used variables.

N	Number of relay nodes
S	The source node
D	The destination
λ	Exponential parameter of the intermeeting time (the biggest value)
T	The maximal lifetime of the message
$\mu (t)$	The probability that the source makes a relay node cooperative at time t
$\alpha (t)$	The required reward at time t
$\beta (t)$	The benefit the source can get if the destination gets the message at time t
$X(t)$	The number of relay nodes carrying message at time t
$F(t)$	The delivery ratio at time t
C	The maximal energy

4. Problem Formulation

4.1. Theoretical Framework

Let $X(t)$ denote the number of relay nodes that have message at time t. Because only the source has message at time 0, we have $X(0)=0$ . Given a small time interval $\Delta t$ , we have

$$\begin{array}{cc}& X\left(t+\Delta t\right)=X\left(t\right)+{\displaystyle \sum }_{m\in \left(Y\left(t\right)\right\}}^{}{\phi }_m\left(t,t+\Delta t\right).\end{array}$$

(1)

Symbol $\{Y(t)\}$ denotes the set of relay nodes that do not have message at time t, so the cardinality of this set is $N-X(t)$ . ${\phi }_m\hspace{0.17em}\hspace{0.17em}(t,t+\Delta t)$ denotes the event whether the relay node m gets messagein time interval $[t,t+\Delta t]$ . If ${\phi }_m(t,t+\Delta t)=1$ , we can say that node m successfully obtains message, but if ${\phi }_m(t,t+\Delta t)=0$ , this event does not happen. Note that a relay node can get message only from the source or other cooperative relay nodes. In addition, two nodes encounter with each other according to an exponential distribution with parameter λ. Therefore, node m encounters with a specific node (e.g., n) in time interval $[t,t+\Delta t]$ with probability $1-e^{-\lambda \Delta t}$ . If node n is the source, node m can get message immediately. However, if node n is a relay node, m can get message from n only when n is cooperative. In addition, a relay node is cooperative at time t with probability $\mu (t)$ , so the total probability that node m gets message in interval $[t,t+\Delta t]$ is

$$\begin{array}{cc}& p\left({\phi }_m\left(t,t+\Delta t\right)\right)=\mathrm{1}-e^{-\lambda \Delta t}{\left(\mathrm{1}-\mu \left(t\right)\left(\mathrm{1}-e^{-\lambda \Delta t}\right)\right)}^{X\left(t\right)}.\end{array}$$

(2)

Combining with (1) and (2), we can get

$$\begin{array}{l}E\left(X\left(t+\Delta t\right)\right)=E\left(X\left(t\right)\right)\\ +\left(N-E\left(X\left(t\right)\right)\right)E\left({\phi }_m\left(t,t+\Delta t\right)\right).\end{array}$$

(3)

Further, we can obtain

$$\begin{array}{cc}& \underset{\Delta t\to \mathrm{0}}{\lim }\frac{E\left({\phi }_m\left(t,t+\Delta t\right)\right)}{\Delta t}=\lambda \left(\mathrm{1}+\mu \left(t\right)X\left(t\right)\right).\end{array}$$

(4)

Then we have

$$\begin{array}{l}E\left(\dot{X}\left(t\right)\right)=\frac{E\left(X(t+\Delta t)\right)-E\left(X\left(t\right)\right)}{\Delta t}\\ =\left(N-E\left(X\left(t\right)\right)\right)\frac{E\left({\phi }_m\left(t,t+\Delta t\right)\right)}{\Delta t}\\ =\lambda \left(N-E\left(X\left(t\right)\right)\right)\left(\mathrm{1}+\mu \left(t\right)X\left(t\right)\right).\end{array}$$

(5)

One main metric of routing algorithm in DTN is the delivery ratio, which denotes the probability that the destination D obtains message within given time. Let $F(t)$ denote the delivery ratio when the given time is t. Before getting its value, we first give another symbol $H(t)=1-F(t)$ , which denotes the probability that D does not obtain message before time t. Moreover, let $H(t,t+\Delta t)$ denote the probability that D does not get message in time interval $[t,t+\Delta t]$ . Therefore, we have

$$\begin{array}{cc}& H\left(t+\Delta t\right)=H\left(t\right)H\left(t,t+\Delta t\right).\end{array}$$

(6)

Similar to the relay nodes, D may get message from the source or the cooperative relay nodes. Therefore, we have

$$\begin{array}{cc}& H\left(t,t+\Delta t\right)=e^{-\lambda \Delta t}{\left(\mathrm{1}-\mu \left(t\right)\left(\mathrm{1}-e^{-\lambda \Delta t}\right)\right)}^{X\left(t\right)}.\end{array}$$

(7)

Further, we can obtain

$$\begin{array}{cc}& E\left(\dot{H}\left(t\right)\right)=-\lambda E\left(H\left(t\right)\right)\left(\mathrm{1}+\mu \left(t\right)X\left(t\right)\right)\\ E\left(\dot{F}\left(t\right)\right)=\lambda \left(\mathrm{1}-E\left(F\left(t\right)\right)\right)\left(\mathrm{1}+\mu \left(t\right)X\left(t\right)\right).\end{array}$$

(8)

Let $U(t)$ denote the total income of the source till time t, which equals the result that the benefit takes away the expenditure. Therefore, we have

$$\begin{array}{l}U\left(t+\Delta t\right)=U\left(t\right)-\mu \left(t+\Delta t\right)\alpha \left(t\right)X\left(t+\Delta t\right)\Delta t\\ +\beta \left(t\right){\rho }_D\left(t,t+\Delta t\right).\end{array}$$

(9)

Time interval $\Delta t$ is very small, so we can assume that the behavior of the source remains unchanged. That is, the source makes a relay node that has message be cooperative with the same probability denoted by $\mu (t+\Delta t)$ in the time interval. In addition, the number of relay nodes that have message can be denoted by $X(t+\Delta t)$ . Because the source has to pay certain reward if it makes a relay node be cooperative and the reward is $\alpha (t)$ at time t, the total reward the source has to pay is $\mu (t+\Delta t)X(t+\Delta t)\alpha (t)\Delta t$ . In addition, if the destination gets message, the source can obtain certain benefit. Symbol $\rho (t,t+\Delta t)$ denotes whether D gets message in interval $[t,t+\Delta t]$ , so we can obtain (9).

Because nodes that have message do not receive the same message any more, if the event $\rho (t,t+\Delta t)$ happens, we can see that the destination D does not have message before. In other words, we have

$$\begin{array}{l}p\left({\rho }_D\left(t,t+\Delta t\right)=\mathrm{1}\right)=H\left(t\right)\left(\mathrm{1}-H\left(t,t+\Delta t\right)\right)\\ =F(t+\Delta t)-F\left(t\right).\end{array}$$

(10)

Combining with (9) and (10), we can obtain

$$\begin{array}{cc}& E\left(\dot{U}\left(t\right)\right)=\beta \left(t\right)E\left(\dot{F}\left(t\right)\right)-\mu \left(t\right)\alpha \left(t\right)E\left(X\left(t\right)\right).\end{array}$$

(11)

Based on (11), we have

$$\begin{array}{cc}& E\left(U\left(T\right)\right)={{\displaystyle \int }}_{\mathrm{0}}^T\left(\beta \left(t\right)E\left(\dot{F}\left(t\right)\right)-\mu \left(t\right)\alpha \left(t\right)E\left(X\left(t\right)\right)\right)dt.\end{array}$$

(12)

T is the maximal lifetime of the message, and our object is to maximize the value of $E(U(T))$ , which is a function about $\mu (t)$ . That is, our object is to solve the following question:

$$\begin{array}{l}\mathrm{Max}\phantom{\text{ect}\hspace{0.17em}\hspace{0.17em}\text{to}}\hspace{0.5em}E\left(U\left(T\right)\right)\\ \text{Subject}\hspace{0.17em}\hspace{0.17em}\text{to}\hspace{1em}\mu \left(t\right)\in \left[\mathrm{0,1}\right],\hspace{1em}t\in \left[\mathrm{0},T\right].\end{array}$$

(13)

4.2. Optimal Control

Obviously, the above question is an optimal control problem, and $\mu (t)$ is the control variable. We use Pontryagin's maximum principle in ([30, P. 109, Theorem 3.14]) to solve the above problem. According to the principle, we should first get the Hamiltonian function.

Let $((X,F),\mu )$ be an optimal solution. In particular, at time t, X denotes the value of $E(X(t))$ and F denotes the value of $E(F(t))$ . Similarly, μ denotes the value of $\mu (t)$ . According to [30], the Hamiltonian function can be got by the derivative of the objective function and the derivation of the corresponding state functions, so we can get the Hamiltonian H:

$$\begin{array}{lll}H\hfill & =\hfill & \beta \stackrel{.}{F}-\mu \alpha X+{\lambda }_F\stackrel{.}{F}+{\lambda }_X\stackrel{.}{X}\hfill \\ \hfill & =\hfill & \left(\beta +{\lambda }_F\right)\stackrel{.}{F}+{\lambda }_X\stackrel{.}{X}-\mu \alpha X\hfill \\ \hfill & =\hfill & \lambda \left(\beta +{\lambda }_F\right)\left(1-F\right)\left(1+\mu X\right)\hfill \\ \hfill & \hfill & +\lambda {\lambda }_X\left(1+\mu X\right)\left(N-X\right)-\mu \alpha X.\hfill \end{array}$$

(14)

Note that, at time t, α and β are simple expressions of $\alpha (t)$ and $\beta (t)$ , respectively. Based on (14), we have

$$\begin{array}{l}g=\frac{\partial H}{\partial \mu }=\lambda \left(\beta +{\lambda }_F\right)\left(\mathrm{1}-F\right)X\\ +\lambda {\lambda }_{X}X\left(N-X\right)-\alpha X.\end{array}$$

(15)

Then, we can get the costate or adjoint functions ${\lambda }_X$ and ${\lambda }_F$ based on the Hamiltonian H [30]:

$$\begin{array}{l}\dot{{\lambda }_F}=-\frac{\partial H}{\partial F}=\lambda (\beta +{\lambda }_F)(\mathrm{1}+\mu X)\\ \dot{{\lambda }_X}=-\frac{\partial H}{\partial X}=-\lambda (\beta +{\lambda }_F)(\mathrm{1}-F)\mu \\ +\lambda {\lambda }_X(\mathrm{1}+\mu X)-\lambda {\lambda }_X\mu (N-X)+\mu \alpha .\end{array}$$

(16)

The transversality conditions are shown as follows [30]:

$$\begin{array}{cc}& {\lambda }_F\left(T\right)={\lambda }_X\left(T\right)=\mathrm{0}.\end{array}$$

(17)

Then according to Pontryagin's maximum principle in ([30, P. 109, Theorem 3.14]), there exist continuous or piece-wise continuously differentiable state and costate functions, which satisfy

$$\begin{array}{cc}& \mu \in \arg \underset{\mathrm{0}\le {\mu }^{*}\le \mathrm{1}}{\max }\mathrm{\hspace{0.17em}\hspace{0.17em}}H\left({\lambda }_F,{\lambda }_X,\left(F,X\right),{\mu }^{*}\right).\end{array}$$

(18)

This equation between the optimal control parameter μ and the Hamiltonian H allows us to express μ as a function of the state $(X,F)$ and costate ( ${\lambda }_X,{\lambda }_F$ ), resulting in a system of differential equations involving only the state and costate functions and not the control function. In fact, this equation means that maximizing the value of $E(U(T))$ equals maximizing the corresponding Hamiltonian H. In particular, at given time t, the state $(X,F)$ and costate $({\lambda }_X,{\lambda }_F)$ can be seen as constants, and $\mu (t)$ can maximize H at this time. Therefore, according to (15), we can obtain the optimal policy as follows:

$$\begin{array}{cc}& \mu =\{\begin{array}{cc}\mathrm{1},\hfill & g>\mathrm{0}\hfill \\ \mathrm{0},\hfill & g<\mathrm{0}.\hfill \end{array}\end{array}$$

(19)

Below, we will prove that when the function of $\alpha (t)$ and $\beta (t)$ satisfies certain conditions, the optimal policy has a simple structure. The conditions are as follows: $\alpha (t)$ is increasing with time t, but $\beta (t)$ is no-decreasing function; $\alpha (t)$ and $\beta (t)$ are continuous and differentiable; they are nonnegative. In fact, the maximal lifetime $(T)$ of the message is fixed, so if the value of t is bigger, the remaining lifetime ( $T-t$ ) is shorter. In this case, the relay nodes may think that the source may be eager to transmit message to D quickly, so they may ask for more rewards. That is to say, if the value of t is bigger, the value of $\alpha (t)$ may be bigger. Therefore, the condition that $\alpha (t)$ is increasing is rational in some environments. On the other hand, it is better if the destination gets message earlier, so the assumption that $\beta (t)$ is no-decreasing function is rational in certain applications too.

If above conditions can be satisfied, the optimal policy conforms to the threshold form and has at most one jump. In particular, we have the following theorem.

Theorem 1.

If $\alpha (t)$ and $\beta (t)$ satisfy the above conditions, the optimal policy satisfies $\mu (t)=1$ , $t<h$ , and $\mu (t)=0$ , $t>h$ , $0\le h\le T$ .

Proof.

First, note that the functions $\alpha (t)$ and $\beta (t)$ are nonnegative. In addition, we simply use $X(t)$ , $Y(t)$ , and $F(t)$ to denote $E(X(t))$ , $E(Y(t))$ , and $E(F(t))$ in the proving process, respectively.

When $X=0$ , none of the relay nodes has message, so the value of μ cannot have any impact. Therefore, we only consider the case that $X>0$ . Based on (15), we define

$$\begin{array}{cc}& f=\frac{g}{X}=\lambda \left(\beta +{\lambda }_F\right)\left(\mathrm{1}-F\right)+\lambda {\lambda }_X\left(N-X\right)-\alpha .\end{array}$$

(20)

Then, we can get

$$\begin{array}{lll}\dot{f}\hfill & =\hfill & \lambda \left(\dot{\beta }+{\lambda }_F^{\cdot }\right)(1-F)-\lambda (\beta +{\lambda }_F)\dot{F}\hfill \\ \hfill & \hfill & +\lambda {\lambda }_X^{\cdot }(N-X)-\lambda {\lambda }_X\dot{X}-\dot{\alpha }\hfill \\ \hfill & =\hfill & \lambda \left(\dot{\beta }+{\lambda }_F^{\cdot }\right)(1-F)-\lambda \lambda (\beta +{\lambda }_F)(1-F)(1+\mu X)\hfill \\ \hfill & \hfill & +\lambda {\lambda }_X^{\cdot }(N-X)-\lambda {\lambda }_X\lambda (1+\mu X)(N-X)-\dot{\alpha }.\hfill \end{array}$$

(21)

Combining with (16), we have

$$\begin{array}{lll}\dot{f}\hfill & =\hfill & \lambda \dot{\beta }(1-F)+\lambda {\lambda }_X^{\cdot }(N-X)\hfill \\ \hfill & \hfill & -\lambda {\lambda }_X\lambda (1+\mu X)(N-X)-\dot{\alpha }\hfill \\ \hfill & =\hfill & \lambda \dot{\beta }(1-F)+\lambda (N-X)\left({\lambda }_X^{\cdot }-\lambda {\lambda }_X(1+\mu X)\right)-\dot{\alpha }.\hfill \end{array}$$

(22)

In addition, from (16), we can obtain

$$\begin{array}{lll}{\lambda }_X^{\cdot }\hfill & =\hfill & -\frac{\partial H}{\partial X}=-\lambda (\beta +{\lambda }_F)(1-F)\mu \hfill \\ \hfill & \hfill & \hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}+\lambda {\lambda }_X(1+\mu X)-\lambda {\lambda }_X\mu (N-X)+\mu \alpha \hfill \\ \hfill & =\hfill & -\mu (\lambda (\beta +{\lambda }_F)(1-F)+\lambda {\lambda }_X(N-X)-\alpha )\hfill \\ \hfill & \hfill & +\lambda {\lambda }_X(1+\mu X)\hfill \\ \hfill & =\hfill & -\mu f+\lambda {\lambda }_X(1+\mu X).\hfill \end{array}$$

(23)

Suppose that $f(s)=0$ ; we have

$$\begin{array}{l}\dot{{\lambda }_X}\left(s\right)=-\mu \left(s\right)f\left(s\right)+\lambda {\lambda }_X\left(s\right)(\mathrm{1}+\mu \left(s\right)X\left(s\right))\\ =\lambda {\lambda }_X\left(s\right)\left(\mathrm{1}+\mu \left(s\right)X\left(s\right)\right).\end{array}$$

(24)

Combining with (22), we can obtain

$$\begin{array}{lll}\dot{f}(s)\hfill & =\hfill & \lambda \dot{\beta }(s)(1-F(s))-\dot{\alpha }(s)\hfill \\ \hfill & \hfill & +\lambda (N-X(s))\left({\lambda }_X^{\cdot }(s)-\lambda {\lambda }_X(s)(1+\mu (s)X(s))\right)\hfill \\ \hfill & =\hfill & \lambda \dot{\beta }(s)(1-F(s))-\dot{\alpha }(s).\hfill \end{array}$$

(25)

Because $\alpha (t)$ is increasing with time t and $\beta (t)$ is no-decreasing function, we have

$$\begin{array}{c}\dot{\beta }\left(s\right)<\mathrm{0},\hspace{1em}\hspace{1em}\dot{\alpha }\left(s\right)>\mathrm{0}.\end{array}$$

(26)

Further, $1-F(s)\ge 0$ , so we have

$$\begin{array}{cc}& \dot{f}\left(s\right)\mathrm{\hspace{0.17em}\hspace{0.17em}}=\lambda \dot{\beta }\left(s\right)(\mathrm{1}-F\left(s\right))-\dot{\alpha }\left(s\right)<\mathrm{0}.\end{array}$$

(27)

That is, if $f(s)=0$ , the function will decrease at time s.

Then we assume that $f(s)<0$ . Based on (19), we have $\mu (s)=0$ . Combining with (22) and (23), we also can obtain (25). Further, we can get (27) and know that $f(t)$ will decrease at time s.

In summary, if $f(s)\le 0$ , $f(t)$ will decrease at time s. Therefore, if $f(s)\le 0$ , we have $f(t)<0$ , $t>s$ . Further, according to (19), the optimal policy satisfies $\mu (t)=1$ , $t<h$ , and $\mu (t)=0$ , $t>h$ , $0\le h\le T$ . That is, once $\mu (t)\ne 1$ , it will be 0 later and then remain unchanged all the time, so the optimal policy conforms to the threshold form and has at most one jump. This proves that Theorem 1 is correct.

5. Model Validation and Performance Analysis

5.1. Model Validation

In this section, we will check the accuracy of our framework by comparing the theoretical results obtained by our model with the simulation results. We run several simulations using the opportunistic network environment (ONE) [31] based on three different scenarios. In the first one, we use the famous random waypoint (RWP) mobility model [32], which is commonly used in many mobile wireless networks. There are totally 500 nodes, and all of these nodes move according to the RWP model within a 10000 m × 10000 m terrain with a scale speed chosen from a uniform distribution from 4 m/s to 10 m/s. The communication range is 5 m. Moreover, the source and destination nodes are randomly selected among these nodes. In the second scenario, we use a real motion trace from about 2100 operational taxis for about one month in Shanghai city collected by GPS [33]. The location information of the taxis is recorded at every 40 seconds with the area of 102 km². We randomly pick 500 nodes from this trace. In addition, the source and destination nodes are randomly selected among these nodes too. The third scenario is based on the dataset collected in the Infocom 2005 conference [34]. In particular, this dataset includes 41 attendees, who connect with each other by Bluetooth. Among those attendees, we randomly select two nodes as the source and destination, respectively.

The functions of $\alpha (t)$ and $\beta (t)$ may be any form. For simplicity, we define $\alpha (t)=(1-e^{-t/10000})/1000$ and $\beta (t)=1000e^{-t/10000}$ . In fact, the value of $\mu (t)$ may be any value between 0 and 1 at time t too. Because our main goal is to check the accuracy of our theoretical framework, we only consider two special cases: case  1: $\mu (t)=1$ , $t\ge 0$ ; case  2: $\mu (t)=0$ , $t\ge 0$ . The first case means that the sources make nodes be cooperative all the time and message is propagated according to epidemic routing (ER) algorithm, but in the second case, the source does not ask for help from others at all, so message is propagated according to the direct transmission algorithm (DT). At the starting of each simulation, one message is generated with maximal lifetime T, and each simulation is repeated 20 times. In addition, let the maximal message lifetime T increase from 0 to 50000 s.

Based on these settings, we can get Figures 1, 2, and 3, respectively.

Figure 1

Simulation and numerical results comparison of total fees with RWP mobility model.

Figure 2

Simulation and numerical results comparison of total fees with Shanghai city motion trace.

Figure 3

Simulation and numerical results comparison of total fees with Infocom 05 motion trace.

From the results, we can see that the average deviation between the theoretical and simulation results is very small. For example, the average deviation is about 4.22% for the RWP mobility model and 5.01% for the Shanghai city motion trace. For the Infocom 2005 dataset, the average deviation is about 7.12%. Though the deviation is bigger than that in RWP and Shanghai city motion traces, it also can be seen very accurately. This demonstrates the accuracy of our theoretical framework. For this reason, we can use the numerical results obtained by our theoretical framework to evaluate the performance of different policies.

In addition, the results above also show that the performance is different when the source adopts different policies. In particular, the results in Figures 1 and 2 show that it is not good for the source to request help all the time. For example, when the value of T is bigger than 4000 s in Figure 2, the total income of the source may be negative if it requests help all the time. This shows that the policy of the source can have important impact on its total income, and this means that our optimal control policy is necessary. Later, we will show that the optimal policy obtained by (19) is the best through extensive numerical results.

5.2. Performance Analysis with Numerical Results

In this section, we use the best fitting for the Shanghai city motion trace in the above simulation to describe the exponential distribution of the intermeeting time between nodes.

First, we evaluate the performance of the optimal policy obtained by (19). For comparison, we consider three other cases: case  1: $\mu (t)=1$ , $t\ge 0$ ; case  2: $\mu (t)=0$ , $t\ge 0$ ; case  3: random. The random policy means that the value of $\mu (t)$ is randomly selected from the interval $[\mathrm{0,1}]$ at time t. Other settings are the same as those in simulation, and then we can obtain Figure 4.

Figure 4

Performance comparison with different policies.

The result in Figure 4 shows that the optimal policy is the best one. Under the optimal policy, the source can always get the maximal total reward. This means that our optimal control policy is correct.

Now, we further compare the performance of different policies when the number of relay nodes is different. In this case, we assume that the maximal message lifetime T equals 10000 s, and let the number of relay nodes increase from 50 to 1000. Other settings remain unchanged. Numerical result is shown in Figure 5, and it demonstrates that the optimal policy obtained by (19) is the best too.

Figure 5

Performance comparison with different policies when the number of relay nodes is different.

In addition, total reward under the optimal policy is increasing with the number of nodes. In fact, when there are more nodes, the source can request help from more nodes at early time. Because the reward that the relay nodes request is increasing with time (e.g., $\alpha (t)=(1-e^{-t/10000})/1000$ is increasing function), this behavior will decrease the cost of the source and the source will stop requesting help at early time. As shown in Theorem 1, the source will stop making relay nodes be cooperativeat certain time (e.g., h). In particular, the optimal policy satisfies $\mu (t)=1$ , $t<h$ , and $\mu (t)=0$ , $t>h$ , $0\le h\le T$ . When the number of nodes is bigger, the value of h is smaller, so the source stops requesting help earlier and it will pay less reward. The result in Figure 6 shows that h is really decreasing with the number of nodes. When the number of relay nodes is smaller, the source has to ask for help for a longer time. For example, when there are 50 relay nodes, the source nearly requires help all the time.

Figure 6

The value of the threshold under the optimal policy when the number of relay nodes is different.

On the other hand, the result in Figure 6 also shows that the optimal policy really conforms to the threshold form. We can see the result in Figure 7 more clearly, when there are 500 and 1000 relay nodes, respectively. That is, the source asks for help from others with probability 1 before the threshold h, and then it stops doing this.

Figure 7

The optimal policy when the number of relay nodes is different.

In the above simulation and numerical results, we define $\alpha (t)=(1-e^{-t/10000})/1000$ , which is an increasing function. The optimal policy conforms to the threshold form in this case. However, $\alpha (t)$ may conform to any form. In the rest of this section, we want to know whether the threshold policy is still better when $\alpha (t)$ has different forms. In particular, we define $\alpha (t)=50$ , $t\le 5000$  s; $PR(t)=0\hspace{0.17em}\hspace{0.17em}t>5000$  s. It is easy to see that $\alpha (t)$ is not an increasing function. Other settings are the same as those in simulation. Based on these settings, we can obtain Figure 8.

Figure 8

Performance analysis when $\alpha (t)$ conforms to different form.

Note that the optimal policy is obtained by (19), but the threshold policy conforms to Theorem 1. In fact, there is a threshold policy, which is corresponding to a specific value of h. Therefore, there are many threshold policies, which can be denoted by threshold (h). The threshold policy in Figure 8 can maximize the total income of the source under all of the threshold policies.

The result in Figure 8 shows that the threshold policy is worse than the optimal policy obtained by (19). This means that the optimal policy does not conform to the threshold form in this case. Therefore, the form of the function $\alpha (t)$ can have certain impact on the optimal policy.

6. Conclusions

To increase the efficiency, most routing algorithms in DTN need nodes to work in a cooperative way. In particular, nodes should stay in the network to forward the message further after getting message. However, due to the impact of selfishness, nodes have no incentive to stay in the network after getting message. To make these nodes be cooperative, the source has to pay certain reward (e.g., $\alpha (t)$ ) to them, and such reward may be varying with time. On the other hand, if the destination gets message timely, the source can get certain reward (e.g., $\beta (t)$ ) too. For example, the sooner the destination obtains message, the more reward the source may get. In this paper, we propose a unifying framework to evaluate the total income that the source gets under different policies. Then based on the framework, we study the optimal control problem through Pontryagin's maximum principle. In addition, we prove that the optimal policy conforms to the threshold form when $\alpha (t)$ and $\beta (t)$ satisfy certain conditions. Simulations based on both synthetic and real motion traces show the accuracy of our theoretical framework. Numerical results show that the optimal policy obtained by (19) is the best.

Note that once we know the functions $\alpha (t)$ and $\beta (t)$ , we can get the theoretical model that can evaluate the routing performance under different policies. Furthermore, we can get the optimal policy from (19). In this case, nodes just need to conform to the optimal policy. However, $\alpha (t)$ and $\beta (t)$ are system specified, so we may not know their form as the premise. In this case, we need certain learning process to get the functions of $\alpha (t)$ and $\beta (t)$ rapidly. In other words, in certain applications, we have to explore the learning process, and this will be our future work.