交叉立方体环互连网络虫洞路由广播算法

交叉立方体环网络是一类层次性互连网络,具有易于扩展其规模的特性。为了提高这种网络在虫洞通信模式下的广播通信性能,提出了一个先环上广播再交叉立方体内部广播的策略,并结合递归分解交叉立方体的方法,进而提出了在虫洞路由模型下时间步为o(n/log2(n+1)+log3m)的广播路由算法。研究表明,该算法可保证通信各路径是不交叉的,从而有效提高了通信性能。

交叉立方体环的Hamilton连通性和Pancyclicity性

交叉立方体是超立方体互连网络的一种变型,它的某些性质优于超立方体。例如,其直径几乎是超立方体的一半;当n≥3,交叉立方体CQn具有Hamilton连通性;当n≥2,所有长度在4到2n之间的圈都能够以扩张1嵌入CQn,即交叉立方体具有Pancyclity性。但是,交叉立方体同超立方体一样,当需要升级时,必须成倍增加结点。交叉立方体环互连网络CRN作为层次环互连网络HRN[8]的一种,可以有效地克服这个缺点,当需要升级时,只需在环上增加一个交叉立方体。在文中,证明了交叉立方体环互连网络仍然保持了交叉立方体具有的Hamilton连通性和Pancyclity性。

互联网络RCP(n)的最短路算法

RCP(n)是最近提出的一种新型互联网络拓扑结构,是由环、Petersen图和交叉立方体所组成的,具有短直径、良好的可扩展性和正则性以及较小的构造开销的性质,是一种具有良好拓扑性质的互联网络。针对RCP(n)上节点编码的特点,采用逐步分解编码,依次寻找路径的方法给出了寻找RCP(n)上任意两点间最短路的一个多项式算法,为RCP(n)上作进一步的路由算法、最优分组等通讯性能的研究提供了理论支持,因此具有一定的理论意义和应用价值。