Iterative Dynamic Water-filling for Fading Multiple-Access Channels with Energy Harvesting

I. INTRODUCTION

• The paper addresses a setting not covered by prior studies identified by the authors: fading channels with both finite battery capacity and maximum per-slot energy consumption constraints.Its dynamic water-filling algorithm maximizes the channel sum-rate under these constraints.Source: §I · p. 2
• The single-user dynamic water-filling algorithm is optimal, using energy wastage scheduling, battery depletion and full-charge points, then water-filling within the resulting segments.With unconstrained battery capacity and transmission power, it reduces to staircase water-filling with non-decreasing water levels over time slots.Source: §I · pp. 2–3

II. PROBLEM FORMULATION

• The model assumes non-causal knowledge of channel and energy-harvesting states across K slots, with finite battery capacity and maximum per-slot energy consumption.It considers N transmitters in a fading multiple-access channel; harvested energy and channel states are assumed to be perfectly estimated.Source: §I · p. 2, §II · pp. 4–5
• The maximum-sum-rate energy-scheduling problem is convex with O(NK) constraints, while a generic convex solver has complexity exponential in the number of constraints.The schedule includes both transmission and energy-wastage decisions.Source: §I · p. 3, §II · p. 5

I. INTRODUCTION

• O(NK^2) per iteration, one iteration is within (N-1)K/2 nats of optimal sum-rate, and simulations show convergence in only a few iterations.The iterative dynamic water-filling algorithm is designed for the multi-user case.Source: §I · p. 3

II. PROBLEM FORMULATION

• Finite battery capacity and maximum per-slot consumption can force harvested energy to be wasted when accumulated surplus exceeds what the battery can store.The formulation represents this energy wastage in the energy schedule.Source: §II · p. 5

III. DYNAMIC WATER-FILLING FOR SINGLE-USER CASE

• The single-user sum-rate objective is Cs(p) = sum over k of log(1 + pkHk).The section drops user subscripts for this case.Source: §III · p. 6
• The method first finds the optimal wastage schedule D*, then finds the optimal transmission schedule p* given D*; together they solve the single-user problem.The transmission schedule is subject to the constraints in (10), while the wastage schedule is subject to the constraints in (8).Source: §III · p. 6

A. The Optimal Wastage Schedule

• Wasted energy can result when the per-slot consumption limit prevents using available energy and the battery capacity prevents storing the surplus.The construction of D* uses as much harvested energy for transmission as possible while preserving feasibility.Source: A. The Optimal Wastage Schedule · p. 6, ENDFOR · p. 7
• Given all E_k, D∗k is determined only by the preceding battery level Bk−1; assuming B0 = 0, it can be obtained by computing (13), (12), and (4) for k = 1, 2, ..., K.Source: A. The Optimal Wastage Schedule · p. 7

ENDFOR

• D* minimizes total wasted energy among feasible schedules; any schedule wasting less energy makes the feasible transmission domain empty.This minimum-wastage property is subject to the feasible domain being non-empty.Source: ENDFOR · p. 7
• Feasible wastage schedules with the same total waste as D* have the same optimal transmission value, even though the optimal wastage schedule may not be unique.The transmission domain and optimal transmission value are the same across these optimal wastage schedules.Source: ENDFOR · p. 8
• The optimal transmission value is achieved by solving the transmission problem with wastage schedule D*.Theorem 1 equates the optimal values under D* and the original problem.Source: ENDFOR · p. 8

B. Properties of Optimal Transmission Schedule

• The schedule uses all effective energy after accounting for wastage, since transmitting otherwise wasted energy in some slot would improve the objective.Source: B. Properties of Optimal Transmission… · p. 10
• The KKT conditions are necessary and sufficient for optimality because the objective is concave and the constraints are linear.Theorem 2 gives the resulting transmission-schedule characterization.Source: B. Properties of Optimal Transmission… · pp. 10–11
• Theorem 2 characterizes an optimal feasible schedule by water levels that increase only at battery depletion points (BDPs) and decrease only at fully charged points (BFPs).The level is constant across intervening segments.Source: B. Properties of Optimal Transmission… · p. 11
• Between adjacent optimal BDP/BFP boundaries, the boundary set determines the segment water level and transmission schedule.The optimal boundary set includes the initial and final slots as BDPs.Source: B. Properties of Optimal Transmission… · p. 12
• A manually generated BDP/BFP set may yield a feasible, semi-feasible, or infeasible schedule; it is optimal only when the schedule is feasible and its water levels satisfy Theorem 2.Semi-feasible schedules violate battery-capacity constraints, so they are not feasible solutions.Source: B. Properties of Optimal Transmission… · p. 13

C. Composing Optimal BDP/BFP Set

• Starting from (0, BDP), the algorithm recursively composes the ordered optimal set by appending BDPs or BFPs until (K, BDP) is reached.Each search operates on a segment between existing BDP/BFP points.Source: C. Composing Optimal BDP/BFP Set · pp. 13–14
• Forward search selects the largest candidate point whose segment schedule is feasible or semi-feasible, adding a BDP when feasible and invoking backward search when semi-feasible.The segment schedule is calculated using (26).Source: C. Composing Optimal BDP/BFP Set · p. 13
• Backward search selects the largest B_max-violation point as a BFP, then uses schedule feasibility to add it or recurse with forward or backward search.If the segment ending at the candidate BFP is infeasible, forward search continues; if semi-feasible, backward search continues.Source: C. Composing Optimal BDP/BFP Set · pp. 13–14

(0, BDP), (K, BDP)

• The recursive searches enforce opposite water-level orderings when adding BDPs versus BFPs, and Algorithm 2 has complexity O(K^2).The stated bound uses O(1) complexity for the traditional water-filling operation.Source: (0, BDP), (K, BDP) · pp. 14–15

D. Proof of Optimality

• When an interval is infeasible but both parts split at its largest BDP are feasible, that BDP belongs to the optimal BDP/BFP set.Source: D. Proof of Optimality · p. 15
• For a semi-feasible segment, recursive backward search yields feasible subsegments separated by BFPs and a BDP, with water levels decreasing across the breakpoints.The recursion iteratively selects the largest Bmax-violation points as BFPs before reaching a feasible segment.Source: D. Proof of Optimality · pp. 16–17
• An added BFP remains optimal for the longer interval: later choices cannot raise the water level before the intervening BDP, and existing BFPs remain breakpoints.If the next added point is a BDP, it lies after that intervening BDP.Source: D. Proof of Optimality · p. 17
• Forward-search BDPs require water levels to rise across the breakpoint, while backward-search BFPs require them to fall, satisfying the optimality conditions.The conditions mean water levels may increase only at BDPs and decrease only at BFPs.Source: D. Proof of Optimality · pp. 15, 17, 18
• Algorithm 2 produces the optimal BDP/BFP set, and constant-water-level filling between adjacent points yields the optimal transmission schedule.This is the theorem’s conclusion for the problem in (15)-(16).Source: D. Proof of Optimality · p. 18

IV. ITERATIVE DYNAMIC WATER-FILING FOR MAC

• Each user has an independent battery evolution process, so its feasible transmission-schedule domain does not depend on other transmitters, although the optimal value comes from joint optimization.Source: §IV · p. 18
• The single-user dynamic water-filling analysis extends to the MAC because the additional logarithm term does not affect the proofs of Lemmas 1 and 2 or Theorem 1.Source: §IV · p. 18
• The proposed iterative dynamic water-filling algorithm targets the MAC problem, whose convex formulation has O(NK) constraints and remains computationally difficult for general convex solvers.It is based on Algorithm 2.Source: §IV · p. 19

A. Joint Optimal Single-User Solution

• Given D*, P is optimal for (5)–(6) iff each p_n is optimal for its single-user problem given the other transmitters’ schedules.The result follows from strict concavity in each single variable and joint concavity over all variables.Source: A. Joint Optimal Single-User Solution · p. 19
• With other schedules fixed, the second term in (35) is constant, yielding an equivalent problem with the single-user structure solved by Algorithm 2.The equivalent problem uses the effective channel ˜H_k^n(¯P_n).Source: A. Joint Optimal Single-User Solution · p. 20

B. Iterative Dynamic Water-Filling Algorithm

• The proposed iterative algorithm is intended to obtain the optimal schedule to problem (5)–(6).The section says it will then show the algorithm’s optimality.Source: B. Iterative Dynamic Water-Filling… · p. 20
• The algorithm initializes m = 1, P = 0, and V(0) = 0, specifies a maximum iteration count M, and includes a Local Wasting Schedule.Source: B. Iterative Dynamic Water-Filling… · p. 20
• It calculates H̃k(P̄n), solves (37), and updates pn in P using Algorithm 2.Source: B. Iterative Dynamic Water-Filling… · p. 20

• Each iteration successively solves (37) for each transmitter to update its schedule until C(P) converges.Source: GOTO STEP 3 ENDIF · p. 21
• The alternating updates make C(P) non-decreasing, and its bounded objective value ensures a convergent point; each subproblem’s solution is unique.Source: GOTO STEP 3 ENDIF · p. 21
• At convergence, each transmitter’s schedule is optimal given the schedules of the other transmitters, and the resulting P is optimal for problem (5)-(6).Source: GOTO STEP 3 ENDIF · p. 21
• (N −1)K/2 nats is the maximum gap between Algorithm 4’s objective after its first iteration and the optimal value.Source: GOTO STEP 3 ENDIF · p. 22
• Algorithm 4 has complexity O(NK^2) per iteration because it calls Algorithm 2 for each of N transmitters, at O(K^2) complexity per call.Source: GOTO STEP 3 ENDIF · p. 22

C. Suboptimality of TDMA

• Unlike without energy harvesting, where TDMA is optimal under average-power constraints, TDMA is suboptimal with finite horizons and finite batteries because some transmitters should transmit simultaneously.When transmitters’ water levels reach at least γk/Hk^n, simultaneous transmission can help avoid or reduce battery overflow.Source: C. Suboptimality of TDMA · pp. 22–23

V. NUMERICAL RESULTS

• With N = 5 users, simulations set K = 20 slots and zero initial energy for each user; reported average-rate comparisons across scheduling strategies and the optimal schedule solved by a general convex solver use 2000 runs.Source: §V · pp. 23–24
• In single-user energy- and power-constrained scenarios, proposed and convex-solver schedules match, while modified staircase, greedy, and balanced policies perform worse.Source: §V · pp. 24–25, Figure 7 · p. 25, Figure 8 · p. 26
• In the energy-constrained scenario, greater harvesting variance raises available energy and sum-rate; in the power-constrained scenario, it increases energy waste and lowers available energy and sum-rate.Source: §V · pp. 24–25, Figure 7 · p. 25, Figure 8 · p. 26
• As battery capacity increases, optimal and proposed performance improve and the modified-staircase gap narrows; at equal capacity, high-power performance exceeds low-power performance.The paper attributes these effects to reduced potential overflow and the high-power scenario’s larger transmission-energy dynamic range.Source: §V · pp. 25–26
• In multi-user simulations, the proposed schedule matches convex-solver performance; rates improve as m increases, while iterative modified staircase performs worse at large m and Algorithm 4 converges in 2 iterations.Source: §V · pp. 27–28

VI. CONCLUSIONS

• The scheduling problem has O(NK) variables and constraints, and the iterative dynamic water-filling algorithm is proposed to avoid the high computational complexity of a general convex solver.The paper formulates the N-user fading multiple-access energy-harvesting problem over K time slots as a convex optimization problem.Source: §VI · p. 28
• For one user, dynamic water-filling uses different water levels between battery-depletion and battery-full-charged points; for multiple users, it iterates across users until convergence.Source: §VI · p. 28
• The proposed optimal energy scheduling algorithm converges in a few iterations and achieves significant sum-rate gains over various suboptimal schedules.The supplied conclusion reports no numerical gain values.Source: §VI · p. 29

APPENDIX A PROOF OF LEMMA 2

• Rescheduling wasted energy to an earlier slot is allowed only while that energy remains in the battery and does not change the feasible transmission schedules or their optimum.At possible earlier slots, transmission must already be at maximum energy consumption; otherwise, increasing it would reduce wastage and contradict the minimum-wastage schedule.Source: Appendix A · pp. 29–30

APPENDIX B PROOF OF LEMMA 3

• At the largest Bmax-violation point, setting a BFP pulls energy back from the later segment, raises the earlier water level, and lowers the later one.The battery level at the BFP becomes Bmax, and reduced energy flow across that point prevents new Bmax violations in the segment.Source: Appendix B · pp. 30–31
• Backward recursion separates the segment at BFPs until the preceding schedule is semi-feasible or a feasible segment supplies the next BFP.The resulting subsegments have corresponding water levels; the recursive construction also identifies a feasible segment before adding the next BFP.Source: Appendix B · p. 31
• If a water-level segment is infeasible, the energy-push operation lowers its level until the first negative-battery violation point becomes a BDP.If a battery fills during lowering, that slot is retained as a BFP, and lowering continues after it.Source: Appendix B · p. 32
• The iterative search merges segments when their water levels require it and stops when it finds a BDP or the remaining segment is feasible.The water levels of segments bounded by BFPs and ending at the BDP decrease segment by segment.Source: Appendix B · pp. 32–33

APPENDIX C PROOF OF THEOREM 4

• Theorem 4’s conditions are necessary and sufficient: if every transmitter satisfies its subproblem’s KKT conditions simultaneously, the joint schedule satisfies all KKT conditions and is optimal.The proof also derives necessity from the joint optimal schedule, since each transmitter’s subproblem conditions are a subset of the joint problem’s conditions.Source: Appendix C · p. 33