A Low Computational Complexity Power Allocation Algorithm Based on Greedy Policy

In the non-orthogonal multiple access (NOMA) system, the power allocation algorithm at the transmitter plays a key role in the throughput performance. However, the Full Search Power Allocation (FSPA) algorithm is difficultly applied to the practical system due to its unacceptable computational complexity, although it can achieve the optimal performance. By combining the principle of the successive interference cancellation receiver, this paper proposes a novel power allocation algorithm based on greedy policy, whose main idea comes from the principle of the local optimal discrimination in greedy algorithm. The goal of this algorithm is to maximize the total throughput performance of the system. Its detailed structure can be presented in the form of tree. Starting from the root of the tree, we begin perform the power allocation, local throughput judgment, and optimal branch reservation layer by layer. After that, the only surviving path from the tail node to the first node is the final allocation result. It is proven that the proposed greedy strategy satisfies the principle without aftereffect and the obtained final power allocation is globally optimal. As the simulation results show, under the case that the total throughout of this algorithm has less than 1.5% difference from the one of full space search, the complexity is successfully decreased from the exponential growth with the number of users to the linear growth. Moreover, compared with other suboptimal algorithms, this algorithm also shows advantages of different degrees.