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

Résumé Technique : Ordonnancement de tâches à faible consommation énergétique basé sur les MDP pour l'IoT sans batterie

Énoncé du problème
Les dispositifs de l'Internet des Objets (IoT) sans batterie dépendent de la récupération d'énergie ambiante, ce qui entraîne des opérations intermittentes devant être gérées par un ordonnancement conscient de l'énergie. Ce défi est particulièrement aigu dans les applications de surveillance périodique où une chaîne spécifique de tâches — détection, calcul local et transmission sans fil — doit être achevée dans un cycle de rapport fixe. La difficulté fondamentale réside dans l'équilibre entre deux contraintes concurrentes : l'intermittence énergétique et les contraintes temporelles strictes.

• Contrainte énergétique : L'exécution d'une tâche nécessite une tension de condensateur suffisante pour garantir que le dispositif ne subisse pas une panne de courant (tension tombant en dessous d'un seuil de coupure) avant l'achèvement de la tâche.
• Contrainte temporelle : Les tâches doivent respecter une stricte précédence (détection $\to$ calcul $\to$ transmission) et des fenêtres de démarrage permises. Retarder une tâche pour récolter plus d'énergie risque de faire manquer l'échéance des tâches suivantes ou du cycle lui-même, tandis que lancer une tâche trop tôt avec une énergie insuffisante risque une panne de courant.

Les approches existantes se concentrent souvent sur la faisabilité à court terme, l'optimisation d'un seul cycle ou des modèles énergétiques simplifiés, échouant à optimiser conjointement les performances à long terme sous contraintes strictes et des arrivées d'énergie stochastiques.

Méthodologie
Les auteurs formulent le problème d'ordonnancement comme un Processus de Décision Markovien (MDP) à récompense moyenne à long terme. Le cadre modélise explicitement la dynamique du système pour capturer le compromis entre la sécurité énergétique et le respect des délais.

1. Modèle du système :

   • Le dispositif fonctionne par cycles périodiques de durée $T_s$, divisés en unités de temps discrètes.
   • L'énergie est récoltée via un transducteur de récupération d'énergie (EH) et stockée dans un condensateur. L'évolution de la tension est modélisée en utilisant la dynamique des circuits RC, tenant compte de la charge pendant la récolte et de la décharge pendant l'exécution des tâches ou le sommeil.
   • Une métrique de probabilité d'« exécution sûre » est définie pour quantifier la probabilité qu'une tâche s'achève sans que la tension du condensateur ne descende en dessous du seuil de coupure $V_{out}$.

2. Formulation MDP :

   • Espace d'états : Défini par un triplet $(V_n, \tau_n, f_n)$, représentant la tension du condensateur, l'horloge locale (temps dans le cycle) et un indicateur de tâche signalant l'avancement de la chaîne de tâches (0 : détection en attente, 1 : détection terminée, 2 : calcul terminé, 3 : transmission terminée). La tension continue est quantifiée pour permettre des méthodes MDP à états finis.
   • Espace d'actions : Le dispositif peut choisir de dormir, de détecter, de calculer ou de transmettre, sous réserve des fenêtres permises de l'état actuel.
   • Conception de la récompense : Deux fonctions de récompense sont proposées. La Récompense de base couple les décisions d'ordonnancement avec la probabilité d'exécution sûre. La Récompense basée sur la sigmoïde introduit un paramètre de seuil pour pénaliser plus sévèrement les exécutions risquées à faible énergie, favorisant un ordonnancement conservateur dans les états énergétiques intermédiaires afin de réduire les pannes de courant.

3. Dérivation de la politique :

   • Les auteurs prouvent que la Chaîne de Markov induite est unichaine (contenant exactement une classe récurrente), garantissant que la récompense moyenne à long terme est indépendante de l'état initial.
   • Ils établissent que la politique stationnaire optimale possède une structure de seuil par rapport à la tension du condensateur. Cela signifie que pour tout instant donné et toute étape de tâche, il existe un seuil de tension au-dessus duquel le dispositif doit exécuter la tâche et en dessous duquel il doit dormir.
   • Cela conduit à l'ordonnanceur Optimal Stationnaire à Seuil (OSTB), qui peut être calculé hors ligne en utilisant la Programmation Linéaire (LP).

4. Extension aux énergies corrélées :

   • Pour traiter des scénarios réalistes où les arrivées d'énergie sont temporellement corrélées (par exemple, des conditions lumineuses variables), le cadre est étendu en augmentant l'état avec une variable de mode EH régie par un processus de Markov à états finis.
   • Des conditions suffisantes sont fournies pour montrer que la structure basée sur les seuils reste optimale dans ce contexte corrélé, les seuils dépendant désormais à la fois de l'instant et du mode EH actuel.

Contributions clés

1. Formulation MDP à contraintes strictes : L'article présente l'ordonnancement périodique de tâches sans batterie comme un MDP à états finis qui impose explicitement les fenêtres de démarrage permises, la précédence des tâches et les conditions d'exécution sûre dérivées de la dynamique du condensateur, dépassant les pénalités d'utilité souples utilisées dans les travaux antérieurs.
2. Conception de récompense conservatrice : Une nouvelle fonction de récompense basée sur la sigmoïde est introduite pour promouvoir explicitement un ordonnancement conservateur dans les états énergétiques intermédiaires, réduisant efficacement les pannes de courant tout en maintenant les objectifs d'achèvement des tâches à long terme.
3. Caractérisation structurelle : Les auteurs prouvent la propriété unichaine du MDP et démontrent que la politique optimale est basée sur des seuils. Cela réduit l'espace de recherche de la politique d'une généralité de mappage à un ensemble de seuils de tension, permettant un calcul efficace de l'ordonnanceur OSTB.
4. Extension EH corrélée : Le cadre est étendu pour gérer la récolte d'énergie corrélée via un modèle de Markov à états finis, préservant l'optimalité basée sur les seuils sous des conditions spécifiques.
5. Évaluation complète : L'ordonnanceur OSTB proposé est mis en comparaison avec une heuristique Earliest-Deadline-First avec Garde Énergétique (EDF-EG) et une politique As-Late-As-Possible (ALAP).

Résultats
Les simulations numériques démontrent la supériorité de l'ordonnanceur OSTB :

• Performance : OSTB atteint un taux d'achèvement complet de la chaîne à long terme (cycles réussis de détection-calcul-transmission) plus élevé que EDF-EG et ALAP, en particulier lorsque l'énergie récoltée est rare.
• Fiabilité : La conception de la récompense basée sur la sigmoïde réduit considérablement le nombre de pannes de courant par rapport à la fonction de récompense de base.
• Latence : Dans les régimes à faible énergie, OSTB atteint une latence d'exécution plus faible que les lignes de base en équilibrant de manière adaptative la récolte d'énergie et l'exécution des tâches, tandis que ALAP souffre d'une latence maximale due à sa stratégie « attendre jusqu'au dernier moment ».
• EH corrélé : Dans les scénarios d'énergie corrélée, la politique OSTB augmentée adapte les seuils en fonction du mode EH actuel, améliorant davantage les taux d'achèvement de bout en bout.
• Évolutivité : La complexité du calcul hors ligne est polynomiale par rapport à la dimension de l'état discrétisé, tandis que la complexité de l'implémentation en ligne est $O(1)$ par pas de temps, ne nécessitant qu'une recherche de seuils de tension.

Signification
L'article affirme que le cadre proposé fournit une solution rigoureuse et analytiquement traitable pour l'ordonnancement de tâches conscient de l'énergie dans l'IoT sans batterie. En couplant explicitement la disponibilité énergétique avec l'urgence des délais via une politique de seuil adaptative, l'ordonnanceur OSTB gère efficacement le compromis fondamental entre l'attente d'une énergie supplémentaire et le risque de manquer les délais. Le travail met en évidence que pour les dispositifs à stockage d'énergie limité, l'optimisation conjointe de la sécurité et du timing produit des gains de performance significatifs par rapport aux heuristiques qui n'optimisent que l'un de ces facteurs. La caractérisation structurelle de la politique optimale offre une voie d'implémentation pratique, évitant le besoin d'apprentissage en ligne complexe ou de calculs temps réel lourds.