Eitan Altman
email: altman@sophia.inria.fr

Amar Prakash Azad
email: azad@sophia.inria.fr

Francesco De Pellegrini
email: francesco.depellegrini@create-net.org

Combined Optimal Control of Activation and Transmission in Delay Tolerant Networks

Keywords: Optimal control, fluid models, delay tolerant networks, threshold policies

Performance of a delay tolerant network has strong dependence on the nodes participating in data transportation. Such networks often face several resource constraints especially related to energy. Energy is consumed not only in data transmission but also in listening and in several signaling activities. On one hand these activities enhance the system's performance while on the other hand, they consume significant amount of energy even when they do not involve actual node transmission. Accordingly, in order to use energy efficiently, one may have to limit not only the amount of transmissions but also the amount of nodes that are active at each time. Therefore we study two coupled problems: i) the activation problem which determines when a mobile will turn on in order to receive packets, and ii) the problem of regulating the beaconing. We derive optimal energy management strategies by formulating the problem as an optimal control one, which we then explicitly solve.

We also validate our findings through extensive simulations which are based on contact traces.

I. INTRODUCTION

During the last few years, there has been a growing interest in Delay Tolerant Networks (DTNs) [START_REF] Burleigh | Delay-tolerant networking: an approach to interplanetary Internet[END_REF], [START_REF] Pelusi | Opportunistic networking: data forwarding in disconnected mobile ad hoc networks[END_REF]. In such networks, no continuous connectivity guarantee can be given [START_REF] Chaintreau | Impact of human mobility on opportunistic forwarding algorithms[END_REF], [START_REF] Spyropoulos | Efficient routing in intermittently connected mobile networks: the multi-copy case[END_REF]. Nevertheless, messages can still arrive at their destination thanks to the mobility of some subset of nodes that carry copies of the message. One central problem in DTNs is the routing of packets towards the intended destination, since mobile nodes rarely possess aprioriinformation on the encounter pattern. This is also known as the zero knowledge scenario [START_REF] Tariq | Message ferry route design for sparse ad hoc networks with mobile nodes[END_REF], [START_REF] Zhao | Controlling the mobility of multiple data transport ferries in a delay-tolerant network[END_REF]. One intuitive solution is to disseminate multiple copies of the message in the network, thereby increasing the probability that at least one of them will reach the destination node within ag i v e nt i m ew i n d o w [START_REF] Spyropoulos | Efficient routing in intermittently connected mobile networks: the multi-copy case[END_REF] .

The above scheme is referred to as epidemic-style forwarding [START_REF] Vahdat | Epidemic routing for partially connected ad hoc networks[END_REF], which is similar to the spread of infectious diseases. Each time a message-carrying node encounters an uninfected node, it infects this node by passing on the message. Finally, the destination receives the message when it meets an infected node. In this paper, we refer to a more efficient variant of the plain epidemic routing, namely the two hop routing protocol. The source transmits copies of its message to all mobiles it encounters, but the latter relay the message only if they meet the destination [START_REF] Groenevelt | The message delay inm o b i l ea d hoc networks[END_REF]. In this framework, we study the problem of optimal control of both routing and activation of relays; our objective is to maximize the probability of message delivery to the destination before a given deadline expires while satisfying specific energy constraints. Henceforth, our focus here is solely on two hop routing protocol.

In particular, being mostly composed of battery operated mobile terminals, the functioning of a mobile DTN depends on its overall energy budget. Such energy budget has to accommodate the cost of energy expended on two major operations, namely, message forwarding and node beaconing 1 . Typically, a finite energy cost accrues every time a message is transmitted and received. Furthermore, in DTNs, due to the need of continuous node discovery, relay nodes spend substantial energy for periodic beaconing.

Thus the energy budget has to be controlled in order to cope with two distinct trade-offs: iT h eh i g h e rt h en u m b e ro fm e s s a g ec o p i e s ,t h es m a l l e r the message delay. This gain comes at the price of a higher energy expenditure, because of forwarding more messages. ii Since when a relay performs beaconing it depletes its battery charge over time, it is possible to make relays active, i.e. to start their beaconing operations at different points in time, in order to better schedule the use of their battery charge. This can be done, e.g., using wake-up timers.

To overcome these difficulties, previous research in contextof sensor network have discussed the benefit of optimal activation times of deployed sensor nodes [START_REF] Kar | Dynamic node activation in networks of rechargeable sensors[END_REF]- [START_REF] Banerjee | Optimal dynamic activation policies in sensor networks[END_REF]. Given a finite DTN energy budget, a natural way to optimize the network performance is to control a number of DTN parameters; we focus here on two such parameters. The first one is the beaconing rate,w h i c hc o n t r o l st h ep o w e rb yw h i c hr e l a yn o d e so p e r a t e their transceivers; this has an effect on the so called intermeeting rate [START_REF] Chaintreau | Impact of human mobility on opportunistic forwarding algorithms[END_REF], [START_REF] Spyropoulos | Efficient routing in intermittently connected mobile networks: the multi-copy case[END_REF]. The second one is the time when relay nodes are activated. Our goal here is to obtain jointly optimal transmission and activation control policies that maximize the probability of successful delivery of the message by some time T ,g i v e n the total energy budget and a bound on the activation rate of the relay nodes. As such, this appears to be the first study that addresses a combined modeling and optimization of beaconing, activation and routing for mobile ad hoc DTNs.

We leverage fluid approximations of the system dynamics, and use tools from optimal control theory to obtain a closedform dynamic optimal policy. As we will see later, this turns out to be a two-dimensional threshold type policy. We validate the model and the results using extensive simulations.

The remainder of the paper is structured as follows: we introduce the model and problem in section II, which we solve in sections III-IV. In section V, we extend the model to allow for unbounded activation rates. In section VI, we validate the model via numerical investigation and discuss the results with real world traces. Section VII briefly surveys the related literature, followed by concluding remarks of section VIII.

Main contributions

Compared with the existing literature, this paper makes the following two main contributions:

1) Our model explicitly accounts for the maximum allowed energy expenditure, the delivery probability within a given deadline, and the activation of relays. It also accounts for the impact of beaconing on the battery depletion of activated relays, a quite important aspect for mobile DTNs where network operations heavily depend on node discovery.

2) We provide a formulation rooted in optimization, which entails joint optimization of the activation control and the transmission control in order to maximize the time-constrained delivery probability. This is a non-standard dynamic optimization problem formulated with coupled controls. Once solved, interesting properties of the optimal solution and the special role of the control on the relay activation have emerged.

II. SYSTEM MODEL

For ease of reading, we collect all the main symbols used in the paper in Table I. We consider a network of N +1 mobile nodes, where one of them, the source,h a sam e s s a g et os e n d to a destination node. We adopt the two hop routing relay policy, so that the source relays to mobiles which do not have the message but a relay transfers the message if and only if it meets the destination node. This relay strategy is monotone [START_REF] Altman | Optimal monotone forwarding policies in delay tolerant mobile ad-hoc networks[END_REF] because the number of copies of the message increases over time.

The time between contacts of any two nodes is assumed to be exponentially distributed with parameter ξ N (dependent on number of nodes). The validity of such a model has been discussed in [START_REF] Groenevelt | Message delay in MANETs[END_REF], and its accuracy has been shown for a number of mobility models (Random Walker, Random Direction, Random Waypoint). The contact rate ξ N is known to converge ξ when the number of nodes grows large, under the fluid approximations (see [START_REF] Zhang | Performance modeling of epidemic routing[END_REF]- [START_REF] Chaintreau | The age of gossip: Spatial mean-field regime[END_REF]). We explain fluid approximations in more detail later in this section. We assume that the message that is transmitted is relevant for some time T .W ed on o ta s s u m ea n yf e e d b a c kt h a ta l l o w st h es o u r c e or other mobiles to know whether the message has made it successfully to the destination within the allotted time T .

Each mobile sends periodically beacons to inform the source that they are in radio range. The source can transfer the message according to its forwarding policy. A relay node may already have a copy of the message: for such a node beaconing is not required, which may save considerable amount of energy. In what follows, we assume, that relays beacon until they get a message copy from the source. However, some nodes can switch to inactive state to save energy.

Accordingly, we define the state of a tagged node as falling into one of the three categories: i. inactive:t h et a g g e dn o d ed o e sn o tt a k ep a r ti na n y communication; ii. activated:t h et a g g e dn o d ed o e sn o th a v eam e s s a g e copy, it keeps beaconing until it receives a message copy; iii. infected:anodewithamessageisacti vebutitdoesnot send beacons. We assume that once a node becomes infected, it preserves energy for the last transmission of the message to the destination node, in case it meets destination before time T .

Notice that the average lifetime of a mobile may be considerably shorter than the bound T .T h i sl i m i t e dl i f e t i m ei sd u e to constraints on the total energy consumed: two hop routing is particularly convenient since a relay does not use much energy in transmission; however, the impact of beaconing is substantial in comparison to transmission energy. In this respect we model the lifetime of an activated mobile as an exponential random variable with average value µdU :t h i s model captures the fact that the battery empties with rate µdU if it uses power level U (t).T ot h i sr e s p e c tµ>0 is the maximum battery consumption rate.

A. The Control

There are two parameters that are controlled: a. activation rate control:i n a c t i v em o b i l e sd on o tc o ntribute to communications in the DTN and do not use energy. By activating fewer/more mobiles per unit of time, one can use resources when needed. The activation rate at time t is denoted by V (t).

b. transmission control (U (t)):t h eb e a c o n i n gt r a n s m i s s i o n power is controlled in order to mitigate the battery discharge of active relay nodes. The transmission control at time t is denoted by U (t). Let {T n } be the sequence of instants where some event occurs: either an encounter takes place between two mobiles, or an activation of a mobile. Only at these times the Markov chain representing the state ( X N , Y N ) may change, where X N is the process that represents the number of nodes (out of N total nodes) that have the message, and where Y N represents the number of active mobiles (out of N total nodes) at time t.

Next, we introduce the fluid model used in the rest of the paper. Approximation of Markov chains through differential equations is a well known technique; see for example [START_REF] Darling | Differential equation approximations for markov chains[END_REF] for as urv e y .Theus eoffl ui da pproxi ma t i onsi sas t a nda rdt ooli n modeling epidemic forwarding [START_REF] Zhang | Performance modeling of epidemic routing[END_REF]- [START_REF] Chaintreau | The age of gossip: Spatial mean-field regime[END_REF]. The approximation is known to be tight as the population of nodes grow; more precisely, if one increases the rate of events by a factor N , then the sample paths of the Markov chain ( X N , Y N ),s c a l e d by a factor of 1/N ,a r ek n o w nt oc o n v e r g ei np r o b a b i l i t yt o the solution of the limiting differential equation (under the so called regime of vanishing intensities [START_REF] Benaïm | A class of mean field interaction models for computer and communication systems[END_REF], which holds indeed in the case of uniform mobility under constant node density). This differential equation, which we introduce below, is the starting point in our analysis. 2

Fluid Approximations

Let X(t) be the fraction of the mobile nodes that have at time t ac o p yo ft h em e s s a g e .L e tY (t) denote the fraction of active mobiles at time t which do not have a copy of the message. V (t) denotes the activation rate at time t and U (t) denotes the transmission control. (X(t),Y(t)) grows at a rate given by the following pair of coupled differential equations:

Ẋ(t)=U (t)Y (t)ξ (1) Ẏ (t)=-U (t)Y (t)(ξ + µ)+V (t) (2)
The term U (t)Y (t)ξ above represents the increase in the number of mobiles with copies of the message: it is due to encounters between the source with active mobiles without messages where each of these encounters has rate ξ.C l e a r l y , at time t = 0 no active nodes exist: by continuity, Y (0) = 0. We also assume that U (t) ∈ [u, 1] for some u ≥ 0,a n dt h e activation rate V is bounded as 0 ≤ V (t) ≤ K(t), 0 ≤ t ≤ T, where K(t) is a piecewise continuous function. Without loss of generality, we further assume that T 0 V (t)dt =1 , i.e., we assume that horizon T is long enough to activate all nodes. Let the set of functions V : {V (•)} satisfying these two constraints (non-negativity and upper bounds, and unit area).

We note that from the control formulation point of view, one can find some earlier work (e.g. [START_REF] Altman | Optimal monotone forwarding policies in delay tolerant mobile ad-hoc networks[END_REF], [START_REF] Altman | Forward correction and fountain codes in delay tolerant networks[END_REF]) where multiplicative control has been used in the context of delay tolerant networks. To our knowledge, this is the first paper to include both an additive control (activation control V (.)) and a multiplicative one (U (.)).

Delivery Delay Distribution

The probability distribution of delay T d ,denotedbyD(t) := P (T d <t) is given by (see [20, Appendix A]),

D N (t)=1-(1 -z)E exp -ξ N t s=0 X N (s)ds . (3)
In the mean field limit this gives

D(t)=1-(1 -z)exp -ξ t s=0 X(s)ds , (4)
(where

D(t) = lim N →∞ D N (t), ξ = lim N →∞ ξ N (t),a n d X(t) = lim N →∞ X N (t)/N .
) Note that because of monotonicity, maximizing D(t) in ( 4) is equivalent to maximizing t s=0 X(s)ds.W en o t ea l s ot h a ts i n c et h em e a nfi e l dl i m i t is simply the expectation of the Markov chain, i.e. X(t)= E[ X(t)],t h e nw eh a v eb yJ e n s e n ' si n e q u a l i t y D N ≤ D.T h u s D(t) is not only the mean field limit of the probability of successful delivery as N grows, but it is also a bound for the successful delivery probability (for every N ).

Energy Consumption

In what follows, we will consider the case when the total energy consumed by the network is bounded. Let ǫ>0 be the energy consumed by the network for transmission and reception of a single copy of the message (rescaled by N ). Thus, the total energy consumed by the network for transmission and reception of message copies during [0,T] is ǫ(X(T ) -X(0)). Also, we need to account for the energy expenditure due to beaconing: the beaconing power used at time t by active relays is proportional to U (t)Y (t)ξ so that the energy expenditure in [0,T] due to beaconing is

µ T 0 U (s)Y (s)ds = µ ξ (X(T ) -X(0)) (5)
Hence, it follows that the total energy consumed in time T is

E(T )=(ǫ + µ ξ )(X(T ) -X(0)). 3 Remark 2.1:
Observe that the linearity of the cost of beaconing in the number of generated copies is a feature of two hop routing; it is not a general property that applies to other protocols, such as epidemic routing.

B. The Optimization Problem

Our goal is to obtain joint optimal policies for the activation V (t) and the transmission control U (t),w i t hU (t) ∈ [u, 1], and V (•) satisfying the additional upper-bound and integral constraints introduced earlier, that solve max

{V (•)∈V,U(•)} D(T ), s.t. X(T ) ≤ x, X(0) = z, (6
) 3 In the fluid limit approximation, the constraint forces the energy expended in the network to scale sub-linearly with the number ofn o d e s ,i . e . , lim N→∞

1 N E(T) < ∞.
where x and z (x>z)a r es p e c i fi e d .R e c a l lt h a tm a x i m i z i n g D(T ) is equivalent to maximizing T 0 X(t)dt.

III. OPTIMAL CONTROL

The solution to the problem will be shown to consist of policies involving two thresholds, one beyond which we stop activating mobile terminals, and the other beyond which we stop transmitting beacons. Various methodologies have been developed to establish the threshold structure of optimal transmission policies in DTNs: one based on the Pontryagin maximum principle [START_REF] Altman | Optimal monotone forwarding policies in delay tolerant mobile ad-hoc networks[END_REF], another based on some sample path comparisons [START_REF] Altman | Decentralized stochastic control of delay tolerant networks[END_REF], some on stochastic ordering, etc. These approaches, developed in the context of DTNs with one type of population, are not applicable to our problem since the model is no longer scalar. Accordingly, we develop a new approach that establishes the optimality of a threshold type policy for the activation control, following which we use Pontryagin's maximum principle [START_REF] Leitmann | Optimal Control[END_REF].

To obtain the optimal solution we first hold U (t) ∈ [u, 1] fixed, carry out optimization with respect to V (•),andthenwe substitute the optimal V (•), V * (•),i n t ot h eo b j e c t i v ef u n c t i o n and carry out a further maximization with respect to U (•).F or the first step, it is convenient to write the integral of X(•) explicitly as a function V (•),w h i c ht u r n so u tt ob el i n e a r:

T 0 X(t)dt = ξ T 0 m(t)V (t)dt , (7)
where m(•) is some appropriate function, an expression for which is provided in the next subsection.

A. Optimal Activation Control

With U (t) ∈ [u, 1] fixed, we now first justify the equivalence [START_REF] Vahdat | Epidemic routing for partially connected ad hoc networks[END_REF], with an explicit expression for m(•),a n dt h e ns h o wt h a t m(•) is non-increasing. This will allow us to conclude that the optimum choice for V (•) is of threshold form.

Lemma 3.1: Equivalence in (7) holds, with the expression for m(•) given by eq. ( 11) in the proof below. Proof. To derive the equivalent form, we solve the coupled equations ( 1)-( 2) in terms of V (•) and U (•) with zero initial conditions. Let

Φ(t, T )=exp -(ξ + µ) t T U (s)ds . (8)
Plugging ( 8) in ( 2) with zero initial conditions, we obtain

Y (t)= t 0 Φ(t, s)V (s)ds =Φ(t, 0) t 0 Φ(0,s)V (s)ds (9)
Again, using ( 9) in (1) we obtain

X(t)=ξ t 0 dσU (σ)Φ(σ, 0) σ 0 Φ(0,s)V (s)ds (10)
Letting dW := U (σ)Φ(σ, 0)dσ,a n dt h e ni n t e g r a t i n gb yp a r t s , we obtain

X(t)=ξ t 0 dW (σ) σ 0 Φ(0,s)V (s)ds = ξW(t) t 0 Φ(0,s)V (s)ds -ξ t 0 W (σ)Φ(0,σ)V (σ)dσ
Using the above equation, we can express the original objective function as follows:

T 0 X(t)dt = ξ T 0 W (t) t 0 Φ(0,t)V (t)dt - T 0 t 0 W (σ)Φ(0,σ)V (σ)dσ
Notice that we can simplify it further by integration by parts.

Defining Z through dZ = W (t)dt,w eh a v e T 0 X(t)dt = ξ Z(T ) T 0 Φ(0,t)V (t)dt - T 0 Z(t)Φ(0,t)V (t)dt -T T 0 W (t)Φ(0,t)V (t)dt + T 0 W (t)Φ(0,t)V (t)dt
which implies [START_REF] Vahdat | Epidemic routing for partially connected ad hoc networks[END_REF] where m(t) is given by

m(t)=Z(T )Φ(0,t) -Z(t)Φ(0,t) -TW(t)Φ(0,t)+tW (t)Φ(0,t) (11)
which concludes the proof. ⋄ Lemma 3.2: m(t) is non-increasing in t for all U (•) ≥ 0, and is monotonically decreasing for U (t) > 0.M o r e o v e r , the expression for m(•),a sg i v e ni n( 1 1 ) ,c a ne q u i v a l e n t l y be written as

m(t)= T t (T -s)U (s)Φ(s, 0)dsΦ(0,t) (12)
where

Φ(s, 0) = exp - s 0 U (s)ds
Proof. The expression for m(t) in [START_REF] Banerjee | Optimal dynamic activation policies in sensor networks[END_REF] can first be simplified using W (s)= s 0 dσU (σ)Φ(σ, 0) and deriving

Z(t)=tW (t) - t 0 sU (s)Φ(s, 0)ds
The expression for m(t) in ( 12) now follows from direct calculations.

Using the fact that

Φ(t, 0)Φ(0,t)=1,a n d d dt Φ(0,t)=(ξ + µ)U (t)Φ(0,t) , we obtain dm(t) dt = -(T -t)U (t) -(ξ + µ)U (t)m(t) ,
which is non-positive for all t ∈ [0,T] since m(t) is nonnegative, and is strictly negative whenever U (t) > 0. ⋄ Let us define ℓ := inf t ∈ (0,T]:

t 0 K(s)ds =1 . ( 13
)
In view of the results of Lemma 3.1 and Lemma 3.2, we have the following. Theorem 3.1: The optimal policy V * exists and is given by

V * (t)= K(t) if 0 ≤ t ≤ ℓ, 0 otherwise . ( 14
)
Note that due to threshold policy the nodes are activated till time l.B yd e fi n i t i o n( 1 3 ) ,l denotes the time till all nodes are activated (within time T )f o ro p t i m a la c t i v a t i o np o l i c y .

Proof : Any activation policy V can be viewed as a probability measure over [0,T];letuscallQ * and Q two random variables having densities V * and V respectively, where V * is defined by eq. ( 14), and where V is some other arbitrary policy. By construction,

P [Q>t] ≥ P [Q * >t].S i n c em is continuous, for t ∈ I = m([0,T]) we can define t = min(m -1 (t)) so that P [m(Q * ) >t]=P [Q * ≤ t] ≥ P [Q ≤ t]=P [m(Q) >t]
which concludes the proof since m(Q * ) ≥ m(Q). ⋄ In the rest of the development, we will assume that V (s), seen as a measure, is non-degenerate, i.e., when it is applied at time t,n o d e sa r ea c t i v a t ew i t hp o s i t i v ep r o b a b i l i t yf r o mt onwards. Formally, we will employ the following Corollary 3.1:

Let δ 0 V (s)ds > 0 for any δ>0.T h e n , Y (t) > 0, ∀t>0 (15)
Also, X(t) is a non-decreasing function for all t>0,andisa monotone increasing function when U (t) is strictly positive. Remark 3.1: (Turnpike property)W en o t ef r o mT h e o r e m 3.1 that for all T large enough (in fact for all T that satisfy T 0 K(s)ds ≥ 1), the optimal threshold ℓ is the same.

B. Optimal Transmission Control

In the previous subsection we characterized the optimal activation policy. We now proceed to derive the optimal transmission policy. From Corollary 3.1, X(t) is a monotonic increasing function. Furthermore we notice that similarly to what was shown in [START_REF] Altman | Optimal monotone forwarding policies in delay tolerant mobile ad-hoc networks[END_REF], the controlled dynamics X with U (t) can be interpreted as a slower version of the uncontrolled dynamics of X,i.e.,thedynamicsobtainedwhenU (t)=1.In this subsection, we first derive the uncontrolled dynamics for ag e n e r a la c t i v a t i o np o l i c y .T h i sw i l lt h e ne n a b l eu st od e r i ve the optimal control policy in closed form.

1) Uncontrolled Dynamics: Let X(t) denote the uncontrolled dynamics of the system: it is the fraction of infected mobiles when U (t)=1for 0 ≤ t ≤ T .

Proposition 3.1: For a given activation policy V ,t h ef r a ction of infected nodes under U (t)=1and X(0) = z is

X(t)= ξ ξ + µ t 0 (1 -e -(ξ+µ)(t-s) )V (s)ds + z (16)
Proof : From (1) and (2) we have

Ẋ(t)+ ξ ξ + µ Ẏ (t)= ξ ξ + µ V (t) ⇒ X(t)+Y (t) ξ ξ + µ = ξ ξ + µ t 0 V (s)ds + z ⇒ Y (t)=(f (t) -X(t)) ξ + µ ξ ( 17
)
where we have introduced f (t) := ξ ξ+µ t 0 V (s)ds + z,which depends only on the activation control. The uncontrolled version X(t) is obtained by substituting ( 17) in (1) for U (t)=1, which leads to: Ẋ +(ξ + µ)X =(ξ + µ)f .T h es o l u t i o ni s:

X(t)=e -(ξ+µ)t t 0 e (ξ+µ)s ξ s 0 V (r)drds + z. (18)
Further, by integration by parts we obtain [START_REF] Chaintreau | The age of gossip: Spatial mean-field regime[END_REF]. ⋄ Remark 3.2: For any given activation policy V :w es u b s t itute ( 17) into (1) to obtain a single differential equation, which is equivalent to the original system (1)-( 2), i.e., Ẋ = U (t)ξg(X, t),

where g(X, t) := (f (t) -X(t)) ξ+µ ξ . Remark 3.3: Considering ( 16), if we let W (r)= ξ ξ+µ (1e -(ξ+µ)r ) {r≥0} , the uncontrolled trajectory appears as the convolution X = W * V ,i . e . ,i tc a nb es e e na st h el i n e a r transformation of the basic two hop dynamics via the kernel V imposed by the activation policy. In fact, since we can interpret V as a measure with total mass 1,i nt h es i n g u l a rc a s e ,i . e . , when µ =0and V = δ(t),w eo b t a i nX(t)=(1-e -ξt )+z, i.e., the case of plain two hop routing, as expected.

We observe also that in case U (t)=c, t ∈ [0,T], u ≤ c ≤ 1 is a constant energy control policy, a simple time-rescaling argument offers

X(t)= ξ ξ + µ t 0 (1 -e -c(ξ+µ)(t-s) )V (s)ds + z = X(ct). (20)
In the following, using the uncontrolled dynamics of the system, we can obtain the explicit form of the optimal transmission control using the maximum principle [START_REF] Bertsekas | Dynamic Programming and Optimal Control[END_REF].

2) Optimal Control: Definition 3.1: ApolicyU restricted to take values in [u, 1] is called a threshold policy with parameter h if U (t)=1for t ≤ h a.e. and U (t)=u for t>ha.e.. Theorem 3.2: Consider the problem of maximizing D(T ) with respect to U (•) subject to the constraint X(T ) ≤ z + x, under the activation control V .

i. If X(T ) ≤ x + z,t h e nt h eo p t i m a lp o l i c yi sU (t)=1. ii. If X(uT ) >x+ z,t h e nt h e r ei sn of e a s i b l es o l u t i o n . iii. If X(T ) >x+z>X(uT ),thenthereexistsathreshold

policy. An optimal policy is necessarily a threshold one in the form

U * (t)= 1 if t ≤ h * u if t>h * (21)
Proof : Parts (i) and (ii) follow immediately from the fact that X is monotonically non-decreasing. We thus proceed with part (iii), working under the assumption X(T ) >x>X(uT ).Fix any activation policy V ;t h e nf r o mt h eR e m a r k3 . 2w en e e d to solve max

U(•)∈[u,1] T 0 X(t)dt, s.t. Ẋ(t)=U (t) ξg(X(t),t)
We use the maximum principle to solve this problem. Introduce the Hamiltonian

H(X, p, U)=X(t)+(ξ + µ)U (t)p(t)(f (t) -X(t)) ,
where p(•) is the co-state variable. Since H is linear in U ,the optimal control takes the extreme values u and 1 depending on whether H is positive or negative (it will be clear from the arguments below that the case H =0occurs on a set of Lebesgue measure zero). From [START_REF] Darling | Differential equation approximations for markov chains[END_REF], we know that f (t) -X(t) > 0 for all t.H e n c et h es i g no fH depends solely on that of p.T h u sw ea r r i v ea tt h es i m p l eo p t i m a l i t yc o n d i t i o n :

U (t)= 1, if p>0 u, if p<0 (22)
The co-state variable is generated by

ṗ(t)=- dH dX = -[1 -(ξ + µ)U (t)p(t)] = -1+(ξ + µ)U (t)p(t) (23)
Notice that we already know (based on linearity) that there must be at least one switch; in fact, if there is no switch, the only viable control would be either U (t)=u or U (t)=1for all t ∈ [0,T],w h i c hi sn o tp o s s i b l eb e c a u s ec a s e s( i )a n d( i i ) are excluded by assumption. We now prove that the optimal policy is of the threshold type by showing that there can be only one switch. There are three cases to consider based on the sign of p(0) in [START_REF] Bertsekas | Dynamic Programming and Optimal Control[END_REF].

Let us first consider the case p(0) < 0:f r o m( 2 3 )t h e n U (0) = u and further from this we can say that ṗ(0) < 0. This means that p(0 + ) <p (0) < 0.H e n c ep(t) will never change sign, which contradicts the switching condition.

Let us next consider the case p(0) > 0 and -1+ p(t) U (t)(ξ + µ) > 0.T h i si m p l i e sU (0) = 1 and ṗ(0) > 0, i.e., p(0 + ) >p(0) > 0.Hencethesignofp(t) always remains positive and optimal control remains at U =1 .T h i sa g a i n contradicts our assumptions.

Hence the only remaining possibility is that p(0) > 0 but -1+p(t) U (t)(ξ + µ) < 0.ThisimpliesU (0) = 1 but ṗ(0) < 0,i . e . ,p(0 + ) <p (0).N o t i c et h a tt h es i g no f ṗ(t) remains negative as long as p(t) is decreasing until time h when value p(h)=0is attained. Furthermore, p(h + ) < 0 and ṗ(h + ) < 0, and the same reasoning of the previous case applies.

We see that the optimal control starts at U (0) = 1 but switches to U (h)=u and never returns back. This satisfies the switching condition and guarantees that optimal control has exactly one switch. The optimal control is then given by

U (t)= u, if t>h * 1, if t ≤ h * (24)
where h * can be computed using the procedure above. ⋄

IV. JOINT OPTIMAL CONTROL

The analysis above have clearly led to the complete solution of the optimization problem [START_REF] Zhao | Controlling the mobility of multiple data transport ferries in a delay-tolerant network[END_REF], which is captured below.

Theorem 4.1: For the optimization problem (6), the solution is given by the optimal activation control V * (t) applied jointly with the corresponding threshold policy (as optimal transmission control) given in Thm. 3.2.

Proof :

The joint optimization problem, given by [START_REF] Zhao | Controlling the mobility of multiple data transport ferries in a delay-tolerant network[END_REF], can be equivalently expressed by

max {V (•)∈V,U(•)} T 0 X(t), s.t. X(T ) ≤ x, X(0) = z, ( 25
)
where x and z (x>z)a r es p e c i fi e d .

It is direct from Lemma 3.1, the joint optimal control is equivalent to step wise optimal control of V (.) for any U (.) and the optimal control of U (.).T h e r e f o r e ,t h ep r o o fi sd i r e c t using Thm. 3.1 and Thm. 3.2. ⋄

A. Activation and Transmission Thresholds

We have seen that the optimal policies are characterized by two scalar quantities, ℓ and h * ,t a k i n gv a l u e si n(0,T).O n e interesting question now is whether one should wait for all the nodes to be activated before switching off the transmission control or not, i.e., whether it should be h * ≤ ℓ or h * >ℓ . If h * ≤ ℓ,i ti st h e np o s s i b l et oa c t i v a t eas m a l l e rn u m b e ro f relays with consequent energy savings; thus it is of interestt o know the relative order of the thresholds h * and ℓ.

For ease of following the development below, let us introduce X as the optimal dynamics for t ≥ h * :f r o m( 1 ) -( 2) and fixing the control

U (t)=u for t ∈ [h * ,T],w i t hi n i t i a l condition X(0) = X(h),w eh a v e Ẋ(t)+u(ξ + µ)X(t)=u(ξ + µ)f
Hence, the optimal dynamics for t ≥ h * is of the form

X(t)=e -u(ξ+µ)(t-h) t 0 e u(ξ+µ)s (ξ + µ)uf (s + h)ds +X(h)e -(ξ+µ)(t-h) ,t > h .
Notice that X(T )=X(T )=x.W i t h o u tl o s so fg e n e r a l i t y we assume z =0in the rest of the paper unless specified, for the sake of simplicity. Theorem 4.2: If T>max{h * ,ℓ},t h e nt h ef o l l o w i n gr e l ation holds for the bound x and the threshold h * :

h * >ℓ, if x>X(ℓ)+∆X(ℓ, T ), h * ≤ ℓ, otherwise , (26)
where

X(ℓ)= ξ ξ + µ ℓ 0 (1 -e -(ξ+µ)(ℓ-s) )V (s)ds, ∆X(ℓ, T )= ξ ξ + µ -X(ℓ) 1 -e -u(ξ+µ)(T -ℓ) .
X(ℓ) denotes the uncontrolled growth of X in t =(0,ℓ] and ∆X(ℓ, T ) refers to the increment in X in (ℓ, T ] under the controlled dynamics (with U = u ).

Proof : We first consider the case when h * >ℓand show that for large values of the threshold h * , X(T ) is also large. Further we consider the case when h * ≤ ℓ and show that still the behavior holds true. Consequently we can conclude that the result holds. When h * >ℓ, X(T )=x can be expressed as a summation of three terms as follows:

x =∆X(0,ℓ)+∆X(ℓ, h * )+∆X(h * ,T) (27)
where ∆X(t 1 ,t 2 )=X(t 2 ) -X(t 1 ).T h ef o l l o w i n gd y n a m i c s will be valid over the corresponding intervals:

Ẋ(t)+(ξ + µ)X(t)=(ξ + µ)f (t), 0 <t≤ ℓ (28) Ẋ(t)+(ξ + µ)X(t)=(ξ + µ)f (ℓ),ℓ < t ≤ h * (29) Ẋ(t)+u(ξ + µ)X(t)=u(ξ + µ)f (ℓ),h * <t≤ T(30)
The first term ∆X(0,ℓ) is given by ( 16):

∆X(0,ℓ)= ξ ξ + µ ℓ 0 (1 -e -(ξ+µ)(ℓ-s) )V (s)ds
Similarly ∆X(ℓ, h * ) is obtained from [START_REF]Optimal monotone forwarding policies in delay tolerant mobile ad-hoc networks[END_REF] with initial condition X(ℓ),andsubsequently∆X(h * ,T) is obtained from [START_REF] Pellegrini | Optimal monotone forwarding policies in delay tolerant mobile ad hoc networks with multiple classes of nodes[END_REF] with initial condition X(h * ).F i n a l l yw ec a ne x p r e s sx as,

x = ξ (ξ + µ) + X(ℓ) - ξ (ξ + µ) e -(ξ+µ)u(T -ℓ)+∆(1-u)
where ∆=h * -ℓ.Fromtheaboveequationitcanbeseenthat X(T ) increases with ∆.H e n c et h i sc o n c l u d e st h efi r s tp a r t . Following a similar approach, we can also show that X(T ) increases with ∆ when h * <ℓ .B ys u b s t i t u t i n gh * = ℓ,w e obtain the closed-form expression for x = X(T ) as

x = X(T )=X(ℓ)+ ξ (ξ + µ) (1 -e -u(ξ+µ)(T -ℓ) )
⋄Moreover, when both threshold times coincide, i.e. h * = ℓ, the bound x can be expressed as

x = X(T )=X(ℓ)+ ξ ξ + µ (1 -e -u(ξ+µ)(T -ℓ) ).

B. Uniform Activation

Let the node activation be uniformly spread over time, i.e., K(s)=K 0 ,w h e r e ℓ 0 K(t)dt = ℓ 0 K 0 dt =1.L e tu =0for the sake of simplicity. Since we have X(h, T )=0,i tf o l l o w s directly from Theorem 4.2 that x>X(ℓ) if h * >ℓ.

Proposition 4.1: The optimal threshold for constant activation is given by

h * = min( t, T ), if x>X(ℓ)( h * >ℓ) min( t, T ), if x ≤ X(ℓ)( h * ≤ ℓ) (31)
where

t = 1 ξ + µ log ξ(e (ξ+µ)ℓ -1) (ξ + µ) 2 ℓ(x -ξ ξ+µ ) , t = L(-e -(xℓ(ξ+µ) 2 +ξ)/ξ )ξ + xℓ(ξ + µ) 2 + ξ ξ(ξ + µ) .
Here L(•) denotes the Lambert function, 4 which is real-valued on the interval [-exp(-1), 0] and always below -1.

Proof : Let us first consider when h * >l ,t h et o t a ln u m b e r of infected nodes at time T is given as

x = X(l)+∆X(h, l)+∆X(T,h)
Last term vanishes due to the fact that u =0.T he re foreus i ng (29), we can write

x = X(h)= ξ ξ + µ l 0 (1 -e -(ξ+µ)(h-s) )K(s)ds h = 1 ξ + µ log ξ(e (ξ+µ)ℓ -1) (ξ + µ) 2 ℓ(x -ξ ξ+µ )
.

This concludes the first case. For the second case when h * <l, we can express x = X(h)+∆X(l, h)+∆X(T,l)

Since u =0 ,o n l yt h efi r s tt e r mr e m a i n s .T h e r e f o r e ,w ec a n express

x = X(h)= ξ ξ + µ h 0 (1 -e -(ξ+µ)(h-s) )K(s)ds x = ξ (ξ + µ) 2 (e -(ξ+µ)h +(ξ + µ)h -1) h = L(-e -(xℓ(ξ+µ) 2 +ξ)/ξ )ξ + xℓ(ξ + µ) 2 + ξ ξ(ξ + µ) .
This concludes the proof for the second case, which together with the first case concludes the proof. ⋄ Notice from above that h * is approximately linear in ℓ.

Uniform activation is also of interest because of the following reason. In a scenario such as energy harvesting, it is expected to have cyclic kind of activation, e.g. more nodes are activated during the day exploiting solar energy than are at night. In Proposition 5.1 in the next section, we show that the threshold h * depends on E[V ].T hi sa l l o w sust oa pproxi ma t e the uniform activation with appropriate parameters which may require simpler calculation.

C. Impact of time horizon T

In the earlier sections we showed that the optimal transmission control policy U * is a threshold policy for finite (fixed) time horizon. We now extend our earlier results to the case when the time horizon T is unbounded, and analyze asymptotically the impact on optimal policies.

Optimal activation policy V * derived in earlier section clearly indicates that early activation is optimal (satisfying the rate constraint K(t)). We also saw that V * is the same for T above some value ℓ. ii. For u =0 ,t h eo p t i m a lt r a n s m i s s i o np o l i c yw h e nT → ∞ is given by,

A * = U (t)=1 if t ≤ T m U (t)=0 if t>T m . (32)
Proof : (i) is direct. (ii) follows directly from the fact that the optimal activation policy V does not depend on T . ⋄ V

. E XTENSION TO UNBOUNDED ACTIVATION

In some cases, the activation rate may not be bounded: this is the case of timer-based activation of batches of relays. Thus, in this section we extend our model to the case of unbounded activation, i.e., we assume that, for some τ>0,

t t-τ V (s)ds ≤ K u (t) ≤ 1
where K u (t) ≥ 0 is a piecewise continuous function. Again, the activation rate is subject to the normalization condition T 0 V (s)ds =1 ;w ei m p o s eK u (0) = 0 without loss of generality. In this case, the optimal activation threshold is

ℓ := τ • max{k ∈ N| K u (kτ) < 1, K u ((k +1)τ ) ≥ 1}
The main difference from the results derived in Section III-A is related to the explicit form of the optimal activation control. Also, the related uncontrolled dynamics under the optimal activation control can be expressed in a very simple form.

The following theorem captures these. Theorem 5.1: Let the activation rate be bounded in the integral form. Let t k = kτ, k =0,...,L-1 such that t L-1 <ℓ, let t L = ℓ and define

a k = K u (t k ), k =0 ,...,L -1,a n d a L =1-h<L a h ; a k is zero otherwise. Then i.
The optimal activation control is

V * (t)= ∞ k=0 a k δ(t -t k ),
where δ is the Dirac distribution ii. Under the optimal activation control V * ,t h eo p t i m a l uncontrolled dynamics are

X(t)= ∞ k=0 a k W (t -t k )
where W (r)=(1-e -(ξ+µ)r ) {r≥0} .

Proof : i. Since the proof of Theorem. 3.1 remains intact, we can derive the first statement from a direct calculation. In particular, considering any other activation V ,weobservethat [START_REF] Vahdat | Epidemic routing for partially connected ad hoc networks[END_REF] in this case becomes

T 0 V * (t)m(t)dt = T 0 L k=0 a k δ(t -t k )m(t)dt = L k=0 a k m(t k )= L k=0 K(t k )m(t k ) ≥ L k=0 t k+1 t k V (s)m(s)ds = T 0 V (s)m(s)ds (33)
ii. As from ( 16), the uncontrolled trajectory is given by the convolution X -z = W * V ,s ot h a t

X(t)=W * L k=0 a k δ(t -t k )= L k=0 a k W (t -t k )
which concludes the proof ⋄ It is immediate to observe that Corollary 3.1 applies to the case of unbounded activation rate also, from which it follows that the proof of Theorem 3.2 can be applied tout court and as a consequence Corollary 4.1 as well.

Finally, the previous result shows that, apart from the effect of initial condition z,t heunc ont rol l e ddyna mi c sc a nbe obtained as a linear combination of the sequence of delayed plain dynamics that would be obtained starting the system at the activation epochs t k ,u n d e ra ne m p t ys y s t e m( i . e . ,u n d e r zero initial conditions). The weights, in turn, are given by the fraction of nodes activated at times t k .

A. Role of V * in the case h * >ℓ

Using the results for unbounded activation, we can provide more insight on the role of V * on the optimal success probability. As we will see in the following section, this result is very well corroborated by numerical studies. In particular, consider an optimal (bounded) activation policy V * and the related optimal transmission control. Let us consider u =0 and z =0for the sake of simplicity. Assume h * >ℓ,a n dl e t W = W {0≤u≤h * -ℓ} ,a n dn o t e where we used the fact that W (t)=0for t<0, V * has a finite support, and the integral of the convolution is the product of the integrals. Now, let τ>0 and consider the obtained unbounded activation as a bound Proposition 5.1: Let the optimal activation policy V * be such that ℓ>h * ;t h e n

T 0 X(u)du = h * -ℓ 0 W (u)du h * 0 V * du = h * 0 W (u) (34)
K u (t)= t 0 V * (u)du;w e obtain h * = 1 ξ + µ log ξ ξ + µ Ẽ ξ ξ+µ -x where Ẽ = L k=1 a k (τ )e -kτ .T a k i n gt h el i m i tf o rτ → 0,w e observe that lim τ →0 Ẽ = ℓ 0 e -(ξ+µ)u V * (u)du = G X V * (ξ + µ) where Q V * is a random variable having density V * ,a n d G Q V * (ξ + µ)
h * = 1 ξ + µ log ξ ξ + µ G Q V * (ξ + µ) ξ ξ+µ -x .
Notice that, as a consequence of the above, using the standard moment series expansion for the moment generating function, we obtain

G Q V * (ξ+µ)=1-(ξ+µ) Q V * + 1 4 (ξ+µ) 2 Q 2 V * + ...,whichleadstoG Q V * (ξ+µ)=1-(ξ+µ) Q V * +o(ℓ 2 (ξ+ µ) 2 ).

T h u s ,u n d e rt h ea s s u m p t i o n so ft h ep r o p o s i t i o na b o v e ,

and when ℓ ≪ 1/(ξ +µ),weexpectthetransmissionthreshold to be linear in

Q V * .
Comparing the expression in [START_REF] Krifa | Optimal buffer management policies for delay tolerant networks[END_REF] we obtain a closed form relation that ties the system parameters and the activation policy; in particular we realize that in the regime ℓ ≪ 1/(ξ + µ), D(T ),w i l lb ed e t e r m i n e dm a i n l yb yt h ev a l u e Q V * . Ultimately, this means that the system "loses memory" of the shape of the optimal activation distribution as soon as the activation of nodes becomes smaller than the typical time scale of the system, i.e., 1/(ξ + µ).

VI. NUMERICAL VALIDATION

Here we provide a numerical validation of the model. Our experiments are trace based: message delivery is simulated by a Matlab R script receiving as input pre-recorded contact traces; in our simulations, we assume time is counted from the time when the source meets the first node, so that z =1+P a , where P a is the probability that the first node met is active. Also, the lifetime of active node is an exponential random variable with parameter µ.

We considered a Random Waypoint (RWP) mobility model [START_REF] Camp | A survey of mobility models for ad hoc network research[END_REF]. We registered contact traces using Omnet++ in a scenario where N nodes move on a squared playground of side 5 Km. The communication range is R =1 5m, the mobile speed is v =4 .2 m/s and the system starts in steady-state conditions in order to avoid transient effects [START_REF] Boudec | Perfect simulation andstationarityof ac l a s so fm o b i l i t ym o d e l s , "i nProc. of Infocom.M i a m i[END_REF]. The time limit is set to τ =20000s. Most graphs refer to the case with N =200.

With the first set of measurements, we verified the fit of the activation model for the uncontrolled dynamics, i.e., when x + z =1,a ndus i ngauni forma c t i v a t i onpol i c y .W ea s s ume d that µ =0and u =0.W es e l e c t e da tr a n d o mp a i r so fs o u r c e and destination nodes and traced the dynamics of the infected nodes, see Fig. 1a.I); as seen there and in the following figures the fit with the model is rather tight.

The different curves seen in Fig. 1a.I) are obtained varying the constraint on the uniform activation policy; in particular the activation threshold ℓ =5000, 10000, 15000.W eincluded also the unbounded activation case when all relays can be activated at time t =0 ;n a m e l yf o rℓ =0and V = δ.A s indicated there, in the case of constant activation a change of concavity must occur in the dynamics (notice that X(∞)=1). Indeed, for example in [START_REF] Altman | Optimal monotone forwarding policies in delay tolerant mobile ad-hoc networks[END_REF], plain two hop routing has concave state dynamics. However, the change of concavity is an effect of the activation term, since (1)-( 2) gives Ẍ = ξ(ξ +µ)Y -K 0 which shows a sign switch when ℓ<T.

Also, we depicted in Fig. 1b) the values of the optimal threshold for the transmission control in the case of uniform activation policy, at the increase of the activation threshold ℓ.W ec o n s i d e r e dt w oe n e r g yb o u n d sx + z =0 .1 and x + z =0 .05.A se x p e c t e d ,as l o w e ra c t i v a t i o nf o r c e st h e optimal threshold to increase: as it appears in the figure, for the chosen activation constraint, the threshold increase is almost linear with ℓ,s h o w i n gc o n g r u e n c ew i t h( 3 1 ) .N o t i c e that for the parameters chosen, we have ℓ<h * .T h el i n e a r increase the observation made in Prop. 5.1, since in both cases

Q V * = ℓ/2 is linear in ℓ.
We repeated in Fig. 1a.II) the measurements of the dynamics of infected nodes and collected the CDF of the delay in the case of the optimal control in Fig. 1c). We can clearly observe the effect of the threshold policy on the dynamics of the infected nodes, since the increase of the number of infected stops at the threshold (u =0 ). Conversely, we can observe that the delay CDF has a slightly lower curve compared to the uncontrolled case (reported with a thin solid line).

So far, we did not consider the effect of µ on the success probability D(T ).F i g .2d e p i c t st h es u c c e s sp r o b a b i l i t yf o r increasing values of µ.A se x p e c t e d ,t h eh i g h e rt h er e l a t i v e magnitude of µ with respect to ξ,t h el o w e ri st h es u c c e s s probability. However, the effect of energy exhaustion due to beaconing takes over for larger values of µ and causes a much faster decay in case of looser constraints on energy (x + z = 0.1)t h a ni nt h ec a s eo ft i g h t e ro n e s( x + z =0.05).

Finally, we compared the effect of the activation bound on the success probability D(T ).I np a r t i c u l a r ,w ec o n s i d - ered three alternative bounds: uniform, squared sine and exponential. In the case of a squared sine bound, we let

K(t)= 2 ℓ sin 2 ( 2 π t ℓ ) {0≤t≤ℓ}
.T h ec o m p a r i s o nw i t ht h eu n iform activation shows that they result in a similar performance: as observed in Fig. 3a) the optimal transmission control and as a consequence the success probability (Fig. 3b) ) as a function of ℓ are similar. This behavior is due to the fact that in both cases h * ≥ ℓ and the two activation measures have the same expected value. This confirms what was predicted in Prop. 5.1: in practice the system loses trace of the shape of the distribution as soon h * ≥ ℓ.W ealsodepictedthebeha vior in the case of a bound given by a truncated exponential where α = -70ξ:a ss e e ni nF i g .3 a )a n dF i g .3 b ) ,t h eh i g h e r activation rate permits a larger success probability. This effect becomes dominant at larger values of ℓ and this results in the slower increase of the transmission threshold which saturates to a reference value; notice that this is a consequence of the exponential saturation of Q V * with ℓ,a so b s e r v e da l r e a d y from Prop. 5.1. We repeated the measurements on the success probability D(T ) for increasing numbers of nodes, as reported in Fig. 3c). We can see the match of the uniform activation and the squared sine one. Also, we reported the behavior under truncated exponential activation in the case of |α| =70ξ;t h e success probability in all these examples is seen to depend mostly on the expected value of V * ,a so b s e r v e de a r l i e r . Remark 6.1: As observed from the Fig. 3c), system performance is predicted by a single target parameter, i.e., the expected value of the activation distribution. Our model for activation expresses in closed form performance of a DTN under the assumption that the system can be described by a single intermeeting intensity which does not change over time. In real world contact traces, however, stationarity and uniformity assumptions on intermeeting intensities may not hold. Even though this realistic scenario is out of the scope of our model -and no claim of optimality can be made there with respect to the results derived before -we would like to draw here some conclusion on the applicability of our joint activation and control in the case where nonuniform and non-stationary encounter patterns are present.I n order to do so, we considered two real world traces which resulted in two very different contexts. The first trace is part of the DieselNet trace collection, which was generated by the DieselNet network and is available online [START_REF]The disruption tolerant networking project at UMass[END_REF], [START_REF] Burgess | Maxprop: Routing for vehicle-based disruption-tolerant networking[END_REF]. Those traces resulted from the contacts experienced by devices where the DTN network is made of IEEE802.11 terminals mounted on buses. The second real world trace is the CN dataset; it was generated by a DTN composed of 21 devices carried by employees within the Create-Net premises. Each of them volunteered to carry a mobile running a Java application relying on Bluetooth connectivity and employees were located on different floors of the same building during a 4-week period. The application periodically triggered (every 60 seconds) a Bluetooth node discovery; detected nodes were recorded using the Bluetooth address, together with the current timestamp on the device. Thus, the two data sets were generated in two different frameworks with respect to the mobility of the devices: the CN trace relates to human indoor mobility and the UMASS trace relates to the mobility pattern of a fleet of buses. Fig 4a ) andb) show the results of experiments performed with these data sets. We preliminarily calculated the average intermeeting rate resulting from the experimental traces. Then, we performed the simulations calculating the optimal threshold under a uniform activation profile. We notice from those figures that the performance of the solution predicted using the Poisson uniform approximation in real world traces proves conservative from the standpoint of the number of infected nodes, i.e., it tends to infect more nodes than predicted by the model, thus violating the constraint on energy. Ac l o s e rl o o ka tt h et r a c e sr e v e a l e dt h a ti nb o t hr e a l world traces there exists a group of "fast spreaders": this group is composed of potential relays which do meet the source with higher rate compared to the average. Because of this, the fraction of nodes that belong to that group will be infected at a much faster rate. However, the optimal control is determined based on the average intermeeting rate of a potential relay: the control is thus driven to act pessimistically and the overall fraction of infected nodes turns out to be larger than the fraction issued as a constraint. In particular, this effect becomes visible since the fraction of fast spreaders is larger than the constraint itself.

In particular, those results show that the presence of a wide range in the values taken by the intermeeting intensities is one critical feature that is not described in the current version of our model and should be captured by a framework designed to fit those cases as well. In previous works [START_REF] Altman | Optimal control in two-hop relay routing[END_REF], [START_REF]Optimal monotone forwarding policies in delay tolerant mobile ad-hoc networks[END_REF] it was showed how to extend the control of DTNs [START_REF] Pellegrini | Optimal monotone forwarding policies in delay tolerant mobile ad hoc networks with multiple classes of nodes[END_REF], [START_REF] Chahin | Blind onlineo p t i m a l forwarding in heterogeneous delay tolerant networks[END_REF] to the case when multiple intermeeting intensities are present. However, no activation control was applied in those models, and along those lines, class-dependent activation is a promising direction to be tackled in future work.

B. Further application of the model

The activation policies that we consider in this paper are of the monotone type: relays are activated at some point in time until either batteries are drained or deadline is reached. However the proposed model can be used to explore the combined usage of activation with different techniques. For DTNs, in particular, duty cycling techniques [START_REF] Jun | Power management in delay tolerant networks: a framework and knowledge-based mechanisms[END_REF] or messagelimiting forwarding policies [START_REF] Altman | Optimal monotone forwarding policies in delay tolerant mobile ad-hoc networks[END_REF] are proposed in literature in order to reduce power drainage at relays.

Duty cycling: Our model can incorporate duty cycling energy saving using a thinning argument. When duty cycles alternate between sleep and active mode, the intermeeting intensity of relays with the source node and the destination is rescaled by the fraction q of time a mobile is in awake mode, i.e., replacing ξ with qξ and µ with qµ.

Message limiting: Many works in the literature limit the released copies to reduce the energy expenditure; our model includes such a case by letting all nodes be activated at the beginning, i.e., K(t)=Nδ(t),t h eu n d e ru n b o u n d e d activation, and optimizing against a target value x only.

Uniform activation: As u b -o p t i m a lp o l i c yw o u l dc o n s i d e r an optimal forwarding policy to be given, e.g., a uniform policy V u (t) independent of the actual activation constraint K;t hi sgreat l ys i mpl i fi est hei mpl ement at i onoft heact i v at i on mechanism on board of relays since a random timer would do. Such suboptimal policies can be incorporated in our model by interpreting activation control V as a probability density function of a randomly picked mobile being activated in a given interval; it amounts to replacing V * with V u V * and then calculating the optimal forwarding policy accordingly.

For the sake of completeness, we included a sample numerical analysis in Table II, where the actual function K(t) is a squared sine; using our model it is possible to study the combined effect of activation, message-limiting policies and also combine it with duty cycle effects. Observe the thinning of intermeeting process resulting in performance decay.

Finally, we evaluated the performance attained using blind uniform activation, which behaves irrespective of the actual activation constraint; as seen in Table II on the actual activation constraint produces a significant drop of performance, as expected from such a sub-optimal policy.

VII. RELATED LITERATURE

Control of forwarding schemes has been addressed in the DTNs literature before. For example, [START_REF] Fawal | Performance analysis of self limiting epidemic forwarding[END_REF] describes the relative performance of different self-limiting strategies. In [START_REF] Zhao | Controlling the mobility of multiple data transport ferries in a delay-tolerant network[END_REF]and its follow-up [START_REF] Tariq | Message ferry route design for sparse ad hoc networks with mobile nodes[END_REF], the authors optimize network performance by designing message relays. Some papers related to our work here are [START_REF] Altman | Optimal monotone forwarding policies in delay tolerant mobile ad-hoc networks[END_REF], [START_REF] Krifa | Optimal buffer management policies for delay tolerant networks[END_REF], [START_REF] Neglia | Optimal delay-power tradeoff ins p a r s ed e l a y tolerant networks: a preliminary study[END_REF]. In [START_REF] Krifa | Optimal buffer management policies for delay tolerant networks[END_REF], the authors consider buffer constraints and derive buffer scheduling policies in order to minimize the delivery time. In [START_REF] Altman | Optimal monotone forwarding policies in delay tolerant mobile ad-hoc networks[END_REF], we have provided a general framework for the optimal control of a broad class of monotone relay strategies, rooted in the original result obtained for epidemic routing in [START_REF] Zhang | Performance modeling of epidemic routing[END_REF]. The more recent paper [START_REF] Altman | Decentralized stochastic control of delay tolerant networks[END_REF] employs stochastic approximation to avoid the explicit estimation of network parameters. The performance of the two hop forwarding protocol along with the effect of the timers have been evaluated in [START_REF] Hanbali | Performance of ad hoc networks with two-hop relay routing and limited packet lifetime[END_REF]; the framework proposed there allows for performance optimization by choosing the average timer duration.

Optimal activation of nodes in redundantly deployed sensor networks has been studied before in [START_REF] Kar | Dynamic node activation in networks of rechargeable sensors[END_REF]- [START_REF] Banerjee | Optimal dynamic activation policies in sensor networks[END_REF]. A thresholdbased activation policy was shown to perform close to the optimal policy for dynamic node activation in [START_REF] Kar | Dynamic node activation in networks of rechargeable sensors[END_REF]. In [START_REF] Kansal | Performancea w a r et a s k i n g for environmentally powered sensor networks[END_REF], spatial temporal correlation has been exploited to improve usable lifetime in environmentally powered sensor networks. Scheduling/controlling the activity nodes to exploit energy harvesting features has been studied in [START_REF] Banerjee | Optimal dynamic activation policies in sensor networks[END_REF].

Energy efficiency in DTNs has been studied in [START_REF] Choi | Adaptive asynchronous clock based power saving protocols for delay tolerant networks[END_REF], [START_REF] Jun | Power management in delay tolerant networks: a framework and knowledge-based mechanisms[END_REF], [START_REF] Kim | Energy optimal epidemic routing for delay tolerant networks[END_REF] and in [START_REF] Li | Energy-efficient optimal opportunistic forwarding for delay-tolerant networks[END_REF]. In [START_REF] Kim | Energy optimal epidemic routing for delay tolerant networks[END_REF], authors study binary spreading forwarding policy, where each node forwards the packet to other nodes (when nodes meet) till n nodes are infected using a token mechanism. Authors study the energy and delay tradeoff and determine the optimal number of nodes to be infected. Asynchronous sleep scheduling algorithms are proposed in [START_REF] Jun | Power management in delay tolerant networks: a framework and knowledge-based mechanisms[END_REF] to reduce energy consumption during the idle listening mode. A model related to ours is presented in a parallel work in [START_REF] Li | Energy-efficient optimal opportunistic forwarding for delay-tolerant networks[END_REF], which analyzes the tradeoff between transmission energy consumption and delivery delay. In line with findings of [START_REF] Altman | Optimal monotone forwarding policies in delay tolerant mobile ad-hoc networks[END_REF] and [START_REF] Zhang | Performance modeling of epidemic routing[END_REF], authors show that the forwarding policies are threshold optimal. The optimality is shown via simulation based performance comparison for the two hop routing and probabilistic epidemic forwarding.

Compared to existing literature, in this paper we have proposed an entirely different and new framework that has not been introduced before: our aim was in fact to include not only the optimality of resources utilization in terms of released copies, but also in terms of the energy spent by relays in order to signal its presence to the destination, which is a fundamental functionality required in the context of mobile DTNs.

Finally, we identified relations among a few physical parameters of the optimal joint control, the deadline T ,theactivation rate bound, and the beaconing rate. A valuable insight that we obtained is how under optimal joint forwarding and activation, the system "loses memory" about the shape of the activation distribution, and only the mean activation instant counts.

VIII. CONCLUDING REMARKS

In this paper, we have considered the joint optimization problem underlying activation of mobiles and transmission control in the context of DTNs. Multi-dimensional ordinary differential equations have been used to describe (using the fluid limit) the associated system dynamics. Since the previously used approaches were not applicable to establish the structure of optimal activation policies, we devised a new method that is based on identifying the exact weight of the activation control at each time instant. We further validated our theoretical results through simulations for various activation schemes or constraints on activation.

Starting from the proposed framework, there are several promising directions that are left open as possible extensions of the model. For instance, we did not account for simultaneous multiple sources-destination pairs and for the presenceo f heterogeneity in the contact pattern of mobile nodes, due to either devices heterogeneity or the mobility pattern. One may also envision the possibility to activate mobiles dependingo n the class they belong to, e.g., battery lifetime or transmission power. We also did not account for the presence of exogenous traffic that may interfere with DTNs.

Finally, the control problems that we considered were formulated as maximization of the delivery delay distribution D(T ) subject to a hard constraint on the energy expended, i.e., number of copies released. We note that we could have formulated the problem with soft constraints, instead of hard constraints, using a weighted sum of throughput and energy cost. We argue that the optimal joint policy for this softconstrained problem is of a double threshold type (i.e., both u and v have threshold structures). Indeed, the new problem can be viewed as the maximization of the Lagrangian that corresponds to the constrained problem. We can thus associate with the original problem a "relaxed" problem. For afi x e du,w eh a v ea l r e a d ys e e nt h a tt h ec o s ti sl i n e a ri n v(•).ThereforetheKarush-Kuhn-T ucker(KKT)conditionsare necessary and sufficient optimality conditions, which implies that a threshold-type v is also optimal for the unconstrained problem. To show that a double threshold policy is optimal for the relaxed problem, it will be necessary to verify that there is a unique optimal policy for the constrained problem, which we leave as future research, which we intend to undertake.

4 . 2 :

 42 W en e x ts t u d yt h ei m p a c to fT on U * .T h i si ss u m m a r i z e di nt h ep r o p o s i t i o nb e l o w .D e fi n e T m := sup{t : X(t) ≤ x} and T m := sup{t : X(t) ≤ x}. Proposition Consider maximization of D(T ) subject to the constraint X(T ) ≤ z + x,u n d e rt h eo p t i m a la c t i v a t i o n control V * and transmission control U (t) ∈ [u, 1].

  i. For u>0,t h e r ei sn of e a s i b l ep o l i c yf o ra n yT>T m .

Fig. 1 :

 1 Fig.1: a) Dynamics of the number of infected nodes under uniform activation, when ℓ =0 , 5000, 10000, 15000;u p p e rp a r t (a.I) depicts uncontrolled dynamics, the lower one (a.II) optimal dynamics for x =0 .1 b) Optimal Threshold under constant activation for two different values of x.c)CDFofthedelayforoptimalcontrol:thethinsolidlinesrepresent the value attained by the uncontrolled dynamics. The case ℓ =0corresponds to plain Two hop routing.

Fig. 2 :

 2 Fig. 2: Success probability for increasing values of µ/ξ,under uniform activation with ℓ =1 0 0 0 0 sa n dx + z =0 .05, 0.1, respectively.

  is the moment generating function calculated in ξ + µ.T h u sw eo b t a i nt h ef o l l o w i n gr e s u l tt h a th o l d sf o r the bounded activation case:

Fig. 3 :

 3 Fig. 3: a) Optimal threshold as a function of ℓ b) Corresponding success probability D(T ) c) Success probability for increasing number of nodes. Different lines refer to the case of uniform (solid), squared sine and truncated exponential activationbounds.

Fig. 4 :

 4 Fig. 4: Simulation results in the case of real world traces: a) CN trace b) DieselNet trace Our model for activation expresses in closed form performance of a DTN under the assumption that the system can

TABLE I :

 I Main notation used throughout the paper

  , lack of information

	Policy	Ps
	Optimal	0.97
	Optimal: duty cycle q =0.2, 0.4, 0.6, 0.8	0.32, 0.56, 0.79, 0.90
	Uniform Activation	0.86

TABLE II :

 II Application of the model to duty cycling and suboptimal policies; squared sine activation constraint, RWP mobility, 200 nodes, ξ =6.8211 • 10 -6 , µ = ξ/10, T =25000s, ℓ =8000s, x =0.1.

Ap e r i o d i cs i g n a l i n gf o rn o d ed i s c o v e r yp r i o rt om e s s a g er e c eption.

This mean field limit is not only an approximation but turns outt ob et h e exact expected value of the Markov chain. This property is duet ot h ef a c t that the forwarding policy is the two-hop routing, so that thet o t a li n t e n s i t y of the contact process of the source with relays is linear in N ,a n do n ec a n then use the argument in[START_REF] Benaïm | A class of mean field interaction models for computer and communication systems[END_REF].

The Lambert function,s a t i s fi e sL(x)exp(L(x)) = x.A st h ee q u a t i o n y exp(y)=x has an infinite number of solutions y for each (non-zero) value of x,t h ef u n c t i o nL(x) has an infinite number of branches.

IX. ACKNOWLEDGMENTS

This work was partially supported by the European Commission within the framework of the BIONETS project IST-FET-SAC-FP6-027748, see www.bionets.eu.T h ec o l l a borative research of the first three authors was supported by an INRIA-UIUC grant for cooperation. The work of first and second authors were partly supported by CEFIPRA (contract number No.4000-IT-1), as well as by the GANESH associate team project of INRIA. The third author's research was also supported by a grant from the Department of Energy (DOE).