基于改进遗传算法的电力系统保护CPS关键业务路由优化

A CPS Key Service Routing Optimization Approach of Power System Protection Based on Improved Genetic Algorithm

摘要: 电力CPS (Cyber-Physical System, 信息物理融合系统)是智能电网的重要特征之一。针对当前，电力CPS中系统保护信息空间对电力系统空间影响的研究还相对较少，因此需要重点研究以解决其在电力的安全稳定可靠运行问题。本文针对系统保护这一智能电网中的代表性的CPS，提出了改进的遗传算法解决通信链路中断后对于网络业务路由路径的优化问题。该方法首先进行跨空间的风险传播影响分析，然后通过对电网潮流影响、业务平均时延、全网均衡度等指标进行系统保护网络通信链路中断对于电网产生的影响分析，最后通过实例仿真实验表明该解决方法在满足时延和电网潮流影响的基础上，优化后的路径比原始路径在全网业务均衡度指标上提升了49%，保障了网络可靠性。

Abstract: CPS (Cyber-Physical System) of power system is an important feature of smart grid. At present, there is relatively little research on the spatial impact of the system protection information space on the power system in the CPS. Therefore, it is necessary to focus on research to solve the problems of safe, stable and reliable operation in power. This paper proposes an improved genetic algorithm to solve the optimization problem of the network service routing path after the communication link is interrupted. This method first analyzes the impact of cross-space risk propagation, and then analyzes the influence of net-work communication link interruptions on the power grid through impacts such as power flow impact, average service latency, and the whole network services balance, and finally through an example simulation experiment. It shows that the proposed solution can improve the reliability of the network by ensuring that the optimized path is 49% better than the original path in the service metrics of the entire network, based on the effect of delay and the impact of grid power flow.

1. 引言

信息物理融合系统(cyber-physical system, CPS)是综合计算、网络和物理环境的多维复杂系统。通过计算、通信与控制技术的有机融合与深度协作，实现大型工程系统的实时感知、动态控制和信息服务 [1] 。

智能电网中的系统保护业务及系统，是典型的信息物理融合系统代表 [2] 。该CPS可以划分为物理空间和信息空间，其中物理空间包含了多个相互联系的物理实体(如智能电网中的电源、负荷、输电线路等)，而信息空间则包含了各类监控设备、计算设备和通信网络。其中信息环节的可靠性问题可能导致物理系统的运行风险 [3] 。当系统保护信息空间发生故障时将影响到电网的安全运行，因此需要掌握信息空间的安全程度，分析风险影响，并提出相应的优化策略来确保信息空间和电网系统的稳定可靠运行。鉴于此，对于电力CPS的信息空间进行风险评估具有重要意义 [4] 。

在电力CPS中，电力系统空间和信息系统空间中的风险都有可能导致其发生停电事故。文献 [5] 以变电站通信系统为研究对象，采用故障树分析法对系统的可靠性进行了分析和预测，但该方法仅能评估通信系统的可靠性，无法分析通信系统失效对电力系统运行状态的影响。文献 [6] 分析了信息系统对电力系统可靠性的影响，构建了由信息系统功能、一次系统元件及信息电力作用关系组成的系统可靠性模型。总之，现有的研究大多关注电力空间的风险及其故障传播机制方式 [7] ，对信息空间可能带来的风险的研究还相对较少。因此需要重点研究以解决其在电力CPS中面临的安全稳定可靠运行问题。

针对上述问题，本文首先分析了系统保护专网通信链路中断对于电力CPS的影响，并进一步以电网潮流和网络业务加权影响风险值最小的路由优化为目标，提出利用改进的遗传算法重新规划信息空间通信链路中断后的业务路由策略，从而降低网络的运行风险。

2. 系统保护通信网通信链路中断对电力CPS的影响分析

2.1. 跨空间风险传播影响风险

系统保护主要是针对电力系统中跨区互联大电网安稳运行所采取的一种综合防御体系，有控制主站，协控子站和执行站3部分构成。相应的通信系统有各级子站的SDH设备，通信通道，通信子站和通信网络组成，一般采用树形或者网状结构，可以实现区域内和区域间的信息交互 [8] 。

在电力系统保护CPS中，电力空间和信息空间之间有着广泛的交互，如图1所示。信息空间中的中断风险有可能传递到电力空间中并导致误动、拒动等电力影响 [9] 。

Figure 1. Interaction between information space and power space

图1. 信息空间与电力空间交互

跨空间风险传播影响包括信息空间对电力空间的直接影响和间接影响。设跨空间风险传递概率为 ，本文在此进行简单化处理，只考虑直接影响，未考虑间接影响的因素。

在研究路由问题时，网络可表示成无向加权图 $G\left(V,E\right)$ ，其中V表示节点集，E表示连接节点的通信链路集。源节点和目的节点分别用S和D表示，每个链路的连接用 $A_{ij}$ 表示，定义如下：

$\{\begin{array}{l}{A}_{ij}\ne 0节点i到节点j的时延为A_{ij}\\ A_{ij}=0节点i到节点j的路径不存在\end{array}$

在本文中通信链路中断会引起电网中的潮流变化，也会对网络业务的平均时延和业务均衡度产生影响。设该网络中中断的链路个数为，下面将具体分析由通信链路中断所产生的风险影响值。

2.2. 对电网潮流的影响

系统保护通信链路中断造成的信息空间的变化会引起电力空间的变化。而电力设备的变化会引起电力系统潮流发生变化，从而影响电网可靠性。若某条线路上所流过的功率超过限值，则该条线路也会退出运行。以电力系统中常见的失负荷概率(Loss of Load Probability, LOLP)作为电网可靠性指标进行分析 [10] 。

$LOLP={\displaystyle \underset{i\in S}{\sum }{p}_i}$ (1)

在式(1)中：S为系统中所有负荷削减状态的集合， $p_i$ 为系统在状态i的概率。则对电网潮流的影响风险值 $I_1=L_{OLP}$ 。

2.3. 对网络业务的影响

通信链路上承载了电网信息交互业务，其中如继电保护、稳定控制等重要业务，通信链路的中断会对其上传输的业务造成影响。对业务的影响将从业务平均通信时延代价和全网业务均衡度两个角度进行分析。

2.3.1. 业务平均时延代价

通常情况下为了预防事故发生，传输网上的业务都配置了主用路由和备用路由，当发生链路中断时，该链路上承载的业务均由主用路由切换到备用路由，则业务传输时延会发生变化，产生传输代价 [11] 。

对于链路上承载的所有具备备用路径的业务而言，都会切换备用路径产生传输代价，则可以得到中断通信链路上承载业务的平均时延代价：

$\bar{T}={\displaystyle \underset{i=1}{\overset{L}{\sum }}{T}_i}/L$ (2)

其中，L为网络中承载的业务数目， $T_i$ 是业务i的时延， $\bar{T}$ 为全网业务的平均通信代价。则通信链路中断对网络业务中的业务平均时延的影响风险值 $I_2=\bar{T}$ 。

2.3.2. 业务均衡度代价

若由原先的主用路由切换到备用路由，每条链路上承载的业务数量会发生变化，则全网业务均衡度也将发生改变。定义全网业务均衡度为BD [12] 。

$\bar{L}={\displaystyle \underset{i=1}{\overset{m}{\sum }}{L}_i}/m$ (3)

$BD=\sqrt{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{\left(L_i-\bar{L}\right)}^2}/m}$ (4)

其中， $L_i$ 为第i条链路上承载的业务数目， $\bar{L}$ 为链路的平均承载业务数量，m为网络中总链路数。则通信链路中断对网络业务中的业务均衡度的影响风险值 $I_3=BD$ 。

3. 基于改进遗传算法的系统保护业务路由优化策略

3.1. 数学模型

信息空间中通信链路的中断影响风险值为通信链路中断发生对电力空间造成影响的概率与中断影响值的乘积 [13] 。即：

$R=K\cdot P\cdot I$ (5)

式(5)中，R为通信链路中断后影响风险综合值，K为跨空间风险传递概率，P为通信链路中断概率，I为中断影响值。I包括三部分，对电网潮流的影响风险值 $I_1$ ，对网络业务中的业务平均时延影响风险值 $I_2$ ，对业务均衡度的影响风险值 $I_3$ [14] 。

在分析通信链路中断对业务影响时，我们考虑了对业务路由的影响和对电网潮流的影响，则以对电网潮流影响值和业务影响风险值加权和最小化为优化策略的目标函数。为了使业务能够均匀的分布在网络上，需要对各边的业务容量进行一定的限制，同时对于线路上所流过的功率限值也进行了一定的限制。为此构造电力CPS网络路由优化策略的目标函数：

$F=\min R=K\cdot P\cdot \min \left(\alpha I_1+\beta I_2+\delta I_3\right)$

$s.t.\{\begin{array}{l}{T}_i<T_{\max }\\ L_i<L_{\max }\\ \left|d_{i,j}\right|<P_{i,j}^{\max }\end{array}$ (6)

其中 $\alpha$ ， $\beta$ ， $\delta$ 为影响因素权重常数，从目标函数可以看出，即满足电网潮流影响、平均时延和业务均衡度的情况下，使F取得最小值。

由于通信链路中断对电网潮流和网络业务运行造成的影响程度可能存在不同，我们通过层次分析法 [15] 构建比较矩阵、计算矩阵的特征向量来确定每个因素的权重，并通过验证一致性指标来保证权重的可信度。

3.2. 改进遗传算法

针对上述问题本文采用如图2所示的改进遗传算法步骤进行求解，在编码机制和选择机制上，依据业务路径的特征进行了适应性修改，具体如下。

3.2.1. 编码机制

染色体编码即为从源节点到目的节点的队列组成，如某业务从源节点S到目的节点D的一个染色体编码为“ $S{N}_1{N}_2\cdots N_{K}D$ ”。染色体编码的第一位置基因(节点)是业务源节点，第二位置基因是从与业务源节点连接的其它节点中随机选择或启发式选择。选择的节点从节点集V中删除，以避免重复选择。然后重复此过程直至到达业务目的节点 [16] 。

Figure 2. The steps of improved genetic algorithm

图2. 改进遗传算法步骤

3.2.2. 初始化种群

通过最大时延 $T_{\max }$ 约束去掉不满足时延要求的链路，这样可以加快搜索速度。然后对拓扑结构图进行路径编码，最后随机选择N条路径，得到N个初始化种群。

3.2.3. 适应度函数

根据适应度函数可以区分种群中个体的优劣，适应度值越大说明个体越优秀。本文建立以下适应度函数：

$fitness=\frac{1}{F}=\frac{1}{\alpha I_1+\beta I_2+\delta I_3}$ (7)

因为所求F越小越接近问题最优解，则采用倒数的形式以满足适应度 $fitness$ 越大的条件。

3.2.4. 选择操作

假设种群数量为N (为方便后续的交叉和变异操作，N取偶数)，则将种群分为两组并分别进行适应度对比，留下适应度较高的个体。此时个体数量为0.5 N，再进行一次选择操作，此时个体数量为0.25 N。然后通过“轮盘赌选择”从本代的N个个体中选择0.75 N个个体。与通过最佳保留选择出的0.25 N个个体组成新的N个个体进行后续操作。

3.2.5. 交叉操作

交叉操作是指按交叉概率 $P_c$ 随机从亲代群体中选择两个个体，将两个亲代个体的部分结构相互交换，生成两个新的子代个体。图3中的 $N_2$ 和 $N_5$ 是两个公共节点，随机选择 $N_2$ 作为交叉点。

Figure 3. A schematic diagram of the crossover operation

图3. 交叉操作示意图

3.2.6. 变异操作

变异操作以一个很小的变异概率 $P_m$ 改变染色体上某些基因，找回较好的基因。图4为变异操作过程，从染色体中随机选择一个基因(节点 $N_2$ )为变异点，从业务源节点到变异点的基因(节点)保持不变，变异点之后的基因(节点)从相连的基因(节点)中随机选择，直到业务路径目的节点。

4. 仿真验证分析

为了能够验证本文提出的算法有效性，我们通过仿真实例进行分析。采用拓扑示意图共有17个节点，25条通信链路，如图5所示。在其链路上承载了7条业务，分别为{[1,11], [1,16], [2,14], [2,16], [3,13], [4,8], [5,15]}。且其初始路由路径按照Dijkstra算法以时延为权值进行配置。

Figure 4. A schematic diagram of the mutation operation

图4. 变异操作示意图

Figure 5. The power communication network topology

图5. 电力通信网拓扑

我们从该电力CPS的网管设备上读取各种数据，包括各条链路传输时延，链路故障的相关记录等信息。参考 [16] 及从网管系统中得到的链路故障相关记录可知，链路13~14中断概率 $$ ，链路13~17中断概率 $p_2=0.2137$ 。而由文献 [7] 可知未考虑和考虑信息空间故障对电力CPS的失负荷概率 $L_{OLP}$ 影响值如表1所示。

Table 1. Calculation results of load loss probability

表1. 失负荷概率计算结果

由图7的拓扑可得知，该网络为冗余星型网络，即主路由备用路由双备份，各节点之间的路径不唯一。则未考虑信息系统时，电网的失负荷概率为0.0763 = 7.63%。考虑信息系统对电力系统的影响后，失负荷概率为0.0888 = 8.88%。

通信链路的中断可能会引起物理空间发生故障。由于本文风险跨空间传播机制中只考虑直接影响，则跨空间风险影响传递概率取值1。在通信链路中断下会引起电力支路发生故障，会引起电网潮流发生变化。在链路13~14和13~17都中断的情况下，利用上文提出的基于改进的遗传算法的路由优化算法，为受影响的业务重新进行业务路径分配。

在遗传算法中，染色体长度为7，设定初始种群规模为100，迭代次数为500，交叉率 $P_c$ 为0.9，变异率 $P_m$ 为0.055，适应度函数计算时，由2.2节中的权重一致性分析可知，权重 $\alpha =0.8540$ ， $\beta =0.4994$ ， $$ 。

Figure 6. Space distribution of initial population and 500 generations after operation

图6. 初始种群和运行500代后种群分布空间

图6为初始种群和运行500代后种群的分布空间。从结果中可以看出，初始种群由于随机性，种群中染色体的适应度散落在区间[0.9, 1.68]，而在运行500代后，适应度分布范围在[1.78, 2.22]，并且有77%的个体适应度约在2.22。可以看出本文算法对路由优化的有效性。

以业务[2,16]为例，来分别对比采用以时延为权值的Dijkstra算法和本文提出的基于改进的遗传算法进行业务路由路径优化结果，如图7所示。

Figure 7. Route of service routing

图7. 业务路由路径

选取在本次运算中的最优解，可以得到各业务的路径，与初始路径对比如表2所示。

Table 2. Comparison of original service paths and optimized service paths

表2. 原始业务路径和优化后业务路径对比

将本文提出的算法与Dijkstra算法对比的各项指标如图8所示。

Figure 8. Comparative analysis of indicators

图8. 指标对比分析

由表2可以算出，当链路13~14和13~17中断时的信息空间中断对电力CPS的影响风险综合值

由于优化算法同时考虑了三个因素，并且链路中断，可选路径数目变少导致其平均时延比初始路径有所增大，但均能满足时延要求。对于业务均衡度而言，优化后的路径比原始路径减少了49%，有较大程度的减少。由于对三个指标的权重不同，所以在失负荷概率小幅增加的情况下可以看出经过遗传算法优化后的业务路径更加符合实际情况。

图9展示了在本实例中，每次迭代后种群中的最优解。可以看出当最大迭代次数为500代时，运行到150代左右时，路由优化策略产生的最优解已经保持稳定不变，具有良好的收敛性。

5. 结论

本文主要研究了智能电网中，在系统保护CPS中信息空间通信链路的中断对电力CPS产生的影响分析。首先对跨空间的风险传播影响进行分析，然后以电网潮流、业务平均时延、全网业务均衡度为指标

Figure 9. The optimal solution produced by each iteration

图9. 每次迭代产生的最优解

对通信链路中断前后进行对比分析。并在链路中断的条件下，为受影响的链路进行路由路径优化，并采用层次分析法获取各个受到影响因素的权值；进一步根据风险定义，得到链路中断综合风险值。对于受到影响的业务，利用改进的遗传算法以电网潮流影响值、业务平均时延和业务均衡度为约束条件，为其重新分配业务。通过仿真实验，验证了算法的有效性。

但本文仍存在一些未完善的工作，在对跨空间风险传播影响进行分析时进行了简单化处理，只考虑了信息空间对物理空间的直接影响，在后续的研究中需要考虑到综合能源系统中的系统保护的间接影响的因素。同时下一步的研究工作将横向比较不同启发式算法求解路由路径问题的性能，进一步提高算法的效率。

基金项目

2017年国家电网公司总部科技项目：系统保护通信网络技术体制及关键技术研究(Grant No. SGXT0000ASJS1700054)。