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

Sintesi Tecnica: Ottimizzazione Ibrida del Grey Wolf per l'Assegnazione dello Spettro nelle Reti Ottiche Elastiche

Definizione del Problema
Il documento affronta il sottoproblema dell'Assegnazione dello Spettro (SA) all'interno della sfida più ampia del Routing e dell'Assegnazione dello Spettro (RSA) nelle Reti Ottiche Elastiche (EON). Poiché le applicazioni ad alta larghezza di banda guidano la crescita del traffico, le tradizionali reti WDM (Wavelength Division Multiplexing) a griglia fissa stanno diventando insufficienti. Le EON offrono una soluzione attraverso un'allocazione flessibile dello spettro utilizzando una granularità più piccola. Tuttavia, il problema RSA è NP-hard, particolarmente nelle reti su larga scala, a causa della necessità di soddisfare simultaneamente tre vincoli critici:

1. Continuità dello Spettro: Gli indici dei segmenti di frequenza (FS) devono rimanere identici attraverso tutti i collegamenti fisici in un percorso.
2. Contiguità dello Spettro: La larghezza di banda allocata deve formare un blocco continuo di segmenti di frequenza adiacenti senza frammentazione.
3. Non sovrapposizione: Un segmento di frequenza su un collegamento può servire una sola richiesta di connessione alla volta.

L'obiettivo specifico di questo lavoro è minimizzare l'utilizzo totale dei segmenti di frequenza (FS) nelle reti ottiche di grandi dimensioni per migliorare la capacità e l'efficienza della rete.

Metodologia
Gli autori propongono un Ottimizzatore Grey Wolf Discreto (GWO) Ibrido integrato con il Simulated Annealing (SA), denominato SA-GWO.

• Grey Wolf Optimizer (GWO): L'algoritmo di base imita la gerarchia sociale e il comportamento di caccia dei lupi grigi (Alpha, Beta, Delta e Omega). È stato scelto per le sue forti capacità di esplorazione globale. Tuttavia, gli autori osservano che il GWO standard può soffrire di convergenza prematura e intrappolamento in minimi locali, specialmente in spazi di ricerca di grandi dimensioni.
• Adattamento Discreto: Poiché il problema SA riguarda l'ordinamento discreto delle richieste piuttosto che variabili continue, gli autori adattano il GLO. Sostituiscono il calcolo standard della distanza basato su vettori con la distanza di Hamming per misurare la dissimilarità tra i vettori di soluzione (permutazioni delle richieste).
• Ibridazione con Simulated Annealing (SA): Per affrontare i limiti del GWO standard, il SA viene incorporato nel meccanismo di aggiornamento della posizione del GWO.
  • Invece di aggiornare deterministicamente le posizioni dei lupi basandosi solo sui leader Alpha, Beta e Delta, l'algoritmo genera una soluzione vicina per ogni lupo utilizzando una mutazione di scambio (swap mutation) proporzionale alla distanza di Hamming.
  • L'accettazione di questa nuova soluzione segue il criterio di Metropolis. Se la nuova soluzione è migliore, viene accettata. Se è peggiore, viene accettata con una probabilità $P = e^{-\Delta E/T}$, dove $\Delta E$ è la differenza di fitness e $T$ è la temperatura corrente.
  • Questa accettazione probabilistica permette all'algoritmo di sfuggire agli ottimi locali, bilanciando l'esplorazione e lo sfruttamento in modo più efficace rispetto al solo GWO.
• Valutazione: Le soluzioni vengono valutate in base al numero massimo di segmenti di frequenza utilizzati, rispettando i vincoli del modello di Assegnazione dello Spettro a Distanza (DSA), inclusi i requisiti di banda di guardia (guardband).

Contributi Chiave

1. Innovazione Algoritmica: Lo sviluppo di un meta-euristica ibrida (SA-GWO) specificamente progettata per il problema discreto dell'Assegnazione dello Spettro nelle EON.
2. Integrazione dei Meccanismi: La nuova integrazione del Simulated Annealing nella fase di aggiornamento della posizione del GWO per raffinare il processo di ricerca e prevenire la convergenza prematura.
3. Formulazione Discreta: L'adattamento del GWO per l'ottimizzazione combinatoria discreta utilizzando la distanza di Hamming e le mutazioni di scambio, anziché l'aritmetica vettoriale continua.

Risultati Sperimentali
L'algoritmo SA-GWO proposto è stato valutato utilizzando:

• Topologie: Vari grafi sintetici generati tramite librerie Python (NetworkX e Matplotlib), inclusi grafi casuali e grafi completi con un numero di nodi compreso tra 14 e 25.
• Confronti: I risultati sono stati messi a confronto con un algoritmo standard a due fasi (Two-Phase), l'algoritmo GWO standard e le soluzioni ottime generate dal solver CPLEX 12.9.0 (per istanze più piccole).

Risultati:

• Grafi da Piccoli a Medi (14–19 nodi): L'algoritmo SA-GWO ha superato significativamente l'algoritmo di riferimento a due fasi. In molti casi, ha prodotto risultati molto vicini alle soluzioni ottime trovate da CPLEX.
• Grafi Grandi (20–25 nodi): Sebbene il SA-GWO non abbia raggiunto i risultati ottimi di CPLEX (il che è previsto per problemi NP-hard a questa scala), ha dimostrato una superiorità significativa rispetto all'algoritmo GWO standard, riducendo il numero massimo di segmenti di frequenza utilizzati.
• Scalabilità: L'approccio ibrido si è dimostrato robusto nel gestire l'aumento della complessità all'aumentare delle dimensioni del grafo, mentre il GWO standard ha mostrato un divario di prestazioni maggiore rispetto alla versione ibrida.

Significato e Rivendicazioni
Il documento afferma che l'approccio SA-GWO proposto migliora efficacementamente la capacità di rete ottimizzando l'allocazione dei segmenti di frequenza. Il significato primario risiede nella capacità dell'algoritmo di raggiungere un migliore equilibrio tra esplorazione globale e sfruttamento locale. Incorporando il Simulated Annealing, il metodo mitiga il rischio di rimanere intrappolati in minimi locali, un problema comune nei problemi RSA su larga scala.

Gli autori concludono che la tecnica ibrida minimizza significativamente la frammentazione dello spettro e massimizza l'utilizzo delle risorse rispetto ai metodi tradizionali. Posizionano questo lavoro come un passo verso la risoluzione di problemi RSA complessi e su larga scala dove i metodi esatti (come CPLEX) diventano computazionalmente proibitivi, offrendo un'alternativa euristica di alta qualità.

Lavoro Futuro
Gli autori delineano modestamente direzioni future, tra cui:

• Estendere l'algoritmo ad scenari di assegnazione dinamica dello spettro per gestire le richieste di traffico in tempo reale.
• Investigare l'ottimizzazione multi-obiettivo per affrontare simultaneamente il consumo di energia e la latenza.
• Esplorare l'integrazione di euristiche basate sul machine learning per migliorare l'allocazione predittiva dello spettro.