SpringerOpen Newsletter

Receive periodic news and updates relating to SpringerOpen.

This article is part of the series Recent advances in optimization techniques in wireless communication networks.

Open Access Research

Equal rate resource allocation for multiuser OFDM

Chunhui Liu1*, Anke Schmeink2 and Rudolf Mathar1

Author Affiliations

1 , RWTH Aachen University, 52062 Aachen, Germany

2 UMIC Research Centre, RWTH Aachen University, 52062 Aachen, Germany

For all author emails, please log on.

EURASIP Journal on Wireless Communications and Networking 2012, 2012:344  doi:10.1186/1687-1499-2012-344

The electronic version of this article is the complete one and can be found online at: http://jwcn.eurasipjournals.com/content/2012/1/344


Received:14 February 2012
Accepted:17 August 2012
Published:16 November 2012

© 2012 Liu et al.; 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.

Abstract

The performance of multicarrier systems can be enhanced by the water filling strategy, in which different rates and powers are allocated to subcarriers. However, the induced large signalling overhead leads to less transmission efficiency. To suppress this effect this article proposes an alternative strategy by dynamically assigning the same rate to each subcarrier per user. First, we quantify the asymptotic limits of its instantaneous per-symbol performance loss compared to water filling. Then, we apply this strategy to weighted sum rate maximization subject to minimum required rates and limited transmission power. Due to the simplicity of the proposed strategy, a low-complexity method is given, which can be used for other resource allocation problems in multi-carrier systems with small modifications. Simulations demonstrate that the instantaneous per-symbol performance loss of our method compared to the water filling strategy becomes insignificant if the number of users is large. The proposed method has even better performance for fast time-varying channels with respect to the signalling overhead. Moreover, given the subcarrier assignment from the proposed method, water filling can be performed and the output is close to the primal optimum.

Keywords:
OFDM; Resource allocation; Rate maximization

Introduction

Orthogonal frequency division multiplexing (OFDM) divides the whole transmission band into multiple subcarriers to combat the inter-symbol interference. This allows for allocating different rates and powers to subcarriers according to channel characteristics so that the system performance is enhanced. There are two basic resource allocation problems [1]. One is the margin-adaptive (MA) problem, where the transmission power is minimized subject to a fixed rate. The other aims at maximizing the data rate subject to limited transmission power, so called the rate-adaptive (RA) problem. Both can be solved by the well-known water filling approach. As a result different rates and powers are allocated to subcarriers.

The resource allocation is executed at the transmitter, while channel state information is usually measured at receivers. Receivers must be notified about the employed allocation and coding scheme, thus, inducing a significant signalling overhead is required [2]. The faster channels change, the more frequently the resource allocation scheme alters. The temporal channel variation highly depends on the velocity of receivers and reflectors between transmitters and receivers. For multiuser resource allocation, even though the channel rapidly changes for only one user, the resource allocation scheme has to be updated frequently. Therefore, water filling may degrade in fast time-varying environments.

In [3,4], the same power is assigned to subcarriers achieving certain data rates. Since each data rate corresponds to a certain mapping and coding scheme, dynamic mapping and coding schemes cannot be identified from the allocated power. Thus, the signalling overhead still remains large. To reduce the signalling overhead, [5] suggests to cluster subcarriers into blocks. If the number of subcarriers in one block is large, the performance impairs severely. In contrast, the overhead is not significantly reduced. The same power and rate are statically allocated to a fixed number of subcarriers, which have greater channel gain-to-noise ratios (CNRs) [6]. This fixed number is known to the receiver, which implies that the subcarrier assignment does not adapt to the channel conditions. The same signal-to-noise ratios are obtained over all subcarriers in [7]. However, the resulting performance loss may be very large, when the channel frequency selectivity is severe.

Different from previous studies, this article proposes to dynamically allocate to the same rate to all subcarriers assigned to a user, while the rates to subcarriers of different users may differ. In doing so, the signalling overhead is drastically reduced, such that the overall performance is improved. It follows that the resource allocation scheme can be more efficiently updated after changing the subcarrier assignment than for water filling. Consequently, an easily implementable and low-cost heuristic can be designed. Compared to the conventional multiuser resource allocation [8], minimum rate constraints [9] are included to become closer to practical requirements. This results in additional challenges for the heuristic design, since the rate constraints fulfilled at equality and inequality have to be separated. The proposed method has linear complexity in the number of users and subcarriers and only small performance loss compared to the dual optimum [10,11], which has the closest performance to exhaustive search. Moreover, a constant rate is allocated to subcarriers in wireless local area networks (WLAN) [12]. In our proposed strategy, the same rate but different powers are allocated.

Thus, we only change the scale of the symbol mapper according to the resource allocation scheme. In this sense, only minor modifications are needed and the proposed strategy can be applied with simple modifications.

The remainder of this article is organized as follows. In Section ‘Preliminaries’, the considered multiuser resource allocation problem is formulated including signalling overhead, when water filling and the proposed strategies are applied. Water filling achieves the best instantaneous per-symbol performance, when the signalling overhead is not considered. Theoretical asymptotic limits are given for the instantaneous per-symbol performance loss of the proposed strategy applied to single-user resource allocation in Section ‘Single-user resource allocation’. The equal-rate resource allocation is specified for a fixed subcarrier assignment in Section ‘Multiuser resource allocation given subcarrier assignment’. Subsequently, a heuristic is designed to determine the multiuser subcarrier assignment in Section ‘Heuristic subcarrier assignment’. Simulation results are presented in Section ‘Simulation results’.

Preliminaries

We consider a multiuser OFDM system with one transmitter, K users and N subcarriers. Perfect channel knowledge is assumed at the transmitter, where resource allocation is executed. A resource allocation scheme is effective for L OFDM symbols, while L is determined by temporal channel variation and the time duration of one OFDM symbol. In a fast time-varying environment L cannot be large. For example, one frame in the worldwide interoperability for microwave access (WiMAX) [13] is composed of 48 OFDM symbols. The resource allocation scheme is updated for every L OFDM symbols via the signalling overhead. There are 2Mdata rates that may be allocated to each subcarrier. It means that M bits are necessary to identify one discrete rate. According to [2], if the water filling strategy is used, NM bits are required for expressing one resource allocation scheme and sent at first. Thereafter, data symbols follow. Note that N⌈ log2(K)⌉ bits are always needed to notify each receiver of which subcarriers are assigned to it. This amount is constant in this study.

We aim at maximizing the weighted sum rate subject to limited transmission power and individual minimum rate required by users. When the water filling strategy is adopted, it is stated as

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M1','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M1">View MathML</a>

(1)

The non-negative power and rate allocated to subcarrier n for user k is denoted by pk,n and rk,n, respectively. They are related by the equality constraint, where gk,nis the CNR of subcarrier n of user k. Once subcarrier n is assigned to a user, M bits must be sent at first for every L OFDM symbols. The average rate for signalling over each subcarrier is M/L. The achieved rate for user k is weighted by positive wk, which is given by the system for the purpose of fairness control among users. Each user requires a minimum rate Rk, expressed by the second constraint. The transmission power is limited to P, illustrated by the third constraint. The set of users is referred to as <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M2','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M2">View MathML</a>. The set <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M3','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M3">View MathML</a> contains the subcarriers assigned to user k. We denote the cardinality of <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M4','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M4">View MathML</a> by sk. One subcarrier is assigned to at most one user at any specific time to avoid interference to each other, illustrated by the last constraint in (1). The variables of problem (1) are rk,n, pk,n and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M5','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M5">View MathML</a>

The dual optimum of (1) can be obtained by the dual method [10]. The Karush-Kuhn-Tucker conditions [14] are applied to (1), where K + 1 dual variables appear. Then, the ellipsoid method is used to let these dual variables iteratively converge. The number of iterations is related to <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M6','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M6">View MathML</a>[8,15]. In each iteration (K + 1)Nequations must be calculated. Hence, the complexity for determining the dual optimum of (1) is <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M7','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M7">View MathML</a>. The concrete solution is available in [11]. This can be viewed as the extension from single-user water filling to multiuser water filling, where different rates and powers are allocated to subcarriers to meet transmission constraints.

To notify receivers of the employed resource allocation scheme with a smaller signalling overhead, the same rate rk may be allocated to the subcarriers assigned to user k=1,…,K. Then, only KM bits are sufficient to distinguish data rates for all subcarriers. The signalling overhead is reduced by (NK)M bits. The resource allocation problem (1) can be rewritten as

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M8','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M8">View MathML</a>

(2)

In (1), M bits must be sent for each subcarrier to identify the employed rate in the current L OFDM symbols. Thus, on average M/L bits/OFDM symbols must be additionally achieved over each subcarrier. In (2), only M bits of signaling overhead is necessary for each user. Hence, on average M/Lbits/OFDM symbols must be additionally achieved for each user. Thus, each minimum required rate is increased by M/L for signalling. In the following, we first extract two classical single-user resource allocation problems to quantify the instantaneous per-symbol performance loss of the proposed strategy. Thereafter, a heuristic method is designed to solve (2). The variables of problem (1) are rk,pk,n and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M9','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M9">View MathML</a>

Equal rate resource allocation

In this section, single-user and multiuser equal rate resource allocations are investigated. A heuristic solution is given for the considered problem (2).

Single-user resource allocation

We first focus on resource allocation for a single user k. The signalling overhead is not considered here to investigate the instantaneous per-symbol performance loss of the proposed strategy. If the subcarrier assignment <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M10','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M10">View MathML</a> for user k is fixed, the power and rate allocation can be easily determined. Let Pk denotes the transmission power for user k. A single-user MA resource allocation problem [1] with the proposed strategy applied is written as

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M11','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M11">View MathML</a>

(3)

where the transmission power is minimized while satisfying the required rate. Obviously, the allocated rate and power are rk=Rk/sk and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M12','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M12">View MathML</a>, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M13','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M13">View MathML</a>, respectively. The optimum objective is

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M14','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M14">View MathML</a>

(4)

where Hk is the harmonic average of the CNRs <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M15','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M15">View MathML</a>, derived as <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M16','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M16">View MathML</a>. Compared to the water filling solution <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M17','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M17">View MathML</a> from [1], the instantaneous per-symbol performance loss is

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M18','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M18">View MathML</a>

(5)

where Gk is the geometric average of the CNRs <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M19','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M19">View MathML</a> as <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M20','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M20">View MathML</a>. Its asymptotic limit is

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M21','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M21">View MathML</a>

(6)

The equation above implies that the performance loss is limited, when either the required rate or the number of users is large. This may be satisfied in large scale systems, where many users are served and each of them demands a large rate.

Similarly, the new strategy is applied to a single-user RA resource allocation problem [1] given <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M22','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M22">View MathML</a>

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M23','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M23">View MathML</a>

(7)

where the data rate is maximized subject to the transmission power limit. The power and rate allocation can be easily derived by taking <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M24','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M24">View MathML</a> to the power constraint, expressed as

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M25','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M25">View MathML</a>

(8)

where the associated water level is μk=Pk/sk + 1/Hk. Compared to the water filling solution sk log2(μkGk) from [1], the instantaneous per-symbol performance loss is

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M26','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M26">View MathML</a>

(9)

The performance loss (9) tends to

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M27','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M27">View MathML</a>

(10)

Similar to the previous asymptotic limit of performance loss for the single-user MA problem, the performance loss for the single-user RA problem is limited when a small number of subcarriers is assigned to user k or the transmission power is large.

Without considering the signalling overhead, Figure 1 shows the instantaneous per-symbol performance loss by the proposed strategy compared to water filling for the single-user MA problem (3). It approaches the limit (6) as the required rate increases. For the single-user RA problem (7), the performance loss by the proposed strategy is shown in Figure 2. It asymptotically reduces to zero (10). The maximum loss appears, when these two strategies employ different numbers of subcarriers. The asymptotic limit is 27.89 % in Figure 1, while the loss goes up to 7.4 % in Figure 2, since the CSI variation is very large with respect to the example subcarriers. Note that we want to give an example for these theoretical asymptotic limits, which can simply be repeated by readers. The performance loss with random CNRs is smaller than the special case. This can be explicitly seen from the simulation result for the multiuser case.

thumbnailFigure 1. Single-user equal rate resource allocation 1. Instantaneous per-symbol performance loss of single-user MA equal rate resource allocation compared to water filling versus the increasing required rate with N = 8 subcarriers gk,n = 9 − n, n = 1,…,8.

thumbnailFigure 2. RA single-user equal rate resource allocation 2. Instantaneous per-symbol performance loss of single-user RA equal rate resource allocation compared to water filling versus increasing power limit with N=8 subcarriers gk,n = 9 − n, n = 1,…,8.

In water filling, different CNRs over subcarriers result in different allocated rates and powers. Compared to that, the single-user equal-rate resource allocation can be viewed as water filling over subcarriers having the equal CNR Hk, shown by (4) and (8). Thus, both strategies have the same water level given the same subcarrier assignment. When subcarrier assignment <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M28','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M28">View MathML</a> for user k changes, only the harmonic average Hk needs to be updated to obtain the new sum power Pkwith (4) or the new sum rate skrkwith (8). Then, we can interpret problem (2) as the multiuser water filling over subcarriers with equal CNRs for different users.

Multiuser resource allocation given subcarrier assignment

The above interpretation can be used to solve (2) while relaxing the rate constraints, which will be met by an iterative processing later. Let <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M29','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M29">View MathML</a> denotes the set including RA users and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M30','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M30">View MathML</a> refer to the set including MA users. Given the subcarrier assignment for the RA users <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M31','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M31">View MathML</a>, the power allocated to each RA user has to be decided by additionally considering the weights. This new problem can be stated as

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M32','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M32">View MathML</a>

(11)

where the power constraint must be met at equality due to the complementary slackness condition [14]. Then, the dual problem is to maximize <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M33','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M33">View MathML</a> subject to ν≥0. Let the derivative <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M34','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M34">View MathML</a> and the above problem can be solved as

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M35','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M35">View MathML</a>

(12)

where the sharing factor νis

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M36','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M36">View MathML</a>

(13)

and νwk is the water level for user k. However, from (12), it can be seen that the power allocated to user k may be zero or not adequate to achieve the minimum required rate <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M37','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M37">View MathML</a>. If this occurs on user k, we call him an MA user [1]. Then, user k has to be excluded from <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M38','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M38">View MathML</a> and included in <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M39','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M39">View MathML</a>. The transmission power for user <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M40','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M40">View MathML</a> is derived by solving problem (3) with the fixed rate <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M41','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M41">View MathML</a> reached. The power for the remaining users in <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M42','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M42">View MathML</a> is <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M43','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M43">View MathML</a>. Then, the power allocation (12) is recalculated for user <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M44','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M44">View MathML</a>. This iterative procedure finishes until all minimum rate constraints are satisfied. This solution can be interpreted as water filling over different users <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M45','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M45">View MathML</a>. Hence, its complexity is <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M46','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M46">View MathML</a>.

Heuristic subcarrier assignment

Given the subcarrier assignment, the solution of (1) can be viewed as two-dimensional water filling over users and subcarriers, while the solution of (2) reduces to a one-dimensional water filling only over users by allocating an equal rate to subcarriers of each user. In [16], for the single user k, the sum power (4) can be depicted as an inverse unimodal function of sk with subcarriers in <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M47','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M47">View MathML</a> sorted in a descending order of the CNRs <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M48','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M48">View MathML</a>, while different bit-error rates are achieved over subcarriers. We found in examples that this property remains for the proposed strategy. Then, the upgraded bisection method by inheriting the golden section method [17] can be used with complexity <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M49','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M49">View MathML</a>. In the following, a method to determine the multiuser subcarrier assignment is designed. It is composed of initialization and subcarrier adjustment.

Initialization for subcarrier assignment

We use the idea from [18], where the initialization has two steps. First, the cardinality, i.e., the number of subcarriers assigned to each user, is evaluated according to the average CNR over subcarriers and the rate and power constraints. After that, specific subcarriers are assigned to users according to these evaluated numbers. To fit the idea to our problem, we propose the cardinality evaluation, summarized in Algorithm 1. In each iteration, only one cardinality increases by one. If the sum power for reaching the minimum required rates is beyond the power limit, we add one to the cardinality that induces the largest power decrement. Otherwise, we add one to the cardinality, which results in the largest weighted sum rate to (11) without the minimum rate constraints considered.

Algorithm 1. Cardinality evaluation

1: <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M50','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M50">View MathML</a>

2: sk←1, k=1,…,K

3: fori=1,…,NKdo

4: if<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M51','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M51">View MathML</a>then

5: <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M52','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M52">View MathML</a>

6: else

7: <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M53','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M53">View MathML</a><a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M54','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M54">View MathML</a>

8: end if

9: <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M55','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M55">View MathML</a>

10: end for

Let <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M56','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M56">View MathML</a> contains all subcarriers 1,…,Nat first. In [18], sksubcarriers are assigned to user k at one time and users get subcarriers in a row. The problem is that the last user has limited options, since better subcarriers have been taken by the previous users. Different from that, an additional iterative procedure is introduced to distribute subcarriers to users following the evaluated cardinalities from Algorithm 2. In each iteration, each user k obtains only <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M57','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M57">View MathML</a> subcarriers. This number is smaller than the evaluated sk and is determined by the geometric mean of {s1,…,sK}. The process finishes when set <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M58','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M58">View MathML</a> is empty. In doing so, each user has the chance to have subcarriers with relatively high CNRs. The complexity of our initialization is <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M59','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M59">View MathML</a>.

Algorithm 2. Initialization of subcarrier assignments

1: <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M60','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M60">View MathML</a>

2: repeat

3: for each k=1,…,Kdo

4: <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M61','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M61">View MathML</a>

5: <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M62','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M62">View MathML</a>

6: <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M63','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M63">View MathML</a>

7: end for

8: until<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M64','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M64">View MathML</a>

Subcarrier adjustment

As before, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M65','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M65">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M66','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M66">View MathML</a> denote the sets of RA and MA users, respectively. After the initialization, subcarrier n may be assigned to an MA or RA user or to no user. There are four cases of reassigning a subcarrier. First, removing a subcarrier from an MA user induces that the transmission power for this MA user increases and thus less sum rate is achieved for RA users. Second, after removing a subcarrier from an RA user, the achieved sum rate increases. Third, by adding a subcarrier to an MA user, the transmission power for this MA user decreases and hence more sum rate is achieved for RA users. Fourth, adding a subcarrier to an RA user results in an increased sum rate. Reassigning one subcarrier from one to another user is a combination of two of the four cases above.

In the inner loop of Algorithm 3, each subcarrier is successively adjusted among users to improve the objective of problem (2). This procedure repeats I times iteratively by the outer loop. Hence, we name our method iterative successive subcarrier adjustment (ISSA). Before each inner loop, the users are divided into sets <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M67','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M67">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M68','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M68">View MathML</a> according to the present subcarrier assignment by water filling over users as explained before. These two sets remain within one inner loop. As discussed before, if the subcarrier assignment varies, the sum power (4) for each user or the weighted sum rate in problem (11) can be recalculated by updating the associated harmonic average. Each subcarrier may be reassigned to K−1 users. The number of iterations I can be preliminarily determined. Alternatively, it can be adaptive to the channel condition and the transmission constraints by the iteration control similar to [19]. For example, the outputs of two successive iterations can be compared. If the difference is small, we return the output. For a given I, Algorithm 3 has complexity of <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M69','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M69">View MathML</a>. Then, the proposed method has the overall complexity of <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M70','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M70">View MathML</a>. Complexities are compared in Table 1, where the dual optimum to (1) has complexity <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M71','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M71">View MathML</a>.

Table 1. Complexity comparison

Simulation results

In this section, simulations are performed to compare the proposed strategy to the dual optimum of (1). The simulation system consists of 128 subcarriers. Each minimum rate and each weight are uniformly distributed within [10,20] bits per OFDM symbol and [1, 10], respectively. The frequency selective channel is modeled as consisting of 16 independently Rayleigh distributed paths with an exponential decaying profile. The expected CNR of each subcarrier is normalized to −5 dB. The transmission power is limited to 20 dBW. Here, we show the performance loss of the proposed method in percent compared to the dual optimum.

For the considered multiuser resource allocation (1) and (2), Figure 3 plots the instantaneous per-symbol performance loss of the proposed heuristic solution of problem (2) compared to the dual optimum of problem (1), as <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M76">View MathML</a>. As the number of iterations I increases, the gap between two neighboring iterations becomes smaller. It converges at I=5 on average in our simulation. The performance loss first increases and then decreases in the number of users for I=1. It only decreases in the number of users for I>1. As the number of users increases, user diversity grows and a higher rate can be achieved over each subcarrier. On the other hand, it is more likely that subcarriers are assigned to inappropriate users that may impact the achieved sum rate. In each iteration subcarriers are sequentially adjusted. In the case of I=1, once such an error occurs, it cannot be corrected. It is not invertible. Hence, the curve with I=1 first goes down due to the increase of user diversity and then goes up because of those non-invertible errors. In the cases of I>1, subcarriers can be readjusted several times and some errors become invertible. As I increases, more and more errors are corrected and performance is improved.

thumbnailFigure 3. Multiuser equal rate resource allocation 1. Instantaneous per-symbol performance loss of the equal rate resource allocation compared to the dual optimum versus the number of users.

Algorithm 3. Iterative successive subcarrier adjustment

1: fori ∈ {1,…,I}

2: <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M77','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M77">View MathML</a> water filling over users

3: for each n∈{1,…,N}do

4: if<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M78','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M78">View MathML</a>then

5: adjust subcarrier n among MA users in <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M79','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M79">View MathML</a> to minimize <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M80','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M80">View MathML</a>

6: else

7: adjust subcarrier n among RA users in <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M81','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M81">View MathML</a> and MA users in <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M82','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M82">View MathML</a> to maximize the objective

8: end if

9: end for

10: end for

In [2], NM bits represent one resource water filling allocation scheme, where M bits are used to distinguish different available rates. There are LR <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M83','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M83">View MathML</a> NM data bits within L OFDM symbols. For the proposed strategy, KM bits are enough and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M84','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M84">View MathML</a> data bits are contained in L OFDM symbols. If the water filling has a better performance, the following inequality must hold as

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M85','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M85">View MathML</a>

(14)

which is equivalent to

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M86','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M86">View MathML</a>

(15)

If the resource allocation is updated per frame, we define <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M87','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M87">View MathML</a>, which is the minimum frame length for the case that water filling has a better performance than the proposed strategy. For comparison, we use for all kwk=1 and M=6. The above inequality does not hold below the curve in Figure 4, which is much greater than 48, i.e., the frame length in WiMAX [13]. This implies that our strategy performs better for smaller L, i.e., fast time-varying channels. In practice, its performance is expected to be again better, since the overhead has to be transmitted at a rate much lower than the data rate to assure every user receives it correctly.

thumbnailFigure 4. Multiuser equal rate resource allocation 2. Minimum number of OFDM symbols for the case that water filling has better performance versus the number of users.

Finally, the output subcarrier assignment of the proposed heuristic method can be used to provide a solution to (1). Water filling, i.e., different powers and rates allocated to subcarriers, can be performed over the output subcarrier assignment. Then, a heuristic solution is obtained for (1). It is very close to the dual optimum of multiuser water filling (1), as shown in Figure 5. The performance loss becomes insignificant as K increases. The curves are the performance loss in percent compared to water filling, expressed as the ratio

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M88','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M88">View MathML</a>

(16)

thumbnailFigure 5. Multiuser equal rate resource allocation 3. Instantaneous per-symbol performance loss of water filling over the subcarrier assignment given by the proposed method compared to the dual optimum versus the number of users.

It is equal to

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M89','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/344/mathml/M89">View MathML</a>

(17)

At first, as the number of users increases, the user diversity becomes bigger and the sum rate by water filling grows significantly. Hence, the ratio above gets bigger and bigger. Then, as the number of users continues increasing, even though the user diversity still increases, the minimum require rates are more. To satisfy those minimum required rates, the sum rate becomes smaller. Thus, the ratio decreases in this range. When a subcarrier is assigned to an inappropriate user, the performance becomes worse. This probability becomes higher as the number of users increases.

It can be seen from Figures 3 and 5 that the gap between two neighboring numbers of iterations becomes smaller as I increases. However, it may occur that some occasional cases do not converge as I increases. In such a case we can set a maximum value for I.

Conclusion

This article investigated resource allocation for multiuser OFDM. It proposed an equal rate allocation to the subcarriers assigned to one user. This resulted in a small signalling overhead and a low-complexity method of multiuser resource allocation. Asymptotic limits were given for the instantaneous per-symbol performance loss of the proposed strategy in the case of single-user resource allocation. With this strategy, a heuristic method was designed to maximize the weighted sum rate subject to the minimum rate constraint and the power limit. Simulations demonstrated that the proposed strategy has a better performance than water filling when channels vary rapidly. This method gave a near optimal subcarrier assignment to resource allocation problems with water filling applied. This implies that our method can be used for other resource allocation problems in multi-carrier systems with small modifications.

Competing interests

The authors declare that they have no competing interests.

References

  1. Y Li, GL Stueber, Orthogonal Frequency Division Multiplexing for Wireless Communications (Springer, New York, 2005)

  2. J Gross, I Paoluzzi, H Karl, A Wolisz, Throughput study for a dynamic OFDM-FDMA system with inband signaling. in Proc, ed. by . IEEE VTC Spring, Volume 3 (Milan, Italy, 2004)

  3. Y Zhang, C Leung, Subchannel Power-Loading Schemes in Multiuser OFDM Systems. IEEE Trans. Veh. Technol 58, 5341–5347 (2009)

  4. W Yu, JM Cioffi, Constant-power waterfilling: performance bound and low-complexity implementation. IEEE Trans. Commun 54, 23–27 (2006)

  5. K Liu, F Yin, W Wang, Y Liu, An efficient greedy loading algorithm for adaptive modulation in OFDM systems. in Proc, ed. by . IEEE PIMRC (Berlin, Germany)) (pp), . 2005 OpenURL

  6. D Dardari, Ordered subcarrier selection algorithm for OFDM-based high-speed WLANs. IEEE Trans. Wirel. Commun 3, 1452–1458 (2004). Publisher Full Text OpenURL

  7. CS Park, KB Lee, Transmit power allocation for BER performance improvement in multicarrier systems. IEEE Trans. Commun 52, 1658–1663 (2004)

  8. K Seong, M Mohseni, JM Cioffi, Optimal resource allocation for OFDMA downlink systems. in Proc, ed. by . IEEE ISIT ((Seattle, Washington, 2006)

  9. W Xu, C Zhao, P Zhou, Y Yang, Efficient adaptive resource allocation for multiuser OFDM systems with minimum rate constraints (Glasgow, Scotland, 2007)

  10. W Yu, R Lui, Dual methods for nonconvex spectrum optimization of multicarrier systems. IEEE Trans. Commun 54, 1310–1322 (2006)

  11. G Wunder, T Michel, Optimal resource allocation for parallel Gaussian broadcast channels: minimum rate constraints and sum power minimization. IEEE Trans. Inf. Theory 53, 4817–4822 (2007)

  12. B O’Hara, A Petrick, in IEEE 802, ed. by . 11 Handbook (IEEE Press, 2005)

  13. JG Andrews, A Ghosh, R Muhamed, Fundamentals of WiMAX (Prentice Hall, 2007)

  14. S Boyd, L Vandenberghe, Convex Optimization (Cambridge University Press, Cambridge, 2004)

  15. S Boyd, C Barratt, Ellipsoid Method (Lecture notes {http://www, 2008), . stanford.edu/class/ee364b/lectures/ webcite} OpenURL

  16. C Liu, A Schmeink, R Mathar, Constant-rate power allocation under constraint on average BER in adaptive OFDM Systems. Proc. IEEE ICC (2010)

  17. J Kiefer, Sequential minimax search for a maximum. Proceedings of the American Mathematical Society (1953)

  18. D Kivanc, G Li, H Liu, Computationally efficient bandwidth allocation and power control for OFDMA. IEEE Trans. Wirel. Commun. 2, 1150–1158 (2003). Publisher Full Text OpenURL

  19. RY Shao, S Lin, MPC Fossorier, Two simple stopping criteria for turbo decoding. IEEE Trans. Commun 47, 1117–1120 (1999). Publisher Full Text OpenURL