Product Multicommodity Flow in Wireless Networks

DOI10.1109/TIT.2008.917663zbMATH Open1306.94004arXivcs/0601012MaRDI QIDQ3604576FDOQ3604576

Devavrat Shah, Ritesh Madan, Olivier Lévêque

Publication date: 24 February 2009

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: 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/sqrtn$ 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.

Full work available at URL: https://arxiv.org/abs/cs/0601012

Recommendations

• Multicommodity network flow models and algorithms in telecommunications
• Multicommodity flow problems and decomposition in telecommunications networks
• Multicommodity Multicast, Wireless and Fast
• A Polymatroid Flow Model for Network Coded Multicast in Wireless Networks
• Multicommodity Flows in Ring Networks
• Multicommodity flows in tree-like networks
• Wireless Multicast Optimization: A Cross-Layer Approach

zbMATH Keywords

wireless networkscaling lawcapacity regionproduct multicommodity flow (PMF)

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Communication theory (94A05)

Cited In (1)

• Euclidean prize-collecting Steiner forest

This page was built for publication: Product Multicommodity Flow in Wireless Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3604576)