具有擴展的局部連通性的超立方體網(wǎng)絡(luò)中的容錯路由.pdf

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

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