交叉扭立方体的建模与分析

发布时间：2018-04-07 15:36

  本文选题：交叉立方体　切入点：扭N立方体　出处：《广西大学》2014年硕士论文

【摘要】：进入信息化社会后,强大的网络需求一直督促网络结构不断发生变化。为了满足这一需求,提出了立方体网络的概念,其中超立方体网络是一种最受欢迎的新型网络结构。很多学者针对超立方体网络进行深入研究,并得到了很多关于其的优秀结论。但是随着研究的深入,也暴露了超立方体网络的一些缺陷,对其进行改进得到了诸多变体结构。本文在结合交叉立方体和扭N立方体两种结构的基础上提出了一种新型网络结构,在各方面都有改进。具体工作如下： (1)本文通过研究交叉立方体和扭N立方体的结构,提出了交叉扭立方体的定义,并给出了相应的拓扑结构网络图,证明了交叉扭立方体部分子网与超立方体网络同构,同时研究了交叉扭立方体的网络直径、连通度等问题。通过上述拓扑结构基本性质的研究,得到了交叉扭立方体的性能优于扭N立方体的重要结论。 (2)为了更深入研究交叉扭立方体模拟其他网络结构的能力,本文研究交叉扭立方体互连网络上的圈嵌入问题,证明了任何长度为L(3L≤2n)的圈均能以扩张1嵌入到交叉扭立方体中,同时证明了交叉扭立方体是Hamilton连通图,然后提出时间复杂度为O(L)的交叉扭立方体的圈嵌入算法。 (3)由于图嵌入主要包括圈和树嵌入两个方面,所以在研究圈嵌入后,本文选择继续研究树的嵌入性质。首先引入完全二项树和完全四项树的概念,其次给出交叉扭立方体的3D视图,最后得出了N阶完全二项树可以以扩张为2嵌入到N维交叉扭立方体中的重要结论,并且证明了N阶完全四项树可以以扩张2嵌入到2N-1维的交叉扭立方体中的结论。 (4)在之前已有的研究结果基础上,本文更加深入研究此种变体的路由属性。首先通过研究交叉扭立方体的局部连通性来确定其容错性,证明了它即使在错误节点分布不均匀的情况下仍然能够保持网络的正常工作；其次根据其结构特征提出适合此种结构的路由算法,证明路由算法找到的路径长度接近两个节点间的最短路径长度,并且经过分析计算出算法的时间复杂度为O(n),通过对比发现提出的新算法要优于Efe提出的交叉立方体路由算法。
[Abstract]:After entering the information society, the strong network demand has been urging the network structure to change constantly.In order to meet this demand, the concept of cube network is proposed, in which hypercube network is the most popular new network structure.Many scholars have studied hypercube network deeply and got many excellent conclusions about it.However, with the development of research, some defects of hypercube network have been exposed, and many variants have been obtained by improving the hypercube network.In this paper, a new network structure is proposed based on the combination of cross cube and torsional N cube, which has been improved in all aspects.The specific work is as follows:1) by studying the structure of crossed cube and twisted N cube, the definition of cross twisted cube is proposed, and the corresponding topological structure network diagram is given. It is proved that the partial subnet of cross twisted cube and the network of hypercube are isomorphic.At the same time, the network diameter and connectivity of cross-twisted cubes are studied.Based on the study of the basic properties of the above topological structure, it is concluded that the performance of the crossed twisted cube is better than that of the twisted N-cube.In order to further study the ability of cross-twisted cubes to simulate other network structures, the problem of loop embedding on cross-twisted cubes interconnection networks is studied in this paper.It is proved that any cycle of L ~ 3L 鈮，

本文编号：1719796