学位论文 > 优秀研究生学位论文题录展示

星图网络并行最优路径寻找算法的研究与设计

作　者: 王丹丹
导　师: 郭大昌
学　校: 广东工业大学
专　业: 组合数学与最优化
关键词: 星图网络并行路径算法哈米尔顿循环拉丁方最短距离不相交路径
分类号: TP393.02
类　型: 硕士论文
年　份: 2011年
下　载: 21次
引　用: 0次
阅　读: 论文下载

内容摘要

星图网络具有良好的点边对称性、很强的分层结构以及很好的容错性能,与超立方体网络相比较,在节点数目相当时,星图网络的直径和度都远远比超立方体的小,因此星图网络作为一个互联网络的模式,最近受到研究者的密切关注,并被认为是最有可能取代已被广泛应用的超立方体的一种拓扑结构。对于互联网络来说,能否有效地在节点之间进行数据传输是很重要的,通过建立点不相交路径而获得有效地路由,不但能避免信息堵塞,提高信息传递效率,而且能在节点出现故障的情况下提供可选择的路由。本文在星图拓扑结构特性的基础上设计了星图中的并行路径寻找算法。本文首先阐述了星图网络的知识背景、研究现状以及星图网络的拓扑结构。然后,根据源节点和目的节点在第一维的数字是否相同,应用哈米尔顿循环拉丁方给出了相应的寻找并行路径的算法。1.针对星图的源节点到目的节点第一维相同的情况,提出了一种星图的信息路由算法,给出了从一个源节点到一个目的节点传递k个数据包,令第i个数据包将沿着第i条路径传输(1≤i≤k).对所有的数据包,要保证每个数据包的路径与其余数据包的路径不相交。为了构造这样的路由,提出了应用哈米尔顿循环拉丁方的星图信息路由算法,该算法的时间复杂度为O(n2)。同时,也给出了并行路径的个数以及路径的长度,并对结论进行了证明。与传统算法相比较,该算法简单直接,方便快捷,能使路径达到最优。2.针对星图的源节点到目的节点第一维不相同的情况,也可以应用哈米尔顿循环拉丁方的星图信息路由算法,但没有第一种情况显而易见。由于情况稍微复杂,在使用哈米尔顿循环拉丁方时,一些路径并没有直接到达目的节点,再次利用路径函数,通过循环达到目的节点。也给出该算法的时间复杂度为O(n2)。本文同样也给出这种模式的并行路径以及并行路径的个数和长度,并证明了所得出的结论。在实例中,能方便快捷寻找出路径,同时也验证了该算法的有效性。

全文目录

摘要  4-5
ABSTRACT  5-7
目录  7-8
CONTENTS  8-9
第一章绪论  9-13
  1.1 研究背景及意义  9-10
  1.2 国内外研究现状  10-11
  1.3 研究内容  11-12
  1.4 论文的结构安排  12-13
第二章星图  13-20
  2.1 星图的基本概念  13-14
  2.2 星图的相关定义与性质  14-20
第三章源与目的节点的第一维相同并行路由算法  20-30
  3.1 引言  20
  3.2 预备知识  20-21
  3.3 星图应用哈米尔顿拉丁方的并行路由算法  21-23
  3.4 算法设计  23-29
  3.5 本章小结  29-30
第四章源与目的节点的第一维不相同并行路由算法  30-43
  4.1 引言  30
  4.2 预备知识  30-31
  4.3 算法设计  31-37
  4.4 主要结论证明  37-42
  4.5 本章小结  42-43
结论  43-45
参考文献  45-48
攻读硕士学位期间发表的论文  48-50
致谢  50

星图网络并行最优路径寻找算法的研究与设计

内容摘要

全文目录

相似论文