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

Resumen Técnico: Programación de Tareas Consciente de la Energía Basada en MDP para IoT sin Batería

Enunciado del Problema
Los dispositivos del Internet de las Cosas (IoT) sin batería dependen de la recolección de energía ambiental, lo que conduce a operaciones intermitentes que deben gestionarse mediante programación consciente de la energía. Este desafío es particularmente agudo en aplicaciones de monitoreo periódico donde una cadena específica de tareas —sensado, computación local y transmisión inalámbrica— debe completarse dentro de un ciclo de reporte fijo. La dificultad central radica en equilibrar dos restricciones competitivas: intermitencia energética y restricciones temporales estrictas.

• Restricción Energética: Ejecutar una tarea requiere un voltaje de capacitor suficiente para asegurar que el dispositivo no experimente una falla de energía (voltaje que cae por debajo de un umbral de apagado) antes de que la tarea se complete.
• Restricción Temporal: Las tareas deben adherirse a una precedencia estricta (sensado $\to$ computación $\to$ transmisión) y ventanas de inicio permisibles. Retrasar una tarea para recolectar más energía corre el riesgo de perder el plazo límite para tareas posteriores o el ciclo mismo, mientras que iniciar una tarea demasiado pronto con energía insuficiente corre el riesgo de una falla de energía.

Los enfoques existentes a menudo se centran en la viabilidad a corto plazo, la optimización de un solo ciclo o modelos de energía simplificados, fallando en optimizar conjuntamente el rendimiento a largo plazo bajo restricciones estrictas y llegadas de energía estocásticas.

Metodología
Los autores formulan el problema de programación como un Proceso de Decisión de Markov (MDP) de Recompensa Promedio a Largo Plazo. El marco modela explícitamente la dinámica del sistema para capturar la compensación entre la seguridad energética y el cumplimiento de los plazos.

1. Modelo del Sistema:

   • El dispositivo opera en ciclos periódicos de duración $T_s$, divididos en unidades de tiempo discretas.
   • La energía se recolecta mediante un transductor de Recolección de Energía (EH) y se almacena en un capacitor. La evolución del voltaje se modela utilizando dinámicas de circuitos RC, contabilizando la carga durante la recolección y la descarga durante la ejecución de tareas o el sueño.
   • Se define una métrica de probabilidad de "ejecución segura" para cuantificar la probabilidad de que una tarea se complete sin que el voltaje del capacitor caiga por debajo del umbral de apagado $V_{out}$.

2. Formulación MDP:

   • Espacio de Estados: Definido por una terna $(V_n, \tau_n, f_n)$, que representa el voltaje del capacitor, el reloj local (tiempo dentro del ciclo) y una bandera de tarea que indica el progreso de la cadena de tareas (0: sensado pendiente, 1: sensado completado, 2: computación completada, 3: transmisión completada). El voltaje continuo se cuantiza para habilitar métodos de MDP de estado finito.
   • Espacio de Acciones: El dispositivo puede elegir dormir, sensar, computar o transmitir, sujeto a las ventanas permisibles del estado actual.
   • Diseño de Recompensa: Se proponen dos funciones de recompensa. La Recompensa Básica acopla las decisiones de programación con la probabilidad de ejecución segura. La Recompensa Basada en Sigmoide introduce un parámetro umbral para penalizar más severamente las ejecuciones arriesgadas y de baja energía, promoviendo una programación conservadora en estados de energía intermedios para reducir las fallas de energía.

3. Derivación de la Política:

   • Los autores demuestran que la Cadena de Markov inducida es unichain (contiene exactamente una clase recurrente), asegurando que la recompensa promedio a largo plazo sea independiente del estado inicial.
   • Establecen que la política estacionaria óptima tiene una estructura umbral con respecto al voltaje del capacitor. Esto significa que para cualquier paso de tiempo dado y etapa de tarea, existe un umbral de voltaje por encima del cual el dispositivo debe ejecutar la tarea y por debajo del cual debe dormir.
   • Esto conduce al programador Óptimo Estacionario Basado en Umbrales (OSTB), que puede calcularse fuera de línea utilizando Programación Lineal (LP).

4. Extensión a Energía Correlacionada:

   • Para abordar escenarios realistas donde las llegadas de energía están correlacionadas temporalmente (por ejemplo, condiciones de luz variables), el marco se extiende aumentando el estado con una variable de modo EH gobernada por un proceso de Markov de estado finito.
   • Se proporcionan condiciones suficientes para mostrar que la estructura basada en umbrales permanece óptima en este entorno correlacionado, con umbrales que ahora dependen tanto del paso de tiempo como del modo EH actual.

Contribuciones Clave

1. Formulación MDP con Restricciones Estrictas: El artículo plantea la programación periódica de tareas sin batería como un MDP de estado finito que hace cumplir explícitamente ventanas de inicio permisibles estrictas, precedencia de tareas y condiciones de ejecución segura derivadas de la dinámica del capacitor, yendo más allá de las penalizaciones de utilidad suaves utilizadas en trabajos anteriores.
2. Diseño Conservador de Recompensa: Se introduce una nueva función de recompensa basada en sigmoide para promover explícitamente una programación conservadora en estados de energía intermedios, reduciendo efectivamente las fallas de energía mientras se mantienen los objetivos de finalización de tareas a largo plazo.
3. Caracterización Estructural: Los autores demuestran la propiedad unichain del MDP y demuestran que la política óptima es basada en umbrales. Esto reduce el espacio de búsqueda de políticas de un mapeo general a un conjunto de umbrales de voltaje, permitiendo un cálculo eficiente del programador OSTB.
4. Extensión a EH Correlacionado: El marco se extiende para manejar la recolección de energía correlacionada mediante un modelo de Markov de estado finito, preservando la optimalidad basada en umbrales bajo condiciones específicas.
5. Evaluación Exhaustiva: El programador OSTB propuesto se compara con una heurística de Fecha Límite Más Próxima Primero con Guardia de Energía (EDF-EG) y una política Tan Tardío Como Sea Posible (ALAP).

Resultados
Las simulaciones numéricas demuestran la superioridad del programador OSTB:

• Rendimiento: OSTB logra una tasa de finalización de cadena completa a largo plazo más alta (ciclos exitosos de sensado-computación-transmisión) en comparación con EDF-EG y ALAP, particularmente cuando la energía recolectada es escasa.
• Fiabilidad: El diseño de recompensa basado en sigmoide reduce significativamente el número de fallas de energía en comparación con la función de recompensa básica.
• Latencia: En regímenes de baja energía, OSTB logra una latencia de ejecución más baja que las líneas base al equilibrar adaptativamente la recolección de energía y la ejecución de tareas, mientras que ALAP sufre de latencia máxima debido a su estrategia de "esperar hasta el último momento".
• EH Correlacionado: En escenarios de energía correlacionada, la política OSTB aumentada adapta los umbrales según el modo EH actual, mejorando aún más las tasas de finalización de extremo a extremo.
• Escalabilidad: La complejidad de cálculo fuera de línea es polinómica en la dimensión del estado discretizado, mientras que la complejidad de implementación en línea es $O(1)$ por paso de tiempo, requiriendo solo una búsqueda de umbrales de voltaje.

Significado
El artículo afirma que el marco propuesto proporciona una solución rigurosa y analíticamente tratable para la programación de tareas consciente de la energía en IoT sin batería. Al acoplar explícitamente la disponibilidad de energía con la urgencia del plazo a través de una política de umbral adaptativa, el programador OSTB gestiona efectivamente la compensación fundamental entre esperar más energía y el riesgo de perder plazos. El trabajo destaca que para dispositivos con almacenamiento de energía limitado, optimizar conjuntamente la seguridad y el tiempo produce ganancias de rendimiento significativas sobre heurísticas que optimizan solo uno de estos factores. La caracterización estructural de la política óptima ofrece una ruta de implementación práctica, evitando la necesidad de aprendizaje en línea complejo o computación en tiempo real pesada.