Automatica 42 (2006) 1837 – 1847 www.elsevier.com/locate/automatica
A passivity approach to game-theoretic CDMA power control夡 X. Fan a,∗ , T. Alpcan b , M. Arcak c , T.J. Wen c , T. Ba¸sar b a University of Miami, Florida, FL, USA b University of Illinois, Urbana-Champaign, IL, USA c Rensselaer Polytechnic Institute, Troy, NY, USA
Received 20 December 2004; received in revised form 27 November 2005; accepted 10 May 2006 Available online 23 August 2006
Abstract This paper follows a game-theoretical formulation of the CDMA power control problem and develops new decentralized control algorithms that globally stabilize the desired Nash equilibrium. The novel approach is to exploit the passivity properties of the feedback loop comprising the mobiles and the base station. We first reveal an inherent passivity property in an existing gradient-type algorithm, and prove stability from the Passivity Theorem. We then exploit this passivity property to develop two new designs. In the first design, we extend the base station algorithm with Zames–Falb multipliers which preserve its passivity properties. In the second design, we broaden the mobile power update laws with more general, dynamic, passive controllers. These new designs may be exploited to enhance robustness and performance, as illustrated with a realistic simulation study. We then proceed to show robustness of these algorithms against time-varying channel gains. 䉷 2006 Elsevier Ltd. All rights reserved. Keywords: CDMA power control; Nonlinear control; Passivity; Game theory
1. Introduction In wireless communication networks, transmission power levels must be regulated to maintain a satisfactory quality of service for users. Increased power levels ensure longer transmission distance and higher data transfer rate, but also increase battery consumption and interference to neighboring users. In code division multiple access (CDMA) systems, power control was posed by Zander (1992) and Yates (1995) as a constrained optimization problem, where each user minimizes its transmission power level pi , while keeping its signal-to-interference ratio (SIR) i greater than a user-specific threshold tar i , chosen to ensure adequate quality of service. However, in this scheme 夡 This paper was not presented at any IFAC meeting. This paper was recommended for publication in revised form by Associate Editor Andrew R. Teel under the direction of Editor Hasson Khalil. This research is supported in part by the RPI Office of Research through an Exploratory Seed Grant. Research of T. Alpcan and T. Ba¸sar was supported in part by NSF ITR Grant CCR 00-85917. ∗ Corresponding author. Tel.: +1 305 284 8639; fax: +1 305 284 4044. E-mail addresses:
[email protected] (X. Fan),
[email protected] (T. Alpcan),
[email protected] (M. Arcak),
[email protected] (T.J. Wen),
[email protected] (T. Ba¸sar).
0005-1098/$ - see front matter 䉷 2006 Elsevier Ltd. All rights reserved. doi:10.1016/j.automatica.2006.05.022
additional admission control is required to ensure that a feasible solution exists. An alternative approach, pursued in Falomari, Mandayam, and Goodman (1998), Ji and Huang (1998), Alpcan, Ba¸sar, Srikant, and Altman (2002), Alpcan and Ba¸sar (2004), Saraydar, Mandayam, and Goodman (2001), Sung and Wong (1999), is to study the power control problem as an uncooperative game (Ba¸sar & Olsder, 1995), in which each user attempts to minimize its own cost function (or maximize its utility function) in response to the actions of others. Falomari et al. (1998) investigated possible utility functions for both voice and data sources, and showed the existence and uniqueness of the Nash equilibrium. A linear pricing scheme was also proposed in Falomari et al. (1998) to achieve a Pareto improvement in the utilities of mobiles. Alpcan et al. (2002) and Alpcan and Ba¸sar (2004) proposed a power control game, where the cost function is defined as the difference between a pricing function and a logarithmic, strictly concave, utility function of the SIR of the mobiles. The authors then showed the existence of a unique Nash equilibrium, and stabilized it with a gradient algorithm, in which each mobile updates its power based upon a feedback from the base station generated by a static algorithm.
1838
X. Fan et al. / Automatica 42 (2006) 1837 – 1847
In this paper, we introduce a passivity framework for CDMA power control in which broader classes of mobile and base station algorithms can be developed. We first show that the gradient algorithm of Alpcan et al. (2002) is a special case in this framework and, next, present two new designs. In our first design, we extend the base station algorithm with Zames–Falb multipliers which preserve its passivity properties. In our second design, we broaden the mobile power update laws with more general, dynamic, passive controllers. For both designs stability is established from the Passivity Theorem (Zames, 1966), which states that the negative feedback interconnection of two passive systems is stable. As we illustrate with an example in Section 6, the additional design flexibility offered by the extended algorithms can be exploited for improved performance and robustness. A similar passivity framework, and extended classes of controllers, were developed in Wen and Arcak (2004) for Internet congestion control. Although CDMA power control relies on a fundamentally different physical infrastructure, we demonstrate in this paper that a mathematical representation of its feedback structure presents similarities to that in Wen and Arcak (2004) for Internet congestion control. The results in this paper, however, are not a direct application of those in Wen and Arcak (2004) because the basis for congestion control schemes studied in Wen and Arcak (2004) is constrained optimization, whereas the CDMA scheme in this paper is game-theoretical. The paper is organized as follows: we introduce in Section 2 the system model considered, and present our passivity-based stability analysis. In Section 3, we design an extended class of price algorithms for the base station. In Section 4, we generalize the power update laws for the mobiles. In Section 5, we show robustness of these algorithms against time-varying channel gains. The simulation results are presented in Section 6, followed by concluding remarks in Section 7. We will use projection functions to ensure nonnegative values for physical quantities, such as power. Given f (x) defined on x ∈ R 0 , its positive projection is defined as f (x) if x > 0, + (f (x))x := 0 (1) if x = 0 and f (x) < 0, f (x) if x = 0 and f (x) 0. If x and f (x) are vectors, then (f (x))+ x is interpreted in the component-wise sense. When (f (x))+ x = 0, we say that the projection is active. When (f (x))+ x = f (x), we say that the projection is inactive. For a function f (x, y) that depends on variables other than x, we define (f (x, y))+ x as in (1), and refer to it projection of f (x, y) with respect to x. In the paper, the state variables are nonnegative quantities, that is x ∈ Rn 0 , and the invariance of the positive orthant Rn 0 is achieved with the help of projection functions defined in (1). Stability of an equilibrium x ∗ is considered in the sense of Lyapunov (Khalil, 1996, Definition 4.1). By global asymptotic stability of x ∗ , we mean that, in addition to stability all solutions starting in Rn 0 converge to x ∗ . The issues of existence and uniqueness of solutions resulting from the discontinuity of these functions is not emphasized in this paper. Existence is guaranteed for a differential inclusion
that encompasses the projection discontinuity, as in Filippov (1988). Using this differential inclusion formulism, it would also be possible to strengthen the stability results proven in this paper. As an example, our definition of global asymptotic stability does not imply uniformity of convergence, whereas for the inclusion (Teel & Praly, 2000, Proposition 1) would guarantee uniformity as well. We denote by x the vector norm of x, and by xLp the Lp -norm of x(t), p ∈ [0, ∞]. For d ∈ L∞ , we define da = limt→∞ sup d(t). A function (·) : R 0 → R 0 is defined to be class- if it is continuous, zero at zero, and strictly increasing, and class-∞ if it is class- and ∞ at ∞. A function (s, t) : R 0 × R 0 → R 0 is a class KL function if for each fixed t 0 the function (·, t) is a class-K function, and for each fixed s 0, (s, t) is decreasing to zero as t → 0. A system x˙ = f (x, u) is said to be input-to state stable (ISS) if there exist class-K functions 0 (·) and (·) such that, n for any input u(·) ∈ Lm ∞ and x0 ∈ R , the response x(t) from the initial state x(0) = x0 satisfies xL∞ 0 (x0 ) + (uL∞ ),
xa (ua ).
A system x˙ = f (x, u), y = h(x) is said to be passive if there exists a continuously differentiable positive semidefinite function V (x) (called the storage function) such that jV V˙ = f (x, u) uT y = uT h(x), jx
∀(x, u) ∈ Rn × Rm .
The system y = h(t, u) is passive if uT y 0. 2. CDMA power control and a passivity property We consider a single-cell CDMA wireless network model which consists of M users and is a special case of the ones described in Fan, Arcak, and Wen (2004a) and Alpcan, Ba¸sar, and Dey (2004). Within the cell, each user connects to the base station with nonnegative sending power pi pmax , where pmax is an upper-bound imposed by physical limitations of the mobiles. The received signal at the base station, yi = hi pi , is attenuated by the channel gain 0 < hi < 1 between the ith mobile and the base station. Thus, the SIR obtained by mobile i at the base station is given by Lhi pi , 2 k=i hk pk +
i :=
(2)
where L is the spreading gain of the CDMA system and 2 is the noise variance containing the contribution of the secondary background interference. We define a power control game as in Alpcan and Ba¸sar (2004) where each user i is associated with a convex cost function defined as the difference between the utility function of the user and its pricing function: Ji = Pi (pi ) − Ui (i (p)),
(3)
in which, p = [p1 , p2 , . . . , pM ]T . The utility function is a logarithmic function of the SIR, i : Ui (i ) = ui log(i + L),
(4)
X. Fan et al. / Automatica 42 (2006) 1837 – 1847
and quantifies the demand of the user for service level or SIR, where ui > 0 is a user-specific utility parameter. The choice of a logarithmic function is motivated by the maximum achievable bandwidth as in Shannon’s (1949) Theorem. The pricing function Pi (pi ) is assumed to be twice continuously differentiable, nondecreasing, and strictly convex in pi . It is imposed by the system to limit the interference caused by each mobile, as well as the battery usage. As shown in Alpcan et al. (2002) and Alpcan and Ba¸sar (2004), the noncooperative game (3) admits a unique Nash equilibrium, and the first-order gradient update law jJi Li hi dUi = 2 jpi di k=i hk pk + dPi (pi ) − i , i > 0, dpi
p˙ i = − i
(5)
where i > 0 is a user-dependent stepsize, achieves asymptotic stability of this Nash equilibrium under a number of conditions on the functions Ui (·) and Pi (·), and on the number of users. In this section, we first present a passivity-based stability proof for the update algorithm (5), which does not impose any restriction on the number of users. Next, we exploit this passivity property to derive broader classes of controllers. Noting from (2) and (4) that ui ( k=i hi pk + 2 ) dUi (i ) ui = = , (6) di i + L L( i hi pi + 2 ) and substituting (6) in (5), we rewrite the controller (5) as + dPi (pi ) u i i h i + , (7) p˙ i = −i 2 dpi k h k pk + pi where the projection (·)+ pi is added to ensure positivity of pi . To prepare for our passivity analysis, we let M be the number of the mobiles, and define h := [ h1
h2
q := (y) = −
· · · hM ]T , 1 , y + 2
(8) (9)
y := hT p,
(10)
w := −h · q.
(11)
The update law (7) can then be represented as in Fig. 1, where the diagonal entries i of the forward block are given by + dPi (pi ) + ui i wi . (12) i : p˙ i = −i dpi pi In this representation, the forward block corresponds to the mobiles and the feedback path corresponds to the base station. Denoting by p∗ the unique Nash equilibrium, and by y ∗ , ∗ q and w ∗ , the corresponding values in (9), (10) and (11), we prove in Proposition 1 below that the forward block is passive from (w − w ∗ ) to (p − p ∗ ). Next, because the feedback block is a nondecreasing function of y, it satisfies the sector property (q − q ∗ )(y − y ∗ )0.
(13)
1839
Fig. 1. First-order gradient algorithm of CDMA power control.
Since pre-multiplication by h and post-multiplication by its transpose, hT , preserve passivity, stability of the equilibrium follows from the Passivity Theorem: Proposition 1. Consider the feedback system (8)–(12), represented as in Fig. 1. The forward system from (w − w ∗ ) to (p − p∗ ) is passive, and the equilibrium p = p ∗ is globally asymptotically stable. Proof. The derivative of the storage function 1 1 (pi − pi∗ )2 V (p − p ∗ ) = 2 u i i
(14)
i
along the solution of (12) is + 1 dPi (pi ) (pi − pi∗ ) −i + ui i wi V˙ = ui i dpi pi i 1 dP (p ) i i (pi − pi∗ ) −i + u i i w i . ui i dpi i
This inequality follows because, if the projection is active, (−i (dPi (pi )/dpi ) + ui i wi )+ pi = 0, pi = 0 and −i (dPi (pi )dpi ) + ui i wi < 0, which means that + 1 dPi (pi ) (pi − pi∗ ) −i + ui i wi 0= ui i dpi pi i 1 dP (p ) i i (−p ∗ ) −i + u i i w i . ui i i dpi i 0 0, f (t) dt < m0 . (18) 0
Our new base station algorithm is the cascade of Z(s) and the nonlinearity (·) in (9), as depicted in Fig. 2 with the dashed feedback block. Its stability follows from the same arguments as in Proposition 1, because a monotone first-third quadrant nonlinearity (9) cascaded with inverse-Zames–Falb multiplier (17) is passive (Willems, 1970; Zames & Falb, 1968):
where xZ is the internal state of Z(s), x˜z = xz − xz∗ in which xz∗ is the equilibrium for the constant input (y ∗ ), and (·) is a nonnegative function (see Willems, 1970, Zames & Falb, 1968 for proofs of this property). We now prove the closedloop stability by using the Lyapunov function V in Proposition 1. The derivative of V along the solution again satisfies (15). Integrating both sides and denoting p˜ := p − p∗ , we get V (p(T ˜ )) − V (p(0)) ˜ T T − W (p(t)) ˜ dt + (p − p ∗ )T (w − w ∗ ) dt 0 0 T T =− W (p(t)) ˜ dt − (y − y ∗ )(q − q ∗ ) dt, 0
0
(21)
X. Fan et al. / Automatica 42 (2006) 1837 – 1847
where W (p(t)) ˜ :=
1 dPi (pi ) dPi (pi∗ ) (pi − pi∗ ) − ui dpi dpi i
is positive definite as in (15), and the equality in (21) follows from (17). Substituting (20) in (21), we obtain V (p(T ˜ )) V (p(0)) ˜ + (x˜Z (0)) T − W (p(t)) ˜ dt 0
V (p(0)) ˜ + (x˜Z (0)),
(22)
which, combined with the Hurwitz property of Z(s), proves stability of the origin (p, ˜ x˜z ) = 0. To prove p˜ → 0, we note from (22) that
T
W (p(t)) ˜ dt V (p(0)) ˜ + (xZ (0)).
0
Then, using boundedness of p, ˙ we can apply Barbalat’s Lemma (Khalil, 1996) to conclude that p˜ → 0 asymptotically. Since Z(s) is Hurwitz, x˜z → 0 also. 4. An extended class of mobile power control algorithms In Section 3, we extended the price update law for the base station using the passivity property of the forward block from (w−w ∗ ) to (p−p ∗ ), and the monotone nondecreasing property of the feedback block in Fig. 1. In this section, we first prove another passivity property in Fig. 1, this time from (w − w ∗ ) to p, ˙ and next use it to generalize the power update law for the mobiles. Proposition 4. Consider the feedback system (8)–(12), represented as in Fig. 1. The forward system from (w − w ∗ ) to p, ˙ and the return system from y˙ to −(q − q ∗ ) are both passive. Proof. For the forward system, we let V1 (p − p ∗ ) =
1 (i (Pi (pi ) − Pi (pi∗ )) ui i i
− ui i wi∗ (pi − pi∗ )) where V1 (0) = 0. The derivative of each component of V1 with respect to pi is jV1 1 = jpi ui i
i
dPi (pi ) − ui i wi∗ dpi
1841
we conclude that V1 is a positive definite function. Next, we note that the derivative of V1 is 1 dPi (pi ) ∗ ˙ V1 = i − ui i wi p˙ i ui i dpi i 1 dPi (pi ) i = − ui i wi p˙ i + (wi − wi∗ )p˙ i ui i dpi i 1 dPi (pi ) i = − ui i wi ui i dpi i + dPi (pi ) × −i + ui i wi dpi pi + (wi − wi∗ )p˙ i . (23) i
Because the first term is negative definite, as can be shown from the uniqueness of equilibrium p ∗ and the discussion in Appendix C in Wen and Arcak (2004), the forward system from (wi − wi∗ ) to p˙ is passive. Now consider the return system, and let y (( ) − (y ∗ )) d V2 (y − y ∗ ) = y∗ y 1 1 = − d , (24) + + 2 y ∗ + 2 y∗ where V2 (0)=0, ∇V2 (0)=(1/(y ∗ +2 )−1/(y +2 ))|y=y ∗ =0, and ∇ 2 V2 = 1/(y + 2 )2 > 0, so V2 is a nonnegative function. The return system from y˙ to (q − q ∗ ) is passive since 1 1 V˙2 = − y˙ = (q − q ∗ )y. − ˙ y + 2 y ∗ + 2 We now extend the first-order control law (7) with a more general class of passive systems: Theorem 5. Consider the feedback interconnection shown in Fig. 2, where the base station price update is given by (9) and the mobile power control law (12) is replaced by + ˙ i = Ai i + Bi −i dPi (pi ) − qi , i ∈ R ni , dpi i + dPi (pi ) − qi . (25) p˙ i = Ci i + Di −i dpi pi If the ith subsystem (Ai , Bi , Ci , Di ) has the structure ⎤ ⎤ ⎡ ⎡ 0 −ai1 bi1 −ai2 ⎥ ⎢ ⎢b ⎥ ⎥ , Bi = ⎢ .i2 ⎥ , Ai = ⎢ .. ⎦ ⎣ ⎣ .. ⎦ . −ai,ni
0
bi,ni
which, when set to zero, has the unique solution at p = p∗ . Because the second derivative is
Ci = [ ci1
j2 V1 1 = P1 (p1 ) > 0, u1 jpi2
with aij > 0, bij > 0, cij > 0, i > 0, ∀i, j , then the equilibrium ( , p)=(0, p∗ ) of the interconnected system is globally asymptotically stable.
ci2
· · · ci,ni ] ,
Di = i ,
(26)
1842
X. Fan et al. / Automatica 42 (2006) 1837 – 1847
The order of the filter (25), ni , is a design parameter. A higher ni introduces additional design flexibility and can be exploited for improved performance and robustness. However, it also increases the cost or power used in implementation, which means that a trade-off has to be made. Simulations in Section 6 show that an improvement is achieved even with the choice ni = 1 in performance.
which implies −i Pi (pi ) + ui i wi 0 since i > 0. Thus,
Proof. We first show that the modified system (25) is passive from (w − w ∗ ) to p. ˙ Consider the following positive definite function for the ith mobile:
V1i ( i , pi − pi∗ )
i (i Pi (pi ) − ui i wi )(−i Pi (pi ) + ui i wi )+ pi = 0, and the left-hand side of (30) is zero and the right-hand side is nonnegative. Substituting (29) and (30) in (28), we obtain
j =1
− ui i wi∗ (pi − pi∗ )).
(27)
The derivative of V1i along the solution (25) and (9) is (after adding and subtracting wi from wi∗ ): V1i ( i , pi − pi∗ ) ⎧ ni ⎨ cij = ij (−aij ij ⎩ b j =1 ij
1 (i Pi (pi ) − ui i wi ) ui i ⎞+ ⎛ ni cij ij + i (−i Pi (pi ) + ui i wi )⎠ ×⎝ +
j =1
j =1
i=1
+ i (i Pi (pi ) − ui i wi ) × (−i Pi (pi ) + ui i wi )+ pi .
(31)
Following the same argument after Eq. (23), we conclude that the right-hand side of the inequality is negative for ( , p) = (0, p ∗ ) and, hence, the equilibrium (0, p ∗ ) is globally asymptotically stable. 5. Robustness against slowly-varying channel gain
(28)
We first note that cij ij (−aij ij + bij (−i Pi (pi ) + ui i wi ))+ ij bij + aij cij 2 = − + cij ij (−i Pi (pi ) + ui i wi ) bij ij
(29)
ij
which is immediate if the projection is inactive. If the projection is active, then ij = 0, and both sides of the equality are zero. Next, we claim that ⎛ ⎞+ ni (i Pi (pi )−ui i wi )⎝ cij ij + i (−i Pi (pi )+ui i wi )⎠ j =1
(i Pi (pi ) − ui i wi )
pi ni
cij ij
j =1
+ i (i Pi (pi ) − ui i wi )(−i Pi (pi ) + ui i wi )+ pi . If the projection is inactive, this inequality holds since i (i Pi (pi ) − ui i wi )(−i Pi (pi ) + ui i wi )+ pi 0. If the projection is active, then
j =1
from which it follows that M ni aij cij 2 d V1i + V2 − dt bij ij
pi
+ (wi − wi∗ )p˙ i .
ni
aij cij 2 + i (i Pi (pi ) bij ij
∗ + ui i wi )+ pi + (wi − wi )p˙ i
⎫ ⎬
+ bij (−i Pi (pi ) + ui i wi ))+ ij ⎭
−
− ui i wi )(−i Pi (pi )
ni cij 2 1 V1i ( i , pi − pi∗ ) = ij + (i (Pi (pi ) − Pi (pi∗ )) 2bij ui i j =1
ni
cij ij + i (−i Pi (pi ) + ui i wi ) 0,
(30)
Thus far we have assumed that the channel gain hi is constant, whereas it may vary in time due to Rayleigh fading, which occurs on a fast time scale, and due to the slower displacement of mobiles. As we further discuss in Section 6, fast variations can be filtered with a maximum likelihood estimator (MLE) tailored to the Rayleigh distribution (Ruprecht, 1989). Thus, in this section we treat hi (t) as a slowly varying parameter and prove an input-to-state stability (Sontag, 1989) property of the algorithm in Theorem 6 against the bounded time derivative h˙ i (t). Theorem 6. Consider the feedback interconnection in Fig. 1, where the base station price update and the mobile power control law are given by (9) and (25), respectively. If the pricing function Pi (pi ) is twice continuously differentiable, nondecreasing, and strictly convex in pi , and further satisfies 1 pi
dPi (pi ) dpi
2 → ∞,
as pi → ∞,
(32)
then the system (8)–(11), (25) satisfies the input-to-state stability estimate: ∗ ∗ ˙ p(t) − p (p(0) − p , t) + sup h( ) ,
0
∀t 0,
(33)
where (·) is a class-KL function and is a class-K function.
X. Fan et al. / Automatica 42 (2006) 1837 – 1847
Proof. Because the Nash equilibrium p ∗ depends on hi ’s via fi (p, h) = −i i = 1, . . . , M
which implies, from (q − q ∗ )y˙ = (q − q ∗ )hT p˙ + (q − q ∗ )h˙ T p = − (wi − wi∗ )p˙ i + (q − q ∗ ) h˙ i pi
dPi (pi∗ ) ui i hi + = 0, ∗ 2 dpi k hk pk + (34)
p∗ is now time-varying. Toprove estimate (33), we use the same storage function V1 = M i=1 V1i for the forward system as in Theorem 2, and obtain from the same steps as in (27)–(31):
i
V˙ − (p − p ∗ ) + −
i=1
ni M i=1 j =1
+
M
−
+
aij cij 2 bij ij (35)
Because the first term on the right-hand side of (35) is negative definite and approaches infinity as p goes to infinity, as shown from the uniqueness of equilibrium p∗ and the discussion in Appendix C in Wen and Arcak (2004), there exists a class-∞ function (·) such that
i
− (p − p ∗ ),
(36)
h˙ i pi ((hT p) − (hT p ∗ ))
Because jw ∗ ˙ w˙ ∗ = h, jh
ni M
−
i=1 j =1
(37)
For the return system, the function y (( ) − (y ∗ )) d V2 (y − y ∗ ) = y∗ y 1 1 = − d + ∗ + 2 y + 2 y∗ satisfies V2 (0)=0, ∇V2 (0)=(1/(y ∗ +2 )−1/(y+2 ))|y=y ∗ =0, and ∇ 2 V2 =1/(y +2 )2 > 0, so we can choose V2 as the storage function and its derivative is V˙2 = ((y) − (y ∗ ))y˙ + (y ∗ )(y − y ∗ )y˙ ∗ = (q − q ∗ )y˙ + (y ∗ )(y − y ∗ )y˙ ∗ . Thus, the Lyapunov function V = V1 + V2 yields −
aij cij 2 bij ij
+ (wi − wi∗ )p˙ i − ui i (pi − pi∗ )w˙ i∗ + (q − q ∗ )y˙ + (y ∗ )(y − y ∗ )T y˙ ∗
jy ∗ ˙ h, jh
(38)
˙ max{|w˙ i∗ |, |y˙ ∗ |} h,
∀i = 1, . . . , M
where aij cij , bij
(39)
and
aij cij 2 bij ij
− ui i (pi − pi∗ )w˙ i∗ .
y˙ ∗ =
where jw∗ /jh and jy ∗ /jh are bounded due to boundedness of hi ’s within the interval [0, 1], we obtain
:= mini,j
which implies
i=1 j =1
− pi∗ )
V˙ − 2 − (p − p ∗ ) + p − p ∗
i=1
V˙ − (p − p ∗ ) +
aij cij 2 bij ij
for some > 0. Thus, we have
+ M 1 dPi (pi ) 1 dPi (pi ) − − wi + wi ui dpi ui dpi pi
ni M
i=1 j =1
ui i w˙ i∗ (pi
−
i
i=1
+ (wi − wi∗ )p˙ i
ni M
+ (q ∗ )2 (y˙ ∗ )T hT (p − p ∗ ).
(wi − wi∗ )p˙ i − ui i (pi − pi∗ )w˙ i∗ .
V˙1 = − (p − p ∗ ) +
i
that,
+ M 1 dPi (pi ) 1 dPi (pi ) V˙1 − − wi + wi ui dpi ui dpi pi +
1843
Mp max h ˙ ˙ h + h(q ∗ )2 h. 4 Observing h is bounded and using the inequality
˙ + := uh
(40)
p − p∗ (p − p ∗ )p − p ∗ + −1 ()
(41)
which holds for any class-∞ function (·), we obtain V˙ − 2 − {(p − p ∗ ) − (p − p ∗ )p − p ∗ } + −1 (). From assumption (32) we can choose a class-∞ function satisfying (r) , 2r and obtain
(r)
∀r 0
V˙ − 2 −
1 2
(p − p ∗ ) + −1 ().
(42)
(43)
The input-to-state stability estimate (33) thus follows from (43) by Sontag and Wang (1995, Remark 2.4). While Theorem 3 has been proven for the basic form of the gradient algorithm in Section 2, analogous results can be derived for the broader classes of algorithms developed in Sections 3 and 4.
1844
X. Fan et al. / Automatica 42 (2006) 1837 – 1847
6. Simulations We now simulate the power control schemes developed in previous sections using MATLAB. For the purpose of simulations we extend the single cell wireless network model considered in the previous sections to a multicell model, similar to the ones described in Alpcan et al. (2004), and depicted in Fig. 3. For “hand-offs” of mobiles between different cells, the same switching-based studies presented in Alpcan and Ba¸sar (2004) and Paul, Akar, Mitra, and Safonov (2004) is applicable. We let the wireless network consist of six arbitrarily placed cells and 10 mobiles. Users connect to the nearest base station within the network, where we make the simplifying assumptions that each cell contains one base station, and that each mobile connects to a single base station at any given time. Mobiles are initially located randomly in the system and their locations are shown in Fig. 4(a), while their movement, modeled as a random walk, is shown in Fig. 4(b). In simulations, we make the channel model more realistic by taking the fast time-scale Rayleigh fading into account. As a result, the received signal at the base station, yi = hi gi pi , is
attenuated by slow-varying gain, hi and fast-varying Rayleigh distributed random variable gi > 0. The gain hi is modeled by the log-normal shadowing path loss model, hi =(0.1/di ) ·Y−1 , where di denotes the distance to the base station and log(Y ) is a zero-mean Gaussian random variable with a standard deviation of = 0.1. The loss exponent is chosen as 2.5 which corresponds to a low density urban environment Rapaport (1996). We study the channel gain model in two time-scales. In the fast time-scale, where the base station samples the received power levels with frequency ff , the received power levels exhibit significant amount of variation due to Rayleigh fading, and hence, it is hard to implement any power control algorithms. Thus, the base station takes k independent received power levels within each time interval Ts = k/ff , k > 1, and implements a MLE on these samples. It is not difficult to show that this MLE is unbiased, and hence, we can take this slower time scale of fs = 1/Ts for our analysis and designs in Sections 3–5. The frequency fs is chosen in such a way that the channel gain, hi , varies slowly from one time interval Ts = 1/fs to another as assumed in the previous sections.
Fig. 3. A simple multicell wireless network.
Locations of Base Stations and Mobiles
Locations of Base Stations and Mobiles
2
1.8
1.6
1.6
1.4
1.4
1.2 1
1 0.8
0.6
0.6
0.4
0.4
0.4
0.6
0.8
1
1.2
X Coordinate
1.4
1.6
1.8
0.2 0.2
2
Base Station Mobile
1.2
0.8
0.2 0.2
(a)
Base Station Mobile
Y Coordinate
Y Coordinate
1.8
2
0.4
0.6
(b) Fig. 4. Mobile locations and movements of mobiles.
0.8
1
1.2
X Coordinate
1.4
1.6
1.8
2
X. Fan et al. / Automatica 42 (2006) 1837 – 1847
The cost function for the ith user is chosen as
while the extended passive power control algorithm is
2 Ji =−pmax pi −pmax log(pmax −pi )−i h2i pi2 −ui log(i +L),
where ui = 10, and pmax = 1000, which are chosen to be the same for all users for simplicity. When discretized with an Euler approximation, the basic gradient algorithm (5) for the ith user becomes pi (n + 1) = pi (n) pmax pi (n) u i hi , + i − + 2 pmax − pi (n) k hk pk (n) + (44)
Loop gain Bode plot comparison between controllers A1 and B1
Magnitude (dB)
40 20
pi (n + 1) = pi (n) + Ci i (n) pmax pi (n) u i hi + Di − , + 2 pmax − pi (n) k hk pk (n) + (45) where n denotes the updating time, and pi (n) is projected into the set [0, pmax ] for all i, n. To illustrate how one can exploit the additional design flexibility in the extended algorithm (45), we compare its delay robustness to that of the basic design (44). From linear system theory, the delay robustness for single-input-single-output (SISO) system is given in Franklin, Powell, and Emami-Naeini (1994) by Tmax =
-20 -40
A1 B1 -45
10-3
10-2
10-1 100 Frequency (rad/sec)
101
102
PM , gc
(46)
where Tmax is the maximum delay allowed in the feedback loop without destabilizing the system, PM is the phase margin, and gc is the gain crossover frequency. To enhance robustness, one needs to increase the phase margin and/or decrease the bandwidth. This may be accomplished by making use of the design flexibility introduced by A, B, C, and D in (45). To illustrate the result, we consider A=−20, B =1, C =0.5, and D = 0.5, and linearized (44) and (45) around the equilibrium p ∗ . The corresponding loop gain of the linearized system is
-60 0 Phase (deg)
i (n + 1) = i (n) + Ai i (n) pmax pi (n) u i hi + Bi − + , 2 pmax − pi (n) k hk pk (n) +
0
-90 10-4
1845
103
Fig. 5. Bode plot comparison. Upper: basic gradient algorithm (44); Lower: extended design (45).
Gs (s) = hT (hT p)(I − W (s))(P (p ∗ ))−1 s −1 W (s)h, where W (s) = diag{i } for the basic gradient algorithm (44) and W (s) = diag{Di + Ci (sI − Ai )−1 Bi } for controller (45).
Power Levels of Selected Mobiles
Power Levels of Selected Mobiles
3.5
5 4.5
3
4 2.5 Power Levels
Power Levels
3.5 3 2.5 2 1.5
2
1.5
1
1 0.5 0.5 0
(a)
300
400
500
600
700
800 900 1000 1100 1200 1300 1400 Time
0
(b)
300
400
500
600
700
800 900 1000 1100 1200 1300 1400 Time
Fig. 6. The power levels comparison when mobile is stationary and transmission delay is 2 s: (a) basic gradient algorithm (44) with predicted delay stability margin 1.29 s; (b) controller (45) with margin 26.8 s.
1846
X. Fan et al. / Automatica 42 (2006) 1837 – 1847 Power Levels of Mobiles
Power Levels of Selected Mobiles
5
4
4.5
3.5
4 3
3
Power Levels
Power Levels
3.5
2.5 2
2.5 2 1.5
1.5 1 1 0.5
0.5 0 300
400
(a)
500
600
700
800 900 1000 1100 1200 1300 1400 Time
0
300
(b)
400
500
600
700
800 900 1000 1100 1200 1300 1400 Time
Fig. 7. The power levels comparison when mobile is moving and transmission delay is 2 s: (a) basic gradient algorithm (44) with predicted delay stability margin 1.29 s; (b) controller (45) with margin 26.8 s.
The loop gain for the two controllers are shown in Fig. 5. The corresponding predicted delay stability margin, based on (46), is 1.29 s for (44), whereas it is 26.8 s for controller (25)–(26). This is indeed verified by simulations as shown in Figs. 6 and 7. Fig. 6 shows the situation where the mobiles are stationary and Fig. 7 shows the case where they exhibit a random walk. We note from Fig. 6 that, when delay is large, the basic gradient algorithm (44) becomes unstable, while controller (45) still shows convergence. A comparison of Figs. 6 and 7 also suggests robustness properties of controller (45) against mobiles’ location variation, which cause h(t) to vary with ˙ |h(t)|0.1.
7. Conclusion Following a game-theoretical formulation of the CDMA power control problem, we developed in this paper a class of mobile and base station passive controllers more general than heretofore. In our first design, we extended the base station algorithm with Zames–Falb multipliers which preserve its passivity properties. In our second design, we broadened the mobile power update laws with more general, dynamic, passive controllers, and studied their robustness against time varying channel gains. As we illustrated with an example, these extended controllers offer additional design flexibility, which can be exploited for several objectives, such as for improved robustness to disturbances and time-delays. The foundation of the study in this paper was the passivity framework, which also perfectly matched the underlying decentralized feedback structure in computer networks (Wen & Arcak, 2004). Our next question is: can it also be applied to other broader spatially-distributed systems, such as transportation, economic and power systems?
References Alpcan, T., & Ba¸sar, T. (2004). A hybrid systems model for power control in multicell wireless data networks. Performance Evaluation, 57(4), 477–495. Alpcan, T., Ba¸sar, T., & Dey, S., (2004). A power control game based on outage probabilities for multicell wireless data networks. Proceedings of the American control conference (Vol. 2, pp. 1661–1666), Boston, MA, July 2004. Alpcan, T., Ba¸sar, T., Srikant, R., & Altman, E. (2002). CDMA uplink power control as a noncooperative game. Wireless Networks, 8, 659–669. Ba¸sar, T., & Olsder, G. J. (1995). Dynamic noncooperative game theory. (2nd ed.), London, San Diego: Academic Press. Falomari, D., Mandayam, N.,& Goodman, D., (1998). A new framework for power control in wireless data networks: Games utility and pricing. Proceedings of Allerton conference on communication, control, and computing (pp. 546–555). Illinois, USA, September 1998. Fan, X., Arcak, M.,& Wen, J.T., (2004a). Passivation designs for CDMA uplink power control. Proceedings of the American control conference (Vol. 4, pp. 3617–3621), Boston, MA, July 2004. Fan, X., Arcak, M., & Wen, J.T., (2004b). Robustness of CDMA power control against disturbances and time-delays. Proceedings of the American control conference (Vol. 4, pp. 3622–3627), Boston, MA, July 2004. Filippov, A. F. (1988). Differential equations with discontinuous right-hand sides. Dordrecht: Kluwer Academic. Franklin, G. F., Powell, J. D., & Emami-Naeini, A. (1994). Feedback control of dynamic systems. (3rd ed.), Boston, MA: Addison-Wesley Publishing Company, Inc.. Ji, H., & Huang, C. (1998). Non-cooperative uplink power control in cellular radio systems. Wireless Networks, 4(3), 233–240. Khalil, H. (1996). Nonlinear systems. (2nd ed.), Englewood Cliffs, NJ: Prentice Hall. Paul, A., Akar, M., Mitra, U., & Safonov, M., (2004). A switched system model for stability analysis of distributed power control algorithms for cellular communications. Proceedings of American control conference (Vol. 2, pp. 1655–1660), Boston, MA, July 2004. Rapaport, T. S. (1996). Wireless communications: Principles and practice. Upper Saddle River, NJ: Prentice Hall. Ruprecht, J. (1989). Maximum-likelihood estimation of multipath channels. Konstanz, Germany: Hartung-Gorre Verlag. Saraydar, C. U., Mandayam, N., & Goodman, D. (2001). Pricing and power control in a multicell wireless data network. IEEE Journal on Selected Areas in Communications, 19(10), 1883–1892.
X. Fan et al. / Automatica 42 (2006) 1837 – 1847 Shannon, C. E. (1949). The mathematical theory of information. Urbana, IL: University of Illinois Press, (reprinted 1998). Sontag, E. (1989). Smooth stabilization implies coprime factorization. IEEE Transactions on Automatic Control, 34, 435–443. Sontag, E. D., & Wang, Y. (1995). On characterizations of the input-to-state stability property. Systems & Control Letters, 24, 351–359. Sung, C.W., & Wong, W.S., (1999). Power control for multirate multimedia CDMA systems. Proceedings of IEEE Infocom (Vol. 2, pp. 957–964), New York, NY, 1999. Teel, A. R., & Praly, L. (2000). A smooth Lyapunov function from a class-KL estimate involving two positive semidefinite functions. ESAIM Control Optimization Calculus of Variation, 5, 313–367. Wen, J., & Arcak, M. (2004). A unifying passivity framework for network flow control. IEEE Transactions on Automatic Control, 49(2), 162–174. Willems, J. L. (1970). Stability theory of dynamical systems. New York: Wiley. Yates, R. D. (1995). A framework for uplink power control in cellular radio systems. IEEE Journal on Selected Areas in Communications, 13(7), 1341–1347. Zames, G., (1966). On the input–output stability of time-varying nonlinear feedback systems, Part I: Conditions derived using concepts of loop gain, conicity, and positivity; Part II: Conditions involving circles in the frequency plane and sector nonlinearities. IEEE Transactions on Automatic Control, AC-11: 228–238, 465–476. Zames, G., & Falb, P. L. (1968). Stability conditions for systems with monotone and slopere-stricted nonlinearities. SIAM Journal on Control, 6, 89–109. Zander, J. (1992). Performance of optimum transmitter power control in cellular radio systems. IEEE Transactions on Vehicular Technology, 41(1), 57–62.
Xingzhe Fan received the B.E. and M.E. degrees from Tsinghua University, Beijing, China, and the Ph.D. degree from the Electrical, Computer, and Systems Engineering Department, Rensselaer Polytechnic Institute, Troy, NY, in 1998, 2000, and 2004, respectively. He is currently a visiting assistant professor in University of Miami, Miami, FL. His research interests are in nonlinear control and distributed optimization and communication systems.
Tansu Alpcan received the B.S. degree in electrical engineering from Bogazici University,Istanbul, Turkey in 1998. He received the M.S. and Ph.D. degrees in electrical and computer engineering from the University of Illinois at Urbana-Champaign in 2001 and 2006, respectively. His research interests include game theory, control and optimization of communication networks, network security, and intrusion detection. He has authored or co-authored more than 20 journal and conference articles. Dr. Alpcan was an associate editor for the IEEE Conference on Control Applications (CCA) in 2005. He received a Fulbright scholarship in 1999 and the Best Student Paper Award at the IEEE Conference on Control Applications in 2003. Dr. Alpcan received Robert T. Chien and Martin J. Ross awards from the University of Illinois in 2006.
Murat Arcak is an assistant professor of Electrical, Computer and Systems Engineering at the Rensselaer Polytechnic Institute in Troy, NY. He was born in Istanbul, Turkey in 1973. He received the B.S. degree in Electrical and Electronics Engineering from the Bogazici University, Istanbul, in 1996, and the M.S. and Ph.D. degrees in Electrical and Computer Engineering from the University of California, Santa Barbara, in 1997 and 2000, under the direction of
1847
Petar Kokotovic. He joined Rensselaer in 2001. Dr. Arcak’s research is in nonlinear control theory and its applications, with particular interest in robust and observer-based feedback designs and in analysis and design of large-scale networks. In these areas, he has published over eighty journal and conference papers, and organized several technical workshops. He is a member of SIAM, a senior member of IEEE, and an associate editor for the IFAC journal Automatica. He received a CAREER Award from the National Science Foundation in 2003, and the Donald P. Eckman Award from the American Automatic Control Council in 2006. John Ting-Yung Wen received the B. Eng. degree from McGill University, Montreal, QC, Canada, in 1979, the M.S. degree from the University of Illinois, Urbana, in 1981, and the Ph.D. degree from Rensselaer Polytechnic Institute, Troy, NY, in 1985, all in electrical engineering. From 1981 to 1983, he was a System Engineer in Fisher Control Company, Marshalltown, IA, where he worked on the coordination control of a pulp and paper plant. From 1985 to 1988, he was a Member of the Technical Staff at the Jet Propulsion Laboratory, Pasadena, CA, where he worked on the modeling and control of large flexible structures and multiple-robot coordination. Since 1988, he has been with the Department of Electrical, Computer, and Systems Engineering with a joint appointment in the Department of Mechanical, Aerospace, and Nuclear Engineering at Rensselaer Polytechnic Institute, where he is currently a Professor. His current research interests are in the area of precision motion control, distributed control, and modeling and control of mechanical and material systems.
Tamer Ba¸sar is with the University of Illinois atUrbana-Champaign (UIUC), where he holds the positions of the Fredric G.and Elizabeth H. Nearing Endowed Professor of Electrical and Computer Engineering, Center for Advanced Study Professor, and Research Professor at the Coordinated Science Laboratory. He received the B.S.E.E. degree from Robert College, Istanbul, in 1969, and the M.S., M.Phil., and Ph.D. degrees from Yale University during the period 1970–1972. Hejoined UIUC in 1981 after holding positions at Harvard University and Marmara Research Institute (Turkey). He has published extensively in systems, control,communications, and dynamic games, and has current research interests in modeling and control of communication networks; control over heterogeneousnetworks; resource allocation, management and pricing in networks; mobile computing; security issues in computer networks; and robustidentification, estimation and control. Dr. Ba¸sar is the Editor-in-Chief of Automatica, Editor of the Birkhäuser Series on Systems and Control, Managing Editor of the Annals of the International Society of Dynamic Games (ISDG),and member of editorial and advisory boards of several international journals in control, wireless networks, and applied mathematics. He hasreceived several awards and recognitions over the years, among which are the Medal of Science of Turkey (1993), Distinguished Member Award (1993), Axel by Outstanding Paper Award (1995), and Bode Lecture Prize (2004) of the IEEE Control Systems Society (CSS), Millennium Medal of IEEE (2000), Tau Beta Pi Drucker Eminent Faculty Award of UIUC (2004); the Outstanding Service Award (2005) and the Giorgio Quazza Medal (2005) of the International Federation of Automatic Control (IFAC), and the Richard E. Bellman Control Heritage Award of the American Automatic Control Council (2006). He is a member of the National Academy of Engineering (of USA), a member of the European Academy of Sciences, a Fellow of IEEE, a Fellow of IFAC, a past president of CSS, and the founding president of ISDG.
