李佳亮，常天慶，張 雷

（裝甲兵工程學院，北京 100072）

一種基于元胞自動機的故障樣本選取方法*

李佳亮，常天慶，張 雷

（裝甲兵工程學院，北京 100072）

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

元胞自動機，傳染病，電路，故障傳播，樣本選取

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 引言

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

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

1 元胞自動機

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

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

2 模型建立

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

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

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

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

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

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

2.2 演化規(guī)則

定義每個元胞的位置表示為 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個元胞的狀態(tài)。在二維空間中，定義Aij（t）表示元胞在t時刻的輸出狀態(tài)，得

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

2.3 故障傳播行為

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

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

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

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

3 實例分析

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

圖2 輸出板各模塊組成

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

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

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

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

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

4 結(jié)論

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

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

［2］游愛麗，閆萍.基于元胞自動機的甲型HINI流感病毒的模型［J］.新疆大學學報，2010，46（2）：56-59.

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

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

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

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

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

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

［9］高鳳岐，連光耀，黃考利，等.基于半實物仿真的電路板故障注入系統(tǒng)設(shè)計與實現(xiàn)［J］.計算機測量與控制，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

軍隊預研基金資助項目（2015YY05）

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