Source-linked AI summary
Utility Optimal Scheduling in Energy Harvesting Networks
Longbo Huang, Michael J. Neely
TL;DR
Finite-capacity storage makes utility-optimal scheduling difficult because energy availability couples present power use with future actions. The paper develops online Lyapunov-based ESA and MESA algorithms that jointly manage harvesting and transmissions without process knowledge. ESA achieves utility within O(ε) of optimal with deterministic O(1/ε) storage and congestion bounds, while MESA retains the utility guarantee with O([log(1/ε)]^2) storage sizes and average congestion.
Problem
Finite-capacity energy storage and time-varying harvestable energy complicate utility-optimal scheduling under the requirement that consumed energy never exceed stored energy.
Method
ESA uses perturbed-weight Lyapunov optimization for online joint energy harvesting, power allocation, routing, and scheduling without knowledge of the harvestable-energy process.
Results
ESA achieves utility within O(ε) of optimal with O(1/ε) energy storage and deterministically O(1/ε) network backlog, while MESA achieves the same utility gap with O([log(1/ε)]^2) storage sizes.
Takeaways & Limitations
The algorithms provide close-to-optimal utility with finite, explicitly bounded storage, and ESA does not require statistical knowledge of energy or channel processes.
Abstract
from arXiv · showhide
In this paper, we show how to achieve close-to-optimal utility performance in energy harvesting networks with only finite capacity energy storage devices. In these networks, nodes are capable of harvesting energy from the environment. The amount of energy that can be harvested is time varying and evolves according to some probability law. We develop an \emph{online} algorithm, called the Energy-limited Scheduling Algorithm (ESA), which jointly manages the energy and makes power allocation decisions for packet transmissions. ESA only has to keep track of the amount of energy left at the network nodes and \emph{does not require any knowledge} of the harvestable energy process. We show that ESA achieves a utility that is within $O(ε)$ of the optimal, for any $ε>0$, while ensuring that the network congestion and the required capacity of the energy storage devices are \emph{deterministically} upper bounded by bounds of size $O(1/ε)$. We then also develop the Modified-ESA algorithm (MESA) to achieve the same $O(ε)$ close-to-utility performance, with the average network congestion and the required capacity of the energy storage devices being only $O([\log(1/ε)]^2)$.
I. INTRODUCTION
The paper addresses utility-optimal scheduling in stochastic energy-harvesting networks with finite storage, time-varying channels, and an energy-availability constraint. It develops ESA and MESA using perturbed-weight Lyapunov optimization to manage energy and transmission decisions online.
- Energy harvesting can support autonomous wireless networks, potentially freeing devices from always-on energy sources and enabling very long operation.
- Finite energy-storage capacity complicates scheduling because current power use can deplete energy and restrict future transmissions.
- ESA uses perturbed weights to push energy levels away from underflow while jointly making harvesting, power-allocation, routing, and scheduling decisions.
- ESA is online and requires neither knowledge of the harvestable-energy process nor statistical knowledge of channel qualities.
- MESA achieves the same O(ε) close-to-optimal utility performance with energy storage sizes of O([log(1/ε)]^2), rather than ESA’s O(1/ε) sizes.
C. The Energy Queue Model
The model represents harvested energy and queued data explicitly while enforcing that transmission power never exceeds stored energy. The objective is to jointly control admissions, routing, scheduling, power, and harvesting to maximize utility under stability constraints.
- Each node’s finite-capacity battery or ultracapacitor is modeled as an energy queue tracking the energy remaining at that node.
- The energy-availability constraint requires consumed power to be no more than energy currently stored.
- Harvestable energy varies by slot, is represented by an energy-state vector, and may be correlated across nodes.
- The algorithm can implement finite storage by harvesting below a threshold of O(1/ε) and dropping harvestable energy above it.
- The network jointly chooses data admissions, power allocation, routing, scheduling, and energy management to maximize utility while maintaining finite average backlog.
F. Discussion of the Model
The model is intended for interconnected battery-powered networks and accommodates stochastic channel and energy processes. The paper formulates an upper-bounding optimization framework that supports analysis under broader ergodic dynamics.
- The model covers field-monitoring sensor networks and mobile ad hoc networks, including correlated harvestable energy among collocated nodes.
- Energy availability couples current power allocation to future decisions, creating a scheduling challenge that can otherwise require substantial statistical knowledge.
- The optimal-utility upper-bound formulation uses channel-state-dependent power allocations and energy-harvesting decisions across state pairs.
- The analysis can extend to finite-state irreducible and aperiodic Markov channel and energy processes.
IV. ENGINEERING THE QUEUES
ESA uses perturbed Lyapunov weights to jointly make energy-harvesting, power-allocation, routing, and scheduling decisions while respecting energy availability. The online algorithm relies on current channel and queue states rather than harvest-process knowledge.
- Weight perturbation: Perturbed Lyapunov weights push energy queues toward nonzero target levels, helping prevent underflow during power allocation.The target queue levels are the nodes’ energy levels, and the perturbation is designed to ensure sufficient energy when links receive power.
- Per-slot optimization: ESA approximately minimizes the Lyapunov drift bound subject to the energy-availability constraint at every time slot.Its decisions cover energy harvesting, data admission, power allocation, routing, and scheduling.
- Energy management: The algorithm harvests energy when the energy queue is below its threshold and otherwise can avoid harvesting, enabling finite-capacity implementation.The threshold is constructed through the perturbation vector and deterministic queue bounds established later.
- Routing and scheduling: When a link has positive maximum weight, ESA allocates its full rate to a maximizing commodity and uses idle-fill if needed.The routing and scheduling rule is applied after determining link weights and power allocation.
- Online information: ESA observes channel and queue states and requires neither the harvestable-energy process nor statistical knowledge of channel qualities.The required observations are the instantaneous channel state and data and energy queue sizes.
V. PERFORMANCE ANALYSIS
ESA provides deterministic queue and energy-storage bounds together with utility close to the optimum. These guarantees extend from i.i.d. network randomness to finite-state irreducible, aperiodic Markov processes.
- ESA under i.i.d. randomness: Θ_n ≜ δβV + Pmax sets the perturbation used in the deterministic queue and energy bounds.The resulting constant in the utility bound is independent of V.
- ESA under i.i.d. randomness: 0 ≤ Q_n^(c)(t) ≤ βV + Rmax and 0 ≤ E_n(t) ≤ θ_n + hmax hold for all time under ESA.The theorem also guarantees E_n(t) ≥ Pmax whenever node n allocates nonzero power to an outgoing link.
- ESA under Markovian randomness: The queue bounds remain valid for arbitrary channel and energy-state sample paths, including finite-state Markov processes.The sample-path nature of Part (a) separates these deterministic bounds from the stochastic utility analysis.
- ESA under i.i.d. randomness: O(1/V) utility gap and O(1/V) utility-backlog tradeoff characterize ESA’s performance under the stated randomness assumptions.With ε = 1/V, the average data queue size is O(1/ε), while energy queues remain deterministically bounded by an O(1/ε) constant.
VI. REDUCING THE BUFFER SIZE
MESA preserves close-to-optimal utility while reducing average congestion and required energy-storage capacity to logarithmic-squared scale. It combines virtual queues with a finite actual energy queue and a two-phase attraction-point procedure.
- Performance objective: O([log(1/ε)]^2) energy-storage size and O([log(1/ε)]^2) average data queue size accompany the same O(ε) utility guarantee.This is the principal buffer-size reduction claimed for MESA.
- Conditions: The MESA guarantee assumes finite unique y* and finite-state irreducible, aperiodic Markov channel and energy processes.The theorem additionally assumes the system is in steady state at time T and that a steady-state ESA queue distribution exists.
- MESA design: For V = 1/ε, M = 4[log(V)]^2 defines the actual energy-queue capacity used by MESA.The construction associates each node with an actual energy queue of size M and virtual data and energy queues.
- MESA design: MESA uses Phase I to discover queue attraction points and Phase II to coordinate harvesting, power allocation, routing, and scheduling around them.The two phases operate through virtual queue processes before controlling the actual finite energy queue.
- Implication: Under the theorem’s conditions, MESA reduces required energy capacity and network congestion when the exponential attraction result holds.The paper states that this condition is mostly satisfied in practice.
VII. SIMULATION
The simulations evaluate ESA and MESA in a six-node data collection network with Markovian energy arrivals. ESA approaches the optimal utility, while MESA combines similar utility with poly-logarithmic actual queue growth.
- ESA is simulated on a six-node data collection network in which nodes 1, 2, and 3 forward sensed data through relay nodes 4 and 5 to the sink.
- Each node’s available energy follows a two-state Markov chain, taking value 2 in the good state and 0 otherwise.
- The total network utility under ESA converges quickly to approximately 2.03, its stated optimal value.
- At most 5 of more than 10^5 packets were dropped in the MESA simulations for any tested V value.
- O([log(V)]^2) actual queue growth contrasts with virtual queues growing linearly in V under MESA, matching Theorem 5.
- ESA’s analysis guarantees O(ε) utility optimality with O(1/ε) storage and O(1/ε) time-average congestion.
APPENDIX A – PROOF OF LEMMA 2
The proof of Lemma 2 bounds the relevant queue-drift terms by squaring queue updates, summing componentwise inequalities, and taking conditional expectations.
- The proof begins by squaring both sides of an update and applying ([x]+)^2 ≤ x^2.
- Analogous inequalities are derived for additional update terms before aggregation.
- Summing the bounds over commodity-node pairs and nodes defines a combined constant B.
- Conditional expectations over channel states, energy states, and action randomness are then taken given Z(t).
- Subtracting the V-weighted utility term and rearranging yields the lemma.
APPENDIX B – PROOF OF THEOREM 2
Theorem 2 is proved by showing ESA preserves energy availability, approximately minimizes the drift expression, and maintains deterministic queue and energy bounds.
- Part (a): ESA’s choice of θ makes the energy-availability constraint redundant because any node transmitting positive power has at least Pmax stored energy.
- Part (a): The proof establishes deterministic upper bounds on actual data queues and energy storage through induction over time.
- Part (b): ESA minimizes the drift-related function D(t), and its value is no greater than that of any alternative policy plus a constant.
- Part (b): The comparison policy minimizes the drift expression subject to energy, admission, power, and flow constraints.
- Part (b): Taking expectations, summing over time, and using nonnegative Lyapunov terms produces the utility bound.
- Part (b): The proof concludes after rearranging, dividing by VT, taking the long-run liminf, and applying Jensen’s inequality.
APPENDIX C – PROOF OF LEMMA 3
The proof of Lemma 3 analyzes the modified energy process by induction across three cases, establishing the claimed relationship between actual and auxiliary energy levels.
- The proof introduces an intermediate queue process that omits packet discards under specified auxiliary-energy conditions.
- The queue comparison follows from Lemma 3 in and yields the stated bound for the intermediate process.
- The energy relation is proved by induction, separating cases where the auxiliary energy is below, above, or within a bounded interval.
- The three-case induction establishes the energy relation and completes the lemma.
- Case II: When the auxiliary energy exceeds the upper threshold by more than M, the update keeps the actual energy at M.
- Case III: Within the interval, two subcases handle increments at most M and increments exceeding M.
APPENDIX D – PROOF OF THEOREM 5
The proof establishes that MESA’s power allocations remain valid and that its packet-dropping rate is O(ε), preserving ESA’s utility performance up to the bounded-derivative argument.
- Power-allocation validity: MESA’s power allocations are valid because its stored energy is at least Pmax whenever decisions are made in the relevant energy interval.The proof uses En(t) ≥ [Ên(t)−En]+ ≥ Pmax when Ên(t) ∈ [En+Pmax, En+M].
- Utility preservation: MESA performs ESA’s admission, routing, and scheduling actions, so without packet dropping it achieves the same utility performance.
- Dropping-rate bound: O(1/V) is the resulting average packet-dropping rate, because each slot drops at most N(μmax + Rmax) packets.This completes the proof of Theorem 5’s utility argument when combined with bounded utility derivatives.
- Packet-dropping event: Packet dropping occurs only when some shifted energy level falls below En+Pmax or exceeds En+M.The proof defines the packet-dropping event as the union over nodes of these two threshold violations.
- Event containment: Under the stated bounds, the packet-dropping event is contained in a rare energy-deviation event controlled by the ESA analysis.The proof successively establishes Ê(t) ⊂ Ē(t) ⊂ E(t, m̃), with m̃ specified in the cited passages.