Optimal Routes and Flows in Congestion Constrained Ad Hoc Networks

D. O'Neill, D. Julian and S. Boyd

Submitted to Infocom 2004.

Future ad hoc and multi-hop networks will simultaneously support many different types of traffic such as streaming video, voice, and data. This is particularly true for emerging 802.11, bluetooth, or other wireless technologies expected to support ubiquitous internet access. Supporting different traffic types requires the network to find the best set of routes from sources to sinks, individual link data rates and individual link transmitter powers, all subject to QoS constraints. In this paper we present an analysis based on Perron Frobenius theory, which yields Pareto optimal values for these system variables and offers a new view of system capacity and cost in terms of the associated eigenvalues. Performance metrics can be utility functions or other protocol performance measures. A simple method of solution, the DSM algorithm, is presented. The DSM is iterative and adaptive, responding to changes in the wireless environment by automatically seeking a new set of optimal system variables.