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

琚成 楊會(huì)甲 成斐鳴 張建奇

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

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

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：2095-1302（2019）01-00-05

0 引 言

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

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

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

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

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é)點(diǎn)（Router Device，RD）、I/O節(jié)點(diǎn)等。其中，路由資源管理與分配算法運(yùn)行在SM中。當(dāng)ISA100.11a網(wǎng)絡(luò)中存在BBR時(shí)，網(wǎng)絡(luò)可劃分為骨干網(wǎng)絡(luò)和數(shù)據(jù)鏈路（Data Link，DL）子網(wǎng)，如圖1所示。

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

具體工作過程如下：

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

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

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

2 算法設(shè)計(jì)

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