基于距离的线路数据处理算法

郁文斌

（北京全路通信信号研究设计院集团有限公司，北京 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 总结

本文主要通过分析目前各产品处理线路数据功能差异，针对线路数据的计算处理提出了基于距离的处理算法。本算法可以提供给数据配置用户对于线路数据配置规则的制定，而不是由研发用户固化到软件中，使得数据配置灵活且统一。同时，算法对研发用户屏蔽数据配置规则，使得线路数据计算根据用户需求由给定的输入点输出距离线路逻辑数据起点的相对距离，获取到与线路数据相关的大小比较、范围判断、距离计算的参数，从而解决各产品由于线路数据配置不同而导致的逻辑计算无法通用的问题，同时使得研发用户不用考虑线路数据的处理而提高产品研发效率。

本算法未给出根据输入点及距离输入点的相对距离，返回对应里程标点的功能。同时本算法可以考虑提供给脚本语言的接口，这两方面均可以应用于产品自动化测试的预期结果计算的应用，并作为对于后续工作的展望。