负载目标下基于延迟分配的多层级相依网络级联失效模型

张家瑞; 黄健; 高家隆; ZHANG Jiarui; HUANG Jian; GAO Jialong

doi: 10.11887/j.cn.202405009

张家瑞，黄健，高家隆

国防科技大学智能科学学院，湖南长沙 410073

基金项目: 国家自然科学基金资助项目（61906202）

详细信息

作者简介

张家瑞（1995—），男，陕西咸阳人，博士研究生，E-mail: zjr888@stu.xjtu.edu.cn

通讯作者

黄健（1971—），女，浙江绍兴人，研究员，博士，博士生导师，E-mail: nudtjhuang@hotmail.com

中图分类号: TP273

文献标识码: A

文章编号: 1001-2486(2024)05-079-11

Cascading failure model for multi-level interdependent networks based on delay distribution under load target

ZHANG Jiarui ， HUANG Jian ， GAO Jialong

College of Intelligence Science and Technology, National University of Defense Technology, Changsha 410073 , China

摘要

在负载具有目标节点的多层级相依网络中，为了避免大规模级联失效的发生、增加网络鲁棒性、提高负载完成效率，提出一种可调参数的级联失效模型。该模型设置了新的初始负载和节点容量，构建了负载延迟分配机制，在负载分配的异质性和均匀性基础上制定了负载重分配规则。解析分析模型的级联失效条件，并通过WS-BA相依网络进行了仿真实验，结果表明，在网络容量一定条件下，合理调节异质性参数和均匀性参数可以提高网络的鲁棒性和效率。

关键词

负载目标 / 相依网络 / 级联失效 / 负载重分配

Abstract

In the multi-level interdependent network where the target node was under load, in order to prevent the occurrence of large-scale cascading failures, enhance the robustness of the network and improve the efficiency of load completion, a cascading failure model with adjustable parameters was proposed. New initial loads and node capacities were set in this model, a load delay distribution mechanism was constructed and load redistribution rules were formulated on the basis of the heterogeneity and uniformity of load distribution. The cascading failure conditions of this model were analyzed and parsed, and simulation experiments were carried out through the WS-BA interdependent network. The results show that under a certain network capacity, the robustness and efficiency of the network can be improved by reasonably adjusting the heterogeneity and uniformity parameters.

Keywords

load target / interdependent network / cascade failure / load redistribution

1 多层级相依网络模型 2 级联失效模型 2.1 节点状态 2.2 初始负载 2.3 节点限额容量 2.4 负载重分配 3 基于延迟判断的负载重分配 3.1 负载重分配策略 3.1.1 延迟判断 3.1.2 负载分配 3.2 负载重分配流程 4 级联失效模型数值解析 5 实验分析 5.1 网络性能评估指标 5.2 实验验证 5.2.1 初始负载定义的准确性 5.2.2 节点状态对网络的影响 5.2.3 重分配方法的影响 5.2.4 层级的影响 6 结论

现实网络或多或少地与其他网络存在物理依附、信息交换等耦合关系，正是这种网络节点间的相互联系，增加了故障传播的范围和速度^[1-2]。研究相依网络的级联失效模型对设计更健壮的网络系统，以及提高网络的鲁棒性都具有重要意义。

自从Buldyrev等^[3]于2010年发表在Nature上的文章开启了相依网络级联失效的研究浪潮，针对相依网络级联失效的研究越来越多，但大多都是将失效节点的负载平均分配给全局节点，不仅使相依网络建模较为粗糙，而且分配实时性差，难以有效应用。Parshani等^[4]研究了部分相依网络的鲁棒性，但其节点故障后，结论的普适性不强。严玉为等^[5]研究了基于时间序列的网络级联失效模型，虽然考虑了负载的时序关系，但缺少重分配方法的分析。总的来说，针对相依网络的研究集中在对失效节点随依赖关系产生的级联失效的影响分析上，对相依网络负载重分配策略考虑较少。

目前负载重分配策略是负载增量的调整^[6]，大多基于单层网络的研究，针对相依网络的很少，仅有的研究大多也没有考虑负载异质性和相依网络连边的不同，不加区分地进行负载分配，模型过于简化，主要可以归纳为三类方法：①均匀分布^[7]，即将负载均匀分配给多个节点；②依据节点的特征属性来确定分配比例^[8-9]，主要包括按照节点度等特性排序，将负载按比例分配；③根据节点的容量进行分配^[10]，主要根据节点的最大总容量和节点当前的剩余容量的大小分配负载。这三类方法是针对同质的简单相依网络负载重分配问题提出的，暂未考虑以下四个问题：①有部分负载完成后需要发送结果至特定的节点，没有考虑到分配的负载有原始目标节点；②网络中节点都是同质的，节点之间无层级关系；③网络中总负载过高情况下，无法防止网络面临不可避免的崩溃；④负载的异质性。

本文针对包含多层级异质节点的相依网络级联失效模型开展研究，通过不同节点状态构建部分节点的延迟分配机制，在保证负载到达原始目标节点基础上，通过节点层级和负载紧迫度最小化负载分配范围，调节负载分配异质性和均匀性以提高网络的鲁棒性和处理效率。最后，解析分析了网络发生级联失效的临界值，利用WS-BA相依网络进行了实验验证，通过失效节点数量、负载完成时间以及负载完成率三个指标评估了本文所提出的负载重分配策略的有效性。

1 多层级相依网络模型

现实网络中，节点并不会因所依赖节点失效而随之失效，而是节点性能下降，因为还有其他相依赖边以及子网络连边存在，可以维持节点进行信息处理，因此降低了失效节点的数量。

本文设置的相依网络包含两个单层子网络（子网A和子网B），网络包含节点、节点内连边以及子网络间的耦合连边，如图1所示。网络中节点具有个体差异，节点有不同的信息处理能力，以节点层级衡量节点的信息处理能力。因为有向边比无向边具有更广的适用范围，因此设置网络为有向网络。子网A和B具有相互依赖的关系，通过耦合边相连，子网络之间的耦合边为有向边，信息通过耦合边由子网A流向子网B进行处理。子网络内连边为有向边，节点间可以进行单向的信息交互。同时，网络具有层级结构，节点之间具有上下级的隶属关系，低层级节点将本级无法处理的数据发送至高层级节点，在高层级节点处进行信息融合计算，之后高层级节点再将计算后结果分发至低层级节点。

2 级联失效模型

级联失效模型中初始负载和节点容量是构建重分配的基础，负载重分配是关乎网络能否发生级联失效的重要因素。本文所述的多层级相依网络中，关于子网A和子网B中节点的负载和容量的相关定义是类似的，为叙述的清晰与简便，以子网A中节点v^A_i为例进行说明。

图1多层级有向相依网络

Fig.1Multilevel directed dependent network

2.1 节点状态

节点状态是描述节点在当前时间下的工作状态，需要定义不同的状态来对节点和网络进行定性描述。

定义1 网络中的节点状态有三类，包括活跃态、低效态、失效态，且一个节点在任意时刻只能处于其中一种状态。活跃态是指功能正常节点状态；低效态是指只能完成部分功能或承担部分负载的节点状态；失效态是指节点丧失相应功能，不能承担负载。

将不处于活跃态的节点，包括失效态和低效态节点统称为传播态节点。失效态节点要从网络中移除，且所有与失效态节点相连的边同时失效，对网络中该节点、互连边以及耦合边进行删除，该节点上的负载一定要进行重分配。对于低效态节点，承担负载的容量会降低，若节点的实时负载大于节点的负载承担量，也要进行负载的重分配。

2.2 初始负载

很多学者认为节点的初始负载是由节点的介数或节点的度定义的^[11]。一部分观点认为节点的度和初始负载正相关，即节点v^A_i的初始负载L_i=a（k^A_i）^b，其中a和b是可调参数，k^A_i为该节点度值。这是基于局部特性的度量，对于单层同质网络有一定科学性，但没有考虑连边具有不同类型，以及节点具有不同层级。另一部分观点基于节点特性的度量，认为节点的介数中心性度与初始负载相关^[12]，但网络中大部分层级较低的节点负载将等于0，与实际的初始负载不符。

这两种方法并不完全适用于本文所研究的多层级相依网络，要设置合理的节点初始负载，平衡节点内部度和耦合度间的关系。考虑到层级高的节点汇总了来自不同下层节点的信息，信息处理能力大，因此层级也会影响节点的初始负载。本文设置的节点初始负载定义如式（1）所示。

L_{i}^{A} (0) = \frac{μ \cdot D_{A} {(k_{i}^{A} - c_{i}^{A})}^{α}}{D_{A} - d_{i}^{A} + 1} + (1 - μ) {(\frac{c_{i}^{A}}{\sum_{j \in V_{A}, k \in V_{B}} R_{j k}})}^{β}

(1)

其中：

k_{i}^{A}

和

c_{i}^{A}

分别为子网A的内部度和耦合度; R_jk表示经过节点v^A_j、v^B_k之间的最短路径的个数；α和β是可调参数；V_A和V_B分别是子网A和子网B的节点集合；d^A_i表示节点层级，D_A表示子网A中节点总层级，且节点最小层级从1开始；μ∈[0，1]是初始负载的调节参数，节点内部度和耦合度对负载的贡献程度可以通过μ进行调整。

2.3 节点限额容量

网络中节点的能力值表示为该节点最大的承担负载量，也就是节点的容量。节点v^A_i的节点容量正比于其初始负载L^A_i（0），但相依网络中节点能力受到依赖节点的制约，节点容量会随节点状态发生变化^[13]。

现实系统中很多节点受损后并不完全失效，只是部分功能受损。考虑到有节点会出现性能下降而未失效的情况，本文在Motter^[14]提出的“负荷-容量”模型（ML模型）的基础上，定义了节点的限额容量。

定义2 限额容量是对处于活跃态和传播态节点能力的衡量，表示节点在当前时间下可承担的最大负载量，正比于节点的初始负载，比例系数随着节点状态的改变而改变。

当节点的负载不大于该节点的限额容量时，可接受任意负载的分配；当前负载大于限额容量时，可能引发新一轮的负载分配。节点限额容量定义具体如式（2）所示。

C_{i}^{A} = (1 + γ) σ_{i} L_{i}^{A} (0)

(2)

其中：γ是容限系数，可以通过调节初始负载来对节点容量的大小产生影响；节点限额容量不大于节点的设计容量，因此σ_i∈[0，1]是节点的限额系数。

2.4 负载重分配

为了降低级联失效带来网络崩溃的可能性，提高网络的鲁棒性，需要通过合理的负载重分配策略调整传播态节点的负载。

定义3 负载重分配主要是为了解决由节点低效可能引起的网络故障，包括网络中节点的失效移除和节点限额容量降低而导致耦合节点无法完成负载的耦合故障和负载分配后超过节点限额容量的传播故障。

为便于描述多层级相依网络的负载重分配策略，下面先介绍负载分配节点和待分配负载节点的定义。

定义4 负载分配节点是指将无法继续承担的负载分配给其他节点去完成，且处于传播态的节点。

定义5 待分配负载节点是指可以接受来自负载分配节点的负载，且处于活跃态或者低效态的节点。

如图2所示，假设子网A中的红色节点v^A_i失效后，负载被3个绿色的待分配负载节点v^A_j、v^A_j₂和v^A_j₃ 完成一次负载的更新。以节点v^A_j为例，节点更新如式（3）所示。

L_{j}^{A} \to {(L_{j}^{A})}^{'} = L_{j}^{A} + Δ L_{j}^{A}

(3)

其中，ΔL^A_j为节点v^A_j的负载增量，即承担来自负载分配节点v^A_i的负载大小。

图2受攻击节点的单次负载分配过程

Fig.2A load distribution process of the attacked node

同时，当网络中待分配负载节点满足式（4）所示条件时，网络中的负载重分配才会停止，否则，不满足条件的节点还会进行再一次的负载更新。

L_{i}^{A} ⩽ \sum_{k \in Γ_{i}^{A}} (C_{k}^{A} - Δ L_{k}^{A})

(4)

其中，Γ^A_i是节点v^A_i的待分配负载节点集合。

3 基于延迟判断的负载重分配

节点由活跃态转化为传播态或因能力下降等不能承担当前负载时，网络可能会因负载重分配导致整体负载持续饱和，直至崩溃。因此，可允许部分失效节点暂不进行负载的重分配，而等待网络负载水平较低时再进行处理。网络中需要重分配的负载具体可细分为两种，一种是可以直接进行分配的负载，另外一种是延迟分配的负载。

3.1 负载重分配策略

3.1.1 延迟判断

现实网络中，有很多负载延迟等待的例子。例如，交通运输系统中，不同类型的车辆具有不同等级的路权^[15]；中断系统中，中央处理器能够根据各中断请求的轻重缓急自动对它们进行排队处理^[16]等。现实网络中节点所承担的负载是不相同的，网络限额容量一定情况下，需要保证紧急负载能够实时完成。因此，本文对负载设置不同优先级，待优先级较高的负载分配请求处理完毕后，再响应优先级较低的负载分配请求。

当子网络中所有节点当前总负载比整个子网络的总限额容量还大时，即满足式（5）时，所有待分配负载节点无法全接受当前的分配负载，就需要对不同状态节点进行延迟处理。对于网络中处于失效态的节点，将负载全部分配给当前负载最小的待分配负载节点，通过延长负载接受时间以换取网络节点的负载空余。对于网络中处于低效态的节点，可以进行负载的延迟判断，对一部分优先级较低的负载进行延迟处理，暂停相应低优先级负载的分配，将其加入延迟负载集合中，待节点负载空余时再处理。同一节点的延迟负载是时变的，当网络中有低效态节点时，就要更新延迟负载；对于不同节点的延迟负载，将待分配负载节点的剩余容量可一次分配的部分负载按照节点的分配顺序进行依次分配。

\sum_{i \in V_{A}} L_{i}^{A} (\sum_{k \in V_{B}} L_{k}^{B}) > \sum_{i \in V_{A}} σ_{i} C_{i}^{A} (\sum_{k \in V_{B}} σ_{k} C_{k}^{B})

(5)

延迟判断过程中，以子网A为例：子网A中节点数为V_A，子网A中失效节点数为S_A，低效态节点v^A_i的初始负载为L^A_i（0），待分配负载节点数为Γ^A_i，节点的单位处理能力为s。在没有新的负载加入网络时，假设节点v^A_i失效后分配负载需要延迟，且其余节点都处于满载状态。下面对节点v^A_i的优先级最低的负载延迟上界进行讨论。

极端情况下，若其余失效节点状态都是失效态，都与节点v^A_i拥有相同的待分配负载节点，且分配负载优先级都比v^A_i负载高，在S_A个节点同时失效情况下，待分配负载节点在一次分配过后都失效，节点v^A_i中L^A_i（0）-sΓ^A_i的负载都无法完成，网络面临级联失效。

在节点v^A_i的最低优先级负载延迟后能够分配的情况下，考虑负载的延迟上界问题。当其余失效节点状态都为失效态时，待分配负载节点部分失效后只剩1个时，负载的延迟等待时间最大为：

\frac{L_{i}^{A} (0)}{s} - Γ_{i}^{A}

(6)

当其余失效节点状态都为低效态时，待分配负载节点都处于正常态，负载的延迟等待时间最大为：

S_{A} (\frac{L_{i}^{A} (0)}{s Γ_{i}^{A}} - 1) + 1

(7)

当其余失效节点状态中有M个为低效态、S_A-M-1个为失效态，使得一轮分配后，待分配负载节点部分失效只剩1个时，此时负载的延迟等待时间最大为：

\frac{L_{i}^{A} (0) - s Γ_{i}^{A}}{s} (S_{A} - M) - S_{A} + M + 1

(8)

此时，对式（7）和式（8）所得的最大延迟等待时间进行讨论，判断延迟上界的取值。令：

F = \frac{L_{i}^{A} (0)}{s} (S_{A} - M - \frac{S_{A}}{Γ_{i}^{A}}) + Γ_{i}^{A} (M - S_{A}) + M

(9)

当0＜M＜S_A时，有：

F > \frac{L_{i}^{A} (0)}{s} (\frac{S_{A} - M - \frac{S_{A}}{Γ_{i}^{A}}}{S_{A} - M}) - Γ_{i}^{A}

(10)

当S_A远大于Γ^A_i且s较大时，可以使得F＜0；其余情况下，因为L^A_i（0）

≫

Γ^A_i，所以F≥0。

综上，当网络中失效节点数较多且节点处理能力较大时，负载的延迟等待上界为式（7）；当网络中失效节点数与待分配负载节点相差不大，或节点的负载处理能力较小时，负载的延迟等待上界为式（8）。实际的网络负载分配过程中，负载等待时间远远低于等待上界。

3.1.2 负载分配

因为节点的负载有其原始目标节点，所以需要最小化待分配负载节点到目标节点的距离。当子网A中节点v^A_i失效时，首先找到其位于子网B中的原始目标节点v^B_j，搜索节点v^A_i到节点v^B_j的最短路径集合l^AB_ij，该路径集合上经过的所有节点都可为待分配负载节点，同时为l^AB_ij内节点设置最小的节点间距；若负载不能同时分配给当前的待分配负载节点集合，则扩大路径集合，找到次短路径集合并为集合上的待分配负载节点设置次高的节点间距，循环往复，找到所有的待分配负载节点。与此类似，若节点无原始目标节点，则按从一阶邻居节点开始，将邻居节点作为最短路径，从多阶邻居节点中选择待分配负载节点。

考虑为不同节点间距的待分配负载节点分配不同比例的负载，即负载分配的异质性问题，首先需要分类判断待分配负载节点的优先级。负载分配节点v^A_i需要分配的负载ΔL^A_i主要有三类：较v^A_i层级高的待分配负载节点v^A_j的负载ΔL^A_ij（+）、与v^A_i层级相同的节点v^A_l的负载ΔL^A_il（=）、较v^A_i层级低的节点v^A_m的负载ΔL^A_im（-）。不同的节点层级决定了分配的顺序，本文采用负载紧迫度U对需要重分配的负载优先级进行定量表示。负载紧迫度是时变的，每个待分配负载节点针对不同的负载分配节点有不同的负载紧迫度。为了分析过程的简洁，不再单独为每一负载设置紧迫度，但对于实际物理系统的负载分配，留有了单独设置负载紧迫度的接口。本文中需要重分配的负载的紧迫度和被分配的节点层级成反比，即U^A_ij=1/|d^A_i-d^A_j|。负载根据紧迫度从高到低的顺序，按照不同的比例同时被分配给以上不同层级的三类节点。也就是说，需要分配给低层级节点的负载最重要，而分配给较自己层级高的节点的负载重要度最低，即:

Δ L_{i m}^{A} (-) > Δ L_{i m}^{A} (=) > Δ L_{i m}^{A} (+)

(11)

此外，对于同样优先级的多个节点之间，节点的剩余限额容量是不同的，即节点能力的冗余值是不相同的，因此，需要考虑负载分配均匀性来继续划分负载分配比例。

综上，考虑以上因素，将负载分配节点v^A_i不能承担的负载ΔL^A_i分配给待分配负载节点v^A_j的负载ΔL^A_ij的大小定义如式（12）所示。

Δ L_{i j}^{A} = \frac{U_{i j} \cdot λ_{j}}{\sum_{n \in Γ_{i}^{A}} U_{i n} \cdot λ_{n}} \frac{(1 / l_{i j}^{κ}) \cdot {(C_{j}^{A} - L_{j}^{A})}^{θ} Δ L_{i}^{A}}{\sum_{m \in Γ_{i j}^{A}} (1 / l_{i m}^{κ}) \cdot {(C_{m}^{A} - L_{m}^{A})}^{θ}}

(12)

其中：Γ^A_ij是当前层级的待分配负载节点集合，λ为不同层级的待分配负载节点个数。异质性参数κ∈（-∞，0]控制不同间距的待分配负载节点的分配比例：当κ=0时，负载分配对节点间距没有偏好，即不同节点间距的相同待分配负载节点间均匀分配；当κ→-∞时，负载分配偏好节点间距较小的待分配负载节点，即节点间距越小，负载分配比例越大。θ∈（-∞，∞）用于控制同层级节点的负载分配均匀性：θ＞0时，同层级节点的负载分配偏好剩余节点容量大的；θ＜0时，同层级节点的负载分配偏好剩余节点容量小的。

3.2 负载重分配流程

负载重分配过程包括负载正常分配和延迟分配两个子过程，子过程不断循环直到负载重分配过程完成。具体分配流程如图3所示。

图3负载重分配流程

Fig.3Load redistribution flow chart

4 级联失效模型数值解析

基于本文所设计的节点初始负载、节点容量以及负载重分配机制，对网络发生级联失效进行深层次的理论分析，解析各个参数之间的变化关系。

当节点v^A_i失效后，其上一部分比例的负载会分配到其邻居节点v^A_j，节点v^A_j进行一次负载更新，要保证v^A_j不出现失效态则需要满足式（13）所示的条件。

L_{j}^{A} + Δ L_{j}^{A} ⩽ C_{j}^{A}

(13)

将式（1）、式（2）和式（12）代入式（13）所示条件，可以得到式（14）。

\begin{matrix} L_{j}^{A} + \frac{U_{i j} \cdot λ_{j}}{\sum_{n \in Γ_{i}^{A}} U_{i n} \cdot λ_{n}} \frac{(1 / l_{i j}^{κ}) \cdot {(C_{j}^{A} - L_{j}^{A})}^{θ} Δ L_{i}^{A}}{\sum_{m \in Γ_{i j}^{A}} (1 / l_{i m}^{κ}) \cdot {(C_{m}^{A} - L_{m}^{A})}^{θ}} ⩽ \\ (1 + γ) σ_{i} [\frac{μ \cdot D_{A} {(k_{j}^{A} - c_{j}^{A})}^{α}}{D_{A} - d_{j}^{A} + 1} + (1 - μ) {(\frac{c_{j}^{A}}{\sum_{m \in V_{A}, n \in V_{B}} R_{m n}})}^{β}] \end{matrix}

(14)

同时，分配过程中节点的负载是只增不减的，节点的负载都不会低于它们的初始负载，因此，可以得到如式（15）和式（16）所示两个不等式。

L_{j}^{A} ⩾ \frac{μ \cdot D_{A} {(k_{j}^{A} - c_{j}^{A})}^{α}}{D_{A} - d_{j}^{A} + 1} + (1 - μ) {(\frac{c_{j}^{A}}{\sum_{m \in V_{A}, n \in V_{B}} R_{m n}})}^{β}

(15)

Δ L_{i}^{A} ⩾ \frac{μ \cdot D_{A} {(k_{i}^{A} - c_{i}^{A})}^{α}}{D_{A} - d_{i}^{A} + 1} + (1 - μ) {(\frac{c_{i}^{A}}{\sum_{j \in V_{A}, k \in V_{B}} R_{j k}})}^{β}

(16)

将式（15）和式（16）代入式（14），化简后得到式（17）。

\begin{matrix} \frac{1}{D_{A} - d_{j}^{A} + 1} \frac{U_{i j} \cdot λ_{j}}{\sum_{n \in Γ_{i}^{A}} U_{i n} \cdot λ_{n}} \frac{(1 / l_{i j}^{κ}) \cdot {(C_{j}^{A} - L_{j}^{A})}^{θ}}{\sum_{m \in Γ_{i j}^{A}} (1 / l_{i m}^{k}) \cdot {(C_{m}^{A} - L_{m}^{A})}^{θ}} < \\ \frac{γ}{D_{A} - d_{i}^{A} + 1} \end{matrix}

(17)

当i=j时，即网络中节点层级都相同时，式（17）可以化简为式（18）。

\frac{(1 / l_{i j}^{κ}) \cdot {(C_{j}^{A} - L_{j}^{A})}^{θ}}{\sum_{m \in Γ_{i j}^{A}} (1 / l_{i m}^{κ}) \cdot {(C_{m}^{A} - L_{m}^{A})}^{θ}} < γ

(18)

式（18）左边值随着θ增加递减，且斜率也不断减小至0，因此，当κ固定时，θ越大，网络鲁棒性越强，但当到达某一最大值时，再增加θ也不会增加网络鲁棒性。

当κ→-∞时，先分配负载至间距较小节点，且分子分母相差较大，当θ小于阈值时，此时阈值为某一负数，分数值急剧上升，容易发生级联失效。当κ=0时，此时网络发生级联失效的临界条件如式（19）所示。分子分母之间差距缩小，但仍会在θ小于阈值时发生级联失效。

\frac{{(C_{j}^{A} - L_{j}^{A})}^{θ}}{\sum_{m \in Γ_{i j}^{A}} {(C_{m}^{A} - L_{m}^{A})}^{θ}} < γ

(19)

当i≠j时，式（17）可以化简为式（20）。

\frac{D_{A} - d_{i}^{A} + 1}{D_{A} - d_{j}^{A} + 1} \frac{U_{i j} \cdot λ_{j}}{\sum_{n \in Γ_{i}^{A}} U_{i n} \cdot λ_{n}} \frac{(1 / l_{i j}^{κ}) \cdot {(C_{j}^{A} - L_{j}^{A})}^{θ}}{\sum_{m \in Γ_{i j}^{A}} (1 / l_{i m}^{κ}) \cdot {(C_{m}^{A} - L_{m}^{A})}^{θ}} < γ

(20)

同样地，随着θ增加至某一最大值，网络的鲁棒性也越来越强。当总层级数小于

λ_{j} / \sum_{n \in Γ_{i}^{A}} λ_{n}

时，待分配负载节点与攻击节点之间层级越接近，较小的γ值就可以不发生级联失效；当总层级数较大时，若受攻击的节点层级较高，而待分配负载节点层级较低，等式左边值也就越小，此时相应的γ值是网络发生级联失效的临界条件。

5 实验分析

5.1 网络性能评估指标

1）失效节点数量：以级联失效前后网络中失效且未能成功分配负载的节点数量S作为衡量网络的抗毁性的一个指标^[17]。当S值较大时，网络的鲁棒性差；S值小，鲁棒性就高。

2）负载完成时间：采用网络完成所有负载并将结果返回到目标节点所需的时间T作为衡量重分配机制效率的一个指标。当T值较大时，网络的重分配机制效率较低；T值小，重分配机制效率就高。

3）负载完成率：采用负载完成量占比G作为衡量网络抗毁性的一个指标。当G值较大时，网络的抗毁性高；G值小，抗毁性就差。

5.2 实验验证

采用V=500的WS-BA相依网络来分析影响多层级相依网络的鲁棒性和重分配机制效率的因素，其中WS小世界子网络V_A=300，BA无标度网络V_B=200。按照网络中节点的度值从大到小顺序，对20个重点节点进行攻击，每个节点攻击20次以消除概率影响，通过失效节点数量、负载完成时间以及平均负载完成率三个指标衡量网络参数对网络的影响。

5.2.1 初始负载定义的准确性

节点初始负载定义的准确性和合理性直接影响网络性能的评估结果^[18]。因此，首先通过对比来分析初始负载定义的准确性。

为证实本文方法能使网络抵制更强的级联失效，在μ=0.3、α=1、β=13的条件下，将本文方法分别与度定义的初始负载模型（度值方法）^[19]和介数定义的初始负载模型（介数方法）^[20]的指标结果进行对比，如图4所示，阴影部分为95%置信区间。

图4（a）所示是三类方法的失效节点数量，可以看到在同一个网络下，当网络达到最强鲁棒性时，本文γ=0.7，文献^[19]中γ=1.2，文献^[20]中γ＞1.6。本文所提方法在网络达到最强鲁棒性时需要的γ值最小，说明此策略下的网络更难发生级联失效。因为介数大的节点属于多个最短节点间距集合，极易过载，因此增加节点负载或减小剩余节点容量，降低了网络鲁棒性，且从图4（c）中可以看到负载完成率也较低，但介数定义方法能够缩短负载完成后的转移时间，图4（b）显示整体的负载完成时间较低。

图4三种初始负载设置方法下的评估指标变化

Fig.4Change of evaluation indicators under three initial load setting methods

5.2.2 节点状态对网络的影响

设置节点为低效态的方法有两种：一种是随机选择一部分节点设置为低效态，另一种是按照节点特征值排序选择一部分节点设置为低效态。本文特征值选择节点介数，对攻击网络后的指标结果进行分析。

固定节点初始负载，设置γ=0.1、μ=0.3、α=1、β=13，将网络中一部分节点设置为低效态节点，从0开始，提高低效态节点数量得到指标变化结果，如图5所示。

由图5可以看到，介数选择方法下，图5（a）失效节点数量在持续下降，当网络中节点全为低效态时，失效节点数量为0；图5（b）中负载完成时间在不断增加；图5（c）中负载完成率随着低效态节点数量增加在不断增加，斜率先增大后减小，均值不断逼近1，因为有向网络中存在的叶子节点受到攻击后，无法将负载重分配给其他活跃态节点，因此导致少部分负载无法完成。随机设置方法下，当低效态节点数量较少时，评估指标结果的波动较大；随着低效态节点的增加，慢慢与介数选择方法所得结果趋同。说明低效态节点数量能够减少级联失效的发生，提高网络鲁棒性，提高负载完成率，但增加了负载完成时间。按介数值选择一定数量的低效态节点，能够减少失效节点数量，且提高网络效率。

图5评估指标随着低效态节点数量增加的变化结果

Fig.5Change results of the evaluation indicators with the increase of the number of low-efficiency nodes

通过增大γ值，增加网络的节点限额容量，设置μ=0.3、α=1、β=13，也同样通过随机选择和介数选择方法设置30个节点为低效态，观察网络受到攻击后的指标变化情况，如图6所示。

图6中随着γ值的增加，负载完成时间和失效节点数量在不断下降，负载完成率和负载完成数量不断增加。相较于随机选择所得结果波动较大，介数选择得到结果更加稳定，方差较小，且大部分情况下比随机选择所得结果更优。因为随机选择具有一定的概率性，当选择的低效态节点正好处于待分配负载节点集中，结果就会提高。

图6两种低效态节点设置方法下的评估指标变化

Fig.6Change of evaluation indicators under two low-efficiency node setting methods

总体来说，采用介数选择方法增加低效态节点数量时，能够提高网络的鲁棒性，网络中失效节点数稳定下降，负载完成率也在上升，但负载完成时间在不断增加。这是由于低效态节点受到攻击导致无法处理负载时，可以延迟分配负载，等待活跃态节点负载空余的过程中增加了负载完成的时间。因此，按照介数选择方法设置合适数量的低效态节点，能够在保证网络效率较高的同时，减少级联失效的发生。

5.2.3 重分配方法的影响

本文设计对比实验来分析负载分配异质性和分配均匀性对网络产生的影响，固定初始状态为γ=0.3、μ=0.3、α=1和β=23，调整异质性参数κ和均匀性参数θ来考察评估指标的变化，结果用热力图表示，如图7所示。

图7评估指标随着异质性和均匀性参数的变化结果

Fig.7Result of evaluation indicators with the heterogeneity and uniformity parameters changes

图7（a）中显示的是对每个网络攻击20个节点后失效节点的数量和，可以看到，失效节点数量随着θ的增加在不断降低，随着κ减小也在不断降低，但κ值对失效节点数量的影响有限，而θ对失效节点数量的影响较大，且随着θ值的增加，变化幅值也在不断减小。当κ=-40，θ≥10时，可以达到最小的失效节点数量。节点间距越小，负载分配比例越高，网络发生级联失效的范围也越小，同时，当节点间距固定，在一定范围内，待分配负载节点的剩余容量与获得额外负载的相关性越高，网络发生级联失效的程度越小。

图7（b）所示是负载完成时间去掉最大值和最小值后的平均值变化，可以看到，平均负载完成时间随着κ的降低先不断减少再增加，随着θ的增大在不断降低，但κ对负载完成时间的影响较大，当κ=-60时，平均负载完成时间基本达到最小，再减小κ值就会增加时间。因为负载有目标节点，负载分配偏好节点间距较大的待分配负载节点后，离目标节点较远，转发需要大量时间，而当κ太小时，会增加单个节点的计算量，导致网络总计算时间增加，尤其是大规模复杂网络更明显。

图7（c）所示是负载完成率的平均值，可以看到，图中大部分蓝色集中在左侧，即当κ值固定时，较小的θ得到较低的负载完成率，因为负载不能一次分配就完成，需要不断分配的节点增多，负载不能完成的概率增大。此后，负载完成率随着κ和θ的变化无明显规律，但增加θ值后，负载完成率整体较高，不过最大也没有到达1。

综上，选择合适的κ值，能够最大限度地降低级联失效的发生范围，同时降低负载完成时间；提高θ值能够在一定范围内降低级联失效程度，减少负载完成时间，提高负载完成率。

5.2.4 层级的影响

网络中节点层级也影响网络鲁棒性和效率，设置μ=0.3、α=1、β=23、κ=-20、θ=20，且层级间最大差值为20时，分析不同网络层级下得到的评估结果，如图8所示。

由图8可以看到，随着层数的增加，网络失效节点数量整体呈现上升的趋势，但在层数大于11后保持稳定，负载完成率在不断降低，负载完成时间在不断上升。因为提高网络层级产生了较大数量的低层级节点，重分配时具有较高负载紧迫度，因此重分配次数增多，增加了负载完成时间，同时这些节点初始负载较低，节点容量也较低，增加了节点失效的可能性，降低了负载完成率。

综上，增大网络的节点容量、降低网络的层级数可以提高网络鲁棒性，但不能完全避免级联失效的发生，同时其不仅提高了网络的成本，也降低了刻画现实系统的准确性。在网络初始条件一定情况下，要想降低网络发生级联失效的可能性、提高负载完成率，可以适当选择较小κ值（κ＜0）、提高θ值（θ＞0）。

图8评估指标随着网络层级数量的变化结果

Fig.8Result of evaluation indicators with the number of network layers changes

6 结论

采用复杂网络刻画复杂系统来研究级联失效问题，具有广泛的现实意义，得到越来越多学者的青睐。本文基于现实世界网络的负载具有异质性的情况，建立了多状态节点的优先和延迟分配；在设计初始负载和节点容量基础上，结合负载的目标节点，考虑负载重分配的范围与均匀性，设计相依网络的负载重分配机制，并最终进行解析分析与数值仿真。从结果可以看出，调节网络的节点容量和层级等设计因素可提高网络鲁棒性和效率，但要在成本或描述准确性方面做出牺牲。合理的负载分配范围与均匀性等可控因素，对网络抵御级联失效风险、发挥出更大的性能具有至关重要的作用。

本文揭示了相依网络的级联失效机理，设计了更合理的初始负载，保证了网络性能评估结果的准确性，构建了负载重分配策略，防止网络在总负载过高情况下面临不可避免的崩溃。本研究不仅对设计鲁棒性较强网络具有借鉴意义，也可以提供有效提高网络鲁棒性和处理效率的策略，为人们理解现实复杂系统的内在运行规律提供了一种手段，具有理论与现实意义。

图1多层级有向相依网络

Fig.1Multilevel directed dependent network

下载: 全尺寸图片

图2受攻击节点的单次负载分配过程

Fig.2A load distribution process of the attacked node

下载: 全尺寸图片

图3负载重分配流程

Fig.3Load redistribution flow chart

下载: 全尺寸图片

图4三种初始负载设置方法下的评估指标变化

Fig.4Change of evaluation indicators under three initial load setting methods

下载: 全尺寸图片

图5评估指标随着低效态节点数量增加的变化结果

Fig.5Change results of the evaluation indicators with the increase of the number of low-efficiency nodes

下载: 全尺寸图片

图6两种低效态节点设置方法下的评估指标变化

Fig.6Change of evaluation indicators under two low-efficiency node setting methods

下载: 全尺寸图片

图7评估指标随着异质性和均匀性参数的变化结果

Fig.7Result of evaluation indicators with the heterogeneity and uniformity parameters changes

下载: 全尺寸图片

图8评估指标随着网络层级数量的变化结果

Fig.8Result of evaluation indicators with the number of network layers changes

下载: 全尺寸图片

图1多层级有向相依网络

Fig.1Multilevel directed dependent network

图2受攻击节点的单次负载分配过程

Fig.2A load distribution process of the attacked node

图3负载重分配流程

Fig.3Load redistribution flow chart

图4三种初始负载设置方法下的评估指标变化

Fig.4Change of evaluation indicators under three initial load setting methods

图5评估指标随着低效态节点数量增加的变化结果

Fig.5Change results of the evaluation indicators with the increase of the number of low-efficiency nodes

图6两种低效态节点设置方法下的评估指标变化

Fig.6Change of evaluation indicators under two low-efficiency node setting methods

图7评估指标随着异质性和均匀性参数的变化结果

Fig.7Result of evaluation indicators with the heterogeneity and uniformity parameters changes

图8评估指标随着网络层级数量的变化结果

Fig.8Result of evaluation indicators with the number of network layers changes

引用提醒

图(8)

引用本文

张家瑞, 黄健, 高家隆. 负载目标下基于延迟分配的多层级相依网络级联失效模型[J]. 国防科技大学学报, 2024, 46(5): 79-89.

复制

ZHANG J R, HUANG J, GAO J L. Cascading failure model for multi-level interdependent networks based on delay distribution under load target[J]. Journal of National University of Defense Technology, 2024, 46(5): 79-89.

Copy

计量

图1多层级有向相依网络

Fig.1Multilevel directed dependent network

图2受攻击节点的单次负载分配过程

Fig.2A load distribution process of the attacked node

图3负载重分配流程

Fig.3Load redistribution flow chart

图4三种初始负载设置方法下的评估指标变化

Fig.4Change of evaluation indicators under three initial load setting methods

图5评估指标随着低效态节点数量增加的变化结果

Fig.5Change results of the evaluation indicators with the increase of the number of low-efficiency nodes

图6两种低效态节点设置方法下的评估指标变化

Fig.6Change of evaluation indicators under two low-efficiency node setting methods

图7评估指标随着异质性和均匀性参数的变化结果

Fig.7Result of evaluation indicators with the heterogeneity and uniformity parameters changes

图8评估指标随着网络层级数量的变化结果

Fig.8Result of evaluation indicators with the number of network layers changes

WANG J W, RONG L L, ZHANG L. A model for cascading failures in complex networks with a tunable parameter[J]. Modern Physics Letters B,2009,23(10):1323-1332.

RINALDI S M, PEERENBOOM J P, KELLY T K. Identifying,understanding,and analyzing critical infrastructure interdependencies[J]. IEEE Control Systems Magazine,2001,21(6):11-25.

BULDYREV S V, PARSHANI R, PAUL G,et al. Catastrophic cascade of failures in interdependent networks[J]. Nature,2010,464:1025-1028.

PARSHANI R, DICKISON M, COHEN R,et al. Dynamic networks and directed percolation[J]. EPL(Europhysics Letters),2010,90(3):38004.

严玉为, 蒋沅, 杨松青, 等. 基于时间序列的网络失效模型[J]. 物理学报,2022,71(8):331-339. YAN Y W, JIANG Y, YANG S Q,et al. Network failure model based on time series[J]. Acta Physica Sinica,2022,71(8):331-339.(in Chinese)

蒋文君, 刘润然, 范天龙, 等. 多层网络级联失效的预防和恢复策略概述[J]. 物理学报,2020,69(8):81-91. JIANG W J, LIU R R, FAN T L,et al. Overview of precaution and recovery strategies for cascading failures in multilayer networks[J]. Acta Physica Sinica,2020,69(8):81-91.(in Chinese)

HONG C, ZHANG J, DU W B,et al. Cascading failures with local load redistribution in interdependent Watts-Strogatz networks[J]. International Journal of Modern Physics C,2016,27(11):1650131.

HAO Y C, JIA L M, WANG Y H,et al. Modelling cascading failures in networks with the harmonic closeness[J]. PLoS One,2021,16(1):0243801.

JIN Z Y, DUAN D L, WANG N. Cascading failure of complex networks based on load redistribution and epidemic process[J]. Physica A: Statistical Mechanics and Its Applications,2022,606:128041.

王立夫, 李欢, 赵国涛. 基于节点最大剩余容量的改进负荷再分配策略[J]. 东北大学学报(自然科学版),2020,41(9):1223-1230. WANG L F, LI H, ZHAO G T. Improved load re-allocation strategy based on maximum residual capacity of node[J]. Journal of Northeastern University(Natural Science),2020,41(9):1223-1230.(in Chinese)

袁铭. 带有层级结构的复杂网络级联失效模型[J]. 物理学报,2014,63(22):77-84. YUAN M. A cascading failure model of complex network with hierarchy structure[J]. Acta Physica Sinica,2014,63(22):77-84.(in Chinese)

BAO Z J, CAO Y J, DING L J,et al. Comparison of cascading failures in small-world and scale-free networks subject to vertex and edge attacks[J]. Physica A: Statistical Mechanics and Its Applications,2009,388(20):4491-4498.

QIU S M, YU T, DU X L,et al. Research on command and control network load redistribution algorithm based on“triangle” structure[C]//Proceedings of the 2019 4th International Conference on Mechanical, Control and Computer Engineering(ICMCCE),2019.

MOTTER A E. Cascade control and defense in complex networks[J]. Physical Review Letters,2004,93(9):098701.

岳文伟. 城市交通拥塞控制策略研究[D]. 西安: 西安电子科技大学,2020. YUE W W. Traffic congestion control strategies in urban road networks[D]. Xi′an: Xidian University,2020.(in Chinese)

周明德. 微型计算机硬件软件及其应用[M].2版. 北京: 清华大学出版社,1988. ZHOU M D. Microcomputer hardware and software and its application[M].2nd ed. Beijing: Tsinghua University Press,1988.(in Chinese)

ZENG Y. Evaluation of node importance and invulnerability simulation analysis in complex load-network[J]. Neurocomputing,2020,416:158-164.

韩丽, 刘彬, 邓玉静, 等. 加权无标度网络的级联失效模型[J]. 软件学报,2017,28(10):2769-2781. HAN L, LIU B, DENG Y J,et al. Cascading failure model of weighted scale-free networks[J]. Journal of Software,2017,28(10):2769-2781.(in Chinese)

WANG W X, CHEN G R. Universal robustness characteristic of weighted networks against cascading failure[J]. Physical Review E,2008,77(2 Pt 2):026101.

ZHAO Z, ZHANG P, YANG H J. Cascading failures in interconnected networks with dynamical redistribution of loads[J]. Physica A: Statistical Mechanics and Its Applications,2015,433:204-210.

首页

期刊介绍

投稿指南

编委会

出版声明

开放获取声明

联系我们

期刊订阅

Rss

AI检索

English

1 多层级相依网络模型

2 级联失效模型

3 基于延迟判断的负载重分配

4 级联失效模型数值解析

5 实验分析

6 结论