基于有限狀態(tài)自動機理論的CBTC系統(tǒng)列車管理方法研究

王志平，耿 鵬，孫曉光

(通號城市軌道交通技術(shù)有限公司，北京 100070)

1 概述

隨著軌道交通技術(shù)發(fā)展，基于無線通信的列車自動控制系統(tǒng)（Communication Based Train Control System，CBTC）以列車追蹤間隔短、運能大、運營效率高、移動閉塞追蹤等特點，受到國內(nèi)外業(yè)主的青睞，中國通號、阿爾卡特、西門子、阿爾斯通、交控等國內(nèi)外生產(chǎn)廠家分別推出CBTC系統(tǒng)，并得到了廣泛應(yīng)用。在此基礎(chǔ)上，以中國鐵路通信信號股份有限公司為代表的信號生產(chǎn)廠家，自主研制了基于CBTC系統(tǒng)的互聯(lián)互通信號技術(shù)，實現(xiàn)不同廠商列車在各條線路的混合運營，解決不同信號廠家車地設(shè)備之間彼此“交流”的世界性技術(shù)難題。同時，如何對不同廠商的列車進行高效且安全的管理、如何提高系統(tǒng)的通用性和擴展性對車地通信技術(shù)中的列車管理功能帶來挑戰(zhàn)。

列車管理功能是CBTC系統(tǒng)車地通信方法中關(guān)鍵技術(shù)，本文提出一種基于有限狀態(tài)自動機的CBTC系統(tǒng)列車自動管理方法，利用有限狀態(tài)自動機理論對列車通信自動管理模型進行定義，并根據(jù)定義構(gòu)造非確定有限自動機（NFA）和確定性有限自動機（DFA），完成創(chuàng)建列車管理狀態(tài)自動機能夠識別的語言，實現(xiàn)CBTC系統(tǒng)列車自動管理功能。該方法通過控制列車內(nèi)部狀態(tài)遷移和監(jiān)控的方式管理列車列表，根據(jù)每列車的前后狀態(tài)決定應(yīng)向列車發(fā)送對應(yīng)的消息，并依據(jù)列車當前的狀態(tài)周期對問題列車進行安全側(cè)處理。該方法不僅具有高效率和易擴展的優(yōu)點，對于不同廠商列車或采用其他協(xié)議（如：RSSP-I安全通信協(xié)議）的列車均可通過遷移列車狀態(tài)的方式進行列車自動管理，對提高系統(tǒng)的通用性有很好的借鑒意義。

2 列車通信及管理功能

CBTC系統(tǒng)中車地通信及列車管理的主要功能包含安全通信管理、列車通信管理、列車注冊、注銷、列車回段控制、列車降級刪車和列車接口適配功能等。

基于無線通信的列車自動控制系統(tǒng)中，車載ATP和地面ATP傳輸應(yīng)用消息之前，需采用RSSP-II安全通信協(xié)議棧進行3次握手信息交互并通過信息驗證及確認后，車載ATP才會向地面ATP發(fā)起注冊請求等應(yīng)用消息，安全通信管理功能是指地面ATP對安全連接狀態(tài)的管理，包括安全連接的建立和釋放，如圖 1、 2所示。

列車通信管理是指對車地通信過程中車地應(yīng)用通信通道狀態(tài)的管理，包含地面ATP認為與車載ATP通信超時、地面ATP主動斷開通信和地面ATP認為該消息來自相鄰地面ATP控制區(qū)域等多種情況。例如：地面ATP在通信超時時間范圍內(nèi)未接收到車載ATP的任何應(yīng)用消息（包含消息延時的情況），則地面ATP認為與車載ATP通信超時，并觸發(fā)安全側(cè)操作。

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

列車注冊功能是指車載ATP在和地面ATP建立安全連接之后，車載ATP主動向地面ATP發(fā)起注冊請求，地面ATP對列車進行加車操作并持續(xù)維護該列車的通信狀態(tài)及安全狀態(tài)，直到列車主動注銷或地面ATP認為列車信息或狀態(tài)非法主動斷開該車通信并降級刪除該列車。

注銷功能主要包含兩部分：列車向地面ATP主動注銷和地面ATP主動注銷該列車。當車載ATP向地面ATP發(fā)起注銷請求后，地面ATP需向車載ATP回復(fù)注銷確認，車載ATP收到注銷確認之后向地面ATP發(fā)起斷開安全連接指示，地面ATP收到安全連接斷開請求后采取刪除列車操作，釋放該列車的管理權(quán)。當?shù)孛鍭TP認為列車駛出管轄區(qū)且未收到列車主動注銷請求或地面ATP認為列車位置信息出錯等情況發(fā)生時，地面ATP向列車發(fā)送主動注銷請求，列車收到地面ATP的注銷請求后再地面ATP發(fā)起主動注銷。

列車回段管理功能是指列車運營完畢最大安全前端進入轉(zhuǎn)換軌后與地面ATP主動注銷，此時列車安全整個安全包絡(luò)可能還未完全進入轉(zhuǎn)換軌內(nèi)，若地面ATP立即對列車降級操作，則會影響后車移動授權(quán)的回縮，影響運營效率，從而需對回段注銷的列車進行特殊管理操作。

列車降級刪車管理是指地面ATP周期對已降級的列車采取刪除列車操作，釋放列車管理權(quán)，不再對列車進行維護管理。

列車接口適配功能是指地面ATP和車載ATP進行應(yīng)用消息交互時，需采用相同的車地通信接口規(guī)范，對列車發(fā)送的消息進行接收處理，包含消息檢查和解析存儲等功能，例如列車位置報告信息、列車注冊注銷信息等；同時，地面ATP需對列車消息進行響應(yīng)，周期向車載ATP回復(fù)對應(yīng)的信息，例如：列車移動授權(quán)信息、注冊應(yīng)答和注銷響應(yīng)等。

CBTC系統(tǒng)中車載ATP和地面ATP常規(guī)的信息交互流程圖，如圖 3所示。

3 列車通信及管理模型

根據(jù)列車通信及管理功能和需求創(chuàng)建列車通信及管理模型，車載ATP通過安全通信協(xié)議層和應(yīng)用接口層向地面ATP發(fā)送消息，地面ATP應(yīng)用軟件通過接口層接收消息后送至車地適配模塊，并通過對消息的解析觸發(fā)列車管理狀態(tài)自動機，對列車進行加車、刪車操作；列車管理狀態(tài)自動機根據(jù)列車當前狀態(tài)及觸發(fā)事件對列車狀態(tài)進行遷移和管理，并依據(jù)前后狀態(tài)選擇向車載ATP回復(fù)對應(yīng)的消息，實現(xiàn)操作列車通信及自動管理功能，列車通信及管理模型如圖 4、 5所示。

圖3 車地通信應(yīng)用消息交互流程圖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 列車狀態(tài)管理自動機模型示意圖Fig.5 Schematic diagram of train state management automata model

4 有限自動機理論

有限狀態(tài)自動機 (Finite State Automaton,FSA)是對一類處理系統(tǒng)建立的數(shù)學(xué)模型，這類系統(tǒng)具有一系列離散的輸入輸出信息和有窮數(shù)目的內(nèi)部狀態(tài)，系統(tǒng)只需要根據(jù)當前所處的狀態(tài)和當前面臨的輸入信息就可以決定系統(tǒng)的后繼行為。每當系統(tǒng)處理了當前的輸入后，系統(tǒng)的內(nèi)部狀態(tài)也將發(fā)生改變。該理論在計算機領(lǐng)域應(yīng)用較為廣泛，主要用于研究有限內(nèi)存的計算過程和某些語言類抽象而出的一種計算模型。有限狀態(tài)自動機擁有有限數(shù)量的狀態(tài)，每個狀態(tài)可以遷移到零個或多個狀態(tài)，輸入符號決定執(zhí)行哪個狀態(tài)的遷移，還可以表示為一個有向圖（稱為狀態(tài)轉(zhuǎn)換圖）。

有限狀態(tài)自動機的定義如下。

字母表∑上的有限狀態(tài)自動機是一個五元式，M= (Q，∑，δ，q0，F(xiàn)),其中，

Q是一個有限狀態(tài)的集合，?q∈Q，q稱為M的一個狀態(tài)。

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

q0是初始狀態(tài)，q0∈Q。

δ是Q×∑→Q的狀態(tài)轉(zhuǎn)移函數(shù)，即δ(q，a) =p，表示M在狀態(tài)q讀入字符a，將狀態(tài)變成p，若p為一個確定唯一的狀態(tài)，則稱該有限狀態(tài)自動機為確定的有限狀態(tài)自動機（DFA），若p為一個不確定的狀態(tài)，比如可以有多個狀態(tài)時，則稱該有限狀態(tài)自動機為不確定的有限狀態(tài)自動機（NFA），DFA和NFA是等價的，可以相互轉(zhuǎn)化。

F是M的終止狀態(tài)集合，F(xiàn)?Q。

對于字母表∑上的有限自動機M，它能識別的所有串的集合，稱為自動機M能夠識別的語言，記為L(M)。

5 列車管理自動機實現(xiàn)

根據(jù)4章節(jié)有限狀態(tài)自動機的理論和定義，結(jié)合CBTC系統(tǒng)中列車通信及管理功能和模型，我們先來定義一個簡單的語言L(M1)，例如：L(M1) ={Ev1Ev2Ev3Ev4}，其 中Ev1、Ev2、Ev3和Ev4為 車 載ATP向地面ATP發(fā)送的消息事件，Ev1為車載ATP發(fā)起的安全連接建立指示，Ev2為車載ATP發(fā)起的注冊請求，Ev3為車載ATP發(fā)起的注銷請求，Ev4為車載ATP發(fā)起的斷開安全連接指示。構(gòu)造一個確定的有限狀態(tài)自動機M1來識別語言L(M1)，滿足列車管理功能，如下所示。

定義地面ATP內(nèi)部列車自動管理狀態(tài)機的初始態(tài)為q0，此狀態(tài)為安全側(cè)狀態(tài)，終止狀態(tài)也為q0，即安全連接未建立狀態(tài)，狀態(tài)轉(zhuǎn)移函數(shù)如下：

δ(q0,Ev1) =q1,q1為安全連接已建立狀態(tài)；

δ(q1,Ev2) =q2,q2為列車已注冊狀態(tài)；

狀態(tài)遷移關(guān)系如表 1所示。

表 1 有限狀態(tài)自動機M1狀態(tài)轉(zhuǎn)換關(guān)系表Tab.1 State transition relationship table of finite state automaton M1

通過上述關(guān)系表，可以形成有限狀態(tài)自動機M1的狀態(tài)轉(zhuǎn)換圖，如圖 6所示。

圖6 有限狀態(tài)自動機M1狀態(tài)轉(zhuǎn)換示意圖Fig.6 Schematic diagram of state transition of finite state automata M1

通過表 1和圖 6構(gòu)造的確定的有限狀態(tài)自動機M1，可以實現(xiàn)對L(M1)語言的接收，控制每列車的內(nèi)部狀態(tài)，實現(xiàn)列車自動管理功能（例如：加車、刪車操作）。當列車狀態(tài)從q0轉(zhuǎn)移至q1時，進行增加列車操作；當列車狀態(tài)從q1轉(zhuǎn)移至q0時，進行刪除列車操作，對該列車的狀態(tài)進行初始化，釋放該列車控制權(quán)。每列車從q0狀態(tài)（初始狀態(tài)，也是安全側(cè)狀態(tài)）開始，不管和地面ATP進行什么樣的信息交互，最終的狀態(tài)都應(yīng)遷移至接收狀態(tài)q0（狀態(tài)圖中用同心圓表示接收狀態(tài)），這也是遵循SIL4級安全產(chǎn)品設(shè)計所采用的“故障導(dǎo)向安全”理論。

不難發(fā)現(xiàn)，有限狀態(tài)自動機M1處理的列車消息的能力有限，例如：在q1狀態(tài)下Ev3時自動機該如何處理？表 1中對于響應(yīng)狀態(tài)集合為“N/A”的事件是自動機M1所處理不了的場景，從而需對M1進行優(yōu)化，優(yōu)化后的有限狀態(tài)自動機為M2，M2的狀態(tài)轉(zhuǎn)移函數(shù)如下：

狀態(tài)遷移關(guān)系如表 2所示。

表 2 有限狀態(tài)自動機M2狀態(tài)轉(zhuǎn)換關(guān)系表Tab.2 State transition relationship table of finite state automaton M2

通過上述關(guān)系表，可以形成有限狀態(tài)自動機M2的狀態(tài)轉(zhuǎn)換圖，如圖 7所示。

圖7 有限狀態(tài)自動機M2狀態(tài)轉(zhuǎn)換示意圖Fig.7 Schematic diagram of state transition of finite state automata M2

經(jīng)過優(yōu)化后，有限狀態(tài)自動機M2可以接收的語言與M1相比更加豐富，例如可以接收以下語言：

概括地，有限狀態(tài)自動機M2可以接收的語言L(M2)為：

{{Ev2,Ev3,Ev4}*{Ev1}+{Ev3}*Ev2{Ev1,Ev3}*{{Ev3{Ev1,Ev3}*Ev4}∪Ev4}}，其中，Ev+表示事件Ev的觸發(fā)次數(shù)大于等于1，Ev*=Ev0∪Ev+。

Ev作為∑上的輸入，不僅可以為車載ATP發(fā)送的響應(yīng)事件，還可以為地面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判斷回段刪車條件被觸發(fā)。

有限狀態(tài)自動機M2中，在列車已注冊條件下，如果再次收到了列車注冊請求，還可以繼續(xù)優(yōu)化，分為兩種情況進行分類處理：

1）列車沒有發(fā)送位置報告信息時，可以允許重復(fù)注冊；

2）列車已發(fā)送正確的位置信息時，認為該注冊請求不正常，應(yīng)采取安全側(cè)處理。

另外，對于列車回段的特殊功能可以在M2上進行狀態(tài)擴展，在Q集合中增加列車回段狀態(tài)q3，繼續(xù)優(yōu)化形成有限狀態(tài)自動機M3，M3的狀態(tài)轉(zhuǎn)移函數(shù)如下：

狀態(tài)遷移關(guān)系如表 3所示。

表 3 有限狀態(tài)自動機M3狀態(tài)轉(zhuǎn)換關(guān)系表Tab.3 State transition relationship table of finite state automata M3

可以注意到表 3中在q1狀態(tài)（列車已注冊）下對于車載ATP的注銷請求有兩種狀態(tài)遷移，而不像表 2中對于Ev3的響應(yīng)只有一種狀態(tài)。這種在一種狀態(tài)下對于同一個輸入形成多種狀態(tài)的有限自動機稱為不確定的有限狀態(tài)自動機（NFA）；同理，在q2狀態(tài)（列車已注冊）下對于車載ATP的注冊請求也有兩種狀態(tài)遷移，表明此處需對列車重復(fù)注冊事件進行分類處理。

通過上述關(guān)系表，可以形成有限狀態(tài)自動機M3的狀態(tài)轉(zhuǎn)換圖，如圖 8所示。

經(jīng)過對有限狀態(tài)自動機M2進行擴展優(yōu)化后，可以接收的語言L(M3)為：

圖8 有限狀態(tài)自動機M3狀態(tài)轉(zhuǎn)換示意圖Fig.8 Schematic diagram of state transition of finite state automata M3

其中L2(M3)為：

其中L3(M3)為：

它可以滿足本文提到的所有列車通信及管理相關(guān)功能，例如列車重復(fù)注冊時需地面ATP對列車狀態(tài)維護的不同處理：車載ATP向地面ATP發(fā)起安全連接建立指示，地面ATP收到安全連接建立指示后等待列車注冊請求，車載ATP發(fā)送列車注冊請求后又向地面ATP發(fā)送注冊請求或注冊成功發(fā)送了一段時間的位置報告信息之后，又向地面ATP發(fā)送注冊請求，地面ATP此時應(yīng)根據(jù)具體情況分別處理，維持列車在列車已注冊狀態(tài)或認為列車信息非法降級刪除列車。該功能抽象成有限狀態(tài)機接收的事件序列為：Ev1{Ev2}＊，此序列為有限狀態(tài)自動機M3語言L(M3)的一個子集，可以被L(M3)所接收，即有限狀態(tài)自動機M3可以滿足此功能需求。

6 結(jié)束語

基于有限自動機理論的列車管理方法實現(xiàn)的車地通信適配模塊，被廣泛應(yīng)用國內(nèi)多條地鐵線路，例如：北京地鐵8號線、重慶互聯(lián)互通5號線、合肥3號線等。另外，全自動無人駕駛中的列車休眠和喚醒功能，其實也是對事件響應(yīng)和列車內(nèi)部狀態(tài)的擴展。該方法不僅支持采用無線通信和RSSPII安全通信協(xié)議的列車，還可以支持采用有線通信和RSSP-I安全通信協(xié)議列車。實踐表明，該方法實現(xiàn)的列車管理功能軟件模塊，不僅可以對列車進行高效且安全的管理，還具備較高的可擴展性和可維護性。