基于节点最大剩余容量的改进负荷再分配策略

王立夫， 李 欢， 赵国涛

(东北大学秦皇岛分校 控制工程学院， 河北 秦皇岛 066004)

在复杂网络中当一个节点受到扰动出现故障或受到攻击时，有可能会使网络无法正常运行，更为严重的后果是导致整个网络瘫痪.类似于网络中出现的这种现象将其称作复杂网络的级联故障，有时也被称为“雪崩效应”.这种现象在现实网络中非常常见，例如发生在美国、加拿大、意大利、印度、中国等国家的数次大规模停电[1]；同时，还包括互联网的崩溃[2]以及一些大城市频繁发生的交通堵塞等现象，都是由于网络中的节点出现故障或遭受攻击导致网络出现大规模的级联故障.因此，近几年来对于复杂网络的级联故障的研究受国内外学者的广泛关注[3-4].

当网络发生故障时，由于负荷的再次分配，使负荷具有一定的流动性，不同的负荷分配方式对减小网络的规模和网络的鲁棒性产生的效果是不同的[5-7]，因此对于故障节点的负荷在网络中是如何分配，很多学者也进行了相关的研究.Zhang等，Liu等[8-9]在相依网络的级联故障中在考虑了节点的超负荷故障和相依故障基础上，提出了一种冗余设计的思想，通过对一些重要的节点实施备份来缩小级联故障的范围，并且在节点备份的基础上又进行了优化，使系统的可控性和鲁棒性均得到了很好的提升，但是采用节点备份和边备份导致网络的成本较高，代价较大.若在负荷分配的研究过程中不考虑可分配节点在接收负荷之后所导致节点存在满载和超负荷的情况[10-11]，那么将会导致级联故障的大规模蔓延.

因此本文在前人所做工作的基础之上，考虑到节点自身的剩余容量信息，提出了一种新的负荷分配方式，该方法可以有效避免节点满载或超负荷的情况，阻止级联故障的蔓延.另外本文考虑了负荷分配时，路径长度对负荷分配的影响，使复杂网络能够有效地抵御级联故障给网络所带来的影响.

1 级联故障模型

在许多基础设施网络中，例如交通网、通信网等网络，节点的负荷与度值存在着紧密的联系,即度值越大，负荷则越大，所以本文也将采用度来定义网络节点的初始负荷，如式(1)所示:

L0(vi)=ρ×k(vi)τ，i=1,2,…,N

(1)

其中，ρ，τ为决定网络负荷大小的参数.

在复杂网络模型中，一个节点容量的大小反映了它能够处理额外负荷的能力.定义网络节点vi的初始容量为[3]

C0(vi)=(1+a)L0(vi)

(2)

其中，a>0为网络的容忍参数，a的值决定了网络容量的大小.当网络中的节点接收了一部分来自外部的额外负荷之后，网络节点的负荷会增加，接收负荷的节点可能会出现满载、超负荷、或未满载三种情况.当节点vj接收到来自节点vi的负荷L(vi)后，节点vj剩余容量C(vj)为

我国于2018 年3 月17 日由国务院办公厅印发了《科学数据管理办法》（以下简称《办法》），从职责、科学数据采集、汇交与保存、共享与利用、保密与安全等方面对科学数据管理与共享进行了规范。其中，第四章主要对科学数据的共享与利用进行了规范。《科学数据管理办法》解读可从科技部基础研究司司长叶玉江和国家科技基础条件平台中心副主任王瑞丹对《办法》提出的具体措施中体现。《办法》第十九条、二十条、二十一条、二十二条、二十三、二十四条等对科学数据的共享利用相关问题进行了规定。

C(vj)=C0(vj)-L0(vj)

(3)

其中:C0(vj)为节点vj的初始容量；L0(vj)为节点vj的初始负荷；C(vj)为节点vj的剩余容量.当C(vj)>0时，表示节点vj未满载；当C(vj)<0时，表示节点vj超负荷；当C(vj)=0时，表示节点vj满载.

当复杂网络中的某个节点发生故障时，可以按照最近邻负荷分配策略[11](nearest neighbor load distribution strategy，NNL策略)将失效节点本身所具有的负荷按照比例分配给近邻节点.当节点vi发生故障时，它的负荷量为L0(vi)，分配给邻居节点vj的比例Pij如式(4)所示：

(4)

L(vj)=L0(vj)+Pij×L0(vi)

(5)

在许多实际的网络中，当网络遭受蓄意攻击或出现随机故障时，发生在某个节点上的故障会因为节点之间的连接关系影响到其他的节点，最终导致整个网络无法正常运行甚至是崩溃.

图1为初始情况下网络的拓扑结构图.当网络中的1号节点出现故障，1号节点的负荷需要选择其邻居节点(2号、3号和4号节点)按照式(5)进行分配，1号节点失效以后与1号节点相连的边会从网络中脱离，如图2所示.2号，3号和4号节点由于接收了额外的负荷导致自身的负荷超过了其容量成为了失效节点，如图3所示.4号节点失效之后会选择邻居节点(5号，7号节点)按照上述过程进行分配，最终使网络崩溃，如图4所示.

由图1可见，当故障节点具有较大负荷时，采用最近邻负荷分配策略会存在大量的失效节点的情况，其原因是在负荷分配时只考虑了故障节点近邻节点的剩余容量，未考虑在负荷分配时出现的节点满载和超负荷状况，使网络产生了大量的失效节点.基于这种现象，本文提出了一种基于节点最大剩余容量的负荷再分配策略，在负荷分配时考虑了节点剩余容量的大小，避免出现满载和超负荷现象.

2 分配策略

当网络中的某一重要节点失效时，由于网络节点的负荷具有流动性，故障节点的负荷会按照一定规则分配到其他节点，分配时不仅限于其邻居节点.本文在故障节点负荷分配时，考虑从故障节点的邻居节点中选择剩余容量最大的节点作为负荷分配的首选节点，按照一定比例分配给这个节点，然后再在这个节点的邻居节点中再找剩余容量最大的节点进行分配，直至将全部负荷分配结束.本文将此分配方式称为基于最大剩余容量的负荷再分配方式(improved load re-allocation strategy based on maximum residual capacity of nodes，IBMRC策略).负荷分配的具体步骤如下：

1) 网络初始化：复杂网络的初始容量为C0(vj)(j=1,2,…,N)，初始负荷为L0(vj)(j=1,2,…,N).

3) 选择分配节点：节点vi有m个邻居节点，负荷分配首先选择其邻居节点中剩余容量最大的节点vl(迭代变量为l，l=1),即

C(vl)={max(C(vj)),j=1,2,…,m}.

注：第一次分配时剩余容量最大节点为初始容量减去初始负荷最大的节点，即

C(vl)=max{(C0(vj)-L0(vj)),j=1,2,…,m}

4) 负荷分配：分配给节点vl的负荷为b×C(vl)，则分配后节点vl的负荷为

L(vl)=L0(vl)+b×C(vl)

(6)

其中，b∈(0,1]，为可调参数，决定分配后节点是否满载.节点vl在避免节点满载的情况下只接收故障节点vi的一部分负荷，b越接近于1节点vl剩余容量越少，当b=1时，vl剩余容量为0，正好满载.

5) 故障节点剩余负荷：故障节点vi还需要分配的负荷为

L(vi)=L0(vi)-b×C(vl) .

(7)

6) 判断是否再分配：故障节点vi的剩余负荷L(vi)是否为零，若不为零(i=l，l=i+1)，转步骤3)寻找节点vl的邻居节点中剩余容量最大的节点进行分配.

7) 分配算法结束：当故障节点vi的剩余负荷L(vi)为零时，负荷分配结束.

IBMRC策略的具体流程如图5所示.以图1所示网络为例，分析网络中的节点受到攻击后，负荷分配的具体过程如图6所示，负荷分配比例b设置为0.8.

初始网络的拓扑结构图如图1所示.由图可知,1号节点为网络中负荷最大的节点，当1号节点出现故障时，负荷会选择1号节点的邻居节点中剩余容量最大的节点即4号节点按照式(6)进行分配，分配给4号节点负荷为4，故障节点剩余未分配的负荷按照式(7)计算，结果为14；将剩余负荷重新选择4号节点的邻居节点中剩余容量最大的节点即5号节点按照式(6)进行分配，按照式(7)计算剩余负荷为10；再次将剩余负荷重新选择5号节点的邻居节点中剩余容量最大的节点即8号节点按照式(6)进行分配，按照式(7)计算剩余负荷为0，分配结束.

在考虑路径长度对负荷分配的影响时，分配方式是在IBMRC策略的步骤4)和5)的式(6)和式(7)中引入路径参数d，具体的负荷分配比例如式(8)所示:

(8)

故障节点剩余的负荷为

(9)

其中，b,k为可调参数，可以决定分配负荷的多少.当k=0时，式(8)和式(9)与式(6)和式(7)相同，该分配策略退化为IBMRC策略.

如图1所示的网络，按照考虑路径长度的分配策略进行负荷分配，将负荷分配的最短路径提取出来如图7所示，设置b=0.8,k=1，负荷分配过程如图8所示.

故障节点的负荷按照式(9)进行分配后，每个节点的节点状态如图8所示，网络中未出现满载和超负荷的节点.

3 仿 真

本文提出的负荷分配策略主要是在网络节点出现故障时，故障节点在负荷分配的同时能够有效地避免节点接收额外负荷之后出现满载或超负荷的情况，及时抑制级联故障在网络中的蔓延，本节将对IBMRC策略的有效性进行仿真验证.

3.1 不考虑路径长度的IBMRC策略

由于实际中的大多数基础设施网络较为符合无标度网络的一些特征，因此本文提出的负荷分配策略将选择150个节点的无标度网络进行验证.对网络节点的攻击方式主要有两种——随机攻击和蓄意攻击，不同的攻击方式对网络的影响是不同的.随机攻击即随意攻击网络中的一个节点；蓄意攻击主要是对网络中的关键节点(负荷最大的节点)进行攻击.设定网络的容忍参数a=0.2，参数ρ=1，τ=2，负荷分配参数b=0.6，仿真验证如图9所示.

图9 不同攻击方式在IBMRC策略下对故障节点负荷L的影响
Fig.9 The effect of different attack modes on the loadLof the fault node under the IBMRC strategy

图9中横轴f表示的是接收额外负荷节点数占整个网络节点数的比例，纵轴表示的是故障节点负荷L的变化.两种不同的攻击方式下采用IBMRC策略进行分配最终使故障节点的负荷为零.同时通过两种不同的攻击方式进行对比可以看出蓄意攻击相比随机攻击对网络的影响较大，导致接收额外负荷节点的数量较多，负荷分配的时间过长.因此，本文主要验证网络遭受到蓄意攻击时，在IBMRC策略下研究不同参数对网络节点状态以及负荷的影响.

首先，研究不同的负荷分配参数b值对故障节点负荷的影响.仿真验证如图10所示.当b值逐渐增加时，接收额外负荷的节点数逐渐减少，减少了负荷分配的时间，提升了负荷分配效率，故障节点负荷减少的速度也越来越快.这样趋势的呈现，是因为b值决定了节点接收额外负荷量的多少，b值越大节点接收的额外负荷量则越多，导致故障节点负荷减少的速度越快，接收额外负荷>的节点数也就越少.同时，b值的增加也会对接收额外负荷节点的剩余容量C存在一定的影响，如图11所示.接收额外负荷节点的剩余容量随着b值的增加逐渐减少，但是均在零以上，即接收额外负荷节点的负荷没有超过自身的容量，无失效节点产生.

一个节点接收额外负荷量的多少主要取决于节点容量的大小，节点的容量越大，基于负荷不变的情况下节点的剩余容量则会越大，那么节点根据自身容量信息所能接收的额外负荷量就越多.因此，容忍参数a也会对故障节点的负荷分配存在一定的影响.设定参数ρ=1，τ=2，负荷分配参数b=0.6，与NNL策略进行对比，仿真验证结果如图12所示.

当a值逐渐增加时，在两种分配策略下接收额外负荷节点的剩余容量在逐渐上升.网络采用IBMRC策略进行分配时，接收额外负荷节点的剩余容量在初始情况下大于零，随着a值的增加呈现上升的趋势.在NNL策略下节点的剩余容量随着a值的增加缓慢上升，但均小于零，产生了失效节点.因此，经过对比分析，IBMRC策略相比NNL策略提升网络节点的剩余容量的效果要好.同时，当网络采用IBMRC策略进行负荷分配时，a值的增加，使故障节点的负荷下降得越来越快，接收额外负荷的节点数也越来越少，减少了负荷分配所需的时间，提升了负荷分配效率，如图13所示.

3.2 考虑路径长度的IBMRC策略

网络中的某一重要节点失效时，节点的负荷会沿着其所在的路径进行分配，节点之间的距离越长，节点的损耗就会越多，基于这种情况本文又考虑了路径长度对负荷分配的影响，并且通过仿真做了相关的验证.根据第二节的分析，路径可调参数k也对负荷分配比例存在着一定的影响，因此设定负荷分配参数b=0.6.设定网络的容忍参数a=0.2，参数ρ=1，τ=2，令k从0.1变化来验证k值在考虑路径长度的情况下采用IBMRC策略对网络故障节点负荷以及接收额外负荷节点剩余容量的影响，仿真验证结果如图14，图15所示.

随着路径可调参数k值的逐渐增加，接收额外负荷节点的数量越来越多，故障节点的负荷下降的趋势越来越缓慢，但是节点的剩余容量却得到了提升.造成此现象的原因是路径可调参数k值也对负荷的分配比例存在着一定的影响，k值越小，负荷分配的比例则越大，节点接收的额外负荷会越多，节点的剩余容量也将会减小.但是k值不能过大，在给定的初始条件下，k值过大会导致故障节点的负荷不能在有限的节点数内进行分配，故障节点还存在一部分剩余的负荷.因此，综合以上分析，考虑路径长度的IBMRC策略在网络的关键节点遭受故障时，也能起到较好的效果.

3.3 不考虑路径长度的IBMRC策略(特高压电网)

为了更好地体现IBMRC策略在实际应用中的广泛性，本文选取了由国家电网公司发布的2020年“三华”特高压规划电网图为研究对象，从图论的角度将电网抽象为网络拓扑图，将发电厂、变电厂抽象为节点，电力传输线路抽象为边.最终将该电力网络图抽象为具有55个节点，74条边的网络拓扑结构图.

首先，研究不同负荷分配参数对故障节点负荷的影响，设定容忍参数a=0.2，参数ρ=1，τ=2，仿真验证结果如图16，图17所示.

随着负荷分配参数b值的增加，接收额外负荷节点数占整个网络的比例越来越小，故障节点的负荷量也减少得越来越快.节点接收额外的负荷之后节点的剩余容量均大于零，网络中无超负荷节点.因此，通过调节负荷分配参数可以使特高压电网良好地运行.

设定参数ρ=1，τ=2，负荷分配参数b=0.6，验证容忍参数a对特高压电网负荷分配的影响，如图18，图19所示.当网络容忍参数a的值逐渐增加时，网络采用IBMRC策略时，节点的剩余容量逐渐增加且均大于零，故障节点的负荷也下降得越来越快，接收额外负荷节点的数量占整个网络节点数的比例也越来越小，网络中无失效节点产生，对网络发生的级联故障产生了良好的控制作用.当特高压电网采用NNL策略进行分配时，邻居节点接收了一定的负荷之后导致其负荷量超过了容量，即节点发生了超负荷故障成为了失效节点，按照网络的级联故障机制将会再次进行分配，因此不能很好地控制级联故障的蔓延.

3.4 考虑路径长度的IBMRC策略(特高压电网)

当特高压电网处于正常运行时，线路的路径长度会对网络的负荷传输存在一定的影响.设定初始参数ρ=1，τ=2，容忍参数a=0.2，负荷分配参数b=0.6，令路径调节参数k从0.1开始变化，验证k值对故障节点负荷，以及节点剩余容量的影响，ρ=1，τ=2，仿真验证如图20，图21所示.

随着路径可调参数k值的逐渐增加，故障节点的负荷减少得越来越慢，导致故障节点的负荷在整个网络内无法进行完全分配，还存在剩余负荷，为了避免网络中节点的超负荷故障发生，在实际网络的运行过程中，根据具体情况调节k值的大小.在k值增加的过程中节点的剩余容量均大于零.

在故障节点的负荷完全分配的情况下即保证k值在0.1和0.4之间，网络中无失效节点产生，使网络的级联故障得到了有效的控制。

4 结 语

基于级联故障对网络造成的影响，本文提出了基于节点最大剩余容量的改进负荷再分配策略(IBMRC策略)，并且与前人提出的NNL策略从网络节点剩余容量以及接收额外负荷节点数量的角度作了对比.当网络中负荷最大的节点出现故障时，采用IBMRC策略可以有效地避免接收额外负荷的节点出现超负荷故障，抑制了级联故障的蔓延，相比于NNL的分配策略来说效果有所提升.另外，本文又分析了路径长度对负荷分配的影响，在关键节点出现故障时，IBMRC策略可以通过调节路径参数，使网络的剩余容量空间有所提升，阻止级联故障的蔓延.为了更好地说明该方法在实际生产中的广泛性，本文选取了实际的特高压电网进行仿真，最终IBMRC策略对于虚拟网络和实际的电力网络控制效果大体相似，都起到了良好的控制作用.