The research of power allocation algorithm with lower computational complexity for non-orthogonal multiple access

The next generation of mobile communications is facing huge challenges, mainly in the following two aspects: on the one hand, mass mobile terminals will be connected to the mobile network. On the other hand, green communications are demanded urgently. The information and communication technology industry consumes nearly 10% of global energy and produces greenhouse gases accounted for 2% of global emissions [1]. At present, in terms of the frequency spectrum and energy efficiency, the fourth generation of mobile communications (4G) cannot meet the requirements of future mobile communications. Energy efficiency and spectrum utilisation are the most attention-demanding issues in 5G and beyond the system.

In the previous and 4G systems, orthogonal multiple access (OMA) is usually used to achieve multi-user access. Although OMA can increase the capacity of the system, it is not outstanding enough in terms of spectrum utilisation. In terms of further improving the spectrum efficiency and system capacity of mobile communications, non-OMA (NOMA) is a technology worthy of attention. This new technology is trying to increase the throughput by allocating the same spectrum resource to different users through non-orthogonal access methods [2]. In addition, NOMA can also increase user connections in the case of limited resources. However, the price of this technology needs to pay is the complicated receiver structure and successive interference canceller (SIC) technology [3].

At present, the comparison between the orthogonal frequency division multiple access (OFDMA) system and NOMA system in terms of system capacity can be seen in many documents. In the literature [4, 5], the influence of the number of users on the NOMA system performance is described. Meanwhile, the design method and simulation process of the NOMA downlink are analysed. In [6], it can be seen that NOMA also has good performance in high mobility scenarios. Further, the system performance gain is verified when the NOMA combined with the beamforming. In the literature [7], several power allocation algorithms which are commonly used in NOMA are proposed, such as full search power allocation (FSPA) algorithm, fractional transmits power allocation (FTPA) algorithm and fixed power allocation (FPA) algorithm. For the algorithms mentioned, the first one is an optimal power allocation algorithm with high search complexity; the second one is a suboptimal algorithm for adaptive power allocation based on channel conditions; the third is also a suboptimal solution, which combines pre-pairing scheme and FPA. Comparing the pre-pairing user scheme with optimal traversal searching, the system throughput would decrease slightly, but the former's complexity of matching search would reduce significantly. In addition, a SIC detection based on the worst case is also proposed in this article. This model assumes that if a decoding error occurs in a previously decoded user during the SIC detection, the user being decoded at the terminal is directly judged as decoding error, which is equivalent to the worst-case error propagation model.

In [8], NOMA technology is proposed and studied. Several users are multiplexed in the power domain at the transmitting end. At the receiving end, SIC technology is used to eliminate the interference between multiplexed users. Average throughput and edge throughput of NOMA and OFDMA systems are analysed and compared. In addition, the hybrid technology of NOMA and multiple-input multiple-output (MIMO) is also discussed to enhance the system throughput. Under these circumstances, the base station (BS) transmitting multiple beams equals to multi-users MIMO. A cluster of multiplexed users is transmitted through one beam. At the receiving end, interference rejection combining technology and SIC technology are used to eliminate interference between beams and interference between users in the beam respectively.

User pairing scheme based on the FPA algorithm in NOMA system was studied in the literature [9]. On the transmit terminal, multi-user transmission through superposition coding (SC) in the power domain is also a key technology of NOMA. The SC technology is highlighted in the literature [10]. SC is a well-known nonorthogonal scheme, which achieves better system gain compared with OMA system. In ref. [11], the detection and optimisation scheme about SIC is studied in detail in the receiving end.

In this article, considering that the power allocation mechanism in the NOMA system in 5G is not clear, we study NOMA technology and its power allocation problem. The main contributions of this article are summarised as follows.

In NOMA system, SIC is considered for reception, and a mathematical model for capacity maximisation problem is established. Then, the power allocation strategies are researched and compared.

Simulation results show that the system capacity under the proposed power allocation scheme is perceptibly better than the original power algorithm.

The remainder part of the article is organised as follows: In Section 2, the system model and sub-carrier based on NOMA are described in brief. Thereafter, the system capacity maximisation problem and user pairing scheme are formulated in Section 3. A sub-optimal power optimisation algorithm based on the tree structure is described in detail in Section 4. Meanwhile, the complexity of this algorithm is investigated briefly in this section. Simulation results and conclusions are described in Section 5 and 6, respectively.

The core of the OFDMA is still the sub-channel transmission technology, as well as all sub-channels are orthogonal with each other. However, different from traditional OFDMA, each sub-channel is not allocated to only one user in NOMA. Several users share the same sub-band in the power domain [1]. In addition, the signal waveform of NOMA is based on OFDM.

The downlink power allocation is considered, which is shown in Figure 1. For OFDMA, each user only occupies the sub-carrier allocated to itself, as shown in Figure 1(a). For multiple access interferences, OFDMA has good robustness. However, the disadvantages of OFDMA are low spectrum utilisation and inter-carrier interference that is difficult to suppress. Different from OFDMA, all users share the whole bandwidth in NOMA system, as shown in Figure 1(b). Therefore, sub-carrier allocation is not needed to be considered in the NOMA system, since all users share the whole spectrum.

Fig. 1

Every unit of time and frequency domain in BS carries n user signals. During the downlink transmission, each user uploads the channel information to the BS in real time. Every user is allocated power by BS according to channel conditions. The weaker the channel, the greater power is allocated, and vice versa, the less power is allocated. Thus, the power of received signal in the terminal device is contrary to channel conditions. When the ending receives n user signals, it can detect all user signals conveniently, simply and correctly according to the order of the first strong and weak. In summary, all users are separated by SIC at the receiver side.

For convenience, it is assumed the transmitter and the receiver are single send and dual receive modes. Taking N users into account, the signal received by UE-i (u = 1,...,N) is denoted as x_i. Meanwhile, the channel bandwidth is assumed as 1 Hz, and the power of each user can be assumed as (1) E[|x1|2]=1 E[|{x_1}{|^2}] = 1

Transmission power is distributed to two users. Then, the signal after SC can be expressed as (2) x(t)=∑i=1NβiPxi x(t) = \sum\limits_{i = 1}^N \sqrt {{\beta _i}P{x_i}} where β_i ∈ (0,1), (i = 1,...,N) is the power assignment of the user UE-i i = 1,...,N, which should be satisfied ∑i=1Nβi=1 \sum\nolimits_{i = 1}^N {\beta _i} = 1 . According to the rules of the NOMA system, the power allocated to each user is related to the channel gain. At the receiving end, user i can be written as (3) yn(t)=hnx(t)=hn∑i=1NβiPxi+wn=hn∑i=1n-1βiPxi︸Removed by SIC+hnβnPxn︸Desired signal+hn∑i=n+1NβiPxi︸Remained interference+wn︸Interference {y_n}(t) = {h_n}x(t) = {h_n}\sum\limits_{i = 1}^N \sqrt {{\beta _i}P{x_i}} + {w_n} = \underbrace {{h_n}\sum\limits_{i = 1}^{n - 1} \sqrt {{\beta _i}P{x_i}}}_{{\mathop{\rm Removed \ by \ SIC}\nolimits} } + \underbrace {{h_n}\sqrt {{\beta _n}P{x_n}}}_{\rm Desired \ signal} + \underbrace {{h_n}\sum\limits_{i = n + 1}^N \sqrt {{\beta _i}P{x_i}}}_{{\mathop{\rm Remained \ interference}}} + \underbrace {{w_n}}_{\rm Interference} where h_n is the channel gain between BS and the user n, w_n is the additive white Gaussian noise including the cell interference, the power spectral density of noise is expressed as N₀. β represents the power allocation factor for each user, β_n ∈ C^T. The received data transmission rate of the user i, (i = 1,...,N) can be expressed as (4) Rn=BS∑n=1Nsclog2(1+γn) {R_n} = {B_S}\sum\limits_{n = 1}^{Nsc} \mathop {\log}\nolimits_2 (1 + {\gamma _n}) (5) Rm→n=BS∑n=1Nsclog2(1+γm→n) {R_{m \to n}} = {B_S}\sum\limits_{n = 1}^{Nsc} \mathop {\log}\nolimits_2 (1 + {\gamma _{m \to n}}) (6) RN=BS∑n=1Nsclog2(1+γN) {R_N} = {B_S}\sum\limits_{n = 1}^{Nsc} \mathop {\log}\nolimits_2 (1 + {\gamma _N}) where γ_n and γ_N represent the instantaneous signal-to-noise ratio (SNR) generated in the process of decoding its information by the nth user and the Nth user, respectively. γ_m→n is the instantaneous SNR generated by the nth user decoding the mth user. The above symbols can be expressed as: γn=|hn|2βnP∑i=n+1N|hn|2βiP+BSN0 {\gamma _n} = {{|{h_n}{|^2}{\beta _n}P} \over {\sum\nolimits_{i = n + 1}^N |{h_n}{|^2}{\beta _i}P + {B_S}{N_0}}} , γm→n=|hn|2βnP∑j=m+1N|hn|2βjP+BSN0 {\gamma _{m \to n}} = {{|{h_n}{|^2}{\beta _n}P} \over {\sum\nolimits_{j = m + 1}^N |{h_n}{|^2}{\beta _j}P + {B_S}{N_0}}} and γN=|hn|2βNPBSN0 {\gamma _N} = {{|{h_n}{|^2}{\beta _N}P} \over {{B_S}{N_0}}} . B_S is the bandwidth of the sub-carrier.

From Eqs. (4)–(6), we can find that the power allocated to each user will affect the rate of the current user and other users. Power allocation plays an important role in the NOMA system [9]. The way to maximise the NOMA system transmission rate is an urgent problem to solve. This problem can be set as an optimisation model (7) Max Rsum=BS∑n=1Nsc[log2(1+γn)+log2(1+γN)] {\rm Max} \ {R_{sum}} = {B_S}\sum\limits_{n = 1}^{Nsc} [\mathop {\log}\nolimits_2 (1 + {\gamma _n}) + \mathop {\log}\nolimits_2 (1 + {\gamma _N})] (8) S.t.Ru≥rmin {\rm{S}}.{\rm{t}}.{R_u} \ge {r_{min}} (9) Pu,n≥0, ∀u,∀n, {P_{u,n}} \ge 0,\;\;\forall u,\forall n, (10) ∑n=1Nsc∑u=1UPu,n≤PT \sum\limits_{n = 1}^{Nsc} \sum\limits_{u = 1}^U {P_{u,n}} \le {P_T} where Eq. (7) represents the optimisation goal, which is trying to maximise the transmission rate of the NOMA system. The transmission rate of each user should be greater than a certain threshold, as indicated in Eq. (8). It can be seen from Eq. (9) that the power which is allocated to each user is guaranteed to be positive. Eq. (10) shows that the total power is limited. Therefore, it is very difficult to find a specific algorithm to maximise Eq. (7) in the NOMA system.

Another indicator that reflects system capacity is the channel's outage probability. The outage probability is defined as [7]: (11) Pout(R)=Pr(R(γ)<Rth) {P_{out}}(R) = \Pr (R(\gamma) < {R_{th}})

That is to say, if any small decoding error probability cannot be achieved for data of transmission rate R_th, then the system is in the terminal state. The ɛ-outage channel capacity is defined as the largest possible rate to make outage probability in Eq. (11) is less than. In other words, the channel terminal capacity is to meet Pr(R(γ) ≤ R_th) with the corresponding R_ɛ. However, maximise problem of transmission rate is just discussed with different power allocations due to the limit space issues.

In the NOMA system, each sub-carrier loads multiple users. However, to improve the system throughput and transmission rate, users pairing scheme needs to consider on each sub-band. According to the principle of NOMA, the greater of difference among the users’ channel condition, the greater the probability of pairing and the better the effect of pairing.

It can be learnt from previous studies that FPA does not consider the user's current channel gain, but only allocates power based on the fixed ratio. The computational complexity of this method is low, while the system performance is not very good. On the other hand, FTPA avoids these problems. The power allocated to each user is related to the channel gain. The calculation complexity of the above two power allocation algorithms is relatively low, but it is difficult to achieve the performance of FSPA. Here, we introduce a hierarchical pairing scheme that combines the sub-optimal power allocation method mentioned in the article.

4.1

Proposed algorithm description

It can be seen from formula (3) that received signal has eliminated the interference of high-power users to the current user during SIC. The current SINR of user n is only related to the power allocated by users n+1 to N and is not interfered by users with low SNR. In other words, the current SIRN is only interfered by users with high SNR. Therefore, the interference to the current user depends on the accumulated transmit power of all users in the upper layer and has nothing to do with how the power is allocated among the users. The process can be modelled using a tree-like structure. In addition, it can be seen from formula (3) that if we keep the sum of the power allocation ratios of users with high SNR constant. At the same time, it does not consider how the power is distributed among users. The interference to advanced users will be stable. This observation constitutes the basis for reducing computational complexity.

Here, an improved algorithm power allocation algorithm is introduced, which is called tree topology power allocation (TTPA) algorithm. The process can be modelled using a tree-like structure. The core idea of TTPA is to search and determine power distribution coefficient using layered. Due to the different channel gains, all users are ranked and located at different levels of tree-like structure. The specific implementation process can be described as follows.

Step 1: According to users’ channel gains, all users are placed in a tree model structure as shown in Figure 2. The user located at the top of the tree model has the worst channel gain, and the remaining users are sorted from low to high channel gain. Then the user placed at the bottom of the tree model has the best channel gain. Therefore, the number of multiplexed users in NOMA system is equal to the number of layers.

Step 2: Since all users are arranged in the tree structure in ascending order of channel gain, the power coefficient of the current layer is lower than the previous layer and larger than the latter. Therefore, all power allocation coefficients β should meet the following conditions 0<β1<1N 0 < {\beta _1} < {1 \over N} , βn-1≤βn≤1-∑i=1n-1βiN+1-n {\beta _{n - 1}} \le {\beta _n} \le {{1 - \sum\nolimits_{i = 1}^{n - 1} {\beta _i}} \over {N + 1 - n}} . For example, the candidate power allocation factors for the first layer users are {3/8,1/4,1/8}. The interval between these power allocation factors is denoted as Δ,Δ = 1/8.

Step3: Then, the system capacity of all the candidate nodes in each layer can be written as Rn=Bnlogn(1+SINRnpost) {R_n} = {B_n}\mathop {\log}\nolimits_n (1 + SINR_n^{post}) , where, SINRnpost=Pn|hn|2∑k=1n-1Pi|hi|2+In+Nn=βn|hn|2∑i=1n-1βi|hi|2+In+NnPtotal SINR_n^{post} = {{{P_n}|{h_n}{|^2}} \over {\sum\nolimits_{k = 1}^{n - 1} {P_i}|{h_i}{|^2} + {I_n} + {N_n}}} = {{{\beta _n}|{h_n}{|^2}} \over {\sum\nolimits_{i = 1}^{n - 1} {\beta _i}|{h_i}{|^2} + {{{I_n} + {N_n}} \over {{P_{total}}}}}} , I_N and N_N represent interference and noise, respectively;

Step 4: In each layer, system capacity at every node is calculated. The node with the highest rate is hunted as the surviving node. For instance, the power allocation factor β₁₃ in the first layer is selected as the starting point of the power allocation factor in the next layer. Then calculate the cumulative power allocation factor from the first layer to the current layer, which is denoted as Ω. Among the nodes with the same Ω, only the node with the largest current system capacity is selected as the initial value of the next layer allocation, such as the black dots of each layer in Figure 2. Remaining nodes are deleted. Repeat Step 3 to complete the judgement of the current level.

Step 5: From the previous steps, it can be seen that there is only one surviving node in each layer. Then, trace back layer by layer from the only surviving node in the fourth layer to the root of the tree. The final path is the best power allocation scheme for all multiplexed users. Finally, substituting the optimal power distribution coefficient into the system capacity formula, the capacity of the entire system channel can be obtained. For example, the final power allocation coefficient combination is {β₁₃,β₂₅,β₃₅,β₄₃} as in Figure 2. Multiplying the sub-band power by these allocation coefficients, the power allocated to each user can be obtained.

Fig. 2

The tree model selects the optimal node in each layer for power distribution, which can achieve global optimisation. Therefore, it has achieved the effect of FSPA. However, compared with FSPA, its calculation amount and complexity are greatly reduced. The algorithm steps are shown in Table 1.

Table 1

Algorithm of tree topology power allocation

1: Input: pre-processing SINRs of N users: set n=0, R = 0.2: Constructing and initialising the tree topology model; the number of multiplexed users in NOMA system is equal to the number of layers.3: Branch and node settings. Each branch represents the possible power allocation ratio for each user; each node corresponds to a possible power allocation ratio combination up to the nth layer.4: Intra-stage processing; for each node in the current stage, calculate the sum rate of each node in the current and previous stage. For each level, only keep the node with the largest sum rate. The other nodes are considered redundant and discarded to reduce computational complexity.5: Processing for the last stage. The branch number in level n equals to the number of nodes kept in stage N-1.6: For the last stage, βn equals to 1-∑i=1n-1βi 1 - \sum\nolimits_{i = 1}^{n - 1} {\beta _i} . The branch number in stage N equals to the number of nodes kept in stage N-1. The node which has the largest sum rate in each layer is considered to be the survival node.7: Trace back from the node which is determined in Steps 5 and 6, and then output the combination of power allocation ratio.

We consider a cell scenario centred on the BS and composed of several cellular users. Cellular users are evenly distributed in a circular coverage area with a radius of 50 m. We assume the channel of the wireless downlink is Rayleigh channel. In this case, the signal to be transmitted is an OFDM signal using NOMA mode. The number of multiplexed users in the NOMA system changed from 2 to 8. This article assumes that the user pairing has been completed under FTPA and FPA. The average capacity under different power allocation modes is researched.

Figure 3 shows the system capacity under different power allocation algorithms. The number of users changed from 2 to 8. It can be seen that the system capacity based on the proposed TTPA is significantly better than the FPA and FTPA algorithms. This advantage becomes more significant when the number of users increases. The analysis shows that the geometric average throughput of each surviving node is higher than any other node in the same layer with TTPA. Therefore, in actual transmission systems, this sub-optimal power optimisation algorithm can be used to improve system performance.

Fig. 3

The computational complexity of the exhaustive search and TTPA methods is compared in Figure 4. It can be seen that TTPA greatly reduces the computational complexity of power allocation greatly. When the number of users is equal to 4 and 5, the computational complexity of the TTPA method is only 1/100 and 1/1000 of the exhaustive search respectively.

Fig. 4

In this paper, a new method for allocating channel pairing and users’ power allocation in NOMA system of 5G is introduced. The optimisation of system capacity and power allocation was researched in this article. We also studied the constraint relationship between the total transmission power and the maximum system capacity when user's QoS is satisfied. The optimisation problem of the system had high computational complexity. FSPA allows for better performance but involves a higher degree of computational complexity. Although the FPA and FTPA algorithms are relatively simple, their performance is not so good. In view of this, this article proposes a TTPA. The TTPA algorithm places users with different channel gains in different positions in the tree structure, which keeps the node with the optimal system capacity in each layer and deletes the remaining nodes. The proposed algorithm has lower computational complexity and can achieve better system performance when meeting users’ QoS.