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

Technische Samenvatting: Long-Horizon Draadloze Link-scheduling met State-Augmented Graph Neural Networks

Probleemformulering
Het artikel behandelt het probleem van optimale link-scheduling in grootschalige device-to-device draadloze netwerken. Het doel is om de langetermijn gemiddelde somrate te maximaliseren over een tijdshorizon $T$, terwijl elke link $i$ een minimale gemiddelde rate-eis $\Delta_i$ haalt. In tegenstelling tot traditionele benaderingen die zich richten op het maximaliseren van instantane somrates, vereist dit probleem tijdsvariërende policies om temporele restricties te voldoen en interferentie te vermijden.

Het netwerk wordt gemodelleerd onder een primair interferentiemodel, waarbij twee links interfereren als ze een gemeenschappelijk device delen. Dit wordt gerepresenteerd door een conflict-graaf $G(V, E)$ met een adjacency matrix $A$. Het scheduling-probleem wordt geformuleerd als een geconstrueerd combinatorisch optimalisatieprobleem (Vergelijking 3), waarbij de beslissingsvariabelen binaire vectoren $s(t) \in \{0, 1\}^K$ zijn voor elke tijdstap $t$. De totale zoekruimte is combinatorisch in het product van het aantal links $K$ en de tijdshorizon $T$, waardoor exacte oplossingen computationeel onhaalbaar zijn voor grootschalige netwerken.

Methodologie
De auteurs stellen een learning-gebaseerde aanpak voor die geworteld is in Lagrangiaanse dualiteit en state augmentation. De methodologie verloopt via drie belangrijke theoretische en praktische stappen:

1. Dual Domain Analyse en Primal Infeasibility:
   De auteurs analyseren het probleem eerst met behulp van de Lagrangiaanse duale vorm. Zij tonen aan dat de Lagrangiaanse maximizers voor een vaste duale variabele $\lambda$ tijd-invariant zijn (Propositie 1). Dat wil zeggen, de optimale schedule $s^\dagger(t, \lambda)$ verandert niet over de tijd. Bijgevolg kan een statische policy, afgeleid van een enkele optimale duale variabele $\lambda^\star$, niet simultaan voldoen aan de minimale rate-eisen voor alle links, omdat deze er niet in slaagt om transmissies af te wisselen om interferentie te vermijden. Dit maakt de standaard primal-dual benadering van het vinden van een enkele optimale $\lambda^\star$ en een bijbehorende statische schedule ontoereikend voor het long-horizon probleem.

2. Dual Gradient Descent Dynamiek:
   Om de beperking van tijd-invariantie te overwinnen, onderzoekt het artikel de dual gradient descent dynamiek. Door de duale variabele $\lambda(u)$ iteratief bij te werken op basis van constraint-schendingen (subgradients) en de bijbehorende Lagrangiaanse maximizer $s^\ddagger(u)$ in elke stap te berekenen, genereert het algoritme een sequentie van schedules. Theoretische analyse (Propositie 3) toont aan dat hoewel individuele schedules in deze sequentie mogelijk niet optimaal zijn, de gemiddelde rate van de sequentie $s^\ddagger(1:T)$ asymptotisch optimaal en haalbaar is als $T \to \infty$. Dit suggereert dat de oplossing voor het long-horizon probleem ligt in het leren van een policy die de trajectorie van dual gradient descent nabootst.

3. State-Augmented Graph Neural Networks (SAGNN):
   Om dit efficiënt te implementeren zonder de NP-harde Lagrangiaanse maximalisatie bij elke stap op te lossen, stellen de auteurs een parametrische policy $\Phi(A, \lambda; H)$ voor met behulp van een Graph Neural Network (GNN).

   • State Augmentation: De belangrijkste innovatie is het behandelen van de duale variabele $\lambda(t)$ als een interne staat (of input signaal) voor de GNN, naast de netwerktopologie $A$. Dit stelt de policy in staat om de scheduling-beslissingen dynamisch aan te passen op basis van het huidige niveau van de constraint-schending.
   • Training (Offline): De GNN-parameters $H$ worden offline getraind om de instantane Lagrangiaanse $M(s, \lambda)$ te maximaliseren over een distributie van netwerktopologieën en duale variabelen. De loss-functie bestraft constraint-schendingen, gewogen door de gesamplede $\lambda$.
   • Executie (Online): Tijdens de executie genereert de getrainde GNN een schedule $s(t)$ op basis van de huidige netwerkstaat $A$ en de huidige duale variabele $\lambda(t)$. De duale variabele wordt vervolgens online bijgewerkt met behulp van de subgradient van de constraint-schending (Vergelijking 21), wat een closed-loop systeem creëert dat de dual gradient descent dynamiek nabootst.

Belangrijkste Bijdragen

• Theoretisch Inzicht: Het artikel stelt vast dat hoewel optimale Lagrangiaanse maximizers tijd-invariant zijn en daarmee ontoereikend voor het geconstreinde long-horizon probleem, de sequentie van maximizers gegenereerd door dual gradient descent asymptotisch optimale gemiddelde rates oplevert.
• Algoritme Ontwerp: De auteurs introduceren een State-Augmented GNN (SAGNN) die leert de Lagrangiaanse maximizers te benaderen. Door duale variabelen als dynamische inputs te incorporeren, leert de policy de scheduling-beslissingen over de tijd te variëren, waardoor een effectieve balans wordt gevonden tussen het voldoen aan constraints en het maximaliseren van prestaties.
• Schaalbaarheid: De aanpak ontkoppelt de complexiteit van de tijdshorizon $T$ van de learning parameterisatie. De GNN leert een mapping voor een enkele tijdstap, waardoor het direct leren van een sequentie van lengte $T$ (wat computationeel prohibitief zou zijn) wordt vermeden.

Resultaten
Uitgebreide numerieke simulaties zijn uitgevoerd op Random Geometric Graphs (RGG's) met ongeveer 500 links.

• Constraint Satisfaction: Het voorgestelde algoritme voldoet succesvol aan de minimale rate-eisen voor het overgrote deel van de links. Voor de weinige onder-gescheduled links zijn de schendingen van de constraints minimaal.
• Prestaties: De methode presteert beter dan verschillende baseline heuristieken wat betreft de gemiddelde somrate en bereikt een snellere runtime.
• Generalisatie: De geleerde policy vertoont robuustheid, generaliseert over verschillende transmissie-eisen en past zich effectief aan over de tijd. De policy wisselt succesvol tussen niet-interfererende links en geeft prioriteit aan links met een hogere mate van constraint-schending naarmate de duale variabelen evolueren.

Betekenis en Claims
Het artikel claimt dat de primaire betekenis ligt in het overbruggen van de kloof tussen de theoretische optimaliteit van dual gradient descent en de praktische behoefte aan efficiënte, learning-gebaseerde scheduling policies. Er wordt betoogd dat state augmentation een noodzakelijke techniek is om GNN's in staat te stellen tijdsvariërende policies te leren die vereist zijn voor long-horizon constraints, een taak die standaard tijd-invariante policies of directe sequentie-learning (die te duur is) niet effectief kunnen oplossen. Het werk valideert dat het nabootsen van duale dynamiek de oplossing van hoog-dimensionale, geconstreerde combinatorische problemen in draadloze netwerken met computationele efficiëntie mogelijk maakt.