Computer Science – Information Theory
Scientific paper
2006-01-05
Computer Science
Information Theory
Revised version of "Capacity-Delay Scaling in Arbitrary Wireless Networks" submitted to the IEEE Transactions on Information T
Scientific paper
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 $n^2$ dimensional capacity region. These results answer the following questions which arise naturally from previous work: (a) What is the significance of $1/\sqrt{n}$ 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. Building on previous 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. 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.
Leveque Olivier
Madan Ritesh
Shah Devavrat
No associations
LandOfFree
Product Multicommodity Flow in Wireless Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Product Multicommodity Flow in Wireless Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Product Multicommodity Flow in Wireless Networks will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-110151