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

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

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

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

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

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

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

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

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