基于比较模型的扩展立方体网络的（t，k）-诊断度研究

doi:10.11959/j.issn.1000-436x.2017159

通信学报 ›› 2017, Vol. 38 ›› Issue (8): 9-18.doi: 10.11959/j.issn.1000-436x.2017159

基于比较模型的扩展立方体网络的（t，k）-诊断度研究

梁家荣(),陈秒江

广西大学计算机与电子信息学院，广西南宁 530004

修回日期:2017-06-06 出版日期:2017-08-01 发布日期:2017-09-07
作者简介:梁家荣（1966-），男，广西玉林人，博士，广西大学教授，主要研究方向为网络的故障诊断、并行与网络计算。|陈秒江（1992-），男，广西北流人，广西大学硕士生，主要研究方向为网络的故障诊断、并行与网络计算。
基金资助:
国家自然科学基金资助项目(61363002);广西自然科学基金资助项目(2016GXNSFAA380134)

Research on（t，k）-diagnosability for augmented cube network under the comparison model

Jia-rong LIANG(),Miao-jiang CHEN

School of Computer and Electronic Information，Guangxi University，Nanning 530004，China

Revised:2017-06-06 Online:2017-08-01 Published:2017-09-07
Supported by:
The Nationa1 Natura1 Science Foundation of China(61363002);The Natura1 Science Foundation of Guangxi Zhuang Autonomous Region of China(2016GXNSFAA380134)

摘要/Abstract

摘要：

针对扩展立方体网络故障诊断问题，提出一种基于比较模型的（t，k）-故障诊断方法。首先，通过图论的方法研究n维扩展立方体网络（AQ_n）的重要性质，根据这些性质设计了一个基于比较模型的算法来寻找该扩展立方体网络的最大非故障组件。然后，利用所得的最大非故障组件来确定该网络系统的（t，k）-故障诊断度。最后，提出并证明了n维扩展立方体网络是（t，2n-1）-可诊断的。结果表明，n维扩展立方体网络的（t，2n-1）-诊断度 $\frac{2^{n - 1} (2 n - 2) lb(2 n - 3)}{{(2 n - 3)}^{2}}$ 远大于其条件诊断度（6n-17）及传统故障诊断度（2n-1）。

关键词: 扩展立方体网络, （t，k）-诊断度, 比较模型, PMC模型, 故障组件

Abstract:

Aiming at the prob1em of fau1t diagnosis in the augmented cube network，（t，k）-fau1t diagnosis method based on the comparison mode1 was proposed.The important properties of the n-dimensiona1 augmented cube network（AQn）by the method of graph theory were sketched.Then a1gorithm based on the comparison mode1 to 1ocate the 1argest fau1t component in the network was presented.Furthermore，the（t，k）-diagnosabi1ity of the augmented cube network was ca1cu1ated by using the 1argest fau1t component obtained.Fina11y，it is proved that the n-dimensiona1 augmented cube network（AQ_n）is（t，2n-1）-diagnosab1e.The resu1t shows that the（t，2n-1）-diagnosabi1ity of AQ _nis $\frac{2^{n - 1} (2 n - 2) lb(2 n - 3)}{{(2 n - 3)}^{2}}$ ，which is much 1arger than 6n-17，the conditiona1 diagnosabi1ity of AQ_n.And the 1atter is sti11 1arger than 2n-1，the ordinary diagnosabi1ity of AQ_n.

Key words: augmented cube network, comparison mode1, PMC mode1, fau1t component

中图分类号:

TP393

梁家荣,陈秒江. 基于比较模型的扩展立方体网络的（t，k）-诊断度研究[J]. 通信学报, 2017, 38(8): 9-18.

Jia-rong LIANG,Miao-jiang CHEN. Research on（t，k）-diagnosability for augmented cube network under the comparison model[J]. Journal on Communications, 2017, 38(8): 9-18.

图/表 8

表1

图1

图2

图3

图4

图5

表2

表3

各种网络的（t，k）诊断度"

多处理器系统	$(t, k) - 诊断度$
超立方网络，n≥3
交叉超立方，n≥3
扭立方体，n≥3	$t = \frac{2^{n - 1} (n - 2) lb n}{n^{2}}$
局部扭立方体，n≥3
多重扭立方体，n≥3	$k = n$
广义扭立方体，n≥3
星图，n≥4	$t = \frac{2^{n - 2} (n - 3)}{n - 1}$
Bubble-sort图n≥4
Pancake图，n≥4	$k = n - 1$
扩展立方体，n≥3	$t = \frac{2^{n - 1} (2 n - 2) lb (2 n - 3)}{{(2 n - 3)}^{2}} k = 2 n - 1$

表3

参考文献 25

[1]	FRIEDMAN A D , SIMONCINI L . System-level fault diagnosis[J]. Computer, 1980,13(3): 47-53.
[2]	PREPARATA F P , METZE G , CHIEN R T . On the connection assignment problem of diagnosable system[J]. IEEE Transaction on Computers, 1967,16(12): 848-854.
[3]	YE L C , LIANG J R . Five-round adaptive diagnosis in Hamiltonian networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2015,26(9): 2459-2464.
[4]	YANG X , TANG Y . A（4n-9）/3 diagnosis algorithm for hypercube networks[J]. Information Sciences, 2007,177(8): 1771-1781.
[5]	CHANG G Y , CHANG G J , CHEN G H . Diagnosabilities of regular networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2005,16(4): 314-323.
[6]	FAN J . Diagnosability of the M?bius cubes[J]. IEEE Transactions on Parallel and Distributed Systems, 1998,9(9): 923-928.
[7]	HSIEH S Y , CHUANG T Y . The strong diagnosability of regular networks and product networks under the PMC model[J]. IEEE Transactions on Parallel and Distributed Systems, 2009,20(3): 367-378.
[8]	KAVIANPOUR A , KIM K H . Diagnosability of hypercubes under the pessimistic one step diagnosis strategy[J]. IEEE Transactions on Computers, 1991,40(2): 232-237.
[9]	BARSI F , GRANDONI F , MAESTRINI P . A theory of diagnosability of digital systems[J]. IEEE Transactions on Computers, 1976,25(6): 585-593.
[10]	SENGUPTA A , DAHBURA A T . On self-diagnosable multiprocessor systems:diagnosis by the comparison approach[J]. IEEE Transactions on Computers, 1992,41(11): 1386-1396.
[11]	LEE C W , HSIEH S Y . Diagnosability of two-matching composition networks under the model[J]. IEEE Transactions on Dependable and Secure Computing, 2011,8(2): 246-255.
[12]	SENGUPTA A , DAHBURA A . On self-diagnosable multiprocessor systems:diagnosis by the comparison approach[J]. IEEE Transactions on Computers, 1992,41(11): 1386-1396.
[13]	CHANG G Y , CHANG G J , CHEN G H . Diagnosability of regular networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2005,16(4): 314-323.
[14]	HSIEH S Y , CHEN Y S . Strongly diagnosable systems under the comparison diagnosis model[J]. IEEE Transactions on Computers, 2008,57(12): 1720-1725.
[15]	HSIEH S Y , CHEN Y S . Strongly diagnosable product networks under the comparison diagnosis model[J]. IEEE Transactions on Computers, 2008,57(6): 721-732.
[16]	YE L C , LIANG J R , LIN H X . A fast pessimistic diagnosis algorithm for hypercube-like networks under the comparison model[J]. IEEE Transactions on Computers, 2016,65(9): 2884-2888.
[17]	SAAD Y , SCHULTZ M H . Topological properties of hypercube[J]. IEEE Transactions on Computers, 1988,37(7): 867-872.
[18]	LEE S C , HOOK L R . Logic and computer design in nanospace[J]. IEEE Transactions on Computers, 2008,57(7): 965-977.
[19]	CHOUNDUM S A , SUNITHA V . Augmented cubes[J]. Networks, 2002,40(2): 71-84.
[20]	CHANG N W , HSIEH S Y . Conditional diagnosability of augmented cubes under the PMC model[J]. IEEE Transactions on Dependable and Secure Computing, 2012,9(1): 46-60.
[21]	HONG W S , HSIEH S Y . Strong diagnosability and conditional diagnosability of augmented cubes under the comparison diagnosis model[J]. IEEE Transactions on Reliability, 2012,61(1): 140-148.
[22]	ARAKI T , SHIBATA Y . （t,k）-diagnosable system:a generalization of the PMC models[J]. IEEE Transactions on Computers, 2003,52(7): 971-975.
[23]	CHEN C A , HSIEH S Y . （t,k）-diagnosis for component-composition graphs under the MM* model[J]. IEEE Transactions on Computers, 2011,60(12): 1704-1717.
[24]	熊茜, 梁家荣, 马强 . 交换超立方网络的（t,k）故障诊断度研究[J]. 通信学报, 2016,37(3): 190-198.
	XIONG X , LIANG J R , MA Q . Research on（t,k）-diagnosability for exchanged hypercube network[J]. Journal on Communications, 2016,37(3): 190-198.
[25]	HSIEH S Y , CHEN C A . Computing the(t,k)-diagnosability of component-composition graphs and its application[C]// The Series on Lecture Notes in Computer Science,2010, 6507: 363-374.

基于比较模型的扩展立方体网络的（t，k）-诊断度研究

Research on（t，k）-diagnosability for augmented cube network under the comparison model

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 25

相关文章 2

Metrics

推荐阅读 0

比较器节点w	被测节点u	被测节点v	症状σ（w：u，v）
非故障	非故障	非故障	0
非故障	非故障	故障	1
非故障	故障	非故障	1
非故障	故障	故障	1
故障	非故障	非故障	0或1
故障	非故障	故障	0或1
故障	故障	非故障	0或1
故障	故障	故障	0或1

[1]	郭晨,肖志芳,冷明,彭硕,王博. 交换交叉立方网络在PMC模型下的(t,k)-诊断度研究[J]. 通信学报, 2019, 40(6): 190-202.
[2]	熊茜,梁家荣,马强. 交换超立方网络的(t,k)故障诊断度研究[J]. 通信学报, 2016, 37(3): 190-198.

维度n	AQ_n	Q_n
5	5	4
6	13	9
7	23	18
8	44	36
9	77	70
10	145	136