Energy Optimal Control for Time Varying Wireless Networks Notes | EduRev

: Energy Optimal Control for Time Varying Wireless Networks Notes | EduRev

 Page 1


IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 52, NO. 7, JULY 2006 1
Energy Optimal Control for Time Varying
Wireless Networks
Michael J. Neely
Abstract—We develop a dynamic control strategy for min-
imizing energy expenditure in a time varying wireless network
withadaptivetransmissionrates.Thealgorithmoperateswithout
knowledgeoftraf?cratesorchannelstatistics,andyieldsaverage
power that is arbitrarily close to the minimum possible value
achieved by an algorithm optimized with complete knowledge of
futureevents.Proximitytothisoptimalsolutionisshowntobein-
versely proportional to network delay. We then present a similar
algorithm that solves the related problem of maximizing network
throughput subject to peak and average power constraints. The
techniquesusedinthispaperarenovelandestablishafoundation
for stochastic network optimization.
Index Terms—Stochastic Optimization, Queueing Analysis,
Ad-Hoc Networks, Distributed Algorithms, Mobile Networks
I. INTRODUCTION
Wirelesssystemsoperateovertimevaryingchannelsthatare
in?uenced by random environmental conditions, wireless fad-
ing, and power allocation decisions. To improve performance
and meet the ever increasing demand for high throughput
and low delay, modern wireless devices are designed with
channel monitoring capabilities and rate adaptive technology.
Such technology is currently being implemented for cellular
communication with High Data Rate (HDR) services [3], and
the ability to measure and react to channel information is
expected to improve signi?cantly.
1
It is of central importance
to develop control strategies that take maximum advantage of
this information to improve network performance and energy
ef?ciency.
In this paper, we develop throughput optimal control strate-
gies that conform to peak power constraints while minimizing
average power expenditure. This design goal is crucial in
all modern wireless scenarios, regardless of whether trans-
missions take place at a basestation, a hand-held unit, or
at a node within an ad-hoc sensor network. Indeed, peak
powerconstraintsareimportantinsystemswith?xedhardware
saturation levels or external environment regulations, while
average power levels are important to extend network lifetime
in systems with limited energy resources.
Here, we consider an ad-hoc network with N nodes and
L wireless links, as shown in Fig. 1. We assume a slotted
structure with slots equal to 1 time unit. Packets randomly
arrive to the network every timeslot and must be delivered to
their destinations, perhaps by routing over multi-hop paths.
Michael J. Neely is with the Department of Electrical Engineering, Uni-
versity of Southern California, Los Angeles, CA 90089 USA (email: mjneely
AT usc.edu, web: http://www-rcf.usc.edu/~mjneely).
This work was presented in part at the IEEE INFOCOM conference, March
2005, and at the USC CSI Research Review, March 2004.
1
Indeed, it is claimed in [4] that channel measurements can be obtained
almost as often as the symbol rate of the link in certain local area wireless
networks.
µ(p)
S = {Excellent}
S = {Good}
S = {Average}
S = {Bad}
S = {Zero}
power p
3
N
2
0
1
4
Fig. 1. A cell-partitioned wireless network, and an example set of rate-power
curves for 5 different channel states.
The transmission rates of each data link are determined every
timeslot by link channel conditions and network power allo-
cation decisions according to an L-dimensional rate function
~ µ(
~
P(t),
~
S(t)), where
~
P(t) is a vector of power allocations
and
~
S(t) is a vector of parameters describing the current
channel conditions. For most of this paper, we assume that all
nodes maintain the same locations relative to one another for
the duration of the network operation. Although the network
topology remains ?xed in this scenario, link conditions may
vary dramatically due to environmental effects, local mobility,
or wireless fading. Extensions to networks with arbitrary
mobility patterns are developed in Section VI.
Powervectorsarerestrictedtoacompactset?ofacceptable
power allocations, so that
~
P(t) ? ? for all t. The set ?
includes the peak power constraints for each node together
with any additional constraints the network might impose on
instantaneous transmissions. All of our results are presented
for general power sets ? and general rate functions ~ µ(
~
P,
~
S).
An example of concave rate-power curves for one data link
with a discrete set of possible channel states is shown in Fig.
1. Such curves might also depend on the signal to interference
ratio at the intended receiver, so thatµ
l
(
~
P,
~
S) for a given link
l is determined by the full vector of power allocations and
channelstates[22][12][23].However,tosimplifythemultiple
access control layer while capturing the geographic structure
and interference properties of ad-hoc networks, we focus our
implementation examples on a cell partitioned network model.
Under this model, the network region is divided into cells,
each containing a distinct set of nodes. Speci?cally, we de?ne
cell(n) as the cell of each node n?{1,...,N}, and de?ne
tran(l) and rec(l) as the transmitting and receiving nodes
associated with a given wireless link l ? {1,...,L}. We
assume that each cell can support at most one active link
transmission per timeslot, and that nodes can transmit only
to other nodes in the same cell or in adjacent cells. That is,
the feasible power set ? includes the constraint that if P
l
> 0
for some link l, then P
˜
l
= 0 for all links
˜
l 6= l such that
Page 2


IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 52, NO. 7, JULY 2006 1
Energy Optimal Control for Time Varying
Wireless Networks
Michael J. Neely
Abstract—We develop a dynamic control strategy for min-
imizing energy expenditure in a time varying wireless network
withadaptivetransmissionrates.Thealgorithmoperateswithout
knowledgeoftraf?cratesorchannelstatistics,andyieldsaverage
power that is arbitrarily close to the minimum possible value
achieved by an algorithm optimized with complete knowledge of
futureevents.Proximitytothisoptimalsolutionisshowntobein-
versely proportional to network delay. We then present a similar
algorithm that solves the related problem of maximizing network
throughput subject to peak and average power constraints. The
techniquesusedinthispaperarenovelandestablishafoundation
for stochastic network optimization.
Index Terms—Stochastic Optimization, Queueing Analysis,
Ad-Hoc Networks, Distributed Algorithms, Mobile Networks
I. INTRODUCTION
Wirelesssystemsoperateovertimevaryingchannelsthatare
in?uenced by random environmental conditions, wireless fad-
ing, and power allocation decisions. To improve performance
and meet the ever increasing demand for high throughput
and low delay, modern wireless devices are designed with
channel monitoring capabilities and rate adaptive technology.
Such technology is currently being implemented for cellular
communication with High Data Rate (HDR) services [3], and
the ability to measure and react to channel information is
expected to improve signi?cantly.
1
It is of central importance
to develop control strategies that take maximum advantage of
this information to improve network performance and energy
ef?ciency.
In this paper, we develop throughput optimal control strate-
gies that conform to peak power constraints while minimizing
average power expenditure. This design goal is crucial in
all modern wireless scenarios, regardless of whether trans-
missions take place at a basestation, a hand-held unit, or
at a node within an ad-hoc sensor network. Indeed, peak
powerconstraintsareimportantinsystemswith?xedhardware
saturation levels or external environment regulations, while
average power levels are important to extend network lifetime
in systems with limited energy resources.
Here, we consider an ad-hoc network with N nodes and
L wireless links, as shown in Fig. 1. We assume a slotted
structure with slots equal to 1 time unit. Packets randomly
arrive to the network every timeslot and must be delivered to
their destinations, perhaps by routing over multi-hop paths.
Michael J. Neely is with the Department of Electrical Engineering, Uni-
versity of Southern California, Los Angeles, CA 90089 USA (email: mjneely
AT usc.edu, web: http://www-rcf.usc.edu/~mjneely).
This work was presented in part at the IEEE INFOCOM conference, March
2005, and at the USC CSI Research Review, March 2004.
1
Indeed, it is claimed in [4] that channel measurements can be obtained
almost as often as the symbol rate of the link in certain local area wireless
networks.
µ(p)
S = {Excellent}
S = {Good}
S = {Average}
S = {Bad}
S = {Zero}
power p
3
N
2
0
1
4
Fig. 1. A cell-partitioned wireless network, and an example set of rate-power
curves for 5 different channel states.
The transmission rates of each data link are determined every
timeslot by link channel conditions and network power allo-
cation decisions according to an L-dimensional rate function
~ µ(
~
P(t),
~
S(t)), where
~
P(t) is a vector of power allocations
and
~
S(t) is a vector of parameters describing the current
channel conditions. For most of this paper, we assume that all
nodes maintain the same locations relative to one another for
the duration of the network operation. Although the network
topology remains ?xed in this scenario, link conditions may
vary dramatically due to environmental effects, local mobility,
or wireless fading. Extensions to networks with arbitrary
mobility patterns are developed in Section VI.
Powervectorsarerestrictedtoacompactset?ofacceptable
power allocations, so that
~
P(t) ? ? for all t. The set ?
includes the peak power constraints for each node together
with any additional constraints the network might impose on
instantaneous transmissions. All of our results are presented
for general power sets ? and general rate functions ~ µ(
~
P,
~
S).
An example of concave rate-power curves for one data link
with a discrete set of possible channel states is shown in Fig.
1. Such curves might also depend on the signal to interference
ratio at the intended receiver, so thatµ
l
(
~
P,
~
S) for a given link
l is determined by the full vector of power allocations and
channelstates[22][12][23].However,tosimplifythemultiple
access control layer while capturing the geographic structure
and interference properties of ad-hoc networks, we focus our
implementation examples on a cell partitioned network model.
Under this model, the network region is divided into cells,
each containing a distinct set of nodes. Speci?cally, we de?ne
cell(n) as the cell of each node n?{1,...,N}, and de?ne
tran(l) and rec(l) as the transmitting and receiving nodes
associated with a given wireless link l ? {1,...,L}. We
assume that each cell can support at most one active link
transmission per timeslot, and that nodes can transmit only
to other nodes in the same cell or in adjacent cells. That is,
the feasible power set ? includes the constraint that if P
l
> 0
for some link l, then P
˜
l
= 0 for all links
˜
l 6= l such that
IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 52, NO. 7, JULY 2006 2
cell(tran(
˜
l)) = cell(tran(l)). We further assume that the
transmission rate of each link depends only on the channel
state and the power allocated to that link, so that ~ µ(
~
P,
~
S) =
(µ
1
(P
1
,S
1
),...,µ
L
(P
L
,S
L
)). This structure arises if nodes
in neighboring cells transmit over orthogonal frequency bands.
Inthisway,ifanodeistransmittingthenitcannotconcurrently
receive from nodes within the same cell, and any data it
receives from adjacent cells must be on a different frequency
band. If the cell structure is rectinlinear, it is well known
that only 9 orthogonal subbands are required to ensure all
neighboring cells have distinct subbands, and this number can
be reduced to 7 if cells are arranged according to a hexagonal
pattern. While the cell partitioned structure is not critical to
our analysis, it simpli?es exposition and allows scheduling
decisions to be decoupled cell by cell. Relaxations of the
model or further restrictions on power assignment can easily
be incorporated by modifying the set constraint ? or the rate
function ~ µ(
~
P,
~
S).
The goal of this paper is to develop a power allocation
and routing algorithm that supports all incoming traf?c while
minimizing average power expenditure. We develop a robust
policy that does not require knowledge of input rates or
channel probabilities yet uses a total power expenditure that
is arbitrarily close to the minimum average power expended
by a system optimized with complete knowledge of future
events. Distance to this minimum power level is controlled by
a parameter V effecting an explicit tradeoff in average end-
to-end network delay.
Previous work in the area of power allocation for wireless
systems can be categorized into static optimization solutions
[5]-[12] and dynamic control algorithms [14]-[13]. In [5], a
utility optimization problem is presented for a static wireless
downlink, and pricing schemes are developed to enable power
allocations to converge to a fair allocation vector. Linear
programming, geometric programming, and other convex op-
timization methods are considered in [6]-[10] for routing and
power allocation problems in wireless systems and sensor
networks. Such techniques rely on the mathematical theory of
Lagrangian duality (see, for example, [28]). This theory was
applied in the landmark paper [29] to develop mechanisms for
optimal static resource allocation in a non-wireless network.
We note that convex optimization approaches traditionally
yield single-operating point solutions, which may not be well
suited to cases when optimal networking involves dynamic
allocation of resources. Indeed, in [12] it is shown that
minimizingenergyinastaticad-hocnetworkwithinterference
involves the computation of a periodic transmission schedule,
yielding dramatic improvements over any ?xed resource al-
location. A similar scheduling problem is shown to be NP-
complete in [11].
Prior work in the area of stochastic optimization and dy-
namic control for wireless networks considers much smaller
systems with more a-priori statistical information, including
[23] [24] [25] for energy ef?cient scheduling in single queue
systems, and [26] [27] for multi-user downlinks with in?nite
backlog. A downlink with randomly arriving traf?c and peak
and average power constraints is considered in [13] using
a theory of Lyapunov drift, although the algorithm requires
perfect knowledge of channel probabilities in order to meet
the average power requirement. Lyapunov theory can be used
to design stabilizing power allocation and routing algorithms
that do not require knowledge of arrival rates or channel
statistics in cases where there are only peak power constraints
on the wireless devices [22]. Historically, Lyapunov theory
has been extremely useful in the development of stable queue
controlpoliciesforradionetworksandswitchingsystems[14]-
[22]. However, there was previously no Lyapunov method for
performingqueueingnetworkoptimization(suchasstabilizing
a network with minimum average power).
In this paper, we develop a simple Lyapunov drift technique
that enables system stability and performance optimization
to be achieved simultaneously [2] [1] [30]. The technique
extends the Lyapunov methods of [14]-[22] and bridges the
gap between convex optimization theory and stochastic queue-
ing control problems. We note that alternative approaches
to stochastic network optimization have recently appeared
in [31] [32] [33] using ?uid model transformations and/or
stochastic gradient theory. Our Lyapunov technique is similar
to the notion of a stochastic gradient (see Chapters 4-5 of
[2] for a comparison between static gradient search methods
and Lyapunov scheduling), although it was developed from a
queueing stability perspective and yields explicit bounds on
average power and delay.
For simplicity of exposition and to highlight the issues of
powerallocation,inthe?rsthalfofthispaperweconsideronly
single-hop networks with no routing. The paper is organized
as follows: In the next section we consider a motivating
example of a 2-user wireless downlink. In Section III we
develop a control policy for minimizing average power for
one-hop networks. In Section IV we treat a related problem
of maximizing throughput subject to peak and average power
constraints (for cases when traf?c is either supportable or
insupportable). Extensions to multi-hop networks and mobile
networks are treated in Sections V and VI, and simulations
are presented in Section VII.
II. A SIMPLE EXAMPLE
To illustrate the decisions involved in energy-optimal
scheduling, we consider the following example of a two-queue
wireless downlink, where a single node (labeled ‘node 0’)
transmits data to two different stations over downlink channels
1 and 2 (as in Fig. 1 in the case when only node 0 is active).
The system operates in slotted time, and every slot the channel
states are measured, power allocation decisions are made, and
new arrivals are queued according to their destinations.
Let U
1
(t) and U
2
(t) represent the current backlog queued
for transmission to destinations 1 and 2, respectively, and
consider the decision of whether or not to allocate power to
channel 1. Clearly no power should be allocated if U
1
(t) = 0.
When U
1
(t) > 0, we must decide whether to allocate power
on the current slot or wait for a more energy-ef?cient future
channel state. In this example, we consider only ON/OFF
power constraints and assume that either no power is allocated
to any channel, or full power of 1 Watt is allocated to either
channel 1 or channel 2. Link conditions for each channel 1
Page 3


IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 52, NO. 7, JULY 2006 1
Energy Optimal Control for Time Varying
Wireless Networks
Michael J. Neely
Abstract—We develop a dynamic control strategy for min-
imizing energy expenditure in a time varying wireless network
withadaptivetransmissionrates.Thealgorithmoperateswithout
knowledgeoftraf?cratesorchannelstatistics,andyieldsaverage
power that is arbitrarily close to the minimum possible value
achieved by an algorithm optimized with complete knowledge of
futureevents.Proximitytothisoptimalsolutionisshowntobein-
versely proportional to network delay. We then present a similar
algorithm that solves the related problem of maximizing network
throughput subject to peak and average power constraints. The
techniquesusedinthispaperarenovelandestablishafoundation
for stochastic network optimization.
Index Terms—Stochastic Optimization, Queueing Analysis,
Ad-Hoc Networks, Distributed Algorithms, Mobile Networks
I. INTRODUCTION
Wirelesssystemsoperateovertimevaryingchannelsthatare
in?uenced by random environmental conditions, wireless fad-
ing, and power allocation decisions. To improve performance
and meet the ever increasing demand for high throughput
and low delay, modern wireless devices are designed with
channel monitoring capabilities and rate adaptive technology.
Such technology is currently being implemented for cellular
communication with High Data Rate (HDR) services [3], and
the ability to measure and react to channel information is
expected to improve signi?cantly.
1
It is of central importance
to develop control strategies that take maximum advantage of
this information to improve network performance and energy
ef?ciency.
In this paper, we develop throughput optimal control strate-
gies that conform to peak power constraints while minimizing
average power expenditure. This design goal is crucial in
all modern wireless scenarios, regardless of whether trans-
missions take place at a basestation, a hand-held unit, or
at a node within an ad-hoc sensor network. Indeed, peak
powerconstraintsareimportantinsystemswith?xedhardware
saturation levels or external environment regulations, while
average power levels are important to extend network lifetime
in systems with limited energy resources.
Here, we consider an ad-hoc network with N nodes and
L wireless links, as shown in Fig. 1. We assume a slotted
structure with slots equal to 1 time unit. Packets randomly
arrive to the network every timeslot and must be delivered to
their destinations, perhaps by routing over multi-hop paths.
Michael J. Neely is with the Department of Electrical Engineering, Uni-
versity of Southern California, Los Angeles, CA 90089 USA (email: mjneely
AT usc.edu, web: http://www-rcf.usc.edu/~mjneely).
This work was presented in part at the IEEE INFOCOM conference, March
2005, and at the USC CSI Research Review, March 2004.
1
Indeed, it is claimed in [4] that channel measurements can be obtained
almost as often as the symbol rate of the link in certain local area wireless
networks.
µ(p)
S = {Excellent}
S = {Good}
S = {Average}
S = {Bad}
S = {Zero}
power p
3
N
2
0
1
4
Fig. 1. A cell-partitioned wireless network, and an example set of rate-power
curves for 5 different channel states.
The transmission rates of each data link are determined every
timeslot by link channel conditions and network power allo-
cation decisions according to an L-dimensional rate function
~ µ(
~
P(t),
~
S(t)), where
~
P(t) is a vector of power allocations
and
~
S(t) is a vector of parameters describing the current
channel conditions. For most of this paper, we assume that all
nodes maintain the same locations relative to one another for
the duration of the network operation. Although the network
topology remains ?xed in this scenario, link conditions may
vary dramatically due to environmental effects, local mobility,
or wireless fading. Extensions to networks with arbitrary
mobility patterns are developed in Section VI.
Powervectorsarerestrictedtoacompactset?ofacceptable
power allocations, so that
~
P(t) ? ? for all t. The set ?
includes the peak power constraints for each node together
with any additional constraints the network might impose on
instantaneous transmissions. All of our results are presented
for general power sets ? and general rate functions ~ µ(
~
P,
~
S).
An example of concave rate-power curves for one data link
with a discrete set of possible channel states is shown in Fig.
1. Such curves might also depend on the signal to interference
ratio at the intended receiver, so thatµ
l
(
~
P,
~
S) for a given link
l is determined by the full vector of power allocations and
channelstates[22][12][23].However,tosimplifythemultiple
access control layer while capturing the geographic structure
and interference properties of ad-hoc networks, we focus our
implementation examples on a cell partitioned network model.
Under this model, the network region is divided into cells,
each containing a distinct set of nodes. Speci?cally, we de?ne
cell(n) as the cell of each node n?{1,...,N}, and de?ne
tran(l) and rec(l) as the transmitting and receiving nodes
associated with a given wireless link l ? {1,...,L}. We
assume that each cell can support at most one active link
transmission per timeslot, and that nodes can transmit only
to other nodes in the same cell or in adjacent cells. That is,
the feasible power set ? includes the constraint that if P
l
> 0
for some link l, then P
˜
l
= 0 for all links
˜
l 6= l such that
IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 52, NO. 7, JULY 2006 2
cell(tran(
˜
l)) = cell(tran(l)). We further assume that the
transmission rate of each link depends only on the channel
state and the power allocated to that link, so that ~ µ(
~
P,
~
S) =
(µ
1
(P
1
,S
1
),...,µ
L
(P
L
,S
L
)). This structure arises if nodes
in neighboring cells transmit over orthogonal frequency bands.
Inthisway,ifanodeistransmittingthenitcannotconcurrently
receive from nodes within the same cell, and any data it
receives from adjacent cells must be on a different frequency
band. If the cell structure is rectinlinear, it is well known
that only 9 orthogonal subbands are required to ensure all
neighboring cells have distinct subbands, and this number can
be reduced to 7 if cells are arranged according to a hexagonal
pattern. While the cell partitioned structure is not critical to
our analysis, it simpli?es exposition and allows scheduling
decisions to be decoupled cell by cell. Relaxations of the
model or further restrictions on power assignment can easily
be incorporated by modifying the set constraint ? or the rate
function ~ µ(
~
P,
~
S).
The goal of this paper is to develop a power allocation
and routing algorithm that supports all incoming traf?c while
minimizing average power expenditure. We develop a robust
policy that does not require knowledge of input rates or
channel probabilities yet uses a total power expenditure that
is arbitrarily close to the minimum average power expended
by a system optimized with complete knowledge of future
events. Distance to this minimum power level is controlled by
a parameter V effecting an explicit tradeoff in average end-
to-end network delay.
Previous work in the area of power allocation for wireless
systems can be categorized into static optimization solutions
[5]-[12] and dynamic control algorithms [14]-[13]. In [5], a
utility optimization problem is presented for a static wireless
downlink, and pricing schemes are developed to enable power
allocations to converge to a fair allocation vector. Linear
programming, geometric programming, and other convex op-
timization methods are considered in [6]-[10] for routing and
power allocation problems in wireless systems and sensor
networks. Such techniques rely on the mathematical theory of
Lagrangian duality (see, for example, [28]). This theory was
applied in the landmark paper [29] to develop mechanisms for
optimal static resource allocation in a non-wireless network.
We note that convex optimization approaches traditionally
yield single-operating point solutions, which may not be well
suited to cases when optimal networking involves dynamic
allocation of resources. Indeed, in [12] it is shown that
minimizingenergyinastaticad-hocnetworkwithinterference
involves the computation of a periodic transmission schedule,
yielding dramatic improvements over any ?xed resource al-
location. A similar scheduling problem is shown to be NP-
complete in [11].
Prior work in the area of stochastic optimization and dy-
namic control for wireless networks considers much smaller
systems with more a-priori statistical information, including
[23] [24] [25] for energy ef?cient scheduling in single queue
systems, and [26] [27] for multi-user downlinks with in?nite
backlog. A downlink with randomly arriving traf?c and peak
and average power constraints is considered in [13] using
a theory of Lyapunov drift, although the algorithm requires
perfect knowledge of channel probabilities in order to meet
the average power requirement. Lyapunov theory can be used
to design stabilizing power allocation and routing algorithms
that do not require knowledge of arrival rates or channel
statistics in cases where there are only peak power constraints
on the wireless devices [22]. Historically, Lyapunov theory
has been extremely useful in the development of stable queue
controlpoliciesforradionetworksandswitchingsystems[14]-
[22]. However, there was previously no Lyapunov method for
performingqueueingnetworkoptimization(suchasstabilizing
a network with minimum average power).
In this paper, we develop a simple Lyapunov drift technique
that enables system stability and performance optimization
to be achieved simultaneously [2] [1] [30]. The technique
extends the Lyapunov methods of [14]-[22] and bridges the
gap between convex optimization theory and stochastic queue-
ing control problems. We note that alternative approaches
to stochastic network optimization have recently appeared
in [31] [32] [33] using ?uid model transformations and/or
stochastic gradient theory. Our Lyapunov technique is similar
to the notion of a stochastic gradient (see Chapters 4-5 of
[2] for a comparison between static gradient search methods
and Lyapunov scheduling), although it was developed from a
queueing stability perspective and yields explicit bounds on
average power and delay.
For simplicity of exposition and to highlight the issues of
powerallocation,inthe?rsthalfofthispaperweconsideronly
single-hop networks with no routing. The paper is organized
as follows: In the next section we consider a motivating
example of a 2-user wireless downlink. In Section III we
develop a control policy for minimizing average power for
one-hop networks. In Section IV we treat a related problem
of maximizing throughput subject to peak and average power
constraints (for cases when traf?c is either supportable or
insupportable). Extensions to multi-hop networks and mobile
networks are treated in Sections V and VI, and simulations
are presented in Section VII.
II. A SIMPLE EXAMPLE
To illustrate the decisions involved in energy-optimal
scheduling, we consider the following example of a two-queue
wireless downlink, where a single node (labeled ‘node 0’)
transmits data to two different stations over downlink channels
1 and 2 (as in Fig. 1 in the case when only node 0 is active).
The system operates in slotted time, and every slot the channel
states are measured, power allocation decisions are made, and
new arrivals are queued according to their destinations.
Let U
1
(t) and U
2
(t) represent the current backlog queued
for transmission to destinations 1 and 2, respectively, and
consider the decision of whether or not to allocate power to
channel 1. Clearly no power should be allocated if U
1
(t) = 0.
When U
1
(t) > 0, we must decide whether to allocate power
on the current slot or wait for a more energy-ef?cient future
channel state. In this example, we consider only ON/OFF
power constraints and assume that either no power is allocated
to any channel, or full power of 1 Watt is allocated to either
channel 1 or channel 2. Link conditions for each channel 1
IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 52, NO. 7, JULY 2006 3
t 0 1 2 3 4 5 6 7 8
Arrivals A
1
(t) 3 0 3 0 0 1 0 1 0
A
2
(t) 2 0 1 0 1 1 0 0 0
Channels S
1
(t) G G M M G G M M G
S
2
(t) M M B M B M B G B
Max U
i
µ
i
U
1
(t) 0 3 0 3 1 0 1 1 2
Policy U
2
(t) 0 2 2 2 2 3 2 1 0
Better U
1
(t) 0 3 3 6 6 3 1 1 2
Choices U
2
(t) 0 2 2 3 1 2 3 3 0
Fig. 2. An example set of arrivals, channel conditions, and queue backlogs
for a two queue wireless downlink under two different scheduling algorithms,
illustrating the power ef?ciency gains enabled by having full knowledge of
future arrivals and channel states.
and 2 vary between ‘Good,’ ‘Medium,’ and ‘Bad’ states:
(P
1
(t),P
2
(t))? ?
M
=
{(0,0),(1,0),(0,1)}
S
1
(t),S
2
(t)?{G,M,B}
Assume identical rate functions for i = 1,2, given by:
µ
i
(0,S
i
) = 0 units/slot for all S
i
?{G,M,B}
µ
i
(1,G) = 3,µ
i
(1,M) = 2,µ
i
(1,B) = 1 (units/slot)
That is, a link can transmit 3 units of data in the ‘Good’ state,
2 units in the ‘Medium’ state, and 1 in the ‘Bad’ state.
Let A
1
(t) and A
2
(t) represent the number of new data
units arriving during slot t and destined for nodes 1 and
2, respectively. Queueing dynamics proceed according to the
equation:
U
i
(t+1) = max[U
i
(t)-µ
i
(P
i
(t),S
i
(t)),0]+A
i
(t)
SupposearrivalsA
i
(t)andchannelstatesS
i
(t)forthe?rst9
timeslotst?{0,...,8}areasgiveninFig.2,andconsiderthe
policy of allocating power to the channel with the largest rate-
backlogproductU
i
(t)µ
i
(1,S
i
(t)).Thispolicycanbeshownto
stabilizethesystemwheneverpossible[15][19][21],although
it is not necessarily energy-ef?cient. According to the ?gure,
both queues are empty at time t = 0 when arrivals enter the
system according to vector (A
1
(0),A
2
(0)) = (3,2), resulting
in a backlog vector (U
1
(1),U
2
(1)) = (3,2) at the beginning
of slot 1. Because the channel states at slot 1 are given
by (S
1
(1),S
2
(1)) = (G,M), the rate-backlog indices for
channels 1 and 2 at slot 1 are given byU
1
(t)µ
1
(1,S
1
(t)) = 9,
U
2
(t)µ
2
(1,S
2
(t)) = 4, so that the MaxU
i
µ
i
policy places full
power to channel 1 (as indicated by the boxed values in the
?gure).
Because there were no new arrivals during slot 1, the result-
ing backlog vector at time t = 2 is given by (U
1
(t),U
2
(t)) =
(0,2), as shown in the ?gure. The policy proceeds by ex-
pending 1 Watt of power for time t ? {1,...,8}, and the
scheduling decision at slot t = 8 will leave the system again
empty at time t = 9. If the same arrival and channel patterns
were extended periodically every 9 timeslots, the Max U
i
µ
i
policy would allocate 1 Watt of power 8 timeslots out of every
9, yielding a time average power consumption of P
av
= 8/9
Watt. Similar power consumption levels are observed when
the policy is simulated for random arrivals and channel states
with the same steady state distributions as this example (see
Section VII).
Now consider the alternate policy of waiting until slot 3 to
allocate power, and then making decisions as shown in the
?gure. These decisions also leave the system empty at slot 9,
but yield an average power expenditure of P
av
= 5/9 Watt
over the 9 slot interval. Average power can be further reduced
if channel states and arrivals are extended periodically (or
probabilistically) over the in?nite time horizon, and it can be
shown that the minimum average power required to stabilize
such a system is given by P
*
av
= 0.518.
The above example illustrates the energy gains available
by more intelligent scheduling. In cases where power can be
allocated as a continuous variable, more complex decisions
are involved: Should we exploit better channel states by
transmitting at higher data rates with the same power level, or
by transmitting at the same data rate with reduced power? In
thenextsection,wedevelopasimpledecisionmakingstrategy
that does not require knowledge of future events, traf?c rates,
or channel statistics, yet yields an average power expenditure
that is arbitrarily close to optimal.
III. SINGLE HOP NETWORKS
ConsiderthewirelessnetworkofFig.1withN nodesandL
links, where each link corresponds to a directed transmission
from one node to another. Packets randomly arrive to the
system and are queued according to their destinations. This is
a single-hop network, and hence incoming data is associated
with a particular transmission link l ? {1,...,L} and is
assumed to leave the network once it is transmitted. Let A
l
(t)
represent the amount of bits arriving for transmission over
link l during slot t, and let U
l
(t) represent the current queue
backlog (or ‘un?nished work’) in queue l. Let
~
S(t) and
~
P(t)
represent the L-dimensional vectors of channel states and
power allocations. In vector notation, the queueing dynamics
are:
~
U(t+1) = max[
~
U(t)-~ µ(
~
P(t),
~
S(t)),0]+
~
A(t) (1)
where ~ µ(
~
P,
~
S) is the rate function associated with the given
physical layer modulation and coding strategies used for
wireless communication.
We assume that there are a ?nite number of channel state
vectors
~
S, and that ~ µ(
~
P,
~
S) is a continuous function of the
power vector
~
P for each channel state
~
S.
2
Every timeslot
a power vector
~
P(t) is chosen in reaction to queue backlog
and current channel conditions, subject to the constraint that
~
P(t) ? ? for all t, where ? is a compact set of acceptable
power vectors. Throughout this paper, we use these general
rate functions and set constraints to present our main re-
sults. However, in all examples of distributed implementation,
we assume the rate function has the structure: ~ µ(
~
P,
~
S) =
(µ
1
(P
1
,S
1
),...,µ
L
(P
L
,S
L
)). Further, in our examples we
assume that ? consists of all vectors
~
P satisfying the cell-
partition constraint (i.e., that if P
l
> 0 for some link l, then
P
˜
l
= 0 for all
˜
l6=l satisfying cell(tran(l)) =cell(tran(
˜
l))),
2
Our results hold more generally for any (potentially discontinuous) rate-
power curve that satis?es the upper semi-continuity property [2].
Page 4


IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 52, NO. 7, JULY 2006 1
Energy Optimal Control for Time Varying
Wireless Networks
Michael J. Neely
Abstract—We develop a dynamic control strategy for min-
imizing energy expenditure in a time varying wireless network
withadaptivetransmissionrates.Thealgorithmoperateswithout
knowledgeoftraf?cratesorchannelstatistics,andyieldsaverage
power that is arbitrarily close to the minimum possible value
achieved by an algorithm optimized with complete knowledge of
futureevents.Proximitytothisoptimalsolutionisshowntobein-
versely proportional to network delay. We then present a similar
algorithm that solves the related problem of maximizing network
throughput subject to peak and average power constraints. The
techniquesusedinthispaperarenovelandestablishafoundation
for stochastic network optimization.
Index Terms—Stochastic Optimization, Queueing Analysis,
Ad-Hoc Networks, Distributed Algorithms, Mobile Networks
I. INTRODUCTION
Wirelesssystemsoperateovertimevaryingchannelsthatare
in?uenced by random environmental conditions, wireless fad-
ing, and power allocation decisions. To improve performance
and meet the ever increasing demand for high throughput
and low delay, modern wireless devices are designed with
channel monitoring capabilities and rate adaptive technology.
Such technology is currently being implemented for cellular
communication with High Data Rate (HDR) services [3], and
the ability to measure and react to channel information is
expected to improve signi?cantly.
1
It is of central importance
to develop control strategies that take maximum advantage of
this information to improve network performance and energy
ef?ciency.
In this paper, we develop throughput optimal control strate-
gies that conform to peak power constraints while minimizing
average power expenditure. This design goal is crucial in
all modern wireless scenarios, regardless of whether trans-
missions take place at a basestation, a hand-held unit, or
at a node within an ad-hoc sensor network. Indeed, peak
powerconstraintsareimportantinsystemswith?xedhardware
saturation levels or external environment regulations, while
average power levels are important to extend network lifetime
in systems with limited energy resources.
Here, we consider an ad-hoc network with N nodes and
L wireless links, as shown in Fig. 1. We assume a slotted
structure with slots equal to 1 time unit. Packets randomly
arrive to the network every timeslot and must be delivered to
their destinations, perhaps by routing over multi-hop paths.
Michael J. Neely is with the Department of Electrical Engineering, Uni-
versity of Southern California, Los Angeles, CA 90089 USA (email: mjneely
AT usc.edu, web: http://www-rcf.usc.edu/~mjneely).
This work was presented in part at the IEEE INFOCOM conference, March
2005, and at the USC CSI Research Review, March 2004.
1
Indeed, it is claimed in [4] that channel measurements can be obtained
almost as often as the symbol rate of the link in certain local area wireless
networks.
µ(p)
S = {Excellent}
S = {Good}
S = {Average}
S = {Bad}
S = {Zero}
power p
3
N
2
0
1
4
Fig. 1. A cell-partitioned wireless network, and an example set of rate-power
curves for 5 different channel states.
The transmission rates of each data link are determined every
timeslot by link channel conditions and network power allo-
cation decisions according to an L-dimensional rate function
~ µ(
~
P(t),
~
S(t)), where
~
P(t) is a vector of power allocations
and
~
S(t) is a vector of parameters describing the current
channel conditions. For most of this paper, we assume that all
nodes maintain the same locations relative to one another for
the duration of the network operation. Although the network
topology remains ?xed in this scenario, link conditions may
vary dramatically due to environmental effects, local mobility,
or wireless fading. Extensions to networks with arbitrary
mobility patterns are developed in Section VI.
Powervectorsarerestrictedtoacompactset?ofacceptable
power allocations, so that
~
P(t) ? ? for all t. The set ?
includes the peak power constraints for each node together
with any additional constraints the network might impose on
instantaneous transmissions. All of our results are presented
for general power sets ? and general rate functions ~ µ(
~
P,
~
S).
An example of concave rate-power curves for one data link
with a discrete set of possible channel states is shown in Fig.
1. Such curves might also depend on the signal to interference
ratio at the intended receiver, so thatµ
l
(
~
P,
~
S) for a given link
l is determined by the full vector of power allocations and
channelstates[22][12][23].However,tosimplifythemultiple
access control layer while capturing the geographic structure
and interference properties of ad-hoc networks, we focus our
implementation examples on a cell partitioned network model.
Under this model, the network region is divided into cells,
each containing a distinct set of nodes. Speci?cally, we de?ne
cell(n) as the cell of each node n?{1,...,N}, and de?ne
tran(l) and rec(l) as the transmitting and receiving nodes
associated with a given wireless link l ? {1,...,L}. We
assume that each cell can support at most one active link
transmission per timeslot, and that nodes can transmit only
to other nodes in the same cell or in adjacent cells. That is,
the feasible power set ? includes the constraint that if P
l
> 0
for some link l, then P
˜
l
= 0 for all links
˜
l 6= l such that
IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 52, NO. 7, JULY 2006 2
cell(tran(
˜
l)) = cell(tran(l)). We further assume that the
transmission rate of each link depends only on the channel
state and the power allocated to that link, so that ~ µ(
~
P,
~
S) =
(µ
1
(P
1
,S
1
),...,µ
L
(P
L
,S
L
)). This structure arises if nodes
in neighboring cells transmit over orthogonal frequency bands.
Inthisway,ifanodeistransmittingthenitcannotconcurrently
receive from nodes within the same cell, and any data it
receives from adjacent cells must be on a different frequency
band. If the cell structure is rectinlinear, it is well known
that only 9 orthogonal subbands are required to ensure all
neighboring cells have distinct subbands, and this number can
be reduced to 7 if cells are arranged according to a hexagonal
pattern. While the cell partitioned structure is not critical to
our analysis, it simpli?es exposition and allows scheduling
decisions to be decoupled cell by cell. Relaxations of the
model or further restrictions on power assignment can easily
be incorporated by modifying the set constraint ? or the rate
function ~ µ(
~
P,
~
S).
The goal of this paper is to develop a power allocation
and routing algorithm that supports all incoming traf?c while
minimizing average power expenditure. We develop a robust
policy that does not require knowledge of input rates or
channel probabilities yet uses a total power expenditure that
is arbitrarily close to the minimum average power expended
by a system optimized with complete knowledge of future
events. Distance to this minimum power level is controlled by
a parameter V effecting an explicit tradeoff in average end-
to-end network delay.
Previous work in the area of power allocation for wireless
systems can be categorized into static optimization solutions
[5]-[12] and dynamic control algorithms [14]-[13]. In [5], a
utility optimization problem is presented for a static wireless
downlink, and pricing schemes are developed to enable power
allocations to converge to a fair allocation vector. Linear
programming, geometric programming, and other convex op-
timization methods are considered in [6]-[10] for routing and
power allocation problems in wireless systems and sensor
networks. Such techniques rely on the mathematical theory of
Lagrangian duality (see, for example, [28]). This theory was
applied in the landmark paper [29] to develop mechanisms for
optimal static resource allocation in a non-wireless network.
We note that convex optimization approaches traditionally
yield single-operating point solutions, which may not be well
suited to cases when optimal networking involves dynamic
allocation of resources. Indeed, in [12] it is shown that
minimizingenergyinastaticad-hocnetworkwithinterference
involves the computation of a periodic transmission schedule,
yielding dramatic improvements over any ?xed resource al-
location. A similar scheduling problem is shown to be NP-
complete in [11].
Prior work in the area of stochastic optimization and dy-
namic control for wireless networks considers much smaller
systems with more a-priori statistical information, including
[23] [24] [25] for energy ef?cient scheduling in single queue
systems, and [26] [27] for multi-user downlinks with in?nite
backlog. A downlink with randomly arriving traf?c and peak
and average power constraints is considered in [13] using
a theory of Lyapunov drift, although the algorithm requires
perfect knowledge of channel probabilities in order to meet
the average power requirement. Lyapunov theory can be used
to design stabilizing power allocation and routing algorithms
that do not require knowledge of arrival rates or channel
statistics in cases where there are only peak power constraints
on the wireless devices [22]. Historically, Lyapunov theory
has been extremely useful in the development of stable queue
controlpoliciesforradionetworksandswitchingsystems[14]-
[22]. However, there was previously no Lyapunov method for
performingqueueingnetworkoptimization(suchasstabilizing
a network with minimum average power).
In this paper, we develop a simple Lyapunov drift technique
that enables system stability and performance optimization
to be achieved simultaneously [2] [1] [30]. The technique
extends the Lyapunov methods of [14]-[22] and bridges the
gap between convex optimization theory and stochastic queue-
ing control problems. We note that alternative approaches
to stochastic network optimization have recently appeared
in [31] [32] [33] using ?uid model transformations and/or
stochastic gradient theory. Our Lyapunov technique is similar
to the notion of a stochastic gradient (see Chapters 4-5 of
[2] for a comparison between static gradient search methods
and Lyapunov scheduling), although it was developed from a
queueing stability perspective and yields explicit bounds on
average power and delay.
For simplicity of exposition and to highlight the issues of
powerallocation,inthe?rsthalfofthispaperweconsideronly
single-hop networks with no routing. The paper is organized
as follows: In the next section we consider a motivating
example of a 2-user wireless downlink. In Section III we
develop a control policy for minimizing average power for
one-hop networks. In Section IV we treat a related problem
of maximizing throughput subject to peak and average power
constraints (for cases when traf?c is either supportable or
insupportable). Extensions to multi-hop networks and mobile
networks are treated in Sections V and VI, and simulations
are presented in Section VII.
II. A SIMPLE EXAMPLE
To illustrate the decisions involved in energy-optimal
scheduling, we consider the following example of a two-queue
wireless downlink, where a single node (labeled ‘node 0’)
transmits data to two different stations over downlink channels
1 and 2 (as in Fig. 1 in the case when only node 0 is active).
The system operates in slotted time, and every slot the channel
states are measured, power allocation decisions are made, and
new arrivals are queued according to their destinations.
Let U
1
(t) and U
2
(t) represent the current backlog queued
for transmission to destinations 1 and 2, respectively, and
consider the decision of whether or not to allocate power to
channel 1. Clearly no power should be allocated if U
1
(t) = 0.
When U
1
(t) > 0, we must decide whether to allocate power
on the current slot or wait for a more energy-ef?cient future
channel state. In this example, we consider only ON/OFF
power constraints and assume that either no power is allocated
to any channel, or full power of 1 Watt is allocated to either
channel 1 or channel 2. Link conditions for each channel 1
IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 52, NO. 7, JULY 2006 3
t 0 1 2 3 4 5 6 7 8
Arrivals A
1
(t) 3 0 3 0 0 1 0 1 0
A
2
(t) 2 0 1 0 1 1 0 0 0
Channels S
1
(t) G G M M G G M M G
S
2
(t) M M B M B M B G B
Max U
i
µ
i
U
1
(t) 0 3 0 3 1 0 1 1 2
Policy U
2
(t) 0 2 2 2 2 3 2 1 0
Better U
1
(t) 0 3 3 6 6 3 1 1 2
Choices U
2
(t) 0 2 2 3 1 2 3 3 0
Fig. 2. An example set of arrivals, channel conditions, and queue backlogs
for a two queue wireless downlink under two different scheduling algorithms,
illustrating the power ef?ciency gains enabled by having full knowledge of
future arrivals and channel states.
and 2 vary between ‘Good,’ ‘Medium,’ and ‘Bad’ states:
(P
1
(t),P
2
(t))? ?
M
=
{(0,0),(1,0),(0,1)}
S
1
(t),S
2
(t)?{G,M,B}
Assume identical rate functions for i = 1,2, given by:
µ
i
(0,S
i
) = 0 units/slot for all S
i
?{G,M,B}
µ
i
(1,G) = 3,µ
i
(1,M) = 2,µ
i
(1,B) = 1 (units/slot)
That is, a link can transmit 3 units of data in the ‘Good’ state,
2 units in the ‘Medium’ state, and 1 in the ‘Bad’ state.
Let A
1
(t) and A
2
(t) represent the number of new data
units arriving during slot t and destined for nodes 1 and
2, respectively. Queueing dynamics proceed according to the
equation:
U
i
(t+1) = max[U
i
(t)-µ
i
(P
i
(t),S
i
(t)),0]+A
i
(t)
SupposearrivalsA
i
(t)andchannelstatesS
i
(t)forthe?rst9
timeslotst?{0,...,8}areasgiveninFig.2,andconsiderthe
policy of allocating power to the channel with the largest rate-
backlogproductU
i
(t)µ
i
(1,S
i
(t)).Thispolicycanbeshownto
stabilizethesystemwheneverpossible[15][19][21],although
it is not necessarily energy-ef?cient. According to the ?gure,
both queues are empty at time t = 0 when arrivals enter the
system according to vector (A
1
(0),A
2
(0)) = (3,2), resulting
in a backlog vector (U
1
(1),U
2
(1)) = (3,2) at the beginning
of slot 1. Because the channel states at slot 1 are given
by (S
1
(1),S
2
(1)) = (G,M), the rate-backlog indices for
channels 1 and 2 at slot 1 are given byU
1
(t)µ
1
(1,S
1
(t)) = 9,
U
2
(t)µ
2
(1,S
2
(t)) = 4, so that the MaxU
i
µ
i
policy places full
power to channel 1 (as indicated by the boxed values in the
?gure).
Because there were no new arrivals during slot 1, the result-
ing backlog vector at time t = 2 is given by (U
1
(t),U
2
(t)) =
(0,2), as shown in the ?gure. The policy proceeds by ex-
pending 1 Watt of power for time t ? {1,...,8}, and the
scheduling decision at slot t = 8 will leave the system again
empty at time t = 9. If the same arrival and channel patterns
were extended periodically every 9 timeslots, the Max U
i
µ
i
policy would allocate 1 Watt of power 8 timeslots out of every
9, yielding a time average power consumption of P
av
= 8/9
Watt. Similar power consumption levels are observed when
the policy is simulated for random arrivals and channel states
with the same steady state distributions as this example (see
Section VII).
Now consider the alternate policy of waiting until slot 3 to
allocate power, and then making decisions as shown in the
?gure. These decisions also leave the system empty at slot 9,
but yield an average power expenditure of P
av
= 5/9 Watt
over the 9 slot interval. Average power can be further reduced
if channel states and arrivals are extended periodically (or
probabilistically) over the in?nite time horizon, and it can be
shown that the minimum average power required to stabilize
such a system is given by P
*
av
= 0.518.
The above example illustrates the energy gains available
by more intelligent scheduling. In cases where power can be
allocated as a continuous variable, more complex decisions
are involved: Should we exploit better channel states by
transmitting at higher data rates with the same power level, or
by transmitting at the same data rate with reduced power? In
thenextsection,wedevelopasimpledecisionmakingstrategy
that does not require knowledge of future events, traf?c rates,
or channel statistics, yet yields an average power expenditure
that is arbitrarily close to optimal.
III. SINGLE HOP NETWORKS
ConsiderthewirelessnetworkofFig.1withN nodesandL
links, where each link corresponds to a directed transmission
from one node to another. Packets randomly arrive to the
system and are queued according to their destinations. This is
a single-hop network, and hence incoming data is associated
with a particular transmission link l ? {1,...,L} and is
assumed to leave the network once it is transmitted. Let A
l
(t)
represent the amount of bits arriving for transmission over
link l during slot t, and let U
l
(t) represent the current queue
backlog (or ‘un?nished work’) in queue l. Let
~
S(t) and
~
P(t)
represent the L-dimensional vectors of channel states and
power allocations. In vector notation, the queueing dynamics
are:
~
U(t+1) = max[
~
U(t)-~ µ(
~
P(t),
~
S(t)),0]+
~
A(t) (1)
where ~ µ(
~
P,
~
S) is the rate function associated with the given
physical layer modulation and coding strategies used for
wireless communication.
We assume that there are a ?nite number of channel state
vectors
~
S, and that ~ µ(
~
P,
~
S) is a continuous function of the
power vector
~
P for each channel state
~
S.
2
Every timeslot
a power vector
~
P(t) is chosen in reaction to queue backlog
and current channel conditions, subject to the constraint that
~
P(t) ? ? for all t, where ? is a compact set of acceptable
power vectors. Throughout this paper, we use these general
rate functions and set constraints to present our main re-
sults. However, in all examples of distributed implementation,
we assume the rate function has the structure: ~ µ(
~
P,
~
S) =
(µ
1
(P
1
,S
1
),...,µ
L
(P
L
,S
L
)). Further, in our examples we
assume that ? consists of all vectors
~
P satisfying the cell-
partition constraint (i.e., that if P
l
> 0 for some link l, then
P
˜
l
= 0 for all
˜
l6=l satisfying cell(tran(l)) =cell(tran(
˜
l))),
2
Our results hold more generally for any (potentially discontinuous) rate-
power curve that satis?es the upper semi-continuity property [2].
IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 52, NO. 7, JULY 2006 4
and such that each entry P
l
is limited by a peak value
P
peak
according to either the continuous power constraint
0 = P
l
= P
peak
or the discrete ON/OFF power constraint
P
l
?{0,P
peak
}.
A. Minimum Power For Stability
Here we characterize the minimum average power required
to stabilize the system. We begin with a precise de?nition of
stability in terms of the over?ow function g(M) associated
with a queue with un?nished work process U(t):
g(M)
M
=
limsup
t?8
1
t
t
X
t=0
Pr[U(t)>M]
The function g(M) represents the largest limiting fraction of
time the un?nished work is above the value M.
De?nition 1: A queue with un?nished work process U(t)
is stable if g(M)? 0 as M ?8. A network of queues is
stable if all individual queues are stable.
Inthespecialcasewhenqueuebacklogevolvesaccordingto
an ergodic Markov chain with a countably in?nite state space,
then this notion of stability is equivalent to the existence of
a steady state probability distribution for the chain. However,
the above stability de?nition is more general in that it does
not require a countably in?nite state space, nor does it require
ergodicity. A more detailed discussion of stability issues is
given in [34] [35] [2].
Assume that inputs and channel processes are ergodic with
arrival rates
~
? = (?
l
) and channel probabilities p
~
S
. In [2],
the network capacity region ? is de?ned as the closure of
the set of all rate vectors stabilizable under some power
allocation algorithm that conforms to the power constraint
~
P(t) ? ?. The following theorem speci?es the minimum
average power required for network stability, among the class
of all algorithms with complete knowledge of future events.
Theorem 1: (Minimum Power for Stability) If the network
is stabilizable (so that
~
?? ?), the minimum power required
for stability is given by P
*
av
, where P
*
av
is the solution to the
following nonlinear optimization problem (de?ned in terms of
auxiliary probability variables a
~
S
k
and power vectors
~
P
~
S
k
for
all
~
S and for k?{1,2,...}):
Minimize: P
av
=
P
~
S
p
~
S
P
8
k=1
a
~
S
k
~
1
0
~
P
~
S
k
Subject to: ~ µ
av
M
=
P
~
S
p
~
S
P
8
k=1
a
~
S
k
~ µ(
~
P
~
S
k
,
~
S)=
~
?
~
P
~
S
k
? ?,a
~
S
k
= 0 for all k,
~
S
P
L+2
k=1
a
~
S
k
= 1 for all
~
S
Further, the value of P
*
av
is unchanged if the optimization
problem above is restricted to use at most L + 2 auxiliary
variables a
~
S
k
and
~
P
~
S
k
for any channel state
~
S.
The theorem indicates that minimum power for stability is
achieved among the class of stationary policies that measure
the current channel state
~
S(t) and then randomly allocate
a power vector
~
P
~
S
k
with probability a
~
S
k
. This minimum is
attained by a particular policy because the number of channel
states is ?nite and the power set ? is compact. The value of
P
*
av
is the resulting average power of this stationary policy,
and ~ µ
av
is the resulting time average transmission rate vector.
This is expressed in the following corollary to Theorem 1.
Corollary 1: Ifchannelstates
~
S(t)arei.i.d.overslots,min-
imum power for stability is given by the valueP
*
av
, minimized
over the class of all stationary randomized algorithms that
make decisions based only on the current channel state
~
S(t),
and yielding for all timeslots t:
X
l
E{P
l
(t)|H(t)} =P
*
av
~ µ
av
M
=
E
n
~ µ

~
P(t),
~
S(t)

|H(t)
o
=
~
? (2)
whereH(t)representsthehistoryofpastchannelstatesduring
slots t ?{0,1,...,t-1}.
As the corollary assumes channel states are i.i.d. over slots,
the above expectation is the same for all slots t. Theorem 1 is
proven via the following two claims: (Claim 1) No algorithm
can achieve stability with a smaller average power P
*
av
, and
(Claim 2) any rate vector
~
? strictly interior to ? can be
stabilized with an average power that is arbitrarily close to
P
*
av
. Claim 1 is proven in Appendix A by extending the
dimensionality of the system from L to L+1 and applying
Caratheodory’s Theorem [28] (where the k?{1,...,L+2}
result is also obtained). Below we prove Claim 2:
Proof: (Claim 2) The network capacity region ? is proven
in [2] to consist of all rate vectors
~
? such that a stationary
power allocation rule exists satisfying (2). The value ofP
*
av
is
by de?nition the average power consumption, minimized over
all such stationary rules. If
~
? is strictly interior to ?, there
exists a positive value  such that
~
?+~ ? ? (where ~  is the
L-dimensional vector with all entries equal to ). It follows
that there exists a stationary power allocation rule satisfying:
E
n
~ µ

~
P(t),
~
S(t)
o
=
~
?+~ >
~
?
and we de?ne P
*
av
() as the minimum average power con-
sumed by any such stationary policy. The time average trans-
mission rate of each queue is strictly larger than the arrival
rate, and hence the network is stable [2]. This holds for
arbitrarily small values of . Furthermore, it is not dif?cult
to show:
3
P
*
av
=P
*
av
()=

1-


max

P
*
av
+


max
P
*
av
(
max
)
where 
max
is the largest scalar such that (?
l
+
max
)? ?. It
follows that P
*
av
()? P
*
av
as ? 0, so that stability can be
attained with power that is arbitrarily close to P
*
av
.
We note that the concept of randomization used in Theorem
1 is vitally important to treat the general case where the
set {~ µ(
~
P,
~
S)|
~
P ? ?} is not necessarily convex. Otherwise,
optimality can be achieved by a strategy that allocates a ?xed
power vector
~
P
~
S
whenever the channel is in state
~
S. Note
that even if there are only two possible channel states for
every link, the total number of channel state vectors is 2
L
.
Thus,whiletheabovestaticoptimizationde?nestheminimum
3
The right hand side of the inequality follows by noting P
*
av
() is less than
or equal to the average power associated with the mixed strategy that uses
the P
*
av
strategy with probability 1-/max and the Pav(max) strategy
with probability /max.
Page 5


IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 52, NO. 7, JULY 2006 1
Energy Optimal Control for Time Varying
Wireless Networks
Michael J. Neely
Abstract—We develop a dynamic control strategy for min-
imizing energy expenditure in a time varying wireless network
withadaptivetransmissionrates.Thealgorithmoperateswithout
knowledgeoftraf?cratesorchannelstatistics,andyieldsaverage
power that is arbitrarily close to the minimum possible value
achieved by an algorithm optimized with complete knowledge of
futureevents.Proximitytothisoptimalsolutionisshowntobein-
versely proportional to network delay. We then present a similar
algorithm that solves the related problem of maximizing network
throughput subject to peak and average power constraints. The
techniquesusedinthispaperarenovelandestablishafoundation
for stochastic network optimization.
Index Terms—Stochastic Optimization, Queueing Analysis,
Ad-Hoc Networks, Distributed Algorithms, Mobile Networks
I. INTRODUCTION
Wirelesssystemsoperateovertimevaryingchannelsthatare
in?uenced by random environmental conditions, wireless fad-
ing, and power allocation decisions. To improve performance
and meet the ever increasing demand for high throughput
and low delay, modern wireless devices are designed with
channel monitoring capabilities and rate adaptive technology.
Such technology is currently being implemented for cellular
communication with High Data Rate (HDR) services [3], and
the ability to measure and react to channel information is
expected to improve signi?cantly.
1
It is of central importance
to develop control strategies that take maximum advantage of
this information to improve network performance and energy
ef?ciency.
In this paper, we develop throughput optimal control strate-
gies that conform to peak power constraints while minimizing
average power expenditure. This design goal is crucial in
all modern wireless scenarios, regardless of whether trans-
missions take place at a basestation, a hand-held unit, or
at a node within an ad-hoc sensor network. Indeed, peak
powerconstraintsareimportantinsystemswith?xedhardware
saturation levels or external environment regulations, while
average power levels are important to extend network lifetime
in systems with limited energy resources.
Here, we consider an ad-hoc network with N nodes and
L wireless links, as shown in Fig. 1. We assume a slotted
structure with slots equal to 1 time unit. Packets randomly
arrive to the network every timeslot and must be delivered to
their destinations, perhaps by routing over multi-hop paths.
Michael J. Neely is with the Department of Electrical Engineering, Uni-
versity of Southern California, Los Angeles, CA 90089 USA (email: mjneely
AT usc.edu, web: http://www-rcf.usc.edu/~mjneely).
This work was presented in part at the IEEE INFOCOM conference, March
2005, and at the USC CSI Research Review, March 2004.
1
Indeed, it is claimed in [4] that channel measurements can be obtained
almost as often as the symbol rate of the link in certain local area wireless
networks.
µ(p)
S = {Excellent}
S = {Good}
S = {Average}
S = {Bad}
S = {Zero}
power p
3
N
2
0
1
4
Fig. 1. A cell-partitioned wireless network, and an example set of rate-power
curves for 5 different channel states.
The transmission rates of each data link are determined every
timeslot by link channel conditions and network power allo-
cation decisions according to an L-dimensional rate function
~ µ(
~
P(t),
~
S(t)), where
~
P(t) is a vector of power allocations
and
~
S(t) is a vector of parameters describing the current
channel conditions. For most of this paper, we assume that all
nodes maintain the same locations relative to one another for
the duration of the network operation. Although the network
topology remains ?xed in this scenario, link conditions may
vary dramatically due to environmental effects, local mobility,
or wireless fading. Extensions to networks with arbitrary
mobility patterns are developed in Section VI.
Powervectorsarerestrictedtoacompactset?ofacceptable
power allocations, so that
~
P(t) ? ? for all t. The set ?
includes the peak power constraints for each node together
with any additional constraints the network might impose on
instantaneous transmissions. All of our results are presented
for general power sets ? and general rate functions ~ µ(
~
P,
~
S).
An example of concave rate-power curves for one data link
with a discrete set of possible channel states is shown in Fig.
1. Such curves might also depend on the signal to interference
ratio at the intended receiver, so thatµ
l
(
~
P,
~
S) for a given link
l is determined by the full vector of power allocations and
channelstates[22][12][23].However,tosimplifythemultiple
access control layer while capturing the geographic structure
and interference properties of ad-hoc networks, we focus our
implementation examples on a cell partitioned network model.
Under this model, the network region is divided into cells,
each containing a distinct set of nodes. Speci?cally, we de?ne
cell(n) as the cell of each node n?{1,...,N}, and de?ne
tran(l) and rec(l) as the transmitting and receiving nodes
associated with a given wireless link l ? {1,...,L}. We
assume that each cell can support at most one active link
transmission per timeslot, and that nodes can transmit only
to other nodes in the same cell or in adjacent cells. That is,
the feasible power set ? includes the constraint that if P
l
> 0
for some link l, then P
˜
l
= 0 for all links
˜
l 6= l such that
IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 52, NO. 7, JULY 2006 2
cell(tran(
˜
l)) = cell(tran(l)). We further assume that the
transmission rate of each link depends only on the channel
state and the power allocated to that link, so that ~ µ(
~
P,
~
S) =
(µ
1
(P
1
,S
1
),...,µ
L
(P
L
,S
L
)). This structure arises if nodes
in neighboring cells transmit over orthogonal frequency bands.
Inthisway,ifanodeistransmittingthenitcannotconcurrently
receive from nodes within the same cell, and any data it
receives from adjacent cells must be on a different frequency
band. If the cell structure is rectinlinear, it is well known
that only 9 orthogonal subbands are required to ensure all
neighboring cells have distinct subbands, and this number can
be reduced to 7 if cells are arranged according to a hexagonal
pattern. While the cell partitioned structure is not critical to
our analysis, it simpli?es exposition and allows scheduling
decisions to be decoupled cell by cell. Relaxations of the
model or further restrictions on power assignment can easily
be incorporated by modifying the set constraint ? or the rate
function ~ µ(
~
P,
~
S).
The goal of this paper is to develop a power allocation
and routing algorithm that supports all incoming traf?c while
minimizing average power expenditure. We develop a robust
policy that does not require knowledge of input rates or
channel probabilities yet uses a total power expenditure that
is arbitrarily close to the minimum average power expended
by a system optimized with complete knowledge of future
events. Distance to this minimum power level is controlled by
a parameter V effecting an explicit tradeoff in average end-
to-end network delay.
Previous work in the area of power allocation for wireless
systems can be categorized into static optimization solutions
[5]-[12] and dynamic control algorithms [14]-[13]. In [5], a
utility optimization problem is presented for a static wireless
downlink, and pricing schemes are developed to enable power
allocations to converge to a fair allocation vector. Linear
programming, geometric programming, and other convex op-
timization methods are considered in [6]-[10] for routing and
power allocation problems in wireless systems and sensor
networks. Such techniques rely on the mathematical theory of
Lagrangian duality (see, for example, [28]). This theory was
applied in the landmark paper [29] to develop mechanisms for
optimal static resource allocation in a non-wireless network.
We note that convex optimization approaches traditionally
yield single-operating point solutions, which may not be well
suited to cases when optimal networking involves dynamic
allocation of resources. Indeed, in [12] it is shown that
minimizingenergyinastaticad-hocnetworkwithinterference
involves the computation of a periodic transmission schedule,
yielding dramatic improvements over any ?xed resource al-
location. A similar scheduling problem is shown to be NP-
complete in [11].
Prior work in the area of stochastic optimization and dy-
namic control for wireless networks considers much smaller
systems with more a-priori statistical information, including
[23] [24] [25] for energy ef?cient scheduling in single queue
systems, and [26] [27] for multi-user downlinks with in?nite
backlog. A downlink with randomly arriving traf?c and peak
and average power constraints is considered in [13] using
a theory of Lyapunov drift, although the algorithm requires
perfect knowledge of channel probabilities in order to meet
the average power requirement. Lyapunov theory can be used
to design stabilizing power allocation and routing algorithms
that do not require knowledge of arrival rates or channel
statistics in cases where there are only peak power constraints
on the wireless devices [22]. Historically, Lyapunov theory
has been extremely useful in the development of stable queue
controlpoliciesforradionetworksandswitchingsystems[14]-
[22]. However, there was previously no Lyapunov method for
performingqueueingnetworkoptimization(suchasstabilizing
a network with minimum average power).
In this paper, we develop a simple Lyapunov drift technique
that enables system stability and performance optimization
to be achieved simultaneously [2] [1] [30]. The technique
extends the Lyapunov methods of [14]-[22] and bridges the
gap between convex optimization theory and stochastic queue-
ing control problems. We note that alternative approaches
to stochastic network optimization have recently appeared
in [31] [32] [33] using ?uid model transformations and/or
stochastic gradient theory. Our Lyapunov technique is similar
to the notion of a stochastic gradient (see Chapters 4-5 of
[2] for a comparison between static gradient search methods
and Lyapunov scheduling), although it was developed from a
queueing stability perspective and yields explicit bounds on
average power and delay.
For simplicity of exposition and to highlight the issues of
powerallocation,inthe?rsthalfofthispaperweconsideronly
single-hop networks with no routing. The paper is organized
as follows: In the next section we consider a motivating
example of a 2-user wireless downlink. In Section III we
develop a control policy for minimizing average power for
one-hop networks. In Section IV we treat a related problem
of maximizing throughput subject to peak and average power
constraints (for cases when traf?c is either supportable or
insupportable). Extensions to multi-hop networks and mobile
networks are treated in Sections V and VI, and simulations
are presented in Section VII.
II. A SIMPLE EXAMPLE
To illustrate the decisions involved in energy-optimal
scheduling, we consider the following example of a two-queue
wireless downlink, where a single node (labeled ‘node 0’)
transmits data to two different stations over downlink channels
1 and 2 (as in Fig. 1 in the case when only node 0 is active).
The system operates in slotted time, and every slot the channel
states are measured, power allocation decisions are made, and
new arrivals are queued according to their destinations.
Let U
1
(t) and U
2
(t) represent the current backlog queued
for transmission to destinations 1 and 2, respectively, and
consider the decision of whether or not to allocate power to
channel 1. Clearly no power should be allocated if U
1
(t) = 0.
When U
1
(t) > 0, we must decide whether to allocate power
on the current slot or wait for a more energy-ef?cient future
channel state. In this example, we consider only ON/OFF
power constraints and assume that either no power is allocated
to any channel, or full power of 1 Watt is allocated to either
channel 1 or channel 2. Link conditions for each channel 1
IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 52, NO. 7, JULY 2006 3
t 0 1 2 3 4 5 6 7 8
Arrivals A
1
(t) 3 0 3 0 0 1 0 1 0
A
2
(t) 2 0 1 0 1 1 0 0 0
Channels S
1
(t) G G M M G G M M G
S
2
(t) M M B M B M B G B
Max U
i
µ
i
U
1
(t) 0 3 0 3 1 0 1 1 2
Policy U
2
(t) 0 2 2 2 2 3 2 1 0
Better U
1
(t) 0 3 3 6 6 3 1 1 2
Choices U
2
(t) 0 2 2 3 1 2 3 3 0
Fig. 2. An example set of arrivals, channel conditions, and queue backlogs
for a two queue wireless downlink under two different scheduling algorithms,
illustrating the power ef?ciency gains enabled by having full knowledge of
future arrivals and channel states.
and 2 vary between ‘Good,’ ‘Medium,’ and ‘Bad’ states:
(P
1
(t),P
2
(t))? ?
M
=
{(0,0),(1,0),(0,1)}
S
1
(t),S
2
(t)?{G,M,B}
Assume identical rate functions for i = 1,2, given by:
µ
i
(0,S
i
) = 0 units/slot for all S
i
?{G,M,B}
µ
i
(1,G) = 3,µ
i
(1,M) = 2,µ
i
(1,B) = 1 (units/slot)
That is, a link can transmit 3 units of data in the ‘Good’ state,
2 units in the ‘Medium’ state, and 1 in the ‘Bad’ state.
Let A
1
(t) and A
2
(t) represent the number of new data
units arriving during slot t and destined for nodes 1 and
2, respectively. Queueing dynamics proceed according to the
equation:
U
i
(t+1) = max[U
i
(t)-µ
i
(P
i
(t),S
i
(t)),0]+A
i
(t)
SupposearrivalsA
i
(t)andchannelstatesS
i
(t)forthe?rst9
timeslotst?{0,...,8}areasgiveninFig.2,andconsiderthe
policy of allocating power to the channel with the largest rate-
backlogproductU
i
(t)µ
i
(1,S
i
(t)).Thispolicycanbeshownto
stabilizethesystemwheneverpossible[15][19][21],although
it is not necessarily energy-ef?cient. According to the ?gure,
both queues are empty at time t = 0 when arrivals enter the
system according to vector (A
1
(0),A
2
(0)) = (3,2), resulting
in a backlog vector (U
1
(1),U
2
(1)) = (3,2) at the beginning
of slot 1. Because the channel states at slot 1 are given
by (S
1
(1),S
2
(1)) = (G,M), the rate-backlog indices for
channels 1 and 2 at slot 1 are given byU
1
(t)µ
1
(1,S
1
(t)) = 9,
U
2
(t)µ
2
(1,S
2
(t)) = 4, so that the MaxU
i
µ
i
policy places full
power to channel 1 (as indicated by the boxed values in the
?gure).
Because there were no new arrivals during slot 1, the result-
ing backlog vector at time t = 2 is given by (U
1
(t),U
2
(t)) =
(0,2), as shown in the ?gure. The policy proceeds by ex-
pending 1 Watt of power for time t ? {1,...,8}, and the
scheduling decision at slot t = 8 will leave the system again
empty at time t = 9. If the same arrival and channel patterns
were extended periodically every 9 timeslots, the Max U
i
µ
i
policy would allocate 1 Watt of power 8 timeslots out of every
9, yielding a time average power consumption of P
av
= 8/9
Watt. Similar power consumption levels are observed when
the policy is simulated for random arrivals and channel states
with the same steady state distributions as this example (see
Section VII).
Now consider the alternate policy of waiting until slot 3 to
allocate power, and then making decisions as shown in the
?gure. These decisions also leave the system empty at slot 9,
but yield an average power expenditure of P
av
= 5/9 Watt
over the 9 slot interval. Average power can be further reduced
if channel states and arrivals are extended periodically (or
probabilistically) over the in?nite time horizon, and it can be
shown that the minimum average power required to stabilize
such a system is given by P
*
av
= 0.518.
The above example illustrates the energy gains available
by more intelligent scheduling. In cases where power can be
allocated as a continuous variable, more complex decisions
are involved: Should we exploit better channel states by
transmitting at higher data rates with the same power level, or
by transmitting at the same data rate with reduced power? In
thenextsection,wedevelopasimpledecisionmakingstrategy
that does not require knowledge of future events, traf?c rates,
or channel statistics, yet yields an average power expenditure
that is arbitrarily close to optimal.
III. SINGLE HOP NETWORKS
ConsiderthewirelessnetworkofFig.1withN nodesandL
links, where each link corresponds to a directed transmission
from one node to another. Packets randomly arrive to the
system and are queued according to their destinations. This is
a single-hop network, and hence incoming data is associated
with a particular transmission link l ? {1,...,L} and is
assumed to leave the network once it is transmitted. Let A
l
(t)
represent the amount of bits arriving for transmission over
link l during slot t, and let U
l
(t) represent the current queue
backlog (or ‘un?nished work’) in queue l. Let
~
S(t) and
~
P(t)
represent the L-dimensional vectors of channel states and
power allocations. In vector notation, the queueing dynamics
are:
~
U(t+1) = max[
~
U(t)-~ µ(
~
P(t),
~
S(t)),0]+
~
A(t) (1)
where ~ µ(
~
P,
~
S) is the rate function associated with the given
physical layer modulation and coding strategies used for
wireless communication.
We assume that there are a ?nite number of channel state
vectors
~
S, and that ~ µ(
~
P,
~
S) is a continuous function of the
power vector
~
P for each channel state
~
S.
2
Every timeslot
a power vector
~
P(t) is chosen in reaction to queue backlog
and current channel conditions, subject to the constraint that
~
P(t) ? ? for all t, where ? is a compact set of acceptable
power vectors. Throughout this paper, we use these general
rate functions and set constraints to present our main re-
sults. However, in all examples of distributed implementation,
we assume the rate function has the structure: ~ µ(
~
P,
~
S) =
(µ
1
(P
1
,S
1
),...,µ
L
(P
L
,S
L
)). Further, in our examples we
assume that ? consists of all vectors
~
P satisfying the cell-
partition constraint (i.e., that if P
l
> 0 for some link l, then
P
˜
l
= 0 for all
˜
l6=l satisfying cell(tran(l)) =cell(tran(
˜
l))),
2
Our results hold more generally for any (potentially discontinuous) rate-
power curve that satis?es the upper semi-continuity property [2].
IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 52, NO. 7, JULY 2006 4
and such that each entry P
l
is limited by a peak value
P
peak
according to either the continuous power constraint
0 = P
l
= P
peak
or the discrete ON/OFF power constraint
P
l
?{0,P
peak
}.
A. Minimum Power For Stability
Here we characterize the minimum average power required
to stabilize the system. We begin with a precise de?nition of
stability in terms of the over?ow function g(M) associated
with a queue with un?nished work process U(t):
g(M)
M
=
limsup
t?8
1
t
t
X
t=0
Pr[U(t)>M]
The function g(M) represents the largest limiting fraction of
time the un?nished work is above the value M.
De?nition 1: A queue with un?nished work process U(t)
is stable if g(M)? 0 as M ?8. A network of queues is
stable if all individual queues are stable.
Inthespecialcasewhenqueuebacklogevolvesaccordingto
an ergodic Markov chain with a countably in?nite state space,
then this notion of stability is equivalent to the existence of
a steady state probability distribution for the chain. However,
the above stability de?nition is more general in that it does
not require a countably in?nite state space, nor does it require
ergodicity. A more detailed discussion of stability issues is
given in [34] [35] [2].
Assume that inputs and channel processes are ergodic with
arrival rates
~
? = (?
l
) and channel probabilities p
~
S
. In [2],
the network capacity region ? is de?ned as the closure of
the set of all rate vectors stabilizable under some power
allocation algorithm that conforms to the power constraint
~
P(t) ? ?. The following theorem speci?es the minimum
average power required for network stability, among the class
of all algorithms with complete knowledge of future events.
Theorem 1: (Minimum Power for Stability) If the network
is stabilizable (so that
~
?? ?), the minimum power required
for stability is given by P
*
av
, where P
*
av
is the solution to the
following nonlinear optimization problem (de?ned in terms of
auxiliary probability variables a
~
S
k
and power vectors
~
P
~
S
k
for
all
~
S and for k?{1,2,...}):
Minimize: P
av
=
P
~
S
p
~
S
P
8
k=1
a
~
S
k
~
1
0
~
P
~
S
k
Subject to: ~ µ
av
M
=
P
~
S
p
~
S
P
8
k=1
a
~
S
k
~ µ(
~
P
~
S
k
,
~
S)=
~
?
~
P
~
S
k
? ?,a
~
S
k
= 0 for all k,
~
S
P
L+2
k=1
a
~
S
k
= 1 for all
~
S
Further, the value of P
*
av
is unchanged if the optimization
problem above is restricted to use at most L + 2 auxiliary
variables a
~
S
k
and
~
P
~
S
k
for any channel state
~
S.
The theorem indicates that minimum power for stability is
achieved among the class of stationary policies that measure
the current channel state
~
S(t) and then randomly allocate
a power vector
~
P
~
S
k
with probability a
~
S
k
. This minimum is
attained by a particular policy because the number of channel
states is ?nite and the power set ? is compact. The value of
P
*
av
is the resulting average power of this stationary policy,
and ~ µ
av
is the resulting time average transmission rate vector.
This is expressed in the following corollary to Theorem 1.
Corollary 1: Ifchannelstates
~
S(t)arei.i.d.overslots,min-
imum power for stability is given by the valueP
*
av
, minimized
over the class of all stationary randomized algorithms that
make decisions based only on the current channel state
~
S(t),
and yielding for all timeslots t:
X
l
E{P
l
(t)|H(t)} =P
*
av
~ µ
av
M
=
E
n
~ µ

~
P(t),
~
S(t)

|H(t)
o
=
~
? (2)
whereH(t)representsthehistoryofpastchannelstatesduring
slots t ?{0,1,...,t-1}.
As the corollary assumes channel states are i.i.d. over slots,
the above expectation is the same for all slots t. Theorem 1 is
proven via the following two claims: (Claim 1) No algorithm
can achieve stability with a smaller average power P
*
av
, and
(Claim 2) any rate vector
~
? strictly interior to ? can be
stabilized with an average power that is arbitrarily close to
P
*
av
. Claim 1 is proven in Appendix A by extending the
dimensionality of the system from L to L+1 and applying
Caratheodory’s Theorem [28] (where the k?{1,...,L+2}
result is also obtained). Below we prove Claim 2:
Proof: (Claim 2) The network capacity region ? is proven
in [2] to consist of all rate vectors
~
? such that a stationary
power allocation rule exists satisfying (2). The value ofP
*
av
is
by de?nition the average power consumption, minimized over
all such stationary rules. If
~
? is strictly interior to ?, there
exists a positive value  such that
~
?+~ ? ? (where ~  is the
L-dimensional vector with all entries equal to ). It follows
that there exists a stationary power allocation rule satisfying:
E
n
~ µ

~
P(t),
~
S(t)
o
=
~
?+~ >
~
?
and we de?ne P
*
av
() as the minimum average power con-
sumed by any such stationary policy. The time average trans-
mission rate of each queue is strictly larger than the arrival
rate, and hence the network is stable [2]. This holds for
arbitrarily small values of . Furthermore, it is not dif?cult
to show:
3
P
*
av
=P
*
av
()=

1-


max

P
*
av
+


max
P
*
av
(
max
)
where 
max
is the largest scalar such that (?
l
+
max
)? ?. It
follows that P
*
av
()? P
*
av
as ? 0, so that stability can be
attained with power that is arbitrarily close to P
*
av
.
We note that the concept of randomization used in Theorem
1 is vitally important to treat the general case where the
set {~ µ(
~
P,
~
S)|
~
P ? ?} is not necessarily convex. Otherwise,
optimality can be achieved by a strategy that allocates a ?xed
power vector
~
P
~
S
whenever the channel is in state
~
S. Note
that even if there are only two possible channel states for
every link, the total number of channel state vectors is 2
L
.
Thus,whiletheabovestaticoptimizationde?nestheminimum
3
The right hand side of the inequality follows by noting P
*
av
() is less than
or equal to the average power associated with the mixed strategy that uses
the P
*
av
strategy with probability 1-/max and the Pav(max) strategy
with probability /max.
IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 52, NO. 7, JULY 2006 5
power level P
*
av
, it is not practical to envision solving the
optimization via standard techniques, even if the channel
state probabilities p
~
S
are fully known. In the next section
we overcome this problem by developing a novel stochastic
optimization technique.
B. An Energy-Optimal Control Algorithm
Here we develop a practical control algorithm that stabilizes
the system and expends an average power that is arbitrarily
close to the minimum power solution P
*
av
. For simplicity
of exposition, we assume the arrival vectors
~
A(t) are i.i.d.
over timeslots with arrival rate E{
~
A(t)} =
~
?, and that the
channelstatevectors
~
S(t)arei.i.d.overtimeslotswithchannel
probabilities p
~
S
.
4
The algorithm below uses an arbitrary
control parameter V > 0 that affects a tradeoff in average
queueing delay.
Energy-Ef?cient Control Algorithm (EECA) : Every times-
lot, observe the current levels of queue backlog
~
U(t) and
channel states
~
S(t) and allocate a power vector
~
P(t) =
(P
1
,...,P
L
) according to the following optimization:
Maximize:
P
L
l=1
h
2U
l
(t)µ
l
(
~
P,
~
S(t))-VP
l
i
(3)
Subject to:
~
P = (P
1
,...,P
L
)? ?
The EECA algorithm is similar to the power allocation
algorithm of maximizing
P
l
U
l
µ
l
(
~
P,
~
S) [21] [15] [19], with
the exception that the optimization metric is modi?ed by a
weighted power term-VP
l
for each linkl. It is interesting to
note that the resulting metric is similar to the index policy of
[27] developed for minimizing power in a system with in?nite
backlog and no queueing. However, the “index” that is used
in [27] is a constant Lagrange multiplier that is pre-computed
based on channel probability information, while our “index”
includes a dynamic queue stateU
l
(t) that is updated from slot
to slot but requires no pre-computation or a-priori statistical
knowledge.
Distributed Implementation: For cell-partitioned networks,
we have ~ µ(
~
P,
~
S) = (µ
1
(P
1
,S
1
),...,µ
L
(P
L
,S
L
)). In this
case, the above optimization is implemented according to the
following simple algorithm: Each node measures the channel
state S
l
(t) for each of its own outgoing links l and computes
a quality value Q
l
, where Q
l
is the maximum value of
2U
l
(t)µ
l
(P
l
,S
l
(t))-VP
l
over either the continuous interval
0= P
l
= P
peak
or the 2-valued set P
l
?{0,P
peak
}. De?ne
˜
P
l
as the quality maximizing power level for linkl. De?ne O
n
as the set of links l?{1,...,L} such that tran(l) =n. Each
node n then computes l
*
n
and Q
*
n
, de?ned as follows:
l
*
n
M
=
argmax
l?On
Q
l
, Q
*
n
M
=
Q
l
*
n
The value of Q
*
n
is the contribution that node n brings to the
summation in (3) if it is chosen for transmission. Each node
then broadcasts its value of Q
*
n
to all other nodes in its cell,
and the node n with the largest Q
*
n
is selected to transmit in
4
We note that the i.i.d. assumptions are not necessary, and the same
algorithms can be used for general ergodic arrivals and channels, resulting
in modi?ed but more involved delay expressions [2].
that cell (ties are broken arbitrarily). Transmission takes place
over link l = l
*
n
, with power level
˜
P
l
. In cases where each
cell can support more than one transmission, the algorithm is
simply implemented by selecting the set of nodes with the
largest quality metrics.
Example 1: Under the ON/OFF constraint P
l
?{0,P
peak
},
the power
˜
P
l
for each link l is given by:
˜
P
l
=

P
peak
if 2U
l
(t)µ
l
(P
peak
,S
l
(t))>VP
peak
0 else
In this case, we see that power is allocated only when the
backlog exceeds a channel state dependent threshold.
Example 2: Suppose we have a continuous constraint 0=
P
l
=P
peak
and that rate functions have a logarithmic pro?le:
µ
l
(P,S) = log(1 +?
S
P), where ?
S
is an attenuation/noise
coef?cient associated with channel state S. In this case, the
optimal power level is a continuous function of the queue
backlog. Indeed, for any link l with channel state S
l
(t) = S
and queue backlog U
l
(t) = U, the quality maximizer
˜
P
l
is a
critical point of 2Uµ
l
(P,S)-VP over the interval 0=P =
P
peak
. Differentiating with respect to power, we have:
d
dP
[2Uµ
l
(P,S)-VP] =
2U?
S
1+?
S
P
-V
and it easily follows that:
˜
P
l
= min

max

2U
l
(t)
V
-
1
?
S
l
(t)
,0

,P
peak


To evaluate the above algorithm, de?ne A
2
max
, µ
out
max
, and
B as follows:
A
2
max
M
=
max
n
X
l?On
E

A
2
l
	
µ
out
max
M
=
max
{n,
~
S,
~
P??}
X
l?On
µ
l
(
~
P,
~
S)
B
M
=
A
2
max
+(µ
out
max
)
2
(4)
Now assume that
~
? is strictly interior to the network capacity
region ?, and de?ne the scalar value
max
as the largest value
that can be added to each component of
~
? so that the resulting
vector is still within the capacity region, i.e., (?
l
+
max
)? ?.
Theorem 2: If
~
? is strictly interior to ?, then the EECA
algorithm with any V > 0 stabilizes the system, with a
resulting average congestion bound given by:
X
l
U
l
M
=
limsup
t?8
1
t
t-1
X
t=0
"
X
l
E{U
l
(t)}
#
=
BN +VNP
peak
2
max
Furthermore, average power P
av
is given by:
P
av
M
=
limsup
t?8
1
t
t-1
X
t=0
"
X
l
E{P
l
(t)}
#
=P
*
av
+BN/V
whereP
*
av
is the minimum power solution of the optimization
in Theorem 1.
Thus, theV parameter can be chosen so thatBN/V is arbi-
trarily small, yielding average power that is arbitrarily close to
the optimum. However, the congestion bound grows linearly
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!