劉西蒙，張郁芳，周書明，李小燕

（1.福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 福州 350108；2.福州大學(xué)網(wǎng)絡(luò)安全福建省高校重點(diǎn)實(shí)驗(yàn)室，福建 福州 350108；3.福建師范大學(xué)數(shù)學(xué)與信息學(xué)院，福建 福州 350007）

1 引言

隨著多處理器系統(tǒng)規(guī)模不斷擴(kuò)大，處理器發(fā)生故障的情形不可避免。為了確保系統(tǒng)的穩(wěn)定運(yùn)行，需要對處理器進(jìn)行測試和診斷，從而修復(fù)或更換有故障的處理器，以提高系統(tǒng)的可靠性。

故障診斷是評估系統(tǒng)可靠性和可用性的關(guān)鍵研究。系統(tǒng)中識別故障處理器的過程稱為系統(tǒng)級診斷[1]。最早的系統(tǒng)級診斷模型由Preparata、Metze和Chien[1]提出，稱為PMC 模型。PMC 模型通過相鄰2 個(gè)處理器互相測試來進(jìn)行診斷。Maeng 和Malek[2]提出了基于比較的MM 模型，該模型是通過一個(gè)處理器把任務(wù)發(fā)送到與它相鄰的2 個(gè)處理器，然后比較它們的測試結(jié)果來進(jìn)行診斷。隨后，Sengupta 等[3]提出了MM*模型，該模型是MM 模型的一種特殊情況，在該模型下，每個(gè)處理器均對與它有直接物理相連的任意2 個(gè)不同處理器的測試結(jié)果進(jìn)行比較。在系統(tǒng)級診斷中，如果系統(tǒng)可以檢測出不超過t個(gè)故障處理器，則稱該系統(tǒng)為t-可診斷的。在t-診斷系統(tǒng)中可以實(shí)現(xiàn)的t的最大值稱為診斷度[1]。由于系統(tǒng)的最小度的限制，傳統(tǒng)的診斷度很小。為進(jìn)一步提高系統(tǒng)的診斷能力，Zhang 等[4]提出了一種新的度量方法，稱為h-額外條件診斷度，并研究了超立方網(wǎng)絡(luò)的h-額外條件診斷度。圖G的h-額外條件診斷度（用(G)表示）是指在滿足G中每個(gè)無故障分支至少包含h+1個(gè)頂點(diǎn)的條件下，G可以保證識別的最大故障頂點(diǎn)數(shù)目。Lin 等[5]研究了一些正則網(wǎng)絡(luò)在PMC 模型下的h-額外條件診斷度（h=1 或2）。Huang 等[6]分析了交錯(cuò)群圖在PMC 模型下的h-額外條件診斷度。Liu 等[7]研究了分層立方網(wǎng)絡(luò)在PMC 模型和MM*模型下的h-額外條件診斷度。LYU 等[8]確定了一般正則網(wǎng)絡(luò)在PMC模型和MM*模型下的h-額外條件診斷度（h=1或2）。Sun 等[9]研究了完全立方網(wǎng)絡(luò)在PMC 模型和MM*模型下的h-額外條件診斷度。

t/s-診斷策略（即系統(tǒng)最多可以識別出t個(gè)故障頂點(diǎn)，其中至多s個(gè)無故障頂點(diǎn)被誤診為故障頂點(diǎn)）是一種十分高效的系統(tǒng)級診斷策略。Somani 等[10]基于t/s-診斷策略提出了t/s-診斷度，并研究了超立方網(wǎng)絡(luò)和星形網(wǎng)絡(luò)在PMC 模型下的t/s-診斷度；Fan 等[11]研究了雙射連接網(wǎng)絡(luò)的t/s-診斷度；Yang等[12]提出了立方網(wǎng)絡(luò)的(4m-h)/3-診斷算法；Zhou等[13]給出了星形網(wǎng)絡(luò)的t/s-診斷度；Lin 等[14]討論了符合某些條件的正則網(wǎng)絡(luò)的t/s-診斷度，并提出了一種t/s-診斷算法；Liang 等[15]研究了關(guān)于超立方網(wǎng)絡(luò)在PMC 和MM*模型下的t/s-診斷度和t/s-診斷算法。此外，Xie 等[16]提出了關(guān)于超立方類網(wǎng)絡(luò)的時(shí)間復(fù)雜度較低的t/s-診斷算法；Li 等[17]研究了數(shù)據(jù)中心網(wǎng)絡(luò)DCell 在PMC 和MM*模型下的t/s-診斷度。然而，大多數(shù)網(wǎng)絡(luò)在MM*模型下的t/s-診斷度和t/s-診斷算法尚未得到研究。

Malluhi 等[18]提出了一種新的互連拓?fù)洌Q為分層超立方網(wǎng)絡(luò)，其拓?fù)浣Y(jié)構(gòu)適用于大規(guī)模并行系統(tǒng)，且通信效率較高。目前，關(guān)于分層超立方網(wǎng)絡(luò)可靠性問題的研究較少，嚴(yán)重制約了分層超立方網(wǎng)絡(luò)的應(yīng)用和推廣，基于此，本文對n維分層超立方（HHCn,n-dimension hierarchical hypercube）網(wǎng)絡(luò)（后文簡稱HHCn）在PMC 模型和MM*模型下的h-額外條件診斷度和t/s-診斷度展開研究，設(shè)計(jì)了相應(yīng)的t/s-診斷算法，并分析其時(shí)間復(fù)雜度。

2 準(zhǔn)備工作

2.1 術(shù)語與符號

對于以下未定義的圖論和網(wǎng)絡(luò)術(shù)語，可以參考文獻(xiàn)[19]。網(wǎng)絡(luò)可以拓?fù)錇閳DG=G(V,E)，其中每個(gè)頂點(diǎn)u∈V表示一個(gè)處理器，每條邊(u,v)∈E表示處理器u和v之間的連接。在圖G中，頂點(diǎn)v的鄰集N G(v)表示在圖G中與v相鄰的任意頂點(diǎn)u的集合，即NG(v)={u∈V|(u,v)∈E}。類似地，子集S?V的鄰集N G(S)表示與S中的某些頂點(diǎn)相鄰但是不包含S本身的頂點(diǎn)的集合。由S導(dǎo)出的G的子圖用G[S]表示，其頂點(diǎn)集為S，邊集為{(u,v)|(u,v)∈E,u,v∈S}。根據(jù)鄰域和子集鄰集的定義可知，N G[S]=N G(S)∪S。當(dāng)G在上下文中語義明確時(shí)，為方便起見，將省略下標(biāo)G。頂點(diǎn)u在G中的度定義為d(u)=|N G(u)|。集合M和N的對稱差集表示為

對于任意子集F?V(G)，符號G-F表示從圖G中刪除F中所有頂點(diǎn)，并刪除至少有一個(gè)末端頂點(diǎn)在F中的邊所得到的圖。G-F的每個(gè)極大連通子圖稱為圖G的一個(gè)連通分支，如果G-F是不連通的，則稱F為點(diǎn)割集。G1?G2表示G1與G2同構(gòu)。mc(G) 表示圖G的最大連通分支的頂點(diǎn)數(shù)目。表示{1,2,3,…,n}。圖G的h-額外連通度是指使G-F不連通，并且剩余的每個(gè)連通分支的頂點(diǎn)數(shù)目不小于h+1的集合F的最小基數(shù)，用κh(G)表示。D表示PMC模型或MM*模型，(G,D)表示圖G在PMC 模型或MM*模型下的h-額外條件診斷度。在本文中，“圖”“網(wǎng)絡(luò)”“系統(tǒng)”含義相同。

2.2 PMC 模型和MM＊模型

在PMC 模型中，對于系統(tǒng)G=G(V,E)中任意2 個(gè)相鄰頂點(diǎn)u和v，當(dāng)且僅當(dāng)u測試v時(shí)，(u,v)∈E。G(V,E)中的測試結(jié)果集用函數(shù)σ:E→{0,1}表示，σ稱為系統(tǒng)癥候。用u測試v的結(jié)果表示為σ(u,v)。當(dāng)u無故障時(shí)，如果v也無故障，則σ(u,v)=0；否則，σ(u,v)=1。如果u有故障，則σ(u,v)的值是不可靠的。

在MM*模型中，系統(tǒng)G=G(V,E)的比較方案可以刻畫為一個(gè)多重圖M(V,L)，其中V和L分別為G的頂點(diǎn)集和邊集。若2 個(gè)頂點(diǎn)u和v都與頂點(diǎn)w相鄰，則u與v可以通過w進(jìn)行比較，即(u,v)w∈L。σ(u,v)w表示頂點(diǎn)w對2 個(gè)頂點(diǎn)u和v執(zhí)行比較的結(jié)果。符號σ稱為系統(tǒng)癥候，定義為圖G中所有比較結(jié)果的集合。當(dāng)w無故障時(shí)，如果u和v都沒有故障，則σ(u,v)w=0；否則，σ(u,v)w=1。如果w有故障，則σ(u,v)w的值可能為1 或0。在MM*模型中，如果(u,w),(v,w)∈E，則(u,v)w∈L。

引理1[20]對于系統(tǒng)G=(V,E)中的任意2 個(gè)不同故障子集F1和F2，當(dāng)且僅當(dāng)存在一個(gè)頂點(diǎn)u∈V-(F1∪F2)和一個(gè)頂點(diǎn)v∈F1ΔF2使(u,v)∈E時(shí)，F(xiàn)1和F2在PMC 模型下才是可區(qū)分的。

引理2[3]對于系統(tǒng)G=(V,E)中的任意2 個(gè)不同的故障子集F1和F2，當(dāng)且僅當(dāng)滿足以下條件之一時(shí)，F(xiàn)1和F2在MM*模型下才是可區(qū)分的。

1) 有2 個(gè)頂點(diǎn)u,w∈V-(F1∪F2)，并且有一個(gè)頂點(diǎn)v∈F1ΔF2使(u,w)∈E和(v,w)∈E。

2) 有2 個(gè)頂點(diǎn)u,v∈F1-F2，并且有一個(gè)頂點(diǎn)w∈V-(F1∪F2)使(u,w)∈E和(v,w)∈E。

3) 有2 個(gè)頂點(diǎn)u,v∈F2-F1，并且有一個(gè)頂點(diǎn)w∈V-(F1∪F2)使(u,w)∈E和(v,w)∈E。

2.3 分層超立方網(wǎng)絡(luò)

Malluhi 等[18]提出了分層超立方網(wǎng)絡(luò)，它將n維帶環(huán)立方網(wǎng)絡(luò)[21]中的環(huán)用超立方網(wǎng)絡(luò)替代。下面介紹分層超立方網(wǎng)絡(luò)的定義和性質(zhì)。

定義1[18]n維分層超立方網(wǎng)絡(luò)HHCn用圖來定義，其中頂點(diǎn)集為{(X,Y)|X=an-1an-2…a m,Y=am-1am-2…a0}，ai∈{0,1}，0≤i≤n-1，n=2m+m且m≥ 1。HHCn的頂點(diǎn)連接規(guī)則如下。

1) (A,Bl)對于所有0≤l≤m-1。

2) (Am+dec(B),B)，其中dec(B)是B的十進(jìn)制值。

HHCn是由2n個(gè)頂點(diǎn)組成的(m+1)-正則二部圖，每個(gè)頂點(diǎn)的度數(shù)為m+1，其中n=2m+m。HHCn由 22m簇組成，每個(gè)簇與m維超立方網(wǎng)絡(luò)Qm同構(gòu)。每個(gè)簇用Ci表示，i∈<22m＞。Q2m結(jié)構(gòu)與HHCn結(jié)構(gòu)如圖1 所示（其中，m=2，n=6）。

圖1 Q 22結(jié)構(gòu)與HHC6結(jié)構(gòu)

情況2X中的頂點(diǎn)至少分布在2 個(gè)不同的簇中，如圖2 所示。

圖2 引理7 情況2 示意

3 分層超立方網(wǎng)絡(luò)的h-額外條件診斷度

本節(jié)將對分層超立方網(wǎng)絡(luò)在2 個(gè)不同的模型下的h-額外條件診斷度進(jìn)行研究。

定義2[4]在圖G=G(V,E)中，當(dāng)G-F是不連通的且G-F的每個(gè)分支至少含有h-1 個(gè)頂點(diǎn)時(shí)，稱故障集F為h-額外故障集。

定義3[4]對于圖G=G(V,E)中任意一對不同的h-額外故障子集F1,F2?V滿足|F1|≤t和|F2|≤t，且F1,F2是可區(qū)分的，則稱圖G是h-額外條件t-可診斷的，使圖G是h-額外條件t-可診斷的t的最大值，稱為圖G的h-額外條件診斷度，記作～t h(G)。

圖3 引理10 示意

證明記P是HHCn中一個(gè)簇C1的一個(gè)頂點(diǎn)子集，其中HHCn[P]?K1,h，F(xiàn)1=N(P)且F2=F1∪P。設(shè)S=N(P) ∩(HHCn-C1)，通過引理5 和HHCn的性質(zhì)可得

因此，根據(jù)引理4 和引理9 可知引理11 成立。證畢。

根據(jù)引理10 和引理11，可以得出定理1。

圖4 引理12 示意

聲明1J不包含孤立的頂點(diǎn)。

假設(shè)I(≠?)是J中的一組孤立頂點(diǎn)集。顯然，對于任意i∈I有I≤2n-1，N(i)?F1∪F2。此外，|F1F2|≥ 1，|F2F1|≥ 1。否則，如果F2F1=?（或者F1F2=?），則F1?F2。也就是說N(i)?F2，則i是HHCn-F2中的一個(gè)孤立頂點(diǎn)，這與h≥ 1的條件相矛盾。另一方面，如果在F1F2中存在2 個(gè)頂點(diǎn)u和v使(u,i),(v,i)∈E，則(F1,F2)是可區(qū)分的，這與假設(shè)相矛盾。如果不存在頂點(diǎn)u∈F1F2使(u,i)∈E，則HHCn-F2中的i是一個(gè)孤立頂點(diǎn)，這與h≥ 1的條件相矛盾。因此，N(i) ∩(F1F2)=1。同樣地，N(i) ∩(F2F1)=1。因此，有

所以，|F1∩F2|≥ |N(i) ∩(F1∩F2)|=m-1。

令A(yù)=JI，接下來證明A≠?。利用反證法，假設(shè)A=?，可得

這是矛盾的，證畢。

根據(jù)引理10 和引理12，可以得出定理2。

4 分層超立方網(wǎng)絡(luò)的t/s-診斷度

本節(jié)將研究HHCn在PMC模型下以及MM* 模型下的t/s-診斷度（m≥5，n=2m+m，1≤s≤m-1）。此外，還將設(shè)計(jì)相應(yīng)的t/s-診斷算法。

定義4[10]給定一個(gè)系統(tǒng)G，當(dāng)系統(tǒng)中的故障頂點(diǎn)數(shù)目不超過t時(shí)，若對于任意癥候σ，系統(tǒng)可以將所有故障頂點(diǎn)都分離在一個(gè)故障集合F′中，且F′包含至多s個(gè)無故障頂點(diǎn)，即F′≤|F|+s，則稱這個(gè)系統(tǒng)是t/s-可診斷的。滿足系統(tǒng)是t/s-可診斷的最大的t值稱為t/s-診斷度。

定義5[12]給定系統(tǒng)G=(V,E)和在G中由故障集產(chǎn)生的癥候σ。若T0(G)是G的0-測試子圖，則需滿足T0(G)是G的一個(gè)子圖，同時(shí)V(T0(G))?V且E(T0(G))={(u,v)∈E,σ(u,v)=σ(v,u)=0}。

引理13[12]在PMC 模型下給定一個(gè)系統(tǒng)G=(V,E)以及在G中由故障集產(chǎn)生的癥候σ，有如下結(jié)論。

1) 令u,v是G中的 2 個(gè)相鄰頂點(diǎn)。如果σ(u,v)=σ(v,u)=0，則要么頂點(diǎn)u和v均無故障，要么頂點(diǎn)u和v均存在故障。

2) 令C為T0(G)的分支，則C中的所有頂點(diǎn)要么都是故障的，要么都是無故障的。

定義6[17]給定系統(tǒng)G=(V,E)及在G中由故障集產(chǎn)生的癥候σ。令x?V，頂點(diǎn)x的0-比較子集表示為C0(x)={c∈V|?a∈V,σ(x,a)c=0}。G的0-比較子圖記為T′(G)，表示為G的一個(gè)子圖，其中，V(T′(G))?V且E(T′(G))={(x,c)∈E|c∈C0(x),x∈C0(c)}，如圖5 所示。

圖5 G 的0-比較子圖 T ′(G)的說明

引理14[17]給定一個(gè)至多包含t個(gè)故障頂點(diǎn)的系統(tǒng)G=(V,E)，以及在G中基于MM*模型由故障集產(chǎn)生的癥候σ，有如下結(jié)論。

1) 如果對于任意2 個(gè)頂點(diǎn)x,y∈V且(x,y)∈E使y∈C0(x)和x∈C0(y)，則x和y具有相同的狀態(tài)（即同為故障或無故障）。

2) 對于連通分支R?T′(G)，R中的所有頂點(diǎn)要么都是故障的，要么都是無故障的。

3) 如果T′(G)的連通分支R滿足|V(R)|≥t+1，則R中的所有頂點(diǎn)都是無故障的。

根據(jù)引理13中結(jié)論2)和引理14中結(jié)論2)可知，C中的所有頂點(diǎn)均為無故障，因此引理15 成立。證畢。

證明設(shè)F是HHCn的故障集，F(xiàn)′是所有故障頂點(diǎn)和可疑頂點(diǎn)的集合，C為T0(HHCn)或T′(HHCn)的最大連通分支。通過考慮F的大小進(jìn)行證明。

根據(jù)引理15 可得

F′中最多包含s個(gè)無故障頂點(diǎn)。因此，在此情況下，定理3 成立。

輸出故障頂點(diǎn)集F′和無故障頂點(diǎn)集Y，其中F′∪Y=V(HHCn)

1) 初始化F′=?，Y=?，U=V(HHCn)，其中，?表示空集。

2) 檢查HHCn中所有的測試結(jié)果。?表示2個(gè)頂點(diǎn)u和v在PMC 模型下相互測試。刪除測試結(jié)果是1 ? 0、0 ? 1、1 ? 1的邊，并將0 ? 0的邊添加到E′中。令T0(HHCn)為E′的導(dǎo)出子圖。

3) 獲得無故障頂點(diǎn)的集合C。通過廣度優(yōu)先搜索在T0(HHCn)中獲得最大連通分支C，并將C中的所有頂點(diǎn)添加到Y(jié)中。令U=U-Y。

4) 對于前面步驟中每個(gè)未診斷的頂點(diǎn)v，如果它的相鄰頂點(diǎn)u∈C且σ(u,v)=1，則將v添加到F′中。令U=U-F′。

根據(jù)定理3 中情況2 可知，如果可疑頂點(diǎn)的數(shù)目超過s+1 個(gè)，則所有的可疑頂點(diǎn)都是無故障的。如果可疑頂點(diǎn)的數(shù)目少于s個(gè)，那么定理4 顯然成立。

這意味著F′最多包含s個(gè)無故障頂點(diǎn)。因此，定理4 成立。證畢。

定理5當(dāng)m≥ 5，n=2m+m，且1≤s≤m-1時(shí)，算法t/s-HHCn-DIAG-PMC 的時(shí)間復(fù)雜度為O(NlogN)，其中N=|V(HHCn)|。

證明算法t/s-HHCn-DIA G-PMC 主要時(shí)間成本在于獲取T0(HHCn)的最大連通分支C，廣度優(yōu)先搜索算法最多運(yùn)行O(N(m+1))次。因?yàn)閘og(2m+1)=m+1 ≤log(N)，所以獲取T0(HHCn)的最大連通分支C的時(shí)間復(fù)雜度為O(NlogN)。其他每步的時(shí)間復(fù)雜度至多為O(N)。因此，算法t/s-HHCn-DIA G-PMC 的時(shí)間復(fù)雜度為O(NlogN)。證畢。

本文提出了一種在MM*模型下通過深度優(yōu)先搜索（DFS,depth first search）定位HHCn的無故障連通分支的算法DFS-MM*，如算法2 所示。然后基于DFS-MM* 算法，提出了一個(gè)針對HHCn的t/s-診斷算法t/s-HHCn-DI AG-M M*，其中，T表示無故障的頂點(diǎn)集合，F(xiàn)′表示通過此算法被診斷為故障頂點(diǎn)的集合，H表示為未診斷(可疑)的頂點(diǎn)集合。

算法2DFS-MM*

輸入HHCn中由故障集F產(chǎn)生的癥候σ，頂點(diǎn)集R和頂點(diǎn)x∈HHCn

由定理3 中情況2 可知，若可疑頂點(diǎn)的數(shù)目超過s+1，則所有可疑頂點(diǎn)都是無故障的。相反，如果可疑頂點(diǎn)的數(shù)目小于s，那么定理6 顯然成立。

由引理3 可知，HHCn-F中存在一個(gè)唯一的最大連通分支K且V(K)≥V(HHCn) -|F|-s，那么HHCn中除去最大連通分支K外剩余的小連通分支至多包含s個(gè)頂點(diǎn)。根據(jù)t/s-HHCn-DIAG-MM*算法，當(dāng)|V(K)|≥V(HHCn) -|F|-s＞t+1時(shí)，K中的所有頂點(diǎn)被診斷為無故障。在t/s-HHCn-DIAG-MM*算法中，如果|F′ |=t，則H中的所有頂點(diǎn)被診斷為無故障，沒有頂點(diǎn)被誤診；如果|F′ |≠t，則將所有未診斷（可疑）頂點(diǎn)分離到F′中。因此，F(xiàn)′=V(HHCn)-T，其中T被診斷為無故障的頂點(diǎn)的集合。則有

這意味著F′最多包含s個(gè)無故障頂點(diǎn)。因此，定理6 成立。證畢。

定理7當(dāng)m≥ 5，n=2m+m，且1≤s≤m-1時(shí)，t/s-HHCn-DIAG-MM*算法的時(shí)間復(fù)雜度為O(NlogN)，其中N=|V(HHCn)|。

5 比較結(jié)果

在系統(tǒng)級診斷中，如果系統(tǒng)可以檢測出不超過t個(gè)故障處理器，則稱該系統(tǒng)為t-可診斷的。在t-診斷系統(tǒng)中可以實(shí)現(xiàn)的t的最大值稱為診斷度，即傳統(tǒng)診斷度[1]。根據(jù)t-可診斷的定義可知，分層超立方網(wǎng)絡(luò)的傳統(tǒng)診斷度為m+1 。本節(jié)對本文研究的分層超立方網(wǎng)絡(luò)的h-額外條件診斷度、t/s-診斷度與傳統(tǒng)診斷度進(jìn)行比較分析，結(jié)果如圖6 所示。

圖6 HHCn 在3 種診斷策略下的故障診斷度（n=2m+m）

由圖6 可知，當(dāng)m≥5 時(shí)，分層超立方網(wǎng)絡(luò)的h-額外條件診斷度、t/s-診斷度均大于傳統(tǒng)診斷度，且分層超立方網(wǎng)絡(luò)的h-額外條件診斷度是傳統(tǒng)診斷度的h+1 倍，t/s-診斷度是傳統(tǒng)診斷度約s+1 倍。因此，與傳統(tǒng)診斷度相比，h-額外條件診斷度和t/s-診斷度提高了網(wǎng)絡(luò)的診斷度，能更好地評估分層超立方網(wǎng)絡(luò)的可靠性。

6 結(jié)束語

本文的研究成果有利于進(jìn)一步評估分層超立方網(wǎng)絡(luò)的可靠性，為分層超立方網(wǎng)絡(luò)的應(yīng)用和推廣奠定了的理論基礎(chǔ)。在接下來的工作中，可以考慮使用t/s-診斷算法監(jiān)控分層超立方網(wǎng)絡(luò)中的故障服務(wù)器。此外，郭晨等[26]研究了交換交叉網(wǎng)絡(luò)在PMC模型下的(t,k)-診斷度，熊茜等[27]研究了交換超立方網(wǎng)絡(luò)在PMC 模型下的(t,k)-診斷度，受其啟發(fā)，分層超立方網(wǎng)絡(luò)在PMC 模型和MM*模型下的(t,k)-故障診斷問題將是下一個(gè)研究內(nèi)容。