Distributed Sub-gradient Method for Delay Tolerant Networks

In this paper we consider that nodes in a Delay Tolerant Network (DTN) may collaborate to minimize the sum of local objective functions, depending in general on some parameters or actions of all the nodes in the network. If the local objective functions are convex, it can be adopted a recently proposed computation framework, that relies on local sub-gradient methods and consensus algorithms to average each node information. Existing convergence results for this framework can be applied to DTNs only in the case of nodes' synchronous operation and simple mobility models without memory. We address both these issues. First, we prove convergence to the optimal solution for a more general class of mobility processes. Second, we show that, under asynchronous operation, a straight application of the original method would lead to suboptimal solutions and we propose some changes to solve this problem. As a particular case study, we show how the framework can be applied to optimize the dissemination of dynamic content in a DTN.Dans ce rapport, nous considérons que les noeuds dans un réseau tolérant les delais (Delay Tolerant Network, DTN) peuvent collaborer afin de minimiser la somme des fonctions objective locales, qui dépendent en général des paramètres ou des actions de tous les noeuds du réseau. Si les fonctions objectif locales sont convexes, il peut être adopté une méthodologie récemment proposé, qui s'appuie sur le calcul du sous-gradient de la fonction locale et les algorithmes de consensus pour faire la moyenne de l'information de chaque noeud. Les résultats de convergence existants pour cette méthodologie peuvent être appliqués aux DTNs uniquement dans le cas de operation synchrone des noeuds et pour des modèles de mobilité simples, sans mémoire. Nous abordons ces deux questions. Tout d'abord, nous prouvons la convergence de la méthode à la solution optimale pour une classe plus générale des processus de mobilité. Deuxièmement, nous montrons que, dans le cas de opération asynchrone, une application directe de la méthode originale conduit à des solutions sous-optimales et nous proposons quelques modifications pour résoudre ce problème. Comme étude de cas particulier, nous montrons comment le cadre peut être utilisé pour optimiser la diffusion de contenus dynamiques dans un DTN