一种用于WSON的路径与波长联合分配方法及装置

摘要: 本发明涉及光通信网络资源调度,具体地涉及一种用于wson的路径与波长联合分配方法及装置。背景技术:1、波长交换光网络(wavelengthswitchedopt...
一种用于WSON的路径与波长联合分配方法及装置

本发明涉及光通信网络资源调度,具体地涉及一种用于wson的路径与波长联合分配方法及装置。

背景技术:

1、波长交换光网络(wavelength switched optical network,wson)是下一代光传送网络的核心技术,通过波分复用(wdm)技术在单根光纤中同时传输多个波长的光信号。在wson中,当业务请求动态到达时,需要实时为其计算并分配一条从源节点到宿节点的光路,该光路包含路径(经过哪些节点和链路)和波长序列(在每个链路上使用哪个波长)。这一过程称为路由与波长分配(routing and wavelength assignment,rwa)。

2、wson中的rwa问题受到以下关键约束:第一,波长连续性约束,若路径上不使用波长转换器,则同一业务在所有链路上必须使用相同波长。第二,波长冲突约束,同一链路上的同一波长不可被多个业务同时占用。第三,波长转换器约束,仅部分节点具备波长转换能力,且转换器容量有限,每次波长转换消耗1单位容量。第四,光信噪比(optical signal-to-noise ratio,osnr)约束,端到端光信噪比必须满足预设硬阈值,否则信号质量无法保证。

3、现有技术方案包括传统最短路径算法、传统启发式搜索(a*搜索)、端到端神经网络方法以及整数线性规划(integer linear programming,ilp)方法。

4、其中,dijkstra算法、yen算法(k条最短路径)等传统图算法仅基于拓扑距离或跳数进行路径计算,完全不考虑链路的波长占用状态、转换器位置与容量等实时资源信息。在动态业务到达场景下,这些算法计算出的路径往往因波长资源冲突或转换器不足而不可行,导致阻塞率居高不下。无法反映实时波长占用状态;无法考虑波长转换器的位置与容量限制;无法评估osnr约束的可满足性;在资源紧张时产生大量不可行解,搜索效率低下。

5、传统启发式搜索中a*算法通过引入启发式函数估计从当前节点到目标节点的代价,引导搜索方向。传统a*在wson中的应用通常采用人工设计的启发式函数,如最短路径距离、跳数、或简单的链路负载权重。启发式函数人工设计,参数固定,难以适应网络状态的动态变化;无法反映波长转换器的实时拥塞状态;无法学习历史业务数据中的隐含规律;在高动态、大规模网络中扩展节点数过多,计算开销大。

6、近年来有研究尝试使用端到端神经网络(如序列到序列模型、强化学习)直接输出路径和波长序列。这类方法将rwa问题建模为序列生成问题,由神经网络一次性输出完整的光路方案。神经网络输出难以严格保证硬约束的可行性,可能输出同一链路同一波长被重复占用的非法方案,可能在非转换器节点处进行波长转换,可能超出转换器容量上限,可能不满足osnr硬阈值;产生非法解后需要额外的修复机制,增加系统复杂度;落地风险高,难以在实际网络中部署。

7、整数线性规划(ilp)将rwa问题建模为整数规划问题,通过求解器寻找全局最优解。在大规模网络(如1000节点、10万链路)和高动态业务场景下,问题规模急剧膨胀;计算复杂度极高,难以满足在线实时计算的需求(通常需要秒级甚至毫秒级响应);对计算资源要求苛刻,不适合实际网络部署。

技术实现思路

1、为了实现在动态变化的网络状态下,快速生成反映实时资源拥塞的启发式代价,减少搜索过程中的无效扩展,在利用神经网络学习能力的同时,严格保证输出光路满足波长冲突、转换器容量、osnr等硬约束,避免产生非法解。本发明实施例提供了一种用于wson的路径与波长联合分配方法及装置。

2、第一方面,本发明实施例提供了一种用于wson的路径与波长联合分配方法,包括:

3、将当前wson网络建模为有向图;其中,有向图g=(v,e)中,v为节点集合,e为有向链路集合;

4、对于链路集合中的每条链路,根据波长是否已被占用的状态,构建波长可用状态掩码向量,得到对应的低维向量、当前可用波长数量占波长数量的比例以及物理长度归一化值,拼接得到边特征向量;

5、对于节点集合中的每一节点,根据节点是否为转换器节点、转换器剩余容量的归一化值、节点的入度和出度,构建节点特征向量;

6、获取当前待分配的业务请求,根据所述业务请求中的源节点和宿节点的初始嵌入及其距离编码,构造请求向量;

7、将所述有向图、节点特征向量、边特征向量和所述请求向量输入请求条件化图神经网络模型,得到每条链路的边代价评分和每一节点的波长偏好评分;

8、根据增强状态空间的增强状态,按照预设的硬约束条件,基于预先构建的包括扩展代价和启发式代价的累计代价函数,在增强状态空间执行光路搜索,得到k条候选光路;其中,每条光路包含路径及波长序列,所述增强状态至少包括当前节点及当前波长序列;所述扩展代价至少包含由所述边代价评分引导的学习代价项及换波惩罚项,并基于所述波长偏好评分在波长转换节点处仅扩展top-m个候选波长,所述启发式代价包括从当前节点到目标节点的估计剩余代价。

9、在一个或一些可选的实施例中,在增强状态空间执行光路搜索时,基于下述不换波扩展规则和换波扩展规则进行状态扩展:

10、不换波扩展规则:对于从当前节点v的每条出边链路,执行以下检查:确定当前链路上的当前波长为可用状态,计算经过当前链路后的更新后的osnr预算不低于0;若满足上述不换波扩展规则检查条件,生成新状态,并计算累计代价;

11、换波扩展规则:仅当前节点为转换器节点且转换器剩余容量大于0时,允许换波,若满足换波扩展规则执行以下步骤:

12、获取当前节点的波长偏好评分;

13、根据波长偏好评分选择top-m个候选波长;

14、对每个候选波长,执行所述不换波扩展规则检查,若满足上述不换波扩展规则检查条件,则生成新状态,并计算累计代价,累加1次换波次数,且转换器剩余容量减1。

15、在一个或一些可选的实施例中,所述预设的硬约束条件包括:

16、同一链路同一波长不可被多条业务重复占用;

17、波长仅允许在具备波长转换能力的节点处改变,且每次波长转换消耗该节点波长转换器容量;

18、候选光路的端到端osnr满足预设硬阈值。

19、在一个或一些可选的实施例中,增强状态空间的增强状态为:

20、s=(v,λ,sw,osnr_budget),

21、其中,v为当前所在节点,λ为当前使用的波长,sw为累计换波次数,osnr_budget为剩余osnr预算。

22、在一个或一些可选的实施例中,对于链路集合中的每条链路,根据波长是否已被占用的状态,构建波长可用状态掩码向量,得到对应的低维向量、当前可用波长数量占总波长数的比例以及物理长度归一化值,拼接得到边特征向量,包括:

23、对于链路集合中的每条链路,根据波长是否已被占用的状态,构建波长可用状态掩码向量,其中w为波长数量,第λ维取值为1表示链路e上的第λ个波长当前可用于新业务分配,取值为0表示该波长已被占用或不可用;

24、通过编码器将所述波长可用状态掩码向量压缩为低维向量,其中,d为维度;

25、根据所述波长可用状态掩码向量,计算每一链路上当前可用波长数量占波长数量的比例::

26、根据所述波长可用状态掩码向量,计算每一链路的物理长度归一化值:,其中,l(e)表示当前链路e的实际物理长度,lmin表示在当前有向图中所有链路中的最小长度,lmax在当前有向图中所有链路中的最大长度,ε为一个极小的正数;

27、根据所述低维向量、当前可用波长数量占波长数量的比例、物理长度归一化值,拼接得到边特征向量:。

28、在一个或一些可选的实施例中,所述编码器为多层感知机。

29、在一个或一些可选的实施例中,所述对于节点集合中的每一节点,根据节点是否为转换器节点、转换器剩余容量的归一化值、节点的入度和出度,构建节点特征向量,包括:

30、对于节点集合中的每一节点v,根据节点是否为转换器节点、转换器剩余容量的归一化值、节点的入度和出度,构建下述4维特征向量,作为节点特征向量:

31、

32、其中,

33、,表示节点v剩余波长转换容量,表示节点v已占用波长转换容量,表示节点波长转换总容量;in_deg(v)为节点v的入度;out_deg(v)为节点v的出度。

34、在一个或一些可选的实施例中,所述获取当前待分配的业务请求,根据所述业务请求中的源节点和宿节点的初始嵌入及其距离编码,构造请求向量,包括:

35、获取当前待分配的业务请求;

36、对所述业务请求中的源节点和宿节点的节点特征分别进行线性变换得到对应的初始嵌入;

37、确定所述业务请求中的源节点和宿节点间的距离编码;

38、根据所述业务请求中的源节点和宿节点的初始嵌入及其距离编码,构造请求向量:

39、q=f([h_s]||[h_t]||[dist_encoding(s,t)])

40、其中h_s和h_t分别为源节点s和宿节点t的初始嵌入;dist_encoding(s,t)为源宿节点间的距离编码表示。

41、在一个或一些可选的实施例中,所述的方法,包括基于下述边代价评分计算公式,计算得到边代价评分:

42、=,

43、其中,和为图神经网络输出的端点节点嵌入,e为边,为边本身的原始特征,q为请求向量,f(·)为边代价头网络。

44、在一个或一些可选的实施例中,所述的方法,包括基于下述波长偏好评分计算公式,计算得到波长偏好评分:

45、,其中,属于,为第λ个波长的可学习嵌入向量。

46、在一个或一些可选的实施例中,所述累计代价函数为:

47、f(u)=g(u)+h(u);

48、其中,扩展代价g(u)为:

49、,其中,表示到达节点v的累计代价,表示链路e的长度代价,为边代价评分,表示波长转换惩罚,为节点v的转换器剩余容量;α为路径长度惩罚系数,β为换波惩罚系数,β2为转换器容量惩罚系数;

50、启发式代价h(u)为:

51、,其中,为从当前节点u到宿节点t的最短路径距离,为启发式调节系数。

52、在一个或一些可选的实施例中,所述的方法,还包括通过下述方式进行资源更新:

53、当从k条候选光路中选择一条进行实际分配后,更新网络资源状态:

54、更新链路波长占用状态:对光路经过的每条链路e和每个使用的波长λ,标记为已占用;

55、更新转换器节点容量:对光路中每个进行波长转换的节点v,执行conv_rem(v)=conv_rem(v)-1;

56、记录osnr相关参数:记录该光路的实际端到端osnr。

57、在一个或一些可选的实施例中,所述请求条件化图神经网络模型采用或图注意力网络,并通过邻居采样实现大规模图上的训练与推理。

58、在一个或一些可选的实施例中,通过下述方式训练得到所述请求条件化图神经网络模型:

59、获取训练样本集,其中,每个训练样本包括历史时刻的业务请求和对应的网络状态;

60、对于每个训练样本,根据网络状态构建有向图,构建节点特征向量和边特征向量,并根据业务请求构建请求向量;

61、使用传统搜索路径算法生成多条候选路径,并进行约束过滤,得到可行候选光路集合;

62、对于每个训练样本的可行候选光路集合中的每条可行候选光路,基于多目标综合评分函数,计算综合评分;

63、根据每一训练样本的可行候选光路的综合评分进行排序,筛选前后n%的光路标注为正样本和负样本;

64、根据所有正样本和负样本,构建偏好对集合;

65、根据每一训练样本的有向图、节点特征向量、边特征向量和请求向量,在待训练的输入请求条件化图神经网络模型进行前向计算,得到每条链路的边代价评分和每一转换器节点的波长偏好评分;

66、对于每一可行候选光路,基于预设的模型预测评分函数,计算得到模型预测评分;

67、对于每一偏好对,根据对应的模型预测评分,最小化pairwise排序损失,通过反向传播调整模型参数;

68、重复执行模型训练过程直至迭代达到预设条件,得到所述请求条件化图神经网络模型。

69、在一个或一些可选的实施例中,对每个训练样本使用传统搜索路径算法生成的多条候选路径进行约束过滤,包括:

70、波长可用性校验,检查候选路径上各链路是否存在可用波长;

71、转换器合法性校验,检查候选路径中换波点是否为转换器节点;

72、转换器容量校验,检查候选路径中转换器节点剩余容量是否满足换波需求;

73、osnr阈值校验,检查候选路径中端到端osnr是否满足预设硬阈值要求。

74、在一个或一些可选的实施例中,所述多目标综合评分函数:

75、

76、其中,表示路径长度总代价,表示该候选路径中发生换波的次数,表示发生换波的节点集合,表示转换器紧张度惩罚函数,α为路径长度惩罚系数,β为换波惩罚系数,β2为转换器容量惩罚系数。

77、在一个或一些可选的实施例中,所述模型预测评分函数:

78、

79、在一个或一些可选的实施例中,所述pairwise排序损失函数为:

80、。

81、第二方面,本发明实施例提供了一种用于wson的路径与波长联合分配装置,包括:

82、第一构建模块,用于将当前wson网络建模为有向图;

83、第二构建模块,用于对于链路集合中的每条链路,根据波长是否已被占用的状态,构建波长可用状态掩码向量,得到对应的低维向量、当前可用波长数量占波长数量的比例以及物理长度归一化值,拼接得到边特征向量;

84、第三构建模块,用于对于节点集合中的每一节点,根据节点是否为转换器节点、转换器剩余容量的归一化值、节点的入度和出度,构建节点特征向量;

85、第四构建模块,用于获取当前待分配的业务请求,根据所述业务请求中的源节点和宿节点的初始嵌入及其距离编码,构造请求向量;

86、模型评价模块,用于将所述有向图、节点特征向量、边特征向量和所述请求向量输入请求条件化图神经网络模型,得到每条链路的边代价评分和每一节点的波长偏好评分;

87、增强搜索模块,用于根据增强状态空间的增强状态,按照预设的硬约束条件,基于预先构建的包括扩展代价和启发式代价的累计代价函数,在增强状态空间执行光路搜索,得到k条候选光路;其中,每条光路包含路径及波长序列,所述增强状态至少包括当前节点及当前波长序列;所述扩展代价至少包含由所述边代价评分引导的学习代价项及换波惩罚项,并基于所述波长偏好评分在波长转换节点处仅扩展top-m个候选波长,所述启发式代价包括从当前节点到目标节点的估计剩余代价。

88、第三方面,本发明实施例提供了一种计算机可读存储介质,其上存储有计算机程序,其特征在于,该程序被处理器执行时实现如第一方面所述的用于wson的路径与波长联合分配方法。

89、第四方面,本发明实施例提供了一种计算机设备,包括存储器,处理器及存储在存储器上并可在处理器上运行的计算机程序,其特征在于,所述处理器执行所述程序时实现如第一方面所述的用于wson的路径与波长联合分配方法。

90、第五方面,本发明实施例提供了一种包含指令的计算机程序产品,当计算机程序产品在计算机设备上运行时,使得计算机设备执行如第一方面所述的用于wson的路径与波长联合分配方法。

91、本发明实施例提供的上述技术方案的有益效果至少包括:

92、本发明实施例提供的用于wson的路径与波长联合分配方法,通过引入图神经网络(gnn),将链路的实时波长占用状态、节点的波长转换器剩余容量,与业务请求的源宿节点信息相结合,学习并生成与当前网络状态高度相关的边代价评分和波长偏好评分,充当了增强状态空间搜索过程中的启发式代价,替代了传统的人工固定启发式。由于该启发式能够精准反映链路拥塞程度和转换器紧张度,搜索过程得以优先向资源充裕、代价较低的方向扩展,减少a*扩展数量,显著减少了因盲目探索不可行路径而产生的无效扩展节点数量,从而大幅提升了在线计算速度和动态业务响应能力。

93、本发明实施例提供的用于wson的路径与波长联合分配方法,采用了“学习启发式+硬约束搜索”的方式,从根本上解决了端到端神经网络方案难以保证物理层硬约束的问题。图神经网络仅负责生成引导搜索方向的边代价和波长偏好,而最终的可行光路生成则通过硬约束的增强状态空间搜索完成,在扩展状态时,强制检查并满足所有硬约束,确保了模型输出的任何光路都必然是物理上可行的合法解,避免了传统端到端方法因产生非法解而导致的高落地风险。

94、本发明实施例提供的用于wson的路径与波长联合分配方法,在模型训练时采用基于无最优标签的排序学习训练方法,无需全局最优标签即可训练启发式评分,适用于仅具历史数据的场景,有效解决了实际网络运维中难以获取全局最优解作为训练标签的难题。该方法利用传统算法(如ksp、a)快速生成一批可行候选光路,并在多目标约束下可同时得到多条候选光路,便于后续策略选择或保护机制扩展,根据多目标的综合评分函数j(l)对这些候选解进行排序,自动区分出相对优劣的候选对,模型通过pairwise排序损失进行训练,其核心目标是让模型预测的评分顺序与j(l)的排序顺序保持一致。通过这种方式,神经网络只需不断学习模仿排序偏好,即可逐步逼近多目标优化目标,从而在动态网络环境下生成更优的搜索引导代价。

95、本发明实施例提供的用于wson的路径与波长联合分配方法,通过波长掩码低维嵌入,构建波长可用状态掩码向量对应的低维向量,避免在大规模边集合上重复搬运多维特征,降低计算量。

96、本发明的其它特征和优点将在随后的说明书中阐述,并且,部分地从说明书中变得显而易见,或者通过实施本发明而了解。本发明的目的和其他优点可通过在所写的说明书以及附图中所特别指出的结构来实现和获得。

97、下面通过附图和实施例,对本发明的技术方案做进一步的详细描述。