新型互連網(wǎng)絡(luò)的可靠性-連通度與診斷性研究.pdf

1、新型互連網(wǎng)絡(luò)是多處理器計算機(jī)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的發(fā)展方向。新型互連網(wǎng)絡(luò)由于結(jié)構(gòu)上的對稱性、正則性、組合的遞歸性以及相對較小的網(wǎng)絡(luò)直徑等特征，使得其具有低成本、高容錯、路由簡單等優(yōu)點。新型互連網(wǎng)絡(luò)的可靠性問題是多處理器新型互連網(wǎng)絡(luò)計算機(jī)系統(tǒng)發(fā)展過程中亟待解決的關(guān)鍵問題。新型互連網(wǎng)絡(luò)可靠性研究的核心內(nèi)容是連通度和診斷性研究。然而，迄今為止新型互連網(wǎng)絡(luò)的可靠性研究尚處起步階段，有些方面還未涉及，特別是在連通度和診斷性的某些方面，這些情況嚴(yán)重限制了新

2、型互連網(wǎng)絡(luò)的應(yīng)用和推廣?；诖耍疚牟捎眉险?、圖論、計算機(jī)算法以及數(shù)據(jù)統(tǒng)計分析等相關(guān)方法對新型互連網(wǎng)絡(luò)的可靠性問題展開研究。本文的研究將有助于厘清新型互連網(wǎng)絡(luò)的可靠性能，為我國發(fā)展高可信網(wǎng)絡(luò)提供重要的理論基礎(chǔ)和性能參數(shù)。
　　本文首先以條件t-可診斷為研究對象，利用F、T、M、HF四個彼此關(guān)聯(lián)的結(jié)點集合對互測PMC模型下的條件t-可診斷展開研究，得出互測PMC模型下關(guān)聯(lián)集合的關(guān)聯(lián)規(guī)則。以此為基礎(chǔ)，設(shè)計了互測PMC模型下基于關(guān)聯(lián)集

3、合的條件t-可診斷算法。進(jìn)而對互測PMC模型下的條件t-可診斷的判定算法展開研究，在得到基于互測PMC模型條件t-可診斷的充要條件之后，設(shè)計了條件故障集合的求取算法和基于互測PMC模型的條件t-可診斷判定算法。該算法能快速地對系統(tǒng)是否屬于條件t-可診斷進(jìn)行判定。之后，本文以建立可區(qū)分函數(shù)的全新視角來對條件故障集合的可區(qū)分性展開研究，提出了基于互測PMC模型的條件故障集合可區(qū)分函數(shù)，并在此基礎(chǔ)上形成基于互測PMC模型的條件t-可診斷的判定

4、函數(shù)和基于互測PMC模型的條件診斷度求取算法。這些研究成果對于提高系統(tǒng)的診斷速度、降低條件診斷度的計算難度和改善條件t-可診斷的判定方法等方面有著重要的理論價值和現(xiàn)實意義。
　　其次，針對新型互連網(wǎng)絡(luò)的最新拓?fù)溲芯砍晒粨Q交叉立方網(wǎng)絡(luò)的拓?fù)湫再|(zhì)、連通度和診斷性展開研究。通過對交換交叉立方網(wǎng)絡(luò)進(jìn)行拓?fù)浞治龅贸鼋粨Q交叉立方網(wǎng)絡(luò)的拓?fù)湫再|(zhì)，并以其拓?fù)湫再|(zhì)為基礎(chǔ)研究得出交換交叉立方網(wǎng)絡(luò)的條件連通度和限制連通度均為2s，其中t≥s＞2。

5、再以交換交叉立方網(wǎng)絡(luò)的限制連通度為基礎(chǔ)，根據(jù)限制連通度與條件診斷度之間的關(guān)聯(lián)關(guān)系研究得出交換交叉立方網(wǎng)絡(luò)的條件診斷度為4(s-1)+1，其中t≥s＞2。交換交叉立方網(wǎng)絡(luò)的連通度和診斷性的研究成果將有助于未來對其展開可靠性評價。
　　再次，本文進(jìn)行了新型互連網(wǎng)絡(luò)診斷性的拓展研究。以g正確鄰結(jié)點條件t-可診斷理論為基礎(chǔ)，提出了強(qiáng)g正確鄰結(jié)點條件t-可診斷的定義，并展開拓?fù)湫再|(zhì)研究。進(jìn)而，以n維超立方網(wǎng)絡(luò)為研究對象，研究了n維超立方網(wǎng)絡(luò)

6、的強(qiáng)g正確鄰結(jié)點條件t-可診斷的性質(zhì)定理。在此基礎(chǔ)上，通過研究得出互測PMC模型下n維超立方網(wǎng)絡(luò)的強(qiáng)g正確鄰結(jié)點條件診斷度小于22g(n-2g)+22g-1-1，其中n≥5，1≤g＜［n/3]。強(qiáng)g正確鄰結(jié)點條件t-可診斷的提出拓展了診斷性研究的邊界，也豐富了診斷性理論，具有一定的研究價值。
　　最后，本文對研究工作進(jìn)行總結(jié)歸納。同時通過分析給出新型互連網(wǎng)絡(luò)可靠性——連通度與診斷性研究下一步的研究方向，具體包括比較診斷模型下的診斷