《互连网络的条件嵌入与容错》由会员分享，可在线阅读，更多相关《互连网络的条件嵌入与容错（4页珍藏版）》请在金锄头文库上搜索。
1、互连网络的条件嵌入与容错【摘要】：电子计算机的出现引起了信息科学突飞猛进的发展.信息量的增加和计算量的日益增大,迫切要求计算机存储能力和运算速度的提升.单台计算机的性能提升即将遇到集成电路制作工艺的瓶颈,这加剧了并行计算机系统的诞生.并行计算机系统通常以某种具有优秀性质的互连网络作为拓扑结构,将多个处理机互连,并行处理,以期大幅提升系统的性能.在众多的互连网络中,路和圈以其简单的结构成为最为基础也最为重要的两种网络拓扑.在设计和选择互连网络时,路和圈的可嵌入性是一个非常重要的因素.因此,互连网络中路和圈的嵌入问题成为一个颇具吸引力的研究领域.在实际的系统中,元器件和通信信道故障在所难免,对应在
2、互连网络中,节点(顶点) 故障和通信连线(边) 故障是不可避免的.这就要求在嵌入路和圈时,这些路和圈不能够通过故障边,即“规避嵌入 ”.另外 ,如果某些元器件或通信线路出现故障 ,那么原网络将遭到一定程度的破坏.在此情形下,人们希望网络的拓扑结构性质得到最大程度的保持.因此,网络的容错能力的度量成为一个重要的课题.另一方面,在某些情形下,人们在选择路由时,希望路由线路通过某些特定的信道,这就使得“指定嵌入” 意义非凡 .本文共分六章.第一章介绍论文的研究内容和意义、一些基本概念和性质、相关的研究进展及论文获得的主要结果.第二章到第四章研究了 k 元 n 立方网络中穿越某些指定子图(线性森林和路
3、)的圈嵌入问题.后两章分别研究了 Bubblc-sort 网络和 Star 网络的容错能力.在无故障 k 元 n 立方网络中穿越指定线性森林的哈密尔顿圈的嵌入问题上,我们在第二章证明了对于 k 元 n 立方网络(n2,k3) 中的任意一个边数不超过 2n-1 的线性森林,这一 k 元 n 立方中可以嵌入一个穿越该线性森林的哈密尔顿圈.这推广了 Wang 等在文献 97中的部分结果.在只有故障边的 3 元n 立方网络中穿越指定线性森林的哈密尔顿圈的嵌入问题上,我们在第三章证明了对于 3 元 n 立方网络(n2)中的任意一个边数 m2n-1的线性森林 L,若故障边数不超过 n-|m/2|-1,则这
4、一 3 元 n 立方中可以嵌入一个穿越 L 的无故障哈密尔顿圈。这一结论将 Chen 在文献59中关于故障超立方网络的指定嵌入的结果推广到了 3 元 n 立方网络中.泛圈性是比哈密尔顿性更强的网络性质.在 k 元 n 立方网络中穿越指定路的泛圈性问题上,我们在第四章证明了对于 k 元 n 立方网络(n2为整数,k5 为奇数)中的任意一个边数不超过 2n-1 的路 P,在该k 元 n 立方中可以嵌入长从(k-1)(n-1)/2+k 到 kn 且穿越 P 的圈.网络的容错能力常用在出现一定数目的故障顶点或故障边的情况下,网络的优良拓扑性质的保存程度来度量.在 Bubble-sort 网络的容错参数
5、的研究方面,我们研究了在 n-维的 Bubble-sort 网络中使得所有的(n-k)-维子 Bubble-sort 网络都发生故障所需要的最小顶点数 FB(n,k)和最小边数 fB(n,k).对于一些特殊的 k,我们得到了这两个参数的确切值.而在k=2 时,我们使用一种巧妙的构造映射的方法,得到了 FB(n,2)和 fB(n,2)的一个上界；并使用这一思想,得到了 fB(n,k)和 fB(n,k)的一个上界.连通度在一定程度上也可以度量互连网络的容错能力.在这一方面,由于在迭代的网络发生故障时,网络可能不再连通,在此情形下,我们希望故障互连网络的每个连通分支都有和原网络具有相同拓扑性质的小规
6、模的非故障的子网.基于这种考虑,我们提出了迭代网络的 k-嵌入限制连通度的概念,并以 Star 网络为例研究了嵌入限制连通度和其它一些连通度之间的关系；对于某些 k,得到了 Star 网络的 k-嵌入限制连通度的值.【关键词】：互连网络容错线性森林哈密尔顿圈 k 元 n 立方 bubble-sort 网络 star 网络【学位授予单位】：山西大学【学位级别】：博士【学位授予年份】：2012【分类号】：TP393.0;O157.5【目录】：中文摘要 8-10ABSTRACT10-14 第一章绪论 14-271.1研究内容与意义 14-161.1.1 研究内容 141.1.2 研究意义 14-16
7、1.2 基本概念和性质 16-221.2.1 图论的基本概念和记号 16-181.2.2 互连网络模型 18-221.3 连网络的嵌入与容错的研究进展 22-251.3.1 网络嵌入的研究进展 22-241.3.2 网络容错参数的研究进展 24-251.4 本文的主要结果 25-27 第二章 k 元 n 立方网络中的指定嵌入 27-512.1 准备工作 27-282.2 奇元 n 立方网络中的指定嵌入 28-402.3 偶元 n 立方网络中的指定嵌入 40-492.4 本章小结 49-51 第三章故障 3 元 n 立方网络中的指定嵌入 51-633.1 准备工作 51-523.2 哈密尔顿圈嵌
8、入 52-623.3本章小结 62-63 第四章 k 元 n 立方网络中穿越指定路的圈嵌入 63-734.1 准备工作 63-644.2k 元 2 立方网络的路泛圈性 64-664.3k 元 n立方网络的路泛圈性 66-724.4 本章小结 72-73 第五章 Bubble-sort 网络的条件容错 73-845.1 准备工作 73-755.2Bubble-sort 网络的容错性75-825.2.1F_B(n,k)和 f_B(n,k)的界 75-765.2.2f_B(n,1)的确定 76-775.2.3f_B(n,2)的一个上界 77-815.2.4f_B(n,k)的一个改进的上界 81-825.3 本章小结 82-84 第六章 Star 网络的嵌人限制连通性度量 84-906.1准备工作 84-866.2Star 网络的连通度比较与计算 86-896.3 本章小结89-90 总结与展望 90-92 参考文献 92-101 攻读博士学位期间的主要研究成果 101-102 致谢 102-103 个人简况及联系方式 103-105 本论文购买请联系页眉网站。
