On User Pairing in Uplink NOMA

User pairing in non-orthogonal multiple-access (NOMA) uplink is investigated considering some predefined power allocation schemes. The base station divides the set of users into disjunct pairs and assigns the available resources to these pairs. The combinatorial problem of user pairing to achieve the maximum sum rate is analyzed in the large system limit for various scenarios, and some optimum and sub-optimum algorithms with a polynomial-time complexity are proposed. In the first scenario, 2 M users and the base station have a single-antenna and communicate over M subcarriers. The performance of optimum pairing is derived for M -> infinity and shown to be superior to random pairing and orthogonal multiple access techniques. In the second setting, a novel NOMA scheme for a multi-antenna base station and single carrier communication is proposed. In this case, the users need not be aware of the pairing strategy. Furthermore, the proposed NOMA scheme is generalized to multi-antenna users. It is shown that for the considered power allocation scheme, random and optimum user pairing perform similarly in the large system limit, but optimum pairing is significantly better in finite dimensions. It is shown that NOMA with the proposed user pairing scheme outperforms a previously proposed NOMA with signal alignment.