Uniform Multi-commodity Flow in Wireless Networks with Gaussian Fading Channels
Olivier Leveque, Ritesh Madan, Devavrat Shah · 2006
Starting with the seminal work of Gupta and Kumar (2000), there have been many interesting results that give information theoretic outer and inner approximations to the rate region for wireless networks. While these bounds are almost tight for geometric random networks, not much is known about their tightness for arbitrary wireless networks. In contrast, Leighton and Rao (1988) established a powerful result that uniform multi-commodity flow (UMCF) is within a factor of log n of the natural min-cut capacity for any graph (equivalent to a wireline network) of n nodes. Our motivation is to obtain a similar simple and general characterization for UMCF (shown to be equivalent to the characterization for a much wider class of traffic models) for any wireless network. In this paper, we apply and extend known results to obtain such characterization for networks with Gaussian fading channels. For channel state information (CSI) only at the receivers, we establish that UMCF is within a Delta2log n factor of the information theoretic min-cut capacity of a wireless network, where Delta is the max-degree of a sub-graph induced by the underlying wireless network. For deterministic AWGN channels, we show that UMCF is within square root of the min-cut bound for any network