Two-dimensional downlink burst construction in IEEE 802.16 networks

-

Documents
18 pages
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

Several burst construction algorithms for orthogonal frequency division multiple access were proposed. However, these algorithms did not meet the downlink burst characteristics specified in the IEEE 802.16 standard. This article therefore proposes the best corner-oriented algorithm (BCO). BCO not only complies with downlink burst characteristics, but also considers the three issues to obtain high throughput, as follows: BCO maintains all free slots as a continuous area by constructing each burst in the corner of the available bandwidth area for minimizing external fragmentation; BCO shrinks the burst area to minimize internal fragmentation, if the requested bandwidth has been satisfied; and for exploring the continuous subchannels with good channel quality, BCO ensures that the burst adopts an optimal modulation coding scheme by selecting the excellent corner that can generate the maximal throughput. The simulation results indicate that BCO achieves 2-9 times the throughput achieved by the previous algorithms under a heavy load.

Sujets

Informations

Publié par
Publié le 01 janvier 2011
Nombre de lectures 5
Langue English
Signaler un problème

Lai and Chen EURASIP Journal on Wireless Communications and Networking 2011, 2011:173
http://jwcn.eurasipjournals.com/content/2011/1/173
RESEARCH Open Access
Two-dimensional downlink burst construction in
IEEE 802.16 networks
*Yuan-Cheng Lai and Yen-Hung Chen
Abstract
Several burst construction algorithms for orthogonal frequency division multiple access were proposed. However,
these algorithms did not meet the downlink burst characteristics specified in the IEEE 802.16 standard. This article
therefore proposes the best corner-oriented algorithm (BCO). BCO not only complies with downlink burst
characteristics, but also considers the three issues to obtain high throughput, as follows: BCO maintains all free
slots as a continuous area by constructing each burst in the corner of the available bandwidth area for minimizing
external fragmentation; BCO shrinks the burst area to minimize internal fragmentation, if the requested bandwidth
has been satisfied; and for exploring the continuous subchannels with good channel quality, BCO ensures that the
burst adopts an optimal modulation coding scheme by selecting the excellent corner that can generate the
maximal throughput. The simulation results indicate that BCO achieves 2-9 times the throughput achieved by the
previous algorithms under a heavy load.
Keywords: burst construction, downlink, IEEE, 802.16, OFDMA
1. Introduction attempted to determine the optimal matches between
Because IEEE 802.16 uses the technique of orthogonal bursts and subchannels [3-8].
frequency division multiple access (OFDMA), the band- The IEEE 802.16 standard defines a number of specifi-
width resources are represented by a two-dimensional cations to alleviate the overhead of management mes-
area of slots, in which the two dimensions are time in sages and to concentrate the transmission power on
units of symbols and frequency in units of subchannels specific subchannels for battery-powered devices, as fol-
[1]. Therefore, the bandwidth allocation in IEEE 802.16 lows: (1) the burst must be a continuous bandwidth
must consider the construction of a two-dimensional area, (2) the shapes of the bursts used in downlink and
bandwidth area, called a burst, assigned to a connection. uplink transmissions should be rectangular and multi-
The subchannel diversity should be considered when rectangular, respectively, and (3) one burst should use
constructing bursts. Subchannel diversity means that a only one MCS based on the worst signal-to-noise ratio
connection uses a different modulation coding scheme (SNR) among the assigned subchannels [1,9].
(MCS) on various subchannels because the connection The previous researches that focused on the maxi-
encounters various channel qualities on various sub- mum matching problem violated the specifications in
channels [2]. Therefore, for each connection, each burst IEEE 802.16 standard, and are thus unpractical. There-
must be constructed in its corresponding best-quality fore, a number of researchers regarded the burst con-
struction problem as a variant of the bin packingsubchannels, i.e., the subchannels on which the connec-
problem. So-In et al. [10] designed the enhanced one-tion receives the optimal channel quality to maximize
bandwidth usage. Several algorithms for the IEEE 802.16 column striping with non-increasing area first mapping
burst construction problem were proposed to obtain the algorithm (eOCSA), which constructs each burst from
higher throughput. A number of researchers regarded bottom right to top left of the available bandwidth area.
this problem as a maximum matching problem and Wang et al. [11] developed the weighted less flexibility
first algorithm (WLFF), which constructs each burst on
athe best edge selected in the free bandwidth area. The
* Correspondence: pplong@gmail.com
best edge is the edge on which a constructed burstDepartment of Information Management, National Taiwan University of
Science and Technology, #43, Sec. 4, Keelung Rd., Taipei 106, Taiwan
© 2011 Lai and Chen; licensee Springer. This is an Open Access article distributed under the terms of the Creative Commons
Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in
any medium, provided the original work is properly cited.Lai and Chen EURASIP Journal on Wireless Communications and Networking 2011, 2011:173 Page 2 of 18
http://jwcn.eurasipjournals.com/content/2011/1/173
generates the minimal variance of the sub-blocks in the 2. Background
free bandwidth area. Thus, constructing the burst on 2.1. IEEE 802.16 network
this best edge provides the most flexibility for the fol- The IEEE 802.16 network consists of a base station (BS)
lowing burst construction. eOCSA and WLFF conform and a number of subscriber stations (SSs). The BS pro-
to the specifications (1) and (2); however, they comple- vides connectivity, radio resource management, and
tely neglect subchannel diversity and the specification control of SS, which supports the connectivity with the
(3). BS.
A number of issues must be addressed to conform to The two layers in the IEEE 802.16 protocol stack are
the specifications and maximize the throughput. First, the physical layer, which transfers raw data, and the
external fragmentation may occur because the burst MAC layer, which supports the physical layer by ensur-
must be a continuous bandwidth area, which means that ing that the radio resources are used efficiently. The
the total available slots are sufficient to satisfy a burst; three duplex modes in the physical layer with OFDMA
however, the lack of contiguity may prevent their use by are Time Division Duplex (TDD), Frequency Division
this burst. Thus, the external fragmentation should be Duplex (FDD), and Half-duplex Frequency Division
avoided. Second, because of the rectangular shape of a (H-FDD). The TDD is the most attractive
downlink burst or improper slot allocation, internal duplex mode because of its flexibility. In addition, the
fragmentation may occur, which results from a burst modulation methods, that is quadrature phase shift key-
with capacity exceeding the requested bandwidth. The ing (QPSK), 16 quadrature amplitude modulation
internal fragmentation must be minimized because the (16QAM), or 64 quadrature amplitude modulation
unused slots internal to a burst are wasted. Third, (64QAM), and the associated coding rate for data trans-
because one burst must use one MCS based on the mission are selected according to the channel quality,
worst SNR among the assigned subchannels, it must be that is, signal-to-noise ratio (SNR).
constructed in its corresponding optimal block, i.e., a An IEEE 802.16 frame for downlink and uplink trans-
block in which a number of continuous subchannels missions is divided into downlink (DL) and uplink (UL)
have good SNRs. subframes in the time domain of the TDD mode (the
Therefore, this article proposes a one downlink burst right part of Figure 1). A burst is an allocated band-
construction algorithm, called the best corner-oriented width assigned to one dedicated connection of one SS
algorithm (BCO), to maximize the throughput. BCO not and is formed by slots. A slot is the minimal bandwidth
only conforms to the constraints in IEEE 802.16 stan- allocation unit, and consists of one subchannel and one
dards, but also considers these issues. To avoid external to three symbols. A subchannel is the smallest allocation
fragmentation, BCO constructs each burst in a corner of unit in the frequency domain, and a symbol is the smal-
the free bandwidth area to ensure that all free slots are lest allocation unit in the time domain. A number of
within a continuous area. A corner is the intersection of other fields in a frame provide specific functions. For
the horizontal edge and left-hand vertical edge of the example, preamble synchronizes each SS, DL/UL-MAP
free bandwidth area. To minimize internal fragmenta- describes the position and measure of each downlink/
tion, BCO shrinks the area of the burst if the requested uplink burst, and frame control header specifies DL sub-
bandwidth is satisfied to enable unused slots internal to frame prefix and the length of DL-MAP message.
this burst to be used by other bursts. BCO evaluates the In the IEEE 802.16, the SS must acquire bandwidth
channel quality in each corner to explore an optimal from the BS before transmitting or receiving data. On
block, and subsequently constructs the optimal burst in downlink, the BS broadcasts to all SSs, and each SS
the corner in which the burst can provide the largest picks up its destined packets. On uplink, SSs must
throughput. inform the BS of the bandwidth they require for data
This article is organized as follows: Section 2 presents transmission by sending a bandwidth request (BWR).
a discussion of the literature on the IEEE 802.16 net- Upon receiving the BWRs, the BS allocates the bursts in
work, the burst construction in downlink transmission, an uplink subframe to each SS, and subsequently broad-
and related studies. In Section 3, the problem statement casts this information through UL-MAP. After receiving
of the downlink burst construction is formally intro- UL-MAP, each SS uses the allocated burst to transmit
duced, and the issues to solve this problem are pre- its data.
sented. Section 4 provides a description of the proposed Figure 1 demonstrates that, for efficient bandwidth
BCO algorithm in detail. In Section 5, the superior per- use, the BS must consider several factors, including the
formance of BCO in comparison with eOCSA and power saving policy, quality of services (QoS) require-
WLFF is demonstrated by simulation. Finally, conclu- ments, channel quality variation, DL/UL bandwidth
sions and future studies are given in Section 6. ratio, and burst structure. Bandwidth allocation isLai and Chen EURASIP Journal on Wireless Communications and Networking 2011, 2011:173 Page 3 of 18
http://jwcn.eurasipjournals.com/content/2011/1/173
Figure 1 Bandwidth allocation in IEEE 802.16 network.
generally performed in two phases, flow scheduling and to allow a more flexible construction, although the
burst construction, because it is difficult to consider all uplink burst must be constructed with a multi-rectangu-
of these factors in a single step [9]. The objective of lar shape for reducing power consumption of SSs [9].
flow scheduling is to estimate the appropriate number Third, the SS has various levels of SNR on various sub-
of slots to assign to each connection and to subse- channels because of the variable noises on each sub-
quently schedule these connections according to their channel. To minimize the overhead and the complexity
QoS requirements, power saving policy, DL/UL band- of MAC control messages, each burst uses only one
width ratio, and other related factors. Several algorithms MCS based on the worst SNR of all assigned
for flow scheduling were evaluated in the literature (e.g., subchannels.
[12]). In burst construction, however, the burst for each Figure 2 shows an example of the construction of a
connection must be constructed according to the num- downlink burst for a connection with 15 slots allocated
ber of the allocated slots, the burst structure, channel by the flow scheduler. For simplicity, the SNR of each
quality variation, and computational complexity. This subchannel is transformed into its corresponding MCS
study considered the burst construction in the downlink (bytes/slot). A downlink burst can be presented as a rec-
transmission, i.e., downlink burst construction. tangle with a height-width pair (h,w) placed on a start-
ing slot (y,x), which is represented by a row-column
2.2. Burst construction in downlink transmission manner, for example, [(y,x),(h,w)] = [(0,0),(3,5)], as
The downlink burst structure specified by the IEEE shown in Figure 2. The MCS used by this burst is 9
802.16 standard is based on the downlink-partial usage bytes/slot, which is the worst MCS of its occupied sub-
of subchannels (DL-PUSC) method [1], in which the channels, i.e., subchannels 0 to 2.
burst uses partial subchannels in the OFDMA frequency
range. The downlink bursts have three distinct require- 2.3. Related studies
ments. First, the burst must be a continuous area to Because the construction of bursts that can provide the
minimize DL-MAP overhead because DL-MAP is trans- optimal throughput is a NP-hard problem [9], several
mitted at the lowest data rate for robustness (e.g., QPSK algorithms were proposed to raise throughput and were
modulation) and to ensure that all SSs can decode their classified as the max matching solutions and bin packing
embedded contents even under poor channel conditions. solutions. The objective of max matching solutions for
Second, the shape of the downlink burst is a rectangle burst construction is to assign bursts to their best-Lai and Chen EURASIP Journal on Wireless Communications and Networking 2011, 2011:173 Page 4 of 18
http://jwcn.eurasipjournals.com/content/2011/1/173
Figure 2 An example of constructing a downlink burst.
quality subchannels. Therefore, the researchers [3-8] independently use different MCSs. Thus, these burst
transformed this problem into a max matching problem construction solutions make unreasonable assumptions
and attempted to determine the optimal matches and do not comply with the IEEE 802.16 specifications.
between bursts and subchannels to maximize the Burst construction can be regarded as a process of
throughput. Sheu et al. [3] utilized the Hungary algo- placing items of variable heights, widths, and values into
rithm, which is a commonly used combinatorial optimi- a two-dimensional area to maximize the total value of
zation algorithm for the assignment problem with m all items in the area. Thus, the burst construction pro-
connections and m subchannels. Their approach first blem can be regarded as a variant of the bin packing
forms a subchannel assignment matrix, in which each problem, the objective of which is to determine the opti-
row represents one connection and each column repre- mal shape and position of each burst in the bandwidth
area for maximizing the overall throughput of all con-sents one subchannel. The entry in the matrix indicates
structed bursts. However, the traditional studies inthe channel condition with regard to a connection, e.g.,
SNR. The Hungary algorithm is subsequently applied to operational research are not applicable for the burst
determine the optimal connection-subchannel match. construction because they focus on packing objects with
Chen et al. [4] proposed the dynamic frequency selec- fixed shapes and values [13-15]. Thus, a number of algo-
tion approach, in which each connection selects its sub- rithms were proposed [10,11,16-21]. The eOCSA algo-
channel according to the probability distribution, where rithm proposed by So-In et al. [10] constructs the first
the selection probability is determined by channel qual- burst in the bottom right-hand corner of the available
ity. Toufik and Knopp [5] presented a max-min alloca- bandwidth area, and subsequently constructs another
tion policy, which first constructs a matching graph burst if the available bandwidth area above the previous
(from subchannels to connections) and subsequently burst is sufficient. Otherwise, eOCSA subsequently con-
iteratively removes the edge with minimal weight from structs the burst on the left-hand edge of the previous
the matching graph until a perfect match is obtained. If burst. The approaches [16-18] were designed in a
twoormoreconnectionsselectthesamesubchannel, method similar to eOCSA, but with minor modifica-
the probability of selecting this subchannel decreases. tions. Cicconetti et al. [19] further evaluated the internal
All connections subsequently repeat the selection based fragmentation of the burst constructed in different
on the modified probabilities. This process continues directions, that is, vertical direction or horizontal direc-
until each subchannel is only chosen by one connection tion, and subsequently selected the direction that experi-
or until the maximal number of iterations is reached. A enced less fragmentation to construct the burst. Eshanta
number of studies applied greedy methods to allocate et al. [20] also proposed two approaches. One method
the best subchannel to the connection with the highest constructs bursts with the fixed width in a vertical
transmission rate [6-8]. However, as shown in Table 1, direction and the other constructs bursts with the fixed
height in a horizontal direction.these studies assumed that a subchannel is occupied by
only one burst. They also assumed that the subchannels The WLFF [11] constructs the burst on the best edge
assigned to one burst are disjointed and can in the free bandwidth area. The best edge is the edge onLai and Chen EURASIP Journal on Wireless Communications and Networking 2011, 2011:173 Page 5 of 18
http://jwcn.eurasipjournals.com/content/2011/1/173
Table 1 Comparisons among related studies
Author Year Solution Complexity Requested Shape of DL Subchannel
bandwidth burst diversity
4Sheu et al. [3] 2007 Hungary algorithm O(M ) No No Yes
iChen et al. [4] 2006 DFS O(L) No No Yes
3Toufik and Knopp 2004 Max-min allocation O(M ) No No Yes
[5]
Najeh et al. [6] 2005 Greedy O(LM) No No Yes
Kivanc et al. [7] 2003 O(LM) No No Yes
Ergen et al. [8] 2003 O(LM) Yes No Yes
2
So-In et al. [10] 2009 Sequentially construct bursts from one side to O(L ) No Yes No
another
2
Sarigiannidis et al. 2010 O(L ) No Yes No
[16]
Erta et al. [17] 2007 O(LM) No Yes No
Ohseki et al. [18] 2007 O(LM) Yes Yes No
2
Cicconetti et al. 2010 O(L ) No Yes No
[19]
2
Eshanta et al. [20] 2011 O(L ) No Yes No
2
Wang et al. [11] 2008 WLFF O(L ) No Yes No
2
Zubow et al. [21] 2010 GSA O(L ) No Yes No
L, number of connections; M, number of subchannels; i, maximum number of repetition.
which a burst is constructed, and generates the minimal number of slots allocated by the flow scheduler and the
variance of the sub-blocks in the free bandwidth area. requested bandwidth for C, respectively. Although thei
Thus, constructing the burst on this best edge provides flow scheduler estimates A according to the requestedi
the most flexibility for the following burst construction. bandwidth W,italsoconsidersseveralotherfactorsi
The greedy scheduling algorithm [21] was designed in a when performing this estimation. Thus, the throughput
manner similar to WLFF. However, none of the bin provided by A may be lower than W because the flowi i
packing solutions considers subchannel diversity. scheduler does not allocate sufficient slots in the current
Table 1 shows the summary of these methods. The downlink subframe. Conversely, the throughput provided
complexity refers to the time complexity consumed by by A may exceed W because the burst allocator con-i i
the burst construction algorithm. The required band- structs the burst in an excellent block.
width implies that the algorithm not only considers the A two-dimensional matrix R represents the used
allocated slots, but also considers the requested band- MCSs on different subchannels for each connection in
width during burst construction. This is because the order to investigate the effects of subchannel diversity,
bandwidth provided by the allocated slots may exceed where R(i, j) specifies the MCS used by C on the jthi
the required bandwidth of the connection when the subchannel. A downlink subframe is composed of M×N
burst is constructed on good-quality subchannels. slots, where M is the number of subchannels and N is
Therefore, these unused slots can be further utilized by the number of slots within one subchannel.
the other bursts if the algorithm extra considers the A downlink burst can be represented as a rectangle
requested bandwidth. with a height-width pair placed on a starting slot; i.e., a
downlink burst B=[(y, x),(h, w)], where (y, x)and(h,
3. Problem statement w) represent the starting slot and the height-width pair,
This section first defines a number of used notations respectively. Let B be the downlink burst constructedi
and formally states the problem of the two-dimensional for C. In addition, let NOS and MCS denote the num-i i i
downlink burst construction. ber of occupied slots and the MCS adopted by B ,i
respectively. Th is the throughput achieved by connec-i
3.1. Notations tion C,anditsvalueismin(NOS ×MCS ,W ), wherei i i i
A two-phase bandwidth allocation is used, as described in NOS×MCS is the bandwidth that can be supported byi i
Section 2.1. Let C be the set of all downlink connec- B.Whenthe valueof NOS ×MCS exceeds theall i i i
tions, and let L be the number of all downlink connec- requested bandwidth W , connection C only requiresi i
tions, i.e., L=|C |. In addition, let C represent the ith W to transmit its data; therefore, the effective through-all i i
connection after flow scheduling. A and W denote the put is W. All used notations are listed in Table 2.i i iLai and Chen EURASIP Journal on Wireless Communications and Networking 2011, 2011:173 Page 6 of 18
http://jwcn.eurasipjournals.com/content/2011/1/173
Table 2 Used notations
Notation Definition
C The set of all downlink connectionsall
L The number of all downlink connections, i.e., L=|C |all
C The ith connection after the flow scheduling phasei
W The requested bandwidth for C, in terms of bytesi i
A The number of allocated slots for C in the flow scheduling phasei i
M The of subchannels in a downlink subframe
N The number of slots within one subchannel
R The MCS matrix for different connections on different subchannels, where R(i,j) specifies the MCS used by C on the jth subchanneli
B The constructed downlink burst for Ci i
NOS The number of occupied slots by Bi i
MCS The MCS adopted by Bi i
Th Throughput achieved by Ci i
3.2 Problem and Issues constructer constructs each burst on its corresponding
Problem statement: Given a downlink subframe of M×N inferior-quality subchannels and uses a low MCS; the
slots, the set of C (all C,W,and A), and the MCS bandwidth is inefficiently used. An example of optimalall i i i
matrix R, construct all B to maximize the overall block exploration is shown in Figure 3c, in which thei
throughput of C is low when B is constructed in anThi 1 1throughput .
0≤i≤L−1 inferior block (i.e., subchannels 1, 2, and 3), whereas the
Inefficient bandwidth usage must be eliminated to throughput is high when B is constructed in an optimal1
solve this problem. The following issues must be care- block (i.e., subchannels 5 and 6).
fully considered when designing a downlink burst con- 4. Best corner-oriented algorithm
struction algorithm. BCO not only complies with the downlink burst struc-
1. External fragmentation ture specified in IEEE 802.16 standards, but also consid-
A downlink burst with a rectangular shape may cause ers the issues discussed in Section 3.2. To avoid external
external fragmentation. External fragmentation refers to fragmentation, BCO maintains all free slots as a contin-
the division of available slots into small pieces that can- uous area by constructing each burst in the corner. To
not meet burst requirements. Figure 3a shows an exam- minimize internal fragmentation, BCO expands the
ple of a connection C with A = 12 slots. The burst B1 1 1 burst by one slot height in steps. At any step, if the
cannot be constructed because the free bandwidth was throughput of the constructed burst exceeds the
divided into pieces that were too small to accommodate requested bandwidth, the burst is large enough and is
B , although the total free bandwidth was sufficient for1 not further expanded, even when the number of occu-
A .1 pied slots is smaller than the number of allocated slots,
2. Internal fragmentation i.e., NOS <A. To explore an optimal block, BCO con-i i
The number of occupied slots, NOS,mustequalthei structs a virtual burst in various corners, and subse-
allocated number of slots, A , for any connection C .i i quently selects the best corner in which the burst
However, the throughput provided by A may exceed Wi i provides the largest throughput.
when the burst B isconstructedinanoptimalblocki
and thus, has an excellent MCSi.Thiscausesinternal 4.1. Definition of corners
fragmentation, which means that only some slots within BCO avoids external fragmentation by constructing a
a burst are used to transmit data, and the remaining are burst starting from the corner and limiting it by the
wasted. Figure 3b shows an example of internal frag- bounded width and height. The corner, bounded width,
mentationinthat C only uses ten slots to transmit1 and bounded height are formally defined as follows:
data, and the remaining two slots are wasted. given the available bandwidth area before constructing
3. Optimal block exploration the ith burst, the edge set, E, surrounding this area in ai
The SS experiences various levels of SNR on different counterclockwise order is defined by
subchannels resulting from variable noises on each sub- j j jJ J0 0 1 1E = {H ,V ,H ,V ,...,H,V ,...,H ,V },where Hi i i i i i i i i ichannel. The burst must be constructed in its corre-
j
and are the jth horizontal and vertical edges, respec-sponding optimal block, i.e., a block in which a number Vi
of continuous subchannels have excellent SNRs, and jtively. The corner, is defined as an available slot,CRithus,itcanuseasatisfactoryMCS.Thus,iftheburstLai and Chen EURASIP Journal on Wireless Communications and Networking 2011, 2011:173 Page 7 of 18
http://jwcn.eurasipjournals.com/content/2011/1/173
Figure 3 Examples of issues by constructing B with A =12 slots and W =270 bytes: (a) External fragmentation; (b) Internal1 1 1
fragmentation; (c) Optimal block exploration.Lai and Chen EURASIP Journal on Wireless Communications and Networking 2011, 2011:173 Page 8 of 18
http://jwcn.eurasipjournals.com/content/2011/1/173
j temporary burst, B , with a possible height-width pairtmpwhich is the intersection of H and left-hand verticali
and calculates the throughput that this burst can pro-jkedge V of . The corresponding bounded width andHi i vide. The steps are listed as follows:
j jk Initialization: h = 1// set initial heightheight are defined as H and V ,where H andii i
Step 1: Determine the width w for h by considering k j k jV denote the lengths of and V , respectively.Hi ii Ai, Wi, and the width H . i
Therefore, constructing a burst in the corner indicates jStep 2: B =[(y, x)(h, w)], where . In addi-(y,x)= CRtmpj ithat one of the vertices of the burst lies in ,andtheCRi tion, calculate the throughput of B . tmp
j bestwidth and height of this burst are restricted by H and Bi Step 3: Record the optimal burst with the opti-tmp
k mal height-width pair obtained thus far.V , respectively. Figure 4a demonstrates that three cor-i
Step 4: h = h+1;ners are located on slot(0,4), slot(3,0) and slot(7,0) at
kconstructing the ith burst, and their corresponding If h ≤V , go to step 1.i
(height, width) pairs are (3,4), (5,4), and (5,8), respec-
bestWhen the loop ends, B provides the optimaltmptively. Figure 4b presents an example of constructing
j1 throughput among all B virtually constructed in .burst B in the CR . CRtmpi i i
Lemma: Provided with a downlink subframe of M×N In Step 1, A and W were used to calculate the widthi i
slots and number of connections, L, the available band- when the height was given, to alleviate internal fragmen-
width area is continuous if each downlink burst is con- tation. BCO first calculated the width w where (w ×h)1, 1
structed in the corner. was equal to the allocated slots A. BCO calculated thei
width wProof: Mathematical induction is applied to prove the that the throughput provided by the burst2
(w ×h) to satisfy the requested bandwidth W.Subse-claim. For L = 1, which indicates that only one burst is 2 i
jrequired to be constructed, the free slots are maintained quently, BCO used the minimum of w , w,and H as1 2 i
as a continuous area after this burst is constructed in
the width. This is because if w is the minimum, con-2 j j kand limited by H and V .CR 0 00 structing a burst with a larger width w will exceed the1
requested bandwidth, resulting in internal fragmenta-Suppose that all free slots are maintained as a contin-

juous area when L = s.When L = s+1,the(s+ 1)th tion. In addition, H, as the minimum, indicates thatijburst is constructed in one of the corners (i.e., )CRs+1 the available bandwidth area located in this corner with
j k the height h is insufficient to accommodate a burst withand limited by the corresponding H and V .s+1 s+1
A slots. Therefore, the burst should be shrunk by usingij Constructing burst in maintains this burst adja-CRs+1 j
H as its width. The exact calculations of w and w1 2icent to other constructed bursts. In addition, limiting

are described in the following section.j
the burst by H prevents the horizontal division ofs+1 Furthermore, examining each possible height of a
the continuous free bandwidth area. Conversely, con- burst can avoid the phenomenon of throughput anom-
j k aly. The throughput anomaly indicates that a burst withstructing burst in and limiting it by V pre-CR s+1s+1 a large height may anomaly cause lower throughput
vent the vertical division of the continuous free than a burst with a small height when the burst with a
bandwidth area. Consequently, the free slots, after con- large height uses an inferior MCS. Figure 5 shows an
structing the (s+ 1)th bursts, are not divided and are, example in which the throughput provided by the burst
therefore, maintained as a continuous area. Thus, by the B(h = 3), referring to the burst with height 3, is consid-
mathematical induction, the available bandwidth area is erably lower than that provided by the burst B(h=2)
always a continuous area. because B(h = 3) used an inferior MCS, although B(h =
3) is larger than B(h = 2). In this case, a burst with a
4.2. Burst construction small height that provides large throughput should be
BCO minimizes the internal fragmentation by exploring constructed to avoid slot waste.
the optimal height-width pair of the burst constructed
j
in the selected . The optimal height-width pair indi-CR 4.3. Pseudo code of the BCO algorithmi
Figure 6 shows the pseudo code of BCO. To constructcates that the burst with thispairprovidestheoptimal
burst B for each connection C,BCOfirstusesthethroughput or the smallest area. To obtain the optimal i i
FindCorner function to obtain CRList, which containsheight-width pair, BCO repeatedly constructs aLai and Chen EURASIP Journal on Wireless Communications and Networking 2011, 2011:173 Page 9 of 18
http://jwcn.eurasipjournals.com/content/2011/1/173
j j kFigure 4 An example of constructing a burst in the corner. (a) An example for explaining , and ; (b) Construct the burst B inCR H V iii i1 with eight slots.CRiLai and Chen EURASIP Journal on Wireless Communications and Networking 2011, 2011:173 Page 10 of 18
http://jwcn.eurasipjournals.com/content/2011/1/173
Figure 5 An example of throughput anomaly. (a) Construct B(h = 2); (b) Construct B(h = 3).
j bestthe corners from the available bandwidth area. The subsequently compares with B to determineB ii
FindCorner function returns the CRList by examining
which is superior, i.e., which has higher throughput or
the horizontal and the vertical edges of the available
which occupies the fewer slots under the same obtained
bandwidth area. BCO subsequently explores the optimal j jbestthroughput. If is superior, BCO sets B to .B Bicorner by virtually constructing the burst in each corner i i
jto address the optimal block exploration (line 6-13), i.e., After virtually constructing all and obtaining the bestBi
BCO repeatedly invokes the ConstructBurst function to best bestburst B , BCO constructs B as B .ii ij jvirtually construct a burst in the corner .BCOB CRi i