Advanced
A Fast Converged Solution for Power Allocation of OFDMA System
A Fast Converged Solution for Power Allocation of OFDMA System
Journal of Electrical Engineering and Technology. 2014. Mar, 9(2): 721-725
Copyright © 2014, The Korean Institute of Electrical Engineers
  • Received : April 23, 2013
  • Accepted : August 16, 2013
  • Published : March 01, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Sungho Hwang
LIG Nex1 R&D Center, Korea. (sungho.hwang@lignex1.com)
Ho-Shin Cho
Corresponding Author: School of Electronics Engineering, Kyungpook National University, Korea. (hscho@ee.knu.ac.kr)

Abstract
In this paper, we propose a fast adaptive power allocation method for an orthogonal frequency division multiple access (OFDMA) system that employs an adaptive modulation and coding (AMC) scheme. The proposed scheme aims to reduce the calculation complexity of greedy adaptive power allocation (APA), which is known as the optimal algorithm for maximizing the utility argument of power. Unlike greedy APA, which starts power allocation from “0”, the proposed algorithm initially allocates a certain level of power determined by the water-filling scheme. We theoretically demonstrate that the proposed algorithm has almost the same capability of maximizing the utility argument as the greedy APA while reducing the number of operations by 2 M , where M is the number of AMC levels.
Keywords
1. Introduction
The orthogonal frequency division multiple access (OFDMA) system is a multi-carrier system. As such, the system capacity is obtained by the sum of the individual subcarrier capacities, which highly depends on the amount of power allocated to each subcarrier. Naturally, the subcarrier capacity increases when more power is allocated. To maximize the overall system capacity, optimally controlling and assigning the power for each individual carrier within the limits of the total transmission power would be ideal. Such power allocation has been a difficult and challenging issue for many researchers. Lagrangian methods have been used as potential solutions for capacity maximization. Water-filling, in which more power is allocated to stronger subcarriers, is known as the optimal solution for capacity maximization using Lagrangian methods [1] .
However, water-filling is inappropriate for obtaining the best performance when the adaptive modulation and coding (AMC) scheme is employed, in which the power allocation is performed with a number of discrete power levels. Regarding this issue, several adaptive power allocation (APA) schemes, which are sometimes called the “bit-loading” problem, have been investigated to increase the system utility in an OFDMA system with discrete AMC levels [3] - [5] . APA schemes have been developed with slightly different objectives and constraints. In [3] , the maximum utility rate has been obtained under a limited power constraint, whereas in [5] , the total transmission power is minimized to achieve a target data-rate of the system, which is the sum of the individual data-rates of all users. These schemes have an iterative procedure to successfully achieve each objective by using optimal [3] , heuristic [4] , or sub-optimal [5] algorithms. In particular, as an optimal algorithm, greedy APA (the modified Levin-Campello algorithm) maximizes the utility argument of power at each bit assignment. However, because zero power is initially allocated to all subcarriers, the processing time for iterative allocation of power to all subcarriers until the total allocated power reaches the limit is excessively long. In this paper, we propose a fast convergent power allocation method to significantly reduce the processing time for an OFDMA system that employs AMC.
The remainder of this paper is organized as follows. In section 2, we explain the OFDMA channel architecture and some system parameter. In section 3, we provide problem formulation and proposed algorithm. Section 4 describes the computer simulation model and its numerical results. Finally, conclusions are presented in Section 5.
2. System Model
We assume that AMC has M discrete channel states and the channels are already allocated to users by means of one of the existing sub-carrier allocation methods such as maximum C/I or proportional fairness (PF). In this paper, we address only the power allocation to each sub-carrier. The channel state of sub-carrier i is denoted by ρi , which the corresponding user experiences. It is defined as
PPT Slide
Lager Image
, where Ni and hi are the noise power density and frequency response, respectively, of sub-carrier i [2] . Thus, the channel state vector is defined by
PPT Slide
Lager Image
where S denotes the number of sub-carriers.
3. Problem Formulation and Proposed Algorithm
In this section, we formulate an optimization problem to maximize the system utility for the allocated sub-carriers and provide a power allocation algorithm to obtain an optimal solution.
Let Ui (·) be the utility function for sub-carrier i and Ptotal be the total transmission power. If sub-carrier i has an allocated power Pi , then its utility is Ui ( Pi ). Thus, we are interested in the following problem:
PPT Slide
Lager Image
PPT Slide
Lager Image
where Ui ( Pi )= ai log(1+ biPi ρi ) is a differentiable nondecreasing concave function, ai is the weight vector for the allocated user at sub-carrier i to generalize the problem, and bi is the factor for controlling the bit error rate of the allocated user at sub-carrier i . By changing the value of ai , Problem ( P ) can cover throughput maximization as well as PF allocation, and bi is determined by bi = −1.5/ln(5⋅BER i ) [8], where BER i is the bit error rate of the allocated user at sub-carrier i . Then, the optimal power allocation for problem ( P ) has the following solution [1] :
PPT Slide
Lager Image
where ( x ) + = max( x , 0) and λ is chosen such that the power constraint is satisfied:
PPT Slide
Lager Image
This equation represents the water-filling method of power allocation.
If the fixed sub-carrier allocation is based on the subcarrier channel state as in the greedy or PF algorithm for system throughput, the variation of each sub-carrier channel state is sufficiently low to satisfy the following constraint:
PPT Slide
Lager Image
Thus, the solution of problem ( P ), (4), is rewritten as:
PPT Slide
Lager Image
where E ( ai ) indicates the average of ai . The term (1/ S )Σ(1/ bkρk ) on the right-hand side indicates the average of the inverse channel states. Thus, we know that the performance improvements are marginal even though APA is employed in a continuous utility system under the following assumptions [2] :
A1) The variation of each sub-carrier channel state is sufficiently low.
A2) The variation of weighting factor ai decreases as long-term utility is maximized.
By using these properties (A1 and A2), we propose a new algorithm for a discrete data rate. The proposed algorithm allocates power to maximize the system utility. This purpose is the same as that of the underlying greedy APA [3] . However, our proposed scheme initializes Pi using the
PPT Slide
Lager Image
value, whereas greedy APA initializes Pi as “0.” Therefore, the proposed scheme can reduce the number of iterations for power allocation.
To compare the performance of the proposed algorithm with greedy APA, we explain some variables by using Fig. 1. In this figure,
PPT Slide
Lager Image
is the optimum power for the i -th subcarrier and Pi [ n ] is the minimum required power of level n for the i -th sub-carrier. The relationship between ( δ 1 ) and ( δ 2 ) as well as that between ( δ 2 ) and ( δ 3 ) in Fig. 1 are explained by Theorems 1 and 2 , respectively. The inequality of the slopes for ( δ 1 ) and ( δ 4 ) are shown in the Claim .
PPT Slide
Lager Image
Some variables for a new algorithm
The proposed algorithm is described in the following procedures:
1) For initialization,
PPT Slide
Lager Image
2) The remaining power, Ptotal −Σ iPi , is allocated using greedy APA.
Theorem 1: If Ui ( Pi ) is a differentiable non-decreasing concave function, for every i , the following property is satisfied:
PPT Slide
Lager Image
where Δ UiL = Ui ( Pi [ n * ])− Ui ( Pi [ n * −1]), Δ PiL = Pi [ n * ]− Pi [ n * −1], Δ Ui * = Ui ( Pi * )− Ui ( Pi [ n * ]), and Δ Pi * = Pi * Pi [ n * ].
Proof: Eq. (8) is achieved because Ui ( Pi ) is a nondecreasing and concave function and
PPT Slide
Lager Image
Theorem 2: If Ui ( Pi ) is a differentiable non-decreasing concave function, for every i and j , the following property is satisfied:
PPT Slide
Lager Image
Proof: If
PPT Slide
Lager Image
and
PPT Slide
Lager Image
are optimal, then any change in allocation will not increase the average utility. Let 0 < Δ P <
PPT Slide
Lager Image
, 0 < Δ P <
PPT Slide
Lager Image
and two arbitrary users exchange an amount of power equal to Δ P with each other. The new average utility will then be equal to or less than the optimal one. This inequality is given by
PPT Slide
Lager Image
which is equivalent to
PPT Slide
Lager Image
When Δ P → 0, we have
PPT Slide
Lager Image
and similarly, we obtain
PPT Slide
Lager Image
Using (12) and (13), we obtain
PPT Slide
Lager Image
PPT Slide
Lager Image
Claim: If Uj ( Pj ) is a non-decreasing concave function and variables αj and βi are given by
PPT Slide
Lager Image
and
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
Proof: Uj ( Pj ) is a non-decreasing concave function and Pj [ n * +1] >
PPT Slide
Lager Image
> Pj [ n * ]. Therefore, approximate equality and inequality are given by
PPT Slide
Lager Image
From Theorem 1 and (17), for every i and j , variables αj and βi satisfy the inequalities αj ≈ 1 and βi > 1, respectively
PPT Slide
Lager Image
Therefore, the following equation is satisfied by using Theorem 2 and Claim for every i and j :
PPT Slide
Lager Image
Thus, if Pi [ n * ] is allocated to every i -th sub-carrier before Pi [ n * +1] is allocated to any j -th sub-carrier, the performance of greedy APA is guaranteed.
For the iteration component, the greedy APA algorithm finds the sub-carrier with the maximum value of system utility per power. Thus, the computational complexity of a single iteration is O ( S ). We can ignore other components of the iteration and initialization processes because their computational complexity is much smaller than O ( S ). Therefore, if Ai is the number of power allocations of subcarrier i , the computational complexity of greedy APA is
PPT Slide
Lager Image
We can rewrite (19) as follows because max Ai is M :
PPT Slide
Lager Image
For the proposed scheme, the computational complexity of the initialization is O ( S ). Furthermore, the computational complexity of the proposed scheme is O ( S ) during a single iteration because the iteration component is the same as that of greedy APA. However, because of the initialization, the remaining power is given by Σ i
PPT Slide
Lager Image
, which is always less than Σ i
PPT Slide
Lager Image
. Therefore, the power allocation to each sub-carrier occurs only once or not at all. Finally, the maximum computational complexity of the proposed scheme is
PPT Slide
Lager Image
4. Numerical Results
This section, the performance of the proposed scheme is evaluated in terms of system utility and the number of operations by comparing it with the performances of the greedy APA [3] , adaptive transmission scheme (ATS) [4] , or water-filling [1] schemes under random varying radio channel conditions. As assumed in section III, the overall system capacity function is a non-decreasing concave function. Therefore, we use the overall system capacity as the system utility for a simple simulation. Although the discrete utility function is considered for the proposed scheme, greedy APA, and ATS, the continuous utility function is considered for the water-filling scheme.
The OFDMA system, proposed by the IEEE 802.16 WMANS standard, is considered herein with 240 subcarriers and 7 AMC levels. The probability density function of the signal-to-noise ratio (SNR) is assumed to be an exponentially distributed random variable with mean values uniformly distributed between [0, 16] dB [6] . We suppose that user traffic is sufficiently heavy to fully occupy a buffer.
Fig. 2 shows the average system utility for 100 symbol times. In Fig. 2 , the maximum C/I method with the dynamic sub-carrier allocation algorithm is used for all power allocation schemes. The system utility of each scheme increases as the number of users increases owing to multiuser diversity. The water-filling scheme, which is the solution to the optimization problem for the continuous system utility function, shows maximum system utility. The proposed scheme outperforms ATS and equal power allocation with the discrete system utility function and shows the same performance as greedy APA.
PPT Slide
Lager Image
Average system utility versus number of users
Fig. 3 shows the number of operations for power allocation, which is the total number of iterations for 100 symbols. The proposed scheme reduces the number of operations by almost thirteen times compared with greedy APA. This is because the average AMC level for each selected user in our simulation is about 6. Therefore, the proposed scheme needs less than one operation for each sub-carrier, however, greedy APA needs more than six operations for each sub-carrier. This result corresponds to (20) and (21).
PPT Slide
Lager Image
Number of operations for power allocation
5. Conclusion
In this paper, we proposed a fast APA algorithm to maximize the discrete system utility for an OFDMA system employing AMC. The proposed scheme showed the same performance as greedy APA, which is the optimum solution for a discrete system utility function. In addition, it reduced the number of operations by almost 2M times that of greedy APA. Therefore, the proposed scheme can be used in an actual system that employs AMC to maximize the system utility within a short processing time.
Acknowledgements
This work was supported in part by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (NRF-2012R1A1A4A01).This work was also supported in part by Defense- Acquisition Program Administration and Agency for Defense Development under the contract UD130007DD.
BIO
Sungho Hwang He received the B.S., M.S., and Ph. D. degrees in electrical engineering from Kyungpook National University in 2004, 2006, and 2010, respectively. In 2010, he joined LIG Nex1 R&D center as a Research Engineer. His current research interests include radio resource management, MAC protocol design, and RADAR resource management.
Ho-Shin Cho He received the B.S., M.S., and Ph. D. degrees in electrical engineering from the Korea Advanced Institute of Science and Technology in 1992, 1994, and 1999, respectively. From 1999 to 2000, he was a Senior Member of the Research Staff with the Electronics and Telecommunications Research Institute, where he was involved in developing a base station system for IMT-2000. From 2001 to 2002, he was a faculty member of the School of Electronics, Telecommunications, and Computer Engineering, Hankuk Aviation University. In 2003, he joined faculty of the School of Electronics Engineering, Kyungpook National University. In 2010, He was a visiting professor at University of Connecticut, USA. His current research interests include radio resource management, MAC protocol design, traffic modeling, self-organized network in wireless mobile communication systems and underwater acoustic sensor networks. Prof. Cho was awarded a rising researcher fellowship of KRF in 1998, and is a member of IEEE, IEICE, IEEK, ASK, and KICS.
References
Tse D. 2005 Fundamentals of Wireless Communication Cambridge University Press
Song G. , Li Y. (G.) 2005 “Cross-Layer Optimization for OFDM Wireless Networks-Part I: Theoretical Framework,” IEEE Trans. Commun. 4 (2) 614 - 624
Song G. , Li Y. (G.) 2005 “Cross-Layer Optimization for OFDM Wireless Networks-Part II: Algorithm Development,” IEEE Trans. Commun. 4 (2) 625 - 634
Kim K. 2005 “Efficient Adaptive Modulation and Power Allocation Algorithm for OFDMA Cellular Systems,” in Proc. 2005 Wireless Telecommunications Symposium 169 - 173
Chen Y. -F. , Chen J. -W. 2008 “A Fast Subcarrier, Bit, and Power Allocation Algorithm for Multiuser OFDM-based Systems,” IEEE Trans. Veh. Tech. 57 (2) 873 - 881    DOI : 10.1109/TVT.2007.907029
Ali S.H. , Lee Ki-Dong , Leung V.C.M. 2007 “Dynamic resource allocation in OFDMA wireless metropolitan area networks,” IEEE Wireless Communications 14 (1) 6 - 13