A Fair Downlink Scheduling Algorithm for 3GPP LTE Networks

Published Online May 2013 in MECS

The Third Generation Partnership Project (3GPP) has standardized Long Term Evolution (LTE) / System Architecture Evolution (SAE) in Release-8 to build the framework for 3G evolution towards 4G. The motivation for 3G evolution came from the growing demand for network services such as VoIP, web browsing, video telephony, and video streaming, with constraints on delays and bandwidth requirements. LTE aims to support all the applications with better performance at reduced cost, besides maintaining seamless mobility [1-6]. LTE is an all-IP packet based system with design targets of supporting high peak data rates of 100Mb/s in the downlink (DL) and 50 Mb/s in the uplink (UL), low latency (10ms round-trip delay), improved system capacity and coverage [7, 8]. To achieve the performance objectives, LTE employs the several enabling technologies which include Orthogonal Frequency Division Multiple Access (OFDMA) [9], Single Carrier Frequency Division Multiple Access (SC-FDMA) [10] and Multiple Input Multiple Output (MIMO) [11]. LTE technology uses air interface based on OFDMA for downlink and SC-FDMA for uplink. The LTE operates in both Time Division Duplexing (TDD) and Frequency Division Duplexing (FDD) modes and can be deployed in a range of channel bandwidths up to 20MHz.

The QoS provisioning has been an important issue in the mobility management of wireless networks [12-17]. To provide QoS in wireless networks, the Radio resource management (RRM) plays a crucial role in managing the limited radio resources effectively [18]. The Packet Scheduler is an entity of RRM in LTE that resides in the MAC layer of eNodeB [19-22]. It is responsible for the allocation of shared radio resources among the mobile User Equipments (UEs). The scheduler assigns resources to users with the granularity of resource blocks (RBs) every TTI, based on the channel condition feedback received from UEs in the form of Channel Quality Indicator (CQI).

This paper focuses on Downlink scheduling in LTE. Several scheduling strategies have been proposed in the literature [23-35]. In Round Robin scheduling algorithm, the UEs are assigned the resources in round-robin fashion, without taking into account channel conditions. The Max C/I (or Best CQI) algorithm allocates the resource blocks to the UEs with highest CQI on RB during a TTI [1]. Round-Robin algorithm offers fairness with respect to time to all UEs, but it is less efficient with respect to throughput because it doesn’t take into account channel variations. The Best CQI algorithm is efficient, but it is not fair to all users. The UEs, such as those at the cell edges, which face bad channel conditions, will always not get RBs allocated. Hence such users always starve of radio resources, which is practically not acceptable. So, fairness should also be taken into account along with focus on spectral efficiency. In [33], the proposal for the fair scheduling algorithms is made, in which RB allocation is done to all chosen UEs in a TTI, selecting

UEs one after another starting from the one with highest CQI onwards in order. Once a UE gets RB, it is not assigned further till other users are assigned RBs or till the RBs are free within a TTI. This paper proposes a novel scheduling algorithm based on the one proposed

Figure 1: LTE air interface elements.

in [33] and explores the possibility of improving overall throughput of the cell, besides maintaining fairness to users. The performance of the algorithm is investigated using a MATLAB based LTE link level simulator from Vienna University [36].

The rest of the paper is organized as follows. The section II deals with the framework for LTE Downlink scheduling. The section III discusses the proposed algorithm for LTE Downlink scheduling. The simulation results are discussed in section IV. Finally, section V concludes the paper.

• II.    LTE Downlink Scheduling

• A.    LTE Downlink Air Interface

The LTE downlink air-interface employs Orthogonal Frequency Division Multiplexing (OFDM) together with advanced antenna techniques and adaptive modulation and coding (AMC) to achieve better spectral efficiency, which enables operators to transfer more data per MHz of spectrum at lower cost-per-bit. OFDM is a multicarrier transmission scheme, in which the available bandwidth is divided into multiple narrow sub-carriers and data is transmitted on these sub-carriers in parallel streams. Each sub-carrier is then modulated using different levels of modulation such as QPSK, 16-QAM and 64-QAM. OFDM has the benefits of robustness against frequency selective fading, superior spectral flexibility, bandwidth scaling, and efficient receiver architecture.

The resource allocation in LTE is done in time/frequency domain. The LTE air interface elements are shown in Fig. 1. In time-domain, the DL channels in air interface are divided into Frames of 10 ms each. A frame consists of ten Subframes, each of 1 ms. Each subframe interval is referred to as Transmission Time Interval (TTI). Each subframe consists of two Slots of 0.5ms. In frequency domain, the total available system bandwidth is divided into sub-channels of 180 kHz, with each sub-channel comprising of 12 consecutive equally spaced OFDM sub-carriers of 15 KHz each. A timefrequency radio resource spanning over 0.5 ms slots in the time domain and over 180 KHz sub-channel in the frequency domain is called Resource Block (RB). Each RB carries OFDM symbols and the number of symbols per RB depends upon cyclic prefix being used (typically 6 or 7). The number of resource blocks in the available bandwidth is called Resource grid. Resource Element (RE) represents one OFDM subcarrier during one OFDM symbol interval. The number of RBs in a resource grid depends on the size of the bandwidth. The LTE operates in the bandwidth of 1.4 MHz up to 20 MHz, with number of RBs ranging from 6 to 100 for bandwidths 1.4 MHz to 20 MHz respectively, as shown in Table I [37].

Table I. LTE Bandwidth and RB Specifications

Bandwidth(MHz)	1.4	3	5	10	15	20
Number of RBs	6	15	25	50	75	100
Number of subcarriers occupied	72	180	300	600	900	1200

• B.    LTE Downlink Scheduling Framework

Multi-user Packet-scheduling plays a vital role in the distribution of available radio resources among the active users in order to ensure QoS needs of users. In order to counteract the time-varying and frequency-selective nature of the wireless channel, the scheduler needs to allocate resources (on per RB basis) to appropriate UEs which have good channel conditions based on the selected metric, every TTI. The metric is used as transmission priority of each UE on each RB, and is defined based on channel quality, status of transmission queues, buffer state, QoS requirements and resource allocation history. Packet schedulers are deployed at eNodeB and they allocate resources with a granularity of one TTI and one RB in time and frequency domain respectively. In order to perform channel-aware packet scheduling, each eNodeB need to have the knowledge of Channel State Information (CSI) for each user, for all the RBs in the available bandwidth. The CSIs are derived based on channel gain, interference conditions and Signal to interference noise ratio (SINR) estimation errors.

Figure 2: LTE Packet scheduler framework in RRM

The LTE packet scheduling task comprises of two subtasks: Time-domain packet scheduling (TDPS) and Frequency-domain packet scheduling (FDPS) as shown in the Fig. 2 [30]. TDPS identifies UEs that can transmit in the next TTI, taking into considerations input from HARQ manager, which provide the set of UEs that need to retransmit in a specific TTI. In order to improve the spectral efficiency of the system, FDPS tries to allocate each RB to appropriate UE such that the value of M sum is maximized in eqn. (1).

M sum = ∑ M(i, j) x A(i, j) (1)

where M(i, j) is the channel aware metric of i ^th UE for j ^th RB. A(i, j) = 1 or 0, if i ^th UE is allocated j ^th RB or otherwise respectively. The channel aware metric values M(i, j) for different users on different RBs is shown in Fig. 3 [30].

	RB,	RB:		RB.
UE,		M,2			Mu
UE,	M 21	M 2.2			Mu
	■ .
UEn	Mm	Mn2			Mn,m
Figure 3: Metric values for each user and each RB

The design of LTE downlink scheduler is a complex process and it poses a number of challenges such as -maximization of system capacity, ensuring fairness to all users, QoS provisioning, reducing complexity etc. A good scheduler should be capable of exploiting fast variations in channel conditions, besides maintaining fairness between the users. The proposed scheduler aims at uniform distribution of resources among users to ensure fairness, and at the same time maximize the overall system capacity within a cell.

• III.    The Proposed Downlink Scheduling Mechanism

In this section, a new algorithm New-SCH Algorithm for DL scheduling is proposed, which is based on the method proposed in [33]. The new algorithm makes use of Assignment Model of Operations research [38] for UEs to RBs mapping during each TTI. This technique improves the overall throughput performance of the cell, while maintaining fairness in the resource allocation among the users. The details of New-SCH Algorithm are given in Algorithm 1, which outlines the steps involved in DL scheduling during each TTI.

The algorithm presumes that each eNodeB gets channel feedback information in the form of CQI-feedback Matrix , of the size equal to (No. of UEs x No. of RBs in a TTI), for all TTIs. The proposed algorithm in time-domain selects UEs to be scheduled during each TTI taking into consideration about fairness. In frequencydomain, it maps UEs to appropriate RBs, such that the net throughput performance of the cell is optimized, besides maintaining fairness. The Assignment Model used in this algorithm maps UEs to RBs during each TTI, such that the net cost of the assignment in CQI-feedback Matrix is maximized. This enables improvement in throughput performance, besides maintaining fairness.

Algorithm 1. New-SCH Algorithm

• 1.    Obtain the Channel information for different UEs in the form of CQI-Feedback Matrix , for current TTI.

• 2.    Choose the users to be scheduled during current TTI, giving preference to those users which were less scheduled and not scheduled in previous TTIs.

• 3.    Map Users to RBs during current TTI, using Assignment Model so that the cost of allocation in CQI-Feedback Matrix is maximized.

• 4.    Schedule the Users during the current TTI.

• 5.    Repeat the above steps for each TTI.

• IV.    Results and Discussions

• A.    Simulation Parameters

The implementation of the new scheduling algorithm, New-SCH Algorithm is done using a MATLAB based LTE link level simulator from the Vienna University [36], that implements standard compliant LTE downlink. It can carry out simulations in single-downlink, single-cell, multi-user and multi-cell scenarios. The simulator enables emulation of all the transmission features between Base station and UEs.

The simulations are carried out for frequency-selective channels modeled by ITU for Pedestrian-B (Ped-B) channels. Simulations are performed for 6, 15 and 25 users, choosing the bandwidths of 1.4, 3 and 5 MHz respectively. A single cell, multi-user scenario is chosen for simulation. The simulation parameters used are listed in Table II.

Table II. Simulation Parameters

Parameter	Value
Number of Base stations	1
Channel type	Pedestrian-B
Scheduling Algorithms	Best CQI, Round-Robin, New-SCH Algorithm, MS-Algorithm
Number of UEs	6, 15, 25
Bandwidth (in MHz)	1.4, 3 , 5 MHz
Simulation length	100 Subframes
Transmission Mode	SISO

• B.    Simulation Results and Discussions

The performance evaluation of the proposed scheduling algorithm based on simulation results is explained in this section. The performance is measured in terms of the overall cell throughput and Block Error ratio (BLER). The simulation results of the New-SCH Algorithm are compared with Round Robin, Best CQI and MY_SCH- algorithms (or MS Algo ) proposed in [33]. The performance analysis of individual users in terms of individual user throughput is done to study distribution of

Throughput, 100 Subframes, 0 Re-tx, SISO 1.4 MHz, 6 Users, PedB,

(a)

(b)

Figure 4: (a) Cell throughput (b) BLER for 6 users, BW= 1.4 MHz radio resources among users in different scheduling techniques.

The overall cell throughput and BLER plots for different conditions: 6 users at 1.4 MHz, 15 users at 3 MHz and 25 users at 5 MHz bandwidths (BW) are shown in Fig. 4, 5 and 6 respectively. In all the cases, it is observed that the New-SCH Algorithm shows good throughput performance closer to that of the Best-CQI, compared to other algorithms. There has been the improvement in the throughput in case of New-SCH algorithm, without costing much in BLER performance, at different SNRs.

The throughput performances of 6 users operating with selected bandwidth of 1.4 MHz, at SNRs ranging between 0-40 dBs, in different scheduling algorithms is shown in Fig. 7. While the Best-CQI method offers best throughput performance, it is least in case of Round Robin method. The fairness in the distribution of resources among all the UEs, by each of the scheduling algorithm can be observed by the amount of variations in users throughput performances at different SNRs. The throughput fluctuations are more among users in case of Best CQI method, which indicates that it is less fair in the

Throughput, 100 Subframes, 0 Re-tx, SISO 3.0 MHz, 15 Users, PedB,

(b)

Figure 6: (a) Cell throughput (b) BLER for 25 users,

BW=5.0 MHz

(a)

BLER

(b)

Figure 5: (a) Cell throughput (b) BLER for 15 users,

BW=3.0 MHz

distribution of resources among UEs. The lesser variations among the throughputs of different users, in case of MS-Algorithm and New-SCH algorithm indicates better fairness in the allocation of resources. It is seen from the plots that New-SCH algorithm provides an optimal performance in terms of throughput and fairness, when compared with other scheduling techniques.

0.18

Throughput, 100 Subframes, 0 Re-tx, SISO 5.0 MHz, 25 Users, PedB,

(a)

Round Robin:Throughput, 100 Subframes, 0 Re-tx, SISO,1.4 MHz, 6 Users, PedB

0.16

0.14

0.12

0.1

0.08

0.06

0.04

0.02

25      30      35      40

---•-- user1

---•--  user2

---е--- user3

---•--- user4

---•--- user5

---•--- user6

SNR [dB]

(a)

Throughput [Mbps] Throughput [Mbps]                                                          ^{g p     p}

Best CQI:Throughput, 100 Subframes, 0 Re-tx, SISO,1.4 MHz, 6 Users, PedB 0.45

0.4

0.35

0.3

0.25

0.2

0.15

0.1

0.05

---•--- user1

---•-- user2

---•-- user3

user4

---•-- user5

user6

15      20      25

SNR [dB]

(b)

MS Algo:Throughput, 100 Subframes, 0 Re-tx, SISO,1.4 MHz, 6 Users, PedB 0.35

--•-- user1

0.3

0.25

0.2

0.15

---•--- user2

---•-- user3

---•--- user4

---•-- user5

user6

New-SCH Algo:Throughput, 100 Subframes, 0 Re-tx, SISO,1.4 MHz, 6 Users, PedB 0.35

SNR [dB]

(d)

Figure 7: User througputs for (a) Round Robin (b) Best CQI (c) MS-Algorithm (d)New-SCH Algoritm

The bar graph of Fig. 8 shows the individual throughput performances of 6 users operating with 1.4 MHz bandwidth, at a constant SNR of 40 dB. The figure shows that the New-SCH Algorithm provides userthroughput performance closer to that of Best CQI method compared to other scheduling techniques. The

0.1

0.05

0                _____________С_____________Е_____________Е_____________Е_____________Е_____________Е_____________Е

0       5      10      15      20      25      30      35      40

SNR [dB]

(c)

Figure 8: Throughputs of different users for different scheduling algorithms at SNR=40.

lesser fluctuation in the throughputs among users in New-SCH Algorithm is indicative of its ability to distribute resources to all users in a fair manner.

• V. Conclusions

3GPP LTE network is intended to deliver high speed data and multimedia services to next generation mobile users. LTE downlink scheduling, an entity of RRM, plays a vital role in the allocation of shared radio resources among UEs. The scheduler needs to address the tradeoff that exists between throughput performance and fairness among users. This paper proposed a novel DL scheduling algorithm using Assignment Model , which effectively maps UEs to RBs during each TTI. The proposed algorithm is simulated and the results are compared with three different scheduling algorithms available in literature. The performance of the new algorithm is investigated in terms of throughput and BLER to analyze its performance at both cell-level and user level. The simulator results show that the new algorithm balances well between throughput and fairness.