Multi-User Scheduling in the 3GPP LTE Cellular Uplink

[ptt3i]

In this paper, we consider resource allocation in the 3GPP Long Term Evolution (LTE) cellular uplink, which
will be the most widely deployed next generation cellular uplink. The key features of the 3GPP LTE uplink (UL)
are that it is based on a modified form of the orthogonal frequency division multiplexing based multiple acess
(OFDMA) which enables channel dependent frequency selective scheduling, and that it allows for multi-user
(MU) scheduling wherein multiple users can be assigned the same time-frequency resource. In addition to the
considerable spectral efficiency improvements that are possible by exploiting these two features, the LTE UL
allows for transmit antenna selection together with the possibility to employ advanced receivers at the basestation,
which promise further gains. However, several practical constraints that seek to maintain a low signaling
overhead, are also imposed. In this paper, we show that the resulting resource allocation problem is APX-hard
and then propose a local ratio test (LRT) based constant-factor polynomial-time approximation algorithm. We
then propose two enhancements to this algorithm as well as a sequential LRT based MU scheduling algorithm
that offers a constant-factor approximation and is another useful choice in the complexity versus performance
tradeoff. Further, user pre-selection, wherein a smaller pool of good users is pre-selected and a sophisticated
scheduling algorithm is then employed on the selected pool, is also examined. We suggest several such user
pre-selection algorithms, some of which are shown to offer constant-factor approximations to the pre-selection
problem. Detailed evaluations reveal that the proposed algorithms and their enhancements offer significant gains.

Keywords: Local ratio test, DFT-Spread-OFDMA uplink, Multi-user scheduling, NP-hard, Resource allocation,
Submodular maximization.