基于有限状态自动机理论的CBTC系统列车管理方法研究

王志平，耿 鹏，孙晓光

(通号城市轨道交通技术有限公司，北京 100070)

1 概述

随着轨道交通技术发展，基于无线通信的列车自动控制系统（Communication Based Train Control System，CBTC）以列车追踪间隔短、运能大、运营效率高、移动闭塞追踪等特点，受到国内外业主的青睐，中国通号、阿尔卡特、西门子、阿尔斯通、交控等国内外生产厂家分别推出CBTC系统，并得到了广泛应用。在此基础上，以中国铁路通信信号股份有限公司为代表的信号生产厂家，自主研制了基于CBTC系统的互联互通信号技术，实现不同厂商列车在各条线路的混合运营，解决不同信号厂家车地设备之间彼此“交流”的世界性技术难题。同时，如何对不同厂商的列车进行高效且安全的管理、如何提高系统的通用性和扩展性对车地通信技术中的列车管理功能带来挑战。

列车管理功能是CBTC系统车地通信方法中关键技术，本文提出一种基于有限状态自动机的CBTC系统列车自动管理方法，利用有限状态自动机理论对列车通信自动管理模型进行定义，并根据定义构造非确定有限自动机（NFA）和确定性有限自动机（DFA），完成创建列车管理状态自动机能够识别的语言，实现CBTC系统列车自动管理功能。该方法通过控制列车内部状态迁移和监控的方式管理列车列表，根据每列车的前后状态决定应向列车发送对应的消息，并依据列车当前的状态周期对问题列车进行安全侧处理。该方法不仅具有高效率和易扩展的优点，对于不同厂商列车或采用其他协议（如：RSSP-I安全通信协议）的列车均可通过迁移列车状态的方式进行列车自动管理，对提高系统的通用性有很好的借鉴意义。

2 列车通信及管理功能

CBTC系统中车地通信及列车管理的主要功能包含安全通信管理、列车通信管理、列车注册、注销、列车回段控制、列车降级删车和列车接口适配功能等。

基于无线通信的列车自动控制系统中，车载ATP和地面ATP传输应用消息之前，需采用RSSP-II安全通信协议栈进行3次握手信息交互并通过信息验证及确认后，车载ATP才会向地面ATP发起注册请求等应用消息，安全通信管理功能是指地面ATP对安全连接状态的管理，包括安全连接的建立和释放，如图 1、 2所示。

列车通信管理是指对车地通信过程中车地应用通信通道状态的管理，包含地面ATP认为与车载ATP通信超时、地面ATP主动断开通信和地面ATP认为该消息来自相邻地面ATP控制区域等多种情况。例如：地面ATP在通信超时时间范围内未接收到车载ATP的任何应用消息（包含消息延时的情况），则地面ATP认为与车载ATP通信超时，并触发安全侧操作。

图2 安全连接建立示意图Fig.2 Schematic diagram of security connection establishment

列车注册功能是指车载ATP在和地面ATP建立安全连接之后，车载ATP主动向地面ATP发起注册请求，地面ATP对列车进行加车操作并持续维护该列车的通信状态及安全状态，直到列车主动注销或地面ATP认为列车信息或状态非法主动断开该车通信并降级删除该列车。

注销功能主要包含两部分：列车向地面ATP主动注销和地面ATP主动注销该列车。当车载ATP向地面ATP发起注销请求后，地面ATP需向车载ATP回复注销确认，车载ATP收到注销确认之后向地面ATP发起断开安全连接指示，地面ATP收到安全连接断开请求后采取删除列车操作，释放该列车的管理权。当地面ATP认为列车驶出管辖区且未收到列车主动注销请求或地面ATP认为列车位置信息出错等情况发生时，地面ATP向列车发送主动注销请求，列车收到地面ATP的注销请求后再地面ATP发起主动注销。

列车回段管理功能是指列车运营完毕最大安全前端进入转换轨后与地面ATP主动注销，此时列车安全整个安全包络可能还未完全进入转换轨内，若地面ATP立即对列车降级操作，则会影响后车移动授权的回缩，影响运营效率，从而需对回段注销的列车进行特殊管理操作。

列车降级删车管理是指地面ATP周期对已降级的列车采取删除列车操作，释放列车管理权，不再对列车进行维护管理。

列车接口适配功能是指地面ATP和车载ATP进行应用消息交互时，需采用相同的车地通信接口规范，对列车发送的消息进行接收处理，包含消息检查和解析存储等功能，例如列车位置报告信息、列车注册注销信息等；同时，地面ATP需对列车消息进行响应，周期向车载ATP回复对应的信息，例如：列车移动授权信息、注册应答和注销响应等。

CBTC系统中车载ATP和地面ATP常规的信息交互流程图，如图 3所示。

3 列车通信及管理模型

根据列车通信及管理功能和需求创建列车通信及管理模型，车载ATP通过安全通信协议层和应用接口层向地面ATP发送消息，地面ATP应用软件通过接口层接收消息后送至车地适配模块，并通过对消息的解析触发列车管理状态自动机，对列车进行加车、删车操作；列车管理状态自动机根据列车当前状态及触发事件对列车状态进行迁移和管理，并依据前后状态选择向车载ATP回复对应的消息，实现操作列车通信及自动管理功能，列车通信及管理模型如图 4、 5所示。

图3 车地通信应用消息交互流程图Fig.3 Flow chart of application message interaction of train-ground communication

图4 车地通信及列车管理模型示意图Fig.4 Schematic diagram of train-ground communication and train management model

图5 列车状态管理自动机模型示意图Fig.5 Schematic diagram of train state management automata model

4 有限自动机理论

有限状态自动机 (Finite State Automaton,FSA)是对一类处理系统建立的数学模型，这类系统具有一系列离散的输入输出信息和有穷数目的内部状态，系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。每当系统处理了当前的输入后，系统的内部状态也将发生改变。该理论在计算机领域应用较为广泛，主要用于研究有限内存的计算过程和某些语言类抽象而出的一种计算模型。有限状态自动机拥有有限数量的状态，每个状态可以迁移到零个或多个状态，输入符号决定执行哪个状态的迁移，还可以表示为一个有向图（称为状态转换图）。

有限状态自动机的定义如下。

字母表∑上的有限状态自动机是一个五元式，M= (Q，∑，δ，q0，F),其中，

Q是一个有限状态的集合，∀q∈Q，q称为M的一个状态。

∑是输入字母表，输入字符串都是∑上的字符串。

q0是初始状态，q0∈Q。

δ是Q×∑→Q的状态转移函数，即δ(q，a) =p，表示M在状态q读入字符a，将状态变成p，若p为一个确定唯一的状态，则称该有限状态自动机为确定的有限状态自动机（DFA），若p为一个不确定的状态，比如可以有多个状态时，则称该有限状态自动机为不确定的有限状态自动机（NFA），DFA和NFA是等价的，可以相互转化。

F是M的终止状态集合，F⊆Q。

对于字母表∑上的有限自动机M，它能识别的所有串的集合，称为自动机M能够识别的语言，记为L(M)。

5 列车管理自动机实现

根据4章节有限状态自动机的理论和定义，结合CBTC系统中列车通信及管理功能和模型，我们先来定义一个简单的语言L(M1)，例如：L(M1) ={Ev1Ev2Ev3Ev4}，其 中Ev1、Ev2、Ev3和Ev4为 车 载ATP向地面ATP发送的消息事件，Ev1为车载ATP发起的安全连接建立指示，Ev2为车载ATP发起的注册请求，Ev3为车载ATP发起的注销请求，Ev4为车载ATP发起的断开安全连接指示。构造一个确定的有限状态自动机M1来识别语言L(M1)，满足列车管理功能，如下所示。

定义地面ATP内部列车自动管理状态机的初始态为q0，此状态为安全侧状态，终止状态也为q0，即安全连接未建立状态，状态转移函数如下：

δ(q0,Ev1) =q1,q1为安全连接已建立状态；

δ(q1,Ev2) =q2,q2为列车已注册状态；

状态迁移关系如表 1所示。

表 1 有限状态自动机M1状态转换关系表Tab.1 State transition relationship table of finite state automaton M1

通过上述关系表，可以形成有限状态自动机M1的状态转换图，如图 6所示。

图6 有限状态自动机M1状态转换示意图Fig.6 Schematic diagram of state transition of finite state automata M1

通过表 1和图 6构造的确定的有限状态自动机M1，可以实现对L(M1)语言的接收，控制每列车的内部状态，实现列车自动管理功能（例如：加车、删车操作）。当列车状态从q0转移至q1时，进行增加列车操作；当列车状态从q1转移至q0时，进行删除列车操作，对该列车的状态进行初始化，释放该列车控制权。每列车从q0状态（初始状态，也是安全侧状态）开始，不管和地面ATP进行什么样的信息交互，最终的状态都应迁移至接收状态q0（状态图中用同心圆表示接收状态），这也是遵循SIL4级安全产品设计所采用的“故障导向安全”理论。

不难发现，有限状态自动机M1处理的列车消息的能力有限，例如：在q1状态下Ev3时自动机该如何处理？表 1中对于响应状态集合为“N/A”的事件是自动机M1所处理不了的场景，从而需对M1进行优化，优化后的有限状态自动机为M2，M2的状态转移函数如下：

状态迁移关系如表 2所示。

表 2 有限状态自动机M2状态转换关系表Tab.2 State transition relationship table of finite state automaton M2

通过上述关系表，可以形成有限状态自动机M2的状态转换图，如图 7所示。

图7 有限状态自动机M2状态转换示意图Fig.7 Schematic diagram of state transition of finite state automata M2

经过优化后，有限状态自动机M2可以接收的语言与M1相比更加丰富，例如可以接收以下语言：

概括地，有限状态自动机M2可以接收的语言L(M2)为：

{{Ev2,Ev3,Ev4}*{Ev1}+{Ev3}*Ev2{Ev1,Ev3}*{{Ev3{Ev1,Ev3}*Ev4}∪Ev4}}，其中，Ev+表示事件Ev的触发次数大于等于1，Ev*=Ev0∪Ev+。

Ev作为∑上的输入，不仅可以为车载ATP发送的响应事件，还可以为地面ATP自己采取的动作事件，例如：地面ATP主动注销和地面ATP判断与车载ATP通信超时等。扩展后∑的事件集合为：∑= {Ev1，Ev2，Ev3，Ev4，Ev5，Ev6，Ev7}，其中Evn表示的含义如下：

Ev1：安全连接建立指示；Ev2：车载ATP注册请求；

Ev3：车载ATP注销请求；

Ev4：安全连接断开指示；

Ev5：地面ATP主动注销请求；

Ev6：地面ATP判断与车载ATP通信超时；

Ev7：地面ATP判断回段删车条件被触发。

有限状态自动机M2中，在列车已注册条件下，如果再次收到了列车注册请求，还可以继续优化，分为两种情况进行分类处理：

1）列车没有发送位置报告信息时，可以允许重复注册；

2）列车已发送正确的位置信息时，认为该注册请求不正常，应采取安全侧处理。

另外，对于列车回段的特殊功能可以在M2上进行状态扩展，在Q集合中增加列车回段状态q3，继续优化形成有限状态自动机M3，M3的状态转移函数如下：

状态迁移关系如表 3所示。

表 3 有限状态自动机M3状态转换关系表Tab.3 State transition relationship table of finite state automata M3

可以注意到表 3中在q1状态（列车已注册）下对于车载ATP的注销请求有两种状态迁移，而不像表 2中对于Ev3的响应只有一种状态。这种在一种状态下对于同一个输入形成多种状态的有限自动机称为不确定的有限状态自动机（NFA）；同理，在q2状态（列车已注册）下对于车载ATP的注册请求也有两种状态迁移，表明此处需对列车重复注册事件进行分类处理。

通过上述关系表，可以形成有限状态自动机M3的状态转换图，如图 8所示。

经过对有限状态自动机M2进行扩展优化后，可以接收的语言L(M3)为：

图8 有限状态自动机M3状态转换示意图Fig.8 Schematic diagram of state transition of finite state automata M3

其中L2(M3)为：

其中L3(M3)为：

它可以满足本文提到的所有列车通信及管理相关功能，例如列车重复注册时需地面ATP对列车状态维护的不同处理：车载ATP向地面ATP发起安全连接建立指示，地面ATP收到安全连接建立指示后等待列车注册请求，车载ATP发送列车注册请求后又向地面ATP发送注册请求或注册成功发送了一段时间的位置报告信息之后，又向地面ATP发送注册请求，地面ATP此时应根据具体情况分别处理，维持列车在列车已注册状态或认为列车信息非法降级删除列车。该功能抽象成有限状态机接收的事件序列为：Ev1{Ev2}＊，此序列为有限状态自动机M3语言L(M3)的一个子集，可以被L(M3)所接收，即有限状态自动机M3可以满足此功能需求。

6 结束语

基于有限自动机理论的列车管理方法实现的车地通信适配模块，被广泛应用国内多条地铁线路，例如：北京地铁8号线、重庆互联互通5号线、合肥3号线等。另外，全自动无人驾驶中的列车休眠和唤醒功能，其实也是对事件响应和列车内部状态的扩展。该方法不仅支持采用无线通信和RSSPII安全通信协议的列车，还可以支持采用有线通信和RSSP-I安全通信协议列车。实践表明，该方法实现的列车管理功能软件模块，不仅可以对列车进行高效且安全的管理，还具备较高的可扩展性和可维护性。