喬慧娟，原 軍

(太原科技大學(xué) 應(yīng)用科學(xué)學(xué)院，太原 030024)

由數(shù)千個處理器組成的多處理器系統(tǒng)能夠提高計算的能力，但如果多處理器系統(tǒng)中某個處理器出現(xiàn)故障，就可能造成整個互連網(wǎng)絡(luò)的癱瘓。發(fā)現(xiàn)故障處理器，并用無故障處理器將其替換，是保證多處理器系統(tǒng)運行的安全性和可靠性的重要手段。因此，故障診斷度，即系統(tǒng)能診斷出的故障處理器的最大數(shù)量，成為評估多處理器系統(tǒng)可靠性的一個重要指標(biāo)。

1967年，Preparata，Metze和Chien[1]建立了一個系統(tǒng)級診斷模型，稱為PMC模型。它通過系統(tǒng)本身自動測試處理器，這大大提高了系統(tǒng)故障診斷的效率。之后研究人員還建立了許多系統(tǒng)級診斷模型，例如BGM模型[2]、比較模型[3]。本文考慮Preparata，Metzem和Chien提出的PMC模型。

因為經(jīng)典的診斷度對頂點沒有任何限制，所以當(dāng)連接到某個頂點的所有鄰點同時出現(xiàn)故障時，系統(tǒng)將沒有辦法判斷該頂點的狀態(tài)。因此，經(jīng)典的診斷度總小于系統(tǒng)的最小度。為了更好地反映實際系統(tǒng)中的故障模式，2005年，Lai等人[4]提出了條件診斷度，它假設(shè)在一個系統(tǒng)當(dāng)中任意頂點的所有鄰點都不會同時出現(xiàn)故障。條件診斷度可以更好地衡量系統(tǒng)的可診斷能力。

2012年，Peng等人[5]提出了一個更一般的限制條件，要求每個無故障頂點連接大于等于g個無故障鄰點。在此條件下，系統(tǒng)的診斷度稱為g-好鄰條件診斷度。之后系統(tǒng)的g-好鄰條件診斷度得到了廣泛的研究，譬如，Wang等人[6]研究了MM*模型下超立方體的g-好鄰條件診斷度；Yuan等人[7]研究了PMC模型下和MM*模型下k元n方體的g-好鄰條件診斷度；Li等人[8]研究了PMC模型下和MM*模型下星圖的g-好鄰條件診斷度。

2007年，Hsu等人[9]發(fā)現(xiàn)之前的大多數(shù)文獻(xiàn)都在研究整個系統(tǒng)上的診斷度，而忽略了系統(tǒng)中的局部信息。于是，他們提出了局部診斷度的概念并研究了PMC模型下星圖的局部診斷度。2019年，Yin和Liang[10]提出了g-好鄰局部診斷度的概念，并研究了PMC模型下超立方體的g-好鄰局部診斷度。

星圖是一類重要的多處理器系統(tǒng)網(wǎng)絡(luò)拓?fù)洌哂薪Y(jié)點度低，對稱性好，直徑小和高度的容錯性。因其良好的拓?fù)湫再|(zhì)被作為互連網(wǎng)絡(luò)拓?fù)鋺?yīng)用于許多多處理器計算機(jī)系統(tǒng)之中[11-12]。本文討論并得到PMC模型下星圖Sn的每個結(jié)點的g-好鄰局部診斷度。再結(jié)合g-好鄰局部診斷度和g-好鄰診斷度的關(guān)系，可以推出星圖在PMC模型下的g-好鄰診斷度。

1 基本概念及符號說明

多處理器系統(tǒng)通常建模為一個無向簡單圖G(V(G)，E(G))，其中頂點代表處理器，邊代表處理器之間的通信鏈接。文中常省略字母G，例如分別用V，E代替V(G)，E(G).在無向圖G(V，E)中，(u，v)=e∈E表示頂點u和v之間的邊，u和v是e的端點且彼此相鄰。對于一個頂點u∈V，符號NG(u)表示u的所有鄰點的集合。圖G中頂點u的度用dG(u)或d(u)表示，δ(G)表示G的最小度。若對所有的頂點v∈V，有d(v)=k，則稱圖G是k-正則的。令F?V，定義NG(F)=(∪v∈FNG(v))F為G中頂點集F的鄰集。GF是G的一個子圖，它是通過刪掉F中的所有頂點和與F中頂點相關(guān)聯(lián)的邊而得到的。在圖G中，如果GF不連通，則稱F為G的頂點割。使G只剩下一個頂點或不連通，需要刪除的最小頂點數(shù)稱為G的連通度，記作κ(G).如果每個頂點u∈VF在VF中至少有g(shù)個鄰點，則子集F?V稱為G的Rg-頂點集，也稱g-好鄰條件集。若頂點子集F是連通圖G的Rg-頂點集且GF不連通，則稱F是G的Rg-頂點割。G的Rg-頂點連通度，用κg(G)表示，是G的最小Rg-頂點割的頂點數(shù)。定義F1，F(xiàn)2?V的對稱差F1ΔF2=(F1F2)∪(F2F1).

在PMC模型中，系統(tǒng)中兩個直接相連的頂點可以互相發(fā)送測試消息。對于任意兩個相連的頂點u和v，有序?qū)?u，v)表示頂點u在其鄰點v上執(zhí)行的測試。測試任務(wù)T是每個相鄰頂點對的測試的集合。可以將其建模為有向圖T=(V，L)，其中V是G的頂點集，L={u→v|u，v∈V(G)，(u，v)∈E(G)}.測試任務(wù)T的所有測試結(jié)果的集合稱為校正子，從形式上說，它是一個函數(shù)σ:L→{0，1}.σ(F)表示故障頂點集F可能產(chǎn)生的所有校正子的集合。假設(shè)F1和F2是V中兩個不同的集合，如果σ(F1)∩σ(F2)=?，則F1和F2是可區(qū)分的且(F1，F(xiàn)2)是可區(qū)分對，否則，F(xiàn)1和F2是不可區(qū)分的且(F1，F(xiàn)2)是不可區(qū)分對。

下面給出了PMC模型下兩個故障集是可區(qū)分的充要條件。

定理1[13]對于G中任意一對相異的頂點子集F1和F2，(F1，F(xiàn)2)是一個可區(qū)分對當(dāng)且僅當(dāng)存在兩個頂點u∈F1ΔF2，v∈V(F1∪F2)使得(u，v)∈E.(見圖1).

圖1 PMC模型下的可區(qū)分對(F1，F(xiàn)2)Fig.1 A distinguishable pair(F1，F(xiàn)2)under the PMC model

2005年，Lai等人提出了條件診斷度的定義。G的條件診斷度tc(G)=max{t|G是條件t-可診斷的}。

2012年，Peng等人擴(kuò)展了條件診斷度的概念，提出了g-好鄰條件診斷度tg(G)=max{t|G是g-好鄰條件t-可診斷的}。

引理1如果系統(tǒng)G中任意一對滿足|F1|≤t，|F2|≤t的條件故障集F1，F(xiàn)2是可區(qū)分的，則系統(tǒng)G是條件t-可診斷的。

引理2如果系統(tǒng)G中任意兩個滿足|F1|≤t，|F2|≤t的g-好鄰條件故障集F1，F(xiàn)2是可區(qū)分的，則系統(tǒng)G是g-好鄰條件t-可診斷的。

2007年，Hsu等人通過研究系統(tǒng)的局部信息，提出了局部診斷度。系統(tǒng)G在頂點u處的局部診斷度tl(u)=max{t|G在頂點u處是局部t-可診斷的}。

引理3令G是一個圖并且u是G中的一個頂點，頂點u是局部t-可診斷的當(dāng)且僅當(dāng)對于任意一對滿足|F1|≤t，|F2|≤t，u∈F1ΔF2的不同的條件故障集F1，F(xiàn)2?V是可區(qū)分的。

定義1在系統(tǒng)G中，如果tl(u)=d(u)，則稱頂點u∈V是強(qiáng)局部可診斷的。

定義2如果G的每個頂點都是強(qiáng)局部可診斷的，則系統(tǒng)G是強(qiáng)局部可診斷的。

2019年，Yin和Liang提出了g-好鄰局部診斷度并得到了下面的一些結(jié)論。

引理4圖G在頂點u∈V處是g-好鄰局部t-可診斷的當(dāng)且僅當(dāng)對于任何一對滿足|F1|≤t，|F2|≤t，u∈F1ΔF2的不同的g-好鄰條件故障集F1，F(xiàn)2?V，(F1，F(xiàn)2)是一個可區(qū)分對。

引理5[10]系統(tǒng)G在頂點u處的g-好鄰局部診斷度tgl(u)=max{t|G在頂點u處是g-好鄰局部t-可診斷的}。

引理6圖G是g-好鄰條件t-可診斷的當(dāng)且僅當(dāng)G的每個頂點都是g-好鄰局部t-可診斷的。

n維星圖記為Sn，它的頂點集V(Sn)={u1u2…un|ui∈{1，2，…，n}并且ui≠uj對于i≠j}.兩個頂點u和v是相鄰的當(dāng)且僅當(dāng)u的標(biāo)號可以通過將v的標(biāo)號的第一個元素與第i個元素(2≤i≤n)互換得到，即若u=u1u2…ui-1uiui+1…un，v=uiu2…ui-1u1ui+1…un，則u和v相鄰。Sn是由n!個頂點和(n-1)n!/2條邊組成的，并且對于任意整數(shù)n≥3，Sn是n-1正則、點可遷、邊可遷的偶圖。圖2給出了一個3維星圖S3和4維星圖S4.

圖2 3維星圖和4維星圖Fig.2 3D and 4D star graphs

2 PMC模型下星圖的g-好鄰局部診斷度

這個部分討論PMC模型下星圖的g-好鄰局部診斷度，下面先給出一些相關(guān)的定理和引理：

定理2[14]當(dāng)0≤g≤n-2時，Sn的Rg-頂點連通度κg(Sn)=(n-g-1)(g+1)!.

引理7當(dāng)n≥3時，n維星圖Sn是強(qiáng)局部可診斷的。

引理8設(shè)H是Sn的子圖且δ(H)≥g，則|V(H)|≥(g+1)!

引理9令H是星圖Sn的一個子圖，頂點集V(H)={h1h2…h(huán)g+1(g+2)…n|1≤hi≤g+1，0≤g≤n-2，n≥4}，且令F1=NSn(H)，F(xiàn)2=F1∪V(H)，則|F1|=(n-g-1)(g+1)!，|F2|=(n-g)(g+1)!，并且F1，F(xiàn)2是g-好鄰條件故障集。

定理3設(shè)整數(shù)0≤g≤n-2，n≥4，那么在PMC模型下n維星圖Sn中任意一個頂點u∈V(Sn)，都有u的g-好鄰局部診斷度tgl(u)≤(n-g)(g+1)!-1.

證明運用引理4證明tgl(u)≤(n-g)(g+1)!-1，即在Sn中有兩個滿足|F1|≤(n-g)(g+1)!，|F2|≤(n-g)(g+1)!

且u∈F1ΔF2的不同的g-好鄰條件故障集F1，F(xiàn)2?V(Sn)，F(xiàn)1和F2是不可區(qū)分的。令H，F(xiàn)1和F2的定義如引理9(如圖3所示)且由Sn的對稱性，不妨設(shè)u=12…n.則u∈V(H)=F2F1=F1ΔF2.由引理9可知|F1|≤(n-g)(g+1)!，|F2|≤(n-g)(g+1)!，并且F1和F2是g-好鄰條件故障集。注意到V(Sn)(F1∪F2)與F1ΔF2之間不存在邊。由定理1，F(xiàn)1和F2是不可區(qū)分的。所以星圖Sn在u∈F1ΔF2點處不是g-好鄰局部(n-g)(g+1)!-可診斷的。

圖3 F1，F(xiàn)2和H的關(guān)系圖Fig.3 A diagram of F1，F(xiàn)2 and H

定理4設(shè)整數(shù)0≤g≤n-2，n≥4，那么在PMC模型下n維星圖Sn中任意一個頂點u∈V(Sn)，都有u的g-好鄰局部診斷度tgl(u)≥(n-g)(g+1)!-1.

證明首先，考慮g=0的情況。此時，對Sn的故障集沒有條件限制。因此，對于Sn中的任意頂點u，Sn在u處的g-好鄰局部診斷度等于Sn在u處的局部診斷度。因為n≥4，所以由引理7和定義2可以推斷出V(Sn)的每個頂點都是強(qiáng)局部可診斷的。由于Sn是(n-1)-正則的，根據(jù)定義1可以得出，對于任意頂點u∈V(Sn)，Sn在u處的局部診斷度等于頂點u的度，即tl(u)=dSn(u)=n-1.當(dāng)g=0時，(n-g)(g+1)!-1=n-1.因此tgl(u)=tl(u)=n-1≥(n-g)(g+1)!-1，結(jié)論成立。

接下來，考慮1≤g≤n-2的情況。由引理4，只需證明對于任意兩個滿足|F1|≤(n-g)(g+1)!-1，|F2|≤(n-g)(g+1)!-1并且u∈F1ΔF2的不同的g-好鄰條件故障集F1和F2，(F1，F(xiàn)2)是可區(qū)分對。反之，假設(shè)存在頂點u和兩個不同的g-好鄰條件故障集F1和F2，其中|F1|≤(n-g)(g+1)!-1，|F2|≤(n-g)(g+1)!-1，使得F1ΔF2包含頂點u，但(F1，F(xiàn)2)是不可區(qū)分對。討論以下兩種情況。

情況1F2F1=?或F1F2=?.

不失一般性，假設(shè)F2F1=?且u∈F1F2≠?.則V(Sn)(F1∪F2)=V(Sn)F1且F1ΔF2=F1F2.由于F1和F2是不可區(qū)分的，故由定理1可知，要么V(Sn)=F1，要么V(Sn)≠F1且V(Sn)F1與F1F2之間不存在邊。

子情況1.1V(Sn)=F1

由于1≤g≤n-2，n≥4且|F1|≤(n-g)(g+1)!-1，故n!=|V(Sn)|=|F1|≤(n-g)(g+1)!-1≤(n-(n-2))(n-2+1)!-1=2(n-1)!-1

子情況1.2V(Sn)≠F1

此時，V(Sn)(F1∪F2)和F1ΔF2之間沒有邊。由V(Sn)≠F1可知，F(xiàn)1∩F2是Sn的一個頂點割。因為F1和F2是g-好鄰條件故障集，所以F1∩F2也是g-好鄰條件故障集，從而F1∩F2是Rg-頂點割，由定理2，|F1∩F2|≥(n-g-1)(g+1)!.由于F2是g-好鄰條件故障集，因此在Sn中F1F2的生成子圖的最小度至少為g，即δ(Sn[F1F2])≥g.再由引理8，|F1F2|≥(g+1)!從而|F1|=|F1∩F2|+|F1F2|≥(n-g-1)(g+1)!+(g+1)!+(g+1)!=(n-g)(g+1)!>(n-g)(g+1)!-1，與假設(shè)|F1|≤(n-g)(g+1)!-1矛盾！

情況2F2F1≠?且F1F2≠?.

因為F1和F2是不可區(qū)分的，所以由定理1可知，要么V(Sn)=F1∪F2，要么V(Sn)(F1∪F2)與F1F2之間不存在邊。分兩種情況討論。

子情況2.1V(Sn)=F1∪F2

當(dāng)1≤g≤n-2時，(n-g)(g+1)!關(guān)于g是嚴(yán)格單調(diào)遞增的，故由1≤g≤n-2且n≥4可知，n!=|V(Sn)|=|F1∪F2|=|F1|+|F2|-|F1∩F2|≤|F1|+|F2|≤2(n-g)(g+1)!-2≤2(n-(n-2))(n-2+1)!-2=4(n-1)!-2

子情況2.2V(Sn)≠F1∪F2

此時，V(Sn)(F1∪F2)與F1ΔF2之間無邊。故F1∩F2是一個割。又因為F1和F2是g-好鄰條件故障集，所以F1∩F2也是g-好鄰條件故障集。從而F1∩F2是Rg-頂點割。由定理2可知，|F1∩F2|≥(n-g-1)(g+1)!.由于F2是g-好鄰條件故障集，故在Sn中F1F2的生成子圖的最小度至少為g，即δ(Sn[F1F2])≥g，由引理8，|F1F2|≥(g+1)!.從而|F1|=|F1∩F2|+|F1F2|≥(n-g-1)(g+1)!+(g+1)!=(n-g)(g+1)!>(n-g)(g+1)!-1，與假設(shè)|F1|≤(n-g)(g+1)!-1矛盾！

由定理3和定理4，可以推出下面的定理。

定理5設(shè)整數(shù)0≤g≤n-2，n≥4，那么在PMC模型下n維星圖Sn中每一個頂點u的g-好鄰局部診斷度tgl(u)=(n-g)(g+1)!-1.

定理6[10]對于一個圖G，G的g-好鄰診斷度tg(G)=min{tgl(u)|?u∈V}.

推論1Sn的g-好鄰診斷度tg(Sn)=min{tgl(u)|u∈V(Sn)}=(n-g)(g+1)!-1.其中0≤g≤n-2且n≥4.

3 總結(jié)

本文考慮了在PMC模型下星圖Sn的每個頂點上的g-好鄰局部診斷度，并證明了在PMC模型下，當(dāng)0≤g≤n-2且n≥4時，星圖Sn的每個頂點的g-好鄰局部診斷度為(n-g)(g+1)!-1.因為星圖具有頂點對稱性，所以通過計算星圖Sn中每個頂點的g-好鄰局部診斷度可以進(jìn)一步推導(dǎo)出星圖的g-好鄰診斷度。比較模型作為研究診斷度的經(jīng)典模型，可以考慮在比較模型下星圖Sn的每個頂點上的g-好鄰局部診斷度。除此之外還可以在這兩種經(jīng)典模型下考慮其它著名網(wǎng)絡(luò)拓?fù)涞拿總€頂點的g-好鄰局部診斷度。