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

Sintesi Tecnica: Programmazione di Collegamenti Wireless a Lungo Orizzonte con Reti Neurali a Grafo con Stato Aumentato

Formulazione del Problema
Il documento affronta il problema della programmazione ottimale dei collegamenti in reti device-to-device su larga scala. L'obiettivo è massimizzare la media a lungo termine del tasso di somma (sum rate) su un orizzonte temporale $T$, garantendo al contempo che ogni collegamento $i$ raggiunga un requisito di tasso medio minimo $\Delta_i$. A differenza degli approcci tradizionali che si concentrano sulla massimizzazione dei tassi di somma istantanei, questo problema richiede politiche variabili nel tempo per soddisfare i vincoli temporali ed evitare interferenze.

La rete è modellata sotto un modello di interferenza primario, in cui due collegamenti interferiscono se condividono un dispositivo comune. Ciò è rappresentato da un grafo di conflitto $G(V, E)$ con matrice di adiacenza $A$. Il problema di programmazione è formulato come un problema di ottimizzazione combinatoria vincolata (Equazione 3), dove le variabili decisionali sono vettori binari $s(t) \in \{0, 1\}^K$ per ogni slot temporale $t$. Lo spazio di ricerca totale è combinatorio nel prodotto tra il numero di collegamenti $K$ e l'orizzonte temporale $T$, rendendo le soluzioni esatte computazionalmente intrattabili per reti su larga scala.

Metodologia
Gli autori propongono un approccio basato sull'apprendimento, fondato sulla dualità lagrangiana e l'aumento dello stato. La metodologia procede in tre fasi teoriche e pratiche principali:

1. Analisi del Dominio Duale e Inammissibilità Primale:
   Gli autori analizzano prima il problema utilizzando il Lagrangiano duale. Dimostrano che i massimizzatori lagrangiani per una variabile duale fissa $\lambda$ sono invarianti nel tempo (Proposizione 1). Ovvero, lo schema ottimale $s^\dagger(t, \lambda)$ non cambia nel tempo. Di conseguenza, una politica statica derivata da un singolo $\lambda$ ottimale non può soddisfare i requisiti di tasso minimo per tutti i collegamenti simultaneamente, poiché non riesce ad alternare le trasmissioni per evitare interferenze. Ciò rende insufficiente per il problema a lungo orizzonte l'approccio primal-dual standard che consiste nel trovare un singolo $\lambda^\star$ e uno schema statico corrispondente.

2. Dinamica del Gradiente Duale:
   Per superare il limite dell'invarianza temporale, il documento investiga la dinamica del gradiente duale. Aggiornando iterativamente la variabile duale $\lambda(u)$ in base alle violazioni dei vincoli (subgradienti) e calcolando il corrispondente massimizzatore lagrangiano $s^\ddagger(u)$ ad ogni passo, l'algoritmo genera una sequenza di schemi. L'analisi teorica (Proposizione 3) mostra che, sebbene i singoli schemi in questa sequenza possano non essere ottimali, il tasso medio della sequenza $s^\ddagger(1:T)$ è asintoticamente ottimale e ammissibile quando $T \to \infty$. Ciò suggerisce che la soluzione del problema a lungo orizzonte risiede nell'apprendere una politica che imiti la traiettoria del gradiente duale.

3. Reti Neurali a Grafo con Stato Aumentato (SAGNN):
   Per implementare questo processo in modo efficiente senza risolvere la massimizzazione lagrangiana NP-hard ad ogni passo, gli autori propongono una politica parametrica $\Phi(A, \lambda; H)$ utilizzando una Rete Neurale a Grafo (GNN).

   • Aumento dello Stato: L'innovazione chiave è trattare la variabile duale $\lambda(t)$ come uno stato interno (o segnale di input) per la GNN, insieme alla topologia della rete $A$. Ciò consente alla politica di adattare le decisioni di programmazione dinamicamente in base al livello attuale di violazione del vincolo.
   • Addestramento (Offline): I parametri della GNN $H$ sono addestrati offline per massimizzare il Lagrangiano istantaneo $M(s, \lambda)$ su una distribuzione di topologie di rete e variabili duali. La funzione di perdita penalizza le violazioni dei vincoli pesate dal $\lambda$ campionato.
   • Esecuzione (Online): Durante l'esecuzione, la GNN addestrata genera uno schema $s(t)$ basato sullo stato attuale della rete $A$ e sulla variabile duale corrente $\lambda(t)$. La variabile duale viene quindi aggiornata online utilizzando il subgradiente della violazione del vincolo (Equazione 21), creando un sistema a ciclo chiuso che imita la dinamica del gradiente duale.

Contributi Chiave

• Intuizione Teorica: Il documento stabilisce che, sebbene i massimizzatori lagrangiani ottimali siano invarianti nel tempo e quindi inammissibili per il problema vincolato a lungo orizzonte, la sequenza di massimizzatori generata dal gradiente duale produce tassi medi asintoticamente ottimali.
• Design dell'Algoritmo: Gli autori introducono una SAGNN (State-Augmented GNN) che apprende ad approssimare i massimizzatori lagrangiani. Incorporando le variabili duali come input dinamici, la politica impara a variare le decisioni di programmazione nel tempo, bilanciando efficacementamente la soddisfazione dei vincoli e la massimizzazione delle prestazioni.
• Scalabilità: L'approccio scinde la complessità dell'orizzonte temporale $T$ dalla parametrizzazione dell'apprendimento. La GNN apprende una mappatura per un singolo passo temporale, evitando la necessità di apprendere direttamente una sequenza di lunghezza $T$, il che sarebbe computazionalmente proibitivo.

Risultati
Sono state condotte estese simulazioni numeriche su Grafi Geometrici Casuali (RGG) con circa 500 collegamenti.

• Soddisfazione dei Vincoli: L'algoritmo proposto soddisfa con successo i requisiti di tasso minimo per la stragrande maggioranza dei collegamenti. Per i pochi collegamenti sotto-programmati, le violazioni dei vincoli sono minori.
• Prestazioni: Il metodo supera diversi euristiche di base in termini di tasso di somma medio e raggiunge un tempo di esecuzione più rapido.
• Generalizzazione: La politica appresa dimostra robustezza, generalizzando attraverso diversi requisiti di trasmissione e adattandosi efficacemente nel tempo. La politica riesce ad alternare tra collegamenti non interferenti, dando priorità a quelli con livelli di violazione dei vincoli più elevati man mano che le variabili duali evolvono.

Significato e Rivendicazioni
Il documento sostiene che la sua importanza primaria risieda nel colmare il divario tra l'ottimalità teorica del gradiente duale e la necessità pratica di politiche di programmazione efficienti basate sull'apprendimento. Argomenta che l'aumento dello stato è una tecnica necessaria per consentire alle GNN di apprendere politiche variabili nel tempo richieste dai vincoli a lungo orizzonte, un compito che le politiche standard invarianti nel tempo o l'apprendimento diretto di sequenze (troppo costoso) non possono risolvere efficacemente. Il lavoro valida il fatto che apprendere a imitare le dinamiche duali permette di risolvere problemi combinatori vincolati ad alta dimensionalità nelle reti wireless con efficienza computazionale.