·通信工程
数字技术与应用
具有扩展局部连通性超立方体中的容错路由
张涌速
（太原师范学院计算机系
山西太原
030012)
摘要：在局部违通性的基础上，提出了针对超立方休月络Ha的扩展的局部k一维子立方体选通性规念，证明了具有扩展的局部k一维于立方体连通性的H中正确端点间是速通的；提出了超立方休网络n中基于扩展局部k一维于立方体速通性的路由算法。
关键词：客储路由
超立方体月络
中图分类号：TP302.8
扩展的局部一维于立方休的连通性
算法
文本城号：1007-9416（2010)08-0057-02
文数标识码，A
Fault-TolerantRoutinginHypercubeNetworkswithExtendedLo-
cal-Connectivity
ZHANG Yong-yi
(Department of Computer，Taiyuan Normal University,Taiyuan 030012,China)
Abstract;Based on the coneepts of local ksubeubeeonneetivity for hypertube metworks, s new conceptsextended loeal ksubeube conncctivity was propesed.lt was proved that all nen-faulty sodes in s hypereube setwork with extesded local ksubeubeeenseetivity
saaeaaeeaaae te s given nonfaulty destination
node wss proposed in s hypereube network.
Key WordsFaulttolerant routing,Hypercube network,Extended loeal k—subeubeeonnectivity;Algorithm
引言
随若并行计算机、互联网络和VLSI技术的迅速发展，系统中的并行处理越来越多，结点故障和链路故障H益增大，随之，网络的容错路由间题成为网络研究的重要课题川。由于超立方体理想的特性，如正则性，对称性，直轻小，可扩展性强，最大容错性等，使它成为网络中最常用的拓扑结构，在考惠超立方体网络故障时，结点故障模型和链路故障模型是两种最常见的故障模型，国内外对此作了大景的研究。文献"4利用概率的方法对超立方体网络的弃错路由进行了研究。文献15.61分别提出了不安全结点，安全向量等念并给出了相应的容错路由算法，这算法主要关注最优通路，而容错能力与n一维超立方体中的结点总数2"相距甚远。2001年王国军等在文龄中提出了基于局部连通性的容错路由算法，结点的容错能力大大提高，但错误结点数也不到超立方体结点数的一率。本文在局部子立方体连通性基础上进一步提出了扩展的局部k一维子立方体连通性和扩展局部子立方体连通性概念，使得容错模型降低了对k一维子立方体的要求，提高了通用性和错误结点数，同时容错模型也适用链路故障。
1
扩展的局部k一维子立方体连
通性
1.1基本概念
基本的k一维子立方体；对于任意给定的t、k(0 万方数据
的标记。本文仅讨论这种形式的子立方体，并在下文中把"基本"二字去撑。
两个k一维子立方体之间的海明距离：指的是这两个k一维子立方体的二进制标记中的不同的二进制位的位数，海明距离为 1的两个k一维子立方体称为邻接的，也即；设b,b,"b, **b++b2"-b,.a,a,""a, **+/a**""a,为两个k一维子立方体，若b,b,"b,b. +/b+"b_和a,,"*a,a+/+2"*a_H有
一做
不同时，称这两个k一维子立方体邻接。
1.2扩展的局部k一维子立方体连通性本节给出扩展的局部k一维立方体
连通性的概念及其与全局连通性的关系。
定义1(扩展的局部k一维子立方体的连通性)：如果n一维超立方体网络H,中每一个 k一维子立方体中由正确结点构或的每个连通子图中存在正确结点与第接的k一维子立方体中正确结点相邻接，且至少有一个k一维子立方体正确结点是连通的，则称 H,是扩展局部k一维子立方体连通的。
概据这定义，在一个扩展局部k一维子立方体连通的n维超立方体H中，一个k 一维于立方体H，中可有2*-1个错误结点，因此，扩展局部k一维子立方体连通的n一维超立方体Hn中可能有总计多达2***(2*-1)=2n-2-个错误结点。又因k—维子立方体有n-k个邻接的的k一维子立方体，而基本的k一维子立方体的个数为2"/2*=2"**，故有故障的链路条数可以为n2-1=2#--1(n-k)。
下面证明扩展的局部k一维子立方体连通的H中的正确结点构成一个连通图。
定理1：扩展的局部k一维子立方体连通的n一维超立方体网络H,中的正确结点构成一个连通图。
证明：对H,中的任意一对正确结点U和 V，记U所在的k维子立方体为a,a," a,**+++*"a，记V所在的k一维子立方体为C,C""C，**c++C+2"C先找到正确结
nede
点是连通的子立方体b,b*b*b++b+*" b,任取b,b,b,**b+b"b,中的一个正确接点W。
首先：我们说明U和W是连通的，如果U 和W在同一个k一维子立方体内且在此k一维子立方体内的同一个连通子图中，则U和 W是连通的，否则，在序列a,，a,，"*，a,a+*+1" a++2"",a,Rb,.b,,"",b,,b++}b,*?"*,b, 中按下标从小到大取出第一个对应元素不等的元a，和b,，则a,a""aana,**a,+/a an和b,b+ 两个k一维子立方体邻接。在
a,a,a,a
+1a,**a+*/a++2"*a,内部，U所在的连通子图中有正确结点S，和b,b,b，aa+a,**a+*+/a+++2"a,中某个正确结点T，是结的，可知U和T。是连通的：然后在序列a， a""aBau+""，an和bb?b,b}b*2"，b,中按下标从小到大取出第一个对应元素不等的元a，和b +2,b,b,"*b-lai,a+** a,**a+/&+*2"a 和b,b,"-b - b,, a+ a,**a+*+/&++2"a, 这两个k—维子立方体邻接，在b,b"b-a a“a,*+ +a,内部，T。所在的连通子图中有正确结点S和b,b,"-ba"aa++/+2"a,中某个正确结点T 是邻结的，可知T，和T，是连通的，故U和 T，是连通的，此过程一直继续，直到上述形式的两序列完全相同，此时U与b,b,"b,**b+*b+*2"b,中的某个正确结点T，是连通的。又b,b,b,*b+b++2"*b,是连通图，故U与W是连通的。
其次证明：V和W是连通的，和证明U和 W是连通的同理。
综合上述两步U和V是连通的。证毕下面我们给出扩展k一维子立方体连
通的H,之间的关系。
推论1；如果n一维超立方体是扩展局部 k一维超立方体连通的，则当h>k时，H,也
数字技术与应用
57