On Capacity and Optimal Scheduling for the Half-Duplex Multiple-Relay Channel

Lawrence Ong, Mehul Motani, Sarah J. Johnson

TL;DR

This paper tackles the complex problem of scheduling in half-duplex relay networks, where nodes cannot transmit and receive simultaneously. The authors derive new capacity bounds and prove that the optimal transmission rate depends only on the time allocated to different network states, not their sequence, leading to a greedy algorithm that finds the optimal "schedule" for maximum data throughput.

What Problem Does This Paper Address?

In wireless communications, the "Multiple-Relay Channel" (MRC) describes a scenario where a source sends data to a destination with the help of several intermediate relays. While theoretical models often assume "full-duplex" (nodes can talk and listen at once), most real-world hardware is "half-duplex."

The transition to half-duplex introduces a massive headache: scheduling. If a relay is transmitting, it’s deaf to incoming data. If it’s listening, it isn't helping move data forward. This creates a combinatorial explosion of possible network states. The authors seek to answer: What is the maximum possible data rate (capacity) for these networks, and how should we schedule the relays' transmit/listen modes to achieve it?

Methods

The authors approach the problem through the lens of Information Theory, focusing on two channel models: Discrete Memoryless and Phase-Fading.

  1. Capacity Bounds: They establish an upper bound using a specialized "cut-set bound" for half-duplex networks and a lower bound (achievable rate) based on a Decode-Forward (DF) strategy.
  2. The "Schedule" Concept: They define a schedule as the fraction of time the network spends in each possible transmit/listen state. Crucially, they prove that the achievable rate is a function of these time fractions, but independent of the order in which the states occur.
  3. Maximin Optimization: Finding the best schedule is formulated as a "maximin" problem—maximizing the minimum reception rate across all relays.
  4. Algorithmic Solutions: They propose a general greedy algorithm (Algorithm 1) and then simplify it for specific channel conditions (Algorithms 2 and 3), providing closed-form solutions for certain topologies.

Datasets

As a theoretical information theory paper, no empirical datasets were used. Instead, the authors evaluated their algorithms using:

  • Synthetic Channel Models: Discrete memoryless channels and phase-fading Gaussian channels.
  • Numerical Simulations: A four-node linear network (Source -> Relay 1 -> Relay 2 -> Destination) where coordinates were varied to test different path-loss scenarios.

Key Insights and Ideas

  • Order Doesn't Matter: One of the most practical findings is that you don't need to coordinate a complex sequence of states. As long as the total time allocated to each state is correct, the specific timing doesn't change the achievable rate.
  • The "Front-End" Bottleneck: In phase-fading channels, the overall network rate is always constrained by the "front" of the network—either the first few relays or the entire chain. It is never the "back" relays alone that limit the system.
  • rSNR-Degraded Channels: The authors identify a specific condition called "received Signal-to-Noise Ratio (rSNR) degradation" (where SNR consistently drops as you move further from a transmitter). In these channels, the optimal schedule always balances the rates so that every relay and the destination are simultaneous bottlenecks.
  • The HD vs. FD Gap: Unlike full-duplex (FD) networks, where Decode-Forward can sometimes achieve the theoretical capacity (the cut-set bound), in half-duplex (HD) networks, there is almost always a persistent gap between the achievable DF rate and the upper capacity bound.

Key Results

  • Algorithm Efficiency: The proposed Algorithm 2 reduces the complexity of finding an optimal schedule from searching $(2^{K}-1)$ combinations to at most $K$ combinations (where $K$ is the number of relays).
  • Closed-Form Solutions: For 4-node networks, the authors derived exact formulas for the optimal time fractions ($p_0, p_1, p_2, p_3$) based on channel gains.
  • Performance Comparison: Numerical results show that while adding relays increases the rate in both FD and HD, the HD network suffers significantly more as the number of relays grows because the "listening" requirement consumes a larger portion of the available time resource.

Limitations and Future Work

  • "Full" Decode-Forward: The paper assumes all relays must fully decode the source message. In some scenarios, "Partial" Decode-Forward or "Compress-Forward" (where relays just pass on a quantized version of what they hear) might yield higher rates.
  • Static Topologies: The scheduling assumes fixed node positions. Extending this to mobile nodes or fading channels with shorter coherence times would be a natural next step.
  • Complexity: While Algorithm 3 is efficient, the general maximin problem for very large networks (many relays) still faces a dimensionality challenge as the number of states grows exponentially ($2^{D-2}$). The authors suggest heuristic algorithms for these extreme cases.

Summary updated

Abstract

We study the half-duplex multiple-relay channel (HD-MRC) where every node can either transmit or listen but cannot do both at the same time. We obtain a capacity upper bound based on a max-flow min-cut argument and achievable transmission rates based on the decode-forward (DF) coding strategy, for both the discrete memoryless HD-MRC and the phase-fading HD-MRC. We discover that both the upper bound and the achievable rates are functions of the transmit/listen state (a description of which nodes transmit and which receive). More precisely, they are functions of the time fraction of the different states, which we term a schedule. We formulate the optimal scheduling problem to find an optimal schedule that maximizes the DF rate. The optimal scheduling problem turns out to be a maximin optimization, for which we propose an algorithmic solution. We demonstrate our approach on a four-node multiple-relay channel, obtaining closed-form solutions in certain scenarios. Furthermore, we show that for the received signal-to-noise ratio degraded phase-fading HD-MRC, the optimal scheduling problem can be simplified to a max optimization.
BibTeX
@article{ong2012capacity,
  author = {Lawrence Ong and Mehul Motani and Sarah J. Johnson},
  title = {{On Capacity and Optimal Scheduling for the Half-Duplex Multiple-Relay Channel}},
  journal = {IEEE Trans. Information Theory},
  year = {2012},
  url = {https://openreview.net/forum?id=hJ82c8WAvV},
}

Loading related content...

Figure