弹性光网络中的路由和频谱分配问题

A Study of the Routing and Spectrum Allocation in Elastic Optical Networks

摘要: 随着网络流量需求激增，弹性光网络因其高效的频谱利用率成为热点，路由和频谱分配问题是其核心研究问题。目前，整数线性规划模型是求解路由和频谱分配问题的重要方法，但现有的研究多集中于一般网络拓扑，直接应用于特殊拓扑如环网络会导致模型复杂、求解效率低下。本文旨在针对环网络这一常见拓扑结构，根据环网络的自身特性，建立线性整数规划模型以精确求解路由和频谱分配问题。在此基础上，设计了一种结合问题具体情况的分支切割算法，包括初始化上下界、设计分支策略以及寻找有效割平面等方法。数值实验表明，我们所建模型在问题求解规模和求解时间上均表现出显著优势，进一步应用分支切割算法后，求解规模得到进一步扩展。本文提出的简化线性整数规模模型在精确求解路由和频谱分配问题上具有优越性，所设计的分支切割算法能有效提升大规模问题的求解效率与求解规模，为环形网络中的频谱资源优化提供了有效的理论工具与算法支持。

Abstract: With the explosive growth of network traffic demand, elastic optical networks have emerged as a hot research topic due to their high spectrum efficiency. The routing and spectrum allocation problem stands as a core research challenge in this domain. Currently, the integer linear programming model serves as an important method for solving the routing and spectrum allocation problem. However, existing studies mostly focus on general network topologies, and applying these models directly to special topologies such as ring networks often leads to high model complexity and low solving efficiency. This paper aims to address the routing and spectrum allocation problem for the common ring network topology by establishing a linear integer programming model that precisely solves the problem based on the inherent characteristics of ring networks. Furthermore, a branch-and-cut algorithm tailored to the specific problem is designed, incorporating methods such as initializing upper and lower bounds, designing branching strategies, and identifying effective cutting planes. Numerical experiments show that the proposed model exhibits significant advantages in terms of problem-solving scale and computation time. After further applying the branch-and-cut algorithm, the solving scale is further extended. The simplified linear integer programming model presented in this paper demonstrates superiority in precisely solving the routing and spectrum allocation problem, and the designed branch-and-cut algorithm effectively enhances the solving efficiency and scale for large-scale problems, providing a valuable theoretical tool and algorithmic support for spectrum resource optimization in ring networks.