基于分布式OID 的列車(chē)編組標(biāo)識(shí)符生成算法

馬伯臻，李常賢

（1 大連交通大學(xué) 電氣信息工程學(xué)院，遼寧大連 116028；2 大連交通大學(xué) 軌道交通裝備設(shè)計(jì)與制造技術(shù)國(guó)家地方聯(lián)合工程研究中心，遼寧大連 116028）

以太網(wǎng)技術(shù)的高速發(fā)展，對(duì)列車(chē)編組技術(shù)提出了更高的要求。列車(chē)組之間經(jīng)常需要?jiǎng)討B(tài)編組（連掛和解編），導(dǎo)致列車(chē)通信網(wǎng)絡(luò)拓?fù)浒l(fā)生變化。在這一過(guò)程中，編組的唯一標(biāo)識(shí)符起著重要的作用。每一個(gè)編組在列車(chē)通信網(wǎng)絡(luò)內(nèi)都需要被特殊標(biāo)記。每個(gè)編組對(duì)應(yīng)唯一的標(biāo)識(shí)符，便于列車(chē)管理系統(tǒng)監(jiān)控列車(chē)編組過(guò)程。編組標(biāo)識(shí)符的唯一性和有序性在列車(chē)拓?fù)浒l(fā)現(xiàn)過(guò)程中起著重要的作用，直接決定了拓?fù)浒l(fā)現(xiàn)結(jié)果的準(zhǔn)確性。

目前，世界各國(guó)對(duì)于通用唯一標(biāo)識(shí)符的研究過(guò)于分散化，主要集中在數(shù)據(jù)庫(kù)分布式標(biāo)識(shí)符領(lǐng)域，而在列車(chē)編組領(lǐng)域開(kāi)展的研究較少。各大鐵路設(shè)備研發(fā)公司采用的列車(chē)通用唯一標(biāo)識(shí)符的算法無(wú)法自動(dòng)計(jì)算，需要人為配置。這種情況無(wú)法保證編組標(biāo)識(shí)符的唯一性。部分列車(chē)網(wǎng)絡(luò)設(shè)備制造公司采用基于時(shí)間戳的標(biāo)識(shí)符生成算法，這種算法過(guò)度依賴系統(tǒng)時(shí)鐘，無(wú)法滿足列車(chē)靈活編組的需求。

針對(duì)這種情況，提出了一種基于分布式OID的列車(chē)編組通用唯一標(biāo)識(shí)符生成算法。該算法采用分布式OID 作為基礎(chǔ)UUID，結(jié)合name-based UUID 算法和MD5［4］加密算法，保證了生成UUID 值的唯一性。采用有序的namespace，保證了生成UUID 值的有序性，便于列車(chē)靈活編組。在算法空間復(fù)雜度和安全性方面較之傳統(tǒng)算法更具有優(yōu)越性。

1 列車(chē)CstUUID

CstUUID（Consist Universally Unique Identifier）由RFC 4122 協(xié)議定義。CstUUID 是一個(gè)128 Bits的標(biāo)識(shí)符。CstUUID 可以唯一標(biāo)注Consist，保證了Consist 在列車(chē)范圍內(nèi)不會(huì)重復(fù)。

CstUUID 有序性和唯一性的目的在于找出擁有 最 小CstUUID 值 的Consist［1］。將 該Consist 的 頂節(jié)點(diǎn)ETBN 設(shè)備作為列車(chē)的Top Node。列車(chē)將指向Top Node 的方向定義為方向1（DIR 1），將相反方向定義為方向2（DIR 2），定義參考方向是為了對(duì)ETBN 設(shè)備進(jìn)行編號(hào)。將Top Node 節(jié)點(diǎn)定義為1 號(hào)，其他ETBN number 沿著方向2 依次遞增，如圖1 所示。

圖1 列車(chē)拓?fù)鋱D

CstUUID 最終作用于ETB（Ethernet Train Backbone）拓?fù)浒l(fā)現(xiàn)過(guò)程。ETBN 通過(guò)TTDP 算法（Train Topology Discovery Protocol），獲 取 到ETB干路上所有ETBN 設(shè)備的MAC 地址，按照CstUUID 從小到大進(jìn)行排序，最終以Connectivity Table的形式保存。CstUUID 的有序性保證了ETBN 設(shè)備、組成網(wǎng)以及組成網(wǎng)子網(wǎng)可以有序編號(hào)，保證了邏輯拓?fù)涞臏?zhǔn)確性。

IEC 61375 2-5 協(xié)議說(shuō)明了CstUUID 是在UUID（Universally Unique IDentifier）的基礎(chǔ)上生成的。UUID 長(zhǎng)為 128 Bits 的通用唯一識(shí)別碼，為便于表示，UUID 標(biāo)準(zhǔn)型式包含 32 個(gè) 16 進(jìn)制數(shù)字，以“-”分為5 段，形式為 8-4-4-4-12 的 32 個(gè)字符，例如：

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

詳細(xì)結(jié)構(gòu)如圖2 所示。

圖2 UUID 數(shù)據(jù)結(jié)構(gòu)圖

根據(jù)RFC 4122 協(xié)議定義，共有5 個(gè)版本的UUID。版本1 是基于時(shí)間的UUID，版本2 是基于DCE 安全服務(wù)的UUID，版本3 是基于MD5 加密算法的UUID，版本4 是基于隨機(jī)數(shù)的UUID，版本5是基于SHA-1 加密算法的UUID。這5 類(lèi)UUI 對(duì)于時(shí)間戳，節(jié)點(diǎn)和時(shí)鐘序列的定義不同，因此對(duì)應(yīng)有5 種不同的UUID 生成算法［2］。

2 現(xiàn)行CstUUID 算法分析

2.1 現(xiàn)行CstUUID 算法分類(lèi)

版本1 是基于時(shí)間的UUID 算法，傳統(tǒng)的Cst-UUID 生成算法是基于該算法產(chǎn)生的。此類(lèi)UUID算法是通過(guò)計(jì)算當(dāng)前時(shí)間戳、隨機(jī)數(shù)和MAC 地址得到的。設(shè)備通過(guò)讀取系統(tǒng)時(shí)間作為時(shí)間戳，MAC 地址視為節(jié)點(diǎn)ID。把隨機(jī)數(shù)當(dāng)作時(shí)鐘序列來(lái)防止UUID 重復(fù)生成。這種算法暴露出了很大的問(wèn)題。

版本2 是基于DCE 服務(wù)的UUID 算法，這類(lèi)算法和基于時(shí)間的UUID 算法相同，但會(huì)把時(shí)間戳的前4 位置換為POSIX 的UID 或GID。

版本3 是基于名稱(chēng)的UUID 生成算法，該算法分為：MD5［4］加密的UUID 生成算法和版本5 基于SHA-1 加密的UUID 算法。這2 種算法都是對(duì)基礎(chǔ)UUID 和命名空間字符進(jìn)行加密來(lái)實(shí)現(xiàn)UUID的唯一性。

版本4 是基于隨機(jī)數(shù)的UUID 生成算法，該類(lèi)算法是通過(guò)隨機(jī)數(shù)或偽隨機(jī)數(shù)構(gòu)成UUID，因此生成的UUID 不僅無(wú)序而且容易重復(fù)，具有很強(qiáng)的不確定性。

2.2 現(xiàn)行CstUUID 算法分析與優(yōu)化

現(xiàn)行的CstUUID 生成算法主要基于版本1、版本3、版本5、版本4 的UUID 生成算法，我們通過(guò)對(duì)比這4 個(gè)版本的CstUUID 生成算法的特點(diǎn)與合理性，最終提出新的算法。

以開(kāi)放式列車(chē)為例： ETB 干路上存在2 個(gè)ETBN 設(shè) 備A、B。其 中A 號(hào)ETBN 為T(mén)op Node，分別處于2 個(gè)不同的Consist 中。設(shè)A 號(hào)ETBN 設(shè)備的CstUUID 小于B 號(hào)ETBN 設(shè)備的CstUUID。在A 和B 之間插入新的ETBN 節(jié)點(diǎn)C 號(hào)ETBN，如圖3 所示。

圖3 插入新節(jié)點(diǎn)圖

版本1 的UUID 算法是通過(guò)讀取系統(tǒng)時(shí)鐘來(lái)獲取時(shí)間戳，C 號(hào)設(shè)備啟動(dòng)時(shí)間晚于B 號(hào)設(shè)備，那么在時(shí)間戳上C 號(hào)設(shè)備大于B 號(hào)設(shè)備。C 號(hào)設(shè)備最終生成的CstUUID 就會(huì)大于B 號(hào)設(shè)備的CstUUID，這與IEC 61375 2-5 協(xié)議相違背。

反證法證明：A 號(hào)設(shè)備在B 號(hào)設(shè)備之后啟動(dòng)，此時(shí)A 號(hào)設(shè)備的時(shí)間戳大于B 號(hào)設(shè)備的時(shí)間戳，反映到CstUUID 上就是A 號(hào)設(shè)備的CstUUID 大于B號(hào)設(shè)備的CstUUID。A 號(hào)設(shè)備此時(shí)如果被定義為T(mén)op Node 與IEC 61375 2-5 協(xié)議相違背。根據(jù)IEC 61375 2-5 協(xié) 議，Top Node 節(jié) 點(diǎn) 的CstUUID 應(yīng) 該 是ETB 干路上最小的，那么使用版本1 的UUID 算法就無(wú)法達(dá)到協(xié)議的要求。

基于版本3 或版本5 UUID 的CstUUID 生成算法可以不需要在時(shí)間上對(duì)UUID 進(jìn)行區(qū)分，通過(guò)命名空間中的名稱(chēng)就可以區(qū)分不同的CstUUID。由于采用MD5［4］或SHA-1 加密算法，保證了CstUUID 在時(shí)間和空間上的唯一性。由于不適用MAC地址，使得設(shè)備的安全性得到極大的提高?？梢酝ㄟ^(guò)給相應(yīng)的ETBN 設(shè)備分配不同的名稱(chēng)，來(lái)實(shí)現(xiàn)CstUUID 的由大到小的排列。通過(guò)有序的命名空間使得CstUUID 有序化。 這種算法符合IEC 61375 2-5 協(xié)議的要求，該類(lèi)算法的技術(shù)難點(diǎn)在于選擇基礎(chǔ)UUID 和定義命名空間。

版本4 借助隨機(jī)數(shù)或偽隨機(jī)數(shù)的CstUUID 算法很簡(jiǎn)單，但實(shí)際上很少使用。使用該算法會(huì)造成C 號(hào)設(shè)備的CstUUID 隨機(jī)生成，不能保證C 號(hào)設(shè)備 的CstUUID 和A號(hào)設(shè)備、B號(hào)設(shè)備的CstUUID 不發(fā)生重復(fù)，也無(wú)法保證CstUUID（A）

通過(guò)對(duì)比4 種不同的CstUUID 生成算法，CstUUID 生成算法采用基于命名空間的UUID 算法在唯一性和有序性方面較為合適。在CstUUID生成算法中較為核心的是基礎(chǔ)UUID 的定義和命名空間的定義，這2 點(diǎn)我們采用分布式OID 作為基礎(chǔ)UUID，保證了UUID 的唯一性。采用Cst_ID 組成的數(shù)組作為命名空間，Cst_ID 作為名稱(chēng)，這樣保證了CstUUID 的有序性。這2 點(diǎn)將在下面的章節(jié)進(jìn)行討論。

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

針對(duì)傳統(tǒng)UUID 生成算法無(wú)序性以及人工定義CstUUID 算法重復(fù)性的問(wèn)題。我們提出了一種基于分布式OID 的CstUUID 生成算法，該算法的核心是基于名稱(chēng)的UUID 算法。依靠分布式OID構(gòu)成基礎(chǔ)UUID 值，Cst_ID 構(gòu)成命名空間，接著對(duì)基礎(chǔ)UUID 和命名空間進(jìn)行MD5［4］加密，從而得到符合字典序的唯一CstUUID。

首先采用NTS 結(jié)構(gòu)（Node Tree Structure）將列車(chē)網(wǎng)絡(luò)信息分成不同的層次進(jìn)行管理［3］。本地列車(chē)作為節(jié)點(diǎn)樹(shù)的根節(jié)點(diǎn)（Root Node），記為（ITrn），列車(chē)網(wǎng)絡(luò)中子網(wǎng)作為根節(jié)點(diǎn)的下一級(jí)子節(jié)點(diǎn)，記為（Cltr01…CltrNN）。具體結(jié)構(gòu)如圖4 所示。

圖4 節(jié)點(diǎn)樹(shù)結(jié)構(gòu)圖

在列車(chē)中使用（ITrn）.（Cltr）.（Cst）...... 格式來(lái)定義列車(chē)網(wǎng)絡(luò)信息。列車(chē)Consist 的OID 值由IEC 61375 2-5 協(xié)議提供。初始的OID 無(wú)法直接使用，這里我采用OID 編碼規(guī)則對(duì)OID 編碼進(jìn)行轉(zhuǎn)換。

設(shè)OID 格式為“x.x.xxx.xxxx.xx.xx……”。前2 部分如果定義為x. y，那么它們將合成一個(gè)字40*x + y，其余部分單獨(dú)作為一個(gè)字節(jié)進(jìn)行編碼。OID 保存在SNMP 協(xié)議定義的MIB 數(shù)據(jù)庫(kù)中［4］。

將分布式OID 的CstUUID 結(jié)合Cst_ID 代入到MD5［4］算法中進(jìn)行降重加密。首先需要對(duì)信息進(jìn)行填充，使其字節(jié)長(zhǎng)度對(duì)512 求余等于448。這樣做的原因是為滿足算法對(duì)信息長(zhǎng)度的要求。同時(shí)，還需定義4 個(gè)鏈接變量（Chaining Variable），分別為：A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210。將上面4 個(gè)鏈接變量復(fù)制：A復(fù)制到a，B復(fù)制到b，C復(fù)制到c，D復(fù)制到d。主循環(huán)對(duì)a、b、c和d進(jìn)行非線性函數(shù)運(yùn)算為式（1）：

將計(jì)算之后的A，B，C，D分別加上a，b，c，d，最后得到的新的A，B，C，D的值就是輸出結(jié)果?；诜植际絆ID 的CstUUID 生成算法狀態(tài)機(jī)如圖5、圖6 所示。

圖5 基于分布式OID 的CstUUID 生成狀態(tài)機(jī)

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

4 算法優(yōu)越性與合理性分析

4.1 合理性分析

假 設(shè) 現(xiàn) 在 有3 個(gè)ETBN 設(shè) 備：A 號(hào)ETBN 設(shè)備，B 號(hào)ETBN 設(shè) 備，C 號(hào)ETBN 設(shè) 備。A 號(hào) 和B 號(hào)ETBN 連接在ETB 干路上。在列車(chē)初運(yùn)行開(kāi)始前，由于沒(méi)有執(zhí)行列車(chē)拓?fù)浒l(fā)現(xiàn)算法（TTDP），A號(hào)和B 號(hào)的CstUUID 均為出廠時(shí)設(shè)置。出廠時(shí)設(shè)置可采用基于時(shí)間的UUID 算法，只需要保證A 號(hào)ETBN 設(shè) 備 和B 號(hào)ETBN 設(shè) 備 的CstUUID 不 同 即可。拓?fù)鋱D如圖7 所示。

圖7 算法測(cè)試拓?fù)鋱D

A 號(hào)ETBN 設(shè) 備 和B 號(hào)ETBN 設(shè) 備 連 接 到ETB 上之后，執(zhí)行列車(chē)初運(yùn)行。 SNMP 協(xié)議在列車(chē)初運(yùn)行過(guò)程中實(shí)現(xiàn)。 寫(xiě)入SNMP 協(xié)議棧到ETBN 設(shè)備，在ETBN 工作時(shí)，根據(jù)SNMP 協(xié)議，在ETBN 芯片上開(kāi)發(fā)一個(gè)內(nèi)存區(qū)域作為MIB 數(shù)據(jù)庫(kù)，MIB 內(nèi)部保存了進(jìn)程或通信數(shù)據(jù)的OID。ETBN讀取OID 值，通過(guò)OID 編碼規(guī)則將OID 值轉(zhuǎn)化為基礎(chǔ)UUID 值。ETBN 設(shè)備讀取自定義的Cst_ID值，將Cst_ID 保存在命名空間中。基礎(chǔ)UUID 和Cst_ID 代入到基于名稱(chēng)的UUID 算法中，通過(guò)MD5［4］加密生成最終的CstUUID。初運(yùn)行過(guò)程繼續(xù)進(jìn)行其他設(shè)置。Cst_ID 構(gòu)成的命名空間，實(shí)現(xiàn)了在字典序上CstUUID 的有序性。通過(guò)以上過(guò)程，A號(hào)設(shè)備和C 號(hào)設(shè)備可生成對(duì)應(yīng)的CstUUID。如果A 號(hào)設(shè)備的Cst_ID 小于B 號(hào)設(shè)備的Cst_ID，那么根據(jù)IEC 61375 2-5 協(xié)議可知A 號(hào)ETBN 是頭車(chē)，A號(hào)設(shè)備的CstUUID 在字典序上小于B 號(hào)設(shè)備的CstUUID。

通過(guò)將執(zhí)行程序燒錄到XILINX ZYNQ7000 開(kāi)發(fā)平臺(tái)驗(yàn)證，如圖8 所示。

圖8 列車(chē)拓?fù)浒l(fā)現(xiàn)中的CstUUID

其中，A 號(hào)ETBN 的CstUUID：

“31000000-0000-0000-0000-000000000000”

B 號(hào)ETBN 的CstUUID：

“32000000-0000-0000-0000-000000000000”

在字典序上A 號(hào)ETBN 的CstUUID 小于B 號(hào)ETBN 設(shè)備的CstUUID。試驗(yàn)結(jié)果與協(xié)議完全符合。

當(dāng)設(shè)備C 插入到ETB 干路上時(shí)，根據(jù)C 號(hào)設(shè)備的Cst_ID 對(duì)C 設(shè)備進(jìn)行編組的劃分。根據(jù)設(shè)計(jì)的算法，如果C 號(hào)設(shè)備的Cst_ID 與A 號(hào)設(shè)備或B 號(hào)設(shè)備的Cst_ID 相等，那么他們的CstUUID 也會(huì)相等，說(shuō)明2 個(gè)ETBN 設(shè)備同處一個(gè)Consist 內(nèi)。通過(guò)實(shí)際設(shè)備驗(yàn)證，結(jié)果符合IEC 61375 2-5 協(xié)議定義。而傳統(tǒng)基于時(shí)間的CstUUID 生成算法在上述情況下運(yùn)行時(shí)，由于時(shí)間戳遞增的性質(zhì)，勢(shì)必會(huì)有C 號(hào)設(shè)備CstUUID 大于B 號(hào)設(shè)備的CstUUID，這與IEC 61375 2-5 協(xié)議定義相違背。比較可知所提出的算法實(shí)際上較為合理。拓?fù)鋱D如圖9 所示。

圖9 非冗余同編組拓?fù)鋱D

4.2 空間復(fù)雜度分析

提出的CstUUID 生成算法的空間復(fù)雜度為基礎(chǔ)UUID 和Cst_ID 所占用的存儲(chǔ)空間，經(jīng)計(jì)算最小使用128 Bits 存儲(chǔ)空間即可滿足需求。傳統(tǒng)基于時(shí)間的CstUUID 生成算法的空間復(fù)雜度需要考慮MAC 地址占用的存儲(chǔ)空間和系統(tǒng)時(shí)鐘占用的存儲(chǔ)空間，其值大于128 Bits。因此，在空間復(fù)雜度上所研究的算法具有優(yōu)越性。

從安全角度講，所提出的算法采用MD5［4］加密算法，而傳統(tǒng)基于時(shí)間的CstUUID 生成算法并不具備加密算法，MAC 地址和時(shí)間戳直接暴露于用戶，用戶可以通過(guò)解碼很輕易地讀取設(shè)備的MAC 和時(shí)間戳，安全系數(shù)較低。

通過(guò)以上分析，文中的算法不僅在原理上較為契合IEC 61375 2-5 協(xié)議，并且在空間復(fù)雜度和安全性方面具有良好的性能。

5 結(jié) 論

列車(chē)編組是列車(chē)的關(guān)鍵技術(shù)之一，CstUUID 在列車(chē)編組過(guò)程中起著重要的作用。文中討論了列車(chē)編組的2 種模式，探討了5 種UUID 生成算法，引出了傳統(tǒng)的CstUUID 生成算法—基于時(shí)間的CstUUID 生成算法。傳統(tǒng)CstUUID 生成算法采用時(shí)間戳，MAC 地址和時(shí)鐘序列來(lái)構(gòu)成CstUUID。這種算法過(guò)分依賴時(shí)間戳，無(wú)法應(yīng)對(duì)ETBN 節(jié)點(diǎn)插入的情況。由于使用MAC 地址而沒(méi)有采用加密算法，安全性方面存在問(wèn)題。針對(duì)這些問(wèn)題，我們提出了一種基于分布式OID 的CstUUID 生成算法。文中提出的算法使用由Cst_ID 構(gòu)成的有序的命名空間，由分布式OID 構(gòu)成的基礎(chǔ)UUID 以及MD5［4］加密算法，不僅在原理上符合IEC 61375 2-5 定義的列車(chē)編組過(guò)程，并且提高了CstUUID 生成過(guò)程的安全性，保證了生成的CstUUID 的有序性。在空間復(fù)雜度和安全性方面具有優(yōu)越性。

在未來(lái)的工作中，將會(huì)逐步優(yōu)化算法，降低算法的時(shí)間復(fù)雜度，使之更契合列車(chē)初運(yùn)行算法。并將開(kāi)發(fā)平臺(tái)與ETBN 設(shè)備互聯(lián)，通過(guò)多次執(zhí)行列車(chē)初運(yùn)行來(lái)進(jìn)一步檢測(cè)算法。