Tatiana Seregina

Olivier Brun

Rachid Elazouzi

Balakrishna Prabhu

On the Design of a Reward-Based Incentive Mechanism for Delay Tolerant Networks *

A central problem in Delay Tolerant Networks (DTNs) is to persuade mobile nodes to participate in relaying messages. Indeed, the delivery of a message incurs a certain number of costs for a relay. We consider a twohop DTN in which a source node, wanting to get its message across to the destination as fast as possible, promises each relay it meets a reward. This reward is the minimum amount that offsets the expected delivery cost, as estimated by the relay from the information given by the source (number of existing copies of the message, age of these copies). A reward is given only to the relay that is the first one to deliver the message to the destination. We show that under fairly weak assumptions the expected reward the source pays remains the same irrespective of the information it conveys, provided that the type of information does not vary dynamically over time. On the other hand, the source can gain by adapting the information it conveys to a meeting relay. For the particular cases of two relays or exponentially distributed inter-contact times, we give some structural results of the optimal adaptive policy.

Index termsdelay tolerant networks, reward incentive mechanism, adaptive strategy

Introduction

Delay-tolerant networking (DTN) is an approach to computer network architecture that seeks to address the technical issues in networks that may lack continuous network connectivity [START_REF] Fall | A delay-tolerant network architecture for challenged internets[END_REF]. A typical example is that of a mobile network with a low node density. Such a network is only sporadically connected, meaning that it often happens that there is no end-to-end path between a source node and a destination node. In these challenging environments, popular ad hoc routing protocols such as AODV [START_REF] Perkins | Ad-hoc on-demand distance vector routing[END_REF] and DSR [START_REF] Johnson | Dynamic source routing in ad hoc wireless networks[END_REF] fail to establish routes because they try to establish a complete route before forwarding the data. Instead what is needed is a routing scheme that is capable of storing messages and forwarding them once a link becomes available in hope that they will eventually reach their destinations. Several such routing schemes have been proposed in the research litterature, some of them seeking to minimize the message delivery time by replicating many copies of the message [START_REF] Vahdat | Epidemic routing for partially connected ad hoc networks[END_REF], whereas for other ones the emphasis is more on resource and energy consumption.

In our work, we focus on the so-called two-hop routing scheme, which is known to provide a good tradeoff between message delivery time and resource consumption [START_REF] Al-Hanbali | Performance of ad hoc networks with two-hop relay routing and limited packet lifetime[END_REF]. With two-hop routing, the communication is basically in 3 phases:

• First, the source gives the message to each and every mobile nodes it meets.

These nodes act as relays for delivering the message to its destination.

• A relay cannot forward the message to another relay, so it will store and carry the message until it is in radio range of the destination.

• Once this happens, the relay deliver the message to the destination.

In most previous works, it is assumed that relays are willing to cooperate with the source node. However, the delivery of a message incurs a certain number of costs for a relay. First, there are energy costs for receiving the message from the source and transmitting it to the destination. It is also natural to assume that there is some cost per unit time for storing the message in the buffer of the relay. The question we are interested in is thus the following: why should a relay accept to have its battery depleted and its buffer occupied for relaying messages exchanged between other nodes? In other words, how to persuade mobile nodes to participate in relaying messages?

For that purpose, we propose a very simple incentive mechanism. The source promises to each and every relay it meets a reward, but informs them that only the first one to deliver the message to the destination will get a reward. The reward asked by a relay has to offset its expected cost, as estimated by the relay when it meets the source. The reward thus depends on the time at which it meets the source, but also on the information given by the source through the probability of success estimated by the relay. When it meets a relay, the source has basically three options:

• it can give full information to the relay, that is it can tell to the relay the number and the age of all existing message copies,

• it can give only partial information to the relay, that is it can tell to the relay the number of message copies in circulation without disclosing the information on the age of these copies, and

• it can give no information at all to the relay, in which case the relay only knows at what time it met the source.

The dependence of the reward on the information has the following intuitive explanation. If for instance a relay is told by the source that many message copies are already in circulation, the relay will clearly estimate a smaller probability of getting the reward (since others relays could have already delivered the message), and thus this relay will naturally ask for a higher reward to offset its costs. On the contrary, it seems intuitively better for the source to give full information to the first relay it meets. To address this issue of selfish relay nodes, we present a solution based on mechanism design theory that considers how to implement good system-wide solution to problem that involved agents, each individual has a strategy space and decisions result as a function of his private information. The amount of reward proposed by source to relay nodes, is based on the private information that source node likes to share with a meeting relay. Hence our model is particular type of game of asymmetric information characterized by a leader (source node) who would like to condition his actions on some information that he decides to share with a selfish player.

Contributions

We propose an incentive mechanism for the relays to compensate for their costs and risks in carrying messages for a source. In the proposed mechanism every relay is proposed a different reward based on its meeting time with the source but only the first one to deliver gets its reward. The main contribution of this paper is the investigation of the influence of the information given by the source to the relays and the reward it has to propose to them as compensation.

We first focus on static strategies, that is strategies in which the source always give the same type of information (either full information, partial information, or no information) to the relays irrespective of their contact times. For each of the three information settings and for an arbitrary inter-contact distribution, we give expressions (in terms of integrals) for the reward that the source has to propose to each of the relays as a function of the meeting times with the previous relays.

The proposed reward guarantees full cooperation from each of the relays. Since only the first relay to deliver the message gets its reward, the amount paid by the source for the delivery of the message lies somewhere in between what is proposed to the first and the last relay. We show that the expected reward paid by the source is the same in all three settings. In other words, the expected reward paid by the source when it guarantees full cooperation of relays for delivering a message is the same irrespective of the information that source makes available to relays, as long as the source does not adapt the information it gives.

We then study the benefits that can be expected by the source from an adaptive strategy. In an adaptive strategy, the source decides to give full information, partial information or no information at all to a relay at the time it meets it, based on the contact times with this relay and all previous ones. Since the analysis is much more involved than in the static case, we restrict ourselves to the two following settings: (a) when there are only two relays, and (b) when inter-contact times with the source and the destination are exponentially distributed. Under both settings, we show that the source can do better by changing its strategy on the fly as and when it meets the relays. The resulting adaptive strategy will be shown to be of threshold type. Namely, in the setting with two relays, when the source meets the first relay, it is always optimal for the source to tell it that it is the first one. For the second relay, if it arrives before the threshold, which depends on the meeting time with the first relay, it is optimal to give full information, otherwise it is optimal not to give any information.

The above contributions are made under the assumption of arbitrary but independent and identically distributed inter-contact times. For the special case of exponentially distributed inter-contact times, we shall give explicit expressions for the probability of success of the relays in each of the three settings which, as a consequence, gives an explicit expression for the reward that a relay can expect to get in each of the three settings.

Organization of the paper

The paper is organised as follows: the next section we discuss the related works. Section 3 introduces the system model and the assumptions used in the paper. In section 4 we investigate the impact of information that the source share with relays on the reward that it proposes to them in the static scenario. The extension to the adaptative scenario is provided in section 5. Section 6 provides the simulation results which validate the analytical results. General discussion on main assumptions is held in section 7. Section 8 concludes the paper.

Related Work

In literature on DTNs [START_REF] El-Azouzi | Evolutionary forwarding games in delay tolerant networks: Equilibria, mechanism design and stochastic approximation[END_REF][START_REF] Zhang | Performance modeling of epidemic routing[END_REF], several incentive schemes have been recently proposed. For example, [START_REF] Shevade | Incentive-aware routing in dtns[END_REF] uses Tit-for-Tat (TFT) to design an incentive-aware routing protocol that allows selfish DTN nodes to maximize their individual utilities while conforming to TFT constraints. Mobicent [START_REF] Chen | Mobicent: a credit-based incentive system for disruption tolerant network[END_REF] is a credit-based incentive system which integrates credit and cryptographic technique to solve the edge insertion and edge hiding attacks among nodes. PI [START_REF] Lu | Pi: A practical incentive protocol for delay tolerant networks[END_REF] attaches an incentive on the sending bundle to stimulate the selfish nodes to cooperate in message delivery. SMART [START_REF] Zhu | Smart: A secure multilayer credit-based incentive scheme for delay-tolerant networks[END_REF] is a secure multilayer credit-based incentive scheme for DTNs. In SMART, layered coins are used to provide incentives to selfish DTN nodes for bundle forwarding. MobiGame [START_REF] Wei | Mobigame: A user-centric reputation based incentive protocol for delay/disruption tolerant networks[END_REF] is a user-centric and social-aware reputation based incentive scheme for DTNs. In addition, [START_REF] Li | Routing in socially selfish delay tolerant networks[END_REF] proposes socially selfish routing in DTNs, where a node exploits social willingness to determine whether or not to relay packets for others. Authors in [START_REF] Ning | Incentive-aware data dissemination in delay-tolerant mobile networks[END_REF] formulate nodal communication as a two-person cooperative game for a credit-based incentive scheme to promote nodal collaboration. RELICS [START_REF] Yusuf | Relics: In-network realization of incentives to combat selfishness in DTNs[END_REF] is another cooperative based energy-aware incentive mechanism for selfish DTNs, in which a rank metric was defined to measure the transit behavior of a node. In [START_REF] Wang | Incentive driven information sharing in delay tolerant mobile networks[END_REF], authors proposed an incentive driven dissemination scheme that encourages nodes to cooperate and chooses delivery paths that can reach as many nodes as possible with fewest transmissions. A fundamental aspect that is usually ignored in DTN literature is the feedback message, which may incur into a large delay. In fact, the exchange of rewards between relays should not require feedback messages. In order to overcome lack of feedback, the proposed mechanism assumes that a relay receives a positive reward if and only if it is the first one to deliver the message to the corresponding destination. [START_REF] Chahin | Incentive mechanisms based on minority games in heterogeneous delay tolerant networks[END_REF] is a credit-based incentive system using the theory of Minority Games [START_REF] Moro | The Minority Game: an introductory guide[END_REF] in order to attain coordination in distributed fashion. This mechanism considers the realistic case when the cost for taking part in the forwarding process varies with the devices technology or the users habits.

The proposed mechanism in this paper is a sub-field of mechanism design that concerns itself with how to develop incentive mechanism that will lead to a desirable solution from a systemwide point of view. In recent years mechanism design has found many important applications in the computer sciences; e.g., in security design problems [START_REF] Feigenbaum | Distributed algorithmic mechanism design: Recent results and future directions[END_REF] , in distributed scheduling resource allocation [START_REF] Johari | Efficiency loss in market mechanisms for resource allocation[END_REF] and cooperation routing in ad-hoc networks [START_REF] Molva | A collaborative repudiation mechanism to enforce node cooperation in mobile ad hoc networks[END_REF].

System Model and Objectives

We consider a wireless network with one source node, one destination node and N relays. We shall assume that the source and the destination nodes are fixed and not in radio range of each other, whereas other nodes are moving according to a given mobility model.

At time 0, the source generates a message for the destination. The source wants this message to be delivered to the destination as fast as possible. However, it cannot transmit it directly to the destination since both nodes are not in radio range of each other. Instead, the source proposes to each relay it meets a reward for delivering the message 1 . It is assumed that the network is two-hop, that is a relay has to deliver the message by itself to the destination (it cannot forward the message to another relay). An important assumption we shall make is that relays are not seeking to make profit: a relay accepts the message provided the reward promised to it by the source offsets its expected cost for delivering the message to the destination, as estimated by the relay when it meets the source. One can liken our model to that of FON in which users leave their WiFi access point open for others and in return are able to access WiFi in places other than their homes. Even though the FON model does not involve any exchange of payment, it still has a large number of subscribers, which shows that people are willing to share without necessarily having profit in mind.

This expected cost has several components. A relay that accepts the message from the source always incurs a reception cost C r . This is a fixed energy cost for receiving the message from the source. The relay will then store the message into its buffer and carry it until it is in radio range of the destination. We assume here that there is an incurred storage cost C s per unit time the message is stored in the buffer of the relay. Hence, the expected storage cost depends on the expected time it takes to reach the destination. Once the relay meets the destination, it can deliver the message. This incurs an additionnal transmission cost C d which is a fixed energy cost for transmitting the message to the destination. This cost is incured if and only if the relay is the first one to deliver the message to the destination, in which case the relay gets the reward. If on the contrary, the message has already been delivered, the relay gets nothing but save the transmission cost.

The payment mechanism we propose can be implemented as follows: to each relay it meets, the source gives an electronic cheque (or a promise of payment) worth the reward promised to this relay encrypted with the public-key of the destination. The relay that is the first to deliver the message also sends the e-cheque to the destination who then decrypts the e-cheque and sends it back to the relay. For the other relays, the destination does not decrypt the cheque. Therefore, the payments are made solely from the account of the source, and the destination determines who is the only one to get it.

Remark 1. Note that in this mechanism there is no incentive for a relay to accept a message from another relay (that is, a message will never have more than two-hops). This can be illustrated with an example. Consider relay 1 which has obtained the message from the source. As the reward proposed increases with time, any relay which accepts the message from either the source or relay 1 will definitely need a reward larger than what relay 1 got. This implies that relay 1 will need to a propose any other relay a reward higher than what it gets from the source. Thus, there is no incentive for relay 1 to forward to another relay. This argument holds for any relay. Hence, in our mechanism no relay will forward the message to another relay, and the network will work like a two-hop DTN irrespective of the underlying routing protocol.

The Role of Information

As should be apparent from the above discussion, the reward asked by a relay to the source depends both on the expected time it will take for the relay to reach the destination and on the probability of success it estimates at the time it meets the source. The latter represents the probability of this relay to be the first one to deliver the message. The crucial observation here is that this probability notably depends on the information given by the source to the relay.

Intuitively, if a relay is told by the source that there are already many message copies in circulation, it will correctly infer that it has a higher risk of failure than if it was the first one to meet the source, and it will naturally ask for a higher reward. The source can of course choose not to disclose the information on the number of existing message copies, in which case relays estimate their success probabilities based solely on the time at which they meet the source and on the number of competitors. In that case, the first relay to meet the source will certainly underestimate its success probability, and again ask for a higher reward than if it was told it was the first one.

It is thus clear that the expected reward to be paid by the source depends on the information it gives to the relays. There are several feasible strategies for the source. We shall distinguish between static strategies and dynamic strategies.

In static strategies, the information given to the relays is fixed in that it does not depend on the times at which the source meets the relays. We shall consider three static strategies:

• full information: each relay is told by the source how many other relays have already received the message, and at what times,

• partial information: each relay is told by the source how many message copies there are in circulation, but the source does not reveal the age of these copies,

• no information: each relay is told nothing by the source; it only knows at what time it meets the source.

In dynamic strategies, the source adapts the information it conveys on the fly as and when it meets the relays. In such a strategy, the decision to give full information, only partial information or no information at all to a relay depends on the contact times with previous relays.

Assumptions on Contact Processes

As mentionned before, the N relays are moving according to a given mobility model. This model represents the movement of relays, and how their location, velocity and acceleration change over time. However, rather than assuming a specific mobility model, we instead characterize the movements of relays solely through their contact processes with the source and the destination. Our main assumption here is that inter-contact times between a relay and the source (resp. destination) are independent and identically distributed (i.i.d.) random variables with finite first and second moments. In the following, we let T s (resp. T d ) be the random time between any two consecutive contacts between a relay and the source (resp. destination). We shall moreover assume that the random variables T s and T d are independent. In addition, we shall assume that contacts between relays and any of the fixed nodes are instantaneous, i.e., that the duration of these contacts can be neglected.

Another assumption we make is that the nodes do not keep track of previous meeting instants with the other nodes. This assumption is important for the calculation of rewards because it implies that the source and a relay have the same information about the future meeting time of this relay with the destination. Hence, with any information the source gives to this relay both will compute the same reward. If this assumption were not satisfied, then the relay would have an additional piece of information in the time it last met the destination. Using this information its posterior probability of meeting the destination after picking up the packet would be different from the one computed by the source.

At this point, we make two important observations which hinge upon the previous assumptions of i.i.d. contact process and relays not keeping track of previous contacts:

• For a given relay, the time instant at which the message is generated by the source can be seen as a random point in time with respect to the contact process of this relay with the source. Hence, the random time between the instant at which the message is generated and the instant at which the relay will meet the source corresponds to what is called the residual life of the inter-contact times distribution with the source in the language of renewal theory. In the sequel, we shall refer to this time as the residual inter-contact time with the source.

• Similarly, the time instant at which a given relay receives the message from the source can be considered as a random point in time with respect to the contact process of this relay with the destination. Hence, residual inter-contact time with the destination is given by the residual life of the inter-contact times distribution with the destination.

Let F s (x) = P(T s > x) (resp. F d (x) = P(T d > x)) be the complementary cumulative distribution function of T s (resp. T d ). As a consequence of the above, the density functions of the residual inter-contact times with the source and the destination are given by fs (x) = F s (x)

E[T s ] and fd (x) = F d (x) E[T d ] , (1)
respectively. We also note that the mean residual inter-contact times with the source and the destination are given by E

[ Ts ] = E[T 2 s ]/(2 E[T d ]) and E[ Td ] = E[T 2 d ]/(2 E[T d ])
, respectively.

Objectives

In the following, we adopt the point of view of the source and investigate the strategy it should follows in order to minimize the price to be paid for delivering a message. We first analyze the case of static strategies in Section 4, and then consider dynamic strategies in Section 5.

Expected Reward Under a Static Strategy

In this section, we assume that the source follows a static strategy, i.e., it does not adapt the information it conveys to as and when it meets the relays. More precisely, we consider the three following settings: (a) the source always gives full information to the relays, (b) it always gives only partial information to the relays or (c) it always gives no information at all to the relays. In the sequel, the superscript F (resp. P , N ) will be used to denote quantities related to the full information (resp. partial information, no information) setting. Also, we shall use relay i and the i th relay interchangeably to refer to the relay that is the i th one to meet the source in chronological order.

Estimated Probability of Success

Let also S i , i = 1, . . . , N , be the random time at which the source meets the i th relay. We denote by S the vector (S 1 , . . . , S N ). In order to simplify notations, we shall write S -n to denote the vector (S 1 , . . . , S n-1 , S n+1 , . . . , S N ) and S m:n to denote the vector (S m , . . . , S n ). Similarly, for fixed s 1 , s 2 , . . . , s N , we denote by s the vector (s 1 , s 2 , . . . , s N ). We shall also use the notations s -n and s m:n with the same interpretation as for vectors of random variables. Define p i (s) as the (real) probability of success of the i th relay for the given vector s of contact times, that is the probability of this relay to be the first one to deliver the message. Let also p (k) i (s) be the probability of success estimated under setting k by relay i when it meets the source2 . Note that in general p (k) i (s) and p i (s) are different. Indeed, the probability of success p i (s) depends on all contact times. On the contrary, it is obvious that for i < N , p (k) i (s) does not depend on s i+1 , • • • , s N , since, when it meets the source, relay i does not know at what time the source will meet relays i + 1, . . . , N . Similarly, for i > 1, p (k) i (s) depends on s 1 , . . . , s i-1 only in the full information setting. Besides, we also note that

p (P ) 1 (s) = p (F ) 1 (s), (2)
since the first relay obtains exactly the same information from the source in the partial information and in the full information settings. Finally, we note that

p (F ) N (s) = p N (s), (3)
since in the full information setting, the last relay knows the contact times of all relays with the source. i (s) be the reward asked by this relay to the source under this setting. The reward

Expected Cost for a Relay

R (k) i (s)
proposed to relay i has to offset its expected cost E[V (k) i (s)], which is given by

E[V (k) i (s)] = C r + C s E[ Td ] + [C d -R (k) i (s)]p (k) i (s). ( 4
)
The first term in the net expected cost is the reception cost, which is always incurred. The second term represents the expected storage cost. It is directly proportional to the mean of the residual inter-contact time with the destination. The last term is the cost of transmitting the message to the destination which then gives the reward to the relay. This term enters into play only if relay i is the first one to reach the destination, which explains the factor p (k) i (s).

Rewards Promised by the Source to Individual Relays: General Inter-Contact Times

Relay i will accept the message provided the proposed reward offsets its expected cost, that is, if

R (k) i (s) is such that E[V (k) i (s)] ≤ 0.
Thus, the minimum reward that the source has to promise relay i is

R (k) i (s) = C d + C r + C s E[ Td ] 1 p (k) i (s) =: C 1 + C 2 1 p (k) i (s) . (5)
Note that the reward asked by relay i depends on the information given by the source only through the estimated probability of success p (k) i .

Given S 1 = s 1 , • • • , S N = s N , the expected reward paid by the source under setting k is

R (k) (s) = N i=1 p i (s)R (k) i (s). (6)
With [START_REF] Al-Hanbali | Performance of ad hoc networks with two-hop relay routing and limited packet lifetime[END_REF], it yields

R (k) (s) = C 1 + C 2 N i=1 p i (s) p (k) i (s) . ( 7
)
While the reward promised to the relays in different information settings can be computed using the above equations, later we will give explicit expressions for these rewards for exponential inter-contact times which are observed in certain mobility models.

Before going to exponentially distributed inter-contact times, we present our main result, which holds for general inter-contact time distributions.

Expected Reward Paid by the Source

Until now, we have computed the reward the source should offer to each of the relays as a function of the time it meets them and the information offered to them. We now turn our attention to the expected reward paid by the source when the expection is taken over all possible meeting times. This quantity can be thought of as the long-run average reward per message the source will have to pay if it sends a large number of messages (and assuming that message generation occurs at a much slower time scale than that of the contact process).

The expected reward paid by the source under setting k can be obtained by unconditioning [START_REF] El-Azouzi | Evolutionary forwarding games in delay tolerant networks: Equilibria, mechanism design and stochastic approximation[END_REF]

on S 1 , • • • , S N , R (k) = s R (k) (s)f S (s)ds = ∞ s1=0 ∞ s2=s1 • • • ∞ s N =s N -1 R (k) (s)f S (s)ds N • • • ds 2 ds 1 , (8)
where f S (s) is the joint distribution of S 1 , • • • , S N . Since the residual intercontact times between the relays and the source are i.i.d. random variables, f S (s) is the joint distribution of the order statistics of the N random variables

S 1 , • • • , S N . That is, f S (s) = N ! fs (s 1 ) . . . fs (s N ). (9)
With ( 7), ( 8) and ( 9), we obtain the expected reward paid by the source in terms of the probabilities of success estimated by the relays,

R (k) = C 1 + C 2 N ! N n=1 s p n (s) p (k) n (s)
fs (s 1 ) . . . fs (s N )ds. [START_REF] Lu | Pi: A practical incentive protocol for delay tolerant networks[END_REF] From the probability of success estimated by the relays in the three settings, we can prove that the expected reward to be paid by the source for delivering its message is the same in all three settings, as stated in Theorem 1.

Theorem 1. The expected reward to be paid by the source under setting k ∈ {F, P, N } is

R (k) = C 1 + N C 2 . ( 11
)
Proof. See Appendix A.

Remark 2. We note that our result can be adapted to the case when the intercontact times distributions are different for different relays. In that case one needs to replace (9) by the equivalent density computed using the Bapat-Beg theorem [START_REF] Bapat | Order statistics for non identically distributed variables and permanents[END_REF] for the order statistics of independent but not necessarily identical distributed random variables. This formula is quite complicated to use in practice. Also, if we assume heterogeneous inter-contact time, it means that each relay has to know the inter-contact time distribution of all the other relays, which may not be a realistic assumption.

Theorem 1 shows that if the source does not adapt the information it gives, the expected reward it will have to pay remains the same irrespective of the information it conveys. We also note that the expected reward grows lineraly with the number of relays.

The result in Theorem 1 has the following intuitive explanation. It says that the expected reward paid by the source is equal to expected total cost incurred by all the relays in the process of delivering the message. Each relay accepts and stores the message until it meets the destination, and a cost of

C 2 = C r + C s E[ Td ]
in the process. Since there are N relays which carry the message, the expected total cost for carrying the message is N C 2 . Of these N , one relay will be successful in delivering the message and will incur an additional delivery cost of C 1 = C d . Thus, the expected total cost incurred by the relays is C 1 + N C 2 . Since on the long run the relays make neither a profit nor a loss, the expected total costs incurred by the relays should be offset by the reward paid by the source, which explains the result in Theorem 1. What is less intuitive though is that the expected reward paid does not depend on the type of information given to the relays.

Rewards Promised by the Source to Individual Relays: Exponential Inter-Contact Times

Let us assume that the inter-contact times between a relay and the source (resp. destination) follows an exponential distribution with rate λ (resp. µ)

We shall first compute the probability of success of each of relays given all the contact times, and then use this expression to compute the probability of success of each of relays in the three information settings. The rewards to be promised to relays can then be computed using [START_REF] Al-Hanbali | Performance of ad hoc networks with two-hop relay routing and limited packet lifetime[END_REF].

Proposition 1. For a given vector s = (s 1 , • • • , s N ), the success probability of n th relay is,

p n (s) = N i=n 1 -e -µ(si+1-si) i i i j=1 e -µ(si-sj ) . (12)
Proof. Consider relay n that met the source at time s n and first compute its probability to deliver the message to the destination for each time interval (s i , s i+1 ], n ≤ i < N . The probability that a relay does not meet the destination in (s i , s i+1 ] is e -µ(si+1-si) , and the probability that the n th relay will be the first one to meet the destination in (s i , s i+1 ] among i relays that have the message at time

s i , is 1-(e -µ(s i+1 -s i ) ) i i .
Next, take into account the probability that none of the relays that received the message before time s i have not yet meet the destination, which is i j=1 e -µ(si-sj ) .

The probability of success of the n th relay is then the sum of success probabilities in each interval (s i , s i+1 ], i ≥ n,

p n (s) = N i=n 1 -e -µ(si+1-si) i i i j=1 e -µ(si-sj ) . (13)
Next, for each setting k ∈ {F, P, N }, write the success probability, p

i , estimated by relay i when it receives the message from the source.

Full Information Case

Proposition 2. For given times s = (s 1 , • • • , s n ), n th relay computes its probability of success as

p (F ) n (s) = µ n-1 k=1 e -µ(sn-s k ) N i=n (N -n)! (N -i)! λ i-n i j=n 1 (N -j)λ+jµ . ( 14
)
Proof. The formal proof involves unconditioning the probability in [START_REF] Wei | Mobigame: A user-centric reputation based incentive protocol for delay/disruption tolerant networks[END_REF] on the meeting times of the subsequent relays with the source, and in given in the research report [START_REF] Seregina | On the design of a reward-based incentive mechanism for delay tolerant networks[END_REF] which accompanies this paper. Here we give a sketch of the proof which summarizes the main steps. Let S j (resp. Y j ) be a random time at which j th relay meets the source (resp. destination). Note that S j ,

• • • , S N and Y 1 , • • • , Y j-1 are independent ∀j ≥ 2.
Recall that for independent exponential random variables X 1 , • • • , X n with respective parameters λ 1 , • • • , λ n , the probability that the minimum is

X i is λ i /(λ 1 + • • • + λ n ).
Consider relay n that met the source at time s n . For j > n, the probability that S j is the minimum from random variables S j , • • • , S N and Y 1 , • • • , Y j-1 is λ/((N -j +1)λ+(j -1)µ), which essentially means that random time S j will be the first to occur among the random variables S j , • • • , S N of meeting times with the source and that none of j -1 relays will not meet the destination before S j happens.

For i > n, the product

(N -n)! ((N -n) -(i -n))! i j=n+1 λ (N -j + 1)λ + (j -1)µ ( 15
)
represents probability that S i is the minimum from

S i , Y 1 , • • • , Y i-1 where S n+1 < • • • < S i .
This means that after time s n and before time S i occurs no relay has yet met the destination. For i ≥ n, the probability that Y n is the minimum from

S i+1 , • • • , S N , Y 1 , • • • , Y i is µ (N -i)λ + iµ , (16)
that means that n th relay will be the first to deliver the message before time S i+1 . Thus, probability that n th relay will deliver the message to the destination in time interval (s

i , s i+1 ], n ≤ i < N is, (N -n)! (N -i)! µ λ i j=n λ (N -j)λ + jµ , (17)
and by summing over the subsequent relays one obtains probability that after time s n , n th relay will be the first to deliver the message, that is,

N i=n (N -n)! (N -i)! µ λ i j=n λ (N -j)λ + jµ , (18)
The probability that none of the relays that received the message before time s n did not yet meet the destination is n-1 k=1 e -µ(sn-s k ) . With this and (18), we obtain the success probability of n th relay given times

s 1 , • • • , s n , p (F ) n = µ n-1 k=1 e -µ(sn-s k ) N i=n (N -n)! (N -i)! λ i-n i j=n 1 (N -j)λ+jµ . (19)
4.5.2 Partial Information Case Proposition 3. Given the time s n with the number, n, of already existing copies, the n th relay computes its success probability as

p (P ) n (s) = λ λ-µ e -µsn -e -λsn 1-e -λsn n-1 ×µ N i=n (N -n)! (N -i)! λ i-n i j=n 1 (N -j)λ+jµ , if λ = µ, (20)
and

p (P ) n (s) = λs n e -λsn 1-e -λsn n-1 N i=n (N -n)! (N -i)!N i-n+1 , if λ = µ. (21)
Proof. The probability that after time s n , the n th relay is the first one to deliver the message to the destination is given by [START_REF] Moro | The Minority Game: an introductory guide[END_REF]. Consider a relay that received the copy of the message before time s n . For λ = µ, the probability that the relay does not meet the destination before s n is sn 0 λe -λs e -µ(sn-s)

1 -e -λsn ds = λ λ -µ e -µsn -e -λsn

1 -e -λsn .

Then the probability that none of the n -1 relays that received the message before time s n did not deliver it to the destination before s n is

λ λ -µ e -µsn -e -λsn
1 -e -λsn n-1

, for λ = µ.

The product of this probability with the probability (18) that after time s n , n th relay is the first one to deliver the message to the destination, gives the claimed result.

Similarly reasoning, the claimed result for λ = µ is obtained after substituting λ instead of µ in [START_REF] Moro | The Minority Game: an introductory guide[END_REF] and with that the integral in [START_REF] Bapat | Order statistics for non identically distributed variables and permanents[END_REF] gives λs n e -λ sn 1-e -λ sn .

Corollary 1. For the given times s = (s 1 , • • • , s n ), the success probability of the n th relay in the full information setting, p (F ) n , can be represented through p (P ) n as follows,

p (F ) n (s 1 , • • • , s n ) = n-1 k=1 e -µ(sn -s k ) λ λ-µ e -µsn -e -λsn
1-e -λsn n-1 p

(P ) n (s), if λ = µ. ( 24
)

No Information Case

Proposition 4. Given only the time s n , the n th relay computes its success probability as

p (N ) n (s) = = N m=1 (N -1)! (N -m)!(m-1)! 1 -e -λsn m-1 e -λsn N -m p (P ) m . (25)
Proof. Consider the relay n that meets the source at time s n and informed only this meeting time and not the number of already existing copies of the message. The probability that any relay does not meet the source before time s n is e -λsn and that it meets the source is 1 -e -λsn . Then the n th relay can compute its probability of success as

p (N ) n (s) = = N m=1 C m-1 N -1 1 -e -λsn m-1 e -λsn N -m p (P ) m (s) = N m=1 (N -1)! (N -m)!(m-1)! 1 -e -λsn m-1 e -λsn N -m p (P ) m (s). (26)
Thus, the source when it meets a relay can compute the reward it should promise to this relay within each setting based on the corresponding success probability estimated by the relay.

Adaptive Strategy

The analysis in the previous section shows that as long as the information given to all the relays is of the same type, the source has to pay the same reward. Could the source do better by changing the type of information it gives to relays based on and when it meets them? We show in this section that the source can indeed reduce the expected reward it pays if it can adapt the type of information dynamically. Consider the following situation in which the source encounters the second relay a long time after it encountered the first one. If the source discloses the time when it met the first relay to the second one, then the second relay will correctly compute its probability of success to be small and will ask for a high reward. If instead the source were not to disclose this information, then the probability of success computed by the relay would be higher and the source could propose a lower reward. Thus, source stands to gain by changing the type of information based on the time instants it encounters the relays.

In this we shall investigate the benefits that an adaptive strategy can procure for the source, and bring to light certain structural properties concerning of the optimal adaptive strategy for some particular cases of the model.

A key assumption we shall make in the analysis of the adaptive strategy is that the relays do not react to the fact that the source is adapting its strategy. A relay will compute its success probability based only on its contact time with the source and additional information, if any, received from the source. In practice, if the relay knows that the source will adapt its strategy as a function of time, then the relay will also react accordingly, to which the source will react, and so on ad infinitum. As a first approximation, we shall restrict the analysis of the adaptive strategy assuming that the relays are naive.

Adaptive Versus Static Strategies

We shall first give bounds on the expected reward paid by the source when it uses the adaptive strategy.

Let R (A) denote the expected reward paid by the source when it uses the adaptive strategy. The decision of the source to either give or not information to a relay it meets will depend upon the reward it has to propose in each of the three settings. Thus, the source when it meets a relay can compute the reward it should promise to this relay within each setting based on the corresponding success probability estimated by the relay and then to choose the setting of least reward to be paid to this relay. That is,

R (A) = s N n=1 p n (s) min k R (k) n f S (s)ds. ( 27
)
From the definition of the adaptive strategy, it can do no worse than any static strategy which gives an upper bound. Also, the source has to pay at least C 1 + C 2 because this is the average cost when there is only one relay, which gives a lower bound. It follows that

Proposition 5. C 1 + C 2 ≤ R (A) ≤ R (k) = C 1 + N C 2 . Corollary 2. R (A) R (k) ≥ C1+C2 C1+N C2 ≥ 1 N .
By using an adaptive strategy the source can reduce its expenses at most by a factor of 1/N .

Although the exact analytical expressions for an adaptive policy is difficult to compute, an advantage of the adaptive strategy can be seen from the numerical results. In Figures 1 and2 with λ and is gets close to R (F ) when λ → ∞. On the other hand, for small values of λ, R (A) is close to the minimal reward

5 relays, µ =1, C 1 =1, C 2 =5 C 1 + NC 2 C 1 + C 2
C 1 + C 2 . It appears that R (A) has the form (C 1 + C 2 ) + C 2 (1 -e -λγ
), for some constant γ, but we are unable to prove this result. The exact analytical expression of R (A) is difficult to compute unlike the expression for R (k) . Nonetheless, we shall give some structural properties of the adaptive strategy. In particular, for N = 2, it will be shown that the adaptive strategy is of threshold type in which the second relay is given either full information or no information depending on how late it meets the source after the first one.

Two Relays, Decreasing Density Function of Inter-Contact Times

Let us consider a network of a fixed single source, a fixed single destination, and two relays with an underlying mobility model described in the Section 3.2. Futher assume that densities of residual inter-contact times, fs and fd , are decreasing functions.

In order to establish the structure of the adaptive strategy, one needs to determine which information setting has the lowest reward at any given instant. The reward of a given setting depends in turn on the probability of success estimated by the relay based on the information given by source (see [START_REF] Al-Hanbali | Performance of ad hoc networks with two-hop relay routing and limited packet lifetime[END_REF]). For the comparison of the rewards, we shall need a few results on the probabilities of success, which we give now. Lemma 1.

1.

p 2 (s) ≤ 1 2 ≤ p 1 (s), (28)
2. for fixed

s 2 , p 1 (s 1 , s 2 ) decreases (p 2 (s 1 , s 2 ) increases) with s 1 . Proof. See Appendix B.
The above result states that the real probability of success of the first relay decreases when its meeting time with the source gets closer to that of the second relay. It gives a similar monotonicity result for the probability of success of the second relay. The assumption of decreasing density function comes into play in the proof of these results.

The next lemmas shows the similar inequalities for the success probabilities in the full information setting and the partial information setting.

Lemma 2. p (F ) 2 (s) ≤ 1 2 ≤ p (F ) 1 (s). (29)
Proof. The first inequality follows from Lemma 1 and equality (3). For the second inequality, note that the probability of success of the first relay in the full information setting can be represented as follows,

p (F ) 1 (s) = ∞ s2=s1 p 1 (s) fs (s 2 -s 1 )ds 2 . (30)
Using Lemma 1 for p 1 (s), we obtain

p (F ) 1 (s) ≥ 1 2 ∞ s2=s1 fs (s 2 -s 1 )ds 2 = 1 2 , (31) since
∞ s2=s1 fs (s 2 -s 1 )ds 2 = 1 due to the property of probability density function. Lemma

Proof. From Lemma 2 for p

(F )
1 , along with equation ( 2), it follows that p

(P ) 1 (s) ≥ 1/2. It is now sufficient to show that p (P ) 2 (s) ≤ 1/2.
The success probability of the second relay in the partial information setting satisfies

p (P ) 2 (s) = s2 s1=0 p (F ) 2 (s) fs (s 1 )ds 1 s2 s1=0 fs (s 1 )ds 1 (33) ≤ 1 2 s2 s1=0 fs (s 1 )ds 1 s2 s1=0 fs (s 1 )ds 1 = 1 2 . ( 34
)
where the inequality follows from Lemma 2 according to which p

(F ) 2 ≤ 1/2.
We now proceed to the main results on the comparison of the rewards in various information settings. The first results shows that it is always beneficial for the source to give information to the first relay independently of s 1 .

Proposition 6. R (F ) 1 (s) = R (P ) 1 (s) ≤ R (N ) 1 (s) (35)
Proof. The equality R

(F ) 1 = R (P ) 1
follows from ( 5) and (2). For the inequality, from [START_REF] Al-Hanbali | Performance of ad hoc networks with two-hop relay routing and limited packet lifetime[END_REF], it is sufficient to establish that

p (N ) 1 (s) ≤ p (P ) 1 (s), ∀s 1 ≥ 0. The probability, p (N ) 1 (s) = p (P ) 2 (s 1 )P(S 2 < s 1 ) + p (P ) 1 (s 1 )(1 -P(S 2 < s 1 )) = P(S 2 < s 1 ) p (P ) 2 (s 1 ) -p (P ) 1 (s 1 ) + p (P ) 1 (s 1 ) ≤ p (P ) 1 (s 1 ), (36)
where the last inequality follows from (32).

The next result in favour of an adaptive strategy pertains to the reward the source should propose to the second relay.

Proposition 7. R (N ) 2 (s) ≤ R (P ) 2 (s). ( 37
)
Proof. The success probability of the second relay in the no information setting, p

P(S 1 < s 2 ) + p (P ) 1 (s)(1 -P(S 1 < s 2 )), (N ) 2 (s), can be expressed as p (N ) 2 (s) = p (P ) 2 (s)
with S 1 being the random time when the source gives the copy of the message to the first relay it meets. With (32), the following inequality holds,

and the statement of the proposition follows.

Proposition 7 says that between the choice of informing a relay that it is the second one and not giving this information, it is better for the source not to give this information.

Before proceeding to the next result, we prove another lemma. The first term of the last sum is negative due to (32). To complete the proof, we show the negativity of two last terms of this sum.

From (33), find the derivative, dp With [START_REF] Perkins | Ad-hoc on-demand distance vector routing[END_REF] and from (30), the derivative,

dp (P ) 1 (s) ds = -p 1 (s, s) fs (s) < 0.
Thus, the derivative dp (N ) (s) ds is negative and the claimed result follows.

Until now we have shown that it is optimal to give the full information to the first relay, and for the second relay it is giving no information is always better that giving partial information. We now compare the settings of no information with that of full information.

Our main result for this section, stated in Theorem 2 shows that there is a threshold, which depends on the meeting time with the first relay, before which it is optimal to give full information to the second relay and beyond which it is optimal to give no information. Once, the source meets the first relay, it can compute this threshold, and based on when it meets the second relay decide to give or not the information.

Define the difference of the success probabilities as a function of s 1 and s 2 ,

g(s 1 , s 2 ) = p (N ) 2 (s 1 , s 2 ) -p (F ) 2 (s 1 , s 2 ), (40)
then for the source, it will be better to give information when g(s 1 , s 2 ) < 0.

Theorem 2. There exists

0 ≤ θ 1 < ∞ such that 1. if 0 ≤ s 1 < θ 1 , then g(s 1 , s 2 ) ≥ 0, ∀s 2 ≥ s 1 ; 2. if θ 1 < s 1 < ∞, then (a) g(s 1 , s 2 ) < 0, ∀s 2 ∈ [s 1 , s 1 + ω(s 1 )), (b) g(s 1 , s 2 ) > 0, ∀s 2 ∈ (s 1 + ω(s 1 ), ∞),
where θ 1 is a solution of the equation g(s 1 , s 1 ) = 0 and ω(s 1 ) is a solution of g(s 1 , s 1 + v) = 0 with respect to v when g(s 1 , s 1 ) < 0. and hence, g(0, s 2 ) ≥ 0. Since, for fixed s 2 , the function g(s 1 , s 2 ) is non-negative at s 1 = 0 and decreases in s 1 , we can conclude that the equation g(s 1 , s 2 ) = 0 has at most one real solution with respect to s 1 . Thus, if for s 1 and s 2 close to each other, g(s 1 , s 2 ) < 0, i.e. if g(s 1 , s 1 ) < 0 then there exists ω(s 1 ) such that g(s 1 , s 2 ) < 0 if s 2 ∈ [s 1 , s 1 + ω(s 1 )) and g(s 1 , s 2 ) > 0 for s 2 ∈ (s 1 + ω(s 1 ), ∞) since g(s 1 , s 1 + v) increases with v as was seen before. Meanwhile, in case g(s 1 , s 1 ) ≥ 0, the difference g(s 1 , s 1 + v) will be positive ∀v ≥ 0. Now let us find out when the condition g(s 1 , s 1 ) < 0 holds. As was shown before, for fixed s 2 , g(0, s 2 ) ≥ 0, and hence, g(0, 0) ≥ 0. Consider the behaviour of g(s 1 , s 1 ) with increasing of s 1 .

Note that p

(F ) 2 (s 1 , s 1 ) = 1/2, since, p (F ) 2 (s 1 , s 1 ) = ∞ y2=0 fd (y 2 ) ∞ y1=y2 fd (y 1 )dy 1 dy 2 = 1/2, ( 47
)
proof of which can be found in the proof of Lemma 1. Thus,

g(s 1 , s 1 ) = p (N ) 2 (s 1 , s 1 ) -1 2 , (48)
and it decreases with s 1 since p (N ) 2

decreases with time (Lemma 4). Thus, the equation g(s 1 , s 1 ) = 0 has at most one real solution θ with respect to s 1 , such that if 0 ≤ s 1 ≤ θ then g(s 1 , s 1 ) > 0. If s 1 > θ then g(s 1 , s 1 ) < 0 and the threshold ω(s 1 ) for the meeting time s 2 holds.

Two relays, exponentially distributed inter-contact times

Let us illustrate the result in Theorem 2 for exponentially distributed intercontact times.

The difference in (40)) can be written as

g(s 1 , s 1 + v) = a(s 1 )e -µv -b(s 1 )e -λv , where
a(s 1 ) = 1 2 λ λ -µ e -µs1 -1 , and b(s 1 ) = µ 2 λ 2 -µ 2 e -λs1 .
First, consider the case λ > µ. Proposition 8 ( [24]). For λ > µ, there exist 0

≤ θ 1 ≤ θ 2 < ∞ such that 1. if 0 ≤ s 1 ≤ θ 1 , then g(s 1 , s 1 + v) ≥ 0, ∀v ≥ 0; 2. if s 1 ≥ θ 2 , then g(s 1 , s 1 + v) < 0, ∀v ≥ 0; 3. if θ 1 < s 1 < θ 2 , then 2. if θ 1 < s 1 < ∞, then (a) g(s 1 , s 1 + v) < 0, ∀s 2 ∈ [s 1 , s 1 + ω(s 1 )); (b) g(s 1 , s 1 + v) > 0, ∀s 2 ∈ (s 1 + ω(s 1 ), ∞);
where θ 1 and ω(s 1 ) are as defined in Proposition 8.

s 2 = s 1 + ω(s 1 ) s 1 s 2 θ 1 s 1 = s 2 FULL NO INFORMATION
research community. A non homogenous spatial dispersion of nodes are created by random way point model. A Mobile node starts to travel new selected goal at selected speed. After that the mobile node pauses for a time interval and then again starts the process. The new speed and direction are both chosen from pre-defined ranges [1, 13.9]. We collected inter-contact time traces over 800 weeks for 10 relays. Using these traces, we computed the inter-contact time distribution, which is then used by the source and the relays to compute the promised reward to each relay.

Every 20 hours, the source generates a message. This period of 20 hours will be called a time-slot. The simulation time of 800 weeks corresponds to 6720 slots. In figures 5-7 we plot the expected reward as a function of time-slot computed by analytical model and simulation for N = 2, N = 4 and N = 10. We observe that the analytical results match closely the simulator result. We also observe that the three curves for three stettings are very closed after few time slots (e.g., 100 slots for two relays). There is a slight discrepancy between the simulation and the analytical results due to a small amount of inhomogeneity in the inter-contact time distributions of relays.

Discussion of Assumptions, Limitations and Future Work

In this section we discuss the main assumptions that were adopted to yield a tractable model and we describe limitations and possible extensions.

Routing protocols: Our proposed scheme in principle can work for any DTN routing protocol. Indeed, the assumption about how a relay node obtains a reward may limit coordination between relay nodes. In fact, in order to avoid the use of feedbacks that allow relays to know whether the message has been successfully delivered or not, we assume that a relay will receive a reward if and only if it is the first one to deliver the message. However, this reward scheme may foster unintended deviant behaviors in which relay nodes may refuse to forward messages to other relays in order to increase their own utility. In the future, we will propose a modification of our mechanism that can eliminate this problem by using some additional rewards between relays in order to incentivize messages propagation between them. Mobility pattern: A key challenge in developing our results has been to make general assumptions about the mobility of DTN nodes. In particular, the properties derived for our incentive mechanism hold under any homogeneous mobility pattern. Indeed, the large majority of analytical studies are typically assumed that the cumulative distribution function of inter contact time decays exponentially over time such as in random waypoint models. But many extensive empirical mobility traces have been showed that cumulative distribution function of inter contact time follows approximately a power law over large time range with exponent less than unit [START_REF] Chaintreau | Impact of human mobility on opportunistic forwarding algorithms[END_REF]. By investigating a general assumption about the mobility, in future works, we will evaluate our scheme on realistic traces [START_REF] Rawdad | A community resource for archiving wireless data at dartmouth[END_REF] in order to evaluate the robustness of our proposed mechanism. Another aspect that we want to take into account is the heterogeneous models.

Existing analytical studies in the literature strongly rely on the assumption that nodes identical and uniformly visit the entire network space. Experimental data, however, have shown that mobility patterns of individuals are typically restricted to a given area, and the overall node density is often largely inhomogeneous. Such models allow studying how DTN routing mechanisms are affected by highly inhomogeneous node density and differences in mobility patterns and transmission technologies.

Buffer management: In our model we consider only one source-destination pair generates packet into DTN. For several source-destination pairs, node buffers may well overflow if no message discarding policy is adopted. In this scenario, efficient drop policies at relay nodes decide which messages should prioritised under capacity constraints regardless of the specific routing algorithm used. In the future, we propose to work on intentional DTN Drop/Scheduling policies with respect to our mechanism. Such study engenders sources to develop a mechanism design in order to know the information about the messages that relay stores in his buffer. Then we will propose a mechanism that can allow the source to truthfully elicit private information from each and every relay nodes it meet. However, information elicitation is most challenging when it is most useful: when there is no ground truth available to evaluate answers.

Conclusions

In this paper we proposed a reward mechanism to incentive relays to sacrifice their memory and battery on DTNs relaying operation. Furthermore we argue that such a coordination scheme should not rely on end to end control message exchange. To this respect, our paper provided a novel key contribution: the reward mechanism in fact is designed to secure the participation of relays in the delivery process by proposing a reward that takes into account the costs incurred by the relays and the risk they are exposed to during the delivery process. This reward is the minimum amount that offsets the expected delivery cost, as estimated by the relay from the information given by the source (number of existing copies of the message, age of these copies). We first showed that the expected reward paid by the source remains the same irrespective of the information it conveys, ranging from full state information to no information. We also studied the dynamic case in which the source can change the information that it conveys on the fly as and when meets the really. Under some additional assumptions, the source can gain by adopting the dynamic strategy.

A Proof of the Theorem 1 (55)

A.3 No Information Case

Since the success probability of the n th relay in the no information setting depends only on s n , we can rewrite the expression for the expected reward paid by the source as (60)

R (N ) = C 1 + C 2 × × N n=1 ∞ sn=0 1 p

B Proof of Lemma 1

Proof. Prove the first inequality in the first part of the lemma. Then the second inequality will follow from the fact that p 1 (s) + p 2 (s) = 1.

The probability of success of the second relay given vector of meeting times with the source, s,

p 2 (s) = ∞ y2=s2 fd (y 2 -s 2 ) ∞ y1=y2
fd (y 1 -s 1 )dy 1 dy 2 .

(61)

Change the variables and using the properties of the integration of non-negative functions obtain, (62)

The last expression gives 1/2. Show it thoroughly. Consider probability density function f (•). Thus, for the function f , by the changing of integration order obtain,

∞ u=0 f (u) ∞ v=u f (v)dvdu = ∞ v=0 f (v) v u=0 f (u)dudv. ( 63
)
Note also, that the integration in the left hand side does not depend of the choice of the integration variables and thus can be rewritten as

∞ u=0 f (u) ∞ v=u f (v)dvdu = ∞ v=0 f (v) ∞ u=v f (u)dudv. ( 64
)
Summation of this two equalities gives one in the right hand side due to the properties of the probability density function and thus,

∞ u=0 f (u) ∞ v=u f (v)dvdu = 1 2 . ( 65
)
Since p 1 (s) + p 2 (s) = 1, then for the second statement of the lemma to hold, show only that for fixed s 2 , the probability p 2 (s 1 , s 2 ) is increasing function of s 1 . This directly follows from (61) due to the decreasing property of the function fd .

  as the net cost for relay i under setting k, and let R (k)

  , R(A) is plotted as a function of λ for N = 5, µ = 1, C 1 = 1, and C 2 = 5 (C 2 = 0.5 in Figure2). It is observed that R

Figure 1 :

 1 Figure 1: Expected reward paid by the source for the adaptive strategy. N = 5, µ = 1, C 1 = 1, C 2 = 5.

Figure 2 :

 2 Figure 2: Expected reward paid by the source for the adaptive strategy. N = 5, µ = 1, C 1 = 1, C 2 = 0.5.

Lemma 4 .

 4 p (N ) (s) decreases with s.Proof. The probability,p (N ) (s) = p

( 1 -

 1 P( Ŝ < s)).

( 1 -

 1 P( Ŝ < s)).

  , s) -p (F ) 2 (ŝ, s) ≤ 0 due to the second statement of the Lemma 1 and the equation (3).

Figure 5 :

 5 Figure 5: Expected reward under three static strategies: full information, partial information and no information for N = 2, µ = 0.0998, λ = 0.2542, C 1 = 3, C 2 = 1.1002.

Figure 6 :

 6 Figure 6: Expected reward under three static strategies: full information, partial information and no information for N = 4, µ = 0.1, λ = 0.2547, C 1 = 3, C 2 = 1.1.

Figure 7 :

 7 Figure 7: Expected reward under three static strategies: full information, partial information and no information for N = 10, µ = 0.1001, λ = 0.2541, C 1 = 3, C 2 = 1.0999.

n: 1 ,f 1 f= C 1 + C 2 N n=1 sn: 1 f= C 1 + C 2 N n=1 1 =

 11121121 does not depend on s n+1 , • • • , s N , we can rewrite[START_REF] Lu | Pi: A practical incentive protocol for delay tolerant networks[END_REF] as followsR (k) = C 1 + C 2 p n (s)f S n+1:N |S1:n (s n+1:N |s 1:n )ds N :n+1ds nSn|S1:n-1 (s n |s 1:n-1 )sn-1:S1:n-1 (s 1:n-1 )ds 1:n-1 ds n S1:n (s 1:n )ds 1:n C 1 + N C 2 .

n- 1 .sn

 1 (sn) s1:n-1≤sn s n+1:N p n (s)f S 1:N (s 1:N )ds -n ds n Observe that the joint distribution f S 1:N (s 1:N ) can be eqivalently written as followsf S 1:N (s 1:N ) = (N -1)! fs (s 1 ) • • • fs (s n-1 ) fs (s n+1 ) • • • fs (s N )N fs (s n ) = f S-n (s -n )N fs (s n ). (57)Note that the outer summation in (56) specifies only the ordinal position of the time s n for each member of summation, and thus can be put under the integral by removing the ordinal dependence as follows,R (N ) = C 1 + C 2 m+1:N p m (s)f S-m (s -m )ds -m ds n .(58)Now the sum represents the success probability of the n th relay in the no information setting, namely,p (N ) n (s n ) = N m=1 s1:m-1≤snsm+1:N p m (s)f S-m (s -m )ds -m . (sn) fs (s n )ds n = C 1 + N C 2 .

p 2 (

 2 1 )dy 1 dy 2 .

Note that since the source is not informed when the message reaches the destination, it can still propose the message to a relay even if the message has already been delivered by another relay.

We remind the reader that relay i refers to the ith relay in chronological order of meeting times with the source.

* This work has been partially supported by the European Commission within the framework of the CONGAS project FP7-ICT-2001-8-317672 and PHC-Toubkal Project. Partial results for the model considered in this work have appeared in the Proceedings of WiOpt 2014.

Before going to the proof of the above result, we give some consequences. If the source met the first relay at s 1 ≤ θ 1 , then irrespective of the time instant at which it meets the second relay, it should not give any information to the second relay. On the other hand, if s 1 ≥ θ 1 , then the strategy of the source should be of threshold type: if it meets the second relay before s 1 + ω(s 1 ), then it should give full information, otherwise it should not give any information.

Proof of Theorem 2. First, note that for fixed s 2 , g(s 1 , s 2 ) decreases with s 1 , since in this case p (F ) 2 (s 1 , s 2 ) increases with s 1 (Lemma 1 with equality 3), whereas p (N ) 2 (s) does not depend on s 1 . Thus, the closer s 1 is to s 2 the smaller g(s 1 , s 2 ) is. This also implies that for fixed s 1 , g(s 1 , s 1 + v) will increase with v, for v ≥ 0.

Let us show that g(0, s 2 ) = p

With [START_REF] Perkins | Ad-hoc on-demand distance vector routing[END_REF], and that p (F ) 2 (s 1 , s 2 ) increases with s 1 (Lemma 1 with equality 3), the difference,

where the last inequality follows from the Lemma 2. Now due to the non-negativity of the first difference in (42) the following inequality can be obtained,

The success probability, p (P ) 2 (s 1 , s 2 ), can be represented as

Again, due to the increasing property of p

2 (0, s 2 ). Then, since p (F ) 2 (0, s 2 ) does not depend on s 1 , we obtain, The other case λ ≤ µ is similar with the difference that θ 2 = ∞. For any s 1 there will always be some values of s 2 when the source will not give information to the second relay. The formal result is as follows.

Proposition 9 ( [24]

). For λ ≤ µ, there exist 0 ≤ θ 1 < ∞ such that 1. if 0 ≤ s 1 ≤ θ 1 , then g(s 1 , s 1 + v) ≥ 0, ∀v ≥ 0; The adaptive strategy for λ < µ for the source is illustrated in Figure 4. As a special case, for λ = µ,

where LW is the LambertW function.

Simulation

The simulation has been performed on ONE (Opportunistic Network Environment) simulator [START_REF] Keränen | The one simulator for dtn protocol evaluation[END_REF], which is a discrete event simulator written in Java. This simulator combines mobility modeling, DTN routing and visualization in one package that is easily extensible and provides a rich set of reporting and analyzing modules. We use simulation to compare the performance of the reward mechanism ranging from full information to no information. For this simulation we use the Random Waypoint model which is the most commonly used in where ds N :n+1 is to be read as ds N ds N -1 • • • ds n+1 , and

We now proceed to the analysis of the success probabilities estimated by the relays in each of the three settings.

A.1 Full Information Setting

The success probability of the n th relay in the full information setting can be expressed as

With (49), it yields

A.2 Partial Information Setting

With (49) and (51), we can write the expected reward under the partial information setting as follows

Now, observe that the success probability of the n th relay can be expressed as p (P ) n (s) =

s n-1:1 p (F ) n (s)f S 1:n-1 (s1:n-1)ds1:n-1

s n-1:1

f S 1:n-1 (s1:n-1)ds1