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

程 峰，馮冬芹，褚 健

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

1 概述

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

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

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

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

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

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

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

為了實(shí)現(xiàn)網(wǎng)關(guān)節(jié)點(diǎn)對整個網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)據(jù)傳輸過程的監(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)過網(wǎng)關(guān)節(jié)點(diǎn)的轉(zhuǎn)發(fā)才能完成。

2.2 短地址分配

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

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

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

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

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

2.3 信道接入

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

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

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

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

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

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

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

3 路由算法設(shè)計

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

3.1 多徑機(jī)制

在本文路由算法中采用多徑備份路由機(jī)制，即每個網(wǎng)絡(luò)節(jié)點(diǎn)都具有一個主路徑和若干個備份路徑可供選擇，數(shù)據(jù)在同一時刻只通過其中一條路徑進(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ò)中每一個節(jié)點(diǎn)(根節(jié)點(diǎn)除外)均具有一條主路徑。

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

3.1.2 鄰居鏈表

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

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

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

3.1.3 備份路徑形成

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

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

根據(jù)備份路徑選擇算法判斷鄰居鏈表中的每個節(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)只有一個，即節(jié)點(diǎn)0x2003。

圖4 備份路徑的形成

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

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

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

其中，LQI為歸一化后的鏈路質(zhì)量，取值范圍為0～1，LQI越大，說明鏈路質(zhì)量越優(yōu)；為時間比例因子，表示數(shù)據(jù)包到達(dá)網(wǎng)關(guān)節(jié)點(diǎn)可用剩余時間占源節(jié)點(diǎn)所擁有周期時間片的比例；Nsource和Nsub數(shù)值包含在數(shù)據(jù)包當(dāng)中，對于周期性數(shù)據(jù)，Nsource表示源節(jié)點(diǎn)所擁有的周期時間片，對于非周期性數(shù)據(jù)，Nsource可以看做為一個很大的常數(shù)，周期數(shù)據(jù)包在離開源節(jié)點(diǎn)時Nsub=Nsource=H×2，之后數(shù)據(jù)包每經(jīng)過一個節(jié)點(diǎn)轉(zhuǎn)發(fā)，有Nsub=Nsub-1。

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

路由選擇更新算法：

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

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

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

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

通過最短路徑算法，網(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ā)，此時路由轉(zhuǎn)發(fā)值計算公式為：

其中，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 故障與回路檢測

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

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

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

若網(wǎng)絡(luò)中每個節(jié)點(diǎn)均含有備份路徑，即節(jié)點(diǎn)的度[14]均大于等于2，根據(jù)圖論知識可知，該網(wǎng)絡(luò)中必然存在一個回路。如圖5、圖7中就存在這樣一個回路，0x4008->0x3004-> 0x2001->0x3002->0x4008。網(wǎng)絡(luò)中回路的存在使得數(shù)據(jù)包有可能不斷在回路內(nèi)轉(zhuǎn)發(fā)進(jìn)而無法到達(dá)網(wǎng)關(guān)節(jié)點(diǎn)，同時也浪費(fèi)了網(wǎng)絡(luò)資源。為了解決這個問題，引入轉(zhuǎn)發(fā)記錄表和黑名單機(jī)制。轉(zhuǎn)發(fā)記錄表用于記錄節(jié)點(diǎn)在一個通信宏周期內(nèi)轉(zhuǎn)發(fā)數(shù)據(jù)的記錄，包含源節(jié)點(diǎn)短地址、數(shù)據(jù)包序列號、轉(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時，則將該記錄加入黑名單。網(wǎng)絡(luò)節(jié)點(diǎn)在路由計算之前，首先在黑名單中根據(jù)接收到的數(shù)據(jù)包的源節(jié)點(diǎn)短地址、序列號進(jìn)行查找，若存在記錄，則進(jìn)行路由選擇計算時，直接忽略黑名單記錄中的轉(zhuǎn)發(fā)節(jié)點(diǎn)，流程如圖9所示。

圖9 回路檢測流程

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

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

3.4.1 主路徑獲取

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

3.4.2 鄰居表與備份路徑建立

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

本文針對EPA工業(yè)無陑網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特點(diǎn)，提出了一種基于短地址和最短路徑擴(kuò)散機(jī)制的實(shí)時可靠路由算法，性能測試結(jié)果表明該算法有效提高了數(shù)據(jù)正確接收率，并降低了傳輸時延，能夠滿足一般工業(yè)應(yīng)用數(shù)據(jù)傳輸要求，驗(yàn)證了算法的可靠性和實(shí)時性。下一步研究工作主要是對本文算法做進(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 Architec- tures,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 Interna- tional Performance,Computing,and Communications Conference.Phoenix,USA: IEEE Press,2003: 281-290.

[7]沈序建,周 焱.工業(yè)現(xiàn)場級無陑技術(shù)綜述[J].電子科技大學(xué)學(xué)報,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ǎng)絡(luò)路徑確定性探討[J].自動化儀表,2013,34(1): 10-13.

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

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

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

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