Technische Samenvatting: Naar een ILP-benadering van temporele dekking in sensornetwerken

Probleemstelling

Het artikel behandelt de uitdaging van het waarborgen van temporele dekking in buiten sensornetwerken die worden gevoed door energie-oogsttechnologie (energy harvesting). Terwijl ruimtelijke dekking (het garanderen dat elk Point of Interest, of POI, wordt gemonitord door ten minste één sensor) een goed onderzocht probleem is, is het handhaven van continue temporele dekking moeilijk wanneer sensoren afhankelijk zijn van beperkte energiebronnen die fluctueren of onvoldoende zijn om continue werking te ondersteunen.

De specifieke context van het probleem betreft sensoren waarbij het energieverbruik tijdens de actieve staat ($c(S_j)$) groter is dan de energie-oogstrate ($h(S_j)$). Gevolgelijk kunnen sensoren niet ononderbroken blijven functioneren zonder onderbreking. Ze moeten afwisselen tussen een actieve staat (het monitoren van POI's, waarbij netto energie wordt verbruikt) en een passieve staat (energie oogsten om op te laden). De kernuitdaging is het orkestreren van de activatie- en laadcycli van meerdere sensoren om te garanderen dat elke POI op elk moment gedekt is, terwijl rekening wordt gehouden met individuele batterijbeperkingen en door een schema te zorgen dat houdbaar is over een oneindige horizon.

Methodologie

De auteurs stellen een systeemmodel voor op basis van Integer Lineaire Programmering (ILP) om haalbare sensorschema's te genereren. Het systeem bestaat uit $m$ POI's en $n$ sensoren, waarbij elke sensor een vaste dekkingsset, een batterijcapaciteit, een verbruikssnelheid en een oogstsnelheid heeft. De auteurs gaan uit van een lineair laadprofiel binnen een gedefinieerde energieruimte $[e_{min}, e_{max}]$ en constante oogstsnelheden (gericht op stabiele bronnen zoals RF).

Er zijn twee verschillende ILP-formuleringen ontwikkeld om het planningsprobleem op te lossen:

1. Niet-preëmptieve Benadering (NPA):

   • Mechanisme: Sensoren volgen strikte schakelregels op basis van batterijniveaus. Een sensor gaat pas van passief naar actief wanneer deze volledig is opgeladen en blijft actief voor een vaste duur totdat de batterij een lager drempelniveau bereikt. Toestandsveranderingen zijn niet toegestaan halverwege een cyclus.
   • Modellering: Deze benadering abstraheert de energiedynamiek naar temporele beperkingen. Het houdt de instantane energieniveaus niet expliciet bij in de ILP; in plaats daarvan wordt haalbaarheid afgedwongen door de duur en de volgorde van passieve en actieve intervallen te beperken.
   • Afweging: Dit vereenvoudigt de implementatie (vereist enkel timers) en vermindert het aantal toestandsveranderingen, maar beperkt de flexibiliteit van de planning.

2. Volledig Preëmptieve Benadering (FPA):

   • Mechanisme: Sensoren kunnen op elk moment van staat wisselen, mits het batterijniveau boven een minimale drempel blijft. Toestandsveranderingen zijn niet gebonden aan volledige laad- of ontlaadcycli.
   • Modellering: Deze benadering houdt het energieniveau $e(S_i, t)$ expliciet bij voor elk discreet tijdstap binnen de ILP. Het bevat beperkingen voor energieaccumulatie, verbruik en de vereiste dat het batterijniveau aan het einde van de hyperperiode ten minste gelijk moet zijn aan het beginniveau om herhaalbaarheid te garanderen.
   • Afweging: Dit biedt meer flexibiliteit om haalbare schema's te vinden onder strikte energiebeperkingen, maar verhoogt de complexiteit van de ILP en het aantal vereiste toestandsveranderingen (synchronisatie-overhead).

Belangrijke Theoretische Fundamenten:

• Hyperperiode: Het schema is ontworpen om cyclisch te zijn, herhalend over een berekende hyperperiode $H$.
• Geldigheid en Herhaalbaarheid: De auteurs stellen voorwaarden vast (Stelling 1) die garanderen dat de batterij niet leegloopt tijdens de hyperperiode (geldigheid) en dat de energietoestand aan het einde van de cyclus een oneindige herhaling mogelijk maakt (herhaalbaarheid/energieneutraliteit).
• Haalbaarheids-prefilter: Een lichtgewicht controle op basis van Lemma 3 wordt toegepast voordat de ILP wordt opgelost om te verifiëren of de som van de ratio's van oogst naar verbruik voor sensoren die een POI dekken ten minste 1 is.

Belangrijkste Bijdragen

1. Duale ILP-formuleringen: Het artikel presenteert twee verschillende ILP-modellen (NPA en FPA) voor het temporele dekkingprobleem in energie-oogstende sensornetwerken.
2. Theoretisch Bewijs van Dominantie: De auteurs bewijzen (Lemma 4 en Lemma 5) dat de FPA-benadering de NPA-benadering domineert; elk schema dat haalbaar is onder NPA is ook haalbaar onder FPA, maar FPA kan oplossingen vinden in scenario's waar NPA faalt vanwege het gebrek aan preëmptie.
3. Oneindige Horizon Garantie: Het werk demonstreert dat de eindige schema's die door de ILP worden geproduceerd, geldig zijn over de potentieel oneindige levensduur van het systeem door energieneutraliteit over de hyperperiode af te dwingen.
4. Discretisatieanalyse: Het artikel kwantificeert de benaderingsfout die wordt geïntroduceerd door de continuïteit van de tijd te discretiseren in het FPA-model (Lemma 6), waarbij de fout wordt begrensd door de helft van het verbruik per tijdstap.

Experimentele Resultaten

De auteurs hebben beide benaderingen geëvalueerd met behulp van synthetische scenario's gegenereerd via een aangepast UUniFast-algoritme, waarbij de inflatiefactor (de ratio van verbruik tot oogst) varieerde van 1,2 tot 6.

• Haalbaarheid: FPA vond consistent haalbare oplossingen voor inflatiefactoren tot 3,2, terwijl de haalbaarheid van NPA aanzienlijk daalde naarmate de inflatiefactor toenam. FPA behield een hoge haalbaarheid totdat de inflatiefactor de 5 naderde, waar energiebeperkingen theoretisch onmogelijk te voldoen waren.
• Oplostijd: NPA vereiste aanzienlijk meer rekentijd en bereikte vaak de limiet van 480 seconden naarmate het probleem meer beperkt werd. FPA vertoonde veel snellere convergentie en bleef computationeel efficiënt, zelfs voor moeilijke instanties.
• Synchronisatie-overhead: NPA produceerde schema's met zeer weinig toestandsveranderingen (lage synchronisatiekosten), wat resulteerde in stabiele activatiepatronen. In contrast hiermee resulteerde FPA in een aanzienlijk hoger aantal moduswijzigingen per tijdseenheid, wat wijst op een hogere implementatiecomplexiteit en potentieel energieverlies door schakelen.
• Discretisatiesensitiviteit: Naarmate de tijddiscretisatiestap ($\Delta t$) afnam, nam de oplostijd voor NPA scherp toe, terwijl de oplostijd voor FPA geleidelijker toenam. NPA vereiste ook ongeveer twee keer zoveel binaire beslissingsvariabelen als FPA vanwege hulpvariabelen voor blokstarts.

Betekenis en Claims

Het artikel beweert een gat in de literatuur te vullen door het bieden van exacte, optimale planning via ILP voor sensoren die zowel energie verbruiken als oogsten, waarbij specif specifiek wordt ingegaan op de afleiding van een eindige, herhaalbare hyperperiode die continue temporele dekking over een oneindige horizon garandeert.

De auteurs positioneren hun werk als een vergelijkende analyse van twee strategieën:

• FPA wordt gepresenteerd als de robuuste oplossing voor moeilijke energieomgevingen, in staat om haalbare schema's te vinden waar rigide benaderingen falen, zij het met hogere synchronisatiekosten.
• NPA wordt gepresenteerd als een praktisch alternatief voor scenario's waar implementatieeenvoud en een lage synchronisatie-overhead prioriteit hebben boven het vinden van een oplossing in zeer beperkte energieomstandigheden.

Het artikel concludeert dat hoewel FPA beter presteert dan NPA wat betreft haalbaarheid en oplostijd, NPA "betere kwaliteit" oplossingen biedt in termen van stabiliteit en lagere synchronisatie-overhead. De auteurs suggereren dat toekomstig werk hybride methoden moet verkennen om deze afwegingen in balans te brengen en het kader uit te breiden naar stochastische energie-oogstpercentages (bijv. zon of wind) en real-world deployment traces.