Hybrid Discrete Grey Wolf Optimization Approach for solving Spectrum Assignment Problem in Elastic Optical Networks

Technische Samenvatting: Hybride Discrete Grey Wolf Optimization voor Spectrumtoewijzing in Elastic Optical Networks

Probleemstelling
Het artikel behandelt het Spectrum Assignment (SA) subprobleem binnen de bredere Routing and Spectrum Assignment (RSA) uitdaging in Elastic Optical Networks (EONs). Omdat applicaties met een hoge bandbreedte de groei van het verkeer aanjagen, worden traditionele fixed-grid Wavelength Division Multiplexing (WDM) netwerken ontoereikend. EONs bieden een oplossing door middel van flexibele spectrumallocatie met een kleinere granulariteit. Echter, het RSA-probleem is NP-hard, met name in grootschalige netwerken, vanwege de noodzaak om drie kritieke beperkingen simultaan te voldoen:

1. Spectrumcontinuïteit: De indexen van de frequentieslots moeten identiek blijven over alle fysieke verbindingen in een pad.
2. Spectrumcontiguousiteit: De gealloceerde bandbreedte moet een continue blok van aangrenzende frequentieslots vormen zonder fragmentatie.
3. Niet-overlappend: Een frequentieslot op een verbinding kan slechts één verzoek tegelijkertijd bedienen.

Het specifieke doel van dit werk is het minimaliseren van het totale gebruik van frequentieslots (FSs) in grootschalige optische netwerken om de netcapaciteit en efficiëntie te verhogen.

Methodologie
De auteurs stellen een Hybride Discrete Grey Wolf Optimizer (GWO) voor die geïntegreerd is met Simulated Annealing (SA), getermd SA-GWO.

• Grey Wolf Optimizer (GWO): Het basisalgoritme bootst de sociale hiërarchie en het jachtgedrag van grijze wolven na (Alpha, Beta, Delta en Omega). Het is gekozen vanwege de sterke capaciteiten voor globale exploratie. De auteurs merken echter op dat standaard GWO kan lijden onder voortijdige convergentie en het vastlopen in lokale minima, vooral in grote zoekruimtes.
• Discrete Adaptatie: Aangezien het SA-probleem betrekking heeft op discrete ordening van verzoeken in plaats van continue variabelen, passen de auteurs GWO aan. Ze vervangen de standaard vectorgebaseerde afstandsberekeningen door Hamming-afstand om de dissimilariteit tussen oplossingsvectoren (permutaties van verzoeken) te meten.
• Hybridisatie met Simulated Annealing (SA): Om de beperkingen van standaard GWO aan te pakken, is SA ingebed in het mechanisme voor de positie-update.
  • In plaats van de positie van wolven deterministisch bij te werken op basis van enkel de Alpha, Beta en Delta leiders, genereert het algoritme een naburige oplossing voor elke wolf met behulp van een swap-mutatie die proportioneel is aan de Hamming-afstand.
  • De acceptatie van deze nieuwe oplossing volgt het Metropolis-criterium. Als de nieuwe oplossing beter is, wordt deze geaccepteerd. Als de nieuwe oplossing slechter is, wordt deze geaccepteerd met een waarschijnlijkheid $P = e^{-\Delta E/T}$, waarbij $\Delta E$ het verschil in fitness is en $T$ de huidige temperatuur.
  • Deze probabilistische acceptatie stelt het algoritme in staat om lokale optima te ontsnappen, waardoor exploratie en exploitatie effectiever in balans worden gebracht dan met GWO alleen.
• Evaluatie: Oplossingen worden geëvalueerd op basis van het maximale aantal gebruikte frequentieslots, waarbij wordt voldaan aan de constraints van het Distance Spectrum Assignment (DSA) model, inclusief guardband-vereisten.

Belangrijkste Bijdragen

1. Algoritmische Innovatie: De ontwikkeling van een hybride meta-heuristiek (SA-GWO) die specifiek is afgestemd op het discrete Spectrum Assignment probleem in EONs.
2. Mechanisme-integratie: De nieuwe integratie van Simulated Annealing in de positie-updatefase van GWO om het zoekproces te verfijnen en voortijdige convergentie te voorkomen.
3. Discrete Formulering: De adaptatie van GWO voor discrete combinatorische optimalisatie met behulp van Hamming-afstand en swap-mutaties, in plaats van continue vectoraritmetiek.

Experimentele Resultaten
Het voorgestelde SA-G\WO algoritme werd geëvalueerd met behulp van:

• Topologieën: Diverse synthetische grafen gegenereerd met Python-bibliotheken (NetworkX en Matplotlib), inclusioneel willekeurige grafen en complete grafen met een aantal knooppunten variërend van 14 tot 25.
• Vergelijkingen: De resultaten werden vergeleken met een standaard Two-Phase algoritme, het standaard GWO algoritme en optimale oplossingen gegenereerd door de CPLEX 12.9.0 solver (voor kleinere instanties).

Bevindingen:

• Kleine tot Middelgrote Grafen (14–19 knooppunten): Het SA-GWO algoritme presteerde aanzienlijk beter dan het Two-Phase referentiealgoritme. In veel gevallen produceerde het resultaten die zeer dicht bij de optimale oplossingen lagen die door CPLEX werden gevonden.
• Grote Grafen (20–25 knooppunten): Hoewel de SA-GWO niet de optimale CPLEX-resultaten bereikte (wat te verwachten is voor NP-harde problemen op deze schaal), demonstreerde het een significante superioriteit ten opzichte van het standaard GWO algoritme, waarbij het maximaal aantal gebruikte frequentieslots werd verminderd.
• Schaalbaarheid: De hybride aanpak bleek robuust in het beheren van de toegenomen complexiteit naarmate de grootte van de grafen groeide, terwijl standaard GWO een grotere prestatiekloof vertoonde vergeleken met de hybride versie.

Significantie en Claims
Het artikel claimt dat de voorgestelde SA-GWO aanpak de netcapaciteit effectief verbetert door de spectrumallocatie te optimaliseren. De primaire significantie ligt in het vermogen van het algoritme om een betere balans te bereiken tussen globale exploratie en lokale exploitatie. Door Simulated Annealing te incorporeren, mitigeert de methode het risico om vast te lopen in lokale minima, een veelvoorkomend probleem in grootschalige RSA-problemen.

De auteurs concluderen dat de hybride techniek de spectrumfragmentatie aanzienlijk vermindert en de hulpbronnenbenutting maximaliseert in vergelijking met traditionele benaderingen. Zij positioneren dit werk als een stap naar het oplossen van complexe, grootschalige RSA-problemen waar exacte methoden (zoals CPLEX) computationeel onhaalbaar worden, en bieden een hoogwaardig heuristisch alternatief.

Toekomstig Werk
De auteurs schetsen bescheiden toekomstige richtingen, waaronder:

• Het uitbreiden van het algoritme naar dynamische spectrumassignatie scenario's om realtime verkeersvraag te beheren.
• Het onderzoeken van multi-objective optimalisatie om gelijktijdig energieverbruik en latentie aan te pakken.
• Het verkennen van de integratie van machine learning-gebaseerde heuristieken om voorspellende spectrumallocatie te verbeteren.