数事执术与率用
局部不连通广义超立方体中的容错路由
张涌逸
(太原师范学院计算机系山西晋中030619)
通信技术
摘要：本文我们提出了局部m炸子立方体不连通的广义n-维超立方体的概念，讨论了局部m维于立方体不连通的广义n-炸超立方体的连通性，给出了基于局部m维子主方体不连通的广义n-维超立方体的路由算法,分析了时间复杂度，
关键词:广艾n-超立方体局部m炸子立方体不连通的广义n-维超立方体容错路由算法
中图分类号：TP302.8 1引言
文献标识码：A
文章编号:1007-9416(2014)08-0037-01
命题得证。
对并行处理器的网络拓扑结构，人们已经提出了各种各样的模型，有些也已经用到了实际的应用中，在这些模型中超立方体是常见的模型之一，由于它有良好的性能，人们对它讨论很多，它也有各种各样的变形，广义超立方体就是它的一种变形，随着电子技术的发展，并行处理器数目越来越多，处理器出错误的可能性也越来越大。如何在节点出现错误及结点不能参与传输数据的情况下，仍然能把数据从源节点传输到目的结点，也及容错成为人们越来越关注的问题。在文献1中讨论了具有局部连通性的广义超立方体中的容错路由问题，容错结点个数小于结点个数的一半，本文进一步讨论了广义超立方体中的容错路由，容错结点个数可超过一率以上，同时不需要所有的广义Ⅱ一维超立方体的Ⅲ子立方体正确结点都须具有连通性，只需有一个m子立方体连通即可。
2局部m维子立方体不连通的广义n-维超立方体中的容错路由
广义n-维超立方体：它的结点集V=ix,x,"x：0≤x,≤t-,t为整数，=1，2，，Ⅱ，两个结点有边相连当且仅当对应的位有一位不同。为讨论方便，取t,=t,=.=t,=k>1。
广义n-维超立方体的m子立方体：结点集S=(x,x,"x-k +k,:0≤k,≤k,i=nm+1,nm+2,*,n(x为o到k之间
k.-m+
确定的整数，i=0，1，，n一m),两个结点有边相连当且仅当对应的位有一位不同。简记为x,""X-m+1*，称x,X,""X.-为广义超立方体的m子立方体的标记。
局部m维子立方体不连通的广义n-维超立方体：在广义n-维超立方体中的每个M子立方体中的正确结点所在的连通分支中有个正确结点和邻接m子立方体中的正确结点相邻接，且至少有一个 m子立方体中的正确结点构成连通图。
从局部m维子立方体不连通的广义n一维超立方体定义可以看出，不需要所有的m子立方体的正确结点构成连通图。也不需要m子立方体错误结点数少于正确结点数，这样错误结点个数可突破结点个数可突破一半的限制。
定理：局部M维子立方体不连通的广义Ⅱ一维超立方体是连通
图。
证明：对于广义n维超立方体任意两个结点S=s,s,""5 T=t,t,t,，以及—一个正确结点连通的m子立方体W=w.w,"w.-"*。首先我们说明S和W中某个正确结点相连。由S=S,5"s，知S所在的 m子立方体为s,5,""s.-*，从前到后比较s,S,""s.和w,W,"w..对应得位，设5,5,"s.--+中wW,"W.对应得第一个不同的位为 k,，找S在w,w,".kS,+I"S.-n+,*中连通分支和w,w,"
，""S-+*中的一对正确的邻接点T，T，，知S到T,连通，再从
w.S
T,起，重复上述过程，直到W中有正确结点和S相邻。同理有W中也有正确结点和T相邻，又W中的正确结点构成连通图，知S和T连通，
收稿日期：201407-16
上面的证明过程也就是局部m维子立方体不连通的广义n-维
超立方体容错路由的算法思想。下面我们根据这个想法给出算法。
算法：局部m维子立方体不连通的广义Ⅱ一维超立方体路由算
法：
输人：在局部m维子立方体不连通的广义n-维超立方体输入一对正确结点S、T。
输出：输出一条从S到T的路径，
输入S=S,Ss,、T=t,t-t,(s和t,为0到k之间确定的整数）寻找一个正确结点连通的m子立方体W=w,W,"-W.-m*；路径加人:P=S，
(1)for( i:=1 ,inm,i++)
if(s,≠w,)i1)搜索S在w,W,"kS,+I""s.-n*中连通分支和 W,W,"W,.5,"5,-*中的—对正确的邻接点T,T,2)路径加人 P=在w,W,"·kS,+1S.-.*搜索到的S到T,的路径及结点T,)
(2)路径加人：P,=T
(3)for( i:=1,i≤nm;i++)
if(t,≠w.)1)搜索T在ww..k,.",+.t."*中连通分支和 W,W,"w,f,+I"-t.--*中的—对正确的邻接点S,.S,,2)路径加人 P,=在w,W,"k，",+I-t.-*搜索到的S到S1的路径及结点S,
(4)取出(1)、(3)中最后一个结点U、V在W中寻找U到V.并添加到P1
(5)把P,的路径取反然后添加到P：
算法在(2)中寻找一个正确结点连通的m子立方体需要时间 0(k-mk")。算法(1)需要时间o(2(nm)k")故整个算法时闻复杂
度为0(3k")。 3结语
我们在局部广义k一维子立方体连通性基础上进一步提出了局部M维子立方体不连通的广义Ⅱ一维超立方体的就念，之后我们证明了此类广义Ⅱ一维超立方体是连通的，并提出了路由算法。通过分析得到的时间复杂度是0(3k")。此时间复杂度要比广度搜索时间复杂度大，但算法是基于局部信息且不需要所有的广义n-维超立方体的
m子立方体正确结点连通，同时还扩大了容错性。参考文献
[1]刘红美.广义超立方体网络容错路由算法[J].武汉理工大学学报：交通科学与工程版.2006.30(4):682-685.
[2]王国军.陈建二,陈松检乔.其有大量错误结点的超立方体网络的高效路由算法的设计与讨论[J].计算机学报,2001,24(9):909-916.
作者简介：张涌逸(1968一)，男，山西河曲人,硕士，制教投，主要研究方向为网络容错、网络路由和分布式测试等。