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

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.

1. 引言

随着互联网的大规模普及以及各种网络需求的快速发展，人们对于基础通信设备也有了更高的要求。传统的波分复用光网络(Wavelength Division Multiplexing)由于它以固定大小波长通道的形式去承载业务需求，且每两个波长通道之间有固定的保护载波间隔，就会在一些场景下造成频谱资源的浪费。例如，若单个业务需求小于固定间隔，会导致此业务所占波长通道的大多数频谱资源未被利用；若单个业务需求大于固定间隔，其每个波长之间的保护载波会避免相邻波长信号干扰，但同时也会造成频谱资源的浪费。因此，使用了正交频分复用技术的弹性光网络(Elastic Optical Networks)应运而生。它可以以更为精细的粒度将频谱槽灵活地分配给业务需求，节省了相当大的频谱资源，有助于后续更大规模流量场景的研究。在弹性光网络中，路由和频谱的分配问题(Routing and Spectrum Allocation)是一个重要的研究课题。RSA问题是指在网络中寻找可用的路径并分配合适的频谱资源，以便在同一时间段内有更多的业务需求得到满足，降低业务阻塞率。在进行频谱分配的过程中，有三条需要满足的约束条件，分别是频谱连续性、频谱一致性和频谱不重叠性[1]。频谱的连续性是指同一个需求所分配的频谱槽索引是连续的；频谱的一致性是指同一需求在路由中的不同链路上所分配的频谱槽索引值相同；频谱的不重叠性是指对于链路中的每一个频谱槽，最多只能有一个需求占用该频谱槽。截至目前，求解RSA问题的方法有很多，包括建立线性整数规划模型(Integer Linear Programming) [2]、近似算法[3]、智能算法[4]等。以往的基于线性整数规划的研究都是着眼一般网络[5]，很少涉及特殊网络拓扑。目前基于环网络的RSA问题主要集中于近似算法，若直接将一般网络中的ILP模型照搬到环网络中，则会导致变量和约束条件过多，求解时间过长的现象。因此我们考虑建设简化的环网络中的ILP模型并根据问题背景进行优化[6]。

2. 文献综述

2002年，Dirceu等人[7]研究了在WDM环网络中路由和频谱分配问题，针对该NP难问题，提出了整数线性规划精确解法及多种低复杂度启发式算法。2011年，Wang等人[2]着手研究了弹性光网络中的静态路由和频谱分配问题，证明该问题是NP-hard问题，将目标函数设定为最小化网络光纤上频谱槽的最大索引值，提出相应的整数线性规划模型，并提出基于负载均衡的RSA算法和基于最短路径与最大频谱复用的算法。2012年，Velasco等人[8]引进信道的新概念，提出一种新型ILP模型公式。通过预先设定一定需求量的信道集合，将问题的复杂度大大降低。2014年，Velasco等人[9]提出新型ILP模型并使用分支定价算法求解该模型。通过改善松弛下界和使用合适的割平面，在更大规模的网络拓扑中呈现更好的表现，使得那些使用商业求解器难以求解的问题得以解决。2019年，张雷等人[3]研究了链和环结构网络中的路由与频谱分配问题，并得出结论，在环网络中，当节点数$N\le 4$ 时，频谱分配问题在多项式时间内可解，当$N\ge 5$ 时，该问题是NP难问题。2023年，Junjia Zhang等人[10]提出了一种一般网络下改进的整数线性规划模型，变量设置更合理，约束条件更简约，并通过数值实验验证该模型相比之前ILP模型的优越性。

3. 问题研究

这一部分我们将介绍两个经典的ILP模型，找到合适的寻找上下界方法，并简单介绍分支切割算法框架，根据问题的自身特性补充算法框架细节。

3.1. 经典ILP模型

2011年Wang等人[2]在首次全面研究了RSA问题并建立了相对应的ILP模型，该模型为RSA问题的研究奠定了坚实的基础。目标函数为：

$\min MS$

约束条件如下所示：

$MS\ge w\cdot V_{i,o,s,d}^w,\forall w,i,o,s,d$ (1)

${\displaystyle \sum _{w,o=d,i\in I_o}{V}_{i,o,s,d}^w}=T_{s,d},\forall s,d$ (2)

${\displaystyle \sum _{w,i=s,o\in O_i}{V}_{i,o,s,d}^w}=T_{s,d},\forall s,d$ (3)

${\displaystyle \sum _{w,s=d}{V}_{i,o,s,d}^w}=0,\forall i,o$ (4)

${\displaystyle \sum _{s,d}{V}_{i,o,s,d}^w}\le 1,\forall w,i,o$ (5)

${\displaystyle \sum _{w,o\ne d,i\in I_o}{V}_{i,o,s,d}^w}={\displaystyle \sum _{w,o\ne s,p\in O_o}{V}_{o,p,s,d}^w},\forall s,d,o$ (6)

$\left(V_{i,o,s,d}^w-V_{i,o,s,d}^{w+1}-1\right)\cdot \left(-B\right)\ge {\displaystyle \sum _{\overline{w}\in \left[w+2,\varphi \right]}{V}_{i,o,s,d}^{\overline{w}}},\forall w,i,o,s,d$ (7)

$\left(V_{i,o,s,d}^w-1\right)\cdot B+T_{s,d}\le {\displaystyle \sum _{\overline{w}\in \left[1,\varphi \right]}{V}_{i,o,s,d}^{\overline{w}}},\forall w,i,o,s,d$ (8)

其中变量$\varphi$ 表示一条链路中频谱槽的总数；$I_n$ 和$O_n$ 分别表示通过传入链路与节点$n$ 相连的节点集合和通过传出链路与节点$n$ 相连的节点集合；${\Xi }_{n,m}$ 表示业务需求矩阵；矩阵元素$T_{n,m}$ 表示需求从节点$n$ 到节点$m$ 所需频谱槽的数量；$V_{i,o,s,d}^w$ 表示若有一个需求从节点$s$ 到节点$d$ ，中间路由包含$\left(i,o\right)$ 这条链路并且该需求占用了索引为$w$ 的频谱槽，则为1，否则为0；变量$MS$ 为网络中所有链路上所分配的频谱槽的最大索引值。

约束(1)是为了得到MS的下界；约束(2)~(4)是流量需求约束，确保网络中流量守恒；约束(5)表示链路上的频谱槽最多被一个需求占用，即频谱的不重叠性；约束(6)保证了频谱的一致性；约束(7)~(8)则是保证了频谱的连续性。

3.2. 改进ILP模型

2023年，Junjia Zhang等人[10]提出了一种一般网络下改进的整数线性规划模型，变量设置更合理，约束条件更简约。目标函数为：

$\min MS$

约束条件如下所示：

$MS\ge c\cdot x_{i,j,c,p},\forall \langle i,j\rangle \in E,c\in C,p\in P$ (9)

${\displaystyle \sum _{p\in P}{x}_{i,j,c,p}\le 1,\forall \langle i,j\rangle \in E,c\in C}$ (10)

$1-x_{i,j,c,p}+x_{i,j,c+1,p}\ge x_{i,j,c^{\prime },p},\forall \langle i,j\rangle \in E,c\in C-\left\{\left|C\right|-1,\left|C\right|\right\},p\in P,c^{\prime }\in \left[c+2,\left|C\right|\right]$ (11)

$T_p\cdot x_{i,j,p}={\displaystyle \sum _{c\in C}{x}_{i,j,c,p}},\forall \langle i,j\rangle \in E,p\in P$ (12)

${\displaystyle \sum _{j:\langle s_p,j\rangle \in E}{x}_{s_p,j,p}}-{\displaystyle \sum _{j:\langle j,s_p\rangle \in E}{x}_{j,s_p,p}}=1,\forall p\in P$ (13)

${\displaystyle \sum _{j:\langle d_p,j\rangle \in E}{x}_{d_p,j,p}}-{\displaystyle \sum _{j:\langle j,d_p\rangle \in E}{x}_{j,d_p,p}}=-1,\forall p\in P$ (14)

${\displaystyle \sum _{j:\langle i,j\rangle \in E}{x}_{i,j,p}}-{\displaystyle \sum _{j:\langle j,i\rangle \in E}{x}_{j,i,p}}=0,\forall i\in V-\left\{s_p,d_p\right\},p\in P$ (15)

${\phi }_{c,p}\ge x_{i,j,c,p},\forall \langle i,j\rangle \in E,c\in C,p\in P$ (16)

${\displaystyle \sum _{c\in C}{\phi }_{c,p}=T_p},\forall p\in P$ (17)

其中，变量$x_{i,j,c,p}$ 表示若给需求$p$ 分配的路由中包含$\langle i,j\rangle$ 链路并且使用了索引为$c$ 的频谱槽则为1，否则为0；$x_{i,j,p}$ 表示若给需求$p$ 分配的路由中包含$\langle i,j\rangle$ 链路则为1，否则为0；${\phi }_{c,p}$ 表示若第$p$ 个需求使用了频谱槽索引为$c$ 的子载波则为1，否则为0；$C=\left\{1,2,\cdots ,\left|C\right|\right\}$ ，是环网络中每条链路上的频谱槽集合；$P=\left\{1,2,\cdots ,\left|P\right|\right\}$ ，是环网络中的业务需求集合；$T_p,p\in P$ 表示第$p$ 个业务需求$\left(s_p,d_p\right)$ 在光路中所需要的频谱槽的数量。$X_{i,j}$ 表示若链路$\langle i,j\rangle$ 被任意需求使用则为1，否则为0。

约束(9)确定了所有光纤链路中所使用频谱槽的最大索引值；约束(10)确保了子载波的不可重叠性限制；约束(11)保证了子载波的连续性；约束(12)进一步强化了子载波在路径上的连续性要求；公式(13)至(15)共同施加了流守恒定律，确保各节点对之间路径上的流量合理分配；最后，公式(16)和(17)则用于分配子载波资源，以满足每对节点之间的通信需求。

3.3. 环网络中的ILP模型

目前关于ILP模型在RSA问题上的研究主要集中在一般网络中[11] [12]，而在特殊拓扑网络中，如环网络的路由和频谱分配问题则主要集中于近似算法的研究。若直接将一般网络中的ILP模型照搬到环网络中会导致变量和约束条件过多，求解效率过低的现象。因此我们尝试根据环网络本身的特性[13]，建立简约的ILP模型求解RSA问题。目标函数为：

$\min MS$

约束条件如下所示：

$d_{k1}+d_{k2}=1,\forall k\in K$ (18)

$o_{k{k}^{\prime }}+o_{k^{\prime }k}=1,\forall k,k^{\prime }\in K,k\ne k^{\prime }$ (19)

$f_k+r_k\le f_{k^{\prime }}+M\cdot \left(3-d_{ki}-d_{k^{\prime }i}-o_{k{k}^{\prime }}\right),\forall k,k^{\prime }\in K,k\ne k^{\prime },i\in \left(1,2\right)$ (20)

$f_{k^{\prime }}+r_{k^{\prime }}\le f_k+M\cdot \left(2-d_{ki}-d_{k^{\prime }i}+o_{k{k}^{\prime }}\right),\forall k,k^{\prime }\in K,k\ne k^{\prime },i\in \left(1,2\right)$ (21)

$MS\ge f_k+r_k-1,\forall k\in K$ (22)

$f_k\ge 1,\forall k\in K$ (23)

其中$f_k$ 表示第$k$ 个业务需求所分配的第一个频谱槽的索引值；$d_{ki}$ 表示若第$k$ 个需求的方向为$i$ 时则为1，否则为0，其中$i$ 表示业务需求所分配的方向，$i=1$ 为顺时针，$i=2$ 为逆时针；$o_{k{k}^{\prime }}$ 表示若$f_k<f_{k^{\prime }}$ 则为1，否则为0；$r_k$ 是第$k$ 个需求所需的频谱槽数。

约束(18)表示每个业务需求在环网络中只能选择一个方向，即要么为顺时针路径，要么为逆时针路径；约束(19)~(21)表示对于任意两个不同的需求，如果被分配到同一条边上，则两个需求所分配的频谱槽的位置不能出现交叉，即满足频谱的不重叠性；约束(22)是为了限制MS的下界；约束(23)表示每个需求所分配的频谱槽索引必须从1开始，即不存在需求阻塞的情况。

我们建立的ILP模型在环网络中具有显著优势。在变量设置上，由于任意节点对之间仅存在两条候选路径——顺时针与逆时针方向，这可以通过引入方向变量$d_{ki}$ 表示，即约束(18)。同时这也彻底摒弃了原先模型中需要流守恒约束(约束(13)~(15))来确定路由的繁琐方式。进一步，改进模型通过引入频谱起始位置$f$ 、排序变量$o_{k{k}^{\prime }}$ 及其配套约束(约束(19)~(21))，巧妙自然地满足了频谱的连续性和一致性，这让我们只需额外描述频谱不重叠性这一约束即可，大大降低了约束条件的复杂度。

3.4. ILP模型理论复杂度分析

为了从理论上分析上述三组模型的复杂度，我们给出每个ILP模型的变量和约束条件数量级。见表1，该表为不同ILP模型的变量和约束条件的数量级，其中$K$ 为需求集，$E$ 为环网络边集，$V$ 为环网络点集，$S$ 为每条链路中频谱槽的集合。

Table 1. Number of variables and constraints per model

表1. 每组模型的变量和约束数量级

模型	变量	约束条件
经典ILP模型	$O\left({\left|K\right|}^2+\left|K\right|\cdot \left|E\right|\right)$	$O\left(\left|K\right|\cdot \left|V\right|+{\left|K\right|}^2\cdot \left|E\right|\right)$
改进ILP模型	$O\left(\left|E\right|\cdot \left|S\right|\cdot \left|K\right|\right)$	$O\left(\left|E\right|\cdot {\left|S\right|}^2\cdot \left|K\right|\right)$
环网络中的ILP模型	$O\left({\left|K\right|}^2+2\left|K\right|\right)$	$O\left(4{\left|K\right|}^2\right)$

由于环网络边数$\left|E\right|$ 远小于需求数$\left|K\right|$ 和每条链路中频谱槽总数$\left|S\right|$ ，因此可以忽略不计。

3.5. 分支切割算法

由于环网络中路由和频谱分配问题本身的复杂性，直接使用Gurobi求解器求解ILP模型的效率比较低，运行时间比较长，求解问题的规模也较小。因此我们考虑使用分支切割算法[14] [15]，设计有针对性的策略对该ILP模型进行优化。

分支切割算法是分支定界和切割平面法的结合。其基本框架如下所示：

分支切割算法步骤：

1) 初始化上下界；

2) 将ILP模型线性松弛，求得松弛解$u^{\ast }$ ；

3) 判断$u^{\ast }$ 是否为整数解，若是则更新上界，回溯；否则进入下一步；

4) 添加有效不等式，更新模型约束并重新求解；

5) 分支，每个节点计算下界。如果下界超过当前最优上界，则剪枝。

在分支定界框架中，上界(UB)和下界(LB)的确定对加速求解过程至关重要。一个好的初始上下界可以加快问题的求解速率，避免不必要的分支的求解。下界的获取基于负载均衡算法。该算法松弛了频谱的一致性约束，根据流守恒建立ILP模型，得到网络负载最小的路由选择和频谱分配，其最优解为目标函数提供了一个理论下界。上界的获取基于启发式算法。该算法基于负载均衡与首次适配策略，能够在多项式时间内生成可行解，为分支定界过程提供初始上界，并可在分支树中动态更新。具体算法步骤如下所示。

负载均衡生成下界算法：

目标函数：

$\min L$

约束条件：

$x_{ij}^k=\{\begin{array}{l}1,\left(i,j\right)\in k\hfill \\ 0,\text{ else}\hfill \end{array}$ (24)

${\displaystyle \sum _i{x}_{ij}^k}={\displaystyle \sum _i{x}_{ji}^k,\forall j\in V,k\in K}$ (25)

${\displaystyle \sum _k{x}_{ij}^k\cdot r_k}\le L,\forall \left(i,j\right)\in E,k\in K$ (26)

${\displaystyle \sum _j{x}_{sj}^k}=1,{\displaystyle \sum _j{x}_{jt}^k}=-1,\forall k\in K$ (27)

该ILP模型满足了RSA问题中的流量守恒、连续性约束和不重叠性约束，缺少一致性约束的满足，因此可以得到L的最小值即为理论下界。

另一方面，理论上讲每一个需求可以走任意一条路由，但如果某些需求把资源集中在某几条“热门”链路上，那么就可能导致网络链路中最大频谱槽数偏大，不满足最小化最大频谱槽数的目标函数。因此我们希望每一条链路上所承载的需求数尽可能接近，避免网络资源的局部过度使用，使得整个网络的链路利用率最高[16] [17]，这样我们得到的上界才能尽可能的小。

基于负载均衡的启发式算法：

1) 需求排序，按$r_k$ 大小倒序排序；

2) 初始化每条链路的频谱占用状态为空闲；

3) 对于每个请求$\left(s_d,t_d,r_k\right)$ 。

计算两条候选路径，选择当前负载较轻的路径(若相同则选择最短路)。

扫描可用频谱资源，使用First-Fit策略寻找可容纳$r_k$ 个连续频谱槽的索引最小的块。

在该路径上分配频谱槽，更新状态。

4) 输出上界UB

该上界同时可作为大M值进行优化。

由于求负载均衡上界的ILP模型比较简单，且求下界的负载均衡算法是一个简单的启发式算法，相比较而言，分支切割算法是一个迭代搜索过程，涉及大量分支、剪枝、割平面添加等操作。因此，在实际程序运行过程中，前期通过负载均衡求得上下界的运行时间相比分支切割算法的求解时间来讲可以忽略不计。

分支策略的优劣直接影响分支切割算法的搜索效率和收敛速度。基于环网络RSA问题的特性，我们设计并实现了一种基于问题结构的分支策略。如当多个方向变量的分数值接近程度相当时，算法优先考虑频谱需求较大的业务进行分支；在RSA问题中，方向的选择决定了业务需求路由的选择，进而决定了不同业务需求是否有链路的重合，从而进行频谱不重叠性的判断。

由于ILP模型在描述频谱不重叠性时使用了大M法，导致在使用分支切割算法进行求解时频谱的不重叠性刻画不够紧致[13]，因此我们从此入手设计频谱不重叠性的有效不等式，当算法检测到两个业务很可能在同一条边上竞争频谱资源时，添加一个不含大M项的紧约束，若$d_{ki},d_{k^{\prime }i}\in \left[a,1\right],o_{k{k}^{\prime }}\in \left[b,1\right]$ ，则：

$f_k+r_k\le f_{k^{\prime }},\forall k,k^{\prime }\in K,k\ne k^{\prime }$ (28)

4. 数值实验

4.1. ILP模型改进的对比实验

在本节中，我们通过仿真实验对比不同规模的环网络中模型的性能。我们将求解器的计算时间上限设定为3600秒以处理单个实例。其中每个实例根据环网络点数N和需求总数K的数量随机生成。为保证环网络中每个需求都能被合理安排频谱资源，我们将每条链路上的最大频谱槽数量设置为所有业务需要的频谱槽之和。假设环网络中每条链路的长度相同，每条边为双向链路。除此之外，我们设置了0至30个不同数量的连接请求(每步递增5个)以及10至30个顶点的环网络拓扑结构(每步递增10个)，并为每个连接请求数量随机生成20组流量数据集[18]。每个业务需求的请求量随机选取1到6的任意整数，其源节点和目的节点均从网络拓扑结构中随机选取。

见表2和表3，这两张表分别为本文ILP模型和改进后ILP模型的各项指标。其中，“done”表示在3600秒时限内完成的求解比例，该数据来自20次实验中不同连接请求数量的统计结果。“FS指数”是模型在时限内获得的平均输出值，若模型能在时限内求解，则该值即为最优解的目标函数值。“Gap”指目标函数上下界之间的差异比例，即$\frac{\text{Incumbent}-\text{BestBound}}{\text{Incumbent}}$ ，其中Incumbent表示当前最优整数解，BestBound表示当前最优下界。该数值越大表明模型求解过程越不完善。“Runtime”表示求解模型所需的计算时长。其中“FS指数”、“Gap”和“Runtime”的数值均为20次实验结果的平均值。表中“—”表示在规定时间内无法求解。

为保证所有需求均能得到满足，不发生需求阻塞，我们将M设定为所有需求所需频谱槽个数之和。

Table 2. Performance metrics of the ILP model

表2. 本文ILP模型的各项指标

点数N	需求数K	Done (%)	FS index	Gap (%)	Runtime (s)
10	5	100.00	8.5	0	0.02
10	10	100.00	11.2	0	0.12
10	15	100.00	12.4	0	0.24
10	20	100.00	15.1	0	4.28
10	25	100.00	18.9	0	161.33
10	30	95.00	25.7	3.57	3600
20	5	100.00	8.1	0	0.01
20	10	100.00	12.0	0	0.13
20	15	100.00	14.9	0	0.32
20	20	100.00	15.0	0	2.71
20	25	100.00	17.3	0	118.50
20	30	90.00	20.2	18.10	3600
30	5	100.00	7.5	0	0.01
30	10	100.00	10.7	0	0.07
30	15	100.00	15.5	0	0.80
30	20	100.00	18.3	0	97.85
30	25	95.00	19.9	6.17	3600
30	30	90.00	21.2	12.5	3600

Table 3. The performance metrics of the ILP model proposed by Zhang et al.

表3. Zhang等人ILP模型的各项指标

点数N	需求数K	Done (%)	FS index	Gap (%)	Runtime (s)
10	5	100.00	8.5	0	0.15
10	10	100.00	11.2	0	0.32
10	15	100.00	12.4	0	109.85
10	20	100.00	15.1	0	594.70
10	25	85.00	20.5	4.24	3516.10
10	30	—	—	—	—
20	5	100.00	8.1	0	0.14
20	10	100.00	12.0	0	0.34
20	15	100.00	14.9	0	74.52
20	20	90.00	17.9	0	944.73
20	25	80.00	24.3	23.26	2656.69
20	30	—	—	—	—
30	5	100.00	7.5	0	0.21
30	10	100.00	10.7	0	0.30
30	15	100.00	15.5	0	1794.32
30	20	—	—	—	—
30	25	—	—	—	—
30	30	—	—	—	—

下面三张图表以时间为纵轴(对数坐标，单位为秒)，横轴为K值，即需求数。不同颜色的折线表示不同模型的求解时间变化。其中蓝色折线表示我们新建立的环网络中的ILP模型，黄色折线即为经典ILP模型，红色折线表示最近研究中出现的ILP模型，绿色折线则表示使用张雷等人的论文思路建立的组合算法。

Figure 1. Line graph of time consumption for solving the RSA problem when N = 10

图1. N = 10时不同需求数求解RSA问题耗时折线图

Figure 2. Line graph of time consumption for solving the RSA problem when N = 20

图2. N = 20时不同需求数求解RSA问题耗时折线图

Figure 3. Line graph of time consumption for solving the RSA problem when N = 30

图3. N = 30时不同需求数求解RSA问题耗时折线图

由上面的实验可知，与其他ILP模型相比，我们建立的ILP模型具有较为明显优势：在求解能力上，本模型在10至30个节点、5至30个业务需求的环网络测试场景中，求解成功率显著优于其他模型。尤其在处理较大规模问题时，传统及改进ILP模型无法在规定时间内完成求解，而本模型仍能保持较高成功率。在解的质量上，对于均能成功求解的实例，本模型所得FS指数均值始终低于对比模型。由于FS指数直接决定网络最大频谱资源占用量，该结果证明本模型具有更高的频谱利用效率和业务承载潜力。在收敛性能上，本模型求解过程中的Gap值持续低于其他ILP模型。较小的Gap值反映了可行解与理论下界更为接近，说明模型具有更稳定、更快速的收敛特性。在计算效率上(见图1~3)，在相同问题规模下，本模型的求解耗时均短于其他对比模型，体现了其在计算速度上的优势。

4.2. 分支切割算法改进的实验效果

以环网络点数N为60，需求数K为500作为参考，分别测试在不同层节点处a，b的不同组合对问题求解时间的影响。实验实例随机选取20组，取平均值。见表4~6，这三张图分别为不同深度节点的不同组参数的模型运行时间。

Table 4. Parameter optimization experiment for root node

表4. 根节点参数调优实验

a	b	Runtime (s)
0.7	0.65	1420.51
0.75	0.7	980.25
0.7	0.7	1105.83
0.75	0.75	1290.37

Table 5. Parameter optimization experiment for middle node

表5. 中间节点参数调优实验

a	b	Runtime (s)
0.8	0.75	1050.28
0.8	0.8	950.33
0.85	0.8	920.54
0.85	0.85	1150.76

Table 6. Parameter optimization experiment for deep node

表6. 深度节点参数调优实验

a	b	Runtime (s)
0.85	0.8	913.14
0.85	0.85	897.45
0.9	0.85	890.24
0.9	0.9	907.80

由表4到表6可知，在根节点时a = 0.75，b = 0.7，在中间节点时a = 0.85，b = 0.8，在深度节点时a = 0.9，b = 0.85，是分支切割算法中较好的参数设定。

通过使用分支切割算法，我们得到在不同问题规模下ILP模型的求解时间，如下图所示其中，N表示环网络点数，K表示业务需求数。

Table 7. Optimized algorithm result data

表7. 算法优化后的结果数据

N K	50	100	200	300	400	500	600
20	0.75	7.75	38.16	122.21	133.27	397.67	636.13
40	0.99	7.61	42.11	107.59	126.98	365.17	648.25
60	0.87	6.68	40.97	131.44	157.34	476.84	787.51
80	0.98	8.07	46.28	106.51	229.64	530.34	657.67

表7可以很明显地看到，之前未使用分支切割算法的ILP模型最多只能处理N ≤ 30，K ≤ 30的路由和频谱分配问题，能够求得RSA问题的精确解的问题规模较小。通过使用分支切割算法进行优化，当需求数为600时RSA问题的运行时间依旧维持在一个较小的水平。可以说，分支切割算法的优化扩大了路由和频谱分配问题的求解规模，加快了求解速率。

4.3. 与遗传算法的对比实验

为进一步评估本文提出的精确ILP模型与分支切割算法的实际优势，我们在相同的实验环境下与遗传算法进行对比。该算法在弹性光网络的RSA问题中已有广泛应用，具有较强的代表性和实用性。

我们选取环网络节点数N = 30，需求数K从50至200，每组随机生成20个实例，得到的结果是这20组实例的平均值。这里的Gap为近似解和最优解的差值与最优解的比。通过实验调优，对于遗传算法而言，种群大小为100，交叉概率0.85，变异概率0.15，最大迭代数为150。

Table 8. Performance comparison between the proposed algorithm and genetic methods

表8. 本文算法与遗传算法的性能对比

需求数K	算法	FS index	Runtime (s)	Gap (%)
50	本文算法 遗传算法	40.6 44.3	0.87 2.56	0 9.11
100	本文算法 遗传算法	167.4 176.5	7.73 8.26	0 5.44
150	本文算法 遗传算法	268.3 280.1	23.33 17.51	0 4.40
200	本文算法 遗传算法	378.4 395.6	39.24 19.87	0 4.55

通过表8的数据，我们可知本文提出的精确算法具有较高的解的质量，因此在牺牲一定计算时间的情况下获取精确解有一定的必要性。

5. 结论

本研究构建了一个解决环网络中路由和频谱分配问题的ILP模型并在此基础上使用分支切割算法进行改进。该模型通过巧妙地定义变量和设计约束条件，隐式满足频谱的一致性和连续性约束，实现了模型规模的显著缩减。在实际使用求解器进行求解的过程中，我们发现影响求解时间和收敛速度的主要原因是约束条件中的大M约束。因此我们根据RSA问题自身的特点设计相应的分支策略，并通过加强频谱不重叠性这一约束为目的建立了有效不等式。实验结果表明，本文建立的简化ILP模型在求解时间和规模上具有明显优势。根据问题自身特性初始化上下界、设计分支策略、寻找合适的切割平面，构建起合适的分支切割算法，数值实验表明该算法显著扩大了问题的求解规模。与传统的启发式算法如遗传算法相比，本算法具有较好的求解质量，因此在一定的问题规模下，有必要牺牲一定的时间换取精确求解。

基金项目

本研究受到了国家自然科学基金(Nos. 12171051, 12171052)和北京市自然科学基金(No. Z220004)的资助。

NOTES

^*通讯作者。