交錯立方體在故障情形下的診斷度和診斷算法*

王 喜，張書奎

(1.蘇州工業(yè)職業(yè)技術(shù)學(xué)院,江蘇 蘇州 215004；2.蘇州大學(xué)計算機科學(xué)與技術(shù)學(xué)院,江蘇 蘇州 215006)

1 引言

多處理器互連網(wǎng)絡(luò)(簡稱互連網(wǎng)絡(luò))是指由多個處理器按照一定規(guī)則相互連接而成的網(wǎng)絡(luò)，目前越來越廣泛地出現(xiàn)在計算機技術(shù)的相關(guān)研究與應(yīng)用領(lǐng)域中。作為并行系統(tǒng)的基礎(chǔ)，互連網(wǎng)絡(luò)的性質(zhì)直接決定了系統(tǒng)的性能。近年來，我國在基于并行系統(tǒng)的超級計算機領(lǐng)域有一系列的重大突破，特別地，由國防科技大學(xué)牽頭研制，安裝在國家超級計算天津中心的超級計算機——“天河三號”E級原型機，在最新的全球超級計算機TOP500榜單中蟬聯(lián)冠軍[1]。

由于大規(guī)?；ミB網(wǎng)絡(luò)中有很多處理器，這就很難避免某些處理器出現(xiàn)故障，而這些故障處理器可能影響到整個互連網(wǎng)絡(luò)的穩(wěn)定性，從而導(dǎo)致整個網(wǎng)絡(luò)癱瘓，造成極大的經(jīng)濟損失。一個互連網(wǎng)絡(luò)的拓撲結(jié)構(gòu)可用一個圖來表示，其中處理器與處理器之間的通信鏈路可分別用頂點集和邊集表示。為了確?；ミB網(wǎng)絡(luò)可以正常運行，那么在頂點出現(xiàn)故障時，就應(yīng)及時、準確地找出故障頂點并進行替換。系統(tǒng)能夠找出故障頂點并進行替換的能力，稱為系統(tǒng)的診斷性。系統(tǒng)的診斷度是一個系統(tǒng)中能夠準確找出所有故障頂點的最大個數(shù)。若系統(tǒng)中出現(xiàn)的故障頂點的個數(shù)不超過其診斷度t時，則該系統(tǒng)能夠確保所有的故障頂點都可被正確地診斷出來，那么系統(tǒng)是t-可診斷的[2]。

Preparata等[2]在給出系統(tǒng)級故障診斷概念的同時提出了一個經(jīng)典診斷模型——PMC診斷模型，該模型是用3位作者姓名的首字母來命名的?；谠撛\斷模型的研究已經(jīng)在大規(guī)模多處理器系統(tǒng)、無線傳感器網(wǎng)絡(luò)系統(tǒng)、片上網(wǎng)絡(luò)設(shè)計等領(lǐng)域廣泛應(yīng)用[3]。PMC診斷模型使用測試頂點測試其它頂點，且通過測試結(jié)果來判斷頂點狀態(tài)，然而，如果測試頂點本身是有故障的，那么測試的結(jié)果將是不準確的。Chang等[3]研究了判斷一個網(wǎng)絡(luò)是否適用 PMC診斷模型的方法。 Hakimi等[4]證明了一個系統(tǒng)在PMC模型下是可診斷的，還給出了系統(tǒng)在PMC模型下是t-可診斷的充分必要條件。Lin等[5]研究了基于PMC模型的通用正則圖上限制連通度和診斷度之間的關(guān)系。然而，上述研究成果無法適用于大部分的網(wǎng)絡(luò)[6]。因此，近年來，研究者們做出了大量關(guān)于特殊網(wǎng)絡(luò)在PMC模型下的診斷度和t-診斷的研究成果[7 - 10]。曹騫等[8]研究了無K3子圖的互連網(wǎng)絡(luò)在PMC模型下的條件可診斷度。張麗果等[9]提出了PMC模型下超立方體的一種時間復(fù)雜度為O(N2)的條件診斷算法。

交錯立方體(Cross-cube)[7]作為超立方體網(wǎng)絡(luò)的一類重要變形，與超立方體相比具有低直徑、哈密頓連通性等優(yōu)越性。研究交錯立方體中部分頂點和邊出現(xiàn)故障的情形下的診斷度和診斷算法，能夠更加精確地度量該網(wǎng)絡(luò)的可性。本文將討論交錯立方體上存在故障邊和故障頂點時，基于PMC模型的系統(tǒng)診斷度和診斷算法。進一步，將研究該算法的時間復(fù)雜度并進行相關(guān)仿真實驗。研究結(jié)果表明，本文設(shè)計的算法在高效性方面明顯優(yōu)于文獻[9]和文獻[11]中的診斷算法。

2 預(yù)備知識

本文所用到的圖的符號和定義遵循徐俊明[12]所著圖論書中規(guī)范。本文使用G=(V(G),E(G))表示一個圖， 其中V(G)表示頂點集，E(G)表示邊集[12]。對于圖G中任意2個頂點u和v，若(u,v)∈E(G)，則u和v是鄰居；頂點u在圖G中的鄰居集合表示為NG(u)={v|(u,v)∈E(G)}；頂點u和v之間的距離表示為dist(u,v)；頂點u的度數(shù)表示為degG(u)。圖G的最小頂點度數(shù)表示為δ(G)。如果V′?V(G)，可用G[V′]表示圖G的頂點導(dǎo)出子圖。進一步，使用G-V′來表示G[V(G)-V′]。 圖G的連通度表示為κ(G)[12]。

Figure 1 A 4-dimensional cross-cube C4圖1 1個4維交錯立方體C4

在PMC診斷模型下，相鄰的頂點可相互測試。給定圖G中任意2個相鄰的頂點u和v，頂點u對頂點v進行了1次測試可以表示為1個有序?qū)Α磚,v〉，其中u表示測試者，v表示被測試者，根據(jù)u和v的測試狀態(tài)可得出相應(yīng)的測試結(jié)果0或1。如表1所示，當(dāng)且僅當(dāng)測試者u是無故障的，才可以精確地給出被測頂點v的正確測試結(jié)果。例如若v是無故障的，則測試結(jié)果是0；若v是有故障的，則測試結(jié)果是1。若測試者u是有故障的，則對被測試頂點v的診斷結(jié)果是不準確的，測試結(jié)果可以隨機為0或1。

Table 1 PMC model表1 PMC診斷模型

1個圖G中相鄰頂點之間進行的所有測試所構(gòu)成的集合，稱作測試任務(wù)，可用1個有向圖T=(V,L)表示，其中在測試任務(wù)T中u測試v用〈u,v〉∈L表示。本文假設(shè)任意2個相鄰頂點會互相進行測試，即若(u,v)∈G，則有〈u,v〉∈L且〈v,u〉∈L。

測試任務(wù)T的所有測試結(jié)果的集合可表示為癥候群，用函數(shù)σ：L→{0,1}來表示。給定任意測試任務(wù)T的1個癥候群σ，故障頂點集合F?V，以及頂點u∈V-F，當(dāng)頂點v∈F的測試結(jié)果為σ(〈u,v〉)=1，以及當(dāng)頂點u∈V-F的測試結(jié)果為σ(〈u,v〉)=0時，則稱F與σ是一致的。由于測試者出現(xiàn)故障時給出的測試結(jié)果是不可靠的，故同一個故障頂點集合F會產(chǎn)生出多個不同的癥候群。本文使用σ*(F)來表示故障頂點集F所有可能產(chǎn)生的癥候群。在圖2的網(wǎng)絡(luò)結(jié)構(gòu)示例中，有4個頂點相連，其中u,x,y為無故障頂點，v是故障頂點。在PMC模型中，相鄰的頂點都會進行相互測試，從而該網(wǎng)絡(luò)產(chǎn)生測試任務(wù)T={〈u,v〉,〈v,u〉,〈v,x〉,〈x,v〉,〈x,y〉,〈y,x〉}。測試結(jié)果對應(yīng)的癥候群為σ*={{1,0,0,1,0,0},{1,1,0,1,0,0},{1,0,1,1,0,0},{1,1,1,1,0,0}}。

Figure 2 A diagnosis example of PMC model圖2 PMC模型診斷案例

定義2[2]對于任意2個不同的故障頂點集合F1,F2?V，若滿足條件σ*(F1)∩σ*(F2)=?，則F1與F2是可區(qū)分的故障頂點集，(F1,F2)是1對可區(qū)分對；否則(F1,F2)是1對不可區(qū)分對。

定理1[3]對于任意2個不同的頂點集合F1?V和F2?V，F(xiàn)1和F2是可區(qū)分對的充分必要條件是V-(F1∩F2)至少存在1個頂點u與F1ΔF2(頂點集合F1和F2的對稱差)中的1個頂點v相鄰。

定理2[4]任意的圖G=(V(G),E(G))在PMC診斷模型下是t-可診斷的充分必要條件是存在2個不同的故障頂點集合F1?V和F2?V是可區(qū)分的，且滿足|F1|≤t和|F2|≤t。

定理3[13]若n≥2，則κ(Cn)=(n+1)。

定理4[7]若n≥3，則Cn是(n+1)-可診斷的。

3 交錯立方體的診斷度

本節(jié)研究交錯立方體的診斷度的精確值。首先，在引理1和引理2中證明Cn上頂點鄰居集合的下界；接下來在引理3中研究Cn的可區(qū)分對；最后給出定理5和定理6，證明Cn的可診斷性和診斷度的精確值。

根據(jù)Cn的一些基本性質(zhì)，可證明引理1成立。

引理1 給定u和v是Cn中2個不同的頂點，且(u,v)∈E(Cn)，則有|NCn(u)∪NCn(v)|≥2n。

證明 根據(jù)交錯立方體的定義，在Cn中相鄰的頂點最多有2個共同鄰居。設(shè)E′={(u,v)|u=un-1un-2…u2u1u0,v=un-1un-2…u2v1v0},可分為以下2種情形：

情形1 當(dāng)(u,v)?E′時,則|NCn(u)∩NCn(v)|=0。由此可得|NCn(u)∪NCn(v)|=|NCn(u)|+|NCn(v)|-|NCn(u)∩NCn(v)|≥(n+1)+(n+1)-0=2n+2。如圖3a所示。

情形2 當(dāng)(u,v)∈E′時,則|NCn(u)∩NCn(v)|=2。由此可得|NCn(u)∪NCn(v)|=|NCn(u)|+|NCn(v)|-|NCn(u)∩NCn(v)|≥(n+1)+(n+1)-2=2n。如圖3b所示。

Figure 3 Examples of the verticesu,v and their neighbors in Cn圖3 Cn中頂點u和v及其鄰居的示例

根據(jù)上述情況，可得|NCn(u)∪NCn(v)|≥2n，引理1得證。

引理2 給定u，v和x是Cn上3個不同的頂點，且這些頂點滿足如下2個條件：(1) (u,v)∈E(Cn)；(2)(v,x)∈E(Cn)。則有|NCn(u)∪NCn(v)∪NCn(x)|≥3n-2。

證明 根據(jù)交錯立方體的定義，在Cn中相鄰的頂點最多有2個共同鄰居，且距離為2的頂點最多有2個共同鄰居。令E′={(u,v)|u=un-1un-2…u2u1u0,v=un-1un-2…u2v1v0}以及W(u,v,x)= |NCn(u)∪NCn(v)∪NCn(x)|=|NCn(u)|+|NCn(v)|+|NCn(x)|-|NCn(u)∩NCn(v)|-|NCn(u)∩NCn(x)|-|NCn(v)∩NCn(x)|，可分以下5種情形：

情形1 當(dāng)(u,v),(u,x),(v,x)?E′且NCn(u)∩NCn(x)={v}時，則|NCn(u)∩NCn(v)|=|NCn(v)∩NCn(x)|=0且|NCn(u)∩NCn(x)|=1。那么W(u,v,x)≥3(n+1)-0-0-1=3n+2。

情形2 當(dāng)(u,v)∈E′且(u,x),(v,x)?E′，則|NCn(u)∩NCn(v)|=2×|NCn(v)∩NCn(x)|=0且|NCn(u)∩NCn(x)|=1。那么W(u,v,x)≥3(n+1)-0-2-1=3n。

情形3 當(dāng)(x,v)∈E′且(u,v),(u,x)?E′，與情形2類似，有W(u,v,x)≥3n。

情形4 當(dāng)(u,v),(u,x),(v,x)?E′且|NCn(u)∩NCn(x)|={v,y}時，則|NCn(u)∩NCn(v)|=|NCn(v)∩NCn(x)|=0且|NCn(u)∩NCn(x)|=2。那么W(u,v,x)≥3(n+1)-0-0-2=3n+1。

情形5 當(dāng)(u,v),(u,x),(v,x)∈E′時，與情形4類似，有W(u,v,x)≥3n。

綜上所述，可得|NCn(u)∪NCn(v)∪NCn(x)|≥3n-2，引理2得證。

引理3 若n≥4，假設(shè)Cn中存在1個由1條故障邊和多個故障頂點組成的集合S且|S|≤n，令F1和F2表示Cn中2個不同的故障頂點集合，且滿足條件F1≤δ(Cn-S)和F2≤δ(Cn-S)，則當(dāng)F1-F2中有頂點u,在F2-F1中有頂點v，且(u,v)∈E(Cn)時，F(xiàn)1和F2是1對可區(qū)分對。

證明 使用S表示Cn中由1條故障邊和多個故障頂點組成的集合S且|S|≤n，即S是V(Cn)∪E(Cn)的1個子集。由定理4可知，當(dāng)|S|=0時，F(xiàn)1和F2是1對可區(qū)分對。

因此，僅需考慮當(dāng)|S|≥1時的情形。因為(u,v)∈E(Cn)，由定義1，有|NCn(u)∩NCn(v)|≤2。因為|F1|≤δ(Cn-S)和|F2|≤δ(Cn-S)，可以得到|F1|+|F2|≤2δ(Cn-S)。根據(jù)定義1和定理3，可以得到δ(Cn-S)<δ(Cn)=n+1。

假設(shè)F1和F2是1對不可區(qū)分對，則對于在F1ΔF2=(F1-F2)∪(F2-F1)中的任意頂點x，都有NCn-S(x)?F1∪F2。此時，將分為以下2種情形討論：

情形1 當(dāng)(u,v)∈S時，可得|F1|+|F2|≥|NCn-S(u)∪NCn-S(v)∪{u,v}|=|NCn-S(u)|+|NCn-S(v)|+|{u,v}|≥2δ(Cn-S)+2。這與條件|F1|+|F2|≤2δ(Cn-S)矛盾，故該情況不成立。如圖4a所示。

情形2 當(dāng)(u,v)?S時，此時(u,v)∈E(Cn)，由定義1，有|NCn(u)∩NCn(v)|≤2。進而可以得到|NCn-S(u)∪NCn-S(v)-{u,v}|=degCn-S(u)+degCn-S(v)-2≥2n-|S|。如圖4b所示。由于F1≤δ(Cn-S)，F(xiàn)2≤δ(Cn-S)且頂點u和v在F1ΔF2中，故可得|F1∩F2|≤δ(Cn-S)-1。進一步可以得到|NCn-S(u)∪NCn-S(v)-{u,v}|-|F1∩F2|≥2n-|S|-(δ(Cn-S)-1)≥1>0。

由此可以得出下列情形，即(NCn-S(u)∪NCn-S(v))-({u,v}∪(F1∩F2))中至少存在1個頂點x。根據(jù)先前假設(shè)，F(xiàn)1和F2是1對不可區(qū)分對，則對于任意頂點x∈F1ΔF2=(F1-F2)∪(F2-F1)，都滿足NCn-S(x)?F1∪F2。根據(jù)引理2，可以得出|F1|+|F2|≥|NCn-S(u)∪NCn-S(v)∪NCn-S(x)|≥|NCn(u)∪NCn(v)∪NCn(x)|-|S|≥(3n-2)-|S|。然而這與先前條件|F1|+|F2|≤2δ(Cn-S)矛盾，因此該情況不成立。

Figure 4 Distribution of vertices u,vand their neighbors in Cn圖4 Cn中頂點u和v及其鄰居的分布情況

綜上所述，若F1-F2中存在頂點u，在F2-F1中存在頂點v，且滿足(u,v)∈E(Cn)時，F(xiàn)1和F2是1對可區(qū)分對。

定理5 給定Cn上存在由1條故障邊和多個故障頂點組成的集合S且|S|≤n，則當(dāng)n≥4時，Cn-S是δ(Cn-S)-可診斷的。

證明 假設(shè)在Cn-S中存在滿足條件max{|F1|,|F2|}≤δ(Cn-S)的1對不可區(qū)分對F1和F2。由于F1和F2是一對不可區(qū)分對，則對于在F1ΔF2=(F1-F2)∪(F2-F1)上的任意頂點u，都有NCn-S(u)?F1∪F2。

由于F1≠F2，那么在F1-F2中至少存在1個頂點，假設(shè)該頂點為v。因為F1≤δ(Cn-S)，degCn-S(x)≥δ(Cn-S)，NCn-S(x)?F1∪F2，且v∈F1-F2。所以，至少存在1個頂點x分布于(NCn-S(v)∩F2)-F1中。根據(jù)引理3可知，F(xiàn)1和F2是1對可區(qū)分對，這與假設(shè)矛盾，由定理2可知，當(dāng)n≥4時，Cn-S是δ(Cn-S)-可診斷的，故定理得證。

定理6 給定Cn上存在由1條故障邊和多個故障頂點組成的集合S且|S|≤n，則當(dāng)n≥4時，Cn-S的診斷度是δ(Cn-S)。

證明 根據(jù)定理5可知，當(dāng)n≥4時，Cn-S是δ(Cn-S)-可診斷的。因此，僅需證明Cn-S中存在1對不同的故障頂點集合F1和F2，使得F1和F2是1對不可區(qū)分對，其中F1≤δ(Cn-S)+1且F2≤δ(Cn-S)+1。

假設(shè)Cn-S中存在頂點u滿足條件degCn-S(u)=δ(Cn-S)。令F1=NCn-S(u)∪{u}且F2=NCn-S(u)，則可以驗證|F1|=δ(Cn-S)+1和|F2|=δ(Cn-S)，根據(jù)定理1可知，F(xiàn)1和F2是1對不可區(qū)分對。

綜上所述，當(dāng)n≥4時，Cn-S的診斷度是δ(Cn-S)。

4 交錯立方體上的故障診斷算法

定理6證明了n維交錯立方體在故障情形下的診斷度。根據(jù)引理3和定理5研究思路，本節(jié)提出一種在該情形下基于PMC模型的時間復(fù)雜度為O(Nlog2N)的快速診斷算法CDiag，其中N表示Cn的頂點總數(shù)。

在算法CDiag中，分別用M和F表示1個無故障集合和故障集合，PMC(u,v)表示頂點u對頂點v的測試結(jié)果。具體算法如下所示：

算法:CDiag

輸入:當(dāng)n≥4時，n維交錯立方體Cn上存在由1條故障邊和多個故障頂點組成的集合S且|S|≤n。

輸出:診斷出的故障頂點集合F。

步驟1 令F←?,M←?,G←Cn-S,k←δ(G)；

步驟2 令u←FindFFNode(G,k)；

步驟3 returnDiagMain(G,u,M,F,k)；

functionFindFFNode(G,δ)

步驟1 for (u,v)∈E(G) then

步驟2 ifPMC(u,v)=0andPMC(v,u)=0 then

步驟3 令k←1；

步驟4 forx∈(NG(u){v})then

步驟5 ifPMC(u,x)=0 andPMC(x,u)=0 then

步驟6 令k←k+1；

步驟7 fory∈(NG(v)u}) then

步驟8 ifPMC(v,y)=0 andPMC(y,v)=0 then

步驟9 令k←k+1；

步驟10 ifk>δthen

步驟11 returnu；

end function

functionDiagMain(G,u,M,F,δ)

步驟1 forv∈NG(u) then

步驟2 ifv∈(M∪F) then

步驟3 if |M∪F|=|V(G)|or |F|=δthen

步驟4 returnF；

步驟5 else

步驟6 ifPMC(u,v)=0 then

步驟7 令M←M∪{u,v}；

步驟8 if |M∪F|=|V(G)| or |F|=δthen

步驟9 returnF；

步驟10 else

步驟11 returnDiagMain(G,v,M,F,δ)；

步驟12 else

步驟13 令M←M∪{u}，F(xiàn)←F∪{v}；

步驟14 if |M∪F|=|V(G)| or |F|=δthen

步驟15 returnF；

步驟16 if |M∪F|=|V(G)| or |F|=δthen

步驟17 returnF；

end function

算法分析：當(dāng)n≥4時，給定1個n維交錯立方體Cn和滿足一定條件的故障集合S。算法CDiag能夠在Cn-S(用G表示)上診斷出δ(G)個故障頂點。算法CDiag首先調(diào)用函數(shù)FindFFNode找出1個無故障頂點u，然后調(diào)用函數(shù)DiagMain遍歷網(wǎng)絡(luò)G的頂點，通過對整個網(wǎng)絡(luò)G的頂點進行分類，將識別出的故障頂點放入故障頂點集合F中，無故障頂點放入無故障頂點集合M中，最終精確診斷出G上的δ(G)個故障頂點，算法的流程圖如圖5所示。

Figure 5 Flow chart of CDiag algorithm圖5 算法CDiag的流程圖

舉例說明：當(dāng)n=4時，C4上存在由1條故障邊(1111,1100)和3個故障頂點{1101,1000,0000}組成的集合S。經(jīng)過算法CDiag步驟1，G是由頂點集合{0110,0111,0001,0011,0010,0101,0100,1111,1110,1100,1010,1011,1001}和邊集合{(0110,1110),(0110,0111),(0110,0101),(0110,0100),(0110,0010),(0111,0101),0111,0001),(0111,0100),(0001,1011),(0001,0011),0001,0010),(0011,0101),(0011,1001),(0011,0010),(0010,1010),(0101,1111),(0101,0100),(0100,1100),(1111,1110),(1111,1001),(1110,1010),(1110,1100),(1010,1011),(1010,1001),(1011,1001)}構(gòu)成的圖，且k=2；經(jīng)過算法CDiag步驟2，找出1個無故障頂點0110；經(jīng)過算法CDiag步驟3，最終找出故障頂點集合{1101,1000,0000}。

下面分析該算法的時間復(fù)雜度。本節(jié)使用鄰接表存儲圖G，使用N表示Cn的頂點總數(shù)，顯然N=2n。根據(jù)定義1，可在O(Nlog2N)內(nèi)計算出δ(G)和E(G)，在O(N)內(nèi)計算出V(G)，在O(n) 內(nèi)計算出NG(u)，這些值可在程序調(diào)用前預(yù)先計算出來，而算法CDiag可在常數(shù)時間內(nèi)調(diào)用這些數(shù)值。另外，根據(jù)PMC模型的定義，可在常數(shù)時間內(nèi)計算出PMC(u,v)。函數(shù)FindFFNode中步驟1需要O(n)，步驟2～步驟3需要O(1)，步驟4～步驟11需要O(n)。因此，函數(shù)FindFFNode的時間復(fù)雜度為O(n2)。函數(shù)DiagMain采用廣度優(yōu)先搜索方法診斷故障頂點，其最壞情形下，時間復(fù)雜度為O(2n+n2n)=O(Nlog2N)。綜上所述，算法CDiag的時間復(fù)雜度為O(Nlog2N)。

5 模擬實驗及結(jié)果分析

本節(jié)將本文設(shè)計的診斷算法CDiag與Sengupta-Dahbura提出的診斷算法FDiag(其時間復(fù)雜度為O(N5))、張麗果等[9]提出的診斷算法DDiag(其時間復(fù)雜度為O(N2))進行比較，文獻[9]設(shè)計的診斷算法DDiag在故障點數(shù)量較小時具有較高的可靠性。本文對上述算法用Python語言編程實現(xiàn)，用1臺配置為Intel Core(TM) i5-7Y54 CPU 1.20 1.61 GHz，8 GB內(nèi)存的計算機來評估算法的性能，并分析實驗結(jié)果。實驗中邊故障和頂點故障都是隨機生成的。

實驗1 給定1個12維的交錯立方體C12(共4 096個頂點)在故障情形(由1條故障邊和多個故障頂點組成的故障集合S)下，利用算法CDiag診斷出δ(C12-S)個故障頂點所花費的CPU時間。算法CDiag重復(fù)運行100次的最壞和平均情況分別如圖6a和圖6b所示。

Figure 6 CPU time of fault diagnosis圖6 故障診斷花費的CPU時間

根據(jù)實驗結(jié)果可以看出，對C12-S進行故障診斷消耗的CPU時間與其網(wǎng)絡(luò)上頂點數(shù)量相關(guān)，與S中元素數(shù)目的關(guān)聯(lián)性不大。對比使用文獻[9]中算法DDiag的實驗結(jié)果，平均CPU時間900～1 000 ms，最壞CPU時間為1 100～1 300 ms。對比使用文獻[11]中算法FDiag的實驗結(jié)果，平均CPU時間為1 100～1 200 ms，最壞CPU時間為1 300～1 500 ms。由實驗數(shù)據(jù)可以看到，本文算法的執(zhí)行效率優(yōu)于文獻[9]和文獻[11]中算法的。

實驗2 給定1個10維的交錯立方體C10(共1 024個頂點)。利用算法CDiag基于PMC模型計算C12中診斷出k個故障頂點的成功率，其中k∈{0,50,100,150,200,250,300,350,400,450,500}。進一步，將算法CDiag重復(fù)運行100次的成功率與文獻[9]中算法DDiag和文獻[11]中算法FDiag的實驗結(jié)果相比較，如圖7所示。

根據(jù)算法CDiag的實驗結(jié)果，隨著數(shù)值k的不斷增加，10維的交錯立方體C10診斷出k個故障頂點的成功率在k≥300時逐步降低，隨著故障頂點數(shù)量增加，C10上存在多個連通分支幾率逐漸增大，故成功率逐步降低。對比使用文獻[9]中算法DDiag的實驗結(jié)果，當(dāng)k≥50時成功率逐步降低,并且下降速度快于算法CDiag的。對比使用文獻[11]中算法FDiag的實驗結(jié)果，當(dāng)k≥50時成功率逐步降低,并且下降速度與算法CDiag接近。由實驗數(shù)據(jù)可以看到，本文算法的穩(wěn)定性優(yōu)于文獻[9]中算法，并且與文獻[11]中算法接近。

Figure 7 Success rate of fault diagnosis圖7 故障診斷的成功率

綜上所述，本文提出的診斷算法CDiag與Sengupta-Dahbura提出的診斷算法(其時間復(fù)雜度為O(N5)[11])和張麗果等提出的診斷算法 (其時間復(fù)雜度為O(N2)[9])相比，在高效性方面較優(yōu)。進一步，其穩(wěn)定性方面優(yōu)于文獻[9]中算法，并與文獻[11]中算法接近。

6 結(jié)束語

診斷度和診斷算法是互連網(wǎng)絡(luò)中可靠性研究的重要課題，而基于PMC模型的診斷方法是互連網(wǎng)絡(luò)的一種常用的系統(tǒng)診斷方法。本文首先證明了基于n維交錯立方體在出現(xiàn)故障邊和故障頂點的情況下的診斷度，然后提出了該故障情形下的快速診斷算法，并基于該算法進行了相應(yīng)的仿真實驗。實驗結(jié)果顯示，在多種故障參數(shù)下本文所提算法的性能優(yōu)于對比算法。近年來，研究者們對互連網(wǎng)絡(luò)的診斷度和診斷算法做了大量的研究，并且延伸到無線傳感網(wǎng)絡(luò)、P2P網(wǎng)絡(luò)等方向。因此，這些網(wǎng)絡(luò)出現(xiàn)類似故障情形時，其系統(tǒng)的診斷度和診斷算法還有待于進一步的研究。