Optimal scaling of multicommodity flows in wireless ad hoc networks: beyond the Gupta-Kumar barrier

Abstract

We establish a tight max-ow min-cut theorem for multi-commodity routing in random geometric graphs. We show that, as the number of nodes in the network n tends to in-nity, the maximum concurrent ow (MCF) and the minimum cut-capacity scale as (n^2 r^3(n)/k) for a random choice of k (n) source-destination pairs, where r(n) ) is the communication range in the network. We exploit the fact, that the MCF in a random geometric graph equals the interference-free capacity of an ad-hoc network under the protocol model, to derive scaling laws for interference-constrained network capacity. We generalize all existing results reported to date by showing that the per-commodity capacity of the network scales as (1/r(n)k) for the single-packet reception model suggested by Gupta and Kumar, and as (nr(n)/k) for the multiple-packet reception model suggested by others. More importantly, we show that, if the nodes in the network are capable of multiple-packet transmission and reception, then it is feasible to achieve the optimal scaling of (n^2 r^3(n)/k), despite the presence of interference. This result provides an improvement of (nr^2(n) ) over the highest achieved capacity reported to date. In stark contrast to the conventional wisdom that has evolved from the Gupta-Kumar results, our results show that the capacity of ad-hoc networks can actually increase with n while the communication range tends to zero!