Graph-Theoretical Dynamic User Pairing for Downlink NOMA Systems

We propose a novel graph-theoretical dynamic user pairing strategy based on the user rate requirements in cellular networks employing non-orthogonal multiple access (NOMA). The proposed approach relies on first constructing a conflict graph corresponding to all possible user pairings and then reformulating the problem of finding the best user pairs as that of finding the maximum weighted independent set (MWIS) on the conflict graph. This formulation turns the originally NP-hard problem into one that can be solvable in polynomial time thanks to the claw-freeness property of the conflict graph. The proposed user pairing method satisfies the maximum number of user demands with optimal network sum-rate as shown theoretically and as validated by the simulation results.