Primal decomposition and online algorithms for flow optimization in wireless DTNs
Authors:
- 1 December 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 84-90
Abstract
We study flow optimization in wireless Delay Tolerant Networks (DTNs), using Capacity Region Evolving Graphs (CREGs). CREGs comprise cascaded subgraphs which represent the network topology at consecutive time intervals called epochs. The data flows jointly attainable at all wireless links during each time interval are described in terms of a respective capacity region. We associate the sizes of the node buffers at the beginning and end of time with a set of cost and utility functions, and formulate the transport problem of maximizing the sum of the utilities minus the sum of the costs. Then, we present a primal decomposition algorithm for solving this flow optimization problem exactly and efficiently, taking advantage of its special structure. This algorithm unavoidably relies on the knowledge, in advance, of the complete evolution of the network topology at all epochs. As this is a stringent requirement, we devise a heuristic online algorithm that arrives at efficient (but suboptimal) flows at each epoch without looking into future epochs.Keywords
This publication has 11 references indexed in Scilit:
- On the cost/delay tradeoff of wireless delay tolerant geographic routing2012
- Network Capacity Region and Minimum Energy Function for a Delay-Tolerant Mobile Ad Hoc NetworkIEEE/ACM Transactions on Networking, 2011
- Optimal routing and scheduling for deterministic delay tolerant networks2009
- An Introduction to Network Flows over Time2008
- Efficient Routing in Intermittently Connected Mobile Networks: The Single-Copy CaseIEEE/ACM Transactions on Networking, 2008
- Resource Allocation and Cross-Layer Control in Wireless NetworksFoundations and Trends® in Networking, 2006
- MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks2006
- Building a reference combinatorial model for MANETsIEEE Network, 2004
- Routing in a delay tolerant networkACM SIGCOMM Computer Communication Review, 2004
- Convex Optimization2004