基于有限狀態自動機理論的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安全通信協議列車。實踐表明，該方法實現的列車管理功能軟件模塊，不僅可以對列車進行高效且安全的管理，還具備較高的可擴展性和可維護性。