基于Dijkstra算法的ISA100.11a路由策略

琚成 楊會甲 成斐鳴 張建奇

摘 要：為了有效利用網(wǎng)絡(luò)能量，針對工業(yè)現(xiàn)場無線網(wǎng)絡(luò)數(shù)據(jù)傳輸可靠性和實時性要求，提出了一種基于Dijkstra算法的ISA100.11a路由策略。以網(wǎng)絡(luò)能耗、鏈路質(zhì)量和端到端平均延時為評價指標，建立復(fù)合權(quán)值模型，依據(jù)Dijkstra算法選擇I/O節(jié)點到骨干路由器數(shù)據(jù)傳輸最優(yōu)路徑。首先與ISA-Floyd路由算法相比較，在同等條件下，ISA100.11a網(wǎng)絡(luò)生命周期得到延長;然后分析網(wǎng)絡(luò)能耗、鏈路質(zhì)量和端到端平均延時三個評價指標的相互作用關(guān)系，并優(yōu)化其在路由算法中的權(quán)重。最終測試結(jié)果表明，該算法在延長網(wǎng)絡(luò)生命周期的同時，有效保障了網(wǎng)絡(luò)通信的可靠性和確定性。

關(guān)鍵詞：無線傳感網(wǎng)絡(luò);ISA100.11a;Dijkstra算法;圖路由;復(fù)合權(quán)值

中圖分類號：TP393文獻標識碼：A文章編號：2095-1302（2019）01-00-05

0 引 言

隨著《中國制造2025》制造強國戰(zhàn)略的開展，智能制造關(guān)鍵技術(shù)的研發(fā)與應(yīng)用成為熱點。智能制造標準體系是智能制造工作的頂層設(shè)計和基礎(chǔ)保障，明確了智能制造系統(tǒng)的架構(gòu)組成[1]。無線傳感網(wǎng)絡(luò)位于智能制造系統(tǒng)架構(gòu)中的互聯(lián)互通層面，貫穿智能制造系統(tǒng)架構(gòu)生命周期和系統(tǒng)層級[2]。因此，無線傳感網(wǎng)絡(luò)是智能制造的重要技術(shù)支撐。

無線傳感網(wǎng)絡(luò)具備高密度特征，在固定區(qū)域內(nèi)包含大量具有無線通信能力的感知節(jié)點和路由節(jié)點，它們以自組織和多跳方式相互協(xié)調(diào)實現(xiàn)區(qū)域內(nèi)信息的感知、采集、處理和傳輸[3]。無線傳感網(wǎng)絡(luò)有效解決了布局布線困難、安裝維修費用高等問題，但在工業(yè)現(xiàn)場復(fù)雜環(huán)境下，區(qū)域內(nèi)監(jiān)控設(shè)備密度大，節(jié)點信號間相互串?dāng)_且受外界干擾較多，使得無線網(wǎng)絡(luò)資源開銷較大，數(shù)據(jù)通信可靠性和實時性受到影響，使其成為工業(yè)無線技術(shù)的應(yīng)用瓶頸[4]。路由技術(shù)作為無線傳感網(wǎng)絡(luò)的關(guān)鍵技術(shù)，影響整個網(wǎng)絡(luò)生命周期及其可靠性和實時性，因此提出一種適用于工業(yè)現(xiàn)場的路由算法至關(guān)重要。

ISA100.11a標準作為三大工業(yè)無線傳感網(wǎng)絡(luò)標準之一，以用戶需求為導(dǎo)向，力求滿足工業(yè)現(xiàn)場低復(fù)雜度、低功耗和合理成本需求，是第一個開放的、面向工業(yè)應(yīng)用的標準[5]。ISA100.11a標準闡明了ISA100.11a網(wǎng)絡(luò)體系架構(gòu)、拓撲結(jié)構(gòu)以及所采用的關(guān)鍵技術(shù)，但未指定具體路由算法。同時，由于傳統(tǒng)路由協(xié)議AODV[6]，OSPF[7]，DSR[8]等的運行機制與ISA100.11a網(wǎng)絡(luò)底層IEEE 802.15.4時分多址（Time Division Multiple Access，TDMA）機制不兼容，因此無法滿足確定性調(diào)度需求。為此，ISA100.11a網(wǎng)絡(luò)路由技術(shù)成為了研究熱點。謝昊飛和李小占等人以鏈路質(zhì)量和剩余能量為評價指標尋找一條從感知節(jié)點到網(wǎng)關(guān)的優(yōu)化路徑[9-10]。T Nhon等人采用流量感知消息調(diào)度和競爭窗口尺寸調(diào)整算法優(yōu)化所選路徑的鏈路質(zhì)量和端到端平均延時[11]。Pham等人以節(jié)點剩余能量和端到端平均延時為評價指標，基于整數(shù)線性規(guī)劃算法構(gòu)建路由算法，結(jié)果表明該路由算法在延長網(wǎng)絡(luò)生命期的同時提高了網(wǎng)絡(luò)數(shù)據(jù)通信的實時性[12]。

隨著工業(yè)現(xiàn)場應(yīng)用復(fù)雜化和精細化程度逐漸加深，基于網(wǎng)絡(luò)數(shù)據(jù)實現(xiàn)決策和分析的業(yè)務(wù)應(yīng)用場景逐漸增強，這便要求網(wǎng)絡(luò)通信具備良好的可靠性和實時性[13]。為滿足如上需求，本文提出了一種基于最短路徑Dijkstra算法的ISA100.11a路由策略，以網(wǎng)絡(luò)能耗、鏈路質(zhì)量、端到端平均延時作為路徑選擇的評價指標，建立復(fù)合權(quán)值模型，優(yōu)化工業(yè)現(xiàn)場網(wǎng)絡(luò)通信數(shù)據(jù)傳輸路徑，在延長網(wǎng)絡(luò)生命周期的同時，保障網(wǎng)絡(luò)通信數(shù)據(jù)的可靠性和實時性。

1 ISA100.11a概述

ISA100.11a網(wǎng)絡(luò)設(shè)備包括系統(tǒng)管理器（System Manager，SM）、網(wǎng)關(guān)（Gateway，GW）、中間件（Middleware，MW）骨干路由器（Backbone Router，BBR）、路由節(jié)點（Router Device，RD）、I/O節(jié)點等。其中，路由資源管理與分配算法運行在SM中。當(dāng)ISA100.11a網(wǎng)絡(luò)中存在BBR時，網(wǎng)絡(luò)可劃分為骨干網(wǎng)絡(luò)和數(shù)據(jù)鏈路（Data Link，DL）子網(wǎng)，如圖1所示。

由于骨干網(wǎng)絡(luò)多采用以太網(wǎng)或工業(yè)現(xiàn)場總線等高速通信特性網(wǎng)絡(luò)以滿足ISA100.11a網(wǎng)絡(luò)大容量、高帶寬、通信實時性的要求，故而不在本文討論范圍內(nèi)。DL子網(wǎng)內(nèi)節(jié)點依據(jù)SM分配鏈路和操作時隙，采用多跳方式與BBR進行信息交互，通過中間件存取數(shù)據(jù)庫信息，并利用Web系統(tǒng)和數(shù)據(jù)庫組成B/S模型實現(xiàn)人機交互進行工業(yè)現(xiàn)場監(jiān)控[9]。ISA100.11a標準闡明了DL子網(wǎng)內(nèi)的數(shù)據(jù)傳輸主要依賴ISA100.11a標準中的圖路由協(xié)議。圖作為DL子網(wǎng)的有向鏈路集合，采用八進制字符串索引集合dlmo.Graph管理，包括圖ID、優(yōu)化分支指示、鄰居數(shù)、數(shù)據(jù)緩沖隊列、最大生命周期、鄰居表索引。DL子網(wǎng)內(nèi)設(shè)備可占據(jù)多個圖且圖之間可存在重疊，因此可形成多條到達目的設(shè)備的路徑。在圖1中DL子網(wǎng)內(nèi)包含虛線和實線兩個圖，分別具有不同的圖ID，I/O節(jié)點1#可通過實線或虛線路徑上傳數(shù)據(jù)到BBR。

具體工作過程如下：

（1）I/O節(jié)點提取協(xié)議數(shù)據(jù)單元（Protocol Data Unit，PDU）中的契約Contract ID搜索圖ID。

（2）判斷優(yōu)化分支指示值決定所選鄰居后，將緩沖隊列中的PDU傳遞給鄰居節(jié)點，鄰居節(jié)點重復(fù)上述過程直到PDU到達BBR。

本文的重點是依據(jù)路徑選擇的評價指標，借助最短路徑Dijkstra算法合理規(guī)劃DL子網(wǎng)內(nèi)數(shù)據(jù)傳播路徑形成圖，優(yōu)化PDU傳播過程。

2 算法設(shè)計

對工業(yè)現(xiàn)場控制而言，不僅要保證數(shù)據(jù)傳輸過程的完整性，還要保證數(shù)據(jù)傳輸?shù)膶崟r性;對于工業(yè)現(xiàn)場監(jiān)測而言，則需要維持整體網(wǎng)絡(luò)及局部節(jié)點的長久存活周期。為滿足上述需求，本文路由算法以網(wǎng)絡(luò)能耗、鏈路質(zhì)量和端到端平均延時為評價指標，保證網(wǎng)絡(luò)運行的可靠性、健壯性和實時性。