局部不連通廣義超立方體中的容錯路由

張涌逸

摘要：本文我們提出了局部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}，兩個結點有邊相連當且僅當對應的位有一位不同。為討論方便，取t1=t2=…=tn=k>1。

廣義n-維超立方體的m子立方體：結點集S={x1x2…xn-mkn-m+1

kn-m+2…kn：0kik，i= n-m+1，n-m+2，…，n}（xi為0到k之間確定的整數，i=0，1，…，n-m），兩個結點有邊相連當且僅當對應的位有一位不同。簡記為x1x2…xn-m+1*，稱x1x2…xn-m為廣義超立方體的m子立方體的標記。

局部m維子立方體不連通的廣義n-維超立方體：在廣義n-維超立方體中的每個m子立方體中的正確結點所在的連通分支中有一個正確結點和鄰接m子立方體中的正確結點相鄰接，且至少有一個m子立方體中的正確結點構成連通圖。

從局部m維子立方體不連通的廣義n-維超立方體定義可以看出，不需要所有的m子立方體的正確結點構成連通圖。也不需要m子立方體錯誤結點數少于正確結點數，這樣錯誤結點個數可突破結點個數可突破一半的限制。

定理：局部m維子立方體不連通的廣義n-維超立方體是連通圖。

證明：對于廣義n-維超立方體任意兩個結點S=s1s2…sn、T=t1t2…tn，以及一個正確結點連通的m子立方體W=w1w2…wn-m*。首先我們說明S和W中某個正確結點相連。由S=s1s2…sn，知S所在的m子立方體為s1s2…sn-m*，從前到后比較s1s2…sn-m和w1w2…wn-m對應得位，設s1s2…sn-m+1中w1w2…wn-m對應得第一個不同的位為，找S在w1w2……sn-m+1*中連通分支和w1w2……sn-m+1*中的一對正確的鄰接點T1、T2，知S到T2連通。再從T2起，重復上述過程，直到W中有正確結點和S相鄰。同理有W中也有正確結點和T相鄰。又W中的正確結點構成連通圖，知S和T連通。命題得證。

上面的證明過程也就是局部m維子立方體不連通的廣義n-維超立方體容錯路由的算法思想。下面我們根據這個想法給出算法。

算法：局部m維子立方體不連通的廣義n-維超立方體路由算法：

輸入：在局部m維子立方體不連通的廣義n-維超立方體輸入一對正確結點S、T。

輸出：輸出一條從S到T的路徑。

輸入S=s1s2…sn、T=t1t2…tn（si和t1為0到k之間確定的整數）

尋找一個正確結點連通的m子立方體W=w1w2…wn-m*；

路徑加入：P1=S；

（1）for（ i：=1；in-m；i++）

if（siwi）{1）搜索S在w1w2……sn-m*中連通分支和w1w2……sn-m*中的一對正確的鄰接點T1、T2；2）路徑加入：P1=在w1w2……sn-m*搜索到的S到T1的路徑及結點T2；}

（2）路徑加入：P2=T；

（3）for（ i：=1；in-m；i++）

if（tiwi）{1）搜索T在w1w2……tn-m*中連通分支和w1w2……tn-m*中的一對正確的鄰接點S1、S2；2）路徑加入：P2=在w1w2……tn-m*搜索到的S到S1的路徑及結點S2；}

（4）取出（1）、（3）中最后一個結點U、V，在W中尋找U到V，并添加到P1；

（5）把P2的路徑取反然后添加到P1；

算法在（2）中尋找一個正確結點連通的m子立方體需要時間0（k（n-m）km）。算法（1）需要時間0（2（n-m）km）。故整個算法時間復雜度為0（3kn）。

3 結語

我們在局部廣義k-維子立方體連通性基礎上進一步提出了局部m維子立方體不連通的廣義n-維超立方體的概念。之后我們證明了此類廣義n-維超立方體是連通的，并提出了路由算法。通過分析得到的時間復雜度是0（3kn）。此時間復雜度要比廣度搜索時間復雜度大，但算法是基于局部信息且不需要所有的廣義n-維超立方體的m子立方體正確結點連通，同時還擴大了容錯性。

參考文獻

[1]劉紅美.廣義超立方體網絡容錯路由算法[J].武漢理工大學學報：交通科學與工程版，2006，30（4）：682-685.

[2]王國軍，陳建二，陳松喬.具有大量錯誤結點的超立方體網絡的高效路由算法的設計與討論[J].計算機學報，2001，24（9）：909-916.

摘要：本文我們提出了局部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}，兩個結點有邊相連當且僅當對應的位有一位不同。為討論方便，取t1=t2=…=tn=k>1。

廣義n-維超立方體的m子立方體：結點集S={x1x2…xn-mkn-m+1

kn-m+2…kn：0kik，i= n-m+1，n-m+2，…，n}（xi為0到k之間確定的整數，i=0，1，…，n-m），兩個結點有邊相連當且僅當對應的位有一位不同。簡記為x1x2…xn-m+1*，稱x1x2…xn-m為廣義超立方體的m子立方體的標記。

局部m維子立方體不連通的廣義n-維超立方體：在廣義n-維超立方體中的每個m子立方體中的正確結點所在的連通分支中有一個正確結點和鄰接m子立方體中的正確結點相鄰接，且至少有一個m子立方體中的正確結點構成連通圖。

從局部m維子立方體不連通的廣義n-維超立方體定義可以看出，不需要所有的m子立方體的正確結點構成連通圖。也不需要m子立方體錯誤結點數少于正確結點數，這樣錯誤結點個數可突破結點個數可突破一半的限制。

定理：局部m維子立方體不連通的廣義n-維超立方體是連通圖。

證明：對于廣義n-維超立方體任意兩個結點S=s1s2…sn、T=t1t2…tn，以及一個正確結點連通的m子立方體W=w1w2…wn-m*。首先我們說明S和W中某個正確結點相連。由S=s1s2…sn，知S所在的m子立方體為s1s2…sn-m*，從前到后比較s1s2…sn-m和w1w2…wn-m對應得位，設s1s2…sn-m+1中w1w2…wn-m對應得第一個不同的位為，找S在w1w2……sn-m+1*中連通分支和w1w2……sn-m+1*中的一對正確的鄰接點T1、T2，知S到T2連通。再從T2起，重復上述過程，直到W中有正確結點和S相鄰。同理有W中也有正確結點和T相鄰。又W中的正確結點構成連通圖，知S和T連通。命題得證。

上面的證明過程也就是局部m維子立方體不連通的廣義n-維超立方體容錯路由的算法思想。下面我們根據這個想法給出算法。

算法：局部m維子立方體不連通的廣義n-維超立方體路由算法：

輸入：在局部m維子立方體不連通的廣義n-維超立方體輸入一對正確結點S、T。

輸出：輸出一條從S到T的路徑。

輸入S=s1s2…sn、T=t1t2…tn（si和t1為0到k之間確定的整數）

尋找一個正確結點連通的m子立方體W=w1w2…wn-m*；

路徑加入：P1=S；

（1）for（ i：=1；in-m；i++）

if（siwi）{1）搜索S在w1w2……sn-m*中連通分支和w1w2……sn-m*中的一對正確的鄰接點T1、T2；2）路徑加入：P1=在w1w2……sn-m*搜索到的S到T1的路徑及結點T2；}

（2）路徑加入：P2=T；

（3）for（ i：=1；in-m；i++）

if（tiwi）{1）搜索T在w1w2……tn-m*中連通分支和w1w2……tn-m*中的一對正確的鄰接點S1、S2；2）路徑加入：P2=在w1w2……tn-m*搜索到的S到S1的路徑及結點S2；}

（4）取出（1）、（3）中最后一個結點U、V，在W中尋找U到V，并添加到P1；

（5）把P2的路徑取反然后添加到P1；

算法在（2）中尋找一個正確結點連通的m子立方體需要時間0（k（n-m）km）。算法（1）需要時間0（2（n-m）km）。故整個算法時間復雜度為0（3kn）。

3 結語

我們在局部廣義k-維子立方體連通性基礎上進一步提出了局部m維子立方體不連通的廣義n-維超立方體的概念。之后我們證明了此類廣義n-維超立方體是連通的，并提出了路由算法。通過分析得到的時間復雜度是0（3kn）。此時間復雜度要比廣度搜索時間復雜度大，但算法是基于局部信息且不需要所有的廣義n-維超立方體的m子立方體正確結點連通，同時還擴大了容錯性。

參考文獻

[1]劉紅美.廣義超立方體網絡容錯路由算法[J].武漢理工大學學報：交通科學與工程版，2006，30（4）：682-685.

[2]王國軍，陳建二，陳松喬.具有大量錯誤結點的超立方體網絡的高效路由算法的設計與討論[J].計算機學報，2001，24（9）：909-916.

摘要：本文我們提出了局部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}，兩個結點有邊相連當且僅當對應的位有一位不同。為討論方便，取t1=t2=…=tn=k>1。

廣義n-維超立方體的m子立方體：結點集S={x1x2…xn-mkn-m+1

kn-m+2…kn：0kik，i= n-m+1，n-m+2，…，n}（xi為0到k之間確定的整數，i=0，1，…，n-m），兩個結點有邊相連當且僅當對應的位有一位不同。簡記為x1x2…xn-m+1*，稱x1x2…xn-m為廣義超立方體的m子立方體的標記。

局部m維子立方體不連通的廣義n-維超立方體：在廣義n-維超立方體中的每個m子立方體中的正確結點所在的連通分支中有一個正確結點和鄰接m子立方體中的正確結點相鄰接，且至少有一個m子立方體中的正確結點構成連通圖。

從局部m維子立方體不連通的廣義n-維超立方體定義可以看出，不需要所有的m子立方體的正確結點構成連通圖。也不需要m子立方體錯誤結點數少于正確結點數，這樣錯誤結點個數可突破結點個數可突破一半的限制。

定理：局部m維子立方體不連通的廣義n-維超立方體是連通圖。

證明：對于廣義n-維超立方體任意兩個結點S=s1s2…sn、T=t1t2…tn，以及一個正確結點連通的m子立方體W=w1w2…wn-m*。首先我們說明S和W中某個正確結點相連。由S=s1s2…sn，知S所在的m子立方體為s1s2…sn-m*，從前到后比較s1s2…sn-m和w1w2…wn-m對應得位，設s1s2…sn-m+1中w1w2…wn-m對應得第一個不同的位為，找S在w1w2……sn-m+1*中連通分支和w1w2……sn-m+1*中的一對正確的鄰接點T1、T2，知S到T2連通。再從T2起，重復上述過程，直到W中有正確結點和S相鄰。同理有W中也有正確結點和T相鄰。又W中的正確結點構成連通圖，知S和T連通。命題得證。

上面的證明過程也就是局部m維子立方體不連通的廣義n-維超立方體容錯路由的算法思想。下面我們根據這個想法給出算法。

算法：局部m維子立方體不連通的廣義n-維超立方體路由算法：

輸入：在局部m維子立方體不連通的廣義n-維超立方體輸入一對正確結點S、T。

輸出：輸出一條從S到T的路徑。

輸入S=s1s2…sn、T=t1t2…tn（si和t1為0到k之間確定的整數）

尋找一個正確結點連通的m子立方體W=w1w2…wn-m*；

路徑加入：P1=S；

（1）for（ i：=1；in-m；i++）

if（siwi）{1）搜索S在w1w2……sn-m*中連通分支和w1w2……sn-m*中的一對正確的鄰接點T1、T2；2）路徑加入：P1=在w1w2……sn-m*搜索到的S到T1的路徑及結點T2；}

（2）路徑加入：P2=T；

（3）for（ i：=1；in-m；i++）

if（tiwi）{1）搜索T在w1w2……tn-m*中連通分支和w1w2……tn-m*中的一對正確的鄰接點S1、S2；2）路徑加入：P2=在w1w2……tn-m*搜索到的S到S1的路徑及結點S2；}

（4）取出（1）、（3）中最后一個結點U、V，在W中尋找U到V，并添加到P1；

（5）把P2的路徑取反然后添加到P1；

算法在（2）中尋找一個正確結點連通的m子立方體需要時間0（k（n-m）km）。算法（1）需要時間0（2（n-m）km）。故整個算法時間復雜度為0（3kn）。

3 結語

我們在局部廣義k-維子立方體連通性基礎上進一步提出了局部m維子立方體不連通的廣義n-維超立方體的概念。之后我們證明了此類廣義n-維超立方體是連通的，并提出了路由算法。通過分析得到的時間復雜度是0（3kn）。此時間復雜度要比廣度搜索時間復雜度大，但算法是基于局部信息且不需要所有的廣義n-維超立方體的m子立方體正確結點連通，同時還擴大了容錯性。

參考文獻

[1]劉紅美.廣義超立方體網絡容錯路由算法[J].武漢理工大學學報：交通科學與工程版，2006，30（4）：682-685.

[2]王國軍，陳建二，陳松喬.具有大量錯誤結點的超立方體網絡的高效路由算法的設計與討論[J].計算機學報，2001，24（9）：909-916.