应用MCDM的弹性光网络频谱碎片整理算法

王鲸鱼，冉金志，王 平

(1.国防科学技术大学 信息通信学院，陕西 西安 710106；2.西安电子科技大学 综合业务网理论与关键技术国家重点实验室，陕西 西安 710071)

随着信息技术的高速发展，网络带宽需求多样化和网络中传输的信息量呈爆炸式增长[1-2]，传统的波分复用技术采用固定频谱间隔来分配频谱，导致频谱资源浪费严重。弹性光网络(Elastic Optical Network，EON)由于能够更灵活地利用频谱资源，受到越来越多的关注[3-7]。路由选择与频谱分配(Routing and Spectrum Assignment，RSA)问题是弹性光网络中的核心问题，其目标是为每个到达的业务计算并分配合理的带宽和路由，从而优化频谱利用率[2]。由于频谱分配需要遵守一致性和连续性约束[3-4]，在网络的动态建立与拆除过程中，可能会产生大量的频谱碎片，而降低频谱资源的利用率并提升网络的阻塞率[4-8]。针对这一问题，已经提出了一些频谱整理的方法。文献[5]通过在频谱分配时增加不同业务间的保护带宽最小化业务带宽阻塞率，但是只适用固定调制方式，易造成带宽资源浪费，频谱利用率低。文献[8]提出了一种基于连接保持时间的非破坏性碎片整理方案。文献[9]在将频谱碎片整理方法分为串行方式与并行方式的基础上主要研究了弹性光网络的并行频谱碎片整理。文献[10]主要介绍了跳跃重整、推挽重整和先接后断三种非中断频谱碎片整理方法并比较了它们的优缺点。

虽然目前提出了很多碎片整理的算法，但大多仅考虑满足当前到达业务能够建立，没有考虑整理碎片和业务建立后链路状态对后续业务建立的影响。基于此，笔者提出一种基于多准则决策(Multiple Criteria Decision Making，MCDM)[11-13]的弹性光网络频谱整理算法，在整理频谱碎片的过程中，当涉及到碎片的移动或重路由等选择性问题时，传统做法是将业务连接移动至空闲频隙即可，而该过程可能会导致移动后网络的碎片率增加，反而降低了网络的容量。笔者拟利用多准则决策的方法对碎片整理过程中遇到的选择性问题综合考虑各种指标做出决策，从而在最大程度上整理频谱碎片，降低网络的阻塞率。

1 相关定义

为了方便算法的描述，首先对相关术语进行解释和定义。

(1) 额外空间中的额外频隙

将频谱末端的一些空间也就是每个链路中超出主要频谱部分的一些空间称为额外空间。额外空间中的频隙称为额外频隙。为了给主要频谱部分留出空间，需要将一些移动后可以改善频谱的连接移动到额外空间。额外空间中额外频隙的长度应至少等于连接请求的最大值，并且额外空间不能建立连接请求。

(2) 标签

在算法运行过程中，不同阶段整理不同类型的业务连接，“标签”是指对不同连接根据类型的不同对它们进行标记。

① “不移动”标签。“不移动”标签标记的是频谱开始端的边缘的连接且如果一个连接的左侧超过1/2(含1/2)相邻于另一个“不移动”连接，则它也将标签为“不移动”标签。在碎片整理过程中，“不移动”连接不会移到任何地方。如图1所示，因为连接A和连接B在频谱开始端，所以标记为“不移动”连接；因为连接C相邻于连接A，所以C也被标记为 “不移动”连接；因为连接D占用了两个链路，其中在链路3上的连接相邻于连接B，满足超过1/2(含1/2)相邻于标记有“不移动”连接的条件，所以连接D也被标记为“不移动”连接。

图1 “不移动”连接示意图

② “消失”标签。如果连接的剩余时间小于预定义的阈值(例如2 s)，则将该连接标签为“消失”。

③ “左移”标签。如果可以将连接移到更好的位置(即更靠近频谱的开始侧)，则将该连接标记为“左移”。

④ “右移”标签。此标签用于标记连接无法移到更好的地方或重新路由到其他路由的连接。

⑤ “重新路由”标签。不可移动的连接可以通过在其他可用路由进行重路由，从而有第二次机会设置在更好的位置，因此笔者将可重路由的连接标记为“重新路由”。

⑥ “缩短”标签：当业务连接被重新路由后，该连接所占用的链路数会减少，使得业务连接的传输占用的频隙数量减少，将这样的连接标记为“缩短”连接。

(3) 连接干扰

为了将空闲频谱块聚合到每个链路的频谱末端，所以当一条连接干扰到其他连接向频谱开始端移动时，将这条连接称为“干扰源”。“干扰源”的判断条件为：

① 该连接没有被标签为“不移动”，因为“不移动”连接在整理的过程中不会被移动并且处于频谱的开始端，不会影响其他连接前移；

② 该连接所占的频隙数和与该连接相邻的空闲频隙数之和大于该连接右侧第一个连接的大小；

③ 该连接之前的空闲频隙数量小于该连接之后第一个连接所占的频隙数量。

图2 连接干扰示意图

例如图2中，连接A没有被标签为“不移动”，连接A所占用的频隙数和相邻空闲频隙之和大于连接B的大小且连接A之前的空闲频隙数小于连接B所占用的频隙数，所以连接A干扰连接B。

(4) 空闲相邻空间的总和

空闲相邻空间的总和表示连接之前和之后的相邻空闲频隙的数量总和。

(5)链路碎片率

链路碎片率(L)与链路中的空闲频隙有关。计算一个具有N个空闲区域链路的碎片率：

(1)

其中，Fi表示第i个空闲区域中空闲块的数量。链路碎片率越大，该链路就越难再加入新连接。

最大碎片率(M)指的是链路中出现空闲频隙与有业务的频隙交叉排列。设一条链路具有N个频隙，当可用频隙的数量为奇数而被占用的频隙为偶数时，链路的碎片率最大，此时需要利用上限函数来计算其大小。此时M为

(2)

例如当N=11时，链路中的空闲频隙为6，则M=62=36。

连接碎片率(C)是一个连接在链路中的碎片率，由L平均后得到

(3)

其中，i表示连接的第i个连接，Q表示连接的总数。

为了达到比较碎片的连接速率，并方便观察，将碎片率进行指标化，使得其范围为[0，1]。首先将链路碎片率(L)及式(1)由式(4)进行归一化，得到指标化链路碎片率(NL)：

(4)

然后，将NL除以连接的总数，得到指标化碎片率N：

(5)

2 基于多准则决策的频谱碎片整理算法描述

2.1 基于多准则决策的频谱碎片整理算法

频谱碎片整理是将空闲频隙聚合在可用频谱的末尾，将到达剩余时间的连接与不可移动的连接转移至规定的额外空间中以实现频谱碎片整理。而在移动频谱碎片的过程中，移动不同的频谱碎片对网络的影响不同，有的可能会降低网络的碎片率，有的则有可能适得其反。所以，在每次选择时，采用多准则决策对频谱碎片进行整理，可以基于网络此时的状态在每个阶段中做出最佳决策来进行频谱碎片的整理。

基于多准则决策的弹性光网络频谱碎片整理算法分为5个阶段。这5个阶段中，每个阶段都会用不同的标签标记不同类型的连接，并根据多准则决策所设置的权重对连接进行判断，最后采取最佳的方案。

第1个阶段，通过判断剩余时间，将满足设定时间阈值的连接标签为“消失”，然后通过预先定义的权重将标签“消失”的连接转移到额外空间，直到额外空间被填满或没有标签为“消失”的连接，这一阶段完成后，主要频谱中就会出现一些空闲的空间。

第2个阶段，通过重新路由的方法，减少连接的数量以便腾出更多的空闲频隙。

第3个阶段，利用首次命中算法将“左移”连接移动到频谱的开始端，并将满足“不移动”连接指标的连接标签为“不移动”连接。

图3 算法总流程图

第4个阶段，利用K-最短路径法对“不移动”连接进行重新路由。如果“不移动”连接不能被重新路由，则更新其标签为“右移”连接。

第5个阶段，首先将“右移”连接移动到额外空间，然后返回到第3个阶段进行循环，直到不执行操作或者所有的连接都标签为“不移动”连接。

总流程如图3所示。5个阶段的流程如图4至图8所示。

图4 第1阶段算法流程

阶段1：

(1) 为每个源到目标节点预先进行计算储存K条最短路径；

(2) 将所有剩余时间小于t的连接标签为“消失”连接；

(3) 对于所有的“消失”连接，如果额外空间中有空闲空间，则进行下一步；

(4) 利用MCDM计算“消失”连接的得分，并将最佳连接转移到额外空间，直到所有“消失”连接转移完毕或额外空间没有空闲空间。

图5 第2阶段算法流程图

阶段2：

(1) 根据K-最短路径筛选出可以重新路由的连接并且标记为“缩短”连接；

(2) 对于所有“缩短”连接，利用MCDM计算其得分，得分最高的进行重路由，直到没有“缩短”连接；

(3) 更新连接的标签。

图6 第3阶段算法流程图

阶段3：

(1) 将在频谱第一个边缘或与频谱第一个边缘的连接相邻或1/2相邻的连接标记为“不可移动”连接；

(2) 将连接前有空闲空间的连接标记为“左移”连接；

(3) 对于所有“左移”连接，利用MCDM计算其得分；

(4) 将得分最高的连接利用首次命中算法将其进行左移，直到没有“左移”连接。

图7 第4阶段算法流程图

阶段4：

(1) 对于所有标记“不可移动”连接，利用K-最短路径筛选出可以重新路由的连接并且更新其标签为“重路由”连接；

(2) 将不可重新路由的“不可移动”连接更新其标签为“右移”连接；

(3) 对于所有“重路由”连接，利用MCDM计算其得分，将最佳连接进行重路由，直到没有“重路由”连接。

阶段5：

(1) 如果额外空间有空闲空间，则进行下一步；

(2) 对于所有标记“右移”连接，利用多准则决策计算其得分，将最佳连接转移到额外空间；

(3) 直到所有“右移”连接都转移或额外空间，没有空闲空间。

2.2 基于MCDM的频谱碎片整理算法中指标与权重设定

相关文献和电信业务数据表明各个指标在不同阶段中起到的作用不同，同一指标在不同的阶段中可能是肯定指标，也可能是否定指标。例如连接的大小(Sx)这一指标，表示连接x所需要的频隙数量，在选择最佳“消失”连接中，Sx是一个肯定指标，因为当连接具有更多的频隙时，它在转移后释放的频隙也就更多；而在选择最佳“左移”连接时，Sx是一个否定指标，因为频隙数量少的连接比频隙数量多的连接更容易得到匹配。因此，同样的指标在不同阶段中具有不同的权重和作用。以选择最佳“消失”连接为例，影响选择“消失”连接的指标有：

① 连接的大小(Sx)：连接x所需的频隙数量。肯定指标，因为当连接具有更多频隙时，它将在传输后释放更多频隙。

② 连接的数量(Lx)：连接x的连接数量。肯定指标，因为连接的数量越多，则占用网络中的空间就越多，转移后释放的空间就越多。

③ 连接受到的干扰数(Ix)：连接x受干扰的连接数。肯定指标，因为干扰连接会阻止其他连接移动到更好的位置。干扰连接x的数量越多，传输该连接越好。

④ 剩余时间(Rx)：连接x的剩余时间。否定指标，因为连接的剩余时间越短，该连接将会越快的被释放，因此，剩余时间越长的连接，占用频隙的时间也就越长，该连接便越值得被移动。

⑤ 移动后的总空闲时隙之和(Tx)：表示连接x的所有链路中所有相邻空闲时隙(在连接之前和之后)的总和。肯定指标，因为两侧都具有较多自由空间的连接，可以在传输后释放的整体性空间更多。

通过简单加性加权的方法对每个指标的重要程度进行确定(范围为1～10)。

对这5个指标进行排序，在“消失”连接的转移过程中，起决定性作用的是转移后对网络空间的影响，所以连接受到的干扰数(Ix)这一指标最为重要，而移动后的总空闲时隙之和(Tx)代表着移动连接后网络空出的频隙数，虽然也体现了对网络的影响，但是Ix的影响程度远大于Tx，因为移动的连接受到的干扰数越多，代表着这个连接对网络的影响程度越大，移动后网络的改善情况就越好。因此，为了凸显其决定性的作用，笔者将连接受到的干扰数(Ix)的重要程度设置为10，本阶段其他4个指标的重要程度设置为：移动后的总空闲时隙之和(Tx)为5；连接的大小(Sx)为4；连接的数量(Lx)和剩余时间(Rx)均为3(表示Lx和Rx重要程度相同)。最终选择“消失”连接的指标的重要程度表，如表1所示。

表1 选择“消失”连接的指标的重要程度表

然后利用层次分析法列出满足一致性的矩阵，如表2所示。

表2 选择“消失”连接的成对比较矩阵表

再规范表2，将表中的值除以总和，如表3所示。

表3 AHP法加权后的结果

最后通过求平均值，确定出筛选最佳“消失”的每个指标的权重，如表4所示。

表4 选择“消失”连接的指标及权重

通过同样的方法确定其他阶段中应选择的最佳连接的指标和权重。

选择最佳“缩短”连接的指标与权重：

① 连接差(Cx)：表示新路由和当前连接路由的连接数量之间的差。肯定指标，因为如果连接可以移动到连接数量较少的路线，将会释放更多的频隙。

② 连接的大小(Sx)：连接x所需的频隙数量。否定指标，因为由于频隙数量的限制，要找到一个需要频隙较多的新连接比较困难。

③ 连接的数量(Lx)：连接x的连接数量。肯定指标，因为连接的数量越多，则占用网络中的空间就越多，转移后释放的空间就越多。

④ 连接受到的干扰数(Ix)：连接x干扰的连接数。肯定指标，因为干扰连接会阻止其他连接移动到更好的位置。干扰连接x的数量越多，传输该连接越好。

⑤ 剩余时间(Rx)：连接x的剩余时间。肯定指标，因为剩余时间较少的连接将更快完成，并在链接上生成片段；但是剩余时间更多的连接将保留更多的时间，因此对其进行缩短操作。

⑥ 移动后的总空闲时隙之和(Tx)：表示连接x的所有链路中所有相邻空闲时隙(在连接之前和之后)的总和。这是一个肯定的指标，因为两侧都具有较多自由空间的连接，可以在传输后释放的整体性空间更多。

选择最佳“缩短”连接的指标的重要程度如表5所示。权重的设定如表6所示。

表5 选择最佳“缩短”连接的指标的重要程度

表6 选择最佳“缩短”连接的指标与权重

选择最佳“左移”连接的指标与权重：

① 移动后的总空闲时隙之和(Tx)：表示连接x的所有链路中所有相邻空闲时隙(在连接之前和之后)的总和。肯定指标，因为两侧都具有较多自由空间的连接，可以在传输后释放的整体性空间更多。

② 连接的大小(Sx)：连接x所需的频隙数量。否定指标，因为小连接有更多机会找到比大地方更好的地方。

③ 剩余时间(Rx)：连接x的剩余时间。肯定指标，因为剩余时间较少的连接将更快完成，并在链接上生成片段；但是剩余时间更多的连接将保留更多的时间，因此对其进行缩短操作。

④ 距离(Dx)：连接x与频谱开始端的距离。肯定指标，越靠近频谱的开始端，越容易被移动。

⑤ 连接的数量(Lx)：连接x的链接数。否定指标，因为链接数较少的连接找到空闲频隙的机会比链接数较多的连接大。

⑥ 移动后碎片改善率(Fx)：新的Lx与现有Lx的差异。因为移动一个连接可以降低其链接的碎片率，所以这是一个肯定指标。

⑦ 连接受到的干扰数(Ix)：受连接x干扰的连接数。肯定指标，因为干扰连接会阻止其他连接移动到更好的位置。干扰越高，传输该连接越好。

⑧ 从起点开始的新距离(Nx)：连接点x的新位置距光谱起点的距离。否定指标，因为笔者的目标是将占用的频隙移到频谱的开始端，将空闲频隙移到频谱的末尾端。因此，离频谱开始端较近的位置比距离较远的位置更好。

选择“左移”连接的指标的重要程度如表7所示。权重的设定如表8所示。

表7 选择“左移”连接的指标的重要程度

表8 选择“左移”连接的指标与权重

因为移动“右移”连接与“消失”连接都是以对网络空间的影响大小为主，影响越大，移动后频谱的改善效果就越好，所以在指标的选择与权重的确定过程中移动“右移”连接与移动“消失”连接的指标与权重相同。选择“重路由”连接与“缩短”连接时，由于都采用的K-最短路径算法，所以选择“重路由”连接与“缩短”连接的指标与权重相同。

3 仿真分析

3.1 仿真条件

为了评估算法的性能，采用美国国家科学基金会(National Science Foundation，NSF)的主干网络进行仿真，如图9所示。该网络拥有14个节点和21个链路，每个节点之间的距离以km为单位。每条链路上具有110个频隙，其中10个作为额外频隙，每个频隙的大小为12.5 GHz。

图9 NSF网络拓扑图

仿真方案：采用随机接入一定数量的业务请求连接，每个业务连接大小在2～10个频隙之间随机产生，每个连接的保持时间为10 s，业务的源节点和目标节点随机生成，路由方法采用K-最短路径法，其中K等于3。为了验证算法的有效性，笔者选取首次命中(K-Shortest Path with First Fit spectrum allocation，KSP-FF)算法[10]和推挽碎片整理算法(Push Pull，PP)[10]进行比较。仿真过程中，设置“消失”连接的剩余时间阈值为10 s，对带宽阻塞率、请求阻塞率和频谱利用率进行分析，其中带宽阻塞率表示被阻塞的请求带宽与总请求带宽的比值，请求阻塞率表示被阻塞的连接数量与总请求的连接数量之比。

3.2 阻塞率分析

图10为分别采用KSP-FF、PP和基于MCDM碎片整理算法下的网络带宽阻塞率。图中，E为Erlang的缩写，中文译为“厄兰“，话务量，意为”占线小时”。以下图同。

图11为基于KSP-FF和多准则决策碎片整理算法的带宽阻塞率改善对比图。

图10 带宽阻塞率 图11 带宽阻塞率改善对比图

从图10可以明显看，出当业务连接较少时，3种算法的带宽阻塞率差距不大，而随着业务连接数量的增加带宽阻塞率都呈现上升趋势，而基于多准则决策的算法优于PP和KSP-FF，当业务请求负载达到300 E即高负载时，基于多准则决策的碎片整理算法带宽阻塞率为36%，明显低于PP和KSP-FF的带宽阻塞率。同时，从图11可以看出，当连接数达到60时，首次命中算法的网络开始出现阻塞情况，而基于多准则决策的算法在业务连接数量达到100左右时，带宽阻塞率才开始出现变化；此时基于多准则决策的算法，相比首次命中的算法带宽阻塞率改善最高可达20%；当业务连接数量达到120左右时，可以看出，基于多准则决策的算法整理后的带宽阻塞率有所降低，当达到140左右时发生突变；此时相比于首次命中算法，基于多准则决策算法的带宽利用率改善了约10%。随着业务连接继续增加，基于多准则决策的频谱碎片整理算法相比于首次命中算法带宽阻塞率降低了约17%。

从上述分析可以得出，基于多准则决策的频谱整理算法可以有效降低网络的带宽阻塞率。

图12 业务请求阻塞率

图13 业务请求阻塞率改善图

图14 频谱利用率

图12和图13为业务请求阻塞率仿真结果。从图12可以看出随着业务连接数量的增加，3种算法的网络请求阻塞率呈现上升趋势，而基于多准则决策的算法的请求阻塞率小于KSP-FF和PP的阻塞率；从图13可以看出，基于多准则决策的算法在业务请求达到120时，才出现请求阻塞的情况，当业务请求达到140时，基于多准则决策的算法相对首次命中算法的请求阻塞率得到明显改善，此时首次命中算法整理后的请求阻塞率为15%左右，基于多准则决策的碎片整理算法整理后的请求阻塞率为10%左右。由以上分析可以得出，相对于其他两种算法，基于多准则决策的算法可以有效改善弹性光网络的业务请求阻塞率。由于多准则决策增加了判决机制，算法运行时间大于KSP-FF和PP算法，但是基于多准则决策在改善业务阻塞率方面有明显的优势。

3.3 频谱利用率分析

图14为频谱利用率仿真图，可以看出整理后的频谱利用率高于整理前的频谱利用率。

随着接入业务连接的增多，当达到高流量负载(业务请求数量达到200 E)时，基于多准则决策的频谱利用率达45%；当业务请求数量达到300 E时，基于多准则决策的频谱利用率高达65%；而基于KSP-FF在高负载下，频谱利用率最高约达38%；因此基于多准则决策的频谱碎片整理算法相比于基于首次命中的频谱碎片整理算法的频谱利用率，得到了很大的改善。这表明，基于多准则决策的频谱碎片整理算法，在降低带宽阻塞率和请求阻塞率的同时，提高了频谱利用率，进而提高了网络资源的利用率。

4 总 结

针对当前弹性光网络中路由选择与频谱分配算法的频谱碎片整理问题，基于多准则决策，笔者提出了弹性光网络中频谱碎片的整理算法降低业务带宽阻塞率。根据层次分析法确定了算法在运行过程中不同指标的权重，举例说明了多准则决策的适用性，并且理论分析和仿真结果表明，基于多准则决策的频谱碎片整理算法，可以有效地提高频谱利用率并降低网络的阻塞率。