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

Technische Samenvatting: MDP-gebaseerde energiebewuste taakplanning voor batterijloze IoT

Probleemstelling
Batterijloze Internet of Things (IoT)-apparaten vertrouwen op omgevingsenergieoogst, wat leidt tot intermitterende bewerkingen die moeten worden beheerd via energiebewuste planning. Deze uitdaging is vooral acuut in periodieke monitoringtoepassingen waarbij een specifieke keten van taken – meten, lokaal rekenen en draadloos verzenden – binnen een vaste rapportagecyclus moet worden voltooid. De kernmoeilijkheid ligt in het balanceren van twee concurrerende beperkingen: energie-intermittentie en harde tijdsbeperkingen.

• Energiebeperking: Het uitvoeren van een taak vereist voldoende condensatorspanning om te garanderen dat het apparaat geen stroomuitval ondervindt (spanning daalt onder een uitschakeldrempel) voordat de taak is voltooid.
• Tijdsbeperking: Taken moeten strikte volgorde (meten $\to$ rekenen $\to$ verzenden) en toelaatbare startvensters naleven. Het uitstellen van een taak om meer energie op te vangen, riskeert het missen van de deadline voor daaropvolgende taken of de cyclus zelf, terwijl het te vroeg starten van een taak met onvoldoende energie risico's op stroomuitval met zich meebrengt.

Bestaande benaderingen richten zich vaak op haalbaarheid op korte termijn, optimalisatie van een enkele cyclus of vereenvoudigde energiemodellen, en falen in het gezamenlijk optimaliseren van prestaties op lange termijn onder harde beperkingen en stochastische energieaankomsten.

Methodologie
De auteurs formuleren het planningsprobleem als een Markov-beslissingsproces (MDP) met lange-termijn gemiddelde beloning. Het kader modelleert expliciet de systeemdynamiek om de afweging tussen energieveiligheid en naleving van deadlines vast te leggen.

1. Systeemmodel:

   • Het apparaat werkt in periodieke cycli van duur $T_s$, onderverdeeld in discrete tijdseenheden.
   • Energie wordt geoogst via een Energieoogst (EH) transducer en opgeslagen in een condensator. De spanningsontwikkeling wordt gemodelleerd met RC-schakelingsdynamica, rekening houdend met opladen tijdens oogsten en ontladen tijdens taakuitvoering of slaap.
   • Een "veilige-uitvoering"-kansmetriek wordt gedefinieerd om de waarschijnlijkheid te kwantificeren dat een taak wordt voltooid zonder dat de condensatorspanning daalt onder de uitschakeldrempel $V_{out}$.

2. MDP-formulering:

   • Statenruimte: Gedefinieerd door een triplet $(V_n, \tau_n, f_n)$, dat de condensatorspanning, de lokale klok (tijd binnen de cyclus) en een taakvlag aangeeft die de voortgang van de taakketen aangeeft (0: meten in afwachting, 1: meten voltooid, 2: rekenen voltooid, 3: verzenden voltooid). De continue spanning wordt gekwantiseerd om methoden voor eindige-staten-MDP mogelijk te maken.
   • Actieruimte: Het apparaat kan kiezen om te slapen, te meten, te rekenen of te verzenden, onderhevig aan de toelaatbare vensters van de huidige staat.
   • Beloningsontwerp: Er worden twee beloningsfuncties voorgesteld. De Basisbeloning koppel planningsbeslissingen aan de kans op veilige uitvoering. De Sigmoid-gebaseerde beloning introduceert een drempelparameter om risicovolle uitvoeringen met lage energie scherper te bestraffen, waardoor conservatieve planning in intermediaire energiestaten wordt bevorderd om stroomuitval te verminderen.

3. Afleiding van beleid:

   • De auteurs bewijzen dat de geïnduceerde Markov-keten unichain is (bevat precies één recurrente klasse), waardoor de lange-termijn gemiddelde beloning onafhankelijk is van de begintoestand.
   • Zij stellen vast dat het optimale stationaire beleid een drempelstructuur heeft met betrekking tot de condensatorspanning. Dit betekent dat voor elke gegeven tijdstap en taakfase een spanningsdrempel bestaat waarboven het apparaat de taak moet uitvoeren en waaronder het moet slapen.
   • Dit leidt tot de Optimale Stationaire Drempelgebaseerde (OSTB) planner, die offline kan worden berekend met Lineaire Programmering (LP).

4. Uitbreiding naar Gecorreleerde Energie:

   • Om realistische scenario's aan te pakken waarin energieaankomsten temporair gecorreleerd zijn (bijvoorbeeld variërende lichtomstandigheden), wordt het kader uitgebreid door de staat te verrijken met een EH-modusvariabele die wordt beheerst door een eindige-staten Markov-proces.
   • Er worden voldoende voorwaarden gegeven om aan te tonen dat de drempelgebaseerde structuur optimaal blijft in deze gecorreleerde setting, waarbij de drempels nu afhankelijk zijn van zowel de tijdstap als de huidige EH-modus.

Belangrijkste Bijdragen

1. Harde-beperkte MDP-formulering: Het artikel presenteert periodieke batterijloze taakplanning als een eindige-staten MDP die expliciet harde toelaatbare startvensters, taakvolgorde en veilige-uitvoeringsvoorwaarden afgeleid uit condensatordynamica afdwingt, en verder gaat dan zachte nutstraffen die in eerdere werken werden gebruikt.
2. Conservatief Beloningsontwerp: Er wordt een nieuwe sigmoid-gebaseerde beloningsfunctie geïntroduceerd om expliciet conservatieve planning in intermediaire energiestaten te bevorderen, wat effectief stroomuitval vermindert terwijl doelen voor taakvoltooiing op lange termijn worden gehandhaafd.
3. Structurele Karakterisering: De auteurs bewijzen de unichain-eigenschap van de MDP en tonen aan dat het optimale beleid drempelgebaseerd is. Dit reduceert de beleidszoekruimte van een algemene mapping tot een reeks spanningsdrempels, waardoor efficiënte berekening van de OSTB-planner mogelijk wordt.
4. Uitbreiding Gecorreleerde EH: Het kader wordt uitgebreid om gecorreleerde energieoogst te verwerken via een eindige-staten Markov-model, waarbij de drempelgebaseerde optimaliteit onder specifieke voorwaarden behouden blijft.
5. Uitgebreide Evaluatie: De voorgestelde OSTB-planner wordt gebenchmarkt tegen een Earliest-Deadline-First met Energie Guard (EDF-EG) heuristiek en een As-Late-As-Possible (ALAP) beleid.

Resultaten
Numerieke simulaties tonen de superioriteit van de OSTB-planner aan:

• Prestaties: OSTB bereikt een hoger lange-termijn percentage voltooiing van volledige ketens (succesvolle meten-rekenen-verzenden cycli) in vergelijking met EDF-EG en ALAP, vooral wanneer geoogste energie schaars is.
• Betrouwbaarheid: Het sigmoid-gebaseerde beloningsontwerp vermindert het aantal stroomuitval aanzienlijk in vergelijking met de basisbeloningsfunctie.
• Latentie: In regimes met lage energie bereikt OSTB een lagere uitvoeringslatentie dan baselines door adaptief energieoogst en taakuitvoering in evenwicht te brengen, terwijl ALAP lijdt aan maximale latentie door zijn strategie "wachten tot het laatste moment".
• Gecorreleerde EH: In scenario's met gecorreleerde energie past de uitgebreide OSTB-beleid drempels aan op basis van de huidige EH-modus, waardoor de end-to-end voltooiingspercentages verder worden verbeterd.
• Schaalbaarheid: De complexiteit van de offline berekening is polynoom in de gediskretiseerde statendimensie, terwijl de complexiteit van de online implementatie $O(1)$ per tijdstap is, waarbij alleen een opzoeken van spanningsdrempels vereist is.

Betekenis
Het artikel stelt dat het voorgestelde kader een rigoureuze, analytisch hanteerbare oplossing biedt voor energiebewuste taakplanning in batterijloze IoT. Door energietijdsbeschikbaarheid expliciet te koppelen aan dringende deadlines via een adaptief drempelbeleid, beheert de OSTB-planner effectief de fundamentele afweging tussen wachten op meer energie en het risico op het missen van deadlines. Het werk benadrukt dat voor apparaten met beperkte energiestorage, het gezamenlijk optimaliseren van veiligheid en timing aanzienlijke prestatiewinst oplevert ten opzichte van heuristieken die slechts op één van deze factoren optimaliseren. De structurele karakterisering van het optimale beleid biedt een praktische implementatieweg, waardoor de behoefte aan complex online leren of zware real-time berekening wordt vermeden.