有向圖在CBTC 系統(tǒng)中的應用

陳凌安

(上海自儀泰雷茲交通自動化系統(tǒng)有限公司)

0 引 言

根據(jù)IEEE 中的定義，CBTC 系統(tǒng)是一種不依賴于軌道電路的高精度的列車定位，雙向連續(xù)、大容量的車－地數(shù)據(jù)通信和車載、地面安全功能處理器來實現(xiàn)列車連續(xù)自動控制的系統(tǒng)。因此，高精度的列車定位是實現(xiàn)CBTC 的基礎。如何從CBTC 系統(tǒng)軟件上，設計和管理列車的位置，以及其他與CBTC 功能相關的信號設備的位置等信息，是本文需要討論的問題。

本文首先從有向圖的理論，來分析城市軌道交通線路與有向圖的相似性。然后，從城市軌道交通的靜態(tài)信號設備和動態(tài)信號設備兩個方面，來分析有向圖的運用及重要作用，最后說明有向圖理論在CBTC 系統(tǒng)中的實用性。

1 有向圖理論

有向圖是一個二元組＜V，E ＞，其中，V 是非空集合，稱為頂點集。E 是V×V 的子集，稱為弧集。如圖1 所示，是典型的有線圖的形式。

圖1 有向圖形式

因此，在有向圖上可以用＜E，偏移量＞來表示圖上任意一點的信息，并且任意點＜Ei，偏移量j ＞還具有唯一性的特點，不存在二義性的問題。

2 有向圖理論在CBTC 中的應用

通過以上對有向圖的理解，城市軌道交通線路類似于一個有向圖，如圖2 所示。通過引入有向圖的概念，我們可以充分利用有向圖中的數(shù)據(jù)結構和算法，來實現(xiàn)一些設備管理和搜索的算法，并可以將這些算法和數(shù)據(jù)結構運用到CBTC系統(tǒng)的軟件中。

在圖2 中，整個的軌道交通線路，以道岔和線路終端作為有向圖的節(jié)點ni。節(jié)點nj和節(jié)點nk之間的線路或者道岔為有向圖的邊si。并且，si具有一定的方向性，在圖中規(guī)定所有向左的方向定義為邊的正方向。

通過以上方式，可以唯一得確定軌道上任何一點的位置，用(si，offset)來表示。

圖2 線路拓撲結構圖

2.1 靜態(tài)設備的管理

靜態(tài)數(shù)據(jù)是指其在城市軌道交通線路圖中位置同定不變的數(shù)據(jù)類型，主要包括靜態(tài)線路數(shù)據(jù)和線路拓撲數(shù)據(jù)。對于CBTC 來講，靜態(tài)設備主要包括以下內(nèi)容:

(1)軌道線路

(2)信標

(3)站臺

(4)區(qū)段

(5)信號機等。

如圖3 所示，為上海某商用運營線路的部分設備布置圖。采用有向圖的方法來管理和搜索信號設備，是一種高效的方法。以定位信標transponderi為例，對于具體的信標來講，transponderi∈sk，同時，

其中，sk的正方向相鄰邊為sn，sk的反方向相鄰邊為sm。

采用有向圖的方法，可以借鑒圖論的經(jīng)典搜索算法來實現(xiàn)CBTC 系統(tǒng)中的信標搜索功能。這樣，既提高了算法的效率，又合理地設計了信號設備的軟件數(shù)據(jù)結構。同樣，對于其他的靜態(tài)信號設備，都可以采用這種方式來實現(xiàn)存儲和管理。

2.2 動態(tài)設備的管理

對于CBTC 下的動態(tài)設備來講，主要就是列車。由于CBTC 的實現(xiàn)依賴于高精度的列車定位，那么如何確定以及實時更新列車的位置，在CBTC 系統(tǒng)中是一個主要的問題。采用有向圖的方法，可以很簡潔地表示列車的位置信息。

圖3 上海某商用運營線路部分信號設備平面布置圖

假設列車所在的位置是traink(si，offsetm)，如果列車運行了distance，則更新后的列車位置計算，可以采用如圖4 的算法來實現(xiàn):

圖4 更新列車位置算法

因此，采用有向圖的方法，可以很方便地實現(xiàn)更新列車位置的算法，并且該算法還具有一定的通用性，比如說，可以運用到搜索一定區(qū)域范圍內(nèi)的信號設備信息等方面。

3 結 論

綜上所述，通過將有向圖理論應用到城市軌道交通的CBTC 系統(tǒng)中，可以解決如下的問題:

(1)CBTC 系統(tǒng)中的設備信息管理;(2)CBTC 系統(tǒng)中的軟件算法優(yōu)化;(3)為實現(xiàn)城市軌道交通信號系統(tǒng)的互聯(lián)互通打好基礎。

［1］ Rail transit vehicle interface standards committee. IEEE standard for communication－based train control performance and functional requirements.1999.