系統(tǒng)級故障診斷算法研究.pdf

1、多計算機系統(tǒng)為人類實現(xiàn)高性能計算、大容量分布式信息存儲和傳輸提供了強大的工具，多機系統(tǒng)的廣泛使用已經(jīng)成為當(dāng)代信息社會的一個重要標志。隨著系統(tǒng)規(guī)模的日益擴大，系統(tǒng)中出現(xiàn)故障的可能性也隨之增大。因此，如何維持系統(tǒng)的高可靠性和可用性就成為一個迫切需要解決的問題。提高系統(tǒng)可靠性的一個主要手段就是及時診斷出系統(tǒng)中發(fā)生故障的結(jié)點機和通信鏈路，以便于維護人員能夠盡快修復(fù)出現(xiàn)故障的部分，恢復(fù)系統(tǒng)的正常工作狀態(tài)。
　　 系統(tǒng)級故障診斷作為故障診斷

2、和定位的一個強有力工具，在容錯領(lǐng)域得到了廣泛的應(yīng)用。其基本思想是充分利用系統(tǒng)中各個獨立結(jié)點機的通信、處理能力，讓它們相互測試，通過對測試結(jié)果進行綜合分析，得出診斷結(jié)論。這種方法不必使用專用設(shè)備進行測試，在不增加系統(tǒng)額外成本的條件下就可以實現(xiàn)系統(tǒng)的快速自診斷，具有極高的應(yīng)用價值。
　　 在系統(tǒng)級故障診斷眾多的研究課題中，最核心的是故障診斷問題，即根據(jù)結(jié)點機相互測試的結(jié)果(癥候)，設(shè)計有效的診斷算法來識別系統(tǒng)中的故障。本文的研究工作

3、主要就是圍繞這一問題展開的。具體而言，本文研究了多計算機系統(tǒng)在不同測試模型和診斷策略下的故障診斷問題，并取得了下列結(jié)果：
　　 1.提出了廣義立方體網(wǎng)絡(luò)的t/k(k=3)-故障診斷算法
　　 與傳統(tǒng)的精確診斷和悲觀診斷策略相比，t/k(k≥2)診斷策略在允許少量(不超過k個)無故障結(jié)點被誤診斷為故障的代價下，大幅度地提高了系統(tǒng)的自診斷能力。廣義立方體網(wǎng)絡(luò)是一類規(guī)則互連網(wǎng)絡(luò)拓撲結(jié)構(gòu)的總稱，它包括了超立方體及其多種變形立方體

4、結(jié)構(gòu)。近年來，人們研究了廣義立方體的t/k診斷度，證明了一個n維的廣義立方體當(dāng)滿足條件k≤n+1，t=(k+1)n-(k+1)(k+2)/2+1時是t/k-可診斷的，然而目前尚無有效的t/k(k≥2)診斷算法。在PMC模型下，本文首次提出了廣義立方體網(wǎng)絡(luò)的t/k(k=3)故障診斷算法，該算法的時間復(fù)雜度為O(Nlog2N)，其中N=2n表示結(jié)點總數(shù)。這項研究成果對研究其它類型的t/k診斷算法，以及把t/k診斷推向?qū)嵱镁哂幸欢ǖ睦碚撘饬x。

5、
　　 2.提出了t-可診斷系統(tǒng)的人工免疫診斷算法
　　 人工免疫系統(tǒng)是一類基于生物免疫系統(tǒng)的功能、原理、基本特征及相關(guān)免疫學(xué)說建立的用于解決各種復(fù)雜問題的計算系統(tǒng)。通過分析生物免疫系統(tǒng)中抗體與抗原之間的關(guān)系，我們定義了一個親合度函數(shù)來評估由潛在故障集產(chǎn)生的癥候(抗體)與輸入癥候(抗原)之間的相似程度，并基于克隆選擇原理提出了一個t-可診斷系統(tǒng)的人工免疫診斷算法。理論分析和計算機仿真實驗證實了該算法的有效性。
　　

6、 3.提出了t-可診斷系統(tǒng)的群體智能診斷算法
　　 群體智能是人們受到自然界中群居生物群體行為的啟發(fā)而提出的一種智能計算或優(yōu)化的方法。群體智能利用群體優(yōu)勢，在沒有集中控制，不提供全局模型的前提下，為尋找復(fù)雜問題解決方案提供了新的思路，受到國際智能計算研究領(lǐng)域?qū)W者的廣泛關(guān)注。本文中，我們借助群體智能方法研究了三個不同的測試模型(PMC模型，對稱比較模型和非對稱比較模型)下的系統(tǒng)級故障診斷問題。通過引入螞蟻尋找食物時所釋放的“信息

7、素”的概念評估了潛在癥候與實際癥候的相似度，并提出了針對一般的t-可診斷系統(tǒng)的群體智能診斷算法。大量仿真實驗的結(jié)果證明了該算法能夠在較短的時間內(nèi)正確地識別出系統(tǒng)中的故障結(jié)點，具有一定的實用價值。
　　 4.在MM*模型下分別針對局部扭曲立方體和M(o)bius立方體提出了兩個快速故障診斷算法
　　 MM*模型是一種非常實用的比較模型，自被提出以來受到了學(xué)者們的極大關(guān)注。局部扭曲立方體和M(o)bius立方體是兩類常用的超

8、立方體變形結(jié)構(gòu)，具有許多優(yōu)良的拓撲性質(zhì)。在MM*模型下，人們已經(jīng)知道n維局部扭曲立方體和M(o)bius立方體的診斷度為n，然而，還沒有針對這兩類特殊結(jié)構(gòu)的高效率故障診斷算法。本文中，我們提出了局部扭曲立方體和M(o)bius立方體在MM*模型下的快速故障診斷算法，其時間復(fù)雜度均為O(Nlog22,N)。就時間復(fù)雜度而言，該算法與經(jīng)典的Sengupta-Dahbura算法(其時間復(fù)雜度為O(N5))相比具有顯著的優(yōu)越性。