Source-linked AI summary
A Deterministic Approach to Wireless Relay Networks
A. S. Avestimehr, S. N. Diggavi, D. N. C. Tse
TL;DR
The paper addresses the difficulty of characterizing capacity in multiuser Gaussian networks by introducing an analytically simpler deterministic model that preserves broadcast and superposition. It exactly characterizes capacity for single-source, single-destination deterministic relay networks and derives Gaussian schemes within 1 bit for the single-relay channel and 2 bits for the Diamond network.
Problem
Most Gaussian network capacity regions are unknown, including the capacity of the simplest single-relay network.
Method
The paper develops a deterministic multiuser channel model and uses capacity-achieving deterministic schemes to construct Gaussian relay-network schemes.
Results
The deterministic single-source, single-destination network achieves its cut-set bound, while Gaussian schemes are within 1 bit for the single-relay channel and 2 bits for the Diamond network.
Takeaways & Limitations
The deterministic model provides exact relay-network capacity characterizations and constant-gap Gaussian approximations for all channel gains in the two examples.
Abstract
from arXiv · showhide
We present a deterministic channel model which captures several key features of multiuser wireless communication. We consider a model for a wireless network with nodes connected by such deterministic channels, and present an exact characterization of the end-to-end capacity when there is a single source and a single destination and an arbitrary number of relay nodes. This result is a natural generalization of the max-flow min-cut theorem for wireline networks. Finally to demonstrate the connections between deterministic model and Gaussian model, we look at two examples: the single-relay channel and the diamond network. We show that in each of these two examples, the capacity-achieving scheme in the corresponding deterministic model naturally suggests a scheme in the Gaussian model that is within 1 bit and 2 bit respectively from cut-set upper bound, for all values of the channel gains. This is the first part of a two-part paper; the sequel [1] will focus on the proof of the max-flow min-cut theorem of a class of deterministic networks of which our model is a special case.
I. INTRODUCTION
Wireless networks are difficult to analyze because broadcast and superposition make links interact, while Gaussian network capacities are often unknown. The paper introduces a deterministic model that retains these wireless features while simplifying analysis under high-SNR and high-dynamic-range conditions.
- Broadcast and superposition make wireless links interact, unlike isolated wireline point-to-point links.
- Gaussian network capacity is unknown for most networks, including the single-relay network.
- The proposed deterministic model is analytically simpler than Gaussian models while capturing broadcast and superposition.
- The model approximates Gaussian behavior when receiver noise is small relative to received signals and received powers span a high dynamic range.
- The paper first motivates the deterministic model through point-to-point, broadcast, and multiple-access examples.
- For arbitrary relay networks with one source and one destination, the deterministic cut-set bound is achievable.
II. A DETERMINISTIC MODEL FOR WIRELESS NETWORKS
The paper introduces a deterministic wireless-network model through three basic channel examples: point-to-point, broadcast, and multiple access. These examples illustrate how the model captures fundamental wireless-channel aspects.
- The deterministic model is introduced for wireless networks through point-to-point, broadcast, and multiple-access channels.
- Each example discusses how the proposed deterministic model captures fundamental aspects of wireless channels.
A. Point-to-Point
The deterministic point-to-point channel represents transmission as signal levels, passing only bits above the noise level. Its capacity tracks the Gaussian channel within one bit.
- The model represents a Gaussian channel as a noiseless truncation pipe for the transmitted signal's most significant bits.
- The deterministic channel passes the first n signal-level bits clearly and discards bits below the noise level.The transmitted signal is represented as a binary vector, with n determined by channel gain.
- The deterministic model focuses on signal levels above noise while omitting background noise from the channel representation.
- n = ⌈log SNR⌉ links the number of reliably received deterministic signal levels to the Gaussian channel's SNR.
- The point-to-point deterministic capacity is a within-one-bit approximation of the AWGN channel capacity.
B. Broadcast Channel (BC):
The deterministic broadcast model assigns each receiver a prefix of the transmitted signal's binary levels according to its received SNR. Its capacity region is within one bit per user of the Gaussian broadcast region.
- The deterministic broadcast channel models Gaussian receivers with ordered received SNRs, SNR2 ≤ SNR1.
- The weak receiver gets the first n2 transmitted bits, while the strong receiver gets the first n1 bits with n1 > n2.
- The receiver-specific bit prefixes represent which signal levels arrive above each user's noise level.
- The deterministic and Gaussian broadcast capacity regions are within one bit per user of each other.
C. Multiple Access Channel (MAC):
The deterministic MAC models signal interaction by truncating below-noise components and replacing same-level real addition with modulo-2 summation. Its capacity region remains within one bit per user of the Gaussian MAC region.
- C. Multiple Access Channel (MAC):: The deterministic MAC and Gaussian MAC regions are compared graphically in Figure 3(b), using dashed and solid boundaries respectively.The cited passage identifies the solid curve as the Gaussian MAC region.
- C. Multiple Access Channel (MAC):: The model separates signal components received clearly above the stronger user's level from components that interact at shared signal levels.The portions above noise level are retained, while below-noise portions are discarded.
- C. Multiple Access Channel (MAC):: The deterministic MAC truncates signal components below the noise level and models same-level interactions using modulo-2 sums over F2.Carry-over between signal levels from real addition is ignored.
- C. Multiple Access Channel (MAC):: The Gaussian and deterministic MAC capacity regions are within one bit per user of each other.The one-bit difference is attributed to the at-most-one-bit increase in cardinality caused by real addition of bounded signals.
D. The Deterministic Model for General Networks
The paper defines a deterministic wireless network over nodes with integer channel gains, finite-field transmitted vectors, and deterministic received signals formed from other nodes’ transmissions.
- D. The Deterministic Model for General Networks: A wireless network G is modeled as a set of N nodes V.The network description introduces the general deterministic model after the basic channel examples.
- D. The Deterministic Model for General Networks: Each directed communication link from node i to node j has a non-negative integer gain n(i,j) modeling the corresponding Gaussian channel gain.The model allows channels with zero gain.
- D. The Deterministic Model for General Networks: At each time t, every node transmits a vector x_i[t] over the finite field F_q.The field size is selected using the maximum link gain q = max_i,j(n(i,j)).
- D. The Deterministic Model for General Networks: Each node receives a deterministic function of the signals transmitted by the other network nodes.The input-output relation is specified for all receiving nodes.
- D. The Deterministic Model for General Networks: The network input-output operations use summation and multiplication in F2 and can be represented pictorially.Figure 4 illustrates an example deterministic wireless network.
E. Related Works
The paper situates its deterministic relay-network model relative to earlier deterministic approaches, including Aref’s model for single-source single-destination relay networks.
- E. Related Works: Aref’s earlier relay-network model proved a capacity result for the single-source single-destination case but captured broadcast without superposition.The paper identifies this as a limitation of that prior model.
- E. Related Works: The paper’s deterministic relay-network framework is illustrated through a pictorial representation in Figure 4.The figure is referenced as an example of the deterministic relay-network model.
III. SINGLE-SOURCE, SINGLE-DESTINATION NETWORK AND ITS CAPACITY
For a deterministic wireless network with one source, one destination, and arbitrary relays, the paper characterizes capacity exactly as the minimum rank across network cuts, generalizing max-flow min-cut.
- The network is studied as a single-source, single-destination information-flow problem.
- A cut partitions the vertices into Ω and Ωc, with the source in Ω and destination in Ωc.
- For each cut, G_Ω,Ωc is the transfer matrix from signals transmitted in Ω to signals received in Ωc.
- The cut-set upper bound can be expressed as the minimum rank of the transfer matrices associated with the cuts.
- Theorem 3.3 states that deterministic-network capacity equals this minimum cut rank, with the minimum taken over all cuts.
- For the Figure 4 example, the capacity is 5, attained by a cut separating {S,A1} from {A2,B1,B2,D}; several other cuts are also tight.
- The result parallels wireline max-flow min-cut, while the sequel proves a broader linear deterministic-network generalization.
IV. CONNECTIONS TO GAUSSIAN RELAY NETWORKS
The paper connects deterministic and Gaussian relay networks by transferring capacity-achieving deterministic schemes to Gaussian networks. The resulting Gaussian rates remain within a channel-gain-independent gap of the cut-set bound.
- The deterministic model supplies capacity-achieving schemes that naturally suggest Gaussian-network schemes.
- The resulting Gaussian rates have gaps from the cut-set upper bound bounded independently of the channel gains.
A. Relay channel to within one bit
For the single-relay Gaussian channel, the deterministic capacity-achieving construction motivates a decode-forward scheme. Its achievable rate is within one bit of the cut-set upper bound for every channel gain configuration.
- Deterministic-to-Gaussian construction: The deterministic relay scheme sends n_SD bits directly, then routes min((n_SR−n_SD)+,(n_RD−n_SD)+) additional bits through non-interfering signal levels.
- Gaussian decode-forward scheme: When |h_SR|<|h_SD|, ignoring the relay achieves R=log(1+|h_SD|^2).
- Gaussian decode-forward scheme: When |h_SR|>|h_SD|, block-Markov encoding yields the decode-forward achievable rate described by the paper.
- Gap to cut-set bound: At most one bit separates the decode-forward achievable rate from the Gaussian relay network’s cut-set upper bound for all channel gains.
- Gap to cut-set bound: The one-bit maximum occurs only when two channel gains are exactly equal, while the average gap is much smaller than one bit.
B. Diamond network to within two bits
The diamond network is modeled deterministically and then mapped to a Gaussian partial-decode-and-forward scheme. The resulting achievable rate is within two bits of the Gaussian cut-set upper bound for all channel gains.
- The diamond Gaussian relay network remains an open capacity problem, so the paper constructs a corresponding deterministic model.The deterministic model is shown alongside the Gaussian network in Figure 6.
- The deterministic diamond capacity equals that of a wireline diamond network and can be achieved by routing over non-interfering links.The wireline network has orthogonal outgoing links at the source and orthogonal incoming links at the destination.
- The Gaussian scheme broadcasts messages m1 and m2, has relay Ai decode mi, and re-encodes both messages for transmission over the relay-to-destination MAC.Achievable rates lie in the intersection of the broadcast-channel and multiple-access-channel capacity regions.
- The deterministic construction motivates a Gaussian partial-decode-and-forward scheme whose achievable rate is compared with the cut-set bound.The analysis defines a rate region R* and bounds it against the Gaussian cut-set upper bound.
- Within two bits, the achievable rate approaches the Gaussian cut-set upper bound for all values of the channel gains.The authors state that the exact constant could potentially be improved, but emphasize a uniform constant-gap characterization of high-SNR behavior.