分布式輸送系統(tǒng)節(jié)點(diǎn)路由控制算法設(shè)計(jì)＊

同濟(jì)大學(xué)機(jī)械與能源工程學(xué)院 上海 201804

0 引言

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

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

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

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

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

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

本文首先簡(jiǎn)述節(jié)點(diǎn)主動(dòng)控制輸送系統(tǒng)模型組成及運(yùn)行原理，通過(guò)分析模型確定算法要達(dá)到的要求。然后提出本文設(shè)計(jì)的分布式控制算法。最后，通過(guò)面向?qū)ο蠓抡娼?duì)算法性能進(jìn)行驗(yàn)證。

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

1.1 模型組成

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

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

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

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

3）輸送實(shí)體 指輸送系統(tǒng)輸送的對(duì)象，比如倉(cāng)儲(chǔ)系統(tǒng)的貨物，生產(chǎn)線(xiàn)上的在制品等。本文輸送系統(tǒng)模型中的運(yùn)輸實(shí)體貼有RFID電子標(biāo)簽。

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

1.2 模型運(yùn)行原理

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

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

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

2.1 節(jié)點(diǎn)路由表

模型中的節(jié)點(diǎn)需要獲得所有其他節(jié)點(diǎn)的信息，這些信息包括達(dá)到某個(gè)節(jié)點(diǎn)的距離以及路徑選擇。這些信息在節(jié)點(diǎn)中用表來(lái)存儲(chǔ)，稱(chēng)為節(jié)點(diǎn)路由表。

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

2.2 上游節(jié)點(diǎn)和下游節(jié)點(diǎn)

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

圖2 節(jié)點(diǎn)路由表

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

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

2.3 算法描述

輸送系統(tǒng)的節(jié)點(diǎn)通過(guò)路由表來(lái)存儲(chǔ)系統(tǒng)中所有其他節(jié)點(diǎn)的信息，并且對(duì)于指定的目的節(jié)點(diǎn)而言，當(dāng)前節(jié)點(diǎn)只存儲(chǔ)下一跳為下游節(jié)點(diǎn)的信息。

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

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

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

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

1 If (本地節(jié)點(diǎn)ni不含到目的節(jié)點(diǎn)nk的路由表項(xiàng))

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

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

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

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

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

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

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

15 ；//路由表不作變動(dòng)

16 End if；

算法說(shuō)明為

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

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

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

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

3 基于動(dòng)態(tài)時(shí)間窗交換的防碰撞、沖突機(jī)制

3.1 時(shí)間窗

當(dāng)實(shí)體通過(guò)節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)被實(shí)體占用一定的時(shí)間。為表征節(jié)點(diǎn)被占用的情況，引入時(shí)間窗的概念。

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

圖4 節(jié)點(diǎn)上時(shí)間窗

3.2 算法描述

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

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

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

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

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

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

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

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

4 算法性能仿真驗(yàn)證

為了驗(yàn)證本文所提出算法的性能，采用C++語(yǔ)言對(duì)分布式輸送系統(tǒng)進(jìn)行面向?qū)ο蠼！Ｔ诜抡娉绦蛑校梢詷?gòu)造任意輸送系統(tǒng)，并加入任意數(shù)量的實(shí)體對(duì)算法性能進(jìn)行驗(yàn)證。

通過(guò)一個(gè)具體的實(shí)例來(lái)對(duì)算法的綜合性能進(jìn)行驗(yàn)證。仿真實(shí)例圖如5所示，其中大的方格表示節(jié)點(diǎn)，大方格右下角的小方格為節(jié)點(diǎn)緩沖區(qū)，連接兩個(gè)節(jié)點(diǎn)的深色條形為傳送帶。

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

圖5 算法性能驗(yàn)證圖例

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

通過(guò)實(shí)體在輸送系統(tǒng)中的實(shí)際傳輸時(shí)間和理論最短時(shí)間比較，來(lái)評(píng)估輸送系統(tǒng)的性能。首先，定義一個(gè)延遲比δ指標(biāo)，即

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

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

表1 節(jié)點(diǎn)運(yùn)行時(shí)間表

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

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

圖7 輸送單元理論、實(shí)際傳輸時(shí)間對(duì)比

圖8 輸送單元傳輸延遲率

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

5 結(jié)語(yǔ)

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