计算机联锁软件设计及进路搜索算法的研究与应用

徐 鑫，陈光武

（兰州交通大学 光电技术与智能控制教育部重点实验室， 兰州 730070）

铁路车站联锁系统是铁路运输领域中的控制系统，以技术手段识别、减弱甚至消除车站内危及行车安全的不确定因素。国内车站联锁控制系统经历了机械联锁控制、电气集中联锁控制，自上世纪80年代我国采用计算机联锁控制以来，计算机联锁控制技术日趋完善并逐渐成为车站联锁控制的主要形式。

1 计算机联锁系统软件总体构成

根据计算机联锁系统硬件结构搭建相应的联锁系统软件，按层次划分为：人机会话层、联锁运算层和执行层，结构如图1。

2 联锁软件设计

本设计基于计算机联锁制式检测标准站（第2版）。

图1 软件层次结构图

2.1 联锁数据结构

联锁运算所处理的对象主要有3类：信号机、道岔和轨道区段。如何将这些设备对象有效地组织起来供联锁程序使用，是编写联锁软件首要的问题。由顶点的集合以及边的集合组成，将每一个设备对象看成是数据节点，根据其在信号平面布置图中位置链接起来就构成了设备节点图。每个数据节点在图中的位置与实际站场图中的位置一致，因此将这种数据结构称为站场型数据结构。部分站场对应的站场型数据结构如图2。

2.2 联锁控制程序

图2 部分站场及对应的数据结构图

软件的编制以铁道部《计算机联锁技术条件》为依据，在设计时要考虑软件的标准化、规范化以及模块化。在编写联锁软件时将联锁控制程序划分为6个模块：（1）操作输入及操作命令形成模块。（2）操作命令执行模块。（3）进路处理模块。（4）状态输入模块。（5）表示输出模块。（6）控制命令输出模块。

3 进路搜索模块设计

进路是由若干个信号机、道岔及道岔位置、轨道区段组成的列车在车站内运行时所经过的通路。进路搜索必须搜索出由始端信号点到终端信号点这条进路上的所有设备节点。如何更高效率地完成进路搜索对联锁软件存在很大的影响，为了程序的安全和高效，可采取各种各样的算法。

3.1 进路搜索算法的分析与比较

实际站场结构类似于图的结构，由节点（信号机，道岔，区段）的集合以及边（节点之间的链接关系）的集合组成，可以采用图的存储结构并运用图的路径搜索方法实现站场的进路搜索。

3.1.1 广度搜索算法

广度优先搜索类似于按树的层次遍历的过程。广度搜索示意如图3。

图3 广度搜索示意图

图3 说明了广度优先搜索的具体实现。这种搜索方法遵循从始端节点开始一层层扩展直到找到目标节点的搜索规则，搜索方向不确定，承受力很有限。如果扩展节点较多，而目标节点又处在较深层，采用前面叙述的广度搜索操作，搜索量非常巨大，往往就会出现内存空间不够用，造成存储数据的溢出等情况。

3.1.2 深度搜索算法

深度搜索类似于树的先序遍历的过程。深度搜索示意如图4。

图4 深度搜索示意图

这种搜索算法避免了广度搜索的搜索路径分支不明确，但是这种算法是选择一条路径走到黑的方式，即不管通过这条路径能不能找到目标节点都要进行试探，而且在找不到目标节点时还要一步步回溯，大大降低了搜索效率。

3.1.3 高度无往返搜索算法

针对上述搜索算法的不足，提出更新的一种进路搜索方法，称其为 “高度无往返搜索”。该方法的搜索目标明确，没有采用广度优先搜索按层扩大分支的策略，类似于深度优先搜索，但与之不同的是这种方法没有采用一直沿一条路径向下搜索，找不到目标节点就一步步回溯的策略。如图5。

图5 高度无往返搜索示意图

“高度无往返搜索”的基本思想是：在站场型数据结构的基础上，每个设备节点都按照其在实际站场中的纵向位置定义其所在高度，横向位置定义其编号大小，在同一线上的设备节点有同样的高度，见表1。在进行进路搜索时，根据始终端节点的横向编号首先确定搜索方向，在搜索方向上遇到对向道岔时，根据目标节点高度与始端节点高度值的比较，确定是沿弯股搜索还是沿直股搜索，完全避免了普通深度优先沿直股优先策略，搜索不到目标节点然后回溯，继续往返搜索的缺点，大大提高搜索效率。

表1 节点高度分布表

3.2 搜索算法的实现

本设计中采用“高度无往返搜索”算法进行进路搜索。该搜索要完成的其中一项任务就是根据进路操作命令，只能选出一条符合要求的进路（基本进路、迂回进路、或是有多条基本进路组成的符合进路）；在仅指明进路的始终端只能选出一条基本进路而不能选出绕弯的或平行的迂回进路。为此采取了一项措施，在建立站场数据结构之前，根据实际站场结构，在2个节点之间存在多条平行进路时，将这2个节点作为一对特殊的节点对存于数据库中，并列出该特殊节点对之间的临时目标节点。

3.2.1 搜索算法的描述

（1）根据按压的节点顺序生成节点对，根据是终端节点的横向编号确定搜索方向。

（2）将生成的节点对与数据库中的特殊节点对相比较，如果是特殊节点对，转到（3），如果不是，转到（4）。

（3）取特殊节点为临时目标节点，生成新的节点对。

（4）取到沿搜索方向上目前节点的下一节点。

（5）判断该节点是否为目标节点？如果是转到（6），如果不是转到（7）。

（6）检查是否还有目标节点？如果有，与上一目标节点构成新的节点对，转到（2），如果没有，搜索成功。

（7）判断该节点是否为死结点（没有后继节点的节点）？如果是，搜索失败，如果不是，转到（8）。

（8）判断是否为对向道岔节点？如果是，转到(9)，如果不是，转到（4）。

（9）根据目标节点高度与弯股节点的高度关系，判断弯股能否通向目标节点？如果能，转到(10)，反之转到（11）。

（10）取弯股节点，转到（5）。

（11）取直股节点，转到（5）。

3.2.2 进路搜索流程

进路搜索算法的基本流程如图6。

图6 进路搜索流程图

利用上述搜索算法，对标准站场（第2版）上行咽喉办理XI-S的发车进路，搜索结果如图7。截图中的操作对象是XI和S信号机，进路搜索数据为该条进路上经过的所有设备节点，显示结果为设备对应的ID，进路方向“1”代表发车进路，进路性质“11”代表列车进路。进路锁闭后在上位机界面显示如图8白光带所示。

图7 进路搜索数据截图

4 联锁软件安全性可靠性分析

目前，无论是质量保证法还是软件容错法的应用，都无法保证系统的绝对安全。开发高安全完整性等级软件应遵循以下原则：（1）自顶向下的设计方法；（2）模块化；（3）验证开发生命周期的每一阶段；（4）验证模块和模块库；（5）文档清晰；（6）提供可审计的文档；（7）确认测试。

图8 上位机界面显示截图

5 结束语

联锁软件采用结构化程序设计方法，自顶而下，逐步求精，并采用模块化设计思想，达到了软件的安全性完整性等级（SIL）4级。采用 “高度无往返搜索”算法进行进路搜索，在时间和空间上都降低了复杂度，大大提高联锁软件的执行效率。

[1]赵志熙. 计算机联锁系统技术[M]. 北京：中国铁道出版社，2008.

[2]殷人昆，陶永雷，谢若阳，盘绚华．数据结构(用面向对象方法与c++描述)[M]. 北京：清华大学出版社，2002.

[3]彭建伟，殷人昆. 基于临接表结构的进路搜索算法研究[J].计算机工程与设计，2006，27（18）：4300-4302.

[4]王 玺. 基于安全信息传输网的分布式计算机联锁系统设计[D]. 北京交通大学，2006，12.

[5] 朱 明，王晓明. 一种铁路微机联锁进路搜索的实现方法[J]. 铁路计算机应用，2007，16（11）.

[6] TB/T3027-2002，计算机联锁技术条件[S].

[7] Signalling and processing systems-Software for railway control and protection systems[J]. EN 50128 Railway Applications Communications,March 2001.