MDP-based Energy-aware Task Scheduling for Battery-less IoT

Technical Summary: MDP-based Energy-aware Task Scheduling for Battery-less IoT

Problem Statement
Battery-less Internet of Things (IoT) devices rely on ambient energy harvesting, leading to intermittent operations that must be managed through energy-aware scheduling. This challenge is particularly acute in periodic monitoring applications where a specific chain of tasks—sensing, local computing, and wireless transmission—must be completed within a fixed reporting cycle. The core difficulty lies in balancing two competing constraints: energy intermittency and hard timing constraints.

• Energy Constraint: Executing a task requires sufficient capacitor voltage to ensure the device does not experience a power failure (voltage dropping below a turn-off threshold) before the task completes.
• Timing Constraint: Tasks must adhere to strict precedence (sensing $\to$ computing $\to$ transmission) and permissible start windows. Delaying a task to harvest more energy risks missing the deadline for subsequent tasks or the cycle itself, while initiating a task too early with insufficient energy risks a power failure.

Existing approaches often focus on short-term feasibility, single-cycle optimization, or simplified energy models, failing to jointly optimize long-term performance under hard constraints and stochastic energy arrivals.

Methodology
The authors formulate the scheduling problem as a Long-term Average-Reward Markov Decision Process (MDP). The framework explicitly models the system dynamics to capture the tradeoff between energy safety and deadline compliance.

1. System Model:

   • The device operates in periodic cycles of duration $T_s$, divided into discrete time units.
   • Energy is harvested via an Energy Harvesting (EH) transducer and stored in a capacitor. The voltage evolution is modeled using RC circuit dynamics, accounting for charging during harvesting and discharging during task execution or sleep.
   • A "safe-execution" probability metric is defined to quantify the likelihood that a task will complete without the capacitor voltage dropping below the turn-off threshold $V_{out}$.

2. MDP Formulation:

   • State Space: Defined by a triplet $(V_n, \tau_n, f_n)$, representing the capacitor voltage, the local clock (time within the cycle), and a task flag indicating the progress of the task chain (0: sensing pending, 1: sensing done, 2: computing done, 3: transmission done). The continuous voltage is quantized to enable finite-state MDP methods.
   • Action Space: The device can choose to sleep, sense, compute, or transmit, subject to the current state's permissible windows.
   • Reward Design: Two reward functions are proposed. The Basic Reward couples scheduling decisions with the safe-execution probability. The Sigmoid-based Reward introduces a threshold parameter to penalize risky, low-energy executions more sharply, promoting conservative scheduling in intermediate energy states to reduce power failures.

3. Policy Derivation:

   • The authors prove that the induced Markov Chain is unichain (containing exactly one recurrent class), ensuring the long-term average reward is independent of the initial state.
   • They establish that the optimal stationary policy has a threshold structure with respect to the capacitor voltage. This means that for any given time step and task stage, there exists a voltage threshold above which the device should execute the task and below which it should sleep.
   • This leads to the Optimal Stationary Threshold-Based (OSTB) scheduler, which can be computed offline using Linear Programming (LP).

4. Extension to Correlated Energy:

   • To address realistic scenarios where energy arrivals are temporally correlated (e.g., varying light conditions), the framework is extended by augmenting the state with an EH mode variable governed by a finite-state Markov process.
   • Sufficient conditions are provided to show that the threshold-based structure remains optimal in this correlated setting, with thresholds now depending on both the time step and the current EH mode.

Key Contributions

1. Hard-Constrained MDP Formulation: The paper casts periodic battery-less task scheduling as a finite-state MDP that explicitly enforces hard permissible start windows, task precedence, and safe-execution conditions derived from capacitor dynamics, moving beyond soft utility penalties used in prior work.
2. Conservative Reward Design: A novel sigmoid-based reward function is introduced to explicitly promote conservative scheduling in intermediate energy states, effectively reducing power failures while maintaining long-term task completion goals.
3. Structural Characterization: The authors prove the unichain property of the MDP and demonstrate that the optimal policy is threshold-based. This reduces the policy search space from a general mapping to a set of voltage thresholds, enabling efficient computation of the OSTB scheduler.
4. Correlated EH Extension: The framework is extended to handle correlated energy harvesting via a finite-state Markov model, preserving the threshold-based optimality under specific conditions.
5. Comprehensive Evaluation: The proposed OSTB scheduler is benchmarked against an Earliest-Deadline-First with Energy Guard (EDF-EG) heuristic and an As-Late-As-Possible (ALAP) policy.

Results
Numerical simulations demonstrate the superiority of the OSTB scheduler:

• Performance: OSTB achieves a higher long-term full-chain completion rate (successful sensing-computing-transmission cycles) compared to EDF-EG and ALAP, particularly when harvested energy is scarce.
• Reliability: The sigmoid-based reward design significantly reduces the number of power failures compared to the basic reward function.
• Latency: In low-energy regimes, OSTB achieves lower execution latency than baselines by adaptively balancing energy harvesting and task execution, whereas ALAP suffers from maximum latency due to its "wait until the last moment" strategy.
• Correlated EH: In correlated energy scenarios, the augmented OSTB policy adapts thresholds based on the current EH mode, further improving end-to-end completion rates.
• Scalability: The offline computation complexity is polynomial in the discretized state dimension, while the online implementation complexity is $O(1)$ per time step, requiring only a lookup of voltage thresholds.

Significance
The paper claims that the proposed framework provides a rigorous, analytically tractable solution for energy-aware task scheduling in battery-less IoT. By explicitly coupling energy availability with deadline urgency through an adaptive threshold policy, the OSTB scheduler effectively manages the fundamental tradeoff between waiting for more energy and the risk of missing deadlines. The work highlights that for devices with limited energy storage, jointly optimizing for safety and timing yields significant performance gains over heuristics that optimize for only one of these factors. The structural characterization of the optimal policy offers a practical implementation path, avoiding the need for complex online learning or heavy real-time computation.