Combinatiorial algorithms for wireless information flow

DOI10.1145/2390176.2390184MaRDI QIDQ2933637zbMATH OpenOpenAlexFDO

Authors J. B. Ebrahimi, Christina Fragouli

Publication date 5 December 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

deterministic networksFord-Fulkerson algorithmunicast connectionwireless networks

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Information theory (general) (94A15)

Abstract: A long-standing open question in information theory is to characterize the unicast capacity of a wireless relay network. The difficulty arises due to the complex signal interactions induced in the network, since the wireless channel inherently broadcasts the signals and there is interference among transmissions. Recently, Avestimehr, Diggavi and Tse proposed a linear deterministic model that takes into account the shared nature of wireless channels, focusing on the signal interactions rather than the background noise. They generalized the min-cut max-flow theorem for graphs to networks of deterministic channels and proved that the capacity can be achieved using information theoretical tools. They showed that the value of the minimum cut is in this case the minimum rank of all the adjacency matrices describing source-destination cuts. In this paper, we develop a polynomial time algorithm that discovers the relay encoding strategy to achieve the min-cut value in linear deterministic (wireless) networks, for the case of a unicast connection. Our algorithm crucially uses a notion of linear independence between channels to calculate the capacity in polynomial time. Moreover, we can achieve the capacity by using very simple one-symbol processing at the intermediate nodes, thereby constructively yielding finite length strategies that achieve the unicast capacity of the linear deterministic (wireless) relay network.

Recommendations

• scientific article; zbMATH DE number 7051224
• Wireless Network Information Flow: A Deterministic Approach
• scientific article; zbMATH DE number 2135146
• Wireless network algorithmics
• Optimization of wireless communication systems using cross-layer information
• Optimal resource allocation for wireless communications: complexity analysis and algorithm design
• Bridging the gap between information theory and wireless networking
• Randomized and deterministic algorithms for network coding problems in wireless networks
• Cooperative Transmission for Wireless Networks Using Mutual-Information Accumulation

Cited in

(5)

• An approximation approach to network information theory
• The multicast capacity of deterministic relay networks with no interference.
• scientific article; zbMATH DE number 7051224 (Why is no real title available?)
• A MAX-Flow/MIN-Cut algorithm for a class of wireless networks
• (Secure) linear network coding multicast

This page was built for publication: Combinatiorial algorithms for wireless information flow

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