程 峰，馮冬芹，褚 健

(浙江大學(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ù)建立路由信息時(shí)機(jī)的不同，路由協(xié)議可以分為 2類：表驅(qū)動路由和按需數(shù)據(jù)路由。為保證數(shù)據(jù)傳輸可靠性與實(shí)時(shí)性，一般采用表驅(qū)動路由協(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)存儲網(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í)刻傳輸數(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ò)探測機(jī)制[4]，增加了節(jié)點(diǎn)計(jì)算復(fù)雜度，并且多跳路徑并行傳輸增加了網(wǎng)絡(luò)負(fù)載。AOMDV在傳輸數(shù)據(jù)時(shí)只采用一條主路徑，沒有充分利用一次路由發(fā)現(xiàn)所獲取的多徑信息。ARAMA協(xié)議利用路徑信息素來選取多跳路徑中的最短路徑，使得最優(yōu)路徑被選擇的概率不斷增強(qiáng)[6]，為多路徑選擇提供了有益思路?？偟膩碚f，傳統(tǒng)無陑傳感器網(wǎng)絡(luò)路由協(xié)議主要存在如下局限性：(1)未考慮工業(yè)網(wǎng)絡(luò)實(shí)時(shí)性問題，工業(yè)控制應(yīng)用對端到端通信的確定性和實(shí)時(shí)性要求較高[7]。目前已有的多數(shù)多徑路由協(xié)議都不能滿足工業(yè)應(yīng)用對數(shù)據(jù)實(shí)時(shí)性的要求，特別是按需路由協(xié)議雖然節(jié)省了資源消耗，但是帶來了巨大的傳輸延時(shí)，根本無法在工業(yè)無陑網(wǎng)絡(luò)中進(jìn)行直接應(yīng)用。(2)數(shù)據(jù)傳輸可靠性問題，多數(shù)表驅(qū)動路由協(xié)議需要大量路由維護(hù)報(bào)文的支持，當(dāng)網(wǎng)絡(luò)規(guī)模較大時(shí)易造成數(shù)據(jù)擁塞，數(shù)據(jù)包無法實(shí)時(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í)時(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í)時(shí)可靠路由算法奠定基礎(chǔ)，隨后對路由算法進(jìn)行詳細(xì)論述，最后通過周期數(shù)據(jù)正確接收率、數(shù)據(jù)傳輸平均跳數(shù)、數(shù)據(jù)遞交延時(shí)性能參數(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ò)時(shí)根據(jù)物理鏈路質(zhì)量建立邏輯路徑，在邏輯上形成樹狀結(jié)構(gòu)，如圖 1中的節(jié)點(diǎn) A、B、C。同時(shí)，節(jié)點(diǎn)會將本節(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ǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

為了實(shí)現(xiàn)網(wǎng)關(guān)節(jié)點(diǎn)對整個(gè)網(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ò)中的每個(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)的低位決定，可用對序(H,L)表示。設(shè)M為一個(gè)節(jié)點(diǎn)所能擁有的最大子節(jié)點(diǎn)個(gè)數(shù)，對于父節(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)短地址 Fathi(H-Fathi,L-Fathi)為：

當(dāng)M=3時(shí)，一種可能的短地址分配情況如圖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)行，一個(gè)通信宏周期分為2個(gè)傳輸階段，即周期性報(bào)文傳輸階段Tp和非周期性報(bào)文傳輸階段Tn，如圖3所示。

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

周期報(bào)文傳輸階段TP用于傳送對實(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)過網(wǎng)絡(luò)轉(zhuǎn)發(fā)至網(wǎng)關(guān)節(jié)點(diǎn)。下面先對單跳傳輸情況進(jìn)行討論，將單跳數(shù)據(jù)遞交時(shí)間τ分為傳輸時(shí)間t和處理時(shí)間T，計(jì)算公式如下：

其中，tcycle為發(fā)送節(jié)點(diǎn)開始發(fā)送周期性數(shù)據(jù)到接收節(jié)點(diǎn)完成接收所需的平均時(shí)間；tACK為接收節(jié)點(diǎn)開始發(fā)送 ACK報(bào)文到發(fā)送節(jié)點(diǎn)完成接收所需的平均時(shí)間；tacyAnn為發(fā)送節(jié)點(diǎn)開始發(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ǎng)絡(luò)中數(shù)據(jù)傳輸往往需要經(jīng)過多跳轉(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)過的期望跳數(shù)為 H，同時(shí)考慮數(shù)據(jù)傳輸過程的重傳因素，因此，節(jié)點(diǎn)i(H,L)需分配的周期時(shí)間片Ti計(jì)算公式如下：

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

在非周期報(bào)文傳輸階段開始，網(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ǎng)絡(luò)性能[13]。在一個(gè)通信宏周期 T內(nèi)，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都會收到同步組網(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ǎng)絡(luò)不同，工業(yè)無陑網(wǎng)絡(luò)對數(shù)據(jù)傳輸?shù)目煽啃院蛯?shí)時(shí)性有較為苛刻的要求，節(jié)點(diǎn)所發(fā)送的周期性數(shù)據(jù)必須在本節(jié)點(diǎn)所擁有的時(shí)間片 Ti內(nèi)完成數(shù)據(jù)遞交過程。為了保證數(shù)據(jù)傳輸?shù)目煽啃?，減少重傳次數(shù)，必須選擇鏈路質(zhì)量最優(yōu)的路徑進(jìn)行傳輸；為了保證數(shù)據(jù)傳輸在有限的時(shí)間片 Ti內(nèi)完成，又需要選擇遞交時(shí)間較少的路徑。因此，在路由算法設(shè)計(jì)中必須動態(tài)考慮鏈路質(zhì)量指示(LQI)和跳數(shù)2個(gè)路由選擇度量。

3.1 多徑機(jī)制

在本文路由算法中采用多徑備份路由機(jī)制，即每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)都具有一個(gè)主路徑和若干個(gè)備份路徑可供選擇，數(shù)據(jù)在同一時(shí)刻只通過其中一條路徑進(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)只通過主路徑進(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)故障問題，即主路徑上的任一鏈路出現(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)信息，同時(shí)維護(hù)了一個(gè)鄰居鏈表。鄰居鏈表的建立可以通過監(jiān)聽網(wǎng)絡(luò)中同步組網(wǎng)報(bào)文來實(shí)現(xiàn)，并將符合鏈路質(zhì)量要求的鄰居短地址加入鄰居鏈表。節(jié)點(diǎn)根據(jù)接收報(bào)文的LQI高低進(jìn)行排序，以單向鏈表形式存放。若節(jié)點(diǎn)i(H,L)鄰居鏈表節(jié)點(diǎn)個(gè)數(shù)為C，則鄰居鏈表 Neibori可記為：

由于無陑鏈路質(zhì)量在短時(shí)間可能發(fā)出較大變化，為保證數(shù)據(jù)傳輸可靠性，需按一定周期對鄰居鏈表進(jìn)行實(shí)時(shí)更新。鄰居鏈表更新通過鄰居緩沖鏈表來實(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ì)量對鄰居緩沖列表中的節(jié)點(diǎn)進(jìn)行排序，并選出前C個(gè)節(jié)點(diǎn)按照先后順序加入鄰居鏈表，具體方法參照鄰居鏈表更新算法。

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

3.1.3 備份路徑形成

備份路徑從鄰居鏈表中選取，為了避免單點(diǎ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 備份路徑的形成

通過上述方法建立備份路徑后，網(wǎng)絡(luò)節(jié)點(diǎn)i(H,L)在向網(wǎng)關(guān)節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包時(shí)，既可以通過主路徑轉(zhuǎn)發(fā)，也可以通過備份路徑進(jìn)行轉(zhuǎn)發(fā)。當(dāng)通過主路徑進(jìn)行轉(zhuǎn)發(fā)時(shí)，數(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為備份路徑個(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-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í)間比例因子，表示數(shù)據(jù)包到達(dá)網(wǎng)關(guān)節(jié)點(diǎn)可用剩余時(shí)間占源節(jié)點(diǎn)所擁有周期時(shí)間片的比例；Nsource和Nsub數(shù)值包含在數(shù)據(jù)包當(dāng)中，對于周期性數(shù)據(jù)，Nsource表示源節(jié)點(diǎn)所擁有的周期時(shí)間片，對于非周期性數(shù)據(jù)，Nsource可以看做為一個(gè)很大的常數(shù)，周期數(shù)據(jù)包在離開源節(jié)點(diǎn)時(shí)Nsub=Nsource=H×2，之后數(shù)據(jù)包每經(jīng)過一個(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)過若干跳傳輸后，剩余時(shí)間越來越少，時(shí)間比例因子α較大，在選取下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)時(shí)，路由跳數(shù)所占權(quán)重較大。于是，時(shí)間比例因子在網(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)后，剩余時(shí)間很短，即Nsub=1或2，這意味著數(shù)據(jù)包必須在1跳或2跳內(nèi)轉(zhuǎn)發(fā)至網(wǎng)關(guān)節(jié)點(diǎn)，此時(shí)上述路由算法已無法保證數(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ù)包后并無法在 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ǎ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ù)時(shí)能夠準(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)在每個(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)文的最短路徑信息域中寫 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í)也會將已更新的本地最短路徑信息加入最短路徑信息域當(dāng)中，以便于其鄰居節(jié)點(diǎn)建立最短路徑。隨著同步組網(wǎng)報(bào)文在網(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)會收到多個(gè)節(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ā)，此時(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 故障與回路檢測

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

因此，當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)無法繼續(xù)轉(zhuǎn)發(fā)數(shù)據(jù)包時(shí)(正常數(shù)據(jù)轉(zhuǎn)發(fā)見圖 8(a))，可能存在 2個(gè)原因：(1)剩余時(shí)間不足，即Nsub=0，此時(shí)中間節(jié)點(diǎn)仍會向上游節(jié)點(diǎn)發(fā)送確認(rèn)消息ACK并暫存未成功發(fā)送的數(shù)據(jù)包，等待本地節(jié)點(diǎn)周期時(shí)間片到來時(shí)再繼續(xù)轉(zhuǎn)發(fā)，如圖 8(b)所示；(2)主路徑和備份路徑的下一跳節(jié)點(diǎn)均受到嚴(yán)重干擾，鏈路質(zhì)量太差，無法成功轉(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ā)過程出現(xiàn)的3種情形

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

圖9 回路檢測流程

由于每個(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è)通信宏周期開始時(shí)進(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)時(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ù)緩沖鏈表對鄰居鏈表進(jìn)行更新。根據(jù)鏈路質(zhì)量的高低從緩沖鏈表中選出 C個(gè)節(jié)點(diǎn)加入鄰居鏈表，時(shí)間復(fù)雜度T1(n)為：

在建立備份路徑時(shí)，對于節(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)行路由選擇過程中，只需將主路徑及所有備份路徑按照式(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ù)雜度為：

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

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

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

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

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

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

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

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

5 結(jié)束語

本文針對EPA工業(yè)無陑網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特點(diǎn)，提出了一種基于短地址和最短路徑擴(kuò)散機(jī)制的實(shí)時(shí)可靠路由算法，性能測試結(jié)果表明該算法有效提高了數(shù)據(jù)正確接收率，并降低了傳輸時(shí)延，能夠滿足一般工業(yè)應(yīng)用數(shù)據(jù)傳輸要求，驗(yàn)證了算法的可靠性和實(shí)時(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é)報(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ǎng)絡(luò)路徑確定性探討[J].自動化儀表,2013,34(1): 10-13.

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

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

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

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