基于策略多播路由的电力通信网路由优化研究

李敏

(国网蚌埠供电公司 信息通信公司，蚌埠 233000)

0 引言

策略路由是一种基于业务流策略请求和网络可用资源进行路由选择的机制[1]。在这种动态路由过程中，涉及到可用带宽、丢失率、时延、时延抖动、开销等等约束参数[2]。多播是一种允许多播源同时发送单一数据包到多个接收者的网络传输技术，可以有效节省网络带宽。多播源把数据包发送到特定的多播组，只有该多播组成员才能收到该数据包[3]。电力通信网是现代大型互联电网的重要组成部分，也是实现电网调度自动化的基础。

随着电力行业信息化程度的提高，电力业务种类和数量迅速增加，对通信指标的需求也变得多样化。策略路由选择除了可达和最短路径的衡量指标之外，还要考虑电力通信业务的具体通信需求和网络动态特性。在电力通信网络路由算法设计中，如何满足其业务通信需求，如何加速算法的求解速度等都是需要重点考虑的问题。目前对路由算法进行优化的文献很多，例如在传统路由算法中加入乘性策略约束参数来提高搜索可靠性并实现最佳路由[4]，考虑负载均衡的路由算法[5]来实现网络资源优化和网络性能提高的目的等。针对电力通信网可靠性、风险评估、失效自愈、策略路由优化等问题。但针对电力通信网中策略多播的路由优化尚未有深入研究。而目前策略多播路由是电力通信网中一种主要的路由方式。实现策略多播路由的主要目标有两点：为每一个接纳的电力通信网业务请求找到满足其策略要求的多播树[6]；优化全局资源利用率，平衡电力通信网负载，最大化业务处理能力[7]。其关键是如何建立满足多个约束的最小代价树，该问题被称为最小Steiner树问题[8]，而多个不相关可加度量约束的多播路由问题被证明是一个NP完全问题，一般要使用智能算法或启发式算法来处理。典型的启发式算法有MST、RS等[9]。

本文主要通过改进的量子进化算法来实现电力通信网中的策略多播路由优化，该改进量子进化算法由优化的MST算法即OMST与量子进化算法结合实现，量子进化算法中对其量子门旋转角选择采用了一种动态调整的方法。而OMST算法用于实现最小Steiner树。该策略多播路由优化方案首先根据电力通信业务对通信指标的不同要求进行类别划分；在多播路由过程中，根据网络状态和业务类别调用相应的适应度函数，利用改进量子进化算法实现路由优化。算法充分考虑了电力通信网传输指标要求和电力通信网业务需求，寻出满足电力通信网业务特性的优化多播路径。并利用仿真实验对本算法性能进行了验证。

1 电力通信网策略业务路由模型

1.1 策略业务路由模型

考虑到电力通信网的网络基础结构和其业务需求，在通信中应该合理选择路由，从而满足电力网业务的要求，并尽量平衡网络负载，提高网络整体性能。根据电力通信网中对时延、带宽、丢包率等指标的要求，电力通信网中的业务分为关键运行业务和事务管理业务两大类，其中关键运行业务大类又可以分为安全1类，安全2类，安全3类；事务管理业务大类可分为安全4类，安全5类。

安全1类关键运行业务是电力生产中的核心业务，对电力系统的可靠运行起着重要作用。安全2类关键运行业务作为电力系统的必要环节，主要负责各类调度和智能管理；安全3类关键运行业务负责变电站及配网状态监控和自动化处理事务管理业务大类从实时性角度出发可以分为安全4类和安全5类，其中安全4类业务为公司经营管理业务，辅助电力系统市场化服务的平稳可靠；安全5类为企业信息化与管理业务，负责电力企业ERP业务。

电力通信网的路由问题可以表示为加权图G(V,E)，其中，V表示节点集，E表示链路集，若源点到目的节点分别用s和d表示，任意一条路径PTx={s,i,…,j,d}表示s到d之间的路径。

在为电力通信网中的业务进行路由选择时，必须考虑各类电力业务的具体通信要求。根据其对通信的指标要求构造目标函数，实现符合电力业务通信特性的传输路径。若PTx为第i类业务的一条可用路径，i∈{1,2,…,5}，则PTx满足式(1)。

(1)

其中，fD(xi)、fB(xi)和fL(xi)分别是时延、带宽和丢包率的目标函数。D(xi)表示i类业务在路径x上的时延，Dmax是电力网中该类业务最大允许时延值；B(xi)是第i类业务在路径x上的可用带宽，Bmax是可行解中的最大可用带宽，Bmin是可行解中的最小可用带宽；L(xi)是i类业务在路径x上的丢包率，Lmax为该类业务在电力网中可容忍的最大丢包率。

以上路由模型所述问题属于多目标多约束优化范畴，在多数情况下无法保证3个目标函数均取得最大值，因此可以利用权重法构造一个电力业务综合目标函数：

maxf(xi)=w1ifD(xi)+w2ifB(xi)+w3ifL(xi)

(2)

其中，w1i，w2i和w3i满足w1i+w2i+w3i=1，其具体取值取决于各类业务对通信指标的不同要求。

本文结合蚌埠供电公司电力通信网的实际情况，对各类电力通信业务的通信指标要求进行了规定，见表1所示。

表1 各类电力通信业务的指标及目标函数

1.2 策略多播路由模型

多播型电力通信网用有权无向图G=(V,E)表示，其中，V是节点集，E是节点间链路集，|V|和|E|分别是节点数和链路数。多播源点设为s∈V，多播目的节点集为D⊆{V-{s}}，对任一节点n∈V定义5个参数，带宽bw(n)，时延delay(n)，开销cost(n)，丢包率ptloss(e)，以及时延抖动dj(e)，其中带宽和开销均大于零，丢包率和时延抖动大于等于零；对任一链路也定义类似的五个参数，带宽bw(n)，时延delay(n)，开销cost(n)，丢包率ptloss(e)，以及时延抖动dj(e)。在给定s、D的情况下，设T(s,D)是由两部分共同构成的多播树，s遍历D的所有成员树，即T中存在由源节点s到某一目的节点的通路pt(s,d)。具有策略优化的多播路由算法就是要在网络G=(V,E)中从原点s到多播目的节点集Md⊆{V-{s}}之间构造一棵包含基本节点的最小开销多播树T(s,Md)，即找出min(cost(T(s,D))，且T(s,D)满足以下关系，如式(3)。

T(s,D)=

(3)

其中，pt(s,d)为T(s,Md)上s到d的路由；Du、DJu、PLu和Bu分别表示电力通信网业务对延迟、延迟抖动、丢包率和带宽的约束值。满足上述公式(2)中四个约束条件的多播树中，cost(T(s,Md))总成本最小。

2 策略多播路由模型的量子进化算法

2.1 量子进化算法及路由优化过程

一个由n个量子比特构成的量子比特编码可以描述为：

令α=cosθ，β=sinθ，则量子比特可以表示为[cosθsinθ]T，其中，θ是量子比特的相位，其改变可以由量子旋转门实现式(4)。

(4)

(5)

为了加快算法收敛，要对种群进行变异操作。量子进化算法采用量子旋转门对信息素进行更新，达到加速算法收敛的目的如式(6)。

(6)

(7)

(8)

(9)

(10)

(11)

引入控制因子λ∈[0,1]，则适应度函数选取如式(12)。

(12)

其中，fmax和fmin分别表示当前一代群体中个体适应度的最大和最小值。原始适应度f(x)定义为式(13)。

(13)

由此，信息素的更新规则将表述为式(14)。

(14)

在为电力通信网业务进行路由选择时，首先根据各类业务对通信指标的需求判定所属类别，确定目标函数及可容忍最大时延、最小可用带宽和最大丢包率等约束条件[13]。根据网络中时延、带宽和节点丢包率大小选择满足策略约束条件的路径。多播路由优化主要是构造一棵多播树，其核心思想是，首先生成一棵只包含源节点的树T，每次选择一条与T连接且满足策略约束的链路，逐步生成该多播树。

构造基于量子进化理论的多播树算法QM步骤如下：

(1) 设源节点s，多播组成员集合{m1,m2,…,mn}，网络中某条链路e(i,j)具有如公式(3)所述的策略约束；建立树T和候选链路集合E1，初始时刻T={s}，E1={e(s,i)|e(s,i)∈E}

(2) 从候选集E1中选一条链路e(m,n)如式(15)。

(15)

其中，m∈T，n∉T，qj为ej上的信息素浓度；η=1/cost(ej)为ej上的启发式函数，ε和δ分别是信息启发因子和期望启发因子；

(3) 根据公式(2)计算链路e(m,n)的约束值，满足要求则将其加入E1中；

(4) 若T尚未覆盖所有目的节点，转到第(2)步，否则，对T进行删减，除去所有非目的节点的叶子节点及相关边，得到最终的多播树。

基于量子进化算法进行策略多播路由优化算法QEA-MRO如下：

(1) 初始化种群；

(2) 测量初始种群Q(t)中各个体，得到一组状态P(t)；

(3) 对P(t)译码并进行适应度评估；

(4) 记录当前的最佳个体状态及其适应度值，作为该种群个体下一步进化的目标值；

(5) 验证得到的最佳个体是否满足最佳路由条件，且连续若干次找到的树是否一致，即算法是否收敛，若两个条件都满足，则结束并输出当前最优解，否则继续：

(6) Whilet≤tmaxdo

Begin

t=t+1；

测量种群Q(t-1)，得到状态P(t)；

对P(t)进行适应度评估；

量子变异操作，采用量子旋转门变异操作更新Q(t)，得到下一代种群Q(t+1)；

记录下最佳个体状态及其适应度值；

End

End

2.2 改进的量子进化算法

在求解多播树中各个体的最优解时，可以利用OMST(Optimized Minimum Spanning Tree)算法生成受约束最小的Steiner树[14]。这种改进的量子进化算法首先基于量子进化算法来选择Steiner预备点，而后对这些节点实施OMST算法求解最小Steiner树。量子进化算法中的每个个体都对应一棵Steiner树，因此由量子交叉和量子门旋转操作可以对个体进行优化，从而得到策略多播路由优化问题的解。

AQEA(Advanced Evolutionary Algorithm)在量子个体上实施量子交叉，可以保留较好的基因段；利用量子门更新和搜索网络自适应调整策略能确保种群的多样性[15]；基于OMST生成最小Stenier树，使得解在收敛精度高的同时具有收敛速度快的优势。对MT算法进行改造，增加OMST算法步骤，改进算法称为IMT。修改MT其第四步为：

(4) 若T尚未覆盖所有目的节点，转到第(2)步，否则，对T的任意两点使用Floyds算法求出图T=(MV,ME)的距离图D(T)，两节点间保留最小代价路径；

(5) 图D(T)中构造仅含MD(多播目的节点)的子图T1；

(6) 计算T1的最小支撑树(MST)ST1；

(7) 用图T中相应的最短路径代替ST1中的每条边，构造图T的子图T2；

(8) 计算T2的最小支撑树ST2；

(9) 对ST2中那些符合mv∉s且该点的度deg(mv)=1的节点逐一进行删除操作，最后得到ST2的最小多播支撑树TMMSP，该树即最小Steiner树。

改进的策略多播路由优化过程只要对QEA-MRO算法修改如下：

第三步修改为：对P(t)译码，用OMST算法求解各个体的Steiner树，并进行适应度评估；

第六步修改为：

(6) Whilet≤tmaxdo

Begin

t=t+1;

测量种群Q(t-1)，得到状态P(t)；利用OMST算法求解各个体的Steiner树，对P(t)的局部群体中每个个体进行适应度评估；

量子变异操作，采用量子旋转门变异操作更新Q(t)，得到下一代种群Q(t+1)；

对IMT中删除的必在Steiner树中的边，其费用加到最优解的最小成本上；

记录下最佳个体状态及其适应度值；

End

End

随着算法循环的递进，种群将逐步收敛于最优解。该算法的搜索空间大，且利用OMST算法可以确保方向性较强的搜索，加快了搜索最优解的速度。

3 仿真与分析

为评价AQEA算法的性能，利用Matlab7.1对算法进行了仿真，主要验证该算法在策略多播路由选择上的有效性和可行性，并与经典算法ACO、QEA进行性能对比。网络拓扑为随机生成的30个节点。各链路带宽、时延和丢包率均为随机生成。

算法参数设定如下：AQEA最大迭代次数200，种群大小为40，节点的最大邻接数为7，量子比特为60，量子门旋转时，初始旋转角为0，进化过程中根据公式(6)动态调整，最后稳定于0.01π。

随机生成的30个节点的网络拓扑图,如图1所示。

图1 30节点拓扑图

执行AQEA后生成的多播树如图2和3所示。

图2 源节点为5的多播树

图3 源节点为13的多播树

图2的源节点为5，目的节点为18，21，25，27；图3的源节点为13，目的节点为1，21，25，29。

假设有业务要求带宽12 Mbps，最大时延要求0.08 s，丢包率低于1%，根据表1可以判断该业务属于安全3类，对应目标函数为f(x3)=0.6fB(x3)+0.3fD(x3)+0.1fL(x3)。将AQEA算法和ACO算法进行对比。取两个不同源点(5和13)时，两种算法的适应度比较,如图4和图5所示。

图4 源节点为5时AQEA算法和ACO算法适应度比较

结果表明，两种算法在种群大小和蚂蚁数量一致时，AQEA的收敛特性显然更好，最优多播路径的收敛速度更快，且其多播路径更优化。

图5 源节点为13时AQEA算法和ACO算法适应度比较

两种算法在不同源点时求解最优多播树的过程中得到的路径时延、带宽、丢包率和目标函数值,如表2所示。

表2 不同节点ACO&AQEA路由比较

从表2中数据可以看出AQEA算法可以实现满足电力通信网业务要求的多播路由，且最优解要优于ACO得到的最优解。即便在两种算法求得的最优解相近时，AQEA中获得的最优解的时延和丢包率性能要更好，表明本算法既能够满足电力通信业务要求，又可以实现负载均衡，提高网络资源利用率。

当节点数量从30逐步增加到150，多播组成员占总节点数的15%时，比较AQEA, QEA,ACO3种算法搜索解的开销和收敛时间，得到的实验效果,如图6和图7所示。

图6 AQEA,QEA,ACO三种算法搜索解的开销

图7 AQEA,QEA,ACO三种算法搜索收敛时间

仿真结果表明，AQEA得到的多播树开销和收敛时间要优于ACO和QEA算法，且随着拓扑规模的增大，优越性越明显。实验同时也说明本算法中动态调整旋转角、利用最小Steiner树来获得多播树的策略是有效的，前者确保信息素及时有效更新，使得蚂蚁选择多播树全局开销更优的链路机会更大，更有可能与其他目标节点共享该链路，从而节省搜索时间，加快收敛速度；利用后者得到的最优多播树具有高精度优势，可以实现更好的路由性能。

4 总结

量子进化算法具有速度快、鲁棒性强的优点，能够较好地完成电力通信网的策略多播路由优化。本文提出一种基于策略多播路由的电力通信网络路由优化的改进的量子进化算法，利用动态方式调整量子选择门旋转角，同时将量子进化算法和OMST算法结合生成最小Steiner树，不仅增强了种群多样性，也加快了种群的收敛速度。实验表明本算法有较好的收敛特性，在多播路由开销和收敛时间上都比传统量子进化算法、蚁群算法更优化。本算法既能够满足电力通信业务要求，在较短的时间内收敛到最优多播树，又可以实现负载均衡，提高网络资源利用率。且对不同的通信业务类别，对应的多播路由也有差异，表明本算法具有业务路由自适应性。