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

Technische Zusammenfassung: Hybride diskrete Grauwolfen-Optimierung für die Spektrumzuweisung in elastischen optischen Netzwerken

Problemstellung
Die vorliegende Arbeit befasst sich mit dem Teilproblem der Spektrumzuweisung (Spectrum Assignment, SA) innerhalb der umfassenderen Herausforderung des Routing und Spectrum Assignment (RSA) in elastischen optischen Netzwerken (EONs). Da Anwendungen mit hohen Bandbreiten das Verkehrsaufkommen vorantreiben, werden traditionelle Festraster-Wellenlängenmultiplex-Netzwerke (WDM) zunehmend unzureichend. EONs bieten eine Lösung durch flexible Spektrumsallokation unter Verwendung kleinerer Granularität. Das RSA-Problem ist jedoch NP-schwer, insbesondere in großflächigen Netzwerken, da drei kritische Bedingungen gleichzeitig erfüllt werden müssen:

1. Spektrumskontinuität (Spectrum Continuity): Die Indizes der Frequenzslots müssen über alle physischen Verbindungen eines Pfades hinweg identisch bleiben.
2. Spektrumskongruenz (Spectrum Contiguity): Die zugewiesene Bandbreite muss einen kontinuierlichen Block aus benachbarten Frequenzslots bilden, ohne Fragmentierung.
3. Überlappungsfreiheit (Non-overlapping): Ein Frequenzslot auf einer Verbindung kann zu einem gegebenen Zeitpunkt nur eine Verbindungsanforderung bedienen.

Das spezifische Ziel dieser Arbeit ist es, die gesamte Nutzung von Frequenzslots (FSs) in großen optischen Netzwerken zu minimieren, um die Kapazität und Effizienz des Netzwerks zu steigern.

Methodik
Die Autoren schlagen einen hybriden diskreten Grauwolfen-Optimierer (Grey Wolf Optimizer, GWO) vor, der mit Simulated Annealing (SA) integriert wurde, bezeichnet als SA-GWO.

• Grauwolfen-Optimierer (GWO): Der Basisalgorithmus ahmt die soziale Hierarchie und das Jagdverhalten von Grauwölfen (Alpha, Beta, Delta und Omega) nach. Er wurde aufgrund seiner starken Fähigkeiten zur globalen Exploration gewählt. Die Autoren stellen jedoch fest, dass der Standard-GWO unter vorzeitiger Konvergenz und dem Verfangen in lokalen Minima leiden kann, insbesondere in großen Suchräumen.
• Diskrete Anpassung: Da das SA-Problem eine diskrete Ordnung von Anfragen anstelle von kontinuierlichen Variablen beinhaltet, passen die Autoren den GWO an. Sie ersetzen die standardmäßige vektorbasierte Distanzberechnung durch die Hamming-Distanz, um die Unähnlichkeit zwischen Lösungsvektoren (Permutationen von Anfragen) zu messen.
• Hybridisierung mit Simulated Annealing (SA): Um die Einschränkungen des Standard-GWO zu adressieren, wird SA in den Positionsaktualisierungsmechanismus eingebettet.
  • Anstatt die Wolfspositionen rein deterministisch basierend auf den Alpha-, Beta- und Delta-Anführern zu aktualisieren, generiert der Algorithmus für jeden Wolf eine benachbarte Lösung mittels einer Swap-Mutation, die proportional zur Hamming-Distanz ist.
  • Die Annahme dieser neuen Lösung folgt dem Metropolis-Kriterium. Wenn die neue Lösung besser ist, wird sie akzeptiert. Wenn sie schlechter ist, wird sie mit einer Wahrscheinlichkeit $P = e^{-\Delta E/T}$ akzeptiert, wobei $\Delta E$ die Differenz der Fitness und $T$ die aktuelle Temperatur ist.
  • Diese probabilistische Annahme ermöglicht es dem Algorithmus, lokale Optima zu verlassen und so die Exploration und Exploitation effektiver auszubalancieren als der GWO allein.
• Evaluierung: Lösungen werden basierend auf der maximal Anzahl der genutzten Frequenzslots bewertet, wobei die Constraints des Distance Spectrum Assignment (DSA)-Modells, einschließlich der Guardband-Anforderungen, eingehalten werden.

Wesentliche Beiträge

1. Algorithmische Innovation: Die Entwicklung eines hybriden Metaheuristik-Ansatzes (SA-GWO), der speziell auf das diskrete Spektrumzuweisungsproblem in EONs zugeschnitten ist.
2. Mechanismenintegration: Die neuartige Integration von Simulated Annealing in die Positionsaktualisierungsphase des GWO, um den Suchprozess zu verfeinern und vorzeitige Konvergenz zu verhindern.
3. Diskrete Formulierung: Die Anpassung des GWO für die diskrete kombinatorische Optimierung unter Verwendung der Hamming-Distanz und Swap-Mutationen anstelle von kontinuierlicher Vektorarithmetik.

Experimentelle Ergebnisse
Der vorgeschlagene SA-GWO-Algorithmus wurde unter Verwendung folgender Parameter evaluiert:

• Topologien: Verschiedene synthetische Graphen, die mit Python-Bibliotheken (NetworkX und Matplotlib) generiert wurden, einschließlich Zufallsgraphen und vollständiger Graphen mit Knotenzahlen von 14 bis 25.
• Vergleiche: Die Ergebnisse wurden gegen einen standardmäßigen Two-Phase-Algorithmus, den Standard-GWO-Algorithmus sowie optimale Lösungen, die durch den CPLEX 12.9.0-Solver (für kleinere Instanzen) generiert wurden, verglichen.

Ergebnisse:

• Kleine bis mittlere Graphen (14–19 Knoten): Der SA-GWO-Algorithmus übertraf den referenzierten Two-Phase-Algorithmus deutlich. In vielen Fällen lieferte er Ergebnisse, die sehr nahe an den von CPLEX gefundenen optimalen Lösungen lagen.
• Große Graphen (20–25 Knoten): Obwohl der SA-GWO nicht die optimalen CPLEX-Ergebnisse erreichte (was für NP-schwere Probleme in diesem Maßstab zu erwarten ist), zeigte er eine signifikante Überlegenheit gegenüber dem Standard-GWO-Algorithmus, indem er die maximal genutzte Anzahl an Frequenzslots reduzierte.
• Skalierbarkeit: Der hybride Ansatz erwies sich als robust im Umgang mit zunehmender Komplexität bei wachsender Graphgröße, während der Standard-GWO eine größere Leistungsdifferenz im Vergleich zur hybriden Version aufwies.

Bedeutung und Behauptungen
Die Arbeit behauptet, dass der vorgeschlagene SA-GWO-Ansatz die Netzwerkkapazität durch die Optimierung der Frequenzslot-Allokation effektiv steigert. Die primäre Bedeutung liegt in der Fähigkeit des Algorithmus, ein besseres Gleichgewicht zwischen globaler Exploration und lokaler Exploitation zu erreichen. Durch die Einbindung von Simulated Annealing mildert die Methode das Risiko ab, in lokalen Minima stecken zu bleiben – ein häufiges Problem bei groß angelegten RSA-Aufgaben.

Die Autoren kommen zu dem Schluss, dass die hybride Technik die Spektrumfragmentierung signifikant minimiert und die Ressourcenausnutzung im Vergleich zu traditionellen Ansätzen maximiert. Sie positionieren diese Arbeit als einen Schritt zur Lösung komplexer, groß angelegter RSA-Probleme, bei denen exakte Methoden (wie CPLEX) rechnerisch prohibitiv werden, und bieten eine hochwertige heuristische Alternative an.

Zukünftige Arbeiten
Die Autoren skizzieren bescheiden zukünftige Richtungen, darunter:

• Die Erweiterung des Algorithmus auf dynamische Spektrumzuweisungsszenarien, um Echtzeit-Verkehrsanforderungen zu handhaben.
• Die Untersuchung der Multi-Objective-Optimierung, um gleichzeitig Stromverbrauch und Latenz zu adressieren.
• Die Untersuchung der Integration von maschinellem Lernen-basierten Heuristiken, um eine prädiktive Spektrumsallokation zu verbessern.