A joint optimization scheme of resource allocation in downlink NOMA with statistical channel state information①

XU Lei (徐 磊)， LI Weifeng， YAO Yijing， CHANG Jing， FANG Hongyu， LI Xiaohui

(School of Electronics and Information Engineering， Anhui University， Hefei 230039， P.R.China)

Abstract In a real communication scenario， it is very difficult to obtain the real-time channel state information (CSI) accurately，so the non-orthogonal multiple access (NOMA) system with statistical CSI has been researched. Aiming at the problem that the maximization of system sum rate cannot be solved directly， a step-by-step resource allocation optimization scheme based on machine learning is proposed. First， in order to achieve a trade-off between the system sum rate and user fairness， the system throughput formula is derived. Then， according to the combinatorial characteristics of the system throughput maximization problem， the original optimization problem is divided into two subproblems， that are power allocation and user grouping. Finally， genetic algorithm is introduced to solve the sub-problem of power allocation， and hungarian algorithm is introduced to solve the subproblem of user grouping. By comparing the ergodic data rate of NOMA users with statistical CSI and perfect CSI， the effectiveness of the statistical CSI sorting is verified. Compared with the orthogonal multiple access (OMA) scheme， the NOMA scheme with the fixed user grouping scheme and the random user grouping scheme， the system throughput performance of the proposed scheme is significantly improved.

Key words: non-orthogonal multiple access (NOMA)， channel state information (CSI)， user grouping， power allocation， throughput

0 Introduction

Non-orthogonal multiple access (NOMA) technology has recently attracted tremendous attention due to its simple design and superior spectrum efficiency，which is recognized as a promising multiple access scheme in the next generation mobile communication networks[1]. By splitting multiple users via different transmission power， superposition coding ( SC)，adopted by NOMA，will introduce interference information， so successive interference cancellation (SIC) is required at receiver side to realize multi-user detection[2]. Much of the existing work about NOMA has assumed that the perfect channel state information (CSI)at transmitter side， which are nearly impractical for many communication scenarios. Therefore， it is of great significance to investigate the resource optimization of downlink NOMA system with statistical CSI.

Recently， some literature has investigated the resource optimization problem in NOMA system with statistic CSI. In Ref.[3]， the performance of two NOMA system with partial CSI has been evaluated. The research results show that statistical CSI based on second order statistics is always better than the incomplete CSI based on feedback， and the system performance with statistical CSI is similar to that with perfect CSI， in the case of low signal to noise ratio (SNR). The power allocation scheme of the NOMA system was investigated in Ref.[4]， and a sub-optimal power allocation algorithm was proposed. Genetic algorithm dynamically allocates power in a group， but the design of user grouping scheme is neglected. In Ref.[5]， a dynamic power allocation scheme and a user grouping algorithm were proposed， users are divided into two sets according to their statistic CSI， and the users， in different sets and with the same sort number， were matched into one group. This grouping method is simple to implement， but it cannot guarantee the overall performance of the system. And this literature proves that the performance of the NOMA system is proportional to the difference in statistical characteristics between users within the same group. In Ref.[6]， a low complexity power allocation sub-optimal solution and a user scheduling scheme were proposed based on a hierarchical clustering algorithm. Energy efficiency is used as the evaluation index， and the near-optimal performance can be achieved.

The aforementioned literature all considers user grouping and power allocation separately. But in fact，user grouping and power allocation are intertwined with each other[7]. Since multiple users are admitted simultaneously， when the number of users is large， the complexity of the SIC receiver in the NOMA system is very high. As a result， it may not be realistic to ask all users in the system to perform NOMA jointly，a promising alternative is to construct a hybrid multiple access system， in which， NOMA is combined with orthogonal multiple access (OMA)[8]. The users in the system are divided into multiple groups， where NOMA is implemented within each group and different groups are allocated with orthogonal resources. Obviously， the performance of the NOMA system is very dependent on which users are grouped together and the power allocation between users[9]. Therefore， effective user grouping and power allocation schemes can provide feasibility for improving the performance of the downlink NOMA system with statistical CSI.

Therefore， based on the user channel difference and the correlation between power allocation and user grouping， combined the advantages of genetic algorithm and Hungarian algorithm in the field of resource optimization， a joint optimization scheme with controllable complexity is proposed in this paper， in which， it is assumed that the transmitter only knows the statistical CSI related to each user. According to the combinatorial characteristics of the system throughput maximization problem， the original optimization problem is divided into two sub-problems， that are power allocation and user grouping. Combined the advantages of genetic algorithm in solving the non-convex problems and the low-complexity characteristics of Hungarian algorithm in solving the matching problem， genetic algorithm is introduced to solve the sub-problem of power allocation， and Hungarian algorithm is introduced to solve the subproblem of user grouping.

The symbols used in this paper are defined as follows.E(·) represents the mean operator，f(·) andF(·) represent the probability density function(PDF) and the cumulative distribution function(CDF)， respectively. AndUrepresents the uniform distribution.

1 System model

In this paper， a single-cell downlink multi-user system is considered， which adopts the hybrid multiple access scheme. A base station (BS) is located in the center of the cell.Nusers are randomly distributed in the cell， and both the users and BS are equipped with a single antenna. The users are divided intoLgroups，and each group containsKlusers， which satisfies

NOMA is implemented within each group and different groups are allocated with orthogonal resources to eliminate inter-group interference， and some intragroup interference can be eliminated by SIC.

Without loss of generality， the widely used Rayleigh fading channel for communication is adopted，which is affected by the joint effect of large-scale fading and small-scale fading. The channel model can be expressed as

whereΩndenotes the large-scale fading coefficient between usernand BS， expressed asΩn=E(|hn|2). It is assumed that BS only has statistical CSI related to each user，i.e.，BS knows the value ofΩfor all users.

In order to simplify the derivation of the problem，thel-th group withKlusers is mainly analyzed， so the signal received by thek-th user in thel-th group can be expressed as

wherePdenotes the transmitting power allocated by BS to each group， and it is assumed that the transmission power allocated by BS to each group is equal.hl，kdenotes the instantaneous channel related to thek-th user in thel-th group.xl，kdenotes the transmitted message intended for thek-th user in thel-th group.al，kdenotes the intra-group power allocation factor allocated to thek-th user in thel-th group.zl，kdenotes independent and identically distributed additive white Gaussian noise， which is subject tozl，k～CN(0，σ2).Without loss of generality， it is assumed that the users are sorted in the ascending order of statistic CSI， i.e.，Ωl，1＜Ωl，2＜… ＜Ωl，K. According to the principle of NOMA， it can be concluded that the power allocation factor satisfiesal，1>al，2>… >al，K. The second term in Eq.(4) is caused by the user’s intra-group interference， which can be partially eliminated by the SIC receiver. According to the optimal SIC decoding order under the statistical CSI proposed in Ref.[10]， the decoding order of the SIC within the group is (1，2，…，Kl)， which is the increasing order of channel gain.The user detection model is shown in Fig.1.

Fig.1 User detection model

Ideally，in the case ofj＜k＜m，thek-th user will detect the message ofj-th user， and then remove the message from its received in a successive manner. The message ofm-th user will be treated as noise at thek-th user. Therefore， the instantaneous data rate of thek-th user in thel-th group is expressed as

2 Performance analysis

Since the analysis of outage probability and ergodic data rate requires the density function of channel，the widely used Rayleigh fading channel for communication is adopted. Therefore， the PDF and the CDF of unsorted channel gain are given as follows.

2.1 Ergodic data rate

In order to compare the impact of statistical CSI and perfect CSI on the performance of the NOMA system， based on Eq.(5) and Eq.(9)， the ergodic data rate formula of userkcan be derived.

2.2 Outage probability

Based on Eq.(10) and Eq.(15)， the user outage probability expression of the NOMA system with statistical CSI can be obtained as

2.3 Throughput

In general， there are mainly two category of methods for optimizing the performance in communication systems. One is to maximize the achievable sum data rate， and the other is to guarantee the fairness of users[13]. On the one hand， to maximize the sum data rate， BS tends to allocate more power to users with high channel gains， which may cause users with low channel gains to be outage. On the other hand， the fairness among the users may result in the performance loss of the achievable sum data rate. In order to achieve a trade-off between achievable sum data rate and user fairness， it is considered to maximize the achievable sum data rate while guaranteeing the minimum rate requirement of each user. Therefore，throughput is adopted to characterize rate performance.Throughput combines rate performance and fairness，which is defined as the sum of target data rate of each user multiplied by its successful transmission probability[14]， expressed as

3 Resource allocation optimization scheme

As analyzed in subsection 2.3， in order to realize the trade-off between system achievable sum data rate and user fairness， throughput is adopted to characterize rate performance in this paper. Therefore， the problem of maximizing system throughput can be expressed as

where the constraint conditionC1is the total transmit power constraint， and the power allocated to each group should be non-negative. The constraint conditionC2is the power allocation factor constraint for each group. The constraint conditionsC3andC4represent the NOMA principle constraints.

The solution used to maximize system throughput in Eq.(22) is not only affected by the power allocation factor， but also depends on that， which users can be allocated to the same group. In many of the existing work， users are grouped directly according to their channel condition， and then power is allocated to users within each group. However， the inherent relationship between power allocation and user grouping is ignored.Therefore， a joint resource allocation optimization algorithm is proposed. According to the combinatorial characteristics of the system throughput maximization problem， the solution to the Eq.(22) can be divided into two stages. In the first stage， based on any pairwise grouping of users， an improved genetic algorithm is used to allocate power to maximize intra-group throughput within each group. In the second stage， based on the results of the first stage， Hungarian algorithm is used to determine the user grouping set， which can maximize the system throughput.

3.1 Power allocation based on improved genetic algorithm

Under the arbitrary and fixed user grouping schemes， it is assumed that transmission power allocated to each group is equal. Therefore， the problem of maximizing system throughput in Eq.(22) can be divided into multiple problems of maximizing intra-group throughput.

Since the objective function is non-convex， exhaustive search for the optimal solution results in heavy complexity， which is hard to accomplish in practice.Therefore， genetic algorithm is adopted for power allocation.

Genetic algorithm is based on natural selection and genetic theory， which combines the survival of the fittest in the process of biological evolution with the random information exchange mechanism of chromosomes within the population. Genetic algorithm abandons the traditional search method， simulates the biological evolution process in nature， and uses artificial evolution to search the target space randomly. Firstly，it regards the possible solution in the problem domain as an individual or chromosome of the group， and encodes each individual into a symbol string form. Then，it simulates the biological evolution process of Darwin’s genetic selection and natural elimination， and iterative operations selection， crossover and mutation based on genetics are performed on the population. Finally，each individual is evaluated according to the predetermined target fitness function，and a better group can be continuously obtained according to the evolutionary rules of survival of the fittest. At the same time， the global parallel searcher is used to search for the optimal individual in the optimization group and the optimal solution that meets the requirements[15].

In the traditional genetic algorithm， parameters of the three operators of selection， crossover and mutation are fixed， which may lead to the destruction of the optimal individual， and result in the non-convergence of the evolutionary process， so the performance of genetic algorithm can be severely restricted. In addition， in the later stage of evolution， the diversity of individuals in the population is greatly reduced， and the fitness values are close to each other， which leads to the algorithm approaching the state of random search.

In order to alleviate the above problems， the mutation probability of the individual is determined dynamically according to the fitness value of the individual， and the crossover method is changed. The mutation probability of the individuals with high fitness is reduced to prevent the damage of good genes， and the mutation probability of the individuals with poor adaptability is improved by introducing new genes into the population. After determining the male parent and the female parent， multiple nodes are selected for multiple crossover， and the two best ones are selected from the results to be inherited to the next generation. The improved algorithm is described as follows.

(1) Initializes population numberSand the maximum generationGmax， and randomly generatesSindividuals expressed by a binary string of lengthNBSplaced in the initial populationQ(0).

(2) Takes the system throughput expression in Eq.(22) as the fitness function， and computes the fitness valuefof each individual.

(4) Firstly，selects and mutates the individuals in the populationQ(G).Then， randomly selects two individuals， crossovers them multiple times according to the crossover probabilityPc. Finally， selects the best two individuals from the offspring individuals to obtain the next populationQ(G+1).

(5) IfG＜Gmax， goes to Step (2)， else， stops and gets the individual with greatest fitness as the solution.

The optimal solution output， obtained according to the above steps， is the solution of the objective function in Eq.(22)， that is the power distribution coefficient of the user.

3.2 User grouping based on Hungarian algorithm

It should be noted that in 3GPP LTE advanced，two users are selected for performing NOMA[16]， and the number of users in each groupKlcannot be too large due to the complexity of SIC. Therefore， the user grouping method for the case ofKl=2 is investigated.The user grouping problem can be expressed as

Since channel differences have a direct impact on the performance of system throughput， users are divided into two sets based on the statistical CSI，denoted asV1andV2.Specific steps are as follows.

(1) Detect the value of statistical featureΩof users in the cell， and users are sorted in the ascending order ofΩ.

(2) Take usern(n=ffloor(N/2)) as the boundary and divide users into two setsV1andV2， whereffloor(·) means rounding to the left.

If the total number of usersNis even， the numbers of users inV1andV2are equal. IfNis odd， the first user inV2is taken out as a user group， and then a user is selected from setV1and setV2respectively to form a two-user group. After the above processing， the channel differences between users within the same group can be enlarged， which can improve the performance gain of NOMA system. However， the arbitrary matching of users in the two sets cannot guarantee the system throughput performance. Considering the impact of power allocation on user grouping， the user grouping problem can be transformed into a one-to-one matching problem between user setsV1andV2for sake of maximizing system throughput. Taking advantage of the low complexity feature of Hungarian algorithm in solving the matching problem， Hungarian algorithm is introduced to solve Eq.(24).

Hungarian algorithm is one of the classic algorithms for bipartite graph matching in graph theory. Its application background is to solve the problem of twodimensional task allocation， and it involves two concepts， namely bipartite graph and augmenting-path.Bipartite graph is a special model in graph theory. LetA=(B，C) be an undirected graph. If the vertexBcan be divided into two disjoint subsets (B1，B2)，and the two verticesiandjassociated with each edge(i，j) in the graph belong to these two different vertex sets， soAis called a bipartite graph. For augmentingpath， letMbe the set of matched edges in the bipartite graphA. IfXis a path connecting two unmatched vertices in the graphA， the edges belonging toMand the edges not belonging toMappear alternately onX， thenXis an augmenting-path relative toM. The basic idea of Hungarian algorithm is to exchange the matching and non-matching edges in the augmenting-path by searching for the augmenting-path， so that there will be one more matching edge until no augmenting-path is found.

Solving Eq.(24) by Hungarian algorithm can be further expressed as selectingWelements from theW×W(W=ffloor(N/2)) matrix shown in Eq.(25) for maximizing their sum， and any of theseWelements are not on the same row and the same column. The selected element denotes the maximum intra-group throughput obtained when usersiandjare allocated to the same group.

In order to prove the effectiveness of the proposed grouping method， genetic algorithm is also used in all comparison schemes. In terms of algorithm complexity，the time complexity of the exhaustive search isO(N!).The time complexity of Hungarian algorithm used in this paper mainly comes from the sorting process，which isO(W2+Wlog2W)， and the time complexity of the fixed matching scheme used in Ref.[5] isO(Wlog2W).The time complexity of the proposed scheme is slightly higher than that of the fixed matching scheme， but much lower than the exhaustive search scheme， so it is still feasible even under a huge number of users.

4 Simulation results and analysis

The system simulation adopts Monte Carlo method and assumes that the number of users in each group is 2， and the power allocated to each group is equal. The comparisons of ergodic data rate with perfect CSI and statistical CSI is shown in Fig.2.

Fig.2 Comparison of ergodic data rate of NOMA users with statistical CSI and perfect CSI

As can be seen from Fig.2， there is a certain gap between systems using statistical CSI and perfect CSI.In this paper， the users are sorted in the ascending order of statistic CSI， so the gap between the statistical CSI and the perfect CSI is reduced. It is proved that statistical CSI is more feasible in practical applications. In Fig.2， user 1 and user 2 represent the user with poor channel and good channel in a group respectively. When the power allocation factor allocated to user 1 is less than 0.9， the ergodic data rate of user 2 is always much higher than that of user 1. When the power allocated to user 1 is small， user 1 may be outage due to the constraint of minimum rate requirement，so the fairness of weak users cannot be guaranteed.However， when the power allocation factor of user 1 exceeds 0.9， the ergodic data rate of user 2 will decrease rapidly， which will affect the overall system rate performance， this is consistent with the result analyzed in subsection 2.3.

The simulation parameters in Fig.3 are as follows.SNR=20 dB，the statistic CSIΩand the target rateRthof users are generated by the system， which is subject toΩ～U(0，5) andRth～U(1，5) respectively. In genetic algorithm， the number of individuals in the population isS=40，the length of binary string isNBS=20，the maximum generationGmax=100， the initial set of crossover probability and the mutation probability arePc=0.7 andPm=0.05 respectively. As can be seen from Fig.3， compared with the traditional OMA system， NOMA system can significantly improve the system throughput. For further comparison， genetic algorithm is used in all schemes to allocate power to users.It can be seen that，the gap between the random grouping scheme and the fixed user grouping scheme is always small， and the fixed grouping scheme proposed in Ref.[5] has achieved the largest channel difference.It is demonstrated that the increasing of the channel difference between users can improve the system throughput， but the advantage brought by the channel difference is reduced after the user power allocation within the group. The symtem throughput of joint optimization scheme proposed in this paper is obviously better than that of the random grouping scheme and fixed grouping scheme in Ref.[5]. As the number of user group served by BS increases， the advantages of the proposed scheme are more obvious than other schemes.That is， the proposed optimization scheme is more suitable for the scenario with a large number of user.

Fig.3 Trend of system throughput with the number of users

The simulation parameters of Fig.4 are as follows.the number of users isN=12， the statistic CSIΩ，the target rateRthof users and the parameters of genetic algorithm are consistent with Fig.3. It can be seen from Fig.4 that， in low SNR region， the system throughput of these schemes are similar to each other. The reason is that the user data rate is low and outage probability is high due to the too low SNR. In high SNR region，the transmitting power is allocated to stronger users as much as possible under the constraint of NOMA principle. The system throughput of proposed grouping scheme is close to that of the fixed matching grouping scheme. However， in practical applications， the SNIR is generally in range of 10 -20 dB. In this case， the system throughput of joint optimization schemes proposed in this paper are better than that of the other three schemes. Compared with TDMA scheme， random grouping scheme and the fixed grouping scheme， the system throughput of the proposed scheme can be improved by about 9 bps/Hz， 2.1 bps/Hz， and 2 bps/Hz， respectively.

Fig.4 Trend of system throughput with the SNR

5 Conclusions

A joint optimization scheme of resource allocation is proposed in this paper based on joint genetic algorithm and Hungarian algorithm. Users are sorted in the ascending order of statistic CSI， so the performance of NOMA system with statistical CSI can further approach the NOMA system with perfect CSI. The closed-form formula of each user’s outage probability is derived，and the outage performance and the achievable sum data rate are analyzed. Then throughput is adopted to characterize system performance. For the sake of maximum system throughput， a joint optimization design of genetic algorithm and Hungarian algorithm is carried out. Simulation results verify the effectiveness of the proposed scheme in improving the performance of system throughput.