Wireless Network Information Flow: A Deterministic Approach

Salman Avestimehr; Suhas Diggavi; David Tse

Source-linked AI summary

Wireless Network Information Flow: A Deterministic Approach

Salman Avestimehr, Suhas Diggavi, David Tse

arXiv:0906.5394v7Jun 30, 2009cs.IT

TL;DR

The paper addresses the limited understanding of information flow in wireless and Gaussian relay networks. It develops deterministic models and uses their insights to analyze Gaussian networks with quantize-map-and-forward, achieving a constant-gap approximation to the cut-set bound. The scheme's gap is independent of SNR and channel values, though the gap grows with network size.

Problem
Capacity remains unknown for most Gaussian networks, while wireless information flow is much less understood than wired network flow.
Method
The paper starts with deterministic models to build insights, then uses them to analyze Gaussian relay networks with quantize-map-and-forward.
Results
The quantize-map-and-forward scheme achieves rates within a constant gap of the cut-set bound, independent of SNR and channel values; the gap is 1 bit/s/Hz for single-relay and two-relay diamond networks.
Takeaways & Limitations
The scheme provides a universal approximation for arbitrary networks without requiring relays to know the channel parameters.
Takeaways & Limitations
The gap grows with the number of nodes because of noise accumulation in quantize-map-and-forward.

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper addresses wireless network capacity by first analyzing a deterministic model that captures signal strength, broadcast, and superposition, then using those insights to develop approximately optimal Gaussian-network schemes. It establishes exact or constant-gap capacity results, including universal quantize-map-and-forward performance and close Gaussian–deterministic approximations for basic channels.

I. INTRODUCTION: Wireless links interact through broadcast and superposition, making network flow substantially less understood than flow over isolated wired links.Signals may reach multiple relays and combine at receivers, creating interference as well as information spread.
I. INTRODUCTION: The paper introduces a deterministic channel model that captures channel strength, broadcast, and superposition while simplifying Gaussian-network analysis.The model focuses on signal interaction rather than noise and is analytically simpler than the Gaussian model.
I. INTRODUCTION: Quantize-map-and-forward lets Gaussian relay networks approach the cut-set upper bound within a channel-parameter-independent additive gap.Each relay quantizes at the noise level and randomly maps the quantized sequence to a Gaussian codeword.
I. INTRODUCTION: The additive gap is 1 bit/s/Hz for both the single-relay network and the two-relay Gaussian diamond network.The stated constant may depend on the number of network nodes, but not on channel values.
I. INTRODUCTION: For linear finite-field deterministic networks, the achievable rate matches the cut-set bound, yielding an exact capacity characterization.The broader deterministic analysis also establishes an achievable rate for arbitrary deterministic channels.
I. INTRODUCTION: The scheme is universal because relays need no channel-gain knowledge, and the deterministic approximations for Gaussian BC and MAC are within one bit per user.The paper also extends the framework to multicast, half-duplex, and fading or frequency-selective relay networks.

D. Linear finite-field deterministic model

The paper defines a linear finite-field deterministic relay model and uses it to analyze relay capacity and assess Gaussian-network approximations. The model is analytically useful, but its correspondence with Gaussian channels can fail for MIMO networks.

Model definition: The deterministic relay network assigns integer link gains and computes each received signal through finite-field operations on transmitted vectors.The field size is assumed to be 2 unless stated otherwise.
Model limitations: For the 2×2 MIMO example, the Gaussian capacity grows with k while the corresponding deterministic capacity remains different, causing the gap to diverge as k increases.The Gaussian model has singular values of order 2^k, whereas the deterministic model has a separate stated capacity expression.
Role in analysis: Despite this limitation, the deterministic model provides useful insights and enables exact relay-network capacity analysis that supports Gaussian-network analysis.Its analytic simplicity is presented as the foundation for the subsequent Gaussian-network results.
Single-relay network: For the single-relay deterministic network, the capacity equals the cut-set bound.The capacity expression selects the direct-link gain when it exceeds the weaker source-relay or relay-destination link; otherwise it selects the minimum relay-side gain.
Single-relay network: A capacity-achieving deterministic strategy keeps the relay silent when the direct link is strongest and otherwise forwards innovations decoded from the source.In the illustrated example, relay forwarding adds 1 bit without overlapping the direct transmission.
Single-relay network: 27 Theorem 3.1 states that decode-forward achieves within 1 bit/s/Hz of the cut-set bound for every single-relay Gaussian channel gain.The stated gap is conservative for many parameter values and reaches its maximum only under a special equality condition among gains.
Single-relay network: The deterministic relay analysis also shows that compress-and-forward and network-coding strategies can achieve the cut-set bound in the corresponding deterministic setting.The network-coding strategy sends sums or linear combinations when the destination receives linearly independent equations.

B. Diamond network

The deterministic diamond network has capacity equal to its cut-set upper bound, while Gaussian strategies can approximate the bound with protocol-dependent guarantees. The analysis also shows why flow mixing is necessary in larger relay networks and motivates quantize-map-and-forward.

Deterministic diamond network: The deterministic diamond network capacity equals its cut-set upper bound.A wired-network routing solution can be mimicked using non-interfering links in the deterministic network.
Gaussian diamond network: 1 bit/s/Hz is the gap achieved by partial-decode-and-forward for the two-relay Gaussian diamond network, for all channel gains.The protocol broadcasts separate messages to the relays, which decode and re-encode them for the multiple-access channel to the destination.
Protocol limitations: Decode-forward cannot achieve the deterministic diamond capacity when all relays must decode the message.In the example, the cut-set upper bound is 3 bits/unit time, while broadcast constraints limit decode-forward to 2 bits/unit time.
Protocol limitations: The decode-forward gap from the Gaussian cut-set upper bound grows as the channel parameter a increases.The corresponding deterministic example has a one-bit gap that translates into an unbounded Gaussian gap.
Protocol limitations: Amplify-forward can be sub-optimal because a relay may transmit amplified noise that corrupts another relay’s signal.In the example, this reduces the achievable rate to 2 bits/channel use and prevents capacity achievement.
Larger relay networks: 5 bits per unit time is achievable in the four-relay deterministic example, matching the destination’s 5-bit input limit.The optimal scheme uses a relay that decodes and forwards a linear combination of source-originated flows; without flow mixing, rates above 3 bits/unit time are impossible.
Quantize-map-and-forward: Quantize-map-and-forward maps noise-level quantized received signals directly to random Gaussian codewords and is universally approximate for arbitrary noisy Gaussian relay networks.The scheme extracts signal bits above the noise level before random mapping for transmission.
Extensions: The deterministic results extend to multicast networks, with achievable multicast rates stated by Theorem 4.2.The extension transmits one message simultaneously from the source to all destinations.

2) Linear finite-field deterministic relay network:

For linear finite-field deterministic relay networks, capacity is characterized by the minimum rank across source–destination cuts, extending max-flow min-cut to arbitrary topologies and multicast.

Capacity characterization: The cut value is the rank of the transfer matrix G_Ω,Ωc associated with each source–destination cut.Independent uniform inputs simultaneously optimize all cuts in the linear finite-field model.
Capacity characterization: Theorem 4.3 gives unicast capacity as the minimum cut rank over all source–destination cuts.The achievable rate approaches this minimum whenever R < minΩ∈ΛD rank(GΩ,Ωc).
Multicast: Theorem 4.4 gives multicast capacity through the corresponding minimum cut ranks to the destinations.The layered-network proof establishes reliability when R is below the minimum over destinations and cuts.
Scope and coding: The results apply to arbitrary network topologies, including networks with cycles, and relay encoding can be restricted to linear functions.The unicast theorem generalizes wired max-flow min-cut, while the multicast theorem generalizes network coding results.
Encoding strategy: The layered-network achievability scheme uses block-based relay mappings and random linear transformations known to the destination.Each relay maps received blocks to transmitted blocks, and the destination decodes using the relay encoding functions.

B. Arbitrary networks (not necessarily layered)

General deterministic relay networks are handled by unfolding the network over time into a layered network, proving the unfolded cut value, and implementing the resulting code across blocks.

Network unfolding: The network is unfolded into K stages so each stage represents one block of the original network’s operation.The unfolded network includes source and destination boundary stages and repeated relay nodes across time.
Network unfolding: Each original relay is represented across stages, with wired memory links of capacity KC connecting consecutive copies.These links model stored information and preserve causal relay processing in the unfolded network.
Implementation: Any unfolded-network rate below C_unf/K is achievable in the original network by using K blocks of length T.The source and relays implement the unfolded encoding across successive blocks, and the destination decodes after K blocks.
Cut analysis: Steady cuts in the unfolded network have value K rank(GΩ,Ωc), linking unfolded cuts to original-network cut ranks.Cuts that violate the required stage monotonicity incur a wired-link contribution of at least KC.
Conclusion: Combining the unfolded achievability result with the cut analysis yields the deterministic-network capacity theorem for arbitrary, unequal-path networks.The proof reduces relevant unfolded cuts to those corresponding to original-network cuts.

VI. GAUSSIAN RELAY NETWORKS

The Gaussian-network analysis translates deterministic-network insights into a constant-gap capacity result, extending the proof from layered to arbitrary networks and from single to multiple antennas.

Motivation: The deterministic model captures some, but not all, high-SNR behavior of Gaussian relay networks and motivates approximate analysis.The Gaussian section uses deterministic proof intuition to obtain approximate rather than exact capacity results.
Proof scope: The Gaussian proof first treats layered networks, then expands arbitrary networks over time and finally extends the result to multiple antennas.The single-antenna case is established before the multiple-antenna generalization.

A. Layered Gaussian relay networks

For layered Gaussian relay networks, a quantize-map-and-forward inner code creates an end-to-end channel whose mutual information is within a constant gap of the cut-set bound, after which an outer code enables reliable transmission.

Coding architecture: The inner code operates over blocks, while an outer code sends many inner-code symbols through the resulting end-to-end channel.The source uses Gaussian codewords, and relays apply random mappings to quantized received blocks.
Quantization and mapping: Each relay quantizes its received complex signal componentwise to the nearest integers, corresponding to scalar quantization at the noise level.The quantization maps a complex number to a pair of integer-valued real and imaginary components.
Quantization and mapping: Each relay maps its quantized received vector independently to a random i.i.d. Gaussian codeword for forwarding.The destination decodes using the relay mappings and its quantized received signals.
Analysis: The mutual-information analysis conditions on network noise to obtain a deterministic network, then bounds distinguishability and the noise-forwarding penalty.The penalty term is proportional to the number of relay nodes.
Guarantee: 15|V| is the layered single-antenna gap from the cut-set upper bound, independent of channel gains.All rates satisfying the theorem’s condition are achievable for the layered Gaussian network.

4) Vector quantization and network operation:

The Gaussian relay operation quantizes each received sequence at the noise level, randomly maps it to a transmit codeword, and decodes at the destination. The construction extends through layered-network arguments to constant-gap unicast and multicast guarantees.

Vector quantization and network operation: Each relay quantizes its received sequence at noise-level distortion and randomly maps the quantized sequence to a transmit sequence.The mapping is uniform over a Gaussian transmission codebook; successful quantization requires a rate exceeding I(Y_i; Ŷ_i).
Vector quantization and network operation: The destination can decode using either maximum-likelihood or typicality decoding.
General Gaussian relay networks: Layering unfolds the network over K stages, replacing finite-field links with orthogonal Gaussian links and implementing the strategy over K blocks.The resulting layered network has |V| nodes per intermediate stage, while the original network achieves the corresponding rate after block expansion.
General Gaussian relay networks: 15(K|V|+2) bounds the unfolded network’s additive gap before block expansion.Letting K approach infinity completes the constant-gap achievability proof for the original Gaussian network.
Multicast extension: For multicast, applying the same relay strategy lets every destination decode when the message rate is below the multicast cut-set bound minus a constant smaller than 15|V|.

VII. CONNECTIONS BETWEEN MODELS

The paper connects Gaussian relay networks to a truncated deterministic model and extends constant-gap guarantees to compound, frequency-selective, and half-duplex settings. These extensions preserve channel-parameter-independent approximation, with gaps scaling according to network dimensions and frequency bands.

Connections between models: The truncated deterministic model approximates Gaussian relay-network capacity within a constant gap by quantizing relay and destination outputs.Theorem 7.1 formalizes the relationship between the Gaussian capacity and the corresponding truncated deterministic capacity.
Compound relay network: The compound-network scheme requires no channel information at the relays, and its gap does not depend on channel-gain values.The compound capacity is achievable within a constant bounded by 13 Σ_i(N_i+3M_i).
Compound relay network: 16|V| bounds the gap when the destination has only quantized channel gains and a universal decoder is used.Quantizing channel gains at the noise level incurs at most the stated additional loss under the described assumptions.
Frequency selective Gaussian relay network: Frequency-selective channels are treated as MIMO links with separate frequency bands, yielding a gap bounded by 12F Σ_i M_i.The result applies to a network with F different frequency bands.
Half duplex relay network: Half-duplex operation is converted into a frequency-selective network by assigning each mode a separate frequency band according to its optimized time fraction.For two relays, the four half-duplex modes can be combined in this way.
Half duplex relay network: The half-duplex capacity is within a constant gap bounded by 12 Σ_i M_i of its cut-set upper bound.

D. Quasi-static fading relay network (underspread regime)

The paper extends its relay-network approximation to fading regimes, distinguishing fast fading, where ergodic capacity is relevant, from slow fading, where outage probability is the relevant measure. The same channel-oblivious relaying strategy supports constant-gap statements in both settings.

Quasi-static fading relay network: Fast fading permits coding across coherence periods, making ergodic capacity the relevant measure.
Quasi-static fading relay network: The quasi-static fast-fading ergodic capacity is within a constant gap bounded by 12 Σ_i M_i of the cut-set bound.The expectation is taken over the channel-gain distribution.
Quasi-static fading relay network: Slow fading prevents interleaving across coherence periods, so performance is characterized through outage probability and ε-outage capacity.The source is assumed not to have channel-gain information.
Quasi-static fading relay network: The slow-fading outage probability is approximated using the compound-network result, with a constant gap bounded by 12 Σ_i M_i.The upper-bound argument uses the condition that rates below the channel-dependent cut-set value minus the gap avoid outage.
Low-rate approximation: At low data rates, the paper motivates a universal multiplicative approximation because a constant additive gap may no longer be useful.The multiplicative factor is independent of channel gains and is lower bounded by 1/[2d(d+1)].
Low-rate approximation: The low-rate multiplicative guarantee is obtained by orthogonalizing links through time division and applying a wired-network max-flow argument.

APPENDIX A PROOF OF THEOREM 3.1

The appendix compares achievable relay strategies with cut-set bounds for single-relay and two-relay diamond networks. It shows that partial decode-forward can approach the cut-set bound within one bit under the analyzed cases.

Single-relay network: If the source-destination link is stronger than the source-relay link, ignoring the relay achieves R = log(1 + |h_SD|^2).
Single-relay network: When the source-relay link is stronger, decode-forward provides an achievable rate based on the source-relay, relay-destination, and direct links.
Single-relay network: The resulting single-relay achievable rate is compared directly with the Gaussian relay-network cut-set upper bound.
Two-relay diamond network: The diamond-network proof assumes an ordering of source-to-relay gains and divides the analysis into two possible cases.
Two-relay diamond network: 1 bit separates the partial decode-forward achievable rate from the two-relay diamond network’s cut-set bound.

APPENDIX C PROOF OF THEOREMS 4.1 AND 4.2

The appendix establishes the layered-network coding proof using block mappings, typicality, and independently randomized relay encoders. Error probability vanishes when the transmission rate is below the minimum cut conditional entropy.

Encoding scheme: The source maps each message independently to a sequence uniformly drawn from the typical transmit set.Messages contain 2^(TR) possibilities and are encoded over T transmission times.
Encoding scheme: Each relay maps a typical received sequence from one T-symbol block to a typical transmit sequence in the next block.The mapping is chosen uniformly at random and independently across relays.
Error analysis: The proof analyzes message-confusion events through typicality and the independence induced by relay mappings.The layered Markov structure reduces the relevant probabilities to conditional-entropy expressions.
Error analysis: R < min over cuts of H(y_Ωc|x_Ωc) makes the error probability arbitrarily small.This follows after combining the confusion-event bounds for the example cut.

C. Proof of Theorems 4.1 and 4.2 for layered networks

The layered-network proof decomposes distinguishability across layers and uses the network's Markov structure to connect these events to cut conditional entropies. The same argument extends to multicast and non-layered deterministic networks.

Layered-network decomposition: The proof follows the linear deterministic analysis while replacing linear transfer matrices with general deterministic transfer functions.For a cut, the transfer function decomposes into disjoint components associated with the network layers.
Layered-network decomposition: The received signals in each receiving layer are deterministic functions of transmitting nodes one layer earlier, including nodes outside the cut.This dependence reflects the layered network structure.
Layered-network decomposition: L_l records whether nodes in layer l can distinguish two messages, while R_l records whether they cannot.These events organize the induction across successive layers.
Capacity proof: The Markovian layered structure converts the sum of layerwise conditional entropies into H(y_Ωc|x_Ωc).Independent relay mappings induce the needed independence between transmitted signals.
Extensions: The multicast extension uses a union bound over receivers, while the non-layered extension follows the corresponding linear-model argument.An alternate non-layered proof uses entropy submodularity.

APPENDIX F PROOF OF LEMMA 6.6

The appendix bounds the loss from using independent equal-power Gaussian inputs instead of optimal covariance allocation in the MIMO channels induced by network cuts. The bound is then applied to the Gaussian-network cut-set expression.

MIMO cut analysis: The cut value C_Ω equals the capacity of the MIMO channel induced by cut Ω.The proof compares optimal water-filling allocation with equal power at transmitting antennas.
MIMO cut analysis: Water filling achieves the MIMO capacity, whereas equal power allocation provides a tractable restricted input distribution.The comparison uses the singular values of the channel matrix.
MIMO cut analysis: At most m/e + min{m,n} bits are lost by restricting an m × n MIMO channel to equal transmit powers.The bound follows from the arithmetic mean-geometric mean inequality.
Application to networks: The Gaussian-network cut-set maximization can be restricted to jointly Gaussian inputs with covariance matrices satisfying individual power constraints.With i.i.d. unit-variance Gaussian inputs, the relevant conditional mutual information reduces to the cut transfer channel.
Application to networks: The scalar specialization yields the claimed constant-gap bound for Lemma 6.6.The result is obtained by applying the equal-power comparison to each cut.

APPENDIX G PROOF OF LEMMA 7.2

The appendix proves MIMO mutual-information comparison lemmas by quantizing channel outputs and bounding the information lost through quantization and bounded perturbations. These lemmas support the stated network approximation result.

Quantized-output comparison: Lemma G.1 compares mutual information for a MIMO channel with continuous output Gx+z and quantized output [Gx].The proof relates the two quantities through conditional mutual information and entropy bounds.
Quantization bound: Lemma G.2 is obtained as a corollary of the two preceding comparison lemmas.The appendix explicitly identifies this corollary relationship.
Quantized-output comparison: The construction introduces ˆy as the quantized channel output and ˜y as ˆy plus an independent bounded perturbation.The perturbation has independent complex components uniform on [0,1] in both real and imaginary parts.
Quantized-output comparison: Data processing gives I(x;y) ≥ I(x;ˆy) ≥ I(x;˜y).This ordering allows the continuous-output channel to be compared with the perturbed quantized representation.
Quantization bound: Each quantized output component differs from its unquantized value by a bounded fractional term.The real and imaginary parts of the fractional component are each bounded in magnitude by 1/2.