论文部分内容阅读
互联网络是随着信息技术与计算机科学的发展而产生的一个跨数学、通信、信息等多种学科的研究领域。互联网络拓扑结构是当今并行计算机一个研究热点，大量学者对并行计算机互联网络拓扑结构做了很多研究，如环、树、星型、网格、环绕、超立方体和彼特森图等互联网络拓扑结构，并且已把其中一些网络应用于实际中。 互联网络的最短路和可分组性一直是网络研究领域的热点。互联网络的最短路寻径方式直接影响着计算机并行处理的性能，建立一种有效的路由方式无疑将为大规模网络的高效并行处理提供坚实的基础。可分组性直接反映一个互联网络的通信开销，可分组性良好的网络通信开销也小。因此研究互联网络的最短路算法和可分组性具有重要的理论意义和应用价值。 超立方体(Hypercube)是最早提出的网络拓扑结构之一。它具有正则性、对称性、强容错性、短直径、可嵌入性等优良性质。1991年，EfeK等提出了超立方体互联网络的一个变种——交叉立方体互联网络(Crossedcube)，它不仅具有和超立方体相同的节点数、连通度、正则性、对称性，而且还有一些比超立方体更优越的性质，如其直径和通信开销大约是超立方体的一半。因此人们把交叉立方体嵌入到一些更复杂的互联网络中构成新的网络拓扑结构，例如新型的互联网络RCP(n)的拓扑结构就是由交叉立方体、环和Petersen图组成的。 本文针对超立方体、交叉立方体和RCP(n)互联网络节点编码的特点，在理论分析的基础上，研究了这三种互联网络最短路和可分组性问题，得到了如下主要结果: 1.给出了基于超立方体节点编码的任意两节点间的所有最短路算法，并分析了算法复杂度; 2.对于交叉立方体，先采用双向逼近的思想给出了一个基于交叉立方体互联网络节点编码的路由算法，然后给出了交叉立方体中任意两节点间所有的最短路算法，并分析了这两个算法的算法复杂度; 3.给出了基于RCP(n)节点编码的最短路算法，并分析了算法复杂度; 4.研究了超立方体Qn、交叉立方体Dn和RCP(n)互联网络的可分组性，给出了最优分组方式和最优分组距离，并对这三种互联网络的可分组性进行了比较。 研究结果表明，本文所给出的基于以上三种互联网络节点编码的最短路算法均是多项式时间算法，因此具有非常高的寻径效率，为这三种互联网络设计路由和并行计算提供了理论基础。本文给出的最优分组方法具有简单、便捷、易操作等特点，为三种网络的通信性能进一步研究提供了强有力的理论支撑。