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 linearlyRead More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!