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

Technical Summary: Hybrid Discrete Grey Wolf Optimization for Spectrum Assignment in Elastic Optical Networks

Problem Statement
The paper addresses the Spectrum Assignment (SA) sub-problem within the broader Routing and Spectrum Assignment (RSA) challenge in Elastic Optical Networks (EONs). As high-bandwidth applications drive traffic growth, traditional fixed-grid Wavelength Division Multiplexing (WDM) networks are becoming insufficient. EONs offer a solution through flexible spectrum allocation using smaller granularity. However, the RSA problem is NP-hard, particularly in large-scale networks, due to the need to satisfy three critical constraints simultaneously:

1. Spectrum Continuity: Frequency slot indices must remain identical across all physical links in a path.
2. Spectrum Contiguity: Allocated bandwidth must form a continuous block of adjacent frequency slots without fragmentation.
3. Non-overlapping: A frequency slot on a link can serve only one connection request at a time.

The specific objective of this work is to minimize the total utilization of frequency slots (FSs) in large optical networks to enhance network capacity and efficiency.

Methodology
The authors propose a Hybrid Discrete Grey Wolf Optimizer (GWO) integrated with Simulated Annealing (SA), termed SA-GWO.

• Grey Wolf Optimizer (GWO): The base algorithm mimics the social hierarchy and hunting behavior of grey wolves (Alpha, Beta, Delta, and Omega). It is chosen for its strong global exploration capabilities. However, the authors note that standard GWO can suffer from premature convergence and entrapment in local minima, especially in large search spaces.
• Discrete Adaptation: Since the SA problem involves discrete ordering of requests rather than continuous variables, the authors adapt GWO. They replace the standard vector-based distance calculations with Hamming distance to measure the dissimilarity between solution vectors (permutations of requests).
• Hybridization with Simulated Annealing (SA): To address the limitations of standard GWO, SA is embedded into the position update mechanism.
  • Instead of deterministically updating wolf positions based solely on the Alpha, Beta, and Delta leaders, the algorithm generates a neighboring solution for each wolf using a swap mutation proportional to the Hamming distance.
  • The acceptance of this new solution follows the Metropolis criterion. If the new solution is better, it is accepted. If it is worse, it is accepted with a probability $P = e^{-\Delta E/T}$, where $\Delta E$ is the fitness difference and $T$ is the current temperature.
  • This probabilistic acceptance allows the algorithm to escape local optima, balancing exploration and exploitation more effectively than GWO alone.
• Evaluation: Solutions are evaluated based on the maximum number of frequency slots utilized, adhering to the Distance Spectrum Assignment (DSA) model constraints, including guardband requirements.

Key Contributions

1. Algorithmic Innovation: The development of a hybrid meta-heuristic (SA-GWO) specifically tailored for the discrete Spectrum Assignment problem in EONs.
2. Mechanism Integration: The novel integration of Simulated Annealing into the GWO position update phase to refine the search process and prevent premature convergence.
3. Discrete Formulation: The adaptation of GWO for discrete combinatorial optimization using Hamming distance and swap mutations, rather than continuous vector arithmetic.

Experimental Results
The proposed SA-GWO algorithm was evaluated using:

• Topologies: Various synthetic graphs generated using Python libraries (NetworkX and Matplotlib), including random graphs and complete graphs with node counts ranging from 14 to 25.
• Comparisons: The results were benchmarked against a standard Two-Phase algorithm, the standard GWO algorithm, and optimal solutions generated by the CPLEX 12.9.0 solver (for smaller instances).

Findings:

• Small to Medium Graphs (14–19 nodes): The SA-GWO algorithm significantly outperformed the Two-Phase reference algorithm. In many cases, it produced results very close to the optimal solutions found by CPLEX.
• Large Graphs (20–25 nodes): While the SA-GWO did not reach the optimal CPLEX results (which is expected for NP-hard problems at this scale), it demonstrated significant superiority over the standard GWO algorithm, reducing the maximum number of frequency slots used.
• Scalability: The hybrid approach proved robust in managing increased complexity as graph sizes grew, whereas standard GWO showed a larger performance gap compared to the hybrid version.

Significance and Claims
The paper claims that the proposed SA-GWO approach effectively enhances network capacity by optimizing frequency slot allocation. The primary significance lies in the algorithm's ability to achieve a better balance between global exploration and local exploitation. By incorporating Simulated Annealing, the method mitigates the risk of getting trapped in local minima, a common issue in large-scale RSA problems.

The authors conclude that the hybrid technique significantly minimizes spectrum fragmentation and maximizes resource utilization compared to traditional approaches. They position this work as a step toward solving complex, large-scale RSA problems where exact methods (like CPLEX) become computationally prohibitive, offering a high-quality heuristic alternative.

Future Work
The authors modestly outline future directions, including:

• Extending the algorithm to dynamic spectrum assignment scenarios to handle real-time traffic demands.
• Investigating multi-objective optimization to simultaneously address power consumption and latency.
• Exploring the integration of machine learning-based heuristics to improve predictive spectrum allocation.