Int J Wireless Inf Networks (2009) 16:44–50 DOI 10.1007/s10776-009-0088-y
Distributed Resource Allocation Based on Game Theory in Multi-cell OFDMA Systems Qiu Jing Æ Zhou Zheng
Published online: 5 March 2009 Springer Science+Business Media, LLC 2009
Abstract A game theoretic solution for distributed uplink resource allocation in multi-cell OFDMA systems is presented in this paper. Convergence rule and steady state characterization are analyzed with potential game. Simulation results show that the proposed non-cooperative potential game algorithm for dynamic subcarrier and power allocation can converge to Nash Equilibrium (NE) quickly and achieve higher energy efficiency compared with pure iterative water-filling algorithm. Keywords Multi-cell OFDMA Distributed resource allocation Game theory
1 Introduction In OFDMA systems, system performance can be greatly improved by performing efficient dynamic resource allocation including subcarrier assignment, power control and adaptive modulation and coding for different users [1–4]. However, in multi-cell OFDMA systems, the co-channel users’ interaction leads to variable interference level which is assumed to be fixed or ignored in single-cell scenarios. Hence the resource allocation problem becomes more complicated. On the other hand, the mobile users in different cells do not have the knowledge of other users’ conditions and cannot cooperate with each other, they are Q. Jing (&) College of Telecommunication, Chongqing University, Chongqing 400044, China e-mail:
[email protected] Q. Jing Z. Zheng Wireless Network Lab, Beijing University of Posts and Telecommunications, Beijing 100876, China
123
more likely to act selfishly to maximize their own performance in a distributed way. Such facts motivate us to adopt the game theory, which is a mathematical tool to providing a formal modeling approach for analyzing interactive decision process [5, 6].Game theory allows us to investigate the existence, uniqueness and convergence to a steady state operating point when network nodes perform independent distributed adaptations. In [7], the authors presented a non-cooperative game approach to minimize the overall transmit power under each user’s power limitation and minimal rate constraint. [8] defined a power unit based utility function and proposed a non-cooperative power game with pricing to give a Pareto improvement over the NE. Although the strategic game models proposed in a considerable amount of researches have shown the existence of NE, these models cannot provide provable uniqueness of NE and insight into the convergence criteria each player must follow to reach an NE. In this paper, we focuses on developing a new framework for distributed resource allocation in multi-cell OFDMA systems, which differs from the above literatures in that a new class of games, called potential game proposed by Monderer and Shapley in [9] are proposed to analyze and model the distributed behavior among users. The potential games are introduced because they can guarantee the existence of at least one NE which can be reached according to best response dynamic or better response dynamic, thus providing theoretic framework for decision rules design. In [10] and [11], potential games were successfully applied to some interference avoidance and scalar power control problems where each user has only one variable (i.e. transmit power or frequency) to optimize. However power allocation in OFDMA systems is
Int J Wireless Inf Networks (2009) 16:44–50
45
so called vector power control problem where each user has a set of power to optimize across parallel subcarriers. Hence the results of [10, 11] cannot be used any more. This paper is organized as follows. Section 2 introduces the system model and formulates the optimization problem. In Sect. 3, a game theoretic framework to subcarrier assignment and power control is proposed where we develop a distributed power allocation algorithm based on exact potential game. Simulation results are given and discussed in Sect. 4. Section 5 draws the conclusion.
2 System Model Consider the OFDMA system consisting of K co-channel cells and N users, where L subcarriers are reused. Each cell consists of some mobile users and their assigned base station (BS). Users assigned with the same frequency interference with each other. We assume the different links among cells are synchronized. For the uplink case, the ith user’s Signal Interference and Noise Ratio (SINR) on the lth subcarrier at time n can be expressed as: ci ðl; nÞ ¼
hii ðl; nÞpi ðl; nÞ N P
max Ui ðCi Þ pi
s:t:
L P
pi ðlÞ ¼ pi pi;max
ð3Þ
l¼1
Each user adjusts its transmit power on each subcarrier to maximize its utility depending on the transmit power of the other co-channel users in the system. The choice of power for user i impacts not only its own performance, but also those of others. In this paper, we use system energy efficiency defined as the ratio of the system capacity over the total power consumption as the measure of system performance. This metric corresponds to the amount of achievable capacity per unit energy. P ri g ¼ Pi ð4Þ p i i 3 Game Theoretic Formulation 3.1 Game Theoretic Model
ð1Þ
hji ðl; nÞpj ðl; nÞ þ r2
j¼1;j6¼1
where pj(l, n) and hji ðl; nÞ is the transmit power and channel gain from the jth user to the ith BS on the lth subcarrier, respectively. r2 is the thermal noise power. The ith user’s transmit data rate per Hz on the lth subcarrier is ci ðl; nÞ ¼ log2 ð1 þ bci ðl; nÞÞ; where b is a constant related to a target Bit Error Rate (BER) by b ¼ 1:5=lnð5BERÞ: With a subcarrier assignment, the data rate of user i is given by X X Ci ðnÞ ¼ ci ðl; nÞ ¼ log2 ½1 þ bci ðl; nÞ ð2Þ l2Di ðnÞ
assignment and power allocation can be formulated as a distributed power control problem as
l2Di ðnÞ
where Di(n) denotes the set of subcarrier indices assigned to user i at time n. Each user adjusts its subcarrier assignment and power allocation in an effort to maximize its own performance. Here we use utility as the measure of users’ performance which quantifies the ‘‘satisfaction’’ or ‘‘payoff’’ that a user obtains from using the channel. In almost all wireless applications, reliable data transmission rate is the most important factor to determine the satisfaction of users. Therefore, the utility function should be a non-decreasing function of C. In essence, the subcarrier assignment can be covered by power allocation problem: when the allocated power on a subcarrier is zero, the subcarrier is not used and vice versa. The channel is assumed to be constant over the time required for resource allocation. Therefore, the time index n can be omitted for convenience and the subcarrier
In the context of game theory, (3) can be modeled as a noncooperative power control game: G ¼ N; fPi gi2N ; fUi gi2N g; where N is the set of users, Pi ¼ fpi : pi ¼ PL l¼1 pi ðlÞ pi;max g is the set of power allocation actions and Ui is the utility function of user i. A game theoretic model for the distributed power allocation is suggested here. We relate the utility function of a particular user i to its achievable data rate. Each user maximizes its own data rate at the cost of high power consumption, which causes interference to other users and brings down their data rate. In order to keep a user from selfishly transmitting the highest power available, the system should impose a pricing function. For the sake of simplicity, our pricing function is proportional to user’s transmit power. As a result, the net utility for user i is given by U i ¼ C i ai pi
ð5Þ
where ai is a non-negative pricing factor whose units are bps/Hz/W so that the two terms in (5) have the same unit. With the net utility as the objective function, (3) can be formulated as: ! L L P P bhii ðlÞpi ðlÞ max log2 1 þ PN pi ðlÞ a i pi l¼1 h ðlÞpj ðlÞþr2 l¼1 j¼1;j6¼i ji ð6Þ L P s:t pi ðlÞ ¼ pi pi;max ; pi ðlÞ 0 l¼1
The situation as so called vector problem where each user has a set of power to optimize across parallel
123
46
Int J Wireless Inf Networks (2009) 16:44–50
subcarriers, is more complicated than power control in CDMA/FDMA/TDMA systems where each user has only one variable (i.e. transmit power) to optimize. The steady state of non-cooperative strategic game is known as NE. In the NE, no player can improve the value of their utility by unilaterally deviating. The action tuples (a unique choice of actions by each player) corresponding to the NE are then predicted as the most likely steady state outcome of the game. In this paper, we introduce potential game to model the above distributed power allocation. Definition 1 A strategic game G ¼ N; fAi gi2N ; fUi gi2N g is called an exact potential game (EPG) if there exist a function Pot(), such that for all i [ N and ai, bi [ Ai Ui ðai ; ai Þ Ui ðbi ; ai Þ ¼ Potðai ; ai Þ Potðbi ; ai Þ
functions set fUi1 ; Ui2 ; . . .; UiL g and action set corresponding to NE fa1i ; a2i ; . . .aLi g: Form a new game G, with player set N, action space A, and objective functions of user i given by Ui ¼ a1 Ui1 þ a2 Ui2 þ þ aL UiL ; then G is an EPG with an EPF given by P = a1P1 ? a2P2 ??aLPL. From Theorem 3, it can be easily proved that NE of EPG G is the set of [E1, E2,…, EN]T, with the L-length vector Ei ¼ ½a1i ; a2i ; . . .; aLi representing the NE vector of player i. According to Definition 1, it is straightforward to see that power control on a single subcarrier l is an EPG, with player set N, action space Pi, and utility function ! bhii ðlÞpi ðlÞ l Ui ¼ log2 1 þ PN ð8Þ ai pi ðlÞ 2 j¼1;j6¼i hji ðlÞpj ðlÞ þ r Potential function
ð7Þ
where, (bi, a-i) refers to the action profile in which the action of user i is changed from ai to bi while the actions of all the other players in the game remain the same. Functions Pot() are called exact potential function (EPF).
l
2
P ðpðlÞÞ ¼ log2 r þ where h0ji ðlÞ ¼
N X
! h0ji ðlÞpj ðlÞ
N X
j¼1
aj pj ðlÞ
ð9Þ
j¼1
bhii ðlÞj ¼ i According to Theorem 1, it hji ðlÞj 6¼ i
For EPG, conditions for existence and uniqueness of NE can be obtained simply, as shown in the following. Theorem 1 [9] Let G ¼ N; fAi gi2N ; fUi gi2N be a potential game, with a potential function Pot. Then G has at least one pure strategy NE which can be found by solving for maximizers of the potential functions.
has a unique NE. According to Theorem 3, the vector power control game in (6) is an EPG with the same player set N, action space P, and its utility function is ! L L X X bhii ðlÞpi ðlÞ Ui ¼ log2 1 þ PN pi ðlÞ ai 2 l¼1 l¼1 j¼1;j6¼i hji ðlÞpj ðlÞ þ r
If, in addition, Ai is a compact, convex set, and Pot is a continuously differentiable function on the interior of Ai and strictly concave on Ai, then NE of G is unique. Suppose that the same strategic game could be played repeatedly. At each stage of the game, players choose actions that improve their utility functions in a round-robin fashion. The criteria for a particular choice of action gives rise to the best and better response dynamics defined below. Best Response Dynamic At each stage, a player i is permitted to deviate from ai [ Ai to some action
ð10Þ Its potential function is PðpÞ ¼
L X
2
log2 r þ
l¼1
N X
! h0ji ðlÞpj ðlÞ
j¼1
N X i¼1
ai
L X
pi ðlÞ
l¼1
ð11Þ Moreover, the vector power control potential game has a unique NE. And the distributed power control algorithm can be designed according to the convergence criteria given in Theorem 2.
bi 2 Ai iff bi ¼ arg max Ui ðai ; ai Þ ai
Better Response Dynamic At each stage, a player i is permitted to deviate from ai [ Ai to some action bi 2 Ai iff bi ¼ fbi 2 Ai : Ui ðbi ; ai Þ [ Ui ðai ; ai Þg Theorem 2 [9] All potential games following a best response dynamic converge to a NE. Potential games with finite action spaces have been established to follow a better response dynamic to converge to a NE. Theorem 3 [9] Consider the set of EPG{EPG1, EPG2,…EPGL}, with player set N and action space A, and potential functions {P1, P2,…PL}, and user i’s utility
123
3.2 Distributed Power Control Scheme Based on the above potential game model and its properties, we propose an distributed power control scheme based on best response dynamic and Gauss-Seidel algorithm [12] in which all users update their power strategies sequentially. 3.2.1 Initialization Set t = 0. We assume that all the users are powered on simultaneously. Each user starts with an initial power allocation and calculates its utility based on (5).
Int J Wireless Inf Networks (2009) 16:44–50
47
3.2.2 Update Power Allocation Let t = t ? 1. For all users i [ N, given power allocation t1 t1 vector Pt1 ¼ fpt1 1 ; p2 ; . . .; pN g; compute t1 pti ðlÞ ¼ arg max Ui pt1 ; pt2 ; . . .pti1 ; pi ; pt1 iþ1 ; . . .pN pi 2Pi
L X
s:t: ; pti ðlÞ 0; pti ðlÞ pi;max
pt1 i ðmÞ l
m¼1;m6¼l
¼ 1; 2; . . .L; i ¼ 1; 2; . . .; N Repeat step 2 until the utility of every user converges.
than a certain threshold value ai;thr ; user i uses the maximum power available to it. It is non-trivial to give an analytical expression for ai;thr because of the complex relationship between di(l) and pi,max. The region of ai;thr \ai \ maxðdi ðlÞÞ= ln 2 corresponds to a transmit l power pi which is between 0 and pi,max. The situation is desirable for higher energy efficiency, as long as the reduced power consumption allows QoS requirements to be met. In order to avoid unnecessarily transmitting at the highest power which potentially harms network energy efficiency, user i can be assigned a larger ai.
3.3 Implication of Pricing Factor
4 Simulation Result
To quantify the implication of pricing factor ai on power control, we approach the optimization problem in (6) with Lagrange multiplier theory. The Lagrangian function in a standard minimization formulation can be written as
To show the performance of the proposed algorithm, we set up a seven-cell simulation scenario. Around a central cell, we consider six adjacent cells with wrap-around technology [14] to remove edge effect. The BS is located at the centre of each cell and users are generated as a uniform distribution with the corresponding cell. The propagation model takes into consideration of path loss and shadowing. The five-path Rayleigh model is used to simulate the frequency selective fading, channel, which has an exponential power profile. The simulation parameters used are listed in Table 1. Suppose all the users in the system have the same pricing factor. We plot in Fig. 1 the evolution of transmit power, data rate and utility with iterations for all the users in central cell, with pricing factor 5 and maximum transmit power 1 W. All users start with maximum transmit power which is allocated equally to all subcarriers. In such a scenario, the proposed Non-cooperative Potential Game Power Allocation (NPGPA) algorithm converges quickly to the steady state after 2–3 iterations. In Fig. 2, we report the evolution of utility with iterations under another different initial power allocation. Observe that different initial conditions lead to the same system steady status despite
Lðpi ; lÞ ¼
L X
½ai pi ðlÞ log2 ð1 þ di ðlÞpi ðlÞÞ ! L L X X pi ðlÞ pi;max ll pi ðlÞ þ l0 ð l¼1
l¼1
ð12Þ
l¼1
where l ¼ ðl0 ; l1 ; . . .; lL Þ is the Lagrange multiplier are constants due to the vector, di ðlÞ ¼ PN bhii ðlÞ 2 j¼1;j6¼i
hji ðlÞpj ðlÞþr
assumption that all the other users’ power allocation are given. According to KKT conditions [13], let pi(l) be a local maximum of (6), then there exists a unique l, such that oL opi ðlÞ
di ðlÞ ¼ ai ð1þdi ðlÞp þ l 0 ll ¼ 0 i ðlÞÞ ln 2
ð13Þ
ll 0; l ¼ 0; 1; . . .L The KKT condition in (13) can be converted to 1 1 ¼ pi ðlÞ þ ln 2 a i þ l 0 ll di ðlÞ
ð14Þ
Given ai [ maxðdi ðlÞÞ= ln 2 and from l0 C 0, we know l 1 1 1 1 ln 2 pi ðlÞ þ \ ln 2 ð15Þ ai þ l0 ai di ðlÞ di ðlÞ Comparing (14) and (15), we see that (14) is true only if ll [ 0, which indicates the constraint pi ðlÞ 0 is active for any l = 1, 2,…L, then the transmit power of user i is zero and it is shut down. The above analysis shows that if pricing factor ai is large enough, user i does not transmit power. In the another extreme situation when ai = 0, which means no pricing is imposed in the utility function, the power allocation result is obviously the well-known water-filling solution with maximum transmit power. Generally, when ai is smaller
Table 1 Simulation parameters Parameters
Value
Cell radius
500 m
System bandwidth
6.4 MHz
Number of subcarriers
32
Users of each cell
10
Doppler frequency
30 Hz
Thermal noise power
-120 dB
BER
10-3
Path loss coefficient
4
Shadowing standard deviation
8 dB
123
48
Int J Wireless Inf Networks (2009) 16:44–50
Fig. 1 Convergence of NPGPA: a system energy efficiency versus iterations, b transmit power versus iterations, c Transmit rate versus iterations, d utility versus iterations
Fig. 2 Utility versus iterations for different initial conditions
experiencing different convergence paths, which proves the uniqueness of NE. Figure 3 shows the performance of all the users in central cell for proposed NPGPA method with different pricing factor when reaching steady state. For smaller pricing factor ai = 0.5, all the users transmit with the same maximum transmit power. As pricing factor increases, the
123
hard shut-down mechanism functions for those users with poor channel conditions. Comparing the NPGPA and Iterative Water-Filling Power Allocation (IWFPA) methods in [15] in Fig. 4, we see that the two methods have almost the same system energy efficiency when ai = 0.5 and the NPGPA method results in higher system energy efficiency for ai = 5 and
Int J Wireless Inf Networks (2009) 16:44–50
49
Fig. 3 Steady state performance of NPGPA
5 Conclusion In this paper, the topic of distributed power control and subcarrier assignment in multi-cell OFDMA systems is addressed. We formulate the problem based on potential game theory and propose a NPGPA algorithm. To avoid unnecessary power transmission under poor channel conditions, a mechanism of shutting down inefficient users is integrated into the game theoretic approach. Simulation results show that the proposed NPGPA algorithm can converge to NE quickly and achieve higher system energy efficiency than existing iterative water-filling approach under the constraint of a fixed total transmit power.
Fig. 4 System energy efficiency comparison of NPGPA and IWFPA
10. The IWFPA method assumes that each user sends a constant amount of power no matter how inefficient that particular user is, which might cause severe co-channel interference to other users. For our proposed NPGPA method, inefficient users are shut down for larger pricing factor so as to avoid a waste of power. For instance, according to Fig. 3, in the simulation at ai = 5, pi,max = 1 W, user 3, 4, 9 and 10 have such low capacity that they are unusable. As a result, they are shut down. However, although shutting down inefficient users reduces the number of users in the network, it improves the data rate of existing users and leads to higher system energy efficiency.
References 1. J. Jang and K. B. Lee, Transmit power adaptation for multi-user OFDM systems, IEEE Journal on Selected Areas in Communications, Vol. 21, pp. 171–178, 2003. doi:10.1109/JSAC.2002. 807348. 2. G. C. Song and L. Ye, Cross-layer optimization for OFDM wireless networks-part I: theoretical framework, IEEE Transaction on Wireless Communications, Vol. 4, No. 2, pp. 614–624, 2005. doi:10.1109/TWC.2004.843065. 3. G. C. Song and L. Ye, Cross-layer optimization for OFDM wireless networks-part II: algorithm development, IEEE Transaction on Wireless Communications, Vol. 4, No. 2, pp. 625–634, 2005. doi:10.1109/TWC.2004.843067. 4. Y. J. Zhang and K. B. Letaief, Multiuser adaptive subcarrier-andbit allocation with adaptive cell selection for OFDM systems, IEEE Transactions on Wireless Communications, Vol. 3, No. 5, pp. 1566–1575, 2004. doi:10.1109/TWC.2004.833501.
123
50 5. D. Fudenberg and J. Tirole, Game Theory, MIT press, Cambridge, MA, 1991. pp. 2. 6. M. Felegyhazi and J. P.Hubaus, Game theory in wireless networks: a tutorial. EPEL Technical report: LCA-REPORT_2006_ 002, 2006. 7. Zh. Han and Zh. Ji, Power minimization for multi-cell OFDM networks using distributed non-cooperative game approach. Proceeding of IEEE GLOBECOM, 2004, 3742–3747. 8. L. Wang and Y. S. Xue, Resource allocation in multi-cell OFDM systems based on non-cooperative game. Proceeding of IEEE PIMRC, pp. 1–5, 2006. 9. D. Monderer and L. Shapley, Potential games, Games and Economic Behavior, Vol. 14, pp. 124–143, 1996. doi:10.1006/game. 1996.0044. 10. J. Neel and J. Reed, Convergence of Cognitive Radio Networks. WCNC, 2004. 11. J. Hicks and A. Mackenzie, A Game Theory Perspective on Interference Avoidance. GLOBECOM, 2004. 12. D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, 2nd ed. Athena Scientific Press, 1989. 13. D. P. Bertsekas, Nonlinear programming, 2nd ed. Athena Scientific Press, 1999. 14. H. Harada and R. Prasad, Simulation and Software Radio for Mobile Communications, Artech House, 2002. pp. 341–344.
123
Int J Wireless Inf Networks (2009) 16:44–50 15. W. Yu and W. Ree, Iterative water-filling for Gaussian vector multiple access channels, IEEE Transaction on Information Theory, Vol. 50, No. 2, pp. 145–152, 2004. doi:10.1109/TIT. 2003.821988.
Author Biography Qiu Jing was born in 1978. She received the B.S. and M.S. degrees in electrical and electronic engineering from Chongqing University, Chongqing, China in 2000 and 2003, respectively, and the Ph.D. degree in electronic engineering from Beijing University of Posts and Telecommunications, Beijing, China in 2006. She is currently a assistant professor in the School of Telecommunication Engineering, Chongqing University, Chongqing, China. Her current research interests include mobile wireless broadband access technologies and radio resource management.
