一种基于元胞自动机的故障样本选取方法*

李佳亮，常天庆，张 雷

（装甲兵工程学院，北京 100072）

一种基于元胞自动机的故障样本选取方法*

李佳亮，常天庆，张 雷

（装甲兵工程学院，北京 100072）

故障样本选取是测试性验证中的关键环节，直接影响测试性验证试验的效率和结果的正确性。在板级电路的故障样本选取过程中，运用传染病思想中的元胞自动机模型分析了电路故障的传播行为，提出了一种基于元胞自动机的故障样本选取方法，实现了故障样本的等效选取。以某型装备关键部件为例，建立了故障传播模型，计算并改进了元胞自动机状态计算方法，通过注入易操作的故障样本，简化了故障注入的流程，提高了故障注入效率。

元胞自动机，传染病，电路，故障传播，样本选取

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

元胞自动机是描述自然界复杂现象的常见工具，该模型被广泛应用于医学领域，对于传染病传播模型构建及传染趋势预测十分有效。于雷［1］等人运用该模型模拟了传染病传播过程，进而研究了SARS 病毒的传播行为；游爱丽、闫萍［2］、汪小帆［3］、于鑫［4］等人也利用元胞自动机模型在医学上进行了传染病的研究，成效明显。其实传染病模型不仅仅在医学领域应用广泛，在工学领域仍然可以利用它的思想进行研究。在集成电路板测试性研究中，由于装置中的不同模块之间或者装置与装置之间会存在耦合现象［5］，由此产生的故障传播情况往往导致故障建模不准确，这对于故障注入工作的开展是不利的，利用传染病模型研究故障传播行为便成为了新的思路。

在分析电路故障时，需要针对故障传播进行深入分析，常见的方法是多信号流图法。基于多信号流图［6］的方法具备直观简洁，结构清晰的特点，它构建故障传播有向图，利用相关性模型进行分析，但是它主要针对静态推理，然而电路中的故障传播往往是一个动态的过程，所以需要研究电路故障的动态传播行为。在这方面的研究中，吴继梅、白慧、邵世煌等［7］提出了一种复杂电路功能故障传播模型，这种模型利用将元胞自动机模型运用到电路分析中，分析了添加扰动的情况下的电路故障传播行为，但是这种方法没有充分考虑主元胞和邻居间的关系。提出一种基于元胞自动机的故障传播模型，根据元胞模型的演化规则研究板级电路故障的传播过程。

1 元胞自动机

元胞自动机（Cellular Automata简称CA）是定义在一个具有离散有限状态的元胞组成的元胞空间上，并且按照一定的局部规则在离散时间维度上演化的动力学系统［7］。在研究中可以将元胞自动机看作是某种模型的总称或者一个特殊框架。CA模型来自于生物学模型，它通过基元和简单规则产生复杂行为，是一种非线性系统的代表，当在电路系统中应用本模型模拟动态过程，根据细胞演化规则，可以较贴切地表述故障传播行为。

元胞自动机作为一种生物模型，它的特征元素主要包括元胞、元胞空间、邻居和规则三大类。元胞作为独立的单元组合在一起构成了元胞集，分散在不同维数的网格中；元胞空间表示元胞取值的所有组合，广义而言，元胞自动机只有0和1两种状态，但是为了充分描述各个单元的具体情况，元胞自动机可以取0-1中间值，这些值的赋予需要被提前定义；邻居是指将会被影响到的一系列元胞，它们或许在某个元胞的周围，或许与该元胞有一定的距离，但是在定义的半径下如果可能被影响到，即被称为邻居；规则体现了元胞自动机的演化过程，不同的规则会塑造不同的元胞状态。

2 模型建立

在实际电路中，每个电路要实现某些功能都需要多个电路模块共同工作，所以在研究电路故障传播的过程中，可以将每个电路系统分成不同的模块，将每个电路模块用元胞表示，电路模块之间的关系用邻居关系表示［8］。为了研究方便，设定电路中某模块产生的故障只能传播给邻居电路模块，并且定义耦合度（Coupling）ε∈（0，1）表示模块间的关联程度即故障影响关联程度。设定故障阈值θ，表示故障状态对于功能的影响，当故障超过该值，判定电路模块发生故障，否则判定故障无影响。

2.1 元胞自动机网格设置

在元胞自动机模型中，元胞的状态有0、1、-1这三种，其中元胞运行正常，即电路模块正常工作、功能有效，定义元胞状态为1；元胞运行失常，即电路模块参数异常、功能失效，定义元胞状态为-1；若元胞状态为0，则表示该点不存在电路模块，元胞为空格。元胞通常存在于三维空间或者二维空间中，其在三维空间中的运动类似布朗运动，这对于研究元胞间的联系，建立空间模型十分不利。常用的元胞自动机是二维的，它又分成三角形、正方形和正六边形，如图1所示，其优缺点比较如表1。

图1 二维元胞自动机的三种网格划分

表1 三种网格比较

综合三种二维网格模型，为进行故障传播性研究，选取正方形网格为研究对象，研究者通过大量的分析得知，如果将所有元胞映射到二维空间，即元胞间只存在二维网格连接，这将会化简模型，同样也可以表征元胞间的演化和位置变换。在二维空间的正方形网格模型中，邻居模型主要有5邻居模型（Von Neumann简称VN），9邻居模型（Moore简称MR）和25邻居模型（Extend Moore简称EM）。

2.2 演化规则

定义每个元胞的位置表示为 r=（i，j），其中 i，j∈（1，n）。根据演化规则：Si（t+1）=f（Si-r，Si-r+1，…，Si，…，Si+r-1，Si+r），Si表示第i个元胞的状态。在二维空间中，定义Aij（t）表示元胞在t时刻的输出状态，得

其中θ表示故障阈值；ε表示邻居元胞耦合度；X1、X2、X3、X4表示 5 邻居模型中元胞 r的左、右、上、下4个邻居，其取值为0和1；Sij（t）表示元胞r的故障程度，其值的大小正向影响邻居元胞状态，通过式（1）可知，当0＜Sij（t）＜θ时，元胞r状态正常，当Sij（t）≥θ或者Sij（t）=0时，元胞失效并产生故障。

2.3 故障传播行为

定义存在外部干扰或者电路内部元器件失效为故障扰动。分析可知，当CA中的所有元胞初始状态均满足0＜Sij（t）＜θ，且无故障扰动时，元胞将在任意t时刻保持正常状态。设定t'时刻Sij（t'）≥θ，即元胞r产生功能故障，此时为添加故障扰动ω状态。

经过分析可知，元胞的邻居对于主元胞的影响往往是不同的，其耦合度值也不同，所以式（3）没有考虑元胞中每个邻居对于主元胞的影响，其改进型如式（4）所示。

随着时间的推移，可知t'时刻以后故障不会自动恢复，从t'+1时刻开始故障元胞r将影响其邻居状态。根据耦合度关系，可以得出邻居元胞故障程度，以ri-1j为例，其故障程度表达式为：

根据式（1）、式（2）、式（5）可以求得邻居元胞状态，当邻居元胞超出阈值，产生故障再影响它的邻居，由此产生故障传播和扩散，设定故障规模达到最大值时，状态空间稳定，故障传播结束。

3 实例分析

以某型装备中的关键部件为例进行研究。某型装备控制盒是一种调速控制装置，它包括自动板、半自动版、输出板、反馈板等，这里主要研究其关键部件—输出板。将输出板模块划分为三角发生器模块、比较器模块、驱动器模块、累加器模块、倒向器模块和放大器模块，如图2所示。

图2 输出板各模块组成

根据统计数据及FMECA故障分析，各个模块之间的耦合度和模块对系统的影响因子如表2所示，可知三角波发生器模块对系统影响较大，与其他模块耦合度较高。

表2 模块耦合度与系统影响因子

本例运用VN模型分析输出板各模块关系如图3所示。对于故障的判定，不同的专家系统有不同的判定依据。这里设定各模块的故障发生阈值θ=0.3，即认为三角波电路模块故障值超过0.3时为t时刻，该模块产生故障现象，并且影响邻居模块状态，产生故障传播行为。经过统计数据分析，设定三角波电路模块在t-1时刻为正常状态，其故障程度满足0＜Sij（t-1）＜θ，为计算方便，设置该时刻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）＞θ，三角波模块产生故障。该故障将传播至倒向器、比较器、驱动器及其他部分。由式（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，可知比较器故障值超过阈值，产生故障行为，进而传播故障给其邻居。以此类推，直至系统稳定，不再产生新故障。此外，电路中故障存在逆向传播的行为，次级电路会影响上一级电路［9］，但是其影响力很小，所以在故障传播的研究中，为了计算方便，避免陷入死循环，可以忽略这一部分故障传播，认为理想状态下电路故障是按照一定的逻辑进行传播的［10］。

图3 输出板各模块的VN模型

在分析故障传播影响后，认为三角波发生电路对于输出板的故障影响最大，同时三角波模块产生故障后会存在故障传播现象，对于输出板其他模块产生影响，造成其他模块的故障产生。所以在选取本电路的故障样本时，只需对三角波发生电路进行分析，在故障注入阶段也可以针对于三角波发生电路进行故障注入。运用的方法是添加信号噪声，使叠加噪声的三角波输出波形的幅值、周期发生改变，以影响电路功能，实现故障的注入。针对于三角波信号叠加可以利用信号发生器产生特定周期和幅值的信号，应用已有的基于探针的故障注入设备可以将所产生的故障源信号叠加到正常三角波信号管脚处，这里将不作具体注入方法的表述。作为一种动态过程，基于本方法的故障注入可以实时地进行。

4 结论

本文提出了一种基于元胞自动机的故障样本选取方法，研究了故障传播行为，这种方法实质上完成了故障样本的等效注入，通过注入易操作的故障样本，避免了对于不易注入的故障样本的操作，简化了故障注入的流程，对于提高测试性验证工作的效率具有深刻的意义。

［1］余雷.基于元胞自动机的传染病传播模型研究［J］.计算机工程与应用，2007，54（2）：196-198.

［2］游爱丽，闫萍.基于元胞自动机的甲型HINI流感病毒的模型［J］.新疆大学学报，2010，46（2）：56-59.

［3］汪小帆，李翔，陈关荣.复杂网络理论及其应用［M］.北京：清华大学出版社，2006：162-163.

［4］于鑫.基于元胞自动机的流行病传播模型模拟［J］.计算机工程与应用，2005，52（2）：205-209.

［5］李果，高建民，高智勇，等.基于小世界网络的复杂系统故障传播模型 ［J］. 西安交通大学学报，2007，41（3）：334-338.

［6］吴继梅，白慧，邵世煌.一种复杂电路功能故障传播模型［J］.微型电脑应用，2008，24（1）.4-7.

［7］连可，黄建国，龙兵.一种基于有向图模型的模糊多故障诊断算法 ［J］. 系统工程与电子技术，2008，30（3）：568-571.

［8］王哈力，单慧.基于复杂网络的小型模拟电路分析［D］.哈尔滨理工大学学报，2006，11（3）：11-17.

［9］高凤岐，连光耀，黄考利，等.基于半实物仿真的电路板故障注入系统设计与实现［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- ），男，河北唐山人，硕士研究生。研究方向：测试性验证。