局部不连通广义超立方体中的容错路由

张涌逸

摘要：本文我们提出了局部m维子立方体不连通的广义n-维超立方体的概念，讨论了局部m维子立方体不连通的广义n-维超立方体的连通性，给出了基于局部m维子立方体不连通的广义n-维超立方体的路由算法，分析了时间复杂度。

关键词：广义n-维超立方体 局部m维子立方体不连通的广义n-维超立方体 容错路由 算法

中图分类号：TP302.8 文献标识码：A 文章编号：1007-9416（2014）08-0037-01

1 引言

对并行处理器的网络拓扑结构，人们已经提出了各种各样的模型，有些也已经用到了实际的应用中，在这些模型中超立方体是常见的模型之一，由于它有良好的性能，人们对它讨论很多，它也有各种各样的变形，广义超立方体就是它的一种变形。随着电子技术的发展，并行处理器数目越来越多，处理器出错误的可能性也越来越大。如何在节点出现错误（及结点不能参与传输数据）的情况下，仍然能把数据从源节点传输到目的结点，也及容错成为人们越来越关注的问题。在文献[1]中讨论了具有局部连通性的广义超立方体中的容错路由问题，容错结点个数小于结点个数的一半。本文进一步讨论了广义超立方体中的容错路由，容错结点个数可超过一半以上，同时不需要所有的广义n-维超立方体的m子立方体正确结点都须具有连通性，只需有一个m子立方体连通即可。

2 局部m维子立方体不连通的广义n-维超立方体中的容错路由

广义n-维超立方体：它的结点集V={x1x2…xn：0xiti-1，ti为整数，i=1，2，…，n}，两个结点有边相连当且仅当对应的位有一位不同。为讨论方便，取t1=t2=…=tn=k>1。

广义n-维超立方体的m子立方体：结点集S={x1x2…xn-mkn-m+1

kn-m+2…kn：0kik，i= n-m+1，n-m+2，…，n}（xi为0到k之间确定的整数，i=0，1，…，n-m），两个结点有边相连当且仅当对应的位有一位不同。简记为x1x2…xn-m+1*，称x1x2…xn-m为广义超立方体的m子立方体的标记。

局部m维子立方体不连通的广义n-维超立方体：在广义n-维超立方体中的每个m子立方体中的正确结点所在的连通分支中有一个正确结点和邻接m子立方体中的正确结点相邻接，且至少有一个m子立方体中的正确结点构成连通图。

从局部m维子立方体不连通的广义n-维超立方体定义可以看出，不需要所有的m子立方体的正确结点构成连通图。也不需要m子立方体错误结点数少于正确结点数，这样错误结点个数可突破结点个数可突破一半的限制。

定理：局部m维子立方体不连通的广义n-维超立方体是连通图。

证明：对于广义n-维超立方体任意两个结点S=s1s2…sn、T=t1t2…tn，以及一个正确结点连通的m子立方体W=w1w2…wn-m*。首先我们说明S和W中某个正确结点相连。由S=s1s2…sn，知S所在的m子立方体为s1s2…sn-m*，从前到后比较s1s2…sn-m和w1w2…wn-m对应得位，设s1s2…sn-m+1中w1w2…wn-m对应得第一个不同的位为，找S在w1w2……sn-m+1*中连通分支和w1w2……sn-m+1*中的一对正确的邻接点T1、T2，知S到T2连通。再从T2起，重复上述过程，直到W中有正确结点和S相邻。同理有W中也有正确结点和T相邻。又W中的正确结点构成连通图，知S和T连通。命题得证。

上面的证明过程也就是局部m维子立方体不连通的广义n-维超立方体容错路由的算法思想。下面我们根据这个想法给出算法。

算法：局部m维子立方体不连通的广义n-维超立方体路由算法：

输入：在局部m维子立方体不连通的广义n-维超立方体输入一对正确结点S、T。

输出：输出一条从S到T的路径。

输入S=s1s2…sn、T=t1t2…tn（si和t1为0到k之间确定的整数）

寻找一个正确结点连通的m子立方体W=w1w2…wn-m*；

路径加入：P1=S；

（1）for（ i：=1；in-m；i++）

if（siwi）{1）搜索S在w1w2……sn-m*中连通分支和w1w2……sn-m*中的一对正确的邻接点T1、T2；2）路径加入：P1=在w1w2……sn-m*搜索到的S到T1的路径及结点T2；}

（2）路径加入：P2=T；

（3）for（ i：=1；in-m；i++）

if（tiwi）{1）搜索T在w1w2……tn-m*中连通分支和w1w2……tn-m*中的一对正确的邻接点S1、S2；2）路径加入：P2=在w1w2……tn-m*搜索到的S到S1的路径及结点S2；}

（4）取出（1）、（3）中最后一个结点U、V，在W中寻找U到V，并添加到P1；

（5）把P2的路径取反然后添加到P1；

算法在（2）中寻找一个正确结点连通的m子立方体需要时间0（k（n-m）km）。算法（1）需要时间0（2（n-m）km）。故整个算法时间复杂度为0（3kn）。

3 结语

我们在局部广义k-维子立方体连通性基础上进一步提出了局部m维子立方体不连通的广义n-维超立方体的概念。之后我们证明了此类广义n-维超立方体是连通的，并提出了路由算法。通过分析得到的时间复杂度是0（3kn）。此时间复杂度要比广度搜索时间复杂度大，但算法是基于局部信息且不需要所有的广义n-维超立方体的m子立方体正确结点连通，同时还扩大了容错性。

参考文献

[1]刘红美.广义超立方体网络容错路由算法[J].武汉理工大学学报：交通科学与工程版，2006，30（4）：682-685.

[2]王国军，陈建二，陈松乔.具有大量错误结点的超立方体网络的高效路由算法的设计与讨论[J].计算机学报，2001，24（9）：909-916.

摘要：本文我们提出了局部m维子立方体不连通的广义n-维超立方体的概念，讨论了局部m维子立方体不连通的广义n-维超立方体的连通性，给出了基于局部m维子立方体不连通的广义n-维超立方体的路由算法，分析了时间复杂度。

关键词：广义n-维超立方体 局部m维子立方体不连通的广义n-维超立方体 容错路由 算法

中图分类号：TP302.8 文献标识码：A 文章编号：1007-9416（2014）08-0037-01

1 引言

对并行处理器的网络拓扑结构，人们已经提出了各种各样的模型，有些也已经用到了实际的应用中，在这些模型中超立方体是常见的模型之一，由于它有良好的性能，人们对它讨论很多，它也有各种各样的变形，广义超立方体就是它的一种变形。随着电子技术的发展，并行处理器数目越来越多，处理器出错误的可能性也越来越大。如何在节点出现错误（及结点不能参与传输数据）的情况下，仍然能把数据从源节点传输到目的结点，也及容错成为人们越来越关注的问题。在文献[1]中讨论了具有局部连通性的广义超立方体中的容错路由问题，容错结点个数小于结点个数的一半。本文进一步讨论了广义超立方体中的容错路由，容错结点个数可超过一半以上，同时不需要所有的广义n-维超立方体的m子立方体正确结点都须具有连通性，只需有一个m子立方体连通即可。

2 局部m维子立方体不连通的广义n-维超立方体中的容错路由

广义n-维超立方体：它的结点集V={x1x2…xn：0xiti-1，ti为整数，i=1，2，…，n}，两个结点有边相连当且仅当对应的位有一位不同。为讨论方便，取t1=t2=…=tn=k>1。

广义n-维超立方体的m子立方体：结点集S={x1x2…xn-mkn-m+1

kn-m+2…kn：0kik，i= n-m+1，n-m+2，…，n}（xi为0到k之间确定的整数，i=0，1，…，n-m），两个结点有边相连当且仅当对应的位有一位不同。简记为x1x2…xn-m+1*，称x1x2…xn-m为广义超立方体的m子立方体的标记。

局部m维子立方体不连通的广义n-维超立方体：在广义n-维超立方体中的每个m子立方体中的正确结点所在的连通分支中有一个正确结点和邻接m子立方体中的正确结点相邻接，且至少有一个m子立方体中的正确结点构成连通图。

从局部m维子立方体不连通的广义n-维超立方体定义可以看出，不需要所有的m子立方体的正确结点构成连通图。也不需要m子立方体错误结点数少于正确结点数，这样错误结点个数可突破结点个数可突破一半的限制。

定理：局部m维子立方体不连通的广义n-维超立方体是连通图。

证明：对于广义n-维超立方体任意两个结点S=s1s2…sn、T=t1t2…tn，以及一个正确结点连通的m子立方体W=w1w2…wn-m*。首先我们说明S和W中某个正确结点相连。由S=s1s2…sn，知S所在的m子立方体为s1s2…sn-m*，从前到后比较s1s2…sn-m和w1w2…wn-m对应得位，设s1s2…sn-m+1中w1w2…wn-m对应得第一个不同的位为，找S在w1w2……sn-m+1*中连通分支和w1w2……sn-m+1*中的一对正确的邻接点T1、T2，知S到T2连通。再从T2起，重复上述过程，直到W中有正确结点和S相邻。同理有W中也有正确结点和T相邻。又W中的正确结点构成连通图，知S和T连通。命题得证。

上面的证明过程也就是局部m维子立方体不连通的广义n-维超立方体容错路由的算法思想。下面我们根据这个想法给出算法。

算法：局部m维子立方体不连通的广义n-维超立方体路由算法：

输入：在局部m维子立方体不连通的广义n-维超立方体输入一对正确结点S、T。

输出：输出一条从S到T的路径。

输入S=s1s2…sn、T=t1t2…tn（si和t1为0到k之间确定的整数）

寻找一个正确结点连通的m子立方体W=w1w2…wn-m*；

路径加入：P1=S；

（1）for（ i：=1；in-m；i++）

if（siwi）{1）搜索S在w1w2……sn-m*中连通分支和w1w2……sn-m*中的一对正确的邻接点T1、T2；2）路径加入：P1=在w1w2……sn-m*搜索到的S到T1的路径及结点T2；}

（2）路径加入：P2=T；

（3）for（ i：=1；in-m；i++）

if（tiwi）{1）搜索T在w1w2……tn-m*中连通分支和w1w2……tn-m*中的一对正确的邻接点S1、S2；2）路径加入：P2=在w1w2……tn-m*搜索到的S到S1的路径及结点S2；}

（4）取出（1）、（3）中最后一个结点U、V，在W中寻找U到V，并添加到P1；

（5）把P2的路径取反然后添加到P1；

算法在（2）中寻找一个正确结点连通的m子立方体需要时间0（k（n-m）km）。算法（1）需要时间0（2（n-m）km）。故整个算法时间复杂度为0（3kn）。

3 结语

我们在局部广义k-维子立方体连通性基础上进一步提出了局部m维子立方体不连通的广义n-维超立方体的概念。之后我们证明了此类广义n-维超立方体是连通的，并提出了路由算法。通过分析得到的时间复杂度是0（3kn）。此时间复杂度要比广度搜索时间复杂度大，但算法是基于局部信息且不需要所有的广义n-维超立方体的m子立方体正确结点连通，同时还扩大了容错性。

参考文献

[1]刘红美.广义超立方体网络容错路由算法[J].武汉理工大学学报：交通科学与工程版，2006，30（4）：682-685.

[2]王国军，陈建二，陈松乔.具有大量错误结点的超立方体网络的高效路由算法的设计与讨论[J].计算机学报，2001，24（9）：909-916.

摘要：本文我们提出了局部m维子立方体不连通的广义n-维超立方体的概念，讨论了局部m维子立方体不连通的广义n-维超立方体的连通性，给出了基于局部m维子立方体不连通的广义n-维超立方体的路由算法，分析了时间复杂度。

关键词：广义n-维超立方体 局部m维子立方体不连通的广义n-维超立方体 容错路由 算法

中图分类号：TP302.8 文献标识码：A 文章编号：1007-9416（2014）08-0037-01

1 引言

对并行处理器的网络拓扑结构，人们已经提出了各种各样的模型，有些也已经用到了实际的应用中，在这些模型中超立方体是常见的模型之一，由于它有良好的性能，人们对它讨论很多，它也有各种各样的变形，广义超立方体就是它的一种变形。随着电子技术的发展，并行处理器数目越来越多，处理器出错误的可能性也越来越大。如何在节点出现错误（及结点不能参与传输数据）的情况下，仍然能把数据从源节点传输到目的结点，也及容错成为人们越来越关注的问题。在文献[1]中讨论了具有局部连通性的广义超立方体中的容错路由问题，容错结点个数小于结点个数的一半。本文进一步讨论了广义超立方体中的容错路由，容错结点个数可超过一半以上，同时不需要所有的广义n-维超立方体的m子立方体正确结点都须具有连通性，只需有一个m子立方体连通即可。

2 局部m维子立方体不连通的广义n-维超立方体中的容错路由

广义n-维超立方体：它的结点集V={x1x2…xn：0xiti-1，ti为整数，i=1，2，…，n}，两个结点有边相连当且仅当对应的位有一位不同。为讨论方便，取t1=t2=…=tn=k>1。

广义n-维超立方体的m子立方体：结点集S={x1x2…xn-mkn-m+1

kn-m+2…kn：0kik，i= n-m+1，n-m+2，…，n}（xi为0到k之间确定的整数，i=0，1，…，n-m），两个结点有边相连当且仅当对应的位有一位不同。简记为x1x2…xn-m+1*，称x1x2…xn-m为广义超立方体的m子立方体的标记。

局部m维子立方体不连通的广义n-维超立方体：在广义n-维超立方体中的每个m子立方体中的正确结点所在的连通分支中有一个正确结点和邻接m子立方体中的正确结点相邻接，且至少有一个m子立方体中的正确结点构成连通图。

从局部m维子立方体不连通的广义n-维超立方体定义可以看出，不需要所有的m子立方体的正确结点构成连通图。也不需要m子立方体错误结点数少于正确结点数，这样错误结点个数可突破结点个数可突破一半的限制。

定理：局部m维子立方体不连通的广义n-维超立方体是连通图。

证明：对于广义n-维超立方体任意两个结点S=s1s2…sn、T=t1t2…tn，以及一个正确结点连通的m子立方体W=w1w2…wn-m*。首先我们说明S和W中某个正确结点相连。由S=s1s2…sn，知S所在的m子立方体为s1s2…sn-m*，从前到后比较s1s2…sn-m和w1w2…wn-m对应得位，设s1s2…sn-m+1中w1w2…wn-m对应得第一个不同的位为，找S在w1w2……sn-m+1*中连通分支和w1w2……sn-m+1*中的一对正确的邻接点T1、T2，知S到T2连通。再从T2起，重复上述过程，直到W中有正确结点和S相邻。同理有W中也有正确结点和T相邻。又W中的正确结点构成连通图，知S和T连通。命题得证。

上面的证明过程也就是局部m维子立方体不连通的广义n-维超立方体容错路由的算法思想。下面我们根据这个想法给出算法。

算法：局部m维子立方体不连通的广义n-维超立方体路由算法：

输入：在局部m维子立方体不连通的广义n-维超立方体输入一对正确结点S、T。

输出：输出一条从S到T的路径。

输入S=s1s2…sn、T=t1t2…tn（si和t1为0到k之间确定的整数）

寻找一个正确结点连通的m子立方体W=w1w2…wn-m*；

路径加入：P1=S；

（1）for（ i：=1；in-m；i++）

if（siwi）{1）搜索S在w1w2……sn-m*中连通分支和w1w2……sn-m*中的一对正确的邻接点T1、T2；2）路径加入：P1=在w1w2……sn-m*搜索到的S到T1的路径及结点T2；}

（2）路径加入：P2=T；

（3）for（ i：=1；in-m；i++）

if（tiwi）{1）搜索T在w1w2……tn-m*中连通分支和w1w2……tn-m*中的一对正确的邻接点S1、S2；2）路径加入：P2=在w1w2……tn-m*搜索到的S到S1的路径及结点S2；}

（4）取出（1）、（3）中最后一个结点U、V，在W中寻找U到V，并添加到P1；

（5）把P2的路径取反然后添加到P1；

算法在（2）中寻找一个正确结点连通的m子立方体需要时间0（k（n-m）km）。算法（1）需要时间0（2（n-m）km）。故整个算法时间复杂度为0（3kn）。

3 结语

我们在局部广义k-维子立方体连通性基础上进一步提出了局部m维子立方体不连通的广义n-维超立方体的概念。之后我们证明了此类广义n-维超立方体是连通的，并提出了路由算法。通过分析得到的时间复杂度是0（3kn）。此时间复杂度要比广度搜索时间复杂度大，但算法是基于局部信息且不需要所有的广义n-维超立方体的m子立方体正确结点连通，同时还扩大了容错性。

参考文献

[1]刘红美.广义超立方体网络容错路由算法[J].武汉理工大学学报：交通科学与工程版，2006，30（4）：682-685.

[2]王国军，陈建二，陈松乔.具有大量错误结点的超立方体网络的高效路由算法的设计与讨论[J].计算机学报，2001，24（9）：909-916.