基于量子遗传算法的电力通信网路由选择策略

曾 瑛，蒋康明，杨 娇，李 彬

（1．广东电网公司 电力调度控制中心，广州510600；2．华北电力大学 电气与电子工程学院，北京102206）

电力市场改革的深化和电力行业信息化程度的提高使电力业务种类和数量迅速增加［1］，对通信指标的需求多样化，为了确保服务质量（QoS），路由选择不再仅仅将“可达”和“最短路径”作为衡量标准，而是希望考虑电力业务具体通信需求和网络的动态特性等要求。因此，如何满足电力业务通信需求、加速算法的收敛速度等问题成为设计面向电力业务路由协议时重点考虑的问题。文献［2］介绍了在路由算法参数中建立一个乘性QoS约束参数，在传统的路由算法基础上加入可用性参数来搜索可靠性最佳路径的方法；文献［3］提出了一种考虑负载均衡的新型联合路由算法，具有负载均衡、优化网络资源和降低端到端时延等优点；文献［4－8］对电力通信网络的可靠性、风险评估、部分网络失效后的自愈方法等内容进行了研究，但尚未研究电力通信网络在带宽、时延和丢包率等多约束条件下路径查找问题，也未建立面向电力业务的路由算法。

针对多约束路由问题的求解，一般采用启发式算法求解，如遗传算法（genetic algorithm，GA）、蚁群算法（ant colony optimization，ACO）、模拟退火算法和粒子群算法等。但是由于这些算法本身存在一些缺点，如遗传算法很难得到最优解，一般是计算得到较优解，在较优解的基础上计算得到最优解，所需要的时间将成倍增加；蚁群算法求解多约束路由时速度慢，容易出现早熟收敛和停滞现象。针对遗传算法和蚁群算法的不足，国内外学者从不同角度提出了改进算法［9－12］，在一定程度上提高了算法的全局搜索能力和收敛速度。量子遗传算法［10］（quantum genetic algorithm，QGA）是将遗传算法与量子计算理论相结合而发展起来的一种新遗传算法，具有种群规模小而不影响算法性能、同时具有开发和探索能力、收敛速度快等特点，在求解组合优化问题时与遗传算法相比表现出优势。

针对以上分析，笔者基于量子遗传算法的基本原理，提出一种面向电力业务的路由算法。该算法根据电力业务对通信指标的不同要求，对其进行划分类别，明确业务对通信指标的要求；路由起始节点根据当前网络状态和电力业务类别调用相应的适应度函数，利用量子遗传算法进行路由选择。该算法一方面考虑了传统技术中的通信指标对路由链路的影响，另一方面构建了适应度函数，对电力系统的各种业务按照其权重值进行考虑。综合考虑最短路径和针对电力业务特点的约束条件，寻出满足电力业务特性的最优路径，仿真结果表明了该算法的有效性。

1 电力通信网路由问题的网络模型

针对电力通信网的物理结构和业务需求情况，应该合理选择路由，满足业务的QoS要求，同时提高电力通信网的服务质量，平衡网络负载。电力通信网中，时延、带宽和丢包率是三个重要的参数，各电力业务对三者的要求也不尽相同。根据对通信指标的不同要求，将电力系统现有业务划分为五种类别，具体为：

1）高可靠宽带实时业务，包括电力市场营销、电能质量监测系统等；

2）高可靠窄带实时业务，包括继电保护和安稳系统；

3）可靠宽带实时业务，包括视频会议；

4）可靠窄带实时业务，包括调度自动化和电能计量；

5）低可靠窄带非实时业务，包括办公自动化、管理信息业务和调度管理信息系统。

在研究路由问题时，电力通信网可表示为一个加权图G（V，E），其中V表示节点集，E表示连接节点的通信链路集，即G是由一组点V＝｛1，2，…，N｝和一组连接V中节点的边E＝V×V组成。设s和d分别表示源节点和目的节点，任意一条路径x＝｛s，i，…，j，d｝表示源节点到目的节点的路径。

针对电力业务对通信指标要求的不同，在为其进行路径选择时应考虑各类电力业务的具体通信需要，根据业务对时延、带宽和丢包率的要求构造相应的目标函数，用以获得符合业务通信特性的传输路径。假设x为第i类业务的一条可用路径，i∈｛1，2，…，5｝，则x满足：

式中：FiD（x），FiB（x）和FiL（x）为目标函数；D（x）为路径x的时延，Dmax为网络中第i类电力业务可容忍的时延最大值；B为网络中第i类电力业务要求的带宽，B（x）为路径x的可用带宽，Bmax为可行解中的可用带宽最大值，Bmin为可行解中的可用带宽最小值；L（x）为路径x的丢包率，Lmax为网络中第i类电力业务可容忍的丢包率最大值。

该问题属于多目标多约束优化问题，在多数条件下，无法保证FiD（x），FiB（x）和FiL（x）均取得最大值，因此构造第i（i＝1，2，…，5）类电力业务优化目标函数为：

其中，权重值wi1，wi2，wi3是正实数，具体数值取决于每类电力业务对时延、带宽和可靠性的不同要求，且满足wi1＋wi2＋wi3＝1。

2 量子遗传算法的基本原理

2．1 量子比特编码

区别与二进制编码、实数编码和树形编码等已有的GA编码方式，QGA采用一种基于量子比特（qubit）的编码方式［10］，即用qubit来存储和表达一个基因，量子比特可以处于0和1两个本征态或两个状态的任意叠加，其状态表示为：

其中，｜α｜2，｜β｜2分别表示量子比特处于“0”态和“1”态的概率且满足｜α｜2＋｜β｜2＝1。

一个由n个qubit构成的量子染色体可以描述为：

其中，｜αr｜2＋｜βr｜2＝1（r＝1，2，…，n），该染色体可同时表达2n个态的信息，保证了种群的多样性，随着量子比特概率幅趋于1或0，染色体收敛到单一态，种群多样性呈逐渐减小趋势，算法收敛。

在对电力通信网路由问题进行求解时，量子染色体的量子比特数由电力通信网节点数和节点中最大邻接点数共同确定。例如在一个N个节点组成的电力通信网，设节点的最大邻接点数为l，求解k使得2k－1≤l≤2k，则编码时量子染色体的量子比特数为n＝N×k。

2．2 量子测量

通过量子编码得到量子比特概率幅表示的染色体，对编码的染色体实施量子测量操作，从而得到长度为n的二进制字符串p＝｛x1，…，xr，…，xn｝，xr为二进制字符0或1。具体测量过程为：随机产生一个数字R（R∈［0，1］），若R 大于｜αr｜2（r＝1，2，…n），xr取1，反之取0。

2．3 量子比特译码

为了计算种群中每个个体的适应度值，需对编码染色体实施量子比特译码［13］操作，将二进制的个体转换为十进制，得到具体路径。首先生成N×l矩阵H，其中H（i，j）表示第i个节点的第j个相邻节点，若与i相邻的节点数小于j，则H（i，j）＝0。译码时，将测量得到的二进制字符串p＝｛x1，…，xr，…，xn｝分为N 组，每组量子比特数为k，把第i组的量子比特数视为一个二进制字符串，并将其转换为十进制数j，表示第i个节点的下一个节点为H（i，j＋1），并寻找节点 H（i，j＋1）的下一个节点，直到找到终点N，译码过程需删除无效路径。

2．4 量子变异

为了加快算法收敛，需对种群进行变异操作，在量子理论中，量子比特状态的转换是通过量子门实现的，常用的量子门有：非门、异或门、受控异或门和旋转门。量子旋转门用旋转角来表征染色体变异，并在变异过程中加入当前最优个体信息，达到加速算法收敛的目的。由于量子旋转门的参数具有可调整性，通用性强，故采用量子旋转门来实现染色体的变异。量子旋转门为2×2的矩阵，具体表示为其中，量子门的旋转角θ＝f（xr，br）×Δθ，f（xr，br）为旋转门方向取值为1，－1或0。xr表示当前染色体的第r位，br表示当前最优染色体的第r位，Δθ为旋转角大小，用以控制算法的收敛速度，太大可能导致算法运行结果发散或早熟得到局部最优解。

3 电力通信网路由选择策略

在为电力业务选择路由时，首先根据业务对通信指标的需求判定所属类别，确定目标函数及可容忍时延最大值、最小可用带宽和可容忍丢包率最大值约束条件。根据网络中时延、带宽和节点的丢包率大小选择满足QoS约束条件的路径，利用量子遗传算法寻找符合业务通信指标要求的最佳路径，具体步骤如下。

1）初始化。遗传代数t＝0，种群Q（t）＝Q（0），种群规模为K，并对种群进行量子遗传编码；经过编码后可得Q（t）＝｛qt1，qt2，…qtK｝，其中，

初始化时，Q（0）的全部染色体的所有基因的概率幅被初始化为

2）对Q（t）的所有个体实施一次测量得到P（t），含有K个确定的个体，即

3）对P（t）进行译码得到具体路径，将路径信息（包括时延、可用带宽和丢包率）代入式（3），进行适应度评估；

4）选择并保存最优个体及其适应度值，作为该种群个体下一步进化的目标值；

5）验证得到的最优个体是否满足最佳路由条件，若是，则结束并输出当前最优个体，否则继续；

6）量子变异操作，采用量子旋转门变异操作更新Q（t），得到下一代种群Q（t＋1）；

7）t＝t＋1，转回2）。

4 仿真实验与分析

为验证所提算法的有效性，笔者使用 Matlab2010Ra仿真平台对ACO和本文算法进行仿真对比分析。设定网络仿真拓扑结构，包含随机生成的20个节点（V1～V20），49条边及随机生成的各链路时延、带宽和节点丢包率，其中（D，B）表示链路上的时延（D／ms）和带宽（B／MHz）。在仿真实验中算法具体参数设定为：QGA算法最大迭代次数为200，种群大小为40，节点的最大邻接点数为7，编码时量子染色体的量子比特数为60，量子旋转门参数的设置参考文献［10］；ACO算法最大迭代次数为200，蚂蚁数量为40，第t代蚂蚁m从i节点转移到j节点的概率为

其中ηij（t）为启发函数，

表示i节点转移到j节点的期望程度，仿真时取信息素重要程度因子α＝1，启发函数重要程度因子β＝1，信息素更新公式

取信息素挥发因子ρ＝0．5，第m只蚂蚁从i节点转移到j节点路径上释放的信息素浓度

表1 电力业务对通信指标的具体要求

假设业务要求带宽为20MHz，路径最小时延控制在100ms以内，丢包率不超过0．3。首先根据业务对通信指标的要求，判定该业务为高可靠宽带实时业务，对应的目标函数为F1（x）＝0．2F1D（x）＋0．6F1B（x）＋0．2F1L（x）。图2和图3分别给出了s＝1，d＝20和s＝2，d＝19时，QGA与ACO在求解业务路由问题时的收敛特性。显然，QGA种群大小和ACO蚂蚁数目K一样时，QGA能更快地收敛到最优路径，并且QGA求得的最优路径要优于ACO求得的最优路径。

图2 s＝1，d＝20时，QGA与ACO的收敛特性

图3 s＝2，d＝19时，QGA与ACO的收敛特性

表2和表3给出了s＝1，d＝20和s＝2，d＝19时，QGA和ACO求得最优路径P及目标函数F值和路径时延、带宽和丢包率的值。由表中数据可知，所提算法不仅可以找到满足电力业务通信要求的路径，而且最优解均优于ACO算法求得的最优解，且当两算法求得的最优解比较相近时，该算法找到最优解的时延和丢包率均小于ACO算法求得的最优解的时延和丢包率，说明该算法在满足电力业务通信要求的条件下，进一步达到了优化网络资源利用、负载均衡的目的。

表2 s＝1，d＝20时QGA和ACO最优路径值对比

表3 s＝2，d＝19时QGA和ACO最优路径值对比

表4给出了满足业务要求，目标函数不同的算法求得的最优解。由表中数据分析可知，针对电力业务对通信指标具体要求的不同，相同源节点和目的节点，相同约束条件下，当业务类型为可靠宽带实时业务时，对应的目标函数为

F3（x）＝0．3F3D（x）＋0．6F3B（x）＋0．1F3L（x），利用所提算法找到最优路径为（2，1，4，10，19）；而当业务类型为高可靠窄带实时业务时，对应的目标函数为

F2（x）＝0．8F2D（x）＋0．1F2B（x）＋0．1F2L（x），找到最优路径为（2，3，4，10，19）。当不同的业务类型，在相同的通信网络，并在有QoS约束的条件下，所求最优路径会随之改变。因此，有必要针对电力业务对通信指标的不同要求，对其进行划分类别，根据类别进行路由选择。

表4 s＝2，d＝19时不同业务类型的最优路径值

5 结论

本研究提出了一种基于量子遗传算法的电力通信网络路由选择策略，一方面考虑了传统技术中的通信指标对路由链路的影响，另一方面根据电力业务对通信指标要求程度构建目标函数。综合考虑最短路径和针对电力业务特点的QoS约束条件，利用量子遗传算法寻出满足电力业务特性的最优路径。从实验结果可以看出，按照对通信指标的不同需求，对电力业务划分类别进行路由选择，能够寻出满足电力业务特性的最佳路径，且算法的收敛性比较理想，能够在较短的时间内收敛到最优解。

［1］ 王勇，利韶聪，陈宝仁．电力通信业务应用及发展分析［J］．电力系统通信，2010，31（217）：44－47．

［2］ 王宇，李乐民．基于可用性的 QoS选路研究［J］．计算机应用研究，2009，26（5）：1844－1846．

［3］ 李培源，龚涌涛，顾畹仪．WDM 网络路由计算中的平衡最短路算法［J］．北京邮电大学学报，2004，27（2）：14－18．

［4］ 王庆铸，卓秀者，刘逢清．电力光纤通信网络的最佳路径选择［J］．电力系统通信，2012，33（231）：18－22．

［5］ 吴润泽，汪波涛，唐良瑞，等．新型ICT网络中的一种动态路由波长分配算法［J］．电力系统保护与控制，2010，38（22）：48－51．

［6］ 吴润泽，祁宏鹏，唐良瑞．新一代电力ICT网络中基于DiR保护环的生存性路由算法［J］．电力系统保护与控制，2011，39（16）：25－29．

［7］ 龚钢军，韩军伟，朱娟溪，等．配电无线传感网功率控制路由优化算法［J］．电力系统保护与控制，2012，40（22）：129－134．

［8］ 熊小伏，吴玲燕，陈星田．满足广域保护通信可靠性和时延要求的路由选择方法［J］．电力系统自动化，2011，35（3）：44－48．

［9］ Tang Kezong，Sun Tingkai，Yang Jingyu．An improved genetic algorithm based on a novel selection strategy for nonlinear programming problems［J］．Computers and Chemical Engineering，2011，35（4）：615－621．

［10］ 杨淑嫒，刘芳，焦李成．一种基于量子染色体的遗传算法［J］．西安电子科技大学学报（自然科学报），2004，31（1）：76－81．

［11］ Yang Jingan，Zhuang Yanbin．An improved ant colony optimization algorithm for solving a complex combinatorial optimization problem ［J］．Applied Soft Computing，2010，10（2）：653－660．

［12］ Twomey C，Stutzle T，Dorigo M．An analysis of communication policies for homogeneous multi－colony ACO algorithms［J］．Information Sciences，2010，180（12）：2390－2404．

［13］ 刘欣，李飞，郑宝玉．基于量子遗传算法的多约束 QoS路由选择算法［J］．南京邮电大学学报（自然科学报），2011，31（2）：31－35．