郭 歡

（西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，成都 611756）

為保證行車安全，通過(guò)技術(shù)方法使進(jìn)路、道岔和信號(hào)機(jī)之間按一定程序、在一定條件下建立起的相互聯(lián)系、相互制約的關(guān)系叫做聯(lián)鎖[1]。在進(jìn)路辦理后，聯(lián)鎖系統(tǒng)根據(jù)始終端節(jié)點(diǎn)進(jìn)行進(jìn)路搜索、敵對(duì)信息檢查、控制道岔轉(zhuǎn)換、進(jìn)路鎖閉、敵對(duì)信息復(fù)查、開放信號(hào)及進(jìn)路解鎖等系列邏輯運(yùn)算。聯(lián)鎖邏輯保障列車在站內(nèi)的安全運(yùn)行，而進(jìn)路選排效率則影響著調(diào)度行車組織能力。

現(xiàn)有的進(jìn)路搜索方式主要有廣度優(yōu)先搜索（BFS，Breadth First Search）、深度優(yōu)先搜索（DFS，Depth First Search）、進(jìn)路表式搜索以及A*搜索等算法。BFS 算法是依據(jù)樹層次遍歷的方法，Dijkstra 單源最短路徑算法采用了和BFS 算法類似的思想[2-3]，適用于股道數(shù)較少的車站；DFS 算法是依據(jù)樹的先序遍歷方法[4]，適用于咽喉區(qū)對(duì)向道岔較少的車站；進(jìn)路表式搜索算法根據(jù)聯(lián)鎖表中的每條進(jìn)路建立進(jìn)路表式數(shù)據(jù)結(jié)構(gòu)，根據(jù)始終端節(jié)點(diǎn)來(lái)調(diào)用進(jìn)路數(shù)據(jù)，算法簡(jiǎn)單，但擴(kuò)展性差[5]；A*搜索算法利用啟發(fā)信息優(yōu)化搜索過(guò)程，減少了大量搜索路徑，但搜索效率仍然受限[6]。雖然以上搜索算法均能準(zhǔn)確搜索出所排進(jìn)路，但是均存在著一定的局限性。本文構(gòu)建規(guī)模較小的動(dòng)態(tài)二叉樹模型，設(shè)計(jì)基于帶有約束條件的DFS 算法，在每個(gè)對(duì)向道岔處通過(guò)約束條件來(lái)決策進(jìn)路搜索走向，按照正確導(dǎo)向一次性找到目標(biāo)節(jié)點(diǎn)，從而避免搜索的盲目性?；诟倪M(jìn)DFS 算法開發(fā)出功能全面且對(duì)硬件要求低的聯(lián)鎖仿真教學(xué)系統(tǒng)，可直觀地反映出車站內(nèi)的進(jìn)路控制過(guò)程，最大限度地滿足師生對(duì)計(jì)算機(jī)聯(lián)鎖系統(tǒng)的實(shí)踐教學(xué)需求。

1 改進(jìn)DFS進(jìn)路搜索算法

1.1 站場(chǎng)型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

站場(chǎng)型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)用來(lái)存儲(chǔ)信號(hào)機(jī)、道岔和軌道電路的狀態(tài)和屬性，具有優(yōu)化程序存儲(chǔ)空間，提高系統(tǒng)穩(wěn)定性等特點(diǎn)。由于設(shè)備屬性不同，需對(duì)它們分別建類，將屬性作為靜態(tài)變量，狀態(tài)作為動(dòng)態(tài)變量，且變量值的設(shè)定必須滿足“故障—安全”原則。因此，需選用合適的編碼方法和差錯(cuò)控制技術(shù)，來(lái)提高軟件的安全性和可靠性[7]。從安全性的角度考慮，需從2n個(gè)碼字中選取2 個(gè)碼字作為有效碼，1 個(gè)用于表示安全側(cè)，另1 個(gè)表示危險(xiǎn)側(cè)，其余的皆為非法碼。由概率理論推斷，在n位二進(jìn)制編碼中，n值越大，其出現(xiàn)危險(xiǎn)的比率就越小，故障導(dǎo)向安全的概率就越大。但是在實(shí)際應(yīng)用中微機(jī)硬件故障或外界干擾致使邏輯出錯(cuò)的概率難以統(tǒng)計(jì)，因而可以利用一種保守的計(jì)算方法，得出用n位二進(jìn)制編碼故障導(dǎo)致危險(xiǎn)的比率為：

若選取n=8，則δ=4×10-3，此值與6502 電氣集中出現(xiàn)危險(xiǎn)概率在同一數(shù)量級(jí)上，故選取8 位即可保證“故障—安全”原則。站場(chǎng)型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)由相鄰節(jié)點(diǎn)通過(guò)單向鏈表的形式鏈接，每個(gè)節(jié)點(diǎn)結(jié)構(gòu)由設(shè)備固有屬性數(shù)據(jù)和相鄰設(shè)備編號(hào)及“緯度”構(gòu)成，將搜索方向統(tǒng)一設(shè)置為由出站信號(hào)機(jī)至進(jìn)站信號(hào)機(jī)，便于動(dòng)態(tài)建立二叉樹時(shí)縮小節(jié)點(diǎn)范圍。以華山北站為例，其站場(chǎng)型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖1 所示。

類似于股道編號(hào)，按照遠(yuǎn)離信號(hào)樓的方向，對(duì)股道按照從小到大的順序進(jìn)行“緯度”定義，同一股道走向上的所有設(shè)備屬于同一“緯度”；若有設(shè)備不與任何股道在同一“緯度”，則將該“緯度”的設(shè)備定義為虛擬股道，參與定義?！熬暥取弊鳛榧s束條件的重要判斷依據(jù)，能夠準(zhǔn)確地推算出進(jìn)路搜索走向。

1.2 基于帶有約束條件的DFS算法設(shè)計(jì)

1.2.1 按鈕合法性檢查

進(jìn)路的搜索過(guò)程其實(shí)是節(jié)點(diǎn)匹配的過(guò)程[8]。在進(jìn)行節(jié)點(diǎn)搜索前先完成按鈕合法性檢查，即判定所按下的兩個(gè)按鈕能否建立進(jìn)路并滿足聯(lián)鎖要求。將不符合表1 匹配條件的進(jìn)路操作直接排除，這樣有利于進(jìn)路搜索效率的提升。

表1 節(jié)點(diǎn)匹配表

1.2.2 二叉樹模型

站場(chǎng)型數(shù)據(jù)結(jié)構(gòu)的本質(zhì)是節(jié)點(diǎn)的鏈接，二叉樹在存儲(chǔ)的過(guò)程中采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，因而可將站場(chǎng)圖形數(shù)據(jù)結(jié)構(gòu)與二叉樹進(jìn)行類比，雖然站場(chǎng)圖形數(shù)據(jù)結(jié)構(gòu)為網(wǎng)狀結(jié)構(gòu)，但進(jìn)路搜索是由始祖節(jié)點(diǎn)出發(fā)到達(dá)目標(biāo)節(jié)點(diǎn)的過(guò)程，故將一條進(jìn)路的搜索網(wǎng)絡(luò)抽象為一棵二叉樹，以二叉樹的形式進(jìn)行建模。在進(jìn)路搜索中所建立的是一棵動(dòng)態(tài)的二叉樹，當(dāng)下達(dá)進(jìn)路操作命令后，其始祖節(jié)點(diǎn)為靠近股道的信號(hào)節(jié)點(diǎn)，然后依據(jù)圖的搜索策略來(lái)尋找目標(biāo)節(jié)點(diǎn)進(jìn)行匹配。由站內(nèi)至站外的搜索方向使二叉樹模型進(jìn)一步縮小內(nèi)存空間，提升匹配效率。

船舶設(shè)備在安裝作業(yè)中涉及了較多的重型設(shè)備構(gòu)件，以及精密的儀表控制設(shè)備，該類設(shè)備在安裝組建中，落實(shí)良好的減振措施對(duì)于船舶設(shè)備的安裝質(zhì)量提升，以及船舶后期的應(yīng)用效果保障發(fā)揮了重要的作用。因此在實(shí)際發(fā)展中如何有效的應(yīng)用減振措施，并且提升船舶設(shè)備的安裝質(zhì)量，則引起了設(shè)備安裝人員及應(yīng)用人員的關(guān)注。筆者針對(duì)當(dāng)前減振措施在船舶設(shè)備安裝中的應(yīng)用，進(jìn)行簡(jiǎn)要的剖析研究，以盼能為相關(guān)船舶設(shè)備的安裝作業(yè)提供參考。

1.2.3 約束條件

由于對(duì)向道岔具有直股和彎股2 個(gè)搜索方向，可通過(guò)約束條件判斷正確的搜索走向，提升效率同時(shí)也節(jié)省存儲(chǔ)空間。在建立數(shù)據(jù)網(wǎng)絡(luò)初期，每個(gè)節(jié)點(diǎn)按照股道排序都定義了“緯度”。搜索方向確定后，從始祖節(jié)點(diǎn)開始，當(dāng)搜索至對(duì)向道岔節(jié)點(diǎn)時(shí)，比對(duì)直股和彎股節(jié)點(diǎn)的“緯度”，然后依據(jù)“緯度”屬性識(shí)別出更接近目標(biāo)節(jié)點(diǎn)的相鄰節(jié)點(diǎn)，沿著相鄰節(jié)點(diǎn)繼續(xù)完成搜索。約束條件遵循以下原則：

（1）無(wú)論接發(fā)車進(jìn)路還是調(diào)車進(jìn)路，搜索方向均設(shè)置為由站內(nèi)至站外；

（2）搜索方向確定后，記錄“緯度”變化是升序、降序還是同一“緯度”；

（3）搜索到對(duì)向道岔時(shí)，首先判斷彎股節(jié)點(diǎn)“緯度”是否在始終端節(jié)點(diǎn)的范圍內(nèi)，若不是則將直股節(jié)點(diǎn)壓入進(jìn)路搜索棧中；若是則根據(jù)原則（2）判斷哪個(gè)節(jié)點(diǎn)“緯度”距離目標(biāo)節(jié)點(diǎn)更接近，將此節(jié)點(diǎn)壓入棧中；

（4）當(dāng)搜索結(jié)束未找到目標(biāo)節(jié)點(diǎn)時(shí)，取消約束條件的限制，按照“直股優(yōu)先”的深度優(yōu)先搜索算法重新搜索，直至找到目標(biāo)節(jié)點(diǎn)，否則認(rèn)為該進(jìn)路不存在。

1.2.4 進(jìn)路搜索算法設(shè)計(jì)

由以上分析可知，X 至3 股接車進(jìn)路的搜索過(guò)程可以看作是一棵二叉樹的遍歷。當(dāng)進(jìn)行圖的深度優(yōu)先搜索時(shí)，從始祖節(jié)點(diǎn)出發(fā)，選擇其鄰接點(diǎn)G 進(jìn)行搜索，再?gòu)腉 出發(fā)訪問(wèn)與G 鄰接的但還未訪問(wèn)過(guò)的G1，再?gòu)腉1 出發(fā)重復(fù)進(jìn)行以上步驟，直到找到目標(biāo)節(jié)點(diǎn)為止。本次設(shè)計(jì)中所采用進(jìn)路搜索的策略是帶有約束條件的DFS，采用深度優(yōu)先策略遍歷時(shí)，約定其沿單一方向進(jìn)行搜索，遇到對(duì)向道岔時(shí)利用約束條件來(lái)決策搜索走向，使每個(gè)搜索到的節(jié)點(diǎn)都有意義，不但提升搜索效率，而且滿足直股優(yōu)先的搜索原則。

進(jìn)路搜索程序的具體實(shí)現(xiàn)過(guò)程如圖3 所示。在進(jìn)路搜索時(shí)以節(jié)點(diǎn)結(jié)構(gòu)圖為基礎(chǔ)，每個(gè)對(duì)向道岔節(jié)點(diǎn)的相鄰節(jié)點(diǎn)擴(kuò)展為2 個(gè)子節(jié)點(diǎn)，除對(duì)向道岔外其他信號(hào)設(shè)備有且只有1 個(gè)后繼節(jié)點(diǎn)。搜索過(guò)程中建立從站內(nèi)至站外的動(dòng)態(tài)二叉樹，從始祖節(jié)點(diǎn)開始，對(duì)該條進(jìn)路搜索過(guò)程中所涉及到的對(duì)向道岔節(jié)點(diǎn)均利用約束條件來(lái)決策對(duì)搜索有意義的相鄰節(jié)點(diǎn)。為防止選出迂回進(jìn)路，只允許同類渡線間搜索，并且八字變更是不允許的，不作入棧操作。對(duì)于變更進(jìn)路，依次搜索始祖節(jié)點(diǎn)到變更按鈕間和變更按鈕到目標(biāo)節(jié)點(diǎn)間的路徑，然后將其組合在一起。流程圖中棧S1 用于存放所搜索進(jìn)路上的所有節(jié)點(diǎn)，G 表示當(dāng)前搜索到的進(jìn)路上的節(jié)點(diǎn)，G1 表示G 的有效相鄰節(jié)點(diǎn)。

2 聯(lián)鎖仿真教學(xué)系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

從教學(xué)角度進(jìn)行需求分析，基于Visual Studio 2010 平臺(tái)采用C++語(yǔ)言進(jìn)行軟件開發(fā)，實(shí)現(xiàn)聯(lián)鎖仿真教學(xué)系統(tǒng)的設(shè)計(jì)。系統(tǒng)主要由交互界面、聯(lián)鎖控制和通信接口3 部分構(gòu)成，各部分均按照鐵總技術(shù)規(guī)范要求來(lái)設(shè)計(jì)，使之更加貼近現(xiàn)實(shí)計(jì)算機(jī)聯(lián)鎖系統(tǒng)。

2.1 人機(jī)交互界面的設(shè)計(jì)與實(shí)現(xiàn)

針對(duì)信號(hào)機(jī)、軌道區(qū)段、道岔特性定義結(jié)構(gòu)體，使程序模塊化，并易于對(duì)象數(shù)據(jù)的擴(kuò)充和維護(hù)。仿真界面參考《計(jì)算機(jī)聯(lián)鎖操作顯示規(guī)范文稿》設(shè)計(jì)，主要由常用功能按鈕區(qū)、站場(chǎng)圖區(qū)和信息窗等部分組成，如圖4 所示。常用功能按鈕區(qū)根據(jù)車站聯(lián)鎖功能來(lái)配置相應(yīng)的按鈕，如清除、總?cè)∠?、總?cè)私狻^(qū)故解、道岔單操、引導(dǎo)、上電解鎖、輔助菜單等；站場(chǎng)圖區(qū)用來(lái)顯示站內(nèi)信號(hào)設(shè)備的狀態(tài)，識(shí)別要控制的設(shè)備；信息窗主要顯示報(bào)警、預(yù)警、設(shè)備狀態(tài)及提示信息，根據(jù)《報(bào)警表》和《預(yù)警表》提示聯(lián)鎖機(jī)與其他系統(tǒng)間的通信狀況及聯(lián)鎖機(jī)運(yùn)行狀態(tài)。此外，還添加了通信故障、通信數(shù)據(jù)和通信拓?fù)? 個(gè)按鈕，用于設(shè)置通信故障，查詢通信狀態(tài)和數(shù)據(jù)。

2.2 進(jìn)路處理模塊的設(shè)計(jì)

當(dāng)始祖節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)匹配成功后，此時(shí)進(jìn)路被選出，但進(jìn)路還未建立，需進(jìn)行進(jìn)路處理（即聯(lián)鎖條件檢查）。聯(lián)鎖條件檢查包括進(jìn)路選排一致性檢查、敵對(duì)進(jìn)路建立檢查、軌道區(qū)段空閑檢查、信號(hào)開放檢查、正常解鎖條件檢查和進(jìn)路鎖閉檢查。

進(jìn)路處理的具體流程如圖5 所示。從列表中依次取出已搜索完成的進(jìn)路，變量i代表當(dāng)前進(jìn)路號(hào)，變量n為臨時(shí)進(jìn)路表中的總數(shù)。首先檢查該條進(jìn)路內(nèi)軌道區(qū)段是否空閑，若不空閑直接進(jìn)入下一條進(jìn)路聯(lián)鎖條件檢查；接著檢查進(jìn)路的選排一致性，將不符合進(jìn)路所需位置的道岔轉(zhuǎn)換至進(jìn)路要求位置，并且當(dāng)檢查到敵對(duì)進(jìn)路沒(méi)有建立的情況下需將敵對(duì)進(jìn)路鎖在未建立的狀態(tài)，然后鎖閉進(jìn)路。當(dāng)以上條件均滿足后，檢查信號(hào)開放的條件，若滿足即可開放信號(hào)，進(jìn)路建立；若不滿足，則進(jìn)入正常解鎖模塊檢查。

2.3 通信接口的設(shè)計(jì)與實(shí)現(xiàn)

聯(lián)鎖系統(tǒng)不再是單獨(dú)的車站信號(hào)控制系統(tǒng)，而是綜合行車指揮控制系統(tǒng)的重要組成部分。聯(lián)鎖系統(tǒng)不但要完成車站內(nèi)的列車安全防護(hù)，還需要與分散自律調(diào)度集中系統(tǒng)（CTC，Centralized Traffic Control System）、 無(wú) 線 閉 塞 中 心（RBC，Radio Block Center）、列控中心（TCC，Train Control Center）及軌旁模擬器等系統(tǒng)建立通信網(wǎng)絡(luò)，實(shí)現(xiàn)信息共享。系統(tǒng)嚴(yán)格遵循《高鐵計(jì)算機(jī)聯(lián)鎖系統(tǒng)接口技術(shù)規(guī)范》制定通信內(nèi)容、周期、時(shí)序及協(xié)議，以數(shù)據(jù)包的形式通過(guò)Socket 傳輸。

聯(lián)鎖機(jī)與其他子系統(tǒng)通信內(nèi)容如表2 所示，聯(lián)鎖系統(tǒng)為CTC 提供站場(chǎng)顯示、按鈕狀態(tài)等信息，并執(zhí)行其下發(fā)的進(jìn)路辦理命令；為RBC 提供站內(nèi)軌道電路、區(qū)間閉塞分區(qū)、區(qū)間閉塞方向及列車進(jìn)路等信息，用于計(jì)算移動(dòng)授權(quán)；為TCC 提供區(qū)間控制命令、進(jìn)路等信息，TCC 向聯(lián)鎖系統(tǒng)提供區(qū)間運(yùn)行方向、區(qū)間閉塞分區(qū)狀態(tài)及信號(hào)限速等信息；軌旁模擬器用來(lái)仿真室外信號(hào)設(shè)備，聯(lián)鎖機(jī)控制軌旁設(shè)備動(dòng)作，軌旁模擬器將設(shè)備狀態(tài)發(fā)送給聯(lián)鎖機(jī)。

表2 聯(lián)鎖機(jī)與其他子系統(tǒng)通信內(nèi)容表

3 系統(tǒng)實(shí)際應(yīng)用

系統(tǒng)操作界面如圖6 所示，聯(lián)鎖仿真教學(xué)系統(tǒng)可自動(dòng)或人工辦理多車接、發(fā)車進(jìn)路，車站值班員可進(jìn)行取消進(jìn)路、人工解鎖、區(qū)段故障解鎖、重開信號(hào)、單操道岔、辦理引導(dǎo)進(jìn)路和引導(dǎo)總鎖閉等操作，此外系統(tǒng)還具備上電解鎖、分散自律控制和站控的轉(zhuǎn)換、正常/輔助改方、區(qū)段分錄不良設(shè)置、設(shè)備狀態(tài)顯示、故障預(yù)警和故障報(bào)警等功能。聯(lián)鎖系統(tǒng)通常由調(diào)度中心直接控制，根據(jù)行車計(jì)劃自動(dòng)辦理接、發(fā)車進(jìn)路，但當(dāng)CTC 設(shè)備故障或通信中斷、天窗維修時(shí)，須將系統(tǒng)轉(zhuǎn)至非常站控，控制權(quán)交還給車站值班員。緊急情況下，車站值班員可破鉛封按壓“非常站控”按鈕脫離CTC 控制，掌握車站控制權(quán)。

實(shí)驗(yàn)室安裝了鄭西線的華山北、渭南北和臨潼東三站聯(lián)鎖系統(tǒng)，通過(guò)局域網(wǎng)連接其他子系統(tǒng)，完成三站四區(qū)間的仿真線路搭建。通過(guò)對(duì)系統(tǒng)的反復(fù)調(diào)試、優(yōu)化，使聯(lián)鎖仿真教學(xué)系統(tǒng)具備功能全、兼容性強(qiáng)、擴(kuò)展性高等特點(diǎn)，并且集成了軌旁模擬器的故障設(shè)置和CTC 的特殊場(chǎng)景一鍵演示等功能，使同學(xué)們實(shí)操的同時(shí)對(duì)聯(lián)鎖系統(tǒng)的原理和功能有更加深入的理解。

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

本文依照站場(chǎng)數(shù)據(jù)自動(dòng)建立站場(chǎng)型數(shù)據(jù)網(wǎng)絡(luò)，根據(jù)始終端按鈕將車站節(jié)點(diǎn)建立動(dòng)態(tài)二叉樹動(dòng)態(tài)模型，在深度優(yōu)先搜索的基礎(chǔ)上利用約束條件使搜索方向更加明確，使搜索效率達(dá)到更優(yōu)，此外根據(jù)高鐵聯(lián)鎖系統(tǒng)的特點(diǎn)，完成聯(lián)鎖功能和通信接口。由于實(shí)驗(yàn)室受場(chǎng)地、經(jīng)費(fèi)等因素的影響，很難搭建現(xiàn)場(chǎng)使用的系統(tǒng)，所以采取純軟件的方式來(lái)實(shí)現(xiàn)聯(lián)鎖系統(tǒng)的功能仿真。該系統(tǒng)不但可以進(jìn)行聯(lián)鎖實(shí)驗(yàn)，還可手動(dòng)設(shè)置通信故障，查詢數(shù)據(jù)包，為學(xué)生提供了很好的動(dòng)手實(shí)踐平臺(tái)。