1752 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 12, NO.

4, APRIL 2013
Frequency Domain Packet Scheduling with
MIMO for 3GPP LTE Downlink
Yinsheng Xu, Hongkun Yang, Fengyuan Ren, Chuang Lin, and Xuemin (Sherman) Shen, Fellow, IEEE
AbstractIn this paper, we formalize a general Frequency
Domain Packet Scheduling (FDPS) problem for 3GPP LTE
Downlink (DL). The DL FDPS problem incorporates the Single-
User Multiple Input Multiple Output (SU-MIMO) technique,
and can express various scheduling policies, including the
Proportional-Fair metric, the MaxWeight scheduling, etc. For
LTE DL SU-MIMO, the constraint of selecting only one MIMO
mode (transmit diversity or spatial multiplexing) per user in each
transmission time interval (TTI) increases the hardness of the
FDPS problem. We prove the problem is MAX SNP-hard, which
implies approximation algorithms with constant approximation
ratios are the best we can expect. Subsequently, we propose an
approximation algorithm of polynomial runtime. The solution
is based on a greedy method for maximizing a non-decreasing
submodular function over a matroid. The algorithm can solve the
general DL FDPS problem with an approximation ratio of 4. We
implement the proposed algorithm and compare its performance
with other well-known schedulers.
Index TermsLong Term Evolution (LTE), downlink (DL),
frequency domain packet scheduling (FDPS), optimization algo-
rithm, approximation ratio, submodular function, matroid.
I. INTRODUCTION
T
HE Third Generation Partnership Project (3GPP) Long
Term Evolution (LTE) standardization is the next forward
step in cellular network. LTE can achieve a high peak-data-rate
that scales with scalable system bandwidths, system capacity
and coverage improvements, spectrum efciency, latency re-
duction and packet optimized radio access. The architecture of
LTE network is depicted in Figure 1. The main functionality
of LTE is divided into three domains: User Equipment (UE),
Evolved UMTS Terrestrial Radio Access Network (EUTRAN)
and System Architecture Evolution (SAE) core, also known
as Evolved Packet Core (EPC). For the Downlink (DL), LTE
provides transmission speed up to 100 Mbps over a 20 MHz
channel. Because of the robustness against multi-path fading,
higher spectral efciency and bandwidth scalability, the Or-
thogonal Frequency Division Multiplexing Access (OFDMA)
has been selected for the LTE DL [1].
In LTE, the system bandwidth is divided into separable
chunks denoted as resource blocks (RBs) [2] (see Figure 1).
Manuscript received May 13, 2012; revised November 6, 2012 and January
1, 2013; accepted January 11, 2013. The associate editor coordinating the
review of this paper and approving it for publication is M. J. Hossain.
Y. Xu, F. Ren (corresponding author), and C. Lin are with the Tsinghua
National Laboratory for Information Science and Technology, Department
of Computer Science and Technology, Tsinghua University, Beijing, 100084,
China (e-mail: {xuysh08, renfy, clin}@[Link]).
H. Yang is with the Department of Computer Science, The University of
Texas at Austin, Texas, 78712, USA (e-mail: [Link]@[Link]).
X. (S.) Shen is with the Department of Electrical and Computer En-
gineering, University of Waterloo, Ontario, N2L 3G1, Canada (e-mail:
xshen@[Link]).
Digital Object Identier 10.1109/TWC.2013.022113.120678
Internet
Fig. 1: The architecture of 3GPP LTE network.
An RB is considered as the minimum scheduling resolution
in the time-frequency domain. The Frequency Domain Packet
Scheduling (FDPS) allocates different RBs to individual users
according to their current channel conditions, queue lengths
and other information. The FDPS policy is conducted during
each Transmission Time Interval (TTI, in LTE, 1TTI=1ms).
The DL OFDMA is achieved by the FDPS assignment of dif-
ferent frequency portions of bandwidth, which simultaneously
realizes frequency-domain multiplexing in concert with time-
domain scheduling [1].
The Spatial Division Multiplexing (SDM) Multiple Input
Multiple Output (MIMO) techniques form another essential
part of LTE in order to accomplish the ambitious requirements
for throughput and spectral efciency. Resting with the spatial
domain user selection over individual RBs, different MIMO
schemes are incorporated in the 3GPP standard [3]. In the
Single-User MIMO (SU-MIMO), the FDPS is restricted since
at most one user can be scheduled over each RB. Moreover,
all the RBs in one TTI (i.e. in one DL subframe) assigned to
an individual user are transmitted either in transmit diversity
mode or spatial multiplexing mode. The transmit diversity is
an approach whereby information is spread across multiple
transmit antennas to maximize the diversity advantage in
fading channels. Spatial multiplexing, on the other hand, is
an approach where the incoming data is divided into multiple
substreams and each substream is transmitted on a different
transmit antenna [4]. Both of the aforementioned MIMO
modes can be utilized to obtain the most advantageous sched-
ule. Although the Multi-User MIMO (MU-MIMO) provides
greater spatial domain exibility via allowing different users
to be scheduled on different spatial streams over the same RB,
we only focus on the SU-MIMO in this paper.
The LTE DL SU-MIMO FDPS problem has been addressed
in some literatures. However, the selection of the scheduling
policy for a specic LTE DL system depends on a case by
1536-1276/13$31.00 c 2013 IEEE
XU et al.: FREQUENCY DOMAIN PACKET SCHEDULING WITH MIMO FOR 3GPP LTE DOWNLINK 1753
case analysis and is not the focus of our work. In this paper,
rather than a particular scheduling objective, we propose a
universal solution for the LTE DL SU-MIMO FDPS problem.
We dene a general prot function which indicates the prot
gained by allocating a set of RBs to an active user. The
prot function is capable of expressing various scheduling
objectives such as the Proportional-Fair metric in [1] that
achieves good compromise between cell throughput and user
fairness, the MaxWeight scheduling in [5] that combines
utility maximization with queue stability, and so on. Based
on the prot function, we formalize a general FDPS problem
involving SU-MIMO enhancement for the LTE DL, which can
cover many existing scheduling algorithms.
Furthermore, we address the hardness of the LTE DL SU-
MIMO FDPS problem through an L-Reduction to a known
problem. We prove the problem is MAX SNP-hard, which
means that the problem is improbable to efciently approxi-
mate within a certain ratio. Accordingly, the approximation
algorithms with constant approximation ratios are the best
solutions that we can expect. Afterwards, we provide an
approximation algorithm for this problem in company with
a provable constant approximation ratio of 4. We design the
solution via a greedy method for maximizing a non-decreasing
submodular function over a matroid. First, the necessary
backgrounds of matroid and submodular function are briey
introduced. Second, we prove the total prot function as well
as many other scheduling objectives are non-decreasing and
submodular. Third, the 4-approximation algorithm is derived
for the LTE DL SU-MIMO FDPS problem. We subsequently
implement the proposed algorithm in Matlab and conduct
comparative simulations to compare its performance with
other well-known schedulers.
The remainder of the paper is organized as follows. Section
II reports related works on the LTE DL FDPS problem.
Section III describes the system model and formalizes the
LTE DL SU-MIMO FDPS problem. Section IV proves the
problem is MAX SNP-hard and shows that polynomial run-
time approximation algorithms with guaranteed approximation
ratios are necessary for practical LTE DL systems. In Section
V, we propose the computable approximation algorithm in
polynomial runtime and nd its approximation ratio. We eval-
uate the performance and draw conclusions in Section VI and
Section VII respectively. The necessary theoretic background
of approximation algorithms and complexity utilized in this
work is supplemented in the appendix.
II. RELATED WORKS
[Link] et al. [6] present a general scheduling framework
for LTE DL. They extend existing work on single-user queue
and channel-aware schedulers to multiuser ones for wideband
systems. In [7], [Link] et al. investigate the performance
of FDPS under Fractional-Load (FL) in LTE DL. The system-
level simulations indicate that FDPS under FL can provide
an effective trade-off between cell throughput and coverage.
[Link] et al. [8] show that the system performance improves
with increasing correlation among OFDMA subcarriers, while
only a limited amount of feedback information is needed to
achieve fairly good performance. [Link] et al. [9] consider
the resource allocation for the downlink of a cellular OFDM
system, with various practical considerations including integer
tone allocations, different sub-channelization schemes, maxi-
mum SNR constraint per tone, and self-noise due to channel
estimation errors and phase noise. A gradient-based schedul-
ing scheme is exploited to solve the optimization problem
in each time-slot. [Link] et al. [10] propose two novel
schedulers with respectively joint and separate implementation
of scheduling and the adaptive modulation and coding (AMC).
As a promising technique, the MIMO mechanism is intro-
duced to enhance the FDPS performance, which is evaluated
by [Link] et al. in [11]. In particular, [Link] et al. address
the performance of SDM MIMO techniques together with
FDPS for the LTE downlink [12]. Using the proportional fair
criterion, the combination of FDPS and SDM is studied. The
results show that the combination achieves increased gains
up to 20% with precoding in the macro-cell scenario while
35% in the micro-cell scenario. [Link] et al. [13] analyze the
average channel capacity and the SINR distribution for LTE
DL MU-MIMO systems. They investigate the SU-MIMO and
the MU-MIMO schemes and show that, the outage probability
for system in SU-MIMO is larger than the one in MU-
MIMO. In addition, the system performance of the two dual-
codeword SU-MIMO schemes in LTE DL is evaluated by
[Link] et al. [14]. [Link] et al. [15] develop closed-
form expressions for the throughput achieved by the feedback
schemes of LTE. Their analysis quanties the joint effects of
three critical components on the overall system throughput,
including the scheduler, the multiple-antenna mode, and the
feedback scheme.
The LTE DL SU-MIMO FDPS problem has been recently
addressed in [1]. [Link] et al. prove the NP hardness of the
optimal MIMO mode selection (spatial multiplexing or trans-
mit diversity) per user in each TTI. Specically, they develop
two approximation algorithms to maximize the Proportional-
Fair (PF) criterion extended to frequency and spatial domains.
The presented algorithms are based on full-channel feedback
and partial-channel feedback respectively, which both achieve
an approximation ratio of 2. In their follow-on work [16],
the FDPS problem is fully extended to incorporate with
MU-MIMO, which also aims at optimizing the PF criterion.
[Link] et al. [17] consider all the aforementioned practical
constraints imposed by LTE standards and address the schedul-
ing problem in practical LTE systems under two trafc models:
backlogged trafc model and nite queue model.
The assumption of an innitely backlogged model in
scheduling analysis is conventional in the above literatures
such as [1], which imply there are always arrival packets to
serve. However, this is not always the case in practical sys-
tems. In reality, packets are generated for each user according
to a stochastic arrival process with respect to applications.
[Link] et al. point out that the Proportional-Fair schedul-
ing does not work so well when the queues are fed by an
admissible arrival process [5]. In particular, it can result in the
instability of queues [18]. Therefore, it is preferable to take
system utility maximization and queueing stability into ac-
count simultaneously when we design scheduling policies. The
main results and contributions of [5] consist of generalization
of the MaxWeight scheduling algorithm already well-known
in the single-carrier setting. The algorithm is accommodated
to a variety of scheduling algorithms for multi-carrier and
frame-based wireless data systems. The NP hardness of these
problems are stated and algorithmic solutions with provable
1754 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 12, NO. 4, APRIL 2013
A
0
B
1
C 1
D
0
E
0
user
RB
Fig. 2: A feasible SU-MIMO FDPS example for the LTE DL when m = 13 and n
= 5. The blue colored (user, RB) pairs denote the RB-to-user assignment of a feasible
schedule. Note that all the RBs assigned to each user belong to the same MIMO mode.
0 denotes the transmit diversity while 1 denotes the spatial multiplexing.
performance bounds are proposed. One of their algorithms has
the approximation ratio of 1
1
e
(for any > 0) while the
other algorithms achieve at most a
1
2
+ fraction of the optimal
values. These conclusions are worthy of further investigation
in different kinds of multi-carrier scenarios.
All of the existing literatures require case by case analysis
and solution. In this paper, however, instead of a particular
objective, we propose a general prot function to formalize
the SU-MIMO LTE DL FDPS problem. The prot function
can express various specic scheduling objectives, including
the PF metric and the MaxWeight algorithms.
III. PROBLEM FORMALIZATION
A. System Model
We consider the downlink of an LTE cellular network,
where the system bandwidth is divided into m RBs. Be-
sides, the network has a single base station and n ac-
tive wireless users. We denote the set of all RBs by M
(M = {1, 2, , m}) and the set of all users by N (N =
{1, 2, , n}). With the LTE SU-MIMO support, we have two
MIMO modes (transmit diversity and spatial multiplexing),
which are represented by 0 and 1 respectively in the modes
set L (L = {0, 1}).
During each time slot, the base station allocates m RBs
to n users. Specically, each RB is assigned to at most one
user, and all the RBs assigned to one user should belong to
one MIMO mode. An example of a feasible SU-MIMO FDPS
scheduling for the LTE DL is illustrated in Figure 2.
We denote by A the power set of M (A = P(M)), i.e.,
the collection of all the subsets of M. a A, we use the
boolean variable x
a
i
to indicate whether or not the set of RBs
a is assigned to user i. User i gets the set a A if and only
if x
a
i
= 1.
We dene the prot function p(a, i, j) as follows
1
,
p : A N L R
0
(1)
where p(a, i, j) indicates the prot gained by assigning a A
to user i N with MIMO mode j L in one feasible
schedule (in one TTI). Moreover, we append the following
assumptions to the prot function to ensure it is a non-
decreasing submodular function. a A, i N, j L, a
1

a
2
M, b M, we assume that,
p(a
1
, i, j) p(a
2
, i, j) (2)
p(, i, j) = 0 (3)
1
R
0
denotes the non-negative real number set, i.e., a A, i N, j
L, p(a, i, j) 0.
p(a
1
{b}, i, j)p(a
1
, i, j) p(a
2
{b}, i, j)p(a
2
, i, j) (4)
(2) indicates that, the more RBs are allocated to the user,
the more prot he obtains, whereas allocating no RB delivers
0 prot to the user (in (3)). Via acquiring the same new RB,
the prot increase will be larger in case that the fewer RBs
are already been assigned (in (4)). Under these reasonable
assumptions, the prot function can be considered as non-
decreasing and submodular. In Section V, we develop an
algorithm to maximize the non-decreasing submodular prot
function over a matroid, which approximately solves the SU-
MIMO FDPS problem in the LTE DL.
The most attractive point of prot function lies in its
generality. We can use p(a, i, j) to model various specic
scheduling policies. In the following, we take the Proportional-
Fair (PF) scheduling objective

ca

c
i,j
studied in [1] as an
example to demonstrate its generality.
Lemma 1: The prot function p(a, i, j) can model the PF
scheduling objective

ca

c
i,j
.
Proof: We dene,
p(a, i, j) =

ca

c
i,j
(5)
where
c
i,j
= r
c
i,j
/R
i
is the PF metric value that user i
achieves on RB c in MIMO mode j.
Since r
c
i,j
0 is the current data rate
2
and R
i
> 0 is the
average service rate
3
, then i, j, c,
c
i,j
0 and

ca

c
i,j

0.
Evidently, the more RBs are allocated, the

ca

c
i,j
is
larger. Thus a
1
a
2
M,

ca1

c
i,j

ca2

c
i,j
.
If no RB is allocated, r
c
i,j
= 0 and then
c
i,j
= 0. When the
fewer RBs are already assigned, the current average service
rate R
i
is smaller and the PF metric is larger. Therefore, the
increase between two PF objectives will be larger when the
fewer RBs are already assigned. Namely, a
1
a
2
M, b
M, where a
1
and a
2
denote the assigned RBs and b denotes
a new RB, we have,

ca1{b}

c
i,j

ca1

c
i,j

ca2{b}

c
i,j

ca2

c
i,j
So far, the PF objective

ca

c
i,j
is proved to satisfy the
assumptions (2)-(4) in turn, and hence we proof the lemma.
The prot function is more general than the PF metric
since the PF only represents the additive objective function.
The prot function, however, involves both additive and non-
additive situations. Furthermore, we can express the three
objective functions in [5] as,
p(a, i, j) = Q
s
i

ca
r
c
i,j
p(a, i, j) = Q
s
i
min{Q
s
i
,

ca
r
c
i,j
}
p(a, i, j) = (Q
s
i
)
2
(max{0, Q
s
i

ca
r
c
i,j
})
2
(6)
2
The current data rate of user i is achieved on RB c in MIMO mode j
within the present TTI.
3
The average service rate is the data rate that a user has already been served
in the past few TTIs, which is commonly achieved through an exponentially
weighted moving average method.
XU et al.: FREQUENCY DOMAIN PACKET SCHEDULING WITH MIMO FOR 3GPP LTE DOWNLINK 1755
where Q
s
i
is the queue length for user i at the beginning
of TTI, and r
c
i,j
is the data rate for user i, RB c in MIMO
mode j in this TTI. These three objective functions combine
throughput maximization and queue stability together. We can
similarly derive the same conclusions in Lemma 1 for the
objectives in (6). So on the whole, the prot function might
vary with different scheduling policies and still maintain its
generality even though (2)-(4) appended.
B. LTE DL SU-MIMO FDPS
We consider a general SU-MIMO FDPS problem for the
LTE DL system with m RBs and n users. In each TTI, for
each set of RBs a (a A and should be allocated in only one
mode j L), we have a prot p(a, i, j) for each user i. Our
goal is to gure out a feasible FDPS solution in each TTI.
More specically, we intend to nd the most advantageous
way to assign a set a (a A) to user i in mode j so that
the total prot is maximized. Thus the LTE DL SU-MIMO
FDPS problem is formalized as the following combinatorial
optimization problem.
max
jL

(a,i)AN
p(a, i, j) x
a
i
subject to:
for each RB c M:

iN,a:ca
x
a
i
1
for each user i N:

aA
x
a
i
1
i N, a A : x
a
i
{0, 1}
(7)
As a matter of fact, the objective function already contains
the constraint that each user is scheduled in only one MIMO
mode. Besides, the rst constraint in (7) shows that every
RB is assigned to at most one user, and the second constraint
ensures each user gets no more than one set of RBs. Evidently,
problem (7) is a binary integer programming and it is not hard
to gure out the PF-FDPS problem studied in [1] is a special
case of (7). The SU-MIMO FDPS algorithm aims at nding
a subset of A N L which maximizes the total prot in
each TTI. Next, we analyze the hardness of (7) and design an
approximation algorithm as its solution.
IV. HARDNESS RESULTS
A. Hardness of (7)
It is straightforward to claim the LTE DL SU-MIMO FDPS
problem (7) is NP-hard. [Link] et al. [1] have shown that the
LTE DL SU-MIMO PF-FDPS problem, a special case of LTE
DL FDPS, is NP-hard. Obviously, if we reduce the LTE DL
PF-FDPS problem to the problem (7) by setting p(a, i) =

ca

c
i
, the NP hardness of (7) is acquired as well.
In [5], [Link] et al. formalize three optimization objec-
tives and design ve corresponding algorithms in multi-carrier
wireless data systems. In such systems, the queue size of user
i at the beginning of time slot t is denoted by Q
s
i
(t), while
the data rate for user i on RB c is denoted by r(i, c, t). We
consider the second objective in [5], which aims at keeping
the stability properties of MaxWeight algorithm and avoiding
unnecessary service to a user, i.e.,
max

i
Q
s
i
(t)min{Q
s
i
(t), (i, t)} (8)
where (i, t) =

c
r(i, c, t)x(i, c, t) represents the amount of
service that user i receives at time slot t.
The hardness of (8) is proved through a reduction from
a known problem in [19] similar to the reduction technique
utilized in [20]. More formally, the hardness results of (8) in
[5] is quoted below.
Lemma 2: For some > 0, there is no (1 )-
approximation algorithm for objective (8) unless P=NP.
Since Lemma 2 actually shows there is no PTAS for
(8), it indicates the MAX-SNP hardness of (8) in another
way. Consequently, we can derive the MAX-SNP hardness of
problem (7) via a similar reduction from the known problem
(8). We demonstrate that hardness result in Theorem 1.
Theorem 1: The LTE DL SU-MIMO FDPS problem (7) is
MAX SNP-hard, and accordingly it does not have a PTAS
assuming P = NP.
Proof: Based on Lemma 5, to prove that a problem B is
MAX SNP-hard, it sufces to present an L-Reduction from
a known MAX SNP-hard problem A to B. Accordingly, we
prove this theorem by an L-Reduction from problem (8) to
the LTE DL SU-MIMO FDPS problem (7).
To simplify notations, all the dependence on TTI t of (8) is
ignored hereafter. The n queues corresponding to n users at the
beginning of each TTI are hence denoted by Q
s
1
, Q
s
2
, , Q
s
n
.
The r(i, c) indicates the data rate for user i on RB c. Now we
start to construct the mapping relationship between instances
via function R. Assume that X is an instance of problem
(8). An instance of problem (7) is expressed by R(X), which
describes an LTE DL system with n users and m RBs using
two feasible MIMO modes. N = {1, 2, n} is the set of
active users. A is the power set of all RBs such that a
A, a is the subset of RBs allocated to one user. Chosen a
MIMO mode (take the transmit diversity for example), the
prot function p : AN R
0
is anew dened as follows.
p(a, i) =

Q
s
i
min{Q
s
i
,

a:ca
r(i, c)} c a in mode 0,
0 otherwise.
(9)
As for problem (8), the prot acquired by user i with queue
length Q
s
i
is p(a, i), as long as c a are scheduled in MIMO
mode 0 (0 stands for transmit diversity). Otherwise, the prot
is set to 0 when the user is scheduled in mode 1 (1 stands for
namely spatial multiplexing). Similarly, provided that mode 1
is chosen, the prot p(a, i) can be also dened. So far, the
instance mapping from (8) to (7) is complete.
Afterwards, we establish the mapping relationship between
solutions. Assume that s is a feasible solution of R(X).
Evidently, s indicates the set of RBs allocated to each user
consisting of the boolean variable x
a
i
. According to the
renewed denition of the prot function in (9), the feasible
solution of R(X) can be decomposed directly to feasible
solution S(s) for X with equal V ALs. As a result, the
mapping function S(s) is dened through x
c
i
, which denotes
whether one RB c of the set a is scheduled or not for problem
(8).
x
c
i
=

1 c a when x
a
i
= 1,
0 otherwise.
(10)
Next we need to check if (25) and (26) hold for mapping
R and S respectively. To validate (25), we assume s
0
is the
1756 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 12, NO. 4, APRIL 2013
optimal solution of R(X). Apparently,
V AL(s) = OPT(R(X)) (11)
Since S(s
0
) is a decomposed feasible solution of X, and
all the prots are set to 0 if scheduling is made with mode 1,
we have
V AL(s) = V AL(S(s
0
)) OPT(X) (12)
Therefore, we obtain OPT(R(X)) OPT(X). So the
inequality (25) holds when = 1.
Combining (11) and (12), we have OPT(X)
V AL(S(s)) OPT(R(X)) V AL(s). So (26) holds
when = 1.
In other words, (R, S) is an L-Reduction from (8) to (7).
Since problem (8) is MAX SNP-hard, the LTE DL SU-MIMO
FDPS problem (7) is also MAX SNP-hard and it does not have
a PTAS unless P = NP.
Theorem 1 addresses the nonexistence of PTAS, which
implies that for some constant > 0, there are no polynomial
time (1 + )-approximation algorithms for the LTE DL SU-
MIMO FDPS problem (7) unless P = NP. In other words, we
could at most hope for approximation algorithms with constant
approximation ratios
4
.
B. Search Space of (7)
In this section, we calculate the number of feasible sched-
ules and estimate the running time of the exhaustive search.
Suppose the LTE DL system has m RBs and n active users.
According to (5), we only need to cover the situation that
all the RBs are used up. Assume that in a feasible schedule
without MIMO enhancement, at most k out of n users are
supplied with m RBs (k min(n, m)). f
1
, f
2
, , f
k
denote
the number of scheduling policies when all the m RBs are
assigned to 1, 2, , k users, respectively, which yields (13),

k
k

f
k
+

k
k 1

f
k1
+

k
1

f
1
= k
m
(13)
The right part of (13) indicates that, since each RB has k
choices, the total options are k
m
. It is straightforward to obtain
f
1
= 1 (all the m RBs are distributed to one user). Similarly,
we can obtain f
2
= 2
m
2, f
3
= 3
m
3 2
m
+ 3, , and
iteratively derive f
min
(n, m). Specically, f
k
= 0 whenever
k > min(n, m).
Taking the MIMO enhancement into account, the search
space F of the LTE DL SU-MIMO FDPS problem (7) is
computed eventually,
F =

n
1

f
1
2 +

n
2

f
2
2
2
+
+

n
min(n, m)

f
min(n,m)
2
min(n,m)
where F > min(n, m)
m
obviously.
In practical systems, the 3GPP LTE Release 8 [21] species
the set of allowed values for m. Here, the set is given as
m {25, 50, 75, 100}. Meanwhile, it is common that dozens
4
For PTAS, we can nd out a (1+)-approximation algorithm computable
in polynomial time for any > 0.
of active users coexist in a cell. Provided that n = 10, m = 25,
then we have,
F > min(n, m)
m
= 10
25
If it takes 1 10
9
s to check one feasible schedule
scheme. The giant running time of an exhaustive search
(> 1 10
16
sTTI=1 10
3
s) is entirely unacceptable.
V. A GREEDY APPROXIMATION ALGORITHM
In this section, we design a greedy approximation algorithm
for the LTE DL SU-MIMO FDPS problem (7), which is
based on maximizing a non-decreasing submodular function
over a matroid. First, the necessary backgrounds of matroid
and submodular function are briey introduced. Second, we
compute the total prot which is the objective of (7), and
prove that objective function as well as many other scheduling
metrics are non-decreasing submodular functions. Third, we
prove the algorithm approximately solves problem (7) with
ratio 4, which invokes a sub-algorithm to maximize the
submodular objective function.
A. Matroid and Submodular Function
A rich variety of combinatorial optimization problems can
be modeled as the maximization of submodular functions over
a matroid [22]. We begin with the denition of matroid [5]
[23].
Denition 1: Let S be a nite ground set and L be a
nonempty collection of subsets of S. The ordered pair (S, L)
is called a matroid if:
1) L.
2) If A L and B A, then B L.
3) If A L, B L, and |A| > |B|, then there exists an
element x A \ B such that B {x} L.
The members of L are called the independent subset [22]
of S. Furthermore, the conditions 2) and 3) indicate the inher-
itance of L and the exchangeability of M [23], respectively.
A special case of matroid is the partition matroid [5]. The
matroid (S, L) is called a partition matroid if there is partition
of S into components {
1
,
2
, . . . }
5
such that,
A L k, |A
k
| 1
Subsequently, we present the denition of submodular set
function [22] [5].
Denition 2: Given a matroid M = (S, L), let f() be a
function on sets in L. We say f() is submodular if a
S, A L, B L, B A and (A {a}) L,
f(A {a}) f(A) f(B {a}) f(B) (14)
where the incremental value of adding element a to the set A
is often used,

a
(A) = f(A {a}) f(A)
In addition, we say the submodular function f() is non-
decreasing if,
f() = 0 and
a
(A) 0.
5
{
1
,
2
, . . . } is a partition of S if
i

i
= S and
i

j
= , i = j.
XU et al.: FREQUENCY DOMAIN PACKET SCHEDULING WITH MIMO FOR 3GPP LTE DOWNLINK 1757
Besides, [22] addresses that the following three statements
are equivalent to dene a non-decreasing submodular set
function f(). a S, A L, B L, B A,

f(A) +f(B) f(A B) +f(A B)

a
(B)
a
(A) 0 (16)
f(A) f(B) +

xA\B

x
(B) (17)
Now that the matroid and the submodular function are well
dened, we turn to the optimization problem. A generalized
optimization problem of maximizing the submodular function
over a matroid is established in [24], i.e.,
max
AS
{f(A) : A L, M = (S, L) is a matroid,
f(A) is submodular and non-decreasing}
(18)
In [24], a greedy solution is also proposed for the problem
(18), which is described in Lemma 3.
Lemma 3: The Greedy-Sub algorithm is a 2-approximation
algorithm to maximize the non-decreasing submodular func-
tion f() over a matroid (S, L). Moreover, the approximation
ratio 2 is tight.
Algorithm 1 GREEDY-SUB
1: input S, L, f()
2: A
3: while a S such that A {a} L do
4: a arg max
aS,A{a}L
(f(A {a}) f(A))
5: A A {a}
6: end while
7: return A and f(A)
B. Non-decreasing Submodular Objective Function
To utilize Lemma 3, we illuminate the objective function of
problem (7) as well as many other scheduling objectives are
non-decreasing and submodular functions.
Recall that M = {1, 2, , m} is the set of all RBs while
N = {1, 2, , n} is the set of all users. Let S = M N be
the ground set. Without MIMO mechanism, a valid schedule
can be denoted by {(a
1
, 1), (a
2
, 2), , (a
n
, n)}, where a
i

P(M), i, j, a
i
a
j
= and (a
i
, i) indicates the set of RBs
a
i
is assigned to user i (i N). If we rene a
i
by a
i
=
{b
i1
, b
i2
, , b
ik
, }, where b
ik
indicates the kth element in
the set a
i
allocated to user i. Then the valid schedule can be
rewritten,
{(a
11
, 1), (a
12
, 1), . . . , (a
21
, 2), (a
22
, 2), . . . ,
(a
n1
, n), (a
n2
, n), . . . }
(19)
Let L be the collection of all valid schedules for the LTE DL
without MIMO enhancement. The representations of elements
in L comply with (19). Evidently, the ordered pair (S, L) is
a matroid according to Denition 1. Then l L such that,
l = {(a
11
, 1), (a
12
, 1), . . . , (a
21
, 2), (a
22
, 2), . . . ,
(a
n1
, n), (a
n2
, n), . . . }
= {(a
1
, 1), (a
2
, 2), . . . (a
n
, n)},
and functions p
0
, p
1
can be dened on L,
p
0
(l) =
n

i=1
p(a
i
, i, 0)
p
1
(l) =
n

i=1
p(a
i
, i, 1)
(20)
where p(a
i
, i, 0) is the prot attained when a
i
is scheduled
to user i in MIMO mode 0 (transmit diversity). Likewise, the
p(a
i
, i, 1) is the prot in MIMO mode 1 (spatial multiplexing).
Obviously, p
0
(l) and p
1
(l) indicate the total prots gained
via some valid schedule l in different MIMO modes respec-
tively (all the users belong to mode 0 or all belong to mode
1). We demonstrate they are non-decreasing and submodular
in the following lemma.
Lemma 4: p
0
and p
1
dened in (20) are non-decreasing
submodular functions over L.
Proof: We only need to prove the lemma for p
0
since p
1
is dened similarly.
Suppose l
1
L and l
2
L are two valid schedule and
l
1
l
2
. That is to say, there is at least one user u is provided
with set of RBs such that (a
1
u
, u) l
1
, (a
2
u
, u) l
2
and
a
1
u
a
2
u
, whereas all the other users could be the same. Based
on (4) for a single user, (a, v) S, we have,
p
0
(l
1
{a, v}) p
0
(l
2
{(a, v)})
= p(a
1
1
, 1, 0) +p(a
1
2
, 2, 0) +p(a
1
v
{a}, v, 0)
p(a
2
1
, 1, 0) p(a
2
2
, 2, 0) p(a
2
v
{a}, v, 0)
p(a
1
1
, 1, 0) +p(a
1
2
, 2, 0) +p(a
1
v
, v, 0)
p(a
2
1
, 1, 0) p(a
2
2
, 2, 0) p(a
2
v
, v, 0)
= p
0
(l
1
) p
0
(l
2
)
Hence the inequality can be rewritten as,
p
0
(l
1
{a, v}) p
0
(l
1
) p
0
(l
2
{(a, v)}) p
0
(l
2
) (21)
which satises the submodular requirement. Meanwhile, based
on the non-decreasing proposition (2) for a single user, it is
straightforward to deduce that,
p
0
(l
2
)
= p(a
2
1
, 1, 0) +p(a
2
2
, 2, 0) +p(a
2
v
, v, 0)
p(a
2
1
, 1, 0) +p(a
2
2
, 2, 0) +p(a
2
v
{a}, v, 0)
= p
0
(l
2
{(a, v)})
(22)
which implies the non-decreasing property. Besides,
p
0
() =
n

i=1
p(, i, 0) = 0 (23)
Combine (21), (22) and (23), we prove the lemma.
Based on the discussions in Lemma 1, we can also consider
the other objective functions like the Proportional-Fair metric
in [1] and MaxWeight scheduling in [5] are non-decreasing
submodular functions. This accounts for the generalized rep-
resentativeness of the prot function as well.
Thereby, Algorithm 1 is applicable to the LTE DL FDPS
problem without MIMO. When we try to optimize (7) without
MIMO enhancement, we are trying to nd an assignment
(which corresponds to an element of a partition matroid) that
maximizes a submodular function.
1758 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 12, NO. 4, APRIL 2013
C. Integrated Solution for (7)
Now we take the SU-MIMO mechanism into account to
design the integrated algorithm for problem (7). The algorithm
takes the inputs consisting of the user collection N, the RB
collection M and the prot function p(a, i, j). In fact, the
algorithm invokes Algorithm 1 in succession to output A
0
and A
1
, which are feasible schedules of problem (7). The
total prot values of the schedules are p
0
(A
0
) and p
1
(A
1
).
The algorithm chooses the larger value and its corresponding
schedule as the output.
Algorithm 2 GREEDY-DOWNLINK (G-D for short)
1: input N, M, p
2: S M N, L P(S), p
0

iN
p(a
i
, i, 0), p
1

iN
p(a
i
, i, 1)
3: [A
0
, p
0
(A
0
)] GREEDY-SUB(S, L, p
0
) // invoke the
Algorithm 1
4: [A
1
, p
1
(A
1
)] GREEDY-SUB(S, L, p
1
)
5: j arg max
i{0,1}
(p
i
(A
i
))
6: return A
j
, p
j
(A
j
), j
Subsequently, we demonstrate Algorithm 2 approximately
solves problem (7) with constant ratio.
Theorem 2: Algorithm 2 is a 4-approximation algorithm for
the LTE DL SU-MIMO FDPS problem (7).
Proof: We rst denote the optimal schedule for problem
(7) as follows,
{(a

1
, 1, j

1
), (a

2
, 2, j

2
), . . . , (a

n
, n, j

n
)}
where (a

k
, k, j

k
) implies the set of RBs a

k
is assigned to user
k in MIMO mode j

k
.
Let p

n
i=1
p(a

i
, i, j

i
) be the optimal total prot
gained. Consider the dual scheme (all schedules are in the
opposite MIMO mode) of the optimal schedule,
{(a

1
, 1, 1 j

1
), (a

2
, 2, 1 j

2
), . . . , (a

n
, n, 1 j

n
)}
and obtain the total prot

n
i=1
p(a

i
, i, 1j

i
) 0. Therefore
we have,
p

i=1
p(a

i
, i, j

i
) +p(a

i
, i, 1 j

i
)
=
n

i=1
p(a

i
, i, 0) +p(a

i
, i, 1)
Recall that in Lemma 3, Algorithm 1 is a 2-approximation
algorithm for maximizing a non-decreasing submodular func-
tion over a matroid. Accordingly, we have,
p

i=1
p(a

i
, i, 0) +p(a

i
, i, 1)
2p
0
(A
0
) + 2p
1
(A
1
)
4 max(p
0
(A
0
), p
1
(A
1
))
where max(p
0
(A
0
), p
1
(A
1
)) is the return prot value of
Algorithm 2. Thus we prove the theorem.
10 20 30 40
100
200
300
400
500
600
700
800
Number of UE
T
o
t
a
l

P
r
o
f
i
t

G
a
i
n


Fig. 3: The numerical example of the Greedy-Downlink algorithm.
TABLE I: Simulation Parameters
Parameter Value
Frequency 2.0 GHz
Bandwidth 20 MHz
MIMO Antennas 22
SU-MIMO Mode Transmit Diversity/Spatial Multiplexing
Simulation Length 10000 TTIs
Number of Users 10/20/30/40/50
User Speed 5/50 KM/h
eNodeB Transmit Power 49 dBm
Uplink Feedback Channel Delay 0 TTI
D. Time Complexity of the Algorithm
The time complexity of the Algorithm 2 depends on that of
Algorithm 1, which operates one after another.
The Algorithm 1 assigns one RB to some user in each loop,
as long as there is still RB available. In the kth loop, the
algorithm need to check another n (m (k 1)) ordered
pairs (a, i) (a P(M), i N), since k 1 out of m RBs
have been already scheduled. So the total running time of
Algorithm 1 can be calculated as,
m

j=1
n(mj + 1) = O(nm
2
)
In consequence, the time complexity of the Algorithm 2
denoted by T
GD
is,
T
G-D
= O(nm
2
). (24)
The time complexity of Algorithm 1 in [1] that Lee et al.
have proposed is calculated as O(nm). It is indicated that
for both algorithms, along with the increasing user number n,
the time complexities of them increase linearly given a xed
number of resource blocks m. Since in most cases the number
of resource block in a TTI is relatively small, e.g., m = 25, the
time complexity of Algorithm 2 is still acceptable compared
to that in [1].
VI. PERFORMANCE EVALUATION
The Algorithm 2 is implemented and evaluated in the MAT-
LAB simulator. We rst give numerical example to illustrate
the total prot scheduled by Algorithm 2. Then, we perform
simulations for Algorithm 2 and other well-known schedulers.
XU et al.: FREQUENCY DOMAIN PACKET SCHEDULING WITH MIMO FOR 3GPP LTE DOWNLINK 1759
10 20 30 40 50
78
79
80
81
82
83
84
85
86
87
Number of UE
A
v
e
r
a
g
e

C
e
l
l

T
h
r
o
u
g
h
p
u
t

(
M
b
p
s
)


Best CQI
Greedy Downlink
Proportional Fair
MaxMin Fair
Round Robin
Fig. 4: The average cell throughput of all the
downloading UEs. (User speed is 5 km/h.)
10 20 30 40 50
78
79
80
81
82
83
84
85
86
87
Number of UE
A
v
e
r
a
g
e

C
e
l
l

T
h
r
o
u
g
h
p
u
t

(
M
b
p
s
)


Best CQI
Greedy Downlink
Proportional Fair
MaxMin Fair
Round Robin
Fig. 5: The average cell throughput of all the
downloading UEs. (User speed is 50 km/h.)
200 400 600 800 1000
3.6
3.8
4
4.2
Transmission Time Interval (TTI)
A
p
p
r
o
x
i
m
a
t
i
o
n

R
a
t
i
o


Simulation
Analytical
Fig. 6: The approximation ratio between the Opti-
mal and the the Algorithm 2.
A. Numerical Example
The numerical example is acquired in one TTI. Namely,
we calculate the numerical values in one schedule. Assume
there are N active users that communicate with the eNodeB
through 80 RBs in one TTI. The prot value of each RB is
randomly generated between 1 and 10, thus the upper bound
of the total prot is 800. We run the Algorithm 2 and compute
the total prot in different cases of N (3, 6, 9, 12 and so on).
As illustrated in Figure 3, the total prot is approximating
the upper bound when N becomes larger, especially when it
is larger than 36. The numerical example shows the system
can approximate the optimal prot when it is scheduled by
Algorithm 2.
B. Comparative Simulations
Here, we utilize the LTE DL system-level simulator [25],
which is an open platform for academic research. On that
platform, we deploy the Algorithm 2 and perform simu-
lations for the Greedy-Downlink (Algorithm 2) scheduler
and other well-known schedulers, including Proportional-Fair
(PF), Max-Min fairness, Best CQI and Round Robin (RR).
Some simulation parameters are summarized in Table I. To
implement Algorithm 2, the prot function is specied as the
current data rate, namely, p(a, i, j) =

ca
r
c
i,j
, where r
c
i,j
is the current data rate of user i on RB c in MIMO mode
j within the present TTI. Moreover, p(a, i, j) can also be
specied as other scheduling objectives in the implementation.
For example, when throughput and fairness are simultaneously
considered, we can set p(a, i, j) =

ca

c
i,j
like (5), where

c
i,j
is the proportional fair metric value that user i achieves
on RB c in MIMO mode j. In other words, the prot function
is veried to represent various scheduling schemes.
We carry out ve similar simulations and calculate the
average cell throughput
6
for each scheduler. The results are
provided with the average values of a 10000 TTIs duration
for each number of UEs. Two kinds of user speed are set, i.e.,
the walking mode (5 km/h) and the vehicular mode (50 km/h),
respectively. As illustrated in Figures 4 and 5, the RR and Best
CQI (always schedules user at the best channel) algorithms
are the lower and upper bounds of all schedulers in terms
of system performance (represented by cell throughput in
this case), respectively. The performance of Greedy-Downlink
6
The cell throughput is the total throughput of all the downloading UEs
that an eNodeB covers.
Algorithm 2 is between the PF and the upper bound, which
indicates its good performance. When the user speed is set
to 50 km/h, due to inuence of serious channel fading, the
average cell throughput of all schedulers are degraded (Figure
5). However, in this case, the Algorithm 2 still achieves better
performance than the PF scheduler.
C. Approximation Ratio
Furthermore, we present the approximation ratio between
the Optimal and the the Algorithm 2, in terms of simulated
and analytical values respectively. In each TTI, the optimal
objective value of the problem (7) is calculated through
an exhausted search. Then the optimal value is divided by
the simulation value of problem (7) when Algorithm 2 is
performed, and thereby we obtain the simulated approximation
ratio. The simulated result shown in Figure 6 (solid line) with
the theoretical approximation ratio of 4 (dash line) indicates
that the worst case of 4 can be a fairly tight performance
bound for the proposed Algorithm 2.
VII. CONCLUSION
In this paper, we have studied a general FDPS problem
for the LTE DL. As one of the promising techniques, the
MIMO is incorporated in the LTE DL to enhance the system
performance. We have focused on the SU-MIMO, which
involves two constrains for the FDPS. Namely, each RB can
be assigned to at most one user while all the RBs assigned
to one user should belong to the same MIMO mode, either
transmit diversity or spatial multiplexing.
Instead of a specic scheduling objective, we have proposed
a general prot function to indicate the prot gained by a valid
schedule. The most attractive point of prot function lies in its
generality. Utilizing prot as the objective, the LTE DL SU-
MIMO FDPS problem can be formalized as a combinatorial
optimization problem. This formalization can be generalized
to many scheduling policies such as Proportional-Fair and
MaxWeight. We have proved the formalized problem is MAX
SNP-hard through an L-Reduction, which implies the problem
is so difcult to be approximated that there is no PTAS for
it. Thus we have proposed an approximation algorithm with
constant ratio of 4 to solve the LTE DL SU-MIMO FDPS
problem. The proposed algorithm is based on a greedy method
that maximizes a submodular function over a matroid. The
simulation results demonstrate the prot model can express
other well-known schedulers and the proposed algorithm can
achieve fairly good performance.
1760 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 12, NO. 4, APRIL 2013
ACKNOWLEDGMENT
The authors gratefully acknowledge the anonymous re-
viewers for their constructive comments. This work is sup-
ported in part by the National Natural Science Foundation
of China (NSFC) under Grant No. 61225011, National Basic
Research Program of China (973 Program) under Grant No.
2012CB315803 and 2009CB320504, and National Science
and Technology Major Project of China (NSTMP) under Grant
No. 2011ZX03002-002-02.
APPENDIX A
APPROXIMATION ALGORITHM AND APPROXIMATION
RATIO
Assume that X is an instance of a maximization problem
7
.
We denote the size of the input by |X| and its optimal value
by OPT(X). Suppose ALG is a feasible solution for the
maximization problem. For instance X, we denote the cost of
ALG by ALG(X). We say that ALG has an approximation
ratio of r(|X|) [23] if, for any instance X, OPT(X) is within
a factor of r(|X|) of ALG(X):
OPT(X) r(|X|) ALG(X)
We also call ALG a r(|X|)-approximation algorithm. When
the approximation ratio is independent of the input size
|X|, we will use the terms approximation ratio of r and r-
approximation algorithm, indicating no dependence on |X|.
Note that r(|X|) 1 (or r 1), and a smaller value of
r(|X|) (or r) indicates that the approximation algorithm has a
better performance in a worst-case sense. In particular, when
r = 1, the approximation algorithm ALG is essentially the
optimal solution for any instance X.
APPENDIX B
POLYNOMIAL-TIME APPROXIMATION SCHEME
A polynomial-time approximation scheme (PTAS) [23] for
a maximization problem is an approximation algorithm that
takes as an input not only an instance of the problem, but also
a value > 0 such that for any xed , the scheme is a (1+)-
approximation algorithm which is computable in polynomial
time in the size of the input instance.
In a technical sense, a PTAS is the best that one can hope
for an NP-hard optimization problem, assuming P = NP.
APPENDIX C
L-REDUCTION
Suppose that A and B are maximization problems,. An L-
Reduction [26] from A to B is a pair of functions R and S,
both computable in polynomial time, with the following two
additional properties:
First, if X is an instance of A with optimum OPT(X),
then R(X) is an instance of B with optimum OPT(R(X))
that satises,
OPT(R(X)) OPT(X) (25)
where is a positive constant.
7
We only focus on maximization problems in this paper since the LTE DL
SU-MIMO FDPS is a maximization problem.
Second, if s is any feasible solution of R(X), then S(s) is
a feasible solution of X such that,
OPT(X) V AL(S(s)) (OPT(R(X)) V AL(s))
(26)
where is another positive constant particular to the reduction
and V AL denotes the value of the feasible solution in both
instances. (26) guarantees that S returns a feasible solution of
X which is not much more suboptimal than the given solution
of R(X). In particular, if s is the optimal solution of R(X),
then S(s) is the optimal solution of X.
The L-Reductions have the composition property [26], illu-
minated in Lemma 5.
Lemma 5: If (R, S) is an L-Reduction from problem A to
problem B, and (R

, S

) is an L-Reduction from problem B

, S

S) is an
L-Reduction from A to C.
APPENDIX D
MAX SNP-HARDNESS
In computational complexity theory, SNP (from Strict NP)
is a complexity class containing a limited subset of NP based
on its logical characterization in terms of graph-theoretical
properties. The class MAX SNP is a subset of optimization
problems derived from SNP [26]. A problem is said to
be MAX SNP-hard if all MAX SNP problems can be L-
reduced to this problem. Note that the problem itself may
not necessarily be MAX SNP.
MAX SNP-hard problems are hard to approximate. It is
shown in [26] that,
Lemma 6: Any MAX SNP-hard problem does not have a
PTAS unless P = NP.
Suppose A is a known MAX SNP problem, thus all the
MAX SNP problems can be L-reduced to A. Once B can be
L-reduced from A, according to the composition property in
Lemma 5, all the MAX SNP problems can also be L-reduced
to B, which indicates B is MAX SNP-Hard. In other words,
to prove that a problem B is MAX SNP-hard, it sufces to
present an L-reduction from a known MAX SNP-hard problem
A to B.
REFERENCES
[1] S.-B. Lee, S. Choudhury, A. Khoshnevis, S. Xu, and S. Lu, Downlink
MIMO with frequency-domain packet scheduling for 3GPP LTE, in
Proc. 2009 IEEE INFOCOM, pp. 12691277.
[2] Agilent, 3GPP long term evolution: system overview, product devel-
opment, and test challenges, Application Note, 2009.
[3] Evolved Universal Terrestrial Radio Access (E-UTRA); Physical layer
procedures (Release 8), 3GPP TS 36.213 version 8.8.0, Tech. Rep.,
2009.
[4] R. Heath and A. Paulraj, Switching between diversity and multiplexing
in MIMO systems, IEEE Trans. Commun., vol. 53, no. 6, pp. 962968,
2005.
[5] M. Andrews and L. Zhang, Scheduling algorithms for multi-carrier
wireless data systems, in Proc. 2007 ACM MOBICOM, pp. 314.
[6] B. Sadiq, R. Madan, and A. Sampath, Downlink scheduling for
multiclass trafc in LTE, EURASIP J. Wireless Commun. Netw., vol.
2009, pp. 1431.
[7] A. Pokhariyal, G. Monghal, K. Pedersen, P. Mogensen, I. Kovacs,
C. Rosa, and T. Kolding, Frequency domain packet scheduling under
fractional load for the UTRAN LTE downlink, in Proc. 2007 IEEE
VTC, pp. 699703.
[8] R. Kwan, C. Leung, and J. Zhang, Multiuser scheduling on the
downlink of an LTE cellular system, Research Lett. Commun., vol.
2008.
XU et al.: FREQUENCY DOMAIN PACKET SCHEDULING WITH MIMO FOR 3GPP LTE DOWNLINK 1761
[9] J. Huang, V. Subramanian, R. Agrawal, and R. Berry, Downlink
scheduling and resource allocation for OFDM systems, IEEE Trans.
Wireless Commun., vol. 8, no. 1, pp. 288296, 2009.
[10] M. Assaad and A. Mourad, New frequency-time scheduling algorithms
for 3GPP/LTE-like OFDMA air interface in the downlink, in Proc. 2008
IEEE VTC, pp. 19641969.
[11] N. Wei, A. Pokhariyal, T. B. Sorensen, T. E. Kolding, and P. E. Mo-
gensen, Mitigating signaling requirements for MIMO with frequency
domain packet scheduling, in Proc. 2007 IEEE VTC, pp. 27712775.
[12] N. Wei, A. Pokhariyal, T. Sorensen, T. Kolding, and P. Mogensen,
Performance of MIMO with frequency domain packet scheduling in
UTRAN LTE downlink, in Proc. 2007 IEEE VTC, pp. 11771181.
[13] Z. Lin, B. Vucetic, and J. Mao, Ergodic capacity of LTE downlink
multiuser MIMO systems, in Proc. 2008 IEEE ICC, pp. 33453349.
[14] E. Virtej, M. Kuusela, and E. Tuomaala, System performance of single-
user MIMO in LTE downlink, in Proc. 2008 IEEE PIMRC, pp. 15.
[15] S. Donthi and N. Mehta, Joint performance analysis of channel quality
indicator feedback schemes and frequency-domain scheduling for LTE,
IEEE Trans. Veh. Technol., vol. 60, no. 7, pp. 30963109, 2011.
[16] S.-B. Lee, I. Pefkianakis, S. Choudhury, S. Xu, and S. Lu, Exploiting
spatial, frequency, and multiuser diversity in 3GPP LTE cellular net-
works, IEEE Trans. Mobile Comput., vol. 11, no. 11, pp. 16521665,
Nov. 2012.
[17] H. Zhang, N. Prasad, and S. Rangarajan, MIMO downlink scheduling
in LTE systems, in Proc. 2012 IEEE INFOCOM, pp. 29362940.
[18] M. Andrews, Instability of the proportional fair scheduling algorithm
for HDR, IEEE Trans. Wireless Commun., vol. 3, no. 5, pp. 14221426,
2004.
[19] V. Kann, Maximum bounded 3-dimensional matching is MAX SNP-
complete, Inf. Process. Lett., vol. 37, no. 1, pp. 2735, 1991.
[20] C. Chekuri and S. Khanna, A PTAS for the multiple knapsack prob-
lem, in Proc. 2000 ACM SODA, pp. 213222.
[21] Physical Channels and Modulation (Release 8), 3GPP TS 36.211
V8.7.0, Tech. Rep., 2009.
[22] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher, An analysis of ap-
proximations for maximizing submodular set functions I, Mathematical
Programming, vol. 14, no. 1, pp. 265294, 1978.
[23] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction
to Algorithms, 2nd edition. The MIT Press, 2001.
[24] M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey, An analysis of
approximations for maximizing submodular set functions II, Mathe-
matical Programming Studies, vol. 8, pp. 7387, 1978.
[25] J. C. Ikuno, M. Wrulich, and M. Rupp, System level simulation of LTE
networks, in Proc. 2010 IEEE VTC.
[26] C. H. Papadimitriou, Computational Complexity. Addison Wesley, 1993.
Yinsheng Xu is currently a [Link] candidate of the
Department of Computer Science and Technology,
Tsinghua University, China. He received his BA
in School of Software from Beijing Institute of
Technology, 2008. His current research interests in-
clude resource scheduling and congestion control in
mobile Internet. Besides, he completes some works
on real-time transmission in the wireless sensor
networks.
Hongkun Yang received his BS and MS degrees
in computer science in 2007 and 2010 respectively,
both from the Department of Computer Science
and Technology, Tsinghua University, China. He is
currently working toward his PhD degree in Com-
puter Science Department, the University of Texas
at Austin. His research interests include wireless
networks and network security.
Fengyuan Ren is a professor of the Department
of Computer Science and Technology at Tsinghua
University, Beijing, China. He received his B.A and
[Link]. degrees in Automatic Control from North-
western Polytechnic University, China, in 1993 and
1996 respectively. In Dec. 1999, he obtained Ph.D.
degree in Computer Science from Northwestern
Polytechnic University. From 2000 to 2001, he
worked at Electronic Engineering Department of
Tsinghua University as a post doctoral researcher. In
Jan. 2002, he moved to the Computer Science and
Technology Department of Tsinghua University. His research interests include
network trafc management, control in/over computer networks, wireless
networks and wireless sensor networks. He (co)-authored more than 80
international journal and conference papers. He is a member of the IEEE, and
has served as a technical program committee member and local arrangement
chair for various IEEE and ACM international conferences.
Chuang Lin is a professor of the Department
of Computer Science and Technology at Tsinghua
University, Beijing, China. He is an Honorary Vis-
iting Professor, University of Bradford, UK. He
received his Ph.D. degree in Computer Science
from Tsinghua University, China in 1994. His cur-
rent research interests include computer networks,
performance evaluation, network security analysis,
and Petri net theory and its applications. He has
published more than 300 papers in research journals
and IEEE conference proceedings in these areas and
has published four books. He is a senior member of the IEEE and the Chinese
Delegate in TC6 of IFIP. He served as the Technical Program Vice Chair, the
10th IEEE Workshop on Future Trends of Distributed Computing Systems
(FTDCS 2004); the General Chair, ACM SIGCOMM Asia workshop 2005
and the 2010 IEEE International Workshop on Quality of Service (IWQoS
2010). He is an Associate Editor of IEEE TRANSACTIONS ON VEHICULAR
TECHNOLOGY and an Area Editor of Computer Networks, and the Journal
of Parallel and Distributed Computing.
Xuemin (Sherman) Shen (IEEE M97-SM02-
F09) received the [Link].(1982) degree from Dalian
Maritime University (China) and the [Link]. (1987)
and Ph.D. degrees (1990) from Rutgers University,
New Jersey (USA), all in electrical engineering.
He is a Professor and University Research Chair,
Department of Electrical and Computer Engineering,
University of Waterloo, Canada. He was the Asso-
ciate Chair for Graduate Studies from 2004 to 2008.
Dr. Shens research focuses on resource management
in interconnected wireless/wired networks, wireless
network security, wireless body area networks, vehicular ad hoc and sensor
networks. He is a co-author/editor of six books, and has published more
than 600 papers and book chapters in wireless communications and networks,
control and ltering. Dr. Shen served as the Technical Program Committee
Chair for IEEE VTC10 Fall, the Symposia Chair for IEEE ICC10, the
Tutorial Chair for IEEE VTC11 Spring and IEEE ICC08, the Technical
Program Committee Chair for IEEE Globecom07, the General Co-Chair for
Chinacom07 and QShine06, the Chair for IEEE Communications Society
Technical Committee on Wireless Communications, and P2P Communications
and Networking. He also serves/served as the Editor-in-Chief for IEEE
Network, Peer-to-Peer Networking and Application, and IET Communications;
a Founding Area Editor for IEEE TRANSACTIONS ON WIRELESS COMMU-
NICATIONS; an Associate Editor for IEEE TRANSACTIONS ON VEHICULAR
TECHNOLOGY, Computer Networks, and ACM/Wireless Networks, etc.; and
the Guest Editor for IEEE JSAC, IEEE Wireless Communications, IEEE
Communications Magazine, and ACM Mobile Networks and Applications, etc.
Dr. Shen received the Excellent Graduate Supervision Award in 2006, and the
Outstanding Performance Award in 2004, 2007 and 2010 from the University
of Waterloo, the Premiers Research Excellence Award (PREA) in 2003 from
the Province of Ontario, Canada, and the Distinguished Performance Award
in 2002 and 2007 from the Faculty of Engineering, University of Waterloo.
Dr. Shen is a registered Professional Engineer of Ontario, Canada, an IEEE
Fellow, an Engineering Institute of Canada Fellow, a Canadian Academy
of Engineering Fellow, and a Distinguished Lecturer of IEEE Vehicular
Technology Society and Communications Society.