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

王志平，耿 鵬，孫曉光

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

1 概述

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

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

2 列車通信及管理功能

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

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

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

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

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

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

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

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

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

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

3 列車通信及管理模型

根據(jù)列車通信及管理功能和需求創(chuàng)建列車通信及管理模型，車載ATP通過安全通信協(xié)議層和應(yīng)用接口層向地面ATP發(fā)送消息，地面ATP應(yīng)用軟件通過接口層接收消息后送至車地適配模塊，并通過對(duì)消息的解析觸發(fā)列車管理狀態(tài)自動(dòng)機(jī)，對(duì)列車進(jìn)行加車、刪車操作；列車管理狀態(tài)自動(dòng)機(jī)根據(jù)列車當(dāng)前狀態(tài)及觸發(fā)事件對(duì)列車狀態(tài)進(jìn)行遷移和管理，并依據(jù)前后狀態(tài)選擇向車載ATP回復(fù)對(duì)應(yīng)的消息，實(shí)現(xiàn)操作列車通信及自動(dòng)管理功能，列車通信及管理模型如圖 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)管理自動(dòng)機(jī)模型示意圖Fig.5 Schematic diagram of train state management automata model

4 有限自動(dòng)機(jī)理論

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

有限狀態(tài)自動(dòng)機(jī)的定義如下。

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

Q是一個(gè)有限狀態(tài)的集合，?q∈Q，q稱為M的一個(gè)狀態(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為一個(gè)確定唯一的狀態(tài)，則稱該有限狀態(tài)自動(dòng)機(jī)為確定的有限狀態(tài)自動(dòng)機(jī)（DFA），若p為一個(gè)不確定的狀態(tài)，比如可以有多個(gè)狀態(tài)時(shí)，則稱該有限狀態(tài)自動(dòng)機(jī)為不確定的有限狀態(tài)自動(dòng)機(jī)（NFA），DFA和NFA是等價(jià)的，可以相互轉(zhuǎn)化。

F是M的終止?fàn)顟B(tài)集合，F(xiàn)?Q。

對(duì)于字母表∑上的有限自動(dòng)機(jī)M，它能識(shí)別的所有串的集合，稱為自動(dòng)機(jī)M能夠識(shí)別的語言，記為L(zhǎng)(M)。

5 列車管理自動(dòng)機(jī)實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

概括地，有限狀態(tài)自動(dòng)機(jī)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自己采取的動(dòng)作事件，例如：地面ATP主動(dòng)注銷和地面ATP判斷與車載ATP通信超時(shí)等。擴(kuò)展后∑的事件集合為：∑= {Ev1，Ev2，Ev3，Ev4，Ev5，Ev6，Ev7}，其中Evn表示的含義如下：

Ev1：安全連接建立指示；Ev2：車載ATP注冊(cè)請(qǐng)求；

Ev3：車載ATP注銷請(qǐng)求；

Ev4：安全連接斷開指示；

Ev5：地面ATP主動(dòng)注銷請(qǐng)求；

Ev6：地面ATP判斷與車載ATP通信超時(shí)；

Ev7：地面ATP判斷回段刪車條件被觸發(fā)。

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

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

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

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

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

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

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

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

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

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

其中L2(M3)為：

其中L3(M3)為：

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

6 結(jié)束語

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