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

引言

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

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

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

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

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

1確定（6，4）網絡故障點個數及具體位置

1.1 （6，4）網絡故障點個數的數據預處理

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

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

1.2（6，4）網絡故障點個數的PMC模型建立

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

在（6，4）網絡自診斷產生的報告中， R（U，V） 表示一個點 U 報告另外一個點 V ，即 U 表示（6，4）網絡自診斷產生的報告中一行中的一個點，V表示（6，4）網絡自診斷產生的報告中一列中的一個點。若一個本身無故障 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）網絡故障點個數的PMC模型，如表2所示。

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

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

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

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

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

通無故障的被檢測點（即一個點周圍均為無故障）時，將其組成一個單獨的集合。可視化全連通無故障的被檢測點，如圖2所示。

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

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

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

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

1.4（6，4）網絡故障點個數的PMC模型求解結果

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

1.5 （6，4）網絡故障點的具體位置

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

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

2 確定 （n，k） 網絡所有故障點個數

2.1數據預處理及 （n，k） 網絡故障點個數PMC模型的建立

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

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

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

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

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

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

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

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

2.3確定 （n，k） 網絡故障點個數的實例分析

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

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

3確定（6，4）網絡中（4，2）子網絡個數及破壞頂點個數

3.1確定（6，4）網絡中（4，2）子網絡個數

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

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

為確定（6，4）網絡中（4，2）子網絡個數，故令 n=6，k=4，m=2 ，代入公式（1）為：

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

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

3.2確定破壞（6，4）網絡中（4，2）子網絡的頂點個數

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

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

3.2.1基于枚舉法求解破壞（6，4）網絡中（4，2）子網絡的頂點個數

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

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

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

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

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

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

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

隨破壞頂點個數，（6.4）網絡中所有子網絡所包含的頂點個數變化圖，如圖7所示。

3.2.2破壞（6，4）網絡中（4，2）子網絡的頂點個數結果

運用枚舉法對（6，4）網絡破壞（4，2）子網絡頂點個數的求解結果為：破壞（6.4）網絡中的所有（4，2）子網絡，至少需要破壞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）網絡破壞（4，2）子網絡42個頂點，如圖8所示。3.2.3（6，4）網絡破壞（4，2）子網絡頂點個數的結果檢驗

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

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

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

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

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

4結論

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

參考文獻：

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

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

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

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

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

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

[7]馮凱，馬鑫玉 .（n，k）. 冒泡排序網絡的子網絡可靠性[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]肖瑤，郭帥，楊震，等.序列式低軌星座全連通網絡拓撲結構設計方法[J].航空學報，2023，44（24）：4-11.

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

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

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

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

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

[15]陳錢，陳康康，董興建，等.一種面向機械設備故障診斷的可解釋卷積神經網絡[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

（責任編輯：馬乃玉）