Note publique d'information : Les réseaux tolérants aux retards (DTN) ont été conçus pour fournir un moyen de communication
durable entre terminaux mobiles dans les régions dépourvues d’infrastructure cellulaire.
Dans de tels réseaux, l’ensemble des voisins de chaque nœud change au fil du temps
en raison de la mobilité des nœuds, ce qui entraîne une connectivité intermittente
et des routes instables dans le réseau. Nous analysons la performance d’un système
d’incitation pour les DTN à deux sauts dans lequel une source en arriéré offre une
récompense fixe aux relais pour délivrer un message. Un seul message à la fois est
proposé par la source. Pour un message donné, seul le premier relais à le délivrer
reçoit la récompense correspondant à ce message, induisant ainsi une compétition entre
les relais. Les relais cherchent à maximiser la récompense attendue pour chaque message
alors que l’objectif de la source est de satisfaire une contrainte donnée sur la probabilité
de livraison du message. Nous considérons deux réglages différents : l’un dans lequel
la source indique aux relais pendant combien de temps un message est en circulation,
et l’autre dans lequel la source ne donne pas cette information. Dans le premier paramètre,
nous montrons que la politique optimale d’un relais est de type seuil : il accepte
un message jusqu’à un premier seuil et le conserve jusqu’à ce qu’il atteigne la destination
ou le deuxième seuil. Les formules de calcul des seuils ainsi que de la probabilité
de livraison des messages sont dérivées pour une source d’arriérés. Nous étudions
ensuite la performance asymptotique de ce réglage dans la limite moyenne du champ.
Lorsque le deuxième seuil est infini, nous donnons l’ODE du champ moyen et montrons
que tous les messages ont la même probabilité de réussite. Lorsque le deuxième seuil
est fini, nous ne donnons qu’une approximation ODE car dans ce cas, la dynamique n’est
pas markovienne. Pour le second réglage, nous supposons que la source propose chaque
message pour une période de temps fixe et qu’un relais décide d’accepter un message
selon une politique randomisée lors d’une rencontre avec la source. S’il accepte le
message, un relais le garde jusqu’à ce qu’il atteigne la destina- tion. Nous établissons
dans quelle condition la probabilité d’acceptation des relais est strictement positive
et montrons que, dans cette condition, il existe un équilibre de Nash symétrique unique,
dans lequel aucun relais n’a quelque chose à gagner en changeant unilatéralement sa
probabilité d’acceptation. Des expressions explicites pour la probabilité de livraison
du message et le temps moyen de livraison d’un message à l’équilibre symétrique de
Nash sont dérivées, ainsi qu’une expression de la valeur asymptotique de la livraison
du message. Enfin, nous présentons de nombreux résultats de simulations pour com-
parer les performances de la stratégie de type seuil et de la stratégie ran- domisée,
afin de déterminer dans quelle condition il est rentable pour la source de donner
l’information sur l’âge d’un message aux relais.
Note publique d'information : Delay-Tolerant Networks (DTNs) were designed to provide a sustainable means of communication
between mobile terminals in regions without cellular infrastructure. In such networks,
the set of neighbors of every node changes over time due to the mobility of nodes,
resulting in intermittent connectivity and unstable routes in the network. We analyze
the performance of an incentive scheme for two-hop DTNs in which a backlogged source
pro- poses a fixed reward to the relays to deliver a message. Only one message at
a time is proposed by the source. For a given message, only the first relay to deliver
it gets the reward corresponding to this message thereby inducing a competition between
the relays. The relays seek to maximize the expected reward for each message whereas
the objective of the source is to satisfy a given constraint on the probability of
message delivery. We consider two different settings: one in which the source tells
the relays for how long a message is in circulation, and one in which the source does
not give this information. In the first setting, we show that the optimal policy of
a relay is of thresh- old type: it accepts a message until a first threshold and then
keeps the message until it either meets the destination or reaches the second threshold.
Formulas for computing the thresholds as well as probability of message delivery are
derived for a backlogged source. We then investigate the asymptotic performance of
this setting in the mean field limit. When the second thresh- old in infinite, we
give the mean-field ODE and show that all the messages have the same probability of
successful delivery. When the second threshold is finite we only give an ODE approximation
since in this case the dynamics are not Markovian. For the second setting, we assume
that the source proposes each message for a fixed period of time and that a relay
decides to accept a message accord- ing to a randomized policy upon encounter with
the source. If it accepts the message, a relay keeps it until it reaches the destination.
We establish under which condition the acceptance probability of the relays is strictly
positive and show that, under this condition, there exists a unique symmetric Nash
equilibrium, in which no relay has anything to gain by unilaterally changing its acceptance
probability. Explicit expressions for the probability of message delivery and the
mean time to deliver a message at the symmetric Nash equilibrium are derived, as well
as an expression of the asymptotic value of message delivery. Finally, we present
numerous simulations results to compare performances of the threshold-type strategy
and the randomized strategy, in order to determine under which condition it is profitable
for the source to give the information on the age of a message to the relays
paprika.idref.fr
data.idref.fr
Documentation
