Evolutionary Power Control Games in Wireless Networks
Eitan Altman1 , Rachid El-Azouzi2 , Yezekael Hayel2 and Hamidou Tembine2
2
INRIA, Sophia Antipolis, France. LIA-CERI, Avignon University, France.
1
Abstract. In this paper, we apply evolutionary games to non-cooperative power control in wireless networks. Speci?cally, we focus our study in a power control in W-CDMA and WIMAX wireless systems. We study competitive power control within a large population of mobiles that interfere with each other through many local interactions. Each local interaction involves a random number of mobiles. An utility function is introduced as the di?erence between a utility function based on SIR of the mobile and pricing. The games are not necessarily reciprocal as the set of mobiles causing interference to a given mobile may di?er from the set of those su?ering from its interference. We show how the evolution dynamics and the equilibrium behavior (called Evolutionary Stable Strategy - ESS) are in?uenced by the characteristics of the wireless channel and pricing characteristics. Keywords: power control, evolutionary games, W-CDMA, WiMAX.
1
Introduction
The evolutionary games formalism is a central mathematical tools developed by biologists for predicting population dynamics in the context of interactions between populations. This formalism identi?es and studies two concepts: the ESS (for Evolutionary Stable Strategy), and the Replicator Dynamics. The ESS, ?rst been de?ned in 1972 by the biologist M. Smith [10], is characterized by a property of robustness against invaders (mutations). More speci?cally, (i) if an ESS is reached, then the proportions of each population do not change in time. (ii) at ESS, the populations are immune from being invaded by other small populations. This notion is stronger than Nash equilibrium in which it is only requested that a single user would not bene?t by a change (mutation) of its behavior. The ESS concept helps to understand mixed strategies in games with symmetric payo?s. A mixed strategy can be interpreted as a composition of the population. An ESS can be also interpreted as a Nash equilibrium of the one-shot game but a (symmetric) Nash equilibrium cannot be an ESS. As is shown in [13], ESS has strong re?nement properties of equilibria(proper equilibrium, perfect equilibrium
This work is partially by the ANR WINEM no 06TCOM05 and the INRIA ARC POPEYE. We thank three anonymous reviewers for their many suggestions for improving this paper.
A. Das et al. (Eds.): NETWORKING 2008, LNCS 4982, pp. 930–942, 2008. c IFIP International Federation for Information Processing 2008
Evolutionary Power Control Games in Wireless Networks
931
etc). Although ESS has been de?ned in the context of biological systems, it is highly relevant to engineering as well [14]. In the biological context, the replicator dynamics is a model for the change of the size of the population(s) as biologist observe, where as in engineering, we can go beyond characterizing and modeling existing evolution. The evolution of protocols can be engineered by providing guidelines or regulations for the way to upgrade existing ones and in determining parameters related to deployment of new protocols and services. There have been a lot of work on non-cooperative modeling of power control using game theory [1,2]. There are two advantages in doing so within the framework of evolutionary games: – it provides the stronger concept of equilibria, the ESS, which allows us to identify robustness against deviations of more than one mobile, and – it allows us to apply the generic convergence theory of replicator dynamics, and stability results that we introduce in future sections. The aim of this paper is to apply evolutionary game models to study the interaction of numerous mobiles in competition in a wireless environment. The power control game in wireless networks is a typical non-cooperative game where each mobile decides about his transmit power in order to optimize its performance. This application of non-cooperative game theory and tools is studied in several articles [6,9,7]. The main di?erence in this article is the use of the evolutionary game theory which deals with population dynamics that is well adapted for studying the power control game in dense wireless networks. Speci?cally, we focus our ?rst study in a power control game in a dense wireless ad hoc network where each user transmits using orthogonal codes like in W-CDMA. In the second scenario, we consider also uplink transmissions but inter-cell interferences like in WiMAX cells deployment. The utility function of each mobile is based on carrier(signal)-to-interference ratio and pricing scheme proportional to transmitted power. We provide and predict the evolution of population between two types of behaviors : aggressive (high power) and peaceful (low power). We identify cases in which at ESS, only one population prevails (ESS in pure strategies) and others, in which an equilibrium between several population types is obtained. We also provide the conditions of the uniqueness of ESS. Furthermore, we study di?erent pricing for controlling the evolution of population. The paper is organized as follows: we present in next section some background on evolutionary games. In section 3, we present the evolutionary game model to study the power allocation game in a dense wireless ad hoc network. In section 4, we propose an evolutionary game analysis for the power allocation game in a context of inter-cell interferences between WiMAX cells. Numerical results of both wireless network architectures are proposed in section 5. Section 6 concludes the paper.
2
Basic Notions on Evolutionary Games
We consider the standard setting of evolutionary games: there is a large populations of players; each member of the population has the same ?nite pure strategies set S. There are many local interactions at the same time.
932
E. Altman et al.
Mixed strategies. Denote by Δ(S) the (|S| ? 1)?dimensional simplex of R|S| . Let x(t) be the |S|- dimensional vector whose j?th element xj (t) is the population share of action j at time t. Thus we have j∈S xj (t) = 1 and xj (t) ≥ 0. We frequently use an equivalent interpretation where x(t) is a mixed strategy used by all players at time t; by a mixed strategy we mean that a player chooses at time t an action j with probability xj (t). With either interpretations, at each local interaction occurring at time t a given player can expect that the other player would play action j with probability xj (t). The vector x(t) will also be called the state of the population. Fitness. The ?tness for a player at a given time is determined by the action k taken by the player at that time, as well as by the actions of the population it interacts with. More precisely, if the player 1 chooses the action k when the state of the population is x then player 1 receives the payo? J(k, x) (called ?tness). The function J(k, x) is not necessary linear in x. Below we denote by F (y, x) = k∈S yk J(k, x) the ?tness for an individual using the strategy y when the state of the population is x. ESS. The mixed strategy x is an ESS if for all strategy mut = x there exists mut > 0 such that ? ∈ (0, mut ), F (x, mut) + (1 ? )F (x, x) > F (mut, mut) + (1 ? )F (mut, x). (1)
We have a su?cient condition on the existence of the ESS. The strategy s is an ESS if it satis?es F (x, x) ≥ F (mut, x), ? mut, and (2) ? mut = x, F (x, x) = F (mut, x) ? F (x, mut) > F (mut, mut). (3)
Dynamics. Evolutionary game theory considers a dynamic scenario where players are constantly interacting with others players and adapting their choices based on the ?tness they receive. A strategy having higher ?tness than others tends to gain ground: this is formulated through rules describing the dynamics (such as the replicator dynamics or others) of the sizes of populations (of strategies). The replicator equation is given by d xk (t) = xk [J(k, x) ? F (x, x)] , k ∈ S. (4) dt There is a large number of population dynamics other than the replicator dynamics which have been used in the context of non-cooperative games. Examples are the excess payo? dynamics, the ?ctitious play dynamics, gradient methods [8], Smith dynamics. Much literature can be found is the extensive survey on evolutionary games in [5].
3
W-CDMA Wireless Network
We study in this section competitive decentralized power control in an wireless network where the mobiles uses, as uplink MAC protocol, the W-CDMA technique
Evolutionary Power Control Games in Wireless Networks
933
R
Fig. 1. Interferences at the receiver in uplink CDMA transmissions
to transmit to a receiver. We assume that there is a large population of mobiles which are randomly placed over a plane following a Poisson process with density λ. We consider a random number of mobiles interacting locally. When a mobile i transmits to its receiver R(i), all mobiles within a circle of radius R centered at the receiver R(i) cause interference to the transmission from node i to receiver R(i) as illustrated in ?gure 1. We assume that a mobile is within a circle of a receiver with probability μ. We de?ne a random variable R which will be used to represent the distance between a mobile and a receiver. Let f (r) be the probability density R function (pdf) for R. Then we have μ = 0 f (r)dr. Remark 1. If we assume that the receivers or access points are randomly distributed following a poisson process with density ν, the probability density function is expressed by f (r) = νe?νr . For uplink transmissions, a mobile has to choose between Higher(H) power level and Lower(L) power level. We denote by PH the higher power and PL the lower power levels. Let s be the population share strategy H. Hence, the signal Pr received at the receiver is given by Pr = gPi l(r), where g is the gain antenna and α > 2 is the path loss exponent. For the attenuation, the most common function is l(t) = t1 , with α ranging from 3 to 6. Note that such l(t) explodes at t = 0, α and thus in particular is not correct for a small distance r and largen intensity λ. Then, it makes sense to assume attenuation to be a bounded function in the vicinity of the antenna. Hence the last function becomes l(t) = max(t, r0 )?α . First we note that the number of transmission within a circle of radius r0 centered 2 at the receiver is λπr0 . Then the interference caused by all mobiles in that circle λπg(sPH +(1?s)PL ) . is I0 (s) = α?2 r0 Now we consider a thin ring Aj with the inner radius rj = jdr and the outer radius rj = r0 + jdr. The signal power received at the receiver from any node in Aj is Pri = gPi . Hence the interference caused by all mobiles in Aj is given by rα
i
Ij (s) =
? ? 2gλπrj dr( sPH +(1?s)PL ) if rj < R, rα ? 2μgλπrj dr( sPH +(1?s)PL ) if rj ≥ R. rα
j j
934
E. Altman et al.
Hence, the total interference contributed by all nodes at the receiver is
R
I(s) = I0 (s) + 2gλπ(sPH + (1 ? s)PL )
r0
r
dr + μ α?1
1
∞ R
1 rα?1
dr ,
= gλπ(sPH + (1 ? s)PL )(
α ?(α?2) r ? 2(1 ? μ)R?(α?2) ). α?2 0
Hence the signal to interference ratio SIN Ri is given by SIN Ri (Pi , s, r) =
α gPi /r0 σ+βI(s) gPi /r α σ+βI(s)
if r ≤ r0 , if r ≥ r0 ,
where σ is the power of the thermal background noise and β is the inverse of the processing gain of the system. This parameter weights the e?ect of interference, depending on the orthogonality between codes used during simultaneous transmissions. In the sequel, we compute the mobile’s utility (?tness) depending on his decision but also on the decision of his interferers. We assume the user’s utility (?tness) choosing power level Pi is expressed by
R
J(Pi , s) = w
0
log(1 + SIN R(Pi , s, r))f (r)dr ? ηPi .
The pricing function Pi de?ne the instantaneous ”price” a mobile pays for using a speci?c amount of power that causes interference in the system and η is a parameter. This price can be the power cost consumption for sending packets. The total ?tness of the population is given by F (s, s) = sJ(PH , s) + (1 ? s)J(PL , s). We are now looking at the existence and uniqueness of the ESS. For this, we need the following result. Lemma 1. For all density function f de?ned on [0, R], the function h : [0, 1] → R de?ned as R 1 + SIN R(PH , s, r) log f (r) dr s ?→ 1 + SIN R(PL , s, r) 0 is continuous and strictly monotone. proof The function s ?→ log
1+SIN R(PH ,s,r) 1+SIN R(PL ,s,r)
f (r) is continuous and integrable
in r on the interval [0, R]. The function h is continuous. Using derivative properties of integral with parameter, we can see that the derivative function of h is the function h : [0, 1] → R de?ned as
R
s ?→
0
? log ?s
? ?s
1 + SIN R(PH , s, r) 1 + SIN R(PL , s, r)
1+SIN R(PH ,s,r) 1+SIN R(PL ,s,r)
f (r).
We show that the term
log
is negative. Let A(s) := = 1+
g(PH ?PL ) rα gPL σ+βI(s)+ rα
1+SIN R(PH ,s,r) 1+SIN R(PL ,s,r) . The function A can be rewritten as A(s)
where
Evolutionary Power Control Games in Wireless Networks
935
I(s) = (s(PH ? PL ) + PL )c(r) and c(r) = λπg if r ≥ r0 and PL )
g(PH ?PL ) rα gPL (σ+βI(s)+ rα )2
?(α?2) α α?2 r0
? 2(1 ? μ)R?(α?2)
λπg α?2 r0
otherwise. Since A satis?es A(s) > 1 and A (s) = ?c(r)β(PH ? < 0. Hence, 1 + SIN R(PH , s, r) 1 + SIN R(PL , s, r) = A (s) ? (log A(s)) = <0 ?s A(s)
? log ?s
i.e h (s) < 0. We conclude that h is strictly decreasing. Using this lemma, we have the following proposition which gives pure strategies depending on the parameters. Proposition 1. For all density function f , the pure strategy PH dominates the R ,PH ,r) η strategy PL if and only if w (PH ? PL ) < 0 log 1+SIN R(PH ,PH ,r) f (r) dr = 1+SIN R(PL h(1). For all density function f , the pure strategy PL dominates the strategy PH R ,PL ,r) η if and only if w (PH ? PL ) > 0 log 1+SIN R(PH ,PL ,r) f (r) dr = h(0). 1+SIN R(PL proof We decompose the existence of the ESS in several cases. 1. PH is preferred to PL : The higher power level dominates the lower if and only if J(PH , PH ) > J(PL , PH ) and J(PH , PL ) > J(PL , PL ). These two inequalities implies that
η (PH ? PL ) < w
R
log
0
1 + SIN R(PH , PH , r) 1 + SIN R(PL , PH , r)
f (r) dr.
2. PL is preferred to PH : Analogously, the lower power dominates the higher power if and only if J(PL , PH ) > J(PH , PH ) and J(PL , PL ) > J(PH , PL ) i.e
η w (PH
? PL ) >
R 0
log
1+SIN R(PH ,PL ,r) 1+SIN R(PL ,PL ,r)
f (r) dr.
We have this other result which gives a su?cient condition for the existence of the ESS.
η Proposition 2. For all density function f , if h(1) < w (PH ? PL ) < h(0), then η ? ? there exists an unique ESS s which is given by s = h?1 w (PH ? PL ) .
Proof. Suppose that the parameters w, η, PH and PL satisfy the following inη equality h(1) < w (PH ? PL ) < h(0). Then the game has no dominant strategy. A mixed equilibrium is characterized by J(PH , s) = J(PL , s). It is easy to see η that this last equation is equivalent to h(s) = w (PH ? PL ). From the lemma η 1, we have that the equation h(s) = w (PH ? PL ) has an unique solution given η by s? = h?1 w (PH ? PL ) . We now prove that this mixed equilibrium is an ESS. To prove this result, we compare s? J(PH , mut) + (1 ? s? )J(PL , mut) and mutJ(PH , mut) + (1 ? mut)J(PL, mut) for all mut = s? . The di?erence between two values is exactly w(s? ? mut)(h(mut) ? h(s? )). According to lemma 1, h is decreasing function. Hence, (s? ? mut)(h(mut) ? h(s? )) is strictly positive for all strategy mut di?erent from s? . We conclude that the mixed equilibrium s? is an ESS.
936
E. Altman et al.
From the last proposition, we can use the pricing η as a design tool for create an incentive for the user to adjust their power control. We observe that the ESS s? decreases when η increases. That means the mobiles become less aggressive when pricing function increases and the system can limit aggressive requests for SIR. In the numerical examples, we show how the pricing function can optimize the overall network throughput. In the next section we study another wireless architecture where interferences are between mobiles which are located in di?erent cell. This typical interference problem occurs in WiMAX environment.
4
OFDMA-Based IEEE802.16 Network
OFDMA (Orthogonal Frequency Division Multiple Access) is recognized as one of the most promising multiple access technique in wireless communication system. This technique is used to improve spectral e?ciency and becomes an attractive multiple access technique for 4th generation mobile communication system as WiMAX. In OFDMA systems, each user occupies a subset of subcarriers, and each carrier is assigned exclusively to only one user at any time. This technique has the advantage of eliminating intra-cell interference (interference between subcarriers is negligible). Hence the transmission is a?ected by intercell interference since users in adjacent sectors may have also been assigned to the same carrier. If those users in the adjacent sectors transmitted with high power the intercell interference may severely limit the SINR achieved by the user. Some form of coordination between the di?erent cells occupying the spectral resource are studied in [4,3]. The optimal resource allocation requires complete information about the network in order to decide which users in which cells should transmit simultaneously with a given power. All of these results however, rely on some form of centralized control to obtain gains at various layers of the communication stack. In a realistic network as WiMAX, centralized multicell coordination is hard to realize in practice, especially in fast-fading environments. We consider an OFDMA system where radio resources are allocated to users on their channel measures and tra?c requirements. Each carrier within a frame must be assigned to at most one user in the corresponding cell. In this way each carrier assignment can be made independently in each cell. Hence when a user is assigned to carrier, the mobile should determine the power transmission to the Base station. This power should take into account the interference experienced by the transmitted packet. Consider the uplink of a multiple multicell system, employing the same spectral resource in each cell. Power control is used in an e?ort to preserve power and to limit interference and fading e?ects. For users located in a given cell, co-channel interference may therefore come from only few cells as illustrated in ?gure 2. Since the intra-cell interference is negligible, we focus on the users which use a speci?c carrier. Consider N cells, and a large number of population of mobiles randomly distributed over each channel and each cell. Since in
Evolutionary Power Control Games in Wireless Networks
937
2 3
7 1
4
6 5
Fig. 2. Hexagonal cell con?guration
OFDMA systems, each carrier is assigned exclusively to only one mobile at any time, we assume that the interactions between mobiles are manifested through many local interactions between N mobiles where N is the set of neighbors of a cell. We can ignore the interaction among more than N mobiles that transmit simultaneously and that can cause interference to each other. Hence, in each slot, interaction occurs only between the mobiles which have been assigned to the same carrier. Let gij denote the average channel gain from user i to cell j. Hence, if a user in cell i transmits with power pi , the received signal strength at cell i is pi gii , while the interference it occurs on cell j is pi gij . Hence, the interference experienced by cell i is given by SIN Ri (p) = σi + gii pi gij pj , where σi is the j=i power of the thermal noise experienced at cell i. The rate achieved by user i is given by ri (p) = log(1 + SIN Ri (p)), where p denotes the power level vector of mobiles choice which are assigned to a speci?c carrier. We assume that the user’s utility is given by ui (p) = ri (p) ? ηpi . The above utility represents the weighted di?erence between the throughput that can be achieved as expressed by Shannon’s capacity and the power consumption cost. We assume that all mobiles perform the on-o? power allocation strategy. In this strategy, each mobile transmits with full power or remains silent. Let Ni be the set of neighbors of a user in cell i. Hence the interference experienced by a user in the cell i is given by SIN Ri (p) = σi + gii pi gji pj , where pj ∈ {0, P }, P is the power level of transmission. Let xi the proportion of transmitters in the cell i. The couple (xi , 1 ? xi ) with xi ∈ (0, 1), represents the state of the cell i. We denote by x?i the vector (x1 , . . . , xi?1 , xi+1 , . . . , xNi ). The ?tness of the cell i can be de?ned as follows: fi (xi , x?i ) = xi fi (P, x?i ) = xi ? x?i (a?i ) = ?
j∈T (a?i )
j∈Ni \{i}
ui (P, a?i )x?i (a?i ) where
a?i ∈{0,P }|Ni |?1
?? xj ? ?
? (1 ? xj )? and
{i}}
j∈Ni \{T (a?i )
T (a?i ) = {k ∈ Ni \{i}, pk = P }, is the set of neighbors transmitting. We have fi (0, x?i ) = 0 for any multi-strategy x?i .
938
E. Altman et al.
A multi-strategy x = (xi )i=1,...N is neutrally stable if for all x = x there exists y > 0 such that ? ∈ (0, y ) fi (xi , x?i + (1 ? )x?i ) ≥ fi (xi , x?i + (1 ? )x?i ) (5)
for some i. The multi-strategy x is evolutionary stable if the inequality (5) is strict. Hence, an ESS is a neutrally stable strategy but the reciprocal is not true. See [11] for more details on neutrally stable strategy. If x is neutrally stable strategy then x is Nash equilibrium. The best response (BR) of the user i to x?i is given by ? ? 1 if fi (P, x?i ) > 0, BRi (x?i ) = 0 if fi (P, x?i ) < 0, ? [0, 1] if fi (P, x?i ) = 0. A strategy x is a Nash equilibrium is equivalent to xi ∈ BRi (x?i ), i = 1, . . . , |N |. In particular when η = 0, the strategy ON is a Nash equilibrium (ON is a dominant strategy). The following proposition gives necessary conditions for pure strategies and strictly mixed strategies to be neutrally stable. Proposition 3. We decompose the di?erent equilibrium strategy in the following items. – If the strategy ON (P) is a neutrally stable equilibrium then η ≤ ηmin where ηmin = 1 P min log 1 + gii
σi P
i=1,...,N
+
j∈Ni , j=i
gji
.
Moreover, ON becomes a strictly dominant strategy if η < ηmin . – If the strategy OFF (0) is a neutrally stable equilibrium then η≥ gii P 1 max log 1 + P i σi =: ηmax .
For η > ηmax , OFF becomes a strictly dominant strategy (hence, an ESS). – If ? j = i, gij = g, gii = g , σi = σ then the game becomes a sym? metric game. Hence, it exists a symmetric equilibrium with the proportion x(= xi , ?i) of transmitters, which must satisfy
n?1
Q(x) :=
k=0
ak xk (1 ? x)n?k?1 (n?1 ) = ηP k
(6)
gP ? where ak = log(1 + σ+kgP ) > 0 represents the ?tness obtained by user i when he transmits and k of the opponents of user i decided to transmit and the n ? 1 ? k others stay quiet. – Every strictly mixed equilibrium (symmetric or not) must satisfy fi (xi , x?i ) = 0 for all i.
Evolutionary Power Control Games in Wireless Networks
939
Proof. The two ?rst assertions of proposition 3 are obtained by Nash equilibrium conditions: the strategy ON (P) is a neutrally stable equilibrium implies that ?i, 0 ≤ fi (P, P, . . . , P ) and the strategy OFF (0) is a neutrally stable equilibrium implies that ?i, fi (P, 0, . . . , 0) ≤ 0. In the last assertion (symmetric case), the ?tness of user i is x(Q(x)?ηP ) where (x, 1?x) is state of the cell. Since Q(1) < 0 and Q(0) > 0 when ηmin < η < ηmax , then the equation (6) has a solution x in (0, 1) which implies the existence of an ESS. Remark that the strategy ON is an ESS if η < ηmin . In order to prove the existence and uniqueness of the ESS in the symmetric case, we study roots of the polynomial Q in the following lemma. Lemma 1. Let 0 ≤ an?1 < an?2 < . . . < a0 , η and P positive reals satisfying ηP ∈ (an?1 , a0 ). Then, the polynomial Q(x) ? ηP has a unique root on (0, 1). Proof. We show existence and uniqueness of the root of the polynomial Q on (0, 1). Existence. Q is a polynomial with real coe?cients. Hence, Q is continuous in (0, 1). The image of the interval (0, 1) contains I = [an?1 ? ηP, a0 ? ηP ]. The inequality an?1 := ηmin < η < a0 := ηmax , implies 0 ∈ I. Thus, there exists, P P a ∈ (0, 1) such that Q(a) = 0. Uniqueness. We show that Q is strictly monotone on (0, 1). Let Q be the derivative of Q. Q is given by Q (x) = ?(n ? 1)a0 (1 ? x)n?2 + (n ? 1)an?1 xn?1 +
n?2 k=1
ak (n?1 )xk (1 ? x)n?1?k k
The inequalities ak ? ak+1 > 0, k = 0, . . . , n ? 2 and x ≥ 0, 1 ? x ≥ 0 imply that Q (x) < 0 on (0, 1). Hence, Q is strictly increasing on (0, 1). We conclude that Q is bijective from (0, 1) to I and hence, Q has a unique root on (0, 1) Given this result, we have the following proposition given the existence and uniqueness of the ESS in the symmetric game. The proof is immediate from the lemma 1 and from proposition 3. Proposition 4. The symmetric power control game has a unique strictly mixed equilibrium.
5
Numerical Examples
In this section, we ?rst investigate the impact of the di?erent parameters and pricing on the ESS and the convergence of the replicator dynamic. We also discuss the impact of the pricing function on the system capacity. W-CDMA Wireless Networks: we show the impact of density of nodes and pricing on the ESS and the average rate. We assume that the receivers which are randomly placed over a plane following a Poisson process with density ν,
940
E. Altman et al.
i.e, f (r) = νe?νr . We recall that the rate of a mobile using power level Pi at R the equilibrium is given by w 0 log(1 + SIN R(Pi , s, r))f (r)dr. We took r0 = 0.2, w = 20, σ = 0.2, α = 3, β = 0.2, R = 1. First, we show the impact of the density of nodes λ on the ESS and the average rate. In ?gures 3-4, we depict the average rate obtained at the equilibrium and the ESS, respectively , as a function of the density λ. We recall that the interference for a mobile increases when λ increases. We observe that the mobiles become less aggressive when the density increases. In the ?gure 3, we observe that it is important to adapt the pricing as function of the density of nodes. Indeed, we observe that for low density of nodes, the lower pricing (η = 0.92) gives better results than higher pricing (η = 0.97). When the density of nodes increases, the better performance is obtained with higher pricing.
0.8
7.8
η=0.92 η=0.97
7.7
0.7
η=0.92 η=0.97
0.6
7.6
0.5
Throughput
7.5
ESS
0.4
7.4
0.3
7.3
0.2
7.2
0.1
7.1 0.2
0.25
0.3
0.35
0.4
0.45
0.5
0 0.2
0.25
0.3
0.35
0.4
0.45
0.5
Density of nodes
Density of nodes
Fig. 3. The average rate of a mobile at Fig. 4. ESS versus density of nodes λ for equilibrium as function of the density of η = 0.92, 0.97 nodes λ for η = 0.92, 0.97
Our second experiment in W-CDMA studies convergence to the ESS of the W-CDMA system described in section 3 under replicator dynamics. Fig. 5 and 6 represent the fraction of population using the high power level for di?erent initial states of the population: 0.99, 0.66, 0.25 and 0.03. We observe that the choice of receiver distributions change the ESS.
1 1
Proportion of players using the high power level: s(t)
0.9
0.8
s =0.99 0 s0=0.66 s =0.25 0 s0=0.03
Proportion of players using the high power level: s(t)
0.9
0.8
s =0.99 0 s0=0.66 s =0.25 0 s0=0.03
0.7
0.7
0.6
0.6
0.5
0.5
0.4
0.4
0.3
0.3
0.2
0.2
0.1
0.1
0
0
2
4
6
8
10
12
14
16
18
20
0
0
5
10
15
20
25
30
35
40
time t
time t
Fig. 5. Convergence to the ESS in CDMA Fig. 6. Convergence to the ESS in CDMA system: uniform distribution system: quadratic distribution
OFDMA-based IEEE802.16 networks. We consider below an numerical example of an OFDMA system. We shall obtain the ESS for several values of
Evolutionary Power Control Games in Wireless Networks
941
η. We assume that gii = g and gij = g for all i = j and σi = σ for all i. We ? consider below a numerical example for di?erent values of N (see ?gure 2 in which N = 7). Let the noise σ = 0.1 and the power attenuation g = g/4 = 0.9. ? In ?gure 7 (resp. 8), we plot the ESS versus η (resp. power level P ). In both ?gures, the population ratio using the strategy ON is monotone decreasing in η.
1
0.7
0.9
0.6
0.8
0.7
0.5
n=3 n=4 n=5 n=6 n=10 n=11
Optimal Strtaegy
0.6
0.5
0.4
0.3
0.2
0.1
0
Optimal Strategy
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
0.4
0.3
0.2
0.1
Pricing parameter η
0 0.6
0.7
0.8
0.9
1
1.1
1.2
1.3
1.4
Power Level
Fig. 7. The population ratio using strategy Fig. 8. The population ratio using strategy ON at equilibrium as a function of η for ON as a function of power level for n = n=7 3, 4, 5, 6, 10, 11
We see that the parameter η which can be interpreted as the pricing per unit of power transmitted, can determine whether the ESS is aggressive (in pure strategies) or in mixed strategies. It can determine in the latter case what fraction of the population will use high power at equilibrium. Pricing can thus be used to control interference.
6
Concluding Remarks
We considered power control games with one or several populations of users and studied evolutionary stable strategies in interaction of numerous mobiles in competition in a wireless environment. We have modeled power control for W-CDMA and OFDMA systems as a non-cooperative population game in which each user needs to decide how much power to transmit over each receiver and many local interactions between users at the same time has been considered. We have derived the conditions for existence and uniqueness of evolutionary stable strategies and characterize the distribution of the users over each power level.
References
1. Alpcan, T., Basar, T., Srikant, R., Altman, E.: CDMA uplink power control as a noncooperative game. Wireless Networks 8(6), 659–670 (2002) 2. Sagduyu, Y.E., Ephremides, A.: SINR-Based MAC Games for Sel?sh and Malicious Users. In: Information Theory and Applications Workshop, San Diego, CA (to appear, January 2007) 3. Hoon, K., Youngnam, H., Jayong, K.: Optimal subchannel allocation scheme in multicell OFDMA systems. In: Proc. IEEE VTC (May 2004)
942
E. Altman et al.
4. Li, G., Liu, H.: Downlink dynamic resource allocation for multi-cell OFDMA system. In: Proc. IEEE VTC (October 2003) 5. Hofbauer, J., Sigmund, K.: Evolutionary game dynamics. AMS 40(4), 479–519 (2003) 6. Meshkati, F., Poor, H., Schwartz, S., Mandayam, N.: An Energy-E?cient Approach to Power Control and Receiver Design in Wireless Data Networks. IEEE Trans. on Communications 52 (2005) 7. Meshkati, F., Poor, H., Schwartz, S.: Energy-E?cient Resource Allocation in Wireless Networks. IEEE Signal Processing Mag. 58 (2007) 8. Rosen, J.B.: Existence and uniqueness of equilibrium points for concave N-person games. Econometrica 33, 520–534 (1965) 9. Saraydar, C., Mandayam, N., Goodman, D.: E?cient Power Control via Pricing in Wireless Data Networks. IEEE Trans. on Communication 50 (2002) 10. Smith, M.: Game Theory and the Evolution of Fighting. In: Smith, J.M. (ed.) On Evolution, pp. 8–28. Edinburgh Univ. Press, Edinburgh (1972) 11. Samuelson, L.: Evolutionary Games and Equilibrium Selection. MIT Press, Cambridge (1997) 12. Tembine, H., Altman, E., ElAzouzi, R., Hayel, Y.: Evolutionary games with random number of interacting players with application to access control. In: Wiopt (to appear 2008) 13. van Damme, E.: Stability and perfection of Nash equilibria. Springer, Heidelberg (1991) 14. Vincent, T.L., Vincent, T.L.S.: Evolution and control system design. IEEE Control Systems Mag. 20(5), 20–35 (2000)