基于负载均衡的电力通信业务路径规划算法

Load Balance Based-Power Communication Service Path Programming Algorithm

摘要: 本文设计一种电力通信业务路径规划算法，有效提高了电力通信业务权重分布的均衡性，降低了路径故障对电力通信业务构成的风险。算法将电力通信业务权重均衡分布作为目标，首先，在跳数小于门限值的节点中，为业务选择可行路径。然后，选择距离最小的ｋ条路径，作为业务的候选路径。最后，从备选路径中，选择业务权重分布均衡的路径，作为业务分配路径，从而保障业务权重分布的均衡性。基于负载均衡的电力通信业务路径规划算法(LBB-PCSPP, Load Balance Based-Power Communication Service Path Programming algorithm)能够有效均衡电力通信业务权重分布，避免电力通信业务向少数路径聚集的现象，从而降低路径故障对电力通信业务构成的风险。

Abstract: This paper designs a power communication service path planning algorithm, which effectively improves the balance of power communication service weight distribution, and reduces the risk of path fault to power communication service. This algorithm takes the balanced weight distribution of power communication service as goal. Firstly, in the nodes whose hops are less than threshold value, a feasible path is selected for service. Then, K path with the smallest distance as candidate path of business is chosen. Finally, the path with balanced distribution of service weights is selected as business allocation path from candidate path, so as to ensure balanced distribution of business weights.

1. 引言

随着智能电网的快速发展，越来越多的智能电力终端、传感器设备、便携式终端被部署在电力通信网中，为电网运营者以及用户提供诸如监测、控制、信息采集、智能用电等服务，电力系统呈现众多子系统间协同通信日益频繁的特点。大量业务需要部署到网络中去，如何合理的规划电力通信业务路径，降低业务通信风险成为保障电力系统稳定运行的重要问题之一。然而，现有的路径规划算法存在两类问题，一类，采用最短路径选取路径策略的算法，会导致部分路径负担过重的问题；另一类，采用负载均衡策略的算法以带宽控制业务路径分配，依然难以避免重要业务过于集中于某条路径的问题，亟需设计针对电力通信特点业务路径规划算法 [1] [2] [3] [4] [5] 。

针对上述问题，基于负载均衡的电力通信业务路径规划算法(LBB-PCSPP, Load Balance Based-Power Communication Service Path Programming algorithm)，首先，在跳数小于门限值的节点中，为业务选择可行路径。其次，选择距离最小的ｋ条路径，作为业务的候选路径。然后，从备选路径中，选择业务权重分布均衡的路径，作为业务分配路径，从而保障业务权重分布的均衡性。.最后，通过实例验证了算法的有效性。

2. 问题模型

2.1. 问题描述

电力通信部门在业务部署过程中，主要考虑路径最短问题，将导致大量电力通信业务向少数几条路径聚集的现象，一旦这些路径出现故障，将导致大量业务中断。因此，在规划电力通信业务路径的过程中，考虑业务权重分布的均衡性问题，能够降低大量电力通信业务同时中断的风险，具有重要的现实意义 [6] [7] 。

2.2. 问题处理流程

电力通信业务路径通过 $BuildPath\left(G\left(N,E\right)\right)$ 算法予以规划，通过跳数和路径上的业务权重选取业务的可行路径，从可行路径中选取ｋ条距离最短路径作为备选路径(距离由业务权重计算)，再从备选路径中选出业务权重分布均衡的路径作为业务规划路径。该算法能够有效解决，业务向少数路径聚集的问题，从而降低路径故障造成的业务风险。 $BuildPath\left(G\left(N,E\right)\right)$ 算法通过三个算法 $InitPath\left(G\left(N,E\right)\right)$ 、 $SelectNextNode\left(n_j\right)$ 、 $SetService\left(n_j,P\right)$ 分别按跳数和最短距离选择可行路径、k条备选路径和业务路径。

3. 基于负载均衡的电力通信业务路径规划算法

本算法综合考虑最短路径算法和负载均衡算法的特点，将业务重要度融入路径规划之中，算法分为4部分：设 $G\left(N,E\right)$ 为电力通信网的拓扑结构， $BuildPath\left(G\left(N,E\right)\right)$ 用于计算业务的部署路径， $InitPath\left(G\left(N,E\right)\right)$ 用于计算节点的路径集合， $SelectNextNode\left(n_j\right)$ 用于计算k条备选路径集合， $SetService\left(n_j,P\right)$ 用于计算业务路径。

3.1. 路径规划算法

$BuildPath\left(G\left(N,E\right)\right)$ 从节点 $n_i\in N$ 的邻节点计算可行路径和候选路径。随后，从候选路径中选择业务权重分布均衡的路径作为业务部署路径，从而保障业务分布的均衡性。其中，业务权重由电力通信业务的安全级别决定，例如：继电保护业务权重为10，办公业务权重为1，A为已分配业务路径集合，B为备选路径集合，C为路径集合，S为备选节点集合， $\alpha$ 为跳数的门限值，例如16。 $InitPath\left(G\left(N,E\right)\right)$ 将与节点 $n_i$ 距离最小的节点放入业务路径集合A，其中，距离是 $n_i$ 每个邻节点上部署的业务权重。 $SelectNextNode\left(n_j\right)$ 遍历 $n_j$ 的邻节点，从 $n_j$ 的可行路径中，选择k条业务权重最低的路径，作为备选路径。 $SetService\left(n_j,P\right)$ 从k个备选路径中，选择业务权重分布均衡的路径，作为业务分配路径，从而保障业务权重分布的均衡性。

$BuildPath\left(G\left(N,E\right)\right)$ 算法流程如图1所示：

步骤1：开始

步骤2：设置每个通信节点 $n_i$ 上的业务权重为零， $n_i\in G\left(N,E\right)$ ；

步骤3：设置通信节点之间的跳数为0， $jum{p}_{ij}=0$ ；

步骤4： $InitPath\left(G\left(N,E\right)\right)\to A$ ，初始化业务路径分配；

步骤5： $SetService\left(center,A\right)$ ，计算业务路径；

步骤6：；

步骤7：如果 $Temp\ne \varphi$ ，转步骤8，否则，转步骤20；

步骤8：如果 $G\left(N,E\right)\ne \varphi$ ，转步骤9，否则，转步骤19；

步骤9：找出距离center最近的节点 $n_i$ ；

步骤10： $G\left(N,E\right)/\left\{n_i\right\}\to G\left(N,E\right)$ ；

步骤11： $SelectNextNode\left(n_i,C\right)\to B$ ；

步骤12：如果 $\left|B\right|=k\vee \left(B\ne \varphi \wedge jum{p}_{ij}=\alpha \right)\vee center\in B$ ，转步骤13，否则，转步骤15；

步骤13： $SetService\left(n_i,B\right)$ ；

步骤14： $C\cup \left\{n_i\right\}\to C$ ，转步骤8；

步骤15：如果 $jum{p}_{ij}<\alpha$ ，转步骤16，否则，转步骤18；

步骤16： $jum{p}_{ij}=jum{p}_{ij}+1$ ；

Figure 1. algorithm flow chart

图1. $BuildPath\left(G\left(N,E\right)\right)$ 算法流程图

步骤17： $Temp\cup \left\{n_i\right\}\to Temp$ ，转步骤8；

步骤18： $n_i$ 不能分配业务，转步骤8；

步骤19： $Temp\to G\left(N,E\right)$ ，转步骤7；

步骤20：结束。

3.2. 可行路径选择

在选择可行路径选择的过程中，以跳数最短为决策条件，设计启发式搜索算法，遍历center的每个邻节点，找出距离center最近的邻节点，将其放入备选集合，以此寻找跳数最短路径。这样可以降低业务的传送时间，以适应电力通信快速反应的特点。

Figure 2. $InitPath\left(G\left(N,E\right)\right)$ algorithm flow chart

图2. $InitPath\left(G\left(N,E\right)\right)$ 算法流程图

$InitPath\left(G\left(N,E\right)\right)$ 算法流程如图2所示：

步骤1：开始；

步骤2： $\varphi \to A$ ；

步骤3：如果center的每个邻节点被遍历，转步骤8，否则，转步骤4；

步骤4：D为center的邻节点集；

步骤5：如果 $D\ne \varphi$ ，转步骤6，否则，转步骤3；

步骤6：找到距离center最近的节点 $n_i$ ；

步骤7： $A\cup \left\{n_i\right\}\to A$ ；

步骤8：返回A；

步骤9：结束。

3.3. 备选路径选择

在选择备选路径的过程中，从可行路径集合中，以业务权重为决策条件，设计启发式搜索算法，寻找权重最低的k条路径，作为备选路径。这样设计能够考虑较小通信时延的基础上，降低权值较大的重要业务向某条路径聚集的现象。

$SelectNextNode\left(n_j\right)$ 算法流程如图3所示：

步骤1：开始；

步骤2： $\varphi \to S$ ；

步骤3：如果已遍历节点 $n_j$ 的邻节点，转步骤8，否则，转步骤4；

步骤4：将到 $n_j$ 的跳数小于门限值的节点 $n_i$ 放入A， $n_i\to A$ ；

步骤5：将A中与 $n_j$ 距离最近的节点 $n_i$ 存入路径C， $n_i\to C$ ；

步骤6：将C中业务权重最低的 $n_j$ 的k条路径放入集合B中， $n_i\to B$ ；

步骤7： $S\cup C\to S$ ，转步骤3；

步骤8：返回S；

步骤9：结束。

Figure 3. $SelectNextNode\left(n_j\right)$ algorithm flow chart

图3. $SelectNextNode\left(n_j\right)$ 算法流程图

3.4. 业务路径筛选

在筛选业务路径的过程中，从备选路径中，以路径段业务重要度分布均衡为决策条件，设计启发式算法，寻找业务分布最均衡的路径，作为业务路径。这样设计能够同时考虑通信时延较小和业务权重分布均衡的特性，以此避免重要业务集中的现象。

Figure 4. $SetService\left(n_j,P\right)$ algorithm flow chart

图4. $SetService\left(n_j,P\right)$ 算法流程图

$SetService\left(n_j,P\right)$ 算法流程如图4所示：

步骤1：开始；

步骤2： $\varphi \to S$ ；

步骤3：如果已遍历P (P为 $n_j$ 的备选路径集合)中的节点，转步骤5，否则，转步骤4；

步骤4：从 $p_i\subset P$ ( $p_i$ 为 $n_j$ 的一条可选路径)中选择业务权重最大的节点 $n_i$ 放入集合S中， $S\cup \left\{n_i\right\}\to S$ ，转步骤3；

步骤5：从S中选择最小 $n_{\min }$ 对应的路径，部署业务；

步骤6：结束。

4. 实例分析

下面结合实例说明：

图5(a)~图5(c)展示方法的结果：

Figure 5. Comparison of business deployment results

图5. 业务部署结果对比

图5中，节点上的数字表示业务权重，(a)为已经部署业务的权重分布，(b)和(c)分别为按照最短路径算法和 $BuildPath\left(G\left(N,E\right)\right)$ 算法部署业务的结果，按照本文设计的算法得到的业务权重分布更加均衡。

5. 结束语

本文设计的基于负载均衡的电力通信业务路径规划算法，有效提高了电力通信业务权重分布的均衡性，降低了路径故障对电力通信业务构成的风险。本算法将电力通信业务权重均衡分布作为目标。首先，在跳数小于门限值的节点中，为业务选择可行路径。然后，选择距离最小的k条路径，作为业务的候选路径。最后，从备选路径中，选择业务权重分布均衡的路径，作为业务分配路径，从而保障业务权重分布的均衡性。 $BuildPath\left(G\left(N,E\right)\right)$ 算法那能够有效均衡电力通信业务权重分布，避免电力通信业务向少数路径聚集的现象，从而降低路径故障对电力通信业务构成的风险。

基金项目

国网江苏省电力有限公司重点科技项目资助(项目编号：J2018066)。