新型规则网络的构建与性能分析

论文摘要

互联网络的连接方式决定了网络的通信能力和效率。优秀的网络结构应该具有良好的对称性、可扩展性、递归性、通用性及通信直径小等特点,此外,当网络出现故障时,还应该具有良好的容错性。超立方体网络具有出色的结构性质,演化出了众多变体结构。本文主要通过研究超立方体网络的结构与性能上的不足,构建出两种新型规则网络结构,并对其性能和应用价值进行了较为深入的探讨与分析。首先,根据交叉立方体（CQn）的结构与关联对的概念,本文对扭立方体连接网络（TNn）的结构特性进行了分析,证明了当n≥5时,TNn是不连通的,并且不连通的结点数占整个网络结点数的一半。接着,本文通过分析TNn的错误所在,提出了一种新型网络结构——扭交叉立方体（TCQn）,证明了该网络结构是完全连通的,并研究了其基本网络性质,如正则性,连通度,容错度,递归性等,表明TCQn具有与CQn同样优秀的网络性质。然后,本文利用SN子网的概念,提出了一种高效的路由算法Route（u, v）,使得网络中任意两点通信只需d（u,v）+1步,并证明了TCQn的网络直径为[（n+1）/2]。本文还研究了TCQn的Hamilton性,分别说明了mesh网络,超立方体及其二项树在TCQn中的嵌入策略,扩大了TCQn的应用范围。此外,结合TCQn与CQn网络,本文提出了一种更优的动态网络结构——动态交叉立方体（DCQn）,其不仅具有与TCQn/CQn相同的网络性质,如网络直径也为[（n+1）/2],更重要的是,当网络规模足够大时,DCQn网络的连接边数仅为TCQn/CQn的一半,利于网络的大规模扩展,并且在DCQ中消息的平均路由数也要小得多,降低了网络的通信延迟。在降低网络连接复杂度方面有另一个非常优秀的新型网络结构——交换超立方体（Exchanged hypercube）,该网络降低了网络规模增大时所需要的拓扑连接的开销,具有出色的成本效益。本文根据交换超立方体的图形化定义,得到交换超立方体的公式化定义,证明了交换超立方部分子网与超立方网同构,提出EHS（s,t）和EHT（s,t）的概念,并在此概念的基础上证明了交换超立方体中只存在长度不小于4的偶数圈,证明了交换超立方体的顶点连通度和边连通度都为min{s+1,t+1}。为使交换超立方体具有更广阔的应用范围,本文还提出了超立方体在交换立方网中的三种嵌入策略,证明了n=s+t+1时,n-1维超立方体Qn-1能够同胚地嵌入到交换超立方体EH（s,t）中。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 论文的选题背景与意义
• 1.2 国内外研究现状
• 1.2.1 超立方体的研究
• n、TN_n及交换超立方体的研究'>1.2.2 CQ_n、TN_n及交换超立方体的研究
• 1.2.3 其他网络结构的研究
• 1.3 本文的主要工作
• 1.4 本文的创新点
• 1.5 论文的组织结构
• 第二章 扭立方体连接网络结构的分析
• 2.1 相关基本定义
• 2.2 扭立方体连接网络的结构分析
• 2.3 本章小结
• N）及其基本性质'>第三章 扭交叉立方体（TCQ_N）及其基本性质
• 3.1 扭交叉立方体网络的定义
• 3.2 基本网络性质
• 3.2.1 正则性
• 3.2.2 顶点/边连通度
• 3.2.3 递归特性
• 3.3 本章小结
• 第四章 扭交叉立方体的路由与网络嵌入
• 4.1 路由算法
• 4.2 网络的嵌入
• 4.2.1 圈的嵌入
• 4.2.2 mesh网络的嵌入
• 4.2.3 超立方体的嵌入
• 4.2.4 二项树的嵌入
• 4.3 本章小结
• N）网络结构'>第五章 动态交叉立方体（DCQ_N）网络结构
• 5.1 动态交叉立方体
• 5.2 本章小结
• 第六章 交换超立方体的结构与嵌入研究
• 6.1 交换超立方体拓扑性质
• 6.2 交换超立方体的嵌入问题
• 6.3 本章小结
• 第七章 总结与展望
• 7.1 本文工作总结
• 7.2 未来工作展望
• 参考文献
• 致谢
• 攻读硕士学位期间参与的科研项目
• 攻读硕士学位期间完成的学术论文与获奖情况