適用于WirelessHART網(wǎng)絡(luò)中實(shí)現(xiàn)圖路由機(jī)制的R－Dijkstra算法

李世興，王 宏，周桂平

(1.中國科學(xué)院沈陽自動化研究所網(wǎng)絡(luò)化控制系統(tǒng)實(shí)驗(yàn)室，遼寧沈陽 110016;2.中國科學(xué)院大學(xué)，北京 100039;3.國網(wǎng)遼寧省電力有限公司電力科學(xué)研究院，遼寧沈陽 110055)

0 引言

微電子技術(shù)的發(fā)展和無線傳感器網(wǎng)絡(luò)的研究為過程工業(yè)無線化奠定了技術(shù)基礎(chǔ)。工業(yè)過程環(huán)境復(fù)雜，信號采用有線傳輸?shù)姆绞接性靸r(jià)成本高、不易于維護(hù)，線纜易老化、腐蝕等弊端［1］。在此背景下，2007年9月 WirelessHART標(biāo)準(zhǔn)由 HCF(Hart Communication Foundation)發(fā)布，得到了艾默生、西門子等自動化國際巨頭的支持［2］。WirelessHART是一種專門為過程控制領(lǐng)域而設(shè)計(jì)的網(wǎng)絡(luò)通信協(xié)議，其典型的網(wǎng)絡(luò)應(yīng)用如圖1所示。WirelessHART協(xié)議的發(fā)布，放寬了傳統(tǒng)有線HART總線的使用環(huán)境限制，大大增強(qiáng)了工業(yè)無線技術(shù)的應(yīng)用潛力。在WirelessHART網(wǎng)絡(luò)中，路由作為數(shù)據(jù)的傳輸和分發(fā)機(jī)制，是網(wǎng)絡(luò)的一大核心任務(wù)，是不可或缺的。在工業(yè)應(yīng)用現(xiàn)場，網(wǎng)絡(luò)節(jié)點(diǎn)之間無線通信往往受到周圍環(huán)境電磁干擾、信號衰減、信號反射等不利因素影響，對無線傳輸?shù)男阅軒砗艽筇魬?zhàn)。因此，WirelessHART采用圖路由，引入多路徑路由機(jī)制，增強(qiáng)了數(shù)據(jù)傳輸?shù)穆窂饺哂啵源_保數(shù)據(jù)可靠無誤的傳輸。

1 問題描述與研究現(xiàn)狀

圖1 WirelessHART網(wǎng)絡(luò)結(jié)構(gòu)

WirelessHART針對應(yīng)用現(xiàn)場復(fù)雜的工作環(huán)境和高可靠性的應(yīng)用需求［3］，采用mesh網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)［4］。網(wǎng)絡(luò)中的節(jié)點(diǎn)都可以作為路由節(jié)點(diǎn)，都具備發(fā)送和接收的功能，能夠與一個(gè)或者多個(gè)節(jié)點(diǎn)進(jìn)行通信。目前，AODV(反應(yīng)式路由協(xié)議)、OLSR(先應(yīng)式路由協(xié)議)等主流的路由算法，大部分是采用的分布式協(xié)議，路由的計(jì)算選擇過程由數(shù)據(jù)的發(fā)送或者轉(zhuǎn)發(fā)者來承擔(dān)，采用網(wǎng)絡(luò)各個(gè)成員來選擇路由和維護(hù)路由的策略。在一個(gè)WirelessHART網(wǎng)絡(luò)中，網(wǎng)絡(luò)管理者負(fù)責(zé)節(jié)點(diǎn)路由和通信資源的分配管理［5－6］，通過命令將路由信息發(fā)送到網(wǎng)絡(luò)設(shè)備，是一種集中式路由配置方案［7］，而不需要網(wǎng)絡(luò)其他節(jié)點(diǎn)進(jìn)行路由計(jì)算。此外，當(dāng)前主要路由算法集中在單路徑路由的研究，當(dāng)路由路徑上某個(gè)節(jié)點(diǎn)故障時(shí)，通信就要受到影響，也不符合WirelessHART對網(wǎng)絡(luò)的要求。所以，當(dāng)前成熟的路由算法不能直接應(yīng)用于WirelessHART網(wǎng)絡(luò)當(dāng)中。

為保證數(shù)據(jù)傳輸可靠性，在WirelessHART協(xié)議中提出了圖路由的路由機(jī)制。圖路由是一種全冗余的路由機(jī)制，路由中的每一跳至少有兩個(gè)路由選擇，屬于多徑路由［8］，所有的網(wǎng)絡(luò)設(shè)備到目的節(jié)點(diǎn)的路徑通過網(wǎng)絡(luò)子圖來指定。子圖就是連接網(wǎng)絡(luò)節(jié)點(diǎn)的路徑上所有節(jié)點(diǎn)的集合，由網(wǎng)絡(luò)管理者創(chuàng)建和管理，并通知給相關(guān)網(wǎng)絡(luò)節(jié)點(diǎn)。在一個(gè)WirelessHART網(wǎng)絡(luò)中，每個(gè)子圖都有一個(gè)唯一的圖ID號來表示，所有的網(wǎng)絡(luò)節(jié)點(diǎn)都必須預(yù)先配置，該ID指出了下一跳可以選擇的鄰居節(jié)點(diǎn)。網(wǎng)絡(luò)節(jié)點(diǎn)對數(shù)據(jù)進(jìn)行轉(zhuǎn)發(fā)時(shí)，通過數(shù)據(jù)包里面的圖ID域，然后查找自己的圖路由表，找出可以選擇的下一跳的鄰居地址，然后將數(shù)據(jù)通過鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)出去。在圖2的網(wǎng)絡(luò)拓?fù)渲?，?jié)點(diǎn)6要給節(jié)點(diǎn)3、節(jié)點(diǎn)4或者節(jié)點(diǎn)5發(fā)送數(shù)據(jù)，可以使用子圖1或者子圖2。節(jié)點(diǎn)6若要給節(jié)點(diǎn)1或節(jié)點(diǎn)2發(fā)送數(shù)據(jù)，只能通過子圖1。

圖2 圖路由示例圖

雖然WirelessHART給出了圖路由的機(jī)制，但并未給出圖路由的實(shí)現(xiàn)算法。國際上Dust、Nivis等公司已經(jīng)有相關(guān)的WirelessHART產(chǎn)品面世，然而這些公司將相關(guān)的算法作為公司的核心技術(shù)，并沒有公開。當(dāng)前，在圖路由方面的研究有少量的成果，其中孫健波等人指出圖路由在實(shí)時(shí)性和網(wǎng)絡(luò)容量方面比傳統(tǒng)的AODV路由算法有明顯改善［9］。國外的一些學(xué)者提出采用網(wǎng)絡(luò)節(jié)點(diǎn)分層的思想用于實(shí)現(xiàn)圖路由的分配［6］，這需要額外增加節(jié)點(diǎn)的層的信息。黨魁等人采用BFS搜索算法生成子圖，實(shí)現(xiàn)圖路由機(jī)制，但算法不支持節(jié)點(diǎn)逐個(gè)加入［10，11］。黃聰提出了雙樹的策略來實(shí)現(xiàn)圖路由，涉及到網(wǎng)絡(luò)拓?fù)涞姆纸馀c合成，過程較為繁瑣［12］。總體上，該領(lǐng)域可獲得的文獻(xiàn)很少，還處于研究起步階段，有廣闊的研究空間。因此，目前開展WirelessHART圖路由實(shí)現(xiàn)算法的研究是很有必要的。

2 R－Dijkstra算法

根據(jù)WirelessHART網(wǎng)絡(luò)構(gòu)建的過程可以得出，新的節(jié)點(diǎn)要加入網(wǎng)絡(luò)，首先要偵聽已經(jīng)在網(wǎng)設(shè)備廣播出來的廣告包，將偵聽到的發(fā)出廣告包的設(shè)備作為自己的鄰居，然后向網(wǎng)絡(luò)管理者發(fā)送加入請求，并匯報(bào)自己的鄰居信息。網(wǎng)絡(luò)管理者根據(jù)要入網(wǎng)節(jié)點(diǎn)報(bào)告的鄰居信息，采用相應(yīng)的路由算法，生成圖路由信息，形成網(wǎng)絡(luò)拓?fù)?，然后網(wǎng)關(guān)通過命令將圖ID和參考鄰居信息發(fā)送給待加入節(jié)點(diǎn)。在形成網(wǎng)絡(luò)拓?fù)渲?，網(wǎng)絡(luò)管理者采用R－Dijkstra算法來計(jì)算路由信息。

2.1 網(wǎng)絡(luò)模型

假如網(wǎng)絡(luò)中所有節(jié)點(diǎn)用圖中的頂點(diǎn)來表示，節(jié)點(diǎn)之間的鏈接用圖中頂點(diǎn)的有向邊來表示，這樣一個(gè)WirelessHART網(wǎng)絡(luò)可以用一個(gè)有向圖模型G=(V，E)來表達(dá)，其中V表示網(wǎng)絡(luò)中節(jié)點(diǎn)的集合，E為有向邊集合。網(wǎng)絡(luò)中每兩個(gè)節(jié)點(diǎn)之間的鏈接可以賦予權(quán)值 w(i，j)，表示由節(jié)點(diǎn)i到節(jié)點(diǎn)j的鏈接權(quán)值。w(i，j)具體值的計(jì)算可以根據(jù)鏈路質(zhì)量、帶寬等多個(gè)指標(biāo)計(jì)算獲得。為了研究方便，暫且將兩節(jié)點(diǎn)之間是否直接鏈接作為w(i，j)取值依據(jù)，有鏈接的鄰居之間的權(quán)值都為1，否則為無窮大。網(wǎng)絡(luò)管理者根據(jù)節(jié)點(diǎn)加入時(shí)匯報(bào)鄰居信息，構(gòu)建模型圖G，然后采用R－Dijkstra算法，得出待加入節(jié)點(diǎn)的路由信息。

2.2 R －Dijkstra算法

2.2.1 R －Dijkstra算法簡介

Dijkstra算法是由荷蘭計(jì)算機(jī)科學(xué)家Edsger Wybe Dijkstra提出的，在圖論領(lǐng)域有著廣泛的應(yīng)用，是經(jīng)典的最短路徑算法［13］。Dijkstra算法的輸入為一個(gè)非負(fù)權(quán)重的有向圖 。在給定出某個(gè)發(fā)頂點(diǎn)的情況下，該算法能夠找出出發(fā)頂點(diǎn)到圖中其余頂點(diǎn)的最短距離［14］。然而Dijkstra算法得出的結(jié)果是最短的距離和路徑，只有單一路徑，不符合WirelessHART中圖路由機(jī)制的要求，因此提出了基于Dijkstra算法搜索的冗余路徑搜索算法R－Dijkstra算法。它首先根據(jù)冗余度參數(shù)，對待加入節(jié)點(diǎn)匯報(bào)的鄰居進(jìn)行選擇，然后對將每個(gè)選出的鄰居作為出發(fā)頂點(diǎn)，分別采用Dijkstra算法進(jìn)行對目的節(jié)點(diǎn)搜索，得出每條路徑后，最后將待加入節(jié)點(diǎn)分別添加到每條路徑的起點(diǎn)上，這樣就得出了冗余度的圖路由路徑，這些路徑都是待加入節(jié)點(diǎn)到目的節(jié)點(diǎn)冗余的目標(biāo)代價(jià)最小的路由，目標(biāo)代價(jià)可以考慮傳輸跳數(shù)、信號質(zhì)量、節(jié)點(diǎn)能量以及負(fù)載等因素［15－17］，從路由實(shí)時(shí)性考慮［18］，這里采用跳數(shù)作為目標(biāo)代價(jià)。

2.2.2 R －Dijkstra算法描述

在Dijkstra算法中引入冗余度參數(shù)r，表示每個(gè)節(jié)點(diǎn)在路由轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)候可選擇的鄰居個(gè)數(shù)為r個(gè)。在圖G中，由上面模型可知，節(jié)點(diǎn)之間的鏈接情況，可以根據(jù)權(quán)值w(i，j)來確定。

(1)在r個(gè)鄰居節(jié)點(diǎn)中，選擇一個(gè)未被選擇過的節(jié)點(diǎn)作為出發(fā)頂點(diǎn)S，目的頂點(diǎn)為T，距離數(shù)組D用來表示S到其余各節(jié)點(diǎn)的傳輸跳數(shù)，路徑記錄數(shù)組為Path，其中D［i］表示S到節(jié)點(diǎn)i的最短距離，Path［i］表示S到節(jié)點(diǎn)i最短路徑需要經(jīng)過的節(jié)點(diǎn)。

(2)在圖G中，根據(jù)w(i，j)的值，初始化D、Path的值。

(3)從數(shù)組D中選擇值最小的且未被選擇過的頂點(diǎn)X，作為中間節(jié)點(diǎn)，其中X1S，X1T。

(4)令Z^IV且Z構(gòu)S，Z X，則數(shù)組D中S到Z的距離值為D［Z］，其中D的值用D［Z］_new來更新，按照以下策略:

如果發(fā)生D［Z］值發(fā)生變化，則相應(yīng)的Path［Z］做路徑記錄，Path［Z］=X，表示S到Z的最短路徑需要經(jīng)過中間節(jié)點(diǎn)X，即S到X再到Z。

(5)不斷重復(fù)(3)、(4)，直到所有D中的頂點(diǎn)都被選擇過。這時(shí)，所獲得的矩陣D中的值就是從S頂點(diǎn)出發(fā)到網(wǎng)絡(luò)中其余各點(diǎn)的最短距離，目的節(jié)點(diǎn)為T，找出Path［T］中記錄節(jié)點(diǎn)，將其輸出，然后將Path［T］中的結(jié)點(diǎn)作為新的目的節(jié)點(diǎn)賦給T，按照該操作方法，依次循環(huán)逆向輸出Path［T］中記錄的節(jié)點(diǎn)，直到不能取出新的目的節(jié)點(diǎn)T，然后輸出起始節(jié)點(diǎn)S，最后將上述輸出內(nèi)容反序，該路徑就是S到T最短路徑。

(6)如果個(gè)鄰居都已經(jīng)被選擇過，則算法結(jié)束，否則返回步驟(1)。

根據(jù)以上算法描述，可以將這幾個(gè)步驟用流程圖的形式來表示，算法的流程圖如圖3所示。

圖3 R－Dijkstra算法流程圖

2.2.3 R －Dijkstra算法實(shí)現(xiàn)

圖在計(jì)算機(jī)中的存儲有鄰接矩陣、鄰接表、十字鏈表等多種方式。為了圖路由操作方便和節(jié)省空間，本算法數(shù)據(jù)結(jié)構(gòu)吸收了鄰接表的思想，采用鏈表的形式來表示網(wǎng)絡(luò)拓?fù)浜蛨D路由參考鄰居。整個(gè)拓?fù)溆蓤D節(jié)點(diǎn)鏈表構(gòu)成，圖節(jié)點(diǎn)中包含圖ID對應(yīng)的參考鄰居信息。其中，參考鄰居信息為參考鄰居鏈表的頭結(jié)點(diǎn)指針。按照WirelessHART協(xié)議，圖路由數(shù)據(jù)分為上行數(shù)據(jù)和下行數(shù)據(jù)，上行數(shù)據(jù)的目的地址為網(wǎng)關(guān)或網(wǎng)絡(luò)管理者，其余的為下行數(shù)據(jù)，所有上行數(shù)據(jù)采用一個(gè)子圖，因此上行數(shù)據(jù)的圖ID域相同，規(guī)定為0。在路由選擇中，每個(gè)節(jié)點(diǎn)都有該圖ID的參考鄰居集合。設(shè)計(jì)的網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)類型如下:

圖路由參考鄰居的數(shù)據(jù)結(jié)構(gòu)類型如下:

若網(wǎng)絡(luò)中有n個(gè)節(jié)點(diǎn)，則距離數(shù)組D、路徑記錄數(shù)組Path設(shè)計(jì)為n維的數(shù)組，如果S到節(jié)點(diǎn)i不需要繞行其他節(jié)點(diǎn)，則Path［i］置為 NULL。

算法實(shí)現(xiàn)過程如下:

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

由Dijkstra算法的執(zhí)行過程可以得出，Dijkstra算法的復(fù)雜度主要在兩個(gè)循環(huán)中［19］，因此Dijkstra算法的復(fù)雜度為O(n2)。RDijkstra算法在Dijkstra算法基礎(chǔ)上引入了冗余度參數(shù)，以Dijkstra算法為基礎(chǔ)，進(jìn)行了r次循環(huán)。因此，R－Dijkstra算法的復(fù)雜度為O(r′n2)。在實(shí)際應(yīng)用中r的取值是比較小的，WirelessHART規(guī)定r32。由于n相對較大，則r=n，可見該參數(shù)對算法復(fù)雜度的影響不很嚴(yán)重，對于當(dāng)前硬件的運(yùn)算速度是完全可以接受的。

3 算法驗(yàn)證

為了驗(yàn)證算法的效果，選取了一個(gè)一般情況下的WirelessHART應(yīng)用場景，該網(wǎng)絡(luò)拓?fù)淙鐖D4(a)所示。其中節(jié)點(diǎn)1是AP(Access Point)節(jié)點(diǎn)，節(jié)點(diǎn)2～7為WirelessHART網(wǎng)絡(luò)已經(jīng)在網(wǎng)的設(shè)備節(jié)點(diǎn)，它們要向節(jié)點(diǎn)1傳輸測量數(shù)據(jù)和狀態(tài)信息。當(dāng)某時(shí)刻，新的設(shè)備節(jié)點(diǎn)8要加入網(wǎng)絡(luò)，在冗余度參數(shù)r為2的情況下，選取節(jié)點(diǎn)6和節(jié)點(diǎn)7為鄰居節(jié)點(diǎn)，經(jīng)過R－Dijkstra算法運(yùn)算，得出兩條路徑的結(jié)果為8→6→4→1，8→7→5→1，如圖4(b)所示。R－Dijkstra算法在保證路徑冗余的同時(shí)，實(shí)現(xiàn)了以跳數(shù)為指標(biāo)的路徑最優(yōu)，該算法得出的結(jié)果較好的滿足了WirelessHART網(wǎng)絡(luò)的要求。

4 結(jié)束語

WirelessHART協(xié)議中，提出了圖路由的數(shù)據(jù)傳輸方式，并-未給出具體的實(shí)現(xiàn)方法，這就給廣大的研究人員和工程人員提出了研究課題。在本文中描述的R－Dijkstra算法是符合Wire lessHART中規(guī)定的圖路由機(jī)制的一種實(shí)現(xiàn)方法。該方法在吸收了Dijkstra算法的思想和方法步驟的基礎(chǔ)上，針對圖路由的具體特點(diǎn)，滿足了路徑冗余的要求，完成了WirelessHART網(wǎng)絡(luò)中的圖路由路徑分配任務(wù)。通過選取典型應(yīng)用案例，經(jīng)過RDijkstra算法運(yùn)算，從實(shí)際應(yīng)用的角度驗(yàn)證了該算法的有效性。

需要說明的是，上文研究以跳數(shù)作為路徑選擇的目標(biāo)代價(jià)，在此基礎(chǔ)上開展路由優(yōu)化目標(biāo)相關(guān)算法研究，使網(wǎng)絡(luò)更加健壯，是下一步要開展的研究工作。

［1］方原柏.流程行業(yè)無線技術(shù)應(yīng)用發(fā)展綜述.自動化儀表，2013，34(2):1－6.

［2］趙亦兵，吳志盛，龐濤.基于無線HART網(wǎng)絡(luò)的時(shí)鐘同步算法研究.自動化與儀器儀表，2010(4):3－5.

［3］陳權(quán)，高宏.RSPEED:無線傳感器網(wǎng)絡(luò)中基于不確定延遲的可靠實(shí)時(shí)路由.通信學(xué)報(bào)，2013，34(8):110 －119.

［4］LEE M J，ZHANG R，ZHENG J J，et al.IEEE 802.15.5 WPAN mesh standard － low rate part:meshing the wireless sensor networks.IEEE Journal on Selected Areas in Communications，2010，28(7):973 －983.

［5］HONG S，SAHU R P，SRIKANTH M R，et al.Real－ time query scheduling for wireless sensor networks.Proceedings of 17th International Conference on Database Systems for Advanced Applications，U-nited States:Institute of Electrical and Electronics Engineers Inc，2012:224－233.

［6］FANG M J，LI D D，QUAN J G，et al.An innovative routing and resource optimization strategy for wireless HART.Proceedings of 2012 International Conference on Technology and Management，Jeju，Jeju －Island，Korea，Republic of，2012:353 －360.

［7］董利達(dá)，黃聰，管林波.基于雙樹結(jié)構(gòu)的無線HART調(diào)度策略.浙江大學(xué)學(xué)報(bào)(工學(xué)版)，2014，48(3):391 －397.

［8］RAMASUBURAMANIAN S，KRISHNAMOORTHY H，KRUNZ M.Disjoint multipath routing using colored tree.Computer Networks，2007，51(8):2163 －2180.

［9］孫健波，孫強(qiáng)，申巍，等.對無線HART網(wǎng)絡(luò)的圖表路由算法的研究.鐵路計(jì)算機(jī)應(yīng)用，2011，20(8):35 －38.

［10］ZHAO J D，LAING Z J，ZHAO Y P.ELHFR:A graph routing in industrial wireless mesh network.Proceedings of 2009 IEEE International Conference on Information and Automation，Zhuhai，Macau，China，2009:106 －110.

［11］黨魁，沈繼忠，董利達(dá).基于RSL篩選的WirelessHART最短路徑路由算法.計(jì)算機(jī)工程與應(yīng)用，2012，48(6):69 －72，83.

［12］黃聰，董利達(dá)，管林波.一種低開銷無線HART路由策略.傳感技術(shù)學(xué)報(bào)，2013，26(2):252 －259.

［13］DIJKSTRA E.A note on two problems in connection with graphs.Numerical Mathematic，1959(1):269 －271.

［14］王怡蘋，李文海，文天柱.面向信號測試的路徑搜索算法研究.儀器儀表學(xué)報(bào)，2013，34(7):1650 －1658.

［15］ATHANASIOU G，KORAKIS T，ERCETIN O，et al.A Cross－ Layer framework for association control in wireless mesh networks.IEEE Transactions on Mobile Computing，2009，8(1):65 －80.

［16］HOU R H，LUI K S，LI J D.Routing in multi－radio multi－channel multi－ hop wireless mesh networks with bandwidth guarantees.Proceedings of IEEE 73rd Vehicular Technology Conference.Budapest，2011:1－5.

［17］劉鐵流，巫詠群.一種新的基于分簇的無線傳感器網(wǎng)絡(luò)多跳節(jié)能路由協(xié)議.信息與控制，2012，41(1):27 －32.

［18］BANSAL S，JUNEJA D，MUKHERJEE S.An analysis of real time routing protocols for wireless sensor networks.International Journal of Engineering Science and Technology，2011，3(3):1797 －1801.

［19］王杰臣，楊得志，張偉.最短路徑問題的一種改進(jìn)算法.解放軍測繪學(xué)院學(xué)報(bào)，1999，16(4):282 －285.