Capacity of Multiple Unicast in Wireless Networks: A Polymatroidal Approach

DOI10.1109/TIT.2014.2347277zbMATH Open1360.94157arXiv1111.4768MaRDI QIDQ2986104FDOQ2986104

Publication date: 16 May 2017

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

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. Our main result is the approximate optimality of a simple layering principle: {em local physical-layer schemes combined with global routing}. We use the {em reciprocity} of the wireless channel critically in this result. Our formal result is in the context of channel models for which "good" local schemes, that achieve the cut-set bound, exist (such as Gaussian MAC and broadcast channels, broadcast erasure networks, fast fading Gaussian networks). Layered architectures, common in the engineering-design of wireless networks, can have near-optimal performance if the {em 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 key technical idea is the modeling of a wireless network by an undirected "polymatroidal" network, for which we establish a max-flow min-cut approximation theorem.

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

Mathematics Subject Classification ID

Communication theory (94A05) Measures of information, entropy (94A17) Communication networks in operations research (90B18)

Cited In (1)

Constant congestion routing of symmetric demands in planar directed graphs

This page was built for publication: Capacity of Multiple Unicast in Wireless Networks: A Polymatroidal Approach

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