郭 歡

（西南交通大學 信息科學與技術學院，成都 611756）

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

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

1 改進DFS進路搜索算法

1.1 站場型網(wǎng)絡拓撲結構

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

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

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

1.2 基于帶有約束條件的DFS算法設計

1.2.1 按鈕合法性檢查

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

表1 節(jié)點匹配表

1.2.2 二叉樹模型

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

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

1.2.3 約束條件

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

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

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

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

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

1.2.4 進路搜索算法設計

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

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

2 聯(lián)鎖仿真教學系統(tǒng)設計與實現(xiàn)

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

2.1 人機交互界面的設計與實現(xiàn)

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

2.2 進路處理模塊的設計

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

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

2.3 通信接口的設計與實現(xiàn)

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

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

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

3 系統(tǒng)實際應用

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

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

4 結束語

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