Resumo Técnico: Rumo a uma Abordagem de PLI para Cobertura Temporal em Redes de Sensores

Declaração do Problema

O artigo aborda o desafio de garantir a cobertura temporal em redes de sensores externas alimentadas por colheita de energia (energy harvesting). Embora a cobertura espacial (garantir que cada Ponto de Interesse, ou POI, seja monitorado por pelo menos um sensor) seja um problema bem estudado, manter a cobertura temporal contínua é difícil quando os sensores dependem de fontes de energia limitadas que flutuam ou são insuficientes para sustentar a operação contínua.

O contexto específico do problema envolve sensores onde a taxa de consumo de energia durante o estado ativo ($c(S_j)$) excede a taxa de colheita de energia ($h(S_j)$). Consequentemente, os sensores não podem operar indefinidamente sem interrupções. Eles devem alternar entre um estado ativo (monitorando POIs, consumindo energia líquida) e um estado passivo (colhendo energia para recarregar). O desafio central é orquestrar os ciclos de ativação e carregamento de múltiplos sensores para garantir que cada POI seja coberto o tempo todo, respeitando as restrições individuais de bateria e garantindo que o cronograma seja sustentável ao longo de um horizonte infinito.

Metodologia

Os autores propõem um modelo de sistema baseado em Programação Linear Inteira (PLI) para gerar cronogramas de sensores viáveis. O sistema consiste em $m$ POIs e $n$ sensores, onde cada sensor possui um conjunto de cobertura fixo, uma capacidade de bateria, uma taxa de consumo e uma taxa de colheita. Os autores assumem um perfil de carregamento linear dentro de uma janela de energia definida $[e_{min}, e_{max}]$ e taxas de colheita constantes (visando fontes estáveis como RF).

Duas abordagens distintas de PLI são desenvolvidas para resolver o problema de agendamento:

1. Abordagem Não-Preemptiva (NPA - Non-Preemptive Approach):

   • Mecanismo: Os sensores seguem regras de alternância estritas baseadas nos níveis de bateria. Um sensor transita de passivo para ativo apenas quando totalmente carregado e permanece ativo por uma duração fixa até que a bateria atinja um limite inferior. Transições de estado não são permitidas no meio de um ciclo.
   • Modelagem: Esta abordagem abstrai a dinâmica de energia em restrições temporais. Ela não rastreia explicitamente os níveis instantâneos de energia na PLI; em vez disso, impõe a viabilidade ao restringir a duração e a ordem dos intervalos passivos e ativos.
   • Compromisso (Trade-off): Isso simplifica a implementação (exigindo apenas temporizadores) e reduz o número de mudanças de estado, mas limita a flexibilidade do agendamento.

2. Abordagem Totalmente Preemptiva (FPA - Fully Preemptive Approach):

   • Mecanismo: Os sensores podem alternar estados a qualquer momento, desde que o nível da bateria permaneça acima de um limite mínimo. As transições de estado não estão vinculadas a ciclos completos de carga/descarga.
   • Modelagem: Esta abordagem rastreia explicitamente o nível de energia $e(S_i, t)$ em cada etapa de tempo discreta dentro da PLI. Inclui restrições para acúmulo de energia, consumo e o requisito de que o nível de bateria ao final do hiperperíodo seja pelo menos igual ao nível inicial para garantir a repetibilidade.
   • Compromisso (Trade-off): Oferece maior flexibilidade para encontrar cronogramas viáveis sob restrições de energia apertadas, mas aumenta a complexidade da PLI e o número de mudanças de estado necessárias (sobrecarga de sincronização).

Fundamentos Teóricos Principais:

• Hiperperíodo: O cronograma é projetado para ser cíclico, repetindo-se sobre um hiperperíodo $H$ computado.
• Validade e Repetibilidade: Os autores estabelecem condições (Teorema 1) garantindo que a bateria nunca se esvazie durante o hiperperíodo (validade) e que o estado de energia ao final do ciclo permita a repetição infinita (repetibilidade/neutralidade de energia).
• Pré-filtro de Viabilidade: Uma verificação leve baseada no Lema 3 é aplicada antes de resolver a PLI para verificar se a soma das razões de colheita para consumo dos sensores que cobrem um POI é de pelo menos 1.

Principais Contribuições

1. Formulações Duplas de PLI: O artigo apresenta dois modelos distintos de PLI (NPA e FPA) para o problema de cobertura temporal em redes de sensores com colheita de energia.
2. Prova Teórica de Dominância: Os autores provam (Lema 4 e Lema 5) que a abordagem FPA domina a abordagem NPA; qualquer cronograma viável sob NPA também é viável sob FPA, mas a FPA pode encontrar soluções em cenários onde a NPA falha devido à sua falta de preempção.
3. Garantia de Horizonte Infinito: O trabalho demonstra que os cronogramas finitos produzidos pela PLI são válidos ao longo da vida útil potencialmente infinita do sistema, ao impor a neutralidade de energia sobre o hiperperíodo.
4. Análise de Discretização: O artigo quantifica o erro de aproximação introduzido pela discretização do tempo contínuo no modelo FPA (Lema 6), limitando o erro a metade da taxa de consumo por etapa de tempo.

Resultados Experimentais

Os autores avaliaram ambas as abordagens usando cenários sintéticos gerados via um algoritmo UUniFast modificado, variando o fator de inflação (a razão entre consumo e colheita) de 1,2 a 6.

• Viabilidade: A FPA encontrou consistentemente soluções viáveis para fatores de inflação de até 3,2, enquanto a viabilidade da NPA caiu significativamente conforme o fator de inflação aumentava. A FPA manteve alta viabilidade até que o fator de inflação se aproximasse de 5, onde as restrições de energia tornaram-se teoricamente impossíveis de satisfazer.
• Tempo de Resolução: A NPA exigiu significativamente mais tempo computacional, frequentemente atingindo o limite de tempo de 480 segundos conforme o problema se tornava mais restrito. A FPA exibiu uma convergência muito mais rápida e permaneceu computacionalmente eficiente mesmo para instâncias difíceis.
• Sobrecarga de Sincronização: A NPA produziu cronogramas com pouquíssimas mudanças de estado (baixo custo de sincronização), resultando em padrões de ativação suaves. Em contraste, a FPA resultou em um número significativamente maior de mudanças de modo por unidade de tempo, implicando maior complexidade de implementação e potencial desperdício de energia devido à alternância.
• Sensibilidade à Discretização: À medida que a etapa de discretização do tempo ($\Delta t$) diminuía, o tempo de resolução da NPA aumentava drasticamente, enquanto o tempo de resolução da FPA aumentava de forma mais gradual. A NPA também exigiu aproximadamente o dobro de variáveis de decisão binária em comparação com a FPA devido às variáveis auxiliares para inícios de bloco.

Significância e Alegações

O artigo afirma preencher uma lacuna na literatura ao fornecer agendamento exato e ótimo via PLI para sensores que tanto consomem quanto colhem energia, abordando especificamente a derivação de um hiperperíodo finito e repetível que garante a cobertura temporal contínua ao longo de um horizonte infinito.

Os autores posicionam seu trabalho como uma análise comparativa de duas estratégias:

• A FPA é apresentada como a solução robusta para ambientes de energia difíceis, capaz de encontrar cronogramas viáveis onde abordagens rígidas falham, embora com maiores custos de sincronização.
• A NPA é apresentada como uma alternativa prática para cenários onde a simplicidade de implementação e a baixa sobrecarga de alternância são priorizadas em relação à busca de uma solução em condições de energia altamente restritas.

O artigo conclui que, embora a FPA supere a NPA em termos de viabilidade e tempo de resolução, a NPA oferece soluções de "melhor qualidade" em termos de estabilidade e menor sobrecarga de sincronização. Os autores sugerem que trabalhos futuros devem explorar métodos híbridos para equilibrar esses compromissos e estender o framework para taxas de colheita de energia estocásticas (ex: solar ou eólica) e traços de implantação do mundo real.