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

王 喜，張書奎

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

1 引言

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

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

Preparata等[2]在給出系統(tǒng)級(jí)故障診斷概念的同時(shí)提出了一個(gè)經(jīng)典診斷模型——PMC診斷模型，該模型是用3位作者姓名的首字母來命名的。基于該診斷模型的研究已經(jīng)在大規(guī)模多處理器系統(tǒng)、無線傳感器網(wǎng)絡(luò)系統(tǒng)、片上網(wǎng)絡(luò)設(shè)計(jì)等領(lǐng)域廣泛應(yīng)用[3]。PMC診斷模型使用測(cè)試頂點(diǎn)測(cè)試其它頂點(diǎn)，且通過測(cè)試結(jié)果來判斷頂點(diǎn)狀態(tài)，然而，如果測(cè)試頂點(diǎn)本身是有故障的，那么測(cè)試的結(jié)果將是不準(zhǔn)確的。Chang等[3]研究了判斷一個(gè)網(wǎng)絡(luò)是否適用 PMC診斷模型的方法。 Hakimi等[4]證明了一個(gè)系統(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模型下超立方體的一種時(shí)間復(fù)雜度為O(N2)的條件診斷算法。

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

2 預(yù)備知識(shí)

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

Figure 1 A 4-dimensional cross-cube C4圖1 1個(gè)4維交錯(cuò)立方體C4

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

Table 1 PMC model表1 PMC診斷模型

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

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

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

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

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

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

3 交錯(cuò)立方體的診斷度

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

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

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

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

情形1 當(dāng)(u,v)?E′時(shí),則|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′時(shí),則|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中頂點(diǎn)u和v及其鄰居的示例

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

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

證明 根據(jù)交錯(cuò)立方體的定義，在Cn中相鄰的頂點(diǎn)最多有2個(gè)共同鄰居，且距離為2的頂點(diǎn)最多有2個(gè)共同鄰居。令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}時(shí)，則|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}時(shí)，則|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′時(shí)，與情形4類似，有W(u,v,x)≥3n。

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

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

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

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

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

情形1 當(dāng)(u,v)∈S時(shí)，可得|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時(shí)，此時(shí)(u,v)∈E(Cn)，由定義1，有|NCn(u)∩NCn(v)|≤2。進(jìn)而可以得到|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)且頂點(diǎn)u和v在F1ΔF2中，故可得|F1∩F2|≤δ(Cn-S)-1。進(jìn)一步可以得到|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個(gè)頂點(diǎn)x。根據(jù)先前假設(shè)，F(xiàn)1和F2是1對(duì)不可區(qū)分對(duì)，則對(duì)于任意頂點(diǎn)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中頂點(diǎn)u和v及其鄰居的分布情況

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

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

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

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

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

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

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

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

4 交錯(cuò)立方體上的故障診斷算法

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

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

算法:CDiag

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

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

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

舉例說明：當(dāng)n=4時(shí)，C4上存在由1條故障邊(1111,1100)和3個(gè)故障頂點(diǎn){1101,1000,0000}組成的集合S。經(jīng)過算法CDiag步驟1，G是由頂點(diǎn)集合{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個(gè)無故障頂點(diǎn)0110；經(jīng)過算法CDiag步驟3，最終找出故障頂點(diǎn)集合{1101,1000,0000}。

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

5 模擬實(shí)驗(yàn)及結(jié)果分析

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

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

Figure 6 CPU time of fault diagnosis圖6 故障診斷花費(fèi)的CPU時(shí)間

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

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

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

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

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

6 結(jié)束語(yǔ)

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