  User pairing in Non-Orthogonal Multiple-Access (NOMA) uplink based on channel
state information 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, $2M$ users and
the base station have a single-antenna and communicate over $M$ subcarriers.
The performance of optimum pairing is derived for $M\rightarrow \infty$ 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 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 the
proposed NOMA scheme outperforms a previously proposed NOMA scheme with signal
alignment.
