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

Riepilogo Tecnico: Pianificazione di Attività Consapevole dell'Energia Basata su MDP per IoT Senza Batteria

Enunciato del Problema
I dispositivi Internet of Things (IoT) senza batteria si affidano al raccolta di energia ambientale, portando a operazioni intermittenti che devono essere gestite attraverso una pianificazione consapevole dell'energia. Questa sfida è particolarmente acuta nelle applicazioni di monitoraggio periodico in cui una specifica catena di attività—rilevamento, elaborazione locale e trasmissione wireless—deve essere completata entro un ciclo di reporting fisso. La difficoltà fondamentale risiede nel bilanciare due vincoli competitivi: l'intermittenza energetica e i vincoli temporali rigidi.

• Vincolo Energetico: L'esecuzione di un'attività richiede una tensione del condensatore sufficiente a garantire che il dispositivo non subisca un'interruzione di alimentazione (tensione che scende sotto una soglia di spegnimento) prima del completamento dell'attività.
• Vincolo Temporale: Le attività devono rispettare una rigorosa precedenza (rilevamento $\to$ elaborazione $\to$ trasmissione) e finestre di avvio ammissibili. Ritardare un'attività per raccogliere più energia rischia di far mancare la scadenza per le attività successive o per il ciclo stesso, mentre avviare un'attività troppo presto con energia insufficiente rischia un'interruzione di alimentazione.

Gli approcci esistenti si concentrano spesso sulla fattibilità a breve termine, sull'ottimizzazione di un singolo ciclo o su modelli energetici semplificati, non riuscendo a ottimizzare congiuntamente le prestazioni a lungo termine sotto vincoli rigidi e arrivi energetici stocastici.

Metodologia
Gli autori formulano il problema di pianificazione come un Processo Decisionale di Markov (MDP) a Ricompensa Media a Lungo Termine. Il framework modella esplicitamente le dinamiche del sistema per catturare il compromesso tra sicurezza energetica e conformità alle scadenze.

1. Modello di Sistema:

   • Il dispositivo opera in cicli periodici di durata $T_s$, suddivisi in unità di tempo discrete.
   • L'energia viene raccolta tramite un trasduttore di Raccolta di Energia (EH) e immagazzinata in un condensatore. L'evoluzione della tensione è modellata utilizzando le dinamiche dei circuiti RC, tenendo conto della ricarica durante la raccolta e della scarica durante l'esecuzione dell'attività o il sonno.
   • Viene definita una metrica di probabilità di "esecuzione sicura" per quantificare la probabilità che un'attività si completi senza che la tensione del condensatore scenda sotto la soglia di spegnimento $V_{out}$.

2. Formulazione MDP:

   • Spazio degli Stati: Definito da una terna $(V_n, \tau_n, f_n)$, che rappresenta la tensione del condensatore, l'orologio locale (tempo all'interno del ciclo) e un flag di attività che indica il progresso della catena di attività (0: rilevamento in sospeso, 1: rilevamento completato, 2: elaborazione completata, 3: trasmissione completata). La tensione continua è quantizzata per abilitare metodi MDP a stati finiti.
   • Spazio delle Azioni: Il dispositivo può scegliere di dormire, rilevare, elaborare o trasmettere, soggetto alle finestre ammissibili dello stato corrente.
   • Progettazione della Ricompensa: Vengono proposte due funzioni di ricompensa. La Ricompensa Base accoppia le decisioni di pianificazione con la probabilità di esecuzione sicura. La Ricompensa Basata su Sigmoidale introduce un parametro di soglia per penalizzare più severamente le esecuzioni rischiose a bassa energia, promuovendo una pianificazione conservativa negli stati energetici intermedi per ridurre le interruzioni di alimentazione.

3. Derivazione della Politica:

   • Gli autori dimostrano che la Catena di Markov indotta è unichain (contenente esattamente una classe ricorrente), garantendo che la ricompensa media a lungo termine sia indipendente dallo stato iniziale.
   • Stabiliscono che la politica stazionaria ottimale ha una struttura a soglia rispetto alla tensione del condensatore. Ciò significa che per qualsiasi passo temporale e fase di attività data, esiste una soglia di tensione al di sopra della quale il dispositivo dovrebbe eseguire l'attività e al di sotto della quale dovrebbe dormire.
   • Ciò porta allo Schedulatore Ottimale Stazionario Basato su Soglia (OSTB), che può essere calcolato offline utilizzando la Programmazione Lineare (LP).

4. Estensione all'Energia Correlata:

   • Per affrontare scenari realistici in cui gli arrivi energetici sono temporalmente correlati (ad esempio, condizioni di luce variabili), il framework è esteso arricchendo lo stato con una variabile di modalità EH governata da un processo di Markov a stati finiti.
   • Vengono fornite condizioni sufficienti per dimostrare che la struttura basata su soglie rimane ottimale in questo contesto correlato, con le soglie che ora dipendono sia dal passo temporale che dalla modalità EH corrente.

Contributi Chiave

1. Formulazione MDP a Vincoli Rigidi: Il documento presenta la pianificazione periodica di attività senza batteria come un MDP a stati finiti che impone esplicitamente finestre di avvio ammissibili rigide, precedenza delle attività e condizioni di esecuzione sicura derivate dalle dinamiche del condensatore, andando oltre le penalità di utilità morbide utilizzate nei lavori precedenti.
2. Progettazione Conservativa della Ricompensa: Viene introdotta una nuova funzione di ricompensa basata su sigmoidale per promuovere esplicitamente una pianificazione conservativa negli stati energetici intermedi, riducendo efficacemente le interruzioni di alimentazione mantenendo al contempo gli obiettivi di completamento delle attività a lungo termine.
3. Caratterizzazione Strutturale: Gli autori dimostrano la proprietà unichain dell'MDP e dimostrano che la politica ottimale è basata su soglie. Ciò riduce lo spazio di ricerca della politica da una mappatura generale a un insieme di soglie di tensione, consentendo un calcolo efficiente dello schedulatore OSTB.
4. Estensione EH Correlata: Il framework è esteso per gestire la raccolta di energia correlata tramite un modello di Markov a stati finiti, preservando l'ottimalità basata su soglie in condizioni specifiche.
5. Valutazione Completa: Lo schedulatore OSTB proposto viene confrontato con un'euristica Earliest-Deadline-First con Energy Guard (EDF-EG) e una politica As-Late-As-Possible (ALAP).

Risultati
Le simulazioni numeriche dimostrano la superiorità dello schedulatore OSTB:

• Prestazioni: OSTB ottiene un tasso di completamento della catena completa a lungo termine più elevato (cicli di rilevamento-elaborazione-trasmissione riusciti) rispetto a EDF-EG e ALAP, in particolare quando l'energia raccolta è scarsa.
• Affidabilità: La progettazione della ricompensa basata su sigmoidale riduce significativamente il numero di interruzioni di alimentazione rispetto alla funzione di ricompensa base.
• Latenza: Nei regimi a bassa energia, OSTB ottiene una latenza di esecuzione inferiore rispetto alle baseline bilanciando adattivamente la raccolta di energia e l'esecuzione delle attività, mentre ALAP soffre di latenza massima a causa della sua strategia "aspetta fino all'ultimo momento".
• EH Correlata: Negli scenari di energia correlata, la politica OSTB arricchita adatta le soglie in base alla modalità EH corrente, migliorando ulteriormente i tassi di completamento end-to-end.
• Scalabilità: La complessità del calcolo offline è polinomiale nella dimensione dello stato discretizzato, mentre la complessità dell'implementazione online è $O(1)$ per passo temporale, richiedendo solo una consultazione delle soglie di tensione.

Significato
Il documento afferma che il framework proposto fornisce una soluzione rigorosa e analiticamente trattabile per la pianificazione di attività consapevole dell'energia nell'IoT senza batteria. Accoppiando esplicitamente la disponibilità energetica con l'urgenza delle scadenze attraverso una politica adattiva a soglia, lo schedulatore OSTB gestisce efficacemente il compromesso fondamentale tra l'attesa di più energia e il rischio di mancare le scadenze. Il lavoro evidenzia che per dispositivi con capacità di accumulo energetico limitata, l'ottimizzazione congiunta per sicurezza e tempistica produce guadagni di prestazioni significativi rispetto alle euristiche che ottimizzano solo uno di questi fattori. La caratterizzazione strutturale della politica ottimale offre un percorso di implementazione pratico, evitando la necessità di apprendimento online complesso o di pesanti calcoli in tempo reale.