对称PMC(SPMC)模型下节点可诊断性研究

在图论和网络科学上,网络故障诊断是目前非常受欢迎的课题之一,影响着多处理器系统的可靠性与安全性。随着多处理器系统规模的急速增长,系统的全局故障诊断模式适用性降低,相应地,局部故障诊断得益于对网络拓扑结构的要求较低,可对网络分块处理,大幅提高了诊断效率,具有更强的适用性,成为了新的研究方向。针对最新的对称PMC(SPMC)模型,研究了网络节点可诊断(局部诊断)的相关性质,提出了新的拓扑结构(拓展树结构),得到了在SPMC模型下网络节点可诊断的条件以及节点可诊断与系统可诊断的关系,并给出了扩展树结构上各节点是否故障的判定定理及详细证明。根据该定理,提出了扩展树结构网络的悲观故障诊断算法ST 2_B-FDA,并应用到超立方体网络中进行仿真实验,验证算法的有效性。该算法时间复杂度仅O(NlogN),远低于一些传统故障诊断算法的时间复杂度,可有效降低诊断成本,大幅度提升诊断效率。此外,所提出算法原理简单,便于实现及应用,也可作为大规模规则网络系统的诊断方法之一。

PMC模型下网络故障的节点可诊断研究

传统故障诊断研究大多忽略了系统局部特征。PMC模型下,针对于这一问题,引入了节点可诊断的概念,并通过节点可诊断方法的研究得到了节点可诊断度的充分条件和t-可诊断新算法STFDA。最后,对n维超立方网络和n维星状网络从节点可诊断的角度进行了分析,验证了所得充分条件的正确性,并将算法应用到这两种网络中进行故障诊断。其中,充分条件和STFDA算法的实现借助了新的结构ST。STFDA算法的时间复杂度为O(Nδ),δ为网络中节点的最大度。相比于其他算法,算法的时间复杂度得到显著降低。