双环网络的仿真研究

论文摘要

图论是离散数学和组合数学领域较为活跃的分支之一。二十世纪六十年代以来,由于生产管理、军事、交通运输、计算机网络等方面提出的实际问题的需要,特别是许多离散性问题的出现,以及由于有了大型电子计算机,从而使大规模问题的求解成为可能,图论及其应用的研究得到了飞速的发展。图的某些参数如连通度和直径,因为其在图论和组合中固有的重要性及其与通信网络的容错性和传输延迟的关系而得到广泛研究。双环网络是图的一种重要形式,是计算机互连网络或通讯系统的一类重要拓扑结构,广泛应用于计算机局域网和各种并行处理结构。二十世纪七十年代以来,人们利用数学的方法研究了双环网络的直径、紧优性、路由和容错性,取得了不少成果。本文将双环网络的寻径过程看成一个遍历节点的过程,提出了利用宽度优先法（BFS）来求解双环网络的直径,由此将计算机仿真引入了双环网络的研究之中。本论文的主要工作包括:1.双环网络直径和紧优性。利用宽度优先法求得双环网络的直径和紧优性。对某个N变化其步长r,s所形成的一族双环网络（N-family）直径具有最大值、最小值和对称分布的特点;紧优双环网络广泛存在,且对称分布。无向双环网络的直径大约是有向双环网络直径的一半。双环网络的直径求解过程可以生成一个等价的螺旋环。2.双环网络紧优分布特性。对某个N变化其步长r,s所形成的一族双环网络（N-family）具有的紧优双环网络数随着N的增大而呈现平稳的波动性,紧优数与N的比值随着N的增大而波动性下降。3.双环网络平均直径。利用宽度优先法求得双环网络的平均直径。N-family中紧优双环网络的平均直径并不一定是最小的,具有最小平均直径的紧优双环网络称为双优双环网络。4.双环网络L形瓦仿真。通过等价的L形瓦可以得到双环网络的直径。随着N的增大和步长的增多,手工构造L形瓦是不可能的,本文利用计算机仿真生成L形瓦,并研究了其形状和参数的分布特征。5.双环网络等价生成树。双环网络是一种网状拓扑结构,为了求其直径,往往将其转换为其它等价的拓扑结构。树是一种典型的数据结构,将双环网络生成等价树,并分析生成树的特征,通过生成树可以得到双环网络的直径。6.双环网络[+h]边优先寻径策略。针对有向单位步长双环网络G（N;1,h）,提出了一种[+h]边优先的寻径策略,并得到一种新的竹筏型L形瓦,“竹筏”中节点之间的[+h]边优先最短路径存在递推关系:由节点的[+h]边优先最短路径推出双环网络的直径公式。7.建立了一个仿真平台。将宽度优先（BFS）搜索的遍历法引入双环网络的研究中,有利于我们进行仿真研究,因此建立了一个仿真平台。仿真平台极大的帮助了我们的研究工作,直径、平均直径、紧优性、螺旋环、生成树、L形瓦、竹筏型L形瓦等都得到很好的仿真。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景
• 1.2 研究方法和内容
• 1.3 论文安排
• 第2章 双环网络直径和紧优性
• 2.1 基本概念
• 2.2 有向单位步长双环网络
• 2.2.1 遍历寻径法
• 2.2.2 寻径算法
• 2.2.3 寻优算法
• 2.2.4 仿真实例
• 2.2.5 等价螺旋环
• 2.3 有向非单位步长双环网络
• 2.3.1 遍历寻径法
• 2.3.2 寻径算法
• 2.3.3 寻优算法
• 2.3.4 仿真实例
• 2.3.5 等价螺旋环
• 2.4 无向单位步长双环网络
• 2.4.1 遍历寻径法
• 2.4.2 寻径算法
• 2.4.3 寻优算法
• 2.4.4 仿真实例
• 2.4.5 等价螺旋环
• 2.5 无向非单位步长双环网络
• 2.5.1 遍历寻径法
• 2.5.2 寻径算法
• 2.5.3 寻优算法
• 2.5.4 仿真实例
• 2.5.5 等价螺旋环
• 2.6 有向与无向双环网络直径的对比
• 2.7 小结
• 第3章 双环网络紧优分布特性
• 3.1 基本概念
• 3.2 有向单位步长双环网络的紧优分布特性研究
• 3.2.1 算法
• 3.2.2 仿真实例
• 3.3 无向单位步长双环网络紧优分布特性研究
• 3.3.1 算法
• 3.3.2 仿真实例
• 3.4 小结
• 第4章 双环网络平均直径
• 4.1 基本概念
• 4.2 有向单位步长双环网络
• 4.2.1 遍历寻径法
• 4.2.2 寻平均直径算法
• 4.2.3 寻优算法
• 4.2.4 仿真实例
• 4.3 有向非单位步长双环网络
• 4.3.1 遍历寻径法
• 4.3.2 寻平均直径算法
• 4.3.3 寻优算法
• 4.3.4 仿真实例
• 4.4 小结
• 第5章 双环网络L形瓦
• 5.1 基本概念
• 5.2 有向单位步长L形瓦仿真
• 5.2.1 双环网络G（N;l,s）的L形瓦仿真算法
• 5.2.2 双环网络G（N;l,s）的仿真实例
• 5.3 有向非单位步长L形瓦仿真
• 5.3.1 双环网络G（N;r,s）的L形瓦仿真算法
• 5.3.2 双环网络G（N;r,s）的仿真实例
• 5.4 小结
• 第6章 双环网络等价生成树的研究
• 6.1 基本概念
• 6.2 有向单位步长双环网络
• 6.2.1 双环网络G（N;l,s）等价树的生成法
• 6.2.2 双环网络G（N;l,s）等价生成树的构造算法
• 6.2.3 双环网络G（N;l,s）等价生成树的构造算法
• 6.3 有向非单位步长双环网络
• 6.3.1 双环网络G（N;r,s）等价树的生成法
• 6.3.2 双环网络G（N;r,s）等价生成树的构造算法
• 6.3.3 双环网络G（N;r,s）等价生成树的构造算法
• 6.4 小结
• 第7章 双环网络[+h]边优先寻径策略
• 7.1 双环网络[+h]优先寻径策略
• 7.1.1 [+h]边优先的最短路径寻径策略
• 7.1.2 [+h]边优先寻径策略的实现
• 7.1.3 文献（陈忠学,2001a）中的错误
• 7.2 小结
• 7.2.1 与[+1][+h]双边寻径策略的比较
• 7.2.2 与传统L形瓦的比较
• 第8章 结束语
• 8.1 论文工作总结
• 8.2 论文创新点
• 8.3 未来的工作展望
• 参考文献
• 在读博士学位期间发表的学术论文
• 在读博士学位期间主持和参加的项目
• 致谢