交错群网络的容错性分析

作     者：郑淑霞 

作者单位：福建师范大学 

学位级别：硕士

导师姓名：许力;周书明

授予年度：2008年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：Cayley图 交错群网络ANn 并行路 诊断度 

摘      要：众所周知，信息社会的基础是计算机互连网络，信息交换的关键是通信算法。寻找具有路由算法简单、容错性能高等良好性质的互连网络是实现各种通信算法和协议的前提。自从***,***倡导把Cayley图(群图)作为对称互连网络模型之后，网络设计者和图论学者利用各种技巧提出并研究了一系列互连网络模型，如超立方体Q，星图网络S及蝴蝶网络(Butterfly Network)，蜂窝网络(Honeycomb Network)等。交错群图AG作为星图可替代的网络，也在1993年由J.S. Jwo,***和***首先提出来。冀有虎提出了一种新的交错群网络AN，与AG相比，AN的每个结点的度大约是旧网络的一半且直径与旧网络大致相同，优越性显而易见。进一步，陈宝兴给出了AN的最优路由算法。本文在此基础上，解决了如下问题： (1)给出了交错群网络AN的n-1条内点不交的并行路构造方法及所有路的长度l的上下界，进而求出了宽直径与直径的关系：D(AN)+1≤d(AN)≤D(AN)+2，同时确定了其连通度是n-1。 (2)多处理器系统的容错计算的研究已有近半个世纪的历史，无论是在诊断策略，诊断模型，还是诊断算法方面，都取得了一系列的成果。Preparata，Metze和Chien首次提出了系统级的t-可诊断的概念。继PMC模型之后，他们又提出了比较诊断模型。本文给出了交错群AN在PMC模型和比较诊断模型下关于不同诊断策略的诊断度。 (3)另一方面，系统级故障诊断是针对一个系统的全局诊断度而言的，却忽略了局部诊断问题。由于整个系统的部分子系统其故障节点的个数可能超出了系统的诊断度。显然，讨论系统的局部诊断度可以得知更多的局部结点的连通度信息。本文最后讨论了交错群网络的局部诊断度和强局部诊断性等相关问题。