2010 IEEE 6th International Conference on Wireless and Mobile Computing, Networking and Communications

Scheduling and Resource Allocation for Multiclass Services in LTE Uplink systems
Oscar Delgado
ECE, Concordia University Montreal, Qc, H3G 1M8, Canada Email: o [email protected]

Brigitte Jaumard
CSE, Concordia University Montreal, Qc, H3G 1M8, Canada Email: [email protected]

AbstractWe propose two scheduling and resource allocation schemes that deal with Quality of Service (QoS) requirements in Uplink Long Term Evolution (LTE) systems. QoS for a multiclass system has been seldom taken into account in previous resource allocation algorithms for LTE uplink. In one of the new algorithms, we investigate the possibility of assigning more than one resource block and its consequences on satisfying stringent QoS requirements in the context of heavy trafc, either in terms of end-to-end delays or of minimum rates. System capacity and the number of effectively served requests are used as performance metrics. Numerical results show that it is possible to manage a multiclass scheme while satisfying the QoS constraints of all requests. Allowing the assignment of more than one resource block per request did not appear to be a meaningful advantage. Indeed, it is only useful when there is a heavy trafc, and some of the requests have stringent QoS requirements. But then, satisfying those requests can only be done at the expense of reducing the overall system capacity and of limiting the number of users who can be served. Index TermsScheduling, QoS, Fair, LTE, Uplink, Delay.

I. I NTRODUCTION Long Term Evolution (LTE) technology allows the development of high performance cellular mobile systems that aim to offer a secure all IP-based network architecture with high data rates, providing various services such as, e.g., voice, streamed multimedia, gaming services, data with low-latency. The 3rd Generation Partnership Project (3GPP) has dened Orthogonal Frequency Division Multiple Access (OFDMA) as the access technique for the downlink and Single Carrier FDMA (SC-FDMA) for the uplink. SC-FDMA is a pre-coded version of OFDM that does not have the drawback of normal OFDM, i.e., a very high peak to average power ratio (PAPR). SC-FDMA solves the PAPR problem by requiring that the resource blocks assigned to a user must be adjacent. Doing so, it reduces the need for linearity, and power consumption in the power amplier; improving the coverage and the celledge performance. To efciently take advantage of SC-FDMA in LTE Uplink, designers must devise scheduling and resource allocation algorithms that consider the contiguous Resource Block (RB) allocation constraint while maximizing the throughput and ensuring fairness among all users. LTE also aims at providing Quality of Service (QoS) for multiple types of trafc. For that reason, nine Quality of service class identiers (QCI) have been dened in the

standard [1]: four GBR (Guaranteed Bit Rate) ones and ve non-GBR ones. Although some work has been done on LTE scheduling, most of the studies focus on downlink, and only a few on the uplink scheduling. Most of them deal without considering a multiclass trafc scenario, i.e., voice, video, and data. In [2], Lee et al. adapt the time domain proportional fair algorithm to the LTE uplink scheme, and from there they derive some algorithms. In their simulation results, the authors show that similar results can be obtained when maximizing the logarithm of the utility function and when maximizing the ratio of the instantaneous throughput to the total throughput. In [3], Qian et al. developed a resource block allocation algorithm for multi-service downlink LTE systems and deduce from it a scheduling algorithm that takes advantage of the queue state information in the data-link layer and the channel state information in the physical layer. Results were analyzed in terms of average user throughput and number of satised users. In [4], Petersen et al. present a comprehensive study of the many resource allocation techniques available for LTE downlink. The quality of service is outlined as being one of the main objectives to maximize the system capacity while serving all users according to their minimum QoS requirements. It is also shown how the radio resource management algorithm at the base station offers opportunities for efcient designs due to the easy access to air interface measurements. Many scheduling and resource block schemes have been proposed in the literature [5], [6]. Few of them incorporate the QoS constraints for multiclass services in LTE Uplink [3], [7]. In this paper, we propose two novel resource allocation algorithms for multiclass services. Our solution takes into account the minimum throughput, and the maximum allowed delay of each request. The resource allocation algorithm adapts dynamically to the number of requests in the system, assigning resources with as much as fairness as possible. The paper is organized as follows. In Section II, we present an optimization formulation of the scheduling and resource allocation problem for LTE uplink systems, in the context of QoS requirements, with the possibility of assigning more than one resource block to a request (while satisfying the resource block continuity requirements). In Section III, we propose two new channel dependent scheduling algorithms, which take into

978-1-4244-7742-5/10/$26.00 2010 Crown

355

account the QoS requirement. Experiment results are presented and analyzed in Section IV. Conclusions are drawn in the last section. II. O PTIMIZATION P ROBLEM F ORMULATION In this section, we dene the resource allocation problem as a constrained utility maximization problem in the context of a Single-Cell SC-FDMA subject to delay and rate constraints, in the context of a trafc with different class of services. Let RB be the set of resource blocks and be the set of requests. We assume that there are different classes of services. Let be the index set of classes, with generic index . Any given request belongs to a given class of service with specic delay and rate requirements, i.e., maximum delay min delaymax and minimum rate (throughput) for all requests of class . For a given request , we further denote by RB the set of resource blocks allocated to request , by the instantaneous transmission power of request , by max the maximum transmission power, by its achievable throughput, and by the class of service it belongs to. We now describe the mathematical model, for a given TTI (Transmission Time Interval), starting by its objective. The maximization of the request utilities can be written as follows: max ( RB ) (1)

one was not, all subsequent blocks are either all selected, or once one is not selected, the subsequent blocks of this latter block are not selected. The second constraint (6) does not allow more than one decrease, and therefore guarantees that as soon as a block is not selected while the previous one was, all subsequent blocks cannot be selected. Constraints (7) ensure, similarly to (2), that each request is assigned to at most one resource block. Lastly, we express the constraint that each request cannot exceed the maximum allowable delay and that its throughput cannot be smaller than the minimum throughput allowed for each request, depending on its class of service: delay delaymax
min

, = , = ,

(9) (10)

where is the class index of request . To provide a proportional fairness the sum of the utilities is often replaced by the sum of the logarithmic utility functions. Hence, we can either use max or max

( RB ) = max

RB

(11)

where ( ) is the utility of request as a function of the throughput , for a given allocation of blocks RB to request . The block resource allocation corresponds to the following set of allocations: , = 1 RB (2)
max 0

ln ( RB ) = max

RB

, ln( ) (12)

(3)

where , = 1 if resource block is allocated to request . Constraints (2) express the condition that each resource block can only be allocated to a single request during one TTI. Constraints (3) convey the power limitations of each user. In order to guarantee the resource block contiguity constraints, we use the following constraints:
+ +1, = , + , , + ,

where ln represents the natural logarithm, and RB = { RB : , = 1}. Note that users are not necessarily all scheduled during a given TTI if not enough resource blocks are available, or if the number of available resource blocks vs. the number of users does not allow the satisfaction of the quality of service (QoS) requirements for all users. Another way to maximize this proportional fair objective (see [8], [9]) is to use: , (13) max
RB

RB, RB, RB

(4) (5) (6) (7) (8)

RB

+ 1 + , 1; , 1
RB + ,

where is a proportion dened as follows delaymax = min delaymean mean and delay is the average delay of class : delaymean = delay .
class

(14)

= 1;

+ , , ,

, = 1

{0, 1}, , {0, 1} RB

Constraints (4) detect whether there is an increase or a decrease of the value of , when compared to +1, taking into account that, due to constraint (5), there cannot be a decrease at the same time than an increase. The rst constraint (6) does not allow more than one increase, and therefore guarantees that once a block is selected while the previous

Although seeking to maximize the general objective in (12) or (13) is equivalent, we will use the approach as dened in (13) since when using the proportional fair scheduling metric instead of the typical proportional fair metric allows giving more priority to the delay requirement to requests that are closer to the maximum delay or to the minimum throughput requirement. Another point of interest is that using such an objective leads to a much more scalable integer linear programming (ILP) problem. However, in the context of real time requirements, it might not be scalable enough; this is the reason why we focus on heuristics in the next section.

356

III. S CHEDULING A LGORITHM In this section, we propose two new scheduling algorithms for LTE Uplink systems, called Single Channel Scheduling Algorithm (SC-SA) and Multiple Channel Scheduling Algorithm (MC-SA) in the context of multiple class trafc. Consequently, both heuristics guarantee the throughput and delay requirements of each request according to its own QoS characteristics (multiple classes of trafc). While the SCSA heuristic allows the assignment of at most one channel block per request and per TTI, independently of its QoS requirements, the second heuristic allows the assignment of more than one channel block per request. The packet scheduling is done as a one step algorithm that combines time-domain (TD) scheduling and frequencydomain (FD) scheduling by selecting the request which will be multiplexed in time and frequency with the same metric, as explained in the next sub-sections. When the number of requests is smaller than the maximum number of resource blocks, both algorithms equally distribute the available RBs among the requests in the cell. This is not necessarily the fairest way to distribute the resource blocks. However, there is no necessity to devise a complex resource block share among the requests in such a case. A. Single channel scheduling algorithm (SC-SA) The SC-SA algorithm dynamically adapts each request throughput to the cell load while trying to meet the multiclass QoS requirements. Algorithm 1 describes in detail the allocation scheme in the SC-SA algorithm. After the initialization phase, in which the scheduler captures the necessary information from the UE (User Equipment), the value of the metric is calculated for every request . During the rst iterations, the scheduler assigns RBs in sequential order as long as it does not have accurate information on the delay or rate performances for the requests (we indeed start from scratch in our simulation) After a few iterations, there are enough information in the system to execute the algorithm with the QoS concerns. In case the number of requests is smaller than the total number of available RBs, the scheduler distributes proportionally the remaining RBs among all the requests. If the number of requests is higher than the total number of available RBs, the scheduler takes the requests that are experiencing the poorest performance and assign them a RB. Finally, once the allocation is performed, the system updates all the relevant parameters. Note that the system adjusts itself in order to match the QoS target. The aim of the SC-SA allocation scheme is to allocate more RBs to requests experiencing the worst (most stringent QoS) conditions, than the ones which have a higher performance. This results in an increased system capacity. The underlying assumption in the SC-SA algorithm is that the channel, in a steady-state, will have a similar behavior over consecutive RBs.

Algorithm 1 SC-SA 1: {Initialization} 2: RB set of unassigned resource blocks delay 3: Dene = { : } 4: Sort the values of in ascending order. 5: for all do delay 6: = 0 if delay delaymax and , 1 otherwise min 7: = 0 if , and , 1 otherwise 8: end for 9: 1 10: while RB = do 11: if < then 12: Let = / 13: Assign the channels in order so that adjacent channels are assigned to the last 1 requests in 14: Assign the remaining adjacent channels to the rst request in 15: else 16: Set to the index of the th value of 17: Assign to request 18: end if 19: RB RB { assigned in previous step} 20: + 1 21: end while

B. Multiple channel scheduling algorithm (MC-SA) The MC-SA algorithm consists of allocating more than one resource block to the requests that are not meeting the throughput target. The reason for allocating multiple RBs to a single request is in order to help the requests such that the average throughput transmitted within one TTI is smaller than the throughput target. Note that a block being made of 12 subcarriers, the delay requirement can always be met using only one single resource block during one TTI. MC-SA uses the same metric value to assign RBs as the SC-SA algorithm for ordering the requests according to their QoS requirements, but a different strategy for assigning blocks, and in particular for deciding how many blocks should be assigned. Algorithm 2 describes in detail the MC-SA allocation procedure. Its initialization phase is identical to the one in the SC-SA algorithm. In addition, MC-SA have a similar behavior as SC-SA when the number of requests is smaller than the total number of available RBs. If the number of requests is higher than the total number of available RBs, the scheduler takes the requests that are experiencing the poorest performance according to metric and try to assign RB RBs. To do this, it nds the RB that maximizes the throughput and then looks for the adjacent block (left and right) that has better throughput and repeating this procedure until RB RBs are assigned to that request. Finally, once the allocation is performed, the system updates all the relevant parameters.

357

Note that neither the MC-SA, nor the SC-SA are efcient scheduling algorithms for the case when the number of requests that require high throughput is high, as if they cannot handle all requests if the total requirements exceed the capacity of the system, it is up to the admission control strategy to administer the available resources. Algorithm 2 MC-SA 1: {Initialization} 2: RB set of unassigned resource blocks delay 3: Dene = { : } 4: Sort the values of in ascending order. 5: for all do delay 6: = 0 if delay delaymax and , 1 otherwise min 7: = 0 if , and , 1 otherwise 8: end for 9: 1 10: while RB = do 11: if < then 12: Let = / 13: Assign the blocks in order so that adjacent blocks are assigned to the last 1 requests in 14: Assign the remaining adjacent blocks to the rst request in 15: else 16: Set to the index of the th value of min 17: if / < 1 then min 18: Find RB = / 19: Find the channel block that = arg max ( ) 20: Assign RB consecutive best channel blocks around on RB to request 21: else 22: Assign the channel block such that max { ( ) : RB } to request 23: end if 24: end if 25: RB RB { assigned in previous step} 26: + 1 27: end while

is equally subdivided among all sub carriers allocated to the mobile in each TTI. For the throughput calculations we consider that the data rate is upper bound by the Shannons formula log2 [1 + , ] , (15) =

where is the SNR gap and is the set of subcarriers assigned to request (generic index ). For a practical MQAM system and the theoretical limit based on Shannon capacity [10], is given by: = 1.5 . ln(5 ) , , 2 (16)

The SNR over a single subcarrier, , , is given by: , = (17)

where , is the channel gain over subcarrier allocated 2 to user , is the noise power, and , is the transmit power, assumed to be subdivided equally among all subcarriers assigned to a user . Hence , [dB] = 10 log10 , + 10 log10 , (18) where is the propagation loss chosen to be 128.1 dB, is the distance from the mobile user to the base station, is the path loss exponent set to 3.76, is the log normal shadowing with an 8dB standard deviation, and is the Rayleigh fading, with a Rayleigh parameter such that [ 2 ] = 1. All the parameter denitions in (15), (17) and (18) have been expressed assuming subcarrier granularity, and can be easily deduced for resource block granularity, e.g., , , . (19) , = 2 RB

IV. P ERFORMANCE E VALUATION In this section, we present numerical results to study the performance of our two new proposed algorithms. A. Simulation Model The simulation model consists of a single cell equipped with an omnidirectional antenna using SC-FDMA uplink based on 3GPP LTE system model. The throughput is averaged over 1000 TTIs; the duration of one TTI is 1 msec. The total bandwidth considered is B = 5MHz, subdivided into 25 RBs of 12 sub carriers. All mobile users are assumed to transmit at the maximum power considered to be 125mW; the power

Table I summarizes a list of the default simulation parameters and assumptions. To simplify the analysis without loss of generality, we consider three service classes (ex. voice, video and web). The trafc model settings are given in Table II, and the trafc distribution is shown in Table III. Requirements of packet delays are considered as one fth of the end to end packet delays in Table II. We consider a very demanding class to force the system to assign more than one RB to a request, we use the value of video as the standard denition television. B. Simulation Results Results reported in this section have been conducted with the parameters described in the previous subsection. We analyze the performance of the algorithms in terms of throughput and delay to asses the quality of their scheduling and resource block allocation. In Fig. 1 we show the ratio of the average satised users versus the total number of users in the system. Note that although we are assigning resources to all users, not all are meeting the QoS requirements.

358

TABLE I S IMULATION PARAMETERS Parameter System Bandwidth Subcarriers per resource block Number of Resource Blocks Trafc model Transmission Time Interval Number of users in cell Noise power per Hz Channel model Type of system User maximum power Available MCSs Simulation time Setting 5MHz 12 25 Innitely backlogged 1ms 10, 20, 30, 40, 50, 60, 70 160dBm Urban Single cell 125 mW M-QAM 10000 TTIs

requirement by assigning more than one RB, while SC-SA is not able to fulll the video call throughput requirements since it only assigns at most one RB per TTI.

TABLE II Q O S R EQUIREMENTS Services Voice Video Web Delay budget 100 ms 150 ms 300 ms Rate budget 64Kbps 3Mbps 128Kbps Packet loss rate 102 103 106

As we can see from the simulation result, algorithm MC-SA has around 5% better performance than SC-SA, this difference is mainly due to the video requests that are the ones which consume more bandwidth and need more than one RB in a given TTI.

Fig. 2.

Average video throughput

Fig. 3 and Fig. 4 show the average voice throughput and average web throughput as a function of the total number of requests in the system. In this case, both algorithms satisfy the throughput requirement, even though MC-SA has slightly lower performance; this is because MC-SA uses this throughput to satisfy the video call demand.

Fig. 1. Number of Users in the system vs. number of users effectively served

Fig. 2 shows the average throughput of video calls versus the total number of requests in the system. It can clearly be seen from the gure that MC-SA satises the throughput
Fig. 3. TABLE III
TRAFFIC DISTRIBUTION

Average voice throughput

Services Voice Video Web

Distribution 50% 10% 40%

Fig. 5 shows the average delay of each class versus the total number of requests in the system. It can be seen from the gure that MC-SA and SC-SA meet the maximum allowed delay. One important thing we can point out is that in order to meet the video requirements, both systems assign resources

359

Fig. 4.

Average web throughput

Fig. 6.

Average voice delay

to video calls at every TTI, nevertheless MC-SA is the only one which guarantees the minimum throughput.

services (voice, web); as compared with a SC-SA system that only assigns one resource block per TTI to a given request. Nevertheless MC-SA outperforms SC-SA by enabling to operate with higher demands of throughput, and maintaining the basic QoS requirements for all admitted requests. R EFERENCES
[1] Evolved Universal Terrestrial Radio Access (E-UTRA) and Evolved Universal Terrestrial Radio Access Network (E-UTRAN), Overall description, 3GPP Technical Specication Group Radio Access Network, December 2008, 3GPP TS 36.300 v.8.7.0. [2] S.-B. Lee, I. Pefkianakis, A. Meyerson, S. Xu, and S. Lu, Proportional fair frequency-domain packet scheduling for 3GPP LTE uplink, in IEEE Annual Joint Conference of the IEEE Computer and Communications Societies - INFOCOM, 2009, pp. 2611 2615. [3] Y. Qian, C. Ren, S. Tang, and M. Chen, Multi-service qos guaranteed based downlink cross-layer resource block allocation algorithm in LTE systems, in International Conference on Wireless Communications Signal Processing, 13-15 2009, pp. 1 4. [4] K. Pedersen, T. Kolding, F. Frederiksen, I. Kovacs, D. Laselva, and P. Mogensen, An overview of downlink radio resource management for UTRAN long-term evolution, IEEE Communications Magazine, vol. 47, no. 7, pp. 86 93, july 2009. [5] H. Yang, F. Ren, C. Lin, and J. Zhang, Frequency-domain packet scheduling for 3GPP LTE uplink, in IEEE Annual Joint Conference of the IEEE Computer and Communications Societies - INFOCOM, March 2010, pp. 1 9. [6] E. Yaacoub and Z. Dawy, Centralized and distributed LTE uplink scheduling in a distributed base station scenario, in International Conference on Advances in Computational Tools for Engineering Applications - ACTEA, July 2009, pp. 11 15. [7] G. Mongha, K. Pedersen, I. Kovacs, and P. Mogensen, QoS oriented time and frequency domain packet schedulers for the UTRAN long term evolution, in IEEE Vehicular Technology Conference (VTC), May 2008, pp. 2532 2536. [8] M. Andrews, L. Qian, and A. Stolyar, Optimal utility based multi-user throughput allocation subject to throughput constraints, in IEEE Annual Joint Conference of the IEEE Computer and Communications Societies - INFOCOM, vol. 4, March 2005, pp. 24152424. [9] H. Kushner and P. Whiting, Convergence of proportional-fair sharing algorithms under general conditions, IEEE Transactions on Wireless Communications, vol. 3, pp. 1250 1259, July 2004. [10] X. Qiu and K. Chawla, On the performance of adaptive modulation in cellular systems, in IEEE Transactions on Communications, vol. 47, no. 6, 1999, pp. 884 895.

Fig. 5.

Average voice delay

Fig. 6 shows that if we do not consider the delay as part of metric we can reach he maximum delay sooner. V. C ONCLUSION In this paper, we developed two Resource Allocation and Scheduling algorithms for handling multiclass QoS in LTE Uplink systems. The Resource Allocation assigns RBs in a fair way such that the throughput and delay are adaptively adjusted according to the trafc load. System performance was evaluated using simulations. Results show that although assigning more than one resource block as in MC-SA helps to serve requests with higher throughput requirements, it also has a negative effect by reducing the throughput of the other

360