基于GT-CA的铁路继电电路逻辑仿真方法研究

Research on Logic Simulation Method of Railway Relay Circuits Based on GT-CA

摘要

针对现有继电电路分析过程的复杂性和不透明性，以及大规模电路分析困难的问题，提出基于图论（GT）和元胞自动机（CA）的铁路继电电路逻辑功能仿真方法。首先，对继电电路进行形式化描述，并引入短电路概念以简化电路结构；其次，制定将继电电路转化为有向图的规则，并基于基尔霍夫电流定律设计有向图方向的判断规则，构建继电电路的元胞自动机模型并制定其演化规则；最后，通过实际继电电路的测试案例，展示电路的动态执行过程，并与预期执行结果进行对比，以验证仿真方法的正确性和有效性。结果表明：4种测试场景下的仿真过程及结果与预期效果一致，基于GT-CA的铁路继电电路逻辑仿真方法具备准确实现铁路继电电路逻辑功能仿真的能力，可为铁路继电电路的设计校验和故障查找提供理论参考和技术支撑。

Abstract

Regarding the complexity and opacity of the existing analysis process for relay circuits, and the difficulty of large-scale circuits analysis, a logic function simulation method of railway relay circuits based on Graph Theory (GT) and Cellular Automata (CA) is proposed. Firstly, a formal description of relay circuits was given, and the short circuit concept was introduced to simplify the circuit structure. Secondly, the rules for transforming relay circuit into directed graph were formulated, and the judgement rules of the directed graph direction were designed based on Kirchhoff's Current Law (KCL). Besides, the CA model of the relay circuits was constructed and its evolution rules were formulated. Finally, through the case study of actual relay circuits, the dynamic execution process of circuits was demonstrated and compared with the expected execution results to verify the correctness and effectiveness of the simulation method. The results show that the simulation process and results are consistent with the expected effects under 4 test scenarios, and the logic simulation method of railway relay circuits based on GT-CA has the ability to accurately realize the logic function simulation of railway relay circuits, which can provide theoretical reference and technical support for the design verification and error finding of railway relay circuits.

Graphical abstract

关键词

铁路继电电路 / 图论 / 元胞自动机 / 逻辑功能仿真

Key words

Railway relay circuit / Graph Theory (GT) / Cellular Automata (CA) / Logical function simulation

继电器作为继电电路的控制元件，其接点的开闭状态受线圈的通电情况控制^［1］，并通过改变电路连通情况实现逻辑运算功能，构成典型的逻辑电路系统。鉴于铁路信号系统对继电电路可靠性与安全性的严格要求，在设计及应用过程中必须对电路的动态执行过程进行深入的理论分析。因此，开展铁路继电电路逻辑功能分析方法的研究，对推进铁路信号工程设计的数字化转型具有重要的理论价值和工程意义。

由于继电电路拓扑结构复杂，人工分析效率较低且易出错，采用形式化建模与计算机仿真技术可显著提高分析效率并降低成本^［2］。早在20世纪80年代，学者们就开始探索基于图论的继电时序电路分析方法^［3］。文献［4］利用开关的选择特性，基于二叉树结构模拟DNA开关电路的运算过程。文献［5］通过将电路抽象为无向图（网络节点对应图顶点，元器件对应边），构建状态方程实现继电电路潜通路分析。文献［6］采用广度优先搜索策略，开发了基于有向图和图形处理单元的并行算法，有效缓解了电路结构枚举过程中的指数级增长问题。

在仿真电路动态执行过程时，众多学者依据通路搜索结果构建电路状态方程^［7］，但其并未充分考虑继电器接点的互斥关系。与此同时，部分学者采用形式化建模方法，旨在构建电路的精确形式化模型。文献［8］基于有限状态机构建了大规模时序电路的合成算法，为快速单通量量子逻辑电路的集成设计提供了新思路。文献［9］使用有限状态机描述继电电路的动态特性，并开发了具有普适性的状态转移函数求解算法。文献［10-11］构建了完备的电路Petri网模型，实现对不同输入激励下潜在通路的系统性检测与分析。文献［12］基于智能体-元胞自动机模型，清晰展示了继电电路的动态执行过程及电路元件的相互影响关系。尽管上述研究已初步实现继电电路的仿真功能，但在分析过程的优化和适用场景的拓展方面仍存在明显不足。

针对上述问题，本研究基于图论（Graph Theory，GT）和元胞自动机（Cellular Automata，CA）理论，提出1种面向铁路继电电路逻辑功能的新型仿真方法。首先对继电电路中的关键元件进行形式化建模，然后制定电路有向图与CA模型的构建规则，最终通过典型工程案例的系统仿真，验证所提方法的可行性与有效性。

1 既有继电仿真方法局限与GT-CA系统架构

1.1　既有继电仿真方法局限

继电电路逻辑仿真的核心在于通过理论分析揭示电路的动态逻辑特性，其基本原理为：通过输入命令激励继电器状态变化，并基于电路拓扑结构逐级传播状态变化的影响，直至无新的影响产生时分析结束^［13］。虽然该领域已有大量研究成果，但现有方法仍存在以下主要局限性。

（1）适用范围较为局限。铁路继电电路中的设备种类繁多，且不同设备的逻辑特性存在较大差异。现有研究的建模设备较为单一，未能全面涵盖所有常用的电路元件。例如，在电源方面，现有方法仅支持直流电源的逻辑处理，尚未扩展至交流电源的仿真分析；在继电器方面，目前仅针对无极继电器建立了形式化模型，而对整流继电器、有极继电器及偏极继电器的逻辑特性尚未实现系统性建模与分析。

（2）分析颗粒度过细。现有研究普遍采用基于单个电路元件的离散化分析方法，通过逐个计算各元件状态实现电路整体状态的映射。尽管该方法在实现层面具有简便性，但计算复杂度随电路规模呈指数级增长，导致其难以满足大规模电路系统的仿真需求。

（3）通路搜索方法存在弊端。常用的电路通路搜索方法主要有2种：一种需要在仿真过程中根据继电器线圈状态的变化重构电路的连接关系，并基于可导通路径搜索现有通路^［14］；另一种则需要假设所有开关元件均处于导通状态，从而获取电源间的所有潜在通路^［15］。因此，现有的通路搜索方法在仿真过程中需要频繁重构电路拓扑关系，或者生成大量非必要路径，大幅增加了仿真软件的存储与计算负担。

1.2　基于GT-CA继电电路逻辑仿真系统架构

针对现有仿真方法的不足，以铁路继电电路为研究对象，以GT和CA为理论基础，将动作程序法和接通径路法相结合，构建基于GT-CA的继电电路逻辑仿真系统架构，如图1所示。

该系统架构由3个模块构成，其中继电电路形式化描述模块主要负责电路元件的数学建模与结构简化，将继电器、电源等电路元件抽象为5种基本类型，构建其数学模型并采用形式化语言精确描述元件间的逻辑关系^［16］，同时引入短电路分割技术，实现电路拓扑结构的初步简化；继电电路有向图模块基于图论方法实现电路结构的转换与分析，首先制定拓扑结构到有向图的映射规则，随后基于基尔霍夫电流定律（Kirchhoff’‍s Current Law，KCL）制定有向图方向判定准则，通过规范通路搜索方向显著减少无效路径的遍历过程；继电电路CA仿真模块通过制定继电电路元胞邻居的获取规则和元胞状态的演化规则，构建继电电路的CA仿真模型，并通过在离散时间点记录模型的元胞状态和演化流程，获取电路执行过程中元件的状态变化与影响关系。

与既有研究相比，所提方法具有显著优势。该方法创新性地结合了GT和CA的优点，通过将继电电路拓扑表示为有向图结构，将通路搜索问题转化为图论路径问题^［17-18］。同时，借助CA对强耦合非线性系统动态过程的模拟能力^［19-20］，利用其并发性和迁移规则，直观呈现电路执行过程和元件状态变化，显著提升了可视化效果。该方法对铁路继电电路的常用元件进行了形式化描述，构建了以短电路为基本分析单元的仿真模型，在保持继电逻辑的同时降低电路耦合度，适用于大规模电路分析。此外，此方法基于KCL制定了有向图方向判定规则，并采用深度优先搜索策略获取全部通路^［21］，优化了通路搜索效率和准确性。

2 继电电路逻辑仿真方法

2.1　继电电路形式化描述

2.1.1　电路元件形式化描述

继电电路中的电路元件按照逻辑功能可以抽象为5类：电源、继电器线圈、接点、负载和连接点。连接点是电路支路的交汇点，其至少连接3条支路。负载是继电电路中除电源、继电器和连接点之外的其余设备，负载状态的改变不会对电路的整体结构和其他元件状态产生影响。将继电电路R抽象为7元组，其定义式为

R=(P,W,G,K,J,F,Y(x))（1）

其中，

P=P_{\mathrm{1}}\bigcup P_{\mathrm{2}}\bigcup P_{\mathrm{3}}\bigcup P_{\mathrm{4}}

W=W_{\mathrm{W}}\bigcup W_{\mathrm{Y}}\bigcup W_{\mathrm{P}}\bigcup W_{\mathrm{Z}}

G=G_{\mathrm{F}}\bigcup G_{\mathrm{M}}\bigcup G_{\mathrm{B}}\bigcup G_{\mathrm{O}}

式中：P为电源的有限集合；W为继电器线圈的有限集合；G为继电器接点和开关的有限集合；K为负载的有限集合；J\mathrm{为}连接点的有限集合；F为继电器接点和线圈的映射函数；Y(x)为电路元件的状态函数；P_{\mathrm{1}}，P_{\mathrm{2}}，P_{\mathrm{3}}和P_{\mathrm{4}}分别为直流正电源、交流正电源、直流负电源和交流负电源的集合；W_{\mathrm{W}}，W_{\mathrm{Y}}，W_{\mathrm{P}}和W_{\mathrm{Z}}分别为无极、有极、偏极和整流继电器线圈集合；G_{\mathrm{F}},G_{\mathrm{M}},G_{\mathrm{B}}\mathrm{和}{G}_{\mathrm{O}}分别为继电器的前、中、后接点集合和开关触点集合。

继电器接点组集合G_T为

G_{\mathrm{T}}=\left\{g_{\mathrm{T}}|g_{\mathrm{T}}=(g_{\mathrm{F}},g_{\mathrm{M}},g_{\mathrm{B}})\right\}（2）

式中：g_{\mathrm{T}}为单独的接点组；g_{\mathrm{F}}，g_{\mathrm{M}}和g_{\mathrm{B}}分别为前、中、后接点元素。

一个继电器包含多个接点组，单个接点组的前、中、后接点数量均为1。继电电路中任意的继电器接点均存在唯一的继电器线圈与之对应，即\forall g\in (G/G_{\mathrm{O}})，\exists !w=F(g)，w\in W。同时任意的线圈均存在至少1组接点与之对应，即\forall w\in W,\exists G^{\text{'}}=F^{-\mathrm{1}}(w)，G\text{'}\subseteq G。

在继电电路分析中，继电器线圈的状态映射函数为Y(w)，即\forall w\in W，Y:W\to \{\mathrm{0,1},\mathrm{2}\}。其中，0表示线圈断电；1表示线圈正向通电；2表示线圈反向通电；“\to”表示2个集合的映射关系。继电器接点的状态映射函数为Y(g)，即\forall g\in G，Y:G\to \{\mathrm{0,1}\}，其中0表示接点断开，1表示接点接通。接点和线圈的状态满足如下约束条件。

（1）继电器的中接点始终为接通状态，即

对于\forall g_{\mathrm{M}}\in G_{\mathrm{M}},存在Y(g_{\mathrm{M}})=\mathrm{1}

（2）继电器接点的状态规则为

\left\{\begin{array}{c}Y(g_{\mathrm{1}})=Y(g_{\mathrm{2}})\\ Y(g_{\mathrm{3}})=Y(g_{\mathrm{4}})\\ Y(g_{\mathrm{1}})+Y(g_{\mathrm{3}})=\mathrm{1}\end{array}\right.（3）

式中：g_{\mathrm{1}},g_{\mathrm{2}},g_{\mathrm{3}},g_{\mathrm{4}}为继电器接点，g_{\mathrm{1}},g_{\mathrm{2}}\inG_{\mathrm{F}}(w)，g_{\mathrm{3}},g_{\mathrm{4}}\in G_{\mathrm{B}}(w)；Y(g)为接点g的状态函数；G_{\mathrm{F}}(w)和G_{\mathrm{B}}(w)为线圈w对应的前、后接点集合。同一继电器的所有接点中，前、后接点的状态相同，且其状态值之和为1。

继电器线圈状态直接决定其接点状态，其影响关系见表1。对于缓动继电器，当继电器线圈状态改变且满足缓动时间后，接点状态随之改变；对于其他类型的继电器，接点和线圈的状态同步变化。

2.1.2　继电电路短电路模型

铁路继电电路规模庞大、元件数量众多，现有的以电路元件为基本单位的分析方法会导致电路仿真过程复杂，同时难以分析大规模电路。为简化电路分析过程，在保持电路结构不变的前提下，引入短电路概念，通过分界点将继电电路划分为若干短电路，实现电路结构的解耦操作。短电路的分界点集合U为

U=P\bigcup J\bigcup G_U（4）

式中：G_U\mathrm{为}所有接点均构成电路的接点组的中接点集合。

为进一步简化电路结构，需对通过导线直接相连的分界点进行归一化处理。即若两相邻分界点间无其余电路元件，则将其合并为1个分界点。

短电路O为2个分界点间的线性电路，其以2个相邻的分界点作为端点，并且包含分界点间所有电路元件。映射M:O\to (P\bigcup W\bigcup G\bigcup K\bigcup J)记录短电路内部的电路元件信息；映射B:O\to U表示短电路与分界点的对应关系，即\forall o\in O,\exists B(o)=\left\{u_{\mathrm{1}},u_{\mathrm{2}}\right\},u_{\mathrm{1}},u_{\mathrm{2}}\in U\mathrm{。}不同种类线圈的分界点记录情况如图2所示。图中：U_{\mathrm{1}}(w)和U_{\mathrm{2}}(w)分别表示与线圈w正向节点和反向节点相距较近的分界点。

2.2　继电电路有向图

2.2.1　有向图基本定义

为确保继电电路的抽象拓扑结构与电路原有结构的一致性，同时为明确电路通路的搜索方向，使用有向图描述电路拓扑结构，将电路分界点抽象为顶点，将短电路抽象为边，并使用边的方向表示电流方向。

有向图D是由一系列顶点及与其相连具有方向性的边组成，可表示为

D=(V,A)（5）

式中：V为有向图的顶点集合；A为有向图的边集合，边集A为顶点集V的笛卡尔积，即A=V\times V。

在图论中，顶点v的度定义为与该顶点关联的边的总数，记作\mathrm{d}\mathrm{e}\mathrm{g}(v)。有向图的入度和出度分别表示以v为终点和起点的边数。路径p=(v_{\mathrm{0}},a_{\mathrm{1}},v_{\mathrm{1}},a_{\mathrm{2}},\dots ,a_n,v_n)是从顶点v_{\mathrm{0}}到顶点v_n的交错序列，其中v_i表示有向图顶点，a_i表示有向边。若路径中所有边互不相同，则称其为迹，简称为(v_{\mathrm{0}},v_n）迹。

2.2.2　有向图映射规则

在构建继电电路的有向图时，使用映射E:U\to V将电路分界点抽象为有向图顶点，并使用映射I:O\to A将短电路抽象为有向边。有向图需重点记录边的互斥关系、内部的元件信息和方向，因此将继电电路的有向图抽象为6元组，其定义式为

D=(V,A,H,Q,Z,X)（6）

其中，

V=V_{\mathrm{Z}}\bigcup V_{\mathrm{F}}\bigcup V_{\mathrm{M}}

V_{\mathrm{Z}}=\left\{E(u)|u\in (P_{\mathrm{1}}\bigcup P_{\mathrm{2}})\right\}

V_{\mathrm{F}}=\left\{E(u)|u\in (P_{\mathrm{3}}\bigcup P_{\mathrm{4}})\right\}

V_{\mathrm{M}}=\left\{E(u)|u\notin P\right\}

式中：H为边的互斥函数；Q为边与继电器线圈的映射函数；Z为边与继电器接点的映射函数；X为边的方向函数；V_{\mathrm{Z}}，V_{\mathrm{F}}和V_{\mathrm{M}}分别为有向图的起始、终止和中间顶点集合。

有向图中的互斥边成对存在，即若a_{\mathrm{1}}与a_{\mathrm{2}}为一对互斥边，则H(a_{\mathrm{1}})=a_{\mathrm{2}}，同时H(a_{\mathrm{2}})=a_{\mathrm{1}}。边的互斥应满足如下条件。

条件1：a_{\mathrm{1}}与a_{\mathrm{2}}具有相同的顶点，且该顶点对应继电器的中接点，即

a_{\mathrm{1}}\bigcap a_{\mathrm{2}}=E(u)（7）

式中：u为继电器的中接点；E(u)为u对应的有向图顶点。

条件2：a_{\mathrm{1}}和a_{\mathrm{2}}分别包含相同继电器的前、后接点，即

\left\{\begin{array}{c}(F^{-\mathrm{1}}(w)\bigcap Z(a_{\mathrm{1}}))\subseteq G_{\mathrm{F}}\\ (F^{-\mathrm{1}}(w)\bigcap Z(a_{\mathrm{2}}))\subseteq G_{\mathrm{B}}\end{array}\right.（8）

式中：w为分界点对应的线圈；F^{-\mathrm{1}}(w)为线圈对应的继电器接点集合；Z(a_i)为边a_i包含的继电器接点集合；G_{\mathrm{F}}和G_{\mathrm{B}}分别为继电器的前接点和后接点集合。

线圈和接点是继电电路的核心控制元件，因此有向图额外记录边包含的线圈与接点信息。对于\forall o\in O,\mathrm{且}a=I(o),则Q(a)=M(o)\bigcap W，Z(a)=M(o)\bigcap G。

2.2.3　有向图方向判断规则

有向图使用边的方向表示边所对应的短电路的电流方向，并使用X:V\to \{-\mathrm{1,0},\mathrm{1}\}表示边在顶点处的电流方向。其中，－1和1分别表示电流流入和流出顶点，0表示电流既可流入顶点，也可流出顶点。

\forall a\in A，a=\{v_{\mathrm{1}},v_{\mathrm{2}}\}，a的方向存在3种情况。

（1）电流由v_{\mathrm{1}}流向v_{\mathrm{2}}，即

（9）

（2）电流由v_{\mathrm{2}}流向v_{\mathrm{1}}，即

（10）

（3）电流为双向的，v_{\mathrm{1}}和v_{\mathrm{2}}间存在2条有向边，即

（11）

式中：“\equiv”为等价符号；表示有向边a以顶点v_{\mathrm{1}}，v_{\mathrm{2}}为端点，方向为v_{\mathrm{1}}指向v_{\mathrm{2}}。

综上，\forall a\in A,a=\left\{v_{\mathrm{1}},v_{\mathrm{2}}\right\}，X(v_{\mathrm{1}})+X(v_{\mathrm{2}})=\mathrm{0}恒成立。因此，边的方向可由其任意端点表示，使用a:X(v_{\mathrm{1}})和a:X(v_{\mathrm{2}})表示边a的方向。

根据KCL，在电路的任意节点上，流入节点的电流之和等于流出节点的电流之和，故边a的方向满足如下规则，各规则示例如图3所示。

规则1：若E^{-\mathrm{1}}(v_{\mathrm{1}})\in P_{\mathrm{1}}，则。

规则2：若E^{-\mathrm{1}}(v_{\mathrm{1}})\in P_{\mathrm{3}}，则。

规则3：在Q(a)\bigcap W_{\mathrm{Z}}=w_{\mathrm{Z}}条件下，若v_{\mathrm{1}}=U_{\mathrm{1}}(w_{\mathrm{Z}})，则；否则，。

规则4：对于\forall v_{\mathrm{i}}\in V，若\mathrm{d}\mathrm{e}\mathrm{g}(v_{\mathrm{i}})=n(n\ge \mathrm{2})，则\exists A^{\mathrm{\text{'}}}=\{a_{\mathrm{1}},a_{\mathrm{2}},\dots ,a_n|a_{\mathrm{1}}\bigcap a_{\mathrm{2}}\bigcap \dots \bigcap a_n=v_i\}，{\mathrm{A}}^{\mathrm{\text{'}}}\subseteq A。若\exists a_i\in \mathrm{A}\mathrm{\text{'}},a_i:X(v_i)\ne \mathrm{0}，则\exists a\mathrm{\text{'}}\in A\mathrm{\text{'}},a\mathrm{\text{'}}:X(v_i)\ne \mathrm{0}。

规则5：对于\forall v_i\in V，若\mathrm{d}\mathrm{e}\mathrm{g}(v_i)=\mathrm{2}，则\exists a_{\mathrm{1}},a_{\mathrm{2}}\in A,a_{\mathrm{1}}\bigcap a_{\mathrm{2}}=v_i，同时a_{\mathrm{1}}:X(v_i)+a_{\mathrm{2}}：X(v_i)=\mathrm{0}。

规则6：对于\forall v_i\in V，若\mathrm{d}\mathrm{e}\mathrm{g}(v_i)=n(n\ge \mathrm{3})，且H(a_{\mathrm{1}})=a_{\mathrm{2}}，同时，a_{\mathrm{3}}:X(v_i)=\dots =a_n:X(v_i)，则a_{\mathrm{1}}:X(v_i)=a_{\mathrm{2}}:X(v_i)=-a_{\mathrm{3}}:X(v_i)。

规则1—规则3描述了有向元件对方向的影响：若顶点对应直流正电源，则电流流出该顶点；若顶点对应直流负电源，则电流流入该顶点；若短电路包含整流继电器线圈，则短电路的电流方向与整流继电器的正方向相同。

规则4—规则6描述了根据已知方向边推导未知方向边的规则：规则4是对继电电路KCL的形式化描述，即一个节点存在输入电流，则其必然存在输出电流；规则5—规则6是规则4的推广，规则5描述了当顶点仅存在2条关联边时，边的方向必定相同；规则6描述了当顶点关联一对互斥边，且其余边的方向相同时，互斥边的方向和其余边的方向相同。

在判断有向图的方向时，以顶点为单位，判断与顶点关联的边的方向。首先，设置满足规则1—规则3的顶点关联边方向，并初始化顶点队列q；然后，使用基于KCL的广度优先搜索算法，设置满足规则4—规则6的顶点关联边方向；最后，对于未设置方向的顶点，将其关联边设置为双向。

基于KCL的广度优先搜索算法流程如图4所示。其中，“顶点未设置方向”表示顶点存在未设置方向的关联边，“顶点满足规则”表示可基于规则设置顶点的所有关联边的方向。

2.3　继电电路元胞自动机模型

2.3.1　元胞自动机定义

元胞自动机模型的核心架构包含元胞、元胞空间、元胞状态、元胞邻居和演化规则5个部分。故将继电电路的元胞自动机模型C_{\mathrm{A}}抽象为5元组，其定义式为

C_{\mathrm{A}}=(C,L,S,N,f)（12）

式中：C\mathrm{为}元胞的有限集合；L\mathrm{为}元胞空间；S\mathrm{为}元胞状态函数；N\mathrm{为}元胞邻居集合；f\mathrm{为}演化规则。

在构建继电电路的CA模型时，使用映射h:A\to C将电路拓扑结构中的有向边映射为元胞；同时，传统CA的元胞空间呈规则的线性或网状结构，然而继电电路的元胞分布与电路结构有关，故将继电电路的元胞空间表示为不规则的2维网状结构。

元胞状态由拓扑边对应的短电路内部元件状态和元胞邻居状态共同决定。即\forall c\in C,S:C\to\{\mathrm{0}，\mathrm{1,2}\}，其中，0表示短电路断开，1表示短电路接通但并未构成完整回路，2表示短电路接通且构成完整回路。

2.3.2　元胞邻居获取规则

根据元胞影响关系的不同，将元胞邻居划分为2种类型，即

N=N_{\mathrm{M}}\bigcup N_{\mathrm{E}}（13）

式中：N_{\mathrm{M}}为激励邻居集合，用于执行继电器线圈对接点的影响逻辑；N_{\mathrm{E}}为通路邻居集合，用于执行电路回路对短电路状态的影响逻辑。

在有向图中使用深度优先搜索算法可得到多条(V_{\mathrm{Z}},V_{\mathrm{F}})迹，将第i条(V_{\mathrm{Z}},V_{\mathrm{F}})迹经过的边顺序存储在迹序列T_i中，并将T_i中的边映射为元胞，从而得到电路的通路元胞子序列N_{Ei}。

对于\forall a\in A,h(a)=c，元胞c的邻居满足如下规则。

规则7：若元胞内存在继电器线圈，则包含该继电器前、后接点的元胞为当前元胞的激励邻居，并称当前元胞为激励元胞，即，\mathrm{对于}\forall w\in Q(a)，G\text{'}=F^{-\mathrm{1}}(w)\bigcap (G_{\mathrm{F}}\bigcup G_{\mathrm{B}})，若Z(a_i)\bigcap G\text{'}\ne \mathrm{\varnothing }，则h(a_i)\in N_{\mathrm{M}}(c)；

规则8：若通路元胞子序列N_{Ei}包含元胞c，则N_{Ei}中除元胞c外的所有元胞为元胞c的通路邻居，即，若c\in N_{Ei}，则N_{Ei}(c)=N_{Ei}-\{c\}。

将第i条(V_{\mathrm{Z}},V_{\mathrm{F}})迹上的通路邻居顺序存储在通路邻居子序列N_{Ei}(c)中，并使用二维数组N_E(c)存放所有的N_{Ei}(c)。

2.3.3　元胞状态演化规则

将触发元胞状态迁移的事件定义为激励事件，并根据激励事件的产生来源将其划分为外部激励和内部激励2种类型。其中，外部激励由电路的外部输入命令产生，而内部激励由元胞邻居产生。

对于\forall c\in C(h(a)=c)，S_t(c)表示元胞的当前状态，S_{t+\mathrm{1}}(c)表示元胞的预期状态。继电电路CA模型的元胞演化过程如图5所示。外部激励与内部激励组成激励事件，激励事件和元胞的当前状态共同决定元胞的预期状态和预期影响。预期影响作为内部激励继续影响其元胞邻居的状态。

将CA的演化规则表述为“激励事件—当前状态—预期状态—预期影响”的形式化结构，即：若激励事件成立且当前状态满足条件，则系统将转移至预期状态并产生预期影响。

继电电路的5种元胞状态演化情况见表2。其中，e_{\mathrm{4}}在所有激励事件中的优先级最高。若元胞同时满足情况2和情况5，则优先执行情况5；若同时满足情况3和情况4，则优先执行情况4。

以元胞c为例(c=h(a))，表中各事件和影响的具体含义如下。

（1）事件e_{\mathrm{1}}表示元胞内所有触点均为接通状态，即\mathrm{对于}\forall g\in Z(a),Y(g)=\mathrm{1}。若元胞不包含触点，则其不能为断开状态，即若\mathrm{Z}(a)=\mathrm{\varnothing }，则\mathrm{S}(c)\ne \mathrm{0}。

（2）事件e_{\mathrm{2}}\mathrm{表示}元胞至少存在1个通路邻居子序列，且该序列中所有的通路邻居均不存在未接通状态，即\exists N_{Ei}(c)\in N_E(c),\mathrm{对于}\forall c^{\mathrm{\text{'}}}\in N_{Ei}(c)，S(c\mathrm{\text{'}})\ne \mathrm{0}。

（3）事件e_{\mathrm{3}}\mathrm{表示}元胞的所有通路邻居子序列中均存在未接通的元胞，即对于\forall N_{Ei}(c)\in N_E(c)，\mathrm{均}\exists c^{\mathrm{\text{'}}}\in N_{Ei}(c),S(c^{\mathrm{\text{'}}})=\mathrm{0}。

（4）事件e_{\mathrm{4}}\mathrm{表示}元胞内存在断开的触点，即若\exists g\in Z(a),\mathrm{则}Y(g)=\mathrm{0}。

（5）i_{\mathrm{1}}，i_{\mathrm{3}}和i_{\mathrm{5}}表示演化情况对通路邻居的影响。其中，影响i_{\mathrm{1}}\mathrm{表示}元胞的通路邻居可能满足情况2，即若\exists c^{\mathrm{\text{'}}}\in N_{Ei}(c)，则c^{\mathrm{\text{'}}}可能满足情况2；i_{\mathrm{3}}表示N_{Ei}(c)中所有元胞的预期状态均为通电状态，即\forall c^{\mathrm{\text{'}}}\in N_{Ei}(c),S_{\mathrm{t}+\mathrm{1}}(c^{\mathrm{\text{'}}})=\mathrm{2}；i_{\mathrm{5}}表示元胞的通路邻居可能满足情况3，即若\exists c^{\mathrm{\text{'}}}\in N_{Ei}(c)，则c^{\mathrm{\text{'}}}可能满足情况3。i_{\mathrm{2}}和i_{\mathrm{4}}表示元胞通电和断电对激励邻居的影响。

在执行元胞对激励邻居的影响时，首先，根据影响情况设置元胞内部线圈状态。对于\forall w\in Q(a)，i_{\mathrm{2}}根据式（14）判定线圈的通电方向；i_{\mathrm{3}}则直接将线圈设置为断电状态（Y(w)=\mathrm{0}）。其次，根据表1执行线圈状态对激励邻居的影响，触发其激励邻居的状态演化，使其满足情况1，4或5。上述i_{\mathrm{2}}对线圈通电方向的判定式为

Y\left(w\right)=\left\{\begin{array}{c}\mathrm{1},h^{-\mathrm{1}}(c_{n-\mathrm{1}})\bigcap h^{-\mathrm{1}}(c)=U_{\mathrm{1}}(w)\\ \mathrm{2},h^{-\mathrm{1}}(c_{n-\mathrm{1}})\bigcap h^{-\mathrm{1}}(c)=U_{\mathrm{2}}(w)\end{array}\right.（14）

式中：c_{n-\mathrm{1}}为元胞c通路邻居的前驱元胞；h^{-\mathrm{1}}(c)为元胞c对应的拓扑边。

3 仿真流程与验证

3.1　仿真操作流程

继电电路仿真平台由继电电路构建软件、上位机软件、继电电路仿真分析软件和电路动态可视化软件构成，其整体架构如图6所示。

首先，电路构建软件通过绘制继电电路图，或读取配线表获取继电电路中各元件的连接关系；其次，上位机软件手动设置关键元件的状态，作为电路仿真的外部激励；随后，继电电路仿真分析软件根据静态数据流实现继电电路的有向图和CA模型构建，根据控制数据流进行仿真动态数据运算；最后，将电路的动态执行过程输出至电路动态可视化软件，实现仿真结果的动态展示。

3.2　测试案例仿真验证

3.2.1　测试案例

选用计算机联锁车站的进站信号机点灯电路作为测试案例，该电路拥有1U，L，H，2U和YB共5个点灯单元和灯丝电路，将各点灯单元和灯丝电路视为1个整体，并将其抽象为负载。测试案例的元件情况见表3。

测试案例的电路图如图7所示，在接点组旁使用箭头标注继电器的常态。图中：“↑”表示继电器常态为励磁吸起状态；“↓”表示继电器常态为断电落下状态；\mathrm{1}\mathrm{D}\mathrm{J}和\mathrm{2}\mathrm{D}\mathrm{J}为整流缓放继电器线圈，其状态受内部激励影响；\mathrm{L}\mathrm{X}\mathrm{J},\mathrm{Y}\mathrm{X}\mathrm{J},\mathrm{T}\mathrm{X}\mathrm{J}，\mathrm{L}\mathrm{U}\mathrm{X}\mathrm{J},\mathrm{Z}\mathrm{X}\mathrm{J}线圈为无极继电器线圈，其状态仅受外部激励影响。

由于\mathrm{1}\mathrm{D}\mathrm{J}和\mathrm{2}\mathrm{D}\mathrm{J}的参数限制，在实际使用时并不会对点灯电路产生整流效果，且电路中不包含对电源极性敏感的元件，因此后续分析将电源视为直流电源处理。

3.2.2　测试案例有向图

对测试电路中直接相连的分界点进行归一化处理，并将2个相邻分界点之间的电路划分为1条短电路。根据继电电路有向图的映射规则，生成的测试案例有向图如图8所示，使用除黑色外的相同颜色的边表示互斥边。

测试案例的有向图包含2个起始顶点V_{\mathrm{Z}}=\{v_{\mathrm{1}},v_{\mathrm{7}}\}，1个终止顶点V_{\mathrm{F}}=\{v_{\mathrm{14}}\}，11个中间顶点和19条有向边。在其生成过程中，电路分界点与有向图顶点的对应关系见表4，有向图方向的设置过程见表5。

3.2.3　测试案例CA模型

根据继电电路CA的构建规则，将电路拓扑结构中的有向边抽象为元胞。考虑到线圈\mathrm{L}\mathrm{X}\mathrm{J},\mathrm{Y}\mathrm{X}\mathrm{J}，\mathrm{T}\mathrm{X}\mathrm{J},\mathrm{L}\mathrm{U}\mathrm{X}\mathrm{J},\mathrm{Z}\mathrm{X}\mathrm{J}虽未直接参与构建电路，但其控制的继电器接点存在于电路中。因此，将上述线圈所在短电路同样抽象为元胞，最终得到的测试案例CA模型如图9所示。

CA模型包含24个元胞，其中，元胞c_i（i\in\{\mathrm{1,2},\mathrm{3},\dots ,\mathrm{19}\}）为有向图的边对应元胞，即c_i=h(a_i)；元胞c_{\mathrm{L}},c_{\mathrm{Y}},c_{\mathrm{T}},c_{\mathrm{L}\mathrm{U}},c_{\mathrm{Z}}分别为\mathrm{L}\mathrm{X}\mathrm{J}，\mathrm{Y}\mathrm{X}\mathrm{J},\mathrm{T}\mathrm{X}\mathrm{J},\mathrm{L}\mathrm{U}\mathrm{X}\mathrm{J},\mathrm{Z}\mathrm{X}\mathrm{J}线圈所在短电路对应元胞。

仿真模型具有6个激励元胞和9个通路元胞子序列，其激励邻居与通路元胞子序列情况分别见表6和表7。

3.2.4　测试案例仿真过程

采用继电电路逻辑仿真方法对测试案例的4种典型场景进行验证，各场景详情见表8。其中，“\uparrow”表示继电器通电吸起；“\downarrow”表示继电器断电落下。

场景1为电路常态情况，此时无进路办理且进站信号机显示H灯；场景2模拟四显示自动闭塞区段办理通过进路时电路的响应特性，此时出站信号机显示黄灯；场景3模拟2U灯主、副灯丝均断丝情况下点灯电路的执行逻辑；场景4则模拟进站信号机故障时引导进路办理情况下的电路执行情况。依次仿真上述4种场景，通过在离散时间点记录短电路元胞的演化情况和实时状态，分析电路的执行过程和结果。所有短电路元胞的演化情况如图10所示，关键元胞的状态变化如图11所示。

仿真过程中各稳态的时间及含义见表9，仿真执行情况和状态含义见表10。

对4种测试场景的电路执行动态逻辑进行分析。场景1中，当\mathrm{L}\mathrm{X}\mathrm{J},\mathrm{T}\mathrm{X}\mathrm{J},\mathrm{L}\mathrm{U}\mathrm{X}\mathrm{J},\mathrm{Y}\mathrm{X}\mathrm{J}落下，\mathrm{Z}\mathrm{X}\mathrm{J}吸起时，S(c_{\mathrm{3}})=\mathrm{2}，此时H灯点亮；场景2中，当\mathrm{L}\mathrm{X}\mathrm{J}与\mathrm{L}\mathrm{U}\mathrm{X}\mathrm{J}吸起时，S(c_{\mathrm{3}})=\mathrm{0}，此时H灯熄灭，并接通2U灯点灯回路，导致2U灯点亮，同时2DJ吸起，并接通L灯的点灯回路，最终导致S(c_{\mathrm{10}})=\mathrm{2}，即L灯点亮；场景3中，当2U灯熄灭后，\mathrm{2}\mathrm{D}\mathrm{J}落下，此时将断开L灯的点灯回路，导致L灯熄灭和\mathrm{1}\mathrm{D}\mathrm{J}落下，并输入外部激励使\mathrm{L}\mathrm{X}\mathrm{J}和\mathrm{L}\mathrm{U}\mathrm{X}\mathrm{J}落下，最终导致S(c_{\mathrm{3}})=\mathrm{2}，即H灯点亮；场景4中，\mathrm{Y}\mathrm{X}\mathrm{J}吸起后将导致S(c_{\mathrm{13}})=\mathrm{2}，即YB灯点亮。由表8—表10可以看出，4种测试场景的仿真过程和结果与预期效果一致，证明了仿真方法的正确性与有效性。

4 结论

（1）本研究通过分析既有铁路继电电路逻辑功能仿真方法的不足，提出基于GT和CA的铁路继电电路逻辑功能仿真方法。该方法通过对继电电路的形式化描述制定短电路的划分规则，基于图论和KCL制定继电电路有向图的抽取规则，以此构建继电电路的CA模型并分析模型的演化过程。

（2）将短电路作为电路分析的基本单位，丰富了电路的层次结构。通过制定有向图方向的设置规则，将传统电路图转化为有向图。在进行通路搜索时，明确指定通路的搜索方向，避免了通路的盲目搜索。

（3）通过形式化建模方法描述铁路继电电路中各种类型的常用元件，从而精确描述了继电电路的逻辑特性，并借助严谨的程序处理保证仿真运算结果的准确性，不仅有效提升了仿真方法的可靠性，也可为后续研究提供理论参考。

参考文献

[1] 郭进，魏艳，刘利芳.铁路信号基础设备［M］.成都：西南交通大学出版社，2008：66-67.

[2] GUO Jin， WEI Yan， LIU Lifang. Railway Signaling Fundamental Equipment ［M］. Chengdu： Southwest Jiaotong University Press， 2008： 66-67. in Chinese

[3] 马小平，王旭，贾利民，等.基于数字孪生和MBSE的铁路防灾监测仿真推演系统设计［J］.中国铁道科学，2024，45（3）：168-181.

[4] MA Xiaoping， WANG Xu， JIA Limin， et al. Design of Railway Disaster Prevention Monitoring Simulation System Based on Digital Twin and MBSE ［J］. China Railway Science， 2024， 45 （3）： 168-181. in Chinese

[5] 牟志京.应用图论对时序继电电路的分析方法［J］.铁道学报，1981，3（4）：53-63.

[6] MU Zhijing. A Graph Method for Analysing the Sequential Relay Circuits ［J］. Journal of the China Railway Society， 1981， 3 （4）： 53-63. in Chinese

[7] CHEN Z， YIN Z X， CUI J Z， et al. DNA Switching Circuits Based on Binary Tree ［J］. IEEE Access， 2021， 9： 94033-94039.

[8] 杨雪，陈策，郗琦.继电器电路潜通路分析的一种方法［J］.航天控制，2018，36（6）：72-75.

[9] YANG Xue， CHEN Ce， XI Qi. An Analytic Method of Sneak Path in Relay Circuit ［J］. Aerospace Control， 2018， 36 （6）： 72-75. in Chinese

[10] BENACHOUR A， YAHIAOUI S， EL BAZ D， et al. Fast Parallel Algorithms for Finding Elementary Circuits of a Directed Graph： a GPU-Based Approach ［J］. The Journal of Supercomputing， 2023， 79： 4791-4819.

[11] RIAZA R. Setting up the State Equations of Switched Circuits Using Homogeneous Models ［J］. IEEE Transactions on Circuits and Systems I： Regular Papers， 2024， 71 （4）： 1947-1960.

[12] YANG S， GAO X， REN J. Sequential Circuits Synthesis for Rapid Single Flux Quantum Logic Based on Finite State Machine Decomposition ［J］. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems， 2023， 42 （10）： 3315-3326.

[13] 郑勇，杨扬.基于FSM和图论的继电电路仿真算法研究［J］.铁道通信信号，2020，56（12）：25-29.

[14] ZHENG Yong， YANG Yang. Research on Relay Circuit Simulation Algorithms Based on FSM and Graph Theory ［J］. Railway Signaling & Communication， 2020， 56 （12）： 25-29. in Chinese

[15] XU P， MA Q. Sneak Circuit Analysis Using Petri Net ［C］// 2010 5th IEEE Conference on Industrial Electronics and Applications （ICIEA）. New York： IEEE Press， 2010： 921-925.

[16] XUE Y， YANG Y， YANG M， et al. Sneak Circuit Analysis of Relay Circuits Based on Logic Delay Petri Nets ［C］// 2023 14th International Conference on Reliability， Maintainability and Safety （ICRMS）. New York： IEEE Press， 2023： 646-655.

[17] 鲁力博，杨扬，杨明，等.基于Agent-CA的继电控制电路逻辑功能仿真研究［J/OL］.控制工程，2024：1-9（2024-04-03）［2024-06-03］.

[18] LU Libo， YANG Yang， YANG Ming， et al. Simulation Research on Logic Function of Relay Control Circuit Based on Agent-CA ［J/OL］. Control Engineering of China， 2024： 1-9 （2024-04-03） ［2024-06-03］. in Chinese

[19] 宋政湘，王建华.继电控制线路逻辑功能分析的建模及算法设计［J］.西安交通大学学报，1998，32（6）：5-8.

[20] SONG Zhengxiang， WANG Jianhua. Modeling and Algorithm Design for the Logical Analysis of Relay Control Circuit ［J］. Journal of Xi’an Jiaotong University， 1998， 32 （6）： 5-8. in Chinese

[21] 李胜.计算机联锁控制电路仿真系统的设计与研究［J］.铁路通信信号工程技术，2018，15（1）：20-24.

[22] LI Sheng. Design of Simulation System for Computer Interlocking Control Circuit ［J］. Railway Signalling & Communication， 2018， 15 （1）： 20-24. in Chinese

[23] 张颖瑶，耿英三，张国钢，等.基于网络拓扑的继电线路逻辑表达式抽取方法［J］.低压电器，2007（21）：1-4，48.

[24] ZHANG Yingyao， GENG Yingsan， ZHANG Guogang， et al. A Logical Formula Extracting Method of Relay Circuit Based on Network Topology ［J］. Low Voltage Apparatus， 2007 （21）： 1-4， 48. in Chinese

[25] 王鲲.基于通信顺序进程与B方法的CBTC计算机联锁系统的形式化建模与验证［J］.中国铁道科学，2018，39（3）：101-109.

[26] WANG Kun. Formal Modeling and Verification of CBTC Computer Interlocking System Based on Communication Sequential Process and B Method ［J］. China Railway Science， 2018， 39 （3）： 101-109. in Chinese

[27] DÖRFLER F， SIMPSON-PORCO J W， BULLO F. Electrical Networks and Algebraic Graph Theory： Models， Properties， and Applications ［J］. Proceedings of the IEEE， 2018， 106 （5）： 977-1005.

[28] VRBIK J. Solving Electrical Circuits via Graph Theory ［J］. Applied Mathematics， 2022， 13 （1）：77-86.

[29] BHARDWAJ R， UPADHYAY A. Cellular Automata： Elementary Cellular Automata ［J］. Journal of Organizational and End User Computing， 2016， 29 （1）： 42-50.

[30] MALECKI K. Graph Cellular Automata with Relation-Based Neighbourhoods of Cells for Complex Systems Modelling： a Case of Traffic Simulation ［J］. Symmetry， 2017， 9 （12）： 322-344.

[31] GONGYE X， WANG Y， WEN Y， et al. A Simple Detection and Generation Algorithm for Simple Circuits in Directed Graph Based on Depth-First Traversal ［J］. Evolutionary Intelligence， 2022， 15： 2411-2420.

基金资助

中国国家铁路集团有限公司科技研究开发计划系统性重大项目(P2024G003)