具有擴展的局部連通性的超立方體網絡中的容錯路由.pdf

1、在n-維超立方體中，去掉一個結點u的n個鄰接點，u將和其余的結點不連通，所以一般認為n-維超立方體的容錯度是n-1，即對于任一結點v的n個相鄰結點，允許其中n-1個結點發(fā)生故障，此時，n—維超立方體仍然保持連通。然而這是一種極端的情況，使用該方法作為n-維超立方體的容錯度存在很多不足，在n—維超立方體網絡中，n個故障結點正好是某一正確結點的相鄰結點的概率非常低，因此，上面用于確定容錯度的方法與實際情況是有差距的。為了提高系統(tǒng)的容錯路由能

2、力，人們做了大量的工作。王國軍等人在在更一般的形式下針對大量錯誤結點給出了兩個基于兩類局部連通性容錯路由算法，但錯誤結點數不超過超立方體網絡Hn結點數的一半。 本文在局部連通性的基礎上，提出了針對超立方體網絡Hn的擴展的局k-維子立方體連通性以及擴展的局部子立方體連通性概念；證明了具有擴展的局部k—維子立方體連通性或擴展的局部子立方體連通性的Hn中正確結點間是連通的；基于擴展的局部子立方體連通性的超立方體網絡Hn給出了單播容錯路