具有大量错误结点的超立方体网络基于矩阵容错路由算法的设计与讨论

《具有大量错误结点的超立方体网络基于矩阵容错路由算法的设计与讨论》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第一章绪论本章首先介绍了课题的研究内容及研究意义，其次介绍了论文设计到的一些基本概念，重点研究了与本文相关的研究方向的进展与现状，主要包括超立方体网络的容错路由算法及分析，最后对本文的组织结构进行了说明。1．1研究内容及意义1．1。1研究内容论文主要论述了如下两个方面的研究工作。(1)基于安全矩阵的的容错路由算法与分析针对在信息传输过程中出现迂回和死锁的情况，提出了安全矩阵(SMs)这一概念，给出了一种建立SMs及其容错路由算法，n维超立方体每个结点所需的存储开销n2个字，安全矩阵记录了局部更多的信息，与传统的路由算法相比，该算法运行所需的时间会增多，但可以保证准确度，避免在信息传输过程

2、中出现迂回和死锁，从而实现源结点与目的结点之间的高效信息传递。(2)基于极大安全链路矩阵的容错路由算法与分析针对n维超立方体结构的多处理机系统中存在链路故障的情况，提出了用于记录最优通路数的MSLMs及其容错路由算法．给出了极大安全链路矩阵的两个性质并证明，同时还证明了在n维超立方体中，对于任意结点A，MSLM^[i][j]=O(1≤i≤n，l≤j≤n)§结点A和所有与其距离为i且第J位与其第j位互异的结点之间一定不存在Hamming距离为i的最优通路。MSLMs是SVs，ESVs，OPMs，EOPMs以及MSPMs的扩展，用矩阵的形式记录了与源结点的距离为1~n的所有最优通路的条数。1

3、．1．2课题研究意义本课题旨在解决具有错误结点与错误联接的超立方体网络的路由算法与性能分析，深入分析超立方体的容错性，以便更方便的寻找最优通路，同时以理论广东工业大学硕士学位论文推导与计算相结合的方式，清楚的说明了在新的容错路由算法下，如何快速寻找最优路径和记录最优路径的条数，为超立方体网络的容错路由算法的研究提供有力的理论基础，该算法主要限制在单播传输方式的研究。1．2基本概念介绍超立方体结构简介定义1-1(n维超立方体网络)n维超立方体网络Q。(或简称为n-cube)是具有下述性质的一种网络拓扑结构：(1)它由2“个结点和n·2”1条边构成；(2)每一个结点可由一个不同的n位二进制串

4、u(n)tl(n-1)⋯u(1)，u(i)∈{0，1}，1≤i≤n进行编号；(3)结点编号的规则为当且仅当Q。中两个结点的二进制串恰有一位不同时，两个结点是相邻的，即这两个结点之间有一条边相连。图1-1是3维超立方体网络的图例，图中有23=8个结点和3·23-'=12条边，图中标出了结点的编号(分别从000到111)。图1_2是4维超立方体网络的图例，图中有24"-16个结点和4·24-,=32条边，图中标出了结点的编号(分别从0000到1111)。很明显，4维超立方体网络可看作由两个3维超立方体网络通过将对应结点用一条边联接起来构成，以这种方式来看待4维超立方体网络时也很容易对各个结点

5、进行编号。啪Cml0lO¨Olll图1-13维超立方体网络Fig卜1Q32lOl第一章绪论∞101010110OIlll】lO111l图卜24维超立方体网络Fig1—2Q4由于超立方体网络具有正规性、对称性、强容错性、直径短、可嵌入性、并行性和网络通信能力的可扩展性等优点而深受研究者和实践者的欢迎。当超立方体点数增大时，结构变得复杂，尤其是在研究结构的容错性等特征时，需要清楚了解超立方体结构的内部特征，因此引进如下的k维子立方体结构。定义卜2(k维子立方体网络)n3n维超立方体网络Qn的12位二进制串u(n)u(n-1)⋯u(1)中长度为n-k的二进制串u(n-k)u(n-k-1)⋯u(

6、1)对应于Q。中的一个具有2。个结点和k·2H条边的子图，称为n维超立方体网络Q。中的一个k维子立方体网络Q。(或简称为k-subcube)。很明显，这里定义的k维子立方体网络Q。中的结点的二进制串具有X(r1)⋯x(n—k+1)u(n—k)u(n—k_1)⋯u(1)的形式，其中每一个X(j)要么为0要么为l。所以k维子立方体也可记为QF辜幸u(n-k)U(n-k-1)⋯u(1)。容易看出Qn的每一个k维子立方体与k-cube是同构的。n维超立方体Qn也包含其它与k-cube同构的子图。图1-2是表示一个4维超立方体网络由两个基本的3维子立方体网络构成的示意图。当然，每一个基本的3维子立

7、方体网络还可以进一步划分为两个基本的2维子立方体网络(图中每个3维子立方体的一个面)，每一个基本的2维子立方体还可以进一步划分为两个基本的1维子立方体(图中每个2维子立方体网络的一条边及两个相关的结点构成)。k维子立方体结构的引入，可以清晰地刻画低维与高维立方体之间的关系，3广东工业大学硕士学位论文文献[2]的局部子立方体连通的概念及特性也是基于k维子立方体网络结构的。定义1-3(距离)对于n维超立方体Q。中的结点A(w州⋯⋯w。W