基于距離的線路數據處理算法

郁文斌

（北京全路通信信號研究設計院集團有限公司，北京 100070）

1 概述

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

2 線路數據介紹

根據目前線路數據設計規范[5-6]，在鐵路信號設備運行需要以勘察的線路數據為基礎進行規范設計后，根據中國國家鐵路集團有限公司對于線路數據管理的最新規范[7]對列控數據進行管理并發布，各生產單位據此進行信號設備所需的線路數據計算，進行信號的控制，以保障行車運營的安全。

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

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

2.1 問題的提出

針對上述討論，線路數據的處理是高鐵領域地面信號軟件的基礎設計，需要解決的問題如下。

1）數據結構設計：如果線路數據的數據結構設計合理，線路數據的配置冗余性低，配置項內容少。

2）統一規范設計：如果基于線路數據的計算方法封裝合理，僅提供用戶輸入到計算結果的服務，則線路數據的邏輯處理極大程度上能夠按需通用，降低上層應用的邏輯設計復雜性。

一條線路上，指定參考方向后，無論與參考方向同向還是反向，均是由若干分段順序構成，每個分段內對應唯一里程標系、起點和終點，并存在長鏈。若要進行計算，那么需要解決兩個問題。

1）數據配置：分段信息，即線路分段順序；段內配置：即段內里程標系起點、終點的配置；長鏈配置。

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

2.2 數據結構設計

本節對于線路數據設計數據結構，工程規定的正向線路方向，即線路基準方向，也是其他方向定義的基準或者參考方向。數據配置方向（以下簡稱UCDIR），其涉及到分段配置方向，段內數據配置方向。用戶計算方向（以下簡稱USDIR），也就是運行的實際方向。無論在UCDIR還是USDIR，分段內里程標均有遞增遞減趨勢。線路基準方向的線路第一個分段為BLS，最后一個分段為BLE，分段內起始里程標為BSS，終點里程標為BSE。

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

根據上述定義，對應關系如下，如表 1、2 所示。

表 1 基礎線路數據配置對應關系表Tab.1 Correspondence table of basic line data configuration

表 2 長鏈線路數據對應關系表Tab.2 Correspondence table of long chain line data

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

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

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

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

表 3 數據配置距離Tab.3 Data configuration distance

研發用戶可以根據表 1、2 建立數據配置與計算所需參數的邏輯關系，設定算法，獲取所需的邏輯參數。以下對算法進行設計。

3 基于距離的算法

如果提供一種算法，對于任意輸入點，根據用戶指定的方向USDIR，輸出其距離USDIR方向上線路邏輯起點的絕對距離，用戶進行計算時，就可以進行簡單的數學運算，得到用戶所需的應用結果。

根據表 1、2 的分析得知，可以制定如下規則：

1) 根據數據配置規則，建立計算線路參數與數據配置的邏輯關系；

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

3) 根據長鏈的處理結果，參考散列表原理[8],根據長鏈定義及其特點，參考散列的應用[9]設計針對長鏈標志和數據的散列算法，計算前方所有段的絕對距離s(x)；

4) 計算其距離段內邏輯起點的相對距離f(x)；

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

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

根據上述規則分別提出解決方法如下。

3.1 段內處理

設M 為長鏈最大配置數，N為最大分段數，x為輸入點，定義公式：

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

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

3.2 不考慮長鏈

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

因此，在數據配置的基礎上，首先建立起數據配置與邏輯參數之間的關系，才能實現公式。對研發用戶屏蔽數據配置，根據需求獲取所需的邏輯參數。

根據表 1 ～ 3，線路段間關系如圖 2、 3 所示。

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

那么對于公式(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

根據表 1 ～ 3，段內關系如圖 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個段內，可得到公式：

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

3.3 加入長鏈

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

因此，z(x)可以根據s(x)+f(x)進行算法實現。

4 算法實現

據此進行算法實現，程序設計邏輯如圖6 所示。

為完成上述程序邏輯，即根據公式（1）～（12）實現算法，需進行功能實現，主要功能如表 4所示。

5 測試驗證

本節根據程序實現的線路數據算法設計案例進行驗證。設計案例的原則為考慮各種數據配置規則下每種線路分段、段內遞增減情況，劃分等價類，每種等價類需要對邊界值設定案例，同時需綜合考慮長鏈點，以此檢驗算法的邏輯是否正確。設定線路場景案例如表 5 所示。

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

測試結果正確，確認算法功能符合預期。

表 4 算法實現功能列表Tab.4 List of functions implemented by the algorithm

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

續表 5 測試案例場景

6 總結

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

本算法未給出根據輸入點及距離輸入點的相對距離，返回對應里程標點的功能。同時本算法可以考慮提供給腳本語言的接口，這兩方面均可以應用于產品自動化測試的預期結果計算的應用，并作為對于后續工作的展望。