论文部分内容阅读
互联网络的连接方式决定了网络的通信能力和效率。优秀的网络结构应该具有良好的对称性、可扩展性、递归性、通用性及通信直径小等特点,此外,当网络出现故障时,还应该具有良好的容错性。超立方体网络具有出色的结构性质,演化出了众多变体结构。本文主要通过研究超立方体网络的结构与性能上的不足,构建出两种新型规则网络结构,并对其性能和应用价值进行了较为深入的探讨与分析。首先,根据交叉立方体(CQn)的结构与关联对的概念,本文对扭立方体连接网络(TNn)的结构特性进行了分析,证明了当n≥5时,TNn是不连通的,并且不连通的结点数占整个网络结点数的一半。接着,本文通过分析TNn的错误所在,提出了一种新型网络结构——扭交叉立方体(TCQn),证明了该网络结构是完全连通的,并研究了其基本网络性质,如正则性,连通度,容错度,递归性等,表明TCQn具有与CQn同样优秀的网络性质。然后,本文利用SN子网的概念,提出了一种高效的路由算法Route(u, v),使得网络中任意两点通信只需d(u,v)+1步,并证明了TCQn的网络直径为[(n+1)/2]。本文还研究了TCQn的Hamilton性,分别说明了mesh网络,超立方体及其二项树在TCQn中的嵌入策略,扩大了TCQn的应用范围。此外,结合TCQn与CQn网络,本文提出了一种更优的动态网络结构——动态交叉立方体(DCQn),其不仅具有与TCQn/CQn相同的网络性质,如网络直径也为[(n+1)/2],更重要的是,当网络规模足够大时,DCQn网络的连接边数仅为TCQn/CQn的一半,利于网络的大规模扩展,并且在DCQ中消息的平均路由数也要小得多,降低了网络的通信延迟。在降低网络连接复杂度方面有另一个非常优秀的新型网络结构——交换超立方体(Exchanged hypercube),该网络降低了网络规模增大时所需要的拓扑连接的开销,具有出色的成本效益。本文根据交换超立方体的图形化定义,得到交换超立方体的公式化定义,证明了交换超立方部分子网与超立方网同构,提出EHS(s,t)和EHT(s,t)的概念,并在此概念的基础上证明了交换超立方体中只存在长度不小于4的偶数圈,证明了交换超立方体的顶点连通度和边连通度都为min{s+1,t+1}。为使交换超立方体具有更广阔的应用范围,本文还提出了超立方体在交换立方网中的三种嵌入策略,证明了n=s+t+1时,n-1维超立方体Qn-1能够同胚地嵌入到交换超立方体EH(s,t)中。