{'fraction_non_alphanumeric': 0.06245021850041978, 'fraction_numerical': 0.015155103007340753, 'mean_word_length': 4.054292242411054, 'pattern_counts': {'":': 0, '<': 30, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 22, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Energy-Efficient Resource Allocation in Time Division Multiple-Access over Fading Channels

We investigate energy-efficiency issues and resource allocation policies for time division multi-access (TDMA) over fading channels in the power-limited regime. Supposing that the channels are frequency-flat block-fading and transmitters have full or quantized channel state information (CSI), we first minimize power under a weighted sum-rate constraint and show that the optimal rate and time allocation policies can be obtained by water-filling over realizations of convex envelopes of the minima for cost-reward functions. We then address a related minimization under individual rate constraints and derive the optimal allocation policies via greedy water-filling. Using water-filling across frequencies and fading states, we also extend our results to frequency-selective channels. Our approaches not only provide fundamental power limits when each user can support an infinite number of capacity-achieving codebooks, but also yield guidelines for practical designs where users can only support a finite number of adaptive modulation and coding (AMC) modes with prescribed symbol error probabilities, and also for systems where only discrete-time allocations are allowed.


I. INTRODUCTION
With battery operated communicating nodes, energy efficiency has emerged as a critical issue in both commercial and tactical radios designed to extend battery lifetime, especially for wireless networks of sensors equipped with non-rechargeable batteries. Because the energy required to transmit a certain amount of information is an increasing and strictly convex function of the transmission rate [1], energy-efficient resource allocation has attracted growing attention [2]- [8].
Among them, [2], [3], [4], [5] dealt with energy-efficient designs based on packet arrival and delay constraints over additive white Gaussian noise (AWGN) channels; while [6] and [7] considered energy-efficient scheduling for time division multi-access (TDMA) networks over fading channels, where the data of each user must be transmitted by a given deadline. Recently, [8] minimized transmit power of orthogonal frequency-division multiplexing (OFDM) systems using quantized channel state information (CSI) of the underlying fading channel.
Resource allocation for fading channels also remains a popular topic in information theoretic studies. However, optimization has been typically carried out to maximize rate (achieve capacity) subject to average power constraints. Assuming that both transmitters and receivers have available perfect CSI, Tse and Hanly derived the ergodic capacity [9] as well as the delay-limited capacity regions [10] along with the optimal power allocation for fading multi-access channels, while Li and Goldsmith found the ergodic [11] and outage capacity regions [12] as well as optimal resource allocation policies for code division (CD), time division (TD) and frequency division (FD) fading broadcast channels. As regarding delay-limited capacity (a.k.a. "zero-outage capacity"), [13] and [14] extended the results of [10], to characterize the outage capacity regions for single-user fading channels and multi-access fading channels, respectively.
In this paper, we re-consider these information theoretic results pertaining to rate efficiency and investigate optimal resource allocation for fading channels from an energy efficiency perspective.
Specifically, we seek to minimize energy/power cost under average rate constraints for TDMA fading channels, given perfect or quantized CSI, at the transmit-and receive-ends. As stated in [11], TD and FD are equivalent in the sense that they exhibit identical ergodic capacity regions and corresponding optimal resource allocation policies. Thus, our results apply also to FDMA fading channels. Unlike [2]- [7], we do not impose delay constraints in our energy minimization problems.
We first study the problem of minimizing total power given a weighted average sum-rate constraint for the block flat-fading TDMA channel (Section III). This is dual to [11], where rate was maximized under a sum-power constraint. Note that we impose a weighted sum-rate constraint for the multi-access channels while [11] consider the sum-power constraint for the broadcast channel.
We then optimize energy-efficiency when each user can only support a finite number of adaptive modulation and coding (AMC) modes. The second problem we consider is power minimization under individual rate constraints, which is the general case for multi-access channels (Section IV).
Rate maximization under individual power constraints has been addressed via superposition coding and successive decoding in [9] and [10]. Here we formulate and solve energy minimization under individual rate constraints for TDMA when users have infinite-codebooks, or, a finite number of AMC-modes which requires only quantized CSI to be fed back from the receiver to the transmitters.
Section VI provides some numerical results, followed by the conclusions of this paper.

II. MODELING PRELIMINARIES
We consider a set of K users linked wirelessly to a single access point and adopt a discrete-time multi-access Gaussian channel model as in [9], [14]: where x k (n) and h k (n) are the transmitted signal and the fading process of the kth user, respectively, and z(n) denotes AWGN with variance σ 2 . Different from [9] and [14], we confine ourselves to TDMA where each user transmits in a dedicated time fraction, not overlapping with other users; i.e., when x k (n) = 0 in (1), we have x i (n) = 0 for ∀i = k. We also assume that the fading processes of all users are jointly stationary and ergodic, with continuous stationary distribution. 1 The joint fading process is slowly time-varying relative to the codeword's length, and adheres to a block fading channel model, which remains constant for a time block T , but is allowed to change in an independent identically distributed (i.i.d.) fashion from block to block. This is a valid model for ideally interleaved TDMA or packet-based access where each data frame "sees" an independent channel realization which remains constant within each frame [15,Chapter 2].  1 As with [14], our analysis can be easily extended to discrete distributions.

III. WEIGHTED SUM AVERAGE RATE CONSTRAINT
We first consider the problem of minimizing total power given a weighted sum average rate constraint. Such a constraint may arise in a wireless sensor network, where the fusion center requires an aggregate rateR to perform a certain task (e.g., distributed estimation) using data from different users with different reward weights. Given a rate allocation policy r(·) and a time allocation policy τ (·), let τ k (h) and r k (h) denote the time fraction allocated to user k and the corresponding transmission rate during τ k (h). Taking into account that user k does not transmit over the remaining 1 − τ k (h) fraction of time, the kth user's overall transmission rate per block is τ k (h)r k (h). If w := [w 1 , . . . , w K ] T collects the rate reward weights assigned to the K users, we let F w denote the set of all possible rate and time allocation policies satisfying the average rate Clearly, using transmit power p k (h) during τ k (h) fraction of time in any given block, user k can theoretically transmit with arbitrarily small error a number of bits/sec up to the Shannon capacity where B is the system bandwidth. Without loss of generality (w.l.o.g.), we assume henceforth that B = 1 and σ 2 = 1. Again, notice that with allocated time fraction τ k (h), the kth user's overall transmit power per block is P k (h) = τ k (h)p k (h) since no power is used for 1 − τ k (h) fraction of time.
WithP k := E h [P k (h)],p := [P 1 , . . . ,P K ] T and in accordance with the definition of the ergodic capacity region, we define a power region as follows.

Definition 1:
The power region for the TDMA fading channel when transmitters and the receiver have perfect CSI, is given by where P T D (r(·), τ (·)) = p : If the block length is sufficiently large and the users are allowed to use different codewords for different fading states, it is easy to show that everyp ∈ P(R) is feasible. Moreover, by the time-sharing argument, we can show that the K-dimensional power region P(R) is convex inp (the proof mimics the steps in capacity region derivations [9], [11], and is omitted for brevity).
Supposing that we assign to users different weights µ := [µ 1 , . . . , µ K ] T ≥ 0, the energy-efficient resource allocation problem can be formulated as Its solutionp yields the optimal rate and time allocation policies, and lies on the boundary surface of P(R) due to its convexity. By solving (4) for all µ ≥ 0, we can determine all the boundary points, and thus the entire power region P(R). When one or more of the entries of µ are zero, the solution to (4) corresponds to an extreme point of the boundary surface of P(R). By letting some of the weights approach 0, we can get arbitrarily close to these extreme points. One can refer to [9], [10], [11], [12], [14] for the explicit characterization of the extreme points.

A. Full CSI and Infinite-Codebooks
When a user can vary its codebook according to each fading state, the boundary of P(R) is feasible. Therefore, the problem (4) can be rewritten as Using the Lagrange multiplier approach, we can decompose (6) into two sub-problems.
1) Given what we term the total rate-reward R(h) := K k=1 w k τ k (h)r k (h) assigned to the K users, we determine how to distribute R(h) among users so that the total power cost in a fixed state h is minimized. That is, we solve Upon defining the rate-reward for user k as R k (h) := w k r k (h) and the corresponding power-cost∼rate-reward (C∼R) function we can rewrite (6) as 2) Having obtained J(·) in (8), we optimize the allocation of R(h) across the realizations of h, so that the total power cost averaged over all fading states is minimized; that is where λ denotes the associated Lagrange multiplier.
To gain insight, we first solve (8) and (9) for two-users before generalizing to K-users.

1) Two-User
Case: With f 1 (x) and f 2 (x) denoting the C∼R functions corresponding to users 1 and 2, we first establish following lemma.
Lemma 1: Supposing w.l.o.g. that w 1 < w 2 , it holds that: where v 0 is the unique solution to the equation f 2 (x) = f 1 (x).
When w 1 < w 2 , Lemma 1 asserts that if µ 1 w 1 h 1 ≥ µ 2 w 2 h 2 , the C∼R curve f 1 (x) of user 1 stays always above f 2 (x). If µ 1 w 1 h 1 < µ 2 w 2 h 2 , the two C∼R curves cross each other once at v 0 , as shown in Fig. 1 Using Lemma 1, we can characterize J(R(h)) in (8) as follows.
Lemma 2: For K = 2 and w 1 < w 2 , the solution to (8) is: and s 0 (h) is the solution of the equation i.e., g(s 0 (h), h) = 0. The minimum cost J(R(h)) is then achieved with these policies: Proof: See Appendix A2.
Lemma 2 specifies the optimal power cost curve J(R(h)) for each fading state h when w 1 < w 2 .
) is simply f 2 (R(h)); otherwise, J(R(h)) comprises part of the f 1 (R(h)) curve, the tangent line, and part of the f 2 (R(h)) curve, as indicated in Fig. 1. Having obtained J(R(h)), we now solve (9) to obtain the optimal resource allocation policies.
Theorem 1: For K = 2 and w 1 < w 2 , the optimal rate and time allocation policies with respect to the minimization problem (4) are as follows: 2) If µ 1 w 1 h 1 < µ 2 w 2 h 2 , and ξ := ((w 1 h 1 )/(ln 2µ 1 )) w 1 c) if λ * > ξ and g(λ * , h) = 0, then for an arbitrary Function g(x, h) is given by (13), and λ * , τ * 0 are obtained numerically by satisfying the weighted Note that depending on λ * , water-filling in (17)- (20) may result in zero transmission rate for the user which has been assigned the entire or part of the block. Therefore, for some fading states where the channel is really bad, both users should defer. Comparing (8) and (9) with [11, eqs. (11), (13)], we find that our power minimization yields similar "opportunistic" policies as the rate maximization in [11].
Since τ * 0 can take any arbitrary value between 0 and 1, the solution in (20) is not unique. However, under the assumption of continuous joint fading distribution density, the probability of g(λ * , h) = 0 is zero, and therefore case c) is an event of measure zero. Thus, after setting τ * 0 to an arbitrary value in [0,1], λ * can be uniquely determined by an one-dimensional, e.g., bi-sectional, search. From Theorem 1, it is clear that in order to achieve energy efficiency over TDMA fading channels, most of the time we should allow one user to transmit per block. This also holds true in rate maximization for TDMA fading channels [11], even though the resultant time and rate allocation fractions are different.
To extend our two-user results to K > 2 users, we will need definition of the convex envelope.
Namely, f c (x) is the boundary surface of the convex hull of the function's epigraph [16].
Using the definitionf(x) := min 1≤k≤K f k (x), we can verify the following property:

Proposition 1:
The optimal C∼R function J(R(h)) in (8) is the convex envelope off (R(h)) in the two-user case; i.e., J(R(h)) =f c (R(h)) as determined by Lemma 2 and Definition 2.
then it is easy to show that J(R(h)) is convex since it has non-decreasing first derivatives for all R(h) ≥ 0. If the convex envelopē f c (R(h)) were not given by J(R(h)), thenf c (R(h)) would be strictly greater than J(R(h)) for some R(h). Since the first and the third branches of J(R(h)) in (11) are exactlyf (R(h)), for can only be greater than J(R(h)) for R(h) ∈ (R a (h), R b (h)). But sincef c (R(h)) is convex, Jensen's inequality implies that its value for any R a (h) < R(h) < R b (h) can not be greater than the value given by the line segment connectingf (R a (h)) withf (R b (h)). This leads to a contradiction, and thus J(R(h)) =f c (R(h)).
2) K-Use Case: Generalizing Proposition 1 to K > 2 users, we can show that: Theorem 2: For a K-user TDMA block fading channel, the optimal C∼R function J(R(h)) at each fading state h is the convex envelope off (R(h)) := min 1≤k≤K f k (R(h)), and the optimality is achieved by allowing at most two users to transmit per time block.
Proof: See Appendix C.
Although Theorem 2 asserts achievability of the optimal policies, it does not provide algorithms realizing these optimal allocation strategies. The latter are challenging since obtaining convex envelopes is generally difficult. As pointed out in [17], the rate-maximizing resource allocation for TD broadcast fading channels in [11] is obtained by water-filling across realizations of concave envelopes. Our energy-efficient resource allocation policies under a weighted sum average rate constraint for TDMA fading channels are obtained via water-filling across realizations of the convex envelopes J(R(h)). But in order to determine J(R(h)), we must generalize Lemma 2 to the K-user case. This is accomplished with the following algorithm.

S1) Remove the C∼R function of user
and f k (x) will not appear in the expression of J(R(h)) for the reasons we detailed in Lemma 2. Let K r be the number of users remaining after such a successive elimination of their C∼R functions from J(R(h)), and define the permutation π(·) such that w π(1) < w π(2) < · · · < w π(Kr) . Then through successive pairwise comparisons and user C∼R function removals, we can ensure that µ π(1) w π(1) h π(1) < µ π (2) w π(2) h π(2) < · · · < µ π(Kr ) w π(Kr ) h π(Kr ) . S2) Let the mth element of u be u m = π(1). If K r ≥ 2, go to Step 3. If K r < 2, all users with C∼R functions not appearing in J(R(h)) have been removed. Then set the number of active users be K 0 = m, s m = ∞, and stop.
Using Algorithm 1, we obtain u and s.
) comprises pieces of the curves {f um (·)} K 0 m=1 as well as the common tangent line segments between f um (·) and f u m+1 Arguing as in the proof of Proposition 1, it follows readily that J(R(h)) is the convex envelope off (R(h)). Once having J(R(h)), we will implement a water-filling strategy to obtain the energyefficient resource allocation across realizations of h. First, for any user k / ∈ u, we let τ * k (h) = 0 and r * k (h) = 0. The rate and time allocation for the remaining K 0 users is given as follows.
2) If K 0 > 1, set s 0 = 0. Since 0 = s 0 < s 1 < · · · < s K 0 = ∞, for the given λ * , there exists In this case, we set and and In eqs. (24)-(26), λ * and τ * 0 are chosen to satisfy the weighted sum-rate constraint Under the assumption of continuous joint fading distribution density, the value of τ * 0 does not affect the weighted sum-rate constraint, and λ * can be uniquely determined by an one-dimensional search, as in the two-user case. To achieve energy efficiency, we should only allow at most two users (and most of the time only one user) to transmit per time block in the K-user case. Again in (24)-(26), water-filling may result in zero transmission rate for the user which has been assigned the entire or part of the time block. For some fading states, when all channels are in deep fading, all users should defer. Also note that Algorithms 1 and 2 are dual to those in [11] for power minimization under an average sum-rate constraint.

B. Quantized CSI and Finite AMC Modes
In this section, we provide a novel formulation and solve the energy minimization problem under a weighted sum average rate constraint for the finite-AMC-mode case. In practice, a user may not be able to support an infinite number of codebooks. Moreover, the codewords in use may not be capacity-achieving. It is thus worth investigating energy-efficient resource allocation for practical systems where each user can only support a finite number of AMC modes. Notice that since transmitters can transmit with a finite number of AMC modes, only quantized CSI could be fed back from the access point to the transmitters suffices.
For user k ∈ [1, K], an AMC mode corresponds to a rate-power pair (ρ k,l , p k,l ), l = 1, . . . , M k , where M k denotes the number of AMC modes. A pair (ρ k,l , p k,l ) indicates that for transmission rate ρ k,l provided by the lth AMC mode, the minimum received power required is p k,l . Notice that the minimum power p k,l may not be given by 2 ρ k,l −1 as in the capacity-achieving case, and some extra power may be required in practice. Also, the rate ρ k,l is maintained with a prescribed symbol error probability (SEP), and p k,l is the corresponding minimum received power under the SEP constraint.
For this reason, we need to implicitly include the SEP constraints in our optimization. Although the kth user only supports M k AMC modes, this user can still support through time-sharing continuous rates up to a maximum value determined by the highest-rate AMC mode ρ k,M k .
By setting ρ k,0 = 0 and p k,0 = 0 and letting γ k,l := (p k,l − p k,l−1 )/(ρ k,l − ρ k,l−1 ), we define the piece-wise linear function relating transmit power with rate as Notice that in order to support rate ρ k,l with channel coefficient h k , the required transmit power is scaled as p k,l /h k . For practical modulation-coding schemes with e.g., M-QAM constellations and error-control codes, Υ k (r k (h)) is guaranteed to be convex [2]. Using (28) to replace the power-rate relationship implied by Shannon's capacity formula, we can define a power region as [c.f. (2), (3)] where It is easy to show that the K-dimensional P ′ (R) is feasible and convex. The optimization problem thus becomes We can rewrite (31) as As in the infinite-codebook case, we can still decompose (32) into two sub-problems. That is, we first optimize per fading realization, and then apply water-filling across J(R(h)) realizations to obtain the optimal resource allocation policies.
Having determined J(R(h)) as in (33), we implement water-filling across realizations of J(R(h)) to derive the optimal resource allocation policies. Different from the infinite-codebook case where all J(R(h)) have continuous slopes, here J(R(h)) are piecewise-linear. Therefore, water-filling should take into account the finite number of slopes of J(R(h)). A somewhat related problem was dealt with in [12], where water-filling over some piecewise-linear concave functions was used to determine the boundary surface of the outage probability region. But energy-efficient resource allocation policies for finite-AMC-modes were not considered in [11] and [12].
Recall that K 0 and all entries of s, r and c are functions of h. Since every point of the convex envelope J(R(h)) can be achieved by time-sharing between points (R m (h), C m (h)), finding the optimal resource allocation strategies is equivalent to solving the following minimization problem: (34) , and thus the optimal allocation policies τ * k (h) and r * k (h) (1 ≤ k ≤ K) for the original problem (31) as follows: ) belongs to users i * and j * , respectively, then and τ * k (h) = 0 and r * k (h) = 0, ∀k = i * , j * , 1 ≤ k ≤ K. Note that if m * = 1, we let user i * transmit with τ * 0 fraction of time and leave the channel idle for the remaining 1 − τ * 0 fraction of time. If i * = j * , then we let the same user transmit with two AMC modes, one for τ * 0 fraction and the other for 1 − τ * 0 fraction of time.
The results of Theorem 3 are analogous in form with those in [12,Theorem 3], which is a generalization of [13, Lemma 3]. But note that the latter deal with the delay-limited/outage capacity; while our results are for energy-efficient resource allocation using finite-AMC-modes, a subject not considered in [12], [13]. In Theorem 3, λ * is the water-filling level. For energy efficiency, we should let the first derivatives J (1) (R(h)) = λ * . However, since J(R(h)) entails a finite number of slopes, equality can not be always achieved. Thus, our strategy is to select the largest , since the user(s) transmit more efficiently than the required power level, we should allow transmission(s) with peak rate given by R m * (h)/w k * . When λ * = s m * (h), users transmit as efficiently as required; thus arbitrary time division suffices. When λ * < s 1 (h), no transmission can be carried out as efficiently as required, and all users defer during this fading state. As in the infinite-codebook case, we should allow at most two users to transmit per time block. However, here we also allow one user to transmit in a time-sharing fashion with two AMC modes during some time blocks.

C. Discrete-Time Allocation
So far we have derived energy-efficient resource allocation strategies under the assumption that the time fraction τ k assigned to each user can be any real number in [0,1]. In practical TDMA systems, time is usually divided with granularity of one time unit (slot), which is determined by the available bandwidth. Therefore, the transmission time assigned to each user per time block has to be an integer multiple of a "slot". Take the well-known GSM system as an example [15,Chapter 4]. In each narrowband channel of 200 KHz, time is divided into slots of length 577 µs and each uplink frame is shared by the users in a time-division manner, and consists of 8 slots.
Upon regarding an uplink frame as a frequency flat-fading time block, we can thus only assign each user a time fraction which is an integer multiple of 1/8. However, this extra discrete-time allocation constraint does not affect the derived energy-efficient allocation policies. In our policies, most of the time we should assign the entire time block to a single user. When we occasionally allow two users to transmit (or allow one user to transmit with two AMC modes), the time division between them can be arbitrary. Therefore, our energy-efficient policies can be easily adopted by practical systems which only allow discrete-time allocation among users.

IV. AVERAGE INDIVIDUAL-RATE CONSTRAINTS
In resource allocation for multi-access channels, other than a weighted average sum-rate constraint, a more general setting is when each user has an individual average rate requirement. We where P T D (r(·), τ (·)) is defined as in (3) The solutionp yielding the optimal rate and time allocation is on the boundary surface ofP(r) due to its convexity. By solving (39) for all µ ≥ 0, we determine all the boundary points, and thus the whole power regionP(r). Again, we will explicitly characterize the optimal resource allocation policies and the resultant boundary point for µ > 0. By letting some of the power cost weights approach 0, we can get arbitrarily close to the extreme points.

A. Infinite-Codebooks
When the user can utilize an infinite number of codebooks to achieve channel capacity per fading state, the optimization in (39) is equivalent to The counterpart of Theorem 2 in this case is given by: Theorem 4: For any µ > 0, there exists a λ * := [λ * 1 , . . . , λ * K ] T > 0, and optimal rate and time allocation policies r * (·) and τ * (·) in (40), such that for each h, r * (h) and τ * (h) solve . Moreover, we have r * (h) and τ * (h) as follows.
If we regard f k (r k,min (h)) as a channel quality indicator (the smaller the better) for user k, Theorem 4 asserts that for each time block, we should only allow the user with the "best" channel to transmit. When there are multiple users with "best" channels, arbitrary time division among them suffices. Therefore, our resource allocation strategies are "greedy" ones. Note that f k (r k,min (h)) contains λ * k . This implies that the user having smallest f k (r k,min (h)) actually has the rate-constraintcontrolled "best" channel.
Rate maximization under individual power constraints was pursued in [9], where it was shown that superposition codes and successive decoding should be employed and that greedy waterfilling based on a polymatroid structure provides the optimal resource allocation. In our powerefficient TDMA setting, we do not have such a polymatroid structure. Albeit in different forms than those in [9], our strategies can be also implemented through a greedy water-filling approach. To obtain the optimal allocation policies in Theorem 4, we need to calculate the Lagrange multiplier vector λ * . Although a K-dimensional search can be used to directly compute λ * from (44), it is computationally inefficient when K is large. Next, we show that an iterative algorithm from [9] can be adopted to calculate λ * . Before that, by the strict convexity of exponential functions and the fact that non-uniqueness of the time allocation τ * (·) occurs with probability 0 when F (h) is continuous, we can argue as in [9,Lemma 3.15] to establish the following lemma: To gain more insight, let us look at a special case where the fading processes of users are independent. If F k (·) stands for the cumulative distribution function (cdf) of user k's fading channel, ln 2µ i , and let s i,k (z) denote the solution to g i,k (x, z) := g i (x) − g k (z) = 0.

Corollary 1:
If the fading processes of users are independent, the optimal solutionp * to (39) for a given µ > 0 can be obtained as where the vector λ * is the unique solution to the equations Proof: By definition, we have and Since The corollary thus follows from (50) and (51).
What left to obtain the optimum {P * k } K k=1 , is to specify {λ * k } K k=1 . We accomplish this by modifying the corresponding iterative algorithm in [9].

Algorithm 4:
Let λ(0) > 0 be an arbitrary initial rate-reward vector. Given the lth iterate λ(l), the (l + 1)st iterate λ(l + 1) is calculated as follows. For each k ∈ [1, K], λ k (l + 1) is the unique rate-reward weight for the kth user such that the average rate of user k isR k under the optimal rate and time allocation policies, when the rate-reward weights of other users remain fixed at λ(l).

B. Finite AMC Modes
Next, we investigate optimal resource allocation under individual average rate constraints for the case when each user can only support a finite number of AMC modes. As in Sec. III-B, for user k ∈ [1, K], an AMC mode corresponds to a rate-power pair {(ρ k,l , p k,l )} M k l=1 , where M k is the number of AMC modes. By time-sharing, a user can support continuous rates up to a maximum value determined by the highest-rate AMC mode ρ k,M k . By defining Υ k (x) as in (28), the new power region is given byP where F ′ denotes the set of all possible rate and time allocation policies satisfying the individual rate constraints, and P ′ T D (r(·), τ (·)) is defined as in (30). It is easy to show that the region P ′ (r) is feasible and convex. The optimization problem thus becomes Using Υ k (x), problem (54) is equivalent to Since every point of Υ k (r k (h)) can be achieved by time-sharing between points (ρ k,l , p k,l /h k ), finding the optimal resource allocation strategies for (55) is equivalent to solving The counterpart of Theorem 3 under individual rate constraints is now: Theorem 6: Ifr is feasible ∀h, we have the optimal solutionτ * k,l (h) (k ∈ [1, K], l ∈ [0, M k ]) to (56), and subsequently the optimal allocation r * k (h) and τ * k (h) for (55) as follows. Given a positive λ * := [λ * 1 , . . . , λ * K ] T , for each fading state h, let l * k := max {l : µ k γ k,l /h k ≤ λ * k } (l * k = 0 if no such l) and C k,l := µ k p k,l /h k , and define ϕ k (h) : k=1 have a single minimum ϕ i (h), i.e., i = arg min k ϕ k (h), thenτ i,l * i = 1 and all otherτ k,l = 0. Consequently, and ∀k = i, k ∈ [1, K], r * k (h) = 0 and τ * k (h) = 0.
In (57) and (58), λ * and {τ * j } J j=1 should satisfy the individual rate constraints Moreover, λ * is almost surely unique and can be iteratively computed by Algorithm 4.
Proof: See Appendix G.
Theorem 6 shows that our policies with finite number of AMC-modes are still greedy ones.
For user k at fading state h, the C∼R function is given by f k (r k (h)) := µ k Υ k (r k (h)) − λ * k r k (h). It is clear that this function attains its minimum at ρ k,l * k . Then comparing the channel quality indicators ϕ k (h) for all the users, we determine which users have the "best" channel and assign resources accordingly. Note that when l * k = 0, the user should remain silent. If at a fading state, this user happens to have the "best" channel, we should let all users defer at this block. When achieves the minimum of f k (r k (h)). Although in Theorem 6 we let user k transmit (if permitted by the policies) with rate ρ k,l * k , the complete solutions should allow this user to transmit with arbitrary time-sharing between ρ k,l * k −1 and ρ k,l * k , as the optimization under a weighted sum-rate constraint in Theorem 3. Summarizing, our greedy polices may result in no transmissions, user(s) transmitting with one AMC mode, or user(s) transmitting in a time-sharing fashion with two AMC modes per fading block.
For the special case where the fading processes of users are independent, let s i,k (z) denote the is also a function of λ * i . Using Theorem 6 and mimicking the proof of Corollary 1, we can establish the following corollary.

Corollary 2:
If the fading processes of users are independent, the optimal solutionp * to (54) for a given µ > 0 can be obtained as where the vector λ * is the unique solution to the equations Some comments are now in order: 1) in the finite-AMC-mode case, the rate ρ k,l of user k is maintained with a prescribed SEP, and p k,l is the corresponding minimum received power under the SEP constraint; 2) our policies for the finite-AMC-mode case could only require quantized CSI at the transmitters; and 3) following the arguments of Sec. III-C, it is clear that the derived policies for infinite codebooks and finite number of AMC-modes apply to systems where only discrete-time allocations are allowed among users.

V. FREQUENCY SELECTIVE CHANNELS
The optimal resource allocation policies in the previous sections are derived for frequencyflat block fading channels encountered with narrow-band communications. In this section we extend our results to frequency-selective fading channels, which are often encountered in wide-band communication systems.
Supposing that the channel varies very slowly relative to the multipath delay spread, it can be decomposed into a set of parallel time-invariant Gaussian multi-access channels in the spectral domain [18]. We consider an K-user spectral Gaussian block fading TDMA channel with continu- , where frequency f ranges over the system bandwidth and ω is the fading state at a given time block. Let r k (f, ω) and τ k (f, ω) denote the rate and fraction of time allocated to user k at frequency f and fading state ω. For the weighted sum-rate constraint optimization, the constraint is now given by Let the set F w consist of all possible rate and time allocation policies satisfying (62), and take the infinite-codebook case for illustration. The power region for this TDMA channel is given by (r(·),τ(·))∈Fw For a finite number of AMC-modes and the individual rate constraint optimization, we can similarly define the corresponding power regions. Subsequently, the optimal resource allocation strategies can be obtained from the previous results by replacing the fading state h with the frequency and fading state pair (f, ω) to determine power regions for frequency-selective channels. That is, we should employ the previous allocation policies for each (f, ω), and then implement water-filling across both frequency f and fading state ω realizations to determine λ * (or vector λ * ).

VI. NUMERICAL RESULTS
In this section, we present numerical results of our energy-efficient resource allocation for a two-user Rayleigh flat-fading TDMA channel. The available system bandwidth is B = 100 KHz, and the AWGN has two-sided power spectral density N 0 Watts/Hz. The user fading processes are independent and the state h k , k = 1, 2, is subject to Rayleigh fading with meanh k . Clearly, the signal-to-noise ratio (SNR) for user k is defined ash k /(N 0 B).
2π)e −y 2 /2 dy is the Marcum's Q-function. From (64), we determine the rate-power pair {(ρ k,l , p k,l )} 3 l=1 for user k = 1, 2. The corresponding power regions I-IV under the constraints i)-iv) for this finite-AMC-mode case with prescribed SEP = 10 −3 are shown in Fig. 4. Similar trends as in Fig. 3 are observed. However, the power regions shrink since more power is required to achieve the same transmission rate in the finite-AMC-mode case relative to that in the infinite-codebook case. Supposingh 1 /(N 0 B) = 10 dBW andh 1 /(N 0 B) = 0 dBW, we also test our energy-efficient resource allocation under the same four sets of rate constraints i)-iv). The power regions for the infinite-codebook case and the finite-AMC-mode case are shown in Fig. 5 and Fig. 6, respectively.
Since the first user has a significantly better channel (i.e., higher SNR) than user 2, the required transmit power of user 1 is much lower than that of user 2 most of the time. Except this, the results are similar to those in Figs. 3 and 4.
We next compare the derived energy-efficient resource allocation with two alternative resource allocation policies. Policy A assigns equal time fractions to the two users per block. Then each user implements water-filling separately to adapt its transmission rate at each assigned time fraction. In policy B, each user is assigned equal time fraction and transmits with equal power per block. Fig. 7 depicts the power savings of our optimal policies under two different sets of rate constraints i) and iii), over the policies A and B for the infinite-codebook case when two users have identical SNRs.
It is seen that when the ratio of two users' power cost weights is far away 1, our optimal policies under a weighted sum-rate constraint can result in huge power savings (near 20 dB) over the other two sub-optimal polices. However, in this case the optimal policies under individual rate constraints only have a small advantage (around 3 dB) in power savings, over the sub-optimal policies. This is because with the weighted sum average rate constraint, we can employ more flexible policies in time and rate allocations. From Fig. 7, we also observe that the separate water-filling in policy A only achieves small power savings (less than 1 dB) over the equal power strategy in policy B. However, in this case separate water-filling in policy A achieves considerable power savings (4 dB) over the equal power strategy in policy B. Fig. 9 depicts similar power savings for the infinitecodebook case under two different sets of rate constraints ii) and iv), when two users have 10 dB in SNR difference. Similar observations are obtained. But note that the optimal policies under individual rate constraints can also achieve large power savings (near 9 dB), over the sub-optimal policies. In a nutsell, our energy-efficient resource allocation policies may indeed result in large power savings.

VII. CONCLUDING REMARKS
Given full or quantized CSI at the transmitters, we derived energy-efficient resource allocation strategies for TDMA fading channels. For energy minimization under a weighted average sum-rate constraint, the optimal allocation policies are given by water-filling over realizations of convex envelopes; whereas for energy minimization under average individual rate constraints, the optimal strategies perform greedy water-filling. Comparing these two strategies for two different optimizations, we find that the first approach requires one to characterize the convex envelope of the minima of C∼R functions per fading state, but the associated scalar Lagrange multiplier λ * can be easily obtained by one-dimensional search. Greedy water-filling simply computes and compares the channel quality indicator functions of individual users and then picks the user(s) with best channel(s) to transmit per block; however, we need to iteratively compute the associated vector Lagrange multiplier λ * (by Algorithm 4).
An interesting feature of our energy-efficient resource allocation strategies should be stressed.
According to our policies, we can let the access point (which naturally has full CSI) decide the time allocation and feed it back to users via uplink map messages, as in e.g., IEEE 802.16 systems [20].
Then given the Lagrange constant λ * (with the weighted sum-rate constraint) or vector λ * (with the individual rate constraints), the user only needs its own CSI to determine the transmission rate at the assigned time fraction. If uplink and downlink transmissions are operated in a timedivision duplexing (TDD) mode, the users can even obtain their own CSI without feedback from the access point. Together with the fact that the access point needs only a few bits to indicate the time allocation (since most of the time we should allow only one user to transmit), this feature is attractive from a practical implementation viewpoint.
As far as future work, it is interesting to study energy minimization over fading channels with delay constraint and/or using quantized CSI throughout. Our energy minimization for finite-AMC modes only requires quantized CSI feedback from the access point. And delay-constrained energy minimization may be seen as the dual problem of the delay-limited capacity maximization in [10].
Extensions to these two directions are currently under investigation. 2 where the last inequality is due to the convexity of f 2 (R), and the equalities are achieved when τ = 0, R 1 = 0 and R 2 = R. Inequality (68) clearly shows that the minimum in (8) is achieved; i.e., J(R) = f 2 (R).
2) When w 1 < w 2 and µ 1 w 1 h 1 < µ 2 w 2 h 2 , f 1 (R) and f 2 (R) intersect as depicted in Fig. 1. Similar to [11, Proof of Lemma 1], we can specify two points R a and R b such that f i.e., at these two points first-order derivatives of f 1 (R) and f 2 (R) are equal: The R a , R b expressions are obtained after solving (69) for R a and R b . Since s 0 is the slope of the common tangent line of the curves f 1 (R) and f 2 (R), we also have Solving (69) and (70), we obtain s 0 as the solution to g(x, h) = 0, where g(x, h) is given by (13), and R a and R b are as in (12). If 0 < R < R a or R > R b , then J(R) simply

B. Proof of Theorem 1
Let R * (h) denote the optimal total rate reward assigned to fading state h, and r * k (h) and τ * k (h) the corresponding optimal rate and time fraction allocated to user k = 1, 2. To solve (9), we rely on the Karush-Kuhn-Tucker (KKT) conditions [16,Chapter 5] (9) with respect to R(h) for a fixed h, only J (1) (R(h)) − λ survives since all R(h ′ ) for realizations h ′ = h are regarded as constants. We thus have at the optimum that if R * (h) > 0, 1) If µ 1 w 1 h 1 ≥ µ 2 w 2 h 2 , then J(R(h)) = f 2 (R(h)) from Lemma 2, and thus J (1) (R(h)) = ln 2µ 2 Substituting the latter into (71) and recalling that R(h) ≥ 0, we find which yields the optimal rate and time allocation in (17).
2) If µ 1 w 1 h 1 < µ 2 w 2 h 2 and we recall that s 0 is the slope of the straight line segment in Fig. 1, it follows from Lemma 2 that where R a , R b and s 0 are functions of h, given in Lemma 2. Now using (73), we arrive at: a) If λ * < s 0 , then J(R(h)) = f 1 (R(h)), and thus R * (h) = w 1 log λ * − log ln 2µ 1 which in turn yields the optimal rate and time allocation in (18).
c) If λ * = s 0 , then J(R(h)) = f 1 (R a ) + s 0 (R(h) − R a ), and R * (h) can be any value between R a and R b . In this case, we obtain the optimal rate and time allocation (20).

C. Proof of Theorem 2
Sincef(x) := min 1≤k≤K f k (x), it is easy to show that J(R(h)) := min By the definition of the convex envelopef c (x), we have where the last inequality is due to the convexity off c (x). From (76) and (77), it is clear that On the other hand, according to the definition off c (x), for any given R(h) there exists R a (h) Eq. (78) shows that we can achieve the equality J(R(h)) =f c (R(h)) by assigning to users i and j which satisfy f i (R a (h)) =f (R a (h)) and f j (R b (h)) =f (R b (h)). This completes the proof.

D. Proof of Theorem 3
Letting M := K k=1 M k , the value of K 0 per fading state may take any integer in [1, M]. We define H K 0 as the set of all fading states h for which Algorithm 3 yields K 0 ∈ [1, M]. We further set s K 0 +1 (h) = ∞, ∀λ > 0, and define for m = 0, 1, . . . , K 0 , the sets Then ∀λ > 0, sinceH 0 (K 0 , λ) = φ, we can express the set H of all possible fading states as Using the defined partitions H K 0 , we can rewrite (34) as If the optimization is feasible, we have It is easy to show that we can always achieve (37) although the solution for τ * 0 may not be unique. In the following, ∀K 0 ∈ [1, M] and ∀m ∈ [1, K 0 ], we drop the dependence ofτ m ,τ * m , R m , C m and s m on h for notational brevity. For K 0 ∈ [1, M] and ∀h ∈ H K 0 , we let Theτ * given by the theorem satisfies By the convexity of J(R(h)), we can easily show that 1) ∀h ∈ H 0 (K 0 , λ * ), since λ * < s 1 = C 1 /R 1 , we have from (88) that i.e., R i < C i /λ * . Then the first summand of the last equality in (87) will be Substituting (89), (91) and (92) into (87), we find Therefore, ∀τ =τ * , ifτ satisfies the total average-rate constraint Hence,τ * is the optimal solution to (34) and consequently the corresponding r * and τ * are the optimal solutions to (31).

E. Proof of Theorem 4
Following the Lagrange multiplier method, (40) is equivalent to Using the definition of f k (r k (h)), we can rewrite (95) as Due to the feasibility and convexity of the power regionP(r), the original problem (39) has a solution. Therefore, given any µ := [µ 1 , . . . , µ K ] T > 0, there exists a λ * := [λ * 1 , . . . , λ * K ] T > 0, as well as optimal rate and time allocation policies r(·) and τ (·) for (95). It is clear that we can again decompose (95) into two sub-problems. Given λ * , we first calculate r * k (h) and τ * k (h) by solving (41) and then we determine the water-filling level λ * by satisfying individual rate constraints.
Since f k (r k (h)) is convex in r k (h), it is easy to show that it attains its minimum at r k,min (h) = log λ * k − log ln 2µ k h k + . From the KKT conditions [16,Chapter 5], it follows that for τ * k (h) > 0, we should have r * k (h) = r k,min (h). Next, we show that a time allocation strategy τ (·) = τ * (·), excluding the arbitrary time sharing when functions f k (r k,min (h)) have multiple minima, is strictly suboptimal.
Let us first consider the two-user case.
Previous considerations show that the optimal resource allocation policies should follow Theorem 4 for the two-user case. Similar arguments extend readily to the general K-user case as well.

F. Proof of Theorem 5
i) From the optimal rate the time allocation policies, we can directly verify the following fact. For all k, if the kth component of λ increases while other components remain fixed, R k (λ) increases whereasR i (λ) decreases for i = k. More generally, for any subset K, if we increase λ k for all k ∈ K and hold the remaining λ i fixed,R i (λ) decreases for i ∈ K C , where superscript C here denotes set-complement.
iii) Upon defining the mapping Λ : λ(l) λ(l + 1), we can readily verify from Lemma 3 and i) that: a) The vector λ * is the unique fixed point of the mapping T .
Similar to Lemma 3, we can show that λ * is almost surely unique. Define G as the set of all feasible rate vectors. Ifr is feasible, there must be a boundary pointr g of G for whichr ≤r g . Let λ g denote the Lagrange multiplier corresponding tor g . Then for λ(0) ≤ λ g , there exists β ≥ λ(0) for whichr(β) ≥r. With this guarantee replacing the counterpart ii)-b) and following the lines in the proof of Theorem 5 (Appendix F), we can show that λ * can be iteratively computed by Algorithm 4 for any positive initialization λ(0) ≤ λ g . The functions f1(R), f2(R) and J(R) when w1 < w2 and µ 1 w 1 h 1 < µ 2 w 2 h 2 (the dash-dotted curve for J(R) is slightly offset for easy visualization).       weighted sum rate constraint:R=200 Kbits/sec, w1=1, w2=1 weighted sum rate constraint:R=200 Kbits/sec, w1=1, w2=2 individual rate constraints:R1=100 Kbits/sec,R2=100 Kbits/sec individual rate constraints:R1=100 Kbits/sec,R2=50 Kbits/sec     optimal policy under weighted sum rate constraint over policy A optimal policy under weighted sum rate constraint over policy B optimal policy under individual rate constraints over policy A optimal policy under individual rate constraints over policy B optimal policy under weighted sum rate constraint over policy A optimal policy under weighted sum rate constraint over policy B optimal policy under individual rate constraints over policy A optimal policy under individual rate constraints over policy B