(6，4)網(wǎng)絡故障點及破壞(4，2)子網(wǎng)絡的研究

引言

多處理器系統(tǒng)的應用領域廣泛，成為解決科學與工程計算領域的必備工具，但多處理器系統(tǒng)由于物理磨損、電磁干擾以及自身壽命等原因容易發(fā)生故障，故多處理器系統(tǒng)在設計或者選擇超立方體網(wǎng)絡時，必須考慮超立方體網(wǎng)絡的容錯性[1-2]，否則會影響多處理器系統(tǒng)的正常運作。 （n，k）. 星圖網(wǎng)絡[3作為超立方體網(wǎng)絡拓撲結構的一個很好替代，有更小的點度、更短的直徑以及更高的容錯性，同時還保留了點邊對稱，層次結構等星圖的性質。PMC（Pairwise MultipleComparison）模型[4]作為經(jīng)典的系統(tǒng)級故障診斷模型，可以診斷多處理器系統(tǒng)的故障，故可使用PMC模型對 （n，k）. -星圖網(wǎng)絡進行故障診斷，進而確定 （n，k）. 星圖網(wǎng)絡中故障點個數(shù)。

針對 -星圖網(wǎng)絡（簡稱 （n，k） 網(wǎng)絡）容錯性問題，采用改進自適應順序診斷算法、深度優(yōu)先遍歷算法、枚舉法等5，解決如下3個問題：

（1）在（6，4）網(wǎng)絡中，設定故障頂點的個數(shù)不會超過5個，根據(jù)（6，4）網(wǎng)絡一次自診斷產生的報告，求解出（6，4）網(wǎng)絡中的所有故障點個數(shù)以及所有故障點個數(shù)的具體位置；

（2）將（6，4）網(wǎng)絡擴展到 （n，k） 網(wǎng)絡中，即在 （n，k） 網(wǎng)絡中設定一個點周圍不全是故障點，根據(jù) （n，k） 網(wǎng)絡以此自診斷產生的報告，需求出 （n，k） 網(wǎng)絡中的所有故障點個數(shù);

（3）若 （n，k） 網(wǎng)絡所包含的所有子網(wǎng)絡都被破壞，則 （n，k） 網(wǎng)絡一些功能不能實現(xiàn)。（6，4）網(wǎng)絡中包含多少個不同的（4，2）子網(wǎng)絡，如果要破壞（6，4）網(wǎng)絡中的所有（4，2）子網(wǎng)絡，那么至少要破壞幾個頂點，且如何破壞。

1確定（6，4）網(wǎng)絡故障點個數(shù)及具體位置

1.1 （6，4）網(wǎng)絡故障點個數(shù)的數(shù)據(jù)預處理

針對（6，4）網(wǎng)絡自診斷產生報告中提供的 3600×3600 組數(shù)據(jù)，即（6，4）網(wǎng)絡自診斷產生報告數(shù)據(jù)表，如表1所示，進行數(shù)據(jù)預處理]

在表1中，遍歷（6，4）網(wǎng)絡自診斷產生報告中的每一個點，提取出（6，4）網(wǎng)絡自診斷產生報告中37組\"-1\"對應的故障點數(shù)據(jù)，構成（6，4）網(wǎng)絡故障可疑點集合；同時提?。?，4）網(wǎng)絡自診斷產報告中，“1\"對應的數(shù)據(jù)為無故障點數(shù)據(jù)，構成（6，4）網(wǎng)絡無故障點集合。（6，4）網(wǎng)絡37組數(shù)據(jù)故障可疑點提取圖，如圖1所示。

1.2（6，4）網(wǎng)絡故障點個數(shù)的PMC模型建立

PMC模型的工作原理為：當測試者處于無故障狀態(tài)時，可以準確判斷被測試者的狀態(tài)，說明無故障測試者所測試的結果是可靠的；當測試者處于故障狀態(tài)時，被測試者狀態(tài)的結果是隨機出現(xiàn)的，說明故障測試者所測試的結果不可靠。

在（6，4）網(wǎng)絡自診斷產生的報告中， R（U，V） 表示一個點 U 報告另外一個點 V ，即 U 表示（6，4）網(wǎng)絡自診斷產生的報告中一行中的一個點，V表示（6，4）網(wǎng)絡自診斷產生的報告中一列中的一個點。若一個本身無故障 U 報告另外一個點 V 無故障，則R（U，V）=1 ;若一個點 U 為故障，報告另外一個點 V可能為無故障或者有故障，則所得測試結果不可靠，且 R（U，V）=-1 。

由PMC模型結論可知：若 R（U，V）=1 ，則 U，V 中至少一個是故障的;若 R（U，V）=0^[7] ，則 U，V 均是無故障的。

總之，若 ，則 U，V 中至少一個是無故障的；若 R（U，V）=1 ，則 U，V 均是無故障的。（6，4）網(wǎng)絡故障點個數(shù)的PMC模型，如表2所示。

1.3基于改進自適應順序診斷算法對（6，4）網(wǎng)絡故障點個數(shù)的PMC模型求解

改進自適應順序診斷算法[8]，需先準備一個可以輪回的測試，即（6，4）網(wǎng)絡自診斷產生報告的每一列相加得到的數(shù)據(jù)集合。從數(shù)據(jù)集合中選擇節(jié)點進行測試，進而診斷出部分節(jié)點的故障狀態(tài)，在上一個診斷結果的基礎之上進行下一次的輪回測試，直到所有數(shù)據(jù)集合中節(jié)點的故障狀態(tài)可以確定。

由于（6，4）網(wǎng)絡37組數(shù)據(jù)故障可疑點中，必有故障頂點的個數(shù)不會超過5個，故采用改進自適應順序診斷算法，對（6，4）網(wǎng)絡故障點9個數(shù)的PMC模型進行求解，有如下4個具體步驟：

第1步：將（6，4）網(wǎng)絡自診斷產生報告中每一個被檢測值的結果相加（即為（6，4）網(wǎng)絡自診斷產生報告的每一列相加），故得出數(shù)據(jù)集合。

第2步：在（6，4）網(wǎng)絡自診斷產生報告中，行為測試點的報告，列為被檢測點的報告。當被檢測值為全連

通無故障的被檢測點（即一個點周圍均為無故障）時，將其組成一個單獨的集合?？梢暬B通無故障的被檢測點，如圖2所示。

第3步：數(shù)據(jù)集合中第一個點開始對（6，4）網(wǎng)絡自診斷產生的報告進行輪回測試，進而診斷出節(jié)點的故障狀態(tài)。若得到值為-1的點，則需記錄此點，直至整個輪回結束。

第4步：開始選擇數(shù)據(jù)集合中的第二個集合點，繼續(xù)進行輪回，直到輪回結束為止，以此類推，直至數(shù)據(jù)集合中的所有點均進行輪回測試。

改進自適應順序診斷算法通過引入動態(tài)調整機制、自適應策略和減少通信開銷，在診斷精度、時間和系

統(tǒng)負載方面優(yōu)于無改進的自適應順序診斷算法。若采用改進自適應順序診斷算法在360×360 組數(shù)據(jù)中尋找故障點，則故障點尋找時間為1.052002秒；若采用未改進自適應診斷算法在 360×360 組數(shù)據(jù)中尋找故障點，則故障點尋找時間為2.105742秒，故可知采用改進自適應順序診斷算法尋找故障點為較優(yōu)算法。

1.4（6，4）網(wǎng)絡故障點個數(shù)的PMC模型求解結果

采用改進自適應順序診斷算法，從（6，4）網(wǎng)絡37組數(shù)據(jù)故障可疑點中，對（6，4）網(wǎng)絡故障點的PMC模型求解的結果為：（6，4）網(wǎng)絡中所有故障點共有5個，分別為1426、3416、4216、5416和6412?？梢暬?，4）網(wǎng)絡中5個故障點，如圖3所示。

1.5 （6，4）網(wǎng)絡故障點的具體位置

通過對（6，4）網(wǎng)絡故障點個數(shù)求解，可知（6，4）網(wǎng)絡故障點有5個，分別為：1426、3416、4216、5416和6412，采用深度優(yōu)先遍歷算法[10]，根據(jù)（6，4）網(wǎng)絡鄰接矩陣創(chuàng)建（6，4）網(wǎng)絡無向圖，其中（6，4）網(wǎng)絡中5個故障點為紅色，其余點為白色。（6，4）網(wǎng)絡故障點位置圖，如圖4所示。

總之，針對求解（6，4）網(wǎng)絡故障點個數(shù)的問題，首先，對（6，4）網(wǎng)絡自診斷產生的報告進行數(shù)據(jù)預處理，篩選出37組\"-1\"對應的故障可疑點數(shù)據(jù)，可知在37組報錯數(shù)據(jù)中至多有5個故障點。其次，構建（6，4）網(wǎng)絡故障點的PMC模型，采用改進自適應順序診斷算法對（6，4）網(wǎng)絡故障點的PMC模型進行求解。最后，計算得出（6，4）網(wǎng)絡中所有故障點共有5個，分別為1426、3416、4216、5416和6412，并標識出（6，4）網(wǎng)絡中這5個故障點的具體位置。

2 確定 （n，k） 網(wǎng)絡所有故障點個數(shù)

2.1數(shù)據(jù)預處理及 （n，k） 網(wǎng)絡故障點個數(shù)PMC模型的建立

對于 （n，k） 網(wǎng)絡自診斷產生報告中的數(shù)據(jù)進行預處理，提取 （n，k） 網(wǎng)絡自診斷產生報告中“-1\"對應的故障點數(shù)據(jù)集合，同時提取 （n，k） 網(wǎng)絡自診斷產生的報告中“1\"對應的數(shù)據(jù)，即無故障點數(shù)據(jù)。

在 （n，k） 網(wǎng)絡自診斷產生的報告中，一行中的點報告一列中的點，即 U 報告 V_? 。如果兩個點不相鄰，那么R（U，V）=0 ；如果一個點 U 本身無故障報告另外一個點V無故障時，那么 R（U，V）=1 ;如果一個點 U 為故障，報告另外一個點V可能為無故障或者有故障時，那么所得測試結果不可靠，即 。

（n，k） 網(wǎng)絡故障點個數(shù)的PMC模型為：若 R（U，V）=0 ，則 U，V 兩點不相鄰；若 R（U，V）=-1 ，則U，V中至少一個是無故障的;若 R（U，V）=1 ，則 U，V 均是無故障的。

2.2基于改進自適應順序診斷算法對 （n，k） 網(wǎng)絡故障點個數(shù)的求解

根據(jù)改進自適應診斷算法求解（6，4）網(wǎng)絡故障點個數(shù)的思路，將改進自適應診斷算法推廣到 （n，k） 網(wǎng)絡中。首先，在 （n，k） 網(wǎng)絡自診斷產生報告中，將每一列相加得到數(shù)據(jù)集合，在該數(shù)據(jù)集合中進行一個輪回測試；再在 （n，k） 網(wǎng)絡數(shù)據(jù)集合中選取節(jié)點進行測試，進而診斷出部分節(jié)點的故障狀態(tài);然后在上一個診斷結果的基礎上進行下一次的輪回測試，直到所有數(shù)據(jù)集合中節(jié)點的故障狀態(tài)可以確定。采用改進自適應診斷算法，對 （n，k） 網(wǎng)絡故障點個數(shù)求解的具體步驟為：

第1步：將 （n，k） 網(wǎng)絡自診斷產生報告中每一個被檢測值的結果相加，得出數(shù)據(jù)集合。第2步：在 （n，k） 網(wǎng)絡自診斷產生報告中，在被檢測值為全連通無故障的被檢測點，將全連通無故障被檢測點組成一個單獨的集合。

第3步：從數(shù)據(jù)集合中的第一個點開始對 （n，k） 網(wǎng)絡自診斷產生的報告進行輪回測試，進而診斷節(jié)點的故障狀態(tài)。如果得到值為-1的點，那么需要記錄此點，直到整個輪回結束。

第4步：選擇數(shù)據(jù)集合中的第二個集合點，繼續(xù)進行輪回，直到數(shù)據(jù)集合中的所有點均進行輪回測試為止，最終得出 （n，k） 網(wǎng)絡故障點個數(shù)。

2.3確定 （n，k） 網(wǎng)絡故障點個數(shù)的實例分析

在 （n，k） 網(wǎng)絡中，以（7，4）網(wǎng)絡實例，采用改進自適應順序診斷算法，對（7，4）網(wǎng)絡故障點個數(shù)進行求解。

首先，需要對（7，4）網(wǎng)絡自診斷產生的報告進行數(shù)據(jù)預處理，實現(xiàn)數(shù)據(jù)篩選，從而得到112組故障點數(shù)據(jù)。若一個點周圍六個點均為故障，則無法判斷中間點是否為故障點;若一個點周圍六個點不全為故障點，則可以判斷中間點是否為故障點。其次，構建（7，4）網(wǎng)絡故障點的PMC模型，采用改進自適應診斷算法，得出全連通無故障的被檢測點的數(shù)據(jù)集合。從集合中的第一個點開始，若得到-1，則需記錄此點，直至整個輪回結束，周而復始，直到數(shù)據(jù)集合中的所有點均進行輪回為止。最后，計算得出（7，4）網(wǎng)絡中所有故障點共有12個，分別為2465、2643、2763、3741、4523、4527、4756、5162、5716、6153和7653。

3確定（6，4）網(wǎng)絡中（4，2）子網(wǎng)絡個數(shù)及破壞頂點個數(shù)

3.1確定（6，4）網(wǎng)絡中（4，2）子網(wǎng)絡個數(shù)

馮凱提出子網(wǎng)絡組合排列理論： S_n，k 中共有 個不同的 S_n-m，k-m 子網(wǎng)絡，且任意一個S_n-m，k-m 子網(wǎng)絡可用某個 唯一表示，其中 1?m?k-1 。

根據(jù)上述理論，設 S_n，k 為 （n，k） 網(wǎng)絡， S_n-m，k-m 為子網(wǎng)絡，那么（6，4）網(wǎng)絡為 S_6，4，（4，2） 子網(wǎng)絡為 S_4，2 ，由 與 n ！相乘，再用乘積除以 （n-m）！ ，得出公式：

為確定（6，4）網(wǎng)絡中（4，2）子網(wǎng)絡個數(shù)，故令 n=6，k=4，m=2 ，代入公式（1）為：

進而由公式（2）得出：（6，4）網(wǎng)絡含有90個不同的（4，2）子網(wǎng)絡。

可視化（6，4）網(wǎng)絡中90個不同的（4，2）子網(wǎng)絡及頂點[1]，如圖5所示。

3.2確定破壞（6，4）網(wǎng)絡中（4，2）子網(wǎng)絡的頂點個數(shù)

為破壞（6，4）網(wǎng)絡中的所有（4，2）子網(wǎng)絡[12]，需求解出至少破壞頂點個數(shù)，進而制定出對應的（4，2）子網(wǎng)絡破壞策略。在（6，4）網(wǎng)絡中擁有90個不同的（4，2）子網(wǎng)絡，但在（6，4）網(wǎng)絡頂點中出現(xiàn)將所有（4，2）子網(wǎng)絡

中的點覆蓋，而不會有單獨一個點未被覆蓋的情況可視化（6，4）網(wǎng)絡的（4，2）子網(wǎng)絡覆蓋，如圖6所示。

3.2.1基于枚舉法求解破壞（6，4）網(wǎng)絡中（4，2）子網(wǎng)絡的頂點個數(shù)

通過枚舉法，列舉在（6，4）網(wǎng)絡中所有四位不相同數(shù)字組合的所有可能，將所有狀態(tài)逐一與目標狀態(tài)進行比較，從而得到滿足所有組合的特定位置數(shù)據(jù)與固定點數(shù)據(jù)相同組合的解。

采用枚舉法，對（6，4）網(wǎng)絡需要破壞（4，2）子網(wǎng)絡頂點個數(shù)進行求解，有如下4個步驟：

第1步：通過嵌套[13]生成4位不相同數(shù)字可能的所有組合，將4位不相同的數(shù)字組合成矩陣，故可以把由4位不同數(shù)字組合成的矩陣作為（6，4）網(wǎng)絡的頂點編號。

第2步：需要經(jīng)過嵌套迭代尋找固定點的組合，并從生成的所有組合中，篩選出滿足特定條件（即所有組

合的特定位置數(shù)據(jù)與固定點數(shù)據(jù)相同）的組合。在滿足放到一個臨時存儲空間的前提下，需要尋找所有可能的組合，與此同時，需要觀察臨時存儲空間中的數(shù)據(jù)是否為一個子圖的數(shù)據(jù)。若臨時存儲空間中的數(shù)據(jù)為一個子圖的數(shù)據(jù)，則需要把滿足特定條件的所有組合放到總存儲列表中，否則需要把臨時存儲空間記為空。

第3步：通過統(tǒng)計在總列表（所有子網(wǎng)絡形成）中每個組合（即（6，4）網(wǎng)絡中每個頂點）出現(xiàn)的次數(shù)，并將每個組合按照降序排列形成一個新的集合。

第4步：去除集合中按降序[14]排列的第一個組合，將集合中剩余組合返回到第二步當中，繼續(xù)進行迭代。以此類推，直到?jīng)]有（4，2）子網(wǎng)絡結束為止。

隨破壞頂點個數(shù)，（6.4）網(wǎng)絡中所有子網(wǎng)絡所包含的頂點個數(shù)變化圖，如圖7所示。

3.2.2破壞（6，4）網(wǎng)絡中（4，2）子網(wǎng)絡的頂點個數(shù)結果

運用枚舉法對（6，4）網(wǎng)絡破壞（4，2）子網(wǎng)絡頂點個數(shù)的求解結果為：破壞（6.4）網(wǎng)絡中的所有（4，2）子網(wǎng)絡，至少需要破壞42個頂點，分別為1234、1243、1256、1265、1324、1342、1423、1432、1526、1562、1625、1652、2135、2146、2153、2164、2315、2351、2416、2461、2513、2531、2614、2641、1236、1245、1254、1263、1326、1362、1425、1452、1524、1542、1623、1632、3124、3142、3214、3241、3412和3421。

可視化（6，4）網(wǎng)絡破壞（4，2）子網(wǎng)絡42個頂點，如圖8所示。3.2.3（6，4）網(wǎng)絡破壞（4，2）子網(wǎng)絡頂點個數(shù)的結果檢驗

馮凱提出： 為在 S_n，k 中使每個 S_n-m，k-m 變得有故障的最小故障頂點數(shù)（在系統(tǒng)的頂點故障模型下）[15]，其中 1?k?n-2 和 2?j?k-2 ，即：

對（6，4）網(wǎng)絡破壞（4，2）子網(wǎng)絡頂點個數(shù)中，在滿足 1?k?n-2 和 2?j?k-2 的前提下，令 n=6，k=4 j=2 ，代人公式（3）為：

由（4）式計算可得，（6，4）網(wǎng)絡破壞（4，2）子網(wǎng)絡頂點個數(shù)范圍為 30～48 。

破壞（6，4）網(wǎng)絡中的所有（4，2）子網(wǎng)絡，實際求解出至少需要破壞42個頂點，屬于（6，4）網(wǎng)絡破壞（4，2）子網(wǎng)絡頂點個數(shù) 30～48 范圍之內，故檢驗出破壞（6，4）網(wǎng)絡中的所有（4，2）子網(wǎng)絡，至少需要破壞42個頂點的可靠性高。

總之，為破壞（6，4）網(wǎng)絡中的所有（4，2）子網(wǎng)絡，求解出至少需要破壞42個頂點，制定出對應的（4，2）子網(wǎng)絡破壞策略為：按照降序排列進行新集合的生成過程中，將影響較大的頂點放在首位，即從影響子網(wǎng)絡最大的頂點開始破壞，一直破壞到42個頂點為止。

4結論

多處理器系統(tǒng)在設計或選擇 （n，k） 網(wǎng)絡時，須考慮 （n，k） 網(wǎng)絡的容錯。通過構建（6，4）網(wǎng)絡和 （n，k） 網(wǎng)絡故障診斷PMC模型，用于診斷多處理器系統(tǒng)的故障，采用改進自適應診斷算法、深度優(yōu)先遍歷算法和枚舉法，確定（6，4）網(wǎng)絡和 （n，k） 網(wǎng)絡中故障點個數(shù)和故障點的具體位置，以及（6，4）網(wǎng)絡破壞（4，2）子網(wǎng)絡的頂點個數(shù)。由于 （n，k） 網(wǎng)絡故障點PMC模型具有高效性和可靠性高的特點，可快速求得 （n，k） 網(wǎng)絡故障點個數(shù)，故可將 （n，k） 網(wǎng)絡故障點PMC模型的應用推廣到人工智能、科學與工程計算領域等方面。

參考文獻：

[1]李麗娜，原軍.具有缺弧和失效點的單定向超立方體的診斷度[J].太原科技大學學報，2024，4（3）：1-2

[2]范詩悅.鐵路通信網(wǎng)絡的可靠性與容錯性分析[J].電子技術，2024，53（2）：1-2.

[3]王世英，王琛.泡型星圖網(wǎng)絡的3限制診斷度（英文）[J].廣州大學學報（自然科學版），2021，20（1）：4-6.

[4]方思越，劉清.政策文獻量化研究中的PMC指數(shù)模型應用述評[J].現(xiàn)代情報，2024，44（4）：2-3.

[5]李吉俊，董自健.基于最近鄰值和枚舉法的車號字符分割及拼接方法[J].江蘇海洋大學學報（自然科學版），2022，31（1）：5-9.

[6]徐敏，王平.基于深度LSTM殘差網(wǎng)絡的旋轉機械故障診斷研究[J].機床與液壓，2023，51（4）：2-4.

[7]馮凱，馬鑫玉 .（n，k）. 冒泡排序網(wǎng)絡的子網(wǎng)絡可靠性[J].計算機科學，2021，48（4）：1-4.

[8]張梓心，曾慧，吳軍剛，等.基于輪回選擇的玉米自交系J1644雜交種選育及配合力分析[J/OL].分子植物育種，1[2024-06-04]htp：/kns.

cnki.net/kcms/detail/46.1068.s.20221219.1327.006.html：10-11.

[9]肖瑤，郭帥，楊震，等.序列式低軌星座全連通網(wǎng)絡拓撲結構設計方法[J].航空學報，2023，44（24）：4-11.

[10]馬新宇.基于深度優(yōu)先的鐵路站場圖遍歷算法研究[J].價值工程，2023，42（6）：1-2.

[11]劉泳杏，楊風，柏慧，等.基于CiteSpace互聯(lián)網(wǎng)醫(yī)院研究進展與趨勢可視化分析[J].醫(yī)學信息，2024，37（10）：2-3.

[12]楊騰，寧芊，陳炳才.基于小波變換和殘差神經(jīng)網(wǎng)絡模型的軸承故障診斷[J].現(xiàn)代計算機，2021（15）：2-4.

[13]田小潤，李晶，張建秀.含故障邊的k元4立方體中的哈密爾頓性[J].太原科技大學學報，2022，43（4）：1-5.

[14]張傳軍，趙海清.半群PC_n的極大冪等元生成子半群[J].山東大學學報（理學版），2021，56（12）：2-3.

[15]陳錢，陳康康，董興建，等.一種面向機械設備故障診斷的可解釋卷積神經(jīng)網(wǎng)絡[J/OL].機械工程學報，1[2024-07-18].htp：/kns.cnki.net/kc-ms/detail/11.2187.TH.20240204.1632.012.html：2-5

Research on （6，4） Network Fault Points and Destructive （4，2） Subnetworks

XIE Hui'，ZHANG Jian-guo2，KANG Xin-shu'，LI Xin2，BAI Jing-qi3 （1.Departai;t sity，Jinzhong9tiolodtoUityo

Abstract： Aiming at the problem of the number of fault points in the （n，k） network， the PMC model of the fault points in the （6，4） network and （n，k） network is established，and the number of fault points in the （6，4） network and （n，k） network is obtained by using the improved adaptive sequential diagnosis algorithm，and the specific location of the fault points in the ^（6，4） network is identified by the depth-first traversal algorithm. The number of （4，2） subnetworks in （6，4） networks is calculated according to the combination and arrangement theory of subnetworks. Enumeration method is used to obtain the vertices of the （4，2） subnetwork in the（6，4）network，and verify the reliability of the Vertices of the （4，2） subnetwork，and then develop the strategy of destroying the（4，2） subnetwork in the（6，4） network.

Keywords： （n，k） network；improved adaptive sequential diagnosis algorithm； depth-first traversal algorithm; enumeration method

（責任編輯：馬乃玉）