IEEE COMMUNICATIONS LETTERS, VOL. 8, NO. 8, AUGUST 2004
Distributed Joint Rate and Power Control
Game-Theoretic Algorithms for Wireless Data
M. Hayajneh, Student Member, IEEE,
and C. T. Abdallah, Senior Member, IEEE
Abstract—In this letter, we consider two distributed game the-
the path gain from the th transmitter to the th receiver. This
oretic algorithms to jointly solve the problem of optimizing the
gain may represent spreading gain and/or cross correlation be-
transmission rates and transmit powers for future wireless data
tween codes in CDMA systems or any gain that captures the
communication systems. We then establish the existence, unique-
effect of a fading channel.
ness and Pareto optimality of Nash equilibria of both games.
that optimally allocates the transmission rates
Index Terms—Game theory, joint rate and power, Pareto effi-
for all users is given by
RANSMITTERS in multimedia wireless networks may where
is the pricing factor broad-
require different quality of services (QoS) in order to es-
casted by the base station (BS) to all users, and
tablish a communication link with a receiver. Providing flex-
sures the willingness of user to pay) is the utility factor of the
ible transmission rates for each transmitter/receiver pair and ef-
th user locally selected based on the desired transmission rate.
ficient use of the shared radio resources requires joint power and
is a constant selected such that
rate control optimization algorithms. Earlier work in this arena
is the minimum required transmission rate. The first term of
used centralized algorithms (c.f. Due to the difficulty of im-
is chosen to maximize the transmission rate of user , while the
plementing centralized algorithms, and to avoid control signals
second term works as a barrier to prevent the th user's rate from
that cause delays in the system operation, distributed algorithms
, and to fairly allocate the transmission rates.
were proposed. Game theory was shown to be an appropriate
is to prevent the greedy use of the available
tool for finding power control algorithms in and for rate
flow control algorithms in and In particular, the authors
below, allocates the transmit power levels that sup-
in proposed a utility based joint power and rate optimiza-
port the resulting Nash equilibrium rates
tion algorithm, but the resulting Nash equilibrium (NE) point
was Pareto inefficient and to guarantee the uniqueness of NE the
rates of all users were forced to be equal. In this letter, we use
game theory framework for finding a pure distributed algorithms
for the joint
rate and power control optimization problem. To
solve the problem, we propose two, layered, but noncooperative
priced games as follows: The first game
allocates the optimal
transmission rates for all users, then provides the second game
with a vector of constants . The second game
is the effective interference that user
needs to overcome.
uate the optimal transmit power levels that support the resulting
are the vectors of transmission rates and
Nash equilibrium transmission rates of game
transmit powers of all users except for the th user, and
signal-to-interference ratio (SIR) defined by
II. SYSTEM SETUP AND OUR APPROACH
transmitter/receiver pairs (users) in a mobile cel-
lular network. The th transmitter,transmits at a power level
from its convex strategy space
In applications where the spectrum and power are limited re-
to the th receiver and sends data at a rate
sources, it is recommended to use a spectrally and power effi-
. The received power level at the th receiver
cient modulation technique such as M-QAM. An empirical link
from the th transmitter is given by
-QAM of user is given by
Manuscript received January 11, 2004. The associate editor coordinating the
is the target BER
review of this letter and approving it for publication was Prof. S. Pierre. The
is a system constant. In this letter we use the
work of C. T. Abdallah was supported in part by the National Science Founda-
following approximation of (4) at high SIR
tion under NSF-ITR 0312611.
The authors are with the Electrical and Computer Engineering Department,
University of New Mexico, Albuquerque, NM 87131-0001 USA (e-mail:[email protected]
is normalized by the channel bandwidth with units,
Digital Object Identifier 10.1109/LCOMM.2004.833817
nats/s/Hz. A user can change the transmission rate by adapting
1089-7798/04$20.00 2004 IEEE
IEEE COMMUNICATIONS LETTERS, VOL. 8, NO. 8, AUGUST 2004
different modulation formats (e.g., 2-QAM, 4-QAM, …).
B. Non-Cooperative Power Control Game With Pricing
Therefore, the transmission rate of each user belongs to a
To find the maximizing
discrete set, but we assume in this letter that the transmissionrates are continuous for simplicity. In Section III we establishthe existence, uniqueness and optimality of the equilibrium
of both games.
and by substituting for the value of
, the maximizing transmit
III. EXISTENCE OF NASH EQUILIBRIUM
power level is thus given by
A. Non-Cooperative Rate Control Game
With Pricing (NRGP)
The optimization problem of the th user defined in game
The transmit power level
represents the minimal power (i.e.,
is to find the transmission rate
from the strategy space
without waste) required to support the optimal transmission rate
maximizes the utility function defined in (1). To do so, we set
is a strictly concave function, and using the same ar-
, there exists a Nash equilibrium point
. In what follows we prove
The maximizing transmission rate of user ,
the uniqueness of the Nash equilibrium point of game
proposing the best response of user
defined in (2), the best response
of user , given the transmit power levels vector of the other
is the maximum transmit power level in the th
, which means that
user's strategy space
concave function of
is a quasiconcave func-
Then, the uniqueness of the Nash equilibrium operating point
tion optimized on a convex set
, and game theory results
can be proved similarly to game
since the best response
guarantee the existence of a Nash equilibrium point In the
vector of users in
remainder of this section we prove the uniqueness of this Nash
is also a standard function. The following Lemma then guar-
equilibrium point. We first need the following result.
antees Pareto optimality (efficiency) of the equilibrium point
defined in (1), the best response
of both NRGP and NPGP games
of user , given the transmission rates vector of the other users
The Nash equilibrium point
is the maximum allowed transmission rate in the th
is Pareto optimal. Mathemat-
user's strategy space
ically speaking, for
Define the best response function
th user as the best action that user
can take to attain the
component wise. For
maximum pay off given the other users' actions
where this set contains only one point From (7),
We already know from (6) that
unconstrained maximizer of the target function
maximizer is unique. Now, assume that
is not feasible, that is,
, then user will get his/her maximum at
the target function is increasing on the set
is the best response of user
, therefore (10) can be written as
The following theorem, proven in guarantees the unique-
ness of a Nash equilibrium operating point of game
If a power control algorithm with a standard best
response function has a Nash equilibrium point, then this Nashequilibrium point is unique.
Without loss of generality, let
See for the definition of a standard function. Theorem 1
. Then we have the following:
allows us to state the following lemma, whose proof is omitted.
, the best response vector of all users
is a standard vector function. Therefore, by theorem 1, gamehas a unique Nash equilibrium point
HAYAJNEH AND ABDALLAH: GAME-THEORETIC ALGORITHMS FOR WIRELESS DATA
In order to find out how
, we need to find
the first-order derivative of
. One can check easily
for all users, and by this we conclude that
is a Pareto optimal NE point of NRGP game
Normalized equilibrium rates of the game G1() and the normalized
is a Pareto optimal NE point of
, it is enough to
minimum required rates of the users (+) in the upper graph and the equilibrium
is the minimum required transmit power
powers of the game G2() in the lower graph versus the user index with pricingfactor = 10 , utility factors u = 10 , and = 10 , 8 i 2 N .
. By re-writing (9) as:
And from (5), we conclude
The additive-white-gaussian noise
(AWGN) variance was set
It was proven in that both synchronous and asynchronous
run for different values of the minimum transmission rates for
algorithms with standard best response functions converge to
different users. Results show that all users were able to reach
the same point. Therefore, we consider asynchronous power
reasonable transmission rates with low transmit power levels
and rate control algorithms which converge to the unique Nash
resulting from game
as shown in the lower graph of Fig. 1.
rithm, the users update their transmission rates and powers inthe same manner as in Assume user
updates its transmis-
sion rate at time instances in the set
In this letter two joint game-theoretic distributed rate and
power control algorithms for wireless data systems were pro-
posed. We presented target functions which are composed of
be the transmission rates vector picked randomly from the total
the difference between a utility function and a pricing function
to set the rules of the games among the users. We established
Consider the game
given in (1) and gen-
the existence, uniqueness and Pareto optimality (efficiency) of
erate a sequence of transmission rates vectors as follows: (a)
the Nash equilibrium point of both games. All 50 users in the
Set the transmission rate vector at time
studied example were able to attain transmission rates that are
higher than their minimum required transmission rates at very
low transmit power levels.
the transmission rate(c)
stop and declare the Nash equilibrium
transmission rates vector as
 D. O'Neill, D. Julian, and S. Boyd, "Seeking Foschini's genie: Optimal
and provide it to algorithm 2.
rates and powers in wireless networks," IEEE Trans. Veh. Technol.
When Algorithm 1 converges to
, Algorithm 2 below finds
mitted for publication.
the optimal levels
 A. Goldsmith, Wireless Communications
Stanford, CA: Stanford
power level at time instances in
 D. Fudenberg and J. Tirole, Game Theory
Cambridge, MA: MIT
 C. Douligeris and R. Mazumdar, "A game theoretic approach to flow
randomly chosen power vector in
control in an integrated environment with two classes of users," in Proc.
Computer Network Symp.
, Apr. 1988, pp. 214–221.
as given in (2) generates a
 F. Kelly, P. Key, and S. Zachary, "Distributed admission control," IEEE
sequence of power vectors as follows: (a)
Set the power
J. Select. Areas Commun.
, vol. 18, pp. 2617–2628, Dec. 2000.
 R. D. Yates, "A framework for uplink power control in cellular radio
systems," IEEE J. Select. Areas Commun.
, vol. 13, pp. 1341–1347, Sept.
 N. Feng, N. Mandayam, and D. Goodman, "Joint power and rate opti-
mization for wireless data services based on utility functions," in Proc.
stop and declare the Nash equilibrium power
, vol. 1, Mar. 1999, pp. 109–113.
 A. B. MacKenzie and S. B. Wicker, "Game theory in communications:
and go to (b)
Motivation, explanation, and application to power control," in Proc.
, Nov. 2001, pp. 821–826.
 C. U. Saraydar, N. B. Mandayam, and D. J. Goodman, "Efficient power
IV. SIMULATION RESULTS
control via pricing in wireless data networks," IEEE Trans. Commun.
We consider a wireless data system with
vol. 50, pp. 291–303, Feb. 2002.
 A. B. MacKenzie and S. B. Wicker, "Game theory and the design of self-
ceiver/transmitter pairs. The path gains
configuring, adaptive wireless networks," IEEE Commun. Mag.
, vol. 39,
from a uniform distribution on
pp. 126–131, Nov. 2001.
Blackwell Science, LtdOxford, UKMMIMolecular Microbiology0950-382XBlackwell Publishing Ltd, 2004? 2004??Review ArticleThe mycobacterial lipoarabinomannan and related moleculesV. Briken, S. A. Porcelli, G. S. Besra and L. Kremer Molecular Microbiology (2004)
2014 Fall Newsletter Friends of IWIRC NY, In This Edition Fall is here and along with the seasons, things are changing over at IWIRC NY! It is election time, when half of our board will roll off and make way for new members and fresh ideas. While we are sad to see our parting board members go, we are excited to work with what looks to be an impressive field of candidates!