CDMA uplink power control as a noncooperative game.
We present a game-theoretic treatment of distributed power control in CDMA wireless systems. We make use of the conceptual framework of noncooperative game theory to obtain a distributed and market-based control mechanism. Thus, we address not only the power control problem, but also pricing and allocation of a single resource among several users. A cost function is introduced as the difference between the pricing and utility functions, and the existence of a unique Nash equilibrium is established. In addition, two update algorithms, namely, parallel update and random update, are shown to be globally stable under specific conditions. Convergence properties and robustness of each algorithm are also studied through extensive simulations.
Introduction
In wireless communication systems, mobile users respond to the time-varying nature of the channel,
described using short-term and long-term fading phenomena [1], by regulating their transmitter
powers. Specically, in a code division multiple access (CDMA) system, where signals of other
users can be modeled as interfering noise signals, the major goal of this regulation is to achieve
a certain signal to interference (SIR) ratio regardless of channel conditions while minimizing the
interference due to user transmit power level. Hence, there are two major reasons for a user to
exercise power control: the rst one is the limit on the battery energy available to the mobile, and
the second reason is the increase in capacity, which can be achieved by minimizing the interference.
Power control in CDMA systems are in either open-loop or closed-loop form. In open-loop
power control, the mobile regulates its transmitted power inversely proportional to the received
power. In closed-loop power control, on the other hand, commands are transmitted to the mobile
over the downlink to increase or decrease its uplink power [2, pp.182].
Research supported in part by grants NSF ANI 98-13710, NSF INT 98-04950, NSF CCR 00-85917, AFOSR
MURI AF DC 5-36128, and ARMY OSP 35352-6086. All correspondence should be forwarded to: Prof. Tamer
Basar, Coordinated Science Laboratory, University of Illinois, 1308 West Main Street, Urbana, IL 61801-2307 USA.
Coordinated Science Laboratory, University of Illinois, 1308 West Main Street, Urbana, IL 61801 USA.
3 INRIA B.P. 93, 06902 Sophia Antipolis Cedex, France, and CESIMO, Facultad de Ingeneria, Univeridad de Los
Andes, Merida, Venezuela.
A specic proposal to implement distributed power control made by Yates [3] relies on each user
updating its power based on the total received power at the base station. It has been shown in [3]
that the resulting distributed power control algorithm converges under a wide variety of interference
models. Another distributed power control scheme has been introduced in [4], which is adaptive
and uses local measurements of the mean and the variance of the interference. The authors have
shown that this algorithm is convergent provided that a certain condition is satised.
Game theory provides a natural framework for developing pricing mechanisms of direct relevance
to the power control problem in wireless networks. In such networks, the users behave
noncooperatively, i.e., each user attempts to minimize its own cost function (or maximize its utility
in response to the actions of the other users. This makes the use of noncooperative game
theory [5] for uplink power control most appropriate, with the relevant solution concept being the
noncooperative Nash equilibrium. In this approach, a noncooperative network game is dened
where each user attempts to minimize a specic cost function by adjusting his transmission power,
with the remaining users' power levels xed. The main advantage of this approach is that it not
only leads to distributed control as in [3], but also naturally suggests pricing schemes, as we will
see in this paper.
Possible utility functions in a game theoretical framework, and their properties for both voice
and data sources have been investigated in detail in [6], which formulates a class of utility functions
that also account for forward error control, and shows the existence of a Nash equilibrium and the
uniqueness of an optimal response. One interesting feature of this framework is that it provides
utility functions for wireless data transmission, where power control directly aects the capacity of
mobiles' data transmission rates. Reference [6] also proposes a linear pricing scheme in order to
achieve a Pareto improvement in the utilities of mobiles.
In an earlier study [7], Nash equilibria achieved under a pricing scheme have been characterized
by using supermodularity. It has been shown that a noncooperative power control game with a
pricing scheme is superior to one without pricing. One deciency of this game setup, however, is
that it does not guarantee social optimality for the equilibrium points.
Linear and exponential utility functions based on carrier(signal)-to-interference ratio are also
proposed in [8]. The existence of a Nash equilibrium is shown under some assumptions on the
utility functions, and an algorithm for solving the noncooperative power control game is suggested.
In this paper, we propose a power control game similar to the ones in [8, 6]. In the model we
adopt, however, we use a cost function dened as the dierence between a linear pricing scheme
proportional to transmitted power, and a logarithmic, strictly concave utility function based on
SIR of the mobile. Furthermore, the utility function is made user-specic by multiplying it with a
utility parameter re
ecting the individual user preferences. We then rigorously prove the existence
and uniqueness of a Nash equilibrium. We also investigate possible boundary equilibrium solutions,
and hence derive a quantitative criterion for admission control. As in [3], one way of extending
the model is to include certain SIR constraints. As an alternative, we suggest a pricing strategy
to meet the given constraints, and analyze the relation between price, SIR, and user preferences as
re
ected by the utility parameter. Thus, we address not only the power control problem, but also
pricing and allocation of a single resource among several users. Furthermore, we study dierent
pricing strategies, and obtain a distributed and market-based power control mechanism. Finally,
under a su-cient condition we prove the convergence of two algorithms, parallel update (PUA)
and random update (RUA), to the unique Nash equilibrium.
In order to illustrate the convergence, stability and robustness of the update algorithms, we
use extensive simulations using MATLAB. Moreover, we study the eect of the various parameters
of the model, especially dierent pricing schemes. In order for the simulations to capture realistic
scenarios, we introduce feedback delay and modeling disturbances, where the latter is caused by
variations in the number and location of users in the network.
The next section describes the model adopted and the cost function. In Section 3, we prove
the existence and uniqueness of the Nash equilibrium. We present update algorithms for mobiles
in Section 4, whereas Section 5 introduces dierent pricing strategies at the base station. The
simulation results are given in Section 6, which is followed by the concluding remarks of Section 7.
2 The Model and Cost Function
We describe here the simple model adopted in this paper for a single cell CDMA system with up
to M users. The number of users is limited under an admission control scheme that ensures the
minimum necessary SIR for each user in the cell. For the i th user, we dene the cost function J i as
the dierence between the utility function of the user and its pricing function, J . The
utility function, U i , is chosen as a logarithmic function of the i th user's SIR, which we denote by
i . This utility function can be interpreted as being proportional to the Shannon capacity [1, 9] for
user i, if we make the simplifying assumption that the noise plus the interference of all other users
constitute an independent Gaussian noise. This means that this part of the utility is simply linear
in the throughput that can be achieved (or approached) by user i using an appropriate coding, as a
function of its transmission power. This logarithmic function is further weighted by a user-specic
utility parameter, u i > 0, to capture the user's level of \desire" for SIR.
The pricing function denes the instantaneous \price" a user pays for using a specic amount
of power that causes interference in the system. It is a linear function of p i , the power level of the
user. Accordingly, the cost function of the i th user is dened as
denotes the vector of power levels of all users except the i th one, and
i is the SIR
function for user i, given by
Here,
R is the spreading gain of the CDMA system, where W is the chip rate and R is the total
rate; we assume throughout that L > 1. The parameter h j , 0 < h j < 1, is the channel gain from
user j to the base station in the cell, and  2 > 0 is the interference. For notational convenience,
let us denote the i th user's power level received at the base station as y i := h i p i , introduce the
quantity
and further dene a user specic parameter (a i ) for the i th user as
a
3 Existence and Uniqueness of Nash Equilibrium
The i th user's optimization problem is to minimize its cost, given the sum of powers of other users
as received at the base station,
noise. The nonnegativity of the power vector (p i
is an inherent physical constraint of the model. Taking the derivative of the cost function (2.1)
with respect to p i , we obtain the rst-order necessary condition:
In the case of a positive inner solution, (3.1) holds with equality. It is easy to see that the second
derivative is also positive, and hence the inner solution, if it exists, is the unique point minimizing
the cost function. The boundary solution, is the other possible optimal point for the
constrained optimization problem. If the user's cost function, J i (p attains its minimum for
a power value less than zero, p i;min < 0, the optimal solution will be the boundary point. Solving
Equation (3.1) and invoking the positivity constraint p i  0, we obtain the reaction function,  i ,
of the i th user:
[a iL
The reaction function is the optimal response of the user to the varying parameters in the model.
It depends not only on the user-specic parameters, like u i ,  i , and h i , but also on the network
parameter, L, and total power level received at the base station,
Actually (3.2) shows
dependence only on  y i , but adding ( 1
both sides, and dividing both sides by (1 1
can express the response of the i th user as a function of the quantity
. The base station
provides the user with total received power level using the downlink. If the frequency of user
updates is su-ciently high, this can be done incrementally in order to decrease the overhead to the
system. A simplied block diagram of the system is shown in Figure 1.
Similar to the transmission control protocol (TCP) in the Internet [10], there is an inherent
feedback mechanism here, built into the reaction function of the user. In this model, the total
received power at the base station provides the user with information about the \demand" in the
network, which is comparable to congestion in case of the TCP. However, one major dierence is
that here the reaction function itself takes the place of the window based algorithms in the TCP.
In order for the i th mobile to be \active", or p i > 0 the following conditions from (3.2) have to
hold: a i > 0 and
intuitive interpretation for these conditions is the following: If the
Mobile 1
Mobile 2
Mobile M
BS
l
l
l

Figure

1: A simplied block diagram of the system.
price,  i , is set too high for a mobile, the mobile prefers not to transmit at all, depending on its
channel gain and utility parameter, and the spreading gain and interference level.
For any equilibrium solution, the set of xed point equations can be written in matrix form by
exploiting the linearity of (3.2). In case of a boundary solution, the rows and columns corresponding
to users with zero equilibrium power are deleted, and the equation below involves only the users
with positive powers. Hence we have (assuming here that all M users have positive power levels at
hM
hM
where the variable c i is dened as c
. Note that c i > 0 if a i is positive.
Theorem 3.1. In the power game just dened (with M users), let the indexing be done such that
a i < a with the ordering picked arbitrarily if a be the largest integer
~
M for which the following condition is satised:
a ~
~
Then, the power game admits a unique Nash equilibrium (NE), which has the property that users
have zero power levels, p
1. The equilibrium power levels of the rst
users are obtained uniquely from (3.3) with M replaced by M  , and are given by
f L
a
If there is no ~
M for which (3.4) is satised, then the NE solution is again unique, but assigns
zero power level to all M users.
Proof. We rst state and prove the following lemma, which will be useful in the proof of the
theorem.
Lemma 3.2. If condition (3.4) is satised for ~
, it is also satised for all ~
M such that
M .
Proof. Suppose that condition (3.4) holds for ~
then we argue that it also holds for ~
M 1. Substituting in
M for ~
M , we rewrite it as:
Due to the indexing of users, we have a ^
M . Substituting a ^
for a ^
above, we obtain
Hence, (3.4) is satised for ~
M 1. The proof then follows by induction on ~
M .
Returning to the proof of the theorem, we rst show that the matrix A in equation (3.3) is full
rank and hence invertible, and thereby the solution to (3.3), p  , is unique. Then we show that
the solution is strictly positive (i.e. p
only if, condition (3.4) is satised for
~
. Finally, we relax condition and allow for boundary solutions, and conclude the proof by
proving the uniqueness of the boundary solution.
In order for the matrix A in (3.3) to be full rank and hence invertible, there should not exist a
nonzero vector This equation can be written as:
Summing up this set of equations over all users,
The term above is nonzero, and hence the sum
has to be zero. Since the
channel gains are strictly positive, h i > 0 8i, and L > 1, it follows from (3.6) that q
Accordingly, the matrix A is full rank and hence invertible, which leads to a unique solution for
equation (3.3). Simple manipulations lead to (3.5), with M , for this unique solution.
If the NE exists and is strictly positive, then (3.3) has to have a unique positive solution, which
we already know is given by (3.5). Hence, (3.5) has to be positive, which is precisely condition (3.4)
in view of also the indexing of the users. On the other hand, if (3.4) holds for ~
then we
obtain from (3.5) that the equilibrium power level of each user is strictly positive. The existence
and uniqueness of the NE follows from (3.3). We thus conclude that condition (3.4) with ~
is both necessary and su-cient for the existence of a unique positive Nash equilibrium.
To complete the proof for the case M possible boundary solutions need to be investigated
to conclude the uniqueness of the inner Nash equilibrium. We have to show that there cannot be
another NE, with a subset ~
M of ~
users transmitting with positive power, and the remaining
users having zero power level. In this case, the reactive power level of the i th mobile,
M, is given by (3.5) with M
M .
For any i th mobile,
M, in order for the zero power level to be part of a Nash equilibrium,
condition
should fail according to the reaction function (3.2) of the mobile. Summing up the equilibrium
power levels as received by the base station of ~
users with positive power levels (from (3.5) with
M) results inL
a j (3.8)
Substituting in (3.7) the expression (3.8) for
a
On the other hand, from Lemma 3.2, and (3.4), we have for any i th user in the indexed set
1g the following
a
~
Also, from the indexing of the users it follows that
Using this in (3.10), we see
that inequality (3.9) is satised for any i th user
regardless of the choice of the
subset ~
M. We note that there exists at least one user belonging to the set
1g, but not
the subset ~
M. Thus, the power of that mobile must be positive, and hence the boundary solution
cannot be a Nash equilibrium. As this argument is valid for any subset ~
M, all boundary solutions
fail similarly for being an equilibrium, including the trivial solution, the origin. We thus conclude
that the inner Nash equilibrium is unique. This completes the proof for the case M
If M  < M in condition (3.4), then the equilibrium (whenever it exists) will clearly be a
boundary point. If condition (3.4) fails for users M  users are indexed as described
in Theorem 3.1, then these users use zero power in the equilibrium. Hence, for any i th user among
should fail. It was shown above that equation (3.8) holds with
~
As condition (3.4) does not hold for the i th user, equation (3.9), and hence (3.7) fails.
Thus, from (3.2) power level of the i th user is zero, 0, at the equilibrium. As this holds for
any i
Mg, the equilibrium power levels for these users are zero.
We now argue that the given boundary solution is unique. One possibility is the existence of
an i th user, where 1  i  M  , to have zero power. This cannot be a Nash equilibrium, as it
follows from (3.8) and (3.9) with ~
Another possibility is the existence of an i th user,
transmitting with positive power level. This cannot be an equilibrium, either,
as it was shown above that (3.7) fails for such an i th user, and directly from the
reaction function (3.2). All possible boundary solutions can be captured by various combinations
of these two cases. Consider the case where a subset of users among use zero power
whereas some of the users among M  use positive power levels. Since for the subset of
users with positive power levels among M  condition (3.4) does not hold, they cannot
be in equilibrium following an argument similar to the one above. Otherwise, as condition (3.4)
holds for the subset of users with zero power level among they cannot be in equilibrium,
either. We conclude, therefore, that the boundary solution is unique.
Finally, in the case where no M  exists satisfying condition (3.4), all users fail to satisfy (3.4),
and the only solution is the trivial one, p
4 Update Schemes for Mobiles, and Stability
In this section, we investigate the stability of the Nash equilibrium in the given model under two
relevant asynchronous update schemes: parallel and random update. We establish a su-cient
condition which guarantees the convergence to the unique equilibrium point for both algorithms.
4.1 Parallel Update Algorithm (PUA)
In the PUA, users optimize their power levels at each iteration (in discrete time intervals) using the
reaction function (3.2). If the time intervals are chosen to be longer than twice the maximum delay
in the transmission of power level information, it is possible to model the system as a delay-free
one. In a system with delays, there are subsets of users, updating their power levels given the
delayed information.
The algorithm is given by
[a iL
y (n)
or equivalently by
y (n)
whose global stability is established in the next theorem. This means that PUA converges to the
unique Nash equilibrium of Theorem 3.1 given as
[a iL
from any feasible initial point, p i  0 8i.
Theorem 4.1. PUA is globally stable, and converges to the unique equilibrium solution from any
feasible starting point if the following condition is satised:
Proof. Let us dene the distance between the i th user's power level received in the base station at
any time (n) and received equilibrium power level as 4y (n)
. We consider rst the case
when y
for an arbitrary i th user. Then, given the received power levels of all users except the
th one at time n,
we have the following from (4.1) and (4.2):
j4y (n+1)
Thus, we obtain
j4y (n+1)
j4y (n)
Next, we consider the case when the received equilibrium power level for an arbitrary i th user
is zero, y
Then, from (4.1) and (4.2) it follows that
j4y (n+1)
Thus, the inequality (4.4) holds for any i th user at any time instant n for both cases. We now show
that (4.3) is a su-cient condition for the right-hand side of (4.4) to be a contraction mapping. Let
denote the l 1 -norm of the vector (4y 1 4y
Then, from (4.4),
jj4y
j4y (n)
Hence, (4.4) is a contraction mapping under condition (4.3), which leads to the stability and global
convergence of the PUA (4.1).
We nally note that using an initial admission control mechanism and user dropping scheme,
which limits the number, M , of users in the cell, this condition can easily be satised for a given
L. Thus, the stability and convergence of the algorithm follows.
4.2 Random Update Algorithm (RUA)
Random update scheme is a stochastic modication of PUA. The users optimize their power levels
in discrete time intervals and innitely often, with a predened probability 0 <  i < 1. Thus, at
each iteration a set of randomly picked users among the M update their power levels. The system
with delay is also similar to PUA. The users make decisions based on delayed information at the
updates, if the round trip delay is longer than the discrete time interval.
The RUA algorithm is described by
y (n)
where  i was dened in (4.1). We already know from the proof of Theorem 4.1 that if user i
updates, then (4.4) holds. Hence, for each
Ej4y (n+1)
user i updates at time ng i
+Efj4y (n)
user i does not update at time ng(1  i )
Ej4y (n)
Using again the l 1 -norm dened in (4.5), but with j4y i j replaced by Ej4y i j (that is, jj4yjj 1 :=
following steps similar to the ones of PUA, we obtain
Ej4y (n+1)
which leads to
jj4y
where   < 1 and  > 0 are the upper and lower limits for the update probability of the i th user
respectively,  <  i <
. Therefore,
is a su-cient condition for the right-hand side of (4.6) to be a contraction mapping, and for the
stability and convergence of RUA in norm. We also note that when all users have the same update
probability, condition simplies to (M 1)=L < 1, same su-cient condition (4.3)
as the one for PUA. We show next a stronger result, almost sure (a.s.) convergence of RUA, under
condition (4.7). By the Markov inequality and using the denition of the l 1 -norm, we haveX
Ej4y (n)
"X
where P (:) denotes the underlying probability measure. Since Ej4y (n)
contracting sequence
with respect to the l 1 -norm as shown,
1. Using this in (4.8), it follows thatX
and thus follows,X
where K is a constant (actually, Hence, the increasing sequence of partial sums
bounded above by K
"(1 ) . Thus, it converges for every " > 0. From the
Lemma [11, 12], it then follows that
Hence, RUA converges also a.s. under condition (4.7).
4.3 Comparison of PUA and RUA
One important feature of PUA is that it ascribes a myopic behavior to the users, that is they optimize
their power levels based on instantaneous costs and parameters, ignoring future implications
of their actions. This behavior of users is realistic for the analyzed wireless network as it may not
be feasible or even possible for a mobile to estimate future values of total interference in the cell or
future variations in its own channel gain.
In the case of RUA, the users are again myopic and update their power levels based on instantaneous
parameters. But, not all of them act at every iteration; whether a particular user responds
or not is determined probabilistically. In the limiting case when all update probabilities,  i , are
equal to 1, RUA is the same as PUA. An advantage of RUA, however, is that through it one can
investigate the convergence of the proposed scheme when there are random delays in the system.
Such delays may be due to dierences in the processing or propagation times.
As we will see in the simulations included in Section 6, in a delay-free system if all the users
have the same initial power level, then RUA performs better than PUA. This is due to the myopic
behavior of users, as well as the inherent randomization in the case of RUA. On the other hand,
the opposite is true for a system with delay as variations in delay provide su-cient randomization,
and PUA becomes more advantageous due to frequent updates. More detailed observations on the
convergence of both algorithms can be found in Section 6 for both delay-free and delayed cases.
Pricing Strategies at the Base Station
In a noncooperative network, pricing is an important design tool as it creates an incentive for the
users to adjust their strategies, in this case power levels, in line with the goals of the network. In
the CDMA system we are studying here, the price per unit power of the i th user,  i , is determined
by the base station in a manner to be discussed shortly. We introduce a pricing scheme where the
price charged to each user is proportional to the received power from the user at the base station.
Thus, the price is proportional to the channel gain of the i th user,
The inner Nash solution by itself does not guarantee that the users with nonzero power levels
will meet the minimum SIR requirement to establish a connection to the base station. Achieving
the necessary SIR level is obviously crucial to the successful operation of the system. Furthermore,
one has to recognize that dierent communication applications in wireless systems leads to dierent
types of users and SIR requirements in addition to the minimum SIR level.
In view of these considerations, we will consider in this section two dierent pricing schemes:
(i) A centralized pricing scheme: Users are divided into classes, with all users belonging to a
particular class having the same utility function parameter (u i ). Further, all users within a class
have the same SIR requirement. The role of the base station is to set prices for these dierent
classes such that, under the resulting Nash equilibrium, the SIR targets of the users are met.
(ii) Decentralized, market-based pricing: The base station sets a single price for all users, and
the users choose their willingness to pay parameter, (u i ), to satisfy their QoS requirements. As
compared to the centralized scheme, this one is more
exible, and allows users to compete for the
system resources by adjusting their individual u i 's.
5.1 Centralized Pricing Schemes and Admission Control
First, we consider the symmetric-user case where every mobile has the same SIR requirement, and
for convenience we let u 1. It is possible to nd a simple pricing strategy by picking the price
directly proportional to the channel gain,  the pricing factor, k, is user independent.
The parameter k is a function of the number of users and the desired SIR level.
Notice that this approach is equivalent to centralized power control as the prices are adjusted
by the base station in such a way that the mobiles use the power levels determined by the unique
Nash equilibrium as a result of their individual optimization. Moreover, the base station can set
the prices such that the SIR requirements of the users are satised. A precise result covering this
case is now captured by the following theorem.
Theorem 5.1. Assume that the users are symmetric in their utilities, u they have the
same minimum SIR requirement,
, and are charged proportional to their channel gain,
Then the maximum number of users, M  , the system can accomodate is bounded by
Moreover, the pricing parameter k under which M  M  users achieve the SIR level
is
Proof. Solving for the user-independent y i from (3.2), we have
Combining this result and the SIR function in (2.2), and taking the minimum SIR,
, as input,
we obtain (5.2) for a single class of users in a cell. To ensure that (5.2) is well dened, we require
the condition in (5.1). Based on (5.2), condition (5.1) satises (3.4). Thus, both the necessary and
su-cient conditions for a unique positive Nash equilibrium are satised if (5.1) holds. Then, the
unique solution is strictly positive according to Theorem 3.1, and all M  M  users attain the
desired SIR level,
.
We note that if M > M  , all users fall below the desired SIR level (
due to the symmetry.
In this case, dropping some of the users from the system in order to decrease the number of users
M below the threshold (M  ) would lead to a viable solution.
Next, we consider the case where the network may provide multiple service levels and multiple
pricing schemes. For this more general case, it is convenient to split the mobiles in a cell into
multiple groups according to their need for bandwidth, or in our context, their desired SIR levels,
where the users within each group are symmetric. Using a multiple pricing scheme, a solution
capturing multiple user groups can be obtained straightforwardly.
5.2 Market-Based Scheme
It is natural to think of each user within a cell having dierent SIR requirements, which can be
quantied with the user-specic utility parameter u. The base station can implement a natural
pricing strategy by formulating the pricing parameter directly proportional to the channel gain,
However, it is impossible in this case for the base station to calculate the parameter
k, as the user preferences are unknown to the base station. Hence, after the base station sets an
appropriate value for price (k), each user dynamically updates its power level by minimizing its
cost under parallel update (PUA) or random update (RUA) algorithms. As a result, a distributed
and market-based power control scheme is obtained.
Due to the interference in the CDMA system, each user aects others. Hence, the i th mobile
can adjust its utility parameter, u i , dynamically according to its minimum SIR level,
given the
interference at the base station. From (3.2) and (2.2), it follows that
The parameter u i is bounded below by the total received power at the base station. This can be
interpreted as follows: If a mobile is in a cell where the interference is low, the mobile can achieve
the desired SIR level with a low power, hence paying a lower price. However, in a situation where
many users compete for the SIR, the mobile has to use more power, and pay a higher price to reach
the same SIR level. In the latter case, the user's willingness to spend more can be justied with a
higher u i based on (3.2).
We note that, together with the utility function, the utility parameter u i quanties the user's
desire for the SIR. The base station can limit aggressive requests for SIR even in the case when a
user pays for its excessive usage of power, by setting an upper-limit, y max , for the received power
of the i th user at the base station: y i  y max . Hence, unresponsive users can be punished by the
base station in order to preserve network resources. From (3.2), we can obtain an upper-bound
on the value of u i . Furthermore, this bound depends only on user-independent parameters, such
as the upper limit of the total received power at the based station, maximum number of mobiles,
and the spreading gain, L, if proportional pricing is used:
When this bound is combined with a simple admission control scheme, limiting the number of
mobiles to M max , the base station can provide guarantees for a minimum SIR level
A tradeo is observed in the choice of the design parameters
versus M max . If the network
wants to provide guarantees for a high SIR level, then it has to make a sacrice by limiting the
number of users. In addition, users may implement a distributed admission scheme according to
their budget constraints and desired SIR levels. If the price necessary to reach a SIR level exceeds
the budget, B i , of the user, that is k
then the user may simply choose not to
transmit at all.
6 Simulation Studies
The proposed power control scheme has been simulated numerically using MATLAB. Here, we
rst investigate dierent pricing schemes for symmetric mobiles in the xed-utility case. Then, we
analyze the robustness of the system under varying parameters such as noise, the number of users,
and channel gains. Furthermore, the rate of convergence of both update schemes, PUA and RUA,
are studied both in the delay-free and delayed cases. Finally, we investigate a system consisting
of users with various utility parameters. All results of the simulations are valid for both update
schemes, PUA and RUA, where the only dierence between the two is the convergence rate.
Simulation parameters are chosen as follows, unless otherwise stated. The spreading gain
128 is chosen in accordance with IS-95 standard [1]. Noise factor is  the stopping
criterion or distance to equilibrium is given by . The users are assumed to be located
randomly in the cell where the distance of the i th user to the base station, d i , is uniformly distributed
between d 100. The channel gains of users are determined by a simple large-scale
path loss formula the path loss exponent is chosen as 2 corresponding to open air
path loss. Under the xed-utility case, users have the same utility parameter, 8i. The initial
condition for simulations is 8i, an estimated value for establishing initial communication
between the mobile and the base station. In the simulations, a discrete time scale is used. The
delay-free case is characterized by a time span that is long enough for perfect information
ow to
users. Subsequently, delay is introduced to the system to make the setting more realistic.
6.1 Eect of the Pricing Parameters
In the rst simulation, proportional and xed pricing schemes are compared. For simplicity, we
rst choose the users being symmetric under both xed pricing,  proportional pricing,
. For illustrative purposes the number of users is chosen small,
In

Figure

2, the equilibrium power and the SIR values of each user can be seen under both
pricing schemes. In the top graph, power values of the users with dierent channel gains are almost
the same under xed pricing. Hence, the users with lower channel gains achieve lower SIR values. In
contrast, all users meet a minimum SIR level under proportional pricing, regardless of their channel
gain. An intuitive explanation is that under proportional pricing the distant users are allowed to
use more power to attain the necessary SIR level. We also note that, proportional pricing is 'fair'
in the sense that the users are not aected by their distance to the base station.
Convergence of users' power levels to their equilibrium values is demonstrated in Figure 3 (a)
under PUA, and Figure 3 (b) under RUA with update probability being 0:6. In both cases there
are 10 users and
The eect of pricing is investigated in the next simulation for a single class of users by varying the
pricing parameter, k, under proportional pricing. Equivalently, this simulation can be interpreted
Power Curves of N=20 users
-2020SIR Values (in dB)
Proportional Pricing
Fixed Pricing
Channel Gains
Users

Figure

2: Comparison of power and SIR nal values of the mobiles for the xed and proportional
pricing schemes.
Power Values vs. Number of Iterations under PUA (L=20,N=10)
Iterations
Power
level
Power Values vs. Number of Iterations under RUA (pi=0.6,L=20,N=10)
Iterations
Power
level
(a) (b)

Figure

3: Convergence of users' individual power levels to the equilibrium values versus number of
iterations under (a) PUA, and (b) RUA with
as varying the utility parameter, u. Both parameters play a crucial role in the system by aecting
the overall power and SIR levels. From (3.2), the eect of u i on the system is inversely proportional
to k i . In Figure 4 it can be observed that a gradual increase in k from 1 to 4, i.e. an increase in
price, aects the system in a such a way that both power and SIR values decrease. Since, with an
increase in the price, the users decrease their powers to the same extent leading to lower SIR values
given a constant noise level. Equivalently, a decrease in u, the users' level of request for SIR, gives
the same result. Furthermore, the observations match theoretical calculations for the single class
case in accordance with (5.2).
(in dB) of Users versus Pricing (or 1/Utility) Parameter
Power Levels of Usersversus Pricing (or 1/Utility) Parameter
Users

Figure

4: Eect of the pricing parameter, k, (utility parameter 1=u) on the SIR and the power
levels of users.
6.2 Convergence Rate and Robustness of Algorithms
6.2.1 Simulations without Delay
The convergence rate of the two update schemes is of great importance, as it has a direct eect on
the robustness of the system. We have simulated PUA and RUA for dierent numbers of symmetric
users under a single pricing scheme. In Figure 5, the number of iterations to the equilibrium point
is shown for dierent probability values of RUA and also for PUA (which corresponds to RUA
with the update probability equal to one). As the number of users increase the optimal update
probability decreases. This result is in accordance with the one in [13] where it is shown that in a
quadratic system without delay, an approximate value for the optimal update probability is 2, as
number of users goes to innity. On the other hand, if number of users is much smaller than the
spreading gain, M  L, then PUA is superior to RUA.
02004000204060Number of Users
RUA for different Nbr. of users and Update Prob.
Update Probability
Number
of
Iterations

Figure

5: Convergence rate for dierent update probabilities and increasing numbers of users.
Next, we investigate the robustness of the system in the delay-free case. First, we analyze it
under increasing noise,  2 . The background noise is increased step by step up to 100% of its initial
value. Accordingly, the base station allows users to increase their powers by decreasing the prices
by the same percentage in the xed-utility case. The simulation is repeated with users
under a proportional pricing scheme. We observe in Figure 6 (a) that the power values increase in
response to the increasing noise to keep the initial SIR constant. Similarly, we increase the number
of mobiles in the system threefold in Figure 6 (b). It has the same eect as increasing the noise due
to the nature of CDMA. Again by adjusting the prices accordingly, all users keep their SIR levels.
Same results are obtained equivalently under the market-based pricing scheme, where users adjust
their utility parameter, u, dynamically while the pricing parameter determined by the base station
is kept constant. As a conclusion, these observations conrm the robustness of the proposed power
control scheme.
Finally, we simulate the system in a realistic setting under a single pricing scheme: The number
of users, taken as initial value, is modeled as a Markov chain. Arrival of new mobiles
is chosen to be Poisson with an average of 2 new users per time interval. Call durations are
exponentially distributed with an average of 20 time intervals. We observe the average percentage
dierence between the theoretical equilibrium and the current operating point of the system in
terms of power values of users for some period of time. In the simulation, PUA is chosen as the
update algorithm. The initial condition is the equilibrium point for users. The simulated system
operates within 1% range of the equilibrium points, and the results are very similar to those of in

Figure

7.
Heretofore, robustness of the system was investigated for static mobiles. The movements of the
Robustness under varying Noise
Power
Values
Users
Values
Robustness under varying number of Users
Power
Values
020Users
User Number in System
Values
(a) (b)

Figure

Power and SIR nal values for increasing noise (a) and numbers of users (b).
users within the cell result in varying channel gains. In the next simulation, the locations, hence,
channel gains of users are varied randomly. The movement of i th user is modelled after a random
walk where a random value is added to the distance of the user to the base station d i at each time
instant. Hence, we obtain d uniformly distributed.
Furthermore, the setting used in this simulation is the same as previous one. From Figure 7, the
system again operates within 1% distance to equilibrium.
6.2.2 Simulations with Delay
We introduce the delay factor into the system in the following way: users are divided into d equal size
groups, and each group has an increasing number of units of delay. First, the convergence rates of
the two update schemes are compared and contrasted under delay-free and delayed conditions. The
update probability of RUA is chosen as 0:66 which corresponds to the optimal update probability
for a large number of users. In the delay-free case RUA outperforms PUA as the number of users
increases. In the delayed case, however, PUA is always superior to RUA.
Then, the simulation investigating the convergence rate of RUA for various update probabilities
is repeated in the delayed case. The result shown in Figure 8 is dierent from the previous one in

Figure

5. Here, PUA converges faster than RUA for any number of users verifying previous results.
Finally, a market-based pricing scheme with proportional pricing at the base station,
investigated. There are two groups of users, which are symmetric within themselves. Users in each
group have dierent utility parameters, u. The group with higher u is labeled as the \priority"
user group, while the other one is called the \regular" user group. In order to observe the eect
of varying number of users on the SIR levels, we let a sample user from each group make a long
enough call. At the same time, the number of users in each group and channel gains of the users
are varied similar to those in previous robustness simulations to create realistic disturbances in
the system. For simplicity, the values of the utility parameters are kept constant throughout the
Percentage Distance to Equilibrium per User vs Time
200204060Number of Users vs Time

Figure

7: Average percentage distance to the equilibrium point vs. time. Channel gains, h i , are
varied based on random movements of users.
020040010305070Number of Users
RUA for different Nbr. of users and Update Prob. (with delay)
Update Probability
Number
of
Iterations

Figure

8: Convergence rate for dierent update probabilities and increasing numbers of users (with
delay).
SIR of two Selected Users vs Time
Received Power (=Price) of Users
h*P Regular User
Priority User
2003050Number
of
Users
Time

Figure

9: SIR and power levels at the base station (or prices) of two selected users from priority
and regular user groups versus time.
simulation. In Figure 9, it is observed that a priority user always obtains a higher SIR than a
regular user. Another observation is that priority users use a higher power level, and therefore pay
more than regular users, as expected. The
uctuation in the power levels is due to the varying
number of users, and varying total demand for SIR in the system.
7 Conclusion
In this paper, we have developed a mathematical model within the framework of noncooperative
game theory, and have obtained distributed, asynchronous control mechanisms for the uplink power
control problem in a single cell CDMA wireless network. Existence of a unique Nash equilibrium
has been proven, and convergence properties of parallel and random update schemes have been
investigated analytically and numerically. Moreover, conditions for the stability of the unique
equilibrium point under the update algorithms have been obtained and analyzed accordingly.
We have shown that the unique Nash equilibrium has the property that, depending on the
parameter values, only a subset of the total number of mobiles are active. Some of the users are
dropped from the system as a result of the power optimization. By dening a utility function and a
utility parameter, user requests for SIR were modeled dynamically. Furthermore, the relationship
between the SIR level of the users and the pricing has been investigated for two dierent pricing
schemes for the xed and varying utility cases. It has been shown both analytically and through
simulations that choosing an appropriate pricing strategy guarantees meeting the minimum desired
SIR levels for the active users in the xed-utility case. In addition, the principles for an admission
scheme have been investigated under the market-based scheme.
The results obtained indicate that the proposed framework provides a satisfactory decentralized
and market-based solution. The algorithms in this model are practically implementable, as
the only information a user requires to update its power other than own preferences and xed parameters
is the total received power level from the base station. This information may be conveyed
incrementally to reduce the overhead in the case of frequent updates.
Although a specic cost structure is chosen in this paper, most of the results may be extended
to more general cost functions. Another possible extension to this work is to a multiple cells model,
where the eect of neighboring cells are taken into account. A further topic of interest is the
development of the counterparts of the results in the case of multiple base stations, which brings
up the challenging issue of hando.



--R

Principles and Practice
CDMA Principles of Spread Spectrum Communication







Computer Networks: A system approach
New York
Probability and Measure

--TR
CDMA
Non-cooperative uplink power control in cellular radio systems
Computer networks
Communications

--CTR
Patrick Maill , Bruno Tuffin, The Progressive Second Price Mechanism in a Stochastic Environment, Netnomics, v.5 n.2, p.119-147, November
Haitao Lin , Mainak Chatterjee , Sajal K. Das , Kalyan Basu, ARC: an integrated admission and rate control framework for CDMA data networks based on non-cooperative games, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA
Haitao Lin , Mainak Chatterjee , Sajal K. Das , Kalyan Basu, ARC: An Integrated Admission and Rate Control Framework for Competitive Wireless CDMA Data Networks Using Noncooperative Games, IEEE Transactions on Mobile Computing, v.4 n.3, p.243-258, May 2005
A. Siris, Resource Control for Hybrid Code and Time Division Scheduling Wireless Systems, Wireless Personal Communications: An International Journal, v.40 n.2, p.171-184, January   2007
Jianwei Huang , Randall A. Berry , Michael L. Honig, Auction-based spectrum sharing, Mobile Networks and Applications, v.11 n.3, p.405-418, June 2006
Sarah Koskie , Zoran Gajic, A Nash game algorithm for SIR-based power control in 3G wireless CDMA networks, IEEE/ACM Transactions on Networking (TON), v.13 n.5, p.1017-1026, October 2005
Altman , T. Boulogne , R. El-Azouzi , T. Jimnez , L. Wynter, A survey on networking games in telecommunications, Computers and Operations Research, v.33 n.2, p.286-311, February 2006
game theory;CDMA;power control;pricing;resource allocation