Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Tuesday, December 18, 2012 - 9:37:13 AM
Last modification on : Wednesday, December 19, 2012 - 3:25:13 PM
Long-term archiving on: : Tuesday, March 19, 2013 - 3:54:26 AM


Explicit agreement for this submission


  • HAL Id : hal-00766287, version 1



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. ⟨hal-00766287⟩



Record views


Files downloads