基于多维帧频谱感知的军用光网络资源分配算法

田相轩，石志强，刘娟，吕莹

(陆军装甲兵学院，北京 100072)

军用光网络在民用光纤技术的带动下有了长足的发展，不仅在通信容量上，而且在信息传输速率与业务种类上都有了迅速的增长。光网络资源的有效调度成为制约提高部队各固定作战单元通信信道利用率/性能的重要制约因素。整个光网络的带宽是固定的。弹性光网络具有高效频谱资源利用率、动态适应带宽调整、灵活调度业务占用频谱资源以及梳理业务传输速度与调制格式等优势，能高效地利用光网络频谱资源[1]。在弹性光网络中，频谱资源分配需满足频谱一致性原则和频谱邻接性原则，频谱级的资源分配提高了频谱利用率，但在细粒度的频谱资源分配的策略下，频谱碎片大量产生，增加了资源分配的复杂性，降低了资源的可用性[2-3]。

针对此类问题，目前主要有3种优化策略，分别是碎片整理、光疏导和频谱分割策略。碎片整理策略是指在业务请求资源已分配或业务请求被阻塞的情况下，通过释放占用的频隙，少占用新的频隙实现光路连通，分两种情况：第一种情况重新分配链路与频谱资源，会打乱现有业务请求传输光路；第二种情况在光路继续保持的状态下进行频谱调整[4-6]。光疏导策略的目的是减少光转发器的使用与频谱保护带的插入，提高频谱资源的利用率，提出将业务请求占用带宽最大的优先分配，采用高于业务请求的调制等级等方法，缺少对网络频谱资源现有、实时状态的考虑，不能实现对业务请求的合理分配[7-9]。频谱分割方法(Split Spectrum Approach，SSA)在弹性光网络中出现任务请求速率太高导致堵塞的情况，将任务请求分解成一组低速率的任务请求，综合多种因素，包括占用的时隙数量以及调制的格式、资源分配带来的新的频谱碎片数量以及业务请求分割的数量，来确定路径、频隙和调制格式的选择，能够有效提高传输效率，减轻频谱碎片化，降低数据阻塞率(Bit Blocking Rate，BBR)。SSA应用在两种场景：一是在光网络链路中，没有连续的频谱来承担所需要的带宽；二是在传输调制或传输过程中出现信号损失，使任务请求的速率无法满足[10-12]。

笔者采取频谱分割的思路，基于频谱的大小与任务请求对光网络带宽资源的实际需求情况，解决弹性光网络中多任务请求资源调度的资源利用率低、频谱碎片化程度高的问题，提出了基于多维帧频谱感知的多任务请求资源分配算法(The Algorithm of the Multi-task Resource Scheduling Based on the Multi-dimensional Frame Matrix of the Cognitive Spectrum,MRSA-MFM)，当多任务请求到达网络时，根据网络的实时资源占用和空闲状态确定网络资源多维帧矩阵，利用资源多维帧矩阵计算k条路径的频谱复用率，确定任务请求分裂度，选定最优分配的频谱，提高光网络资源的可用性和延展性，最大程度的降低频谱资源的碎片化。

1 模型设定

1.1 流量限制原则

业务请求的速率应小于业务请求源节点调制解调器的调制速率之和。

(1)

式中：DP为任务请求分解的数量；m为源节点处调制解调器的数量；Q(y)为调制解调器速率；Qs为业务请求的速率，即业务请求的最大速率应小于调制解调器的可调制最大速率，并且当业务请求分解成DP个子请求，业务请求的速率与保护带宽QG的和也应小于调制解调器的可调制的最大速率。

1.2 频谱一致性原则

频谱一致性原则要求在任务请求的源节点到目的节点之间只能使用同一频谱，即在光路第1段链路确定频隙序列后，剩余的所有链路段必须使用相同的频隙序列。

1.3 频谱邻接性原则

对一个业务请求或者一条光路的建立，在频谱的分配中频隙的使用必须是连续的、相邻的。在业务请求的可用频谱块Bq,k，表示任务请求q的可用的连续空闲频隙，即可用频谱块(Wass,Fs,wass,i,j)，频谱块的起始与终止节点分别为i,j，Wass是指所占用的波长，Fs为时隙,wass为时隙的数量，其中：

j-i=wass.

(2)

1.4 频谱冲突限制

频谱冲突限制要求同一频隙在同一光纤链路上只能被一个任务请求占用，因此同一光纤链路上传输的两信号不能同时占用同一频隙。

2 具体算法

MRSA-MFM算法主要是基于多任务请求对光网络资源的实际需求状态，资源分配完毕后频谱资源的碎片化程度，考虑任务请求的负载容量、路由跳数、频谱完整度和任务分裂度这4个因素，评定对剩余资源分配的影响，从而提高资源的利用效率。基本算法主要分为构建网络资源多维帧矩阵、业务请求分解策略和频谱复用率计算3个部分，其中通过构建多维帧矩阵，描述多任务请求的资源情况，从而构建多任务请求的优先级评定确定资源的分配顺序，合理的资源分配顺序能够有效地利用网络的宽度和资源的深度。其次，针对网络资源的实际状态，以及任务请求的资源需求情况，合理的确定任务请求分解方案，在满足用户需求的前提下，最大化提高带宽利用率。

2.1 资源多维帧描述

多任务请求同时到达网络时，根据业务请求光路建立所占用的光网络资源的多少与光网络的连通状态确定邻接矩阵；设置波长，确定资源状态矩阵，实现资源从节点到波长的多维描述。

1)建立光网络拓扑邻接矩阵

(3)

式中：E为网络拓扑邻接矩阵；V是指存在的节点数量；i,j为链路的某一个源节点和目的节点；Ei,j表示链路连通状态，Ei,j=0表示链路Ei,j未连通，Ei,j=1表示链路Ei,j连通。

2)建立光网络资源状态矩阵

(4)

式中：Wi,j为链路Ei,j的资源状态矩阵。式(4)基于式(3)建立，若两节点之间有连接，构建资源的非零表示参数Wi,j，否则为0；式(4)中矩阵的每个元素的展开项为

(5)

式中：m,n为光路链路中波长的数量与频隙的数量；Wm,n为二元数，Wm,n=0表示光路链路中第m个虚拟波长的第n个频隙空闲,Wm,n=1表示光路链路中第m个虚拟波长的第n个频隙被占用。虚拟波长只是界定的一个频率范围与在这个频率范围上的频隙，不再受限于波长一致性原则。

基于复杂网理论与图论的基本原理，借鉴无线网络中的连通度计算方法，假定拓扑中的任意节点的优先级相同，根据网络节点之间的连通程度，设定光网络拓扑的连通度，在路由的层面上，对光网络进行定量的描述:

(6)

式中：j为拓扑中第j节点，作为中心节点；yj为第j节点作为中心节点时划分子图的数量；Vi为第i子图的节点数量；li为第i子图到中心节点的平均连通距离。

在光网络连通度较高的状态下(连通度Crate=1)，即任意两节点之间都能互连，则路由的长短对光路的建立影响较小，业务请求的速率对光路的影响较大；反之，当网络的连通度较低的状态下，业务请求路由的长度，对光路的建立影响较大，任务请求速率对光路建立的影响降低。设定优先等级计算如式(7)所示，式中多条路径的选取通过最短路径算法获得：

(7)

式中，hq,k表示任务请求q相对应可用路径的跳数。为降低计算复杂度，设定k=5(经仿真分析，若分裂次数大于5，复杂度急剧上升)。

2.2 业务分割与频谱分配策略

提出频谱复用率的度量参数，创新性地利用资源的多维帧矩阵判定资源的有效使用情况，通过业务请求的资源与目前网络资源的空闲情况计算，获取网络资源利用率最大且频谱碎片化程度较低的频谱分配方案，提高频谱资源利用率，减少频谱碎片化。

根据频谱冲突限制原则、频谱邻接原则、频谱一致性原则，与优先级设定策略中的k条路径备用路由算法获得业务请求的需求资源矩阵：

(8)

式中：Qx,y为业务请求所需求的资源状态矩阵；x,y为业务请求的起始节点与目的节点；Wm,n表示业务请求需要光路链路中第m个波长的第n个频隙空闲，不需要的频隙在Qx,y中设定为1.与链路资源状态矩阵求交集可得业务请求光路的可用资源状态矩阵：

(9)

(10)

(11)

根据算法中的分解次数限制，满足式(11)的情况下，以频隙为最小单位进行业务分割，基于子业务请求频谱复用率的和最小的方案进行业务请求分解，获得子业务请求，分解之后的子业务请求作为独立请求处理。

2.3 算法描述

输入为网络资源状态矩阵与多任务请求集合；输出为任务请求的频谱资源分配方案，多维帧频谱感知的多任务请求资源分配算法(MRSA-MFM)流程如图1所示。

步骤1构建网络拓扑邻接矩阵、网络资源多维帧矩阵，为路由计算与频谱分配做准备。

步骤2对服务等级相同的任务请求，根据优先级设定策略，确定资源分配顺序。

步骤3按照优先级顺序，对业务请求进行初步筛选，设定业务请求的初始分裂次数DP=0.

步骤4业务请求速率小于起始节点调制解调器速率的直接到步骤6.

步骤5业务请求速率大于起始节点调制解调器速率或由步骤6导出的请求进行业务请求分解，并对该业务请求的分裂次数DP的值加1.

步骤7当光网络为业务请求Qx,y第k条路由可提供的频谱资源状态矩阵满足业务请求的带宽需求时，计算该条路由频谱资源分配后的频谱复用率，否则，不予进行计算。根据业务请求的频谱复用率，从待选的可用频谱块中选取频谱复用率最高的确定为业务请求可分配频谱；当业务请求无可用频谱资源时，核查业务请求的分裂次数，若DP≤2，将该业务请求转到步骤5，否则设定该任务请求拒绝。

步骤8待资源分配结束，实时更新资源空闲矩阵，更新业务请求的频谱复用率。

3 仿真验证

为验证本文提出算法的有效性，在NSFNET(14个节点，21条双向光纤链路)上进行验证，通过Matlab软件仿真的方式，采用对比验证的方式进行验证，相对比算法为NRSMLA和SSRSMLA[12]。假设每个光纤链路上有200个频隙，频隙带宽为10 GHz，保护带宽为5 GHz.调制解调器的速率分别为25，50，75，100，150，200 Gbit/s.随机产生任务请求，任务请求的大小为{10,20,30,40,50,60,70,80,90,100}Gbit/s，产生的过程服从泊松分布。假定随机生成7组任务请求分别为{150,175,200,225,250,275,300}，在给定的光网络资源频谱下，任务请求数量较多。

网络负载重，分别调用NRSMLA、SSRSMLA算法与本文提出的MRSA-MFM算法进行频谱资源的分配，分配结果如图2所示。从图2中可看到，MRSA-MFM算法在不同负载的情况下能降低任务请求建立光路的阻塞率。随着任务请求数量的增大，网络负载加大，基于网络实时动态的频谱资源的优先级分配实现了任务请求的梳理，基于频谱复用率与业务分裂的频谱资源分配实现了资源使用的最大化，降低了频谱碎片，使得笔者提出的算法优势逐渐明显；从图2可得，当任务请求数量达到250条左右时，本文算法的优势逐渐显现，到任务请求数量达到300条时，相比SSRSMLA算法性能提升3.1%，相比首次命中法的NRSMLA算法性能提升6.1%.

业务请求的分解次数的平均值的变化趋势，随着任务请求数量的增大，业务请求分解的次数逐渐达到饱和值，业务请求的分裂对光路建立的贡献达到饱和，业务请求的阻塞率不断增加，如图3所示。随着网络负载的不断增大，通过业务请求的分裂实现了频谱碎片的有效利用，随着业务请求分裂次数的增加也导致了光路传输的延时的增加，业务请求占用光路的时间延长，另一角度出发业务请求耗费的光路资源增加，降低了后续业务请求建立光路的可能性。

随着任务请求建立光路数量的增多，3种算法的复杂度逐渐上升，延时不断增大，如图4所示。

从图4可以看出，本文算法的延时均小于文献中提到的两种算法。因为算法引入了频谱复用率的核算与优先级的设定，虽增加了算法复杂度，但延时的表现仍然保持在合理的范围。

4 结束语

笔者针对复杂网络多任务请求的频谱资源分配问题提出了基于多维帧频谱感知的多任务请求资源分配算法，算法按照资源多维帧矩阵描述，频谱复用率与任务分解定位频谱的方法实现资源的高效分配，降低频谱碎片化，提高资源的可用性。本文的核心在于利用资源的多维帧矩阵描述的方法计算了频谱复用率，结合网络状态确定了资源分配优先级与频谱分配定位策略，实现了业务请求的梳理，网络资源的高效利用，降低了频谱的碎片化，对基于频谱粒度的光网络资源分配具有参考性，为提高网络资源的利用率提供了参考方案。