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

Resumen Técnico: Optimización de Lobo Gris Discreto Híbrido para la Asignación de Espectro en Redes Ópticas Elásticas

Declaración del Problema
El artículo aborda el subproblema de la Asignación de Espectro (SA) dentro del desafío más amplio de Enrutamiento y Asignación de Espectro (RSA) en las Redes Ópticas Elásticas (EON). A medida que las aplicaciones de gran ancho de banda impulsan el crecimiento del tráfico, las redes tradicionales de Multiplexación por División de Longitud de Onda (WDM) de rejilla fija se están volviendo insuficientes. Las EON ofrecen una solución mediante la asignación de espectro flexible utilizando una granularidad más pequeña. Sin embargo, el problema RSA es NP-duro, particularmente en redes de gran escala, debido a la necesidad de satisfacer tres restricciones críticas simultáneamente:

1. Continuidad de Espectro: Los índices de los slots de frecuencia deben permanecer idénticos en todos los enlaces físicos de una ruta.
2. Contigüidad de Espectro: El ancho de banda asignado debe formar un bloque continuo de slots de frecuencia adyacentes sin fragmentación.
3. No solapamiento: Un slot de frecuencia en un enlace puede servir solo una solicitud de conexión a la vez.

El objetivo específico de este trabajo es minimizar la utilización total de los slots de frecuencia (FSs) en redes ópticas grandes para mejorar la capacidad y la eficiencia de la red.

Metodología
Los autores proponen un Optimizador de Lobo Gris (GWO) Discreto Híbrido integrado con Recocido Simulado (SA), denominado SA-GWO.

• Optimizador de Lobo Gris (GWO): El algoritmo base imita la jerarquía social y el comportamiento de caza de los lobos grises (Alfa, Beta, Delta y Omega). Se elige por su fuerte capacidad de exploración global. Sin embargo, los autores señalan que el GWO estándar puede sufrir de convergencia prematura y atrapamiento en mínimos locales, especialmente en espacios de búsqueda grandes.
• Adaptación Discreta: Dado que el problema de SA implica un ordenamiento discreto de las solicitudes en lugar de variables continuas, los autores adaptan el GWO. Reemplazan el cálculo estándar de distancia basado en vectores con la distancia de Hamming para medir la disimilitud entre los vectores de soluciones (permutaciones de solicitudes).
• Hibridación con Recocido Simulado (SA): Para abordar las limitaciones del GWO estándar, se integra SA en el mecanismo de actualización de posición.
  • En lugar de actualizar determinísticamente las posiciones de los lobos basándose únicamente en los líderes Alfa, Beta y Delta, el algoritmo genera una solución vecina para cada lobo utilizando una mutación de intercambio (swap mutation) proporcional a la distancia de Hamming.
  • La aceptación de esta nueva solución sigue el criterio de Metropolis. Si la nueva solución es mejor, se acepta. Si es peor, se acepta con una probabilidad $P = e^{-\Delta E/T}$, donde $\Delta E$ es la diferencia de aptitud (fitness) y $T$ es la temperatura actual.
  • Esta aceptación probabilística permite al algoritmo escapar de los óptimos locales, equilibrando la exploración y la explotación de manera más efectiva que el Golo GWO por sí solo.
• Evaluación: Las soluciones se evalúan basándose en el número máximo de slots de frecuencia utilizados, adhiriéndose a las restricciones del modelo de Asignación de Espectro de Distancia (DSA), incluyendo los requisitos de banda de guarda.

Contribuciones Clave

1. Innovación Algorítmica: El desarrollo de una metaheurística híbrida (SA-GWO) diseñada específicamente para el problema discreto de Asignación de Espectro en EON.
2. Integración de Mecanismos: La novedosa integración de Recocido Simulado en la fase de actualización de posición de GWO para refinar el proceso de búsqueda y prevenir la convergencia prematura.
3. Formulación Discreta: La adaptación de GWO para la optimización combinatoria discreta utilizando la distancia de Hamming y mutaciones de intercambio, en lugar de la aritmética de vectores continuos.

Resultados Experimentales
El algoritmo SA-G easily fue evaluado utilizando:

• Topologías: Diversos grafos sintéticos generados mediante librerías de Python (NetworkX y Matplotlib), incluyendo grafos aleatorios y grafos completos con conteos de nodos que oscilan entre 14 y 25.
• Comparaciones: Los resultados se compararon con un algoritmo de dos fases estándar, el algoritmo GWO estándar y soluciones óptimas generadas por el solver CPLEX 12.9.0 (para instancias más pequeñas).

Hallazgos:

• Grafos Pequeños a Medianos (14–19 nodos): El algoritmo SA-GWO superó significativamente al algoritmo de referencia de dos fases. En muchos casos, produjo resultados muy cercanos a las soluciones óptimas encontradas por CPLEX.
• Grafos Grandes (20–25 nodos): Aunque el SA-GWO no alcanzó los resultados óptimos de CPLEX (lo cual es esperado para problemas NP-duros a esta escala), demostró una superioridad significativa sobre el algoritmo GWO estándar, reduciendo el número máximo de slots de frecuencia utilizados.
• Escalabilidad: El enfoque híbrido demostró ser robusto en la gestión de la complejidad creciente a medida que crecían los tamaños de los grafos, mientras que el GWO estándar mostró una brecha de rendimiento mayor en comparación con la versión híbrida.

Significancia y Reivindicaciones
El artículo afirma que el enfoque propuesto SA-GWO mejora efectivamente la capacidad de la red mediante la optimización de la asignación de slots de frecuencia. La principal significancia radica en la capacidad del algoritmo para lograr un mejor equilibrio entre la exploración global y la explotación local. Al incorporar el Recocido Simulado, el método mitiga el riesgo de quedar atrapado en mínimos locales, un problema común en los problemas de RSA a gran escala.

Los autores concluyen que la técnica híbrida minimiza significativamente la fragmentación del espectro y maximiza la utilización de los recursos en comparación con los enfoques tradicionales. Posicionan este trabajo como un paso hacia la resolución de problemas de RSA complejos y a gran escala donde los métodos exactos (como CPLEX) se vuelven computacionalmente prohibitivos, ofreciendo una alternativa heurística de alta calidad.

Trabajo Futuro
Los autores delinean modestamente direcciones futuras, que incluyen:

• Extender el algoritmo a escenarios de asignación de espectro dinámica para manejar demandas de tráfico en tiempo real.
• Investigar la optimización multiobjetivo para abordar simultáneamente el consumo de energía y la latencia.
• Explorar la integración de heurísticas basadas en aprendizaje automático (machine learning) para mejorar la asignación predictiva del espectro.