徐 鑫，陳光武

（蘭州交通大學(xué) 光電技術(shù)與智能控制教育部重點實驗室， 蘭州 730070）

鐵路車站聯(lián)鎖系統(tǒng)是鐵路運輸領(lǐng)域中的控制系統(tǒng)，以技術(shù)手段識別、減弱甚至消除車站內(nèi)危及行車安全的不確定因素。國內(nèi)車站聯(lián)鎖控制系統(tǒng)經(jīng)歷了機械聯(lián)鎖控制、電氣集中聯(lián)鎖控制，自上世紀(jì)80年代我國采用計算機聯(lián)鎖控制以來，計算機聯(lián)鎖控制技術(shù)日趨完善并逐漸成為車站聯(lián)鎖控制的主要形式。

1 計算機聯(lián)鎖系統(tǒng)軟件總體構(gòu)成

根據(jù)計算機聯(lián)鎖系統(tǒng)硬件結(jié)構(gòu)搭建相應(yīng)的聯(lián)鎖系統(tǒng)軟件，按層次劃分為：人機會話層、聯(lián)鎖運算層和執(zhí)行層，結(jié)構(gòu)如圖1。

2 聯(lián)鎖軟件設(shè)計

本設(shè)計基于計算機聯(lián)鎖制式檢測標(biāo)準(zhǔn)站（第2版）。

圖1 軟件層次結(jié)構(gòu)圖

2.1 聯(lián)鎖數(shù)據(jù)結(jié)構(gòu)

聯(lián)鎖運算所處理的對象主要有3類：信號機、道岔和軌道區(qū)段。如何將這些設(shè)備對象有效地組織起來供聯(lián)鎖程序使用，是編寫聯(lián)鎖軟件首要的問題。由頂點的集合以及邊的集合組成，將每一個設(shè)備對象看成是數(shù)據(jù)節(jié)點，根據(jù)其在信號平面布置圖中位置鏈接起來就構(gòu)成了設(shè)備節(jié)點圖。每個數(shù)據(jù)節(jié)點在圖中的位置與實際站場圖中的位置一致，因此將這種數(shù)據(jù)結(jié)構(gòu)稱為站場型數(shù)據(jù)結(jié)構(gòu)。部分站場對應(yīng)的站場型數(shù)據(jù)結(jié)構(gòu)如圖2。

2.2 聯(lián)鎖控制程序

圖2 部分站場及對應(yīng)的數(shù)據(jù)結(jié)構(gòu)圖

軟件的編制以鐵道部《計算機聯(lián)鎖技術(shù)條件》為依據(jù)，在設(shè)計時要考慮軟件的標(biāo)準(zhǔn)化、規(guī)范化以及模塊化。在編寫聯(lián)鎖軟件時將聯(lián)鎖控制程序劃分為6個模塊：（1）操作輸入及操作命令形成模塊。（2）操作命令執(zhí)行模塊。（3）進路處理模塊。（4）狀態(tài)輸入模塊。（5）表示輸出模塊。（6）控制命令輸出模塊。

3 進路搜索模塊設(shè)計

進路是由若干個信號機、道岔及道岔位置、軌道區(qū)段組成的列車在車站內(nèi)運行時所經(jīng)過的通路。進路搜索必須搜索出由始端信號點到終端信號點這條進路上的所有設(shè)備節(jié)點。如何更高效率地完成進路搜索對聯(lián)鎖軟件存在很大的影響，為了程序的安全和高效，可采取各種各樣的算法。

3.1 進路搜索算法的分析與比較

實際站場結(jié)構(gòu)類似于圖的結(jié)構(gòu)，由節(jié)點（信號機，道岔，區(qū)段）的集合以及邊（節(jié)點之間的鏈接關(guān)系）的集合組成，可以采用圖的存儲結(jié)構(gòu)并運用圖的路徑搜索方法實現(xiàn)站場的進路搜索。

3.1.1 廣度搜索算法

廣度優(yōu)先搜索類似于按樹的層次遍歷的過程。廣度搜索示意如圖3。

圖3 廣度搜索示意圖

圖3 說明了廣度優(yōu)先搜索的具體實現(xiàn)。這種搜索方法遵循從始端節(jié)點開始一層層擴展直到找到目標(biāo)節(jié)點的搜索規(guī)則，搜索方向不確定，承受力很有限。如果擴展節(jié)點較多，而目標(biāo)節(jié)點又處在較深層，采用前面敘述的廣度搜索操作，搜索量非常巨大，往往就會出現(xiàn)內(nèi)存空間不夠用，造成存儲數(shù)據(jù)的溢出等情況。

3.1.2 深度搜索算法

深度搜索類似于樹的先序遍歷的過程。深度搜索示意如圖4。

圖4 深度搜索示意圖

這種搜索算法避免了廣度搜索的搜索路徑分支不明確，但是這種算法是選擇一條路徑走到黑的方式，即不管通過這條路徑能不能找到目標(biāo)節(jié)點都要進行試探，而且在找不到目標(biāo)節(jié)點時還要一步步回溯，大大降低了搜索效率。

3.1.3 高度無往返搜索算法

針對上述搜索算法的不足，提出更新的一種進路搜索方法，稱其為 “高度無往返搜索”。該方法的搜索目標(biāo)明確，沒有采用廣度優(yōu)先搜索按層擴大分支的策略，類似于深度優(yōu)先搜索，但與之不同的是這種方法沒有采用一直沿一條路徑向下搜索，找不到目標(biāo)節(jié)點就一步步回溯的策略。如圖5。

圖5 高度無往返搜索示意圖

“高度無往返搜索”的基本思想是：在站場型數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上，每個設(shè)備節(jié)點都按照其在實際站場中的縱向位置定義其所在高度，橫向位置定義其編號大小，在同一線上的設(shè)備節(jié)點有同樣的高度，見表1。在進行進路搜索時，根據(jù)始終端節(jié)點的橫向編號首先確定搜索方向，在搜索方向上遇到對向道岔時，根據(jù)目標(biāo)節(jié)點高度與始端節(jié)點高度值的比較，確定是沿彎股搜索還是沿直股搜索，完全避免了普通深度優(yōu)先沿直股優(yōu)先策略，搜索不到目標(biāo)節(jié)點然后回溯，繼續(xù)往返搜索的缺點，大大提高搜索效率。

表1 節(jié)點高度分布表

3.2 搜索算法的實現(xiàn)

本設(shè)計中采用“高度無往返搜索”算法進行進路搜索。該搜索要完成的其中一項任務(wù)就是根據(jù)進路操作命令，只能選出一條符合要求的進路（基本進路、迂回進路、或是有多條基本進路組成的符合進路）；在僅指明進路的始終端只能選出一條基本進路而不能選出繞彎的或平行的迂回進路。為此采取了一項措施，在建立站場數(shù)據(jù)結(jié)構(gòu)之前，根據(jù)實際站場結(jié)構(gòu)，在2個節(jié)點之間存在多條平行進路時，將這2個節(jié)點作為一對特殊的節(jié)點對存于數(shù)據(jù)庫中，并列出該特殊節(jié)點對之間的臨時目標(biāo)節(jié)點。

3.2.1 搜索算法的描述

（1）根據(jù)按壓的節(jié)點順序生成節(jié)點對，根據(jù)是終端節(jié)點的橫向編號確定搜索方向。

（2）將生成的節(jié)點對與數(shù)據(jù)庫中的特殊節(jié)點對相比較，如果是特殊節(jié)點對，轉(zhuǎn)到（3），如果不是，轉(zhuǎn)到（4）。

（3）取特殊節(jié)點為臨時目標(biāo)節(jié)點，生成新的節(jié)點對。

（4）取到沿搜索方向上目前節(jié)點的下一節(jié)點。

（5）判斷該節(jié)點是否為目標(biāo)節(jié)點？如果是轉(zhuǎn)到（6），如果不是轉(zhuǎn)到（7）。

（6）檢查是否還有目標(biāo)節(jié)點？如果有，與上一目標(biāo)節(jié)點構(gòu)成新的節(jié)點對，轉(zhuǎn)到（2），如果沒有，搜索成功。

（7）判斷該節(jié)點是否為死結(jié)點（沒有后繼節(jié)點的節(jié)點）？如果是，搜索失敗，如果不是，轉(zhuǎn)到（8）。

（8）判斷是否為對向道岔節(jié)點？如果是，轉(zhuǎn)到(9)，如果不是，轉(zhuǎn)到（4）。

（9）根據(jù)目標(biāo)節(jié)點高度與彎股節(jié)點的高度關(guān)系，判斷彎股能否通向目標(biāo)節(jié)點？如果能，轉(zhuǎn)到(10)，反之轉(zhuǎn)到（11）。

（10）取彎股節(jié)點，轉(zhuǎn)到（5）。

（11）取直股節(jié)點，轉(zhuǎn)到（5）。

3.2.2 進路搜索流程

進路搜索算法的基本流程如圖6。

圖6 進路搜索流程圖

利用上述搜索算法，對標(biāo)準(zhǔn)站場（第2版）上行咽喉辦理XI-S的發(fā)車進路，搜索結(jié)果如圖7。截圖中的操作對象是XI和S信號機，進路搜索數(shù)據(jù)為該條進路上經(jīng)過的所有設(shè)備節(jié)點，顯示結(jié)果為設(shè)備對應(yīng)的ID，進路方向“1”代表發(fā)車進路，進路性質(zhì)“11”代表列車進路。進路鎖閉后在上位機界面顯示如圖8白光帶所示。

圖7 進路搜索數(shù)據(jù)截圖

4 聯(lián)鎖軟件安全性可靠性分析

目前，無論是質(zhì)量保證法還是軟件容錯法的應(yīng)用，都無法保證系統(tǒng)的絕對安全。開發(fā)高安全完整性等級軟件應(yīng)遵循以下原則：（1）自頂向下的設(shè)計方法；（2）模塊化；（3）驗證開發(fā)生命周期的每一階段；（4）驗證模塊和模塊庫；（5）文檔清晰；（6）提供可審計的文檔；（7）確認測試。

圖8 上位機界面顯示截圖

5 結(jié)束語

聯(lián)鎖軟件采用結(jié)構(gòu)化程序設(shè)計方法，自頂而下，逐步求精，并采用模塊化設(shè)計思想，達到了軟件的安全性完整性等級（SIL）4級。采用 “高度無往返搜索”算法進行進路搜索，在時間和空間上都降低了復(fù)雜度，大大提高聯(lián)鎖軟件的執(zhí)行效率。

[1]趙志熙. 計算機聯(lián)鎖系統(tǒng)技術(shù)[M]. 北京：中國鐵道出版社，2008.

[2]殷人昆，陶永雷，謝若陽，盤絢華．?dāng)?shù)據(jù)結(jié)構(gòu)(用面向?qū)ο蠓椒ㄅcc++描述)[M]. 北京：清華大學(xué)出版社，2002.

[3]彭建偉，殷人昆. 基于臨接表結(jié)構(gòu)的進路搜索算法研究[J].計算機工程與設(shè)計，2006，27（18）：4300-4302.

[4]王 璽. 基于安全信息傳輸網(wǎng)的分布式計算機聯(lián)鎖系統(tǒng)設(shè)計[D]. 北京交通大學(xué)，2006，12.

[5] 朱 明，王曉明. 一種鐵路微機聯(lián)鎖進路搜索的實現(xiàn)方法[J]. 鐵路計算機應(yīng)用，2007，16（11）.

[6] TB/T3027-2002，計算機聯(lián)鎖技術(shù)條件[S].

[7] Signalling and processing systems-Software for railway control and protection systems[J]. EN 50128 Railway Applications Communications,March 2001.