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

Resumo Técnico: Otimização de Lobo Cinzento Discreta Híbrida para Atribuição de Espectro em Redes Ópticas Elásticas

Definição do Problema
O artigo aborda o subproblema de Atribuição de Espectro (SA - Spectrum Assignment) dentro do desafio mais amplo de Roteamento e Atribuição de Espectro (RSA) em Redes Ópticas Elásticas (EONs). À medida que as aplicações de alta largura de banda impulsionam o crescimento do tráfego, as redes tradicionais de Multiplexação por Divisão de Comprimento de Onda (WDM) de grade fixa estão se tornando insuficientes. As EONs oferecem uma solução através da alocação de espectro flexível usando granularidade menor. No entanto, o problema de RSA é NP-difícil, particularmente em redes de grande escala, devido à necessidade de satisfazer três restrições críticas simultaneamente:

1. Continuidade de Espectro: Os índices das fatias de frequência (frequency slots - FSs) devem permanecer idênticos em todos os links físicos de um caminho.
2. Contiguidade de Espectro: A largura de banda alocada deve formar um bloco contínuo de fatias de frequência adjacentes, sem fragmentação.
3. Não sobreposição: Uma fatia de frequência em um link pode servir apenas uma solicitação de conexão por vez.

O objetivo específico deste trabalho é minimizar a utilização total de fatias de frequência (FSs) em redes ópticas de grande escala para aumentar a capacidade e a eficiência da rede.

Metodologia
Os autores propõem um Otimizador de Lobo Cinzento Discreto Híbrido (GWO) integrado com Simulated Annealing (SA), denominado SA-GWO.

• Otimizador de Lobo Cinzento (GWO): O algoritmo base mimetiza a hierarquia social e o comportamento de caça dos lobos cinzentos (Alfa, Beta, Delta e Ômega). Ele é escolhido por sua forte capacidade de exploração global. No entanto, os autores observam que o GWO padrão pode sofrer de convergência prematura e aprisionamento em mínimos locais, especialmente em espaços de busca extensos.
• Adaptação Discreta: Como o problema de SA envolve a ordenação discreta de solicitações em vez de variáveis contínuas, os autores adaptam o GWO. Eles substituem o cálculo de distância baseado em vetores padrão pela distância de Hamming para medir a dissimilaridade entre vetores de soluções (permutações de solicitações).
• Hibridização com Simulated Annealing (SA): Para abordar as limitações do GWO padrão, o SA é incorporado ao mecanismo de atualização de posição do lobo.
  • Em vez de atualizar deterministicamente as posições dos lobos baseando-se apenas nos líderes Alfa, Beta e Delta, o algoritmo gera uma solução vizinha para cada lobo usando uma mutação de troca (swap mutation) proporcional à distância de Hamming.
  • A aceitação desta nova solução segue o critério de Metropolis. Se a nova solução for melhor, ela é aceita. Se for pior, é aceita com uma probabilidade $P = e^{-\Delta E/T}$, onde $\Delta E$ é a diferença de aptidão (fitness) e $T$ é a temperatura atual.
  • Esta aceitação probabilística permite que o algoritmo escape de ótimos locais, equilibrando exploração e explotação de forma mais eficaz do que o GWO sozinho.
• Avaliação: As soluções são avaliadas com base no número máximo de fatias de frequência utilizadas, aderindo às restrições do modelo de Atribuição de Espectro de Distância (DSA), incluindo requisitos de banda de guarda (guardband).

Principais Contribuições

1. Inovação Algorítmica: O desenvolvimento de uma meta-heurística híbrida (SA-Gogo) especificamente adaptada para o problema discreto de Atribuição de Espectro em EONs.
2. Integração de Mecanismos: A integração inovadora do Simulated Annealing na fase de atualização de posição do GWO para refinar o processo de busca e evitar a convergência prematura.
3. Formulação Discreta: A adaptação do GWO para otimização combinatória discreta usando distância de Hamming e mutações de troca, em vez de aritmética de vetores contínuos.

Resultos Experimentais
O algoritmo SA-GWO proposto foi avaliado utilizando:

• Topologias: Diversos grafos sintéticos gerados usando bibliotecas Python (NetworkX e Matplotlib), incluindo grafos aleatórios e grafos completos com contagens de nós variando de 14 a 25.
• Comparações: Os resultados foram comparados com um algoritmo de Duas Fases padrão, o algoritmo GWO padrão e soluções ótimas geradas pelo solver CPLEX 12.9.0 (para instâncias menores).

Descobertas:

• Grafos Pequenos a Médios (14–19 nós): O algoritmo SA-GWO superou significativamente o algoritmo de referência de Duas Fases. Em muitos casos, produziu resultados muito próximos das soluções ótimas encontradas pelo CPLEX.
• Grafos Grandes (20–25 nós): Embora o SA-GWO não tenha alcançado os resultados ótimos do CPLEX (o que é esperado para problemas NP-difíceis nesta escala), demonstrou superioridade significativa sobre o algoritmo GWO padrão, reduzindo o número máximo de fatias de frequência utilizadas.
• Escalabilidade: A abordagem híbrida provou ser robusta na gestão do aumento da complexidade conforme o tamanho dos grafos crescia, enquanto o GWO padrão mostrou uma lacuna de desempenho maior em comparação com a versão híbrida.

Significância e Alegações
O artigo afirma que a abordagem SA-GWO proposta aumenta efetivamente a capacidade da rede ao otimizar a alocação de fatias de frequência. A principal significância reside na capacidade do algoritmo de alcançar um melhor equilíbrio entre exploração global e explotação local. Ao incorporar o Simulated Annealing, o método mitiga o risco de ficar preso em mínimos locais, um problema comum em problemas de RSA de grande escala.

Os autores concluem que a técnica híbrida minimiza significativamente a fragmentação do espectro e maximiza a utilização de recursos em comparação com abordagens tradicionais. Eles posicionam este trabalho como um passo para resolver problemas de RSA complexos e de grande escala, onde métodos exatos (como o CPLEX) tornam-se computacionalmente proibitivos, oferecendo uma alternativa heurística de alta qualidade.

Trabalhos Futuros
Os autores delineiam modestamente direções futuras, incluindo:

• Extensão do algoritmo para cenários de atribuição de espectro dinâmica para lidar com demandas de tráfego em tempo real.
• Investigação de otimização multiobjetivo para abordar simultaneamente o consumo de energia e a latência.
• Exploração da integração de heurísticas baseadas em aprendizado de máquina para melhorar a alocação preditiva de espectro.