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

Details

Event IEEE MASS 2008 Conference

Authors

Garcia-Luna-Aceves, J J.
Technical Publications
September 29th 2008
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!

Citation

Karande, S.; Wang, Z.; Sadjadpour, H.; Garcia-Luna-Aceves, J. J. Optimal scaling of multicommodity flows in wireless ad hoc networks: beyond the Gupta-Kumar barrier. 5th IEEE International Conference on Mobile Ad Hoc and Sensor Systems (MASS 2008); 2008 September 29-October 2; Atlanta, Georgia.

Additional information

Focus Areas

Our work is centered around a series of Focus Areas that we believe are the future of science and technology.

FIND OUT MORE
Licensing & Commercialization Opportunities

We’re continually developing new technologies, many of which are available for Commercialization.

FIND OUT MORE
News

PARC scientists and staffers are active members and contributors to the science and technology communities.

FIND OUT MORE