不完全类超立方体网络的可诊断性

Diagnosability for an Incomplete Participant System Based on Hypercube-like Structure

可诊断度是衡量一个互连网络可靠性的重要指标,用来评估当系统中某些顶点出现故障时该系统可以准确找出故障顶点的能力.PMC模型是并行计算机系统中的一种经典的可诊断模型,被广泛地应用于系统诊断,目前已有大量的基于PMC模型的系统诊断性质研究.类超立方体是一种重要的网络拓扑结构,有很多很好的性质,其中超立方体网络在实际中得到了广泛应用.研究者们针对类超立方体网络存在坏边或者硬故障顶点时系统可诊断度进行了研究,对同时存在两种故障情形下的可诊断度还没有相关研究.设是一个-维类超立方体网络,本文证明对于坏边和硬故障顶点的集合S,若|S|≤n-1且,则H_n-S在PMC模型下的系统可诊断度是δ(H_n-S),其中δ(H_n-S)表示H_n-S的最小顶点度数.

The degree of diagnosability is an important standard to measure the reliability of the interconnection network. It is used to measure the ability of system to find the fault nodes. The PMC model is a classical diagnostic model of parallel computing system which has been applied to system diagnosis widely. There are a lot of researchs of the system diagnosability under the PMC model. Hypercube-like is an important network topology with a lot of good properties and there are a lot of practical networks application based on hypercube-like structure. Researchers have study the diagnosability of hypercube-like which have missing links or broken nodes, and the diagnosability of hypercube-like have missing links and broken nodes has not yet been related research. In this paper, we proves that let S be a subset of missing links and broken nodes in n-dimension hypercube-like Hn with ｜ S ｜ ≤ n - 1 and n ≥ 3, then the diagnosibility of Hn - S under the PMC model isS（ Hn - S）