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

0 引言

在工業(yè)生產(chǎn)中，各類輸送系統(tǒng)對生產(chǎn)效率的提高起著至關(guān)重要的作用。自動化倉儲系統(tǒng)，物流配送中心和柔性制造系統(tǒng)等環(huán)境中的輸送系統(tǒng)，具有由多通道及交叉節(jié)點構(gòu)成的網(wǎng)絡結(jié)構(gòu)。隨著工業(yè)自動化水平的上升，系統(tǒng)呈現(xiàn)大規(guī)?；蛷碗s化的趨勢，控制難度越來越大。

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

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

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

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

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

本文首先簡述節(jié)點主動控制輸送系統(tǒng)模型組成及運行原理，通過分析模型確定算法要達到的要求。然后提出本文設計的分布式控制算法。最后，通過面向?qū)ο蠓抡娼λ惴ㄐ阅苓M行驗證。

1 分布式輸送系統(tǒng)模型

1.1 模型組成

如圖1所示，模型是一個網(wǎng)絡結(jié)構(gòu)，主要包括節(jié)點、弧、輸送實體、中央管理機等。

圖1 分布式輸送系統(tǒng)控制模型

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

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

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

4）中央管理機 負責模型中成員的管理，即時更新成員信息以及系統(tǒng)結(jié)構(gòu)變化。

1.2 模型運行原理

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

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

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

2.1 節(jié)點路由表

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

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

2.2 上游節(jié)點和下游節(jié)點

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

圖2 節(jié)點路由表

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

圖3 上下游節(jié)點圖例

2.3 算法描述

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

輸送系統(tǒng)運行之初，通過配置，節(jié)點路由表存儲關(guān)于相鄰節(jié)點的信息。

在之后一段時間之內(nèi)（視系統(tǒng)復雜程度而定），所有的節(jié)點不斷和相鄰節(jié)點交換信息，交換的信息為節(jié)點所有的路由信息，即路由表。在交換的過程中，不斷更新自己的路由表，直到所有的節(jié)點獲得正確的路由信息。在這段時間之后，除非輸送系統(tǒng)的結(jié)構(gòu)發(fā)生變化，否則各節(jié)點之間不再交換路由信息?，F(xiàn)對此交換過程中用到的距離向量算法描述為

假設網(wǎng)絡節(jié)點集為N，節(jié)點i的鄰居節(jié)點集為Ni，本文算法有兩個輸入：1）本地節(jié)點i接收自鄰居節(jié)點k關(guān)于目的節(jié)點j的最優(yōu)距離；2）鄰居節(jié)點Id。

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

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

2 目的節(jié)點＝ ni；

3 最優(yōu)下一跳＝ nj；

6 目的節(jié)點＝nk；

7 最優(yōu)下一跳＝ nj；

8 次優(yōu)下一跳=原下一跳節(jié)點；

11 目的節(jié)點=nk;

12 次優(yōu)下一跳＝ nj；

15 ；//路由表不作變動

16 End if；

算法說明為

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

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

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

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

3 基于動態(tài)時間窗交換的防碰撞、沖突機制

3.1 時間窗

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

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

圖4 節(jié)點上時間窗

3.2 算法描述

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

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

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

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

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

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

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

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

4 算法性能仿真驗證

為了驗證本文所提出算法的性能，采用C++語言對分布式輸送系統(tǒng)進行面向?qū)ο蠼?。在仿真程序中，可以?gòu)造任意輸送系統(tǒng)，并加入任意數(shù)量的實體對算法性能進行驗證。

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

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

圖5 算法性能驗證圖例

圖6 輸送系統(tǒng)運行狀態(tài)圖

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

式中：t理論為實體在輸送系統(tǒng)中傳輸?shù)睦碚撟疃虝r間，t實際為實體在輸送系統(tǒng)中傳輸?shù)膶嶋H時間。

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

表1 節(jié)點運行時間表

從數(shù)據(jù)來看，所有的實體在輸送過程中都存在一定的延時。但實際上，那些延遲時間較短的實體在輸送過程中并沒有在系統(tǒng)中滯留，它的延遲是在節(jié)點處轉(zhuǎn)向造成的。

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

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

圖8 輸送單元傳輸延遲率

驗證的結(jié)果顯示，系統(tǒng)能有效避免輸送系統(tǒng)中實體的碰撞，能以較小的時延把實體傳輸?shù)侥康墓?jié)點，能達到較高的吞吐量水平。

5 結(jié)語

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