View Related Documents

Abstract

We study a natural class of flow problems that occur in the context of wireless networks; the objective is to maximize the flow from a set of sources to one sink node within a given time limit, while satisfying a number of constraints. These restrictions include capacities and transit times for edges; in addition, every node has a bound on the amount of transmission it can perform, due to limited battery energy it carries. We show that this Maximum energy-constrained dynamic flow problem (ECDF) is difficult in various ways: it is NP-hard for arbitrary transit times; a solution using flow paths can have exponential-size growth; a solution using edge flow values may not exist; and finding an integral solution is NP-hard. On the positive side, we show that the problem can be solved polynomially for uniform transit times for a limited time limit; we give an FPTAS for finding a fractional flow; and, most notably, there is a distributed FPTAS that can be run directly on the network.

Fulltext Preview

Image of the first page of the fulltext document