【作者】 张芩；

【导师】 肖文俊；

【作者基本信息】 华南理工大学 ， 计算机应用技术， 2013， 博士

【摘要】 并行分布系统中，互连网络拓扑结构决定了网络的性能。许多基于Cayley图的互连网络模型被提出，如超立方体网络、Torus网络、蝶网络、de Bruijn和Kautz网络等。学者们一般是针对某种具体的网络结构进行研究，且大多采用直观的方法。由于互连网络表示符号的不同，经常会出现本质相同的网络结构被重复地提出，因此，有必要用基于Cayley图的研究方法来统一处理互连网络拓扑结构问题。小世界网络因其具有高的聚集系数和小的网络直径而受到广泛关注。基于Cayley图可以构建具有确定性小世界特征的网络拓扑结构，研究证明，结合了Cayley图和小世界现象的网络拓扑结构上的算法简单高效。本文的主要研究内容和创新点包括以下几个方面：1．首先，使用群直积和半直积的方法，对一些现行的互连网络拓扑结构进行分析，对其构造的过程加以研究和分类；接着，拓展OTIS网络为SN网络，分析BSN网络与SN网络的关系，论证BSN网络和因子网的关系；最后，将BSN互连结构加以推广，生成更具普遍意义的MSN互连结构，对其拓扑性质、路由和广播算法、嵌入、节点不相交路径等方面做出相关研究。2．对地铁网络进行了全耦合建模，对网络拓扑结构的度量指标进行了计算和分析，比如最短路径数目、节点的度分布情况、聚集系数、鲁棒性等方面。研究表明，基于全耦合的地铁网络拓扑结构具有小世界现象。通过对高密度换乘节点和偏远节点的分析，可以对地铁未来的规划提供有意义的数据作为参考。3．使用Cayley图方法研究P2P覆盖网络，得到了一类符合小世界特性的Cayley图，并以此Cayley图作为P2P覆盖网络的静态拓扑，提出了一类具有小世界特征的P2P覆盖网络拓扑结构模型CHC。通过对比发现，CHC具有对称性好、聚集系数大、平均距离小等许多优势。4.提出使用Cayley图作为虚拟拓扑的静态模型，利用Cayley图的高对称性，使得静态模型具有许多优秀的性质，例如，更简单的路由算法，更高的可靠性和容错性。并以WDM光网络和WMN无线网络为例，讨论Cayley图可以简化拓扑设计中的众多的约束条件，得到一些好的规律。更多还原

【Abstract】 Performance of the network is determined by the topology of interconnection network inparallel distributed system. Many models of interconnection networks based on Cayley graphhave been proposed, such as hypercube, torus, butterfly, de Bruijn and Kautz networks.Most researches focused on a specific structure of the network intuitively. Some samenetwork structures are repeatedly proposed for different symbols. So it is necessary to use themethods based on Cayley graph to unify interconnection network topology.Small-world network interests a lot of researcher for high clustering coefficient andsmall network diameter. Network Topology based on Cayley Graph can be constructed withdeterministic small-world characteristics. The algorithms are simple and efficient if thenetwork topology base on Cayley graph has small-world phenomenon.The main contents and innovations include the following aspects:1. First, some interconnection network topologies are studied and classified by directproduct or semidirect method. Second, OTIS is extended to SN. The relationship of SN andBSN is analyzed. The relationship of BSN and basis network is proved.Finally, more generalinterconnection structure—MSN is proposed by generalizing BSN. Many researches of MSNare in progress, such as topological properties, routing and broadcasting algorithms,embedding, node-disjoint paths, etc.2. All-coupling model is designed for the subway network. Data were calculated andanalyzed by the network topology metrics, such as the number of shortest paths, node degreedistribution, clustering coefficient, robustness and so on. Research shows that theAll-coupling network topology of the subway has small-world phenomenon. Analysinghigh-density nodes and remote nodes, some advices can be provided to the subway company.3. The Cayley graph with small-world characteristics can be static P2P overlay networktopology. CHC is proposed that its static topology model is Cayley graph. CHC has manyadvantages, such as good symmetry, high clustering coefficient and small average distance.4. Cayley graph can be used as a virtual topology static model. Many good properties are found for good symmetry, such as simpler routing algorithm, higher reliability andfault-tolerant. In WDM optical networks and wireless mesh networks, Cayley graph can beused to simplify some constraints of topology design and some good law can be obtained.更多还原