PaperlayerView exact revision on arXiv

Source-linked AI summary

Sub-channel Assignment, Power Allocation and User Scheduling for Non-Orthogonal Multiple Access Networks

Boya Di, Lingyang Song, Yonghui Li

arXiv:1608.08313v1cs.NIcs.IT

TL;DR

The paper studies how to jointly assign sub-channels and allocate power in a downlink NOMA network while maximizing weighted total sum-rate with user fairness. It decouples the NP-hard problem into matching and power-allocation components, then solves them iteratively; the proposed algorithms achieve exchange-stable or globally optimal matching outcomes and outperform OFDMA and a prior NOMA scheme.

  • Problem

    Joint sub-channel and power allocation in a general downlink NOMA system is an NP-hard weighted sum-rate problem involving user fairness.

  • Method

    The paper formulates sub-channel assignment as a many-to-many two-sided matching game with externalities and iteratively combines matching with power allocation.

  • Results

    The proposed algorithms form exchange-stable or globally optimal matchings and outperform OFDMA and a previous resource-allocation scheme in simulations.

  • Takeaways & Limitations

    The approach provides a low-complexity joint resource-allocation solution that balances user fairness with weighted total sum-rate maximization.

Abstract

from arXiv · show

In this paper, we study the resource allocation and user scheduling problem for a downlink nonorthogonal multiple access network where the base station allocates spectrum and power resources to a set of users. We aim to jointly optimize the sub-channel assignment and power allocation to maximize the weighted total sum-rate while taking into account user fairness. We formulate the sub-channel allocation problem as equivalent to a many-to-many two-sided user-subchannel matching game in which the set of users and sub-channels are considered as two sets of players pursuing their own interests. We then propose a matching algorithm which converges to a two-side exchange stable matching after a limited number of iterations. A joint solution is thus provided to solve the sub-channel assignment and power allocation problems iteratively. Simulation results show that the proposed algorithm greatly outperforms the orthogonal multiple access scheme and a previous non-orthogonal multiple access scheme.

I. INTRODUCTION

The paper addresses joint sub-channel assignment and power allocation in downlink NOMA under weighted sum-rate maximization and user-fairness considerations. It formulates assignment as a many-to-many matching game and proposes iterative algorithms whose performance exceeds several baselines.

  • Motivation: NOMA allows multiple users to share each sub-channel, improving spectral efficiency and connectivity but creating inter-user interference.SIC is used at receivers to remove this interference.
  • Problem formulation: Few existing works jointly consider sub-channel and power allocation for a general NOMA system; prior methods often fix power or allocate channels randomly or greedily.The paper identifies the joint problem as coupled because both allocations influence spectral efficiency.
  • Problem formulation: The joint weighted total sum-rate maximization problem with user fairness is non-convex, NP-hard, and complicated by combinatorial allocation and co-channel interference.The formulation targets a downlink network where users may access multiple sub-channels and each sub-channel may serve multiple users.
  • Proposed approach: The proposed solution decouples sub-channel and power allocation, solving them iteratively through a matching game and geometric programming, respectively.Users and sub-channels are treated as two sets of players in a many-to-many matching game with externalities.
  • Proposed approach: USMA-1 forms a two-sided exchange-stable matching after a small number of iterations, while USMA-2 can obtain a global optimal matching with sufficiently many iterations and approach the joint optimum.The paper analyzes stability, convergence, complexity, and optimality.
  • Evaluation: Simulations show better performance than a previous resource-allocation scheme, random allocation, and OFDMA, while considering user fairness.The conclusion characterizes the proposed NOMA approach as balancing fairness with total sum-rate maximization.

II. SYSTEM MODEL

The system is a downlink single-cell NOMA network in which a base station assigns sub-channels and power to users under SIC-based reception. The model includes block fading, CSI-informed allocation, interference among users sharing a sub-channel, and a limit on co-scheduled users to control decoding complexity.

  • A single base station serves mobile users over multiple sub-channels, with users potentially receiving on multiple sub-channels.
  • Inaccurate channel estimation and inevitable frequency offset may degrade NOMA user performance, particularly motivating caution beyond ideal CSI assumptions.
  • The base station uses CSI to assign non-overlapping sub-channel subsets and allocate different power levels to users.
  • Channels follow block fading, remaining constant within a time slot and varying independently across slots; user positions are fixed in the low-mobility assumption.
  • Users sharing a sub-channel create mutual interference and apply SIC, decoding signals in increasing order of channel gains normalized by noise.
  • At most d_f users may share one sub-channel, reducing receiver decoding complexity when d_f ≪ M.

III. PROBLEM FORMULATION

The paper formulates fair resource allocation as weighted total sum-rate maximization over sub-channel assignment and power variables. Because the coupled problem is non-convex and NP-hard, it separates the two decisions and solves them iteratively using geometric programming and matching games.

  • III. PROBLEM FORMULATION: The objective maximizes weighted total sum-rate while incorporating user fairness through per-user weight factors.
  • A. Weighted Sum-rate Maximization Problem Formulation: Matching with geometric programming is presented as one efficient solution method, while optimization theory and coalition formation games are alternative feasible approaches.
  • A. Weighted Sum-rate Maximization Problem Formulation: The decision variables are power allocations p_k,j and binary sub-channel assignment variables b_k,j.
  • A. Weighted Sum-rate Maximization Problem Formulation: Each sub-channel serves at most d_f users, each user occupies at most d_v sub-channels, and power remains bounded by the base station constraints.
  • A. Weighted Sum-rate Maximization Problem Formulation: The formulation is non-convex because of binary assignment constraints and interference in the objective, and its weighted sum-rate maximization is NP-hard.
  • A. Weighted Sum-rate Maximization Problem Formulation: The paper decouples sub-channel and power allocation and updates them iteratively to obtain a joint solution.
  • A. Weighted Sum-rate Maximization Problem Formulation: Given sub-channel assignments, power allocation is formulated as geometric programming, enabling a global optimum through efficient interior-point methods.
  • III. PROBLEM FORMULATION: Given power allocation, sub-channel assignment is formulated as a many-to-many two-sided matching problem solvable with matching games.

B. Geometric Programming for Power Allocation

With sub-channel assignments fixed, the paper converts the SIC-based power allocation problem into geometric programming. It then formulates sub-channel assignment as a constrained many-to-many matching game with externalities.

  • B. Geometric Programming for Power Allocation: After sub-channel allocation is settled, the power allocation problem is rewritten using the assigned sub-channel matrix and user sets.
  • B. Geometric Programming for Power Allocation: Users sharing each sub-channel are reordered according to decreasing channel gains or channel SNRs.
  • B. Geometric Programming for Power Allocation: With SIC decoding, the power allocation problem is converted into a geometric program whose variables include the user rates R_k,j.
  • B. Geometric Programming for Power Allocation: The transformed problem has a linear objective and convex constraints, so it can be solved using interior-point methods.
  • B. Geometric Programming for Power Allocation: The matching model treats users and sub-channels as disjoint sets of selfish, rational players pursuing their own benefits.
  • B. Geometric Programming for Power Allocation: A matching pair consists of a user and sub-channel assigned to each other, and the matching maps users and sub-channels to subsets including the unmatched option.
  • B. Geometric Programming for Power Allocation: The matching is many-to-many: users can match multiple sub-channels and sub-channels can match multiple users, subject to d_f and d_v limits.
  • B. Geometric Programming for Power Allocation: Because players’ preferences depend on other matched players, the game includes externalities, also called peer effects.

2) Preference Lists of the players:

The paper models sub-channel allocation as a many-to-many, two-sided matching game with dynamic preferences and externalities. It introduces swap matching and two-sided exchange stability to handle interdependent user and sub-channel preferences.

  • Preference relations: Users and sub-channels are treated as two sets of players with preference relations over matches in the opposing set.The base station still determines allocations while modeling both sides as selfish and rational players.
  • Preference relations: Each user prefers sub-channels that provide a higher achievable rate, while each sub-channel prefers user groups generating higher rates.These preferences depend on the current matching, producing externalities.
  • Preference relations: Sub-channel preferences are not substitutable, making conventional deferred acceptance and standard fixed-point methods inapplicable.The many-to-many matching problem with externalities is more complex than conventional two-sided matching.
  • Swap matching: The paper introduces switch matching, two-sided exchange stability, and two matching algorithms for the sub-channel allocation problem.These concepts are adapted from matching with externalities to address the allocation setting.
  • Swap matching: A swap exchanges matches between two users while leaving other players’ assignments unchanged, and an approved swap does not decrease either involved player’s rate.At least one involved player’s rate increases under the swap-blocking conditions.
  • Swap matching: Repeated approved swaps continue until no swap-blocking pair remains, producing a two-sided exchange stable matching.Users may be unmatched during a swap, allowing previously unscheduled users to become active.

B. Algorithm Description

The paper proposes USMA-1 and USMA-2 for sub-channel matching, then alternates matching and power allocation in JSPA to obtain a joint resource-allocation solution.

  • USMA-1: USMA-1 initializes a priority-based allocation and repeatedly executes approved swaps until no new swap-blocking pair can be found.User priority increases with its weight when selecting available sub-channels.
  • Matching algorithms: USMA-1 is not guaranteed to find a globally optimal 2ES matching, motivating USMA-2’s global-search procedure.USMA-2 is intended to search for the global optimal matching.
  • JSPA: JSPA initializes equal power allocation and fairness weights inversely proportional to users’ previous average rates.It then iteratively performs sub-channel assignment and power allocation to obtain a joint solution.

C. Stability, Convergence, Complexity and Optimality

The proposed algorithms have convergence and stability guarantees under their stated procedures, while optimality differs between USMA-1 and USMA-2. JSPA is guaranteed to converge because its total sum-rate is nondecreasing and bounded.

  • Stability and convergence: A converged USMA-1 matching is two-sided exchange stable because no user can form a swap-blocking pair to improve utility.The terminal matching is therefore stable under the paper’s exchange criterion.
  • Stability and convergence: USMA-1 converges after a limited number of iterations to a two-sided exchange stable matching.The result follows because approved swaps increase total sum-rate and the number of potential swap-blocking pairs is finite.
  • Stability and convergence: JSPA is guaranteed to converge because matching and power-allocation phases make the total sum-rate nondecreasing and bounded.The sum-rate increases after allocation steps unless the current power allocation already solves the power problem.

2) Complexity:

USMA-1 has a stated polynomial complexity in the number of iterations and matching dimensions, whereas USMA-2 can be extremely expensive. The paper also distinguishes exchange stability from utility optimality.

  • Complexity: USMA-1 has approximate computational complexity O(IMdfdvK), where I is the total iteration count.The number of swap attempts depends on users, sub-channels, and the per-player matching limits.
  • Complexity: The total numbers of USMA-1 and JSPA iterations cannot be expressed in closed form.The stopping iteration depends on when a 2ES matching forms or total sum-rate ceases increasing.
  • Optimality and stability: Not all 2ES matchings obtained by USMA-1 are local maxima of total utility.A swap may be rejected by one user even when another user would benefit substantially.
  • Optimality and stability: Forced swaps increase total utility compared with approved swaps but produce only one-sided exchange stability.This contrasts utility improvement with the stronger stability condition enforced by USMA-1.
  • Complexity: USMA-2 usually has extremely high, approximately exponential-time complexity, so the paper fixes ℓmax in implementation.The fixed iteration limit trades the theoretical large-iteration result for practical computation.

V. SIMULATION RESULTS

The simulations evaluate convergence, spectral efficiency, connectivity, fairness, and the effect of the sharing limit for the proposed JSPA algorithms against OFDMA and other NOMA schemes. JSPA achieves strong performance while exposing a tradeoff between spectral efficiency, fairness, connectivity, and decoding complexity.

  • Convergence: USMA-1 converges with low computational complexity, while JSPA-1 converges within 3–10 iterations depending on operating conditions.For 30 users, USMA-1 requires an average maximum of 70 iterations; JSPA-1 converges within 3–10 iterations.
  • Spectral efficiency: As the user population grows, spectral efficiency and total sum-rate continue increasing but with slower growth because of multiuser diversity.This trend is evaluated using average total sum-rate within 30 slots.
  • Spectral efficiency: JSPA achieves higher spectral efficiency than OFDMA, RA-NOMA, and UG-FTPC, while JSPA-2 improves over JSPA-1 at higher complexity.The proposed allocation provides more freedom than the predefined grouping strategy used by UG-FTPC.
  • User connectivity: NOMA schedules substantially more users than OFDMA when the number of users exceeds the number of sub-channels.OFDMA can access only up to 25 users simultaneously, whereas NOMA scheduling tends toward a fixed value below Kdf but much above OFDMA.
  • User fairness: JSPA provides higher user fairness than the other NOMA schemes and OFDMA, although fairness decreases as the number of users increases.The decrease is attributed to more intense competition among users.
  • Sharing limit: The total sum-rate approaches a stable value as df increases, while df = 1 corresponds to an OMA scheme with lower spectral efficiency.Because SIC complexity grows with df, the paper identifies a tradeoff between spectrum efficiency and decoding complexity.

VI. CONCLUSION

The paper addresses downlink NOMA resource allocation by jointly optimizing sub-channel assignment and power allocation while balancing total sum-rate and user fairness. It uses a low-complexity many-to-many swap-matching formulation, and reports stable matching, performance advantages over OFDMA, and a tunable efficiency–complexity tradeoff.

  • The study targets joint sub-channel assignment and power allocation in a downlink NOMA network while balancing user fairness and total sum-rate.
  • The sub-channel problem is formulated as a many-to-many matching problem with externalities, leading to a low-complexity user-subchannel swap-matching algorithm.
  • The proposed matching process forms a two-sided exchange-stable matching, with analyzed global and local optimality properties.
  • Setting df creates a tradeoff between total sum-rate and decoding complexity because df limits users sharing the same sub-channel.
  • NOMA outperforms traditional OFDMA in both total sum-rate and user fairness.

APPENDIX A

The appendix establishes computational hardness and analyzes special cases of the resource-allocation problem. It shows NP-hardness under equal power or no power allocation, while a relaxed formulation can reduce to OMA allocation.

  • For df > 1, the problem remains NP-hard even when power allocation is not considered.
  • The df = 1 equal-power instance is NP-hard because the corresponding decision problem is NP-complete.
  • In a relaxed problem without constraint (6c), the optimal solution allocates each sub-channel to only one user, yielding an OMA resource allocation.
  • The OMA conclusion does not hold for the general version of problem (6).

APPENDIX C

The appendix explains why the allocation is a many-to-many matching game with externalities and motivates exchange-based stability. Inter-user interference makes preferences depend on the entire set of users sharing each sub-channel.

  • Because users may match multiple sub-channels and each sub-channel may match multiple users, the allocation is a many-to-many matching game.
  • Inter-user interference makes each user’s rate depend on the other users sharing its sub-channel.
  • Sub-channels likewise evaluate user subsets through their power-domain multiplexing relationships, producing externalities.
  • A sub-channel’s preferred user set can change when one member is removed because interference changes the remaining users’ rates.
  • The paper therefore extends switch matching and two-sided exchange stability to the many-to-many setting.
Loading 1608.08313v1…