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

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

Abstract

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

CLC Number:

TP393

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.

Figures/Tables 8

多处理器系统	$(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$

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

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

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 25

Related Articles 15

Metrics

Recommended 0

[1]	Jingbo LI, Li MA, Yang LI, Yingxun FU, Dongchao MA. Optimized design of sensing transmission and computing collaborative industrial Internet [J]. Journal on Communications, 2023, 44(6): 12-22.
[2]	Shiqi ZHAO, Xiaohong HUANG, Zhigang ZHONG. Research and implementation of reputation-based inter-domain routing selection mechanism [J]. Journal on Communications, 2023, 44(6): 47-56.
[3]	Zhen CHEN, Wenhui CHEN, Xiaowei LIU, Dianlong YOU, Linlin LIU, Limin SHEN. Functional complementarity relationship enhanced cloud API recommendation method [J]. Journal on Communications, 2023, 44(6): 125-137.
[4]	Debin WEI, Chengsheng PAN, Li YANG, Zuoren YAN. Adaptive random early detection algorithm based on network traffic level grade prediction [J]. Journal on Communications, 2023, 44(6): 154-166.
[5]	Yuancheng LI, Yongtai QIN. Deep reinforcement learning based algorithm for real-time QoS optimization of software-defined security middle platform [J]. Journal on Communications, 2023, 44(5): 181-192.
[6]	Yingjie XIA, Siyu ZHU, Xuejiao LIU. Research on efficient cross trust-domain group authentication with conditional privacy of vehicle platoon under blockchian architecture [J]. Journal on Communications, 2023, 44(4): 111-123.
[7]	Renchao XIE, Wen WEN, Qinqin TANG, Yunlong LIU, Gaochang XIE, Tao HUANG. Survey on rail transit mobile edge computing network security [J]. Journal on Communications, 2023, 44(4): 201-215.
[8]	Zhiyong LUO, Yu ZHANG, Qing WANG, Weiwei SONG. Study of SDN intrusion intent identification algorithm based on Bayesian attack graph [J]. Journal on Communications, 2023, 44(4): 216-225.
[9]	Yifeng WANG, Yuanbo GUO, Qingli CHEN, Chen FANG, Renhao LIN, Yongliang ZHOU, Jiali MA. Method based on contrastive incremental learning for fine-grained malicious traffic classification [J]. Journal on Communications, 2023, 44(3): 1-11.
[10]	Jin ZHANG, Qiang GE, Weihai XU, Yiming JIANG, Hailong MA, Hongtao YU. Design, implementation and formal verification of BGP proxy for mimic router [J]. Journal on Communications, 2023, 44(3): 33-44.
[11]	Pujie JING, Liangmin WANG, Xuewen DONG, Yushu ZHANG, Qian WANG, Sohail Muhammad. CHA: cross-chain based hierarchical architecture for practicable blockchain regulatory [J]. Journal on Communications, 2023, 44(3): 93-104.
[12]	Jian SHU, Jiawei SHI, Linlan LIU, Al-Kali Manar. Topology prediction for opportunistic network based on spatiotemporal convolution [J]. Journal on Communications, 2023, 44(3): 145-156.
[13]	Dongbin WANG, Dongzhe WU, Hui ZHI, Kun GUO, Xu ZHANG, Jinqiao SHI, Yu ZHANG, Yueming LU. Preventing flow table overflow against denial of service attack in software defined network [J]. Journal on Communications, 2023, 44(2): 1-11.
[14]	Haiyan KANG, Molan LONG. Research on network attack analysis method based on attack graph of absorbing Markov chain [J]. Journal on Communications, 2023, 44(2): 122-135.
[15]	Yuntao ZHANG, Binxing FANG, Chunlai DU, Zhongru WANG, Zhijian CUI, Shouyou SONG. Container escape detection method based on heterogeneous observation chain [J]. Journal on Communications, 2023, 44(1): 49-63.

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