謝昊飛，黃榮科，陳良平

(重慶郵電大學(xué)工業(yè)物聯(lián)網(wǎng)與網(wǎng)絡(luò)化控制教育部重點實驗室，重慶 400065)

0 引言

無線傳感器網(wǎng)絡(luò)［1－2］是由大量部署在特定區(qū)域具有無線通信能力的微型傳感器以自組織和多跳的方式構(gòu)成的智能網(wǎng)絡(luò)系統(tǒng)。其意義在于能夠協(xié)作地感知、采集、處理和傳輸網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)被感知對象的信息。目前，無線傳感器網(wǎng)絡(luò)廣泛應(yīng)用于智能交通、環(huán)境監(jiān)測、軍事安全、智能家居、現(xiàn)代農(nóng)業(yè)、醫(yī)療健康、航天航空等眾多領(lǐng)域。

ISA100.11a［3－4］標(biāo)準(zhǔn)是由 ISA100 協(xié)會定義，旨在工業(yè)無線傳感網(wǎng)標(biāo)準(zhǔn)，為目前工業(yè)無線領(lǐng)域國際三大標(biāo)準(zhǔn)之一。長期以來，無線傳感器網(wǎng)絡(luò)路由［5－7］機制的研究一直是一項熱門。大多選擇終端設(shè)備到網(wǎng)關(guān)之間跳數(shù)最短的路徑來傳輸數(shù)據(jù)，但是，在工業(yè)無線應(yīng)用環(huán)境中，跳數(shù)最短的路徑并不能保證數(shù)據(jù)的可靠傳輸，而且如果頻繁使用同一條路徑傳輸，就會造成該路徑上節(jié)點能量消耗過快而過早失效，從而使整個網(wǎng)絡(luò)被分割成互不相連的孤立部分，縮短了整個網(wǎng)路的生存期［8］。文獻［9］提出了一種基于時隙查詢與緩沖隊列的通信調(diào)度方法。文獻［10］提出了一種基于確定性調(diào)度與鏈路質(zhì)量的前k優(yōu)路徑路由算法。但都沒有考慮無線傳感器網(wǎng)絡(luò)中能量局限性的問題。

本文選取網(wǎng)絡(luò)的鏈路質(zhì)量和設(shè)備剩余能量為指標(biāo)，基于改進的 Floyd［11］算法，提出了 ISA－Floyd 路由算法，為ISA100.11a工業(yè)無線網(wǎng)絡(luò)提供了一種良好的路由解決方案。

1 ISA100.11a拓?fù)浣Y(jié)構(gòu)

遵循 ISA100.11a標(biāo)準(zhǔn)，ISA100.11a工業(yè)無線網(wǎng)絡(luò)包括ISA100.11a DL子網(wǎng)和ISA100.11a骨干網(wǎng)。研究的主要對象為ISA100.11a DL子網(wǎng)，不做特別說明，本文的ISA100.11a網(wǎng)絡(luò)指的是ISA100.11a DL子網(wǎng)。ISA100.11a網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可以分為星形網(wǎng)、樹形網(wǎng)和Mesh網(wǎng)。

ISA100.11a網(wǎng)絡(luò)中的設(shè)備包括系統(tǒng)管理器、安全管理器、網(wǎng)關(guān)、路由和終端設(shè)備。在ISA100.11a網(wǎng)絡(luò)的設(shè)備中，路由設(shè)備具有轉(zhuǎn)發(fā)功能，終端設(shè)備沒有轉(zhuǎn)發(fā)功能。終端設(shè)備一般攜帶相關(guān)傳感器，能收集到感興趣的信息。這些信息通過路由設(shè)備最終上傳到網(wǎng)關(guān)。網(wǎng)關(guān)能夠?qū)@些數(shù)據(jù)進行相應(yīng)的處理，執(zhí)行相關(guān)動作。

2 ISA100.11a通信配置

ISA100.11a網(wǎng)絡(luò)采用時分多址(time division multiple access，TDMA)機制，數(shù)據(jù)鏈路(data link，DL)子網(wǎng)中所有設(shè)備之間的數(shù)據(jù)通信都基于超幀結(jié)構(gòu)，系統(tǒng)管理器為設(shè)備分配相應(yīng)的時隙和通信鏈路等通信資源。設(shè)備獲得系統(tǒng)管理器配置的通信資源后，就可以準(zhǔn)確、可靠和實時地傳輸用戶應(yīng)用數(shù)據(jù)。

時隙表示一段時間;超幀指時隙的集合，是一個循環(huán)的時隙表;鏈路指時隙的使用，即描述在一個超幀循環(huán)時間表中重復(fù)發(fā)生特定的活動。每個超幀周期中的時隙數(shù)目決定了該超幀周期的重復(fù)頻率。圖1顯示在一個擁有3個時隙的超幀中設(shè)備的通信情況。

圖1中，超幀循環(huán)在每個超幀周期的第1個時隙，設(shè)備A發(fā)送信息給設(shè)備B;在每個周期的第2個時隙，設(shè)備B發(fā)送信息給設(shè)備C;每個周期的第3個時隙是空閑的(未分配)。每3個時隙，重復(fù)循環(huán)。系統(tǒng)管理器在一組彼此通信設(shè)備間配置匹配的鏈路。在超幀的第1個時隙，系統(tǒng)管理器在設(shè)備A上配置一條鏈路去發(fā)送信息給設(shè)備B;在同一時隙，給設(shè)備B配置一條鏈路去偵聽信息。在超幀的第2個時隙，系統(tǒng)管理器在設(shè)備B上配置一條鏈路去發(fā)送信息給設(shè)備C;在同一時隙，給設(shè)備C配置一條鏈路去偵聽信息。系統(tǒng)管理器配置網(wǎng)絡(luò)中設(shè)備的時隙和鏈路進行相互配合操作，使得系統(tǒng)穩(wěn)定運行。

圖1 超幀、鏈路、路由關(guān)系Fig.1 Relationship of superframe，link and route

超幀和鏈路作為單獨的但相關(guān)的可配置實體，實際上它們是相互依賴、相互對應(yīng)、相互配合的。圖1說明了這種對應(yīng)關(guān)系和相互結(jié)構(gòu)，解釋了超幀、鏈路和路由的區(qū)別與聯(lián)系。

圖1中，時隙0和時隙1對應(yīng)下的2條相關(guān)鏈路就形成了設(shè)備A到設(shè)備C的路由，路由是本文主要研究的對象。鏈路的配置依賴于路由算法，良好的路由算法能使鏈路高效可靠地傳輸數(shù)據(jù)。

ISA100.11a系統(tǒng)通信配置主要包括ISA100.11a設(shè)備的超幀、時隙、模板等。系統(tǒng)管理器通過合約服務(wù)來進行這些通信配置。合約是ISA100.11a系統(tǒng)管理器與設(shè)備之間達(dá)成的一致協(xié)定，用來建立和支持ISA100.11a設(shè)備之間的通信路徑以滿足應(yīng)用進程的通信需求。設(shè)備的應(yīng)用進程需要同另一個設(shè)備的應(yīng)用進程通信時，這個設(shè)備應(yīng)該首先向系統(tǒng)管理器申請?zhí)囟ǖ暮霞s。系統(tǒng)管理器通過建立、維護、修改和終止合約來執(zhí)行網(wǎng)絡(luò)中設(shè)備之間交互操作。

3 路由設(shè)計

ISA100.11a網(wǎng)絡(luò)中，未加入ISA100.11a網(wǎng)絡(luò)的設(shè)備通過已經(jīng)入網(wǎng)的代理設(shè)備加入網(wǎng)絡(luò)，其路由是依賴于已加入網(wǎng)絡(luò)的代理設(shè)備，所以，ISA100.11a網(wǎng)絡(luò)中的路由算法著重在設(shè)備入網(wǎng)后系統(tǒng)管理器分配的鏈路情況上。

3.1 選路依據(jù)

鏈路質(zhì)量。在ISA100.11a網(wǎng)絡(luò)中，鏈路質(zhì)量一定意義上決定了數(shù)據(jù)傳輸?shù)目煽啃裕溌焚|(zhì)量的好壞往往與重傳次數(shù)、網(wǎng)絡(luò)的流量控制息息相關(guān)。

ISA100.11a設(shè)備掃描鄰居設(shè)備收集鏈路質(zhì)量。當(dāng)設(shè)備收到數(shù)據(jù)幀和確認(rèn)幀時，記錄下該數(shù)據(jù)對應(yīng)的接收信號強度指示(received signal strength indication，RSSI)和相關(guān)值循環(huán)冗余校驗碼(cyclic redundancy check，CRC)，設(shè)備解析數(shù)據(jù)幀時取出尾部相關(guān)值，計算出鏈路質(zhì)量 (link quality indicator，LQI)值，并存入設(shè)備的鄰居表中。設(shè)備周期上傳鄰居表給系統(tǒng)管理器，系統(tǒng)管理器收到設(shè)備與其鄰居設(shè)備的鏈路質(zhì)量LQI值，存儲在相關(guān)表項中，作為路由選擇時的依據(jù)。

剩余能量。ISA100.11a網(wǎng)絡(luò)中的節(jié)點使用電池供電，能量有限。如果某條路徑上的節(jié)點頻繁、超負(fù)荷的工作而使能量過低時，整條路徑都會失效。當(dāng)網(wǎng)絡(luò)中有多條路徑失效后，剩余節(jié)點會變成孤立節(jié)點，網(wǎng)絡(luò)結(jié)構(gòu)遭到破壞，引起網(wǎng)絡(luò)失衡，降低了網(wǎng)絡(luò)壽命。此外，當(dāng)節(jié)點的剩余能量偏低時，傳播的數(shù)據(jù)包將變得不可靠。網(wǎng)絡(luò)中節(jié)點能量合理使用能增加網(wǎng)絡(luò)的公平性，延長網(wǎng)絡(luò)的生存周期。

ISA100.11a網(wǎng)絡(luò)設(shè)備往往都是電池供電，網(wǎng)絡(luò)中的各個設(shè)備有不同級別的可用能量。ISA100.11a標(biāo)準(zhǔn)定義了 dlmo.EnergyDesign，dlmo.EnergyLeft屬性。dlmo.EnergyDesign表明了設(shè)備設(shè)計的能量容量，此屬性固定地貫穿設(shè)備的整個生命周期。dlmo.EnergyLeft屬性是一個動態(tài)的只讀屬性，可以用來報告設(shè)備的剩余能量容量。在啟動時通過dlmo.DeviceCapability dlmo.EnergyLeft報告，也可以通過健康報告HRCO定期報告給系統(tǒng)管理器。

3.2 數(shù)值處理

設(shè)備參數(shù)的 LQI值和 EnergyLeft，EnergyDesign最后都上傳到系統(tǒng)管理器。系統(tǒng)管理器首先對這些值做如下處理。

鏈路質(zhì)量處理結(jié)果為

3.3 路由選擇

ISA100.11a系統(tǒng)管理器時刻維持最新的網(wǎng)絡(luò)鏈路質(zhì)量情況和網(wǎng)絡(luò)中節(jié)點剩余能量信息。系統(tǒng)管理器以鏈路質(zhì)量處理結(jié)果LQIRate為權(quán)值，形成整個網(wǎng)絡(luò)的鏈路質(zhì)量鄰接矩陣，建立鏈路質(zhì)量加權(quán)圖。

ISA100.11a網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖2所示。2節(jié)點之間的權(quán)值表示其之間的鏈路質(zhì)量。對于加權(quán)圖G=(V，E，W);V={v1，v2，v3，…，vn}代表網(wǎng)絡(luò)中的節(jié)點;E={e1，e2，e3，…，ek}表示網(wǎng)絡(luò)中節(jié)點之間的鏈路。W(vi，vj)表示2節(jié)點之間該鏈路上的鏈路質(zhì)量權(quán)值。ISA100.11a網(wǎng)絡(luò)中2節(jié)點之間有2條方向相反的鏈路，一般認(rèn)為這2條鏈路的鏈路質(zhì)量相等。

圖2 拓?fù)浣Y(jié)構(gòu)圖Fig.2 Topology structuremap

圖2中，網(wǎng)絡(luò)中共有9個設(shè)備，因此，可以用9×9的鄰接矩陣表示，2節(jié)點不連接的鏈路設(shè)定其權(quán)值為0，節(jié)點本身之間權(quán)值為無窮大∞，其鄰接矩陣為

借助Floyd算法的思想，本文在文獻［11］基礎(chǔ)上，提出了在如矩陣H所示的帶有鏈路質(zhì)量權(quán)值的鄰接矩陣中尋找2節(jié)點之間最優(yōu)路徑的方法。不同于文獻［11］中求取2節(jié)點之間權(quán)值的最小值，對于ISA100.11a網(wǎng)絡(luò)中的節(jié)點u和 v，需要尋找到2節(jié)點之間鏈路權(quán)值的最大值。判斷是否存在一個節(jié)點w使得從u到w再到v的鏈路質(zhì)量權(quán)值比已知的權(quán)值更大，這里的判斷依據(jù)是將uw，wv這2個權(quán)值乘積再開方與uv權(quán)值做大小的比較，如果是，就更新它。在這之前先要做一些文獻［11］中未考慮完備的預(yù)處理:首先，判斷要插入的節(jié)點不能是節(jié)點u和v，如果是，則跳到下一個節(jié)點;其次，判斷要插入節(jié)點到節(jié)點u和節(jié)點v之間是否可到達(dá)，即判斷插入節(jié)點到節(jié)點u和節(jié)點v之間的距離是否為0，如果為0，則跳到下一節(jié)點;最后，判斷要插入節(jié)點分別到節(jié)點和節(jié)點v的距離是否小于節(jié)點u，v之間的距離，如果都小于，則考慮下一節(jié)點。

具體實現(xiàn)方法如下:

上面方法實現(xiàn)了在帶有鏈路質(zhì)量權(quán)值的鄰接矩陣尋找最優(yōu)路徑的方法。ISA－Floyd路由算法對于能量的考慮是將剩余能量做分級處理，這樣能有效地平均網(wǎng)絡(luò)能量消耗，從而延長網(wǎng)絡(luò)生命周期。由于設(shè)備沒有路由的轉(zhuǎn)發(fā)功能，所以，路由和設(shè)備用一個Bool標(biāo)志位IsRouter來區(qū)別。路由和設(shè)備在選路的時候區(qū)別處理。ISA－Floyd路由算法的具體實現(xiàn)流程如圖3所示。

首先，設(shè)定能量等級為最高級等級1，在以鏈路質(zhì)量為權(quán)值的鄰接矩陣中，當(dāng)存在節(jié)點能量低于該等級時，將該節(jié)點及其相對應(yīng)的鄰接關(guān)系從鄰接矩陣中刪除。運算Floyd改進算法，找到最優(yōu)路徑。如果沒有找到合適的路徑，則將能量等級降低一級后，再重新按照鏈路質(zhì)量權(quán)值選擇路徑，直至能量等級降到最低等級。

4 路由算法測試

本文的測試方法是搭建ISA100.11a工業(yè)無線網(wǎng)絡(luò)測試平臺。分別在系統(tǒng)管理器中使用 ISAFloyd路由算法和 ISA－k 優(yōu)路徑路由算法［10］以及ISA－時隙調(diào)度方法［9］3種路由方法，其他條件一定的3次測試，對比3次結(jié)果中的網(wǎng)絡(luò)剩余能量、數(shù)據(jù)分組投遞率、數(shù)據(jù)傳輸平均時延。

圖3 路由算法流程圖Fig.3 Flow chart of routing algorithm

本文搭建的測試系統(tǒng)由1個網(wǎng)關(guān)，6個路由器，10個終端設(shè)備和1臺電腦組成。更多終端節(jié)點可以根據(jù)測試需要添加。本測試系統(tǒng)將系統(tǒng)管理器集成到網(wǎng)關(guān)，本測試系統(tǒng)的路由算法也即是在網(wǎng)關(guān)上實現(xiàn)。本測試系統(tǒng)的終端設(shè)備包括智能電表、二氧化硫傳感器、煙霧傳感器、閥門定位器、一氧化碳傳感器、甲烷傳感器、溫濕度傳感器、粉塵傳感器、壓力變送器。終端設(shè)備每隔200 ms向網(wǎng)關(guān)傳輸一次現(xiàn)場數(shù)據(jù)，網(wǎng)關(guān)每隔200 ms就向設(shè)備傳輸一次控制數(shù)據(jù)，路由器負(fù)責(zé)轉(zhuǎn)發(fā)數(shù)據(jù)。在測試系統(tǒng)中，時隙長度為10 ms，超幀長度設(shè)定為20。

網(wǎng)絡(luò)剩余能量是網(wǎng)絡(luò)生存的關(guān)鍵因數(shù)，較小的能量消耗是衡量路由算法的重要指標(biāo)，圖4是ISAFloyd和ISA－k優(yōu)路徑以及ISA－時隙調(diào)度方法3種路由方法的網(wǎng)絡(luò)剩余能量曲線圖。從圖4可以看出，ISA－Floyd將能量分等級處理，在任意時刻網(wǎng)絡(luò)剩余能量多于ISA－k優(yōu)路徑和ISA－時隙調(diào)度方法，在整體上延長了網(wǎng)絡(luò)的生命時間。隨著時間的推移，網(wǎng)絡(luò)剩余能量呈銳減趨勢。這是由于在網(wǎng)絡(luò)生存的后期，隨著節(jié)點剩余能量減少，尋找路徑變得困難，傳輸?shù)目煽啃越档?，重傳次?shù)增多，能量消耗過快?？梢钥闯觯琁SA－Floyd路由算法明顯延長了網(wǎng)絡(luò)的生存時間。

圖4 網(wǎng)絡(luò)剩余能量曲線圖Fig.4 Curve graph of network residual energy

圖5是 ISA－Floyd 和 ISA－k 優(yōu)路徑以及 ISA－時隙調(diào)度方法3種路由方法的數(shù)據(jù)分組投遞率曲線圖。數(shù)據(jù)分組投遞率(packet delivery ratio，PDR)是一定時間內(nèi)正確接收的報文數(shù)量與發(fā)送報文總量的比值，反映了網(wǎng)絡(luò)傳輸?shù)目煽啃?。ISA－Floyd路由算法和ISA－k優(yōu)路徑算法都是基于鏈路質(zhì)量考慮，這2種算法的分組投遞率明顯優(yōu)于ISA－時隙調(diào)度方法。ISA－Floyd路由算法考慮鏈路質(zhì)量，能有效地提高數(shù)據(jù)傳輸可靠性。

圖6是 ISA－Floyd 和 ISA－k 優(yōu)路徑以及 ISA－時隙調(diào)度方法3種路由方法數(shù)據(jù)傳輸平均時延曲線圖。ISA－k優(yōu)路徑算法基于時隙偏移的考慮，數(shù)據(jù)傳輸延時較小好。對于無線傳感器網(wǎng)絡(luò)中的路由協(xié)議，端到端平均時延越低越好。ISA－Floyd路由協(xié)議數(shù)據(jù)傳輸延時處在50ms內(nèi)，對網(wǎng)絡(luò)的影響在可控范圍內(nèi)，能夠滿足應(yīng)用要求。

5 結(jié)束語

本文設(shè)計了一種適用于ISA100.11a工業(yè)無線網(wǎng)絡(luò)的路由算法ISA－Floyd，并搭建測試系統(tǒng)，與傳統(tǒng)路由算法進行了比較，測試結(jié)果驗證了該算法的可行性和優(yōu)勢。ISA100.11a系統(tǒng)管理器能量、資源充分、處理速度快，將 ISA－Floyd算法應(yīng)用在ISA100.11a系統(tǒng)管理器中，能夠得到很好的支持。本文中能量的處理可能有其他更好的方式，路由的效率需要更進一步的改進提高。

圖5 數(shù)據(jù)分組投遞率曲線圖Fig.5 Curve graph of packet delivery ratio

［1］王平.測量與控制用無線通信技術(shù)［M］.北京:電子工業(yè)出版社，2008:229－224.

WANG Ping.Measurement and control in wireless communication technologies［M］.Beijing:Electronic Industry Press，2008:229－224.

［2］孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社，2005:109－132.

SUN Liming，LI Jianzhong，CHENG Yu，et al.Wireless Sensor Network［M］.Beijing:Tsinghua University Press，2005:109－132.

［3］ISA Std.100.11a.Wireless Systems for Industrial Automation:Process Control and Related Applications［S］.U－nited States of America:［s.n.］，2009.

［4］王平，王泉，王恒，等.工業(yè)無線技術(shù)ISA100.11a的現(xiàn)狀與發(fā)展［J］. 中國儀器儀表，2009(10):59－63.

WANG Ping，WANG Quan，WANG Heng，et al.Overview and Analysis of the IndustrialWireless Technology ISA100.11a［J］.Chinese instrument，2009(10):59－63.

［5］KEMAL Akkaya，MOHAMED Younis.A survey on routing protocols for wireless sensor networks［J］.Ad Hoc Networks，2005，3(3):325－349.

［6］HONG Li，HUANG Tingpei，ZHOU Weixia，et al.Research of AODV routing protocol based on link availability prediction［J］.Journal on Communications，2008，29(7):118－123.

［7］ALKARAKI JN，KAMAL A E.Routing Techniques in－Wireless Sensor Networks:A Survey［J］.IEEEWireless Communications，2004，11(6):6－28.

［8］王良民，廖聞劍.無線傳感器網(wǎng)絡(luò)可生存理論與技術(shù)研究［M］.北京:人民郵電出版社.2011:1－7.

WANG Liangmin，LIAO Wenjian.Survival Theory and Technology Research in Wireless Sensor Network［M］.Beijing:People’s Posts and Telecommunications Press.2011:1－7.

［9］王平，劉其琛，王恒，等.一種適用于ISAl00.11a工業(yè)無線網(wǎng)絡(luò)的通信調(diào)度方法［J］.儀器儀表學(xué)報，2011，32(5):1189－1195.

WANG Ping，LIU Qichen，WANG Heng，et al.A communication schedule mechanism for ISAl00.11 aIndustrial wireless network［J］.Chinese Journal of Scientific Instrument，2011，32(5):1189－1195.

［10］王恒，李敏，劉其琛，等.一種基于確定性調(diào)度的工業(yè)無線網(wǎng)絡(luò)路由算法［J］.儀器儀表學(xué)報，2011，32(9):1921－1928.

WANG Heng，LIMin，LIU Qichen，et al.Routing algorithm for industrialwireless network based on deterministic scheduling［J］.Chinese Journal of Scientific Instrument，2011，32(9):1921－1928.

［11］張德全，吳果林，劉登峰.最短路問題的Floyd加速算法與優(yōu)化［J］.計算機工程與應(yīng)用，2009，45(17):41－43.

ZHANG Dequan，WU Guolin，LIU Dengfeng.Accelerated and optimized method of Floyd algorithm to find out shortest path［J］.Computer Engineering and Applications，2009，45(17):41－43.

(編輯:劉 勇)