Flow Optimization in Delay Tolerant Networks using Dual Decomposition

Abstract : We study flow optimization in Delay Tolerant Networks (DTNs), which we model using Capacity Region Evolving Graphs (CREGs). CREGs consist of different instances (called replicas) of the network graph in cascade; each replica is associated with a distinct time period (called epoch) and its own Capacity Region. Although CREGs can model any DTN, they are particularly well suited for the study of wireless ones. We define a single-commodity utility maximization problem in a CREG of T replicas that contains as special cases various interesting flow maximization problems. Using dual decomposition, we cast the maximization as a dual problem that can be solved iteratively and where in each iteration a set of T problems, T times smaller than the original, are solved, potentially (if multiple processors are available) in parallel. In addition, we propose two suboptimal utility maximization heuristics that operate on an epoch-by-epoch basis and we discuss a multi-commodity extension to the problem.
Type de document :
Communication dans un congrès
WiOpt'12: Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, May 2012, Paderborn, Germany. pp.444-451, 2012
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00766287
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 18 décembre 2012 - 09:37:13
Dernière modification le : mercredi 19 décembre 2012 - 15:25:13
Document(s) archivé(s) le : mardi 19 mars 2013 - 03:54:26

Fichier

p444-gitzenis.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : hal-00766287, version 1

Collections

Citation

Savvas Gitzenis, George Konidaris, Stavros Toumpis. Flow Optimization in Delay Tolerant Networks using Dual Decomposition. WiOpt'12: Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, May 2012, Paderborn, Germany. pp.444-451, 2012. 〈hal-00766287〉

Partager

Métriques

Consultations de la notice

64

Téléchargements de fichiers

204