Source-linked AI summary
Optimal User Scheduling and Power Allocation for Millimeter Wave NOMA Systems
Jingjing Cui, Yuanwei Liu, Zhiguo Ding, Pingzhi Fan, Arumugam Nallanathan
TL;DR
The paper addresses 5G bandwidth shortage and develops optimization procedures for user scheduling and power allocation. The proposed suboptimal algorithm achieves near-optimal performance with low complexity, while mmWave NOMA outperforms conventional mmWave OMA in sum rate.
Problem
5G faces bandwidth shortage amid unprecedented demand for high data rates.
Method
The paper develops optimization procedures using convex upper- and lower-bound functions, matching theory, and a low-complexity scheduling and power-allocation algorithm.
Results
The proposed suboptimal algorithm achieves near-optimal performance with low complexity, and mmWave NOMA outperforms conventional mmWave OMA in sum rate.
Takeaways & Limitations
The results support a performance-complexity trade-off in which the low-complexity approach remains near optimal while mmWave NOMA exceeds conventional mmWave OMA in sum rate.
Abstract
from arXiv · showhide
This paper investigates the application of non-orthogonal multiple access (NOMA) in millimeter wave (mmWave) communications by exploiting beamforming, user scheduling and power allocation. Random beamforming is invoked for reducing the feedback overhead of considered systems. A nonconvex optimization problem for maximizing the sum rate is formulated, which is proved to be NP-hard. The branch and bound (BB) approach is invoked to obtain the optimal power allocation policy, which is proved to converge to a global optimal solution. To elaborate further, low complexity suboptimal approach is developed for striking a good computational complexity-optimality tradeoff, where matching theory and successive convex approximation (SCA) techniques are invoked for tackling the user scheduling and power allocation problems, respectively. Simulation results reveal that: i) the proposed low complexity solution achieves a near-optimal performance; and ii) the proposed mmWave NOMA systems is capable of outperforming conventional mmWave orthogonal multiple access (OMA) systems in terms of sum rate and the number of served users.
I. INTRODUCTION
The paper motivates combining mmWave communication with NOMA to address high-rate and bandwidth demands while exploiting directional, correlated channels and large bandwidths. It positions NOMA as a way to improve spectral efficiency and connectivity under mmWave hardware and propagation constraints.
- mmWave motivation: mmWave communication is motivated by high data-rate demand, bandwidth shortage, and the large bandwidth available in the mmWave spectrum.The band also introduces severe path loss, low penetration, and high attenuation.
- NOMA background: Power-domain NOMA multiplexes users at different power levels and uses SIC to remove intra-channel interference.The approach is described as supporting massive connectivity and diverse QoS requirements.
- mmWave motivation: Directional mmWave transmission creates correlated user channels that are suitable for applying NOMA.Directional beamforming also compensates for mmWave path loss.
- mmWave-NOMA rationale: Large-scale mmWave arrays provide antenna gains and small inter-beam interference, enabling NOMA transmission over each directional beam.The paper presents this combination as a candidate for improving spectral efficiency in 5G networks.
- System constraints: mmWave systems face costly RF hardware and difficult accurate CSI estimation and feedback, motivating hybrid or analog beamforming and reduced-feedback designs.Prior work includes random beamforming and hybrid analog-digital approaches under these constraints.
B. Motivation and Contributions
The paper jointly studies user scheduling and power allocation for mmWave-NOMA with random beamforming and partial CSI feedback. It formulates an NP-hard sum-rate problem, develops global and low-complexity solution methods, and reports near-optimal and OMA-beating performance.
- Framework: The framework uses random beams and requires users to feed back equivalent channel gains rather than complete channel vectors.The BS schedules users on predefined beams and transmits superposed NOMA signals with allocated power.
- Problem formulation: The optimization jointly schedules users and allocates power across beams and users subject to QoS requirements.The stated objective is sum-rate maximization in a downlink mmWave-NOMA system.
- Complexity: The formulated optimization problem is proved to be NP-hard.The paper states that the problem remains NP-hard even when considering only power allocation or only user scheduling.
- Algorithms: A branch-and-bound approach provides a global optimal power-allocation solution, while matching theory and SCA support a lower-complexity joint algorithm.The low-complexity method targets a tradeoff between performance and computational complexity.
- Results: The proposed low-complexity solution achieves near-optimal performance and the mmWave-NOMA framework outperforms conventional mmWave OMA.The reported comparisons concern both proposed algorithms and sum-rate performance.
B. Channel Model
The channel model captures low-rank and spatially correlated mmWave propagation, while random analog beamforming reduces feedback overhead. The resulting NOMA design accounts for beam assignment, SIC ordering, QoS, power, and user-count constraints.
- Channel model: The mmWave channel is modeled geometrically to represent limited scattering, low rank, and spatial correlation.The model includes path loss, path gains, path directions, and antenna array responses.
- Analog beamforming: Random analog beamforming is adopted because hardware cost and power consumption constrain fully digital beamforming.The predefined beam directions reduce the feedback overhead.
- Feedback and scheduling: Users feed back the magnitudes of their equivalent channel gains and corresponding beam indices to enable BS scheduling and power allocation.The BS then uses this information for subsequent resource assignment.
- SIC operation: NOMA receivers use successive interference cancellation in a specified order to remove intra-beam interference.The formulation imposes decoding conditions for users sharing each beam.
- Optimization model: The optimization maximizes sum rate under total-power, QoS, decoding-order, per-beam user-count, and one-beam-per-user constraints.The paper proves NP-hardness even when only power allocation or user scheduling is considered.
IV. GLOBAL OPTIMAL SOLUTIONS
For fixed user scheduling and decoding order, the paper checks feasibility and solves the nonconvex power-allocation problem globally using branch and bound. Exhaustive treatment of discrete variables makes the overall optimal search computationally demanding.
- Global-search structure: The original formulation contains combinational user-scheduling and decoding-order variables together with continuous power-allocation variables.Exhaustive search is presented as a straightforward way to optimize the integer variables.
- Power allocation: For fixed scheduling and decoding order, the paper develops an optimal power-allocation strategy based on branch and bound.The resulting subproblem remains NP-hard and nonconvex.
- Feasibility checking: Feasibility is checked through a convex power-minimization problem subject to the relevant power and QoS constraints.A fixed scheduling and decoding order is rejected when the problem is infeasible or its minimum required power exceeds the BS power budget.
B. Preliminaries for BB Algorithms
The BB preparation transforms the nonconvex power-allocation formulation into a bounded search over box constraints with computable lower and upper bounds.
- The BB procedure transforms the constraint sets into a multidimensional box and constructs bound functions for each box.
- The objective is reformulated over feasible sets and converted into a minimization problem suitable for BB.
- A binary tree iteratively subdivides the initial box into smaller subsets, with lower and upper bounds computed at leaf nodes.
- Feasibility of specified SINR values is tested through a convex problem, which can be solved directly or with an efficiency-oriented algorithm.
- The bound construction uses matrix-based conditions, including the Perron-Frobenius eigenvalue of a nonnegative matrix.
C. Proposed Optimal User Scheduling and Power Allocation Algorithms
The optimal solution uses BB to search scheduling and decoding possibilities while optimizing power allocation, with convergence supported by exhaustive subdivision and tightening bounds.
- The proposed BB algorithm obtains the optimal power allocation and is stated to converge to the global optimal solution.
- The algorithm subdivides boxes along their longest edges, solves the feasibility problem on each subset, and updates lower and upper bounds.
- The stopping criterion is reached when the difference between global upper and lower bounds is at most ǫ.
- The worst-case computational complexity is exponential in the number of variables, while exhaustive scheduling search has complexity O(KM^t).
- For each scheduling combination and decoding order, BB attains the corresponding optimal power allocation.
V. LOW COMPLEXITY SOLUTIONS
The low-complexity approach replaces exhaustive optimization with matching theory for scheduling and SCA for power allocation, producing a convergent but suboptimal solution.
- The proposed low-complexity algorithm targets a suboptimal solution because computing the global solution becomes cumbersome for large problems.
- SCA replaces the nonconvex formulation with successive first-order Taylor lower-bound approximations and convex subproblems.
- The sum rate improves successively across SCA iterations, and the total power constraint bounds the sequence, implying convergence.
- The SCA solution is suboptimal because the formulation uses lower-bound approximations from relaxation and first-order approximation.
B. Many-to-One Matching Algorithm for User Scheduling
User scheduling is modeled as many-to-one matching with externalities, and the paper develops a matching algorithm based on two-sided exchange stability.
- The scheduling problem is formulated as a many-to-one bipartite matching problem with externalities among users.
- Each beam can support multiple users, whereas each user can access at most one beam.
- Positive beam quotas specify how many users each beam can support, and quotas may differ across beams.
- Beam preferences depend on users supported by other beams, and user preferences depend on all beams rather than only the matched beam.
- Because externalities complicate stability, the paper uses two-sided exchange stability to develop the matching algorithm.
2) Designs of many-to-one matching algorithm:
The many-to-one matching design uses swap operations to improve assignments while preserving the interests of corresponding beams, terminating at a two-sided exchange-stable matching.
- A swap operation exchanges the matched beams of two users while leaving other users’ assignments unchanged.
- A swap-blocking pair is a user pair whose exchange can benefit the users without hurting the corresponding beams.
- The scheduling algorithm repeatedly searches for swap-blocking pairs, performs approved swaps, and keeps the current matching otherwise.
- The process stops when no swap-blocking pair remains, yielding a two-sided exchange-stable matching.
- Initialization uses deferred acceptance, with worst-case proposing number KM and at most M2q2 swap operations.
VI. SIMULTION RESULTS
Simulations evaluate convergence and sum-rate performance across algorithms, SNRs, frequencies, user populations, and users sharing each beam. The proposed matching and SCA design provides strong performance while NOMA generally outperforms OMA.
- Convergence evaluation: BB and SCA converge across different SNR values, while BB bounds tighten with iterations and SCA converges faster despite some performance loss.BB is slower because it performs bisection division for each dimension, approaching exhaustive search at small ǫ.
- Sum rate versus SNR: All algorithms’ sum rates increase monotonically with SNR, although inter-beam interference can make the system interference-limited.In the interference-limited regime, increasing SNR does not improve sum rate.
- Algorithm comparisons: Exhaust+BB grows fastest at high complexity, whereas Matching+SCA achieves good sum-rate performance and matches Matching+BB from 0 ∼10 dB.
- NOMA versus OMA: The mmWave NOMA system outperforms conventional mmWave OMA in sum rate, indicating improved spectral efficiency from applying NOMA.
- Scheduling and power allocation: SCA enhances sum rate compared with fixed power allocation, while matching-based scheduling improves performance as user numbers increase by suppressing inter-beam interference.Random scheduling cannot suppress inter-beam interference and may schedule users with poor channel conditions.
- User-population effects: Matching-based scheduling outperforms random scheduling, and its sum-rate increase slows once the total user population becomes large enough for inter-beam interference to approach a constant.
VII. CONCLUSIONS
The paper develops benchmark and low-complexity solutions for joint user scheduling and power allocation in mmWave NOMA systems, then evaluates their performance against conventional mmWave OMA.
- Problem formulation: Random beamforming is used in mmWave NOMA systems, with sum-rate maximization formulated as a mixed integer programming problem.The optimization is divided into user scheduling and power allocation subproblems.
- Benchmark solution: Exhaustive search and branch and bound obtain benchmark solutions for user scheduling and optimal power allocation, despite prohibitive computational complexity.Branch and bound is applied to solve the power allocation problem optimally.
- Low-complexity solution: Matching theory and SCA support a low-complexity suboptimal algorithm that trades computational complexity against performance.Matching theory is used for user scheduling, while SCA is used for power allocation.
- Simulation results: The proposed suboptimal algorithm achieves near-optimal performance with low complexity compared with the global algorithm.
- Simulation results: The sum rate of mmWave NOMA systems outperforms that of conventional mmWave OMA systems.
APPENDIX A: PROOF OF THEOREM 1
The proof establishes NP-hardness of the sum-rate optimization problem by treating the cases qm = 1 and qm > 1 separately, including a reduction to three-dimensional matching.
- Proof strategy: The proof divides the NP-hardness argument into the cases qm = 1 and qm > 1.
- Case qm = 1: When qm = 1, the problem becomes joint power and user scheduling in conventional OMA systems, whose sum-rate maximization is already NP-hard.
- Case qm > 1: When qm > 1, the problem is shown to remain NP-hard even when power allocation is known.
- Reduction: With known power allocation coefficients, the problem is transformed into a three-dimensional matching problem.The constructed instance uses triples drawn from M × K1 × K2 and matching constraints on their elements.
- Conclusion: The constructed decision problem is NP-complete, so the corresponding optimization instance is NP-hard; therefore, the original problem is NP-hard.