Duality-Guided Graph Learning for Real-Time Joint Connectivity and Routing in LEO Mega-Constellations

Resumo Técnico: Aprendizado de Grafos Guiado por Dualidade para Conectividade Conjunta e Roteamento em Tempo Real em Megaconstelações LEO

Definição do Problema
Megaconstelações de Órbita Terrestre Baixa (LEO) utilizam Links Inter-Satélites a Laser (LISLs) para formar backbones de redes não terrestres de alta capacidade. No entanto, o gerenciamento dessas redes apresenta um desafio significativo devido a três fatores primários:

1. Restrições de Hardware: Terminais de Comunicação a Laser (LCTs) são escassos, e cada terminal pode sustentar apenas um link ativo por vez devido a restrições de apontamento mecânico e ao Campo de Visão (FOR) limitado.
2. Topologia Dinâmica: O grafo da constelação é variante no tempo devido à dinâmica orbital, fazendo com que a viabilidade do link e os pontos críticos de tráfego (hotspots) mudem rapidamente.
3. Complexidade de Otimização Conjunta: O problema exige estabelecer simultaneamente conexões LISL, rotear o tráfego e alocar taxas de fluxo sob demandas de tráfego globais heterogêneas e disponibilidade de gateways. Isso é formulado como um Programa Inteiro Misto (MIP), que é NP-difícil e computacionalmente proibitivo para operações em larga escala e em tempo real. Métodos de otimização iterativos tradicionais (ex: descida de subgradiente) são lentos demais para se adaptarem dentro do "tempo coerente" do grafo da constelação (a duração em que a topologia permanece amplamente inalterada, tipicamente ~1 segundo para sistemas do tipo Starlink).

Metodologia: DeepLaDu
O artigo propõe o DeepLaDu, um framework de aprendizado profundo guiado pela dualidade Lagrangiana que substitui a otimização iterativa por uma inferência de passagem única. A metodologia central envolve:

1. Decomposição de Dualidade Lagrangiana: O problema de otimização conjunta (P1) é relaxado movendo as restrições de capacidade por link para a função objetivo usando multiplicadores de Lagrange ($\lambda$). Esses multiplicadores são interpretados como preços de congestionamento por aresta.

   • Preços altos indicam restrições de capacidade apertadas, desencorajando o roteamento de tráfego sobre esses links enquanto priorizam o estabelecimento desses links para aumentar a capacidade.
   • Esta decomposição separa o problema em três subproblemas independentes resolvíveis via Emparelhamento de Peso Máximo (MWM) para conexões, Caminho Mais Curto Primeiro (SPF) para roteamento e Programação Linear (LP) para alocação de taxa.

2. Inferência por Rede Neural de Grafos (GNN): Em vez de atualizar $\lambda$ iterativamente via descida de subgradiente, uma Rede de Atenção de Grafos (GATv2) é treinada para inferir diretamente os preços de congestionamento ideais a partir do estado da constelação em uma única passagem direta (forward pass).

   • Entrada: O grafo de adjacência dos satélites ($G_{SAT}$), onde os nós representam satélites (características: taxas de atendimento de tráfego/demanda) e as arestas representam pares de LISL conectáveis (características: capacidade agregada do link).
   • Saída: Multiplicadores de Lagrange ($\lambda$) para todos os pares de satélites vizinhos, limitados entre [0, 1].

3. Treinamento Baseado em Subgradiente: Como a função dual é não diferenciável devido à estrutura de MIP subjacente, a GNN é treinada usando uma função de perda derivada do subgradiente da função dual. O loop de treinamento amostra estados da constelação, calcula os preços previstos pela GNN, resolve os subproblemas decompostos para obter o subgradiente e atualiza os pesos da GNN. Isso fornece feedback direto ao nível da aresta sobre os preços de congestionamento, ao contrário de trabalhos anteriores que dependem de métricas de nível de grafo ou de nó mais grosseiras.

Principais Contribuições

• Formulação: O problema conjunto de conexão LISL, roteamento e alocação de taxa é formulado como uma otimização inteira mista sobre grafos variantes no tempo e decomposto via dualidade Lagrangiana.
• Framework DeepLaDu: Um novo framework que treina uma GNN para prever preços de congestionamento por aresta em um único passo, eliminando a latência das atualizações duais iterativas.
• Mecanismo de Treinamento: Introdução de uma função de perda por subgradiente ao nível da aresta que permite um treinamento escalável e estável ao fornecer feedback direto sobre decisões ao nível do link.
• Análise Teórica: Prova de convergência para um ponto estacionário sob suposições moderadas e uma análise de complexidade mostrando que a abordagem escala polinomialmente com o tamanho da constelação, tornando-a adequada para operação em tempo real.
• Avaliação de Desempenho: Simulações extensas em constelações realistas do tipo Starlink com restrições ópticas e de tráfego.

Resultos
Simulações demonstram que o DeepLaDu alcança o seguinte:

• Ganhos de Throughput: Até 20% de maior throughput de rede comparado a baselines não conjuntos ou heurísticos (ex: emparelhamento baseado em grade, emparelhamento aleatório ou otimização separada). Em cenários de extrema escassez de LCT, o gano chega a 50%.
• Eficiência Computacional: O DeepLaDu iguala o desempenho da otimização dual iterativa (LaDu), mas com ordens de magnitude a menos de tempo de computação. Ele opera bem dentro do tempo coerente da constelação (aprox. 1 segundo), enquanto métodos iterativos frequentemente excedem esse limite.
• Escalabilidade: O método mantém o desempenho através de diferentes tamanhos de constelação (500 a 1500 satélites) e diferentes tipos de constelação (Starlink vs. OneWeb).
• Estudos de Ablação: O método supera consistentemente os baselines em várias configurações de LCT, jitter de apontamento e espalhamento angular de feixe.

Significância e Alegações
O artigo afirma que o DeepLaDu fornece uma solução escalável e interpretável para coordenação de recursos em tempo real em backbones de redes não terrestres. Ao incorporar a estrutura de otimização fundamentada da dualidade Lagrangiana no processo de aprendizado, o método garante que os preços de congestionamento aprendidos mantenham sua interpretação econômica como sinais ao nível do link. A abordagem efetivamente transforma um problema de otimização iterativo e de alta latência em um procedimento de inferência computacionalmente eficiente de passo único, abordando a necessidade crítica de reconfiguração rápida em megaconstelações LEO dinâmicas. Os autores observam que, embora o trabalho atual se concentre em configurações determinísticas, extensões futuras podem incorporar incerteza de previsão de tráfego e aprendizado online.