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

Resumo Técnico: Agendamento de Tarefas Consciente de Energia Baseado em MDP para IoT sem Bateria

Declaração do Problema
Dispositivos da Internet das Coisas (IoT) sem bateria dependem de colheita de energia ambiental, levando a operações intermitentes que devem ser gerenciadas por meio de agendamento consciente de energia. Este desafio é particularmente agudo em aplicações de monitoramento periódico, onde uma cadeia específica de tarefas — sensoriamento, computação local e transmissão sem fio — deve ser concluída dentro de um ciclo de relatórios fixo. A dificuldade central reside em equilibrar duas restrições concorrentes: intermitência de energia e restrições de tempo rígidas.

• Restrição de Energia: Executar uma tarefa requer tensão de capacitor suficiente para garantir que o dispositivo não experimente uma falha de energia (tensão caindo abaixo de um limiar de desligamento) antes que a tarefa seja concluída.
• Restrição de Tempo: As tarefas devem aderir a precedências estritas (sensoriamento $\to$ computação $\to$ transmissão) e janelas de início permitidas. Adiar uma tarefa para colher mais energia corre o risco de perder o prazo para tarefas subsequentes ou o próprio ciclo, enquanto iniciar uma tarefa muito cedo com energia insuficiente corre o risco de falha de energia.

Abordagens existentes frequentemente focam na viabilidade de curto prazo, otimização de ciclo único ou modelos de energia simplificados, falhando em otimizar conjuntamente o desempenho de longo prazo sob restrições rígidas e chegadas de energia estocásticas.

Metodologia
Os autores formulam o problema de agendamento como um Processo de Decisão de Markov (MDP) de Recompensa Média de Longo Prazo. O quadro modela explicitamente a dinâmica do sistema para capturar o compromisso entre segurança energética e conformidade com prazos.

1. Modelo do Sistema:

   • O dispositivo opera em ciclos periódicos de duração $T_s$, divididos em unidades de tempo discretas.
   • A energia é colhida por um transdutor de Colheita de Energia (EH) e armazenada em um capacitor. A evolução da tensão é modelada usando dinâmicas de circuito RC, considerando o carregamento durante a colheita e a descarga durante a execução da tarefa ou o sono.
   • Uma métrica de probabilidade de "execução segura" é definida para quantificar a probabilidade de que uma tarefa seja concluída sem que a tensão do capacitor caia abaixo do limiar de desligamento $V_{out}$.

2. Formulação do MDP:

   • Espaço de Estados: Definido por uma tripla $(V_n, \tau_n, f_n)$, representando a tensão do capacitor, o relógio local (tempo dentro do ciclo) e uma bandeira de tarefa indicando o progresso da cadeia de tarefas (0: sensoriamento pendente, 1: sensoriamento concluído, 2: computação concluída, 3: transmissão concluída). A tensão contínua é quantizada para permitir métodos de MDP de estado finito.
   • Espaço de Ações: O dispositivo pode escolher dormir, sensoriamento, computar ou transmitir, sujeito às janelas permitidas do estado atual.
   • Design de Recompensa: Duas funções de recompensa são propostas. A Recompensa Básica acopla decisões de agendamento com a probabilidade de execução segura. A Recompensa Baseada em Sigmoidal introduz um parâmetro de limiar para penalizar execuções arriscadas e de baixa energia de forma mais acentuada, promovendo agendamento conservador em estados de energia intermediários para reduzir falhas de energia.

3. Derivação da Política:

   • Os autores provam que a Cadeia de Markov induzida é unichain (contendo exatamente uma classe recorrente), garantindo que a recompensa média de longo prazo seja independente do estado inicial.
   • Eles estabelecem que a polição estacionária ótima possui uma estrutura de limiar em relação à tensão do capacitor. Isso significa que, para qualquer passo de tempo e estágio de tarefa dado, existe um limiar de tensão acima do qual o dispositivo deve executar a tarefa e abaixo do qual deve dormir.
   • Isso leva ao agendador Baseado em Limiar Estacionário Ótimo (OSTB), que pode ser computado offline usando Programação Linear (LP).

4. Extensão para Energia Correlacionada:

   • Para abordar cenários realistas onde as chegadas de energia são temporalmente correlacionadas (por exemplo, condições de luz variáveis), o quadro é estendido ao aumentar o estado com uma variável de modo EH governada por um processo de Markov de estado finito.
   • Condições suficientes são fornecidas para mostrar que a estrutura baseada em limiar permanece ótima neste cenário correlacionado, com limiares agora dependendo tanto do passo de tempo quanto do modo EH atual.

Principais Contribuições

1. Formulação de MDP com Restrições Rígidas: O artigo lança o agendamento periódico de tarefas sem bateria como um MDP de estado finito que impõe explicitamente janelas de início permitidas rígidas, precedência de tarefas e condições de execução segura derivadas da dinâmica do capacitor, indo além das penalidades de utilidade suave usadas em trabalhos anteriores.
2. Design Conservador de Recompensa: Uma nova função de recompensa baseada em sigmoidal é introduzida para promover explicitamente agendamento conservador em estados de energia intermediários, reduzindo efetivamente falhas de energia enquanto mantém objetivos de conclusão de tarefas de longo prazo.
3. Caracterização Estrutural: Os autores provam a propriedade unichain do MDP e demonstram que a política ótima é baseada em limiar. Isso reduz o espaço de busca de política de um mapeamento geral para um conjunto de limiares de tensão, permitindo o cálculo eficiente do agendador OSTB.
4. Extensão para Colheita de Energia Correlacionada: O quadro é estendido para lidar com colheita de energia correlacionada via um modelo de Markov de estado finito, preservando a optimalidade baseada em limiar sob condições específicas.
5. Avaliação Abrangente: O agendador OSTB proposto é comparado com uma heurística de Primeira a Vencer com Guarda de Energia (EDF-EG) e uma política Tão-Tarde-Quanto-Possível (ALAP).

Resultados
Simulações numéricas demonstram a superioridade do agendador OSTB:

• Desempenho: O OSTB alcança uma taxa de conclusão de cadeia completa de longo prazo mais alta (ciclos bem-sucedidos de sensoriamento-computação-transmissão) em comparação com EDF-EG e ALAP, particularmente quando a energia colhida é escassa.
• Confiabilidade: O design de recompensa baseado em sigmoidal reduz significativamente o número de falhas de energia em comparação com a função de recompensa básica.
• Latência: Em regimes de baixa energia, o OSTB alcança menor latência de execução do que as linhas de base ao equilibrar adaptativamente a colheita de energia e a execução de tarefas, enquanto o ALAP sofre de latência máxima devido à sua estratégia "esperar até o último momento".
• EH Correlacionado: Em cenários de energia correlacionada, a política OSTB aumentada adapta os limiares com base no modo EH atual, melhorando ainda mais as taxas de conclusão ponta a ponta.
• Escalabilidade: A complexidade de computação offline é polinomial na dimensão do estado discretizado, enquanto a complexidade de implementação online é $O(1)$ por passo de tempo, exigindo apenas uma consulta de limiares de tensão.

Significância
O artigo afirma que o quadro proposto fornece uma solução rigorosa e analiticamente tratável para agendamento de tarefas consciente de energia em IoT sem bateria. Ao acoplar explicitamente a disponibilidade de energia com a urgência do prazo através de uma política de limiar adaptativa, o agendador OSTB gerencia efetivamente o compromisso fundamental entre esperar por mais energia e o risco de perder prazos. O trabalho destaca que, para dispositivos com armazenamento de energia limitado, otimizar conjuntamente segurança e tempo produz ganhos de desempenho significativos sobre heurísticas que otimizam apenas um desses fatores. A caracterização estrutural da política ótima oferece um caminho de implementação prática, evitando a necessidade de aprendizado online complexo ou computação em tempo real pesada.