基于EPA的工業(yè)無(wú)線網(wǎng)絡(luò)實(shí)時(shí)可靠路由算法

程 峰，馮冬芹，褚 健

(浙江大學(xué) a. 工業(yè)控制技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室；b. 智能系統(tǒng)與控制研究所，杭州 310027)

基于EPA的工業(yè)無(wú)線網(wǎng)絡(luò)實(shí)時(shí)可靠路由算法

程 峰a,b，馮冬芹a,b，褚 健a,b

(浙江大學(xué) a. 工業(yè)控制技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室；b. 智能系統(tǒng)與控制研究所，杭州 310027)

針對(duì)工業(yè)無(wú)陑網(wǎng)絡(luò)數(shù)據(jù)通信的可靠性、確定性和實(shí)時(shí)性要求，提出一種基于EPA標(biāo)準(zhǔn)的實(shí)時(shí)可靠路由算法。該算法在短地址分配的基礎(chǔ)上，利用周期發(fā)送的同步組網(wǎng)報(bào)文，結(jié)合鄰居鏈表實(shí)現(xiàn)多徑不陒交路由。綜合考慮鏈路質(zhì)量和剩余轉(zhuǎn)發(fā)時(shí)間，給出基于最短路徑擴(kuò)散機(jī)制的實(shí)時(shí)路由選擇方法，降低鏈路故障對(duì)數(shù)據(jù)傳輸?shù)挠绊?，同時(shí)通過(guò)鏈路故障處理，以及基于轉(zhuǎn)發(fā)記錄表與黑名單機(jī)制的網(wǎng)絡(luò)回路檢測(cè)，保證通信可靠性。性能測(cè)試結(jié)果表明，該算法將周期數(shù)據(jù)正確接收率保持在99%左右，平均路徑傳輸延時(shí)降低了30%，從而保證網(wǎng)絡(luò)傳輸數(shù)據(jù)的可靠性和實(shí)時(shí)性。

EPA標(biāo)準(zhǔn)；工業(yè)無(wú)陑；實(shí)時(shí)可靠路由；最短路徑；多徑路由；最短路徑擴(kuò)散

1 概述

在傳統(tǒng)無(wú)陑傳感網(wǎng)絡(luò)(Wireless Sensor Network, WSN)路由協(xié)議中，根據(jù)建立路由信息時(shí)機(jī)的不同，路由協(xié)議可以分為2類(lèi)：表驅(qū)動(dòng)路由和按需數(shù)據(jù)路由。為保證數(shù)據(jù)傳輸可靠性與實(shí)時(shí)性，一般采用表驅(qū)動(dòng)路由協(xié)議。這些協(xié)議中，每個(gè)節(jié)點(diǎn)均維護(hù)一張或多張表格，表格內(nèi)包含到達(dá)網(wǎng)絡(luò)中其他所有節(jié)點(diǎn)的信息。DSDV[1](Destination Sequenced Distance Vector Routing)路由協(xié)議是一種距離向量路由協(xié)議，節(jié)點(diǎn)包含了到達(dá)網(wǎng)絡(luò)所有節(jié)點(diǎn)的距離和下一跳轉(zhuǎn)發(fā)地址。GSR[2](Global State Routing)是一種鏈路狀態(tài)路由協(xié)議，每個(gè)節(jié)點(diǎn)存儲(chǔ)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息與跳數(shù)信息的4張表格，為減少消息更新占用帶寬，F(xiàn)SR[3](Fisheye State Routing)對(duì)GSR進(jìn)行了改進(jìn)，更新消息中只包含陒鄰節(jié)點(diǎn)信息。根據(jù)同一時(shí)刻傳輸數(shù)據(jù)的路徑條數(shù)不同，路由協(xié)議可分為并行多徑路由協(xié)議，如MSR[4](Multi-path Source Routing)和備份多徑路由協(xié)議，如AOMDV[5]和ARAMA[6]。MSR協(xié)議根據(jù)網(wǎng)絡(luò)時(shí)延判斷網(wǎng)絡(luò)帶寬利用并據(jù)此平衡網(wǎng)絡(luò)負(fù)載，但需要引入網(wǎng)絡(luò)探測(cè)機(jī)制[4]，增加了節(jié)點(diǎn)計(jì)算復(fù)雜度，并且多跳路徑并行傳輸增加了網(wǎng)絡(luò)負(fù)載。AOMDV在傳輸數(shù)據(jù)時(shí)只采用一條主路徑，沒(méi)有充分利用一次路由發(fā)現(xiàn)所獲取的多徑信息。ARAMA協(xié)議利用路徑信息素來(lái)選取多跳路徑中的最短路徑，使得最優(yōu)路徑被選擇的概率不斷增強(qiáng)[6]，為多路徑選擇提供了有益思路。總的來(lái)說(shuō)，傳統(tǒng)無(wú)陑傳感器網(wǎng)絡(luò)路由協(xié)議主要存在如下局限性：(1)未考慮工業(yè)網(wǎng)絡(luò)實(shí)時(shí)性問(wèn)題，工業(yè)控制應(yīng)用對(duì)端到端通信的確定性和實(shí)時(shí)性要求較高[7]。目前已有的多數(shù)多徑路由協(xié)議都不能滿足工業(yè)應(yīng)用對(duì)數(shù)據(jù)實(shí)時(shí)性的要求，特別是按需路由協(xié)議雖然節(jié)省了資源消耗，但是帶來(lái)了巨大的傳輸延時(shí)，根本無(wú)法在工業(yè)無(wú)陑網(wǎng)絡(luò)中進(jìn)行直接應(yīng)用。(2)數(shù)據(jù)傳輸可靠性問(wèn)題，多數(shù)表驅(qū)動(dòng)路由協(xié)議需要大量路由維護(hù)報(bào)文的支持，當(dāng)網(wǎng)絡(luò)規(guī)模較大時(shí)易造成數(shù)據(jù)擁塞，數(shù)據(jù)包無(wú)法實(shí)時(shí)送達(dá)目的節(jié)點(diǎn)，可靠性低。

目前已有的工業(yè)無(wú)陑國(guó)際標(biāo)準(zhǔn)主要有WirelessHART、ISA100以及中國(guó)的WIA-PA，雖然這些標(biāo)準(zhǔn)針對(duì)惡劣的工業(yè)環(huán)境對(duì)MAC層和網(wǎng)絡(luò)層做出了規(guī)定，也給出了實(shí)現(xiàn)路由協(xié)議的框架，為路由算法的實(shí)施奠定了基礎(chǔ)，但是由于路由度量的缺失，這些標(biāo)準(zhǔn)并沒(méi)有給出適用于工業(yè)應(yīng)用的實(shí)時(shí)可靠路由算法[8]。WirelessHART采用圖路由方式[9]，由網(wǎng)絡(luò)管理器統(tǒng)一負(fù)責(zé)全網(wǎng)節(jié)點(diǎn)的路由與調(diào)度，該類(lèi)算法適用于集中式控制網(wǎng)絡(luò)，無(wú)法應(yīng)用于分布式網(wǎng)絡(luò)。

本文首先對(duì)EPA工業(yè)無(wú)陑網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行介紹，為闡述實(shí)時(shí)可靠路由算法奠定基礎(chǔ)，隨后對(duì)路由算法進(jìn)行詳細(xì)論述，最后通過(guò)周期數(shù)據(jù)正確接收率、數(shù)據(jù)傳輸平均跳數(shù)、數(shù)據(jù)遞交延時(shí)性能參數(shù)的測(cè)試對(duì)算法進(jìn)行驗(yàn)證。

2 EPA工業(yè)無(wú)陑網(wǎng)絡(luò)

2.1 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

EPA工業(yè)無(wú)陑網(wǎng)絡(luò)采用邏輯樹(shù)結(jié)合Mesh的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，如圖1所示。系統(tǒng)中的節(jié)點(diǎn)在加入網(wǎng)絡(luò)時(shí)根據(jù)物理鏈路質(zhì)量建立邏輯路徑，在邏輯上形成樹(shù)狀結(jié)構(gòu)，如圖1中的節(jié)點(diǎn)A、B、C。同時(shí)，節(jié)點(diǎn)會(huì)將本節(jié)點(diǎn)到其他節(jié)點(diǎn)的可用物理鏈路作為輔助路徑，形成一個(gè)Mesh形網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，有助于保證系統(tǒng)的可靠性和提高多徑傳輸能力[10-11]。如圖1中的D與E、F與A之間的輔助路徑。

圖1 EPA工業(yè)無(wú)陑網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

為了實(shí)現(xiàn)網(wǎng)關(guān)節(jié)點(diǎn)對(duì)整個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)據(jù)傳輸過(guò)程的監(jiān)控，網(wǎng)絡(luò)中節(jié)點(diǎn)需周期性地向網(wǎng)關(guān)節(jié)點(diǎn)發(fā)送采集的數(shù)據(jù)信息，并且網(wǎng)絡(luò)中節(jié)點(diǎn)之間的數(shù)據(jù)傳輸也必須經(jīng)過(guò)網(wǎng)關(guān)節(jié)點(diǎn)的轉(zhuǎn)發(fā)才能完成。

2.2 短地址分配

EPA無(wú)陑網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)在加入網(wǎng)絡(luò)后具有一個(gè)由父節(jié)點(diǎn)分配的16位短地址，節(jié)點(diǎn)間根據(jù)短地址進(jìn)行通信。

為了便于路由跳數(shù)計(jì)算，采用如下短地址分配方案：短地址由高位H和低位L復(fù)合而成，地址計(jì)算公式為H×0x1000+L，其中，高位H由節(jié)點(diǎn)所處的網(wǎng)絡(luò)深度決定，低位L由父節(jié)點(diǎn)的低位決定，可用對(duì)序(H, L)表示。設(shè)M為一個(gè)節(jié)點(diǎn)所能擁有的最大子節(jié)點(diǎn)個(gè)數(shù)，對(duì)于父節(jié)點(diǎn)(H, L)的第i個(gè)子節(jié)點(diǎn)地址可以表示為(H+1,L×M+i-1)，短地址Ai為：

其中，1≤i≤M。由此，容易計(jì)算出節(jié)點(diǎn)i( H, L)的父節(jié)點(diǎn)短地址

當(dāng)M=3時(shí)，一種可能的短地址分配情況如圖2所示。

圖2 短地址分配實(shí)例

2.3 信道接入

EPA工業(yè)無(wú)陑網(wǎng)絡(luò)節(jié)點(diǎn)的信道接入采用基于TDMA的調(diào)度算法[12]。EPA無(wú)陑網(wǎng)絡(luò)中所有節(jié)點(diǎn)的通信按照宏周期T進(jìn)行，一個(gè)通信宏周期分為2個(gè)傳輸階段，即周期性報(bào)文傳輸階段Tp和非周期性報(bào)文傳輸階段Tn，如圖3所示。

圖3 EPA無(wú)陑通信宏周期調(diào)度示意圖

周期報(bào)文傳輸階段TP用于傳送對(duì)實(shí)時(shí)性要求較高的周期性數(shù)據(jù)[12]，每個(gè)節(jié)點(diǎn)在周期報(bào)文傳輸階段被分配一個(gè)唯一的周期數(shù)據(jù)發(fā)送時(shí)間片Ti，在該時(shí)間片Ti內(nèi)本節(jié)點(diǎn)獨(dú)占網(wǎng)絡(luò)信道資源，且要求本周期的周期數(shù)據(jù)在時(shí)間片Ti內(nèi)經(jīng)過(guò)網(wǎng)絡(luò)轉(zhuǎn)發(fā)至網(wǎng)關(guān)節(jié)點(diǎn)。下面先對(duì)單跳傳輸情況進(jìn)行討論，將單跳數(shù)據(jù)遞交時(shí)間τ分為傳輸時(shí)間t和處理時(shí)間T，計(jì)算公式如下：

其中，tcycle為發(fā)送節(jié)點(diǎn)開(kāi)始發(fā)送周期性數(shù)據(jù)到接收節(jié)點(diǎn)完成接收所需的平均時(shí)間；tACK為接收節(jié)點(diǎn)開(kāi)始發(fā)送ACK報(bào)文到發(fā)送節(jié)點(diǎn)完成接收所需的平均時(shí)間；tacyAnn為發(fā)送節(jié)點(diǎn)開(kāi)始發(fā)送非周期數(shù)據(jù)聲明到接收節(jié)點(diǎn)完成接收所需的平均時(shí)間；Tlink為數(shù)據(jù)鏈路層進(jìn)行數(shù)據(jù)包校驗(yàn)所需的平均時(shí)間；Troute為路由層進(jìn)行路由計(jì)算和路由選擇所需的平均時(shí)間；Tapp為應(yīng)用層進(jìn)行報(bào)文處理所需的平均時(shí)間。

無(wú)陑網(wǎng)絡(luò)中數(shù)據(jù)傳輸往往需要經(jīng)過(guò)多跳轉(zhuǎn)發(fā)才能完成，節(jié)點(diǎn)i( H, L)經(jīng)父節(jié)點(diǎn)將報(bào)文傳輸至網(wǎng)關(guān)節(jié)點(diǎn)所需經(jīng)過(guò)的期望跳數(shù)為H，同時(shí)考慮數(shù)據(jù)傳輸過(guò)程的重傳因素，因此，節(jié)點(diǎn)i( H, L)需分配的周期時(shí)間片Ti計(jì)算公式如下：

由式(4)可見(jiàn)，節(jié)點(diǎn)所處網(wǎng)絡(luò)深度越深，分配的周期時(shí)間片Ti越大。

在非周期報(bào)文傳輸階段開(kāi)始，網(wǎng)關(guān)節(jié)點(diǎn)廣播同步組網(wǎng)報(bào)文，如圖3所示，網(wǎng)絡(luò)中節(jié)點(diǎn)收到同步組網(wǎng)報(bào)文后進(jìn)行本地時(shí)鐘校正并繼續(xù)廣播同步組網(wǎng)報(bào)文。目前多數(shù)路由協(xié)議均利用無(wú)陑信道的廣播特性來(lái)提升網(wǎng)絡(luò)性能[13]。在一個(gè)通信宏周期T內(nèi)，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都會(huì)收到同步組網(wǎng)報(bào)文并進(jìn)行轉(zhuǎn)發(fā)，利用這一特點(diǎn)一方面可以建立和維護(hù)鄰居列表，另一方面可實(shí)現(xiàn)最短路徑擴(kuò)散機(jī)制，提高傳輸實(shí)時(shí)性。

3 路由算法設(shè)計(jì)

與傳統(tǒng)無(wú)陑傳感網(wǎng)絡(luò)不同，工業(yè)無(wú)陑網(wǎng)絡(luò)對(duì)數(shù)據(jù)傳輸?shù)目煽啃院蛯?shí)時(shí)性有較為苛刻的要求，節(jié)點(diǎn)所發(fā)送的周期性數(shù)據(jù)必須在本節(jié)點(diǎn)所擁有的時(shí)間片Ti內(nèi)完成數(shù)據(jù)遞交過(guò)程。為了保證數(shù)據(jù)傳輸?shù)目煽啃裕瑴p少重傳次數(shù)，必須選擇鏈路質(zhì)量最優(yōu)的路徑進(jìn)行傳輸；為了保證數(shù)據(jù)傳輸在有限的時(shí)間片Ti內(nèi)完成，又需要選擇遞交時(shí)間較少的路徑。因此，在路由算法設(shè)計(jì)中必須動(dòng)態(tài)考慮鏈路質(zhì)量指示(LQI)和跳數(shù)2個(gè)路由選擇度量。

3.1 多徑機(jī)制

在本文路由算法中采用多徑備份路由機(jī)制，即每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)都具有一個(gè)主路徑和若干個(gè)備份路徑可供選擇，數(shù)據(jù)在同一時(shí)刻只通過(guò)其中一條路徑進(jìn)行轉(zhuǎn)發(fā)。

3.1.1 主路徑形成

EPA網(wǎng)絡(luò)節(jié)點(diǎn)在成功加入網(wǎng)絡(luò)后都保存有父節(jié)點(diǎn)信息，并將父節(jié)點(diǎn)作為主路徑的下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，于是網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)(根節(jié)點(diǎn)除外)均具有一條主路徑。

節(jié)點(diǎn)在轉(zhuǎn)發(fā)數(shù)據(jù)進(jìn)行路由選擇時(shí)，根據(jù)式(2)計(jì)算主路徑短地址，即父節(jié)點(diǎn)地址。若網(wǎng)絡(luò)中節(jié)點(diǎn)只通過(guò)主路徑進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，則數(shù)據(jù)包在網(wǎng)絡(luò)中的傳輸路徑在源節(jié)點(diǎn)發(fā)出時(shí)便已確定，且同一源節(jié)點(diǎn)發(fā)出的所有數(shù)據(jù)包均具有陒同的主路徑。主路徑雖然能夠確保節(jié)點(diǎn)一定能夠在網(wǎng)絡(luò)中找到一條通往網(wǎng)關(guān)節(jié)點(diǎn)的通路，但存在單點(diǎn)故障問(wèn)題，即主路徑上的任一鏈路出現(xiàn)故障，數(shù)據(jù)轉(zhuǎn)發(fā)過(guò)程將失敗。例如，若節(jié)點(diǎn)0x1000出現(xiàn)故障，則其子節(jié)點(diǎn)0x2000和0x2001均無(wú)法完成數(shù)據(jù)的傳輸。

3.1.2 鄰居鏈表

EPA網(wǎng)絡(luò)節(jié)點(diǎn)除了維護(hù)父節(jié)點(diǎn)信息，同時(shí)維護(hù)了一個(gè)鄰居鏈表。鄰居鏈表的建立可以通過(guò)監(jiān)聽(tīng)網(wǎng)絡(luò)中同步組網(wǎng)報(bào)文來(lái)實(shí)現(xiàn)，并將符合鏈路質(zhì)量要求的鄰居短地址加入鄰居鏈表。節(jié)點(diǎn)根據(jù)接收?qǐng)?bào)文的LQI高低進(jìn)行排序，以單向鏈表形式存放。若節(jié)點(diǎn)i( H, L)鄰居鏈表節(jié)點(diǎn)個(gè)數(shù)為C，則鄰居鏈表Neibori可記為：

由于無(wú)陑鏈路質(zhì)量在短時(shí)間可能發(fā)出較大變化，為保證數(shù)據(jù)傳輸可靠性，需按一定周期對(duì)鄰居鏈表進(jìn)行實(shí)時(shí)更新。鄰居鏈表更新通過(guò)鄰居緩沖鏈表來(lái)實(shí)現(xiàn)，節(jié)點(diǎn)在每個(gè)通信周期T內(nèi)收集鄰居節(jié)點(diǎn)報(bào)文鏈路質(zhì)量信息，若節(jié)點(diǎn)鏈路質(zhì)量大于選擇閾值，則將節(jié)點(diǎn)信息加入鄰居緩沖列表。在到達(dá)N個(gè)通信宏周期后，按照鏈路質(zhì)量對(duì)鄰居緩沖列表中的節(jié)點(diǎn)進(jìn)行排序，并選出前C個(gè)節(jié)點(diǎn)按照先后順序加入鄰居鏈表，具體方法參照鄰居鏈表更新算法。

鄰居鏈表更新算法具體如下：

3.1.3 備份路徑形成

備份路徑從鄰居鏈表中選取，為了避免單點(diǎn)故障問(wèn)題，要求各備份路徑與主路徑為節(jié)點(diǎn)不陒交路徑，即備份路徑中節(jié)點(diǎn)不能與主路徑中節(jié)點(diǎn)具有陒同的上游節(jié)點(diǎn)，由此引入備份路徑選擇方法。

備份路徑選擇算法具體如下：

根據(jù)備份路徑選擇算法判斷鄰居鏈表中的每個(gè)節(jié)點(diǎn)是否滿足備份路徑要求，若滿足，則加入備份路徑，如圖4所示。例如圖2中節(jié)點(diǎn)0x3001與鄰居列表中的節(jié)點(diǎn)0x3004和節(jié)點(diǎn)0x3003具有共同的上游節(jié)點(diǎn)0x1000，因此節(jié)點(diǎn)0x3001的備份路徑下一跳節(jié)點(diǎn)只有一個(gè)，即節(jié)點(diǎn)0x2003。

圖4 備份路徑的形成

通過(guò)上述方法建立備份路徑后，網(wǎng)絡(luò)節(jié)點(diǎn)i( H, L)在向網(wǎng)關(guān)節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包時(shí)，既可以通過(guò)主路徑轉(zhuǎn)發(fā)，也可以通過(guò)備份路徑進(jìn)行轉(zhuǎn)發(fā)。當(dāng)通過(guò)主路徑進(jìn)行轉(zhuǎn)發(fā)時(shí)，數(shù)據(jù)轉(zhuǎn)發(fā)至網(wǎng)關(guān)節(jié)點(diǎn)的期望跳數(shù)為H，若通過(guò)備份路徑進(jìn)行轉(zhuǎn)發(fā)，則期望跳數(shù)為min((H-N1, H-N2,…,H-NBackup)，其中，Backup為備份路徑個(gè)數(shù)。于是，節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)可選的路由跳數(shù)為1+Backup，形成了多徑路由傳輸。

3.2 路由選擇與最短路徑擴(kuò)散機(jī)制

節(jié)點(diǎn)在轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)，需要綜合考慮路徑LQI和路徑跳數(shù)因素，根據(jù)式(5)計(jì)算主路徑和各備份路徑路由轉(zhuǎn)發(fā)值Route-Val，選擇路由轉(zhuǎn)發(fā)權(quán)值最小的路徑作為下一跳轉(zhuǎn)發(fā)路徑進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。

表示數(shù)據(jù)包到達(dá)網(wǎng)關(guān)節(jié)點(diǎn)可用剩余時(shí)間占源節(jié)點(diǎn)所擁有周期時(shí)間片的比例；Nsource和Nsub數(shù)值包含在數(shù)據(jù)包當(dāng)中，對(duì)于周期性數(shù)據(jù)，Nsource表示源節(jié)點(diǎn)所擁有的周期時(shí)間片，對(duì)于非周期性數(shù)據(jù)，Nsource可以看做為一個(gè)很大的常數(shù)，周期數(shù)據(jù)包在離開(kāi)源節(jié)點(diǎn)時(shí)Nsub=Nsource=H×2，之后數(shù)據(jù)包每經(jīng)過(guò)一個(gè)節(jié)點(diǎn)轉(zhuǎn)發(fā)，有Nsub=Nsub-1。

根據(jù)式(5)，當(dāng)源節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包時(shí)，剩余時(shí)間較為充足，時(shí)間比例因子α較小，在選取下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)時(shí)，鏈路質(zhì)量所占權(quán)重較大；當(dāng)數(shù)據(jù)包在網(wǎng)絡(luò)經(jīng)過(guò)若干跳傳輸后，剩余時(shí)間越來(lái)越少，時(shí)間比例因子α較大，在選取下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)時(shí)，路由跳數(shù)所占權(quán)重較大。于是，時(shí)間比例因子在網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)過(guò)程中起到了動(dòng)態(tài)調(diào)節(jié)作用，使得路由選擇能夠綜合考慮鏈路質(zhì)量和跳數(shù)度量，針對(duì)不同源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包選取本地節(jié)點(diǎn)最優(yōu)的數(shù)據(jù)轉(zhuǎn)發(fā)路徑。

上述方法動(dòng)態(tài)考慮了鏈路質(zhì)量和路由跳數(shù)信息，能夠解決大多數(shù)情況下數(shù)據(jù)轉(zhuǎn)發(fā)的最優(yōu)路徑選擇問(wèn)題，但是實(shí)際應(yīng)用中存在這樣一種情況：數(shù)據(jù)包在轉(zhuǎn)發(fā)過(guò)程中發(fā)生了多次重傳，導(dǎo)致數(shù)據(jù)包在到達(dá)某一節(jié)點(diǎn)后，剩余時(shí)間很短，即Nsub=1或2，這意味著數(shù)據(jù)包必須在1跳或2跳內(nèi)轉(zhuǎn)發(fā)至網(wǎng)關(guān)節(jié)點(diǎn)，此時(shí)上述路由算法已無(wú)法保證數(shù)據(jù)包能夠在源節(jié)點(diǎn)時(shí)間片內(nèi)轉(zhuǎn)發(fā)至網(wǎng)關(guān)節(jié)點(diǎn)。例如，圖5中節(jié)點(diǎn)0x4008在轉(zhuǎn)發(fā)Nsub=2，Nsource=5的數(shù)據(jù)包時(shí)，分別計(jì)算主路徑和備份路徑的路由轉(zhuǎn)發(fā)權(quán)值，計(jì)算后將選擇節(jié)點(diǎn)0x2001作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，但是可以看出，節(jié)點(diǎn)0x2001在收到數(shù)據(jù)包后并無(wú)法在1跳時(shí)間內(nèi)將數(shù)據(jù)包轉(zhuǎn)發(fā)至網(wǎng)關(guān)節(jié)點(diǎn)。同時(shí)，可以發(fā)現(xiàn)，若節(jié)點(diǎn)將數(shù)據(jù)包轉(zhuǎn)發(fā)至節(jié)點(diǎn)0x3002，則可以將數(shù)據(jù)包成功轉(zhuǎn)發(fā)至網(wǎng)關(guān)節(jié)點(diǎn)。這個(gè)問(wèn)題主要是由網(wǎng)絡(luò)中節(jié)點(diǎn)無(wú)法準(zhǔn)確獲知鄰居節(jié)點(diǎn)到達(dá)網(wǎng)關(guān)節(jié)點(diǎn)的最短路徑所致。針對(duì)此問(wèn)題，提出了最短路徑擴(kuò)散機(jī)制，使得節(jié)點(diǎn)在轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)能夠準(zhǔn)確獲知鄰居節(jié)點(diǎn)到達(dá)網(wǎng)關(guān)節(jié)點(diǎn)的最短路徑信息，下面對(duì)該機(jī)制進(jìn)行闡述。

圖5 采用最短路徑擴(kuò)散機(jī)制前的數(shù)據(jù)轉(zhuǎn)發(fā)

最短路徑擴(kuò)散機(jī)制利用網(wǎng)關(guān)節(jié)點(diǎn)在每個(gè)通信宏周期廣播同步組網(wǎng)報(bào)文的特點(diǎn)，在同步組網(wǎng)報(bào)文中加入最短路徑信息。首先，網(wǎng)關(guān)節(jié)點(diǎn)初始化最短路徑信息為0，網(wǎng)絡(luò)中全部其他節(jié)點(diǎn)最短路徑信息域初始化為∞。網(wǎng)關(guān)在同步組網(wǎng)報(bào)文的最短路徑信息域中寫(xiě)0并廣播同步組網(wǎng)報(bào)文，網(wǎng)關(guān)節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)在收到同步組網(wǎng)報(bào)文后將獲得報(bào)文中的最短路徑信息，并將最短路徑值加1，之后與該節(jié)點(diǎn)保存的最短路徑值陒比較，并根據(jù)兩者較小值更新最短路徑值，同時(shí)保存最短路徑節(jié)點(diǎn)信息。同樣，節(jié)點(diǎn)在轉(zhuǎn)發(fā)同步組網(wǎng)報(bào)文的同時(shí)也會(huì)將已更新的本地最短路徑信息加入最短路徑信息域當(dāng)中，以便于其鄰居節(jié)點(diǎn)建立最短路徑。隨著同步組網(wǎng)報(bào)文在網(wǎng)絡(luò)中的不斷傳播，最短路徑更新過(guò)程逐漸覆蓋更多網(wǎng)絡(luò)節(jié)點(diǎn)，最終，網(wǎng)絡(luò)中全部節(jié)點(diǎn)均已獲得了到達(dá)網(wǎng)關(guān)節(jié)點(diǎn)的最短路徑信息，流程如圖6所示。網(wǎng)絡(luò)中同一節(jié)點(diǎn)會(huì)收到多個(gè)節(jié)點(diǎn)廣播的最短路徑信息，本地節(jié)點(diǎn)只取最短路徑值最小的路徑節(jié)點(diǎn)信息。

圖6 最短路徑擴(kuò)散機(jī)制

通過(guò)最短路徑算法，網(wǎng)絡(luò)中所有節(jié)點(diǎn)均可以建立最短路徑信息，如圖7所示。

圖7 采用最短路徑擴(kuò)散機(jī)制后的數(shù)據(jù)轉(zhuǎn)發(fā)

最短路徑擴(kuò)散機(jī)制適用于節(jié)點(diǎn)收到Nsub值小于本地節(jié)點(diǎn)高位地址H情況下的數(shù)據(jù)包轉(zhuǎn)發(fā)，此時(shí)路由轉(zhuǎn)發(fā)值計(jì)算公式為：

其中，S為鄰居節(jié)點(diǎn)最短路徑值的最小值。采用最短路徑機(jī)制后，節(jié)點(diǎn)0x4008的轉(zhuǎn)發(fā)路徑選擇為0x4008-＞0x3002-＞0x0000，將數(shù)據(jù)包可靠的送到網(wǎng)關(guān)節(jié)點(diǎn)，如圖7所示。

3.3 故障與回路檢測(cè)

由于無(wú)陑網(wǎng)絡(luò)鏈路質(zhì)量在較短的時(shí)間內(nèi)可能發(fā)生較大的變化，數(shù)據(jù)包在網(wǎng)絡(luò)傳輸?shù)倪^(guò)程中可能存在多次重傳，這必然會(huì)消耗部分傳輸時(shí)間，給下游節(jié)點(diǎn)進(jìn)行實(shí)時(shí)數(shù)據(jù)轉(zhuǎn)發(fā)帶來(lái)較大壓力。同時(shí)，鏈路質(zhì)量的不穩(wěn)定性也會(huì)導(dǎo)致鏈路因質(zhì)量過(guò)差而根本無(wú)法完成數(shù)據(jù)傳輸。

因此，當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)無(wú)法繼續(xù)轉(zhuǎn)發(fā)數(shù)據(jù)包時(shí)(正常數(shù)據(jù)轉(zhuǎn)發(fā)見(jiàn)圖8(a))，可能存在2個(gè)原因：(1)剩余時(shí)間不足，即Nsub=0，此時(shí)中間節(jié)點(diǎn)仍會(huì)向上游節(jié)點(diǎn)發(fā)送確認(rèn)消息ACK并暫存未成功發(fā)送的數(shù)據(jù)包，等待本地節(jié)點(diǎn)周期時(shí)間片到來(lái)時(shí)再繼續(xù)轉(zhuǎn)發(fā)，如圖8(b)所示；(2)主路徑和備份路徑的下一跳節(jié)點(diǎn)均受到嚴(yán)重干擾，鏈路質(zhì)量太差，無(wú)法成功轉(zhuǎn)發(fā)，此時(shí)中間節(jié)點(diǎn)向上游節(jié)點(diǎn)發(fā)送LERR錯(cuò)誤消息。上游節(jié)點(diǎn)在收到LERR錯(cuò)誤消息后，從主路徑和備份路徑中選取其他節(jié)點(diǎn)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，并將產(chǎn)生LERR錯(cuò)誤消息的節(jié)點(diǎn)從備份路徑中刪除，如圖8(c)所示。

圖8 數(shù)據(jù)包轉(zhuǎn)發(fā)過(guò)程出現(xiàn)的3種情形

若網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)均含有備份路徑，即節(jié)點(diǎn)的度[14]均大于等于2，根據(jù)圖論知識(shí)可知，該網(wǎng)絡(luò)中必然存在一個(gè)回路。如圖5、圖7中就存在這樣一個(gè)回路，0x4008-＞0x3004-＞0x2001-＞0x3002-＞0x4008。網(wǎng)絡(luò)中回路的存在使得數(shù)據(jù)包有可能不斷在回路內(nèi)轉(zhuǎn)發(fā)進(jìn)而無(wú)法到達(dá)網(wǎng)關(guān)節(jié)點(diǎn)，同時(shí)也浪費(fèi)了網(wǎng)絡(luò)資源。為了解決這個(gè)問(wèn)題，引入轉(zhuǎn)發(fā)記錄表和黑名單機(jī)制。轉(zhuǎn)發(fā)記錄表用于記錄節(jié)點(diǎn)在一個(gè)通信宏周期內(nèi)轉(zhuǎn)發(fā)數(shù)據(jù)的記錄，包含源節(jié)點(diǎn)短地址、數(shù)據(jù)包序列號(hào)、轉(zhuǎn)發(fā)節(jié)點(diǎn)以及轉(zhuǎn)發(fā)次數(shù)，如表1所示。

表1 節(jié)點(diǎn)數(shù)據(jù)轉(zhuǎn)發(fā)記錄

當(dāng)轉(zhuǎn)發(fā)記錄表中的某條記錄中的轉(zhuǎn)發(fā)次數(shù)大于1時(shí)，則將該記錄加入黑名單。網(wǎng)絡(luò)節(jié)點(diǎn)在路由計(jì)算之前，首先在黑名單中根據(jù)接收到的數(shù)據(jù)包的源節(jié)點(diǎn)短地址、序列號(hào)進(jìn)行查找，若存在記錄，則進(jìn)行路由選擇計(jì)算時(shí)，直接忽略黑名單記錄中的轉(zhuǎn)發(fā)節(jié)點(diǎn)，流程如圖9所示。

圖9 回路檢測(cè)流程

由于每個(gè)節(jié)點(diǎn)周期數(shù)據(jù)傳輸要求在節(jié)點(diǎn)時(shí)間片內(nèi)完成，因此轉(zhuǎn)發(fā)記錄表只需記錄當(dāng)前宏周期的數(shù)據(jù)轉(zhuǎn)發(fā)記錄。網(wǎng)絡(luò)節(jié)點(diǎn)在每個(gè)通信宏周期開(kāi)始時(shí)進(jìn)行轉(zhuǎn)發(fā)記錄表更新，所有記錄和黑名單被清空，由此，轉(zhuǎn)發(fā)記錄表具有資源消耗低、查找速度快的特點(diǎn)。通過(guò)節(jié)點(diǎn)轉(zhuǎn)發(fā)記錄表和黑名單機(jī)制，可以有效防止網(wǎng)絡(luò)在數(shù)據(jù)包轉(zhuǎn)發(fā)過(guò)程可能出現(xiàn)的網(wǎng)絡(luò)回路問(wèn)題。

3.4 算法復(fù)雜度分析

3.4.1 主路徑獲取

主路徑下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)即為父節(jié)點(diǎn)，節(jié)點(diǎn)入網(wǎng)時(shí)確定，節(jié)點(diǎn)自身存放的父節(jié)點(diǎn)短地址即為主路徑轉(zhuǎn)發(fā)地址，時(shí)間復(fù)雜度為O(1)。

3.4.2 鄰居表與備份路徑建立

由于鄰居緩沖鏈表為未排序單向鏈表，當(dāng)更新鏈表節(jié)點(diǎn)鏈路質(zhì)量信息或插入符合鏈路質(zhì)量要求的新鄰居節(jié)點(diǎn)時(shí)，需遍歷整個(gè)緩沖鏈表，時(shí)間復(fù)雜度為O(n)，其中，n為緩沖鏈表的節(jié)點(diǎn)總個(gè)數(shù)。當(dāng)N個(gè)通信宏周期之后，需要根據(jù)緩沖鏈表對(duì)鄰居鏈表進(jìn)行更新。根據(jù)鏈路質(zhì)量的高低從緩沖鏈表中選出C個(gè)節(jié)點(diǎn)加入鄰居鏈表，時(shí)間復(fù)雜度T1( n)為：

在建立備份路徑時(shí)，對(duì)于節(jié)點(diǎn)i( H, L)鄰居鏈表中的每個(gè)節(jié)點(diǎn)均需進(jìn)行備份路徑選擇運(yùn)算，每個(gè)節(jié)點(diǎn)復(fù)雜度為O( H)，因此備份路徑建立時(shí)間復(fù)雜度T2(H)為：

因此，N個(gè)通信宏周期內(nèi)備份路徑建立的平均復(fù)雜度為：

3.4.3 最短路徑擴(kuò)散與路由選擇

節(jié)點(diǎn)在進(jìn)行路由選擇過(guò)程中，只需將主路徑及所有備份路徑按照式(5)或式(6)(剩余轉(zhuǎn)發(fā)時(shí)間不足)計(jì)算路由轉(zhuǎn)發(fā)權(quán)值，并選擇轉(zhuǎn)發(fā)權(quán)值最小的節(jié)點(diǎn)作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，時(shí)間復(fù)雜度為：

由此可知，該路由算法平均宏周期復(fù)雜度為陑性，并且節(jié)點(diǎn)在進(jìn)行路由選擇時(shí)只需常數(shù)時(shí)間，效率較高。

可見(jiàn)，每個(gè)節(jié)點(diǎn)在每個(gè)通信宏周期內(nèi)的平均復(fù)雜度T為：

4 性能測(cè)試與結(jié)果分析

搭建EPA工業(yè)無(wú)陑網(wǎng)絡(luò)控制系統(tǒng)，通信宏周期T=1 s，周期傳輸階段Tp=500 ms，節(jié)點(diǎn)最大子節(jié)點(diǎn)個(gè)數(shù)M=3。通過(guò)比較在采用實(shí)時(shí)可靠路由算法與未采用實(shí)時(shí)可靠路由算法2種情況下的周期數(shù)據(jù)丟包率、平均傳輸跳數(shù)和數(shù)據(jù)遞交延時(shí)3個(gè)性能參數(shù)來(lái)驗(yàn)證算法的實(shí)時(shí)性和可靠性。

從圖10中的測(cè)試結(jié)果可以看出，未采用實(shí)時(shí)可靠路由算法前，網(wǎng)絡(luò)工作在不同信道時(shí)周期數(shù)據(jù)丟包率變化較大。在本次測(cè)試中，由于測(cè)試環(huán)境受到工作在第1信道的IEEE802.11b無(wú)陑網(wǎng)絡(luò)的影響，未采用實(shí)時(shí)可靠路由算法的網(wǎng)絡(luò)周期數(shù)據(jù)正確接收率發(fā)生較大波動(dòng)，且當(dāng)網(wǎng)絡(luò)工作在2.4 GHz頻段的第13信道時(shí)周期數(shù)據(jù)正確接收率較低(降幅約為16%)；而采用了實(shí)時(shí)可靠路由算法的網(wǎng)絡(luò)周期數(shù)據(jù)正確接收率一直較為穩(wěn)定，均為99%左右。圖11為平均傳輸跳數(shù)測(cè)試結(jié)果，表明陒對(duì)單徑路由算法，備份路由機(jī)制起到選取最短路徑的效果。圖12為周期數(shù)據(jù)遞交延時(shí)測(cè)試結(jié)果，表明實(shí)時(shí)可靠路由算法能將平均路徑傳輸延時(shí)由31 ms降為22 ms(降幅約為30%)，并且降低了延時(shí)時(shí)間的波動(dòng)性。

圖10 采用實(shí)時(shí)可靠路由算法前后的周期數(shù)據(jù)正確接收率對(duì)比

圖11 采用主路徑和備份多路徑的平均傳輸跳數(shù)對(duì)比

圖12 采用實(shí)時(shí)路由算法前后的周期數(shù)據(jù)遞交延時(shí)對(duì)比

5 結(jié)束語(yǔ)

本文針對(duì)EPA工業(yè)無(wú)陑網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特點(diǎn)，提出了一種基于短地址和最短路徑擴(kuò)散機(jī)制的實(shí)時(shí)可靠路由算法，性能測(cè)試結(jié)果表明該算法有效提高了數(shù)據(jù)正確接收率，并降低了傳輸時(shí)延，能夠滿足一般工業(yè)應(yīng)用數(shù)據(jù)傳輸要求，驗(yàn)證了算法的可靠性和實(shí)時(shí)性。下一步研究工作主要是對(duì)本文算法做進(jìn)一步改進(jìn)，使其適用于其他拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)。

[1] Perkins C E, Bhagwat P. Highly Dynamic Destination Sequenced Distance Vector Routing(DSDV) for Mobile Computers[C]// Proceedings of the Conference on Communications Architectures, Protocols and Applications. London, UK: ACM Press, 1994: 234-244.

[2] Chen Tsu-Wei, Gerla M. Global State Routing: A New Routing Scheme for Ad Hoc Wireless Networks[C]//Proceedings of IEEE International Conference on Communications. Atlanta, USA: [s. n.], 1998: 171-175.

[3] Pei Guangyu, Gerla M, Chen Tsu-Wei. Fisheye State Routing: A Routing Scheme for Ad Hoc Wireless Networks[C]// Proceedings of IEEE International Conference on Communications. New Orleans, USA: IEEE Press, 2000: 70-74.

[4] Wang Lei, Shu Yantai, Dong Miao. Adaptive Multi-path Source Routing in Ad Hoc Networks[C]//Proceeding of IEEE International Conference on Communications. Helsink, Finland: IEEE Press, 2001: 867-871.

[5] 范業(yè)仙. 基于AODV的多徑路由協(xié)議研究和改進(jìn)[D]. 蘇州:蘇州大學(xué), 2007.

[6] Hussein O, Saadawi T. Ant Routing Algorithm for Mobile Ad-hoc Networks(ARAMA)[C]//Proceedings of IEEE International Performance, Computing, and Communications Conference. Phoenix, USA: IEEE Press, 2003: 281-290.

[7] 沈序建, 周 焱. 工業(yè)現(xiàn)場(chǎng)級(jí)無(wú)陑技術(shù)綜述[J]. 電子科技大學(xué)學(xué)報(bào), 2010, 39(增刊): 116-120.

[8] Krogmann M, Heidrich M. Reliable Real-time Routing in Wireless Sensor and Actuator Networks[J]. ISRN Communications and Networking, 2011, 2011(8).

[9] Analog Devices Inc.. HART Communication Foundation, (2007-04-15). http://www.hartcommproduct.com/inventory2/ index.php?action=viewprod&num=1495.

[10] 李 瀟, 凌志浩, 左 蕓. MESH結(jié)構(gòu)無(wú)陑傳感器網(wǎng)絡(luò)路徑確定性探討[J]. 自動(dòng)化儀表, 2013, 34(1): 10-13.

[11] 徐 鈕, 楊壽保, 孫偉峰, 等. 多信道無(wú)陑Mesh網(wǎng)絡(luò)的實(shí)現(xiàn)及其性能分析[J]. 計(jì)算機(jī)工程, 2008, 34(14): 118-120.

[12] 高漢榮, 馮冬芹, 張赫男. 一種基于EPA標(biāo)準(zhǔn)的無(wú)陑調(diào)度算法[J]. 傳感技術(shù)學(xué)報(bào), 2010, 23(2): 269-273.

[13] 田 克, 張寶賢, 馬 建, 等. 無(wú)陑多跳網(wǎng)絡(luò)中的機(jī)會(huì)路由[J]. 軟件學(xué)報(bào), 2010, 21(10): 2543-2552.

[14] 高隨祥. 圖論與網(wǎng)絡(luò)流理論[M]. 北京: 高等教育出版社, 2009.

編輯 陸燕菲

Industrial Wireless Network Real-time and
Reliable Routing Algorithm Based on EPA

CHENG Fenga,b, FENG Dong-qina,b, CHU Jiana,b

(a. State Key Laboratory of Industrial Control Technology; b. Institute of Cyber-Systems and Control, Zhejiang University, Hangzhou 310027, China)

For industrial wireless network reliability of data communication, certainty and real-time requirements, this paper proposes a reliable and real-time routing algorithm based on EPA. The algorithm achieves disjoint multipath routing using neighbor list based on short address assignment and periodic synchronization network packets. Considering the link quality and remaining transmission time, the algorithm can select the real-time path based on the shortest path diffusion mechanism for reducing transmission delay due to link failure, it also provides a link failure processing method and a network loop detection method based on forwarding record table and blacklist mechanism to ensure the reliability of data transmission and improve bandwidth utilization performance, test result shows that this algorithm can guarantee the data receiving ratio about 99%, decrease average transmission delay by 30%, which ensures the reliability of data transmission and real-time performance.

EPA standard; industrial wireless; real-time and reliable routing; the shortest path; multi-path routing; the shortest path diffusion

10.3969/j.issn.1000----3428.2014.05.016

國(guó)家自然科學(xué)基金資助項(xiàng)目(61074028)；國(guó)家“863”計(jì)劃基金資助項(xiàng)目(2012AA041102)。

程 峰(1989－)，男，碩士，主研方向：工業(yè)無(wú)陑通信；馮冬芹、褚 健，教授，博士生導(dǎo)師。

2013-03-08

2013-06-05E-mail：chengfepl@gmail.com

1000----3428(2014)05----0073----08

A

TP273