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

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

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