有向無環圖技術在列車自動監控系統聯動模塊中的應用實現

周俊輝，孫曉光

（通號城市軌道交通技術有限公司，北京 100070）

軌道交通運營模式中的互聯互通全自動駕駛系統（FAO）是一種將列車駕駛員執行的工作，完全自動化的、高度集中的控制系統所替代的列車運行模式。其中列車自動監控系統直接與調度員交互，其自動化程度在列車運行過程中起著關鍵的作用。列車自動監控系統可以實現列車全自動駕駛系統中線路監控、列車監控、時刻表管理、現地控制、模擬培訓和維護支持等功能。每一個功能都包含眾多的需求點，這些不同的需求點又能組成不同的運營場景。所以每一個場景都是由一系列關聯的順序功能節點組合完成的。為保障系統的正常運轉，確保乘客和工作人員的生命安全，聯動模塊將這一系列關聯的順序執行功能節點劃分為各不相同的職責范圍，但是他們之間存在著緊密和必要的聯系，一個功能節點的變化往往需要其他功能節點做出調整或以其他功能節點的完成作為輸入。尤其是系統運營過程中經常性的人工操作（如每天早間上電、列車喚醒、列車出入庫等），列車運行過程中的情況（如通信車在軌道上運行的發車停車折返、列車清客、車輛段內轉線等），更有各種各樣的突發事件（如車輛火災、運行狀態丟失、車輛欠標過大等）。目前各鐵路運營單位一方面通過應急預案作為有效處置突發事件的基本手段。另一方面則通過借鑒學習或者系統經驗制定需求，以需求方案來限定設備廠商該怎么做。不論哪一方面，都是以文本為主要形式，這些文本規定了事件發生時處置的方法和步驟，明確各個模塊的職責，使各模塊在事件發生后按照文本科學高效的協調工作。但是不論是文本預案還是文本系統需求，在使用過程中存在很大的缺陷，需要相關人員熟悉文本的具體內容。而文本本身通常又不夠直觀，不容易記憶，在處理過程中瀏覽不方便，不能快速提取有效元素，無法讓現場人員明確自動運行是否正常，所有問題完全依賴于現場人員對文本的把握程度。有向無環圖技術可以在一定程度上解決聯動模塊將文本數字化的難題。

1 有向無環圖技術分析

有向無環圖技術（DAG），廣泛用于數據庫建模和工程設計等領域。例如工程設計上用DAG 可以清晰的表達工程的進度等。

有向指的是有方向，準確的說應該是同一方向。無環則指構不成閉環。要想完成當前頂點，必須驗證前面的頂點完成，這種策略最終構成一種拓撲樹狀結構，能夠極大地提高擴展性。之所以不允許有環的出現，是因為DAG 可以保證各個頂點之間的順序，通過頂點的屬性知道本圖中的所有路徑。如果有環出現容易導致系統紊亂，進入死循環。

有向圖是由頂點的有窮非空集合和頂點之間邊的集合組成，圖中某個頂點與其他頂點的直連邊條數稱為該頂點的度。有向圖中，指向其他頂點的邊稱為出度，出度表示由一個頂點出發的邊的總數。被其他頂點指向的邊稱為入度，入度表示指向一個頂點的邊的總數。正是因為圖可以有多個出度和入度，可以同時處理多個出度連接的頂點。所以，有向無環圖流向清晰，可拓展性強。

2 FAO中有向無環圖技術應用實現

軌道交通FAO 系統列車自動監控系統中的聯動模塊將不同的運營場景進行提煉，可以得到一系列不同的隨事件演化過程而順序執行的操作程序，該程序可以提示相關人員何時應該做什么，怎么做。每個操作程序對應圖中的一個頂點，一系列的操作程序構成一個完整的有向無環圖。而演化順序則表明了該有向無環圖的鄰接關系。不同的有向無環圖共同實現了特定的場景。有向無環圖的應用是列車自動監控系統聯動模塊的邏輯處理和執行平臺，是聯動模塊的重要組成部分。

2.1 有向無環圖頂點和邊的數據結構設計

有向無環圖頂點的數據結構如圖1 所示，一個頂點表示一個操作程序的一個步驟，其數據結構定義了一個可用于查找的唯一識別號和唯一名稱。超時時間設置決定當前頂點步驟在條件不滿足需要繼續輪詢時停止輪詢需要消耗的時間。一個頂點步驟同時也可以是一個只有一個頂點的有向無環圖，所以要求一個頂點步驟有輸入條件，也有結束條件，用xml 格式的字符串實現該需求。頂點步驟類型分為可選類型和不可選類型，用于區分每條分支的路徑。當父頂點輸出互斥的結果時，需要明確分支的流向，保證互斥路徑的執行。當存在分支路徑時，頂點是否默認步驟決定了該圖正常狀態時的關鍵路徑。

有向無環圖的邊的數據結構是由當前頂點及其父頂點的鄰接關系組成的map 表。

2.2 有向無環圖的數據結構設計

圖1 頂點數據結構Fig.1 Vertex data structure

一張有向無環圖對應一個完整的處置預案，其數據結構用于描述該有向無環圖的詳細內容，如圖2所示。數據結構中同樣有用于查找的唯一識別號和唯一名稱。為了區別不同的觸發情況，加入圖序號來處理。審核狀態表示如果有向無環圖尚處于未審核通過階段，則該圖暫為不可執行的處置預案。自動類型分為全自動、半自動和手動3 種類型。有向無環圖全自動執行是實時觸發該圖后，立即按照鄰接關系順序執行每一個頂點。有向無環圖手動執行是觸發該圖后，圖的執行以及每個頂點步驟的執行都需要人工參與。有向無環圖半自動執行指的是觸發該圖后，人工決定該圖是否執行，如果人工執行后其頂點步驟由系統自動運行（例如車輛火災可能存在誤報，需要人工確認），之后決定是否響應該圖所有頂點步驟。有向無環圖執行后即從根頂點開始判斷每個頂點的輸入條件是否滿足，輸出條件是否滿足。

圖2 圖數據結構Fig.2 Graph data structure

2.3 有向無環圖應用實現

實際運營場景的有向無環圖利用QtGui 繪制相應的頂點和邊，通過外層容器的信號槽實現頂點的點擊、拖拽和連接。

有向無環圖繪制完畢后需實時加載所有頂點和所有邊，檢查該有向無環圖根頂點是否唯一，結束頂點是否唯一，是否有環。

如何監測有向無環圖是否有環，這個依賴于DFS 深度優先搜索算法。遍歷有向無環圖時如果有頂點被第二次訪問到，那么該圖有環，不是DAG。實現流程如圖3 所示。

圖3 檢測是否有環Fig.3 Check whether there is ring

有向無環圖的狀態轉換如圖4 所示。實際場景中每一個頂點都可能是一個獨立的運營場景，故設計時每個頂點都有輸入輸出條件，每個頂點的狀態轉換和整圖的狀態轉換機制相同。所以在具體實現中，單個頂點有向無環圖的情形與多頂點圖的實現一致。

圖4 狀態圖Fig.4 State diagram

聯動模塊通過設置同一個觸發條件會觸發同一張圖，會在這張圖上多次更改狀態記錄。這種情況與實際不符，故實現有向無環圖時，首先檢查實時緩存中是否存在該圖，若存在且狀態已完成則清理緩存重新加載。此時的圖為不同時機觸發的同一張圖，故設置圖序號來區分這種情況。圖啟動后先加載圖序號，確保圖序號從1 開始，若圖序號已存在，則首先獲取當前圖的最大序號，加1 后得到實時觸發圖的序號。

根據實際運營場景繪制有向無環圖時存在一個頂點步驟的完成狀態不同時流向的分支不同，且另外的分支不執行也不影響其他頂點的狀態。故實現有向無環圖時加入頂點類型，用于區分有分支路徑的情況。當頂點響應后首先得確認頂點是否是分支頂點，根據響應類型決定所走路徑，并屏蔽掉另外的分支路徑。

2.4 數據流設計

設計數據流如圖5 所示，狀態實時監測模塊持續不間斷的監視從各個接口獲取的信息，包括表示信息、列車信息、計劃信息和報警信息等。當滿足頂點的觸發條件后通過相應的狀態源處理器檢查數據，通過圖處理器觸發有向無環圖，并實時更新有向無環圖和頂點的狀態變化，最終在圖執行界面上提示相關處置人員當前處在什么階段，何時該做什么，該怎么做。圖處理器同時將實時變化的狀態通過數據庫處理模塊存儲于數據庫中。

3 結果分析

根據列車監控系統聯動模塊實際場景繪制的有向無環圖示例如圖6 所示，表示按照出庫計劃喚醒列車出庫。

按照休眠喚醒計劃，聯動模塊自動觸發該圖，且無需人工干預，觸發后各頂點自動執行。

喚醒1 車作為一個頂點，本身就會經過準備、開始、接收、暫停、恢復、中止、完成和超時等狀態的遷移。所以喚醒1 車頂點可以作為單獨的一個頂點的圖存在。

圖6 實際場景圖示例Fig.6 Example of actual scene

實際運營場景中通常會有七八輛備用車，本圖例僅作參考。因為備用車的存在，頂點設計時，喚醒1 車的輸出需要進行分支，成功直接開庫門，失敗喚醒備車。這兩個分支路徑是互斥的。所以喚醒1 車需要在觸發并下達列車喚醒命令后，設置一個合理的超時時間。在超時時間內未收到回執，則認為失敗，進行喚醒備車。由于喚醒備車和開庫門是喚醒1 車的分支子頂點，所以需將這兩個頂點設為可選頂點，且開庫門為默認頂點。

圖6 中喚醒1 車狀態為超時狀態，進入喚醒備車的分支。喚醒2 車狀態為成功狀態，開庫門頂點進入開始狀態。當開庫門以中止、超時或完成狀態結束后，整個圖的狀態即結束。

聯動模塊可以查看有向無環圖詳細的描述內容，也可以查看各頂點的詳細內容。運行過程中還可以隨時查看頂點當前狀態的觸發條件信息，哪些條件滿足，哪些條件不滿足，便于相關人員進行人工干預處理。

4 結語

實現有向無環圖的關鍵前提是初期識別并抽象聯動預案，而有向無環圖技術作為聯動模塊的有力補充，能高效便捷的實現系統運行，它配置化程度高，可拓展性高，便于不同線路的移植和實際線路的更新。值得注意的是，DAG 并不是一個新的發現，而是一個古老的問題解決機制。但同時也是年輕的數據結構。隨著技術發展，有向無環圖技術將會在今后的項目應用中更廣泛更普及。