# Multiuser Scheduling on the Downlink of an LTE Cellular System

Authors: Raymond Kwan; Cyril Leung; Jie Zhang
Journal: Research Letters in Communications
 (2008)

---

## Abstract

The challenge of scheduling user transmissions on the downlink of a long-term evolution (LTE) cellular communication
system is addressed. In particular, a novel optimalmultiuser scheduler is proposed. Numerical results show that the
system performance improves with increasing correlation among OFDMA subcarriers. It is found that only a limited
amount of feedback information is needed to achieve relatively good performance. A suboptimal reduced-complexity
scheduler is also proposed and shown to provide good performance. The suboptimal scheme is especially attractive
when the number of users is large, in which case the complexity of the optimal scheme is high.


---

## Body

## 1. Introduction

Orthogonal
frequency division multiplexing (OFDM) is a multicarrier modulation technique
that has been adopted in a variety of modern communication systems such as the
digital subscriber lines (DSLs), wireless local area networks (WLANs), the
Worldwide Interoperability for Microwave Access (WiMAX) [1], and long-term evolution
(LTE) cellular networks. In order to exploit multiuser diversity and to
increase flexibility in scheduling, orthogonal frequency division multiple
access (OFDMA), in which multiple users can simultaneously share the
subcarriers, is employed. The problem of power and subcarrier allocation in
OFDMA systems has been the subject of much research (see [2, 3], and references therein).In practice, due to limited
signalling resources, subcarriers are allocated collectively. For example, on
the downlink in LTE, subcarriers are grouped into resource blocks (RBs) of 12
adjacent subcarriers with an intersubcarrier spacing of 15 kHz [4, 5]. Each RB has a time slot
duration of 0.5 milliseconds, which corresponds to 6 or 7 OFDM symbols.
(The actual value depends on whether an extended or
normal cyclic prefix is used.) The smallest
resource unit that a scheduler can assign to a user is a scheduling block (SB),
which consists of two consecutive RBs, spanning a subframe time duration of 1
millisecond [4, 5]. The main issue to be addressed is how SBs are to be
allocated to users, given that the channel qualities for the set of SBs
associated with each user are different. Some studies on LTE-related scheduling
have been reported in [6, 7]
and the references therein.One constraint in LTE downlink scheduling is
that all SBs belonging to a single user can be assigned to only one modulation
and coding scheme (MCS) in each transmission time interval (TTI) or scheduling
period [4, page 326].
(This applies in the non-multiple-input-multiple-output (MIMO) configuration. For the MIMO
configuration, a maximum of two different MCSs can be used for data belonging
to two different transport blocks.) The durations
of a TTI and SB are equal. To the best of our knowledge, the impact of this
restriction on LTE scheduling has not been previously studied. In this paper,
the challenging problem of multiuser scheduling is examined, taking into
account this restriction.


## 2. System Model

In the time
domain, each SB consists of a number,Nsb,
of OFDM symbols. Let L be the total number of subcarriers and Ld(ν)≤L be the number of data-carrying subcarriers for
symbol ν,
where ν=1,2,…,Nsb.
Also, let Rj(c) be the code rate associated with the MCS j∈{1,2,…,J}, Mj be the constellation size of the MCS j and Ts be the OFDM symbol duration. Then, the bit
rate, rj,
that corresponds to a single SB is given by(1)rj=Rj(c)log⁡2(Mj)TsNsb∑ν=1NsbLd(ν).LetU be the number of simultaneous users, and Ntot be the total number of SBs that are available
during each TTI. In addition, let 𝒩i be a subset of the Ntot SBs whose channel quality indicator (CQI)
values are to be reported by user i;
the size of 𝒩i is denoted by Ni.
It is assumed that the Ni highest SB CQI values are fed back. Such a
limited feedback scheme requires a smaller bandwidth albeit at the cost of a
degraded system performance. We also assume that the total available power is
shared equally among the users. As noted in [8, 9], the throughput degradation resulting from such an
assumption is small when adaptive modulation and coding (AMC)
is used, as is the case in LTE.Letxi,n,⁢n=1,2,…,Ni be a real scalar or vector reported (via a
feedback channel) by user i to indicate the collective channel qualities
of all the subcarriers within the nth reported SB.
(The exact nature of xi,n depends on the feedback method
adopted.) Furthermore, let qi,max(xi,n)∈{1,2,…,J} be the index of the highest-rate MCS that can
be supported by user i for the nth SB at CQI value xi,n,
that is, qi,max(xi,n)=arg⁡max⁡j(Rj(c)log⁡2(Mj)∣xi,n).
Due to frequency selectivity, the qualities of the subcarriers within a SB may
differ; the indicator xi,n should provide a good collective
representation of the qualities for all the subcarriers within the nth SB [10–12]. For convenience, we assume that the MCS rate Rj(c)log⁡2(Mj) increases monotonically with j, and that the rate of MCS 1 is zero. SBs whose CQI values are not reported
back are assigned to MCS 1.As mentioned earlier, in a non-MIMO configuration, all
SBs scheduled for a given user within the same TTI must use the same MCS. If
MCSj is to be used for user i,
then only certain SBs can be assigned to the user. For example, suppose Ni=4,
and(2)1≤qi,max(xi,2)<qi,max(xi,1)<qi,max(xi,3)<qi,max(xi,5)≤J.Then, if MCS j=qi,max(xi,3) is used, only SBs n=3 and 5 can be allocated to user i since only these SBs have good enough channel
qualities to support an MCS index of qi,max(xi,3) or higher. Selecting SBs n=1 or 2 with MCS j=qi,max(xi,3) would result in unacceptably high error rates
for these SBs. On the other hand, if j=qi,max(xi,2),
all 4 SBs can be selected, at the expense of a lower
bit rate for SBs 1, 3, and 5.
This suggests that there is an optimal value of j which maximizes the total bit rate for user i.


## 3. Optimal Scheduler

### 3.1. Multiuser Optimization Model

With multiple
users, the optimization problem is more difficult. In addition, each SB can
only be occupied by a single user [4]. Let(3)vi,n(xi,n)=∑j=1qi,max(xi,n)bi,jrjbe the bit rate of SB n selected for user i given the channel quality xi,n,
where bi,j∈{0,1} is a binary decision variable. Let Qmax(i)=max⁡n∈𝒩i{qi,max(xi,n)}.
The constraint(4)∑j=1Qmax(i)bi,j=1is introduced to ensure that the
MCS for user i can only take on a single value between 1 and Qmax(i).
The formulation in (3) allows the selected bit rate for SB n to be less than what xi,n can potentially support, as may be the case if
user i is assigned more than one SB during a TTI.
From (3) and (4), it can be seen that SB n might be selected for user i only if the MCS j* chosen for user i satisfies j*≤qi,max(xi,n).The problem of jointly maximizing the sum of the bit rates for all users can be
formulated as(5)(P1):max⁡A,B∑i=1U∑n∈𝒩iai,n∑j=1qi,max(xi,n)bi,jrjsubject to (4)
and(6)∑i=1Uai,n=1,n∈𝒩i,ai,n,bi,j∈{0,1},∀i,j,n.In problem (P1), A={ai,n,i=1,…,U,n∈𝒩i}, B={bi,j,i=1,…,U,j=1,…,Qmax(i)},
and ai,n is a binary decision variable, with value 1 if SB n is assigned to user i and 0 otherwise. The objective in (5) is to select
optimal values for A and B to maximize the aggregate bit rate ∑i=1U∑n∈𝒩iai,nvi,n(xi,n).


### 3.2. Linearized Model

Note that
Problem(P1) is nonlinear due to the product ai,nbi,j in (5). Although solutions can be obtained
using optimization techniques such as Branch-and-Bound [13], global optimality cannot
be guaranteed. To avoid this difficulty, the problem can be transformed into an equivalent linear problem by introducing an auxiliary variable tn,i,j=ai,nbi,j.
Then, Problem (P1) can be linearized as follows:(7)(P1′):max⁡A,B,T∑i=1U∑n∈𝒩i∑j=1qi,max(xi,n)tn,i,jrjsubject to (4), (6) and(8)tn,i,j≤bi,j,tn,i,j≤ai,nM,tn,i,j≥bi,j−(1−ai,n)M,where M is a large positive real value. Problem (P1′) can then be solved using well-known integer
linear programming techniques [13].


## 3.1. Multiuser Optimization Model

With multiple
users, the optimization problem is more difficult. In addition, each SB can
only be occupied by a single user [4]. Let(3)vi,n(xi,n)=∑j=1qi,max(xi,n)bi,jrjbe the bit rate of SB n selected for user i given the channel quality xi,n,
where bi,j∈{0,1} is a binary decision variable. Let Qmax(i)=max⁡n∈𝒩i{qi,max(xi,n)}.
The constraint(4)∑j=1Qmax(i)bi,j=1is introduced to ensure that the
MCS for user i can only take on a single value between 1 and Qmax(i).
The formulation in (3) allows the selected bit rate for SB n to be less than what xi,n can potentially support, as may be the case if
user i is assigned more than one SB during a TTI.
From (3) and (4), it can be seen that SB n might be selected for user i only if the MCS j* chosen for user i satisfies j*≤qi,max(xi,n).The problem of jointly maximizing the sum of the bit rates for all users can be
formulated as(5)(P1):max⁡A,B∑i=1U∑n∈𝒩iai,n∑j=1qi,max(xi,n)bi,jrjsubject to (4)
and(6)∑i=1Uai,n=1,n∈𝒩i,ai,n,bi,j∈{0,1},∀i,j,n.In problem (P1), A={ai,n,i=1,…,U,n∈𝒩i}, B={bi,j,i=1,…,U,j=1,…,Qmax(i)},
and ai,n is a binary decision variable, with value 1 if SB n is assigned to user i and 0 otherwise. The objective in (5) is to select
optimal values for A and B to maximize the aggregate bit rate ∑i=1U∑n∈𝒩iai,nvi,n(xi,n).


## 3.2. Linearized Model

Note that
Problem(P1) is nonlinear due to the product ai,nbi,j in (5). Although solutions can be obtained
using optimization techniques such as Branch-and-Bound [13], global optimality cannot
be guaranteed. To avoid this difficulty, the problem can be transformed into an equivalent linear problem by introducing an auxiliary variable tn,i,j=ai,nbi,j.
Then, Problem (P1) can be linearized as follows:(7)(P1′):max⁡A,B,T∑i=1U∑n∈𝒩i∑j=1qi,max(xi,n)tn,i,jrjsubject to (4), (6) and(8)tn,i,j≤bi,j,tn,i,j≤ai,nM,tn,i,j≥bi,j−(1−ai,n)M,where M is a large positive real value. Problem (P1′) can then be solved using well-known integer
linear programming techniques [13].


## 4. A Suboptimal Scheduler

In the optimal
scheduler formulations in (P1) and (P1′), the MCSs, SBs, and users are jointly
assigned. To reduce complexity, the proposed suboptimal scheduler performs the
assignment in two stages. In the first stage, each SB is assigned to the user
who can support the highest bit rate. In the second stage, the best MCS for
each user is determined. The idea behind the suboptimal scheduler is to assign
a disjoint subset of SBs to each user, thereby reducing a joint multiuser
optimization problem into U parallel single-user optimization problems.Letφn be the index of the user which can support the
highest-rate MCS for SB n,
that is, φn=arg⁡max⁡i∈{1,2,…,U}qi,max(xi,n).
Furthermore, let 𝒩˜i be the (disjoint) set of SBs assigned to user i,
that is, {n⁢suchthatφn=i}.
In the first stage, the suboptimal scheduler determines {𝒩˜i}i=1U.LetQmax′(i)=max⁡n∈𝒩˜i{qi,max(xi,n)},
and let the MCS vector, bi,
for user i be(9)bi=[bi,1,bi,2,…,bi,Qmax′(i)].In the second stage, the
suboptimal scheduler determines bi which maximizes the total bit rate for user i.
Similar to the approach in Section 3, the optimal bi can be obtained by solving the following
problem:(10)(P2):max⁡bi∑n∈𝒩˜i∑j=1qi,max(xi,n)bi,jrj,s.t.(11)∑j=1Qmax′(i)bi,j=1,bi,j∈{0,1},∀i,j.Compared to (P1) or (P1′), (P2) is a much simpler problem.


## 5. Numerical Results

For
illustration purposes, we assumeNtot=12 SBs per TTI, L=12 subcarriers per SB, N1=N2=⋯=NU=N, and that the normal cyclic prefix
configuration is used [4]. The fading amplitude for each subcarrier and user
follows the Nakagami-m model [14], with a fading figure m=1.
The average signal-to-interference plus noise ratios (SINRs) for the users are 10 dB, 11 dB, and 12 dB, respectively. It is assumed that the SINRs
for all subcarriers of each user are correlated, but identically distributed
(c.i.d.), and that the resource blocks follow the localized configuration
[5]. The correlation
coefficient between a pair of subcarriers is given by ρ|i−j|,
where i and j are the subcarrier indices. The SINR of each
subcarrier is assumed to be independent at the beginning of each scheduling
period, and constant throughout the entire period. For simplicity, it is
assumed that the set of MCSs consists of QPSK 1/2 and 3/4, 16-QAM 1/2 and 3/4,
as well as 64-QAM 3/4 [1], and the L1/L2 control channels are mapped to the
first OFDM symbol within each subframe. Furthermore, each subframe consists of 8 reference symbols [4]. The feedback method is
based on the exponential effective SINR mapping (EESM) [10], with parameter values
obtained from [15].
Let Rtot* be the total bit rate defined in (5) or
(7),
and E[Rtot*] be the value of Rtot* averaged over 2500 channel realizations.Figure1 shows the average total bit rate, E[Rtot*],
as a function of ρ (top) and N (bottom). In Figure 1(a), it can be observed that the performance improves with the
level of correlation among subcarriers. Recall that the idea behind EESM is to map a set of subcarrier SINRs, {Γi}i=1L,
to a single effective SINR, Γ*,
in such a way that the block error probability (BLEP) due to {Γi}i=1L can be well approximated by that at Γ* in additive white Gaussian noise (AWGN)
[1, 10]. The value of Γ* tends to be skewed towards the weaker
subcarriers in order to maintain an acceptable BLEP. At a low value of ρ,
subcarriers with large SINRs are not effectively utilized, leading to a
relatively poor performance. In Figure 1(b), it can be seen that the performance
improves with N, but the rate of improvement decreases. There is little performance improvement
as N increases beyond 8.Average total bit rate as a function ofρ and N, respectively, with U=3.
(a) N=5 and 12 with U=3.
(b) ρ=0.5 and 0.9.
(a)(b)Figure2(a) shows E[Rtot*] as a function of the number, U,
of users for ρ=0.9 and N=12.
The average SINRs for all users are set to 10 dB. As U increases, E[Rtot*] increases due to the more pronounced benefits
from multiuser diversity. Figure 2(b) shows the percentage gain in E[Rtot*] for the optimal scheduler relative to the
suboptimal scheduler as a function of U.
As U increases, it becomes increasingly likely that
a given user will be assigned at most one SB in the first stage operation of
the suboptimal scheduler. In this event, the suboptimal scheduler is actually
optimal. It is therefore expected that the difference in performance between
the optimal and suboptimal schedulers will be small when U is large, as illustrated in Figure 2(b).
The result indicates that the suboptimal scheduler is especially attractive for
large values of U since it provides a significant reduction in
complexity and its performance approaches that of the optimal scheduler.Average total bit rate and percentage gain as
a function of the number of users,U,
with ρ=0.9 and N=12.
(a)(b)


## 6. Conclusion

The problem of
multiuser downlink scheduling in an LTE cellular communication system was
studied. Numerical results show that both the correlation among subcarriers and
the amount of information fed back play important roles in determining the
system performance. It was found that limited feedback may be sufficient to
achieve a good performance. A reduced complexity suboptimal scheduler was
proposed and found to perform quite well relative to the optimal scheduler. The
suboptimal scheduler becomes  especially attractive as the number of users
increases.



---

*Source: 323048-2008-06-12.xml*