PaperlayerView exact revision on arXiv

Source-linked AI summary

Power and Channel Allocation for Non-orthogonal Multiple Access in 5G Systems: Tractability and Computation

Lei Lei, Di Yuan, Chin Keong Ho, Sumei Sun

arXiv:1603.07576v1cs.IT

TL;DR

The paper addresses how to optimize power and channel allocation in NOMA as 5G capacity requirements rise and shared-resource access complicates allocation. It formulates the problems, analyzes tractability, and uses polynomial-time methods for tractable cases and LDDP for intractable ones. The resulting solutions provide near-optimal performance with bounds and improve throughput and fairness over OMA and an earlier NOMA scheme.

  • Problem

    5G capacity requirements motivate NOMA, but shared-resource access creates power, channel-allocation, interference, fairness, and computational tractability questions.

  • Method

    The paper formulates NOMA allocation problems, characterizes tractable and NP-hard cases, and applies Lagrangian duality with dynamic programming to hard cases.

  • Results

    The proposed solutions deliver near-optimal results with global-optimality bounds and significantly improve throughput and fairness over OMA and existing NOMA schemes.

  • Takeaways & Limitations

    Jointly optimized NOMA allocation can be evaluated systematically across tractable and intractable cases rather than relying only on heuristic allocation schemes.

Abstract

from arXiv · show

Network capacity calls for significant increase for 5G cellular systems. A promising multi-user access scheme, non-orthogonal multiple access (NOMA) with successive interference cancellation (SIC), is currently under consideration. In NOMA, spectrum efficiency is improved by allowing more than one user to simultaneously access the same frequency-time resource and separating multi-user signals by SIC at the receiver. These render resource allocation and optimization in NOMA different from orthogonal multiple access in 4G. In this paper, we provide theoretical insights and algorithmic solutions to jointly optimize power and channel allocation in NOMA. For utility maximization, we mathematically formulate NOMA resource allocation problems. We characterize and analyze the problems' tractability under a range of constraints and utility functions. For tractable cases, we provide polynomial-time solutions for global optimality. For intractable cases, we prove the NP-hardness and propose an algorithmic framework combining Lagrangian duality and dynamic programming (LDDP) to deliver near-optimal solutions. To gauge the performance of the obtained solutions, we also provide optimality bounds on the global optimum. Numerical results demonstrate that the proposed algorithmic solution can significantly improve the system performance in both throughput and fairness over orthogonal multiple access as well as over a previous NOMA resource allocation scheme.

I. INTRODUCTION

5G capacity demands motivate NOMA, which improves spectrum efficiency by multiplexing users on shared resources but introduces interference-management and optimization challenges. The paper formulates joint power and channel allocation, analyzes tractability, and develops near-optimal algorithms with performance bounds.

  • Motivation: 5G network capacity must increase dramatically as mobile data traffic is expected to grow thousand-fold.
  • NOMA motivation: NOMA improves spectrum efficiency by allowing multiple users to share the same frequency-time resource, with SIC eliminating some co-channel interference.
  • Research problem: Unlike OMA, NOMA resource allocation must address intra-cell interference, advanced receiver design, and interference management.
  • Research gap: Existing NOMA studies commonly assume fixed power, predefined user sets, or heuristic parameter tuning, while computational complexity and tractability remain insufficiently studied.
  • Contributions: The paper formulates joint power and channel allocation for WSR and SR utilities, proves NP-hardness in general, and identifies tractable special cases.
  • Contributions: Its LDDP framework combines Lagrangian duality and dynamic programming to produce near-optimal solutions with global-optimality bounds, evaluated for throughput and fairness.

II. SYSTEM MODEL

The system model describes downlink NOMA resource allocation across users and subcarriers, with superposition coding and SIC determining achievable rates. A multiplexing limit M captures receiver-complexity constraints, while WSR and SR provide the optimization utilities.

  • Basic notation: A base station serves K users over N subchannels, with channel gain g_kn and allocated power p_kn for user k on subcarrier n.
  • Basic notation: Users are multiplexed on a subchannel exactly when their allocated power is positive, p_kn > 0.
  • NOMA systems: NOMA uses superposition coding and SIC, allowing receivers to decode selected co-channel signals and treat the remaining interference as noise.
  • NOMA systems: Achievable user rates are determined by SINR after SIC through log(1 + SINR), with noise power denoted by η.
  • Complexity constraint: The maximum multiplexing parameter M limits users per subcarrier because receiver complexity and SIC processing delay increase with the number of decoded signals.
  • Utility functions: The paper evaluates weighted-sum-rate and sum-rate utilities; proportional-fairness weights use each user’s reciprocal average prior rate.

III. JOINT POWER AND CHANNEL ALLOCATION

The joint power and channel allocation problem optimizes user-subcarrier assignment and power under system constraints, but is generally non-linear, non-convex, and NP-hard. The paper therefore separates tractable cases from hard cases and establishes hardness through reduction to OFDMA allocation.

  • Problem formulation: JPCAP jointly determines which users occupy each subcarrier and the power allocated to them while maximizing utility.
  • Constraints: The formulation includes total-power and per-user power limits, a maximum of M multiplexed users per subcarrier, and allocation variables for power and assignment.
  • Complexity: The WSR formulation is non-linear and non-convex because binary assignment variables and products of assignment and power variables appear in the objective.
  • Complexity: W-JPCAP is NP-hard, including the M = 1 case that reduces to OFDMA subcarrier and power allocation.
  • Complexity: For M > 1, a constructed special case is equivalent to an OFDMA problem, establishing hardness for general multi-carrier NOMA allocation.

IV. TRACTABILITY ANALYSIS FOR UNIFORM WEIGHTS

For uniform-weight sum-rate utility, single-carrier NOMA is tractable, whereas multi-carrier resource allocation is NP-hard. The optimal single-carrier allocation serves users consecutively by descending channel gain.

  • SC-NOMA: At the SC-NOMA optimum, a weaker-gain user receives positive power only if every stronger-gain predecessor considered receives positive power.Positive-power users form a consecutive prefix of the descending channel-gain order, with at most M users allocated.
  • SC-NOMA: R-JPCAP for SC-NOMA is polynomial-time solvable.The result follows from a consecutive power-allocation procedure beginning with the strongest-gain user.
  • MC-NOMA: R-JPCAP for MC-NOMA is NP-hard.The hardness proof constructs a dominant user and reduces the remaining allocation to an OFDMA resource-allocation problem.
  • Utility functions: Using SR instead of WSR does not remove JPCAP intractability.The paper contrasts uniform-weight SR with weighted SR, where weights are associated with fairness considerations.

V. TRACTABILITY ANALYSIS FOR RELAXED JPCAP

Relaxing individual-power and user-association constraints yields tractable formulations with strong structural results: SR favors OMA, while weighted SR is convex. The unreleased formulations remain NP-hard under relaxed total-power constraints.

  • Hardness: R-JPCAP and W-JPCAP remain NP-hard even when the total-power constraint is relaxed.The result highlights the importance of other constraints, including individual-power and association restrictions, in computational hardness.
  • P2SR: For relaxed SR, assigning all power to the strongest user is optimal in SC-NOMA.With g1 ≥ g2 ≥ ... ≥ gK, the optimal allocation is p1 = Ptot and p2 = ... = pK = 0.
  • P2SR: For relaxed SR in MC-NOMA, an optimal solution assigns at most one user per subcarrier, making OMA optimal.This follows because reallocating multiplexed users’ combined power to the strongest user improves the sum utility.
  • P2SR: P2SR is convex and tractable for both single-carrier and multi-carrier NOMA.A polynomial-time solution chooses the best-channel user on each subcarrier and then applies water-filling.
  • P2WSR: P2WSR is convex after reformulating the problem in rate variables.Successive substitution expresses power variables through rates, while the resulting sum-exp constraints establish convexity.

VI. OPTIMIZATION ALGORITHM FOR NOMA POWER AND CHANNEL ALLOCATION

Because exact global optimization is not targeted for the complex cases, the paper develops LDDP to produce near-optimal solutions with performance bounds. The framework applies to both R-JPCAP and W-JPCAP.

  • Framework: LDDP progressively improves its optimality bounds by scaling parameters.The framework is intended to gauge solution quality even when exact global optimization is unavailable.
  • Framework: The proposed LDDP framework combines Lagrangian duality and dynamic programming.It is designed to provide near-optimal solutions rather than exact global optima and to deliver optimality bounds.
  • Scope: The algorithm is designed to solve both R-JPCAP and W-JPCAP problems.

A. Lagrangian Duality and Power Discretization

The algorithm relaxes individual power constraints with Lagrange multipliers, discretizes total power, and solves the resulting problem by two-stage dynamic programming. The discretized problem is solved globally in polynomial time, while finer discretization approaches the continuous formulation.

  • Lagrangian duality: Lagrangian relaxation converts individual power constraints into multiplier-based utility penalties, leaving a problem solved for given multipliers.The algorithm then searches for multipliers minimizing the Lagrangian dual.
  • Power discretization: Power discretization divides Ptot into J uniform steps of size δ = Ptot/J.The resulting PLR-D formulation uses discrete power levels pj = δ*j.
  • Two-stage DP: Two-stage dynamic programming first optimizes user power allocation within each subcarrier, then allocates power across subcarriers.The first stage tracks multiplexed users, while the second stage combines subcarrier-level values under the total power budget.
  • Two-stage DP: TSDP obtains the global optimum of PLR-D by accumulating optimal partial solutions.At the end of stage two, zD(λ) is the maximum entry in the second-stage dynamic-programming matrix.
  • Complexity: TSDP solves PLR-D in O(KNMJ^2) time, polynomial in M, N, K, and J.The matrix A1 computation dominates the second-stage O(NJ^2) computation.
  • Approximation: Increasing J improves power granularity and can make the PLR-D solution arbitrarily close to the continuous PLR solution.Discrete power levels also match practical systems that use discrete power control.

C. Algorithmic Framework: Lagrangian Duality With Dynamic Programming

LDDP combines Lagrangian duality with dynamic programming to produce near-optimal NOMA allocations when global optimization is NP-hard, while UB-LDDP supplies performance bounds. The framework includes feasibility conversion, discretized power optimization, and post-processing for a theoretically guaranteed upper bound.

  • LDDP combines Lagrangian duality and dynamic programming to deliver near-optimal solutions when computing the global optimum is NP-hard.N-LDDP provides the near-optimal solution, while UB-LDDP provides an upper bound for evaluation.
  • N-LDDP converts infeasible power allocations into feasible solutions by enforcing individual user limits and reallocating released power.Power is reassigned according to channel gain and weight while respecting user and total-power constraints.
  • UB-LDDP relaxes the total-power constraint with multiplier µ and uses power discretization to construct an objective guaranteed to overestimate the global optimum.The resulting bound is obtained through bisection search and satisfies VUB ≥ z†.
  • The upper bound is theoretically valid because Theorem 11 proves VUB ≥ z†.
  • The overall LDDP complexity is O(CKNMJ2), with each TSDP call having polynomial complexity O(KNMJ2).The feasibility-conversion step has complexity O(KN log2(KN)), while upper-bound computation is performed only once for evaluation.

A. Experimental Setup

The experiments evaluate LDDP against NOMA-FTPC and OFDMA-FTPC using downlink simulations with randomly and uniformly distributed users. They assess utility, convergence, fairness, cell-edge throughput, and user grouping under specified NOMA and OFDMA bandwidth settings.

  • The study generates one hundred instances and evaluates five aspects: SR utility, convergence, WSR utility and fairness, cell-edge throughput, and user grouping.
  • LDDP is compared with NOMA-FTPC and OFDMA-FTPC, using greed-based user grouping followed by FTPC power allocation in the baseline schemes.NOMA-FTPC multiplexes M users per subcarrier, whereas OFDMA-FTPC allocates one user per subcarrier.
  • FTPC allocates more power to users with inferior channel conditions to support fairness.
  • OFDMA-FTPC uses 25 subchannels of 180 kHz across 4.5 MHz, while NOMA-FTPC and LDDP use five subcarriers of 900 kHz each.
  • The simulations treat N-LDDP as a near-optimal lower bound and UB-LDDP as an upper bound for the global optimum.

B. Performance in Throughput and Bounding

N-LDDP improves throughput and fairness over NOMA-FTPC and OFDMA-FTPC, while UB-LDDP bounds its solution quality. Larger power discretization levels tighten the bound interval, and convergence is approached within a few iterations.

  • Throughput and bounding: N-LDDP improves SR utility by around 20% over NOMA-FTPC, while NOMA-FTPC performs much better than OFDMA-FTPC.
  • Throughput and bounding: The average gap between UB-LDDP and N-LDDP is 11%, and the gap variation is insensitive to the number of users.
  • Throughput and bounding: Increasing J progressively tightens the interval between UB-LDDP and N-LDDP because finer power discretization improves solution quality.
  • Convergence: N-LDDP and UB-LDDP approach achievable utility and dual-function values within 10 iterations or fewer, with polynomial-time iterations.
  • Fairness: N-LDDP achieves the best fairness performance, while increasing K degrades fairness across all schemes because competition increases.
  • Fairness: OFDMA-FTPC has the lowest fairness index, and the relative fairness differences are smaller than the plotted appearance suggests because the axis starts above zero.

E. Performance for Cell-edge Users in Throughput

The study evaluates N-LDDP for cell-edge throughput and examines the user-grouping patterns produced by its optimization. N-LDDP improves cell-edge rates over NOMA-FTPC and OFDMA-FTPC, while large channel-gain differences are more likely to be grouped.

  • E. Performance for Cell-edge Users in Throughput: Cell-edge performance is evaluated by dividing the service area into edge and center zones.Each simulation uses twenty-user instances with M = 2, J = 100, 100 time slots, and half the users at the cell edge.
  • E. Performance for Cell-edge Users in Throughput: N-LDDP significantly improves cell-edge user rates compared with the evaluated allocation schemes.The reported average rates of all cell-edge users in N-LDDP are much higher than those in NOMA-FTPC and OFDMA-FTPC.
  • F. Characteristics of User Grouping: User grouping results show that users with large channel-gain differences are more likely to share a subcarrier.The grouping analysis applies N-LDDP to 1,000 realizations with M = 2, J = 100, and K = 20, using differences between descending channel-gain indices.
  • F. Characteristics of User Grouping: Optimal assignment does not necessarily pair users with the best and poorest gains on a subcarrier.This observation motivates treating subcarrier allocation as an optimization variable.
  • VIII. CONCLUSIONS: The paper jointly optimizes NOMA power and channel allocation and analyzes the resulting problems' complexity and optimality.It proposes a framework based on Lagrangian dual optimization and dynamic programming for near-optimal solutions with bounds on the global optimum.
  • VIII. CONCLUSIONS: Numerical results show significant throughput and fairness improvement over existing OFDMA and NOMA schemes.The paper also identifies max-min fairness for one scheduling instance as an extension of the work.
Loading 1603.07576v1…