Primal decomposition and online algorithms for flow optimization in wireless DTNs

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.