数字热本与表用
k－维子连通的超立方体中并行路由
张涌逸
(太原师范学院计算机系山西太原030012)
通信技术
摘要：本文在k-维子连通的超立方体网络的定义的基础上,构造任意两个结点U、V的min(dk(U),dk(V)条并行容错路由同时讨论了每条路径的步长的上限。
关键调k一炸子立方体连通的并行路由超立方体容错
中图分类号：TN302.8 1引言
文献标识码：A
文章编号:1007-9416(2013)08-0031-01
依次各位取反，使得每次取的k一维子立方体与V,的海明距离每次
虽然人们提出了很多拓扑结构，但真正又实用价值的拓扑结构并不多见。超立方体以其很多良好的特性：正则、对称、可扩展、容错能力强等，使其成为较为实用的拓扑结构。已经在InteliPSC/2、 NCUBE/10.CM-2,GSI/GrayOrigin2000等中得到应用。随之超立方体网络容错成为一个重要的研究课题。主国军[2]中讨论了可容纳大量错误结点超立方体中并行路由算法。王雷等人之后又提出了一维子连通的超立方体网络的概念[1],可容纳更多错误结点，错误链路。本文在k一维子连通的超立方体网络基础上进一步讨论了超立方体中并行路由问题。
2k-维子连通的超立方体中并行容错路由
2.1基本概念
n维超立方体网络：是由2n个结点构成的无向图Qn=G(V，E)。 V=u,u,"u,-,un:u,(0,1,i=1,2,"",nl。两个结点x,y相邻当且仅当n个位置中恰有一个位置的值不同。
k-维子立方体：是由结点集u,u,"u,-，u_：u,0,ll,i= k+1,2，,n生成的n维超立方体网络Qn的子图.此k-维子立方体记为u，u,"u-**，u，u""u,-称为此k-维子立方体的标记。
两k一维子立方体的海明距离指的是两个k一维子立方体对应标记位不同的个数，
两k-维子立方体相邻是指这两个k一维子立方体海明距离为1。 k一维子连通的：如果Ⅱ一维超立方体网络Qn中的k一维子立方体
里可达结点(至少两个)是连通的，且和每一个相邻k一维子立方体有对可达结点邻接，则称Q为k一维子连通的，
有文献知k一维子连通的n维超立方体网络是连通的。
并行路由：指一个计算机网络中从一个结点到另一个结点通过不交叉路径传递信息的过程。
2.2k-维子连通的超立方体中并行路由
定理：任给k一维子连通的n维超立方体网络Qn中的一对可达结点U，V,至少存在min(d,(U),d,(V))条从U到V的，且的长度不超过(d(U.,V.)+1)2k+2的并行路径,(其中,U.，V.表示U，V所在的相邻;d,(U),d(V)分别表示U，V不在U，V.中相邻的可达结点数，d(U，V)表示U,,V的海明距离。）
证明：
我们讨论当U，V所在的k-维子立方体Uk，Vk的海明距离> 1。设k-维子立方体U,,V,的标记分别为u，u,""u,-k,v，V,""v,-k取U,相邻的n-k个相邻的k-维子立方体H,=u,u,""u--=u" u**,=1,2，",n-k,其中为u取反，即=1-u，则H到V,的海明距离或为d(U,V,)+1或为d(UV)1,对每个H构造一个 k-维子立方体序列wi（简称w序列)如下，对u,+"u,u,,u,，"u,
少1,直到最后一个k-维子立方体必是V,相邻k-维子立方体。可以看出任何两个k一维子立方体序列没有相同的k一维子立方体。1)如果U和Hi中的可达结点相邻，V和W的最后一个k一维子立方体可达结点相邻，则由k一维子连通的性质知存在U到V的路径，2)如果U不和Hi中的可达结点相邻且V和不W的最后一个k-维子立方体可达结点相邻，就舍弃这条路。3)如果U和H中的可达结点相邻，V和不 W,的最后一个k一维子立方体可达结点相邻，且V和Wj的最后一个 k一维子立方体可达结点相邻，U不和H中的可达结点相邻，此时H 和Hj除共同相邻Uk外，只有另外一个共同相邻k-维子立方体Z。Z, 在序列W，，W中，且不在其余序列之中,特别，当d(U，，V,)=2时，有从结点U到Zij再到V的路径。其余情形有从U到Hi，Hi到Zij，再通过W到V的路径。4)其余序列，要么全是与U相邻可达结点对应的序列，要么全是与V相邻可达结点对应的序列，放弃这种序列。到此，我们已经构造了min(d,(U),d,(V))条从U到V的路径。这min(d,(U), d,(V)条从U到V的路径中，一种情况是直接走W序列，另一种情况先走W序列的第一个k一维子立方体，然后在转向Z形式，再转到W 序列到V，由W序列的选取，及Zi的性质，知这些序列处U，V外，没有共同结点这样我们构造的这min(d(U),d(V))条路径，就是U到 V的并行路径，
这些并行路径中，从U到U的邻接k一维子立方体只须一步，同样从V到V.的邻接一维子立方体也只须一步，在最坏情况下经过个k-维子立方体最多需要2k步，中间最多经过d(U.，V,)+1个k-维子立方体，故从U到V最多(d(U,,V,)+1)2k+2步。
至于海明距离U，V所在的k-维子立方体U，，V,的海明距离为
0和1的情形，相比上述情形更简单，就不再费述。 3结语
随着超大规模集成电路的出现使得网络的结构越来越复杂，规模越来越大，人们在设计和处理网络拓扑是也越来越关心网络的可靠性。但以前在研究超立方体网络的容错性时，网络的容错能力相比结点数较小，之后王雷等人提出的k一维子立方体连通的超立方体概念，不止适合结点错误，也适合链路错误，同时也使得网络容错能力超过结点数的一率以上。本文建立一维子立方体连通的超立方体基础上，故本文的并行容错路由的容错能力也超过结点数的一
半以上。参考文献
[1]王雷.陈治平,蒋新华.林亚平.故障翅立方体网络中的高效容错路由算法研究[J].计算机应用.2005(S1):4-8.
[2]王国军.陈松乔,陈建二.其有大量错误结点的超立方体网络中并行路由算法[3].计算机工程与科学,2001(05):5-12.
31