这是用户在 2025-4-11 14:31 为 https://app.immersivetranslate.com/pdf-pro/d145d486-1070-42aa-8d1b-9e2d9f623e6c/?isTrial=true 保存的双语快照页面，由 沉浸式翻译 提供双语支持。了解如何保存？

All d d dd-MPs for All d d dd Level Searching Method for Multistate Network in Resilience Process
all d d dd -MPs for all d d dd level search method for multistate network in resilience process （用于 Resilience 过程中多状态网络的所有级别搜索方法） all -mps

Tao Liu ⊙ ⊙ ^(o.){ }^{\odot}, Guanghan Bai ∙ ∙ ^(∙){ }^{\bullet}, Junfu Zhang ∙ ∙ ^(∙){ }^{\bullet}, and Quan Xu ⊙ ⊙ ^(o.){ }^{\odot}
刘涛 ⊙ ⊙ ^(o.){ }^{\odot} ， 白光汉 ∙ ∙ ^(∙){ }^{\bullet} ， 张俊福 ∙ ∙ ^(∙){ }^{\bullet} ， 徐泉 ⊙ ⊙ ^(o.){ }^{\odot}

Abstract  抽象

The all-level d d d\boldsymbol{d} minimal path vectors ( d d dd-MPs) are an important input for obtaining the performance metric of multistate networks, which is the basis of resilience evaluation and analysis. During the resilience process, network configurations may change, leading to changes in the d d dd-MPs. However, when the network configurations are changed, the repeated searching of d d dd-MPs is time consuming because it is an NP-hard problem. Thus, a framework is proposed to obtain the d d dd-MPs in different situations during the resilience process. First, two d d dd-MP updating algorithms are used instead of repeated searching of the d d dd-MPs when the maximum states of the components are changed. Taking the original d d dd-MPs as the input, the proposed method updates the d d dd-MPs by deleting the unqualified d d dd-MPs or adding the qualified d d dd-MPs during the resilience process. Second, a d d dd-MP searching algorithm is employed to search the new d d dd-MPs derived from the new components that are brought in during the recovery phase. Computational experiments show that the proposed updating methods are more efficient than the existing d d dd-MP searching algorithm. Furthermore, the proposed new d d dd-MP searching algorithm outperforms the repeated searching of d d dd-MPs. In addition, the proposed method can be applied to network design and optimal phase settings, where multiple attempts at network configuration adjustments may be necessary.
全级 d d d\boldsymbol{d} 最小路径向量 （ d d dd -MPs） 是获取多态网络性能指标的重要输入，是弹性评估和分析的基础。在弹性过程中，网络配置可能会更改，从而导致 d d dd -MP 发生变化。但是，当网络配置发生变化时，重复搜索 d d dd -MPs 会很耗时，因为这是一个 NP 困难的问题。因此，提出了一个框架来获得弹性过程中不同情况下的 d d dd -MP。首先，当组件的最大状态发生变化时，使用两种 d d dd -MP 更新算法，而不是重复搜索 d d dd -MP。以原始 d d dd -MPs 作为输入，所提出的方法通过在弹性过程中删除不合格的 d d dd -MPs 或添加合格的 d d dd -MPs 来更新 d d dd -MPS。其次，采用 d d dd -MP 搜索算法来搜索从恢复阶段引入的新组件派生的新 d d dd -MP。计算实验表明，所提出的更新方法比现有的 d d dd -MP 搜索算法更有效。此外，所提出的新 d d dd -MP 搜索算法优于 d d dd -MP 的重复搜索。此外，所提出的方法可应用于网络设计和最佳相位设置，其中可能需要多次尝试网络配置调整。

Index Terms-Minimal path (MP) vectors, multistate network, network reliability, resilience process, topologic adjustment.
索引项 - 最小路径 （MP） 向量、多态网络、网络可靠性、弹性过程、拓扑调整。

Nomenclature  命名法

Abbreviations  缩写

MP Minimal path.  最小路径。
d d dd-MP d d dd-Minimal path.   d d dd - 最小路径。
d d dd-MPM d d dd-Minimal path matrix.
d d dd - 最小路径矩阵。
i.i.d.  身份证 Identical and independently distributed.
相同且独立分发。
MP Minimal path. d-MP d-Minimal path. d-MPM d-Minimal path matrix. i.i.d. Identical and independently distributed.| MP | Minimal path. | | :--- | :--- | | $d$-MP | $d$-Minimal path. | | $d$-MPM | $d$-Minimal path matrix. | | i.i.d. | Identical and independently distributed. |
Notation  表示法
d d d quadd \quad System demand requirement.
d d d quadd \quad 系统需求要求。
V V V quadV \quad Set of the nodes.
V V V quadV \quad 节点集。
Manuscript received 6 October 2023; revised 12 December 2023; accepted 12 January 2024. This work was supported in part by the National Natural Science Foundation of China under Grant 72271242 and Grant 51275425 and in part by Hunan Provincial Natural Science Foundation of China for Excellent Young Scholars under Grant 2022JJ20046. Associate Editor: Y.-K. Lin. (Corresponding authors: Guanghan Bai.)
手稿于 2023 年 10 月 6 日收到;修订于 2023 年 12 月 12 日;2024 年 1 月 12 日接受。这项工作部分得到了中国国家自然科学基金 72271242 和 51275425 资助的支持，部分由中国湖南省自然科学基金优秀青年基金资助 2022JJ20046。副主编：Y.-K.林（通讯作者：白光汉）
Tao Liu, Junfu Zhang, and Quan Xu are with the School of Mechanical Engineering, Xihua University, Chengdu 410000, China (e-mail: favmoon@hotmail.com; zhangjf@mail.xhu.edu.cn; quanxnjd@sina.com).
Tao Liu、Junfu Zhang 和 Quan Xu 就职于西华大学机械工程学院，中国成都 410000（电子邮件：favmoon@hotmail.com;zhangjf@mail.xhu.edu.cn;quanxnjd@sina.com）。
Guanghan Bai is with the Laboratory of Science and Technology on Integrated Logistics Support, College of Intelligence Science and Technology, National University of Defense Technology, Changsha 410073, China (e-mail: baiguanghan@ nudt.edu.cn).
白光汉就职于中国长沙410073国防科技大学智能科学与技术学院综合物流保障科学与技术实验室（电子邮件：baiguanghan@ nudt.edu.cn）。
Color versions of one or more figures in this article are available at https://doi.org/10.1109/TR.2024.3355980.
本文中一个或多个图的彩色版本可在 https://doi.org/10.1109/TR.2024.3355980 处获得。
Digital Object Identifier 10.1109/TR.2024.3355980
数字对象标识符 10.1109/TR.2024.3355980
E E EE Set of the arcs (components).
圆弧 （组件） 的集合。
m m mm Vector of maximum states of the components.
分量的最大状态向量。
x x x\boldsymbol{x} Component state vector.  组件状态向量。
n n nn Total number of components in the network.
网络中的组件总数。
ϕ ( ⋅ ) ϕ ( ⋅ ) phi(*)\phi(\cdot) System structure function.
系统结构功能。
z l z l z^(l)z^{l} l l ll th d d dd-MP.
l l ll th d d dd -MP 的
M Max flow from source node to sink node.
从源节点到汇节点的最大流量。
L d L d L_(d)L_{d} Number of d d dd-MPs.  -MP 的数量 d d dd 。
T 0 T 0 T_(0)T_{0} Staring time of the mission.
任务的凝视时间。
T f T f T_(f)T_{f} Ending time of the mission.
任务结束时间。
T d T d T_(d)T_{d} Time point of disturbance even occurs.
干扰的时间点甚至会出现。
T s T s T_(s)T_{s} Staring time of response and recovery phase.
反应和恢复阶段的起始时间。
T r T r T_(r)T_{r} Ending time of response and recovery phase.
响应和恢复阶段的结束时间。
K d K d K_(d)\boldsymbol{K}_{d} d d dd-minimal paths matrix.
d d dd -minimal paths 矩阵。
U d U d U_(d)U_{d} d d dd-MPMs before distortive event.
d d dd -扭曲事件之前的 MPM。
Γ Γ Gamma\Gamma Set of components that affected by disturbances.
受干扰影响的组件集。
d − M P ― j i d − M P ¯ j i d_(-) bar(MP)_(j)^(i)d_{-} \overline{\boldsymbol{M P}}_{j}^{i} j j jj th d d dd-MP candidate with the index i i ii.
j j jj 索引为 i i ii . 的第 - d d dd MP 候选项 .
M P i M P i MP_(i)M \boldsymbol{P}_{i} i i ii th minimal path.
i i ii th 最小路径。
Δ Δ Delta\Delta Set of new components.  一组新组件。
Φ Φ Phi\Phi Index of new MPs associate with Δ Δ Delta\Delta.
与 Δ Δ Delta\Delta 关联的新 MP 索引。
C v C v C_(v)C_{v} v v vv th cycles in the network.
v v vv th 周期。
Ψ Ψ Psi\Psi Set of the MPs that has been used.
已使用的 MP 集。
Q Q QQ Expectation flow from the source to sink node.
从 source 到 sink 节点的期望流。
Λ d Λ d Lambda_(d)\Lambda_{d} Probability that the flow from the source to the sink node is equal to d d dd.
从源流向汇节点的流等于 d d dd 的概率。
T B T B T_(B)T_{B} CPU running time of using Bai's all level d d dd-MP searching algorithm.
使用 Bai 的所有级别 d d dd -MP 搜索算法的 CPU 运行时间。
T U T U T_(U)T_{U} CPU running time of using proposed d d dd-MP updating algorithms (Algorithm 1 and 2).
使用建议的 d d dd -MP 更新算法的 CPU 运行时间（算法 1 和 2）。
T N T N T_(N)T_{N} CPU running time of using proposed new d d dd-MP searching algorithms (Algorithm 3).
使用建议的新 d d dd -MP 搜索算法的 CPU 运行时间（算法 3）。
N B N B N_(B)N_{B} Number of all the d d dd-MPs in all levels.
所有级别中所有 d d dd -MP 的数量。
N P N P N_(P)N_{P} Number of the new d d dd-MPs derived from the new components.
从新组件派生的新 d d dd -MP 的数量。
E Set of the arcs (components). m Vector of maximum states of the components. x Component state vector. n Total number of components in the network. phi(*) System structure function. z^(l) l th d-MP. M Max flow from source node to sink node. L_(d) Number of d-MPs. T_(0) Staring time of the mission. T_(f) Ending time of the mission. T_(d) Time point of disturbance even occurs. T_(s) Staring time of response and recovery phase. T_(r) Ending time of response and recovery phase. K_(d) d-minimal paths matrix. U_(d) d-MPMs before distortive event. Gamma Set of components that affected by disturbances. d_(-) bar(MP)_(j)^(i) j th d-MP candidate with the index i. MP_(i) i th minimal path. Delta Set of new components. Phi Index of new MPs associate with Delta. C_(v) v th cycles in the network. Psi Set of the MPs that has been used. Q Expectation flow from the source to sink node. Lambda_(d) Probability that the flow from the source to the sink node is equal to d. T_(B) CPU running time of using Bai's all level d-MP searching algorithm. T_(U) CPU running time of using proposed d-MP updating algorithms (Algorithm 1 and 2). T_(N) CPU running time of using proposed new d-MP searching algorithms (Algorithm 3). N_(B) Number of all the d-MPs in all levels. N_(P) Number of the new d-MPs derived from the new components.| $E$ | Set of the arcs (components). | | :---: | :---: | | $m$ | Vector of maximum states of the components. | | $\boldsymbol{x}$ | Component state vector. | | $n$ | Total number of components in the network. | | $\phi(\cdot)$ | System structure function. | | $z^{l}$ | $l$ th $d$-MP. | | M | Max flow from source node to sink node. | | $L_{d}$ | Number of $d$-MPs. | | $T_{0}$ | Staring time of the mission. | | $T_{f}$ | Ending time of the mission. | | $T_{d}$ | Time point of disturbance even occurs. | | $T_{s}$ | Staring time of response and recovery phase. | | $T_{r}$ | Ending time of response and recovery phase. | | $\boldsymbol{K}_{d}$ | $d$-minimal paths matrix. | | $U_{d}$ | $d$-MPMs before distortive event. | | $\Gamma$ | Set of components that affected by disturbances. | | $d_{-} \overline{\boldsymbol{M P}}_{j}^{i}$ | $j$ th $d$-MP candidate with the index $i$. | | $M \boldsymbol{P}_{i}$ | $i$ th minimal path. | | $\Delta$ | Set of new components. | | $\Phi$ | Index of new MPs associate with $\Delta$. | | $C_{v}$ | $v$ th cycles in the network. | | $\Psi$ | Set of the MPs that has been used. | | $Q$ | Expectation flow from the source to sink node. | | $\Lambda_{d}$ | Probability that the flow from the source to the sink node is equal to $d$. | | $T_{B}$ | CPU running time of using Bai's all level $d$-MP searching algorithm. | | $T_{U}$ | CPU running time of using proposed $d$-MP updating algorithms (Algorithm 1 and 2). | | $T_{N}$ | CPU running time of using proposed new $d$-MP searching algorithms (Algorithm 3). | | $N_{B}$ | Number of all the $d$-MPs in all levels. | | $N_{P}$ | Number of the new $d$-MPs derived from the new components. |

I. Introduction  I. 引言

MULTISTATE networks, whose components can operate in different states and obey certain distributions, exist widely in the real world [1]. For example, information exchange networks for UAV swarms [2], [3], supply chain networks [4], manufacturing networks [5], peer-to-peer networks, [6] and road networks [7] can be modeled as such networks. Unexpected external or internal disturbances, such as earthquakes [8], hurricanes [9], and blackouts [10] may adversely affect network operation. Thus, resilience, which characterizes the ability of a
MULTISTATE 网络，其组件可以在不同的状态下运行并遵循某些分布，在现实世界中广泛存在 [1]。例如，无人机集群 [2]、[3]、供应链网络 [4]、制造网络 [5]、点对点网络 [6] 和道路网络 [7] 的信息交换网络可以建模为此类网络。意外的外部或内部干扰，如地震 [8]、飓风 [9] 和停电 [10] 可能会对网络运行产生不利影响。因此，弹性（表征
system to resist and bounce back after a disruption, has become a popular topic [11].
系统在中断后抵抗和反弹，已成为一个热门话题 [11]。
As part of basic resilience research, many researchers have evaluated resilience by proposing proper metrics, such as triangle-based metrics [12], [13], [14], time-dependent metrics [15], [16], multiparameter fusion metrics [17], [18], [19], mission-oriented metrics [20], and baseline metrics [21]. These are primarily based on the changes in system performance during the resilience process. To evaluate and analyze the resilience of a multistate network, Liu et al. [7] proposed the expectation of the flow that can be sent from the source to the sink node as a performance metric. To obtain this performance metric, it is necessary to evaluate the probability of successfully sending the required flow d d dd from a source to a sink. This probability is also referred to as the “reliability of multistate networks.”
作为基础弹性研究的一部分，许多研究人员通过提出适当的指标来评估弹性，例如基于三角形的指标 [12]、[13]、[14]、时间依赖性指标 [15]、[16]、多参数融合指标 [17]、[18]、[19]、面向任务的指标 [20] 和基线指标 [21]。这些主要基于弹性过程中系统性能的变化。为了评估和分析多状态网络的弹性，Liu et al. [7] 提出了可以从源发送到 sink 节点的流的期望作为性能指标。要获得此性能指标，有必要评估成功将所需流 d d dd 从源发送到 sink 的概率。这种概率也称为“多状态网络的可靠性”。
The two common approaches used to obtain this probability are direct and indirect. The direct approach utilizes a state vector to divide the entire state space into accepted, unaccepted, and unspecified sets. The unspecified sets are recursively decomposed until only one unspecified set remains. The reliability is the sum of the probabilities of all accepted sets [22]. However, the indirect approach uses d d dd-minimal cuts ( d d dd-MCs) and d d dd-MPs to indirectly evaluate the reliability, as first proposed by Lin et al. [23] and Jane et al. [24]. Taking d d dd-MPs as an example, the reliability of a multistate network can be calculated by the probability of union of all d d dd-MPs, such as the inclusion-exclusion method [25], sum of disjoint products principle [26], [27], [28] and state space decomposition method [29], [30], [31].
用于获取此概率的两种常用方法是直接和间接。直接方法利用状态向量将整个状态空间划分为已接受、未接受和未指定的集合。未指定的集将递归分解，直到只剩下一个未指定的集。可靠性是所有接受集合的概率之和 [22]。然而，间接方法使用 d d dd -minimal cuts （ d d dd -MCs） 和 d d dd -MPs 来间接评估可靠性，正如 Lin 等人 [23] 和 Jane 等人 [24] 首次提出的那样。以 d d dd -MPs 为例，多态网络的可靠性可以通过所有 d d dd -MP 的并集概率来计算，例如包含-排除法 [25]、不相交乘积之和原理 [26]、[27]、[28] 和状态空间分解法 [29]、[30]、[31]。
The first step in the indirect approach is to search the d d dd-MPs. An efficient d d dd-MP searching method is based on all binary minimal paths (MPs) as prior information [32]. Employing implicit enumeration, Lin et al. [23] proposed an MP-based formulation with three constraints to identify d d dd-MP candidates and obtain the d d dd-MPs for a particular d d dd level. Furthermore, by demonstrating that the second constraint in [23] is unnecessary, Jane et al. [24] reduced the number of constraints from three to two. Yeh [33] improved this method by considering the cycles in a network. By including a rapid enumeration method in the d d dd-MP search algorithm, Chen [34] considerably increased its effectiveness. Yeh [35] presented a mathematical model to seek d d dd-MP candidates inspired by the flow conservation conditions and the definition of d d dd-MP candidates. They further improved the algorithm by proposing a node-based sequential implicit enumeration method [36]. Forghani-Elahabad and Bonani [37] proposed a simple algorithm to calculate the solutions of the Diophantine system, which was used to find all the d d dd-MPs. Niu et al. [38] proposed a distinctive method that integrates the traditional maximum-flow algorithm and a partition technique to find all d d dd-MPs.
间接方法的第一步是搜索 d d dd -MP。一种高效的 d d dd -MP 搜索方法是将所有二进制最小路径 （MP） 作为先验信息 [32]。Lin等[23]采用隐式枚举法，提出了一种基于MP的公式，具有三个约束条件来识别 d d dd -MP候选者并获得特定 d d dd 级别的 d d dd -MP。此外，通过证明 [23] 中的第二个约束是不必要的，Jane 等人 [24] 将约束的数量从 3 个减少到 2 个。Yeh [33] 通过考虑网络中的周期来改进这种方法。通过在 d d dd -MP 搜索算法中包含快速枚举方法，Chen [34] 大大提高了其有效性。Yeh [35] 提出了一个数学模型来寻找 d d dd -MP 候选者，该模型受到流动守恒条件和 d d dd -MP 候选者的定义的影响。他们通过提出一种基于节点的顺序隐式枚举方法[36]进一步改进了算法。Forghani-Elahabad 和 Bonani [37] 提出了一种简单的算法来计算丢番图系统的解，该算法用于查找所有 d d dd -MP。Niu 等 [38] 提出了一种独特的方法，该方法集成了传统的最大流量算法和分区技术来查找所有 d d dd -MP。
These methods focus on a particular d d dd level. However, the performance metric of the multistate network proposed in [7] is based on the reliabilities of all possible d d dd levels. Bai et al. [39] developed a recursive algorithm to obtain all d d dd-MPs for all possible d d dd levels simultaneously by adding MPs and real ( d − 1 d − 1 d-1d-1 )MPs. Based on this mechanism, Yeh [40] analyzed redundant and duplicate d d dd-MP candidates. Bai et al. [41] proposed a method
这些方法侧重于特定 d d dd 级别。然而，[7] 中提出的多状态网络的性能指标是基于所有可能 d d dd 级别的可靠性。Bai等[39]开发了一种递归算法，通过添加MP和实（ d − 1 d − 1 d-1d-1 ）MP来同时获得所有可能 d d dd 水平的所有 d d dd -MP。基于这种机制，Yeh [40]分析了冗余和重复 d d dd 的-MP候选者。Bai等[41]提出了一种方法
to generate fewer duplicate d d dd-MP candidates for all d d dd levels by storing the search steps.
通过存储搜索步骤为所有 d d dd 级别生成更少的重复 d d dd -MP 候选项。
The studies mentioned above were based on a fixed network configuration and did not consider adjustments to the network configuration. However, when a network suffers a disruption and recovers, the state distributions of the components may transfer, which may change the maximum states of the components [7]. For example, if a highway suffers from debris flow and partial lane damage, the probability of the traffic flow being in the perfect state becomes 0 and even in some intermediate states may also become 0 . Thus, the maximum operational state of the component cannot remain unchanged. Additionally, recovery measures may change the network topology. Taking a UAV swarm information exchange network as an example [17], the relinking between two agents that were not in contact directly before brings new components to the original network topology. In this study, the changes in the maximum state of the component or network topology are all the network configuration adjustments. Adjustments in the network configuration indicate that the d d dd-MPs have also changed. Adjustments to the network configuration may occur several times during the resilience process. However, the procedures for searching d d dd-MPs have proved to be an NP-hard problem [39]. Thus, it is time consuming to repeatedly search the d d dd-MPs when the network configuration changes.
上述研究基于固定网络配置，没有考虑对网络配置的调整。然而，当网络遭受中断并恢复时，组件的状态分布可能会转移，这可能会改变组件的最大状态 [7]。例如，如果一条高速公路遭受泥石流和部分车道损坏，则交通流处于完美状态的概率变为 0，甚至在某些中间状态也可能变为 0。因此，组件的最大运行状态不能保持不变。此外，恢复措施可能会更改网络拓扑。以无人机集群信息交换网络为例 [17]，之前没有直接接触的两个代理之间的重新链接为原始网络拓扑带来了新的组件。在本研究中，组件或网络拓扑的 maximum state 的变化都是网络配置调整。网络配置中的调整表明 d d dd -MP 也已更改。在弹性过程中，可能会多次调整网络配置。然而，搜索 d d dd -MPs 的过程已被证明是一个 NP 难题 [39]。因此，当网络配置更改时，重复搜索 d d dd -MP 非常耗时。
In addition, reliability and resilience assessments are vital for designing and optimizing systems [42], [43], [44], [45], [46]. Engineers or managers may attempt to adjust the network configuration during the design and optimization phases. However, this process also encounters the challenge of spending a significant amount of time repeatedly searching for d d dd-MPs.
此外，可靠性和弹性评估对于设计和优化系统至关重要[42]、[43]、[44]、[45]、[46]。工程师或管理人员可能会尝试在设计和优化阶段调整网络配置。但是，此过程也遇到了花费大量时间重复搜索 d d dd -MP 的挑战。
The question, then, is how to update the d d dd-MPs with less computational effort when the network configuration changes. The following were focused on to address this question.
那么，问题是当网络配置更改时，如何以更少的计算工作量更新 d d dd -MP。为了解决这个问题，我们重点介绍了以下内容。
First, analyzing the definition of d d dd-MPs indicates that the original d d dd-MPs of the network before a disturbance are valuable information that can help update the d d dd-MPs when the maximum operational states of the components change. Therefore, two d d dd-MP updating methods were developed for all levels d d dd by deleting unqualified d d dd-MPs or adding qualified d d dd-MPs during the resilience process.
首先，分析 -MPs 的 d d dd 定义表明，干扰发生前网络的原始 d d dd -MP 是有价值的信息，可以帮助在组件的最大运行状态发生变化时更新 d d dd -MP。因此，通过在弹性过程中删除不合格的 d d dd -MP 或添加合格的 d d dd -MP，为所有级别 d d dd 开发了两种 d d dd -MP 更新方法。
Second, when the network topology changes, the qualified d d dd-MPs are retained, focusing on the new d d dd-MPs generated from the new components. Thus, an all-level d d dd-MP search algorithm for new components was developed based on Bai’s [39], [41] method.
其次，当网络拓扑发生变化时，将保留合格的 d d dd -MP，并专注于从新组件生成的新 d d dd -MP。因此，基于 Bai [39]， [41] 方法开发了一种针对新组件的全级 d d dd -MP 搜索算法。
Third, efficiency investigations and an application case study were conducted to demonstrate the performances and effects of the proposed algorithms.
第三，进行了效率调查和应用案例研究，以证明所提出的算法的性能和效果。
The rest of this article is organized as follows. In Section II, the framework of the d d dd-MP searching is presented. In Section III, two d d dd-MP updating algorithms are proposed for multistate networks at different phases of the resilience process. In Section IV, the d d dd-MP search algorithm for new components is introduced. Efficiency investigations are reported in Section V. In Section VI, an application case based on a transport network is
本文的其余部分组织如下。在第 II 节中，介绍了 d d dd -MP 搜索的框架。在第 III 节中，为处于弹性过程不同阶段的多态网络提出了两种 d d dd -MP 更新算法。在第 IV 节中，介绍了新组件的 d d dd -MP 搜索算法。效率调查在第 V 节中报告。在第 VI 节中，基于传输网络的应用案例是
Fig. 1. Bridge network.  图 1.桥接网络。
discussed. Finally, Section VII concludes the article. This work is based on the work presented at a conference by Liu et al. [51].
讨论。最后，第七节对本文进行了总结。这项工作基于 Liu 等人 [51] 在会议上展示的工作。

II. Framework of D D DD-MP Searching in Resilience Process
II. 弹性过程中 D D DD 的 -MP 搜索框架

In this section, the preliminaries of this study are introduced. Then, the d d dd-MP searching framework is given.
在本节中，介绍了本研究的初步内容。然后，给出 d d dd -MP 搜索框架。

A. Preliminaries  A. 初步活动

A direct network G ( V , E , m ) G ( V , E , m ) G(V,E,m)G(V, E, \boldsymbol{m}), which is composed of a finite set of nodes V V VV and a set of arcs E E EE, is considered, where the numbers of nodes and arcs are m m mm and n n nn. Here, i i ii is denoted as an arc, and E = { 1 , 2 , … , n } E = { 1 , 2 , … , n } E={1,2,dots,n}E=\{1,2, \ldots, n\}. For each arc i ∈ E , c i ∈ i ∈ E , c i ∈ i in E,c_(i)ini \in E, c_{i} \in { 0 , 1 , … , m i } 0 , 1 , … , m i {0,1,dots,m_(i)}\left\{0,1, \ldots, m_{i}\right\} is used to refer to the capacity of this component, where m i m i m_(i)m_{i} is the maximum capacity (maximum state) of arc i i ii. Then, m = ( m 1 , m 2 , … , m n ) m = m 1 , m 2 , … , m n m=(m_(1),m_(2),dots,m_(n))\boldsymbol{m}=\left(m_{1}, m_{2}, \ldots, m_{n}\right) is the vector of the maximum states of the components. When x = ( x 1 , x 2 , … , x n ) x = x 1 , x 2 , … , x n x=(x_(1),x_(2),dots,x_(n))\boldsymbol{x}=\left(x_{1}, x_{2}, \ldots, x_{n}\right) is the component state vector of the network, the d d dd-MPs are the component state vectors that satisfy the following conditions.
考虑由一组有限的节点和一组弧 组成的直接网络 G ( V , E , m ) G ( V , E , m ) G(V,E,m)G(V, E, \boldsymbol{m}) E E EE ，其中节点和弧的数量为 m m mm 和 n n nn 。 V V VV 这里， i i ii 表示为弧， 和 E = { 1 , 2 , … , n } E = { 1 , 2 , … , n } E={1,2,dots,n}E=\{1,2, \ldots, n\} .对于每个 arc i ∈ E , c i ∈ i ∈ E , c i ∈ i in E,c_(i)ini \in E, c_{i} \in { 0 , 1 , … , m i } 0 , 1 , … , m i {0,1,dots,m_(i)}\left\{0,1, \ldots, m_{i}\right\} 用于指代此组件的容量，其中 m i m i m_(i)m_{i} 是 arc i i ii 的最大容量（最大状态）。然后， m = ( m 1 , m 2 , … , m n ) m = m 1 , m 2 , … , m n m=(m_(1),m_(2),dots,m_(n))\boldsymbol{m}=\left(m_{1}, m_{2}, \ldots, m_{n}\right) 是分量的最大状态的向量。when x = ( x 1 , x 2 , … , x n ) x = x 1 , x 2 , … , x n x=(x_(1),x_(2),dots,x_(n))\boldsymbol{x}=\left(x_{1}, x_{2}, \ldots, x_{n}\right) 是网络的组件状态向量，则 d d dd -MPs 是满足以下条件的组件状态向量。
  1. ϕ ( x ) ≥ d , ϕ ( ⋅ ) ϕ ( x ) ≥ d , ϕ ( ⋅ ) phi(x) >= d,phi(*)\phi(\boldsymbol{x}) \geq d, \phi(\cdot) is the system structure function.
    ϕ ( x ) ≥ d , ϕ ( ⋅ ) ϕ ( x ) ≥ d , ϕ ( ⋅ ) phi(x) >= d,phi(*)\phi(\boldsymbol{x}) \geq d, \phi(\cdot) 是系统结构函数。
  2. ϕ ( y ) < d ϕ ( y ) < d phi(y) < d\phi(\boldsymbol{y})<d for any y < x y < x y < x\boldsymbol{y}<\boldsymbol{x}, where y < x y < x y < x\boldsymbol{y}<\boldsymbol{x} means y i < x i y i < x i y_(i) < x_(i)y_{i}<x_{i} for all i i ii.
    ϕ ( y ) < d ϕ ( y ) < d phi(y) < d\phi(\boldsymbol{y})<d for any y < x y < x y < x\boldsymbol{y}<\boldsymbol{x} ， 其中 y < x y < x y < x\boldsymbol{y}<\boldsymbol{x} 表示 y i < x i y i < x i y_(i) < x_(i)y_{i}<x_{i} for all i i ii .
    Given all d d dd-MPs, which are denoted as z 1 , z 2 , … , z L z 1 , z 2 , … , z L z^(1),z^(2),dots,z^(L)\boldsymbol{z}^{1}, \boldsymbol{z}^{2}, \ldots, \boldsymbol{z}^{L}, the d d dd-MPs matrix, d d dd-MPM, is defined as K d = [ z 1 , z 2 , … , z L d ] T K d = z 1 , z 2 , … , z L d T K_(d)=[z^(1),z^(2),dots,z^(L_(d))]^(T)\boldsymbol{K}_{d}=\left[\boldsymbol{z}^{1}, \boldsymbol{z}^{2}, \ldots, \boldsymbol{z}^{L_{d}}\right]^{T}, where L d L d L_(d)L_{d} is the number of current d d dd-MPs, and d ∈ d ∈ d ind \in { 1 , 2 , … , M } { 1 , 2 , … , M } {1,2,dots,M}\{1,2, \ldots, M\} is the flow from the source node to the sink node. In addition, M M MM is the maximum flow in the network. As an example, a bridge network with six components is shown in Fig. 1 [30]. The maximum state vector m = ( 3 , 2 , 1 , 1 , 1 , 2 ) m = ( 3 , 2 , 1 , 1 , 1 , 2 ) m=(3,2,1,1,1,2)\boldsymbol{m}=(3,2,1,1,1,2). Then, the all-level d d dd-MPMs are as
    给定所有 d d dd -MPs（表示为 z 1 , z 2 , … , z L z 1 , z 2 , … , z L z^(1),z^(2),dots,z^(L)\boldsymbol{z}^{1}, \boldsymbol{z}^{2}, \ldots, \boldsymbol{z}^{L} ），则 d d dd -MPs 矩阵 d d dd -MPM 定义为 K d = [ z 1 , z 2 , … , z L d ] T K d = z 1 , z 2 , … , z L d T K_(d)=[z^(1),z^(2),dots,z^(L_(d))]^(T)\boldsymbol{K}_{d}=\left[\boldsymbol{z}^{1}, \boldsymbol{z}^{2}, \ldots, \boldsymbol{z}^{L_{d}}\right]^{T} ，其中 L d L d L_(d)L_{d} 是当前 d d dd -MPs 的数量，是从 d ∈ d ∈ d ind \in { 1 , 2 , … , M } { 1 , 2 , … , M } {1,2,dots,M}\{1,2, \ldots, M\} 源节点到接收器节点的流。此外， M M MM 是网络中的最大流量。例如，一个由六个组件组成的桥接网络如图 1 [30] 所示。最大状态向量 m = ( 3 , 2 , 1 , 1 , 1 , 2 ) m = ( 3 , 2 , 1 , 1 , 1 , 2 ) m=(3,2,1,1,1,2)\boldsymbol{m}=(3,2,1,1,1,2) .那么，所有级别的 d d dd -MPM 为
K 1 = [ 0 0 0 0 1 1 0 1 0 1 1 0 1 0 1 0 0 1 1 1 0 0 0 0 ] K 1 = 0 0 0 0 1 1 0 1 0 1 1 0 1 0 1 0 0 1 1 1 0 0 0 0 K_(1)=[[0,0,0,0,1,1],[0,1,0,1,1,0],[1,0,1,0,0,1],[1,1,0,0,0,0]]\boldsymbol{K}_{1}=\left[\begin{array}{llllll} 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 \end{array}\right]
Fig. 2. Resilience process of the component.
图 2.组件的弹性过程。
K 2 = [ 1 0 1 0 1 2 2 2 0 0 0 0 2 1 1 0 0 1 1 1 0 0 1 1 1 2 0 1 1 0 ] K 3 = [ 3 2 1 0 0 1 2 2 0 0 1 1 2 1 1 0 1 2 ] K 4 = [ 3 2 1 0 1 2 ] . K 2 = 1 0 1 0 1 2 2 2 0 0 0 0 2 1 1 0 0 1 1 1 0 0 1 1 1 2 0 1 1 0 K 3 = 3 2 1 0 0 1 2 2 0 0 1 1 2 1 1 0 1 2 K 4 = 3 2 1 0 1 2 . {:[K_(2)=[[1,0,1,0,1,2],[2,2,0,0,0,0],[2,1,1,0,0,1],[1,1,0,0,1,1],[1,2,0,1,1,0]]],[K_(3)=[[3,2,1,0,0,1],[2,2,0,0,1,1],[2,1,1,0,1,2]]],[K_(4)=[[3,2,1,0,1,2]].]:}\begin{aligned} & \boldsymbol{K}_{2}=\left[\begin{array}{llllll} 1 & 0 & 1 & 0 & 1 & 2 \\ 2 & 2 & 0 & 0 & 0 & 0 \\ 2 & 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 2 & 0 & 1 & 1 & 0 \end{array}\right] \\ & \boldsymbol{K}_{3}=\left[\begin{array}{llllll} 3 & 2 & 1 & 0 & 0 & 1 \\ 2 & 2 & 0 & 0 & 1 & 1 \\ 2 & 1 & 1 & 0 & 1 & 2 \end{array}\right] \\ & \boldsymbol{K}_{4}=\left[\begin{array}{llllll} 3 & 2 & 1 & 0 & 1 & 2 \end{array}\right] . \end{aligned}

B. Framework of d-MPs Searching
B. D-MP 搜索框架

A network may suffer from disruptive events which cause the network components to degenerate. By implementing recovery measures, the performance of these affected components can be restored. As shown in Fig. 2, the focus is on two phases of the resilience process [47]. The first is the absorption and adaptation phase, and the second is the response and recovery phase.
网络可能会遇到导致网络组件退化的中断事件。通过实施恢复措施，可以恢复这些受影响组件的性能。如图 2 所示，重点是弹性过程的两个阶段 [47]。第一个是吸收和适应阶段，第二个是反应和恢复阶段。
In the absorption and adaptation phase ( T d ≤ t ≤ T s ) T d ≤ t ≤ T s (T_(d) <= t <= T_(s))\left(T_{d} \leq t \leq T_{s}\right), the state probability distribution of a disturbed component transfers to low states dominated, which may lead to a decrease in the maximum state of the component [7]. Transferring the probability distribution may not lead immediately to a decrease in the maximum state. In the response and recovery phase ( T s < t ≤ T r T s < t ≤ T r T_(s) < t <= T_(r)T_{s}<t \leq T_{r} ), the state probability distribution of the affected component returns to normal, and the maximum state of the component is also restored. Under certain circumstances, the recovery of the network brings new components rather than recovering the damaged components. Thus, the topology of the network is changed.
在吸收和适应阶段 ( T d ≤ t ≤ T s ) T d ≤ t ≤ T s (T_(d) <= t <= T_(s))\left(T_{d} \leq t \leq T_{s}\right) ，受干扰成分的状态概率分布转移到低态占主导地位，这可能导致成分的最大状态降低 [7]。转移概率分布可能不会立即导致 maximum 状态的减少。在响应和恢复阶段 （ T s < t ≤ T r T s < t ≤ T r T_(s) < t <= T_(r)T_{s}<t \leq T_{r} ），受影响组件的状态概率分布恢复正常，并且组件的最大状态也会恢复。在某些情况下，网络的恢复会带来新的组件，而不是恢复损坏的组件。因此，网络的拓扑发生了变化。
In this study, three algorithms were devised for dealing with the different phases of the resilience process. The framework for searching d d dd-MPs is shown in Fig. 3. The resilience process considered is from T 0 T 0 T_(0)T_{0} to T f T f T_(f)T_{f}, which is associated with the mission requirements [20]. At the beginning, several matrices are used to store the d d dd-MPMs before the distortive event, where U d = K d ( T 0 ) , d ∈ { 1 , 2 , … , M } U d = K d T 0 , d ∈ { 1 , 2 , … , M } U_(d)=K_(d)(T_(0)),d in{1,2,dots,M}\boldsymbol{U}_{d}=\boldsymbol{K}_{d}\left(T_{0}\right), d \in\{1,2, \ldots, M\}. In the absorption and adaptation phases, Algorithm 1 is used to update the d d dd-MPs. In the response and recovery phase, if the network topology is
在这项研究中，设计了三种算法来处理弹性过程的不同阶段。搜索 d d dd -MPs 的框架如图 3 所示。考虑的弹性过程是 从 到 T 0 T 0 T_(0)T_{0} T f T f T_(f)T_{f} ，它与任务要求有关 [20]。开始时，使用多个矩阵来存储扭曲事件之前的 d d dd -MPM，其中 U d = K d ( T 0 ) , d ∈ { 1 , 2 , … , M } U d = K d T 0 , d ∈ { 1 , 2 , … , M } U_(d)=K_(d)(T_(0)),d in{1,2,dots,M}\boldsymbol{U}_{d}=\boldsymbol{K}_{d}\left(T_{0}\right), d \in\{1,2, \ldots, M\} 。在吸收和适应阶段，算法 1 用于更新 d d dd -MP。在响应和恢复阶段，如果网络拓扑为