Research On NOMA Downlink User Selection Algorithm Subject To Access Limit,Power Budget,and Rate Demands

Non-Orthogonal Multiple Access（NOMA）technology is a key technology of the 5th Generation Mobile Communication System（5G）.The NOMA system greatly improves the spectral efficiency of the channel by using superposition coding technology.However,superimposing a large number of users on a channel results in larger decoding delay and error propagation.This paper studies the user selection problem on NOMA downlink channels and proposes three user selection algorithms under the constraints of access limits,power budgets,and rate demands.Among them,the access limit refers to the maximum number of users that can be superimposed on a single channel.The main work of this paper is as follows:Firstly,the user selection problem is modeled and analyzed.The research content of this paper is proposed through the model of NOMA downlink system,which makes the user choice problem concrete.This paper mathematically models the user selection problem and analyzes the constraints on user selection,i.e.access limits,power budgets,and rate demands.Then this paper verifies the NP-completeness of the user selection problem.The expression of the objective function is deduced by applying the relaxation strategy,and it is proved that the function has the property of submodularity,so that the problem is modeled as a submodular maximization model,which lays the foundation for the design and analysis of the approximation algorithm.Secondly,three user selection algorithms are proposed.（1）User selection algorithm based on branch and bound.From the perspective of the exact solution,a user selection algorithm based on branch and bound is proposed.The algorithm takes the solution of the greedy algorithm as the lower bound,and the local optimal solution as the upper bound,which can reach the maximum total system rate.（2）Relaxed greedy algorithm.Since the user selection problem is an NP-complete problem,to further reduce the complexity of the algorithm,from the perspective of an approximate solution,based on the simple greedy algorithm,a relaxation strategy is introduced,and then a relaxed greedy algorithm is proposed.（3）Improved relaxed greedy algorithm.Since the relaxed greedy algorithm has extraction loss during user selection,the partial enumeration technique is used to improve it and an approximation algorithm based on partial enumeration is proposed.Finally,the performance of the algorithm is verified.For the approximation algorithm proposed in this paper,through theoretical analysis,the performance ratio of the relaxed greedy algorithm is ₂¹（7）1-1/e（8）,where e is the base of the natural logarithm;the performance ratio of the improved relaxed greedy algorithm is（7）1-1/e（8）,which is the classical constant value for designing approximation algorithms based on submodular functions.This paper compares and simulates several algorithms such as the user selection algorithm based on branch and bound,the greedy algorithm,the traditional enumeration algorithm,the relaxed greedy algorithm,and so on.The result shows that the user selection algorithm based on branch and bound can obtain the maximum total rate of the NOMA downlink channel,which is suitable for the scene with a small problem scale and the pursuit of an accurate solution;the improved relaxation greedy algorithm has low complexity and can obtain an approximate optimal solution,which is suitable for the scene with large problem scale and the pursuit of obtaining an approximate optimal solution in a short time.