MM*模型下网络的限制局部可诊断性

doi:10.12677/aam.2025.145244

期刊菜单

MM*模型下网络的限制局部可诊断性
Extra Local Diagnosability of Networks under the MM* Model

DOI: 10.12677/aam.2025.145244, PDF, HTML, XML, 科研立项经费支持
作者: 郭慧铃, 张淑蓉^*：太原理工大学数学学院，山西太原
关键词: 局部诊断；MM*模型；限制故障模型；多处理器系统；Local Diagnosis； MM* Model； Restricted Fault Model； Multiprocessor System

摘要: 故障诊断对提升大规模网络可靠性意义重大。实际应用中，往往无需全局诊断，仅需确定信息传输区域内特定顶点(处理器)的工作状态。为此提出局部诊断方法，即设计包含特定顶点v的子网络，通过分析该子网络基于诊断模型得到的症状判断v是否故障。为保障故障网络局部连通性，引入h-限制故障模型，该模型要求移除所有故障顶点后网络的每个连通分量所含顶点数大于h。基于此，进一步提出h-限制局部可诊断性的概念，并给出在MM*模型下估计顶点v的限制局部可诊断性的充分条件，同时设计了包含顶点v的子网络结构

T M (v; h)

。

Abstract: Fault diagnosis is crucial for improving the reliability of large-scale networks. In practice, it is often unnecessary to diagnose the entire network. Instead, determining the operational status of speciﬁc vertices (processors) within a particular information transmission region is more important. To address this, we propose a local diagnosis method that constructs a sub-network containing a speciﬁc vertex v. By analyzing the symptoms of this sub-network under a given diagnosis model, we can determine whether v is faulty. To ensure local network connectivity in the presence of faults, we introduce the h-extra fault model. This model requires that after removing all faulty vertices, each connected component of the network must have more than h vertices. Based on this, we further introduce the concept of h-extra local diagnosability. We provide sufficient conditions for estimating the extra local diagnosability of a vertex v under the MM* model and design a sub-network structure

T M (v; h)

that includes vertex v.

文章引用：郭慧铃, 张淑蓉. MM*模型下网络的限制局部可诊断性[J]. 应用数学进展, 2025, 14(5): 153-161. https://doi.org/10.12677/aam.2025.145244

1. 引言

随着互联网技术进入5G/6G高速发展阶段，现代互联网络已构成数字经济时代的核心支撑体系。在该体系下，网络稳定性直接决定了系统服务的连续性——若关键节点发生异常，可能引发数据链路中断、服务崩溃等连锁反应。因此，及时准确的故障诊断能够确保系统尽快恢复正常运行，从而减少损失。

Dahbura和Masson [1]提出了一种时间复杂度为 $O (n^{2.5})$ 的算法，能够有效识别故障处理器集合。有两种知名的诊断模型，一种是由Preparata等人[2]提出的PMC模型，另一种是由Maeng和Malek [3]介绍的MM模型。在PMC模型中，任意两个相邻的处理器可以互相测试。在MM模型中，一个处理器会将相同的任务发送给它的两个相邻处理器，并比较反馈结果。Sengupta和Dahbura [4]提出了一种MM模型的特例，称为MM*模型，其中每个处理器必须测试其任意一对相邻处理器。

Figure 1. Two diagnosis structures: $T (v; t)$ and $T (v; t - 2, 2)$

图1. 两种诊断结构： $T (v; t)$ 和 $T (v; t - 2, 2)$

网络的拓扑结构可以用图来表示。在一般故障模型下，Hsu等人[5]于2007年提出了PMC模型下的局部可诊断性概念，并指出以往的研究主要集中在系统的整体可诊断性上，而忽略了网络内的局部信息。通过计算每个处理器的局部可诊断性，可以更准确地推断整个网络的状态。此外，他们提出了两种PMC模型下的结构： $T (v; t)$ 和 $T (v; t - 2, 2)$ ，可用于确定处理器v的局部可诊断性(见图1)，其中t是v的邻居数。

2009年，Chiang等人[6]指出局部可诊断性与传统可诊断性密切相关。他们研究了在MM*模型下单个顶点的局部可诊断性，并提出了一个名为扩展星形(Extended Star)的局部结构，并基于该结构设计了相应的算法。这些研究为系统级故障诊断提供了更多方法和可能性。

此外，2022年，Chen和Hsu等人[7]提出了PMC模型下更一般的结构。同年，Chen和Lin等人[8]提出了MM*模型下改进的、更全面的结构，并设计了相关算法。2024年，Lv等人[9]提出了MM*模型下条件故障局部诊断的更高效算法，并优化了故障节点数的上界。

随后，一些研究人员(如Lin [10]-[12]、Chen [7] [8]、Lin [13]和Yuan [14]等)设计了一些重要的局部故障诊断算法。在这些算法中，对于网络中的任意给定节点，研究人员找到了包含该节点的特定子结构，并使用这些算法在故障诊断策略下进行子结构自诊断，从而确定该节点是否出现故障。这种方法更适合于故障分布不均匀的大规模网络，我们可以通过局部诊断来维持多处理器网络的功能。

在传统多处理器系统的系统级诊断中，通常假设不同的处理器可以同时出现故障。然而，一种特殊情况是，如果某个处理器v的所有邻居都出现故障，则无法通过v的邻居来判断v是否出现故障。实际上，这种情况的概率非常小。因此，Lai等人[15]引入了一种称为条件故障诊断的度量方法，声称故障节点集合不能包含任何处理器的所有邻居。

此外，大规模故障可能导致网络断开，并将网络分割成多个连通分量。同时，考虑到故障节点的邻居也可能受到影响，那么正常工作的处理器通常会处于一个安全的子网络(即连通分量)范围内。在这种情况下，作为条件故障诊断的推广，Fàbrega等人[16]提出了h-限制故障模型，要求每个连通分量包含的节点数超过h。为了更好地反映网络的系统级可诊断性，Zhang和Yang [17]于2016年推广了条件可诊断性的概念，提出了h-限制可诊断性，即在每个无故障连通分量包含超过h个顶点的条件下，系统能够保证识别出的最大故障节点数。h-限制可诊断性在许多重要网络中受到了广泛关注，例如文献[18] [19]。然而，据我们所知，目前尚未有关于在h-限制故障模型下一般网络的局部诊断问题的研究结果。因此，基于上述研究，我们将定义h-限制局部可诊断性，并设计相应的局部诊断结构。

本文主要提出了一种新的概念——可诊断性，并提供了判断系统是否在任意处理器处h-限制局部可诊断的充分条件；设计了网络中任意顶点v的结构TM(v; h)。本文的结构安排如下：第2节介绍预备知识；第3节介绍限制局部可诊断性的概念，第4节提出了验证网络h-限制局部可诊断性的充分条件；最后，第5节总结了本文的研究成果。

2. 基本概念及符号说明

在多处理器系统的研究中，图论已成为一种重要的数学工具。系统可以通过无向简单图G进行有效建模。在此图中，任意顶点v和边(u, v)分别表示单个处理器v以及两个处理器u和v之间的通信链路。图G中的顶点集(边集)分别用V(G) (E(G))表示。

路径是一个序列 $P = (v_{0}, v_{1}, \dots, v_{k})$ ，包含k + 1个不同的顶点，且满足 $(v_{i}, v_{i + 1}) \in E (G)$ ( $i = 0, 1, \dots, k - 1$ )。P的长度为k。如果 $v_{0} = v_{k}$ ，则称P为一个环。从顶点u到v的最短路径长度称为u和v之间的距离。图G的围长，记为g(G)，是指G中最短环的长度。

对于图G中的任意顶点v，与v相邻的顶点集合记为 $N_{G} (v)$ 。顶点v的度定义为 $d_{G} (v) = | N_{G} (v) |$ 。图G中所有顶点的最小度记为δ(G) (简写为δ)。如果图G中每个顶点的度均为k，则称G为一个k-正则图。如果两条边有一个公共顶点，则它们也被认为是相邻的。对于任意集合 $S \subset V (G)$ ，定义 $N_{G} (S) = \cup_{v \in S} N_{G} (v) \ S$ 。

在无向图G中，对于任意两个顶点 $u, v \in V (G)$ ，如果在G中存在一条连接u和v的路径，则称u和v是连通的。如果图中任意两个顶点都是连通的，则称G为连通图。对于任意非空集合 $S \subseteq V (G)$ ，G[S]是以S为顶点集的G的子图，其边集由两端点均在S中的边组成。称G[S]是由S诱导的子图。进一步地，如果G[S]是一个连通子图，并且S与V(G)\S之间没有边，则称G[S]为G的一个连通分支。

对于任意 $F \subseteq V (G)$ ，G-F表示从G中移除F中的顶点及其相关边后得到的子图。如果子图G-F不连通，则称F为G的一个顶点割。G的顶点割中顶点数的最小值称为G的连通度，记为κ(G)。两个集合S₁和S₂的对称差定义为 $S_{1} Δ S_{2} = (S_{1} \ S_{2}) \cup (S_{2} \ S_{1})$ 。

可诊断性相关概念 PMC模型定义如下：对于任意两个相邻顶点u和v，用 $σ (u, v)$ 表示u对v的测试结果。当u无故障时，如果v无故障，则 $σ (u, v) = 0$ ；否则， $σ (u, v) = 1$ 。假设u出现故障，则无论v是否故障， $σ (u, v)$ 均为随机值0或1，这表明该测试结果不可靠。

假设F是V的一个子集。如果F是G中的故障顶点集合，则集合{σ(u, v)|u和v在G中相邻}称为与F一致的症状。由于故障顶点测试其邻居的结果可以随机为0或1，因此与F一致的症状并非唯一。所有可能由F产生的症状集合记为σ(F)，即σ(F) = {σ|F与症状σ一致}。

对于V(G)的任意两个不同子集 $F_{1}$ 和 $F_{2}$ ，如果 $σ (F_{1}) \cap σ (F_{2}) = \emptyset$ ，则可以判断故障顶点集合是 $F_{1}$ 还是 $F_{2}$ ，因此称 $(F_{1}, F_{2})$ 为可区分对。以下是几个重要结论：

引理2.1. [15] 图G是t可诊断的，当且仅当对于任意两个不同的集合 $F_{1}, F_{2} \subseteq V$ ，满足 $| F_{1} | \leq t$ 且 $| F_{2} | \leq t$ ， $(F_{1}, F_{2})$ 是一个可区分对。

引理2.2. [1] 给定图G以及其中任意两个不同的子集 $F_{1}, F_{2} \subseteq V (G)$ ，在MM*模型下， $(F_{1}, F_{2})$ 是一个可区分对，当且仅当至少满足以下三个条件之一：

1) 存在三个顶点 $v \in (F_{1} Δ F_{2})$ 以及 $u, w \in V (G) - (F_{1} \cup F_{2})$ ，使得 $u w, v w \in E (G)$ 。

2) 存在三个顶点 $u, v \in F_{1} \ F_{2}$ 以及 $w \in V (G) - (F_{1} \cup F_{2})$ ，使得 $u w, v w \in E (G)$ 。

3) 存在三个顶点 $u, v \in F_{2} \ F_{1}$ 以及 $w \in V (G) - (F_{1} \cup F_{2})$ ，使得 $u w, v w \in E (G)$ 。见图2。

Figure 2. Distinguishable pair $(F_{1}, F_{2})$ under the MM* model

图2. MM*模型下的可区分对 $(F_{1}, F_{2})$

局部可诊断性概念 对于局部诊断，Hsu和Tan [5]提出了以下定义。

定义2.3. [5] 给定图G和正整数t，设F是V(G)的一个子集，包含至多t个顶点，且设σ(F)是与F一致的症状。对于任意顶点 $v \in F$ ，如果对于任意子集 $F_{1} \subseteq V (G)$ ，满足 $| F_{1} | \leq t$ 且能产生症状σ(F)，则 $F_{1}$ 包含顶点v，称图G在顶点v处是局部t可诊断的。

以下是限制诊断度的概念。

定义2.4. [17] 图G的顶点子集F是一个h-限制顶点子集，当且仅当G-F的每个连通分支至少包含h + 1个顶点。

定义2.5. [17] 图G是h-限制t可诊断的，当且仅当对于每一对不同的h-限制顶点子集 $F_{1}, F_{2} \subseteq V (G)$ ，满足 $| F_{i} | \leq t$ ( $i = 1, 2$ )， $F_{1}$ 和 $F_{2}$ 是可区分的。图G的h-限制可诊断度，记为 ${\tilde{t}}_{h} (G)$ ，是指G为h-限制t可诊断的最大t值。

3. h-限制局部可诊断性

在过去几十年中，学者们已经得到了许多关于整个网络的h-限制可诊断性的结果。现在，我们考虑h-限制局部可诊断性，并基于定义2.3和引理2.1引入以下定义。

定义3.1. 给定图G和正整数t，设F是V(G)的一个h-限制顶点子集，满足 $| F | \leq t$ ，且设σ(F)是与F一致的症状。对于任意顶点 $v \in F$ ，如果对于任意h-限制顶点子集 $F_{1} \subseteq V (G)$ ，满足 $| F_{1} | \leq t$ 且能产生症状σ(F)，则 $F_{1}$ 包含顶点v，称图G在顶点v处是h-限制局部t可诊断的。

根据定义3.1，可以得到以下结果。

引理3.2. 给定图G和顶点 $v \in V (G)$ ，图G在顶点v处是h-限制局部t可诊断的，当且仅当对于任意两个不同的h-限制集合 $F_{1}, F_{2} \subseteq V (G)$ ，满足 $| F_{1} | \leq t$ 和 $| F_{2} | \leq t$ 且 $v \in F_{1} Δ F_{2}$ ， $(F_{1}, F_{2})$ 是一个可区分对。

证明首先，证明充分性。假设G在顶点v处不是h-限制局部t可诊断的。根据定义3.1，存在两个集合 $F_{1}, F_{2} \subseteq V$ ，使得 $v \in F_{1} Δ F_{2}$ 且 $(F_{1}, F_{2})$ 是一个不可区分对，这与假设矛盾。

接下来，证明必要性。假设G在顶点v处是h-限制局部t可诊断的。假设存在一个不可区分对 $(F_{1}, F_{2})$ ，使得 $v \in F_{1} Δ F_{2}$ 。根据定义3.1， $v \in F_{1} \cap F_{2}$ ，这与假设矛盾。证毕。

上述引理可用于判断系统是否在任意顶点v处是h-限制局部t可诊断的。

对于图G和正整数h，使得G在顶点 $v \in V (G)$ 处是h-限制局部t可诊断的最大t值，称为G在顶点v处的h-限制局部可诊断度，记为 $t_{l (h)} (v)$ 。现在，我们将考虑每个顶点处的h-限制局部可诊断度与G的h-限制可诊断度之间的关系。

引理3.3. 图G是h-限制t可诊断的，当且仅当G在每个顶点处都是h-限制局部t可诊断的。

证明首先，证明充分性。假设G不是h-限制t可诊断的。根据定义2.5，存在至少一对不同的h-限制集合 $F_{1}, F_{2} \subseteq V (G)$ ，满足 $| F_{1} | \leq t$ 和 $| F_{2} | \leq t$ ，且 $F_{1}$ 和 $F_{2}$ 是不可区分的。由于 $F_{1} Δ F_{2} \neq \emptyset$ ，可以选择一个顶点 $v \in F_{1} Δ F_{2}$ 。根据引理3.2，可以得出G在顶点v处不是h-限制局部t可诊断的，这与假设矛盾。

接下来，证明必要性。假设存在一个顶点v，使得G在v处不是h-限制局部t可诊断的。根据引理3.2，存在两个不同的h-限制故障顶点集合 $F_{1}, F_{2} \subseteq V (G)$ ，满足 $| F_{1} | \leq t$ 和 $| F_{2} | \leq t$ ，且 $v \in F_{1} Δ F_{2}$ ， $F_{1}$ 和 $F_{2}$ 是不可区分的。根据定义2.5，可以得出G不是h-限制t可诊断的，这与假设矛盾。证毕。

根据上述结果，可以得到以下推论。

推论3.4. 给定图G，对于任意正整数t，G的h-限制t可诊断度为：

${\tilde{t}}_{h} (G) = \min {t_{l (h)} (v) | v \in V (G)}$ .

4. MM*模型下的限制局部诊断性

在本节中，我们会继续探究在MM*模型下的限制局部诊断性，首先我们将通过定理4.1给出图G中任意顶点v在MM*模型下为h-限制局部t-可诊断的充分条件。然后我们设计了一种新的结构 $T M (v; h)$ ，通过分析结构中点的测试结果，我们便能得到点v的故障状态。

4.1. 限制局部诊断性

在给出定理4.1之前，我们先了解点覆盖的相关概念以及介绍所用到的参数 $M_{h} (v)$ 。图G的点覆盖是指一个点子集Q，属于V(G)，使得E(G)中的每条边至少有一个端点在Q中。具有最小数量的点覆盖数被称为最小点覆盖。对于图G中的任意顶点v， $M_{h} (v)$ 表示任意 $S \subseteq V (G)$ 中 $N_{G} (S)$ 的最小顶点数，满足 $| S | = h + 1$ ，G[S]连通且 $v \in S$ ，即

$M_{h} (v) = \min {| N_{G} (S) | | S \subseteq V, v \in S, | S | = h + 1, G [S] 是连通的}$ .

定理4.1. 给定连通图G，顶点 $v \in V (G)$ 和正整数 $h \geq 2$ ，任意两点之间没有公共邻点，如果对于每个h-限制集合 $F \subseteq V (G) \ {v}$ ，满足 $C_{v}$ 的点覆盖数大于等于 $2 (M_{h} (v) + h - | F |) + 1$ ，其中 $C_{v}$ 是G-F中包含v的连通分支，则图G在顶点v处是h-限制局部 $M_{h} (v) + h$ 可诊断的。

证明我们通过反证法来证明。假设图G在顶点v处不是h-限制局部可诊断的。根据引理3.2，存在两个不同的h-限制集合 $F_{1}$ 和 $F_{2}$ ，使得 $| F_{1} |, | F_{2} | \leq M_{h} (v) + h$ 并且 $v \in F_{1} Δ F_{2}$ ，使得 $F_{1}$ 和 $F_{2}$ 是不可区分的。令 $F = F_{1} \cap F_{2}$ ，则 $| F | \leq M_{h} (v) + h - 1$ ，由于当 $F_{1} \ F_{2} \neq \emptyset$ (分别 $F_{2} \ F_{1} \neq \emptyset$ )并且 $V (G) \ (F_{1} \cup F_{2}) \neq \emptyset$ 时， $G [F_{1} \ F_{2}]$ ( $G [F_{2} \ F_{1}]$ )和 $G - (F_{1} \cup F_{2})$ 的每个连通分支至少有h + 1个顶点。即 $F = F_{1} \cap F_{2}$ 也是一个h-限制顶点子集，并且 $F \subseteq V (G) \ {v}$ 。

假设 $C_{v}$ 是G-F的一个的连通分支，使得 $v \in V (C_{v})$ ，根据定理4.1的条件可得 $C_{v}$ 的点覆盖的顶点数大于等于 $2 (M_{h} (v) + h - | F |) + 1$ ，将这个数值与 $| F_{1} Δ F_{2} | \leq 2 (M_{h} (v) + h - | F |)$ 以及点v属于 $F_{1} Δ F_{2}$ 进行比较，可以得出 $F_{1} Δ F_{2}$ 无法成为 $C_{v}$ 的点覆盖，换句话说，在 $C_{v}$ 的点覆盖中至少有一个顶点位于 $F_{1} Δ F_{2}$ 之外。

Figure 3. A path which from edge e to point v through sets $F_{1}$ or $F_{2}$

图3. 一条从边e到点v经过集合 $F_{1}$ 或 $F_{2}$ 的路径

因此根据点覆盖的性质，如图3在 $C_{v}$ 中存在一条边 $e = (x, y)$ ，这条边位于 $F_{1} Δ F_{2}$ 之外。由于边e、节点x和y以及点v都属于同一个连通分支 $C_{v}$ ，因此存在一条从边e到点v经过集合 $F_{1}$ 或 $F_{2}$ 的路径。根据引理3.2的条件1， $(F_{1}, F_{2})$ 是一对可区分的集合。这就产生了矛盾，从而得到图G在顶点v处是h-限制局部 $M_{h} (v) + h$ 可诊断的。 □

4.2. 结构 $T M (v; h)$

给定正整数 $h \geq 1$ 和 $t \geq 1$ ，设G是一个图，使得 $δ (G) \geq 4$ ，并且G有一个h-限制故障顶点集F，满足G[F]的每个连通分支至少包含两个顶点。对于任意顶点 $v \in V (G)$ ，设 $d = d_{G} v$ ， $R_{v} = 2$ 。在下文中，我们提出了子图 $T M (v; h)$ ，其顶点集 $V (T M (v; h))$ 和边集 $E (T M (v; h))$ 的设计如下(如图4所示)。

$V (T M (v; h))$ 的构造过程：

步骤1. 设 $X_{0} = {v}$ 和 $X_{1} = N_{G} (v) = {x_{11}, x_{21}, \dots, x_{d 1}}$ 。

步骤2. 设 $L_{v} = 2 \times (2 \times (M_{h} (v) + h) + 1 - R_{v} / 2) = 4 M_{h} (v) + 4 h$ 。

对于每个顶点 $u \in X_{R_{v}}$ ，设 $P_{u}$ 是 $G - \cup_{i = 0}^{R_{v} - 1} X_{i}$ 中从u出发的一条路径，满足以下条件：

1) $P_{u}$ 的长度为 $L_{v} - 1$ ；

2) 对于每个 $w \in V (P_{u})$ ， $d_{G} (w) = d$ ；

3) 对于任意两个顶点 $u, w \in X_{1}$ ， $V (P_{u}) \cap V (P_{w}) = \emptyset$ ，并且对于每个 $u_{1} \in V (P_{u})$ 和 $w_{1} \in V (P_{w})$ ，有 $N_{G} (u_{1}) \cap N_{G} (w_{1}) = \emptyset$ 。

设 $X = \cup_{u \in X_{1}} V (P_{u})$ 。

步骤3. 设 $V (T M (v; h)) = X_{0} \cup X_{1} \cup X$ 。

$E (T M (v; h))$ 的构造过程：

设 $E_{1} = {(v, u) : u \in X_{1}}$ 。

那么，我们有：

$E (T M (v; h)) = E_{1} \cup (\underset{u \in X_{1}}{\cup} E (P_{u}))$

Figure 4. Diagnostic tree structure TM(v; h)

图4. 诊断树结构TM(v; h)

定理4.2. 给定一个图G，一个顶点 $v \in V (G)$ 和一个正整数 $h \geq 2$ ，假设 $d = d_{G} (v) \geq 4$ ，并且对于任意一个h-限制故障集合 $F \subseteq V (T M (v; h)) \ {v}$ 。如果G中存在结构 $T M (v; h)$ ，则图G在顶点v处是h-限制局部( $M_{h} (v) + h$ )-可诊断的。

证明根据定理4.1，对于任意h-限制故障集合 $F \subseteq V (T M (v; h)) \ {v}$ ，只需证明在 $T M (v; h) - F$ 中包含v的连通分支 $C_{v}$ 的点覆盖数大于等于 $2 (M_{h} (v) + h - | F |) + 1$ 。

因为 $h \geq 2$ 并且F是h-限制故障集，所以肯定存在某个 $u \in X_{R_{v}}$ ，使得 $V P_{u} \subseteq V C_{v}$ 。由于树 $T M (v; h)$ 中 $C_{v}$ 的连通性，存在一条从v到u的路径 $P_{1}$ 在 $C_{v}$ 中。那么 $P = P_{1} \cup P_{u}$ 是一条包含 $R_{v} + L_{v}$ 个顶点的路径。因此，

$\begin{matrix} | V (C_{v}) | \geq R_{v} + L_{v} \\ = R_{v} + 2 (2 (M_{h} (v) + h) + 1 - \frac{R_{v}}{2}) \\ = 4 (M_{h} (v) + h) + 2 \end{matrix}$

此时 $C_{v}$ 是一个包含路P的树结构，我们可以得到 $C_{v}$ 的点覆盖数至少是

$2 (M_{h} (v) + h) + 1 \geq 2 (M_{h} (v) + h - | F |) + 1$ 。因此，在 $T M (v; h) - F$ 中包含v的连通分支 $C_{v}$ 满足定理4.1中的条件。因此，根据定理4.1，图G在顶点v处是h-限制局部可诊断的。证毕。

5. 总结

本文提出了一种基于局部诊断的大规模网络故障诊断方法，引入了h-限制故障模型，并设计了子网络结构 $T M (v; h)$ 。通过理论分析，给出了在MM*模型下顶点v的限制局部可诊断性条件。该方法能够高效判断特定顶点的工作状态，同时保障网络的局部连通性，提升了网络可靠性。尽管如此，本研究仍存在局限性，如模型的适用范围和动态适应性有待进一步验证。未来工作将聚焦于优化诊断算法、扩展模型适用范围，并探索其在动态网络中的应用。本文的研究为大规模网络的局部故障诊断提供了一种新的思路，具有重要的理论和实际意义。

基金项目

山西省基础研究计划资助项目(202103021224058)。

NOTES

^*通讯作者。

参考文献

[1]	Dahbura, A.T. and Masson, G.M. (1984) An 0(n^2.5) Fault Identification Algorithm for Diagnosable Systems. IEEE Transactions on Computers, 33, 486-492. https://doi.org/10.1109/tc.1984.1676472
[2]	Preparata, F.P., Metze, G. and Chien, R.T. (1967) On the Connection Assignment Problem of Diagnosable Systems. IEEE Transactions on Electronic Computers, 16, 848-854. https://doi.org/10.1109/pgec.1967.264748
[3]	Maeng, J. and Malek, M. (1981) A Comparison Connection Assignment for Self-Diagnosis of Multiprocessor Systems. In: Proceeding of the 11th International Symposium on Fault-Tolerant Computing, ACM Press, 173-175.
[4]	Sengupta, A. and Dahbura, A.T. (1992) On Self-Diagnosable Multiprocessor Systems: Diagnosis by the Comparison Approach. IEEE Transactions on Computers, 41, 1386-1396. https://doi.org/10.1109/12.177309
[5]	Hsu, G. and Tan, J.J.M. (2007) A Local Diagnosability Measure for Multiprocessor Systems. IEEE Transactions on Parallel and Distributed Systems, 18, 598-607. https://doi.org/10.1109/tpds.2007.1022
[6]	Chiang, C. and Tan, J.J.M. (2009) Using Node Diagnosability to Determine T-Diagnosability under the Comparison Diagnosis Model. IEEE Transactions on Computers, 58, 251-259. https://doi.org/10.1109/tc.2008.158
[7]	Chen, M., Hsu, D.F. and Lin, C. (2022) A New Structure for a Vertex to Be Locally T-Diagnosable in Large Multiprocessor Systems. Theoretical Computer Science, 934, 81-90. https://doi.org/10.1016/j.tcs.2022.08.020
[8]	Chen, M., Lin, C. and Pai, K. (2022) A Tree Structure for Local Diagnosis in Multiprocessor Systems under Comparison Model. In: Hsieh, S.Y., Hung, L.J., Klasing, R., Lee, C.W. and Peng, S.L., Eds., Communications in Computer and Information Science, Springer, 49-60. https://doi.org/10.1007/978-981-19-9582-8_5
[9]	Lv, Y., Lin, C., Hsu, D.F. and Fan, J. (2024) An Algorithm for Conditional-Fault Local Diagnosis of Multiprocessor Systems under the MM^⁎ Model. Theoretical Computer Science, 987, Article ID: 114372. https://doi.org/10.1016/j.tcs.2023.114372
[10]	Lin, C., Kung, T. and Tan, J.J.M. (2011) Conditional-Fault Diagnosability of Multiprocessor Systems with an Efficient Local Diagnosis Algorithm under the PMC Model. IEEE Transactions on Parallel and Distributed Systems, 22, 1669-1680. https://doi.org/10.1109/tpds.2011.46
[11]	Lin, C., Kung, T. and Tan, J.J.M. (2013) An Algorithmic Approach to Conditional-Fault Local Diagnosis of Regular Multiprocessor Interconnected Systems under the PMC Model. IEEE Transactions on Computers, 62, 439-451. https://doi.org/10.1109/tc.2011.249
[12]	Lin, C., Teng, Y., Tan, J.J.M. and Hsu, L. (2013) Local Diagnosis Algorithms for Multiprocessor Systems under the Comparison Diagnosis Model. IEEE Transactions on Reliability, 62, 800-810. https://doi.org/10.1109/tr.2013.2285031
[13]	Lin, L., Huang, Y., Lin, Y., Hsieh, S. and Xu, L. (2021) FFNLFD: Fault Diagnosis of Multiprocessor Systems at Local Node with Fault-Free Neighbors under PMC Model and MM* Model. IEEE Transactions on Parallel and Distributed Systems, 33, 1739-1751. https://doi.org/10.1109/tpds.2021.3126257
[14]	Yuan, J., Qiao, H., Liu, A. and Wang, X. (2022) Measurement and Algorithm for Conditional Local Diagnosis of Regular Networks under the MM^* Model. Discrete Applied Mathematics, 309, 46-67. https://doi.org/10.1016/j.dam.2021.11.006
[15]	Lai, P., Tan, J.J.M., Chang, C. and Hsu, L. (2005) Conditional Diagnosability Measures for Large Multiprocessor Systems. IEEE Transactions on Computers, 54, 165-175. https://doi.org/10.1109/tc.2005.19
[16]	Fàbrega, J. and Fiol, M.A. (1996) On the Extraconnectivity of Graphs. Discrete Mathematics, 155, 49-57. https://doi.org/10.1016/0012-365x(94)00369-t
[17]	Zhang, S. and Yang, W. (2016) The g-Extra Conditional Diagnosability and Sequential t/k-Diagnosability of Hypercubes. International Journal of Computer Mathematics, 93, 482-497. https://doi.org/10.1080/00207160.2015.1020796
[18]	Lin, L., Hsieh, S., Xu, L., Zhou, S. and Chen, R. (2018) The Relationship between Extra Connectivity and Conditional Diagnosability of Regular Graphs under the PMC Model. Journal of Computer and System Sciences, 95, 1-18. https://doi.org/10.1016/j.jcss.2017.11.004
[19]	Lin, L., Xu, L., Chen, R., Hsieh, S. and Wang, D. (2019) Relating Extra Connectivity and Extra Conditional Diagnosability in Regular Networks. IEEE Transactions on Dependable and Secure Computing, 16, 1086-1097. https://doi.org/10.1109/tdsc.2017.2726541

为你推荐

友情链接