PMC模型下超立方体的一种条件诊断算法  

Conditional diagnosability algorithm for hypercube under the PMC model

作　　者：张丽果[1] 杜慧敏[2] 韩俊刚[1,2] 

机构地区：[1]西安电子科技大学微电子学院,陕西西安710071 [2]西安邮电学院电子工程学院,陕西西安710121

出　　处：《西安电子科技大学学报》2012年第5期148-153,共6页Journal of Xidian University

基　　金：国家自然科学基金重点资助项目(61136002/F040201);国家自然科学基金资助项目(60976020);教育部科学研究重点资助项目(211180);陕西省教育厅科研计划资助项目(11JK1063;2010JK833);陕西省工业公关计划资助项目(2011K06-47);陕西省13115重大科技专项资助项目(2009ZDKG-43);陕西省自然科学基金资助项目(2010JQ8014)

摘　　要：诊断是一种提升互连网络可靠性的常用手段.条件诊断是假设系统中任一节点的所有相邻节点不会同时发生故障,这种诊断大大提高了诊断的有效性.提出一种在PMC模型下超立方体的条件诊断算法,通过广度优先搜索遍历整个超立方体,在遍历过程中通过相邻节点之间的诊断结果将超立方体节点分成若干个集合,再通过集合之间的关系和集合中所含元素的数量识别出故障集合和无故障集合.对于n维超立方体,节点数为N,该算法的时间复杂度为O(N2)。Diagnosis has played an important role in the reliability of the interconnection network. Conditional diagnosability is the method that assumes that none of the neighbors of any vertex in the system are faulty at the same time. This diagnosis method greatly enhances the effectiveness of the diagnosis. A conditional diagnosability algorithm for the hypercube based on the PMC model is proposed in the paper. The nodes of the hypereube are divided into several sets through the diagnosis result between two adjacent nodes, and faulty sets and fault-free sets are identified through the realation among sets and the number of elements in the set. The conditional diagnosability of faulty nodes can be effectively implemented when the number of the faulty nodes do not exceed 4 （n - 2） ＋ 1 （n ≥ 5）. The time complexity of the algorithm is O（N2 ） for the n-dimensional hypercube with N nodes.

关 键 词：超立方体 PMC模型 条件诊断 诊断算法 

分 类 号：TP303[自动化与计算机技术—计算机系统结构]