计算机通信网络容错诊断与可靠性分析研究

In modern society, computer communication networks are playing an increasingly important role. But in the actual operation of computer networks, faults are inevitable. Then the network we design must have the ability of fault tolerance to ensure that the network can maintain some properties when faults happened..We focus on the study of fault tolerance transmission, fault tolerant embedding problem and fault diagnosis of networks. That is, when fault happens for a networks, how to transmit messages? whether the other networks can be embedded? How to locate the faulty vertices?.In modern society, computer communication networks are playing an increasingly important role. But in the actual operation of computer networks, faults are inevitable. Then the network we design must have the ability of fault tolerance to ensure that the network can maintain some properties when faults happened..We focus on the study of fault tolerance transmission, fault tolerant embedding problem and fault diagnosis of networks. That is, when fault happens for a networks, how to transmit messages? whether the other networks can be embedded? How to locate the faulty vertices?.In this project, we focus on the study of fault tolerant spanning (fan) connectivity, cycle embedding and fault diagnosis of networks. .We are expecting to achieve some interesting results in the following areas:For some classes of network, we expect to determine their spanning (fan) connectivity and furthermore we might be able to provide its relation to the fault amount. Also, we could obtain some results related to cycle embedding problem with faulty. We could also determine the conditional diagnosability for some networks under the comparison model and provide appropriate diagnosis algorithms. Moreover, we are expecting to achieve some new approaches or methodologies for the problems about the genus of the graph. At last, by this research we might be able to discover more relation between embedding, algebra and algorithm theory.

计算机通信网络是现代信息社会的基础,在现代社会中发挥的作用越来越重要.而计算机网络在实际运行过程中,故障的发生是不可避免的.那么我们所涉及的网络要能够有一定的容错性,保证其在故障发生的情况下还能具有一定的性质.我们的项目主要就网络的容错传输问题,容错嵌入问题以及自身的可诊断性进行研究.即考虑网络在发生故障的情况下,网络中的信息如何传输,其他网路能否嵌入,网路的故障是否能被诊断..在本项目中,我们拟对网络的(容错)支撑(扇)连通度,圈(容错)嵌入问题以及容错诊断问题在现有工作的基础上进行进一步的研究. 预期得到一些网络(在容错情形下)的支撑(扇)连通度, 给出它们与故障数的关系;得到一些网络的容错圈嵌入的相关结果;在比较模型下一些网络的条件可诊断数的界, 给出合适的诊断算法;得到关于确定图的亏格和嵌入分布问题上的若干新结果和新方法;得到图的嵌入理论与代数理论以及与算法理论的更多联系.

本项目考虑了网络的故障诊断数问题,得到了比较模型下匹配网络的条件可诊断数、一些网络的g-好邻条件可诊断数、部分正则网络以及平衡立方体的混合容错可诊断数,同时也研究了条件诊断数2强连通度之间的关系;考虑了平衡立方体、星图以及部分匹配网络的强Menger连通性、给定了超边连通度的点可迁图的存在性、得到了星图,分层立方网络,泡泡网络的高阶容错(边)连通度;得到超立方体和星图的嵌入(边)连通度;通过边数给出有向图或二部有向图在最小度给定时是极大连通的或超连通的充分条件;得到强超立方体的宽直径和容错直径;证明了平衡立方体在边容错下的圈嵌入可能性;证明了排列图是超支撑连通的;讨论了超立方体的点容错不交路;得到无向超环面图的强彩虹连通数的上界,从而给出文献中问题的反例. .除此之外,还研究了带根内无叶近-四剖分平面地图具有三参数计数问题;确定一类特殊的广义r-部完全超图的边色数;考虑圆盘图中连通r-跳k-控制集的构造,并设计了一个基于极大独立集的近似算法;提出了一种用于残差密集生成对抗网络的超分辨率方法;研究了两台恒速机上的MapReduce排序问题.