# OFDMA Downlink Burst Allocation Mechanism for IEEE 802.16e Networks

Juan I. Del-Castillo, Francisco M. Delicado, Jose M. Villalón

► To cite this version:

Juan I. Del-Castillo, Francisco M. Delicado, Jose M. Villalón. OFDMA Downlink Burst Allocation Mechanism for IEEE 802.16e Networks. 10th IFIP Networking Conference (NETWORKING), May 2011, Valencia, Spain. pp.250-262, 10.1007/978-3-642-20798-3_19. hal-01597973

HAL Id: hal-01597973

https://inria.hal.science/hal-01597973

Submitted on 29 Sep 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# OFDMA Downlink Burst Allocation Mechanism for IEEE 802.16e Networks

Juan I. del-Castillo*, Francisco M. Delicado, and Jose M. Villalón

Instituto de Investigación en Informática de Albacete (I³A)

Universidad de Castilla-La Mancha (UCLM), Spain

{juanignacio,franman,josemvillalon}@dsi.uclm.es

**Abstract.** Orthogonal Frequency Division Multiple Access (OFDMA) is one of the most promising, demanded and researched modulation and access methods for future mobile wireless networks. Emerging technologies, like Worldwide Interoperability for Microwave Access (WiMAX) or Long Term Evolution (LTE), are adopting OFDMA due to its high spectral efficiency, scalability for high amounts of users and mobility support. In OFDMA, before data is actually transmitted, it must be mapped into a time-frequency matrix through a resource allocation process. This step is critical for a correct network behaviour, and several factors must be taken into account like efficiency, Quality of Service (QoS) fulfillment or power consumption. In this paper, we propose a novel approach for the mapping process of IEEE 802.16e networks, and we compare its performance with several existing algorithms. The effectiveness of our proposal is evaluated in different scenarios by means of extensive simulation.

**Keywords:** WiMAX, IEEE 802.16, OFDMA, Resource allocation

## 1 Introduction

Forthcoming wireless communication technologies are expected to support a high amount of simultaneous users, high spectral efficiencies, low power consumption (especially in the case of portable devices) and high speed mobility. At the physical layer (PHY), Orthogonal Frequency Division Multiple Access (OFDMA) is beginning to be considered as the best solution for some 4th Generation (4G) wireless networks. Worldwide Interoperability for Microwave Access (WiMAX), defined by the IEEE 802.16 standard [1] and other multicarrier-based equipment like Long Term Evolution (LTE) systems [2] are examples of emerging OFDMA-based technologies. OFDMA enable the system to allocate spectral resources in an efficient and flexible way, due to the partial usage of time and frequency domains for several users. However, this gain in flexibility poses a substantial resource allocation challenge.

* This work was supported by the Spanish MEC and MICINN, as well as European Commission FEDER funds, under Grants CSD2006-00046 and TIN2009-14475-C04-03. It was partly supported by JCCM under Grants PII2I09-0045-9916 and PEII09-0037-2328.
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Scheduler and resource allocator are components of the MAC layer.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>**Fig. 2.** OFDMA Downlink subframe structure in IEEE 802.16.</figcaption></figure>

In the context of the IEEE 802.16 standard the specific downlink (DL) resource allocation mechanism is not standardized, so it is left open for design differentiation from individual manufacturers. The resource allocator is one of the components of the Media Access Control (MAC) common part sublayer of an IEEE 802.16 network, and along with the scheduler is responsible of fulfilling Quality of Service (QoS) requirements of user connections (Figure 1). High radio resource utilization also depends on the efficiency of the resource allocator.

In Figure 1, the scheduler and the resource allocator are represented into a dotted box, because their designs can be done independently, or in a joint manner. In the case of an independent design, the goal of the scheduler is to grant bandwidth to the different connections in order to guarantee their QoS requirements. On the other side, the resource allocator will be responsible of distributing time-frequency resources among users, through a process where packets from the scheduler component are mapped into an OFDMA matrix (Section 2). On the other hand, a joint design should also achieve both goals, but it could take advantage of channel state information to maximize throughput [3].

In this paper we consider Partial Usage of Sub-Channels (PUSC) subcarrier permutation mode of the IEEE 802.16 standard. With PUSC, subsets of subcarriers are distributed to form subchannels in order to achieve full channel diversity. In this mode, all subchannels will be equally adequate for all users, so the resource allocation problem is significantly simplified.

The rest of this paper is structured as follows: in Section 2 we define the DL resource allocation problem, highlighting some related factors that may affect the performance of IEEE 802.16 networks. Also we describe the most relevant proposals that exist in the literature in this context. We state our proposal in Section 3 and we carry out a performance evaluation in Section 4 by means of extensive simulation. Section 5 concludes this paper.

# 2 OFDMA Downlink Resource Allocation Problem

## 2.1 DL Subframe Structure and Resource Allocation Restrictions

Point-to-Multipoint (PMP) IEEE 802.16 networks are usually deployed in a cellular architecture [4], where each cell is composed of two types of stations: one Base
Station (BS) that acts as a central controller, and the Subscriber Stations (SSs). All the network traffic flows through the BS, which is in charge of allocating the time-frequency resources among the connections.

Considering an isolated implementation, the resource allocator receives traffic packets from the scheduler component and maps them into the DL subframe. The IEEE 802.16 standard [1] defines the structure for the DL subframe (Figure 2). The DL subframe is usually represented as shown: an OFDMA matrix with the x-axis being time (symbols) and y-axis being frequency (subchannels). After an initial preamble, which is needed to allow the synchronization of the SSs, the BS broadcasts the DL-MAP message (in column-wise order). The remaining space in the subframe is then allocated as rectangular data regions, through a certain resource allocation mechanism. These data regions are called bursts. The position and size of each burst is specified through an Information Element (IE) into the DL-MAP. This implies that, the greater the number of bursts, the higher the size of the DL-MAP will be. As the DL-MAP competes for the same space that could be used to transmit data, its size should be reduced as possible.

The shape bursts must be rectangular, and their sizes must be a multiple of the minimum resource allocation unit (slot). The size of a slot depends on the permutation mode, and in the case of PUSC it is 2x1: two symbols in time per one subchannel in frequency. These two restrictions lead to a problem known as overallocation, and it occurs when more space than the strictly needed is reserved in a certain burst. For example, suppose we have to reserve seven symbols for a certain user. In PUSC mode we could reserve a burst of size 4x2 (a total of eight symbols) leading to a waste of one overallocated symbol.

Traffic from several users may be mapped into the same burst with one condition: data in a certain burst is transmitted using the same Modulation and Coding Scheme (MCS). If the resource allocation mechanism is able to group traffic from different users into the same burst then the number of bursts will be reduced, and therefore the size of the DL-MAP will be reduced too.

## 2.2 Allocation Mechanism Design Factors

Resource allocation mechanisms have to be designed taking into account the goals that have to be achieved, and the factors that complicate the achievement of these goals. The goals of a resource allocator should be the following:

**High throughput.** High network throughput can be achieved by efficiently mapping the traffic into the OFDMA matrix. This efficiency is inversely proportional to the amount of frame space that is not used to transmit data. This wasted space includes control information (DL-MAP and MAC overhead) and unused space inherent to the allocation process (overallocation and unused slots).

As described in Section 2.1 a portion of the DL subframe is used to send the DL-MAP. The size of this message directly depends on the number of bursts. In order to minimize DL-MAP overhead, the number of bursts should be minimized. This can be achieved by grouping traffic from different users into the same burst,
assuming it will be transmitted using the same MCS. As specified in the IEEE 802.16 standard the DL-MAP may be transmitted multiple times (2, 4 or 6 times) in order to prevent its incorrect reception by the SSs due to channel errors, so in these cases the DL-MAP size minimization is even more critical.

Traffic packets are mapped into the frame as Protocol Data Units (PDUs). Each PDU includes a 48-bit MAC header, a payload, a 32-bit Cyclic Redundancy Check (CRC) and in some cases packing or fragmentation subheaders (8-bit and 16-bit respectively). This control overhead also affects performance and should be minimized. A resource allocation mechanism may divide a given allocation into several, at the cost of probably adding fragmentation overhead. Grouping traffic from the same connection into the same burst permits to take advantage of the packing mechanism established in the standard.

At last, regarding mapping efficiency, there are two factors that may impair throughput. As stated in Section 2.1, due to the mandatory rectangular shaping of bursts and because their size must be proportional to the slot size, some overallocation appear. On the other side, a bad resource allocator may leave certain slots completely unassigned to any burst, and therefore more space is wasted. Both overallocation and unused slots should be minimized.

**Quality of Service fulfillment.** On an isolated scheduler/resource allocator design, the latter should always respect the allocation order established by the first. The traffic prioritization of the scheduler is established to fulfill certain QoS requirements of the user connections. If an allocation mechanism does not respect this order QoS guarantees may be impaired. Requirements from some connections can behave incorrectly due to this problem, specially those involving real-time applications like VoIP. QoS requirements may include maximum delay, allowed jitter and bit loss rate. Even best effort applications may be impaired if fairness criteria is used by the scheduler. Ideally, a resource allocator should always preserve the order established by the scheduler. As we will see in Section 2.3, some allocation mechanisms [5] alter this order.

**Power consumption.** One important goal for any emerging wireless technology, including IEEE 802.16 networks, is the minimization of the power consumption of client stations. This factor is even more critical in the case of mobile devices, which have a limited energy budget. In the case of OFDMA, the global energy consumption of the served SSs may be reduced by minimizing the average duration of bursts within a given frame, in such a way that a SS needs to be awake for receiving data during a shorter time. Obviously burst shape will affect this factor: bursts taking few time symbols will reduce global awake times. As the DL-MAP is broadcasted to all SSs, minimizing its size will also reduce the awake period of every SS. Some algorithms [6] specifically deal with this goal, as we will see in Section 2.3.

**Algorithm complexity.** The resource allocation problem is similar to the “bin packing” problem [7], which is NP-complete. As frame duration in OFDMA
mode of the IEEE 802.16 standard is short (2-20ms), the resource allocation
algorithm may not be too complex, discarding optimal solvers and having to ad-
dress the problem heuristically. The input factor of the complexity of a resource
locator will be the number of allocations that need to be mapped into the
frame, which in turn depends on network load (number of connections). Thus, a
resource allocator should properly scale as the number of connections increase.

## 2.3 Related Work

OFDMA resource allocation in IEEE 802.16 networks has attracted much atten-
tion in recent years. Authors of [8] propose the *Raster* algorithm. Frame slots are
allocated from left to right and from top to bottom (in rows). The problem with
this approach is that, as DL-MAP grows from left to right, an initial column for
data must be established. This does not allow the DL-MAP to grow dynamically
if needed, so if the reserved space for the DL-MAP is used, no more data burst
could be allocated. Also, allocations may be splitted at the right edge of the
frame so PDU fragmentation will be increased.

Other proposals avoid the previous problem by assigning slots from right to
left or by keeping track of the total width of the mapped bursts. In [9], authors
propose the SDRA algorithm. Allocations are mapped bottom-up and from
right to left, allowing the DL-MAP to grow dynamically. During the mapping
process, a given allocation will not be assigned more slots than it needs, at the
cost of splitting it into several (at most three) bursts, introducing some PDU
fragmentation. However, the authors assume that all data directed to users with
the same MCS are combined into the same data region, but this is not directly
achievable without altering the scheduling order. Despite this assumption, the
allocations are mapped in order into the frame, but the performance of this
algorithm will highly depend on the size of the allocations. If there are a lot of
small allocations, the DL-MAP size will grow too much.

The goal of the algorithm proposed in [10] is to reduce the number of bursts
by grouping data for different users but with the same MCS. This is done by
allocating bursts of fixed height, called buckets. The width of the buckets grows
as needed when data from the same MCS is progressively introduced. The problem
with this mechanism is that it generates a high amount of overallocation, due to
the fact that whole columns are allocated regardless of the actual required space.
However, it only allocates one burst per MCS, so the DL-MAP size is minimal.

Authors of [5] propose the eOCSA mapping mechanism. It allocates bursts as
SDRA, bottom-up and right-left, seeking to minimize unused slots and energy
consumption (by minimizing burst width) and to allow the DL-MAP to grow dy-
namically. However, to optimize the mapping process the allocations are initially
sorted in decreasing order. This implies that the scheduler order is not preserved
so connections with QoS requirements may be severely impaired. Allocations are
not grouped by MCS, so DL-MAP size is expected not to be minimized.

A comparative of three of the above mentioned algorithms was done in [11].
In [6], authors seek to optimize the receiver awake cycle by reducing the average
duration and delay of the bursts within a given frame. Although this is an
<figure><img src="image_4.png" /><figcaption>Fig. 3. Flow chart of the first phase.</figcaption></figure>

important goal for a resource allocator as stated in Section 2.2, the algorithm
uses a full search approach, making it impractical for more than eight users.

3 Proposed Allocation Mechanism

In this section we describe a novel proposal to the resource allocation problem
described in Section 2. Our proposal is based on the following key concepts, in
order to achieve the goals stated in Section 2.2:

- Traffic from the same MCS should be grouped into the same burst whenever possible, thereby reducing DL-MAP size and PDU fragmentation.

- The mapping process should be efficient enough in order to avoid unused slots and overallocation as much as possible.

- The traffic order established by the scheduler should be preserved, to avoid QoS requisites impairment.

- Average duration of bursts should be minimized, in order to achieve a low global power consumption of the served SSs.

- The algorithm complexity must make its implementation feasible.

The proposed resource allocation mechanism is divided into two phases. In
order to allow a dynamic growth of the DL-MAP, the algorithm reserves *n*
columns, which will be available for the DL-MAP to grow in any moment. The
reserved columns are only used for data allocations when no space is available
(for the performance evaluation of Section 4 we set *n* = 1 reserved column).

We define the concept of *container* as a set of columns of the DL subframe.
In the first phase containers are created, one per MCS processed, and having
<figure><img src="image_5.png" /><figcaption>Fig. 4. Flow chart of the second phase.</figcaption></figure>

just one burst. The width of a container is the same as the burst it contains. When the first phase ends, the width of the containers gets fixed so it does not change in the whole second phase.

Figure 3 shows a flow chart of the process of the first phase. The width($W$) and height($H$) (re)computed in the first phase are given by:

$$W = \lceil A/H_{DL} \rceil \qquad (1)$$

$$H = \lceil A/W \rceil \qquad (2)$$

where $A$ is the area in slots of the packet being mapped, $H_{DL}$ is the height in slots of the DL subframe, and $W$ and $H$ is the computed burst width and height respectively. In the case of a packet of an already processed MCS, the packet is grouped in the existing burst, recomputing its width and height. The first phase ends when the sum of the widths of the containers plus the width of the DL-MAP takes the whole DL subframe (except for the $n$ reserved columns).

At the end of the first phase fixed-width containers have been established (one for each MCS), and we still have unused space below the initial bursts.
<figure><img src="image_6.png" /><figcaption>**Fig. 5.** Example of the mapping process with our proposal.</figcaption></figure>

During the second phase those unused areas are mapped (Figure 4). In the case of a packet of an existing MCS we proceed as in the first phase. If an existing burst of that MCS can hold the packet (increasing its height if needed and if there is enough area in the container), then the packet is grouped into that burst. If there is not a burst of that MCS or if the existing burst can not grow vertically to hold the packet, then a new burst is created. All newly created bursts will have the width of their containers. To select a free area for the new burst, we first use a best-fit criteria. If the new burst does not completely fit in that area then the biggest area is selected, whether it fits completely or not (the packet may be fragmented in this case). When all free areas are used, we proceed by freeing one reserved column. The process finishes when all space is used.

Figure 5 shows an example of the mapping process of our proposal. Figures 5(a) and 5(b) depict the first phase of the algorithm. It can be seen that packet D uses the same MCS as packet C, so they are grouped into the same burst, recomputing width and height of that burst. First phase finishes when there is no more free width. Figures 5(c–e2) depict the second phase, where bursts can be updated and/or created. Figure 5(e1) takes the case of mapping packet H1 (case 1 in the figure), where the reserved column is used for data. Figure 5(e2) shows the case of mapping packets H2, I and J (case 2 in the figure), where the reserved column is used for the DL-MAP instead.

# 4 Performance Evaluation

In this section we compare the performance of our algorithm with three previously proposed allocation mechanisms, by means of extensive simulation. We have selected SDRA [9], Ohseki et al. [10] and eOCSA [5] for the evaluation.
This selection is based on the results and conclusions obtained in [11]. In the case of our proposal we reserve one column ($n = 1$), as stated in Section 3.

For our simulations we consider a single-cell PMP IEEE 802.16 network. The physical bandwidth is 10 MHz which corresponds to a 1024-FFT. We only consider the DL direction and we use the PUSC permutation mode. Frame duration is 5 ms and duplexing technique is Time Division Duplexing (TDD), with a 50% of the frame duration intended for DL.

The wireless channel is modelled using a Rayleigh fading channel based on the ITU Pedestrian A multi-path model [12]. Due to this, SSs change their MCS scheme through the simulation in order to use the most efficient scheme possible.

Two different scenarios are simulated: one where the DL-MAP is transmitted once (x1) and other where the DL-MAP is transmitted four times (x4) as allowed by the standard. In order to check the behaviour of the algorithms under different network loads, we set one BS and a variable number of SSs (from 30 to 80). DL traffic is generated as a mix of traffic models from different types of users: 65% of individual subscribers, 20% of small business and 15% of medium business. Traffic is formed of voice and best-effort classes, modeled as specified in [13]. We set a strict priority scheduler, which gives precedence to packets according to their service class. Voice packets with an end-to-end delay greater than 10 ms are dropped by the scheduler. Each scheduled packet is forwarded to the mapper as an allocation to insert into the OFDMA matrix.

For each scenario we simulate 3 minutes of operation, measuring statistics after the first 10 seconds. We run 30 different executions for each scenario, in order to be able to get the average value and a 95% confidence interval for each metric. Confidence intervals are however not drawn since they are negligible with respect to the estimated average.

## 4.1 Metrics

The following metrics are defined in order to evaluate and compare the performance of our proposal and the other resource allocators. These metrics are based on the factors defined in Section 2.2.

- *DL subframe waste (%)*: this metric is the sum of unused slots, overallocation, DL-MAP overhead and MAC overhead. Each one of these is obtained by dividing the number of symbols it takes (i.e. overallocated symbols) by the total number of symbols of the DL subframe.

- *DL throughput efficiency (%)*: it is defined as the total traffic sent by the BS to the SSs divided by the total DL traffic that arrives at the BS.

- *Skipped traffic (%)*: as a resource allocator may change the packet order initially established by the scheduler, some traffic may be skipped in a given frame. This metric is computed as:

$$S = 100 * \frac{B_{skipped}}{B_{total}} \qquad (3)$$

where $B_{skipped}$ is the sum in bits of the skipped packets according to the scheduler order and $B_{total}$ is the sum in bits of all the processed packets.
<figure><img src="image_7.png" /><figcaption>Fig. 6. DL subframe waste and DL throughput efficiency (DL-MAP x1).</figcaption></figure>

- Bit-loss rate (%): defined as the total traffic dropped by the scheduler (dead-line) divided by the total DL traffic that arrives at the BS.

- Active time (%): this metric indicates the average active time of all SSs. Each frame it is computed as:

$$A_t = 100 * \frac{\sum_{i=1}^{n} (W_0 + \sum_{j=1}^{m_i} W_{i,j})}{n \cdot W} \quad (4)$$

where n is the number of SSs, $m_i$ is the number of bursts that contain data intended for the $i_{th}$ SSs, $W_0$ is the width in slots of the DL-MAP region, $W_{i,j}$ is the width in slots of the $j_{th}$ burst of the $i_{th}$ SS and W is the total width in slots of the DL subframe.

## 4.2 Simulation Results

We start by evaluating DL subframe waste and throughput. Figures 6 and 7 depict waste (vertical bars) and throughput (lines) for the one and four DL-MAP repetition scenarios, respectively. In both cases it can be seen that total subframe waste with our proposal (O.P.) is the lowest of the four algorithms.

As network load increases, our proposal is able to maintain unused slots and overallocation at very low values. In the first scenario (one repetition), the eOCSA algorithm generates more overallocation and leaves more slots unused,
<figure><img src="image_8.png" /><figcaption>Fig. 7. DL subframe waste and DL throughput efficiency (DL-MAP x4).</figcaption></figure>

because its allocation performance highly depends on the size distribution of the arriving packets. Our proposal is able to group packets from the same MCS more efficiently. MAC overhead is greater with O.P., but the overall waste is still lower because we only fragment packets in some specific cases of the process.

In the case of the second scenario (four repetitions), the eOCSA algorithm behaves significantly worse because the effect of DL-MAP overhead is greater, and eOCSA generates big DL-MAPs due to the fact that it does not group packets from the same MCS. Ohseki and O.P. group packets, generating smaller DL-MAPs, but Ohseki has a problem with overallocation because it reserves whole columns for individual MCSs, so much of that space is wasted. SDRA generates too large DL-MAPs, because it does not group packets and even a given allocation may be divided into up to three bursts. DL throughput efficiency is inversely proportional to DL waste, so our proposal is performing better than the other three as seen in Figures 6 and 7.

Figures 8 and 9 shows skipped traffic and bit-loss rate (BLR) of voice packets for both scenarios. It can be seen that the eOCSA algorithm is not preserving the scheduler order, because it firstly sorts allocations by its size. Although this may improve the performance of the mapping process, it also has a harmful effect over voice BLR. In the case of four DL-MAP repetitions the space available for data transmission is lower, so even though the relative disorder is lower its effect over BLR is greater. On the other hand, Ohseki skips packets from time to time, but it does not significantly affect BLR. Our proposal and the SDRA algorithm
<figure><img src="image_9.png" /><figcaption>Fig. 8. Skipped traffic and BLR (x1).</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Fig. 9. Skipped traffic and BLR (x4).</figcaption></figure>

<table><caption>Table 1. Active time (%).</caption><thead><tr><th rowspan="2">DL MAP</th><th rowspan="2">Alg.</th><th colspan="6">Number of Subscriber Stations</th></tr><tr><th>30</th><th>40</th><th>50</th><th>60</th><th>70</th><th>80</th></tr></thead><tbody><tr><td rowspan="4">x1</td><td>SDRA</td><td>22 ± 2 · 10<sup>-4</sup></td><td>22 ± 8 · 10<sup>-5</sup></td><td>22 ± 3 · 10<sup>-5</sup></td><td>22 ± 9 · 10<sup>-5</sup></td><td>21 ± 7 · 10<sup>-5</sup></td><td>21 ± 5 · 10<sup>-5</sup></td></tr><tr><td>Ohseki</td><td>22 ± 2 · 10<sup>-3</sup></td><td>24 ± 3 · 10<sup>-3</sup></td><td>24 ± 2 · 10<sup>-3</sup></td><td>24 ± 9 · 10<sup>-4</sup></td><td>23 ± 1 · 10<sup>-3</sup></td><td>23 ± 5 · 10<sup>-4</sup></td></tr><tr><td>eOCSA</td><td>21 ± 6 · 10<sup>-5</sup></td><td>21 ± 2 · 10<sup>-5</sup></td><td>21 ± 1 · 10<sup>-5</sup></td><td>21 ± 4 · 10<sup>-5</sup></td><td>21 ± 4 · 10<sup>-5</sup></td><td>20 ± 2 · 10<sup>-5</sup></td></tr><tr><td>O.P.</td><td>22 ± 2 · 10<sup>-3</sup></td><td>24 ± 3 · 10<sup>-3</sup></td><td>23 ± 1 · 10<sup>-3</sup></td><td>24 ± 1 · 10<sup>-3</sup></td><td>23 ± 4 · 10<sup>-4</sup></td><td>23 ± 2 · 10<sup>-4</sup></td></tr><tr><td rowspan="4">x4</td><td>SDRA</td><td>30 ± 3 · 10<sup>-3</sup></td><td>37 ± 4 · 10<sup>-3</sup></td><td>38 ± 7 · 10<sup>-4</sup></td><td>37 ± 8 · 10<sup>-4</sup></td><td>37 ± 9 · 10<sup>-4</sup></td><td>37 ± 1 · 10<sup>-3</sup></td></tr><tr><td>Ohseki</td><td>22 ± 3 · 10<sup>-3</sup></td><td>24 ± 3 · 10<sup>-3</sup></td><td>24 ± 2 · 10<sup>-3</sup></td><td>24 ± 9 · 10<sup>-4</sup></td><td>23 ± 1 · 10<sup>-3</sup></td><td>23 ± 5 · 10<sup>-4</sup></td></tr><tr><td>eOCSA</td><td>25 ± 8 · 10<sup>-4</sup></td><td>29 ± 3 · 10<sup>-4</sup></td><td>30 ± 6 · 10<sup>-4</sup></td><td>31 ± 2 · 10<sup>-3</sup></td><td>31 ± 2 · 10<sup>-3</sup></td><td>31 ± 3 · 10<sup>-3</sup></td></tr><tr><td>O.P.</td><td>22 ± 3 · 10<sup>-3</sup></td><td>24 ± 4 · 10<sup>-3</sup></td><td>25 ± 5 · 10<sup>-3</sup></td><td>30 ± 2 · 10<sup>-3</sup></td><td>30 ± 1 · 10<sup>-3</sup></td><td>30 ± 8 · 10<sup>-4</sup></td></tr></tbody></table>

do not disorder traffic in any case because the traffic is processed in strict order, so no voice packets are dropped and BLR is zero.

Average SS active time (%) is shown in Table 1. In the case of the one repetition scenario, there is not much difference between the four algorithms, and active time is relatively low. When we transmit the DL-MAP four times in a frame more variation is observed. In this case Ohseki is consuming less energy than any other algorithm, because it generates very small DL-MAPs and packet are arranged in columns. It can be seen that our algorithm is behaving better than eOCSA and SDRA, also because DL-MAP size is relatively low and we try to minimize burst width through the allocation process.

At last, we compare algorithmic complexities of the four algorithms. SDRA and Ohseki have a linear complexity, $O(N)$, where N is the number of allocations that need to be mapped in a certain frame. They are simple and fast algorithms, and they scale very well. On the other hand, eOCSA has a complexity of $O(N^2)$ due to the fact that it iterates over the allocation list seeking for the best one to fit the next hole. In the case of our proposal, we achieve a worst-case complexity of $O(N \log N)$, due to the need of maintaining an ordered list of holes. However it is perfectly feasible for its real implementation.
## 5 Conclusions

In this paper, we have proposed a new resource allocation algorithm for OFDMA DL of IEEE 802.16 systems. It is clear that the process of resource allocation is not straightforward, and that there are several factors that may affect it. A correct and clever balance of these factors is needed to achieve the desired goals. Usually, tuning up one factor implies worsening others. Through computer simulation, it has been confirmed that our proposal is able to perform better than the other three evaluated algorithms, preserving QoS order, keeping a reduced power consumption and a low algorithmic complexity.

## References

1. IEEE 802.16-2009: IEEE Standard for Local and Metropolitan Area Networks- Part 16: Air Interface for Broadband Wireless Access Systems (2009)

2. Seba, V., Modlic, B.: Multiple Access Techniques for Future Generation Mobile Networks. In: International Symposium Electronics in Marine, pp. 339-344 (2005)

3. Gutiérrez, I., Bader, F., Aquilué, R., Pijoan, J.L.: Contiguous Frequency-Time Resource Allocation and Scheduling for Wireless OFDMA Systems with QoS Support. In: Eurasip Journal on Wireless Communications and Networking. (2009)

4. Andrews, J., Ghosh, A., Muhamed, R.: Fundamentals of WiMAX. Understanding Broadband Wireless Networking. Prentice Hall (2007)

5. So-In, C., Jain, R., Al-Tamimi, A.: eOCSA: An Algorithm for Burst Mapping with Strict QoS Requirements in IEEE 802.16e Mobile WiMAX Networks. In: IEEE Wireless Communication and Networking Conference (2008)

6. Desset, C., de Lima, E.B., Lenoir, G.: WiMAX Downlink OFDMA Burst Placement for Optimized Receiver Duty-Cycling. In: International Conference on Communications, pp. 5149-5154 (2007)

7. Johnson, D.S.: Fast Algorithms for Bin Packing. In: Journal of Computer and System Sciences, pp. 272-314 (1974)

8. Ben-Shimol, Y., Kitroser, I., Dinitz, Y.: Two-Dimensional Mapping for Wireless OFDMA Systems. In: IEEE Transactions on Broadcasting, vol. 52, no. 3, pp. 388-396 (2006)

9. Bacioccola, A., Cicconetti C., Lenzini, L., Mingozzi, E., Erta, A.: A Downlink Data Region Allocation Algorithm for IEEE 802.16e OFDMA. In: International Conference on Information, Communication and Signal Processing, pp. 1-5 (2007)

10. Ohseki, T., Morita, M., Inoue, T.: Burst Construction and Packet Mapping Scheme for OFDMA Downlinks in IEEE 802.16 Systems. In: GLOBECOM 2007, pp. 4307-4311 (2007)

11. Del-Castillo, J.I., Delicado, F.M., Delicado, J., Villalon, J.M.: OFDMA Resource Allocation in IEEE 802.16 networks: A Performance Comparative. In: Wireless and Mobile Networking Conference (WMNC), pp. 1-6 (2010)

12. WiMAX Forum: WiMAX System Methodology v2.1, 230 pp. (2008)

13. Baugh, C.R., Huang, J.: Traffic Model for 802.16 TG3 MAC/PHY Simulations. IEEE 802.16 BWA Working Group (2001)