徐 鑫，陳光武

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 進(jìn)路搜索算法的分析與比較

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

3.1.1 廣度搜索算法

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

圖3 廣度搜索示意圖

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

3.1.2 深度搜索算法

深度搜索類似于樹(shù)的先序遍歷的過(guò)程。深度搜索示意如圖4。

圖4 深度搜索示意圖

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

3.1.3 高度無(wú)往返搜索算法

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

圖5 高度無(wú)往返搜索示意圖

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

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

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

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

3.2.1 搜索算法的描述

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

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

（3）取特殊節(jié)點(diǎn)為臨時(shí)目標(biāo)節(jié)點(diǎn)，生成新的節(jié)點(diǎn)對(duì)。

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

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

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

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

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

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

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

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

3.2.2 進(jìn)路搜索流程

進(jìn)路搜索算法的基本流程如圖6。

圖6 進(jìn)路搜索流程圖

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

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

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

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

圖8 上位機(jī)界面顯示截圖

5 結(jié)束語(yǔ)

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

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

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

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

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

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

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

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