Long-Horizon Wireless Link Scheduling with State-Augmented Graph Neural Networks

Resumo Técnico: Escalonamento de Link Sem Fio de Longo Horizonte com Redes Neurais de Grafos com Aumento de Estado

Formulação do Problema
O artigo aborda o problema do escalonamento ideal de links em redes de comunicação sem fio dispositivo-a-dispositivo de larga escala. O objetivo é maximizar a taxa de soma média de longo prazo ao longo de um horizonte de tempo $T$, garantindo que cada link $i$ atinja um requisito de taxa média mínima $\Delta_i$. Diferente das abordagens tradicionais que focam na maximização de taxas de soma instantâneas, este problema requer políticas variantes no tempo para satisfazer restrições temporais e evitar interferência.

A rede é modelada sob um modelo de interferência primária, onde dois links interferem se compartilharem um dispositivo comum. Isso é representado por um grafo de conflito $G(V, E)$ com matriz de adjacência $A$. O problema de escalonamento é formulado como um problema de otimização combinatória restrita (Equação 3), onde as variáveis de decisão são vetores binários $s(t) \in \{0, 1\}^K$ para cada slot de tempo $t$. O espaço de busca total é combinatório no produto do número de links $K$ e do horizonte de tempo $T$, tornando as soluções exatas computacionalmente intratáveis para redes de larga escala.

Metodologia
Os autores propõem uma abordagem baseada em aprendizado fundamentada em dualidade lagrangiana e aumento de estado. A metodologia procede em três etapas teóricas e práticas principais:

1. Análise do Domínio Dual e Inviabilidade Primal:
   Os autores analisam primeiramente o problema usando o dual lagrangiano. Eles demonstram que os maximizadores lagrangianos para uma variável dual fixa $\lambda$ são invariantes no tempo (Proposição 1). Ou seja, o escalonamento ideal $s^\dagger(t, \lambda)$ não muda ao longo do tempo. Consequentemente, uma política estática derivada de uma única variável dual ótima não pode satisfazer os requisitos de taxa mínima para todos os links simultaneamente, pois falha em alternar as transmissões para evitar interferência. Isso torna a abordagem primal-dual padrão de encontrar um único $\lambda^\star$ e um escalonamento estático correspondente insuficiente para o problema de longo horizonte.

2. Dinâmica de Gradiente Descendente Dual:
   Para superar a limitação da invariância temporal, o artigo investiga a dinâmica do gradiente descendente dual. Ao atualizar iterativamente a variável dual $\lambda(u)$ com base nas violações de restrição (subgradientes) e computar o maximizador lagrangiano $s^\ddagger(u)$ correspondente em cada etapa, o algoritmo gera uma sequência de escalonamentos. A análise teórica (Proposição 3) mostra que, embora os escalonamentos individuais nesta sequência possam não ser ótimos, a taxa média da sequência $s^\ddagger(1:T)$ é assintoticamente ótima e viável conforme $T \to \infty$. Isso sugere que a solução para o problema de longo horizonte reside em aprender uma política que imite a trajetória do gradiente descendente dual.

3. Redes Neurais de Grafos com Aumento de Estado (SAGNN):
   Para implementar isso de forma eficiente sem resolver a maximização lagrangiana NP-difícil em cada etapa, os autores propõem uma política paramétrica $\Phi(A, \lambda; H)$ usando uma Rede Neural de Grafos (GNN).

   • Aumento de Estado: A principal inovação é tratar a variável dual $\lambda(t)$ como um estado interno (ou sinal de entrada) para a GNN, juntamente com a topologia da rede $A$. Isso permite que a política adapte as decisões de escalonamento dinamicamente com base no nível atual de violação de restrição.
   • Treinamento (Offline): Os parâmetros da GNN $H$ são treinados offline para maximizar o lagrangiano instantâneo $M(s, \lambda)$ sobre uma distribuição de topologias de rede e variáveis duais. A função de perda penaliza as violações de restrição ponderadas pelo $\lambda$ amostrado.
   • Execução (Online): Durante a execução, a GNN treinada gera um escalonamento $s(t)$ baseado no estado atual da rede $A$ e na variável dual atual $\lambda(t)$. A variável dual é então atualizada online usando o subgradiente da violação de restrição (Equação 21), criando um sistema de malha fechada que imita a dinâmica do gradiente descendente dual.

Principais Contribuições

• Insight Teórico: O artigo estabelece que, embora os maximizadores lagrangianos ótimos sejam invariantes no tempo e, portanto, inviáveis para o problema de longo horizonte restrito, a sequência de maximizadores gerada pelo gradiente descendente dual produz taxas médias assintoticamente ótimas.
• Design de Algoritmo: Os autores introduzem uma SAGNN (State-Augmented GNN) que aprende a aproximar os maximizadores lagrangianos. Ao incorporar as variáveis duais como entradas dinâmicas, a política aprende a variar as decisões de escalonamento ao longo do tempo, equilibrando efetivamente a satisfação de restrições e a maximização de desempenho.
• Escalabilidade: A abordagem desacopla a complexidade do horizonte de tempo $T$ da parametrização de aprendizado. A GNN aprende um mapeamento para um único passo de tempo, evitando a necessidade de aprender uma sequência de comprimento $T$ diretamente, o que seria computacionalmente proibitivo.

Result Resultados
Simulações numéricas extensas foram conduzidas em Grafos Geométricos Aleatórios (RGGs) com aproximadamente 500 links.

• Satisfação de Restrições: O algoritmo proposto satisfaz com sucesso as restrições de taxa mínima para a vasta maioria dos links. Para os poucos links sub-escalonados, as violações de restrição são menores.
• Desempenho: O método supera várias heurísticas de linha de base em termos de taxa de soma média e alcança um tempo de execução mais rápido.
• Generalização: A política aprendida demonstra robustez, generalizando através de diferentes requisitos de transmissão e adaptando-se efetivamente ao longo do tempo. A política consegue alternar entre links não interferentes, priorizando aqueles com níveis mais altos de violação de restrição conforme as variáveis duais evoluem.

Significância e Alegações
O artigo alega que sua principal significância reside em preencher a lacuna entre a otimalidade teórica do gradiente descendente dual e a necessidade prática de políticas de escalonamento baseadas em aprendizado eficientes. Argumenta-se que o aumento de estado é uma técnica necessária para permitir que as GNNs aprendam políticas variantes no tempo necessárias para restrições de longo horizonte, uma tarefa que políticas invariantes no tempo padrão ou o aprendizado direto de sequências (que é excessivamente caro) não conseguem resolver de forma eficaz. O trabalho valida que aprender a imitar a dinâmica dual permite a solução de problemas combinatórios de alta dimensão e restritos em redes sem fio com eficiência computacional.