Two-Unicast Wireless Networks: Characterizing the Sum Degrees of Freedom

Ilan Shomorony, Amir Salman Avestimehr

Abstract

This paper provides a complete characterization of the "Degrees-of-Freedom" (DoF)—a high-SNR approximation of capacity—for two-unicast multi-hop wireless networks. The authors reveal a surprising "quantization" of network capability: with probability 1, these networks can only achieve a total of 1, 1.5, or 2 sum degrees-of-freedom, depending entirely on specific connectivity patterns in the network graph.

Introduction

In network information theory, single-flow networks (one source to many destinations) are well-understood via the max-flow min-cut theorem. However, multi-hop multi-flow networks—where multiple independent messages traverse a complex web of relays—remain largely unsolved. This research tackles the simplest multi-flow case: two-unicast.

An example of a layered multi-hop wireless network with two source-destination pairs.

In this model, two sources ($s_1, s_2$) send independent messages to two destinations ($d_1, d_2$) through a layered network of relays. The central challenge is managing interference: preventing the signal for $d_1$ from drowning out $d_2$ when they share the same wireless medium over multiple hops.

Methodology

The authors classify networks based on their "Sum DoF" ($D_\Sigma$) using several key techniques:

  1. Condensed Networks: They prove that any complex multi-hop layered network can be "condensed" into a simpler version with at most four layers. This suggests that most relay nodes can simply perform "amplify-and-forward" (acting as simple wires), while only a few "key layers" require sophisticated signal processing.
  2. Two-Mode Operation: To achieve the fractional 1.5 DoF, the authors propose a strategy where nodes alternate between acting as buffers to store signals and using those signals to neutralize interference.
  3. Real Interference Alignment: For cases achieving 2 DoF, the authors employ "real interference alignment," exploiting the properties of irrational numbers to pack multiple signals into the same space at high power levels.
  4. Information-Theoretic Converses: To prove upper bounds, the authors develop new inequalities based on a generalized "Z-channel" structure to identify network bottlenecks.

Key Insights: The 1, 1.5, 2 Rule

The most striking finding is that the sum DoF is discrete rather than continuous. Unless the network is disconnected, it will almost certainly have exactly 1, 1.5, or 2 sum DoF. Beyond just the sum, the authors identify exactly five possible shapes for the entire DoF region, representing the trade-off between User 1's rate and User 2's rate.

The five possible shapes of the Degrees-of-Freedom (DoF) region for two-unicast networks.

These regions are determined by "manageable interference." If a network contains specific subgraphs—like the Butterfly or the Grail—interference can be perfectly canceled or aligned, allowing both users to transmit at their full individual rates (Sum DoF = 2).

Key Results

  • Case A (Sum DoF = 1): Occurs when a single node or edge acts as a "super-bottleneck," forcing both flows to be decodable at a single point.
  • Case B (Sum DoF = 2): Achievable if the network has manageable interference (e.g., two vertex-disjoint paths with specific cancelation properties).
  • Case C (Sum DoF = 1.5): The "default" for networks that aren't severely bottlenecked but lack the perfect symmetry required for full interference cancelation.

Limitations and Future Work

The results rely on a "layered" assumption where signals only move forward. Real-world mesh networks may have complex feedback loops. Additionally, the paper assumes single-antenna nodes and perfect channel state information (CSI). Extending this to three or more unicast pairs introduces exponential combinatorial complexity, which remains an open area for research.

Summary updated

Abstract

We consider two-source two-destination (i.e., two-unicast) multihop wireless networks that have a layered structure with arbitrary connectivity. We show that, if the channel gains are chosen independently according to continuous distributions, then, with probability 1, two-unicast layered Gaussian networks can only have 1, 3/2, or 2 sum degrees of freedom (unless both source–destination pairs are disconnected, in which case no degrees of freedom can be achieved). We provide sufficient and necessary conditions for each case based on network connectivity and a new notion of source–destination paths with manageable interference. Our achievability scheme is based on forwarding the received signals at all nodes, except for a small fraction of them in at most two key layers. Hence, we effectively create a “condensed network” that has at most four layers (including the sources layer and the destinations layer). We design the transmission strategies based on the structure of this condensed network. The converse results are obtained by developing information-theoretic inequalities that capture the structures of the network connectivity. Finally, we extend this result and characterize the full degrees of freedom region of two-unicast layered wireless networks.
BibTeX
@article{shomorony2012two,
  author = {Ilan Shomorony and Amir Salman Avestimehr},
  title = {{Two-Unicast Wireless Networks: Characterizing the Sum Degrees of Freedom}},
  journal = {IEEE Transactions on Information Theory},
  year = {2012},
  doi = {10.1109/tit.2012.2214024},
}
Figure