-
并行系统提供了高速的运算潜力，但在高可靠性和容错性方面仍然存在问题，其原因与并行系统的网络拓扑有关，如超立方体，星图和排列图等。系统的可靠性定义为系统没有故障的概率，每个处理器正常运行的概率被记为p。排列图具有高容错性、直径小和低节点度等特点，因此进一步分析排列图的可靠性具有重要意义。
Lin等[1]定义了排列图An,k子图的可靠性，并利用容斥原理给出了子图可靠性的上界以及子图可靠性的近似计算。Chiang等[2]给出了An,k的相关性质，An,k是k (n‒k)正则图，并且有n!/(n‒k)!个节点，同时得出An,k的直径为
$\left\lfloor {3k/2} \right\rfloor $ 。Cheng等[3]发现An,k中两个节点之间的最短路径算法，该算法也可用于解决其他相关图的类似问题。此外，Feng等[4]发现最小故障边的边界使An,k的每个子图$A_{n,k}^{n - m,k - m}$ 失效：当3≤k时，$n + \left\lceil {n/k - 1} \right\rceil - \leqslant {f_1}\left( {n,k} \right){\rm{ }} \leqslant {\rm{ }}2n$ ；当2≤m≤k‒2时，$\dfrac{{n!}}{{\left( {n - m} \right)!}} \leqslant {f_n}\left( {n,k} \right) \leqslant \left( {\begin{array}{*{20}{c}} k\\ {m - 1} \end{array}} \right) \times \dfrac{{n!}}{{\left( {n - m} \right)!}}$ $ - 2\left( {\begin{array}{*{20}{c}} {k - 3}\\ {m - 1} \end{array}} \right) \times$ $ \dfrac{{n!}}{{\left( {n - m + 1} \right)!}}$ 。Yang等[5]也研究了排列图的容错性和可靠性。Cancela等[6]提出了组合特性，来识别源点到终端直径受限的网络可靠性环境中的不相关边，这产生检测和消除网络不相关边的有效过程，同时保持了可靠性。Zhang等[7]研究了网络物理系统的可靠性问题，提出了k-可靠性模型来描述系统中至少有k个节点的连通性，在随机情况下提高网络的可靠性节点故障，当不考虑体内信息时，常规的分层分配策略比随机分层分配策略产生更强的可靠性；在任何情况下，双向互换分配策略比其子图和相应的单向分配策略具有更强的可靠性。但排列图可靠性的近似值鲜有研究，本文主要提出了排列图可靠性的蒙特卡罗近似算法，以及研究了可靠性界的鲁棒性问题。 -
n，k都是整数，其中1≤k<n。
（1）点的定义：从{1,2,···, n}中取k个不同的整数得到排列a1a2···ak，其中ai=aj当且仅当i=j。
（2）边的定义：排列图中的两点连接成边，当且仅当点（排列）中对应位置只有一个不同，比如节点a1···ai‒1aiai+1···ak和a1···ai‒1biai+1···ak的第i个位置不同，则这两个节点之间有边，其中1≤i≤k。图1以A4,2为例进行说明，X4表示A4,2的一个子图。
图 1 排列图A4,2、子图X4、节点24
Figure 1. A4,2、subgraph X4、node 24
-
$A_{n,k}^{n - m,k - m}$ ，对于节点的排列中固定了m个位置，得到相应的子图。为了研究的方便，本文主要对m=1时的子系统可靠性进行研究。对于An,k，有k种划分方式，每个方式有n个互斥的子图$A_{n,k}^{n - 1,k - 1}$ ，共有nk个不同的子图$A_{n,k}^{n - 1,k - 1}$ 。以A4,2为例，X4表示A4,2的一个子图。当m=1时，对于A4,2，其中k=2，A4,2子图的划分就有两种方式，即：固定第一个位置和固定第二个位置划分。如果固定第二个位置，则有X1、X2、X3、X4这4个互斥的子图$A_{4,2}^{3,1}$ 。如果固定第二个位置共有1X、2X、3X、4X这4个不同的子图$A_{4,2}^{3,1}$ 。 -
排列图子图可靠性的计算是一个NP-hard问题，所以可以用排列图子图可靠性的界去衡量排列图子图可靠性。
文献[1]已经给出上界的计算：
根据容斥原理得：
将
$\displaystyle\sum\limits_{i = 1}^{nk} {{r_i}(p)} - \sum\limits_{i < j} {{r_{(i,j)}}(p) + } \sum\limits_{i < j < l} {{r_{(i,j,l)}}(p) - } $ $\displaystyle\sum\limits_{i < j < l < q} {{r_{(i,j,l,q)}}(p)} $ 作为$R_{n,k}^{n - 1,k - 1}(p)$ 的下界，即：
算法一：取排列图可靠性的上下界平均值作为其近似值，即：
根据式(1)，只需计算
$\displaystyle\sum\limits_{i < j < l < q} {{r_{(i,j,l,q)}}(p)} $ 即可得(3)，下面以例1进行说明。例1：以A5,4为例，计算
$R_{5,4}^{4,3}$ 的下界。根据下界的计算公式，只需要分析$\displaystyle\sum\limits_{i < j < l < q} {{r_{(i,j,l,q)}}(p)} $ 。YXXX (因为n=5，所以Y为1、2、3、4、5之间的任意一个数)可以表示一个子图$A_{5,4}^{4,3}$ ，Y也可以位于第二个位置XYXX，对于A5,4，k=4，所以存在4个位置。针对4个子图$A_{{\rm{5,4}}}^{{\rm{4,3}}}$ 的组合情况，每个子图中有一个位置固定，固定的位置上放置一个常数，记为symbol。则4个子图，就会存在4个symbol放在四个固定的位置上。因为4个symbol最多分布在四个位置上，所以存在4种分类：4个symbol分布在一个位置上、4个symbol分布在两个位置上、4个symbol分布在三个位置上和4个symbol分布在四个位置上。（1）一个位置：因为从四个位置中选择一个位置放置symbol，所以位置的选择有
$C_4^1$ 种。因为同一个位置放置4个symbol，而且表示4个不同的子图，4个symbol不能相同，所以symbol的选择有$C_{\rm{5}}^{\rm{4}} $ 种。对于这样的一组$A_{{\rm{5,4}}}^{{\rm{4,3}}}$ ，因为相同位置放置不同的symbol，所以它们之间是互斥的，一共有$4A_{\rm{4}}^{\rm{3}}$ 个节点。(1XXX,2XXX,3XXX,4XXX)就表示这样放置symbol的一组$A_{{\rm{5,4}}}^{{\rm{4,3}}}$ ，如图2所示。
图 2 1XXX, 2XXX, 3XXX, 4XXX
Figure 2. 1XXX, 2XXX, 3XXX, 4XXX
（2）两个位置：因为从四个位置中选择两个位置放置symbol，所以位置的选择有
$C_{\rm{4}}^{\rm{2}}$ 种。因为将4个symbol放置在两个位置上，有3种分法：(1, 3)、(2, 2)和(3, 1)。(1, 3)表示取得的两个位置，第一个位置放1个symbol，第二个位置放3个symbol。(2, 2)表示取得的两个位置，第一个位置放2个symbol，第二个位置放2个symbol，(3, 1)表示取得两个位置，第一个位置放3个symbol，第二个位置放1个symbol，其所得结果和(1, 3)情况类似。（3）三个位置：因为从四个位置中选择三个位置放置symbol，所以位置的选择有
$C_{\rm{4}}^{\rm{3}}$ 种。因为将4个symbol放置在三个位置上，有三种分法：(1, 1, 2)、(1, 2, 1)和(2, 1, 1)。(1, 1, 2)表示第一个位置放1个symbol，第二个位置放2个symbol，第三个位置放2个symbol。由排列组合知这三种分法所得结果一样，所以只对(1, 1, 2)讨论。（4）四个位置：因为从四个位置中选择四个位置放置symbol，所以位置的选择有
$C_{\rm{4}}^{\rm{4}}$ 种，有一种分法：(1, 1, 1, 1)。和文献[1]类似得到
$\displaystyle\sum\limits_{i < j < l < q} {{r_{\left( {i,j,l,q} \right)}}\left( p \right)} $ 计算方法见表1，其中k>3。Reliability One position Two positions Three positions Four positions ${R_1} = C_k^{\rm{1}}C_n^{\rm{4}}{p^{4A_{n - 1}^{k - 1}}}$ 
$\begin{aligned} {R_2} =& C_k^{\rm{2}}(2C_n^{\rm{1}}C_{n - 1}^{\rm{2}}{p^{4A_{n - 1}^{k - 1} - 2A_{n - 2}^{k - 2}}} + \\& 2C_n^{\rm{1}}C_{n - 1}^{\rm{3}}{p^{4A_{n - 1}^{k - 1} - 3A_{n - 2}^{k - 2}}} + 2C_n^{\rm{2}}C_{n - 2}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - 3A_{n - 2}^{k - 2}}}+\\ & C_n^{\rm{2}}{p^{4A_{n - 1}^{k - 1} - {\rm{2}}A_{n - 2}^{k - 2}}} + \\& C_n^{\rm{2}}C_{n - 2}^{\rm{2}}{p^{4A_{n - 1}^{k - 1} - {\rm{4}}A_{n - 2}^{k - 2}}} \end{aligned}$ 
$\begin{aligned} {R_{\rm{3}}} =& C_k^{\rm{3}}({\rm{3}}C_n^{\rm{1}}C_{n - 1}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - 2A_{n - 2}^{k - 2}}} + \\& {\rm{3}}C_n^{\rm{1}}C_{n - 1}^{\rm{2}}{p^{4A_{n - 1}^{k - 1} - {\rm{4}}A_{n - 2}^{k - 2}}} +\\& {\rm{6}}C_n^{\rm{1}}C_{n{\rm{ - 1}}}^{\rm{1}}C_{n - 2}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - {\rm{4}}A_{n - 2}^{k - 2} + A_{n - {\rm{3}}}^{k - {\rm{3}}}}}+\\& {\rm{3}}C_n^{\rm{1}}C_{n{\rm{ - 1}}}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - {\rm{3}}A_{n - 2}^{k - 2}}}+\\ & {\rm{3}}C_n^{\rm{1}}C_{n{\rm{ - 1}}}^{\rm{1}}C_{n - 2}^{\rm{2}}{p^{4A_{n - 1}^{k - 1} - {\rm{5}}A_{n - 2}^{k - 2} + {\rm{2}}A_{n - {\rm{3}}}^{k - {\rm{3}}}}} \end{aligned}$ 
$\begin{aligned} {R_{\rm{4}}} = & C_k^{\rm{4}}(C_n^{\rm{1}}{p^{4A_{n - 1}^{k - 1}}} + \\& {\rm{4}}C_n^{\rm{1}}C_{n - 1}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - {\rm{3}}A_{n - 2}^{k - 2}}}+ \\& {\rm{3}}C_n^{\rm{1}}C_{n - 1}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - {\rm{4}}A_{n - 2}^{k - 2}}}+ \\& {\rm{6}}C_n^{\rm{1}}C_{n{\rm{ - 1}}}^{\rm{1}}C_{n - 2}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - {\rm{5}}A_{n - 2}^{k - 2} + {\rm{2}}A_{n - {\rm{3}}}^{k - {\rm{3}}}}}+\\& C_n^{\rm{1}}C_{n{\rm{ - 1}}}^{\rm{1}}C_{n - {\rm{2}}}^{\rm{1}}C_{n - {\rm{3}}}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - {\rm{6}}A_{n - 2}^{k - 2} + {\rm{4}}A_{n - {\rm{3}}}^{k - {\rm{3}}} - A_{n - {\rm{4}}}^{k - {\rm{4}}}}}) \end{aligned}$ 
表 1
$\displaystyle\sum\limits_{i < j < l < q} {{r_{\left( {i,j,l,q} \right)}}\left( p \right)} $ 的计算Table 1. the reliability of four subgraphs
通过表1，我们得到
对于k=2，取
k=3，取
对于
$R_{5,4}^{4,3}$ ，由(1)、(4)得：
对于
$\tilde R_{5,4}^{4,3}(p)$ ，取p=e‒at[1]，得到图3。
图 3 排列图A5,4子图可靠性的近似计算
Figure 3. Approximate calculations of subgraph reliability of A5,4
由图3知，如果用界的平均值去估算可靠性时，会出现
$\tilde R_{5,4}^{4,3}(p) < 0$ ，我们称这种情况为鲁棒性，即在某些时刻，近似值没有意义。利用二分法找到了$\tilde R_{5,4}^{4,3}(p) = 0$ 的近似时间节点，当84.6019<t，$\tilde R_{5,4}^{4,3}(p) < 0$ ，即当84.6019<t，$\tilde R_{5,4}^{4,3}(p)$ 没有意义。针对鲁棒性的情况，本文提出了基于排列图的子图可靠性的蒙特卡罗算法近似计算排列图的子图可靠性。
-
蒙特卡罗方法是以概率统计理论为指导的一种非常重要的数值方法，使用随机数解决许多计算问题：
（1）输入最小值，最大值和最可能的估算数据，并为其选择合适的先验分布模型;
（2）根据以上输入，采用一定的规则，快速实施大量的随机抽样;
（3）对随机抽样的数据进行数学计算并处理结果;
（4）基于累积概率的分析，对结果进行概率分析，得出结论。
-
对于排列图An,k，排列图子图的可靠性定义为：当系统发生故障时，仍然存在一个正常运行子图的概率。
利用蒙特卡罗方法对排列图子图的可靠性进行计算的一般过程如下：
算法二：
（1）已知排列图An,k，输入循环次数N，节点正常运行概率p，计数器s=0；
（2）对于第i次循环，生成(0, 1)之间的n!/(n‒k)!个随机数，构成一个n!/(n‒k)!维的向量γi；
（3）每个节点正常运行的概率为p，则失败的概率为q=1‒p；若2)中向量γi的第j个随机数大于q，记对应的节点j正常运行，状态变量记为1，否则记为0，得到状态向量λi；
（4）根据3)中λi状态，判断剩下正常运行的节点，是否构成一个排列图子图，如果构成一个排列图子图，则s+=1，否则s=s；
（5）如果i≤N，i+=1，返步骤(2)；否则，返步骤(6)；
（6）reliability=s/N。
例2：以A3,2(图4)为例，对蒙特卡罗方法进行说明：
图 4 排列图A3,2
Figure 4. arrangement graph A3,2
利用容斥原理，得到
（1）输入循环次数N=100，计数s=0，p=0.8，q=0.2；
（2）随机生成一个6维的向量(0.282 07, 0.136 92, 0.438 19, 0.526 09, 0.065 82, 0.207 75)；
（3）生成状态向量(1,0,1,1,0,1)；
（4）存在正常运行的子图X2(12, 32)和2X(23, 21)，则s+=1；
通过仿真计算，得到表2：
Cycles N Monte Carlo error/% 100 0.218 500 0.185 1 000 0.084 表 2 A3,2的子图可靠性蒙特卡罗近似计算
Table 2. The approximate calculation of the Monte Carlo Method for A3,2
通过表2，发现蒙特卡罗得到的误差不足1%，而且随着循环次数的增多，其误差越小。
-
取p=0.85，N=1 000，得到An, k子图可靠性的界以及近似计算的结果见表3。
An,k Lower bound Algorithm1 Ref[1] Monte Carlo algorithm Upper bound A3,2 −4.048 0.144 0.999 5 0.988 4.335 A4,2 −6.446 −0.766 0.999 5 0.994 4.913 A5,4 0.281 0.297 0.336 0.301 0.313 A6,3 0.344 0.425 0.509 0.434 0.506 A7,3 0.139 0.140 0.149 0.141 0.142 表 3 排列图An,k子图可靠性的界以及近似计算（n=3,4,5,6,7，k=2,3,4）
Table 3. the bounds and the approximate calculation of subgraph reliability for An,k（n=3,4,5,6,7, k=2,3,4）
通过表3发现，A3,2、A4,2的上、下界出现了异常，这就是鲁棒性问题。对于A5,4、A6,3、A7,3，文献[1]中的近似值都大于上界值，而蒙特卡罗模拟的可靠性都在上、下界之间，可见蒙特卡罗模拟的可靠性结果要优于已知算法。
对于图4，取p=0.5, 0.6, 0.7, 0.8, 0.9得到排列图A3,2子图可靠性的近似解。
p Real value Ref [1] Monte Carlo 0.5 0.718 8 0.822 0.718 0.6 0.848 4 0.931 3 0.842 0.7 0.934 8 0.982 4 0.933 0.8 0.981 0.997 8 0.986 0.9 0.997 8 0.999 95 0.997 表 4 排列图A3,2子图可靠性的近似计算
Table 4. The approximate calculation of subgraph reliability for A3,2
图 5 排列图A3,2子图可靠性的近似计算
Figure 5. The approximate calculation of subgraph reliability for A3,2
通过图5，发现算法一的近似计算会出现鲁棒性问题，已有近似计算的结果要大于真实值，利用蒙特卡罗得到近似结果和真实值基本重合。
-
本文主要研究了排列图子图的可靠性问题，提出了排列图子图的下界，在此基础上提出了算法一：将上、下界的平均值作为排列图子图可靠性的近似值。在算法一的计算过程中会有鲁棒性问题，针对这一问题，本文提出了基于排列图的蒙特卡罗模拟算法，对于A3,2的排列图子图的可靠性，利用蒙特卡罗去计算，其误差不足1%。对于其他排列图的可靠性，蒙特卡罗算法也优于已知的近似算法。
并行系统中排列图的可靠性近似算法
Approximation Algorithm of Arrangement Graph Reliability in Parallel System
-
摘要: 讨论了排列图子图可靠性界的鲁棒性问题和可靠性的近似算法,并构造了排列图的蒙特卡罗算法。仿真结果说明所构造的蒙特卡罗算法远优于已知的近似算法，A3,2子图可靠性的蒙特卡罗近似计算误差小于1%。Abstract: In parallel system, the arrangement graphs An,k has good properties such as symmetry, small diameter, and high fault tolerance. Subsystem reliability is defined as the probability that there is still a normal operating subsystem when the system has faults. It is usually used to measure the system health status, and the calculation of subsystem reliability is an NP-hard problem. This paper discusses the robustness of the reliability of the subgraphs and the approximate algorithm of reliability. Further, the Monte Carlo algorithm for arrangement graphs is constructed. The simulation results show that the constructed Monte Carlo algorithm is much better than the known approximation algorithm. In particular, the error of Monte Carlo approximation of A3,2 subgraph reliability is less than 1%.
-
Key words:
- reliability /
- arrangement graph /
- parallel system /
- approximate algorithm /
- Monte Carlo
-
图 3 排列图A5,4子图可靠性的近似计算
Figure 3. Approximate calculations of subgraph reliability of A5,4
图 5 排列图A3,2子图可靠性的近似计算
Figure 5. The approximate calculation of subgraph reliability for A3,2
表 1
$\displaystyle\sum\limits_{i < j < l < q} {{r_{\left( {i,j,l,q} \right)}}\left( p \right)} $ 的计算Table 1. the reliability of four subgraphs
Reliability One position Two positions Three positions Four positions ${R_1} = C_k^{\rm{1}}C_n^{\rm{4}}{p^{4A_{n - 1}^{k - 1}}}$ $\begin{aligned} {R_2} =& C_k^{\rm{2}}(2C_n^{\rm{1}}C_{n - 1}^{\rm{2}}{p^{4A_{n - 1}^{k - 1} - 2A_{n - 2}^{k - 2}}} + \\& 2C_n^{\rm{1}}C_{n - 1}^{\rm{3}}{p^{4A_{n - 1}^{k - 1} - 3A_{n - 2}^{k - 2}}} + 2C_n^{\rm{2}}C_{n - 2}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - 3A_{n - 2}^{k - 2}}}+\\ & C_n^{\rm{2}}{p^{4A_{n - 1}^{k - 1} - {\rm{2}}A_{n - 2}^{k - 2}}} + \\& C_n^{\rm{2}}C_{n - 2}^{\rm{2}}{p^{4A_{n - 1}^{k - 1} - {\rm{4}}A_{n - 2}^{k - 2}}} \end{aligned}$ $\begin{aligned} {R_{\rm{3}}} =& C_k^{\rm{3}}({\rm{3}}C_n^{\rm{1}}C_{n - 1}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - 2A_{n - 2}^{k - 2}}} + \\& {\rm{3}}C_n^{\rm{1}}C_{n - 1}^{\rm{2}}{p^{4A_{n - 1}^{k - 1} - {\rm{4}}A_{n - 2}^{k - 2}}} +\\& {\rm{6}}C_n^{\rm{1}}C_{n{\rm{ - 1}}}^{\rm{1}}C_{n - 2}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - {\rm{4}}A_{n - 2}^{k - 2} + A_{n - {\rm{3}}}^{k - {\rm{3}}}}}+\\& {\rm{3}}C_n^{\rm{1}}C_{n{\rm{ - 1}}}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - {\rm{3}}A_{n - 2}^{k - 2}}}+\\ & {\rm{3}}C_n^{\rm{1}}C_{n{\rm{ - 1}}}^{\rm{1}}C_{n - 2}^{\rm{2}}{p^{4A_{n - 1}^{k - 1} - {\rm{5}}A_{n - 2}^{k - 2} + {\rm{2}}A_{n - {\rm{3}}}^{k - {\rm{3}}}}} \end{aligned}$ $\begin{aligned} {R_{\rm{4}}} = & C_k^{\rm{4}}(C_n^{\rm{1}}{p^{4A_{n - 1}^{k - 1}}} + \\& {\rm{4}}C_n^{\rm{1}}C_{n - 1}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - {\rm{3}}A_{n - 2}^{k - 2}}}+ \\& {\rm{3}}C_n^{\rm{1}}C_{n - 1}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - {\rm{4}}A_{n - 2}^{k - 2}}}+ \\& {\rm{6}}C_n^{\rm{1}}C_{n{\rm{ - 1}}}^{\rm{1}}C_{n - 2}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - {\rm{5}}A_{n - 2}^{k - 2} + {\rm{2}}A_{n - {\rm{3}}}^{k - {\rm{3}}}}}+\\& C_n^{\rm{1}}C_{n{\rm{ - 1}}}^{\rm{1}}C_{n - {\rm{2}}}^{\rm{1}}C_{n - {\rm{3}}}^{\rm{1}}{p^{4A_{n - 1}^{k - 1} - {\rm{6}}A_{n - 2}^{k - 2} + {\rm{4}}A_{n - {\rm{3}}}^{k - {\rm{3}}} - A_{n - {\rm{4}}}^{k - {\rm{4}}}}}) \end{aligned}$ 
下载: 导出CSV
表 2 A3,2的子图可靠性蒙特卡罗近似计算
Table 2. The approximate calculation of the Monte Carlo Method for A3,2
Cycles N Monte Carlo error/% 100 0.218 500 0.185 1 000 0.084
下载: 导出CSV
表 3 排列图An,k子图可靠性的界以及近似计算（n=3,4,5,6,7，k=2,3,4）
Table 3. the bounds and the approximate calculation of subgraph reliability for An,k（n=3,4,5,6,7, k=2,3,4）
An,k Lower bound Algorithm1 Ref[1] Monte Carlo algorithm Upper bound A3,2 −4.048 0.144 0.999 5 0.988 4.335 A4,2 −6.446 −0.766 0.999 5 0.994 4.913 A5,4 0.281 0.297 0.336 0.301 0.313 A6,3 0.344 0.425 0.509 0.434 0.506 A7,3 0.139 0.140 0.149 0.141 0.142
下载: 导出CSV
-
[1] LIN L, XU L, ZHOU S, et al. The Reliability of Subgraphs in the Arrangement Graph[J]. IEEE Transactions on Reliability, 2015, 64(2): 807-818. doi: 10.1109/TR.2015.2413372 [2] CHIANG W K, CHEN R J. On the arrangement graph[J]. Information Processing Letters, 1998, 66(4): 215-219. doi: 10.1016/S0020-0190(98)00052-0 [3] CHENG E, GROSSMAN J W, QIU K, et al. The number of shortest paths in the arrangement graph[J]. Information Sciences, 2013, 240(11): 191-204. [4] FENG K, WANG S Y, ZHANG G Z. Link Failure Tolerance in the Arrangement Graphs[J]. International Journal of Foundations of Computer Science, 2015, 26(02): 241-254. doi: 10.1142/s0129054115500148 [5] YANG W, LI H, GUO X. A kind of conditional fault tolerance of (n,k)-star graphs[J]. Information Processing Letters, 2010, 110(22): 1007-1011. doi: 10.1016/j.ipl.2010.08.015 [6] CANCELA H, KHADIRI M E, PETINGI L A. Polynomial-Time Topological Reductions That Preserve the Diameter Constrained Reliability of a Communication Network[J]. IEEE Transactions on Reliability, 2011, 60(4): 845-851. doi: 10.1109/TR.2011.2170250 [7] ZHANG Z, AN W, SHAO F. Cascading Failures on Reliability in Cyber-Physical System[J]. IEEE Transactions on Reliability, 2016, 65(4): 1745-1754. doi: 10.1109/TR.2016.2606125 -
点击查看大图
图(5)表(4)
计量
- 文章访问数: 5520
- HTML全文浏览量: 784
- PDF下载量: 7
- 被引次数: 0