互连网络条件路覆盖与综合诊断策略下的故障诊断性研究

In faulty systems, the constructions and choices of healthy data transmission paths, and the fault diagnosis which is used to perform system maintenance, are important research subjects in the fields of the designing and analysis of high-performance interconnection networks. According to actual needs, under the restriction about failure distribution, path design and fault diagnosis strategy, many important problems remain to be solved. In the interconnection network with some prescribed restrictions, this project will study the existence of paths which contains all the nodes of the network and the diagnosability of faulty systems. The restrictions are as follows: (1) According to the actual requirement, in order to improve network reliability, we should use appropriate fault models. (2) Considering the efficient and reliable data transmission, we will construct pairwise vertex-disjoint paths. On this basis, the paths which are constructed should pass through prescribed pairwise vertex-disjoint paths. (3) Combining the structural features with fault models of the network, in order to greatly improve fault diagnosability, we should design reasonable fault diagnosis strategy and use several strategies at the same time. Moreover, we will write efficient algorithms of path constructions and fault diagnosis in faulty networks. The expected results of this project will be effective theoretical basis of designing and using topological structures of large-scale multiprocessor systems.

故障系统中数据传输路径的选择和构造，以及通过故障诊断进行系统维护，是高性能互连网络设计以及可靠性分析的主要研究方向之一。而依据实际需求，对高阶互连网络的故障分布、路径设计以及故障诊断策略均提出相应的约束条件后，在路径构造以及故障诊断性方面还有许多重要的问题有待解决。本项目拟研究当互连网络满足一定约束条件时，能够充分使用和覆盖网络所有节点的路径的存在性，以及故障系统的诊断能力。其中，约束条件主要包括：(1)根据实际情况，为提高网络的可靠性，采用相应的网络故障模型；(2)为提高数据传输效率以及安全性，可同时设计多条互不相交的路径，并且构造的路径需要经过预先指定的多条互不相交的线路；(3)结合网络的结构特点和故障模型，设计并综合使用多种故障诊断策略，达到大幅度提高故障诊断能力的目的。同时，拟编写高效故障网络路径设计算法和故障诊断算法，为设计和选择大型并行系统互连网络拓扑结构提供有效理论依据。

网络路覆盖以及故障可诊断性研究为高效网络的设计和运用提供了理论基础和技术支持。本课题主要在研究和建立故障模型、多种类约束条件下不交路径构造和优化，以及不同故障模型下网络连通性，并结合分析网络故障可诊断性方面进行一系列研究。. 在网络故障模型的研究方面，通过与实际问题发生环境相结合，我们从故障模型的规模和种类两方面考虑，研究了不同信道故障和多种类故障同时随即发生时，有向无圈图的容错连通性，并且刻画了大规模故障下超立方网络中能够正常运行的分支结构。. 其次，在不交路研究中考虑了多类约束条件。在强连通竞赛图中设计不交路覆盖时，要求每条路的方向必须相同，得到了强生成连通性的下界；在多信道网络中，为降低信号干扰，要求每条路径只能采用一种信道，提出路径QoS优化问题，并在以有向无圈图作为拓扑结构的无线网络中，对路径的总延时和能耗进行优化，编写高效多项式时间近似算法；同时为了降低节点接收信息和发射信息的干扰，要求路径进入节点和离开节点时采用不同的信道，在超立方网络中，降低干扰性的同时降低传输能耗，计算出了任意两点间不同的最短路径条数；当网络中存在多类攻击源且每一个攻击源可以产生一个故障发生区域包含多个点，为此提出强不交路问题，要求每两条路经过的故障区域均不相同，使得一个攻击源至多破坏一条路径，在此条件下对不交路进行优化设计。. 在网络故障可诊断性方面，对网络各类连通性做了大量研究，包括分支（边）连通性以及折叠超立方网络的强menger连通性。由于故障诊断性的研究过程中很大程度上依赖连通性，并且不同的连通性不仅对故障模型提出了要求，并且影响了网络诊断能力，所以提出了网络分支可诊断性，并对超立方网络的分支可诊断性进行了研究，发现在大规模故障下，超立方有很好的可靠性。. 项目资助发表SCI论文6篇，EI论文1篇，待发表4篇，培养在读硕士生2名，协助培养毕业硕士1名，组织研讨会1次，项目成员短期访学1次并获多项合作研究成果。