Jointly Optimal Channel and Power Assignment for Dual-Hop Multi-channel Multi-user Relaying

Mahdi Hajiaghayi, Min Dong, Ben LiangIEEE JSAC 2011 · DOI · OpenReview

Abstract

We consider the problem of jointly optimizing channel pairing, channel-user assignment, and power allocation, to maximize the weighted sum-rate, in a single-relay cooperative system with multiple channels and multiple users. Common relaying strategies are considered, and transmission power constraints are imposed on both individual transmitters and the aggregate over all transmitters. The joint optimization problem naturally leads to a mixed-integer program. Despite the general expectation that such problems are intractable, we construct an efficient algorithm to find an optimal solution, which incurs computational complexity that is polynomial in the number of channels and the number of users. We further demonstrate through numerical experiments that the jointly optimal solution can significantly improve system performance over its suboptimal alternatives.

Introduction

In modern wireless communication standards such as LTE and Wi-Fi, relays play a pivotal role in extending network coverage and enhancing data rates. When these systems utilize Orthogonal Frequency Division Multiplexing (OFDM), resource allocation becomes a complex multi-dimensional challenge. Specifically, three critical decisions must be made simultaneously: channel pairing (mapping incoming relay channels to outgoing ones), channel-user assignment (allocating specific channel pairs to users), and power allocation (distributing power across the source and relay).

Traditionally, these problems are treated independently because their joint formulation results in a mixed-integer program—a mathematical structure typically considered NP-hard and computationally intractable. This paper challenges that convention by presenting a polynomial-time algorithm that achieves joint optimality, outperforming standard heuristic approaches by significant margins.

System Architecture and Problem Definition

The study focuses on a single-relay cooperative system serving $K$ users over $N$ channels. The transmission occurs in two hops: from the Source to the Relay (Hop 1), and from the Relay to the Users (Hop 2). Additionally, direct links between the Source and Users are considered to maximize diversity gains.

System model of a dual-hop multi-channel multi-user relaying network illustrating channel pairing at the relay.

As illustrated in Figure 1, the relay acts as a central switch. The "Channel Pairing" problem involves determining which subcarrier index in the first hop should be coupled with which index in the second hop. This is represented by the dashed lines within the Relay block. Simultaneously, the system must decide which user receives which paired channel and how much power is allocated to each link to maximize the weighted sum-rate under aggregate and individual power constraints.

Methodology

The authors overcome the inherent complexity of the mixed-integer program through several key mathematical innovations:

1. Convex Reformulation and Relaxation

By utilizing the "perspective" of concave functions, the authors transform the non-convex rate equations into a convex form. They then apply a continuous relaxation to the binary assignment constraints (allowing values between 0 and 1). While relaxation often leads to non-physical fractional assignments, the authors provide a rigorous proof via Lemma 1 that an optimal binary solution always exists for this specific problem structure.

2. Dual Domain Decomposition

Solving the problem in the Lagrange dual domain allows for decomposition. The complex joint problem is reduced to a two-dimensional assignment problem. This sub-problem can be solved efficiently using the Hungarian Algorithm, while user selection is handled on a per-pair basis.

3. The DCDM Algorithm

The proposed Divide-and-Conquer Dual Minimization (DCDM) algorithm ensures convergence to the global optimum. The computational complexity is shown to be $O(N^4)$, where $N$ is the number of channels. This polynomial complexity is a breakthrough, demonstrating that optimal resource allocation is feasible for real-time systems rather than just a theoretical benchmark.

Key Insights and Results

The research yields several critical insights into the behavior of relay networks:

  • The "Binary Miracle": The most significant finding is that the joint problem, which appears to be a 3D assignment problem (typically NP-hard), can be reduced to a 2D assignment because there are no per-user resource constraints. This preserves the binary nature of the solution even after relaxation.
  • Performance Gains: Numerical simulations using Rayleigh fading channels and OFDMA network setups show that the jointly optimal solution provides up to a 20% increase in weighted sum-rate compared to "Separate Optimization" (where pairing and assignment are decoupled from power allocation).
  • Coupling Effects: The benefit of channel pairing is highly dependent on geometry. If the relay is positioned near the source, pairing is critical. If the relay is closer to the users, the first hop becomes the bottleneck, and the relative gains of pairing decrease.
  • Multi-user Diversity: The algorithm effectively exploits multi-user diversity; as the number of users ($K$) increases, the performance gap between the optimal solution and suboptimal heuristics (like "No Pairing" or "Uniform Power Allocation") widens significantly.

Conclusion and Future Work

This work proves that "optimal" does not necessarily mean "computationally impossible." By providing a polynomial-time algorithm for joint resource allocation, the authors offer a path toward more efficient wireless standards.

However, some challenges remain for future exploration. The current model assumes perfect Channel State Information (CSI), which may not be available in high-mobility environments. Furthermore, extending this framework to multi-relay or mesh networks would introduce complex interference patterns that require further algorithmic refinement. While $O(N^4)$ is polynomial, extremely high-speed applications with thousands of subcarriers may still require further optimization or "approximate-but-fast" variants of this optimal framework.

Summary updated

Abstract

We consider the problem of jointly optimizing channel pairing, channel-user assignment, and power allocation, to maximize the weighted sum-rate, in a single-relay cooperative system with multiple channels and multiple users. Common relaying strategies are considered, and transmission power constraints are imposed on both individual transmitters and the aggregate over all transmitters. The joint optimization problem naturally leads to a mixed-integer program. Despite the general expectation that such problems are intractable, we construct an efficient algorithm to find an optimal solution, which incurs computational complexity that is polynomial in the number of channels and the number of users. We further demonstrate through numerical experiments that the jointly optimal solution can significantly improve system performance over its suboptimal alternatives.
BibTeX
@article{hajiaghayi2011jointly,
  author = {Mahdi Hajiaghayi and Min Dong and Ben Liang},
  title = {{Jointly Optimal Channel and Power Assignment for Dual-Hop Multi-channel Multi-user Relaying}},
  journal = {IEEE J. Sel. Areas Commun.},
  year = {2011},
  doi = {10.1109/jsac.2012.121026},
}
Figure