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

熊茜; 梁家荣; 马强

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

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2024-06-05

- 交换超立方网络的(t,k)故障诊断度研究
- Research on(t,k)-diagnosability for exchanged hypercube network
- 通信学报 2016年37卷第3期页码：190-198
- 作者机构：
  
  广西大学计算机与电子信息学院，广西南宁530004
- 作者简介：
  
  [ "熊茜（1990-），男，江西丰城人，广西大学硕士生，主要研究方向为互联网络的故障诊断、并行与网络计算。" ]
  [ "梁家荣（1966-），男，广西玉林人，博士，广西大学教授，主要研究方向为互联网络的故障诊断、并行与网络计算、算法设计与分析。" ]
  [ "马强（1990-），男，甘肃陇南人，广西大学硕士生，主要研究方向为图论、互联网络的故障诊断。" ]
- 基金信息：
  
  国家自然科学基金资助项目(61363002)
- DOI：10.11959/j.issn.1000-436x.2016067
  中图分类号： TP393
- 网络出版日期：2016-03，
  
  纸质出版日期：2016-03-25
- 稿件说明：
移动端阅览
熊茜, 梁家荣, 马强. 交换超立方网络的(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.
熊茜, 梁家荣, 马强. 交换超立方网络的(t,k)故障诊断度研究[J]. 通信学报, 2016,37(3):190-198. DOI： 10.11959/j.issn.1000-436x.2016067.

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. DOI： 10.11959/j.issn.1000-436x.2016067.

摘要

故障诊断是网络系统修复的一个重要环节，PMC诊断模型是一种简单、易于理解的故障诊断模型。通过对以交换超立方网EH(s

p)(1≤s≤p)为拓扑模型的多处理器系统进行结构分析，给出了该网络系统的一般化的故障诊断方法——(t

k)诊断方法，证明了在PMC模型下交换超立方网络EH(s

p)(1≤s≤p)是

</mo><mi>s</mi><mo>+</mo><mn>1</mn></mrow> <mo>)</mo></mrow></mrow></math>

可诊断的，且是条件

</mo><mn>2</mn><mi>s</mi></mrow> <mo>)</mo></mrow></math>

可诊断的。结果表明，交换超立方网的(t

k)诊断度大于其传统诊断度s+1，条件(t

k)诊断度

大于其传统条件诊断度4s-3。这些结果为交换超立方网络的故障诊断提供了重要的理论依据。

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

</mo> <mi>s </mi> <mo>+ </mo> <mn>1 </mn> </mrow> <mo>) </mo> </mrow> </math>

-diagnosable and conditional

</mo> <mn>2 </mn> <mi>s </mi> </mrow> <mo>) </mo> </mrow> </math>

-diagnosable

where 1≤s≤p.The result shows that the(t

k)-diagnosability of EH(s

p) is

which is bigger than its ordinary diagnosability s+1

and the conditional (t

k)-diagnosability is

which is bigger than its ordinary conditional diagnosability 4s-3.Above results present the important theory basis for fault diagnosis of exchanged hypercube network.

关键词

Keywords

references

MALEK M . A comparison connection assignment for diagnosable of multiprocessor systems [C ] // The 7th Annual Symposium on Computer Architecture . New York,United States , c 1980 : 31 - 36 .

MAENG J , MALEKM . A comparison connection assignmentfor self-diagnosis of multiprocessor systems [C ] // The 11th International Symposium on Fault Tolerant Computing . Edinburgh,Scotland , c 1981 : 173 - 175 .

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 .

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 .

KHANNNA S , PUCHS W K . A Graph partitioning approach to sequential diagnosis [J ] . IEEE Transactions on Computer 1997 , 46 ( 1 ): 39 - 47 .

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 .

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 .

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 .

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 .

ZHU Q . The conditional diagnosability of crossed cubes under the comparison model [J ] . International Journal of Computer Mathematics , 2010 , 87 ( 15 ): 3387 - 3396 .

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 .

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 , c 2010 : 494 - 499 .

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 .

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 .

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 .

ARAKI T , SHIBATA Y . (t,k)-Diagnosable system:a generalization of the PMC models [J ] . IEEE Transactions on Computers , 2003 , 52 ( 7 ): 971 - 975 .

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 .

CHANG G Y . (t,k)-diagnosability for regular networks [J ] . IEEE Transactions on Computers , 2010 , 59 ( 9 ): 1153 - 1157 .

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 .

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 .

郭晨，梁家荣，葛志辉，等 . 基于互测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 .

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 .

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 .

MA M J , ZHU L Y . The super connectivity of exchanged hyper-cubes [J ] . Information Processing Letters , 2011 , 111 ( 8 ): 360 - 364 .

LI X J , XU J M . Generalized measures of fault tolerance in exchanged hypercubes [J ] . Information Processing Letters , 2013 , 113 ( 14 ): 533 - 537 .

浏览量

629

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

交换交叉立方网络在PMC模型下的(t,k)-诊断度研究