故障診斷中t-k診斷策略及遺傳診斷算法研究.pdf

1、隨著信息技術(shù)的高速發(fā)展，為了解決宇宙學(xué)、氣象學(xué)、流體力學(xué)、材料學(xué)等重大科學(xué)領(lǐng)域的計算難問題，大規(guī)模并行處理機向著高性能、大規(guī)模、多樣性、多功能的方向發(fā)展。隨之而來的問題就是系統(tǒng)的容錯性和維護問題，特別是在應(yīng)用于某些重要部門(如軍事和金融)的多機系統(tǒng)中，故障的危害不僅可能涉及個人的生命財產(chǎn)，甚至可能關(guān)系國家和民族的安危。由于系統(tǒng)的規(guī)模越來越大，從中發(fā)現(xiàn)故障點的工作也越來越繁重，花費也越來越高。隨著芯片集成技術(shù)的提高，目前的處理機結(jié)點一般都

2、具備一定的通信和處理能力，于是一個很自然的想法就是充分利用結(jié)點的能力，讓它們相互測試，然后再根據(jù)測試結(jié)果和系統(tǒng)拓撲結(jié)構(gòu)等條件，得出正確的診斷結(jié)果，這就是系統(tǒng)級故障診斷的基本思想。這種方法不必使用專用測試設(shè)備，在不增加系統(tǒng)額外成本的情況下就可實現(xiàn)系統(tǒng)的快速自診斷。 本文的工作就是研究如何采用系統(tǒng)級故障診斷的方法解決多機系統(tǒng)的故障診斷問題，主要圍繞增強超立方體的t/k-診斷度及診斷算法，局部扭立方體的t/k-診斷度，BC圖的t/k-

3、診斷算法，t-可診斷系統(tǒng)的遺傳診斷算法等四個方面展開，并分別得出了相應(yīng)的結(jié)論。 1.增強超立方體的t/k-診斷度(k≤2)及診斷算法。為了提高系統(tǒng)級故障診斷中的診斷度，人們以犧牲很小一部分結(jié)點不能正確診斷為代價，提出t/k-診斷策略。增強超立方體是超立方體的一種變體，它在如直徑、平均結(jié)點間距離、通信密度等方面均具有較好的性能。為了確認其診斷度，我們首先證明了當(dāng)故障結(jié)點集|F|＜2n時，增強超立方體的最大連通分圖的結(jié)點數(shù)≥2n-|

4、F|-1；當(dāng)故障結(jié)點集|F|＜3n-2時，增強超立方體的最大連通分圖的結(jié)點數(shù)≥2n-|F|-2。然后基于以上結(jié)論，證明了它的t/2-診斷度為3n-2，并給出了一個復(fù)雜度為O(Nlog2N)的t/k-診斷算法(k≤2)。目前，上述成果尚未文獻報導(dǎo)。 2.局部扭曲立方體的t/k-診斷度。局部扭曲立方體是一種新的的變形立方體結(jié)構(gòu)，它具有很多很好的拓撲特性。我們證明局部扭曲立方體與超立方體有相同的t/k-診斷度。該個結(jié)論也在最近的一篇論

5、文中得出，但是我們采用的證明方法與之不同，是從另一個側(cè)面證明了這個重要的結(jié)論。 3.BC圖的t/k-診斷算法。BC圖是包括了超立方體和交叉立方體、M(o)bius立方體、扭曲立方體、局部扭曲立方體等多種變形立方體的一類圖。人們證明了BC圖的t/k-診斷度，但是尚未給出相應(yīng)的t/k-診斷算法。對于結(jié)點總數(shù)為N的n維BC圖，本文首先證明了當(dāng)故障結(jié)點集|F|＜(n+1)n-(n+1)(n+2)/2+1時，BC圖的最大連通分圖的結(jié)點數(shù)≥

6、2n-|F|-k。然后基于無故障結(jié)點的極大連通分圖，提出了一個時間復(fù)雜度為O(Nlog2N)的t/k-診斷算法。目前尚無相關(guān)t/k-診斷算法的文章發(fā)表，但與著名的悲觀一步t-診斷算法(t/k-診斷算法在k=1的情況)的O(N2.5)相比較，在時間復(fù)雜度上本文所提算法是高效的。 4.一種用于t-可診斷系統(tǒng)的高效故障診斷遺傳算法 Elhadef和Ayeb首次提出采用遺傳算法來進行系統(tǒng)級故障診斷，其適應(yīng)度函數(shù)通過比較實際癥候與

7、當(dāng)前猜測故障集產(chǎn)生的癥候得到。上述算法的缺點是其適應(yīng)度函數(shù)只考慮了故障集隨機生成的一個癥候，因而將漏掉絕大多數(shù)有效的故障集。本文首先對PMC模型提出結(jié)點狀態(tài)與診斷圖中一定癥候相容時結(jié)點狀態(tài)應(yīng)滿足的方程，然后通過設(shè)計基于該方程的適應(yīng)度函數(shù)，提出了針對t-可診斷系統(tǒng)的遺傳算法，理論分析和模擬試驗均表明所提算法在迭代步數(shù)上優(yōu)于原算法。此外，我們還論證了Elhadef和Ayeb提出的產(chǎn)生初始種群方法的有效性。 綜上所述，在本文的四個部分