考虑电力通信网可靠性的业务路由优化分配方法

　　0引言

　　电力通信网是电力系统第2张实体网络，承担着电网公司生产调度、经营管理和企业信息化管理等业务需求。其安全可靠性直接影响电网的安全稳定运行。国内外学者在电力系统可靠性与通信网可靠性方面的研究取得了大量的成果。

　　目前电力通信网可靠性研究主要集中在通信网络拓扑优化和网络结构本身的可靠性等方面。文献提出了基于节点重要性的平衡度网络拓扑优化算法，文献提出考虑容量需求关系与光缆共享的光缆路由优化方法，文献提出了基于复杂网络理论的电力通信网脆弱性评估方法。这些文献都没有从业务层面对电力通信网的可靠性进行评估。

　　考虑到电力通信网络及电力通信业务日益发展，与电网之间的联系也更加紧密，文献指出研究电力通信网整体业务可靠性对于指导电力通信运行部门日常业务规划设计、网络运行方式优化调整等方面具有重要的意义，并提出了业务重要度、全网业务平均风险度和业务风险均衡度等可靠性评价指标，建立了基于全网业务风险均衡度的电力通信网可靠性的评估测度指标、评估模型及求解方法。该文献是在给定业务通道(路由)情况下展开研究的，没有研究提高业务可靠性的方法。以文献提出的业务风险评价指标为基础，研究业务路由的优化分配方法。研究中发现，以网络业务风险均衡度为评价指标进行路由优化分配具有局限性，网络业务风险均衡度最小的路由分配方法并不一定是实际情况下的最优路由分配方法。

　　本文以业务风险均衡度和业务平均风险度为电力通信网的可靠性评估指标，利用多目标遗传算法实现业务路由优化分配，从业务层面为电力通信业务可靠性评估和网络运行方式优化提供理论参考。

　　1问题的提出

　　1.1以业务风险均衡度为路由优化指标的局限性参考文献[10]，业务平均风险度RVg和业务风险均衡度BR计算方法分别为

　　式中：R为全网业务总的风险度，为所有通道的业务风险度总和；N为网络业务的总通道数；RE()为网络中第/个通道的风险度。

　　网络业务风险均衡度BR反应网络中各通道所承载的业务风险度均衡分布情况。该指标过高，则表示网络中业务通道上承载的业务分布不均；如果该指标趋近于0，则标志着全网业务安排风险均衡，网络运行风险较小。但以网络业务风险均衡度为评价指标进行路由优化分配可能具有局限性。

　　以图1所示电力通信网拓扑为例。网络某时刻只有风到风的调度数据网业务，若此时网络上有路径1(NrN2-N5)，路径2(NrN3-N6-N4-N5)这2条可选路径。根据文献中计算方法分别求出这2条路径下相关指标，如表1所示。

　　从表1可以看出，完成业务需求，路径1需要经过2个通道，路径2需要经过5个通道。路径1所承担的业务风险度要远小于路径2，而路径1的业务风险均衡度要高于路径2。我们更倾向于选择路径1完成业务需求，也就是说，单纯基于业务风

　　险均衡度进行路由优化不一定合适，实际中，应该结合业务的需求以不同的评价指标来选择路由。

　　1.2 路由优化指标及方法的选择

　　从上述分析可看出，单独以业务风险均衡度为评估指标，很难准确描述网络通路上业务承载情况。同时，对电力通信网业务进行可靠性评估的过程中同样需要考虑网络业务平均风险度的大小。因此，我们同时考虑业务风险均衡度和业务平均风险度这2个指标，实现电力通信网路由的多目标优化分配。

　　多目标遗传算法的核心是调节各目标函数之间的关系，找出使各目标函数能尽量达到比较小(或比较大)的最优解集[1'NSGAII是最常用的多目标优化算法，其计算效率和鲁棒性较好。

　　2应用NSGAII的路由优化分配方法

　　2.1 染色体的编码

　　应用遗传算法进行路由优化分配的关键是染色体的编码和解码，即确定可靠性指标与染色体之间的联系。本文采用基于优先权的间接编码方式。对网络中每个业务进行染色体独立编码，形成染色体编码段。每个染色体段中基因的位置表示节点，基因组值的大小对应于该节点的优先权大小。染色体个体共有N个独立的编码段，染色体长度L为

　　式中：N为当前所有业务需求总数；N为网络的节点总数。

　　以图1拓扑为例，假设某时刻网络有冲到凡的调度数据网业务需求。则染色体业务需求总数N为1，网络节点总数N为6，则染色体长度L为6。某个染色体个体的表示方法为：（2-5-1-6-3-4)。贝IJ节点1对应的优先权为2，节点2对应的优先权为5。

　　2.2 染色体的解码

　　染色体解码的关键是根据具有优先编码的染色体求出业务需求的路径。对于某个染色体编码段，从起始节点开始进行循迹，当有多个可选通道时，选择优先权高的路径，直至到达终点。每个节点只允许在路径中存在1次。

　　以图1所示拓扑为例，假设某时刻网络有节点Nj到Ns的调度数据网业务需求。其对应染色体段的编码方式为(2-5-1-6-3-4)。则从冲出发，有通道Nj-N2和风我可选，由于节点2对应基因的优先权高于节点3对应基因的优先权，因此循迹过程为NrN2，依次循迹可得业务路径为N1-N2-N6-N4-N5。

　　由于基于优先权编码方式的特殊性，在反求路径过程中会出现死路的情况。同样以图1所示拓扑为例，假设某时刻网络有节点冲到N5的调度数据网业务需求。其对应的染色体段的编码方式为(2-5-4-6-1-3)。则路径依次为NrN2-N6-N4-N3，当循迹过程达到节点N3后，由于与之相连的节点(NuN4,N6)都已经存在路径中，则循迹过程出现死路。为此我们增加阻塞数组。当循迹过程到节点N3，发现无路可走后，则将节点N3放入前面一个节点(N4)的阻塞数组中，循迹过程返回到节点N4。在继续选路的过程中，选择排除阻塞节点(N3)和已存在路径中的节点风)后的剩余节点的)中优先权最大的节点。即路径依次为N7N2-N6-N4-N5，循迹结束。

　　当对基于优先权染色体解码求出各电网通信业务的路径后，利用第1节的计算方法进行网络评价指标的计算，求出各个染色体对应的业务平均风险度Ravg和业务风险均衡度。

　　2.3应用NSGAII的路由优化算法流程

　　1) 随机产生初始种群P。。计算每个个体的业务平均风险度Ravg和业务风险均衡度Br；根据这1个目标函数的值，对种群进行非劣排序，计算拥挤距离。

　　2) 根据非劣排序和拥挤距离计算结果，对P0进行选择、交叉、变异，得到新种群0。，令?=0。

　　3) 形成新的种群R=P,U0,，计算每个个体的Ravg和Br；根据这2个目标函数的值，对新的种群进行非劣排序，计算拥挤距离。

　　4) 根据非劣排序和拥挤距离计算的结果，选择新种群R中最好的N个体形成新的种群PM；对种群Pm进行选择、交叉、变异，得到新的种群。

　　5) 若终止条件成立，则遗传过程结束；否则?=?+1，跳转到步骤3)继续进行循环。

　　遗传算法中选择过程采用二元锦标赛选择，交叉过程采用基于位置的杂交运算法，变异过程则随机的改变某个染色体中2个基因的位置。

　　3优化算例

　　3.1算例1

　　以文献所示拓扑为例，网络中节点个数为6，业务通道边的数目为8。设网络中有5个业务需求，分别为：节点冲到N5的调度数据网业务；节点冲到N6的调度数据网业务；节点风到N4的变电站综合监控业务；节点冲到N5的智能电网信息支撑(SG-ERP)业务；节点风到凡的会议电视系统业务。

　　利用遗传算法进行路由优化分配。网络中有5个业务需求，则每个染色体个体有5个染色体段；网络节点数为6，每个染色体段的长度为6；则染色体的总长度为30。算例中NSGAII参数设置如下：初始种群规模为100，迭代次数为200，变异率为0.1。

　　图2显示了Pareto最优解对应的个数在种群中所占的比例在迭代过程中的变化情况，本文设置的最大运行次数为200次，由图可知运行到30代左右时，Pareto最优解对应的个数在种群中所占的比例已基本保持不变，为45%左右。

　　图3为NSGAII算法初始种群和运行200代后种群的分布空间。结果表明NSGAII算法用于电力

　　通信网路由优化的有效性。由于业务平均风险度Rmg和业务风险均衡度BR这2个目标函数的相互矛盾性，一般情况下不能同时使2个函数同时最小，因此通常根据实际情况从Pareto最优解集中进行选择。

　　表2所示为部分Pareto最优解，各种方案对应的业务路由见表3。若以降低电力通信网的业务风险均衡度BR为主要优化目标，则选择方案1；若以降低业务平均风险度Ravg为主要优化目标，则选择

　　方案5；若无特殊要求时，则可以选择方案3。

　　3.2算例

　　电力通信网中不全是1对1的业务。有可能是1对N{1个起始点，N个终止点)，N对\(N个起始点，1个终止点)或者多个节点顺序执行(从某起始节点出发，顺序经过多个中间节点，最终到达终止节点)等情况。此时可将业务请求分解成多个子业务请求。如图1，某时段网络中有N1到风的调度数据网业务请求，其必须经过N6。则可分解成2个子业务请求，分别为N1到N6和N6到风的调度数据网业务。

　　对图4网络(NSFNET)进行最优路由分配。设网络中有5个业务需求，分别为：风到叫的调度数据网业务，其必须经过N9；N5到Nm的变电站综合监控业务；N„到风的SG-ERP业务；N1到N6的会议电视业务；N3到N13的行政电话业务。由于业务1有中间节点的约束，因此可以拆分成从N1到叫和从N9到N7的2个子业务，则网络中有6个业务需求。每个染色体有6个染色体段；网络节点数为14，每个染色体段长度为14；则染色体总长度为84。算例中NSGAII参数设置：初始种群规模为100，迭代次数为300，变异率为0.1。

　　图5显示了Pareto最优解对应的个数在种群中所占的比例在迭代过程中的变化情况，本文设置的最大运行次数为300次，由图可知运行到100代左右时，Pareto最优解对应的个数在种群中占的比例基本保持在35%左右。图6为NSGAII算法初始种群和运行300代后种群的分布空间。

　　表4为部分Pareto最优解，各种方案对应的业务路由如表5所示。若以降低电力通信网的业务风险均衡度BR为主要优化目标时，则选择方案1；若以降低业务平均风险度Rvg为主要优化目标时，则选择方案5；若无特殊要求时，则可以选择方案3。4结语

　　4.结语

     对电力通信网可靠性进行评估时，不仅要考虑网络固有的可靠性，还应该从业务层面对网络所承载的电力系统业务可靠性进行分析。本文提出的考虑电力通信网可靠性的业务路由优化分配方法，能够在已确定网络拓扑的情况下，为电力系统通信部门安排业务通道和组织运行方式提供科学合理的辅助决策方案，使得电力通信网络业务运行在高可靠性方式下。关于业务在通信过程中时延和网络节点拥挤度对于电力通信网可靠性的影响，均需进行深入的分析和研究。