导　　师： 肖文俊

学科专业： H1203

授予学位： 博士

作　　者： ;

机构地区： 华南理工大学

摘　　要： 在并行分布式系统中，互连网络拓扑结构决定性能。至今为止，已经提出了相当多的互连网络拓扑结构。自从S.B.AKERS与B.KRISHNAMURTHY倡导把CAYLEY图作为对称互连网络模型之后，网络设计者和图论学者利用各种技巧提出并研究了一系列互连网络模型，如超立方体网络、TORUS网络、蝴蝶网络、DE BRUJN和KAUTZ网络等。研究者们一般侧重于针对某种具体的网络结构进行研究，并且大多数是采用直观的方法。由于互连网络表示符号的不同，经常会出现相同的网络结构被重复地提出的问题，因此就有必要采用一种新的研究方法来统一处理互连网络拓扑结构问题。
　　 本文的研究重点在于首先利用代数图论的方法分析一些现行网络拓扑结构的构造共性及构造本质，总结出一种对于互连网络拓扑结构的统一研究方法；然后使用这种研究方法，提出了几类新型的互连网络拓扑结构，并研究其拓扑性质、路由算法、通信算法以及一些典型的并行算法等；最后把这种代数图论的研究方法应用于复杂网络和P2P（PEER TO PEER）网络，构造出了一种新的具有小世界特性的P2P覆盖网络。
　　 本文的主要研究内容和创新点包括以下几个方面：
　　 1、使用代数图论方法对现行著名的互连网络拓扑结构进行分析，归纳出了构造互连网络拓扑结构的一套理论的、系统化的研究方法，如CAYLEY图方法、群直积和半直积方法。这种研究方法对于研究互连网络的构造本质和提出新型的互连网络拓扑结构具有现实的意义。
　　 2、通过采用代数图论中CAYLEY图的方法对OTIS（OPTICAL TRANSPOSE INTERCONNECTION SYSTEM）网络的分析发现，该网络模型是陪集图，缺乏对称性。为了弥补其对称性的不足，作者导师提出了一类BISWAPPED网络结构。本文则介绍了如何采用代数图论方法从OTIS网络模型中构造出BISWAPPED网络的过程，并研究了其拓扑性质及容错性能，然后以BISWAPPED网络为基础，开发了基于该网络结构的一系列并行算法包括基本通信算法、并行矩阵乘算法和并行排序算法等。这些算法在BISWAPPED网络中实现简单，且具有较低的时间复杂度。
　　 3、为了吸取超立方体网络和KAUTZ网络的优点，剔除其缺点，使用代数图论中直积的方法，提出了一类新型的积网络--HYPER-KAUTZ网络，并研究其相关的拓扑性质（包括直径、度和HAMILTON圈等），然后基于HYPER-KAUTZ网络提出了最优广播算法、路由算法等一些基本的并行算法，同时分析了HYPER-KAUTZ网络的容错性能和平均内点距离。HYPER-KAUTZ网络具有路由简单和容错性强等诸多优点。
　　 4、使用代数图论中半直积和CAYLEY图方法来研究复杂网络和P2P网络，通过推广CCC（CUBE-CONNECTED CYCLES）图，得到了一类符合小世界特性的CAYLEY图--GCCC（GENERALIZED CUBE-CONNECTED CYCLES）图，并把GCCC图作为P2P网络的静态拓扑，提出了一类新的具有小世界特征的P2P覆盖网络。相对于随机图的静态拓扑，这类覆盖网络具有对称性好、聚集系数大和平均距离小等许多优势。同时还在该覆盖网络的基础上构造了一种基于CAYLEY图的语义对等网络结构。

关 键 词： 互连网络 并行算法 对等网络 并行分布式系统 拓扑结构 代数图论

分 类 号： [TN915.9]

领　　域： [电子电信] [电子电信]