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

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

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

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

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

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

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

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