交換交叉立方網絡在PMC模型下的(t, k)-診斷度研究

郭晨，肖志芳，冷明，彭碩，王博

（1. 井岡山大學電子與信息工程學院，江西 吉安 343009；2. 江西省農作物生長物聯(lián)網技術工程實驗室，江西 吉安 343009）

1 引言

隨著電子工業(yè)的飛速發(fā)展，計算機系統(tǒng)中處理器的規(guī)模越來越大，尺寸越來越小。而在處理器規(guī)模不斷擴大的同時，計算機系統(tǒng)的故障風險也變得越來越高，由此引發(fā)了一系列可靠性問題的研究，其中又以故障的診斷問題最為迫切[1]。傳統(tǒng)的故障診斷是通過一個所謂的“中心處理器”來測試每一個處理器的運行狀態(tài)，從而給出故障評價，這種診斷方式工作量巨大并且多數(shù)情況都需要斷電甚至拆解系統(tǒng)，既不精確也缺乏可行性。因此，1967年，Preparata等[2]提出了一種基于圖論的系統(tǒng)級故障診斷（system level diagnosis）理論。系統(tǒng)級故障診斷充分利用了每一個處理器的處理能力，讓處理器之間進行相互測試，通過綜合分析來識別故障。通常情況下系統(tǒng)級故障診斷可以帶電進行。因此，系統(tǒng)級故障診斷既經濟又便捷，是多處理器并行計算機故障診斷的主要發(fā)展方向之一。

系統(tǒng)級故障診斷的執(zhí)行還依賴特定的診斷策略(diagnostic strategy)。1967年，Preparata等[2]首次將圖論方法運用于多處理器并行計算機系統(tǒng)的故障診斷，創(chuàng)造性地提出了t-可診斷策略。t-可診斷表示當系統(tǒng)的故障處理器數(shù)不超過t時，所有故障都可以被診斷出來。t-可診斷又可以根據迭代次數(shù)的不同，進一步分為一步t-可診斷和順序t-可診斷這2種類型。其中，一步t-可診斷只需要一次迭代即可完成，而順序t-可診斷則需要反復迭代，直到所有故障都被確認為止，每一次迭代都需要有新的故障被確認。順序t-可診斷是一種通過多步診斷來有效提高系統(tǒng)診斷能力的診斷方式，與一步t-可診斷相比，順序t-可診斷在診斷能力相同的情況下，可以較大程度地節(jié)省測試成本。

根據順序t-可診斷的定義可知，在最壞情況下，順序t-可診斷的每一次迭代只能確定一個故障節(jié)點，因此整體的迭代過程可能需要很長的時間，這大大降低了診斷的實時性?；诖?，2003年，Araki等[3]提出了新一代的順序t-可診斷理論——(t,k)-可診斷。(t,k)-可診斷要求系統(tǒng)在故障節(jié)點數(shù)不超過t時，每次迭代至少可以確定k個故障節(jié)點。(t,k)-可診斷最壞情況下的最大迭代次數(shù)僅為比順序t-可診斷的最大迭代次數(shù)t要小很多。因此，(t,k)-可診斷改善了順序t-可診斷的過度時延，是順序故障診斷的發(fā)展方向。事實上很多故障診斷理論都存在故障隨機分布和故障條件分布這 2種情景[4]，(t,k)-可診斷也不例外。在故障隨機分布的情況下，k=t時的(t,k)-可診斷就是一步t-可診斷，k=1時的(t,k)-可診斷就是順序t-可診斷。而對于故障節(jié)點不是隨機分布，而是和條件t-可診斷[1]一樣。要求所有的節(jié)點都至少有一個正確的鄰節(jié)點的情況，2011年，Chang等[4]把這種情況下的(t,k)-可診斷定義為條件(t,k)-可診斷。條件(t,k)-可診斷充分融合了條件t-可診斷和(t,k)-可診斷的優(yōu)點，在有效利用測試資源的基礎上提高了系統(tǒng)的診斷能力。因此，(t,k)-可診斷和條件(t,k)-可診斷成為了當下的研究熱點[5-11]。其中，Chang等[5]通過研究得出Preparata等[2]提出的PMC模型下超立方網絡(Qn)、扭立方網絡(TQn)、交叉立方網絡(CQn)和莫比烏斯立方網絡(MQn)的(t,k)診斷度均為。Chen等[6]在此基礎上進一步證得MM模型下Qn、TQn、CQn和MQn的(t,k)診斷度為，并進一步給出PMC模型下針對超立方網絡等分支組合圖(component-composition graph)(t,k)診斷度的通用求法[9]。2016-2017年，文獻[10-11]則分別給出了PMC模型下交換超立方網絡(EH(s,t))和MM模型下擴展立方體網絡(AQn)的(t,k)診斷度。(t,k)-可診斷改善了順序t-可診斷的過度時延，是順序故障診斷的發(fā)展方向。

互連網絡(interconnection network)是一個專門服務于處理器和內存模塊的通信機制[12]。迄今為止，互連網絡已發(fā)展成一個以超立方網絡及其變種為代表的具有多重繼承關系的拓撲結構集族。交換交叉立方網絡(ECQ, exchanged crossed cube)[13]是新型互連網絡的最新研究成果，它同時集成了交換立方網絡[14]和交叉立方網絡[15]的優(yōu)點，是多處理器并行計算機系統(tǒng)的一種更加優(yōu)化的組織形式。然而迄今為止，交換交叉立方網絡中以各種診斷度為代表的可靠性研究，如診斷度、g-正確鄰節(jié)點條件診斷度[16]、(t,k)-診斷度等均未有結果，這就嚴重制約了交換交叉立方網絡的應用和推廣。

基于此，本文以交換交叉立方網絡為研究對象，首先對其拓撲性質展開研究，在得到交換交叉立方網絡相關拓撲性質的基礎上，對交換交叉立方網絡在 PMC模型下的(t,k)-診斷度進行研究，通過理論推導得到了交換交叉立方網絡ECQ(s,t)在PMC模型下滿足(s+1,s+1)-可診斷和可診斷，其中0≤δ＜1，1≤s≤t。進而通過仿真驗證了結論的正確性。本文的研究進一步分析了交換交叉立方網絡的可靠性能，為交換交叉立方網絡的應用和推廣掃清了障礙，具有較強的理論價值和現(xiàn)實意義。

2 預備知識

2.1 PMC模型

迄今為止，系統(tǒng)級故障診斷已經提出了多種故障診斷模型，但是使用最為廣泛的還是 1967年Preparata等[2]提出的PMC模型。在PMC模型中，系統(tǒng)用有向圖G(V,E)表示，其中，V表示處理器節(jié)點集合，E表示測試邊集合。G(V,E)中任意的節(jié)點u表示為u∈V，如果存在著節(jié)點u測試節(jié)點v，則表示為(u,v)∈E。測試的結果用σ(u,v)表示，當節(jié)點u對節(jié)點v的測試評價是正確時，表示為σ(u,v)=0；否則表示為σ(u,v)= 1。系統(tǒng)所有的測試結果統(tǒng)稱為系統(tǒng)的一個癥候，用σ表示。PMC模型認為當測試節(jié)點無故障時測試結果真實可信，而當測試節(jié)點本身是故障節(jié)點時測試結果不可信。PMC模型下的測試規(guī)則如表1所示，其中，u、v表示任意2個節(jié)點；u=0表示u是正確節(jié)點，u=1表示u是故障節(jié)點；σ(u,v)表示節(jié)點u對節(jié)點v的測試結果。

表1 PMC模型的測試規(guī)則

2.2 交換交叉立方網絡

交換交叉立方網絡是 Li等[13]提出的一種新型互連網絡拓撲結構，它同時繼承了交換超立方網絡和交叉立方網絡的拓撲性質，表現(xiàn)出更高的性價比。

交換交叉立方網絡的定義需要首先引入關聯(lián)對的概念。

定義1[15]設2個長度為2的二進制字符串X和Y，其中X=x1x0，Y=y1y0。X～Y表示X和Y是關聯(lián)對，當且僅當(X,Y)∈{(00,00),(10,10),(01,11),(11,01)}時，X～Y。

定義2[13]交換交叉立方網絡表示為ECQ(s,t)，其中，s≥1，t≥1。通常用圖G(V,E)進行定義，其中，節(jié)點集合i∈[0,s),j∈[0,t)}。V中任意節(jié)點用一個“s+t+1”位的二進制字符串表示，u[i]表示節(jié)點u在位置i的取值用，u[i:j]表示節(jié)點u從第i個位置到第j個位置的取值用，其中i≤j。邊集合E包括3種類型，分別表示為E1、E2和E3，其定義如下。

E1：u[0]≠v[0]，且u[(s+t):1]=v[(s+t):1]時的邊(u,v)∈E1。

E2：u[0]=v[0]=0，且u[t:1]=v[t:1]，存在著正整數(shù)l，(s+t)≥l＞t，有u[(s+t):l]=v[(s+t):l]，如果l-t是偶數(shù)，那么D={1as-2…a0bt-1…b01|ai,bj∈{0,1}forj∈[0,s-2],i∈[0,t-1]}，u[t+2i+2:t+2i+1]～v[t+2i+2:t+2i+1]，其中E2，那么邊(u,v)∈E2；

E3：u[0]=v[0]=1，且u[(s+t):(Δt+1)]=v[(s+t):(t+1)]，存在著一個正整數(shù)l，t≥l≥1，有u[t:l]=v[t:l]，u[l-1]≠v[l-1]。如果(l-1)是偶數(shù)，那么u[l-2]=v[l-2]。u[(2i+2):(2i+1)]～v[(2i+2):(2i+1)]，其中，那么邊(u,v)∈E。3

由 ECQ(s,t)的定義可知，其中，屬于E1的邊2s+t條，屬于E2的邊2s+t-1t條，屬于E3的邊2s+t-1s條。

ECQ(1,1)、ECQ(1,2)和ECQ(2,2)的拓撲結構如圖1～圖3所示，其中虛線、粗實線和細實線分別表示E1、E2和E3。

圖1 ECQ(1,1)拓撲結構

圖2 ECQ(1,2)拓撲結構

圖3 ECQ(2,2)拓撲結構

ECQ(s,t)具有以下性質。

引理1[13]ECQ(s,t)的所有節(jié)點中，c位置取值為0的節(jié)點的度為s+1，c位置取值為1的節(jié)點的度為t+1。

因此可知，1≤s≤t時 ECQ(s,t)的最小度

引理 2[13]ECQ(s,t)可以劃分成 2個ECQ(s-1,t)或者2個ECQ(s,t-1)。

由引理 2可以把 ECQ(s,t)劃分為 2個ECQ(s-1,t)，分別表示為L和R，其中，L的節(jié)點集，R的節(jié)點集V(R)=。進一步把V(L)分為A和B這2個節(jié)點集合，把V(R)分為C和D這 2個節(jié)點集合，A、B、C和D的定義如下[13]

由A、B、C和D的定義可知，2個端點都屬于A的邊是E2邊，2個端點都屬于B的邊是E3邊，2個端點都屬于C的邊是E2邊，2個端點都屬于D的邊是E3邊，2個端點分別屬于A和B的邊是E1邊，2個端點分別屬于A和C的邊是E2邊，2個端點分別屬于C和D的邊是E1邊。同時A∪B、A∪C和C∪D都是完美匹配[17]，如圖4所示。

圖4 節(jié)點集合A、B、C、D示意

引理3[13]ECQ(s,t)與ECQ(t,s)同構，表示為

引理 4[17]ECQ(s,t)的點連通度k(ECQ(s,t))=s+1，其中1≤s≤t。

引理 5[18]ECQ(s,t)的拓撲結構不含節(jié)點三角（triangle-free）。

由引理5可知，對于ECQ(s,t)中任意的2個節(jié)點u和v，如果(u,v)∈E(ECQ(s,t))，那么|N(u)∩N(v)|=0，其中，N(u)和N(v)分別表示節(jié)點u和節(jié)點v的鄰節(jié)點集合。

2.3 (t,k)-可診斷

(t,k)-可診斷是2003年Araki和Shibata[3]共同提出的新一代順序t-可診斷，(t,k)-可診斷要求在故障節(jié)點不超過t個的情況下，迭代進行故障診斷，每一次迭代至少可以識別出其中的k個故障節(jié)點，其中k≤t。具體定義如下。

定義3[3]對于2個正整數(shù)t和k，k≤t，設F是系統(tǒng)的故障節(jié)點集合，給定癥候下當系統(tǒng)滿足以下2個條件時系統(tǒng)是(t,k)-可診斷系統(tǒng)。

1) 當|F|≤k時，所有的故障節(jié)點都可以被診斷出來。

2) 當k＜|F|≤t時，至少有k個故障節(jié)點可以被診斷出來。

給定一個正整數(shù)k≥1，系統(tǒng)滿足(t,k)-可診斷時，t可取到的最大正整數(shù)稱為系統(tǒng)的(t,k)-診斷度。當系統(tǒng)是(t,k)-可診斷系統(tǒng)時必然也是(t,k′)-可診斷系統(tǒng)，其中1≤k′＜k。(t,k)-可診斷可通過引理6進行判定。

引理 6[3]系統(tǒng)是(t,k)-可診斷系統(tǒng)，當且僅當對于任意故障節(jié)點數(shù)不超過t的癥候σ，或者其中，是與癥候σ一致的故障節(jié)點集合，并且|F|≤t}。

根據定義3可知，當k=t時，(t,k)-可診斷就是一步t-可診斷，因此，k=t時的(t,k)-診斷度可以按照一步t-可診斷的診斷度來求取，如引理7所示。

引理 7[19]設系統(tǒng)S有n個節(jié)點，如果S的點連通度k(S)≥t并且n≥(2t+1)，那么系統(tǒng)S是一步t-可診斷系統(tǒng)。

為了區(qū)分開(t,k)-可診斷和交換交叉立方網絡ECQ(s,t)中的t，下文將把(t,k)-可診斷改寫成(t1,k)-可診斷，其定義和性質定理維持不變。

2.4 集團

集團是 1998年張大方等[20]提出了一種特殊的連通分支，集團內的節(jié)點具有狀態(tài)相同的特點。具體定義如下。

定義 4[20]系統(tǒng)G(V,E)中滿足以下 2個條件的連通分支H，則稱為集團。

1)H中任意相鄰的 2個節(jié)點之間的測試結果都為“0”。

2)H中任意的節(jié)點如果與H以外的節(jié)點相連接，那么它們之間的互測結果不能同時為“0”。

在給定癥候的情況下，可以通過斷開所有測試結果為“1”的互測邊，求取強連通分支的方式來得出所有的集團。以ECQ(1,2)為例，它的癥候如圖5所示，那么斷開所有測試結果為“1”的互測邊之后如圖6所示。因此，該系統(tǒng)的集團有6個，分別是{0001,0000,0101}、{0100,1100}、{0111}、{1000,1001, 1101}、{0110,1110,1111}和{0011, 0010, 1010,1011}。

圖5 ECQ(1,2)的給定癥候示意

集團具有以下性質，如引理8～引理10所示。

引理8[20]集團中所有節(jié)點要么全都是故障節(jié)點，要么全都是正確節(jié)點。

圖6 圖5中包含的集團示意

通常情況下把全部是正確節(jié)點的集團稱為正確集團，把全部是故障節(jié)點的集團稱為故障集團。

引理9[21]如果系統(tǒng)的故障節(jié)點數(shù)不超過t，那么系統(tǒng)中節(jié)點數(shù)大于t的集團必定是正確集團。

引理10[21]正確集團只能和故障集團相鄰。

G(V,E)在給定癥候下的所有集團歸為集合V+，不同集團之間的鄰接集合E+，表示為E+={(X,Y)|X∈V+,Y∈V+,(x,y)∈E,x∈X,y∈Y}。由此可以把G(V,E)表示為G+(V+,E+)。集團集合V+的獨立子集V+′，指的是V+′?V+并且V+′中的任意集團之間都不相鄰。

定義5[5]?(x1)表示m可取到的最小正整數(shù)。指的是在G+(V+,E+)中，V+存在著一個滿足的子集V+′，是V+的獨立子集，使得V+-V+′中不存在滿足|Xi|≥x1的集團Xi。

定義6[5]φ(x1,x2)表示p可取到的最大正整數(shù)。指的是在G+(V+,E+)中，對于V+中滿足|V+′|≤p的每一個子集V+′，V+-V+′是V+的獨立子集，則至少存在著一個屬于V+-V+′的集團Xi，Xi滿足以下2個條件。

定義7[5]函數(shù)I(m)表示節(jié)點數(shù)為m的所有節(jié)點子集中，2個端點都屬于該子集的邊的最大數(shù)目。

由I(m)的定義可知，I(1)=0。

3 交換交叉立方網絡的拓撲性質

接下來，對交換交叉立方網絡拓撲結構的鄰節(jié)點性質展開研究。

定理1設節(jié)點u和節(jié)點v是ECQ(s,t)中任意的2個節(jié)點，則N(u)∩N(v)≤2。

證明用數(shù)學歸納法證明。由圖 1～圖 3可知，ECQ(1,1)、ECQ(1,2)和ECQ(2,2)都滿足N(u)∩N(v)≤2。假設ECQ(s-1,t)(或者ECQ(s,t-1))也滿足N(u)∩N(v)≤2。接下來證明ECQ(s,t)是否滿足N(u)∩N(v)≤2。根據引理 2把ECQ(s,t)劃分為2個ECQ(s-1,t) (或者ECQ(s,t-1))，分別表示為L和R。不失一般性，設當u,v∈V(L)(或者u,v∈V(R))時，N(u)∩N(v)?V(L)(或者N(u)∩N(v)?V(R))。根據數(shù)學歸納法的假設可知|N(u)∩N(v)|≤2。而當u∈V(L)并且v∈V(R)(或者u∈V(R)并且v∈V(L))時，如圖4所示，由于A和C之間是完美匹配，所以|N(u)∩N(v)|≤2。因此，定理1可證，證畢。

定理2設節(jié)點u和節(jié)點v是ECQ(s,t)中任意的2個節(jié)點，且(u,v)∈E(ECQ(s,t))，那么

證明由引理 1可知，ECQ(s,t)的所有節(jié)點中，c位置取值為 0的節(jié)點的度為(s+1)，c位置取值為1的節(jié)點的度為(t+1)。所以由引理5可知，當u和v在c位置的取值都為0時，；當u和v在c位置的取值都為1時，；當u和v有一個在c位置的取值為 0，另一個在c位置的取值為 1時，。因此證畢。

在得到 ECQ(s,t)相關拓撲性質的基礎上，對 ECQ(s,t)在 PMC模型下的(t1,k)-診斷度展開研究。

4 交換交叉立方網絡在PMC模型下的(t1,k)-可診斷

首先進行函數(shù)?(x1)、φ(x1,x2)和I(m)的取值研究。

定理3在ECQ(s,t)中，

證明根據引理 2可把ECQ(s,t)劃分為 2個ECQ(s-1,t)，分別表示為L和R，其中，V(L)=如圖4可知，節(jié)點集合A中的每一個節(jié)點都與節(jié)點集合C中的一個節(jié)點相鄰接。對于ECQ(s,t)的任意節(jié)點子集X和Y，設由于YL中的任意節(jié)點至多只有一個屬于YR的鄰節(jié)點，反之也一樣，因此存在著如式(1)所示的不等式。

Y內部的邊數(shù)≤LY內部的邊數(shù)+

設IL(m)(或者IR(m))表示屬于L(或者R)且節(jié)點數(shù)為m的節(jié)點子集包含內部邊的最大數(shù)目，同樣有IL(1)=0、IR(1)=0。由不等式(1)可知，I(|Y|)≤。不失一般性地，設則那么，

接下來，用數(shù)學歸納進行證明。由圖1～圖3可知，ECQ(1,1)、ECQ(1,2)和ECQ(2,2)都滿足。假設ECQ(p,q)也有其中1＜p＜s、1＜q≤t。那么接下來證明ECQ(s,t)是否滿足

當β=0時由歸納法的假設可知因此。當β≥1時，，同樣由歸納法的假設可知設函數(shù)，可知f′(β)=由于，可知β=1或者時f()β可取到最大值。由于所以I(m)≤mlbm，定理3可證，證畢。

接下來，對ECQ(s,t)在PMC模型下滿足(t1,k)-可診斷時k和t1的取值進行研究。

4.1 k的取值研究

給定癥候下的ECQ(s,t)用表示，其中1≤s≤t。設集團XV+∈，VX表示X的節(jié)點集合，VN(X)表示X的鄰節(jié)點集合。由ECQ(s,t)和集團的定義可知|X|＞0、|VN(X)|＞0，并且X具有以下性質。

定理4把G(V,E)表示為G+(V+,E+)，設集團X∈V+，則|VN(X)|≥k(G)或者

證明由X和VN(X)的定義可知，X和V-VN(X)之間不存在邊連接，如果V-VX-VN(X)≠?則VN(X)是G(V,E)的一個點割集，因此|VN(X)|≥k(G)。而當V-VX-VN(X)=?時，可以直接推導出V=VX+VN(X)，證畢。

另外可知，從VN(X)發(fā)出的到VN(X)以外的邊數(shù)+VN(X)內部的邊數(shù)≥VN(X)到VX的邊數(shù)+VN(X)到V-VX-VN(X)的邊數(shù)，如圖7所示。由引理1可知，ECQ(s,t)中每一個節(jié)點的度∈{s+1,t+1}。由于1≤s≤t，所以從VN(X)發(fā)出的到VN(X)以外的邊數(shù)+VN(X)內部的邊數(shù)≤|VN(X)|(t+1)。VN(X)到VX的邊數(shù)=VX到VN(X)的邊數(shù)=VX發(fā)出的到VX以外的所有邊數(shù)－VX內部的邊數(shù)，因此VN(X)到VX的邊數(shù)≥|VX|(s+1)-I(|VX|)。同理，由于V-VX-VN(X)與VX之間不存在著邊連接，所以VN(X)到V-VX-VN(X)的邊數(shù)。因此VX-VN(X)|)。由定理3可知所以可得

圖7 G+(V+,E+)中集團X和VN(X)示意

由不等式(2)可進一步推導出定理5。

定理5在給定癥候下，ECQ(s,t)用G+(V+,E+)表示，其中，1≤s≤t。那么對于V+中的任意集團X，都有|VN(X)|≥s+1。

證明由于以下分2種情況進行證明。

情況1|VX|≥2(s+1)并且|V-VX-VN(X)|≥2(s+1)，由于|V-VX-VN(X)|=|V|-|VX|-|VN(X)|，所以可推導出2(s+1)≤|VX|≤|V|-|VN(X)|-2(s+1)＜|V|-2(s+1)。因此，可知4(s+1)＜|V|。設p=|VN(X)|，q=|VX|，所以2(s+1)≤q≤|V|-p-2(s+1)＜|V|-2(s+1)。可以把不等式(2)轉換為

對函數(shù)h(p,q)求偏導，可得

所以h(p,q)是關于變量p單調遞減，并且由h(p,q)的一階偏導和二階偏導可知，h(p,q)在p取最大值并且q取最大值(或者取最小值)時可以取到最小值。

假設p≤s+1，那么當p=s+1并且q=2(s+1)(或者q=|V|-2(s+1))時h(p,q)可取到最小值。因此，h(s+1,2(s+1))≤h(p,q)，h(s+1,|V|-2(s+1))≤h(p,q)。由于h(s+1,2(s+1))＞0、h(s+1,|V|-2(s+1))≥0，所以要求h(p,q)＞0，這與h(p,q)≤0相矛盾。因此

情況2

情況2.1

情況2.1.1

情況2.1.2

由V≠VX+VN(X)，可知V-VX-VN(X)≠?。由定理 4可知，|VN(X)|≥k(G)。又由引理 4可知k(ECQ(s,t))=s+1，所以|VN(X)|≥s+1。

情況2.2

證畢。

由引理10和定理5可知，對于給定癥候下的ECQ(s,t)，如果可以確定集團X是正確集團，那么可知VN(X)都是故障節(jié)點，且|VN(X)|≥s+1。因此，在能確定任意一個正確集團的前提下，ECQ(s,t)在PMC模型下滿足(t1,k)-可診斷時k≥s+1。

4.2 t1的取值研究

首先研究ECQ(s,t)中函數(shù)?(t1+1)的取值，在此基礎上研究滿足φ(t1+1,0)≥t1時t1可取到的最大值，進而可以確定ECQ(s,t)在 PMC模型下滿足(t1,k)-可診斷時t1的取值。

定理6對于ECQ(s,t)，函數(shù)?(t1+1)≥其中1≤s≤t。

證明根據?(x1)的定義可知?(t1+1)≥，表示存在著一個滿足的集團子集V′+，使V+-V+′是V+的獨立子集，并且V+-V+′中的任意集團Yj都滿足|Yj|≤t1。設其中X,X,…,X及12a表示V+中所有的集團，

由于V+-V+′是V+的獨立子集，所以集團兩兩不相鄰且由引理1可知，ECQ(s,t)中c位置取值為0的節(jié)點的度為s+1，c位置取值為1的節(jié)點的度為t+1，其中1≤s≤t。因此，，其中，且V+′與V+-V+′之間的邊數(shù)目不超過（當從V′+發(fā)出的所有邊的另一個頂點都屬于V+-V+′時可取到最大值）。

由于

定理6可證，證畢。

基于?(t1+1)和φ(t1+1,0)的關聯(lián)關系，可通過定理6對φ(t1+1,0)≥t1時t1的取值進行研究，得出定理7。

定理 7對于時函數(shù)其中0≤δ＜1。

證明由于所以接下來，需要證明是否成立。設，可以求得。可知當時時h(t1)單調遞減。且當時h(t1)＜0，h(t1)的基本走勢如圖 8所示。 由于時存在著，因此根據的定義可知，時不滿足。而當時為了使，則要求同時可知時。因此，其中0≤δ＜1。定理7可證，證畢。

圖8 h(t1)的走勢

由定理7可知，ECQ(s,t)在PMC模型下滿足-可診斷時，如果，其中0≤δ＜1，那么至少存在著一個集團Xi，|Xi|≥t1+1且|N(Xi)|≥0。根據(t1,k)-可診斷的定義可知系統(tǒng)的故障節(jié)點數(shù)不超過t1時集團Xi必然是正確集團，VN(Xi)是故障節(jié)點。

4.3 交換交叉立方網絡在 PMC 模型下的(t1,k)-診斷度

由于k=t1時(t1,k)-可診斷就是一步t1-可診斷，ECQ(s,t)在k=t1時的(t1,k)-診斷度如定理 8所示。

定理8ECQ(s,t)滿足(s+1,s+1)-可診斷，其中1≤s≤t。

證明由引理4可知，1≤s≤t時k(ECQ(s,t))=s+1。由于1)+1，其中1≤s≤t。由引理7可知，ECQ(s,t)是一步(s+1)-可診斷，因此ECQ(s,t)滿足(s+1,s+1)-可診斷，其中1≤s≤t，定理8可證，證畢。

根據定理5和定理7可進一步證得ECQ(s,t)在t1＞k時的(t1,k)-診斷度，如定理9所示。

定理 9ECQ(s,t)滿足-可診斷，其中

證明由定理7可知，ECQ(s,t)在PMC模型下滿足(t1,k)-可診斷時，如果其中0≤δ＜1，那么至少存在著一個集團Xi，|Xi|≥t1+1且|N(Xi)|≥0。又由定理 5可知，給定癥候下ECQ(s,t)的任意集團Xi∈V+，都有|VN(Xi)|≥s+1，其中1≤s≤t。因此，根據(t1,k)-可診斷的定義可知ECQ(s,t)是可診斷系統(tǒng)，其中。證畢。

4.4 仿真實驗

接下來，對ECQ(s,t)（1≤s≤t≤5）的(t1,k)-診斷度進行仿真實驗驗證。仿真算法分為節(jié)點編碼處理、節(jié)點狀態(tài)編碼處理和(t1,k)-診斷度計算3個模塊。通過節(jié)點編碼處理模塊和節(jié)點狀態(tài)編碼處理模塊分別賦給每一個節(jié)點一個地址值和一個狀態(tài)值，其中，地址值用一個長度與維數(shù)相等的二進制數(shù)表示，狀態(tài)值用一位二進制表示，如圖9所示。

以ECQ(2,2)為例，其拓撲結構如圖3所示，共有節(jié)點數(shù)32個，所有節(jié)點的地址值用一個長度為5的二進制表示，通過節(jié)點編碼處理模塊生成的節(jié)點地址值如表2所示。

節(jié)點有正常和故障2種狀態(tài)，用“0”表示“正?！睜顟B(tài)，用“1”表示故障狀態(tài)。以ECQ(2,2)為例，通過節(jié)點狀態(tài)編碼處理模塊之后，32個節(jié)點的狀態(tài)值總共有232種情況，如表3所示。仿真實驗并不需要考慮232種的所有的情況，只需要根據t的取值，考慮故障節(jié)點數(shù)少于等于t個的情況，因此共有Ct32種情況。

(t1,k)-診斷度計算處理模塊按照引理 6的充要條件進行設計，包含3個步驟，具體如下。

圖9 仿真實驗的節(jié)點編碼和節(jié)點狀態(tài)編碼

表2 ECQ(2, 2)中32個節(jié)點的地址值

表3 ECQ(2, 2)中32個節(jié)點可取的狀態(tài)值

步驟1計算出ECQ(s,t)中不超過t1個故障節(jié)點的所有故障節(jié)點集合。

步驟 2對每一種故障節(jié)點集合的每一個癥候σ，構建出Ωσ,t1。

步驟3如果所有故障節(jié)點集合的所有癥候都滿足或者那么ECQ(s,t)滿足(t1,k)-可診斷，否則t1=t1-1，跳轉到步驟 1。

以ECQ(2,2)為例，步驟 1中不超過t（t≥1）個故障節(jié)點的所有故障節(jié)點集合共有（即 35 960）種。設定t=4之后，故障節(jié)點集合共有種情況，如表4所示。

進而以第5 178種情況的故障節(jié)點集合為例構建起癥候，如圖10所示。

圖10 ECQ(2,2)特定癥候

與圖10癥候相一致的故障節(jié)點集合，只有表5所示的唯一一種情況。因此，Ωσ,t={00000, 00001,00010}。

節(jié)點編碼處理模塊和節(jié)點狀態(tài)編碼處理模塊的處理流程相對簡單，計算規(guī)模較小。仿真實驗的主要處理過程集中在(t1,k)-診斷度計算處理模塊，通過步驟 1可以取得種故障節(jié)點集合，在最壞情況下步驟 2中的每一種故障節(jié)點集合最多需要對應2t1個癥候，最后通過步驟 3進行循環(huán)判斷。仿真實驗的時間復雜度為O(2nt1)，時間復雜度較高。仿真實驗環(huán)境為2顆至強E5-4620 v2 CPU，2塊16 GB 1 600 MHz內存，2塊1.2 TB 10K RPM SAS 6 Gbit/s硬盤，Microsoft SQL Server 2008數(shù)據庫。通過計算得出的仿真實驗數(shù)據如表6所示。實驗結果進一步印證了定理7和定理8的結論。

實際應用中可以引入環(huán)診斷算法[22]進行(t1,k)-故障診斷。根據環(huán)診斷算法，對初始癥候進行局部識別，借助0→0→…→0→1的局部癥候來識別故障節(jié)點，進而在替換掉已識別故障節(jié)點的基礎上進行第二次迭代故障診斷，直到所有的故障節(jié)點都被識別為止。

表4 故障節(jié)點數(shù)不超過4時ECQ(2, 2)的35 960種故障節(jié)點集合

表5 與圖10癥候相一致故障節(jié)點集合

5 結束語

本文以ECQ(s,t)為研究對象，首先對ECQ(s,t)的拓撲結構展開研究，證得了ECQ(s,t)在鄰節(jié)點方面的相關拓撲性質。在此基礎上引入集團的思想，借助3個重要函數(shù)證明了ECQ(s,t)在PMC模型下是(s+1,s+1)-可診斷和可診斷，其中最后通過仿真實驗驗證了結論的正確性。本文的研究成果將有利于進一步理清交換交叉立方網絡的可靠性，為交換交叉立方網絡的應用和推廣奠定了堅實的理論基礎。

表6 仿真實驗數(shù)據與理論推導結果