Scheduling in LTE and LTE-Advanced

Scheduling the Uplink

LTE uplink scheduler acts as part of the LTE radio resource management functionalities to utilize the available radio resources within the physical uplink shared channel (PUSCH) as efficiently as possible, while satisfying the QoS requirements for active users within the network. Due to the configuration of the radio interface employed in LTE uplink, the uplink scheduler performs user multiplexing in both, time and frequency domains to the available resource blocks (RBs) within 1 TTI. The LTE uplink scheduler designs that have been proposed in literature so far perform scheduling per TTI according to the following phases:

1. UE Selection: The first phase of the scheduling operation is to select a subset of the UEs that await transmission to be scheduled for a current TTI. The selection process occurs either by a round robin fashion, a proportional fair criteria, or based on QoS attributes (bit rate, delay, etc.), buffer size, or a combination of these attributes. In a QoS-aware LTE uplink scheduler, the QoS attributes of each scheduler plays an important role in the UE selection process. Since the scheduling process is engaged once every TTI with no consideration for how the bandwidth is to be distributed among the selected UEs, the UE selection can be associated with the Time Domain (TD) scheduling, and be separated from the frequency allocation.
2. UE-Frequency Multiplexing: Once the set of UEs to be scheduled are selected, the scheduler distributes the available RBs among the selected UEs. In channel dependent scheduling (CDS), the scheduler exploits the variations of the selective-fading channels to allocate each group of RBs to a UE with the best channel conditions over these RBs. Hence, the multiplexing of UEs over the available radio resources is termed Frequency-Domain (FD) scheduling.

LTE uplink scheduling can be described as a queuing-based operation. The TD-scheduler provides a priority metric to each UE according to a certain criterion. As a result, the UE gets added to a queue based on its assigned priority. The scheduler then selects a subset of UEs with the highest priority from the UE's priority queue. The number of UEs to be selected per TTI depends on the choice of scheduler's implementation. However, it is usually restricted by the resources available in the PDCCH that can be used to communicate resource grants to these UEs simultaneously. The availability of PDCCH resources varies depending on the LTE downlink control channel status and configuration.

For QoS scheduling, TD metrics that are associated with the UEs can be made as QoS-aware metrics, where a per-UE TD metric can be based on either the GBR of the uplink traffic, the delay, or both.

The FD scheduler performs dynamic scheduling to allocate UEs to a portion of the frequency bandwidth based on the uplink channel quality between the UE and the BS. Similar to the TD scheduler, the FD scheduler performs metric calculations per UE. However, in the case of CDS, the FD scheduler assigns a metric weight for each RB, per UE. The RB metric value depends primarily on the channel condition for the RB of each UE. The FD metric can be based on the CSI, which is the SINR of a RB, or on an estimated achievable throughput of a UE at a specific RB.

The process of calculating both TD and FD metrics for each UE at each RB is defined as the utility function. A utility function is the metric to optimize whatever parameters the LTE system needs to perform at a desired level. The most common objectives that a utility function needs to optimize are spectral efficiency, aggregated throughput, fairness, and QoS guarantee.

The authors of [13] evaluated and categorized the scheduling algorithms currently proposed in literature into three categories based on the method of RB allocation. The first group of scheduling algorithms performs RB allocation with fairly-equal-sized RB groupings. The scheduler divides the available RBs into contiguous chunks, where each chunk represents a contiguous RBs group. Each Resource Chunk (RC) has almost the same number of RBs, where the total number of RCs is set to be the number of UEs. In case the number of RBs is less than the number of UEs, then each RC is set to have only 1 RB. Once RCs are created, the scheduler assigns each RC a metric that is based on an aggregation method chosen by the scheduler (e.g., by summing the RB metrics within the RC, or finding their average).

The authors of [13] studied the performance evaluation of round robin algorithm and a maximum SNR (MAXSNR) [14]. The difference between the two is that latter effectively considers the channel condition within the scheduling decision.

The second group of algorithms performs RB allocation using first maximum search algorithms. Such algorithms perform scheduling according to the following generalized steps:

1. Find the UE-RB with the maximum metric.
2. Allocate the RB to corresponding UE.
3. Expand on currently allocated RB to adjacent RBs for current UE, until an RB is found whose maximum metric belongs to another UE.
4. Allocate the current RB to the new UE if it does not violate the contiguity of resource allocation; otherwise, allocate it to the previous UE.
5. If all UEs are allocated RBs, and there are still RBs left unassigned, allocate the unassigned RBs to the same UEs based on contiguity.

The scheduling algorithms chosen to represent this group are the Greedy algorithm [15], Heuristic Localized Gradient algorithm [16] and First Maximum Expansion (FME) algorithm [17] and its two extensions, Modified FME (M-FME) [17] and Recursive maximum Expansion (RME) algorithm [17]. FME performs RBs allocation using first maximum search algorithm to choose one UE with the maximum utility, while extension of FME chooses the first two UEs with the maximum utility. The RME removes UEs, which are already allocated RBs that have maximum metric associated with these UEs and runs a recursive of the maximum metric on the remaining RBs.

The third group of scheduling algorithms is the global-metric driven algorithms. Rather than starting with the UE-RBs with the maximum algorithm, the algorithms find the UE-RB allocations provide a maximum global metric. The algorithms find a combination of possible allocations, and select the one with maximum global metric. For example, a UE-RB with the highest sum of metrics of UE-RB pairs among the examined combinations.

The algorithms of this category either work on individual RBs, or assign them in RC. Unlike the schedulers of the first group, the globally driven algorithms can either create RCs to be fairly equal in sizes, or RCs sizes that are independently set based on some system criteria. The following steps describe the general steps taken by such algorithms:

1. For each RB or RC, find the UEs with the first maximum metrics.
2. Determine the possible combinations of resource allocations using the selected UEs for each RB, or RC, and construct a search tree.
3. Select the optimal allocation pattern by finding the search tree branch with the maximum, or minimum, weight such that it maximizes the utility function.

Proportional Fair Binary Search Tree (PF-BST) algorithm [15] and Minimum Area Difference (MAD) algorithm [17] are the two algorithms evaluated as an example of this group.

The performance evaluation measures used in [13] are the throughput and the spectral efficiency. The performance evaluation results show that the above mentioned algorithms exhibit comparable performance irrespective of their category. Given the fact that, the RME algorithm entails comparable performance to the other algorithms but distinguished by the least complexity, the authors concluded that the RMS performance is promising as it indicates that acceptable performance can be achieved at low processing requirements.

Scheduling the Downlink

The work presented in [18] investigated multiple packet scheduling algorithms originally proposed for single carrier downlink transmission and good candidates for use in LTE. The authors studied the usability of these algorithms for the implementation of downlink LTE transmission. The algorithms are selected with the aim of maximizing throughput along with fairness. The algorithm studied is the maximum rate (Max-Rate) [19] algorithm, which priorities users with the highest reported instantaneous downlink SNR values. This algorithm maximizes the network throughput. However, it results with low fairness performance. The RR [20] algorithm is chosen to study the performance of LTE scheduler if the fairness is the main objective to achieve. RR is simple in implementation and provides for fairness by allocating an equal share of transmission times to each user. It is obvious that the RR algorithm while meeting the fairness measures it performs poorly when maximizing the throughput is the objective. The authors of [18] studied the performance of Proportional Fair (PF) [21] algorithm to provide a balance between throughput and fairness. The proportional fairness algorithm keeps track of the average data rate of the user over a predefined window. Users are prioritized based on the ratio of their instantaneous attainable data rate to their average data rate in attempt to maximize throughput along with fairness. The above algorithms do not count for the delay requirements of users. Hence, the authors included the Maximum-Largest Weighted Delay First (M-LWDF) [22] in the study to investigate the support of real time applications with delay constraints. The algorithm incorporates the head of line packet delay with the PF mechanism discussed above to prioritize users, hence, strike a balance between low packet loss, fairness and throughput. The exponential/proportional fair (EXP/PF) [23, 24] algorithm schedule real and nor-real time applications users. Real time users receive a higher priority than non-real time users when their head-of-line packet delays are approaching the delay deadline. The simulation environment consists of one cell and 80–120 users constantly moving at speeds between 1- 100 km/h in random directions. The performance evaluation is carried out with one application under investigation in the network, video streaming. The authors claim based on their simulation results that the M-LWDF algorithm outperforms other packet scheduling algorithms by providing better fairness and higher throughput which allows accommodating larger number of users.