李佳亮，常天慶，張 雷

（裝甲兵工程學(xué)院，北京 100072）

一種基于元胞自動(dòng)機(jī)的故障樣本選取方法*

李佳亮，常天慶，張 雷

（裝甲兵工程學(xué)院，北京 100072）

故障樣本選取是測(cè)試性驗(yàn)證中的關(guān)鍵環(huán)節(jié)，直接影響測(cè)試性驗(yàn)證試驗(yàn)的效率和結(jié)果的正確性。在板級(jí)電路的故障樣本選取過(guò)程中，運(yùn)用傳染病思想中的元胞自動(dòng)機(jī)模型分析了電路故障的傳播行為，提出了一種基于元胞自動(dòng)機(jī)的故障樣本選取方法，實(shí)現(xiàn)了故障樣本的等效選取。以某型裝備關(guān)鍵部件為例，建立了故障傳播模型，計(jì)算并改進(jìn)了元胞自動(dòng)機(jī)狀態(tài)計(jì)算方法，通過(guò)注入易操作的故障樣本，簡(jiǎn)化了故障注入的流程，提高了故障注入效率。

元胞自動(dòng)機(jī)，傳染病，電路，故障傳播，樣本選取

Abstract：Sample selection is the key link in fault verification test，it has a direct impact on the accuracy of the efficiency and results.In fault sample selection process of board-level circuit，the cellular automaton model in infectious is used，thought to analyze the behavior of circuit fault propagation，fault sample selection method based on cellular automata is proposed，toselect the fault samples equivalent is achieved.In a certain type of key equipment components，for example，a fault propagation model to calculate and improved cellular automata state calculation method is established，streamlined processes by injecting fault samples which easy to operate，improve the efficiency of fault injection.

Key words：cellular automata，infectious diseases，circuit，fault propagation，sample selection

0 引言

元胞自動(dòng)機(jī)是描述自然界復(fù)雜現(xiàn)象的常見工具，該模型被廣泛應(yīng)用于醫(yī)學(xué)領(lǐng)域，對(duì)于傳染病傳播模型構(gòu)建及傳染趨勢(shì)預(yù)測(cè)十分有效。于雷［1］等人運(yùn)用該模型模擬了傳染病傳播過(guò)程，進(jìn)而研究了SARS 病毒的傳播行為；游愛麗、閆萍［2］、汪小帆［3］、于鑫［4］等人也利用元胞自動(dòng)機(jī)模型在醫(yī)學(xué)上進(jìn)行了傳染病的研究，成效明顯。其實(shí)傳染病模型不僅僅在醫(yī)學(xué)領(lǐng)域應(yīng)用廣泛，在工學(xué)領(lǐng)域仍然可以利用它的思想進(jìn)行研究。在集成電路板測(cè)試性研究中，由于裝置中的不同模塊之間或者裝置與裝置之間會(huì)存在耦合現(xiàn)象［5］，由此產(chǎn)生的故障傳播情況往往導(dǎo)致故障建模不準(zhǔn)確，這對(duì)于故障注入工作的開展是不利的，利用傳染病模型研究故障傳播行為便成為了新的思路。

在分析電路故障時(shí)，需要針對(duì)故障傳播進(jìn)行深入分析，常見的方法是多信號(hào)流圖法。基于多信號(hào)流圖［6］的方法具備直觀簡(jiǎn)潔，結(jié)構(gòu)清晰的特點(diǎn)，它構(gòu)建故障傳播有向圖，利用相關(guān)性模型進(jìn)行分析，但是它主要針對(duì)靜態(tài)推理，然而電路中的故障傳播往往是一個(gè)動(dòng)態(tài)的過(guò)程，所以需要研究電路故障的動(dòng)態(tài)傳播行為。在這方面的研究中，吳繼梅、白慧、邵世煌等［7］提出了一種復(fù)雜電路功能故障傳播模型，這種模型利用將元胞自動(dòng)機(jī)模型運(yùn)用到電路分析中，分析了添加擾動(dòng)的情況下的電路故障傳播行為，但是這種方法沒有充分考慮主元胞和鄰居間的關(guān)系。提出一種基于元胞自動(dòng)機(jī)的故障傳播模型，根據(jù)元胞模型的演化規(guī)則研究板級(jí)電路故障的傳播過(guò)程。

1 元胞自動(dòng)機(jī)

元胞自動(dòng)機(jī)（Cellular Automata簡(jiǎn)稱CA）是定義在一個(gè)具有離散有限狀態(tài)的元胞組成的元胞空間上，并且按照一定的局部規(guī)則在離散時(shí)間維度上演化的動(dòng)力學(xué)系統(tǒng)［7］。在研究中可以將元胞自動(dòng)機(jī)看作是某種模型的總稱或者一個(gè)特殊框架。CA模型來(lái)自于生物學(xué)模型，它通過(guò)基元和簡(jiǎn)單規(guī)則產(chǎn)生復(fù)雜行為，是一種非線性系統(tǒng)的代表，當(dāng)在電路系統(tǒng)中應(yīng)用本模型模擬動(dòng)態(tài)過(guò)程，根據(jù)細(xì)胞演化規(guī)則，可以較貼切地表述故障傳播行為。

元胞自動(dòng)機(jī)作為一種生物模型，它的特征元素主要包括元胞、元胞空間、鄰居和規(guī)則三大類。元胞作為獨(dú)立的單元組合在一起構(gòu)成了元胞集，分散在不同維數(shù)的網(wǎng)格中；元胞空間表示元胞取值的所有組合，廣義而言，元胞自動(dòng)機(jī)只有0和1兩種狀態(tài)，但是為了充分描述各個(gè)單元的具體情況，元胞自動(dòng)機(jī)可以取0-1中間值，這些值的賦予需要被提前定義；鄰居是指將會(huì)被影響到的一系列元胞，它們或許在某個(gè)元胞的周圍，或許與該元胞有一定的距離，但是在定義的半徑下如果可能被影響到，即被稱為鄰居；規(guī)則體現(xiàn)了元胞自動(dòng)機(jī)的演化過(guò)程，不同的規(guī)則會(huì)塑造不同的元胞狀態(tài)。

2 模型建立

在實(shí)際電路中，每個(gè)電路要實(shí)現(xiàn)某些功能都需要多個(gè)電路模塊共同工作，所以在研究電路故障傳播的過(guò)程中，可以將每個(gè)電路系統(tǒng)分成不同的模塊，將每個(gè)電路模塊用元胞表示，電路模塊之間的關(guān)系用鄰居關(guān)系表示［8］。為了研究方便，設(shè)定電路中某模塊產(chǎn)生的故障只能傳播給鄰居電路模塊，并且定義耦合度（Coupling）ε∈（0，1）表示模塊間的關(guān)聯(lián)程度即故障影響關(guān)聯(lián)程度。設(shè)定故障閾值θ，表示故障狀態(tài)對(duì)于功能的影響，當(dāng)故障超過(guò)該值，判定電路模塊發(fā)生故障，否則判定故障無(wú)影響。

2.1 元胞自動(dòng)機(jī)網(wǎng)格設(shè)置

在元胞自動(dòng)機(jī)模型中，元胞的狀態(tài)有0、1、-1這三種，其中元胞運(yùn)行正常，即電路模塊正常工作、功能有效，定義元胞狀態(tài)為1；元胞運(yùn)行失常，即電路模塊參數(shù)異常、功能失效，定義元胞狀態(tài)為-1；若元胞狀態(tài)為0，則表示該點(diǎn)不存在電路模塊，元胞為空格。元胞通常存在于三維空間或者二維空間中，其在三維空間中的運(yùn)動(dòng)類似布朗運(yùn)動(dòng)，這對(duì)于研究元胞間的聯(lián)系，建立空間模型十分不利。常用的元胞自動(dòng)機(jī)是二維的，它又分成三角形、正方形和正六邊形，如圖1所示，其優(yōu)缺點(diǎn)比較如表1。

圖1 二維元胞自動(dòng)機(jī)的三種網(wǎng)格劃分

表1 三種網(wǎng)格比較

綜合三種二維網(wǎng)格模型，為進(jìn)行故障傳播性研究，選取正方形網(wǎng)格為研究對(duì)象，研究者通過(guò)大量的分析得知，如果將所有元胞映射到二維空間，即元胞間只存在二維網(wǎng)格連接，這將會(huì)化簡(jiǎn)模型，同樣也可以表征元胞間的演化和位置變換。在二維空間的正方形網(wǎng)格模型中，鄰居模型主要有5鄰居模型（Von Neumann簡(jiǎn)稱VN），9鄰居模型（Moore簡(jiǎn)稱MR）和25鄰居模型（Extend Moore簡(jiǎn)稱EM）。

2.2 演化規(guī)則

定義每個(gè)元胞的位置表示為 r=（i，j），其中 i，j∈（1，n）。根據(jù)演化規(guī)則：Si（t+1）=f（Si-r，Si-r+1，…，Si，…，Si+r-1，Si+r），Si表示第i個(gè)元胞的狀態(tài)。在二維空間中，定義Aij（t）表示元胞在t時(shí)刻的輸出狀態(tài)，得

其中θ表示故障閾值；ε表示鄰居元胞耦合度；X1、X2、X3、X4表示 5 鄰居模型中元胞 r的左、右、上、下4個(gè)鄰居，其取值為0和1；Sij（t）表示元胞r的故障程度，其值的大小正向影響鄰居元胞狀態(tài)，通過(guò)式（1）可知，當(dāng)0＜Sij（t）＜θ時(shí)，元胞r狀態(tài)正常，當(dāng)Sij（t）≥θ或者Sij（t）=0時(shí)，元胞失效并產(chǎn)生故障。

2.3 故障傳播行為

定義存在外部干擾或者電路內(nèi)部元器件失效為故障擾動(dòng)。分析可知，當(dāng)CA中的所有元胞初始狀態(tài)均滿足0＜Sij（t）＜θ，且無(wú)故障擾動(dòng)時(shí)，元胞將在任意t時(shí)刻保持正常狀態(tài)。設(shè)定t'時(shí)刻Sij（t'）≥θ，即元胞r產(chǎn)生功能故障，此時(shí)為添加故障擾動(dòng)ω狀態(tài)。

經(jīng)過(guò)分析可知，元胞的鄰居對(duì)于主元胞的影響往往是不同的，其耦合度值也不同，所以式（3）沒有考慮元胞中每個(gè)鄰居對(duì)于主元胞的影響，其改進(jìn)型如式（4）所示。

隨著時(shí)間的推移，可知t'時(shí)刻以后故障不會(huì)自動(dòng)恢復(fù)，從t'+1時(shí)刻開始故障元胞r將影響其鄰居狀態(tài)。根據(jù)耦合度關(guān)系，可以得出鄰居元胞故障程度，以ri-1j為例，其故障程度表達(dá)式為：

根據(jù)式（1）、式（2）、式（5）可以求得鄰居元胞狀態(tài)，當(dāng)鄰居元胞超出閾值，產(chǎn)生故障再影響它的鄰居，由此產(chǎn)生故障傳播和擴(kuò)散，設(shè)定故障規(guī)模達(dá)到最大值時(shí)，狀態(tài)空間穩(wěn)定，故障傳播結(jié)束。

3 實(shí)例分析

以某型裝備中的關(guān)鍵部件為例進(jìn)行研究。某型裝備控制盒是一種調(diào)速控制裝置，它包括自動(dòng)板、半自動(dòng)版、輸出板、反饋板等，這里主要研究其關(guān)鍵部件—輸出板。將輸出板模塊劃分為三角發(fā)生器模塊、比較器模塊、驅(qū)動(dòng)器模塊、累加器模塊、倒向器模塊和放大器模塊，如圖2所示。

圖2 輸出板各模塊組成

根據(jù)統(tǒng)計(jì)數(shù)據(jù)及FMECA故障分析，各個(gè)模塊之間的耦合度和模塊對(duì)系統(tǒng)的影響因子如表2所示，可知三角波發(fā)生器模塊對(duì)系統(tǒng)影響較大，與其他模塊耦合度較高。

表2 模塊耦合度與系統(tǒng)影響因子

本例運(yùn)用VN模型分析輸出板各模塊關(guān)系如圖3所示。對(duì)于故障的判定，不同的專家系統(tǒng)有不同的判定依據(jù)。這里設(shè)定各模塊的故障發(fā)生閾值θ=0.3，即認(rèn)為三角波電路模塊故障值超過(guò)0.3時(shí)為t時(shí)刻，該模塊產(chǎn)生故障現(xiàn)象，并且影響鄰居模塊狀態(tài)，產(chǎn)生故障傳播行為。經(jīng)過(guò)統(tǒng)計(jì)數(shù)據(jù)分析，設(shè)定三角波電路模塊在t-1時(shí)刻為正常狀態(tài)，其故障程度滿足0＜Sij（t-1）＜θ，為計(jì)算方便，設(shè)置該時(shí)刻Sij（t-1）=0.2，Sij-1（t-1）=0.1，Sij+1（t-1）=0.1，Si-1j（t-1）=0.1，Si+1j（t-1）=0.1。此時(shí)添加擾動(dòng)ω=0.2，利用式（4）計(jì)算Sij（t）=0.365，此時(shí)Sij（t）＞θ，三角波模塊產(chǎn)生故障。該故障將傳播至倒向器、比較器、驅(qū)動(dòng)器及其他部分。由式（5）計(jì)算可得，Sij-1（t-1）=0.137，Sij+1（t-1）=0.392，Si-1j（t-1）=0.246，Si+1j（t-1）=0.137，可知比較器故障值超過(guò)閾值，產(chǎn)生故障行為，進(jìn)而傳播故障給其鄰居。以此類推，直至系統(tǒng)穩(wěn)定，不再產(chǎn)生新故障。此外，電路中故障存在逆向傳播的行為，次級(jí)電路會(huì)影響上一級(jí)電路［9］，但是其影響力很小，所以在故障傳播的研究中，為了計(jì)算方便，避免陷入死循環(huán)，可以忽略這一部分故障傳播，認(rèn)為理想狀態(tài)下電路故障是按照一定的邏輯進(jìn)行傳播的［10］。

圖3 輸出板各模塊的VN模型

在分析故障傳播影響后，認(rèn)為三角波發(fā)生電路對(duì)于輸出板的故障影響最大，同時(shí)三角波模塊產(chǎn)生故障后會(huì)存在故障傳播現(xiàn)象，對(duì)于輸出板其他模塊產(chǎn)生影響，造成其他模塊的故障產(chǎn)生。所以在選取本電路的故障樣本時(shí)，只需對(duì)三角波發(fā)生電路進(jìn)行分析，在故障注入階段也可以針對(duì)于三角波發(fā)生電路進(jìn)行故障注入。運(yùn)用的方法是添加信號(hào)噪聲，使疊加噪聲的三角波輸出波形的幅值、周期發(fā)生改變，以影響電路功能，實(shí)現(xiàn)故障的注入。針對(duì)于三角波信號(hào)疊加可以利用信號(hào)發(fā)生器產(chǎn)生特定周期和幅值的信號(hào)，應(yīng)用已有的基于探針的故障注入設(shè)備可以將所產(chǎn)生的故障源信號(hào)疊加到正常三角波信號(hào)管腳處，這里將不作具體注入方法的表述。作為一種動(dòng)態(tài)過(guò)程，基于本方法的故障注入可以實(shí)時(shí)地進(jìn)行。

4 結(jié)論

本文提出了一種基于元胞自動(dòng)機(jī)的故障樣本選取方法，研究了故障傳播行為，這種方法實(shí)質(zhì)上完成了故障樣本的等效注入，通過(guò)注入易操作的故障樣本，避免了對(duì)于不易注入的故障樣本的操作，簡(jiǎn)化了故障注入的流程，對(duì)于提高測(cè)試性驗(yàn)證工作的效率具有深刻的意義。

［1］余雷.基于元胞自動(dòng)機(jī)的傳染病傳播模型研究［J］.計(jì)算機(jī)工程與應(yīng)用，2007，54（2）：196-198.

［2］游愛麗，閆萍.基于元胞自動(dòng)機(jī)的甲型HINI流感病毒的模型［J］.新疆大學(xué)學(xué)報(bào)，2010，46（2）：56-59.

［3］汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用［M］.北京：清華大學(xué)出版社，2006：162-163.

［4］于鑫.基于元胞自動(dòng)機(jī)的流行病傳播模型模擬［J］.計(jì)算機(jī)工程與應(yīng)用，2005，52（2）：205-209.

［5］李果，高建民，高智勇，等.基于小世界網(wǎng)絡(luò)的復(fù)雜系統(tǒng)故障傳播模型 ［J］. 西安交通大學(xué)學(xué)報(bào)，2007，41（3）：334-338.

［6］吳繼梅，白慧，邵世煌.一種復(fù)雜電路功能故障傳播模型［J］.微型電腦應(yīng)用，2008，24（1）.4-7.

［7］連可，黃建國(guó)，龍兵.一種基于有向圖模型的模糊多故障診斷算法 ［J］. 系統(tǒng)工程與電子技術(shù)，2008，30（3）：568-571.

［8］王哈力，單慧.基于復(fù)雜網(wǎng)絡(luò)的小型模擬電路分析［D］.哈爾濱理工大學(xué)學(xué)報(bào)，2006，11（3）：11-17.

［9］高鳳岐，連光耀，黃考利，等.基于半實(shí)物仿真的電路板故障注入系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)［J］.計(jì)算機(jī)測(cè)量與控制，2009，17（2）：275-280.

［10］CHEN M，JIANG C S，WU Q X.Sensor fault diagnosis for a class of time delay uncertain nonlinear systems using neural network［J］.International Journal of Automation and Computing，2008，5（4）：401-405.

A Fault Sample Selection Method Based on Cellular Automata

LI Jia-liang，CHANG Tian-qing，ZHANG Lei
（Academy of Armored Force Engineering，Beijing 100072，China）

TP306

A

10.3969/j.issn.1002-0640.2017.09.036

1002-0640（2017）09-0162-04

2016-07-16

2016-08-18

軍隊(duì)預(yù)研基金資助項(xiàng)目（2015YY05）

李佳亮（1992- ），男，河北唐山人，碩士研究生。研究方向：測(cè)試性驗(yàn)證。