1740 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 60, NO.

4, MAY 2011
A Cross-Layer Framework for Overhead Reduction,
Trafc Scheduling, and Burst Allocation in
IEEE 802.16 OFDMA Networks
Jia-Ming Liang, Student Member, IEEE, Jen-Jee Chen, Member, IEEE, You-Chiun Wang, Member, IEEE,
and Yu-Chee Tseng, Senior Member, IEEE
AbstractIEEE 802.16 orthogonal frequency-division multiple
access (OFDMA) downlink subframes have a special 2-D channel-
time structure. Allocation resources from such a 2-D structure
incur extra control overheads that hurt network performance.
Existing solutions try to improve network performance by de-
signing either the scheduler in the medium access control layer
or the burst allocator in the physical layer, but the efciency
of overhead reduction is limited. In this paper, we point out
the necessity of codesigning both the scheduler and the burst
allocator to efciently reduce overheads and improve network
performance. Under the partial-usage-of-subcarriers model, we
propose a cross-layer framework that covers overhead reduction,
real-time and non-real-time trafc scheduling, and burst alloca-
tion. The framework includes a two-tier priority-based scheduler
and a bucket-based burst allocator, which is more complete and
efcient than prior studies. Both the scheduler and the burst
allocator are tightly coupled together to solve the problem of
arranging resources to data trafc. Given available space and
bucket design from the burst allocator, the scheduler can well
utilize the frame resource, reduce real-time trafc delays, and
maintain fairness. On the other hand, with priority knowledge and
resource assignment from the scheduler, the burst allocator can
efciently arrange downlink bursts to satisfy trafc requirements
with low complexity. Through analysis, the cross-layer framework
is validated to give an upper bound to overheads and achieve high
network performance. Extensive simulation results verify that the
cross-layer framework signicantly increases network through-
put, maintains long-term fairness, alleviates real-time trafc de-
lays, and enhances frame utilization.
Index TermsBurst allocation, cross-layer design, fair schedul-
ing, IEEE 802.16, Worldwide Interoperability for Microwave
Access orthogonal frequency-division multiple access (WiMAX
OFDMA).
Manuscript received March 15, 2010; revised January 20, 2011; accepted
February 25, 2011. Date of publication March 10, 2011; date of current version
May 16, 2011. The work of Y.-C. Tseng was supported in part by the Aiming
for the Top University and Elite Research Center Development Plan, by the
National Science Council under Grant 97-3114-E-009-001, Grant 97-2221-
E-009-142-MY3, Grant 98-2219-E-009-019, Grant 98-2219-E-009-005, and
Grant 99-2218-E-009-005, by the Industrial Technology Research Institute,
Taiwan, by the Institute for Information Industry, Taiwan, by D-Link, and by
Intel Corporation. The review of this paper was coordinated by Dr. N. Ansari.
J.-M. Liang, Y.-C. Wang, and Y.-C. Tseng are with the Department of
Computer Science, National Chiao-Tung University, Hsin-Chu 30010, Taiwan
(e-mail: [email protected]; [email protected]; [email protected].
edu.tw).
J.-J. Chen is with the Department of Electrical Engineering, National Uni-
versity of Tainan, Tainan 70005, Taiwan (e-mail: [email protected]).
Color versions of one or more of the gures in this paper are available online
at http://ieeexplore.ieee.org.
Digital Object Identier 10.1109/TVT.2011.2125808
I. INTRODUCTION
T
HE IEEE 802.16 standard [1] has been developed for
wide-range broadband wireless access. The physical
(PHY) layer employs the orthogonal frequency-division multi-
ple access (OFDMA) technique, where a base station (BS) can
simultaneously communicate with multiple mobile subscriber
stations (MSSs) through a set of orthogonal subchannels. The
standard supports the frequency-division duplex (FDD) and
the time-division duplex (TDD) modes. This paper aims at the
TDD mode. Under the TDD mode, the following two types of
subcarrier grouping models are specied: 1) adaptive modu-
lation and coding (AMC) and 2) partial usage of subcarriers
(PUSC). AMC adopts a contiguous permutation strategy, which
chooses adjacent subcarriers to constitute each subchannel and
leverages channel diversity by the high correlation in channel
gains. However, each MSS needs to report its channel quality
on every subchannel to the BS. On the other hand, PUSC adopts
a distributed permutation strategy, which randomly selects sub-
carriers from the entire frequency spectrum to constitute each
subchannel. Thus, the subchannels could be more resistant to
interference, and each MSS can report only the average channel
quality to the BS. Because PUSC is more interference resistant
and mandatory in the standard, this paper adopts the PUSC
model. In this case, there is no issue of subchannel diversity
(i.e., the qualities of all subchannel are similar), because the
BS calculates the average quality for each subchannel based on
MSSs reports [2], [3].
The BS manages network resources for MSSs data trafc,
which is classied into real-time trafc [e.g., unsolicited grant
service (UGS), real-time polling service (rtPS), and extended
real-time polling service (ertPS)] and non-real-time trafc [e.g.,
non-real-time polling service (nrtPS) and best effort (BE)].
These network resources are represented by frames. Each frame
consists of a downlink subframe and an uplink subframe. Each
downlink subframe is a 2-D array over channel and time
domains, as shown in Fig. 1. The resource unit that the BS
allocates to MSSs is called a burst. Each burst is a 2-D subarray
and needs to be specied by a downlink map information
element (DL-MAP_IE or simply IE) in the downlink map (DL-
MAP) eld. These IEs are encoded by the robust quaternary
phase-shift keying (QPSK) 1/2 modulation and coding scheme
(MCS) for reliability. Because the IEs occupy frame space and
do not carry MSSs data, they are considered control overheads.
Explicitly, how we can efciently reduce IE overheads will
0018-9545/$26.00 2011 IEEE
LIANG et al.: OVERHEAD REDUCTION, TRAFFIC SCHEDULING, AND BURST ALLOCATION IN OFDMA NETWORKS 1741
Fig. 1. Structure of an IEEE 802.16 OFDMA downlink subframe under the
TDD mode.
signicantly affect network performance, because it determines
frame utilization. To manage resources to all data trafc, the
standard denes a scheduler in the medium access control
(MAC) layer and a burst allocator in the PHY layer. However,
their designs are left as open issues to implementers.
This paper aims at codesigning both the scheduler and the
burst allocator to improve network performance, which covers
overhead reduction, real-time and non-real-time trafc schedul-
ing, and burst allocation. The design of the scheduler should
consider the following three issues.
The scheduler should improve network throughput while
maintaining long-term fairness. Because the BS may send
data to MSSs using different transmission rates (due to
network situations), the scheduler will prefer MSSs that
use higher transmission rates but should avoid starving
MSSs that use lower transmission rates.
The scheduler should satisfy the delay constraints of real-
time trafc to avoid high packet-dropping ratios. However,
it should also meet the requirements of non-real-time
trafc.
To well utilize the limited frame space, the scheduler
has to reduce IE overheads when assigning resources to
MSSs data trafc. This condition requires the knowledge
of available frame space and burst arrangement design
from the burst allocator.
On the other hand, the design of the burst allocator should
address the following three issues.
The burst allocator should arrange IEs and downlink bursts
for the MSSs resource requests from the scheduler in the
OFDMA channel-time structure to well utilize the frame
space and reduce the control overhead. Under the PUSC
model, because all subchannels are equally adequate for
all MSSs, the problem of arranging IEs and downlink
bursts will become a 2-D mapping problem, which is NP-
complete [4]. To simplify the burst arrangement problem,
an advance planning for the MSSs resource requests in the
scheduler is needed. This condition requires codesigning
for the scheduler and the burst allocator.
To satisfy trafc requirements such as real-time delay
constraints, the burst allocator has to arrange bursts based
on the trafc scheduling knowledge from the scheduler.
For example, bursts for urgent real-time trafc should rst
be allocated to avoid packet dropping.
Simplicity is a critical concern, because a frame is typ-
ically 5 ms [5], which means that the burst allocation
scheme needs to be executed every 5 ms.
In the literature, prior studies design solely either the sched-
uler [6][10] or the burst allocator [4], [11][14] to address the
reduction of IE overheads. Nevertheless, we point out the ne-
cessity of the cross-layer design by the following three reasons.
First, the amount of IE overheads highly depends on the number
of scheduled MSSs and the number of fragmented bursts, where
prior work handles the two issues by the scheduler and the burst
allocator, respectively. However, if we only consider either
issue, the efciency of overhead reduction is limited. Second,
without considering burst arrangements, the scheduler may fail
to satisfy MSSs requirements, because extra IE overheads will
occupy the limited frame space. Third, without considering
the scheduling assignments, the burst allocator may kick out
some important data of MSSs (due to out-of-frame space).
This case may cause unfairness among MSSs and high packet-
dropping ratios of real-time trafc. Therefore, it is necessary to
codesign both the scheduler and the burst allocator due to their
inseparable dependency.
In this paper, we propose a cross-layer framework that con-
tains a two-tier priority-based scheduler and a bucket-based
burst allocator. The scheduler assigns priorities to MSSs traf-
c in a two-tier manner and allocates resources to the trafc
based on its priority. In the rst tier, trafc is differentiated by
its type. Urgent real-time trafc is assigned with the highest
level-1 priority to avoid its packets being dropped in the next
frame. Then, a ratio (0 < < 1) of nonurgent real-time
trafc is assigned with level-2 priority, and non-real-time trafc
is given level-3 priority. The aforementioned design has two
advantages. First, we can avoid generating too many urgent
real-time trafc in the next frame. Second, non-real-time trafc
can have opportunity to be served to avoid being starved. In the
second tier, trafc of the same type (i.e., the same priority level
in the rst tier) is assigned with different priorities calculated
by the following four factors:
1) current transmission rates;
2) average transmission rates;
3) admitted data rates;
4) queue lengths.
The BS can have the knowledge of the aforementioned four
factors, because all downlink trafc is queued in the BS, and
MSSs will report their average channel qualities to the BS [15].
Unlike traditional priority-based solutions that are partial to
non-real-time trafc [10], our novel two-tier priority scheduling
scheme not only prevents urgent real-time trafc from incurring
packet dropping (through the rst tier) but maintains long-
term fairness (through the second tier) as well. The network
throughput is also improved by giving a higher priority to
MSSs that use higher transmission rates (in the second tier).
In addition, the scheduler can adjust the number of MSSs to
be served and assign resources to trafc according to the burst
arrangement manner (from the burst allocator) to signicantly
reduce IE overheads. This design is neglected in prior studies
1742 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 60, NO. 4, MAY 2011
and has a signicant impact on overhead reduction and network
performance.
On the other hand, the burst allocator divides the free space
of each downlink subframe into a special structure that consists
of several buckets and then arranges bursts in a bucket-by-
bucket manner. Given k requests to be lled in a subframe, we
show that this burst allocation scheme generates at most k plus
a small constant number of IEs. In addition, the burst allocator
will arrange bursts according to the priority design from the
scheduler so that the burst allocation can satisfy MSSs trafc
requirements. The aforementioned bucket-based design incurs
very low computation complexity and can be implemented
on most low-cost Worldwide Interoperability for Microwave
Access (WiMAX) chips [16]. Explicitly, in our cross-layer
framework, both the scheduler and the burst allocator are tightly
coupled together to solve the problems of overhead reduc-
tion, real-time and non-real-time trafc scheduling, and burst
allocation.
The major contributions of this paper are fourfold. First,
we point out the necessity of codesigning both the scheduler
and the burst allocator to improve network performance and
propose a cross-layer framework that covers overhead reduc-
tion, real-time and non-real-time trafc scheduling, and burst
allocation. Our framework is more complete and efcient than
prior studies. Second, we develop a two-tier priority-based
scheduler that distributes resources among MSSs according
to their trafc types, transmission rates, and queue lengths.
The proposed scheduler improves network throughput, guar-
antees trafc requirements, and maintains long-term fairness.
Third, a low-complexity bucket-based scheme is designed for
burst allocation, which signicantly improves the utilization
of downlink subframes. Fourth, we analyze the upper bound
of the amount of IE overheads and the potential throughput
degradation caused by the proposed burst allocator, which is
used to validate the simulation experiments and provide guide-
lines for the setting of the burst allocator. Extensive simulations
are also conducted, and their results validate that our cross-
layer framework can achieve high network throughput, main-
tain long-term fairness, alleviate real-time trafc delays, and
improve downlink subframe utilization.
The rest of this paper is organized as follows. Section II
surveys the related work. Section III gives the problem formu-
lation. The cross-layer framework is proposed in Section IV.
Section V analyzes the expected network throughput of the
proposed framework. Extensive simulation results are given in
Section VI. Conclusions are drawn in Section VII.
II. RELATED WORK
Most of the prior studies on resource allocation in IEEE
802.16 OFDMA networks implement either the scheduler or
the burst allocator. For the implementation of the scheduler, the
study in [6] proposes a scheduling scheme according to MSSs
signal-to-noise ratios (SNRs) to achieve rate maximization.
The work in [7] proposes a utility function to evaluate the
tradeoff between network throughput and long-term fairness.
In [8], an opportunistic scheduler is proposed by adopting the
instantaneous channel quality of each MSS to maintain fairness.
However, these studies do not consider the delay requirements
of real-time trafc. The work in [9] tries to minimize the
blocking probability of MSSs trafc requests, and thus, the
packet-dropping ratios of real-time trafc may be reduced.
Nevertheless, all of the aforementioned studies [6][9] do not
address the issue of overhead reduction. The work in [10] tries
to reduce IE overhead from the perspective of the scheduler,
where the number of MSSs to be served in each subframe is re-
duced to avoid generating too many IEs. However, without the
help of the burst allocator, the efciency of overhead reduction
becomes insignicant, and some important data (e.g., urgent
real-time trafc) may not be allocated with bursts because of
out-of-frame space. In this case, some MSSs may encounter
serious packet dropping.
On the other hand, several studies consider implementing
the burst allocator. The work in [17] proposes a new control
message for periodic resource assignment to reduce duplicate
signaling. Reference [18] suggests piggybacking IEs on data
packets to increase the utilization of downlink subframes. How-
ever, both studies [17], [18] involve modifying the standard.
The work in [4] proposes two heuristics for burst allocation:
The rst heuristic scans the free space in a downlink subframe
row by row to try to fully utilize the space, but it may generate
a large number of IEs. The second heuristic presegments a
subframe into several rectangles, and a request will choose a
rectangle larger than it for allocation; however, this scheme re-
quires prior knowledge of the request distribution. The work in
[11] rst allocates bursts for large requests. Nevertheless, larger
requests may not be necessarily more important or urgent. Sev-
eral studies consider allocating bursts in a column-by-column
manner. In [12], bursts with the same MCS are combined into
a large one. However, this scheme is not compliant to the
standard, because a burst may contain requests from multiple
MSSs. The study in [13] pads zero bits in each columns end,
which may cause low subframe utilization. The work in [14]
adopts a backward columnwise allocation scheme, where the
bursts are allocated from the rightdown side to the leftup side
of the subframe. However, this scheme requires 3n bursts for
n MSSs in the worst case. As shown, existing research efforts
may pad too many useless bits, generate too many IEs, or leave
unused slot holes.
Few studies implement both the scheduler and the burst
allocator, but they do not consider reducing the IE overhead.
The studies in [19] and [20] try to arrange resources to MSSs to
maximize their data rates and maintain fairness. However, they
do not consider the delay requirements of real-time trafc. The
studies in [21] and [22] develop a one-tier priority-based sched-
uler to allocate resources to each MSS to exactly satisfy its
demand. Thus, the delay requirement of real-time trafc could
be guaranteed, but the network throughput may be degraded.
Nevertheless, all of the studies [19][22] neglect the issue of
overhead reduction, which may lead to low subframe utilization
and low network throughput. We will show by simulations in
Section VI that, without reducing the IE overhead, the quality-
of-service (QoS) requirements of MSSs trafc may not be
satised, particularly when the network becomes saturated.
Table I compares the features of prior studies and our cross-
layer framework. It is shown that our cross-layer framework
LIANG et al.: OVERHEAD REDUCTION, TRAFFIC SCHEDULING, AND BURST ALLOCATION IN OFDMA NETWORKS 1743
TABLE I
COMPARISON OF PRIOR WORK AND OUR CROSS-LAYER FRAMEWORK
covers all of the features. In addition, our cross-layer framework
has the least computation complexity in burst allocation. Thus,
it can be implemented on most WiMAX low-cost chips.
III. RESOURCE ALLOCATION PROBLEM
We consider the downlink communication in an IEEE 802.16
OFDMA network using the TDD mode. The mandatory PUSC
model is adopted so that there is no issue of subchannel
diversity (because MSSs will report only their average channel
qualities to the BS, as mentioned in Section I). The BS supports
multiple MSSs in a point-to-multipoint manner, where each
MSS has its admitted real-time and non-real-time trafc rates.
The BS has to arrange the radio resource to the MSSs according
to their trafc demands.
The radio resource is divided into frames, where each frame
is further divided into a downlink subframe and an uplink
subframe (see Fig. 1). A downlink subframe is modeled by
a 2-D array with X time units (in the time domain) and Y
subchannels (in the frequency domain). The basic unit in the
X Y array is called a subchannel time slot (or simply a
slot). Each downlink subframe is composed of the following
three portions: 1) preamble; 2) control; and 3) data. The control
portion contains a DL-MAP and an uplink map (UL-MAP)
to indicate the downlink and uplink resource allocation in the
current frame, respectively. The downlink allocation unit is a
subarray, called a downlink burst (or simply a burst), in the
X Y array. Each burst is denoted by (x, y, w, h), where x
is the starting time unit, y is the starting subchannel, w is the
bursts width, and h is the bursts height. An MSS can own
more than one burst in a subframe. However, no two bursts can
overlap with each other. Fig. 1 gives some examples. Bursts 1
and 2 can coexist, but bursts 2 and 3 cannot coexist. Each burst
requires one IE in the DL-MAP to describe its size and location
in the subframe. According to the standard, each burst carries
the data of exact one MSS. Explicitly, from the schedulers
perspective, the number of bursts (and, thus, IEs) will increase
when more MSSs are scheduled. On the other hand, from the
burst allocators perspective, more IEs are required when an
MSSs data are distributed over multiple bursts. An IE requires
60 b encoded by the QPSK 1/2 MCS [5]. Because each slot can
carry 48 b by QPSK 1/2, an IE occupies 5/4 slots, which has a
signicant impact on the available space to allocate bursts in a
downlink subframe.
The resource allocation problem is formulated as follows.
There are n MSSs in the network, where each MSS M
i
, i =
1, . . . , n, is admitted with an average real-time data rate of R
rt
i
(in bits/frame) and a minimal non-real-time data rate of R
nrt
i
(in bits/frame). Let C
i
be the current transmission rate
1
(in
bits/slot) for the BS to send data to M
i
, which may change
over frames. The objective is to design a cross-layer frame-
work that contains both the scheduler and the burst allocator
to arrange bursts to MSSs such that we can reduce the IE
overhead, improve the network throughput, achieve long-term
fairness, alleviate real-time trafc delays, and maximally utilize
downlink subframes. In addition, the design of the cross-layer
framework should not be very complicated so that it can execute
within a frame duration (i.e., 5 ms) and be implemented in most
low-cost WiMAX chips. Note that the fairness index (FI) in
[23] is adopted to evaluate the long-term fairness of a scheme
as follows:
FI =
(

n
i=1
SD
i
)
2
n

n
i=1
(SD
i
)
2
where SD
i
is the share degree of M
i
, which is calculated by
SD
i
=

T1
j=0
_

A
rt
i
(f
c
j) +

A
nrt
i
(f
c
j)
_
T (R
rt
i
+R
nrt
i
)
(1)
where

A
rt
i
(x) and

A
nrt
i
(x) are the amounts of real-time and
non-real-time trafc allocated to M
i
in the xth frame, respec-
tively, f
c
is the current frame index, and T is the window size
(in frames), over which we measure fairness. We denote by
U
d
(x) the utilization of the xth downlink subframe, which is
dened by the ratio of the number of slots used to transmit
data to X Y . Thus, the average downlink utilization over
T frames is

T1
j=0
U
d
(f
c
j)/T. Table II summarizes the
notations used in this paper.
IV. PROPOSED CROSS-LAYER FRAMEWORK
Fig. 2 shows the system architecture of our cross-layer
framework, which is composed of the following two com-
ponents: 1) the two-tier priority-based scheduler and 2) the
1
The estimation of the transmission rate highly depends on the path loss,
fading, and propagation model. Here, we assume that the BS can accurately
estimate the transmission rate for each MSS and will discuss how we can
conduct the estimation in Section VI.
1744 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 60, NO. 4, MAY 2011
TABLE II
SUMMARY OF NOTATIONS
Fig. 2. System architecture of the proposed cross-layer framework, where i =
1 . . . n.
bucket-based burst allocator. The transmission rate C
i
for each
MSS M
i
(see Fig. 2, label 1) is periodically reported to the
scheduler and the burst allocator. Each M
i
s admitted rates R
rt
i
and R
nrt
i
(see Fig. 2, label 2) are sent to the scheduler when M
i
rst associates with the BS or when R
rt
i
and R
nrt
i
change. The
scheduler also monitors the current amounts of queued real-
time and non-real-time data B
rt
i
and B
nrt
i
(see Fig. 2, label 3).
The burst allocator informs the scheduler of the bucket size

bkt
and the available free-space FS in the current downlink
subframe (see Fig. 2, label 4) to help the scheduler distribute
resources among MSSs trafc, where
FS = X Y (FCH size) (UL-MAP size)
(size of DL-MAP control elds) (2)
where FCH is the frame control header. The UL-MAP size can
be known in advance, because the uplink subframe is allocated
before the downlink subframe. The DL-MAP control elds
contain all parts of DL-MAP, except for IEs, which are yet
to be decided by the burst allocator. The schedulers mission
is to generate each M
i
s real-time and non-real-time resource
assignments Q
rt
i
and Q
nrt
i
(see Fig. 2, label 5) to the burst
allocator. Based on Q
rt
i
and Q
nrt
i
, the burst allocator arranges
IEs and bursts to each M
i
(see Fig. 2, label 6). The actual
real-time and non-real-time trafc allocated to M
i
are written,
respectively, as A
rt
i
and A
nrt
i
(see Fig. 2, label 7) and are fed to
the scheduler for future scheduling.
In our cross-layer framework, the priority rule dened in the
scheduler helps the burst allocator determine how bursts can be
arranged for MSSs trafc. On the other hand, the allocation
rule dened in the burst allocator also helps the scheduler to
determine how resources can be assigned to MSSs trafc. Both
the priority and allocation rules are similar to tenons in the
cross-layer framework, which make the scheduler and the burst
allocator tightly cooperate with each other.
Due to the NP-complete nature of the burst allocation prob-
lem and the hardware constraints of low-cost WiMAX chips, it
is inefcient and yet infeasible to derive an optimal solution for
arranging IEs and bursts in a short frame duration. Therefore, to
keep our burst allocator simple and efcient, we adopt a bucket
concept as follows. The available free-space FS in the current
subframe is horizontally sliced into a number of buckets, each
of size
bkt
(see Fig. 3 for an example). The size
bkt
serves
as the allocation unit in our scheme. As shown, the scheduler
always keeps (Q
rt
i
+Q
nrt
i
) as a multiple of
bkt
for each
M
i
. This way, the burst allocator can easily arrange bursts in
a bucket-by-bucket manner, well utilize the frame resource,
and generate quite few bursts and, thus, IEs (which will be
proved to have an upper bound in Section IV-B). In addition,
the long-term fairness is achieved, because the actual allocation
(A
rt
i
, A
nrt
i
) by the burst allocator is likely to be quite close
to the assignment (Q
rt
i
, Q
nrt
i
) by the scheduler for each i =
1, . . . , n.
A. Two-Tier Priority-Based Scheduler
In each frame, the scheduler will generate resource assign-
ments (Q
rt
i
, Q
nrt
i
), i = 1, . . . , n to the burst allocator. To gen-
erate these assignments, the scheduler adopts a two-tier priority
rule. In the rst tier, trafc is differentiated by its type and is
given priority levels according to the following order.
P1: urgent real-time trafc whose packets will pass their
deadlines at the end of this frame;
P2: real-time trafc ranked top ratio (0 < < 1)
sorted by their importance;
P3: non-real-time trafc sorted by their importance.
LIANG et al.: OVERHEAD REDUCTION, TRAFFIC SCHEDULING, AND BURST ALLOCATION IN OFDMA NETWORKS 1745
Fig. 3. Example of the bucket-based burst allocation with three buckets and four resource assignments.
Then, in the second tier, trafc of the same type is assigned
with different priorities by its importance, which is calculated
by the following four factors:
1) current transmission rates;
2) average transmission rates;
3) admitted data rates;
4) queue lengths.
In particular, for priority level P2, we rank the importance of
M
i
s real-time trafc by
I
rt
i
= C
i

C
i
C
avg
i

B
rt
i
R
rt
i
. (3)
Here, the importance I
rt
i
involves the following three factors
that are multiplied together.
1) A higher transmission rate C
i
gives M
i
a higher rating to
improve the network throughput.
2) A higher ratio C
i
/C
avg
i
gives M
i
a higher rating to pre-
vent starvation for MSSs with low average rates, where
C
avg
i
is the average transmission rate for the BS to send
data to M
i
in the most recent T frames. In particular, sup-
posing that an MSS encounters a bad channel condition
for a long period (i.e., a lower C
avg
i
value), we still prefer
this MSS if it can now enjoy a higher transmission rate
(i.e., C
i
> C
avg
i
). In addition, a higher C
i
/C
avg
i
value
means that the MSSs is currently in a better condition;
therefore, we give it a higher priority to improve the
potential throughput.
3) A higher ratio B
rt
i
/R
rt
i
gives M
i
a higher rating to favor
MSSs with more backlogs.
Similarly, for priority level P3, we rank the importance of
M
i
s non-real-time trafc by
I
nrt
i
= C
i

C
i
C
avg
i

1
S
nrt
i
(4)
where S
nrt
i
is the non-real-time rate satisfaction ratio of M
i
in
the most recent T frames, which is calculated by
S
nrt
i
=

T1
j=0
A
nrt
i
(f
c
j)
T R
nrt
i
. (5)
A small S
nrt
i
means that M
i
s non-real-time trafc may be
starved. Thus, a smaller S
nrt
i
gives M
i
a higher rating.
The aforementioned two-tier priority rule not only prevents
urgent real-time trafc from incurring packet dropping (through
the rst tier) but maintains long-term fairness (through the
second tier) as well. The network throughput is also improved
by giving a higher priority to MSSs that use higher transmission
rates (in the second tier). In addition, by giving a ratio of
nonurgent real-time trafc with level-2 priority, the amount of
urgent real-time trafc in the next frame can be reduced, and
non-real-time trafc can have opportunity to send their data.
In the following procedure, we present the detailed opera-
tions of our scheduler. Let e
i
be a binary ag to indicate whether
an IE has been allocated for M
i
, i = 1, . . . , n. Initially, we
set all e
i
= 0, i = 1, . . . , n. In addition, the free space FS is
deducted by ((Y/
bkt
) 1)
IE
to preserve the space for
potential IEs caused by the burst allocator (this case will be
discussed in the next section), where
IE
= 5/4 is the size of
an IE.
1) Let U
rt
i
be the amount of data of M
i
s urgent real-time
trafc in the current frame. For all M
i
with U
rt
i
> 0, we
sort them according to their C
i
values in a descending
order. Then, we schedule the free-space FS for each of
them as follows until FS 0.
a) Reserve an IE for M
i
by setting FS = FS
IE
.
Then, set e
i
= 1.
b) If FS > 0, assign resource Q
rt
i
=
min FS C
i
, U
rt
i
to M
i
and set FS = FS
Q
rt
i
/C
i
|. Then, deduct Q
rt
i
from B
rt
i
.
2) After step 1, if FS > 0, we sort all M
i
that have real-
time trafc according to their I
rt
i
values [by (3)]. Then,
we schedule the resource for each of them as follows
until either all MSSs in the top ratio are examined or
FS 0.
a) If e
i
= 0, reserve an IE for M
i
by setting FS = FS

IE
and e
i
= 1.
b) If FS > 0, assign more resources = minFS
C
i
, B
rt
i
to M
i
. Then, set Q
rt
i
= Q
rt
i
+ and FS =
FS /C
i
|. Deduct from B
rt
i
.
1746 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 60, NO. 4, MAY 2011
3) After step 2, if FS > 0, we sort all M
i
according to
their I
nrt
i
values [by (4)]. Then, we schedule the resource
for each of them as follows until either all MSSs are
examined or FS 0.
a) If e
i
= 0, reserve an IE for M
i
by setting FS = FS

IE
and e
i
= 1.
b) If FS > 0, assign more resources = minFS
C
i
, B
nrt
i
to M
i
. Then, set Q
nrt
i
= and FS =
FS /C
i
|. Deduct from B
nrt
i
.
4) Because the bucket size
bkt
is the allocation unit in
our burst allocator, in this step, we will do a ne-tuning
on Q
rt
i
and Q
nrt
i
such that (Q
rt
i
+Q
nrt
i
) is aligned to a
multiple of
bkt
for each M
i
. To do so, we will gradually
remove some slots fromQ
nrt
i
and then Q
rt
i
until (((Q
rt
i
+
Q
nrt
i
)/C
i
) mod
bkt
) = 0. One exception is when much
of the data in Q
rt
i
are urgent, which makes removing
any resource from M
i
impossible. In this case, we will
add more slots to M
i
until (((Q
rt
i
+Q
nrt
i
)/C
i
) mod

bkt
) = 0. The aforementioned adjustment (i.e., removal
and addition) may make the total resource assignment
below or beyond the available resource FS. If so, we
will further remove some slots from the MSSs with less
importance or add some slots to the MSSs with more
importance until the total resource assignment is equal to
the initial free space given by the burst allocator.
Fig. 4 illustrates the owchart of the scheduler. To sum-
marize, our scheduler generates the resource assignment ac-
cording to the following three priorities: P1) urgent trafc;
P2) real-time trafc; and P3) non-real-time trafc. Step 1 rst
schedules MSSs with urgent trafc to alleviate their real-time
trafc delays. Step 2 schedules the top ratio of MSSs to
reduce the number of MSSs that may have urgent trafc in the
following frames. This step also helps reduce the IE overhead
of future frames caused by urgent trafc, which is neglected
by prior studies. Step 3 schedules MSSs with lower non-real-
time satisfaction ratios to prevent them from starvation. Finally,
step 4 reshapes all assignments such that each (Q
rt
i
+Q
nrt
i
) is
divisible by
bkt
. This step will help the burst allocator fully
utilize a downlink subframe.
We then analyze the time complexity of our scheduler. In
step 1, sorting MSSs by their C
i
values takes O(nlg n) time,
and scheduling the resources for the MSSs with urgent trafc
takes O(n) time. In step 2, sorting MSSs by their I
rt
i
values
requires O(nlg n) time, and scheduling the resources for the
top ratio of MSSs requires at most O(n) time. In step
3, sorting MSSs by their I
nrt
i
values costs O(nlg n) time,
and scheduling the resources for the MSSs with non-real-
time trafc takes O(n) time. In step 4, reshaping all requests
spends at most O(n) time. Thus, the total time complexity is
O(nlg n +n +nlg n +n +nlg n +n +n) = O(nlg n).
B. Bucket-Based Burst Allocator
Ideally, the free space FS in (2) should accommodate each
resource assignment (Q
rt
i
, Q
nrt
i
) calculated by the scheduler
and its corresponding IE(s). However, because the burst al-
location problem is NP-complete, our bucket-based heuristic
Fig. 4. Flowchart of the two-tier priority-based scheduler.
will try to squeeze as more MSSs assignments into FS as
possible and allocate one burst per assignment with a very high
possibility. If more than one burst is required, more IEs are
needed, in which case, some assignments that were originally
arranged by the scheduler may be trimmed down or even
kicked out by the burst allocator. Given the free space FS by
(2), bucket size
bkt
, and assignments (Q
rt
i
, Q
nrt
i
)s from the
scheduler, our bucket-based heuristic works as follows.
1) Horizontally
2
slice FS into Y/
bkt
buckets, each of a
height
bkt
, where Y is divisible by
bkt
. Fig. 3 shows
an example by slicing FS into three buckets.
2) Let k be the number of resource assignments given by
the scheduler. We reserve (k + (Y/
bkt
) 1)
IE
|
slots for IEs at the left side of the subframe. In fact, the
scheduler has also reserved the space for these IEs, and
its purpose will become clear later on. Fig. 3 gives an
example. Because there are four assignments, 4 + 3 1
IEs are reserved.
3) We then assign bursts to satisfy these resource assign-
ments according to their priorities originally dened in
the scheduler. Because each assignment (Q
rt
i
, Q
nrt
i
) may
have data mixed in the categories of P1, P2, and P3, we
redene its priority as follows.
a) An assignment with data in P1 has a higher priority
than an assignment without data in P1.
b) Without the existence of data in P1, an assignment
with data in P2 has a higher priority than an assign-
ment without data in P2.
2
We can also vertically slice FS, but the effect will be the same.
LIANG et al.: OVERHEAD REDUCTION, TRAFFIC SCHEDULING, AND BURST ALLOCATION IN OFDMA NETWORKS 1747
Fig. 5. Flowchart of the bucket-based burst allocator.
Then, bursts are allocated in a bucket-by-bucket man-
ner. In particular, when an assignment (Q
rt
i
, Q
nrt
i
) is
examined, it will be placed starting fromthe previous stop
point and ll up the bucket from right to left until either
(Q
rt
i
, Q
nrt
i
) is satised or the left end of the bucket is
encountered. In the latter case, we will move to the right
end of the next bucket and repeat the aforementioned allo-
cation process. In addition, this cross-bucket behavior
will require one extra IE for the request. The aforemen-
tioned operation is repeated until either all assignments
are examined or all buckets are exhausted. Fig. 3
gives one example, where the four assignments are pri-
oritized by (Q
rt
3
, Q
nrt
3
) > (Q
rt
1
, Q
nrt
1
) > (Q
rt
4
, Q
nrt
4
) >
(Q
rt
2
, Q
nrt
2
). Assignment (Q
rt
1
, Q
nrt
1
) requires two IEs,
because it involves one cross-bucket behavior.
4) According to the allocation in step 3, we place each
resource assignment (Q
rt
i
, Q
nrt
i
) into its burst(s). In ad-
dition, the amount of actual allocation is written into
each (A
rt
i
, A
nrt
i
) and fed back to the scheduler for future
scheduling.
Fig. 5 illustrates the owchart of the burst allocator. We
make some remarks as follows. First, because there are Y/
bkt
buckets, there are at most ((Y/
bkt
) 1) cross-bucket burst
assignments, and thus, at most ((Y/
bkt
) 1) extra IEs are
needed. To accommodate this need, some assignments may
slightly be trimmed down. Thus, (Q
rt
i
, Q
nrt
i
) and (A
rt
i
, A
nrt
i
)
are not necessarily the same. However, the difference should be
very small. Second, the bucket that is located at the boundary of
reserved IEs and data (e.g., the third bucket in Fig. 3) may have
some extra slots (e.g., the lower left corner of the third bucket).
These extra slots are ignored in the aforementioned process for
ease of presentation, but they can be used to allocate bursts
to further improve space efciency. Third, because each cross-
bucket behavior will require one extra IE and there are Y/
bkt
buckets, the number of IEs required is bounded, as proved in
Theorem 1.
Theorem 1: In the bucket-based burst allocator, the (k +
(Y/
bkt
) 1) IEs reserved in step 2 are sufcient for the burst
allocation in step 3.
Proof: Given Y/
bkt
buckets

b
1
,

b
2
, . . ., and

b
Y/
bkt
,
we can concatenate them into one virtual bucket

b with
((Y/
bkt
) 1) joints. We then allocate one virtual burst for
each request from the scheduler in

b; therefore, we have at most

k virtual bursts. Then, we replace each virtual burst by one
real burst. However, we require one extra real burst whenever
the replaced virtual burst crosses one joint. The worst case
occurs when each of the ((Y/
bkt
) 1) joints is crossed by
one virtual burst. In this case, we require (k + (Y/
bkt
) 1)
real bursts to replace all virtual bursts. Because each real burst
requires one IE, we have to reserve at most (k + (Y/
bkt
) 1)
IEs.
In comparison, a naive burst allocation will require the worst
case of 3k IEs if the allocation goes in a row-major or column-
major way [14] (because each request may require up to three
IEs). In our scheme, the bucket size
bkt
can dynamically
be adjusted to reect the grain size of our allocation. A
larger grain size may cause fewer IEs but sacrice resource
utilization, whereas a smaller grain size may cause more IEs
but improve resource utilization. We will discuss the effect of

bkt
in Section VI-F.
We then analyze the time complexity of our burst allocator.
Because we allocate bursts in a zigzag manner, the time com-
plexity is proportional to the number of bursts. By Theorem 1,
we have at most (k + (Y/
bkt
) 1) bursts. Because we have
k n and Y/
bkt
is usually smaller than n, the time complex-
ity is O(k + (Y/
bkt
) 1) = O(n).
To conclude, the proposed scheduler and burst allocator
are dependent on each other by the following two designs.
First, the scheduler reserves the extra IE space caused by the
bucket partition and arranges resources to MSSs trafc so that
the resource assignments can align to buckets. Thus, we can
enhance the possibility that the burst allocator fully satises
the resource assignments from the scheduler. Second, the burst
allocator follows the priority rule in the scheduler to arrange
bursts. Thus, even if the frame space is not enough to satisfy all
trafc, urgent real-time trafc can still be arranged with bursts
to catch their approaching deadlines.
V. ANALYSIS OF NETWORK THROUGHPUT LOSS
BY THE BUCKET-BASED SCHEME
Given an ideal scheduler, we analyze the loss of network
throughput caused by our bucket-based burst allocator. To
simplify the analysis, we assume that the network has only
trafc of priority levels P1 and P3 and each MSS has innite
data in P3. (Trafc of P2 will eventually become urgent trafc
of P1.) Then, we calculate the difference between the expected
throughput by our burst allocator and the maximum throughput
by an ideal burst allocator. In the ideal burst allocator, the
number of IEs is equal to the number of resource assign-
ments from the scheduler. In addition, the frame resource is
always rst allocated to urgent trafc (P1) and then to non-
real-time trafc (P3) with the highest transmission rate. It
follows that the following two factors may degrade the network
throughput by our burst allocator: 1) extra IEs incurred by
step 3 in Section IV-B and 2) the data padding of low-rate
1748 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 60, NO. 4, MAY 2011
non-real-time trafc at the boundary between the data in P1
and P3. In particular, each burst must begin with the data in
P1, followed by the data in P3. Furthermore, if the data in P3
covers more than one column, it must be sent at the highest
transmission rate. If the data in P3 covers less than a column,
it may be sent at a nonhighest transmission rate. The right-
hand side of Fig. 3 shows these two possibilities, where P2 is
empty. Note that, in the rst possibility, all data in P3 must be
transmitted at the highest rate; otherwise, the shaded area will
be allocated to the data in P3 of other MSSs using the highest
rate.
Following the aforementioned formulation, our objective is
to nd the throughput loss L by our burst allocator compared
with the ideal burst allocator as
L = E[

O] c
high
+E[

o] (6)
where

O is the random variable that represents the number of
extra IEs caused by buckets, and

o is the random variable that
represents the throughput degradation (in bits) caused by the
low-rate padding in the shaded area of the second possibility
on the right-hand side of Fig. 3. To simplify the analysis, we
assume that there are only two transmission rates c
high
and c
low
,
where c
high
> c
low
. The probability that an MSS is in either rate
is equal.
A. Calculation of E[

O]
We rst give an example to show how our analysis works.
Suppose that we have three MSSs and three buckets. Each
bucket has two arrangement units, each having
bkt
slots.
Thus, there are, in total, six arrangement units, denoted by
O
1
, O
2
, O
3
, O
4
, O
5
, and O
6
. Resources that are allocated
to the three MSSs can be represented by two separators
[. For example, we list the following three possible al-
locations: 1) O
1
O
2
[O
3
O
4
[O
5
O
6
; 2) O
1
O
2
O
3
O
4
|O
5
O
6
; and
3) O
1
[O
2
O
3
O
4
O
5
[O
6
. In arrangement 1, we need no extra
IE. In arrangement 2, MSS 2 receives no resource, but MSS
1 needs one extra IE. In arrangement 3, MSS 2 requires
two IEs.
We will use arrangement units and separators to conduct
the analysis. Suppose that we have n MSSs, (Y/
bkt
)(= B)
number of buckets, and X B(= ) arrangement units (i.e.,
each bucket has X arrangement units). This approach can be
represented by arbitrarily placing (n 1) separators along a
sequence of arrangement units. Bucket boundaries appear
after each ith arrangement unit such that i is a multiple of X.
Note that only (B 1) bucket boundaries can cause extra IEs,
as mentioned in Section IV. Whenever no separator appears at
a bucket boundary, one extra IE is needed. There are, in total,
( + (n 1))!/(!(n 1)!) ways of placing these separators.
Let

c be the random variable that represents the number of
bucket boundaries, where each of bucket boundaries is inserted
by at least one separator. The probability of (

c = e) is calcu-
lated by
Prob[

c = e] =
C
B1
e

((B1e)+(n1e))!
((B1e))!(n1e)!
(+(n1))!
!(n1)!
. (7)
Note that the termC
B1
e
refers to the combinations of choos-
ing e boundaries from the (B 1) bucket boundaries. Each of
these e boundaries is inserted by at least one separator. The re-
maining (B 1 e) bucket boundaries must not be inserted by
any separator. To understand the second term in the numerator
of (7), we can denote by x
0
the number of separators before the
rst arrangement unit and by x
i
the number of separators after
the ith arrangement unit, i = 1, . . . , . Explicitly, we have
x
0
+x
1
+ +x

= n 1 x
i
0, 1, 2, .
However, when

c = e, (B 1 e) of these x
i
s must be 0.
In addition, e of these x
i
s must be larger than or equal to 1.
Then, this problem is equivalent to nding the number of
combinations of
y
0
+y
1
+ +y
j
+ +y
(B1e)
= n 1 e
y
j
0, 1, 2, . . ..
It follows that there are ( (B 1 e) + (n 1 e))!/
(( (B 1 e))!(n 1 e)!) combinations. Therefore,
E[

O] can be obtained by
E[

O] =
B1

e=0
(number of extra IEs when

c =e)Prob[

c =e]
=
B1

e=0
(B1e)
C
B1
e

((B1e)+(n1e))!
((B1e))!(n1e)!
(+(n1))!
!(n1)!
. (8)
B. Calculation of E[

S]
Recall that E[

S] is the expected throughput degradation

caused by the transmission of a burst at a low rate and the
burst contains some data padding of non-real-time trafc. To
calculate E[

S], let us dene

N
L
as the random variable of
the number of MSSs using the low transmission rate c
low
.
Because there is no throughput degradation by MSSs using the
high transmission rate c
high
, the overall expected throughput
degradation is
E[

S] =
n

m=1
E[

S[

N
L
= m] Prob[

N
L
= m]. (9)
Let

U
i
be the random variable that represents the amount
of data of M
i
s urgent trafc i = 1, . . . , n. Here, we assume
that

U
i
is uniformly distributed among [1, ], where N.
Let

X
L
j
be the random variable that represents the amount of
throughput degradation (in bits) due to the data padding of M
j
s
non-real-time trafc when using c
low
. Because the throughput
degradation caused by MSSs using c
high
is zero, we have
E[

S[

N
L
= m] = E
_
_
m

j=1

X
L
j
_
_
. (10)
Explicitly,

X
L
i
and

X
L
j
are independent of each other for any
i ,= j; therefore, we have
E
_
_
m

j=1

X
L
j
_
_
=
m

j=1
E
_

X
L
j
_
. (11)
LIANG et al.: OVERHEAD REDUCTION, TRAFFIC SCHEDULING, AND BURST ALLOCATION IN OFDMA NETWORKS 1749
Now, let us dene I
U
i
as an indicator of representing whether
M
i
has urgent trafc such that I
U
i
= 1 if M
i
has urgent traf-
c; otherwise, I
U
i
= 0. Because the bursts of low-rate MSSs
without urgent trafc will not contain the data padding of non-
real-time trafc, no throughput degradation will be caused by
them. Therefore, we can derive
E
_

X
L
j
_
=E
_

X
L
j
[I
U
j
= 1
_
Prob
_
I
U
j
= 1

=
_

u=1
f(

U
j
= u)

_
Prob
_
I
U
j
= 1

(12)
where
f(

U
j
= u) =
__
u

bkt
c
low
_

bkt
c
low
_

bkt
(c
high
c
low
)
is a function for representing the throughput degradation
caused by a low-rate MSS with non-real-time data padding
when

U
j
= u.
By combining (9)(12), we can derive that
E[

S] =
n

m=1
_
_
m

j=1
_

u=1
f(

U
j
= u)

_
Prob
_
I
U
j
= 1

_
_
Prob[

N
L
= m]. (13)
Finally, the throughput loss by our burst allocator can be
calculated by combining (8) and (13) into (6).
VI. PERFORMANCE EVALUATION
To verify the effectiveness of our cross-layer framework, we
develop a simulator in C++ based on the architecture in [15],
as shown in Fig. 6. The simulator contains three layers: The
trafc-generating module in the upper layer creates the MSSs
demands according to their real-time and non-real-time trafc
requirements. In the MAC layer, the queuing module maintains
the data queues for each MSS and the scheduling module
conducts the actions of the scheduler. In the PHY layer, the
channel-estimating module simulates the channel conditions
and estimates the transmission rate of each MSS, and the burst-
allocating module conducts the actions of the burst allocator.
The arrows in Fig. 6 show the interaction between all the
modules in our simulator. In particular, the trafc-generating
module will generate trafc and feed them to the scheduling
module for allocating resources and to the queuing module for
simulating the queue of each trafc. The channel-estimating
module will send the transmission rates of MSSs to both the
scheduling and burst allocating modules for their references.
In addition, the scheduling and the burst-allocating modules
will interact with each other, particularly for our scheme.
The simulator adopts a fast Fourier transform (FFT) size of
1024 and the zone category as PUSC with reuse 1. The frame
duration is 5 ms. This way, we have X = 12 and Y = 30.
Six MCSs are adopted, which are denoted by a set MCS =
QPSK1/2, QPSK3/4, 16QAM1/2, 16QAM3/4, 64QAM2/3,
Fig. 6. Architecture of our C++ simulator.
TABLE III
AMOUNTS OF DATA CARRIED BY EACH SLOT AND THE MINIMUM
REQUIRED SNR THRESHOLDS OF DIFFERENT MCSS
64QAM3/4. For the trafc-generating module, the types of
real-time trafc include UGS, rtPS, and ertPS, whereas the
types of non-real-time trafc include nrtPS and BE. Each MSS
has an admitted real-time data rate R
rt
i
of 0 200 bits and an
admitted non-real-time data rate R
nrt
i
of 0 500 bits/frame. In
each frame, each MSS generates 0 2R
rt
i
amount of real-time
data and R
nrt
i
4R
nrt
i
amount of non-real-time data.
For the channel-estimating module, we develop two scenar-
ios to estimate the transmission rate of each MSS. The rst
scenario, called the Stanford University Interim (SUI) scenario,
is based on the SUI path loss model recommended by the IEEE
802.16 Task Group [24]. In particular, each MSS will roam
inside the BSs signal coverage (the largest area that the BS
can communicate with each MSS using the lowest QPSK1/2
MCS) and move following the random waypoint model, with
the maximal speed of 20 m/s [25]. The transmission rate of each
MSS M
i
is determined by its received SNR as
SNR(BS, M
i
) = 10 log
10
_

P(BS, M
i
)
BW N
o
_
where BW is the effective channel bandwidth (in hertz), N
o
is
the thermal noise level, and

P(BS, M
i
) is the received signal
power at M
i
, which is dened by

P(BS, M
i
) =
G
BS
G
M
i
P
BS
L(BS, M
i
)
where P
BS
is the transmission power of the BS, G
BS
and
G
M
i
are the antenna gains at the BS and M
i
, respectively, and
L(BS, M
i
) is the path loss from the BS to M
i
. Given M
i
s
SNR, the BS can determine M
i
s MCS based on Table III. In
particular, the BS will choose the highest MCS whose minimum
required SNR is smaller than SNR(BS, M
i
). Table IV lists the
parameters used in the SUI scenario.
1750 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 60, NO. 4, MAY 2011
TABLE IV
SIMULATION PARAMETERS USED IN THE SUI SCENARIO
Fig. 7. Six-state Markov chain to model the channel condition.
The second scenario, called the Markov scenario, adopts a
six-state Markov chain [26] to simulate the channel condition of
each MSS, as shown in Fig. 7. In particular, let MCS[i] be the
ith MCS, i = 1, . . . , 6. Suppose that an MSS uses MCS[i] to
t its channel condition at the current frame. The probabilities
that the MSS switches to MCS[i 1] and MCS[i + 1] in
the next frame are both (1/2)p
c
, and the probability that it
remains unchanged is 1 p
c
. For the boundary cases of i =
1 and 6, the probabilities of switching to MCS[2] and MCS[5],
respectively, are both p
c
. Unless otherwise stated, we set p
c
=
0.5, and the initial i value of each MSS is randomly selected
from 2 to 5.
We compare our cross-layer framework with the high-rate-
rst (HRF) scheme [21], the modied proportional fair (MPF)
scheme [10], the rate maximization with fairness consideration
(RMF) scheme [20], and the QoS guarantee (QG) scheme [22].
HRF always rst selects the MSS with the highest transmission
rate C
i
to serve. MPF assigns priorities to MSSs, where an
MSS with a higher C
i
value and a lower amount of received
data is given a higher priority. RMF rst allocates resources
to unsatised MSSs according to their minimum requirements,
where MSSs are sorted by their transmission rates. If there
remain resources, they are allocated to the MSSs with higher
transmission rates. Similarly, QG rst satises the minimum
requirements of each MSSs trafc, which are divided into real-
time and non-real-time trafc. Then, the remaining resources
are allocated to MSSs with higher transmission rates. Because
both HRF and MPF implement only the scheduler, we adopt
the scheme in [4] as their burst allocators. In our framework,
we use B = 5 buckets and set = 0.3 in P2, unless otherwise
stated. In Section VI-F, we will discuss the effects of these two
parameters on the system performance. The duration of each
experiment is at least 1000 frames.
A. Network Throughput
We rst compare the network throughput under different
number of MSSs (i.e., n), where the network throughput is
dened by the amount of MSSs data (in bits) transmitted by the
BS during 1000 frames. We observe the case when the network
becomes saturated, where there are 60 90 MSSs to be served.
Fig. 8 shows the simulation results under both the SUI and
the Markov scenarios, where the trends are similar. Explicitly,
when the number of MSSs grows, the throughput increases but
will eventually become steady when there are too many MSSs
(i.e., n 80). The throughput under the SUI scenario is lower
than the throughput under the Markov scenario, because some
MSSs may move around the boundary of the BSs coverage,
leading to a lower SNR and, thus, a lower MCS. Under the
Markov scenario, a higher p
c
means that each MSS may more
frequently change its MCS, and vice versa.
In general, both RMF and QG ignore the effect of IE over-
heads on network performance so that their throughput will
be degraded. Although HRF rst serves MSSs with higher
transmission rates, its throughput is not the highest. The reason
is that HRF not only ignores the importance of IE overheads but
also neglects the effect of C
i
/C
avg
i
factor on potential through-
put when scheduling trafc. The throughput of MPF is higher
than the throughput of RMF, QG, and HRF for the following
two reasons. First, MPF prefers MSSs that use the higher trans-
mission rates, which is similar to HRF. However, HRF incurs
higher IE overheads because of the scheduling methodology
(which will be veried in Section VI-B). Second, both RMF
and QG try to schedule every trafc in each frame, which gen-
erates too many IEs (in fact, we can postpone scheduling some
trafc to reduce IE overheads while still guaranteeing long-term
fairness, as will be veried in Sections VI-B and C). On the
other hand, MPF enjoys higher throughput, because it takes
care of IE overheads from the viewpoint of the scheduler. In
particular, our cross-layer framework has the highest through-
put in most cases because of the following two reasons. First,
our scheduler assigns a higher priority to MSSs with higher
C
i
and C
i
/C
avg
i
values and thus makes MSSs receive their
data in higher transmission rates. Second, both our scheduler
and burst allocator can effectively decrease the number of IEs
and acquire more subframe space for data transmission. Note
that, when n = 90, our cross-layer framework will try to satisfy
a large number of urgent trafc to avoid their packets being
dropped. In this case, its throughput is slightly lower than
the throughput of MPF, but our cross-layer framework can
signicantly reduce the real-time packet-dropping ratio, as will
be shown in Section VI-D.
B. IE Overheads and Subframe Utilization
Fig. 9 shows the average number of IEs in each downlink
subframe. As discussed earlier, HRF, RMF, and QG do not
consider IE overheads; therefore, they will generate a large
number of IEs. The situation becomes worse when the number
of MSSs grows, because each MSS needs to be allocated
with at least one burst (and, thus, one IE). By considering
IE overheads in the scheduler, MPF can reduce the average
number of IEs per frame. It can be observed that, when the
number of MSSs grows, the number of IEs in MPF reduces.
The reason is that MPF allocates more resources to MSSs in
a frame to reduce the total number of scheduled MSSs, thus
reducing the number of allocated bursts (and IEs). In Fig. 9,
our cross-layer framework generates the smallest number of
IEs per frame, because both the proposed scheduler and burst
allocator consider IE overheads, and the framework can adjust
LIANG et al.: OVERHEAD REDUCTION, TRAFFIC SCHEDULING, AND BURST ALLOCATION IN OFDMA NETWORKS 1751
Fig. 8. Comparison on network throughput. (a) SUI scenario. (b) Markov scenario (p
c
= 0.8). (c) Markov scenario (p
c
= 0.2).
Fig. 9. Comparison on IE overheads. (a) SUI scenario. (b) Markov scenario.
Fig. 10. Comparison on subframe utilization. (a) SUI scenario. (b) Markov scenario.
the number of nonurgent real-time trafc to be served to avoid
generating too many bursts.
IE overheads have a strong impact on the utilization of down-
link subframes, as reected in Fig. 10. Because HRF, RMF, and
QG generate a large number of IEs, their subframe utilization
will be lower than MPF and our cross-layer framework. It can
be observed that the number of buckets B signicantly affects
the subframe utilization of our cross-layer framework. In par-
ticular, a very large B (e.g., 30) will reduce the amount of data
carried in each bucket and thus generate many small bursts. On
the other hand, a very small B (e.g., 1) may degrade the func-
tionality of buckets, and thus, some resource assignments may
not fully utilize the bursts allocated to them. Based on Fig. 10,
we suggest setting B = 5 to get the best utilization, and the
analysis result in Section VI-G will also validate this point.
C. Long-Term Fairness
Next, we verify whether each scheme can guarantee long-
term fairness under a highly congested network, where there are
140 200 MSSs. Fig. 11 shows the fairness indices (FI) of all
schemes. Recall that the network becomes saturated when there
are 80 MSSs. Thus, it is impossible to get a FI of 1, because the
network resource is not enough to satisfy the requirements of all
trafc. Based on Fig. 11, HRF incurs the lowest index, because
it always serves MSSs that use higher transmission rates. By
considering the amount of allocated data of each MSS, MPF
can have a higher index than HRF. QG and RMF try to satisfy
the minimum requirement of each trafc in every frame, thus
leading to higher indices. Because RMF allocates the resources
to MSSs sorted by their transmission rates, its index will be
lower than QG.
1752 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 60, NO. 4, MAY 2011
Fig. 11. Comparison on long-term fairness. (a) SUI scenario. (b) Markov scenario.
Fig. 12. Comparison on real-time packet-dropping ratios under different numbers of MSSs. (a) SUI scenario. (b) Markov scenario.
Our cross-layer framework has the highest FI (more than
0.85) due to the following two reasons. First, our priority-based
scheduler only schedules ratio of nonurgent real-time trafc
to avoid starving non-real-time trafc. Second, our cross-layer
framework tries to reduce the IE overheads and acquire more
frame space to allocate bursts for MSSs trafc. In this case, we
have more resources to fairly distribute among MSSs. Thus, our
cross-layer framework can maintain long-term fairness, even in
a highly congested network.
D. Packet-Dropping Ratios of Real-Time Trafc
We then observe the packet-dropping ratios of real-time
trafc, where each MSS will generate 0 2R
rt
i
real-time data
in each frame. When a real-time packet is not transmitted
within 6 frames (i.e., 30 ms) after being generated, it will be
dropped. Fig. 12 shows the real-time packet-dropping ratios
of all schemes under 10 110 MSSs. Both HRF and MPF
distribute resources to MSSs based on the transmission rates
without considering the trafc types; therefore, their ratios
begin raising when n 50. In this case, a large amount of
non-real-time trafc will compete with real-time trafc for the
limited resource. On the other hand, the ratios of RMF and QG
begin raising when n 90. Because both RMF and QG try to
satisfy the minimum requirements of all trafc in each frame,
they can avoid real-time packet dropping when the network
is not saturated (i.e., n < 90). Our cross-layer framework can
have almost zero ratio due to the following three reasons. First,
our priority-based scheduler assigns urgent real-time trafc
with the highest priority. In addition, it schedules a ratio
of nonurgent real-time trafc to avoid generating too many
urgent trafc in the following frames. Second, our bucket-based
burst allocator arranges bursts based on the priorities from the
scheduler; therefore, the bursts of the urgent real-time trafc
can rst be allocated to avoid packet dropping. Third, both
our scheduler and burst allocator try to reduce IE overheads,
and thus, more urgent real-time trafc can be served in each
frame.
Fig. 13 shows the real-time packet-dropping ratios of all
schemes under different admitted non-real-time data rates,
where the network is saturated. Because MPF proportionally
distributes resources among MSSs, it incurs the highest real-
time packet-dropping ratio. On the other hand, because some
MSSs with real-time trafc may have higher transmission rates,
the ratio of HRF is lower than the ratio of MPF. As discussed
earlier, both RMF and QG try to satisfy the minimum require-
ment of each trafc, and thus, their ratios can become lower.
Note that, because QG differentiates real-time trafc from non-
real-time trafc, its ratio is lower than the ratio of RMF. Our
cross-layer framework always has a zero ratio, because the
bursts of urgent real-time trafc are rst allocated, and our
framework can acquire more frame space to serve urgent real-
time trafc by reducing IE overheads.
Because the trends under both SUI and Markov scenarios are
similar, we only show the results under the Markov scenario in
the following experiments.
LIANG et al.: OVERHEAD REDUCTION, TRAFFIC SCHEDULING, AND BURST ALLOCATION IN OFDMA NETWORKS 1753
Fig. 13. Comparison on real-time packet-dropping ratios under different admitted non-real-time rates. (a) SUI scenario. (b) Markov scenario.
Fig. 14. Comparison on non-real-time satisfaction ratios of the bottom 10%
MSSs under the Markov scenario.
E. Satisfaction Ratios of Non-Real-Time Trafc
Next, we measure the satisfaction ratios of non-real-time
trafc [by (5)] under a saturated network. Fig. 14 shows
the satisfaction ratios of non-real-time trafc of the bottom
10% MSSs. When the non-real-time rate is larger than
125 bits/frame, the ratio of HRF is zero, because these
bottom 10% MSSs (whose transmission rates must be lower)
are starved. The ratio of MPF starts diminishing when the
non-real-time rate is larger than 250 bits/frame, because MPF
proportionally distributes resources among trafc. By satisfying
the minimum requirement of each trafc, the ratios of RMF and
QGare close to one. Our cross-layer framework can have a ratio
of nearly one for the bottom 10% MSSs, which means that non-
real-time trafc will not be starved, although our scheme prefers
real-time trafc.
F. Effects of System Parameters
We then observe the effects of system parameters in our
cross-layer framework on network throughput, subframe uti-
lization, and IE overheads under a saturated network (i.e.,
the number of MSS is 90). Fig. 15 shows the impact of the
number of buckets (i.e., B) on network throughput, utilization,
and overhead ratios when Y = 32. Here, the overhead ratio is
dened as the ratio of the number of slots used for MAP infor-
mation (e.g., DL-MAP, UL-MAP, and IEs) to the total number
of slots in a downlink subframe. In general, the utilization
decreases when the overhead ratio increases, because they are
complementary. Based on Fig. 15, the utilization rst increases
Fig. 15. Effect of the number of buckets B on the network throughput,
subframe utilization, and IE overheads under the Markov scenario.
and then decreases when B grows. The former increment is
because some resource assignments do not fully utilize their
allocated bursts. On the other hand, the latter decrement is
because the burst allocator generates too many bursts to satisfy
the thinner buckets. The overhead ratio increases when B
increases, because more IEs are generated. In addition, when
B 4, the throughput increases when B grows, because more
buckets may serve more requests. On the other hand, when
B 8, such a trend reverses, because more IEs are generated,
causing lower utilization. Based on Fig. 15, we suggest setting
B = 4 8, because this range of B value improves both
throughput and utilization while reducing IE overheads.
Fig. 16 shows the effects of and B on real-time packet-
dropping ratios and network throughput in our cross-layer
framework. Explicitly, the real-time packet-dropping ratio
decreases when grows, because more real-time trafc can
be served. However, when increases, the throughput may
decrease, because the scheduler has to select more nonurgent
real-time trafc to serve. In this case, some real-time trafc
with lower transmission rates may be served, which degrades
the throughput. As aforementioned, a large B may generate
more IEs and thus reduce the utilization. Thus, the throughput
in the case of larger B (e.g., B = 15 and 30) starts dropping
earlier than in the case of smaller B (e.g., B = 5 and 10). Based
on Fig. 16, we suggest setting = 0.15 0.45, because this
range of value not only improves the network throughput but
also reduces real-time packet-dropping ratios under different
values of B.
1754 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 60, NO. 4, MAY 2011
Fig. 16. Effect of on the network throughput and real-time packet-dropping ratios under the Markov scenario. (a) Smaller B. (b) Larger B.
Fig. 17. Effect of the number of buckets (B) on the throughput loss L
(by analysis) and the total network throughput (by simulation) under the
Markov scenario.
G. Verication of Throughput Analysis
Finally, we verify our analytic results in the part where two
transmission rates, c
low
= 48 bits/slot and c
high
= 96 bits/slot,
are adopted. The probabilities that an MSS can use c
low
and
c
high
are both 0.5. Then, the probability that m MSSs can use
c
low
is
Prob[

N
L
= m] =C
n
m
(Prob[transmission rate = c
low
])
m
(Prob[transmission rate = c
low
])
nm
=
n!
m!(n m)!
(0.5)
m
(0.5)
nm
=
(0.5)
n
n!
m!(n m)!
.
In addition, the probability that an MSS M
i
has urgent
data is
Prob
_
I
U
i
= 1

= (1 )
T
D
1
where T
D
is the deadline of real-time data that will be dropped
(in frames). Note that, because the scheduler will serve all
queued real-time data from the top n MSSs in each frame,
after (T
D
1) frames, the probability of an MSS with urgent
data is no more than (1 )
T
D
1
. In our simulation, we set
= 0.3, T
D
= 6 frames, and = 200 bits/frame.
Fig. 17 shows the analysis and simulation results. When B <
4, the throughput loss L decreases, but the network throughput
increases as B increases. On the other hand, when B > 8, L
increases, but the network throughput decreases as B increases.
This result indicates that the minimum value of L by analysis
appears at the range of B = [4, 8], whereas the maximum
network throughput by simulation appears at the same range
of B = [4, 8]. Thus, our analysis and simulation results are
consistent. Based on Fig. 17, we suggest setting B = 4 8
to maximize the network throughput and minimize L, which
matches the results in Fig. 15. Therefore, our analysis can
validate the simulation results and provide guidelines for the
setting of the burst allocator.
VII. CONCLUSION
In this paper, we have proposed a cross-layer framework
that covers the issues of overhead reduction, real-time and
non-real-time trafc scheduling, and burst allocation in an
IEEE 802.16 OFDMA network. Compared with existing so-
lutions, our framework is more complete, because it involves
codesigning both the two-tier priority-based scheduler and the
bucket-based burst allocator. Our scheduler reduces potential
IE overheads by adjusting the number of MSSs to be served.
With a two-tier priority rules, it guarantees real-time trafc
delays, ensures satisfaction ratios of non-real-time trafc, and
maintains long-term fairness. On the other hand, our burst
allocator incurs lowcomplexity and guarantees a bounded num-
ber (k + (Y/
bkt
) 1) of IEs to accommodate data bursts.
In addition, it follows the priority rule from the scheduler to
avoid packet dropping of urgent real-time trafc. We have also
analyzed the impact of the number of buckets on the throughput
loss. Through both analyses and simulations, we show how we
can adjust the system parameters to reduce IE overheads, im-
prove subframe utilization, and enhance network throughput. In
addition, these results verify that such a cross-layer framework
signicantly improves the resource allocation and utilization
of downlink communications in WiMAX networks. For future
work, we will investigate how we can optimize the scheduler
and burst allocator for some particular cases, e.g., various trafc
characteristics and MSS densities. In addition, we will consider
extending our results for WiMAX relay networks.
REFERENCES
[1] IEEE Standard for Local and Metropolitan Area Networks Part 16Air
Interface for Fixed and Mobile Broadband Wireless Access Systems
Amendment 2: Physical and MediumAccess Control Layers for Combined
Fixed and Mobile Operation in Licensed Bands and Corrigendum 1, IEEE
Std. 802.16e-2005, 2006.
LIANG et al.: OVERHEAD REDUCTION, TRAFFIC SCHEDULING, AND BURST ALLOCATION IN OFDMA NETWORKS 1755
[2] B. Rong, Y. Qian, and H. H. Chen, Adaptive power allocation and call ad-
mission control in multiservice WiMAX access networks, IEEE Wireless
Commun., vol. 14, no. 1, pp. 1419, Feb. 2007.
[3] K. Sundaresan and S. Rangarajan, Efcient algorithms for leveraging
spatial reuse in OFDMA relay networks, in Proc. IEEE INFOCOM,
2009, pp. 15391547.
[4] Y. Ben-Shimol, I. Kitroser, and Y. Dinitz, Two-dimensional mapping
for wireless OFDMA systems, IEEE Trans. Broadcast., vol. 52, no. 3,
pp. 388396, Sep. 2006.
[5] H. S. Kim and S. Yang, Tiny MAP: An efcient MAP in IEEE
802.16/WiMAX broadband wireless access systems, Comput. Commun.,
vol. 30, no. 9, pp. 21222128, Jun. 2007.
[6] Y. Ma and D. Kim, Rate-maximization scheduling schemes for uplink
OFDMA, IEEE Trans. Wireless Commun., vol. 8, no. 6, pp. 31933205,
Jun. 2009.
[7] J. Shi and A. Hu, Maximum utility-based resource allocation
algorithmin the IEEE 802.16 OFDMAsystem, in Proc. IEEE ICC, 2008,
pp. 311316.
[8] R. Pitic and A. Capone, An opportunistic scheduling scheme with min-
imum data-rate guarantees for OFDMA, in Proc. IEEE WCNC, 2008,
pp. 17161721.
[9] N. A. Ali, M. Hayajneh, and H. Hassanein, Cross-layer scheduling algo-
rithm for IEEE 802.16 broadband wireless networks, in Proc. IEEE ICC,
2008, pp. 38583862.
[10] J. Kim, E. Kim, and K. S. Kim, A new efcient BS scheduler and
scheduling algorithm in WiBro systems, in Proc. IEEE ICACT, 2006,
vol. 3, pp. 14671470.
[11] T. Wang, H. Feng, and B. Hu, Two-dimensional resource allocation for
OFDMA system, in Proc. IEEE Int. Conf. Commun. Workshops, 2008,
pp. 15.
[12] T. Ohseki, M. Morita, and T. Inoue, Burst construction and packet-
mapping scheme for OFDMA downlinks in IEEE 802.16 systems, in
Proc. IEEE GLOBECOM, 2007, pp. 43074311.
[13] X. Perez-Costa, P. Favaro, A. Zubow, D. Camps, and J. Arauz, On the
challenges for the maximization of radio resources usage in WiMAX
networks, in Proc. IEEE CCNC, 2008, pp. 890896.
[14] A. Erta, C. Cicconetti, and L. Lenzini, A downlink data region allocation
algorithm for IEEE 802.16e OFDMA, in Proc. IEEE Int. Conf. Inf.,
Commun. Signal Process., 2007, pp. 15.
[15] T. Kwon, H. Lee, S. Choi, J. Kim, D. H. Cho, S. Cho, S. Yun,
W. H. Park, and K. Kim, Design and implementation of simulator based
on cross-layer protocol between MAC and PHY layers in WiBro com-
patible IEEE 802.16e OFDMA system, IEEE Commun. Mag., vol. 43,
no. 12, pp. 136146, Dec. 2005.
[16] Intel ships its next-generation WiMAX chip with support for mobile
networks. [Online]. Available: http://www.intel.com/pressroom/archive/
releases/2006/20061011comp.htm
[17] Y. Tcha, M. S. Kim, and S. C. Lee, A compact MAP message to provide
a virtual multiframe structure for a periodic xed-bandwidth assignment
scheme, IEEE Std. C802.16e-04/368r2, 2004.
[18] J. Kim and D. H. Cho, Piggybacking scheme of MAP IE for minimizing
MAC overhead in the IEEE 802.16e OFDMA systems, in Proc. IEEE
VTC, 2007, pp. 284288.
[19] K. Kim, Y. Han, and S. L. Kim, Joint subcarrier and power allocation in
uplink OFDMA systems, IEEE Commun. Lett., vol. 9, no. 6, pp. 526
528, Jun. 2005.
[20] L. Gao and S. Cui, Efcient subcarrier, power, and rate allocation
with fairness consideration for OFDMA uplink, IEEE Trans. Wireless
Commun., vol. 7, no. 5, pp. 15071511, May 2008.
[21] X. Zhu, J. Huo, S. Zhao, Z. Zeng, and W. Ding, An adaptive resource
allocation scheme in OFDMA-based multiservice WiMAX systems, in
Proc. IEEE ICACT, 2008, pp. 593597.
[22] X. Zhu, J. Huo, X. Xu, C. Xu, and W. Ding, QoS-guaranteed scheduling
and resource allocation algorithm for IEEE 802.16 OFDMA system, in
Proc. IEEE ICC, 2008, pp. 34633468.
[23] D. M. Chiu and R. Jain, Analysis of the increase and decrease algorithms
for congestion avoidance in computer networks, J. Comput. Netw. ISDN,
vol. 17, no. 1, pp. 114, Jun. 1989.
[24] Channel models for xed wireless applications. [Online]. Available:
http://www.ieee802.org/16/tga/docs/80216a-03_01.pdf
[25] C. Bettstetter, G. Resta, and P. Santi, The node distribution of the random
waypoint mobility model for wireless ad hoc networks, IEEE Trans.
Mobile Comput., vol. 2, no. 3, pp. 257269, Jul.Sep. 2003.
[26] H. S. Wang and N. Moayeri, Finite-state Markov channelA useful
model for radio communication channels, IEEE Trans. Veh. Technol.,
vol. 44, no. 1, pp. 163171, Feb. 1995.
Jia-Ming Liang (S10) received the B.S. and M.S.
degrees in computer science and engineering from
the National Taiwan Ocean University, Keelung,
Taiwan, and the National Sun Yat-Sen University,
Kaohsiun, Taiwan, in 2004 and 2006, respectively.
He is currently working toward the Ph.D. degree in
computer science with the Department of Computer
Science, National Chiao-Tung University, Hsinchu,
Taiwan.
His research interests include resource manage-
ment in wireless networks, cross-layer design, and
WirelessMAN technologies.
Jen-Jee Chen (M11) received the Ph.D. degree
in computer science from the National Chiao-Tung
University, Hsinchu, Taiwan, in 2009.
Since 2011, he has been an Assistant Professor
with the Department of Electrical Engineering,
National University of Tainan, Tainan, Taiwan. His
research interests include wireless communications
and networks, personal communications, mobile
computing, and cross-layer design.
Dr. Chen is a member of the Phi Tau Phi Society.
You-Chiun Wang (M08) received the Ph.D. degree
in computer science from the National Chiao-Tung
University, Hsinchu, Taiwan, in 2006.
He is currently a Postdoctoral Research Fellow
with the Department of Computer Science, National
Chiao-Tung University. His research involves the
design and evaluation of wireless communication
protocols and distributed network algorithms. His
current research interests include broadband wireless
communication, mobile ad hoc and sensor networks,
and mobile computing.
Yu-Chee Tseng (SM03) received the Ph.D. degree
in computer and information science from The Ohio
State University, Columbus, in 1994.
From 2005 to 2009, he was the Chairman of the
Department of Computer Science, National Chiao-
Tung University, Hsinchu, Taiwan, where he has
been a Professor since 2000 and the Associate Dean
since 2007. Since 2005, he has been serving on
the editorial board of Telecommunication Systems.
His research interests include mobile computing,
wireless communication, and parallel and distributed
computing.
Dr. Tseng serves or has served on the editorial boards of the IEEE
TRANSACTIONS ON VEHICULAR TECHNOLOGY (20052009), the IEEE
TRANSACTIONS ON MOBILE COMPUTING (2006present), and the
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
(2008present).