Capacity of Multiple Unicast in Wireless Networks: A Polymatroidal Approach
Authors:
- 13 August 2014
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 60 (10) , 6303-6328
Abstract
A classical result in undirected wireline networks is the near optimality of routing (flow) for multiple-unicast traffic (multiple sources communicating independent messages to multiple destinations): the min cut upper bound is within a logarithmic factor of the number of sources of the max flow. In this paper, we extend the wireline result to the wireless context. In particular, we show the following meta-theorem: if for a given channel and its reciprocal channel, the cut-set bound is (approximately) achievable, then for multiple-unicast in a bidirected network comprised of such channels, the cut-set bound is (approximately) achievable within a logarithmic factor of the number of sources. The achievable scheme can be viewed as an instantiation of a simple layering principle: local physical-layer schemes combined with global routing. We use the reciprocity of the wireless channel critically in this result. We prove this result formally as a capacity approximation result for a variety of channel models, including general Gaussian networks under fast fading, networks comprised only of broadcast and MAC channels, and networks comprised of broadcast erasure channels with feedback. The capacity approximations we prove tend to have both an additive gap (power loss) and a multiplicative gap (degrees of freedom loss). The key engineering insight is that layered architectures, common in the engineering-design of wireless networks, can have near-optimal performance if the locality over which physical-layer schemes should operate is carefully designed. Feedback is shown to play a critical role in enabling the separation between the physical and the network layers. The main technical contribution is the usage of polymatroidal network as a graphical model for analyzing the performance of complex wireless networks.Keywords
All Related Versions
Funding Information
- National Science Foundation (CCF 1017430, CNS 0721652)
- National Science Foundation (CCF 1017430, CNS 0721652)
- Army Research Office (W911NF-14-1-0220)
This publication has 90 references indexed in Scilit:
- Multiuser Broadcast Erasure Channel With Feedback—Capacity and AlgorithmsIEEE Transactions on Information Theory, 2013
- Aligned Interference Neutralization and the Degrees of Freedom of the 2$\,\times \,$2$\,\times \,$2 Interference ChannelIEEE Transactions on Information Theory, 2012
- The Degrees of Freedom of Wireless NetworksVia Cut-Set IntegralsIEEE Transactions on Information Theory, 2011
- A flow model based on polylinking systemMathematical Programming, 2011
- Broadcast erasure channel with feedback - Capacity and algorithms2009
- On the Degrees-of-Freedom of the K-user Gaussian interference channel2009
- Improved Approximation Algorithms for Minimum Weight Vertex SeparatorsSIAM Journal on Computing, 2008
- On the capacity of information networksIEEE Transactions on Information Theory, 2006
- The capacity of wireless networksIEEE Transactions on Information Theory, 2000
- Polymatroidal flow network models with multiple sinksNetworks, 1988