Resumen Técnico: Hacia un enfoque de PLI para la cobertura temporal en redes de sensores

Declaración del Problema

El artículo aborda el desafío de garantizar la cobertura temporal en redes de sensores al aire libre alimentadas por cosecha de energía (energy harvesting). Mientras que la cobertura espacial (asegurar que cada Punto de Interés, o POI, sea monitoreado por al menos un sensor) es un problema bien estudiado, mantener una cobertura temporal continua es difícil cuando los sensores dependen de fuentes de energía limitadas que fluctúan o son insuficientes para sostener una operación continua.

El contexto específico del problema involucra sensores donde la tasa de consumo de energía durante el estado activo ($c(S_j)$) excede la tasa de cosecha de energía ($h(S_j)$). En consecuencia, los sensores no pueden operar indefinidamente sin interrupción. Deben alternar entre un estado activo (monitoreo de POIs, consumo neto de energía) y un estado pasivo (cosecha de energía para recargar). El desafío central es orquestar los ciclos de activación y carga de múltiples sensores para garantizar que cada POI esté cubierto en todo momento, respetando las restricciones individuales de la batería y asegurando que el cronograma sea sostenible sobre un horizonte infinito.

Metodología

Los autores proponen un modelo de sistema basado en Programación Lineal Entera (PLI) para generar cronogramas de sensores factibles. El sistema consiste en $m$ POIs y $n$ sensores, donde cada sensor tiene un conjunto de cobertura fijo, una capacidad de batería, una tasa de consumo y una tasa de cosecha. Los autores asumen un perfil de carga lineal dentro de una ventana de energía definida $[e_{min}, e_{max}]$ y tasas de cosecha constantes (apuntando a fuentes estables como la RF).

Se desarrollan dos formulaciones distintas de PLI para resolver el problema de programación:

1. Enfoque No Preemptivo (NPA - Non-Preemptive Approach):

   • Mecanismo: Los sensores siguen reglas de conmutación estrictas basadas en los niveles de batería. Un sensor transiciona de pasivo a activo solo cuando está completamente cargado y permanece activo durante una duración fija hasta que la batería alcanza un umbral inferior. No se permiten transiciones de estado a mitad del ciclo.
   • Modelado: Este enfoque abstrae la dinámica de la energía en restricciones temporales. No rastrea explícitamente los niveles de energía instantáneos en la PLI; en su lugar, impone la factibilidad mediante la restricción de la duración y el orden de los intervalos pasivos y activos.
   • Compromiso (Trade-off): Esto simplifica la implementación (requiriendo solo temporizadores) y reduce el número de cambios de estado, pero limita la flexibilidad de la programación.

2. Enfoque Totalmente Preemptivo (FPA - Fully Preemptive Approach):

   • Mecanismo: Los sensores pueden cambiar de estado en cualquier momento, siempre que el nivel de la batería se mantenga por encima de un umbral mínimo. Las transiciones de estado no están ligadas a ciclos completos de carga o descarga.
   • Modelado: Este enfoque rastrea explícitamente el nivel de energía $e(S_i, t)$ en cada paso de tiempo discreto dentro de la PLI. Incluye restricciones para la acumulación de energía, el consumo y el requisito de que el nivel de batería al final del hiperperiodo sea al menos igual al nivel inicial para asegurar la capacidad de repetición (replayability).
   • Compromiso (Trade-off): Ofrece mayor flexibilidad para encontrar cronogramas factibles bajo restricciones energéticas estrictas, pero aumenta la complejidad de la PLI y el número de cambios de estado requeridos (sobrecarga de sincronización).

Fundamentos Teóricos Clave:

• Hiperperiodo: El cronograma está diseñado para ser cíclico, repitiéndose sobre un hiperperiodo $H$ calculado.
• Validez y Capacidad de Repetición: Los autores establecen condiciones (Teorema 1) que aseguran que la batería nunca se agote durante el hiperperiodo (validez) y que el estado de energía al final del ciclo permite la repetición infinita (capacidad de repetición/neutralidad energética).
• Prefiltro de Factibilidad: Se aplica una comprobación ligera basada en el Lema 3 antes de resolver la PLI para verificar si la suma de las razones de cosecha respecto al consumo para los sensores que cubren un POI es al menos 1.

Contribuciones Clave

1. Formulaciones Duales de PLI: El artículo presenta dos modelos de PLI distintos (NPA y FPA) para el problema de cobertura temporal en redes de sensores con cosecha de energía.
2. Prueba Teórica de Dominancia: Los autores demuestran (Lema 4 y Lema 5) que el enfoque FPA domina al enfoque NPA; cualquier cronograma factible bajo NPA también es factible bajo FPA, pero FPA puede encontrar soluciones en escenarios donde NPA falla debido a su falta de preemción.
3. Garantía de Horizonte Infinito: El trabajo demuestra que los cronogramas finitos producidos por la PLI son válidos sobre la vida útil potencialmente infinita del sistema al imponer la neutralidad energética sobre el hiperperiodo.
4. Análisis de Discretización: El artículo cuantifica el error de aproximación introducido al discretizar el tiempo continuo en el modelo FPA (Lema 6), acotando el error por la mitad de la tasa de consumo por paso de tiempo.

Resultados Experimentales

Los autores evaluaron ambos enfoques utilizando escenarios sintéticos generados mediante un algoritmo UUniFast modificado, variando el factor de inflación (la razón entre consumo y cosecha) de 1.2 a 6.

• Factibilidad: FPA encontró consistentemente soluciones factibles para factores de inflación de hasta 3.2, mientras que la factibilidad de NPA disminuyó significativamente a medida que el factor de inflación aumentaba. FPA mantuvo una alta factibilidad hasta que el factor de inflación se acercó a 5, donde las restricciones de energía se volvieron teóricamente imposibles de satisfacer.
• Tiempo de Resolución: NPA requirió significativamente más tiempo computacional, alcanzando a menudo el límite de tiempo de 480 segundos a medida que el problema se volvía más restringido. FPA exhibió una convergencia mucho más rápida y se mantuvo computacionalmente eficiente incluso para instancias difíciles.
• Sobrecarga de Sincronización: NPA produjo cronogramas con muy pocos cambios de estado (bajo costo de sincronización), resultando en patrones de activación suaves. En contraste, FPA resultó en un número significativamente mayor de cambios de modo por unidad de tiempo, lo que implica una mayor complejidad de implementación y un potencial desperdicio de energía debido al cambio de estado.
• Sensibilidad a la Discretización: A medida que el paso de discretización temporal ($\Delta t$) disminuía, el tiempo de resolución de NPA aumentaba bruscamente, mientras que el tiempo de resolución de FPA aumentaba más gradualmente. NPA también requirió aproximadamente el doble de variables de decisión binarias que FPA debido a las variables auxiliares para los inicios de bloque.

Significancia y Reclamaciones

El artículo afirma llenar un vacío en la literatura al proporcionar una programación exacta y óptima mediante PLI para sensores que tanto consumen como cosechan energía, abordando específicamente la derivación de un hiperperiodo finito y repetible que garantiza la cobertura temporal continua sobre un horizonte infinito.

Los autores posicionan su trabajo como un análisis comparativo de dos estrategias:

• FPA se presenta como la solución robusta para entornos energéticos difíciles, capaz de encontrar cronogramas factibles donde los enfoques rígidos fallan, aunque con mayores costos de sincronización.
• NPA se presenta como una alternativa práctica para escenarios donde se prioriza la simplicidad de implementación y la baja sobrecarga de conmutación sobre la búsqueda de una solución en condiciones energéticas altamente restringidas.

El artículo concluye que, si bien FPA supera a NPA en términos de factibilidad y tiempo de resolución, NPA ofrece soluciones de "mejor calidad" en términos de estabilidad y menor sobrecarga de sincronización. Los autores sugieren que el trabajo futuro debería explorar métodos híbridos para equilibrar estos compromisos y extender el marco a tasas de cosecha de energía estocásticas (por ejemplo, solar o eólica) y trazas de despliegue del mundo real.