Optimal Joint Subcarrier and Power Allocation in NOMA Is Strongly NP-Hard

Lou Salaün, Chung Shue Chen, Marceau Coupechoux

TL;DR

This paper proves that finding the optimal way to assign radio frequencies (subcarriers) and transmission power to users in 5G's Non-Orthogonal Multiple Access (NOMA) systems is computationally very difficult (strongly NP-hard) for many common performance goals. While this means a perfect solution might be impossible to find quickly, the authors also identify specific scenarios where efficient solutions can be found.

What Problem Does This Paper Address?

The fifth generation (5G) of mobile networks aims for higher data rates, improved spectral efficiency, and massive device connectivity. Non-Orthogonal Multiple Access (NOMA) is a key technology proposed to achieve these goals. Unlike traditional methods (OMA) that divide resources into separate blocks for each user, NOMA allows multiple users to share the same frequency and time resources. This is achieved through power-domain multiplexing, where users are distinguished by their transmission power levels. At the receiver, a technique called Successive Interference Cancellation (SIC) is used to remove interference from stronger signals, allowing weaker signals to be decoded.

A crucial aspect of NOMA is how to best allocate these shared resources. This involves two main decisions:

  1. Subcarrier Allocation: Which frequency bands (subcarriers) should be assigned to which users?
  2. Power Allocation: How much transmission power should each user have on their assigned subcarriers?

Optimizing these decisions is vital for maximizing system performance, often measured by metrics like total data rate (sum-rate), proportional fairness, or max-min fairness. While many studies have proposed algorithms to find good solutions, this paper delves into the fundamental question of computational complexity: how hard is it to find the absolute best (optimal) solution? Specifically, they investigate the complexity of joint subcarrier and power allocation for multi-carrier NOMA (MC-NOMA) systems.

Methods

The core of this paper's contribution lies in its rigorous complexity analysis. The authors employ the technique of pseudo-polynomial reduction from a known NP-hard problem to prove that their NOMA resource allocation problems are also NP-hard.

Here's a breakdown of their approach:

  • Generalizing Objective Functions: They consider a broad class of objective functions called "weighted generalized means of order i < 1." This mathematical framework elegantly encompasses popular metrics like:
  • Sum-rate: The arithmetic mean of individual data rates.
  • Proportional Fairness: The geometric mean of individual data rates.
  • Harmonic Mean: The harmonic mean of individual data rates.
  • Max-Min Fairness: The minimum individual data rate.
  • 3-Dimensional Matching (3DM) as the Source Problem: They use the 3-Dimensional Matching problem (3DM) as their starting point. 3DM is a well-known NP-complete problem, and crucially, it is strongly NP-hard. This means it remains hard even when the numbers involved in the problem are not excessively large.
  • Pseudo-Polynomial Reduction: They construct a mapping (a reduction) from any instance of 3DM to an instance of their NOMA resource allocation problem. This mapping is "pseudo-polynomial" because it preserves the NP-hardness in the strong sense. This means if 3DM is hard to solve, their NOMA problem is also hard to solve.
  • Handling NOMA Specifics: The reduction is carefully designed to account for key NOMA features:
  • Successive Interference Cancellation (SIC): The decoding order at the receiver is modeled.
  • User Multiplexing (M): The constraint that only a limited number of users (M) can be multiplexed on a single subcarrier is incorporated.
  • Power Constraints: Individual user power budgets and subcarrier power limits are considered.
  • Downlink and Uplink: The proofs are shown to apply to both transmission directions.
  • Tractable Cases: After proving the general NP-hardness, they identify specific scenarios where the problem can be solved efficiently (in polynomial time). These include cases with relaxed constraints or simplified system configurations.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity analysis rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Fundamental Hardness of NOMA Optimization: The most significant insight is that optimizing NOMA resource allocation for common fairness and efficiency goals is inherently computationally difficult. This isn't just a matter of finding a better algorithm; it's a fundamental limitation unless P=NP.
  • Unified Framework for Complexity: By using weighted generalized means, the authors provide a unified framework that demonstrates the NP-hardness for a wide range of practical NOMA objective functions, simplifying previous individual proofs.
  • The Power of Reduction: The paper showcases the power of using reductions from established NP-hard problems (like 3DM) to prove the complexity of new problems in a rigorous way.
  • Practical Implications of NP-Hardness: The NP-hardness implies that for large-scale NOMA systems, finding the absolute optimal solution in real-time is likely infeasible. This necessitates the use of heuristic or approximation algorithms in practice.
  • Identifying Tractable Scenarios: The paper is not all doom and gloom. By identifying specific cases where the problem is tractable, it provides valuable guidance for system designers on when efficient optimal solutions are achievable.

Key Results

  • Strong NP-Hardness Proof: The paper formally proves that joint subcarrier and power allocation problems in multi-carrier NOMA systems are strongly NP-hard for objective functions that are weighted generalized means of order $i \leq 1$. This includes sum-rate, proportional fairness, harmonic mean, and max-min fairness.
  • Generalization: This result holds for both downlink and uplink scenarios and for any maximum number of multiplexed users per subcarrier ($M \geq 1$).
  • Tractable Cases Identified: The authors highlight four specific scenarios where the problem can be solved in polynomial time:
  • When the subcarrier allocation is fixed, the sum-rate problem becomes a convex optimization problem.
  • When there's only one user ($K=1$), waterfilling provides the optimal solution.
  • When there's only one subcarrier ($N=1$), a simple sorting-based algorithm works.
  • When individual power constraints are relaxed to a single cellular power constraint, the sum-rate problem is solvable.

Limitations and Future Work

  • Practical Implementation of Optimal Solutions: The NP-hardness implies that finding truly optimal solutions for large, real-world NOMA systems is computationally prohibitive. This paper's findings strongly motivate the development and analysis of efficient heuristic and approximation algorithms.
  • Specific Heuristic Performance: While the paper proves the hardness of finding optimal solutions, it doesn't analyze the performance gap between optimal solutions and existing heuristic algorithms. Future work could focus on quantifying this gap.
  • Dynamic Environments: The current analysis assumes static channel conditions. Future research could explore the complexity of resource allocation in dynamic environments where channel conditions change over time.
  • More Complex NOMA Variants: The paper focuses on a specific model of NOMA. Investigating the complexity of more advanced NOMA schemes (e.g., with imperfect SIC, or different multiplexing strategies) would be valuable.
  • Algorithm Design for Tractable Cases: While tractable cases are identified, the paper could further elaborate on the specific algorithms and their performance characteristics for these scenarios.

Summary updated

Abstract

Non-orthogonal multiple access (NOMA) is a promising radio access technology for 5G. It allows several users to transmit on the same frequency and time resource by performing power-domain multiplexing. At the receiver side, successive interference cancellation (SIC) is applied to mitigate interference among the multiplexed signals. In this way, NOMA can outperform orthogonal multiple access schemes used in conventional cellular networks in terms of spectral efficiency and allows more simultaneous users. This paper investigates the computational complexity of joint subcarrier and power allocation problems in multi-carrier NOMA systems. We prove that these problems are strongly NP-hard for a large class of objective functions, namely the weighted generalized means of the individual data rates. This class covers the popular weighted sum-rate, proportional fairness, harmonic mean and max-min fairness utilities. Our results show that the optimal power and subcarrier allocation cannot be computed in polynomial time in the general case, unless P = NP. Nevertheless, we present some tractable special cases and we show that they can be solved efficiently.
BibTeX
@inproceedings{salaun2018optimal,
  author = {Lou Salaün and Chung Shue Chen and Marceau Coupechoux},
  title = {{Optimal Joint Subcarrier and Power Allocation in NOMA Is Strongly NP-Hard}},
  booktitle = {Université},
  year = {2018},
  doi = {10.1109/icc.2018.8422362},
}
Figure