基于分布式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 設備互聯，通過多次執行列車初運行來進一步檢測算法。