一种基于序贯博弈的多域光网络组播保护方法

摘要

本发明提供了一种基于序贯博弈的多域光网络组播保护方法，该方法当多域光网络中到达第k个组播请求时，该请求与未释放的组播请求形成的组播树进行序贯博弈，下一阶段再与得到的新的组播树进行博弈，通过计算效益函数，最终得到使得光网络链路结构最合理、效益最高的纳什均衡，有效分配链路资源给组播工作树和保护树，使共享保护效益最大化。本发明中的SGDMS方法相较于经典的SSPP方法和具有混合拓扑的HTASP方法，所需成本和资源更少，在不同组播请求下的相应阻塞率有明显降低，大大减少了多域光网络所需的成本，有效提高了网络的生存性能。

说明书

技术领域

本发明属于光网络领域，涉及多域光网络组播保护，具体涉及一种基于序贯博弈的多域光网络组播保护方法。

背景技术

随着光网络规模的不断扩大和结构的日益复杂，多样性业务需求对光网络的生存性提出了进一步的要求。多域光网络的组播是一种光网络中点到多点、多点到多点之间的业务传输方法。组播业务可分为静态组播和动态组播，静态组播的保护是在预先得知多域光网络全局状态的情况下，预先进行保护链路的设计或保护方案的制订；动态组播的保护往往是针对临时到达的组播请求，对于实时性要求更高，更对光网络存续期间的生存性提出了一定的要求。随着光网络中动态业务的不断增加，业务复杂性和实时性的增强，动态组播的需求也不断增长，对于多层多域光网络动态组播的保护也已成为研究和提高光网络生存性的重要课题。

目前，针对光网络在组播保护方面的问题，国内外研究人员也有一定的研究和进展。

现有技术中提出了P圈保护机制，可以通过预先设置环形通道，实现对光网络的快速保护。现有技术中提出了在考虑域间输出策略的基础上，提出了一种多域光网络中基于路径计算单元的分段共享保护方法，相比传统的基于路径计算单元的多域分段保护方法，该方法阻塞率低，平均保护切换时间短。现有技术中还提出了为了克服多域光网络中的可扩展性约束，结合全连通和生成树拓扑聚合的优点，折中了光网络需要存储和发布的链路状态信息与聚合信息与实际物理拓扑的精确性，提出一种基于查询机制的多域分段保护方法，具有良好的可扩展性。这几种新型保护方法相较于传统的基于路径计算单元光网络组播保护方法，已经有所改善，一定程度上降低了光网络的阻塞率。但对于PCE架构下，多层多域光网络较为复杂的结构和动态组播请求下，还没有有效的动态组播保护方法。

发明内容

针对现有技术存在的不足，本发明的目的在于，提供一种基于序贯博弈的多域光网络组播保护方法，以解决现有技术中多域光网络的生存性能不佳的技术问题。

为了解决上述技术问题，本发明采用如下技术方案予以实现：

一种基于序贯博弈的多域光网络组播保护方法，该方法当多域光网络中到达第k个组播请求时，该请求与未释放的组播请求形成的组播树进行序贯博弈，下一阶段再与得到的新的组播树进行博弈，通过计算效益函数，最终得到使得光网络链路结构最合理、效益最高的纳什均衡，有效分配链路资源给组播工作树和保护树，使共享保护效益最大化。

具体的，该方法按照以下步骤进行：

步骤1，给定多域光网络G(V,E)，对于光网络中一组随机到达的组播请求R＝{R

其中：

V为多层多域光网络中所有节点的集合；

E为光网络中所有物理链路的集合；

m为请求的个数；

步骤2，初始化多域光网络G(V,E)并进行拓扑聚合，定义组播工作请求和组播保护请求分别处于两个具有相同的分层PCE结构的虚平面D

步骤3，初始化虚平面D

步骤4，在虚平面D

步骤5，在虚平面D

步骤6，对于τ＝0的组播请求，释放其链路资源并初始化虚平面链路权值w；判断k

步骤7，输出T，P。

具体的，所述的LMPH方法的步骤如下：

步骤401，输入多重着色图G

其中：

V

D为所有目的节点的集合；

r为组播请求的集合；

s为源节点；

Δ

Δ

步骤402，调用MCCP-CMM方法，计算V

其中：

P(s,u)为s至u节点的能量；

P(u,v)为u至v节点的能量；

P

步骤403，对于i∈(1,K)，调用MCCP-CMM方法，计算V

步骤404，将p(u,v)加入组播树T，且将v从D中删除，按照更新规则式，更新多重着色图G

步骤405，方法结束，输出满足时延和能量约束的低成本组播树T。

本发明与现有技术相比，具有如下技术效果：

(Ⅰ)本申请中的SGDMS方法相较于经典的SSPP方法和具有混合拓扑的HTASP方法，所需成本和资源更少，在不同组播请求下的相应阻塞率有明显降低，大大减少了多域光网络所需的成本，有效提高了网络的生存性能。

(Ⅱ)采用序贯博弈的方法，将序贯博弈的优势发挥到多域光网络组播业务中，组播工作树和组播保护树根据上次博弈结果不断调整整体组播树结构，逐渐形成一种均衡局面，使得光网络整体资源负载和结构最终趋向于一个稳定值。

(Ⅲ)本申请采用共享保护的多网络保护方式，这种保护方式在一定程度上减少了链路资源的占用，使得光网络链路的冗余减小，大大解决了动态组播业务繁忙的情况下。

(Ⅳ)采用共享保护的多网络保护方式，结合序贯博弈的方法，最后得到的SGDMS方法生成的共享保护方案既可以保证组播业务较短的故障恢复时间，也不会消耗过多的资源。

附图说明

图1(a)为多域光网络G的示意图。

图1(b)为多域光网络拓扑结构的示意图。

图1(c)为组播请求R1的示意图。

图1(d)为组播请求R2的示意图。

图1(e)为组播请求R3的示意图。

图1(f)为组播请求R4的示意图。

图2为域1的结构示意图。

图3(a)为光发射模块TxLaserArray示意图。

图3(b)为发射模块的内部结构示意图。

图4为分光器模块Fork示意图。

图5(a)为发生故障瞬间的光谱图。

图5(b)为运行保护机制后的光谱图。

图6为方法成本比较图。

图7为方法资源利用比较图。

图8为方法阻塞率比较图。

以下结合实施例对本发明的具体内容作进一步详细解释说明。

具体实施方式

问题描述：

序贯博弈是动态博弈的一种，每次博弈使用上一阶段博弈的结果作为博弈的条件，从而产生了不同于上一次博弈的纳什均衡。序贯博弈采用序贯理性假设，即不论之前的阶段发生了什么，局中人都应该在博弈的每一个时间点上最优化自己的决策。在多域光网络的组播业务中，组播工作树和组播保护树根据上次博弈结果不断调整整体组播树结构，逐渐形成一种均衡局面，使得光网络整体资源负载和结构最终趋向于一个稳定值。

定义1：定义多域光网络拓扑结构为G(V,E)，其中V是多层多域光网络中所有节点的集合，V＝{V

定义2：定义序贯博弈模型G，G由G

定义3：定义序贯博弈的序列空间S＝S

实现概率

定义

其中cost为多域光网络光纤链路的成本；delay为路径的时延；ber代表链路的阻塞率；同时，用w代表链路上权值大小。

定义4：定义多域光网络中共享链路e

F(N)→maxF(N)

delay

ber

Num≤7,γ<1

本发明的技术思路：

多域光网络的保护方式可分为专用保护和共享保护，其中共享保护在一定程度上减少了链路资源的占用，使得光网络链路的冗余减小，更适用于动态组播业务繁忙的情况下。在分层PCE结构的多域光网络中，结合序贯博弈的方法，对到达的动态组播业务进行共享保护树的优化，提出了一种基于序贯博弈的多域光网络动态组播保护方法，称为SGDMS(SequentialGame based Dynamic Multicast Shared protection)方法，使光网络的链路资源的到更为合理的分配，达到对整个光网络组播业务的有效保护。

随着光网络的进一步扩大化和复杂化，对于多域光网络组播的研究进一步深入，如何提高网络的生存性，有效保护多域光网络的链路，已经成为该领域的研究热点。针对分层PCE架构下的多域光网络，结合序贯博弈模型，提出了一种基于序贯博弈的多域光网络组播保护方法。通过VPI仿真平台进行相关实验，结果表明，该方法所需成本和资源较少，在不同组播请求下的相应阻塞率有明显降低，有效提高了网络的生存性能。

本文针对多层多域光网络动态组播的保护问题，在分层PCE架构下，结合序贯博弈模型，提出了一种基于序贯博弈的多域光网络组播保护方法，该方法结合序贯博弈模型，有效提高利率多域光网络的生存性能。

本发明的技术方法：

本发明给出一种基于序贯博弈的多域光网络组播保护方法，该方法按照以下步骤进行：

步骤1，给定多域光网络G(V,E)，对于光网络中一组随机到达的组播请求R＝{R

其中：

V为多层多域光网络中所有节点的集合；

E为光网络中所有物理链路的集合；

m为请求的个数；

步骤2，初始化多域光网络G(V,E)并进行拓扑聚合，定义组播工作请求和组播保护请求分别处于两个具有相同的分层PCE结构的虚平面D

步骤3，初始化虚平面D

步骤4，在虚平面D

步骤5，在虚平面D

步骤6，对于τ＝0的组播请求，释放其链路资源并初始化虚平面链路权值w；判断k

步骤7，输出T，P。

具体的，所述的LMPH方法的步骤如下：

步骤401，输入多重着色图G

其中：

V

D为所有目的节点的集合；

r为组播请求的集合；

s为源节点；

Δ

Δ

步骤402，调用MCCP-CMM方法，计算V

其中：

P(s,u)为s至u节点的能量；

P(u,v)为u至v节点的能量；

P

步骤403，对于i∈(1,K)，调用MCCP-CMM方法，计算V

步骤404，将p(u,v)加入组播树T，且将v从D中删除，按照更新规则式，更新多重着色图G

步骤405，方法结束，输出满足时延和能量约束的低成本组播树T。

本发明针对分层PCE架构下的多域光网络，深入分析其保护机制在动态组播业务条件下的作用，以及面对复杂组播业务的架构和生存性需求，结合序贯博弈模型提出了一种基于序贯博弈的多域光网络组播保护方法(SGDMS方法)，最终生成了分层PCE架构下有效的组播业务树和保护树。通过VPI仿真平台进行相关实验，结果表明，该方法相较于经典的SSPP方法和具有混合拓扑的HTASP方法，所需成本和资源更少，在不同组播请求下的相应阻塞率有明显降低，大大减少了多域光网络所需的成本，有效提高了网络的生存性能。

需要说明的是，本发明中的PCE指的是Path Computation Element，即路径计算单元。

需要说明的是，本发明中的LMPH方法的全称为Low-costMulti-constrainedPathHeuristic方法，即多条件约束的低成本组播树方法。

需要说明的是，本发明中MCCP-CMM方法指的是Minimal Comprehensive CostPath based on Colored Multigraph Model，即基于多重着色图的最小综合成本路径算法。

遵从上述技术方案，以下给出本发明的具体实施例，需要说明的是本发明并不局限于以下具体实施例，凡在本申请技术方案基础上做的等同变换均落入本发明的保护范围。

实施例：

遵从上述技术方案，本实施例给出一种基于序贯博弈的多域光网络组播保护方法，该方法在动态组播环境下，对提出的SGDMS方法所形成的多域光网络共享保护方案进行实例说明，以三个不同单位的通信网络为三个不同的自治域，图1(a)为多域光网络的结构G＝(36,69)，经过拓扑聚合后的结构图如图1(b)所示。假设三个单位之间进行临时视频会议安排，会议的开始与结束的时间不确定，R

仿真实验：

网络结构：

VPItransmission Maker光纤通信仿真软件(VPI)具备编译编程语言和进行各种系统的仿真的功能，仅依靠物理模块，就可以以灵活的方式帮助用户完成程序上的实现，快速搭建和修改系统，快速导入导出仿真数据，任意添加注释等。本章借助VPI平台设计了多域光网络系统，用以验证SGDMS方法的性能。在实验中选取经典的SSPP方法和HTASP方法作为比较方法。多域光网络VPI仿真系统由3个域13个节点构成。图2为域1的放大图，其他两个域内结构类似。域1内为节点1至节点5，域2内为节点6至节点9，域3内为节点10至节点13。在多域光网络的系统内，借助OXC的选路交换功能，能够让光复用信号通过OXC时，每一路信号都具备进行上下路的选择的机会，更有利于动态组播请求的处理。VPI平台中可通过联合仿真接口接入基于Matlab语言的程序方法，并以域内的光分插复用器模块作为cPCE，全局控制模拟pPCE功能。

参数设置：

具备了共享保护机制的多域光网络VPI系统的功能模块包括以下部分：TxLaserArray，FiberNLS，WDM_MUX_4，FiberBreak，Fork_2，NE_XC，NE_WDM_ADM，IntSource，AmpSysOpt，SignalAnalyzer。其主要的模块的功能如下：

图3(a)为光发射模块TxLaserArray，图3(b)为发射模块的内部结构。其主要功能是发射调制光信号，而且光信号的发射功率，中心频率、波长等参数是可调的，能够实现多波长的组播发射功能。

图4为分光器模块Fork。在多域光网络的链路中，分光器将一束光信号分成两束正交的相同光信号，并且可以通过添加衰减元件来改变分光比。

实验的主要参数如表1所示。

表1VPI参数设置

实验分析：

在仿真平台VPI上对SGDMS方法的各项性能进行比较分析，首先对SGDMS方法的有效性进行分析验证。选取经典的SSPP方法和HTASP方法[15]作为比较对象，对三种方法性能之间的差异进行比较，其中SSPP方法通过对组播树的分段，分别构建域内和域外的段保护链路；HTASP方法应用全连通和生成树混合的拓扑聚合构建虚拓扑上的虚拟链路，均对多域光网络的保护有一定作用。

第一，方法的有效性分析：

图5(a)为在某一时刻，在多域光网络的VPI系统中发生故障后的光谱图，图5(b)为发生故障后，系统立刻运行SGDMS方法后的光谱图，通过观察光信号的频谱在运行保护方法前后的的变化，可以发现，某一频率的光信号与其他差异较大，在传输过程中产生了剧烈的变化，即该频率的光信号的传输链路出现故障，检测出该故障后，系统运行SGDMS方法，将该光信号切换至保护链路上进行传输，由光谱图可以看出，切换为保护链路后，光信号可以顺利传输，验证了方法的有效性。

第二，不同方法成本比较：

图6为在叶节点数目在0至8之间变化情况下SGDMS方法、SSPP方法和HTASP方法之间的成本比较图。SSPP方法建立从发送端到接收端的路径及备用，成本较高。HTASP方法采用的链路拓扑聚合与节点数有关，当节点数较少时，采用全连通，成本相对较高；节点数超过4后采取生成树方法构建路径，成本增长变缓。SGDMS方法采取博弈的方法对组播树进行优化，同时及时释放τ为0的组播请求，相较于其他方法成本更低。

第三，不同方法资源利用需求比较：

图7为随着组播请求在10至50之间变化时，SGDMS方法、SSPP方法和HTASP方法对于资源的利用的变化趋势和比较情况。资源利用是各个方法运行后，所占用的工作树和保护树的总和，通过观察可以发现，随着组播请求数的不断增加，三种方法对资源的需求的总体趋势是随之逐渐上升的，达到一定水平后又趋于平缓。其中，SSPP方法上升的速度最快，SGDMS方法上升速度最慢，HTASP方法介于两者之间。由此可知，当组播请求数相同时，SSPP方法为每个段都保留了2个备份段，因此占用的资源量最多。HTASP方法由于采用混合拓扑的方法，所形成的链路数小于全连通方法，有效减少了资源的利用。SGDMS方法能够及时释放无用链路，并且结合序贯博弈理论对组播树和生成树的结构进行优化，得到符合纳什均衡的最优链路，因此占用资源最少。

第四，不同方法阻塞率比较：

图8为SGDMS方法、SSPP方法和HTASP方法的阻塞率之间，随着组播请求数量的变化而改变的比较。总体而言，可以发现随着组播请求数的不断增加，三种方法的阻塞率都呈上升趋势，这是由于随着组播请求的增多，逐渐超过网络同时处理组播请求的能力。同时，可以明显观察到，SSPP方法和HTASP方法的阻塞率增长速度要比SGDMS方法更快。SSPP方法主要是通过备份段传输备份业务，HTASP方法通过混合拓扑，能够产生较短的组播工作树和保护树，一定程度上减小了阻塞率；而SGDMS方法中结合序贯博弈，将未释放的业务加入博弈中某一阶段，动态地对组播工作树和保护树进行优化，探寻最优的满足均衡条件的结构，并且及时释放请求结束的链路资源，将阻塞率尽可能降低。