Publication
We provide a tight approximate characterization of the n-dimensional product multicommodity flow (PMF) region for a wireless network of n nodes. Separate characterizations in terms of the spectral properties of appropriate network graphs are obtained in both an information theoretic sense and for a combinatorial interference model (e.g., Protocol model). These provide an inner approximation to the n2 dimensional capacity region. These results answer the following questions which arise naturally from previous work: (a) What is the significance of 1=pn in the scaling laws for the Protocol interference model obtained by Gupta and Kumar (2000)? (b) Can we obtain a tight approximation to the ?maximum supportable flow? for node distributions more general than the geometric random distribution, traffic models other than randomly chosen source-destination pairs, and under very general assumptions on the channel fading model? We first establish that the random source-destination model is essentially a one-dimensional approximation to the capacity region, and a special case of product multi-commodity flow. For a wireline network (graph), a series of results starting from the result of Leighton and Rao (1988) relate the product multicommodity flow to the spectral (or cut) property of the graph. Building on these results, for a combinatorial interference model given by a network and a conflict graph, we relate the product multicommodity flow to the spectral properties of the underlying graphs resulting in computational upper and lower bounds. These results show that the 1=pn scaling law obtained by Gupta and Kumar for a geometric random network can be explained in terms of the combinatorial properties of a geometric random network and the scaling law of the conductance of a grid graph. For the more interesting random fading model with additive white Gaussian noise (AWGN), we show that the scaling laws for PMF can again be tightly characterized by the spectral properties of appropriately defined graphs. As an implication, we obtain computationally efficient upper and lower bounds on the PMF for any wireless network with a guaranteed approximation factor.