张涌逸

摘要：本文我们提出了局部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}，两个结点有边相连当且仅当对应的位有一位不同。……