Dynamic User Clustering and Power Allocation for Uplink and Downlink Non-Orthogonal Multiple Access (NOMA) Systems

Non-orthogonal multiple access (NOMA) has recently been considered as a key enabling technique for 5G cellular systems. In NOMA, by exploiting the channel gain differences, multiple users are multiplexed into transmission power domain and then non-orthogonally scheduled for transmission on the same spectrum resources. Successive interference cancellation (SIC) is then applied at the receivers to decode the message signals. In this paper, first, we briefly describe the differences in the working principles of uplink and downlink NOMA transmissions in a cellular wireless system. Then, for both uplink and downlink NOMAs, we formulate a sum-throughput maximization problem in a cell such that the user clustering (i.e., grouping users into a single cluster or multiple clusters) and power allocations in NOMA clusters can be optimized under transmission power constraints, minimum rate requirements of the users, and SIC constraints. Due to the combinatorial nature of the formulated mixed integer non-linear programming problem, we solve the problem in two steps, i.e., by first grouping users into clusters and then optimizing their respective power allocations. In particular, we propose a low-complexity sub-optimal user grouping scheme. The proposed scheme exploits the channel gain differences among users in an NOMA cluster and groups them into a single cluster or multiple clusters in order to enhance the sum-throughput of the system. For a given set of NOMA clusters, we then derive the optimal power allocation policy that maximizes the sum-throughput per NOMA cluster and in turn maximizes the overall system throughput. Using Karush-Kuhn-Tucker optimality conditions, closed-form solutions for optimal power allocations are derived for any cluster size, considering both uplink and downlink NOMA systems. Numerical results compare the performances of NOMA and OMA and illustrate the significance of NOMA in various network scenarios.

SECTION I. Introduction

Recently, non-orthogonal multiple access (NOMA) [1] has been considered as a promising technique for fifth generation (5G) and beyond 5G (B5G) cellular networks. The key idea of NOMA is to simultaneously serve multiple users (ideally all active users in a serving cell) over same radio resources at the expense of minimal inter-user interference. NOMA not only allows serving individual users with higher effective bandwidth but also allows scheduling more users than the available resources. In contrast to conventional orthogonal multiple access (OMA), where every user is served on exclusively allocated radio resources, NOMA superposes the message signals of multiple users in power domain by exploiting their respective channel gain differences. Successive interference cancellation (SIC) is then applied at the receivers for multi-user detection and decoding. For example, in downlink NOMA, the base station (BS) schedules different users over same spectrum resources but their respective message signals are transmitted using different power levels. By exploiting the power differences, each user equipment (UE) can apply SIC and in turn decode its desired signal.

A. Existing Research on NOMA

Recently, numerous research activities have been initiated to identify the potential gains of NOMA in both the downlink and uplink transmissions. Here we review the most recent and relevant research studies for uplink and downlink NOMA transmissions.

1) Downlink NOMA

The basic concept of NOMA was exploited in [1]–​[3] for downlink transmissions. The authors in [1]–​[3] proposed power domain user multiplexing at the BSs and SIC-based signal reception at UEs. In [2], the authors discussed various practical challenges of NOMA systems including multi-user power allocation and user scheduling, error propagation in SIC, overall system overhead, user mobility, and the combination of NOMA with Multiple-Input Multiple-Output (MIMO) transmission. System-level and link-level simulations in [3] indicated clear benefits of NOMA over OMA in terms of overall system throughput as well as individual users’ throughputs. In [6], closed-form expressions for ergodic sum-rate and outage probability were derived for two-user NOMA systems considering static power allocation.

The impact of user pairing was studied in [7] for a two-user NOMA system. The authors proposed fixed and opportunistic user pairing schemes by statically allocating transmission powers among NOMA users. On the other hand, the impact of power allocation on the fairness of downlink NOMA was investigated in [8], considering perfect channel state information (CSI) feedback as well as average CSI feedback. In [9], a cooperative NOMA system was studied, where the authors advocated the idea of pairing users with weak channel gains with those with strong channel gains for cooperative data transmission. A test-bed for a two-user NOMA system was presented in [4]. The experiments were performed by setting 5.4 MHz bandwidth for NOMA users. The results were compared with those for a two-user OMA system where each user has a transmission bandwidth of 2.7 MHz [4]. The results showed significance of NOMA over OMA in terms of aggregate as well as individual users’ throughputs.

2) Uplink NOMA

For uplink transmissions, NOMA was first investigated in [10] where power control was applied at UE transmitter and minimum mean squared error (MMSE)-based SIC decoding was utilized at BS receiver. A joint subcarrier and power allocation problem was studied in [11]. Specifically, a sub-optimal solution was designed to maximize the sum-rate of a NOMA cluster. Closed-form expressions for sum-throughput and outage probability were derived for a two-user uplink NOMA system in [12] assuming static powers for different users. The authors in [12] also compared their results with those for a TDMA-based OMA system and concluded that without proper selection of target data rate for each NOMA user, a user can always be in outage. This conclusion was also drawn in [6] for downlink NOMA. Apart from these works, a robust user scheduling algorithm for uplink NOMA with SC-FDMA was designed in [13], where the distinct channel gains of different users were exploited to obtain efficient user grouping.

B. Motivation and Contributions

For both uplink and downlink NOMA systems, efficient user clustering and power allocation among users are the most fundamental design issues. To date, most of the research investigations have been conducted either for downlink or for uplink scenario considering two users in the system with fixed power allocations. In particular, there is no comprehensive investigation to precisely analyze the differences in uplink and downlink NOMA systems and their respective impact on the user grouping and power allocation problems. In this context, this paper focuses on developing efficient user clustering and power allocation solutions for multi-user uplink and downlink NOMA systems. The contributions of this paper are outlined as follows:

• We briefly review and describe the differences in the working principles of uplink and downlink NOMA.

• For both uplink and downlink NOMA, we formulate a cell-throughput maximization problem such that user grouping and power allocations in NOMA cluster(s) can be optimized under transmission power constraints, minimum rate requirements of the users, and SIC constraints.

• Due to the combinatorial nature of the formulated mixed integer non-linear programming (MINLP) problem, we propose a low-complexity sub-optimal user grouping scheme. The proposed scheme exploits the channel gain differences among users in a NOMA cluster and groups them either into a single cluster or multiple clusters to enhance the sum-throughput of the uplink and downlink NOMA systems.

• For a given set of NOMA clusters, we derive optimal power allocation that maximizes the sum-throughput of all users in a cluster and in turn maximizes the overall system throughput. Using KKT optimality conditions, for both uplink and downlink NOMA, we derive closed-form optimal power allocations for any cluster size.

• We evaluate the performances of different uplink and downlink NOMA systems using the proposed user grouping and power allocation solutions. Numerical results compare the performances of NOMA and OMA and illustrate the significance of NOMA in various network scenarios. Important guidelines related to the selection of key design factors for NOMA systems are obtained.

C. Paper Organization

The rest of the paper is organized as follows: Section II discusses the fundamentals of downlink and uplink NOMA systems. Section III presents the system model, assumptions, and the joint problem formulation for optimal user clustering and power allocation in NOMA systems. Section IV and Section V, respectively, discuss the proposed sub-optimal user clustering solution and the optimal power allocation solutions for uplink and downlink NOMA systems. Section VI evaluates the performances of the proposed solutions numerically and Section VII concludes the article.

SECTION II. Fundamentals of Downlink and Uplink NOMA

In this section, we discuss the basic concepts of downlink and uplink NOMA considering $m$ users with distinct channel gains in a cluster. The power domain multiplexing is applied to superpose multiple signals, whereas an SIC mechanism is applied at the receiver(s) to decode the superposed signals.

A. Downlink NOMA

Let us consider a general $m$ -user downlink NOMA system, where all users experience distinct channel gains. In $m$ -user downlink NOMA, a single transmitter (i.e., BS) non-orthogonally transmits $m$ different signals over the same radio resources, whereas all $m$ receivers (i.e., UEs) receive their desired signals along with the interferences caused by the messages of other UEs. To obtain the desired signal, each SIC receiver first decodes the dominant¹ interferences and then subtracts them from the superposed signal. Therefore, the received signal strengths of the interference signals need to be sufficiently higher in comparison to the desired signal in order to cancel them by SIC processing at the receiver end. Since each UE receives all signals (desired and interfering signals) over the same radio spectrum (i.e., channel), multiplexing of different signals with different power levels is crucial to diversify each signal and to perform SIC at a given UE receiver.

In downlink NOMA, the messages of high channel gain users are transmitted with low power levels whereas the messages of low channel gain users are transmitted with high power levels. As such, at a given receiver, the strong interfering signals are mainly due to the information of low channel gain users. The weakest channel user (who receives low interferences due to relatively low powers of the messages of high channel gain users) cannot suppress any interferences. However, the highest channel gain user (who receives strong interferences due to relatively high powers of the messages of low channel gain users) can suppress all interfering signals.

Illustration: Fig. 1 illustrates a 3-user downlink NOMA system where $h_{1}$ , $h_{2}$ , and $h_{3}$ are the channel gains of $UE_{1}$ , $UE_{2}$ , and $UE_{3}$ , respectively. Also, it is assumed that $x_{1}$ , $x_{2}$ , and $x_{3}$ are the desired messages of $UE_{1}$ , $UE_{2}$ , and $UE_{3}$ , respectively, while $w_{1}$ , $w_{2}$ , and $w_{3}$ denote the respective additive white Gaussian noise (AWGN). If $h_{1}>h_{2}>h_{3}$ , then $UE_{1}$ can perform SIC to cancel interference from both $UE_{2}$ and $UE_{3}$ , whereas $UE_{2}$ can only cancel interference from $UE_{3}$ . Also, $UE_{3}$ experiences interference from both $UE_{1}$ and $UE_{2}$ , but cannot cancel any of them. Therefore, the achievable throughput for $UE_{i}, \,\forall \,i=1,2,3$ , in a 3-user downlink NOMA cluster can be expressed as \begin{equation} \hat R_{i} = \omega B \log _{2}\left({1+\frac {P_{i} \gamma _{i}}{\sum \limits _{j = 1}^{i-1} P_{j}\gamma _{i}+\omega }}\right),\quad \forall \,i=1,2,3, \end{equation} where $\gamma _{i}=\frac {h_{i}}{N_{0}B}$ is the normalized channel gain with $N_{0}$ being the noise power spectral density, $\omega $ is the number of radio channels (e.g., resource blocks in an LTE/LTE-A system) assigned for the cluster, $B$ is the transmission bandwidth of each channel (e.g., resource block).

FIGURE 1.

Illustration of a 3-user downlink NOMA cluster with SIC at the UEs.

To perform SIC, transmission power for each NOMA user needs to be selected properly. If $P_{1}$ , $P_{2}$ , and $P_{3}$ are the transmission powers for $UE_{1}$ , $UE_{2}$ , and $UE_{3}$ , respectively, then the power allocations need to satisfy the following conditions for efficient SIC at $UE_{1}$ receiver:\begin{align} P_{3}\gamma _{1} - (P_{1}+P_{2})\gamma _{1}\geq&P_{tol}, \\ P_{2}\gamma _{1} - P_{1}\gamma _{1}\geq&P_{tol}, \quad \enspace \end{align} where $P_{1} + P_{2} + P_{3} \leq P_{t}$ , $P_{t}$ is the downlink power budget for this 3-user NOMA cluster, and $P_{tol}$ is the minimum power difference required to distinguish between the signal to be decoded and the remaining non-decoded message signals. (2) and (3) represent the power allocation conditions to cancel interference from $UE_{3}$ and $UE_{2}$ , respectively, at $UE_{1}$ receiver.

From (2) and (3), it is evident that, the transmit power for any user must be greater than the sum transmit power for all users with relatively stronger channel gains. That is, the transmit power for $UE_{3}$ must be greater than the sum transmit power for $UE_{1}$ and $UE_{2}$ , while the transmit power for $UE_{2}$ needs to be greater the transmit power for $UE_{1}$ . Subsequently, the power allocation condition to cancel the interference from $UE_{3}$ to the $UE_{2}$ receiver can be given as \begin{equation} P_{3}\gamma _{2} - (P_{1}+P_{2})\gamma _{2} \geq P_{tol}. \end{equation} Note that, since $\gamma _{1} > \gamma _{2}$ , (2) is automatically satisfied if (4) holds. Therefore, the necessary power constraints for efficient SIC in a 3-user cluster can be given by (3) and (4).

Based on the above illustration, the necessary power constraints for efficient SIC in an $m$ -user NOMA cluster can be expressed as follows:\begin{equation} P_{i}\gamma _{i-1} - \sum \limits _{j = 1}^{i-1}P_{j}\gamma _{i-1} \geq P_{tol}, \, i = 2,3,\cdots ,m. \end{equation} Consequently, an important conclusion about the transmit power for the highest channel gain user in a NOMA cluster can be drawn as given in the following lemma.

Lemma 1 (Maximum Transmit Power for the Highest Channel Gain User in a Downlink NOMA Cluster):

The maximum transmission power allocation to the highest channel gain user in the downlink NOMA cluster must be smaller than $\frac {P_{t}}{2^{m-1}}$ , where $m$ is the number of users in the cluster and $P_{t}$ is the total transmission power budget for the given NOMA cluster.

Proof:

The proof follows by induction. Let us consider a 2-user downlink NOMA cluster where $\gamma _{1}$ and $\gamma _{2}$ are the normalized channel gains of the high and low channel gain users, respectively. As per the SIC constraints in (3), we have \begin{equation*} P_{2}\gamma _{1} - P_{1}\gamma _{1} \geq P_{tol}, \quad \text {and} \quad P_{1}+P_{2} \leq P_{t}, \end{equation*} where $P_{1}$ and $P_{2}$ are the allocated powers for high and low channel gain users, respectively. The maximum allocated power to the highest channel gain user can thus be derived as \begin{equation*} P_{1(max)} \leq \frac {P_{t}-\delta }{2}, \end{equation*} where $\delta =\frac {P_{tol}}{\gamma _{1}}$ is the minimum power difference required for SIC. Note that the value of $\delta $ can be very small when the value of $\gamma _{1}$ is very high, which is usually the case. Similarly, for a 3-user downlink NOMA cluster, the maximum allocated transmit powers for the second higher and the highest channel gain user can be expressed, respectively, as \begin{align*} P_{2(max)}\leq&\frac {P_{t} - \delta }{2}, \\ P_{1(max)}\leq&\frac {P_{t} -\delta }{2^{2}}-\frac {\delta }{2}. \end{align*} Consequently, for an $m$ -user cluster, we have \begin{equation*} P_{1(max)} \leq \frac {P_{t}-\delta }{2^{m-1}}-\frac {\delta }{2^{m-2}}-\cdots - -\frac {\delta }{2} \approx \frac {P_{t}}{2^{m-1}}. \end{equation*} This is the result given in Lemma 1.

B. Uplink NOMA

The operation of uplink NOMA is quite different from that of downlink NOMA. In uplink NOMA, multiple transmitters (i.e., UEs) non-orthogonally transmit to a single receiver (i.e., BS) on the same radio spectrum (i.e., channel). Each UE independently transmits its own signal at either maximum transmit power or controlled transmit power. All received signals at the BS are the desired signals, although they cause interference to each other. Since the transmitters are different, each received signal at the SIC receiver (i.e., the BS) experiences a distinct channel gain. Note that, to apply SIC and decode signals at the BS, we need to maintain the distinctness among various message signals. As such, conventional transmit power control (typically intended to equalize the received signal powers for all users) is not feasible in NOMA systems.

Let us consider a general $m$ -user uplink NOMA system in which $m$ users transmit to a common BS over the same radio channel, at either maximum transmit power or controlled transmit power. The BS receives the superposed message signal of $m$ different users and applies SIC to decode each signal. Since the received signal from the highest channel gain user is likely the strongest at the BS, this signal is decoded first. Consequently, the highest channel gain user experiences interference from all other users in the cluster. Then, the signal for the second highest channel gain user is decoded and so on. As a result, the highest channel gain user experiences interference from all users and the lowest channel gain user effectively enjoys interference-free transmission.

Illustration: Fig. 2 illustrates a 3-user uplink NOMA cluster in which $UE_{1}$ , $UE_{2}$ , and $UE_{3}$ experience channel gains of $h_{1}$ , $h_{2}$ , and $h_{3}$ , respectively, where $h_{1}>h_{2}>h_{3}$ . In uplink NOMA, the user’s signal with the highest channel gain is decoded first at the BS. Thus, the achievable data rate of $UE_{1}$ depends on the interferences from $UE_{2}$ and $UE_{3}$ , whereas $UE_{3}$ achieves an intra-cell interference-free data rate. The data rate of $UE_{2}$ depends on the interference from $UE_{3}$ . Consequently, the achievable data rate (or throughput) for $UE_{i}, \,\forall \,i=1,2,3$ , in a 3-user uplink NOMA cluster can be expressed as \begin{equation} \hat R_{i} = \omega B \log _{2}\left({1+\frac {P_{i} \gamma _{i}}{\sum \limits _{j = i+1}^{3} P_{j}\gamma _{j}+\omega }}\right),\quad \forall \,i=1,2,3, \end{equation} where $\gamma , \omega $ , and $B$ are defined similarly as in downlink NOMA. If $P_{1}$ , $P_{2}$ , and $P_{3}$ are the transmission powers of $UE_{1}$ , $UE_{2}$ , and $UE_{3}$ , respectively, then the following conditions need to be satisfied for efficient SIC at the BS, i.e., \begin{align} P_{1}\gamma _{1} - P_{2}\gamma _{2} - P_{3}\gamma _{3}\geq P_{tol}, \\ P_{2}\gamma _{2} - P_{3}\gamma _{3}\geq P_{tol}, \qquad \enspace \end{align} where $P_{i}\leq P^\prime _{t}, \, \forall \, i$ and $P^\prime _{t}$ is the maximum transmit power budget of each UE. (7) and (8) represent the necessary conditions for efficient decoding of $UE_{1}$ and $UE_{2}$ signals, respectively, prior to decoding the signal of $UE_{3}$ .

FIGURE 2.

Illustration of a 3-user uplink NOMA cluster with SIC at the BS.

Based on the above example, the necessary power constraints for efficient SIC in an $m$ -user uplink NOMA cluster can be expressed as follows:\begin{equation} P_{i} \gamma _{i} - \sum \limits _{j=i+1}^{m}P_{j}\gamma _{j} \geq P_{tol}, \, i=1,2,\cdots ,(m-1). \end{equation}

SECTION III. System Model and Problem Formulation

A. Network Model and Assumptions

We consider a macro BS serving $N$ uniformly distributed UEs for uplink as well as downlink. The BS and each of the UEs use a single antenna configuration. The available system bandwidth $B_{T}$ is divided into frequency resource blocks, each of bandwidth $B$ . That is, the total number of frequency resource blocks are given as $\Omega =B_{T}/B$ . Users who are non-orthogonally scheduled over the same resource blocks form a NOMA cluster. However, each NOMA cluster operates on a frequency resource block which is orthogonal to other frequency resource blocks. The number of users per NOMA cluster is represented by $m$ which ranges from $2 \leq m \leq N$ . Also, the number of resource blocks allocated per cluster is represented by $\omega $ , where $1\leq \omega \leq \Omega $ .

Provided the range of $m$ , the number of clusters can vary between 1 and $N/2$ . The maximum BS transmission power budget is $P_{T}$ , the maximum transmission power budget per downlink NOMA cluster is $P_{t}$ , and the maximum user transmit power is $P^\prime _{t}$ . The normalized channel gain between $i$ -th UE and the BS is represented by $\gamma _{i}$ which accounts for both distance-based path-loss and shadowing. The users are sorted according to the descending order of their normalized channel gains as $\gamma _{1} > \gamma _{2} > \gamma _{3} >\cdots > \gamma _{N}$ .

Now, let us define a variable $\beta _{i,j}$ as follows:\begin{equation} \beta _{i,j}= \begin{cases} 1, & \text {if a user $i$ is grouped into cluster $j$}\\ 0, & \text {otherwise} \end{cases} \end{equation} where $j=1,2,, \cdots , N/2$ and $i=1,2,\cdots ,N$ .

B. Problem Formulation: Downlink NOMA

The joint user clustering (i.e., grouping of users into clusters) and power allocation problem for throughput maximization in downlink NOMA can be formulated as \begin{align*}&\hspace {-0.6pc}\underset {\omega ,~\boldsymbol \beta , \boldsymbol P} {\text {maximize}} {\sum \limits _{j = 1}^{N/2} \sum \limits _{i = 1}^{N} \omega _{j} \beta _{i,j}\log _{2}\left({1+\frac {P_{i} \gamma _{i}}{\sum \limits _{k = 1}^{i-1} \beta _{k,j} P_{k} \gamma _{i} + \omega _{j}}}\right)} \\[1pt]&\hspace {-0.6pc}\text {subject to:} \enspace {\mathbf {C_{1}}}:~\sum \limits _{j = 1}^{N/2} \sum \limits _{i = 1}^{N} \beta _{i,j} P_{i} \leq P_{T}, \\[1pt]&\hspace {-0.6pc}\enspace {\mathbf {C_{2}}}: \sum \limits _{j = 1}^{N/2} \omega _{j} \beta _{i,j}\log _{2}\left({1+\frac {P_{i} \gamma _{i}}{\sum \limits _{k = 1}^{i-1} \beta _{k,j} P_{k} \gamma _{i} +\omega _{j}}}\right) > R_{i}, \forall \, i, \\[1pt]&\hspace {-0.6pc} \enspace {\mathbf {C_{3}}}: \, \left({\beta _{i,j}P_{i}-\sum \limits _{k = 1}^{i-1} \beta _{k,j} P_{k}}\right) \gamma _{i-1} \geq P_{tol}, \, \forall \, i, \\[1pt]&\hspace {-0.6pc}\enspace {\mathbf {C_{4}}}: \,\left({\sum \limits _{j=1}^{N/2} \beta _{i,j} =1, \, \forall \, i}\right) \\[1pt]&\hspace {-0.6pc}\hspace {30pt}\text {AND}\,\left({ \left({ 2 \leq \sum \limits _{i=1}^{N} \beta _{i,j} \leq N}\right) \text {OR}\,\left({\sum \limits _{i=1}^{N} \beta _{i,j} =0, \, \forall \, j }\right)}\right) \\[1pt]&\hspace {-0.6pc} \enspace {\mathbf {C_{5}}}: \sum \limits _{j=1}^{N/2} \beta _{i,j} \omega _{j} \leq \Omega , \quad \forall \,i, \enspace {\mathbf {C_{6}}}: \omega _{j} \in \{1,2,\cdots , \Omega \}, \, \forall \,j, \\[1pt]&\hspace {-0.6pc} \enspace {\mathbf {C_{7}}}: \,\, \beta _{i,j} \in \{0,1\}, \, \forall \,i,j, \end{align*} where $R_{i}$ is the minimum data rate requirement for $i$ -th user. Constraint $\mathrm {{C_{1}}}$ denotes the total power constraint of the BS, Constraint $\mathrm {{C_{2}}}$ ensures the minimum downlink data rate requirements of the users, Constraint $\mathrm {{C_{3}}}$ denotes the SIC constraints as discussed in Section II.A, Constraint $\mathrm {{C_{4}}}$ ensures that one user can be assigned to at most one cluster, while at least two users are grouped into each downlink NOMA cluster, Constraint $\mathrm {{C_{5}}}$ provides the total downlink frequency resource constraint. In addition, Constraints $\mathrm {{C_{6}}}$ and $\mathrm {{C_{7}}}$ demonstrate that $\omega $ and $\beta $ are integer variables.

C. Problem Formulation: Uplink NOMA

Similarly, the joint user clustering and power allocation problem for throughput maximization of an uplink NOMA system can be formulated as follows:\begin{align*}&\hspace {-0.6pc}\underset {\omega ,~\boldsymbol \beta , \boldsymbol P} {\text {maximize}} \sum \limits _{j = 1}^{N/2} \sum \limits _{i = 1}^{N} \omega _{j} \beta _{i,j}{\log _{2}\left({1+\frac {P_{i} \gamma _{i}}{\sum \limits _{k = i+1}^{N} \beta _{k,j} P_{k} \gamma _{k} +\omega _{j}}}\right)} \\&\hspace {-0.6pc}\text {subject to:} \enspace {\mathbf {C^\prime _{1}}}: \sum \limits _{j = 1}^{N/2} \beta _{i,j} P_{i} \leq P^\prime _{t}, \forall \, i, \\&\hspace {-0.6pc} \enspace {\mathbf {C^\prime _{2}}}: \sum \limits _{j = 1}^{N/2} \omega _{j} \beta _{i,j}\log _{2}\left({1+\frac {P_{i} \gamma _{i}}{\sum \limits _{k = i+1}^{N} \beta _{k,j} P_{k} \gamma _{k} +\omega _{j}}}\right) {> R_{i}^\prime , \forall \, i,} \\&\hspace {-0.6pc}\enspace {\mathbf {C^\prime _{3}}}: \,\,P_{i} \gamma _{i} \beta _{i,j} - \sum \limits _{k=i+1}^{N} \beta _{k,j} P_{k} \gamma _{k} \geq P_{tol}, \forall \, i, \\&\hspace {-0.6pc} \enspace {\mathbf {C^\prime _{4}}}: \,\left({\sum \limits _{j=1}^{N/2} \beta _{i,j} =1, \, \forall \, i}\right) \\&\hspace {0.6pc}~\text {AND}\,\left({ \left({ \, 2 \leq \sum \limits _{i=1}^{N} \beta _{i,j} \leq N}\right)\, \text {OR}\,\left({\sum \limits _{i=1}^{N} \beta _{i,j} =0, \, \forall \, j }\right)}\right) \\&\hspace {-0.6pc} \enspace {\mathbf {C^\prime _{5}}}: \sum \limits _{j=1}^{N/2} \beta _{i,j} \omega _{j} \leq \Omega , \quad \forall \,i, \enspace {\mathbf {C^\prime _{6}}}: \omega _{j} \in \{1,2,\cdots , \Omega \}, \, \forall \,j, \qquad \\&\hspace {-0.6pc} \enspace {\mathbf {C^\prime _{7}}}: \,\, \beta _{i,j} \in \{0,1\}, \, \forall \,i,j, \end{align*} where $R^\prime _{i}$ is the minimum uplink data rate requirement for $i$ -th user. Constraint $\mathrm { {C^\prime _{1}}}$ denotes the power constraint of each UE, Constraint $\mathrm { {C^\prime _{2}}}$ ensures the minimum uplink data rate requirements of the users, Constraint $\mathrm { {C^\prime _{3}}}$ ensures the SIC constraint as discussed in Section II.B, and Constraints $\mathrm { {C^\prime _{4}}}-\mathrm { {C^\prime _{7}}}$ are same as defined in Section III.B.

D. Solution Methodology

As can be seen, the formulated problems are mixed integer non-linear programming (MINLP) problems whose solutions are combinatorial by nature. Specifically, for throughput maximization, the optimal user clustering solution requires an exhaustive search to form a NOMA cluster [13]. That is, for every single user, we need to consider all possible combinations of user grouping. For example, let us consider an uplink/downlink NOMA system with $N$ users. In such a system, the number of possible combinations for optimal user clustering, can be expressed as follows:\begin{equation*} \Phi = {\sum }_{i = 2}^{N} {\binom{N }{ i}}. \end{equation*} Evidently, the computational complexity of optimal user clustering may not be affordable for practical systems with a large number of active users. As such, we resort to solve the problem in two steps, i.e., by developing a less complex solution for grouping users into different NOMA clusters and then optimizing their respective powers to maximize the sum-throughput per cluster. Subsequently, Section IV details the proposed low-complexity user clustering scheme. Given the user clustering, we derive optimal power allocations for users in Section V.

SECTION IV. User Clustering in NOMA

In this section, we propose a low-complexity sub-optimal user clustering scheme for both uplink and downlink NOMA systems. The proposed scheme exploits the channel gain differences among users and aims at enhancing the sum-throughput of the considered cell. Prior to user grouping, this scheme relies on selecting a feasible number of clusters, i.e., decides on the number of clusters and in turn the number of users per cluster. Once the number of users in a cluster is decided, user grouping is performed. In the following, the key concepts of our proposed user paring policies and their algorithmic presentations are detailed.

A. Key Issues for User Clustering in Downlink NOMA

Let us consider an $m$ -user downlink NOMA cluster to which $\omega $ units of resource blocks are allocated. For such a system, the achievable per-user throughput in (1), where $i = 1, 2,3,\cdots ,m$ , provides necessary insights to group users into a cluster. These insights are discussed below.

• After SIC, the throughput of the highest channel gain user in a cluster is not subject to the intra-cluster interference; instead, its throughput depends on its own channel gain and power. Although the allocated transmit power for the highest channel gain user is low (as mentioned in Section II.A), its impact on the throughput is minimal. Subsequently, if the gain of the highest channel is sufficiently high, then the achievable data rate negligibly depends on the transmission power, unless the power is very low. Thus it is beneficial to distribute the high channel gain users in a cell into different NOMA clusters, as they can significantly contribute to the sum-throughput of a cluster.

• To increase the throughput of the users with low channel gains, it is useful to pair them with high channel gain users. The reason is that the high channel gain users can achieve a higher rate even with low power levels while making a large fraction of power available for weak channel users. As such, the key point of our proposed user clustering in downlink NOMA is to pair the highest channel gain user and the lowest channel gain user into the same NOMA cluster, while the second highest channel gain user and the second lowest channel gain user into another NOMA cluster, and so on.

• The throughput of the remaining users in a NOMA cluster follows the same format. That is, the expression for SINR contains the same channel in both the denominator and numerator, whereas the transmit power in the numerator is greater than the sum power in the denominator (this is given by the SIC constraint). As such, the throughput of the remaining users in a NOMA cluster depends mainly on the distribution of the transmit power levels.

B. Key Issues for User Clustering in Uplink NOMA

Let us consider an $m$ -user uplink NOMA cluster to which $\omega $ resource blocks are allocated. For such a system, the achievable per-user throughput in (6), where $i = 1, 2,3,\cdots ,m$ , provides necessary insights to group users. These insights are discussed below.

• In an uplink NOMA cluster, all users’ signals experience distinct channel gains. To perform SIC at the BS, we need to maintain the distinctness of received signals. As such, the conventional transmit power control is not feasible in a NOMA cluster. Further, contrary to downlink NOMA, the power control at any user does not increase the power budget for any other user in a cluster. As such, power control will result is sum-throughput degradation.

• The distinctness among the channels of different users within a NOMA cluster is crucial to minimize inter-user interference and thus to maximize the cluster throughput.

• In uplink NOMA, the highest channel gain user does not interfere to weak channel users (actually his interference is cancelled by SIC). Therefore, this user can transmit with its maximum power to achieve a higher throughput. It is thus beneficial to include the high channel gain users transmitting with their maximum powers in each NOMA cluster, as they can significantly contribute to the throughput of a cluster.

C. User Clustering Algorithm

Based on the above discussions, let we classify the users into two classes: Class-A and Class-B. The number of users in Class-A, denoted as $\alpha $ , have much higher channel gains compared to users in Class-B, i.e., \begin{equation*} \gamma _{1}, \gamma _{2}, \cdots , \gamma _\alpha \gg \gamma _{\alpha +1}, \gamma _{\alpha +2}, \cdots , \gamma _{N}. \end{equation*} Then, the proposed sub-optimal user clustering algorithm can be given as in Algorithm 1 below.

Algorithm 1 User Clustering in Downlink and Uplink NOMA

1.

Sort users: $\gamma _{1} \geq \gamma _{2} \geq \cdots \geq \gamma _\alpha \gg \gamma _{\alpha +1} \geq \gamma _{\alpha +2} \geq \cdots \geq \gamma _{N}$ .

2.

Select no. of clusters: $\text {if}\enspace (\alpha < N/2)$ then number of clusters,$\kappa = \alpha :~ \text {else if}~(\alpha \geq N/2)~\text {then number of clusters},~\kappa = N/2$ .

3.

1. Group users into clusters for downlink NOMA:

   1st cluster $=\{\gamma _{1}, \gamma _{\kappa +1},\gamma _{2\kappa +1}, \cdots ,\gamma _{N}\}$ ,

   2nd cluster $=\{\gamma _{2}, \gamma _{\kappa +2}, \gamma _{2\kappa +2},\cdots ,\gamma _{N-1}\},\cdots $ ,

   $\kappa $ -th cluster $=\{\gamma _{\kappa }, \gamma _{2\kappa }, \gamma _{3\kappa },\cdots ,\gamma _{N-\kappa -1}\}$ .

2. Group users into clusters for uplink NOMA:

   1st cluster $=\{\gamma _{1}, \gamma _{\kappa +1},\gamma _{2\kappa +1}, \cdots ,\gamma _{N-\kappa -1}\}$ ,

   2nd cluster $=\{\gamma _{2}, \gamma _{\kappa +2}, \gamma _{2\kappa +2},\cdots ,\gamma _{N-\kappa -2}\},\cdots $ ,

   $\kappa $ -th cluster $=\{\gamma _{\kappa }, \gamma _{2\kappa }, \gamma _{3\kappa },\cdots ,\gamma _{N}\}$ .

4.

Cluster size: $\text {if}~((N {\textbf {mod}}~\kappa ) == 0)$ then uniform cluster size else different cluster size.

To illustrate, in Fig. 3 and Fig. 4, we show user grouping for 2-user, 3-user, and 4-user NOMA clusters in downlink and uplink, respectively, where the total number of users is assumed to be 12.

FIGURE 3.

Illustration of 2-user, 3-user, and 4-user NOMA clustering for downlink transmission to 12 active users in a cell.

FIGURE 4.

Illustration of 2-user, 3-user, and 4-user NOMA for uplink transmission of 12 active users in a cell.

SECTION V. Optimal Power Allocations in NOMA

Given the NOMA clusters obtained from Section IV, in this section, we derive optimal power allocations for a NOMA cluster with $m$ users in the both downlink and uplink transmission scenarios, where $2\leq m \leq N$ . Closed-form expressions for optimal power allocations are derived using KKT optimality conditions.

A. Downlink NOMA

1) Problem Formulation

Let us consider an $m$ -user downlink NOMA cluster, where the normalized channel gains of $UE_{1}, UE_{2},\cdots , UE_{m}$ are assumed to be $\gamma _{1}, \gamma _{2},\cdots ,\gamma _{m}$ , respectively, and their respective minimum rate requirements are $R_{1}, R_{2},\cdots ,R_{m}$ , where $R_{i}>0$ . It is assumed that $\omega $ resource blocks, each of bandwidth $B$ , are allocated to the downlink NOMA cluster. If $P_{1}, P_{2},\cdots ,P_{m}$ are the transmission powers for $UE_{1}, UE_{2},\cdots ,UE_{m}$ , respectively, then the optimal power allocation problem can be given as \begin{align*}&\quad \underset {P}{\text {max}} \quad \omega B {\sum }_{i = 1}^{m}\log _{2}\left({1+\frac {P_{i} \gamma _{i}}{\sum \limits _{j = 1}^{i-1} P_{j}\gamma _{i}+\omega }}\right) \\[.7pt]&\text {subject to:}\enspace {\mathbf {C_{1}}}:\,\,\sum \limits _{i = 1}^{m}P_{i} \leq P_{t}, \\[.7pt]&\quad \,\, {\mathbf {C_{2}}}:\,\,\, \omega B\log _{2}\left({1+\frac {P_{i} \gamma _{i}}{\sum \limits _{j = 1}^{i-1} P_{j}\gamma _{i} + \omega }}\right) \geq R_{i}, \forall \, i, \quad \\[.7pt]&\quad \,\, {\mathbf {C_{3}}}:\,\,\, P_{i}\gamma _{i-1} - \sum \limits _{j = 1}^{i-1}P_{j}\gamma _{i-1} \geq P_{tol}, \quad \forall \, i = 2,3,\cdots ,m, \end{align*} where $\sum _{j = 1}^{i-1} P_{j}\gamma _{i}$ is the inter-user interference for $i$ -th user in downlink NOMA cluster. Constraint ${\mathrm {{C_{1}}}}$ is the total power constraint, Constraint ${\mathrm {{C_{2}}}}$ is the minimum rate requirement per user, and Constraint ${\mathrm {{C_{3}}}}$ denotes the SIC constraints. Note that the aforementioned problem is convex under Constraints $\mathrm {{C_{1}}}-\mathrm {{C_{3}}}$ .

2) Closed-Form Optimal Power Solution

For the aforementioned problem, the Lagrangian can be expressed as:\begin{align}&\hspace {-1.8pc}\mathcal {L}(P,\lambda ,\mu ,\psi ) \notag \\[2pt]=&\omega B{\sum }_{i = 1}^{m}\log _{2}\left({1+\frac {P_{i}\gamma _{i}}{\sum \limits _{j = 1}^{i-1} P_{j}\gamma _{i}+\omega }}\right) \notag \\[2pt]=&\,\lambda \left({P_{t}-\sum \limits _{i=1}^{m}P_{i}}\right)+\sum \limits _{i=1}^{m}\mu _{i}\Big \{P_{i}\gamma _{i}-\left({\sum \limits _{k=1}^{i-1}~P_{k}\gamma _{i} - \omega }\right) \notag \\[2pt]&\times \Big (\varphi _{i}-1\Big )\Big \}+ \sum \limits _{i=2}^{m}\psi _{i}\left({P_{i}\gamma _{i-1}-\sum \limits _{l=1}^{i}P_{l}\gamma _{i-1}-P_{tol}}\right),\notag \\[2pt] {}\end{align} where $\lambda $ , $\mu _{i}$ , and $\psi _{j}$ are the Lagrange multipliers, $\forall \,i = 1,2,3,\cdots ,m$ and $\forall \,j = 2,3,4,\cdots ,m$ . Also, $\varphi _{i} = 2^{\frac {R_{i}}{ \omega B}}$ . Taking derivatives of (11) w.r.t. $P_{i}$ , $\lambda $ , $\mu _{i}$ , $\psi _{j}$ , we can write Karush-Kuhn-Tucker (KKT) conditions as follows:\begin{align} \frac {\partial \mathcal {L}}{\partial P_{1}^\ast }=&\frac {\omega B\gamma _{1}}{P_{1}\gamma _{1}+\omega } \notag \\[2pt]&-\, {\sum }_{k=2}^{m}\frac {\omega BP_{k}\gamma _{k}^{2}}{\left({\sum \limits _{l=1}^{k}P_{l}\gamma _{k}+\omega }\right)\left({\sum \limits _{l^\prime =1}^{k-1} P_{l^\prime }\gamma _{k}+\omega }\right)} -\lambda \notag \\[2pt]&+\,\mu _{1}\gamma _{1}-\sum \limits _{j=2}^{m}(\varphi _{j}-1)\mu _{j}\gamma _{j}\notag \\[2pt]&-\,\sum \limits _{j=2}^{m}\psi _{j}\gamma _{j-1} \leq 0,\, \textrm {if} \,P_{1}^\ast \geq 0, \\[2pt] \frac {\partial \mathcal {L}}{\partial P_{i}^\ast }=&\frac {\omega B\gamma _{i}}{\sum \limits _{j=1}^{i} P_{j}\gamma _{i}+\omega } \notag \\[2pt]&-\, {\sum }_{k=i+1}^{m}\frac {\omega BP_{k}\gamma _{k}^{2}}{\left({\sum \limits _{l=1}^{k}P_{l}\gamma _{k}+\omega }\right)\left({\sum \limits _{l^\prime =1}^{k-1}P_{l^\prime }\gamma _{k}+\omega }\right)} \notag \\[2pt]&-\,\lambda +\mu _{i}\gamma _{i}- \sum \limits _{k=i+1}^{m}(\varphi _{k}-1)\mu _{k}\gamma _{k}+\psi _{i}\gamma _{i-1} \notag \\[2pt]&-\,\sum \limits _{j=i+1}^{m}\psi _{j}\gamma _{j-1} \leq 0 ,\textrm {if} \enspace P_{i}^\ast \geq 0,\, \forall \,i=2,3,\cdots ,m, \notag \\[2pt] \\[2pt] \frac {\partial \mathcal {L}}{\partial \lambda ^\ast }=&P_{t}-\sum \limits _{i=1}^{m}P_{i} \geq 0, \,\text {if}\, \lambda ^\ast \geq 0, \qquad \qquad \qquad \qquad \, \, \\[2pt] \frac {\partial \mathcal {L}}{\partial \mu _{i}^\ast }=&P_{i}\gamma _{i}-\left({\sum \limits _{j=1}^{i-1}P_{j}\gamma _{i}+\omega }\right)\Big (\varphi _{i}-1\Big )\geq 0, \qquad \quad \,\notag \\[2pt]&\textrm {if} \,\mu _{i}^\ast \geq 0, \, \forall \, i = 1,2,3,\cdots ,m, \\[2pt] \frac {\partial \mathcal {L}}{\partial \psi _{i}^\ast }=&P_{i}\gamma _{i-1}-\sum \limits _{j=1}^{i-1}P_{j}\gamma _{i-1} - P_{tol}\geq 0, \qquad \,\notag \qquad \quad \\[2pt]&\textrm {if} \,\psi _{i}^\ast \geq 0, \, \forall \, i = 2,3,4,\cdots ,m. \end{align} In addition, we have several KKT complementarity conditions whose treatment is detailed in the following.

In an $m$ -user cluster, there are $2m$ Lagrange multipliers. Thus there are $2^{2m}$ combinations of Lagrange multipliers that need to be checked to satisfy the KKT conditions [18]. However, checking $2^{2m}$ combinations is computationally complex. For example, if $m=3,4,\cdots ,10$ , then the numbers of combinations are $64, 256,\cdots , 1048576$ , respectively. In our problem $P_{i} > 0,\,\forall \,i = 1,2,3,\cdots ,m$ ; therefore, to obtain a fixed number of solutions for $m$ decision variables we need exactly $m$ equations [16]. Thus, all $2^{2m}$ combinations do not need to be checked, rather we need to check only ${\binom{2m }{ m}}$ combinations. After solving for 2-, 3-, 4-, and 6-user NOMA clusters, we find that the Lagrange multiplier combinations satisfying the KKT conditions are 2, 4, 8, 32, respectively, which is in general $2^{m-1}$ .

The Lagrange multipliers for $m$ -user downlink NOMA cluster belong to three sets of constraints. These sets are the total transmit power constraints, minimum data rate constraints, and SIC constraints, given mathematically as, $A = \{\lambda \}, \quad B = \{\mu _{1}, \mu _{2}, \mu _{3}, \mu _{4},\cdots ,\mu _{m}\}, \quad C = \{\psi _{2}, \psi _{3}, \psi _{4},\cdots ,\psi _{m}\}$ , respectively. Therefore, the solution set is, $S = \{\lambda , \mu _{2}\,\text {or}\,\psi _{2}, \mu _{3}\,\text {or}\,\psi _{3}, \mu _{4}\,\text {or}\,\psi _{4},\cdots ,\mu _{m} \,\text {or}\,\psi _{m}\}$ . For example, for 2-user downlink NOMA, the satisfied KKT conditions are $S_{1} = \{\lambda ,\mu _{2}\}$ and $S_{2} = \{\lambda ,\psi _{2}\}$ . For 3-user NOMA, the satisfied KKT conditions are $S_{1} = \{\lambda ,\mu _{2}, \mu _{3}\}$ , $S_{2} = \{\lambda , \mu _{2}, \psi _{3}\}$ , $S_{3} = \{\lambda ,\psi _{2}, \mu _{3}\}$ , and $S_{4} = \{\lambda , \psi _{2}, \psi _{3}\}$ . Now let us define two additional sets of Lagrange multipliers, $B^\prime = S-B$ and $C^\prime = S-C$ . Then the closed-form solution of optimal power allocation for an $m$ -user downlink NOMA cluster can be given as in the following lemma.

Lemma 2 (Optimal Power Allocations for an$m$ -User Downlink NOMA Cluster):

The closed-form solution of the optimal power allocation for the highest channel gain user in downlink NOMA cluster can be given as follows:\begin{align*} P_{1}=&\frac {P_{t}}{\mathop{\prod \limits _{j=2}^{m}}\limits_{j\not \in B^\prime }\varphi _{j} \mathop{\prod \limits _{j=2}^{m}}\limits_{j\in B^\prime }2} - \underset {j\not \in B^\prime }{\sum _{j=2}^{m}}\frac {\omega (\varphi _{j} - 1)}{\gamma _{j} \mathop{\prod \limits _{k=2}^{j}}\limits_{k\not \in B^\prime }\varphi _{k} \mathop{\prod \limits _{k=2}^{j}}\limits_{k\in B^\prime }2} \\[2pt]&-\,\underset {j\not \in C^\prime }{\sum _{j=2}^{m}}\frac {P_{tol}}{2\gamma _{j-1} \mathop{\prod \limits _{k=2}^{j-1}}\limits_{k\not \in B^\prime }\varphi _{k} \mathop{\prod \limits _{k=2}^{j-1}}\limits_{k\in B^\prime }2}. \end{align*} On the other hand, the optimal power allocations for remaining users (except the highest channel gain user) are given as

1. If \begin{align*} i\not \in B^\prime , P_{i}=&\Bigg [\!\frac {P_{t}}{\mathop{\prod \limits _{j=i}^{m}}\limits_{j\not \in B^\prime }\varphi _{j} \mathop{\prod \limits _{j=i}^{m}}\limits_{j\in B^\prime }2} \!- \!\underset {j\not \in B^\prime }{\sum _{j=i}^{m}}\frac {\omega (\varphi _{j} - 1)}{\gamma _{j} \mathop{\prod \limits _{k=i}^{j}}\limits_{k\not \in B^\prime }\varphi _{k} \mathop{\prod \limits _{k=i}^{j}}\limits_{k\in B^\prime }2} \\[4pt]&-\underset {j\not \in C^\prime }{\sum _{j=i}^{m}}\frac {P_{tol}}{2\gamma _{j-1} \mathop{\prod \limits _{k=i}^{j-1}}\limits_{k\not \in B^\prime }\varphi _{k} \mathop{\prod \limits _{k=i}^{j-1}}\limits_{k\in B^\prime }2} \!+ \! \frac {\omega }{\gamma _{i}}\!\Bigg ]\!\times \! (\varphi _{i} \!-\! 1). \end{align*}

2. If \begin{align*} i\in B^\prime , P_{i}=&\frac {P_{t}}{\mathop{\prod \limits _{j=i}^{m}}\limits_{j\not \in B^\prime }\varphi _{j} \mathop{\prod \limits _{j=i}^{m}}\limits_{j\in B^\prime }2} - \underset {j\not \in B^\prime }{\sum _{j=i}^{m}}\frac {\omega (\varphi _{j} - 1)}{\gamma _{j} \mathop{\prod \limits _{k=i}^{j}}\limits_{k\not \in B^\prime }\varphi _{k} \mathop{\prod \limits _{k=i}^{j}}\limits_{k\in B^\prime }2} \\[4pt]&-\,\underset {j\not \in C^\prime }{\sum _{j=i}^{m}}\frac {P_{tol}}{2\gamma _{j-1} \mathop{\prod \limits _{k=i}^{j-1}}\limits_{k\not \in B^\prime }\varphi _{k} \mathop{\prod \limits _{k=i}^{j-1}}\limits_{k\in B^\prime }2} + \frac {P_{tol}}{\gamma _{i-1}}. \end{align*}

Proof:

See Appendix A.

The optimal transmission powers and the corresponding necessary conditions for 2-, 3-, and 4-user downlink NOMA clusters are provided in Table 1.

TABLE 1 Optimal Transmission Power and Corresponding Necessary Conditions For 2-, 3-, and 4-User Downlink NOMA Cluster

B. Uplink NOMA

1) Problem Formulation

Let us consider an $m$ -user uplink NOMA cluster, where the normalized channel gains of $UE_{1}, UE_{2},\cdots , UE_{m}$ are assumed to be $\gamma _{1}, \gamma _{2},\cdots ,\gamma _{m}$ , respectively, and their respective minimum rate requirements are $R_{1}^\prime , R_{2}^\prime ,\cdots ,R_{m}^\prime $ , where $R_{i}^\prime >0$ . Let us also consider that the $\omega $ units of resource blocks are allocated to this $m$ -user uplink NOMA cluster, where the bandwidth of each resource block is $B$ Hz. The optimal power control problem can then be expressed as follows:\begin{align*}&\enspace \underset {P}{\text {max}}\quad \omega B{\sum }_{i = 1}^{m}\log _{2}\left({1+\frac {P_{i} \gamma _{i}}{\sum \limits _{j = i+1}^{m} P_{j}\gamma _{j} + \omega }}\right) \\[4pt]&\text {subject to:} \quad {\mathbf {C_{1}^\prime }}:\,\, P_{i} \leq P_{t}^\prime ,\quad \forall \, i=1,2, \cdots , m, \\[4pt]&\quad {\mathbf {C_{2}^\prime }}:\,\, \omega B\log _{2}\left({1+\frac {P_{i} \gamma _{i}}{\sum \limits _{j = i+1}^{m} P_{j}\gamma _{j} + \omega }}\right) \geq R_{i}^\prime , \\[4pt]&\qquad \qquad \qquad \qquad \qquad \qquad \forall i\, = 1, 2, \cdots , m, \\[4pt]&\quad {\mathbf {C_{3}^\prime }}:\,\, P_{i} \gamma _{i} \!- \!\sum \limits _{j=i+1}^{m}P_{j}\gamma _{j} \geq P_{tol} ,\quad \forall \, i=1,2,\cdots ,m-1, \end{align*} where $\sum _{j = i+1}^{m} P_{j}\gamma _{j}$ is the inter-user interference for $i$ -th user in uplink NOMA cluster, and $P_{t}^\prime $ is the uplink maximum transmission power budget for each user. Note that the aforementioned optimization problem is also convex under the Constraints $\mathrm { {C_{1}^\prime }}-\mathrm { {C_{3}^\prime }}$ .

2) Closed-Form Optimal Power Solution

The Lagrange function for the above problem can then be expressed as \begin{align}&\hspace {-1pc}\mathcal {L}(P,\lambda ,\mu ,\psi )=\omega B{\sum }_{i = 1}^{m}\log _{2}\left({1+\frac {P_{i} \gamma _{i}}{\sum \limits _{j = i+1}^{m} P_{j}\gamma _{j} + \omega }}\right) \notag \\&+\,\sum \limits _{i=1}^{m}\lambda _{i}\Big (P_{t}^\prime -P_{i}\Big )+\sum \limits _{i=1}^{m}\mu _{i}\left({P_{i}\gamma _{i}-\sum \limits _{j=i+1}^{m}\phi _{i} P_{j}\gamma _{j} - \phi _{i}\omega }\right) \notag \\&+\,\sum \limits _{i=1}^{m-1}\psi _{i}\left({P_{i}\gamma _{i}-\sum \limits _{j=i+1}^{m}P_{j}\gamma _{j}-P_{tol}}\right), \end{align} where $\phi _{i} = \left({2^{\frac {R_{i}^\prime }{\omega B}}-1}\right)$ , and $\lambda _{i}$ , $\mu _{i}$ , and $\psi _{i}$ , are the Lagrange multipliers. Taking derivatives of equation (17) w.r.t. $P_{i}$ , $\lambda _{i}$ , $\mu _{i}$ , and $\psi _{i}$ , we obtain \begin{align} \frac {\partial \mathcal {L}}{\partial P^{*}_{i}}=&\frac {\omega B\gamma _{i}}{\sum \limits _{j = 1}^{m}P_{j}\gamma _{j}+\omega } -\lambda _{i} + \mu _{i}\gamma _{i} - \sum \limits _{k=1}^{i-1}\phi _{k}\mu _{k}\gamma _{i} + \gamma _{i}\psi _{i} \notag \\[.5pt]&-\,\sum \limits _{l=1}^{i-1}\psi _{l}\gamma _{l}\leq 0, \, \textrm {if} \, P_{i}^\ast \geq 0,\, \forall \, i = 1,2,\cdots ,m-1, \notag \\[.5pt] \\[.5pt] \frac {\partial \mathcal {L}}{\partial P^{*}_{m}}=&\frac {\omega B\gamma _{m}}{\sum \limits _{j = 1}^{m}P_{j}\gamma _{j}+\omega } -\lambda _{m} + \mu _{m}\gamma _{m} - \sum \limits _{k=1}^{m-1}\phi _{k}\mu _{k}\gamma _{m} \,\, \, \notag \\[.5pt]&-\,\sum \limits _{l=1}^{m}\psi _{l}\gamma _{l}\leq 0, \, \textrm {if} \, P_{m}^\ast \geq 0, \\[.5pt] \frac {\partial \mathcal {L}}{\partial \lambda _{i}^\ast }=&P_{t}^\prime -P_{i} \!\geq \!0, \, \textrm {if} \, \lambda _{i}^\ast \geq 0,\quad \forall \, i = 1,2,\cdots ,m, \\[.5pt] \frac {\partial \mathcal {L}}{\partial \mu _{i}^\ast }=&P_{i}\gamma _{i}-\sum \limits _{j = i+1}^{m}\phi _{i} P_{j}\gamma _{j}- \phi _{i} \omega \geq 0, \, \textrm {if}\, \mu _{i}^\ast \geq 0,\enspace \,\, \notag \\[.5pt]&\forall \, i = 1,2,\cdots ,m, \\[.5pt] \frac {\partial \mathcal {L}}{\partial \psi _{i}^\ast }=&P_{i} \gamma _{i} - \sum \limits _{j = i+1}^{m}P_{j}\gamma _{j} - P_{tol}\geq 0, \, \textrm {if}\, \psi _{i}^\ast \geq 0, \quad \enspace \notag \\[.5pt]&\forall \, i = 1,2,\cdots ,m-1. \end{align}

In an $m$ -user cluster, there are $(3m - 1)$ Lagrange multipliers, thus there are $2^{3m-1}$ combinations of Lagrange multipliers. Each combination needs to be checked to see whether it satisfies the KKT conditions or not [18]. However, checking $2^{3m-1}$ combinations is computationally complex. For example, if $m=3,4,\cdots ,10$ , then the numbers of combinations are $256, 2048,\cdots , 536870912$ , respectively. However, in our problem $P_{i} > 0,\,\forall \,i = 1,2,3, \ldots ,m$ ; therefore, we do not need to check all the combinations of Lagrange multipliers. To obtain a fixed number of solutions for $m$ decision variables, we need exactly $m$ equations [16]. Thus, only ${\binom{3m-1 }{ m}}$ combinations need to be checked. After solving for 2-, 3-, 4-, and 6-user NOMA clusters, we find that the Lagrange multiplier combinations satisfying KKT conditions are 3 for all cases.

Note that $(3m-1)$ Lagrange multipliers belong to three sets of constraints. These sets are total transmit power constraints, minimum data rate constraints, and SIC constraints, given mathematically as $A = \{\lambda _{1}, \lambda _{2}, \lambda _{3},\cdots ,\lambda _{m}\}, \quad B = \{\mu _{1}, \mu _{2}, \mu _{3},, \ldots ,\mu _{m}\}$ , and $\quad C = \{\psi _{1}, \psi _{2}, \psi _{3}, \ldots ,\psi _{m-1}\}$ , respectively. Therefore, the solution set is, $S = \{\lambda _{1}, \lambda _{2}\,\lambda _{3}, \ldots ,\lambda _{m-1}, \lambda _{m} \,\text {or}\,\mu _{m-1}\,\text {or}\,\psi _{m-1}\}$ . For example, for a 3-user uplink NOMA cluster, the satisfied KKT conditions are $S_{1} = \{\lambda _{1},\lambda _{2}, \lambda _{3}\}$ , $S_{2} = \{\lambda , \lambda _{2}, \mu _{2}\}$ , and $S_{3} = \{\lambda ,\lambda _{2}, \psi _{2}\}$ . Now let us define three additional sets of Lagrange multipliers as $A^\prime = S-A$ , $B^\prime = S-B$ , and $C^\prime = S-C$ . Then the closed-form solution of optimal power allocation for an $m$ -user uplink NOMA cluster can be given as in the following lemma.

Lemma 3 (Optimal Power Allocations for an$m$ -User Uplink NOMA Cluster):

The closed-form solutions of optimal power allocations for an $m$ -user uplink NOMA cluster can be given as follows:

1. If $(A^\prime == \{\varnothing \}), (B^\prime == B) $ , and $(C^\prime == C) $ , $P_{i}=P_{t}^\prime , \quad \forall \, i $ ,

2. If $(A^\prime \neq \{\varnothing \}), (B^\prime \neq B)$ , and $(C^\prime == C) $ , $P_{i}=P_{t}^\prime , \quad \forall \, i = 1,2,\cdots ,m-1 $ , $ P_{m}=\frac {P_{t}^\prime \gamma _{m-1}}{\phi _{m-1}\gamma _{m}} - \frac {\omega }{\gamma _{m}}$ ,

3. If $ (A^\prime \neq \{\varnothing \}), (B^\prime == B) $ , and $ (C^\prime \neq C) $ , $P_{i}=P_{t}^\prime , \quad \forall \, i = 1,2,3,\cdots ,m-1$ , $P_{m}=\frac {P_{t}^\prime \gamma _{m-1}}{\gamma _{m}} - \frac {P_{tol}}{\gamma _{m}} $ .

Proof:

See Appendix B.

The optimal transmission powers and the corresponding necessary conditions for 2-, 3-, and 4-user uplink NOMA clusters are provided in Table 2.

TABLE 2 Closed-Form Solutions for 2-User, 3-User, and 4-User Uplink NOMA Cluster

Remark:

In an uplink NOMA cluster, power control needs to be applied only at the weakest channel gain user. For example, for 4-user uplink NOMA cluster $UE_{1}$ , $UE_{2}$ , and $UE_{3}$ transmits with full power, while power control may be needed at $UE_{4}$ in order to

• maintain minimum data rate for the second weakest channel user ($UE_{3}$ in the 4-user NOMA cluster), and

• maintain minimum received power difference between the least two channel gain users ($UE_{3}$ and $UE_{4}$ in the 4-user NOMA cluster) at the BS receiver.

SECTION VI. Numerical Results and Discussions

In this section, we investigate the throughput performances of downlink and uplink NOMA systems using our proposed user grouping and optimal power allocation solutions. In our simulations, 2, 3, 4, and 6 units of resource blocks are allocated for 2-, 3-, 4-, and 6-user NOMA clusters, respectively. Both uplink and downlink NOMA systems are also compared with OFDMA-based LTE/LTE-Advanced systems. In addition, the total downlink transmission power is uniformly allocated among the available resource blocks. The major simulation parameters are shown in Table 3.

TABLE 3 Simulation Parameters for Downlink Noma and Uplink NOMA

A. Performance Evaluation of Downlink NOMA

In this subsection, we compare the performances of NOMA with OMA in terms of sum-throughput and individual users’ throughputs. Further, we compare the overall throughput performance of 2-user, 3-user, and 4-user downlink NOMA systems by considering 12 active downlink users.

1) Throughput Comparison Between NOMA and OMA Systems

Fig. 5 and Fig. 6 show the sum-throughput and individual throughput of 2-user downlink NOMA cluster and its corresponding OMA system for minimum data rate requirements of 100 Kbps and 1 Mbps, respectively. The normalized channel gain of the higher channel gain user is fixed at 40 dB whereas the channel gain of weak user varies in descending orders. Further, Fig. 7 represents the sum-throughput of 4-user downlink NOMA cluster and its corresponding OMA system as a function of channel variations for each user. In Fig. 7, the initial channel gains of $UE_{1}$ , $UE_{2}$ , $UE_{3}$ , and $UE_{4}$ are set to $\gamma _{1} = 40$ dB, $\gamma _{2} = 32$ dB, $\gamma _{3} = 24$ dB, and $\gamma _{4} = 16$ dB, respectively, and in each sub-figure only one user’s channel is varied by ensuring $\gamma _{1}>\gamma _{2}>\gamma _{3}>\gamma _{4}$ . From these simulation results we have the following observations:

• Sum-throughput for downlink NOMA is always better than that for OMA at any channel conditions. However, a significant throughput gain can be achieved for more distinct channel conditions of users in a cluster.

• Individual throughput of the highest channel gain user in a NOMA cluster is significantly higher than that in case of OMA. However, the throughput of the user with the lowest channel gain is limited by its minimum rate requirement. Therefore, as a remark, the minimum rate requirements of different users can be dynamically adjusted to enhance the fairness among users.

• Sum-throughput for downlink NOMA strongly depends on the highest channel gain user within a cluster. This is due to the fact that the strongest channel gain user can cancel all interfering signals before decoding its own signal, thus its achievable data rate does not depend on inter-user interference.

• The impact of the lowest channel gain user on the cluster sum-throughput is minimal, unless the channel gain is so small that a huge power is required for the lowest channel gain user. At this point, a sharp decay of sum-throughput is observed. Note that the traditional OMA is unable to operate at such poor channel gains.

• In a downlink NOMA cluster, the channel variations of all users, except the highest and the lowest channel gain users, do not considerably affect the sum-throughput of the NOMA cluster (see Fig. 7(b) and Fig. 7(c)).

FIGURE 5.

Throughput performance of 2-user downlink NOMA and OMA systems assuming 100 Kbps minimum data rate. Normalized channel gain of $UE_{1}$ is 40 dB.

FIGURE 6.

Throughput performance of 2-user downlink NOMA and OMA systems assuming 1 Mbps minimum data rate. Normalized channel gain of $UE_{1}$ is 40 dB.

FIGURE 7.

Impact of channel variation on the sum-throughput of 4-user downlink NOMA and OMA systems. Initial normalized channel gains of $UE_{1}$ , $UE_{2}$ , $UE_{3}$ , and $UE_{4}$ are 40 dB, 32 dB, 24 dB and 16 dB, respectively. We assume $R=100$ Kbps and $R=500$ Kbps, where $R=R_{1}=R_{2}=R_{3} =R_{4}$ .

2) Throughput Comparison of Various Downlink NOMA Systems

According to Lemma 1, a large number of users in a downlink NOMA cluster significantly reduces the amount of available power for the strongest channel user, who generally contributes the maximum throughput in a cluster. Therefore, it is crucial to select the correct cluster size. The throughput performance of a NOMA cluster depends significantly on three parameters, i.e., cluster size, transmit power, and channel gains of users. For a particular set of transmit powers and channel gains of users, we can find a cluster size that maximizes the sum-throughput. Table 4 shows the sum-throughput of different NOMA and OMA systems with 12 downlink users for various channel conditions while the transmit power is fixed in all cases.

TABLE 4 Performance of $m$ -User Downlink NOMA $(m = 2,3,4)$ and OMA Systems With 12 Users

In Table 4, we arrange the users in a descending order according to their channel gains. There are 6, 4, and 3 clusters with 2, 3, and 4 users in a cluster, respectively. The throughput performances of the aforementioned downlink NOMA clusters and their respective OMA counterparts are demonstrated in Table 4. The main observations are as follows:

• Less distinct channel gains of users (cases 12 and 14): In this case, the throughputs for different downlink NOMA systems are nearly the same. However, the 4-user NOMA achieves a higher throughput at better channel gains (case 12), while the 2-user NOMA obtains a higher throughput at lower channel gains (case 14). As such, we can conclude that a larger cluster size is preferred for higher channel gains of users and a smaller cluster size should be preferred for lower channel gains of the users. The overall throughput gains of downlink NOMA over OMA are very limited.

• More distinct channel gains of users (case 13): In this case, NOMA systems outperform their OMA counterparts. It can be seen that the 4-user NOMA achieves a better throughput than 2-user and 3-user NOMA systems. Therefore, a higher cluster size can be selected in such cases as long as the power allocation to the highest channel gain user does not decrease significantly (Lemma 1).

• Number of higher channel gain users is equal to the number of clusters (cases 3, 4, 6): In such a case, each downlink NOMA system achieves maximum relative throughput gain compared to OMA. In Table 4, the 4-user downlink NOMA system (i.e., 3 clusters) achieves a maximum of 106.3% throughput gain over OMA system when the number of good channels is equal to 3 (case 3). However, the 3-user (i.e., 4 clusters) and 2-user (i.e., 6 clusters) systems achieve maximum throughput gains of 86.6% and 52.8%, respectively, over OMA systems (case 4 and case 6). Thus, among all NOMA systems, the one with the number of higher channel gain users equal to the number of clusters achieves maximum (or close to maximum) throughput.

• In general, the throughputs for all NOMA systems are quite similar when 50% or more users experience good channels (cases 6 to 12). However, if the higher channel gain users are limited, then higher cluster sizes should be selected to enhance throughput (cases 1 to 3).

Finally, Fig. 8 shows individual users’ throughputs for 3-user downlink NOMA cluster considering two different minimum rate requirements of users, i.e., 100 Kbps and 2 Mbps. In general, our optimal power allocations maximize the transmit power of the highest channel gain user while maintaining the minimum rate requirements of all users in a NOMA cluster. However, in such a case, the lower channel gain users may experience significant throughput difference when compared to the highest channel gain user, as discussed in Section VI.A.1. As such, to improve the throughput fairness among users, the minimum data rate requirements of the users can be adjusted to balance the trade-off between fairness and the overall system throughput.

FIGURE 8.

Throughput performances of 3-user downlink NOMA system, for $R=R_{1}=R_{2}=R_{3}=100$ Kbps and 2 Mbps. Normalized channel gains of $UE_{1}$ and $UE_{2}$ are 40 dB and 30 dB, respectively.

B. Performance Evaluation of Uplink NOMA

In this subsection, we compare the throughput performances of uplink NOMA and OMA systems. We also compare the overall and individual users’ throughputs for 2-user, 3-user, 4-user, and 6-user uplink NOMA systems for 12 uplink users.

1) Throughput Comparisons Between NOMA and OMA

The sum-throughput and individual throughputs for 2-user uplink NOMA cluster are shown in Fig. 9, where the minimum user rate requirement is 100 Kbps. It can be seen that the sum-throughput of NOMA is higher than that of OMA with more distinct channel gains of users in a cluster. Also, the NOMA sum-throughput remains higher than OMA regardless of the weakest channel. On the other hand, when $UE_{1}$ and $UE_{2}$ have nearly the same channel gains, $UE_{2}$ achieves a better data rate. However, due to high interference from $UE_{2}$ , $UE_{1}$ obtains a very low data rate. As the channel gain of $UE_{2}$ reduces, its throughput gradually reduces. At the same time, the interference on $UE_{1}$ also reduces which improves the achievable throughput of $UE_{1}$ . As such, the sum-throughput of uplink NOMA cluster remains almost unchanged.

FIGURE 9.

Throughput performances of 2-user uplink NOMA and OMA systems assuming 100 kbps minimum data rate. Normalized channel gain of $UE_{1}$ is 40 dB.

When the minimum rate requirement of both users is set to as high as 1 Mbps, Fig. 10 depicts the sum-throughput and individual throughputs for a 2-user NOMA cluster as well as the sum-throughput for a 2-user OMA system. It is observed that the sum-throughput for NOMA becomes less than that for the corresponding OMA system in the region where the channel gains are less distinct and power control is applied. When the channel gains are less distinctive, without power control, the sum-throughputs for the 2-user uplink NOMA system and the corresponding OMA system are nearly similar. After applying power control in NOMA, the sum-throughput reduces and goes below that for OMA. We further note that, for uplink NOMA clusters, since the power control is only applicable at the weakest channel gain user, its impact keeps diminishing gradually for systems with 3-user and beyond (see in Fig. 11). Fig. 11 shows the sum-throughput and individual throughputs for a 3-user uplink NOMA cluster and the corresponding sum-throughput for an OMA system, where the minimum individual rate requirement is 1 Mbps. It is evident that the sum-throughputs of 3-user and beyond uplink NOMA clusters are always better than those for the OMA systems.

FIGURE 10.

Throughput performances of 2-user uplink NOMA and OMA systems assuming 1 Mbps minimum data rate. Normalized channel gain of $UE_{1}$ is 40 dB.

FIGURE 11.

Throughput performances of 3-user uplink NOMA and OMA systems assuming 1 Mbps minimum data rate. Normalized channel gains of $UE_{1}$ and $UE_{2}$ are 40 dB and 34 dB, respectively.

2) Comparisons Among Different Uplink NOMA Systems

The important feature of uplink NOMA system is that all lower channel gain users in a NOMA cluster interfere significantly to the higher channel gain users. Note that, due to SIC, low channel gain users do not experience any interference from high channel gain users. In contrast to downlink NOMA, the impact of transmission power control in not significant in uplink NOMA. In uplink NOMA, if more users need to be grouped into a cluster, more distinct channels are required. With different channel conditions of 12 uplink active users, we measure the performances of 2-user, 3-user, 4-user, and 6-user uplink NOMA systems as well as OMA system, shown in Table 5. The users are clustered according to the method discussed in Section IV.C. The channel gains in Table 5 are chosen in order to ensure the minimum channel distinctness required for the 6-user uplink NOMA system.

TABLE 5 Performances of $m$ -User Uplink NOMA $(m = 2,3,4,6)$ and OMA Systems with 12 Different Channel Users

In Table 5, we sort 12 users according to the descending order of their channel gains. There are 6, 4, 3, and 2 clusters available for 2-user, 3-user, 4-user, and 6-user uplink NOMA systems, respectively. From Table 5, we have the following key observations:

• More distinct channel gains of users (case 13): In this case, the performance of any uplink NOMA is much better than that of the OMA system (case 13), whereas a higher order NOMA achieves a higher throughput.

• Less distinct channel gains of users (cases 12 and 14): In this case, a higher order uplink NOMA still performs better, although the throughput performances of different NOMA systems are quite similar. However, in this case, the throughput gains of NOMA over OMA are marginal.

• Number of good channel users is equal to the number of clusters (cases 2, 3, 4, 6): In such a case, each uplink NOMA system achieves the maximum relative throughput gain compared to OMA. In Table 5, case 2 shows a 105.4% throughput gain of the 6-user uplink NOMA system in comparison to OMA system, while case 3, 4, and case 6 show the maximum throughput gain of 4-user, 3-user, and 2-user uplink NOMA systems, respectively, where the gains are 79.9%, 60.25%, and 33.3%, respectively. Thus, among all NOMA systems the one with the number of higher channel gain users equal to the number of clusters achieves the maximum (or close to maximum) throughput.

• When one or more users experience higher channel gains, higher order uplink NOMA systems perform much better than OMA systems (case 1, 2, and 3). As the number of users experiencing higher channel gains increases, different uplink NOMA systems perform nearly similar (cases 4 to 12).

Fig. 13 shows the individual throughputs for the 6-user uplink NOMA cluster, where $UE_{1}$ to $UE_{5}$ experience 40, 35, 30, 26, and 22 dB channel gains, respectively. Fig. 13 shows good throughput fairness among $UE_{1}$ to $UE_{4}$ , whilst, by selecting proper channel gains for $UE_{5}$ and $UE_{6}$ , good throughput fairness can be achieved for all six users. Therefore, exploitation of channel gain differences among the NOMA users is the key to designing efficient uplink NOMA systems.

FIGURE 13.

Throughput performance of 6-user uplink NOMA cluster for 100 Kbps minimum data rate. Normalized channel gains of $UE_{1}$ to $UE_{5}$ are 40, 35, 30, 26, and 22 dB, respectively, while the normalized channel gain of $UE_{6}$ varies.

SECTION VII. Conclusion

Efficient user clustering and power allocations among NOMA users are the key design issues for successful operations of NOMA systems. In this paper, for both uplink and downlink NOMA in a cellular system, we have formulated a joint optimization problem for sum-throughput maximization under the constraints of transmission power budget, minimum rate requirements of users, and operation constraints for SIC receivers. Due to the combinatorial nature of the problem, we have developed a low-complexity sub-optimal user clustering scheme. Given the user clustering, we have derived closed-form optimal power allocations for $m$ -user uplink/downlink NOMA systems. In both of downlink and uplink NOMA, user clusters with more distinctive channel gains provide impressive throughput gains for NOMA systems over their counterpart OMA systems. Numerical results have showed that the performance of downlink NOMA deteriorates if the cluster size increases beyond a certain threshold. Despite the numerous benefits of NOMA over OMA, the issues such as SIC error processing and inter-cell interference, are still under investigation. In this paper, we have considered ideal SIC; however, the performance of NOMA may depend significantly on the SIC errors. In downlink NOMA, each signal needs to be identically encoded, modulated, and precoded at the BS while the SIC receiver needs to successively demodulate, decode, and re-modulate stronger signals. Therefore, for large NOMA clusters, error propagation in SIC may drastically reduce the NOMA performance. Further, inter-cell interference is another major challenge for practical NOMA systems. The power allocation solutions need to be carefully extended for dense cellular networks in which inter-cell interference can be significant.

Fig. 12 demonstrates the sum-throughput for a 4-user uplink NOMA cluster as a function of individual user’s channel gain variation. The normalized channel gains of $UE_{1}$ , $UE_{2}$ , $UE_{3}$ , and $UE_{4}$ are set to 40 dB, 32 dB, 24 dB and 16 dB, respectively. In each sub-figure, the channel gain of each user is varied while the channel gains of of others remain fixed. For example, in case (a), the normalized channel gain of $UE_{1}$ is varied from 40 dB to 32.5 dB while the channel gains of other users are fixed. It is observed that the sum-throughput for uplink NOMA mainly depends on the channel conditions of the highest channel gain user.

FIGURE 12.

Impact of channel variation on the sum-throughput for 4-user uplink NOMA and OMA systems. Initial normalized channel gains of $UE_{1}$ , $UE_{2}$ , $UE_{3}$ , and $UE_{4}$ are 40 dB, 32 dB, 24 dB, and 16 dB, respectively. We assume $R^\prime =100$ Kbps and $R^\prime =500$ Kbps, where $R^\prime =R_{1}^\prime =R_{2}^\prime =R_{3}^\prime =R_{4}^\prime $ .

Appendix A Verification of KKT Conditions for Downlink NOMA

In this Appendix, we show the verification of KKT conditions for a given Lagrange multiplier combination in a general $m$ -user downlink NOMA cluster considering a particular value of $m$ . Let us consider $m=4$ which is a 4-user downlink NOMA cluster. Then, the set of Lagrange multipliers can be expressed as $A = \{\lambda \}, \, B = \{\mu _{1}, \mu _{2}, \mu _{3}, \mu _{4}\} \, \text {and} \, C = \{\psi _{2}, \psi _{3}, \psi _{4}\}$ . The solution sets of Lagrange multipliers that satisfy the KKT conditions are $S = \{\lambda , \mu _{2}\,\text {or}\,\psi _{2}, \mu _{3}\,\text {or}\,\psi _{3}, \mu _{4}\,\text {or}\,\psi _{4}\}$ . Now, consider one set of Lagrange multipliers, say $S_{1} = \{\lambda , \mu _{2}, \mu _{3}, \mu _{4}\}$ , that satisfies the KKT conditions, and thus the values of the Lagrange multipliers are $\lambda ^\ast > 0$ , $\mu _{2}^\ast > 0$ , $\mu _{3}^\ast > 0$ , $\mu _{4}^\ast > 0$ , and $\mu _{1}^\ast = \psi _{2}^\ast = \psi _{3}^\ast = \psi _{4}^\ast =0$ .

For the aforementioned Lagrange multipliers (14) to (16) can be expressed as \begin{align*} P_{t}-\sum \limits _{i=1}^{4}P_{i}=&0, \tag{A.1}\\[2pt] P_{i}\gamma _{i}-\left({\sum \limits _{j=1}^{i-1}P_{j}\gamma _{i}+\omega }\right)\Big (\varphi _{i}-1\Big )=&0, ~ \forall \, i = 2,3,4, \tag{A.2}\\[2pt] P_{i}\gamma _{i}-\left({\sum \limits _{j=1}^{i-1}P_{j}\gamma _{i}+\omega }\right)\Big (\varphi _{i}-1\Big )>&0, ~ \forall \, i = 1, \tag{A.3}\\[2pt] P_{i}\gamma _{i-1}-\sum \limits _{j=1}^{i-1}P_{j}\gamma _{i-1} - P_{tol}>&0, ~\forall \, i = 2,3,4.\qquad \quad \tag{A.4}\end{align*} Equations (A.1)-(A.2) provide the optimal solution of $P_{1}, P_{2}, P_{3}$ and $P_{4}$ , while equations (A.3)-(A.4) provide the necessary conditions for these optimal solutions. Now, solving equations (A.1)-(A.2), we obtain the optimal power allocations as follows:\begin{align*} P_{1}=&\frac {P_{t}}{\varphi _{2}\varphi _{3}\varphi _{4}} - \frac {\omega (\varphi _{2}-1)}{\varphi _{2}\gamma _{2}} - \frac {\omega (\varphi _{3}-1)}{\varphi _{2}\varphi _{3}\gamma _{3}} - \frac {\omega (\varphi _{4}-1)}{\varphi _{2}\varphi _{3}\varphi _{4}\gamma _{4}}, \\[2.5pt] P_{2}=&\frac {P_{t}(\varphi _{2}-1)}{\varphi _{2}\varphi _{3}\varphi _{4}} + \frac {\omega (\varphi _{2}-1)}{\varphi _{2}\gamma _{2}}- \frac {\omega (\varphi _{2}-1)(\varphi _{3}-1)}{\varphi _{2}\varphi _{3}\gamma _{3}} \\[2.5pt]&-\,\frac {\omega (\varphi _{2}-1)(\varphi _{4}-1)}{\varphi _{2}\varphi _{3}\varphi _{4}\gamma _{4}}, \\[2.5pt] P_{3}=&\frac {P_{t}(\varphi _{3}-1)}{\varphi _{3}\varphi _{4}} + \frac {\omega (\varphi _{3}-1)}{\varphi _{3}\gamma _{3}} - \frac {\omega (\varphi _{3}-1)(\varphi _{4}-1)}{\varphi _{3}\varphi _{4}\gamma _{4}}, \\[2.5pt] P_{4}=&\frac {P_{t}(\varphi _{4}-1)}{\varphi _{4}} + \frac {\omega (\varphi _{4}-1)}{\varphi _{4}\gamma _{4}}. \end{align*}

Since $\varphi _{i} =2^{\frac {R_{1}}{\omega B}} > 1,\,\forall \,i=1,2,3,4$ , the solutions of $P_{1},P_{2}, P_{3}$ and $P_{4}$ all are positive. Now, with the considered Lagrange multipliers and positive $P_{i},\,\forall \,i=1,2,3,4$ , after some algebraic operations, equations (12)–(13) can be expressed as \begin{align*}&\hspace {-1.2pc}{\sum }_{j=1}^{3}\frac {\omega ^{2}B(\gamma _{j} - \gamma _{j+1})}{\left({\sum \limits _{k=1}^{j}P_{k}\gamma _{j}\!+\!\omega }\right)\left({\sum \limits _{k=1}^{j}P_{k}\gamma _{j+1}+\omega }\right)} \!+ \!\frac {\omega B\gamma _{4}}{\sum \limits _{l=1}^{4}P_{l}\gamma _{4}\!+\!\omega } \enspace \\[2.5pt]=&\lambda + \sum \limits _{j=2}^{4}(\varphi _{j}-1)\mu _{j}\gamma _{j}, \tag{A.5}\\[2.5pt]&{\sum }_{j=i}^{3}\frac {\omega ^{2}B(\gamma _{j} - \gamma _{j+1})}{\left({\sum \limits _{k=1}^{j}P_{k}\gamma _{j}+\omega }\right)\left({\sum \limits _{k=1}^{j}P_{k}\gamma _{j+1}+\omega }\right)} \\[2.5pt]&+\, \frac {\omega B\gamma _{4}}{\sum \limits _{l=1}^{4}P_{l}\gamma _{4}+\omega } \enspace \\[2.5pt]=&\lambda - \mu _{i}\gamma _{i} + \sum \limits _{j=i+1}^{4}(\varphi _{j}-1)\mu _{j}\gamma _{j}, \, \forall \, i =2,3,4. \tag{A.6}\end{align*}

After performing some algebraic operations in equations (A.5)-(A.6), we obtain the Lagrange multipliers as follows:\begin{align*} \mu _{2}=&\frac {\omega ^{2} B(\gamma _{1}-\gamma _{2})}{\varphi _{2}\gamma _{2} (P_{1}\gamma _{1}+\omega )(P_{1}\gamma _{2}+\omega )}, \tag{A.7}\\ \mu _{i}=&\frac {\omega ^{2} B(\gamma _{i-1}-\gamma _{i})}{\varphi \gamma _{i} \left({\sum \limits _{j=1}^{i-1}P_{j}\gamma _{i-1}+\omega }\right)\left({\sum \limits _{j=1}^{i-1}P_{j}\gamma _{i}+\omega }\right)} \\&+\,\mu _{i-1}\gamma _{i-1}, \quad \forall \, i =3,4, \tag{A.8}\\ \lambda=&\frac {\omega B\gamma _{4}}{\sum \limits _{j=1}^{4}P_{j}\gamma _{4}+\omega } + \mu _{4}\gamma _{4}. \tag{A.9}\end{align*}

In our proposed dynamic power allocation solutions, we sort the UEs according to the descending order of their normalized channel gains, i.e., $\gamma _{1} > \gamma _{2} > \gamma _{3} > \gamma _{4}$ . Therefore, the solutions for $\lambda $ and $\mu _{i}, \, \forall \, i = 2,3,4$ , of equation (A.7)-(A.9) all are positives. Therefore, the set of Lagrange multipliers $S_{1} = \{\lambda , \mu _{2}, \mu _{3}, \mu _{4}\}$ satisfies the KKT conditions. All the other cases can easily be verified by using a similar approach.

Appendix B Verification of KKT Conditions for Uplink NOMA

Similar to the downlink NOMA cluster, we show the verification of KKT conditions for a general $m$ -user uplink NOMA cluster by considering a particular combination of Lagrange multipliers in a particular cluster size. Let us again consider $m=4$ , i.e., a 4-user uplink NOMA cluster. Then, the sets of Lagrange multipliers can be expressed as $A = \{\lambda _{1}, \lambda _{2}, \lambda _{3}, \lambda _{4}\}, \, B = \{\mu _{1}, \mu _{2}, \mu _{3}, \mu _{4}\}, \, \text {and} \, C = \{\psi _{1}, \psi _{2}, \psi _{3}\}$ . Therefore, the solution sets that satisfy the KKT conditions are: $S = \{\lambda _{1}, \lambda _{2}, \lambda _{3}, \lambda _{4}\,\text {or}\,\mu _{3}\,\text {or}\,\psi _{3}\}$ . Now, consider one set of Lagrange multipliers, say, $S_{1} = \{\lambda _{1}, \lambda _{2}, \lambda _{3}, \mu _{3}\}$ , that satisfies the KKT conditions, and thus the values of the Lagrange multipliers are $\lambda _{i}^\ast > 0$ , $\mu _{3}^\ast > 0$ , and $\lambda _{4}^\ast = \mu _{j}^\ast =\psi _{k}^\ast =0, \,\forall \, i = 1,2,3, \, \forall \, j = 1,2,4, \, \forall \, k = 1,2,3$ .

Now, with the aforementioned Lagrange multipliers, equations (20)–(22) can be expressed as \begin{align*} P_{t}^\prime -P_{i}=&0, \quad \forall \, i = 1,2,3, \qquad \tag{B.1}\\ P_{3}\gamma _{3}- \phi _{3}P_{4}\gamma _{4} - \phi _{3} \omega=&0 , \tag{B.2}\\ P_{t}^\prime -P_{4}>&0, \tag{B.3}\\ P_{i}\gamma _{i}-\phi _{i} \sum \limits _{j = i+1}^{4}P_{j}\gamma _{j}- \phi _{i} \omega>&0, \, \forall \, i = 1,2,4, \tag{B.4}\\ P_{i} \gamma _{i} - \sum \limits _{j = i+1}^{4}P_{j}\gamma _{j} - P_{tol}>&0, \quad \forall \, i = 1,2,3. \tag{B.5}\end{align*} Equations (B.1)-(B.2) provide the optimal solutions of $P_{1}, P_{2}, P_{3}$ and $P_{4}$ , while equations (B.3)-(B.5) provide the necessary conditions for these optimal solutions. Now, solving equations (B.1)-(B.2), we obtain the optimal power allocations as follows:\begin{align*} P_{i}=&P_{t}^\prime , \quad \forall \, i = 1,2,3,\\ P_{4}=&\frac {P_{t}^\prime \gamma _{3}}{\phi _{3}\gamma _{4}} - \frac {\omega }{\gamma _{4}}. \end{align*}

Since $\varphi _{i} =2^{\frac {R^\prime _{1}}{\omega B}}-1 > 0,\,\forall \,i=1,2,3,4$ , the solutions of $P_{1},P_{2}, P_{3}$ and $P_{4}$ all are positive. Now, with the considered Lagrange multipliers and the resultant positive $P_{i},\,\forall \,i=1,2,3,4$ , equations (18)–(19) can be expressed as follows:\begin{align*} \lambda _{i}=&\frac {\omega B\gamma _{i}}{\sum \limits _{j=1}^{4}P_{j}\gamma _{j}+\omega }, \, \forall \, i = 1,2, \tag{B.6}\\ \mu _{3}=&\frac {\omega B}{\phi _{3}\sum \limits _{j=1}^{4}P_{j}\gamma _{j}+\phi _{3} \omega }, \tag{B.7}\\ \lambda _{3}=&\frac {\omega B\gamma _{3}}{\sum \limits _{j=1}^{4}P_{j}\gamma _{j}+\omega } + \gamma _{3}\mu _{3}. \tag{B.8}\end{align*}

Since the solutions of $P_{i}$ , $\forall \, i =1,2,3,4$ , are all positive, equations (B.6)-(B.8) show that $\lambda _{1}$ , $\lambda _{2}$ , $\lambda _{3}$ , and $\mu _{3}$ are positive. Therefore, the Lagrange multiplier set $S_{1} = \{\lambda _{1}, \lambda _{2}, \lambda _{3}, \mu _{3}\}$ satisfies the KKT conditions. All the other cases can easily be verified by using a similar approach.