基于Q Learning算法的区域配网业务路由分配方法研究

赵志军　金军

摘 要：传统的配网业务路由分配方法的链条占用率过高，导致丢包率较大。为此，设计了基于Q Learning算法的区域配网业务路由分配方法。按照传统分类方式划分业务路由中的性能指标，根据路由约束条件计算指标的约束值，从而确定业务路由的最优传输路径。结合Bellman Equation方法不断计算并更新配网中的Q值，再综合节点和网络业务指标，利用Q Learning算法计算得到区域配网中的风险均衡度。不断变换VNFs的路由顺序将其转换为TSP路由问题，最终得到路由分配矩阵，实现区域配网业务路由的分配。实验结果表明：与传统分配方法相比，基于Q Learning算法的分配方法的链条占用率低，有效减小了业务数据转发过程的丢包率。

关键词：Q Learning算法;业务路由;Bellman Equation方法;最优传输路径;风险均衡度;路由分配

中图分类号：TN915      文献标识码：A

Research on Route Allocation Method of Regional Distribution

Network Service Based on Q Learning Algorithm

ZHAO Zhi-jun1，JIN Jun2

（1.State Grid Jiaxing Electric Power Supply Company， Jiaxing， Zhejiang 314000，China;

2.Jiaxing Hengchuang Electric Power Group Co. Ltd.， Jiaxing， Zhejiang 314000，China）

Abstract： The traditional routing distribution method of distribution network has a high chain occupancy rate， which leads to a high packet loss rate. This study designed a routing distribution method for regional distribution network based on Q Learning algorithm. According to the traditional classification method， the performance index of the service route is divided， and the constraint value of the index is calculated according to the route constraint conditions， so as to determine the optimal transmission path of the service route. The Bellman Equation method is used to calculate and update the Q value in the distribution network， and then the node and network service indexes are integrated to calculate the risk equilibrium degree in the regional distribution network. The routing order of VNFs is constantly changed into TSP routing problem， and finally the routing distribution matrix is obtained to realize the routing distribution of regional distribution network. The experimental results show that compared with the traditional distribution method， the distribution method based on Q Learning algorithm has a low chain occupancy rate and effectively reduces the packet loss rate in the process of forwarding business data.

Key words：Q Learning algorithm; business routing; Bellman Equation method; optimal transmission path; risk balance; routing assignment

隨着智能电网技术的不断发展，电力配网正逐步向数字化、综合化、智能化、多业务化等方向演进[1]。配网承担着电力资源调度分配和信息化管理等业务需求，配网的安全可靠直接影响电力系统的安全与稳定。

业务路由是一种可拓展的互联网路由器，可以实现业务数据的迁移。在配网运行过程中，业务路由分配关系到电力系统的可靠性和配电网运行方式的优化[2]。因此，配网业务路由分配的合理、可靠分配至关重要。文献[3]中提出了一种基于频谱位示图的联合优化路由频谱分配方法，利用预先计算控制模型、频谱位示图和最佳分配算法构建业务请求数据库，结合实时计算结果，进行了路由频谱分配。文献[4]中提出了一种电力传输网络的动态波道均衡路由分配方法，根据电力网络拓扑结果与业务请求状态完成业务请求合并，对跨域业务进行路由选择，根据位置优先级设定对业务请求优先级进行设置，结合分组波长分配算法实现业务路由的分配。然而，这两种方法路由分配过程的链条占用率过高，导致业务数据转发过程的丢包率较大，实用性较差。

Q Learning算法是强化学习算法中的一种，其中的Q值是在某一状态下采取某种动作能够获得收益的期望，同时Q值会根据环境的状态反馈相应的操作信息。在Q Learning算法中，“状态State”与“行为Action”是两个重要的单位，需要完成的目标为“状态”，完成的路径为“行为”，两者构建成一张Q-table来储存Q值，依照Q值来选取能够获得最大收益的操作[5]。

为此，针对传统方法的不足，引入Q Learning算法，设计一种区域配网业务路由分配方法，以期保护线路继电业务、保障路由业务的服务质量、降低配网风险，为区域配网业务的稳定开展提供技术支持。

1 分配方法设计

1.1 业务路由最优传输路径的确定

在确定业务路由最优传输路径前，首先需划分业务路由中的性能指标。按照传统的分类方形式对区域配网中的路由业务进行划分[6]，跟划分结果将不同的配网运行任务分配给不同业务路由，从而产生不同的传输性能指标。划分结果如表1所示。

为保证性能指标划分的准确性，按照路由约束条件计算指标的约束值。假设vi和vj为区域配网中的节点，eij为网络中由节点vi到vj的链路，w（eij）表示链路eij的约束条件值。此时，路由的约束条件值计算方法如下所示：

w1=∑eij∈Pw（eij）w2=∏eij∈Pw（eij）w3=min eij∈Pw（eij） （1）

式（1）中，w1、w2、w3分别表示的是指标的加性、乘性、凹性的约束条件，P表示路径。对（1）式不断取值，得到存在约束条件下性能指标的网络拓扑结构，如图1所示。

图1中，括号内的数据分别表示时延与可靠度，时延是在[1，9]中随机取得的整数，可靠度是在[0.991，0.999]间随机取得的小数。圆圈内的数字表示配网业务路由。按照路由跳数排序，得到表1中指标的具体数值。在此基础上，使用图1的拓扑结构来确定一条最优路径，利用Dijkstra算法计算业务权值，可得到：

ΨP=∑s，d∈Nf（s，d）2W∑s，d∈Nf（s，d）2（2）

式（2）中，ΨP表示业务权值，W表示传输流的数量， s表示传输时的出发节点，d为目的节点，表示数据包递交率，N=1，2，3，…。基于此，可计算得到如表2所示的业务路由及其度量的参数值。

使用表2中的各项参数，结合多约束路由算法计算路由约束条件，设定约束向量H→=[H1，H2，…，Hm]，若Hi是路径约束值的下限（1≤j≤m，j≠i），则此时的路径P对应第i（1≤i≤m）种约束条件和路径约束下限Hj，路径P满足以下约束条件[7-8]：

wi（P）≤Hi（1≤i≤m）wj（P）>Hj（1≤j≤m，j≠i）（3）

利用上述约束条件，计算得到最优路径对应表2中的序号为2、3。在得到最优路径后，利用Q  Learning算法计算路径所在网络的风险均衡度，依照风险度值的大小，调整业务路由中的指标，实现区域配网业务路由的分配。

1.2 利用Q Learning算法计算网络风险均衡度

在利用Q learning算法计算网络风险均衡度时，首先需计算Q值。在区域配网结构下，随机选取一条最优路径，将配网结构初始化为0，按照最优路径规定的节点，每经过一个节点（即执行一次业务），都使用Bellman Equation方法更新一次 Q-table[9]。初始路径节点表达式如下：

Q（K'，β'）=R+γmax Q（K，β）  （4）

其中，K代表当前状态，β代表当前状态下的执行情况，K'代表行动引起的下一状态，β'表示下的执行情况，R表示奖励，γ是算法中的discount因子。更新后的路径会得到一个reward矩阵，如式（5）所示：

E=-10-10-1-100-1-10-1-1-10-1-1-100 （5）

将（5）式的初始Q-Table的值全设置为0，每一行代表一个风险状态，每一列代表每个状态的最优路径，然后将γ设置为0.8，假设此时从节点1开始传输，先将传输方向规定为向下，此时的节点传输到了节点3，使用Bellman Equation计算方法更新此时的Q-Table，更新后得到的reward表为：

E'=-100000000001000000 （6）

重复上述计算过程，使更新后的reward值保持不变，直到得到最后的网络风险的Q值[10]。综合Q值、節点和网络业务对风险均衡度的影响，计算风险均衡度，可得到：

RG=∑eij∈GR（eij）-R（e）avg∑vi∈GR（vi）-R（v）avg （7）

其中，RG表示网络业务风险均衡度，R（eij）与R（e）avg分别表示链路eij的业务风险值与网络所有链路均值，RG越小表示网络风险越均衡，R（vi）与R（v）avg分别表示配网节点vi的业务风险值与经过该节点的所有链路均值[11]。在计算两种路径的的业务风险均衡度后，依照风险均衡度，实现区域配网业务路由的分配。

1.3 区域配网业务路由分配的实现

首先考虑业务双向通信场景，为避免发生过长排队时延的情况，假设在业务物流分配时，分配请求流入、流出的数据速率均为v，让业务路由在产生的数据速率变化的情况下，满足相邻的频带的要求，计算此时的频带需求：

g=min Cv（8）

其中，C代表频带数值，min 函数将返回两个最优路径中的最小值。不同的最小值对应着不同的HC-VNFs的路由顺序，依照图2所示的路由示意图，确定路由分配顺序。

由图2所示，在路由分配时，需要访问HC-VNFa， HC-VNFb和HC-VNFc三种分配到不同的Pods节点上的虚拟架构[12]。在灵活的路由顺序下，图中的箭头路径分别表明不同的路由，根据公式（8）可以得出相邻HC-VNFs分配时所需的频带需求[13]。

使用计算得到的频带，以频带开销最小函数作为分配目标函数，利用分支限界算法快速搜索频带最小路径，将图2的路由示意图转化为TSP路由问题[14-15]，转化后的TSP路由问题如图3所示。

图3中圆圈点代表了区域配网中的各业务路由，节点1为出发路由，依次无重复的经过2-5个节点，实现最终的路由分配。为避免分配后的路由路径产生环路的现象，将路由分配结果作为输入变量代入到分支限界算法中，最终由算法返回的路径，即为实际的业务路由分配方法，最终实现了区域配网业务路由的分配。

2 仿真实验与结果分析

2.1 实验准备

为验证基于Q Learning算法的区域配网业务路由分配方法的应用性能，利用如下仿真实验进行验证。仿真实验参数设置情况如表3所示。

实验指标分别为配网业务数据转发过程的链路占用率和平均丢包率。

为突出实验结果的对比性，将基于Q Learning算法的区域配网业务路由分配方法作为实验组，将文献[3]中的基于频谱位示图的联合优化路由频谱分配方法和文献[4]中的电力传输网络的动态波道均衡路由分配方法作为对比组，共同完成性能对比实验。

2.2 实验结果统计及分析

将Q值设置为1，改变网络中传输流的数量，观察在传输流数量逐渐增加的情况下，三种分配方法的链路占用率，统计结果如图4所示。

由图4可知，三种分配方法的最大链路占用率会随着网络中的传输流数的增加而逐渐加加。这是因为网络中的传输流数量越多，每条链路被占用的可能性越高，链路的最大占用率也就增大。由图4实验结果图可知，三种分配方法最大链路占用率相差很大，文献[3]方法的链路平均最大占用率为0.45左右，文献[4]方法的链路平均最大占用率为0.4左右，而本方法的链路最大占用率在0.35以下。由此可以证明，基于Q Learning算法的区域配网业务路由分配方法具有较低的链条占用率。

在此基础上，保持与上述实验相同的传输流数量变化情况，比较三种分配方法下的信道丢包率，实验结果如表4所示。

从表5可以看出，随着传输流数量的增加，三种分配方法在网络中的平均丢包率也在逐渐变大。这是因为传输流增加导致的网络中链路之间干扰严重，使传输流丢包愈加严重。由表4实验结果图可知，文献[3]方法的最大丢包率为4.1%，文献[4]方法的最大丢包率为3.6%，而本文方法的最大丢包率为2.4%。相比之下，本文方法的最大丢包率更小。

综上所述：与两种传统分配方法相比，本文方法下的链路占用率小，配网业务数据转发过程的信道丢包率也较小，可以在少占用配网中的链路情况下，减少网络链路之间的干扰和传输流的丢包情况，有效实现区域配网中业务路由的分配。

3 结 论

在配网规模日益扩大的同时，电力信息化的程度也日益加深，电网与电力通信之间的联系越来越密切。研究基于Q Learning算法的区域配网业务路由分配方法，可以增提高配的工作效率，合理化分配业务路由、减少链路占用率，能够有效避免在配网资源传输中出现丢包率过高的现象。因此，本研究提出的分配方法对研究区域配网业务路由分配问题有着进步性的意义。

参考文献

[1] 刘钰，熊兰，肖丹，等.基于业务重要度的电力通信路由系统可靠性分析[J].电测与仪表，2017，54（12）：34-41.

[2] 张乐平，金鑫，胡珊珊，等.基于动态Skyline计算的智能电网分布式路由算法[J].科技通报，2018，34（8）：135-139.

[3] 张曙光，李正贤，王伟.基于频谱位示图的联合优化路由频谱分配算法[J].激光与光电子学进展，2019，56（13）：48-52.

[4] 孙毅，周爽，陆俊，等.电力骨干光传输网络的动态波道均衡路由波长分配算法[J].电力系统自动化，2016，40（13）：114-120.

[5] 薛俏，丁慧霞，张庚，等.基于Q Learning算法的电力通信业务路由规划[J].光学与光电技术，2019，17（4）：51-56.

[6] 艾欣，谭骞，吕志鹏，等.VSG结合无源型能量路由器及其在微网中的应用[J].华北电力大学学报（自然科学版），2018，45（3）：1-9.

[7] 王晓雷，陈云杰，王琛，等.基于Q-learning的虚拟网络功能调度方法[J].计算机工程，2019，45（2）：64-69.

[8] 秦峰，曾浩，林开东.流量自适应分配的多汇聚节点LLN路由协议[J].计算机工程与设计，2019，40（8）：2128-2133.

[9] 姚玉坤，劉江兵，李小勇，等.LLN中基于环路避免的高效路由修复算法[J].系统工程与电子技术，2018，40（5）：1135-1141.

[10]涂山山，于金亮，孟远，等.面向5G雾计算中基于Q-learning的安全中继节点选择方法[J].电信科学，2019，35（7）：60-68.

[11]耿海军，尹霞.一种基于iSPF的下游路径规则实现方法[J].计算机工程，2019，45（6）：103-107.

[12]孙方楠，梁后健，张课，等.基于改进遗传算法的电力通信网路由优化研究[J].自动化与仪器仪表，2018（6）：25-28.

[13]万谦，刘玮，徐龙龙，等.基于Q-learning的不确定环境BDI Agent最优策略规划研究[J].计算机工程与科学，2019，41（1）：166-172.

[14]孙严智，刘旋，刘宇明，等.遗传算法电力通信网关键业务备选路由配置[J].云南电力技术，2017，45（1）：113-117.

[15]王鹏辉，张宁，肖明明.基于节点重要度的路由选择与频谱分配算法[J].计算机工程与应用，2019，55（13）：106-111.