| 一种高效的基于BC图的t/k-诊断算法 |
| |
| 引用本文： | 邓伟,杨晓帆,吴中福.一种高效的基于BC图的t/k-诊断算法[J].电子学报,2006,34(4):698-701. |
| |
| 作者姓名： | 邓伟 杨晓帆 吴中福 |
| |
| 作者单位： | 重庆大学计算机学院,重庆,400044 |
| |
| 基金项目： | 国家发展和改革委员会资助项目，同济大学校科研和教改项目 |
| |
| 摘 要： | 为了提高系统级故障诊断中的诊断度,人们以牺牲很小一部分结点不能正确诊断为代价,提出了t/k-故障诊断策略.BC图是包括了超立方体和多种变形立方体的一类图.对于结点总数为N的BC图,本文提出了一个O(N log2N)的t/k-故障诊断算法.目前尚未有相关t/k-故障诊断算法的文章发表,但与著名的悲观一步t-故障诊断算法(t/k-故障诊断算法在k=1时的情况)的O(N2.5)相比较,在时间复杂度上本文算法是高效的.
|
| 关 键 词： | 系统级故障诊断 诊断算法 BC图 宽度优先搜索 |
| 文章编号： | 0372-2112（2006）04-0698-04 |
| 收稿时间： | 2005-06-22 |
| 修稿时间： | 2005-06-222005-08-26 |
An Efficient Diagnosis Algorithm of BC Graphs |
| |
| DENG Wei,YANG Xiao-fan,WU Zhong-fu.An Efficient Diagnosis Algorithm of BC Graphs[J].Acta Electronica Sinica,2006,34(4):698-701. |
| |
| Authors: | DENG Wei YANG Xiao-fan WU Zhong-fu |
| |
| Affiliation: | College of Computer Science, Chongqing University, Chongqing 400044, China |
| |
| Abstract: | The t/k-diagnosis strategy of system-level diagnosis significantly increases the self-diagnosing capability of multiprocessor systems at the cost of at most k fault-free nodes being incorrectly identified as faulty.The BC graphs are a large class of network topologies,which include several known structures as special cases.Although the t/k-diagnosabilities of the BC graphs have recently been determined,the efficient t/k-diagnosis algorithm of the BC graphs has yet to be developed.In this paper,we present an O(N log_2N) time algorithm for the t/k-diagnosis of the BC graphs,where N is the number of nodes of the system in concern. |
| |
| Keywords: | system-level diagnosis t/k-diagnosis strategy diagnosis algorithm BC graph |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
