交换超立方网络的(t,k)故障诊断度研究

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

摘要/Abstract

摘要：

故障诊断是网络系统修复的一个重要环节，PMC诊断模型是一种简单、易于理解的故障诊断模型。通过对以交换超立方网EH(s,p)(1≤s≤p)为拓扑模型的多处理器系统进行结构分析，给出了该网络系统的一般化的故障诊断方法——(t,k)诊断方法，证明了在PMC模型下交换超立方网络EH(s,p)(1≤s≤p)是 $(2^{\frac{s + p - 1}{2}}, s + 1)$ 可诊断的，且是条件? $(\frac{2^{s + p + 1} - 2 s}{p + 1}, 2 s)$ $2^{\frac{s + p - 1}{2}}$ 可诊断的。结果表明，交换超立方网的(t,k)诊断度大于其传统诊断度s+1，条件(t,k)诊断度 $\frac{2^{s + p + 1} - 2 s}{p + 1}$ 大于其传统条件诊断度4s-3。这些结果为交换超立方网络的故障诊断提供了重要的理论依据。

关键词: 交换超立方网, (t,k)诊断度, 条件(t,k)诊断度, PMC模型

Abstract:

Fault diagnosis was an important part in the processing of network system repair.PMC was a diagnosis model which was simple and easy to be understood.Through analysis of the structure of exchanged hypercube,a generalization measure of fault diagnosis for the network system was provided,called (t,k)-fault diagnosis method.By computing,it is shown that EH(s,p) is $(2^{\frac{s + p - 1}{2}}, s + 1)$ -diagnosable and conditional $(\frac{2^{s + p + 1} - 2 s}{p + 1}, 2 s)$ -diagnosable,where 1≤s≤p.The result shows that the(t,k)-diagnosability of EH(s,p) is $2^{\frac{s + p - 1}{2}}$ ,which is bigger than its ordinary diagnosability s+1,and the conditional (t,k)-diagnosability is $\frac{2^{s + p + 1} - 2 s}{p + 1}$ ,which is bigger than its ordinary conditional diagnosability 4s-3.Above results present the important theory basis for fault diagnosis of exchanged hypercube network.

Key words: exchanged hypercube network, (t,k)-diagnosability, conditional(t,k)-diagnosability, PMC model

熊茜,梁家荣,马强. 交换超立方网络的(t,k)故障诊断度研究[J]. 通信学报, 2016, 37(3): 190-198.

Xi XIONG,Jia-rong LIANG,Qiang MA. Research on(t,k)-diagnosability for exchanged hypercube network[J]. Journal on Communications, 2016, 37(3): 190-198.

图/表 2

参考文献 25

[1]	MALEK M . A comparison connection assignment for diagnosable of multiprocessor systems[C]// The 7th Annual Symposium on Computer Architecture. New York,United States, c1980:31-36.
[2]	MAENG J , MALEKM . A comparison connection assignmentfor self-diagnosis of multiprocessor systems[C]// The 11th International Symposium on Fault Tolerant Computing. Edinburgh,Scotland, c1981:173-175.
[3]	SENGUPTA A , DANBURA A T . On self-diagnosable multiprocessor-systems:diagnosis by the comparison approach[J]. IEEE Transactions on Computers. 1992,41(11): 1386-1396.
[4]	HONG W S , HSIEH S Y . Strong diagnosability and conditional diag-nosability of augmented cubes under the comparison diagnosis model[J]. IEEE Transactions on Reliability, 2012,61(1): 140-148.
[5]	KHANNNA S , PUCHS W K . A Graph partitioning approach to sequential diagnosis[J]. IEEE Transactions on Computer 1997,46(1): 39-47.
[6]	LEE C W , HSIEH S Y . Diagnosability of two-matching composition network under the MM* model[J]. IEEE Transactions on Dependable and Secure Computing. 2011,8(2): 246-255.
[7]	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.
[8]	PREPARATA F P , METZE G , CHIEN R T . On the connectionassign-ment problem of diagnosable systems[J]. IEEE Transactions on Elec-tronic Computers, 1967,16(6): 848-854.
[9]	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.
[10]	ZHU Q . The conditional diagnosability of crossed cubes under the comparison model[J]. International Journal of Computer Mathematics, 2010,87(15): 3387-3396.
[11]	LIN C K , KUNG T L , TAN J J M . An algorithmic approach to condi-tional-fault local diagnosis of regular multiprocessor interconnected systems under the PMC model[J]. IEEE Transactions on uters, 2013,62(3): 439-451.
[12]	LIN C K , PENG S L , TAN J J M , et al. The diagnosability of g-good-neighbor conditional- fault hypercube under PMC model[C]// 2010 International Conference on Parallel and Distributed Processing Tech-niques and Applications(PDPTA'10). Las Vegas,USA, c2010:494-499.
[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]	XU M , THULASIRAMAN K , XU X D . Conditional diagnosability of matching composition networks under the PMC model[J]. IEEE Transactions on Circuits and Systems-II:Express Briefs, 2009,56(11): 875-879.
[15]	LIN C K , KUNG T L , TAN J J M . Conditional-fault diagnosability of multiprocessor systems with an efficient local diagnos algorithm un-der the PMC model[J]. IEEE Transactions on Computers, 2011,22(10): 1669-1680.
[16]	ARAKI T , SHIBATA Y . (t,k)-Diagnosable system:a generalization of the PMC models[J]. IEEE Transactions on Computers, 2003,52(7): 971-975.
[17]	CHEN C , HESIH S Y . (t,k)-diagnosis for component-composition graphs under the MM ?model[J]. IEEE Transactions on Computers, 2011,60(12): 1704-1717.
[18]	CHANG G Y . (t,k)-diagnosability for regular networks[J]. IEEE Transactions on Computers, 2010,59(9): 1153-1157.
[19]	CHANG G Y , CHEN G H . (t,k)-Diagnosability of multiprocessorsys-tems with applications to grids and toris[J]. Siam Journal on Compu-ting, 2007,37(4): 1280-1298.
[20]	LAI P L , TAN J J M , CHANG C P , et al. Conditional diagnosability measures for large multiprocessor systems[J]. IEEE Transactions on Computers, 2005,54(2): 165-175.
[21]	郭晨，梁家荣，葛志辉，等. 基于互测PMC模型的条件诊断算法[J]. 电子学报 2015,43(2): 255-261. GUO C , LIANG J R , GE Z H , et al. A conditional diagnosis algorithm based on ex-test PMC model[J]. Chinese Journal of Electronics, 2015,43(2): 255-261.
[22]	LOH P K K , HSU W J , PAN Y . The exchange hypercube[J]. IEEE Transactions on Parallel and Distributed Systems, 2005,16(9): 866-874.
[23]	LIANG J R , HUANG Y , YE L C . Diagnosabilities of exchanged hypercube networks under pessimistic one-step diagnosis strategy[J]. Journal of System Engineering and Electronics, 2015,26(2): 415-420.
[24]	MA M J , ZHU L Y . The super connectivity of exchanged hyper-cubes[J]. Information Processing Letters, 2011,111(8): 360-364.
[25]	LI X J , XU J M . Generalized measures of fault tolerance in exchanged hypercubes[J]. Information Processing Letters, 2013,113(14): 533-537.