一种基于混合群智能的多域光网络组播路由恢复方法

摘要

本发明公开了一种基于混合群智能的多域光网络组播路由恢复方法，当多域光网络组播路由的源节点与目的节点之间的路径发生故障时，采用以下步骤获得恢复路径：首先判断发生故障的路径的位置，若路径为域内路径，利用人工鱼群算法在域内进行路径搜索，在路径搜索中，采用非合作博弈的方法确定节点处人工鱼的下一步前进方向；获得域内恢复路径和域内最优节点；若路径为域间路径，融合人工鱼模型和博弈论方法获得每个域域内恢复路径和域内最优节点，将所有的域内最优节点上传至一个虚拟的优化层中，再对该优化层中的节点进行路径搜索；最终得到域间恢复路径。本发明运用群智能方法，区分了域间和域内故障不同情况，得到的光网络结构更优化，整体光网络对于故障的感知性更强，提高了网络的生存性。

权利要求

1.一种基于混合群智能的多域光网络组播路由恢复方法，其特征在于，当多域光网络组播路由的源节点与目的节点之间的路径发生故障时，采用以下步骤获得恢复路径：步骤1，判断发生故障的路径的位置，若路径为域内路径，执行步骤2；若路径为域间路径，执行步骤3；

步骤2，利用人工鱼群算法计算当前节点人工鱼的毒素浓度值，采用非合作博弈的方法确定当前节点的人工鱼下一步选择的行为，执行人工鱼选择的行为，得到新节点；所述的当前节点为源节点或新节点；

所述毒素浓度值表示节点处的故障率数值；

重复步骤2的上述过程，直至到达目的节点；比较各节点的毒素浓度值，将毒素浓度值最小的节点作为最优节点，各节点连接形成的路径形成域内恢复路径；

步骤3，利用步骤2的方法获得每个域的域内恢复路径和域内最优节点，所有的域内最优节点形成最优节点集，采用果蝇优化方法对最优节点集中的节点进行路径搜索，最终得到域间恢复路径。

2.如权利要求1所述的基于混合群智能的多域光网络组播路由恢复方法，其特征在于，所述的步骤2具体包括以下步骤：

步骤2.1，在源节点处放置人工鱼，形成初始鱼群，初始化初始鱼群；

步骤2.2，计算初始鱼群各人工鱼当前节点的毒素浓度值；比较毒素浓度值大小，将最小值浓度值和最小值浓度值的人工鱼的状态赋值给公告板；

步骤2.3，利用公式(1)计算当前节点或步骤2.5更新后节点每条人工鱼的效用函数U，选择效用函数Ui值较小的行为作为该条人工鱼所对应的下一步行为；

U＝{U1,U2,…Ui,…,Un} (1)Ui＝αD+βNf+γ·σ (2)式中，Ui表示当前节点该条人工鱼的第i种行为对应的效用函数，n为该条人工鱼对应的行为的个数，D为当前节点误码率，Nf为当前视野范围内人工鱼的数目，σ为该条人工鱼的拥挤因子，α、β、γ为控制变量，0≤α≤1，0≤β≤1，α+β＝1，γ取当前节点的毒素浓度值；

步骤2.4，执行人工鱼选择的行为，更新人工鱼的当前位置信息，得到更新后的节点；

步骤2.5，计算更新后节点各人工鱼的毒素浓度值；比较自身的毒素浓度值与公告板上的毒素浓度值，若自身的毒素浓度值小于公告板上的毒素浓度值，用自身的毒素浓度值及状态更新公告板上的毒素浓度值和状态，否则，公告板状态不变；

步骤2.6，重复步骤2.3至步骤2.5，直至达到目的节点；得到毒素浓度值最小的节点，将毒素浓度值最小的节点作为最优节点，各节点连接形成的路径形成域内恢复路径。

3.如权利要求1所述的基于混合群智能的多域光网络组播路由恢复方法，其特征在于，还包括步骤4：判断步骤2或步骤3获得的恢复路径中的最短路径的数量，若存在一条最短路径，将其作为恢复路径，输出；若存在两条及以上最短路径，选择节点数较少的路径作为恢复路径，输出；若节点数较少的路径多于一条，这些路径均可作为恢复路径，输出任意一条。

说明书

一种基于混合群智能的多域光网络组播路由恢复方法

技术领域

[0001] 本发明属于组播路由恢复技术领域，涉及一种基于混合群智能的多域光网络组播路由恢复方法。

背景技术

[0002] 随着光网络向着高速、透明的方向不断发展，光网络规模的不断增大，具有多层、多域特征的智能光网络开始被广泛使用，其生存性越来越引起重视。由于攻击在透明光网
络中具有扩散传播的特性，光网络受到的攻击会沿着光路的传输不断加深和积累，使得光
信号的质量急剧下降，造成光网络中信号误码率的升高和故障的发生。光网络的生存性机
制可以分为保护和恢复，其中恢复机制是在发生故障后利用路由搜索，快速建立起新的恢
复路径，达到光网络畅通的目的，恢复机制相较于保护机制，不需要网络预留冗余的资源，
对于保证分支网络的生存性具有重要的意义。

[0003] 目前，国内外学者对于光网络的恢复研究主要集中于单域智能光网络和多域智能光网络的单播路由中，这些方法不能直接运用于基于分布式PCE的多域光网络中。公开号为
CN110086710A的专利公开了一种基n人非合作博弈的多域光网络组播路由恢复方法，运用
基于n人非合作博弈，该方法中只考虑了每个节点自身对路由的选择，忽略了网络的整体恢
复性能。

发明内容

[0004] 为解决现有技术中存在的不足，本发明提供了一种基于混合群智能的多域光网络组播路由恢复方法，解决现有的恢复方法存在的恢复时间较长、故障感知性弱的问题。

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

[0006] 一种基于混合群智能的多域光网络组播路由恢复方法，其特征在于，当多域光网络组播路由的源节点与目的节点之间的路径发生故障时，采用以下步骤获得恢复路径：

[0007] 步骤1，判断发生故障的路径的位置，若路径为域内路径，执行步骤2；若路径为域间路径，执行步骤3；

[0008] 步骤2，利用人工鱼群算法计算当前节点的人工鱼的毒素浓度值，采用非合作博弈的方法确定当前节点的人工鱼下一步选择的行为，执行人工鱼选择的行为，得到新节点；所
述的当前节点为源节点或新节点；

[0009] 重复步骤2的上述过程，直至到达目的节点；比较各节点的毒素浓度值，将毒素浓度值最小的节点作为最优节点，各节点连接形成的路径形成域内恢复路径；

[0010] 步骤3，利用步骤2的方法获得每个域的域内恢复路径和域内最优节点，所有的域内最优节点形成最优节点集，再对最优节点集中的节点进行路径搜索，最终得到域间恢复
路径。

[0011] 优选的，所述的步骤2具体包括以下步骤：

[0012] 步骤2.1，在源节点处放置人工鱼，形成初始鱼群，初始化初始鱼群；

[0013] 步骤2.2，计算初始鱼群各人工鱼当前节点的毒素浓度值；比较毒素浓度值大小，将最小值浓度值和最小值浓度值的人工鱼的状态赋值给公告板；

[0014] 步骤2.3，利用公式(1)计算当前节点或步骤2.5更新后节点每条人工鱼的效用函数U，选择效用函数Ui值较小的行为作为该条人工鱼所对应的下一步行为；

[0015] U＝{U1,U2,…Ui,…,Un}(1)

[0016] Ui＝αD+βNf+γ·σ  (2)

[0017] 式中，Ui表示当前节点该条人工鱼的第i种行为对应的效用函数，n为该条人工鱼对应的行为的个数，D为当前节点误码率，Nf为当前视野范围内人工鱼的数目，σ为该条人工
鱼的拥挤因子，α、β、γ为控制变量，0≤α≤1，0≤β≤1，α+β＝1，γ取当前节点的毒素浓度
值；

[0018] 步骤2.4，执行人工鱼选择的行为，更新人工鱼的当前位置信息，得到更新后的节点；

[0019] 步骤2.5，计算更新后节点各人工鱼的毒素浓度值；比较自身的毒素浓度值与公告板上的毒素浓度值，若自身的毒素浓度值小于公告板上的毒素浓度值，用自身的毒素浓度
值及状态更新公告板上的毒素浓度值和状态，否则，公告板状态不变；

[0020] 步骤2.6，重复步骤2.3至步骤2.5，直至达到目的节点；得到毒素浓度值最小的节点，将毒素浓度值最小的节点作为最优节点，人工鱼所选择的节点连接形成的路径形成域
内恢复路径。

[0021] 优选的，所述的步骤3中采用果蝇优化方法对优化层中的节点进行路径搜索。

[0022] 进一步的，还包括步骤4：判断步骤2或步骤3获得的恢复路径中的最短路径的数量，若存在一条最短路径，将其作为恢复路径，输出；若存在两条及以上最短路径，选择节点
数较少的路径作为恢复路径，输出；若节点数较少的路径多于一条，这些路径均可作为恢复
路径，输出任意一条。

[0023] 与现有技术相比，本发明的有益效果是：

[0024] 本发明方法通过群智能的寻优方法，优化了域间及域内路径的选择，能够迅速生成更为可靠的恢复路径。实验结果及分析表明，本发明方法具有良好的收敛速度，恢复时间
更短，降低了在恶意节点下的阻塞率。整体光网络对于故障的感知性更强，提高了网络的生
存性。

附图说明

[0025] 图1是本发明方法的流程图。

[0026] 图2是本发明实施例1和实施例2记载的多域光网络结构。

[0027] 图3是本发明实施例1和实施例2记载的组播工作树。

[0028] 图4是本发明实施例1中域内搜索实搜索方向示意。

[0029] 图5是本发明实施例1最终获得的域内恢复路径。

[0030] 图6是本发明实施例2中三个域在优化层中的节点信息。

[0031] 图7是本发明实施例2最终获得的域间恢复路径。

[0032] 图8是仿真实验中脚本生成器NSG2生成的单个域的网络拓扑结构。

[0033] 图9是分布式多域光网络的网络拓扑结构。

[0034] 图10是本发明方法和其他现有的两种方法的收敛性比较。

[0035] 图11是本发明方法和其他现有的两种方法的恢复时间比较。

[0036] 图12是本发明方法和其他现有的两种方法在恶意节点环境下的阻塞率。

具体实施方式

[0037] 多域光网络由多个域组成，每个域是一个独立的路由和恢复区域，如不同的运营商将网络分为不同的区域管理和控制；

[0038] “域内路径”是指某个域域内路由选择的路径，选择经过那个网关或路由器；“域间路径”是指两个域之间的路径(如图3中的域1内的节点5与域2内的节点11之间的路径)。

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

[0040] 本发明基于分布式PCE网络结构，结合人工鱼群和果蝇优化方法，提出了一种基于混合群智能的多域光网络组播路由恢复方法，本方法主要适用于当多域光网络组播路由的
源节点与目的节点之间的路径发生故障时，多域光网络的链路进行恢复。

[0041] 本发明方法具体包括以下步骤：

[0042] 步骤1，判断发生故障的路径的位置，若路径为域内路径，执行步骤2；若路径为域间路径，执行步骤3；

[0043] 步骤2，融合人工鱼模型和博弈论的方法对域内路径进行恢复，具体思路为：利用人工鱼群算法在域内进行路径寻优搜索，在路径寻优中，采用非合作博弈的方法确定节点
处人工鱼的下一步前进方向；最后获得域内恢复路径以及域内最优节点。

[0044] 人工鱼群方法是根据水域中食物浓度在水中扩散的原理，人工鱼从食物浓度低的源节点寻找前往食物浓度高的目的节点时进行的一系列行为，本发明对其基本模型进行改
进，将人工鱼觅食转换为人工鱼躲避行为，其行为与觅食类似；同时本发明将非合作博弈与
人工鱼群行为选择进行融合，改进后的博弈人工鱼能够更好地体现光网络多域的特性。

[0045] 优选的，本发明步骤2包括以下步骤：

[0046] 步骤2.1，在源节点处放置M条人工鱼，形成初始鱼群，设置人工鱼的初始位置，人工鱼的视野范围visual，人工鱼的步长step，拥挤因子σ；初始化初始鱼群；

[0047] 步骤2.2，计算初始鱼群各人工鱼当前位置的毒素浓度值，并比较大小，取毒素浓度值最小者进入公告板，将最小值浓度值和最小值浓度值对应的此条人工鱼的状态赋值给
公告板；本发明的多域光网络中，毒素值相当于不同节点处的故障率大小。毒素浓度值最小
的节点作为最优节点。

[0048] 步骤2.3，对每条人工鱼进行评价，对其要执行的行为选择进行博弈，每条人工鱼的行为包括躲避行为，聚群行为，追尾行为，吞食行为，跳跃行为，随机行为等。具体的博弈
方法为：利用公式(1)计算当前节点或步骤2.5更新后节点每条人工鱼的效用函数U，选择效
用函数Ui值较小的行为作为该条人工鱼所对应的下一步行为；

[0049] U＝{U1,U2,…Ui,…,Un}   (1)

[0050] Ui＝αD+βNf+γ·σ  (2)

[0051] 式中，Ui表示当前节点该条人工鱼的第i种行为对应的效用函数，n为该条人工鱼对应的行为的个数，D为当前节点误码率，即D＝Nerror/Nall，Nall表示传输的二进制数据总数
的位数，Nerror表示传输的二级制数据总数中出错的位数；Nf为当前视野范围内人工鱼的数
目，σ为当前节点该条人工鱼的拥挤因子，α、β、γ为控制变量，0≤α≤1，0≤β≤1，α+β＝1，γ
＝yi，yi为当前节点的毒素浓度值。

[0052] 并对下一步行为进行拥挤因子评估，选择拥挤因子低的方向。

[0053] 步骤2.4，执行人工鱼选择的行为，更新人工鱼的当前位置信息，得到更新后的节点；本发明优选的基于全局信息和局部信息来更新人工鱼的当前位置信息。

[0054] 步骤2.5，计算更新后节点各人工鱼的毒素浓度值；比较自身的毒素浓度值与公告板上的毒素浓度值，若自身的毒素浓度值小于公告板上的毒素浓度值，用自身的毒素浓度
值及状态更新公告板上的毒素浓度值和状态，否则，公告板状态不变；

[0055] 步骤2.6，重复步骤2.3至步骤2.5，直至找到目的节点，获得域内恢复路径和域内最优节点。

[0056] 基于本发明的分布式PCE网络结构，源节点向本域PCE发送故障消息，PCE启动恢复进程，PCE向节点目的节点发送本地重路由指令。

[0057] 步骤3，首先利用步骤2的方法获得每个域的域内恢复路径和域内最优节点，域内最优节点即毒素浓度值最小的节点。本发明将每个域抽象为一个节点，也就是域内的最优
节点，这些最优节点形成一个最优节点集，如图6所示，类似于一个优化层。然后基于该最优
节点集，采用果蝇优化方法获得最优节点集中节点的恢复路径，最后得到域间恢复路径。例
如实施例2中的节点5、节点7和节点15为三个域中的最优节点，将其作为优化层中的节点，
再对该优化层中的节点进行路径搜索，最后得到所有的域间恢复路径。

[0058] 其中，采用果蝇优化方法获得各个域之间的域间恢复路径的过程包括：

[0059] 步骤3.1，已知源节点和目的节点，它们分别属于其中两个域，假定此多域光网络存在n个域。在源节点所在域内形成初始果蝇种群。确定初始果蝇种群的规模K，记最大迭代
次数为T，并对果蝇种群的初始位置进行初始化。

[0060] 步骤3.2，T的初始值为0，计算规则为：T＝T+1；迭代过程中果蝇个体在嗅觉觅食阶段的搜索方向为随机数rand()，搜索距离为RV。

[0061] 步骤3.3，计算每个果蝇的气味浓度值，具体的气味浓度值的计算可参考“果蝇优化算法及其应用研究，霍慧慧，太原理工大学，2015”。然后找出气味浓度值最低的果蝇个
体，作为最优果蝇个体；

[0062] 步骤3.4，记录气味浓度最低值和此时最优果蝇个体的位置，整个果蝇种群利用贪婪选择策略进行视觉选择，飞往最优果蝇个体的位置；

[0063] 步骤3.5，判断迭代次数是否等于T，若迭代次数小于T，重复步骤3.2至步骤3.3，并判断此时的最低气味浓度值是否优于前一次迭代的最低气味浓度值，若是，执行步骤3.4，
若否则继续重复步骤3.2至步骤3.3，循环该过程，直至达到迭代次数T。

[0064] 在获得恢复路径后，可能存在多条域内恢复路径或域间恢复路径，此时，对于多条恢复路径，执行以下步骤：

[0065] 步骤4，判断域内恢复路径集或域间恢复路径集中的最短路径的数量，若域内恢复路径集或域间恢复路径集中存在一条最短路径，将其作为恢复路径，输出；若存在两条及以
上最短路径，选择节点数较少的路径作为恢复路径，输出；若节点数较少的路径多于一条，
则这些路径均可作为恢复路径，输出任意一条。如图1所示为本发明方法的流程图。

[0066] 基于本发明的分布式PCE网络结构，源节点向本域PCE发送故障消息，PCE启动恢复进程，PCE向目的节点发送本地重路由指令。目的节点向本域PCE发送故障消息，该PCE通过
泛洪机制找到源节点所在域的PCE，发送重路由指令。

[0067] 以下给出本发明的域内恢复和域间恢复的具体实施例，需要说明的是，本发明并不局限于以下具体实施例，凡在本申请技术方案基础上做的等同变换均落入本发明的保护
范围。

[0068] 实施例1

[0069] 本实施例中给定如图2所示的多域光网络，假定该多域光网络存在三个不同的域，给定临时组播请求R＝{2；5,7,11,12,13,16,17,19}，在需要迅速恢复组播的情况下，设计
相关方案保证发生故障后能在一定时间内寻找出最优恢复路径，保证业务的畅通。图3为组
播工作树：路径2‑5‑11‑17‑16，2‑5‑11‑17‑19，2‑5‑11‑7‑13，2‑5‑11‑7‑12。本实施例假定节
点2至节点5的链路故障(即域内故障)。

[0070] 根据本发明步骤2的方法在域内进行搜索，搜索方向如图4所示，节点5作为目的节点，在源节点2处放置M条人工鱼进行路径寻优，除了其上游节点1，共有3个方向可以进行搜
索，图中虚线箭头表示，即链路2‑3，2‑4，2‑6。对该三个方向进行非合作博弈从而确定人工
鱼下一步前进的方向，然后从三个节点继续进行博弈选择路径。图5为最终搜索选择路径，
即路径2‑6‑5。

[0071] 实施例2

[0072] 本实施例同样给定如图2所示多域光网络，同样给定临时组播请求R＝{2；5,7,11,12,13,16,17,19}，图3为组播工作树，即路径2‑5‑11‑17‑16，2‑5‑11‑17‑19，2‑5‑11‑7‑13，
2‑5‑11‑7‑12。假定节点5至节点11发生故障(域间故障)。

[0073] 为构建可靠的域间恢复链路，并减小下一次遭受攻击的影响，根据本发明步骤3的方法在域内进行搜索：首先分别在三个域内进行域内人工鱼寻优，找出各个域(即类觅食
层)中最优路径信息上传至优化层，如图6三个域中最优为将每个域抽象成一个节点之后得
到的优化层，故障率(毒素浓度)最低的三个点5、7、15代表所在域在优化层中的节点信息。
确认源节点和目的节点后调用果蝇优化方法，首先找到目的节点11所在域，随后快速找出
节点5、7之间最短优化路径，图7为最终的恢复路径，从而做到恢复业务和优化传输。

[0074] 仿真实验

[0075] 实验设置：

[0076] 本发明通过NS‑2仿真平台，以课题组开发设计的光网络仿真系统SRSP‑NA为基础，选择文献“基于量子粒子群优化CS算法的QoS组播路由模型，符保龙，柳州职业技术学院学
报,2019,19(05):113‑116”的QPSO‑CS方法和文献“基于改进离散萤火虫算法的QoS组播路
由优化，周志平，杭州电子科技大学，2019”的BRDFA方法两种组播路由方法作为比较对象，
编写这三种方法的相关模块，图8脚本生成器NSG2生成的单个域的网络拓扑结构，图9为分
布式多域光网络的网络拓扑结构。

[0077] 实验结果和分析：

[0078] 首先，对基于本发明方法(MIAMR)的多域光网络在发生故障前后的性能变化来验证方法的有效性。随后，为比较不同方法对在组播恢复中的性能以及恢复后对光网络生存
性的影响，选用QPSO‑CS方法和BRDFA方法进行对比分析。这两种方法都融入了不同的群智
能方法对方法进行改进，是目前解决组播路由问题较有效的方法。其中QPSO‑CS方法充分结
合了QPSO方法和CS方法的优点，增加了量子粒子群方法后期的收敛性；BRDFA方法中采用的
改进萤火虫方法，具有较少参数、操作简单，在寻优过程中能够降低误差。

[0079] (1)方法的收敛性比较

[0080] 在域的数量为7，网络负载为80Erl，恶意节点的比例为5％的情况下，得到如图10的三种方法的收敛性比较。实验结果表明，QPSO‑CS方法开始时收敛速度较快，但后面迅速
放缓，说明其较易陷入局部最优；BRDFA方法引入了萤火虫扰动机制，不易陷入局部最优，但
整体收敛速度较慢。相比较而言，MIAMR方法在不同的迭代次数下，收敛性都好于QPSO‑CS方
法和BRDFA方法。

[0081] (2)不同方法恢复时间比较

[0082] 在域的数量为7，网络负载为80Erl，恶意节点的比例为5％的情况下，如图11，三种改进后的路由恢复方法在恢复时间上都具有较大优势，特别是迭代次数较少的时候相比较
而言差别不是很明显；而随着迭代次数的增加，达到30以上时，相较于QPSO‑CS方法和BRDFA
方法，MIAMR方法需要的恢复时间较少，说明其在路由恢复过程中更加迅速。

[0083] (3)恶意节点环境下的阻塞率

[0084] 在域的数量为7，网络负载为80Erl，恶意节点的比例为在5％～40％之间变化的情况下，观察不同恶意节点比例下的阻塞率情况，结果如图12所示，随着恶意节点比例的上
升，QPSO‑CS方法和BRDFA方法阻塞率急剧上升，这已经超过了网络的容忍度，会造成网络的
拥堵，影响信息的传输；而MIAMR方法在恶意节点较多的情况下，阻塞率上升较慢，网络依旧
可以维持良好的性能，这说明MIAMR方法能够更好的适应恶意节点比例高的情况。

[0085] 可以看出，本发明方法通过群智能的寻优方法，优化了域间及域内路径的选择，能够迅速生成更为可靠的恢复路径。实验结果及分析表明，本发明方法具有良好的收敛速度，
与QPSO‑CS方法和BRDFA方法相比恢复时间更短，降低了在恶意节点下的阻塞率。