Wireless Network Information Flow: A Deterministic Approach
arXiv:0906.5394 · doi:10.1109/TIT.2011.2110110
Abstract
In a wireless network with a single source and a single destination and an arbitrary number of relay nodes, what is the maximum rate of information flow achievable? We make progress on this long standing problem through a two-step approach. First we propose a deterministic channel model which captures the key wireless properties of signal strength, broadcast and superposition. We obtain an exact characterization of the capacity of a network with nodes connected by such deterministic channels. This result is a natural generalization of the celebrated max-flow min-cut theorem for wired networks. Second, we use the insights obtained from the deterministic analysis to design a new quantize-map-and-forward scheme for Gaussian networks. In this scheme, each relay quantizes the received signal at the noise level and maps it to a random Gaussian codeword for forwarding, and the final destination decodes the source's message based on the received signal. We show that, in contrast to existing schemes, this scheme can achieve the cut-set upper bound to within a gap which is independent of the channel parameters. In the case of the relay channel with a single relay as well as the two-relay Gaussian diamond network, the gap is 1 bit/s/Hz. Moreover, the scheme is universal in the sense that the relays need no knowledge of the values of the channel parameters to (approximately) achieve the rate supportable by the network. We also present extensions of the results to multicast networks, half-duplex networks and ergodic networks.
arXiv commentTo appear in IEEE transactions on Information Theory, Vol 57, No 4, April 2011
References in corpus (8)
- Broadcast Capacity Region of Two-Phase Bidirectional Relaying
- A Deterministic Approach to Wireless Relay Networks
- Joint Physical Layer Coding and Network Coding for Bi-Directional Relaying
- Approximate Capacity of Gaussian Relay Networks
- Wireless Network Information Flow
- Approximate capacity of the two-way relay channel: A deterministic approach
- The Approximate Capacity of the Gaussian N-Relay Diamond Network
- Lossy Source Transmission over the Relay Channel
Cited by in corpus (115)
- Topological Interference Management through Index Coding
- An Algebraic Approach to Physical-Layer Network Coding
- Real Interference Alignment: Exploiting the Potential of Single Antenna Systems
- Optimized Backhaul Compression for Uplink Cloud Radio Access Network
- Capacity Results for Binary Fading Interference Channels with Delayed CSIT
- Network Coding Meets Multimedia: a Review
- Nested Lattice Codes for Gaussian Relay Networks with Interference
- Divide-and-conquer: Approaching the capacity of the two-pair bidirectional Gaussian relay network
- Optimized Uplink Transmission in Multi-Antenna C-RAN with Spatial Compression and Forward
- Expanding the Compute-and-Forward Framework: Unequal Powers, Signal Levels, and Multiple Linear Combinations
- On Achieving Local View Capacity Via Maximal Independent Graph Scheduling
- Random Access: An Information-Theoretic Perspective
- Optimal Achievable Rates for Interference Networks with Random Codes
- Aligned Image Sets under Channel Uncertainty: Settling a Conjecture by Lapidoth, Shamai and Wigger on the Collapse of Degrees of Freedom under Finite Precision CSIT
- On the Capacity of the Half-Duplex Diamond Channel
- Two-way Networks: when Adaptation is Useless
- Bounds on the Capacity of the Relay Channel with Noncausal State at Source
- Two-way Interference Channels
- On Optimal Fronthaul Compression and Decoding Strategies for Uplink Cloud Radio Access Networks
- Slepian-Wolf Coding Over Cooperative Relay Networks
- The finite-dimensional Witsenhausen counterexample
- Gaussian Half-Duplex Relay Networks: improved constant gap and connections with the assignment problem
- Secure Degrees of Freedom of One-hop Wireless Networks with No Eavesdropper CSIT
- Approximate Sum-Capacity of the Y-channel
- Information Networks with in-Block Memory
- Multilevel Coding Schemes for Compute-and-Forward with Flexible Decoding
- DMT of Multi-hop Cooperative Networks - Part II: Half-Duplex Networks with Full-Duplex Performance
- DMT of Multi-hop Cooperative Networks - Part I: Basic Results
- Cooperative Multiplexing in the Multiple Antenna Half Duplex Relay Channel
- Hybrid Coding: An Interface for Joint Source-Channel Coding and Network Communication
- On the Optimality of Simple Schedules for Networks with Multiple Half-Duplex Relays
- On Gaussian Half-Duplex Relay Networks
- When are dynamic relaying strategies necessary in half-duplex wireless networks?
- A digital interface for Gaussian relay and interference networks: Lifting codes from the discrete superposition model
- The Capacity of the Semi-Deterministic Cognitive Interference Channel and its Application to Constant Gap Results for the Gaussian Channel
- Optimal Coding Schemes for the Three-Receiver AWGN Broadcast Channel with Receiver Message Side Information
- Capacity of All Nine Models of Channel Output Feedback for the Two-user Interference Channel
- Using Superposition Codebooks and Partial Decode and Forward in Low SNR Parallel Relay Networks
- Gaussian Interference Channel with Intermittent Feedback
- Three-Way Channels with Multiple Unicast Sessions: Capacity Approximation via Network Transformation
- Efficiently Finding Simple Schedules in Gaussian Half-Duplex Relay Line Networks
- The Capacity of Three-Receiver AWGN Broadcast Channels with Receiver Message Side Information
- Cloud Compute-and-Forward with Relay Cooperation
- Sum-capacity of Interference Channels with a Local View: Impact of Distributed Decisions
- The Approximate Capacity of the Gaussian N-Relay Diamond Network
- Two Birds and One Stone: Gaussian Interference Channel with a Shared Out-of-Band Relay of Limited Rate
- Binary Fading Interference Channel with No CSIT
- Compress-and-Forward Scheme for Relay Networks: Backword Decoding and Connection to Bisubmodular Flows
- Strong Converse Theorems for Classes of Multimessage Multicast Networks: A Rényi Divergence Approach
- The Approximate Capacity Region of the Gaussian Z-Interference Channel with Conferencing Encoders
- Ergodic Fading One-sided Interference Channels without State Information at Transmitters
- Cooperative Relaying at Finite SNR -- Role of Quantize-Map-and-Forward
- Two-Hop Interference Channels: Impact of Linear Schemes
- On Cooperative Multiple Access Channels with Delayed CSI at Transmitters
- Coding and System Design for Quantize-Map-and-Forward Relaying
- The Degrees of Freedom of Compute-and-Forward
- On the Symmetric Feedback Capacity of the K-user Cyclic Z-Interference Channel
- Info-Clustering: A Mathematical Theory for Data Clustering
- On the Capacity Regions of Two-Way Diamond Channels
- Efficient Capacity Computation and Power Optimization for Relay Networks
- Towards an Extremal Network Theory -- Robust GDoF Gain of Transmitter Cooperation over TIN
- On the Symmetric -user Interference Channels with Limited Feedback
- Capacity Bounds for a Class of Interference Relay Channels
- Distributed Interference Cancellation in Multiple Access Channels
- Optimal Capacity Relay Node Placement in a Multi-hop Wireless Network on a Line
- Opportunistic Communications in Fading Multiaccess Relay Channels
- Incremental Relaying for the Gaussian Interference Channel with a Degraded Broadcasting Relay
- Wireless Network Simplification : Beyond Diamond Networks
- On the Optimality of Treating Interference as Noise: Compound Interference Networks
- On Two-Pair Two-Way Relay Channel with an Intermittently Available Relay
- Multicasting correlated multi-source to multi-sink over a network
- On Uplink-Downlink Duality for Cellular IA
- Simultaneous Diagonalization: On the DoF Region of the K-user MIMO Multi-way Relay Channel
- Robust Signaling for Bursty Interference
- The Approximate Capacity of the MIMO Relay Channel
- Interference Mitigation in Large Random Wireless Networks
- Interference Channel with Intermittent Feedback
- A Novel Cooperative Strategy for Wireless Multihop Backhaul Networks
- Capacity Results for Intermittent X-Channels with Delayed Channel State Feedback
- Bounded State Estimation over Finite-State Channels: Relating Topological Entropy and Zero-Error Capacity
- Cut-Set Bound Is Loose for Gaussian Relay Networks
- Approximately achieving Gaussian relay network capacity with lattice codes
- Expansion coding: Achieving the capacity of an AEN channel
- The DoF of Two-way Butterfly Networks
- Achievable Regions for Interference Channels with Generalized and Intermittent Feedback
- ITLinQ: A New Approach for Spectrum Sharing in Device-to-Device Communication Systems
- Rover-to-Orbiter Communication in Mars: Taking Advantage of the Varying Topology
- Partial Decode-Forward Relaying for the Gaussian Two-Hop Relay Network
- Secure Capacity Region for Erasure Broadcast Channels with Feedback
- Low-Complexity Near-Optimal Codes for Gaussian Relay Networks
- Efficient Signal-Time Coding Design and its Application in Wireless Gaussian Relay Networks
- Nonparametric Decentralized Detection and Sparse Sensor Selection via Multi-Sensor Online Kernel Scalar Quantization
- On the Gaussian Interference Channel with Half-Duplex Causal Cognition
- Best Relay Selection in Gaussian Half-Duplex Diamond Networks
- Linear Finite-Field Deterministic Networks With Many Sources and One Destination
- Consistency in the face of change: an adaptive approach to physical layer cooperation
- Regenerative and Adaptive schemes Based on Network Coding for Wireless Relay Network
- Distributed Universally Optimal Strategies for Interference Channels with Partial Message Passing
- Wireless Network Coding with Local Network Views: Coded Layer Scheduling
- Communication Tradeoffs in Wireless Networks
- Secret Writing on Dirty Paper: A Deterministic View
- An Achievable Rate Region for Three-Pair Interference Channels with Noise
- Capacity Regions of Families of Continuous-Time Multi-User Gaussian Channels
- Using Network Coding to Achieve the Capacity of Deterministic Relay Networks with Relay Messages
- Multicommodity Flows and Cuts in Polymatroidal Networks
- Quantized Compute and Forward: A Low-Complexity Architecture for Distributed Antenna Systems
- Role of a Relay in Bursty Multiple Access Channels
- Wireless Network Simplification: the Gaussian N-Relay Diamond Network
- Opportunistic Buffered Decode-Wait-and-Forward (OBDWF) Protocol for Mobile Wireless Relay Networks
- Relay Strategies Based on Cross-Determinism for the Broadcast Relay Channel
- Discrete Signaling and Treating Interference as Noise for the Gaussian Interference Channel
- Can Non-Signaling Assistance Increase the Degrees of Freedom of a Wireless Network?
- Lattice Coding for Downlink Multiuser Transmission
- Diamond Networks with Bursty Traffic: Bounds on the Minimum Energy-Per-Bit
- The Capacity of the Gaussian Cooperative Two-user Multiple Access Channel to within a Constant Gap