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

Lawrence Ong, Mehul Motani, Sarah J. Johnson

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. We formulate the optimal scheduling problem to find an optimal schedule that maximizes the DF rate and propose an algorithmic solution. We demonstrate our approach on a four-node multiple-relay channel and show that for the received signal-to-noise ratio degraded phase-fading HD-MRC, the optimal scheduling problem can be simplified.

Introduction

In wireless communications, the Multiple-Relay Channel (MRC) describes a scenario where a source sends data to a destination via several intermediate relays. While theoretical models often assume full-duplex (FD) operation—where nodes can talk and listen simultaneously—most real-world hardware is half-duplex (HD).

The transition to half-duplex introduces a significant scheduling challenge: if a relay is transmitting, it cannot receive incoming data, and vice versa. This creates a combinatorial explosion of possible network states. This paper seeks to determine the maximum possible data rate (capacity) for these networks and how to optimally schedule relay modes to achieve it.

System Model and Scheduling

The HD-MRC consists of a source, a destination, and multiple intermediate relays. The network's operation is defined by its "schedule"—the fraction of time spent in each possible transmit/listen state.

System model of a half-duplex multiple-relay channel (HD-MRC) showing source, relays, and destination.

A crucial finding of this research is that the achievable rate is a function of these time fractions but is independent of the order in which the states occur. This allows the scheduling problem to be formulated as a "maximin" optimization, where the goal is to maximize the minimum reception rate across the relay chain to prevent bottlenecks.

Methods and Algorithms

The authors approach the problem using Information Theory, focusing on Discrete Memoryless and Phase-Fading channel models. They establish an upper bound using a specialized cut-set bound and a lower bound (achievable rate) based on a Decode-Forward (DF) strategy.

To find the optimal schedule, they propose a general greedy algorithm. For specific conditions, such as "received Signal-to-Noise Ratio (rSNR) degradation" (where SNR drops consistently with distance), the complexity of finding an optimal schedule is reduced from exponential to linear relative to the number of relays.

Key Insights and Results

Numerical simulations of a four-node network highlight several key properties of HD-MRC:

  • The HD vs. FD Gap: Unlike full-duplex networks, HD networks exhibit a persistent gap between the achievable DF rate and the theoretical capacity upper bound.
  • Front-End Bottlenecks: In phase-fading channels, the overall rate is typically constrained by the "front" of the network (the source and early relays) rather than the destination end.
  • Algorithm Efficiency: The proposed algorithms allow for closed-form solutions in certain scenarios, drastically reducing the computational overhead for network optimization.
Comparison of achievable DF rates (a) and capacity upper bounds (b) for a four-node network as a function of relay positions.

Conclusion

This work provides a theoretical foundation for scheduling in half-duplex relay networks. While the DF strategy provides a strong baseline, future research may explore "Partial" Decode-Forward or "Compress-Forward" techniques to further bridge the gap to the capacity bound. Additionally, extending these static scheduling models to mobile topologies with varying node positions is a natural next step for practical implementation.

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},
}
Figure