摘要：條件診斷性綜述

（西華大學(xué)計(jì)算機(jī)與軟件工程學(xué)院，四川 成都 610039）

1 研究意義

2019 年6 月在德國法蘭克福舉行的第34 屆國際超級計(jì)算大會上，國際組織“TOP500”公布了最新一期全球超級計(jì)算機(jī)500 強(qiáng)榜單，中國的神威·太湖之光和天河二號繼續(xù)名列第三和第四位，中國共有219 臺超級計(jì)算機(jī)上榜，上榜數(shù)量位列第一，美國和日本分別以116 臺和29 臺超級計(jì)算機(jī)上榜，上榜數(shù)量分別位列第二、第三，這意味著中國超級計(jì)算機(jī)的發(fā)展已處于世界領(lǐng)先水平[1]。超級計(jì)算機(jī)能為能源、醫(yī)藥、飛機(jī)制造、航空航天、國家安全、娛樂業(yè)等廣泛領(lǐng)域提供高性能計(jì)算服務(wù)，從而提升國家的科研實(shí)力和綜合國力，增強(qiáng)國家的競爭力，對國家安全、高科技發(fā)展、經(jīng)濟(jì)和社會發(fā)展具有舉足輕重的意義。

《國家中長期科技發(fā)展規(guī)劃綱要（2006—2020）》明確把“高效能可信計(jì)算機(jī)”和“下一代網(wǎng)絡(luò)關(guān)鍵技術(shù)與服務(wù)”列為重點(diǎn)領(lǐng)域“信息產(chǎn)業(yè)及現(xiàn)代服務(wù)業(yè)”的優(yōu)先主題，把研制高性能、高可信計(jì)算機(jī)和高性能的核心網(wǎng)絡(luò)設(shè)備與傳輸設(shè)備、接入設(shè)備作為信息產(chǎn)業(yè)的戰(zhàn)略重點(diǎn)。超級計(jì)算是在超級計(jì)算機(jī)上實(shí)現(xiàn)的并行計(jì)算，通常超級計(jì)算、高性能計(jì)算、并行計(jì)算三者不加區(qū)分。并行計(jì)算是提高計(jì)算機(jī)系統(tǒng)計(jì)算速度和處理能力的一種有效手段，其基本思想是將較大規(guī)模的任務(wù)分解為多個較小規(guī)模的子任務(wù)，并分配給不同的處理器，各個處理器之間相互協(xié)同、并行地執(zhí)行子任務(wù)，從而達(dá)到加快求解問題的目的。在并行計(jì)算機(jī)的計(jì)算過程中，各個子任務(wù)會分配給不同處理器進(jìn)行處理，處理器之間需要相互通信來進(jìn)行數(shù)據(jù)交換，所需的通信時間與處理時間不可忽視。因此，各處理器之間按照一定方式相互連接所形成的互連網(wǎng)絡(luò)的容錯性和診斷性成為衡量并行計(jì)算機(jī)系統(tǒng)性能的重要指標(biāo)。網(wǎng)絡(luò)的結(jié)構(gòu)性質(zhì)直接反映了系統(tǒng)的性質(zhì)，對網(wǎng)絡(luò)結(jié)構(gòu)深層次地進(jìn)行故障診斷性分析，不斷獲得新的診斷性理論與方法，有利于“高效能可信計(jì)算”的實(shí)現(xiàn)和“下一代網(wǎng)絡(luò)關(guān)鍵技術(shù)與服務(wù)”的突破。

在高性能計(jì)算機(jī)的發(fā)展中，超大規(guī)模并行處理已成為主流體系結(jié)構(gòu)。隨著超大規(guī)模集成技術(shù)和微電子技術(shù)的飛速發(fā)展，單個處理器的性能不斷提高、體積不斷縮小，超大規(guī)模并行處理系統(tǒng)可以集成成千上萬個處理器，同時為了滿足用戶的高可用性需求，系統(tǒng)的內(nèi)部結(jié)構(gòu)也變得越來越復(fù)雜，因此，系統(tǒng)呈現(xiàn)出大規(guī)模性、極度復(fù)雜性、異構(gòu)性等特點(diǎn)。

互連網(wǎng)絡(luò)有效地實(shí)現(xiàn)了處理器之間的通信，它已滲透到社會生活的各個領(lǐng)域。隨著系統(tǒng)中處理器數(shù)目的急劇增加，處理器出現(xiàn)故障的概率不斷增大。當(dāng)具有大量處理器的系統(tǒng)（多計(jì)算機(jī)系統(tǒng)）發(fā)生故障時，系統(tǒng)難以判斷處理器故障類型、位置和原因，易出現(xiàn)診斷精度和診斷速度低下、誤診、漏診等現(xiàn)象，降低了系統(tǒng)的服務(wù)質(zhì)量。金融、證券、軍事、航空航天等國家級重點(diǎn)行業(yè)，對系統(tǒng)的可靠性和可用性要求極高，一旦系統(tǒng)出現(xiàn)故障，勢必會帶來不可估量的損失。因此，對網(wǎng)絡(luò)進(jìn)行多故障診斷性分析，并構(gòu)建高效的多故障診斷算法迫在眉睫。由于網(wǎng)絡(luò)中大量故障結(jié)點(diǎn)呈隨機(jī)分布特性，因此本文從子網(wǎng)絡(luò)性質(zhì)、條件故障診斷度和條件故障診斷策略設(shè)計(jì)3 方面研究網(wǎng)絡(luò)的多故障診斷性。

2 互連網(wǎng)絡(luò)的故障診斷性的研究現(xiàn)狀

當(dāng)多計(jì)算機(jī)系統(tǒng)出現(xiàn)故障處理器時，計(jì)算機(jī)在進(jìn)行信息存儲、信息處理、信息傳輸過程中出錯的可能性增大。為了保證系統(tǒng)的高可用性，一種診斷故障處理器或故障部件（結(jié)點(diǎn)）的有效方式是借助多計(jì)算機(jī)系統(tǒng)強(qiáng)大的計(jì)算能力和通信能力，獲取結(jié)點(diǎn)有無故障的狀態(tài)信息，即癥候，然后再對其進(jìn)行分析，確定故障結(jié)點(diǎn)。研究者們基于測試途徑和比較途徑這2 種獲取癥候的有效方式，提出了許多不同的診斷模型，其中基于測試途徑的診斷模型有PMC 模型、BGM 模型等，基于比較途徑的診斷模型有Malek 模型、Chwa-Hakimi 模型、Maeng-Malek模型、比較模型等。在這些診斷模型中，PMC 模型和比較模型是2 類經(jīng)典的診斷模型。基于這2 類模型，學(xué)者們對不同互連網(wǎng)絡(luò)的故障診斷性進(jìn)行了研究，獲得了大量的研究成果。下面從（強(qiáng)）診斷度、條件診斷度、g-好鄰居條件診斷度、g-額外條件診斷度、診斷算法和二進(jìn)制遞歸網(wǎng)絡(luò)6 方面介紹網(wǎng)絡(luò)故障診斷性領(lǐng)域的研究現(xiàn)狀和存在的問題。

2.1 （強(qiáng)）診斷度和條件診斷度研究現(xiàn)狀

基于PMC 模型和比較模型，研究者們假設(shè)系統(tǒng)中處理器相鄰結(jié)點(diǎn)可以同時出現(xiàn)故障，對系統(tǒng)的診斷度進(jìn)行了大量的研究。Song 等[2]運(yùn)用圖分層的方法，研究了煎餅網(wǎng)絡(luò)的診斷度。Lin 等[3]通過對無三角形網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)性質(zhì)的研究，獲得了它的診斷度。Li 等[4]研究了多網(wǎng)格超立方體網(wǎng)絡(luò)的診斷度?？梢?，對于網(wǎng)絡(luò)診斷度的研究主要針對的是規(guī)則網(wǎng)絡(luò)，不規(guī)則網(wǎng)絡(luò)結(jié)構(gòu)的診斷度還未形成統(tǒng)一的研究方法。

這些系統(tǒng)診斷度都不會超過系統(tǒng)的最小頂點(diǎn)度，系統(tǒng)診斷能力極其有限，究其原因在于這種診斷度研究的前提假設(shè)是未考慮系統(tǒng)中處理器故障出現(xiàn)具有不同概率的情況。在多計(jì)算機(jī)系統(tǒng)中，處理器出現(xiàn)故障的概率是相對獨(dú)立的，而且各處理器出現(xiàn)故障的概率也不相同。因此，對于系統(tǒng)中每個處理器而言，它的所有鄰接處理器都出現(xiàn)故障的概率相當(dāng)小，幾乎可以忽略不計(jì)。基于這樣的考慮，Lai 等[5]提出了系統(tǒng)的強(qiáng)診斷和條件故障診斷的概念，并運(yùn)用圖論方法在PMC 模型下確定了匹配符合網(wǎng)絡(luò)和超立方體的條件故障診斷度，這種條件診斷度的提出增強(qiáng)了多處理器系統(tǒng)的診斷能力。強(qiáng)診斷度和條件診斷度的提出，提升了系統(tǒng)的故障診斷能力，開啟了大量其他網(wǎng)絡(luò)的強(qiáng)診斷度和條件診斷度研究。

隨后，在PMC 模型和比較模型下，Hsieh 等[6]和Chang 等[7]確定了k元n立方體的條件診斷度；Yang[8 ? 9]確定了平衡超立方體的條件診斷度；Li 等[10]和Li[11]研究了多網(wǎng)格超立方體光網(wǎng)絡(luò)的條件故障診斷，獲得了其強(qiáng)診斷度和條件診斷度；Lin 等[12]和Zhou 等[13]研究了洗牌立方體和分層立方體的強(qiáng)診斷度和條件診斷度；Guo 等[14]研究了環(huán)繞匹配符合網(wǎng)絡(luò)的條件診斷度，運(yùn)用該結(jié)果獲得了k元n維立方體和遞歸循環(huán)圖的條件診斷度。在PMC模型下，Lin 等[15]建立了正則圖的3-額外連通度與條件診斷度之間的關(guān)系。在比較模型下，Lin 等[16]和Hao 等[17]利用額外連通度分析確定了正則圖和對稱差圖網(wǎng)絡(luò)的條件診斷度；Xu 等[18]研究了匹配符合網(wǎng)絡(luò)的條件診斷度。這些條件診斷度的研究依然是針對規(guī)則網(wǎng)絡(luò)結(jié)構(gòu)，利用圖結(jié)構(gòu)性質(zhì)獲得的，未研究的規(guī)則網(wǎng)絡(luò)和一般網(wǎng)絡(luò)的條件診斷度仍然值得探索。

對于一般網(wǎng)絡(luò)結(jié)構(gòu)，在PMC 模型下，Cheng 等[19]獲得了任意圖的條件診斷度的一個緊的上界，并應(yīng)用這個結(jié)果推導(dǎo)出了星圖的條件診斷度；Stewart[20]提出了確定一類互連網(wǎng)絡(luò)條件診斷度的方法，運(yùn)用該方法可以直接確定超立方體、折疊立方體等立方體網(wǎng)絡(luò)的條件診斷度。在比較模型和PMC 模型下，Zhu 等[21]研究了一類互連網(wǎng)路，包括BC 網(wǎng)絡(luò)、折疊立方體、置換星圖、超網(wǎng)格等的故障診斷性，建立了該網(wǎng)絡(luò)的診斷度、強(qiáng)診斷度和條件診斷度之間的關(guān)系?？蒲姓卟粌H研究規(guī)則網(wǎng)絡(luò)結(jié)構(gòu)的強(qiáng)診斷性和條件診斷性，還研究一般網(wǎng)絡(luò)的強(qiáng)診斷性和條件診斷性，并試圖用一種通用的模式來解決不同網(wǎng)絡(luò)的故障診斷性；但是所提出的模式僅僅適用于帶有限定條件的一般網(wǎng)絡(luò)或者一類網(wǎng)絡(luò)：因此，具有不同條件的一般網(wǎng)絡(luò)和不同網(wǎng)絡(luò)組成的一類網(wǎng)絡(luò)的強(qiáng)診斷性和條件診斷性依然值得研究。

2.2 g-好鄰居條件診斷度和g-額外條件診斷度研究現(xiàn)狀

在多計(jì)算機(jī)系統(tǒng)中無故障結(jié)點(diǎn)的部分相鄰結(jié)點(diǎn)同時出現(xiàn)故障的概率非常小，幾乎可以忽略，基于這樣的考慮，Peng 等[22]進(jìn)一步延伸了條件診斷理論，假定任何無故障結(jié)點(diǎn)至少有g(shù)個無故障結(jié)點(diǎn)與之相鄰，提出了g-好鄰居條件診斷，并研究了超立方體在PMC 模型下的g-好鄰居條件診斷度。g-好鄰居條件診斷度極大地豐富了條件故障診斷的內(nèi)容，在一定程度上提高了對給定系統(tǒng)的故障診斷能力。Wang 等[23]進(jìn)一步研究了超立方體在比較模型下的g-好鄰居條件診斷度。在PMC 模型和比較模型下，Yuan 等[24]和Yuan 等[25]通過對三元n維立方體和k元n維立方體的Rg-連通性[26]的研究，確定了它們的g-好鄰居條件診斷度；Ren 等[27]確定了t-可診斷系統(tǒng)和完全圖的g-好鄰居條件診斷度；Ren 等[28]推導(dǎo)出了局部扭曲立方體的g-好鄰居條件診斷度。Li 等[29]獲得了星圖網(wǎng)絡(luò)的g-好鄰居條件診斷度；對于(n,k)-星圖網(wǎng)絡(luò)，當(dāng)1≤k≤n–1，1≤g≤n–k時，Xu 等[30]確定了該網(wǎng)絡(luò)的g-好鄰居條件診斷度。對于數(shù)據(jù)中心網(wǎng)絡(luò)Dcell，Li 等[31]研究了該網(wǎng)絡(luò)的g-好鄰居條件診斷度。對于傳遞樹生成的凱萊圖，Wang 等[32]和Wang 等[33]確定了它的1-和2-好鄰居條件診斷度。Wang 等[34]研究了交錯群圖的2-好鄰居條件診斷度?？梢?，g-好鄰居條件診斷度的研究主要是針對規(guī)則網(wǎng)絡(luò)，對于一般網(wǎng)絡(luò)和網(wǎng)絡(luò)簇的研究極少。g-好鄰居條件診斷度的研究還處在發(fā)展階段，研究方法還有待完善，大量互連網(wǎng)絡(luò)，如增廣立方體、分層立方體、多網(wǎng)格超立方體等的g-好鄰居條件診斷度亟待解決。因此，特定互連網(wǎng)絡(luò)、一般網(wǎng)絡(luò)和網(wǎng)絡(luò)簇的g-好鄰居條件診斷度是值得研究的問題。

考慮到多處理器中某個處理器的所有鄰居結(jié)點(diǎn)都出現(xiàn)故障的可能性極小，Zhang 等[35]推廣了條件診斷策略，假定系統(tǒng)出現(xiàn)故障后每個連通分支的結(jié)點(diǎn)數(shù)超過g，提出了g-額外條件診斷策略，并研究了超立方體的g-額外條件診斷度。隨后，Xu 等[36]利用這一新的診斷策略研究了排列圖網(wǎng)絡(luò)的故障診斷，獲得了排列圖網(wǎng)絡(luò)的1-、2-和3-額外條件診斷度；Wang 等[37]獲得了冒泡排序星圖網(wǎng)絡(luò)的2-額外條件診斷度；Wang 等[34]研究了交錯群圖的2-額外條件診斷度。Ren 等[27]確定了t-可診斷系統(tǒng)和完全圖的g-額外條件診斷度。Liu 等[38]在比較模型下，推導(dǎo)了超立方體和折疊立方體的g-額外條件診斷度。當(dāng)前，g-額外條件診斷度的研究還處于發(fā)展階段，未形成普遍適用的方法，大量網(wǎng)絡(luò)結(jié)構(gòu)的g-額外條件診斷度還有待確定。因此，特定互連網(wǎng)絡(luò)、一般網(wǎng)絡(luò)和網(wǎng)絡(luò)簇的g-額外條件診斷度也是值得研究的問題。

2.3 診斷算法研究現(xiàn)狀

近年來，研究人員針對常見的互連網(wǎng)絡(luò)設(shè)計(jì)了大量的診斷算法。在PMC 模型下，Tsai[39]對N個結(jié)點(diǎn)的類立方體提出了時間復(fù)雜度為O(N)的悲觀診斷算法；Zhu 等[40]運(yùn)用圖著色的方法，設(shè)計(jì)了一類適合于任何多處理器系統(tǒng)的故障診斷算法；Hsu 等[41]針對超網(wǎng)格結(jié)構(gòu)提出了一個線性時間診斷算法，至多能夠識別2n(k?1)?1個故障結(jié)點(diǎn)。在比較模型下，針對N個結(jié)點(diǎn)的類立方體，Ye 等[42]運(yùn)用圈分解性質(zhì)，提出了時間復(fù)雜度為O(N(log2N)2)的故障診斷算法，后來，Ye 等[43]運(yùn)用深度優(yōu)先算法找到最大分支，基于最大分支設(shè)計(jì)了一類時間復(fù)雜度為O(Nlog2N)的故障診斷算法；Liu 等[44]針對煎餅網(wǎng)絡(luò)利用擴(kuò)展星圖和哈密爾頓路結(jié)構(gòu)設(shè)計(jì)了一類線性時間算法。

當(dāng)前，在比較模型下的故障診斷算法比在PMC 模型下的故障診斷算法少得多，原因在于前者要比后者故障診斷復(fù)雜得多，需要借助的圖結(jié)構(gòu)性質(zhì)也較多。因此，在比較模型下設(shè)計(jì)高效的故障診斷算法還有待突破，同時針對特定互連網(wǎng)絡(luò)或網(wǎng)絡(luò)簇設(shè)計(jì)特定的故障診斷算法仍然是當(dāng)前的研究熱點(diǎn)。

2.4 二進(jìn)制遞歸網(wǎng)絡(luò)研究現(xiàn)狀

互連網(wǎng)絡(luò)是由若干處理器按照一定互連方式相互連接形成的網(wǎng)絡(luò)結(jié)構(gòu)。在并行處理器系統(tǒng)中，互連網(wǎng)絡(luò)作為其主干網(wǎng)絡(luò)，它的性能直接決定著整個系統(tǒng)性能的好壞?；ミB網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)性質(zhì)和多故障診斷性是決定互連網(wǎng)絡(luò)性能的2 個重要因素。二進(jìn)制遞歸網(wǎng)絡(luò)作為一類具有良好拓?fù)湫再|(zhì)和網(wǎng)絡(luò)參數(shù)的互連網(wǎng)絡(luò)模型，包含了超立方體、交叉立方體、扭曲立方體等，是一類具有廣闊應(yīng)用前景的超級計(jì)算機(jī)網(wǎng)絡(luò)和數(shù)據(jù)中心網(wǎng)絡(luò)結(jié)構(gòu)。超立方體因其具有正則性、對稱性、較小的網(wǎng)絡(luò)直徑、強(qiáng)連通性、對稱性以及結(jié)構(gòu)遞歸性等眾多優(yōu)良的網(wǎng)絡(luò)特性，成為實(shí)際應(yīng)用最廣泛、理論研究最多的一種網(wǎng)絡(luò)拓?fù)?。許多商業(yè)公司的科研人員基于超立方體結(jié)構(gòu)，先后研制了CM-2、nCube、Cosmic Cube、SGI Origin 2000 等并行計(jì)算機(jī)系統(tǒng)，并在神經(jīng)網(wǎng)絡(luò)、P2P 網(wǎng)絡(luò)、覆蓋網(wǎng)絡(luò)等領(lǐng)域進(jìn)行了深入的應(yīng)用研究。為既能保持超立方體這些良好特性，又能減小網(wǎng)絡(luò)的通信延遲(即降低網(wǎng)絡(luò)直徑)，人們對超立方體進(jìn)行了各種改造，得到了許多變體。在分析比較了大量超立方體的變體之后，發(fā)現(xiàn)某些變體和超立方體一樣，都具有相同頂點(diǎn)數(shù)、相同的邊數(shù)、相同的正則性和嚴(yán)格的遞歸性，即每個n維的網(wǎng)絡(luò)都是由2 個n–1 維的網(wǎng)絡(luò)按照某種特定關(guān)系組合而成的。Sun 等[45]將超立方體的這類變體歸納為一類二進(jìn)制遞歸網(wǎng)絡(luò)（binary recursive network,BR），用0 和1 組成的二進(jìn)制字符串對結(jié)點(diǎn)進(jìn)行標(biāo)記，并使用互連代數(shù)對其進(jìn)行了遞歸定義。

這樣，超立方體的不同變體，如扭曲立方體、局部扭曲立方體、折疊立方體、交叉立方體、M?bius 立方體、增廣立方體、加強(qiáng)立方體等二進(jìn)制立方形遞歸網(wǎng)絡(luò)實(shí)質(zhì)上是二進(jìn)制遞歸網(wǎng)絡(luò)的一個特殊子類，因此對二進(jìn)制遞歸網(wǎng)絡(luò)成立的拓?fù)湫再|(zhì)對二進(jìn)制立方形遞歸網(wǎng)絡(luò)同樣成立，但反之不然。一些文獻(xiàn)中提到的類超立方體網(wǎng)絡(luò)、BC 網(wǎng)絡(luò)、匹配符合網(wǎng)絡(luò)等也可看成是二進(jìn)制遞歸網(wǎng)絡(luò)的一些特殊形式。二進(jìn)制遞歸網(wǎng)絡(luò)子類的不同故障診斷度和診斷算法已經(jīng)有大量研究成果[45 ? 46]，但二進(jìn)制遞歸網(wǎng)絡(luò)在直徑、泛圈性、哈密爾頓性等方面的研究成果較少。因此，二進(jìn)制遞歸網(wǎng)絡(luò)的（強(qiáng)）診斷度、條件診斷度、g-好鄰居條件診斷度、g-額外條件診斷度、條件診斷策略和診斷算法的研究仍然是當(dāng)前的熱點(diǎn)研究問題。

3 摘 要：條件診斷

二進(jìn)制遞歸網(wǎng)絡(luò)作為一類新型的網(wǎng)絡(luò)族，包含了立方形遞歸網(wǎng)絡(luò)，如超立方體、交叉立方體、扭曲立方體等。本文將二進(jìn)制遞歸網(wǎng)絡(luò)中故障結(jié)點(diǎn)數(shù)量小于連通度的故障模式稱為少故障模式，故障結(jié)點(diǎn)數(shù)量大于連通度的故障模式稱為隨機(jī)多故障模式。立方形遞歸網(wǎng)絡(luò)作為二進(jìn)制遞歸網(wǎng)絡(luò)的特殊子類，不等同于二進(jìn)制遞歸網(wǎng)絡(luò)。于是，二進(jìn)制遞歸網(wǎng)絡(luò)的多故障條件診斷性理論與方法可以直接應(yīng)用于立方體遞歸網(wǎng)絡(luò)的多故障條件診斷性分析，極大地減少了分別研究每個立方體遞歸網(wǎng)絡(luò)的結(jié)構(gòu)性質(zhì)和多故障條件診斷性的代價。本文對摘要：條件診斷的闡述將從多故障條件診斷度研究、多故障條件診斷策略構(gòu)建和多故障條件診斷算法設(shè)計(jì)3 方面展開，各部分的研究內(nèi)容及相互關(guān)系如圖1 所示。

圖 1 主要研究內(nèi)容及相互關(guān)系

3.1 研究多故障條件診斷度

1）g-好鄰居條件診斷度。與診斷度、強(qiáng)診斷度和條件診斷度相比，g-好鄰居條件診斷度豐富了網(wǎng)絡(luò)故障診斷的內(nèi)容，提高了系統(tǒng)多故障診斷能力。通過研究二進(jìn)制遞歸網(wǎng)絡(luò)的g-好鄰居條件故障點(diǎn)割集規(guī)模和帶條件子圖規(guī)模，建立分析二進(jìn)制遞歸網(wǎng)絡(luò)的g-好鄰居條件診斷度的解析表達(dá)式，可為在二進(jìn)制遞歸網(wǎng)絡(luò)上設(shè)計(jì)自主高效的g-好鄰居條件診斷算法做必要的理論準(zhǔn)備。

2）g-額外條件故障診斷度。g-額外條件故障診斷是一類相當(dāng)新的故障診斷策略。它充分考慮了無故障分支的拓?fù)湫再|(zhì)，豐富了網(wǎng)絡(luò)故障診斷的內(nèi)容。與（強(qiáng)）診斷度、條件診斷度和g-好鄰居條件診斷度相比，它提高了系統(tǒng)多故障診斷能力。通過研究二進(jìn)制遞歸網(wǎng)絡(luò)的g-額外條件故障點(diǎn)割集規(guī)模、無故障分支規(guī)模等，建立確定g-額外條件診斷度的解析表達(dá)式，可為在二進(jìn)制遞歸網(wǎng)絡(luò)上設(shè)計(jì)自主高效的g-額外條件故障診斷算法做必要的理論準(zhǔn)備。

3.2 構(gòu)建多故障條件診斷策略

1）g-條件診斷策略構(gòu)建。在g-好鄰居條件診斷策略中，系統(tǒng)中的每個無故障結(jié)點(diǎn)至少有g(shù)個好鄰居結(jié)點(diǎn)，在條件診斷策略中，系統(tǒng)中的每個處理器的鄰居結(jié)點(diǎn)不會同時出現(xiàn)故障，但在實(shí)際系統(tǒng)中，故障結(jié)點(diǎn)也可能至少存在g個無故障鄰居結(jié)點(diǎn)。為了保證系統(tǒng)的高性能，這就需要系統(tǒng)具有更高的可診斷性，因此可以基于g-好鄰居條件診斷策略和條件診斷策略，假定每個結(jié)點(diǎn)至少有g(shù)個好鄰居結(jié)點(diǎn)，提出g-條件診斷策略。由于系統(tǒng)中每個結(jié)點(diǎn)出現(xiàn)故障的概率是不同的，每個結(jié)點(diǎn)的鄰居結(jié)點(diǎn)都出現(xiàn)故障的概率非常小，幾乎可以忽略，因此每個點(diǎn)至少有g(shù)個好鄰居結(jié)點(diǎn)的假設(shè)是合理的?？梢?，g-條件診斷是g-好鄰居條件診斷和條件診斷的擴(kuò)展，當(dāng)g=1 時，1-條件診斷度即為條件診斷度。通過對g-條件故障點(diǎn)割集規(guī)模和帶條件子圖規(guī)模的研究，確定二進(jìn)制遞歸網(wǎng)絡(luò)的g-條件診斷度的一般方法，可為在二進(jìn)制遞歸網(wǎng)絡(luò)上設(shè)計(jì)自主高效的g-條件診斷算法做必要的理論準(zhǔn)備。

2）跨步條件診斷策略構(gòu)建。在二進(jìn)制遞歸網(wǎng)絡(luò)中，超立方體網(wǎng)絡(luò)結(jié)構(gòu)規(guī)則、簡單易于實(shí)現(xiàn)，但網(wǎng)絡(luò)直徑較大、連通度較小，隨著網(wǎng)絡(luò)規(guī)模增長，其診斷性減弱。雖然可用扭曲立方體、折疊立方體、交叉立方體、M?bius 立方體、增廣立方體、加強(qiáng)立方體等二進(jìn)制立方形遞歸網(wǎng)絡(luò)來克服超立方體的缺點(diǎn)，但是傳統(tǒng)故障診斷都是基于網(wǎng)絡(luò)結(jié)構(gòu)直接建立的；因此，不同故障診斷能力有限，診斷性能提升不夠明顯，改進(jìn)網(wǎng)絡(luò)結(jié)構(gòu)來提升網(wǎng)絡(luò)的故障診斷能力，其性價比也不高。為此，可結(jié)合網(wǎng)絡(luò)結(jié)構(gòu)和網(wǎng)絡(luò)通信模式提出新的故障診斷策略來提升網(wǎng)絡(luò)的故障診斷能力。

網(wǎng)絡(luò)模型結(jié)構(gòu)中的每個處理器由任務(wù)處理器和通信處理器2 部分組成。通常任務(wù)處理器比通信處理器發(fā)生故障的可能性大得多，因此可以假設(shè)：網(wǎng)絡(luò)中通信處理器故障不會出現(xiàn)，處理器故障是由任務(wù)處理器出現(xiàn)故障造成的；網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中不相鄰的2 個處理器之間也能進(jìn)行通信，相互進(jìn)行測試。與傳統(tǒng)診斷策略相比，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中處理器之間的相互測試實(shí)現(xiàn)了“跨步”，本文稱為跨步診斷策略。在這種策略下，可以假設(shè)網(wǎng)絡(luò)中處理器故障或無故障狀態(tài)滿足某些條件，便可定義不同的跨步條件診斷策略。為了便于度量跨步條件診斷性，可以基于Hamming 距離在二進(jìn)制遞歸網(wǎng)絡(luò)結(jié)點(diǎn)間通過添加新邊的方式建立二進(jìn)制遞歸網(wǎng)絡(luò)的通信圖，基于二進(jìn)制遞歸網(wǎng)絡(luò)的通信圖研究二進(jìn)制遞歸網(wǎng)絡(luò)的跨步條件診斷性。

3.3 設(shè)計(jì)多故障診斷算法

根據(jù)二進(jìn)制遞歸網(wǎng)絡(luò)的最小g-好鄰居條件點(diǎn)割集規(guī)模、g-額外條件點(diǎn)割集規(guī)模、子圖規(guī)模等拓?fù)浣Y(jié)構(gòu)性質(zhì)，以及g-好鄰居、g-額外和g-條件診斷度，設(shè)計(jì)g-好鄰居條件診斷算法、g-額外條件診斷算法和g-條件診斷算法；基于二進(jìn)制遞歸網(wǎng)絡(luò)的通信圖，運(yùn)用以上條件診斷算法的設(shè)計(jì)方法設(shè)計(jì)跨步條件診斷算法，實(shí)現(xiàn)二進(jìn)制遞歸網(wǎng)絡(luò)在多故障模式下的故障結(jié)點(diǎn)定位。分析這些診斷算法的復(fù)雜性與正確性，保證算法的可行性與高效性。

4 總結(jié)

為實(shí)現(xiàn)摘要：診斷，本文從（強(qiáng)）診斷度、條件診斷度、g-好鄰居條件診斷度、g-額外條件診斷度、診斷算法和二進(jìn)制遞歸網(wǎng)絡(luò)6 方面系統(tǒng)地對本領(lǐng)域國內(nèi)外研究現(xiàn)狀進(jìn)行了綜述，并對存在問題進(jìn)行了分析。從多故障條件診斷度研究、多故障條件診斷策略構(gòu)建和多故障診斷算法設(shè)計(jì)3 方面闡述了重點(diǎn)研究內(nèi)容。