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

诊断是一种提升互连网络可靠性的常用手段.条件诊断是假设系统中任一节点的所有相邻节点不会同时发生故障,这种诊断大大提高了诊断的有效性.提出一种在PMC模型下超立方体的条件诊断算法,通过广度优先搜索遍历整个超立方体,在遍历过程中通过相邻节点之间的诊断结果将超立方体节点分成若干个集合,再通过集合之间的关系和集合中所含元素的数量识别出故障集合和无故障集合.对于n维超立方体,节点数为N,该算法的时间复杂度为O(N2)。

Conditional diagnosability algorithm for hypercube under the PMC model

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