分布式輸送系統節點路由控制算法設計＊

同濟大學機械與能源工程學院 上海 201804

0 引言

在工業生產中，各類輸送系統對生產效率的提高起著至關重要的作用。自動化倉儲系統，物流配送中心和柔性制造系統等環境中的輸送系統，具有由多通道及交叉節點構成的網絡結構。隨著工業自動化水平的上升，系統呈現大規模化和復雜化的趨勢，控制難度越來越大。

以往對這類輸送系統的控制多采用基于全局信息的集中式控制。由于輸送系統隨著規模的擴大控制器處理的信息量呈指數增長，在復雜的輸送系統中，繼續采用集中式策略將難以實現實時有效的控制。

借鑒計算機網絡的分布式控制思想，提出基于節點主動控制的分布式輸送系統模型[1]。與傳統的輸送系統相比，它的不同之處在于其控制主體為分布在網絡中的節點而非中央計算機。與計算機網絡相似，系統通過多個節點的動態路徑選擇來為輸送實體規劃最優路徑。

模型的控制算法包括兩部分：最優路徑算法和防碰撞、沖突機制。

分布式網絡最優路徑規劃問題作為網絡關鍵問題之一，很多學者投入研究，提出了一系列相關協議。陳文平等[2]提出基于距離矢量的多下一跳路由信息協議，將最優路徑上較大流量很好的分散，從而降低網絡擁塞的風險。胡日新等[3]通過對RIP協議進行改進克服了原協議“壞消息傳得慢”的缺點。

防碰撞、沖突機制是運輸系統控制的關鍵問題之一，研究成果豐富。Rajotia S等[4]通過在網絡系統中節點和弧上建立時間窗，指示它們的占用情況，并在這些時間窗的約束下規劃最優路徑以避免碰撞。Kim 和Tanchoco[5]對以上算法進行了優化，提出了短視策略，即某一時刻只考慮單一實體最佳運行路徑，并考慮先前所有的時間窗設定，以此為依據選擇下一條路徑，降低了計算難度。

本文首先簡述節點主動控制輸送系統模型組成及運行原理，通過分析模型確定算法要達到的要求。然后提出本文設計的分布式控制算法。最后，通過面向對象仿真建模對算法性能進行驗證。

1 分布式輸送系統模型

1.1 模型組成

如圖1所示，模型是一個網絡結構，主要包括節點、弧、輸送實體、中央管理機等。

圖1 分布式輸送系統控制模型

1）節點（node） 節點是本模型的核心組成，它不僅是作為多條弧交匯的物理存在，同時還是整個模型的控制主體。節點上的嵌入式設備集成了通信模塊、RFID讀寫設備和控制器。使得節點能與其他節點和中央管理機進行信息交互，同時能讀取輸送實體上電子標簽的信息，另外，它還能控制本節點和相連弧的動作。

2）弧（arc） 起著連接節點，傳輸實體的作用。在本模型中，弧均為雙向弧（Bi-directional arc）,即在同一條弧中，實體的運輸方向可以不同。

3）輸送實體 指輸送系統輸送的對象，比如倉儲系統的貨物，生產線上的在制品等。本文輸送系統模型中的運輸實體貼有RFID電子標簽。

4）中央管理機 負責模型中成員的管理，即時更新成員信息以及系統結構變化。

1.2 模型運行原理

分布式輸送系統控制模型運作的基本思路是利用現代RFID技術動態地標識放到載貨臺上準備輸送的單元式實體，并讓運行時所經過的節點來選擇需要傳送的輸送設備。

各模塊化載貨臺將其空閑或忙碌狀態通過AP訪問點傳送至管理計算機，確定任一時刻可供使用的載貨臺。貨箱放上載貨臺后，計算機管理系統通過 RFID 讀寫設備往貨箱上的RFID標簽中動態地寫入所需要傳送的起始位置和目標位置等信息。當貨箱被傳輸到下一個交叉節點時，交叉節點處嵌入式系統的RFID 讀寫設備和控制設備會獲取貨箱上的起始目的位置等信息，由此再利用網絡路由技術，使用這些位置信息為該貨箱選擇下一條傳送模塊進行傳送，并通過建立防碰撞、沖突機制避免碰撞和沖突。

2 基于距離矢量的多下一跳路由算法

2.1 節點路由表

模型中的節點需要獲得所有其他節點的信息，這些信息包括達到某個節點的距離以及路徑選擇。這些信息在節點中用表來存儲，稱為節點路由表。

實體輸送系統中節點的路由表包含目的節點、距離和下一跳節點等3個表項。其中，目的節點和下一跳節點都是用節點的Id地址來表示的，典型的節點路由表如2所示。

2.2 上游節點和下游節點

假設節點ni到節點nj的最短路徑長度為。對于目的節點nk，ni到nk的最短路徑長度為，nj到nk的最短路徑長度為。如果為則稱對于目的節點nk，ni是nj的下游節點，nj是ni的上游節點。上游節點和下游節點的概念是相對的，定下了目的節點之后，節點之間的上下游關系才能比較，兩節點之間的上下游關系會隨著目的節點的不同而改變。

圖2 節點路由表

以圖3為例，假設每兩個相連節點之間的路徑長度均為10，就目的節點n15而言，對于n7,根據計算，它到目的節點的最短路徑長度為30，n11和n6到目的節點的最短路徑長度分別為20和40，根據以上定義，n11為n7的下游節點，n6為n7的上游節點。更進一步，可以通過計算得出，n7的上游節點集合為{n1，n2，n3，n5，n6，n9，n13}，它的下游節點集合為 {n8，n11，n12}。

圖3 上下游節點圖例

2.3 算法描述

輸送系統的節點通過路由表來存儲系統中所有其他節點的信息，并且對于指定的目的節點而言，當前節點只存儲下一跳為下游節點的信息。

輸送系統運行之初，通過配置，節點路由表存儲關于相鄰節點的信息。

在之后一段時間之內（視系統復雜程度而定），所有的節點不斷和相鄰節點交換信息，交換的信息為節點所有的路由信息，即路由表。在交換的過程中，不斷更新自己的路由表，直到所有的節點獲得正確的路由信息。在這段時間之后，除非輸送系統的結構發生變化，否則各節點之間不再交換路由信息。現對此交換過程中用到的距離向量算法描述為

假設網絡節點集為N，節點i的鄰居節點集為Ni，本文算法有兩個輸入：1）本地節點i接收自鄰居節點k關于目的節點j的最優距離；2）鄰居節點Id。

本地節點ni接收鄰居節點nj的最優路由，讀取它到目的節點nk(nk≠ni)的距離：

1 If (本地節點ni不含到目的節點nk的路由表項)

2 目的節點＝ ni；

3 最優下一跳＝ nj；

6 目的節點＝nk；

7 最優下一跳＝ nj；

8 次優下一跳=原下一跳節點；

11 目的節點=nk;

12 次優下一跳＝ nj；

15 ；//路由表不作變動

16 End if；

算法說明為

第1行到第4行 當節點ni收到節點nj到達目的節點nk的當前最優路由信息時，節點ni判斷路由表中有沒有到達目的節點nk的路由，如果沒有，則將節點nj作為到達目的節點nk的最優下一跳節點，節點ni到目的節點nk的最優距離暫定為+。

第5行到第9行 如果路由表中已存在到達目的節點nk的路由，且則將節點nj作為最優下一跳節點，最優距離更新為，原路由表項作為次優路由信息存儲在最優路由表項之后。

第10行到13行 如果路由表中已存在到達目的節點nk的路由，的話，說明獲得新的下游節點nj，但非更優，令距離等于，下一跳為nj的新表項加入到最優表項之后，作為次優表項。

第14行到第16行 如果路由表中已存在到達目的節點nk的路由，且說明節點nj不是節點ni的下游節點，路由表不作變動。

3 基于動態時間窗交換的防碰撞、沖突機制

3.1 時間窗

當實體通過節點時，節點被實體占用一定的時間。為表征節點被占用的情況，引入時間窗的概念。

時間窗是一個時間區間，分為占用的（reserved）和空閑的（free）兩種。在節點的占用的時間窗內，節點被指定的實體占用，而其他實體不得進入此節點。占用的時間窗用實體進入和離開此節點時刻之間的時間區間來表示。而空閑的時間窗則指示該節點在這個時間區間內，沒有被實體占用，可供任何實體占用。一個簡單的時間窗如圖4所示，陰影部分表示占用時間窗，空白部分表示空閑時間窗，即時間區間[3，5]、[12，14]為占用時間窗，而時間區間[5，12]則為空閑時間窗。

圖4 節點上時間窗

3.2 算法描述

在節點上設置緩沖區(buffer)，使實體能在緩沖區暫留而不占用節點。為了算法描述方便，假設實體在傳送帶上運行速度恒定，且傳送帶上沒有實體時，傳送帶速度為零。

輸送系統運行之初，所有節點時間窗均為空閑時間窗，可供任何實體占用。當一個節點向下一跳節點傳輸發送實體時，該節點要向其發送以下信息：傳送起始時間tnow和傳輸速度v，下一跳節點根據這些信息和兩節點之間路徑長度L在本節點上新添一個時間窗，并把更新后的時間窗信息發送給所有鄰居節點。具體算法步驟為

第一步：實體到達節點n1，節點n1讀取實體的目的地址，查詢路由表為該實體選擇最優下一跳節點n2；

第二步：首先根據節點n1和節點n2之間傳送帶的方向來判斷路徑是否被占用，若傳送帶靜止或者和實體擬傳送的方向相同，則轉入第三步，若傳送帶的方向和實體擬傳送方向相反，則轉入第四步；

第三步：節點n1根據到節點n2的路徑長度、傳送速度和當前的時間，為節點n2建立一個虛擬的時間窗，并把這個虛擬的時間窗與節點n2的實際時間窗進行對比，若兩者占用的時間窗部分沒有重疊，則把實體向節點n2傳送，并向它發送相應的信息，節點n2根據這些信息在本節點上新添一個時間窗，并把更新后的時間窗發送給鄰居節點。一個算法流程結束。反之，占用的時間窗部分有重疊，則轉入第四步；

第四步：節點n1根據路由表查找是否有次優下一跳，若有，選擇次優下一跳n3，令下一跳為次優下一跳,重復第二、第三步，若沒有次優的下一跳，則把實體暫時存入叉道；

第五步：節點根據自己的時間窗，在本節點足夠大的空白時間窗內（大于把實體從叉道調入節點的時間），定時（如每隔0.2 s）重復上述的判斷（判斷時要考慮把實體從叉道調出的時間），直到有可供傳送的路徑，把實體從叉道中調出，發送給相應節點，一個算法流程結束。

需要注意的是：防碰撞、沖突的算法是建立在節點路由表構建完成的基礎之上的；實體一旦離開節點，在傳送帶上的傳輸速度不能為零，即實體不能靜止地停留在傳送帶中。

4 算法性能仿真驗證

為了驗證本文所提出算法的性能，采用C++語言對分布式輸送系統進行面向對象建模。在仿真程序中，可以構造任意輸送系統，并加入任意數量的實體對算法性能進行驗證。

通過一個具體的實例來對算法的綜合性能進行驗證。仿真實例圖如5所示，其中大的方格表示節點，大方格右下角的小方格為節點緩沖區，連接兩個節點的深色條形為傳送帶。

在圖5所示的輸送系統中，在A～L節點同時加入12個實體，目的地址分別為I、H、G、L、K、J、C、B、A、F、E、D。加入實體后，運行系統，輸送系統的運行狀態圖如圖6所示。

圖5 算法性能驗證圖例

圖6 輸送系統運行狀態圖

通過實體在輸送系統中的實際傳輸時間和理論最短時間比較，來評估輸送系統的性能。首先，定義一個延遲比δ指標，即

式中：t理論為實體在輸送系統中傳輸的理論最短時間，t實際為實體在輸送系統中傳輸的實際時間。

對實例中實體傳輸時間和延遲比統計如表1，實體在傳輸過程中，成功避免碰撞。由表1可知，加入系統的12個實體中，延遲比最小的是2.5%，最大的是38.1%。平均延遲比為11.2%。

表1 節點運行時間表

從數據來看，所有的實體在輸送過程中都存在一定的延時。但實際上，那些延遲時間較短的實體在輸送過程中并沒有在系統中滯留，它的延遲是在節點處轉向造成的。

最大延遲比達38.1%，實體在系統中的滯留時間較長。造成節點滯留的原因是實體經過的路段太過擁擠，使得實體多次被存入緩沖區等待。由此可以得出結論，輸送系統中同時傳輸的實體越多，造成實體輸送的時延比將越大。輸送單元理論、實際傳輸時間對比見圖7，輸送單元傳輸延遲率見圖8。

圖7 輸送單元理論、實際傳輸時間對比

圖8 輸送單元傳輸延遲率

驗證的結果顯示，系統能有效避免輸送系統中實體的碰撞，能以較小的時延把實體傳輸到目的節點，能達到較高的吞吐量水平。

5 結語

本文設計分布式路由控制算法能使系統中的實體在無碰撞、沖突的情況下以較小的時延到達目的節點，同時系統能達到較大的吞吐量水平。后續研究將是在節點或弧發生故障時，節點路由表進行相應的調整以實現網絡的快速自愈，提高算法的穩健性。