一种基于模糊博弈的多域光网络动态组播共享保护方法

摘要

本发明公开了一种基于模糊博弈的多域光网络动态组播共享保护方法，该方法虚拟了两个模型分别计算组播树和组播保护树，然后进行模糊博弈，结成合作联盟后优化各个组播树的路径构成，为动态组播业务生成一对最优的组播工作树和组播保护树。分析及实验结果表明，该方法的时间复杂度较低，在一定数量的动态组播请求范围内，降低了动态组播业务的阻塞率，提高了光网络资源的利用率。

权利要求

1.一种基于模糊博弈的多域光网络动态组播共享保护方法，用于规划多域光网络中每个组播请求的工作树和组播保护树，在所述的多域光网络中包括由多个组播请求组成的组播请求集合R＝{Rm|m＝1,2,…,k}，其中k>1，Rm为第m个组播请求，其特征在于，所述的方法按照以下步骤执行：步骤1、根据待规划的多域光网络，建立组播工作模型；复制所述的组播工作模型，获得组播保护模型；

步骤2、分别在组播工作模型以及组播保护模型中采用路径搜索算法寻找第m个组播请求Rm的工作树Tm以及保护树Pm；

若找到的工作树Tm所经过的网络节点与保护树Pm所经过的网络节点均不相同，则执行步骤3；

否则执行步骤5；

步骤3、判断在执行第m个组播请求Rm时，在第m个组播请求Rm前的所有组播请求是否已经结束，若存在任何一个组播请求未结束，则执行步骤4；否则输出第m个组播请求Rm的工作树Tm和保护树Pm；

步骤4、利用模糊博弈的方法对第m个组播请求Rm的工作树Tm以及所有未完成的组播请求的工作树进行更新，获得第m个组播请求Rm的更新后的工作树T′m；

利用模糊博弈的方法对第m个组播请求Rm的保护树Pm以及所有未完成的组播请求的保护树进行更新，获得第m个组播请求Rm的更新后的保护树P′m；

输出第m个组播请求Rm更新后的工作树T′m和更新后的保护树P′m；

步骤5、判断m

2.如权利要求1所述的基于模糊博弈的多域光网络动态组播共享保护方法，其特征在于，在所述的步骤2中所述的路径搜索算法为最小代价链路生成方法。

说明书

一种基于模糊博弈的多域光网络动态组播共享保护方法

技术领域

[0001] 本发明涉及组播共享保护方法，具体涉及一种基于模糊博弈的多域光网络动态组播共享保护方法。

背景技术

[0002] 大容量、长距离传输一直是光通信的基本发展方向，作为其重要分支，组播通信向着多运营商智能化的趋势发展。组播通信生存能力需求得到越来越多的关注，随着业务动态变化情况复杂，如何实现动态组播业务保护成为一个难题。多域光网络动态组播业务中，随机到达的组播请求具有实时性，并在请求存续期间对保护能力有一定要求，通常逐个请求进行保护配置。光网络共享保护机制是指一种为光网络上的多条业务路径配置一条或者多条备份路径的保护机制，一旦某条业务路径发生故障可以启动保护路径，相较于专用保护机制而言极大地提高了网络资源利用率。

[0003] 国内外学者对组播共享保护技术进行了较为深入的研究。其中，现有技术1提出的LP方法和现有技术2提出的CL-SSP方法都属于基于分段保护的层共享保护，一方面分段的方案能够提升资源共享的效率，但是如果对工作路径分段过多会消耗大量保护资源，从而恶化了网络时延，造成网络性能的降低。而现有技术3提出的定向图组播保护方法忽视了路由必须被执行的现实，采用路径对的方案，牺牲了复杂度但是提升的性能有限。

[0004] 因此，现有技术多数共享保护方案先计算组播工作树，然后对主路径进行分段实施保护，这种方法在工作树的成本降低方面有一定优势，但是忽略了网络的负载压力，而且不从全局角度统一对组播请求进行配置，易导致局部优化，造成“1+1<2”现象。

发明内容

[0005] 本发明的目的在于提供一种基于模糊博弈的多域光网络动态组播共享保护方法，用以解决现有技术中组播共享保护方法存在的网络的负载压力大、资源利用率低以及阻塞率高的问题。

[0006] 为了实现上述任务，本发明采用以下技术方案：

[0007] 一种基于模糊博弈的多域光网络动态组播共享保护方法，用于规划多域光网络中每个组播请求的工作树和组播保护树，在所述的多域光网络中包括由多个组播请求组成的组播请求集合R＝{Rm|m＝1,2,…,k}，其中k>1，Rm为第m个组播请求，所述的方法按照以下步骤执行：

[0008] 步骤1、根据待规划的多域光网络，建立组播工作模型；复制所述的组播工作模型，获得组播保护模型；

[0009] 步骤2、分别在组播工作模型以及组播保护模型中采用路径搜索算法寻找第m个组播请求Rm的工作树Tm以及保护树Pm；

[0010] 若找到的工作树Tm所经过的网络节点与保护树Pm所经过的网络节点均不相同，则执行步骤3；

[0011] 否则执行步骤5；

[0012] 步骤3、判断在执行第m个组播请求Rm时，在第m个组播请求Rm前的所有组播请求是否已经结束，若存在任何一个组播请求未结束，则执行步骤4；否则输出第m个组播请求Rm的工作树Tm和保护树Pm；

[0013] 步骤4、利用模糊博弈的方法对第m个组播请求Rm的工作树Tm以及所有未完成的组播请求的工作树进行更新，获得第m个组播请求Rm的更新后的工作树T′m；

[0014] 利用模糊博弈的方法对第m个组播请求Rm的保护树Pm以及所有未完成的组播请求的保护树进行更新，获得第m个组播请求Rm的更新后的保护树P′m；

[0015] 输出第m个组播请求Rm更新后的工作树T′m和更新后的保护树P′m；

[0016] 步骤5、判断m＜k是否成立，若成立，令m＝m+1后，执行步骤2；否则结束。

[0017] 进一步地，在所述的步骤2中所述的路径搜索算法为最小代价链路生成方法。

[0018] 本发明与现有技术相比具有以下技术效果：

[0019] 1、本发明提供的一种基于模糊博弈的多域光网络动态组播共享保护方法利用模糊博弈的算法对工作树以及保护树的链路进行更新，使得网络在故障发生之后能够快速恢复光信号的传输，从而发挥了保护机制的优势；

[0020] 2、本发明提供的一种基于模糊博弈的多域光网络动态组播共享保护方法动态地规划好各组播请求的组播工作树和保护树，及时释放到期请求的链路资源，而且工作树之间和保护树之间分别可以共享链路资源，能够将阻塞率降到最低。

附图说明

[0021] 图1为本发明的一个实施例提供的方法流程图；

[0022] 图2为本发明的一个实施例提供的多域光网络G；

[0023] 图3为本发明的一个实施例提供的多域光网络拓扑图；

[0024] 图4为本发明的一个实施例提供的组播请求R1路径示意图；

[0025] 图5为本发明的一个实施例提供的组播请求R2路径示意图；

[0026] 图6为本发明的一个实施例提供的发生故障瞬间的光谱图；

[0027] 图7为本发明的一个实施例提供的运行本发明方法提供的保护机制后的光谱图；

[0028] 图8为本发明的一个实施例提供的不同方法阻塞率比较示意图；

具体实施方式

[0029] 多域光网络：随着光通信技术的迅猛发展,光网络设备的大规模部署和多种光通信技术的广泛应用,光网络的分域管理成为一种必然选择。在新一代波分复用的大型光网络体系中,根据设备类型、运营服务商、地域划分的不同均可分为不同的域,从而形成了多域光网络。

[0030] 组播工作模型：根据多域光网络的实体结构建立的虚拟的用于获取组播工作树路径的网络模型。

[0031] 组播保护模型：根据多域光网络的实体结构建立的虚拟的用于获取组播保护树树路径的网络模型。

[0032] 链路权值：是网络链路的参量，用以衡量该链路的状态，为网络分析决定信号传输流向作铺垫，当链路权值为无穷大时，该条链路从网络中断开。

[0033] 工作树：在多域光网络中，数据是通过网络沿着单一路径从源节点向目的节点传递，源节点为了向所有目的节点传递数据，一般采用组播工作树表示当前组播在多域光网络里经过的链路。

[0034] 保护树：工作树的备用链路，链路经过多个网络节点。

[0035] 模糊博弈：将策略集或特征函数模糊化的一种博弈，模糊博弈是合作博弈新的理论分支，与传统合作博弈不同的是，模糊博弈参与者具有部分合作可能性，局中人以无限多的不同参与水平与其他局中人合作，从而获得联盟整体收益和结构分布的最优。在本发明中，定义一个模糊博弈G＝(N,m,v)，其中N＝{N1,N2,…,Ni}是局中人集合，N的任意子集称为联盟， 称为空联盟；m∈RN描述所有局中人的活动水平，是局中人的行为选择；v是特征函数，是局中人行为选择后的总收益。

[0036] 以下是发明人提供的具体实施例，以对本发明的技术方案作进一步解释说明。

[0037] 实施例一

[0038] 在本实施例中公开了一种基于模糊博弈的多域光网络动态组播共享保护方法，用于规划多域光网络中每个组播请求的工作树和组播保护树，在所述的多域光网络中包括由多个组播请求组成的组播工作请求集合R＝{Rm|m＝1,2,…,k}，其中k>1。

[0039] 在本实施例中，生成的工作树集合T＝{T1,T2,…,Tk}以及组播保护树集合P＝{P1,P2,…,Pk}，第m个组播请求Rm的工作时间为

[0040] 所述的方法按照以下步骤执行：

[0041] 步骤1、根据待规划的多域光网络，建立组播工作模型；复制所述的组播工作模型，获得组播保护模型；

[0042] 在本实施例中，相当于定义了两个虚拟平面，分别是组播工作模型pane1和组播保护模型pane2，两个虚平面之间互通已用拓扑的信息，分别在pane1和pane2上对组播工作树和组播保护树的请求进行路径计算。

[0043] 在本实施例中，在组播工作模型pane1和组播保护模型pane2中，每条链路都具有初始链路权值w。

[0044] 步骤2、分别在组播工作模型以及组播保护模型中采用路径搜索算法寻找第m个组播请求Rm的工作树Tm以及保护树Pm；

[0045] 若找到的工作树Tm所经过的网络节点与保护树Pm所经过的网络节点均不相同，则执行步骤3；

[0046] 否则执行步骤5；

[0047] 具体地，步骤2的流程为在组播工作模型中寻找第m个组播请求Rm的工作树Tm，设置第m个工作树Tm的链路权值为 后，其中 为第m个工作树Tm的初始链路权值， λ为权重参数，0＜λ＜1，在组播保护模型中将第m个组播请求Rm的工作树Tm对应链路的链路权值设置为无穷大；

[0048] 同时，在所述的组播保护模型中寻找第m个组播请求Rm的保护树Pm，设置第m个保护树Pm的链路权值为 后，其中 为第m个保护树Pm的初始链路权值， 在组播工作模型中将第m个组播请求Rm的保护树Pm对应的链路的权值设置为无穷大；

[0049] 在本实施例中，先在组播工作模型上处理第m个组播请求Rm的工作树Tm，获得工作树Tm的方法可以是经典的最小代价链路生成方法，也可以是采用基于博弈理论的工作树以及组播保护树生成方法获得。

[0050] 可选地，为了提高组播共享保护方法的效率，路径搜索算法为最小代价链路生成方法。

[0051] 具体包括：

[0052] STEP1：给定光网络G、组播请求R、该组播请求的目的节点集合M和最小生成树Tk上所有节点集合Vk，k为正整数，令k＝1，源节点Vs作为最小生成树T1，则Tk＝T1，VK＝V1＝{Vs}。

[0053] STEP2：令集合M＝M-Vk，在集合M中逐一搜索余下的所有目的节点至生成树上各节点的路径，比较得出距离最小生成树Tk最近的目的节点Vi，将从目的节点Vi到最小生成树Tk的最短路径添加至Tk，将该路径上的所有节点加入集合Vk，令k＝k+1。

[0054] STEP3：判断 是否成立，若成立转STEP4，若不成立转STEP2。

[0055] STEP4：输出Tk。

[0056] 获得工作树Tm之后，在组播工作模型pane1中设定的工作树Tm的权值为 在组播保护模型中将第m个组播请求Rm的工作树Tm对应链路的链路权值设置为无穷大。

[0057] 在组播保护模型中也同样地采用最小代价链路生成方法获得保护树Pm，将保护树Pm链路权值设置为 后，在组播工作模型中将第m个组播请求Rm的保护树Pm对应的链路的权值设置为无穷大。

[0058] 由于在步骤2的处理中，当获得了第m个工作树时，会在组播保护模型中将工作树对应的链路权值设置为无穷大，因此在组播保护模型中寻找保护树Pm时，会存在找不到保护树的情况。反之，在组播工作模型也会存在找不到工作树Tm的情况。

[0059] 在本步骤中，如果不能同时找到第m个组播请求Rm的工作树Tm和保护树Pm就直接执行步骤6。

[0060] 步骤3、判断在执行第m个组播请求Rm时，在第m个组播请求Rm前的所有组播请求是否已经结束，若存在任何一个组播请求未结束，则执行步骤4；否则输出第m个组播请求Rm的工作树Tm和保护树Pm；

[0061] 步骤4、利用模糊博弈的方法对第m个组播请求Rm的工作树Tm以及所有未完成的组播请求的工作树进行更新，获得第m个组播请求Rm的更新后的工作树T′m；

[0062] 利用模糊博弈的方法对第m个组播请求Rm的保护树Pm以及所有未完成的组播请求的保护树进行更新，获得第m个组播请求Rm的更新后的保护树P′m；

[0063] 输出第m个组播请求Rm更新后的工作树T′m和更新后的保护树P′m；

[0064] 在本实施例中，令在第m个组播请求Rm之前开始且未结束的组播请求的工作树为博弈局中人进行模糊博弈，进行模糊博弈时通过对每一个工作树的特征函数进行博弈，特征函数由多个因素共同决定，包括成本，时延，阻塞率，误码率以及链路权值等。对于第i个工作树的特征函数为：

[0065]

[0066] 其中，i∈I，I为进行模糊博弈的局中人的总数，I≤m；

[0067] costi为第i个工作树的成本函数，取决于光纤链路的物理长度，建设成本和分光节点数量等。

[0068] delayi为第i个工作树的时延函数，是光信号通过节点和链路等元器件造成的传输延迟，经过的跳数越多时延越长。

[0069] beri为第i个工作树误码率，是光信号从整条路径的源端传输到目的端之后，目的端接收的信号中的错误比特的数量与整个比特数之比。

[0070] W为第i个工作树的链路权值。

[0071] 计算每个工作树的特征函数，保留特征函数值最大的联盟。

[0072] 设置第m个工作树Tm的模糊度sm，该模糊度用于决定链路Tm参与博弈水平为0或者1，当第m个工作树Tm的模糊度sm为0时，表示第m个工作树Tm不参与博弈；为1时，表示第m个工作树Tm参与博弈。

[0073] SN(ShareNumber)为网络中链路eij的共享总数，其值为链路eij上可同时运行的请求个数，分别定义SNintra和SNinter为域内和域间链路的共享总数。共享总数决定了网络上的链路业务共享能力，如果共享能力过小，一定程度上链路资源得不到充分的利用，失去了共享的意义；如果共享能力过大，网络资源利用率提高，但是随之而来是故障的概率越来越高、影响的范围越来越大，而且由于域间链路相对较少，较大的负载压力施加在域间链路上，易造成阻塞率和时间延迟的大幅增加。

[0074] 步骤5、判断m＜k是否成立，若成立，令m＝m+1后，执行步骤2；否则结束。

[0075] 经过以上步骤，当对所述的组播请求都处理后，获得了当前多域光网络的工作树集合以及保护树集合。

[0076] 实施例二

[0077] 在本实施例中以三个单位为自治域，图2为多域光网络G＝(39,72)，聚合后的拓扑图如图3所示。假定四个动态的临时性电视会议安排R1＝{3；7,10,16,18,27}，R2＝{5；10,12,19,24,37}，R3＝{10；12,16,27}，R4＝{30；9,31,36}，此次安排事先不确定会议的开始与结束时间，要求在会议期间基本保证会议通话质量，出现故障后能迅速恢复。首先根据在两个虚平面上分别生成组播请求R1的组播工作树和组播保护树。由于此时是第一个组播请求，直接由各域cPCE结合域内拓扑计算路径。生成的组播工作树和组播保护树如4所示，其中虚线(3-8-10-9-7,3-8-10-9-27，3-8-10-9-13-17-16，3-8-10-9-13-17-18)代表组播请求R1的组播工作树T1，较粗实线(3-4-5-7-39-27,3-10-11-1-12-16-21-18)代表代表组播请求R1的组播保护树P1。当组播请求R2到达网络时，计算工作树T2和组播保护树P2，然后T2和T1进行模糊博弈，P2和P1也进行模糊博弈，确定与T1(P1)结成的联盟。由图5可以看出，利用本发明提供的方法第2个组播请求R2所得组播工作树T2以及组播保护树P2与第一个组播请求R1的组播工作树T1以及组播保护树P1存在路径共享，其中点划线(5-8-10-9-27-37，5-8-10-
9-13-12，5-8-10-9-13-17-19，5-8-10-9-13-17-16-15-24)为第2组组播的组播工作树T2，灰度较浅的实线路径(5-7-39-38-37，5-4-3-10-11-1-12-16-21-18-19，5-4-3-10-11-1-
12-16-21-23-24)为第2组组播请求的组播保护树P2。当第3个组播请求R3到达时，假定此时第1个组播请求R1尚未结束，则获得的第三个组播请求的工作树T3以及保护树P3与组播工作树T2以及组播保护树P2与第一个组播请求R1的组播工作树T1以及组播保护树P1进行模糊博弈，最终确定第3个组播请求R3的T3(P3)参与水平从而优化第三个组播请求R3的T3和P3。上述方法实例说明FGDMS方法能够在基于分层PCE架构的多域光网络环境中，可为临时性的电视会议安排以及日常业务工作提供高效的共享保护，由于不需要级别特别高的保护机制，FGDMS方法生成的共享保护方案既保证了组播业务较短的故障恢复时间，也不会消耗过多的资源。

[0078] 实施例三

[0079] 在本实施例中，首先对本发明提供的保护方法的有效性进行验证，图6为多域光网络系统发生故障瞬间光信号的光谱图，图7为发生故障后立即运行共享保护机制的光谱图，可以看出中心频率为192.95THz的光信号受到强烈的衰减影响，判定该信号在传输过程中发生故障，系统检测到故障之后迅速运行保护机制，切换光信号的传输路径至本发明提供的方法预先计算好的组播保护树上，快速恢复光信号的传输，从而发挥了保护机制的优势。

[0080] 在本实施例中，如图8所示是SSPP方法、CL-SSP方法和本发明提供的方法之间阻塞率的比较。可以明显看出随着组播请求数的增加，各方法的阻塞率都随之上升，而且SSPP方法和CL-SSP方法上升的速度比本发明提供的方法更快。当组播请求数超过一定的规模时，各方法的阻塞率都明显上升，这是由于请求数逐渐大于网络同时处理的最大规模，所以阻塞率开始上升。其中，SSPP方法的备用段只能用来传输备份业务，而CL-SSP方法采用了自我共享和交叉共享的方法，没有业务的工作段也可用来传输备份业务，所以CL-SSP方法的阻塞率整体低于SSPP方法。但是，本发明提供的方法能够结合之前未释放的组播业务，动态地规划好各组播请求的组播工作树和保护树，及时释放到期请求的链路资源，而且工作树之间和保护树之间分别可以共享链路资源，能够将阻塞率降到最低。

[0081] 因此，根据分析及实验结果表明，本发明提供的方法的时间复杂度较低，在一定数量的动态组播请求范围内，降低了动态组播业务的阻塞率，提高了光网络资源的利用率。