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

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

Research on node diagnosis under the Symmetric PMC(SPMC) model

Network diagnosis is one of the most exciting topics in graph theory and network science,which affects the reliability and security of multiprocessor systems.With the rapid growth of the scale of the multiprocessor system,the applicability of the global fault diagnosis mode of the system is reduced.Accordingly,the local fault diagnosis benefits from the lower requirements for the network topology,which can process the network in blocks,greatly improving the diagnosis efficiency,having a stronger applicability,and becoming a new research direction.Under the latest Symmetric PMC(SPMC) model,this paper studies the relevant properties of network node diagnosis(local diagnosis),proposes a new topology structure(extended tree structure),obtains the judgment conditions for diagnosable nodes,the relationship between nodes diagnosis and system diagnosis,gives the judgment theorem whether nodes are poor on the extended tree structure,and gives out the detailed proof.According to this theorem,one novel network local fault diagnosis algorithm ST₂_B-FDA with the expanded tree structure is proposed.To validate the effectiveness of this algorithm,this paper applies the Hypercube network for simulation.The time complexity of the algorithm is O(NlogN),which is much lower than that of some traditional fault diagnosis algorithms.This algorithm can effectively reduce the diagnosis cost and greatly improve the diagnosis efficiency.In addition,the proposed algorithm is simple in principle,easy to implement and apply,and can also be used as one of the diagnosis methods for large-scale regular network systems.