基于分布式OID 的列车编组标识符生成算法

马伯臻，李常贤

（1 大连交通大学 电气信息工程学院，辽宁大连 116028；2 大连交通大学 轨道交通装备设计与制造技术国家地方联合工程研究中心，辽宁大连 116028）

以太网技术的高速发展，对列车编组技术提出了更高的要求。列车组之间经常需要动态编组（连挂和解编），导致列车通信网络拓扑发生变化。在这一过程中，编组的唯一标识符起着重要的作用。每一个编组在列车通信网络内都需要被特殊标记。每个编组对应唯一的标识符，便于列车管理系统监控列车编组过程。编组标识符的唯一性和有序性在列车拓扑发现过程中起着重要的作用，直接决定了拓扑发现结果的准确性。

目前，世界各国对于通用唯一标识符的研究过于分散化，主要集中在数据库分布式标识符领域，而在列车编组领域开展的研究较少。各大铁路设备研发公司采用的列车通用唯一标识符的算法无法自动计算，需要人为配置。这种情况无法保证编组标识符的唯一性。部分列车网络设备制造公司采用基于时间戳的标识符生成算法，这种算法过度依赖系统时钟，无法满足列车灵活编组的需求。

针对这种情况，提出了一种基于分布式OID的列车编组通用唯一标识符生成算法。该算法采用分布式OID 作为基础UUID，结合name-based UUID 算法和MD5［4］加密算法，保证了生成UUID 值的唯一性。采用有序的namespace，保证了生成UUID 值的有序性，便于列车灵活编组。在算法空间复杂度和安全性方面较之传统算法更具有优越性。

1 列车CstUUID

CstUUID（Consist Universally Unique Identifier）由RFC 4122 协议定义。CstUUID 是一个128 Bits的标识符。CstUUID 可以唯一标注Consist，保证了Consist 在列车范围内不会重复。

CstUUID 有序性和唯一性的目的在于找出拥有 最 小CstUUID 值 的Consist［1］。将 该Consist 的 顶节点ETBN 设备作为列车的Top Node。列车将指向Top Node 的方向定义为方向1（DIR 1），将相反方向定义为方向2（DIR 2），定义参考方向是为了对ETBN 设备进行编号。将Top Node 节点定义为1 号，其他ETBN number 沿着方向2 依次递增，如图1 所示。

图1 列车拓扑图

CstUUID 最终作用于ETB（Ethernet Train Backbone）拓扑发现过程。ETBN 通过TTDP 算法（Train Topology Discovery Protocol），获 取 到ETB干路上所有ETBN 设备的MAC 地址，按照CstUUID 从小到大进行排序，最终以Connectivity Table的形式保存。CstUUID 的有序性保证了ETBN 设备、组成网以及组成网子网可以有序编号，保证了逻辑拓扑的准确性。

IEC 61375 2-5 协议说明了CstUUID 是在UUID（Universally Unique IDentifier）的基础上生成的。UUID 长为 128 Bits 的通用唯一识别码，为便于表示，UUID 标准型式包含 32 个 16 进制数字，以“-”分为5 段，形式为 8-4-4-4-12 的 32 个字符，例如：

“f81d4fae-7dec-11d0-a765-00a0c91e6bf6”

详细结构如图2 所示。

图2 UUID 数据结构图

根据RFC 4122 协议定义，共有5 个版本的UUID。版本1 是基于时间的UUID，版本2 是基于DCE 安全服务的UUID，版本3 是基于MD5 加密算法的UUID，版本4 是基于随机数的UUID，版本5是基于SHA-1 加密算法的UUID。这5 类UUI 对于时间戳，节点和时钟序列的定义不同，因此对应有5 种不同的UUID 生成算法［2］。

2 现行CstUUID 算法分析

2.1 现行CstUUID 算法分类

版本1 是基于时间的UUID 算法，传统的Cst-UUID 生成算法是基于该算法产生的。此类UUID算法是通过计算当前时间戳、随机数和MAC 地址得到的。设备通过读取系统时间作为时间戳，MAC 地址视为节点ID。把随机数当作时钟序列来防止UUID 重复生成。这种算法暴露出了很大的问题。

版本2 是基于DCE 服务的UUID 算法，这类算法和基于时间的UUID 算法相同，但会把时间戳的前4 位置换为POSIX 的UID 或GID。

版本3 是基于名称的UUID 生成算法，该算法分为：MD5［4］加密的UUID 生成算法和版本5 基于SHA-1 加密的UUID 算法。这2 种算法都是对基础UUID 和命名空间字符进行加密来实现UUID的唯一性。

版本4 是基于随机数的UUID 生成算法，该类算法是通过随机数或伪随机数构成UUID，因此生成的UUID 不仅无序而且容易重复，具有很强的不确定性。

2.2 现行CstUUID 算法分析与优化

现行的CstUUID 生成算法主要基于版本1、版本3、版本5、版本4 的UUID 生成算法，我们通过对比这4 个版本的CstUUID 生成算法的特点与合理性，最终提出新的算法。

以开放式列车为例： ETB 干路上存在2 个ETBN 设 备A、B。其 中A 号ETBN 为Top Node，分别处于2 个不同的Consist 中。设A 号ETBN 设备的CstUUID 小于B 号ETBN 设备的CstUUID。在A 和B 之间插入新的ETBN 节点C 号ETBN，如图3 所示。

图3 插入新节点图

版本1 的UUID 算法是通过读取系统时钟来获取时间戳，C 号设备启动时间晚于B 号设备，那么在时间戳上C 号设备大于B 号设备。C 号设备最终生成的CstUUID 就会大于B 号设备的CstUUID，这与IEC 61375 2-5 协议相违背。

反证法证明：A 号设备在B 号设备之后启动，此时A 号设备的时间戳大于B 号设备的时间戳，反映到CstUUID 上就是A 号设备的CstUUID 大于B号设备的CstUUID。A 号设备此时如果被定义为Top Node 与IEC 61375 2-5 协议相违背。根据IEC 61375 2-5 协 议，Top Node 节 点 的CstUUID 应 该 是ETB 干路上最小的，那么使用版本1 的UUID 算法就无法达到协议的要求。

基于版本3 或版本5 UUID 的CstUUID 生成算法可以不需要在时间上对UUID 进行区分，通过命名空间中的名称就可以区分不同的CstUUID。由于采用MD5［4］或SHA-1 加密算法，保证了CstUUID 在时间和空间上的唯一性。由于不适用MAC地址，使得设备的安全性得到极大的提高。可以通过给相应的ETBN 设备分配不同的名称，来实现CstUUID 的由大到小的排列。通过有序的命名空间使得CstUUID 有序化。 这种算法符合IEC 61375 2-5 协议的要求，该类算法的技术难点在于选择基础UUID 和定义命名空间。

版本4 借助随机数或伪随机数的CstUUID 算法很简单，但实际上很少使用。使用该算法会造成C 号设备的CstUUID 随机生成，不能保证C 号设备 的CstUUID 和A号设备、B号设备的CstUUID 不发生重复，也无法保证CstUUID（A）

通过对比4 种不同的CstUUID 生成算法，CstUUID 生成算法采用基于命名空间的UUID 算法在唯一性和有序性方面较为合适。在CstUUID生成算法中较为核心的是基础UUID 的定义和命名空间的定义，这2 点我们采用分布式OID 作为基础UUID，保证了UUID 的唯一性。采用Cst_ID 组成的数组作为命名空间，Cst_ID 作为名称，这样保证了CstUUID 的有序性。这2 点将在下面的章节进行讨论。

3 基于分布式OID 的CstUUID 生成算法

针对传统UUID 生成算法无序性以及人工定义CstUUID 算法重复性的问题。我们提出了一种基于分布式OID 的CstUUID 生成算法，该算法的核心是基于名称的UUID 算法。依靠分布式OID构成基础UUID 值，Cst_ID 构成命名空间，接着对基础UUID 和命名空间进行MD5［4］加密，从而得到符合字典序的唯一CstUUID。

首先采用NTS 结构（Node Tree Structure）将列车网络信息分成不同的层次进行管理［3］。本地列车作为节点树的根节点（Root Node），记为（ITrn），列车网络中子网作为根节点的下一级子节点，记为（Cltr01…CltrNN）。具体结构如图4 所示。

图4 节点树结构图

在列车中使用（ITrn）.（Cltr）.（Cst）...... 格式来定义列车网络信息。列车Consist 的OID 值由IEC 61375 2-5 协议提供。初始的OID 无法直接使用，这里我采用OID 编码规则对OID 编码进行转换。

设OID 格式为“x.x.xxx.xxxx.xx.xx……”。前2 部分如果定义为x. y，那么它们将合成一个字40*x + y，其余部分单独作为一个字节进行编码。OID 保存在SNMP 协议定义的MIB 数据库中［4］。

将分布式OID 的CstUUID 结合Cst_ID 代入到MD5［4］算法中进行降重加密。首先需要对信息进行填充，使其字节长度对512 求余等于448。这样做的原因是为满足算法对信息长度的要求。同时，还需定义4 个链接变量（Chaining Variable），分别为：A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210。将上面4 个链接变量复制：A复制到a，B复制到b，C复制到c，D复制到d。主循环对a、b、c和d进行非线性函数运算为式（1）：

将计算之后的A，B，C，D分别加上a，b，c，d，最后得到的新的A，B，C，D的值就是输出结果。基于分布式OID 的CstUUID 生成算法状态机如图5、图6 所示。

图5 基于分布式OID 的CstUUID 生成状态机

图6 基于分布式OID 的CstUUID 生成算法流程图

4 算法优越性与合理性分析

4.1 合理性分析

假 设 现 在 有3 个ETBN 设 备：A 号ETBN 设备，B 号ETBN 设 备，C 号ETBN 设 备。A 号 和B 号ETBN 连接在ETB 干路上。在列车初运行开始前，由于没有执行列车拓扑发现算法（TTDP），A号和B 号的CstUUID 均为出厂时设置。出厂时设置可采用基于时间的UUID 算法，只需要保证A 号ETBN 设 备 和B 号ETBN 设 备 的CstUUID 不 同 即可。拓扑图如图7 所示。

图7 算法测试拓扑图

A 号ETBN 设 备 和B 号ETBN 设 备 连 接 到ETB 上之后，执行列车初运行。 SNMP 协议在列车初运行过程中实现。 写入SNMP 协议栈到ETBN 设备，在ETBN 工作时，根据SNMP 协议，在ETBN 芯片上开发一个内存区域作为MIB 数据库，MIB 内部保存了进程或通信数据的OID。ETBN读取OID 值，通过OID 编码规则将OID 值转化为基础UUID 值。ETBN 设备读取自定义的Cst_ID值，将Cst_ID 保存在命名空间中。基础UUID 和Cst_ID 代入到基于名称的UUID 算法中，通过MD5［4］加密生成最终的CstUUID。初运行过程继续进行其他设置。Cst_ID 构成的命名空间，实现了在字典序上CstUUID 的有序性。通过以上过程，A号设备和C 号设备可生成对应的CstUUID。如果A 号设备的Cst_ID 小于B 号设备的Cst_ID，那么根据IEC 61375 2-5 协议可知A 号ETBN 是头车，A号设备的CstUUID 在字典序上小于B 号设备的CstUUID。

通过将执行程序烧录到XILINX ZYNQ7000 开发平台验证，如图8 所示。

图8 列车拓扑发现中的CstUUID

其中，A 号ETBN 的CstUUID：

“31000000-0000-0000-0000-000000000000”

B 号ETBN 的CstUUID：

“32000000-0000-0000-0000-000000000000”

在字典序上A 号ETBN 的CstUUID 小于B 号ETBN 设备的CstUUID。试验结果与协议完全符合。

当设备C 插入到ETB 干路上时，根据C 号设备的Cst_ID 对C 设备进行编组的划分。根据设计的算法，如果C 号设备的Cst_ID 与A 号设备或B 号设备的Cst_ID 相等，那么他们的CstUUID 也会相等，说明2 个ETBN 设备同处一个Consist 内。通过实际设备验证，结果符合IEC 61375 2-5 协议定义。而传统基于时间的CstUUID 生成算法在上述情况下运行时，由于时间戳递增的性质，势必会有C 号设备CstUUID 大于B 号设备的CstUUID，这与IEC 61375 2-5 协议定义相违背。比较可知所提出的算法实际上较为合理。拓扑图如图9 所示。

图9 非冗余同编组拓扑图

4.2 空间复杂度分析

提出的CstUUID 生成算法的空间复杂度为基础UUID 和Cst_ID 所占用的存储空间，经计算最小使用128 Bits 存储空间即可满足需求。传统基于时间的CstUUID 生成算法的空间复杂度需要考虑MAC 地址占用的存储空间和系统时钟占用的存储空间，其值大于128 Bits。因此，在空间复杂度上所研究的算法具有优越性。

从安全角度讲，所提出的算法采用MD5［4］加密算法，而传统基于时间的CstUUID 生成算法并不具备加密算法，MAC 地址和时间戳直接暴露于用户，用户可以通过解码很轻易地读取设备的MAC 和时间戳，安全系数较低。

通过以上分析，文中的算法不仅在原理上较为契合IEC 61375 2-5 协议，并且在空间复杂度和安全性方面具有良好的性能。

5 结 论

列车编组是列车的关键技术之一，CstUUID 在列车编组过程中起着重要的作用。文中讨论了列车编组的2 种模式，探讨了5 种UUID 生成算法，引出了传统的CstUUID 生成算法—基于时间的CstUUID 生成算法。传统CstUUID 生成算法采用时间戳，MAC 地址和时钟序列来构成CstUUID。这种算法过分依赖时间戳，无法应对ETBN 节点插入的情况。由于使用MAC 地址而没有采用加密算法，安全性方面存在问题。针对这些问题，我们提出了一种基于分布式OID 的CstUUID 生成算法。文中提出的算法使用由Cst_ID 构成的有序的命名空间，由分布式OID 构成的基础UUID 以及MD5［4］加密算法，不仅在原理上符合IEC 61375 2-5 定义的列车编组过程，并且提高了CstUUID 生成过程的安全性，保证了生成的CstUUID 的有序性。在空间复杂度和安全性方面具有优越性。

在未来的工作中，将会逐步优化算法，降低算法的时间复杂度，使之更契合列车初运行算法。并将开发平台与ETBN 设备互联，通过多次执行列车初运行来进一步检测算法。