基于距離的線路數(shù)據(jù)處理算法

郁文斌

（北京全路通信信號研究設(shè)計(jì)院集團(tuán)有限公司，北京 100070）

1 概述

本文對高鐵信號安全產(chǎn)品列控中心[1]、無線閉塞中心[2]、臨時限速服務(wù)器[3]滿足技術(shù)條件功能的基礎(chǔ)上，對線路數(shù)據(jù)配置和計(jì)算的差異性進(jìn)行分析，參考對于線路數(shù)據(jù)相關(guān)的研究[4]，提出一種基于距離的線路數(shù)據(jù)處理算法，將數(shù)據(jù)配置規(guī)則交給數(shù)據(jù)配置用戶而不是在軟件內(nèi)部自行定義，達(dá)到數(shù)據(jù)配置靈活統(tǒng)一的目的。同時根據(jù)研發(fā)用戶的計(jì)算需求，根據(jù)線路數(shù)據(jù)上任意點(diǎn)的輸入?yún)?shù)信息，得到計(jì)算所需的以線路起點(diǎn)為基準(zhǔn)的絕對距離和以用戶指定參照點(diǎn)為基準(zhǔn)的相對距離，獲得線路數(shù)據(jù)計(jì)算所需的兩點(diǎn)大小比較、兩個區(qū)域范圍判斷、兩點(diǎn)距離計(jì)算信息，使用戶不需要考慮線路數(shù)據(jù)的處理而達(dá)到提高開發(fā)效率的目的。

2 線路數(shù)據(jù)介紹

根據(jù)目前線路數(shù)據(jù)設(shè)計(jì)規(guī)范[5-6]，在鐵路信號設(shè)備運(yùn)行需要以勘察的線路數(shù)據(jù)為基礎(chǔ)進(jìn)行規(guī)范設(shè)計(jì)后，根據(jù)中國國家鐵路集團(tuán)有限公司對于線路數(shù)據(jù)管理的最新規(guī)范[7]對列控?cái)?shù)據(jù)進(jìn)行管理并發(fā)布，各生產(chǎn)單位據(jù)此進(jìn)行信號設(shè)備所需的線路數(shù)據(jù)計(jì)算，進(jìn)行信號的控制，以保障行車運(yùn)營的安全。

目前，對于各產(chǎn)品對于線路數(shù)據(jù)的計(jì)算需求，基本的線路數(shù)據(jù)需要有里程標(biāo)系、里程標(biāo)，在此基礎(chǔ)上定義軌旁設(shè)備的位置相關(guān)的參數(shù)信息，例如線路起終點(diǎn)，應(yīng)答器、信號機(jī)的位置，軌道區(qū)段長度，道岔位置，坡度速度等計(jì)算所需的基礎(chǔ)數(shù)據(jù)，信號設(shè)備據(jù)此進(jìn)行線路數(shù)據(jù)的傳輸和計(jì)算，以提供車載ATP 進(jìn)行制動曲線計(jì)算所需的參數(shù)。由于車載ATP可以在線路的正向、反向運(yùn)行，那么線路數(shù)據(jù)的設(shè)置需要根據(jù)運(yùn)行方向的不同而不同，因此地面設(shè)備需要傳輸?shù)木€路數(shù)據(jù)信息根據(jù)運(yùn)行方向不同而導(dǎo)致處理也不相同，造成各產(chǎn)品的線路數(shù)據(jù)配置規(guī)則和計(jì)算處理設(shè)計(jì)構(gòu)架根據(jù)自身產(chǎn)品特點(diǎn)而存在不同程度上的差異。例如，臨時限速服務(wù)器的線路數(shù)據(jù)與方向無關(guān)，但是需要判斷區(qū)域范圍大小，列控中心和無線閉塞中心則相反，但是他們共同需要在線路數(shù)據(jù)范圍進(jìn)行距離的計(jì)算。

因此，對于線路數(shù)據(jù)的配置、計(jì)算和處理是高鐵信號軟件及測試工具軟件進(jìn)行設(shè)計(jì)的一個必須解決的問題。如果設(shè)計(jì)合理，會極大促進(jìn)產(chǎn)品軟件基于上層信號功能邏輯的實(shí)現(xiàn)簡單易行；反之，則會導(dǎo)致上層應(yīng)用的實(shí)現(xiàn)高耦合。

2.1 問題的提出

針對上述討論，線路數(shù)據(jù)的處理是高鐵領(lǐng)域地面信號軟件的基礎(chǔ)設(shè)計(jì)，需要解決的問題如下。

1）數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：如果線路數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)合理，線路數(shù)據(jù)的配置冗余性低，配置項(xiàng)內(nèi)容少。

2）統(tǒng)一規(guī)范設(shè)計(jì)：如果基于線路數(shù)據(jù)的計(jì)算方法封裝合理，僅提供用戶輸入到計(jì)算結(jié)果的服務(wù)，則線路數(shù)據(jù)的邏輯處理極大程度上能夠按需通用，降低上層應(yīng)用的邏輯設(shè)計(jì)復(fù)雜性。

一條線路上，指定參考方向后，無論與參考方向同向還是反向，均是由若干分段順序構(gòu)成，每個分段內(nèi)對應(yīng)唯一里程標(biāo)系、起點(diǎn)和終點(diǎn)，并存在長鏈。若要進(jìn)行計(jì)算，那么需要解決兩個問題。

1）數(shù)據(jù)配置：分段信息，即線路分段順序；段內(nèi)配置：即段內(nèi)里程標(biāo)系起點(diǎn)、終點(diǎn)的配置；長鏈配置。

2）算法：面向用戶計(jì)算所需的線路數(shù)據(jù)的方法。對于用戶給定的任何形式輸入，提供以距離為基礎(chǔ)的計(jì)算結(jié)果。

2.2 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

本節(jié)對于線路數(shù)據(jù)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)，工程規(guī)定的正向線路方向，即線路基準(zhǔn)方向，也是其他方向定義的基準(zhǔn)或者參考方向。數(shù)據(jù)配置方向（以下簡稱UCDIR），其涉及到分段配置方向，段內(nèi)數(shù)據(jù)配置方向。用戶計(jì)算方向（以下簡稱USDIR），也就是運(yùn)行的實(shí)際方向。無論在UCDIR還是USDIR，分段內(nèi)里程標(biāo)均有遞增遞減趨勢。線路基準(zhǔn)方向的線路第一個分段為BLS，最后一個分段為BLE，分段內(nèi)起始里程標(biāo)為BSS，終點(diǎn)里程標(biāo)為BSE。

線路數(shù)據(jù)需在軟件中進(jìn)行配置，配置第一個分段CLS和最后一個分段CLE。分段內(nèi)數(shù)據(jù)配置起點(diǎn)為CSS和終點(diǎn)CSE。長鏈的配置起點(diǎn)為LCS，帶有長鏈標(biāo)志，終點(diǎn)為LCE，不帶長鏈標(biāo)志，長鏈配置均與方向無關(guān)。長鏈的配置長度為LCL。USDIR方向上，線路計(jì)算的邏輯第一個分段為LLS，最后一個分段為LLE，分段內(nèi)的邏輯起點(diǎn)為LSS，邏輯終點(diǎn)LSE。USDIR方向上，長鏈的邏輯起點(diǎn)為LFS，邏輯終點(diǎn)為LFE。

根據(jù)上述定義，對應(yīng)關(guān)系如下，如表 1、2 所示。

表 1 基礎(chǔ)線路數(shù)據(jù)配置對應(yīng)關(guān)系表Tab.1 Correspondence table of basic line data configuration

表 2 長鏈線路數(shù)據(jù)對應(yīng)關(guān)系表Tab.2 Correspondence table of long chain line data

一條線路上段的順序可能正序或逆序，段內(nèi)線路可能遞增或遞減，根據(jù)表 1、 2 的對應(yīng)關(guān)系，數(shù)據(jù)配置用戶可以自行指定規(guī)則進(jìn)行配置，這套規(guī)則提供了更為靈活和統(tǒng)一的方法，使得配置用戶制定易于配置工作的規(guī)則，從而解決數(shù)據(jù)配置的問題。再結(jié)合算法，提供給研發(fā)用戶統(tǒng)一的計(jì)算所需的邏輯參數(shù)，從而解決線路數(shù)據(jù)計(jì)算算法的問題。

數(shù)據(jù)配置舉例說明：假設(shè)一條線路DIR上有兩個分段，段內(nèi)各有一長鏈，如圖 1 所示。

圖1 線路舉例圖示Fig.1 Line example diagram

數(shù)據(jù)配置規(guī)則可以按表 1、 2 制定，這里給出兩個示例，如表 3 所示。

表 3 數(shù)據(jù)配置距離Tab.3 Data configuration distance

研發(fā)用戶可以根據(jù)表 1、2 建立數(shù)據(jù)配置與計(jì)算所需參數(shù)的邏輯關(guān)系，設(shè)定算法，獲取所需的邏輯參數(shù)。以下對算法進(jìn)行設(shè)計(jì)。

3 基于距離的算法

如果提供一種算法，對于任意輸入點(diǎn)，根據(jù)用戶指定的方向USDIR，輸出其距離USDIR方向上線路邏輯起點(diǎn)的絕對距離，用戶進(jìn)行計(jì)算時，就可以進(jìn)行簡單的數(shù)學(xué)運(yùn)算，得到用戶所需的應(yīng)用結(jié)果。

根據(jù)表 1、2 的分析得知，可以制定如下規(guī)則：

1) 根據(jù)數(shù)據(jù)配置規(guī)則，建立計(jì)算線路參數(shù)與數(shù)據(jù)配置的邏輯關(guān)系；

2) 識別輸入點(diǎn)所在段以及USDIR下，前方所有段；

3) 根據(jù)長鏈的處理結(jié)果，參考散列表原理[8],根據(jù)長鏈定義及其特點(diǎn)，參考散列的應(yīng)用[9]設(shè)計(jì)針對長鏈標(biāo)志和數(shù)據(jù)的散列算法，計(jì)算前方所有段的絕對距離s(x)；

4) 計(jì)算其距離段內(nèi)邏輯起點(diǎn)的相對距離f(x)；

5) 輸出z(x)=s(x)+f(x)；

6) 短鏈則直接對短鏈起點(diǎn)和終點(diǎn)相對線路起點(diǎn)距離進(jìn)行直接計(jì)算，由用戶直接處理。

根據(jù)上述規(guī)則分別提出解決方法如下。

3.1 段內(nèi)處理

設(shè)M 為長鏈最大配置數(shù)，N為最大分段數(shù)，x為輸入點(diǎn)，定義公式：

其中，LFSt'(x)的計(jì)算可以由公式（8）給出。

其中，公式(1)為給定帶有長鏈點(diǎn)返回對應(yīng)配置的長鏈終點(diǎn)；公式(2)為給定帶有長鏈點(diǎn)返回對應(yīng)配置的長鏈所在的下標(biāo)，即線路上的第幾個長鏈點(diǎn)；公式(3)為給定輸入點(diǎn)，返回USDIR方向所在的分段索引；集合(4)為與輸入點(diǎn)同屬一個分段內(nèi)的所有長鏈配置點(diǎn)，且USDIR方向，在輸入點(diǎn)前方的所有長鏈點(diǎn)；公式(5)為USDIR方向，分段x內(nèi)的所有長鏈點(diǎn)。公式(6)為輸入點(diǎn)所在段的前方所有段并包含其中所有長鏈點(diǎn)的距離；公式(7)為USDIR方向，輸入點(diǎn)所在段中，距離段邏輯起點(diǎn)并包含長鏈點(diǎn)的距離；公式(8)為USDIR方向，輸入點(diǎn)具有長鏈標(biāo)志時，對于其距離長鏈邏輯起點(diǎn)的距離，通過設(shè)計(jì)對應(yīng)的長鏈散列算法進(jìn)行實(shí)現(xiàn)。

3.2 不考慮長鏈

對于公式(3)、(4)、(6)和(7)，均涉及到段內(nèi)輸入點(diǎn)距離段內(nèi)線路邏輯起點(diǎn)的判斷和相對距離計(jì)算，且距離的計(jì)算均為不考慮長鏈點(diǎn)的計(jì)算。

因此，在數(shù)據(jù)配置的基礎(chǔ)上，首先建立起數(shù)據(jù)配置與邏輯參數(shù)之間的關(guān)系，才能實(shí)現(xiàn)公式。對研發(fā)用戶屏蔽數(shù)據(jù)配置，根據(jù)需求獲取所需的邏輯參數(shù)。

根據(jù)表 1 ～ 3，線路段間關(guān)系如圖 2、 3 所示。

如果線路上配置段數(shù)為n，j為USDIR方向上邏輯段的下標(biāo)，即x點(diǎn)在線路上的第j段(0 ≤j＜n)，那么與配置的分段下標(biāo)k(x)關(guān)系為：

那么對于公式(2)得出：

圖2 線路分段順序配置與DIR同向圖示Fig.2 Diagram of line section sequential configuration in the same direction of as DIR

圖3 線路分段順序配置與DIR反向圖示Fig.3 Diagram of line section sequential configuration in the opposite direction as DIR

根據(jù)表 1 ～ 3，段內(nèi)關(guān)系如圖 4、 5 所示。

圖4 分段配置與DIR同向圖示Fig.4 Diagram o section configuration in the same direction as DIR

圖5 分段配置與DIR反向圖示Fig.5 Diagram of section configuration in the reverse direction as DIR

對于第i個段內(nèi)，可得到公式：

公式（9）～（12）為在具體線路數(shù)據(jù)根據(jù)第2.2 節(jié)中數(shù)據(jù)結(jié)構(gòu)定義下對于公式(3)～(7)的計(jì)算結(jié)果。

3.3 加入長鏈

3.1 節(jié)中所有公式均需考慮長鏈，比如輸入點(diǎn)帶有長鏈標(biāo)志，計(jì)算時在輸入點(diǎn)前方的所有長鏈點(diǎn)。那么均在3.2節(jié)的基礎(chǔ)上，將輸入點(diǎn)根據(jù)公式（1）轉(zhuǎn)化為長鏈終點(diǎn)，其不帶有長鏈標(biāo)志，轉(zhuǎn)化為不考慮長鏈的計(jì)算，最后再疊加長鏈的處理結(jié)果，涉及長鏈的計(jì)算公式(1)、(2)、(6)中的Σj∈b(i)LCLj，公式(7)中的Σj∈p(x)LCLj以及公式(8)均是根據(jù)設(shè)計(jì)的長鏈散列算法進(jìn)行實(shí)現(xiàn)。

因此，z(x)可以根據(jù)s(x)+f(x)進(jìn)行算法實(shí)現(xiàn)。

4 算法實(shí)現(xiàn)

據(jù)此進(jìn)行算法實(shí)現(xiàn)，程序設(shè)計(jì)邏輯如圖6 所示。

為完成上述程序邏輯，即根據(jù)公式（1）～（12）實(shí)現(xiàn)算法，需進(jìn)行功能實(shí)現(xiàn)，主要功能如表 4所示。

5 測試驗(yàn)證

本節(jié)根據(jù)程序?qū)崿F(xiàn)的線路數(shù)據(jù)算法設(shè)計(jì)案例進(jìn)行驗(yàn)證。設(shè)計(jì)案例的原則為考慮各種數(shù)據(jù)配置規(guī)則下每種線路分段、段內(nèi)遞增減情況，劃分等價類，每種等價類需要對邊界值設(shè)定案例，同時需綜合考慮長鏈點(diǎn)，以此檢驗(yàn)算法的邏輯是否正確。設(shè)定線路場景案例如表 5 所示。

對工程線路數(shù)據(jù)進(jìn)行場景劃分和遍歷，依次設(shè)置分段數(shù)為1 ～5，長鏈數(shù)為0 ～7。根據(jù)上述場景，分別設(shè)計(jì)數(shù)據(jù)以分段內(nèi)邏輯起點(diǎn)LSS，分段內(nèi)邏輯終點(diǎn)LSE，分段內(nèi)長鏈邏輯起點(diǎn)LFS，分段內(nèi)長鏈邏輯終點(diǎn)LFE為參考點(diǎn)，設(shè)計(jì)與基準(zhǔn)方向同向反向時，計(jì)算點(diǎn)與參考點(diǎn)重合，前方1 m，后方1 m 的案例，總共設(shè)計(jì)案例545 個。

測試結(jié)果正確，確認(rèn)算法功能符合預(yù)期。

表 4 算法實(shí)現(xiàn)功能列表Tab.4 List of functions implemented by the algorithm

表 5 測試案例場景Tab.5 Test case scenario

續(xù)表 5 測試案例場景

6 總結(jié)

本文主要通過分析目前各產(chǎn)品處理線路數(shù)據(jù)功能差異，針對線路數(shù)據(jù)的計(jì)算處理提出了基于距離的處理算法。本算法可以提供給數(shù)據(jù)配置用戶對于線路數(shù)據(jù)配置規(guī)則的制定，而不是由研發(fā)用戶固化到軟件中，使得數(shù)據(jù)配置靈活且統(tǒng)一。同時，算法對研發(fā)用戶屏蔽數(shù)據(jù)配置規(guī)則，使得線路數(shù)據(jù)計(jì)算根據(jù)用戶需求由給定的輸入點(diǎn)輸出距離線路邏輯數(shù)據(jù)起點(diǎn)的相對距離，獲取到與線路數(shù)據(jù)相關(guān)的大小比較、范圍判斷、距離計(jì)算的參數(shù)，從而解決各產(chǎn)品由于線路數(shù)據(jù)配置不同而導(dǎo)致的邏輯計(jì)算無法通用的問題，同時使得研發(fā)用戶不用考慮線路數(shù)據(jù)的處理而提高產(chǎn)品研發(fā)效率。

本算法未給出根據(jù)輸入點(diǎn)及距離輸入點(diǎn)的相對距離，返回對應(yīng)里程標(biāo)點(diǎn)的功能。同時本算法可以考慮提供給腳本語言的接口，這兩方面均可以應(yīng)用于產(chǎn)品自動化測試的預(yù)期結(jié)果計(jì)算的應(yīng)用，并作為對于后續(xù)工作的展望。