黃 聰，董利達，管林波

(浙江大學信息與電子工程學系，杭州310027)

隨著無線技術、傳感技術和通信技術的快速發(fā)展，無線傳感器網絡已然成為焦點。2007年，HCF在其HART的基礎上提出無線HART，這是第一個專門面向工業(yè)過程自動化的通信協(xié)議[1]。無線HART規(guī)范采用了TDMA時間同步技術，并提出了Graph路由這種能在復雜多變的通信環(huán)境中高可靠傳遞數據的路由方式，除此之外還應用了用于防干擾的跳頻技術，使得其網絡的魯棒性大大高于其他無線網絡。

與其他大部分無線網絡不同的是，無線HART網絡是由網絡管理器集中管理控制的，路由和通信資源的維護和配置是由網絡管理器負責的。網絡管理器為申請加入節(jié)點和離開節(jié)點建立和回收路由和通信資源，并定期收集網絡中所有節(jié)點的信息優(yōu)化拓撲，優(yōu)化網絡。

無線HART規(guī)范中采用的是先應式路由協(xié)議，包括兩種路由方式，Graph圖表路由和Source源路由。由于是事先計算好的路由，需要定期進行維護，因此與按所需路由相比，先應式路由協(xié)議和中心化調度增大了網絡維護的開銷。路由開銷通常是由路由存儲開銷和路由維護開銷組成，路由存儲開銷是節(jié)點所需的路由表單存儲空間，而路由維護開銷指的是路由維護時所需要的控制命令數。路由開銷是衡量網絡性能的一個非常重要的指標，較大的開銷將會給網絡的運行帶來負面影響。

1 背景及相關研究

1．1 無線HART網絡

無線HART網絡支持Mesh拓撲結構，如圖1所示，一個基本的無線HART網絡由網絡管理器、網關、AP接入點和現(xiàn)場設備[3]組成。網絡中主要存在兩種數據流，一種是設備節(jié)點采集數據發(fā)至網關;另一種是網關到設備節(jié)點的控制和管理數據流。

圖1 WirelessHART網絡拓撲結構[2]

無線HART規(guī)范中定義的路由協(xié)議是一種中心管理控制的先應式路由協(xié)議，網絡管理器負責收集整個網絡的信息然后為每個節(jié)點計算路由并分配GraphId，最后為每個節(jié)點配置到網絡中其他節(jié)點的下一跳的Connection信息(節(jié)點只存儲下一跳信息)，網絡節(jié)點并不需要自己尋找路由，只需要在發(fā)送數據包時查詢網絡管理器事先配置好的路由信息，然后根據通信資源的情況發(fā)給最先可用的下一跳鄰居。無線HART規(guī)范中采用兩種路由方式，Graph路由和Source路由。Graph路由是一種全冗余路由，路由中的每一跳都至少擁有兩個下一跳的選擇。這種路由方式使得數據包在路由路徑中的某節(jié)點離開網絡也仍能成功發(fā)往目的地，大大提高了網絡的健壯性，但其復雜性也使得網絡維護變得困難，網絡維護的代價較高。

無線HART規(guī)范中還定義了另一種路由方式:Source路由，這是一種單徑路由，它嚴格指定數據通信途中的每一跳地址，這種路由方式網絡節(jié)點可以不知道路由，只需要按照數據包中指定的下一跳地址轉發(fā)即可。

1．2 研究現(xiàn)狀

無線傳感器路由協(xié)議[4－6]的研究已經很多，大部分是基于分布式網絡，AODV[4]協(xié)議是其中最著名的之一，Zigbee協(xié)議規(guī)范正是采用這種路由協(xié)議。它是按所需路由協(xié)議，只有向目的節(jié)點發(fā)送包時，源節(jié)點才在網絡中發(fā)起路由查找過程，找到相應的路由。當鏈路斷掉，源節(jié)點需要重新發(fā)起路由查找的過程。

中心管理控制網絡由網絡中心進行計算、維護和配置路由，對于這種中心管理控制網絡路由算法也已經有不少的研究，大部分都是TBR(Tree-Based Routing)算法，即基于樹的路由算法。文獻[7]提出過多的Intra-mesh流會讓中心Root負擔過大，為了減輕中心Root的負擔提出了RDR算法，其中提到了如何修復路由樹。文獻[8]中路由算法同樣是通過構建路由樹的方式，它采用孩子個數作為構建路由樹的參數考慮之一。文獻[9－10]構建路由樹的主要思想是將Graph拓撲先分層，再根據一定的規(guī)則選擇雙親。這些基于路由樹的路由算法得到的路由僅是一條單路徑路由，其可靠性低，與Graph路由有一定的差距，并不適合無線HART網絡。單徑路由可靠性低，一旦其中有個鏈路斷掉則不能通信，多徑路由[11]相比于單徑路由增加了可靠性，研究者通常通過構造不相交(點不相交或邊不相交)的兩棵或多棵樹[12]來獲得兩條或多條路徑，但是獲得的多條路徑往往不能夠保證所有的路徑長度是相等的，即不能獲得多條最短路徑的路由。

也有少數對無線HART的Graph路由算法的研究，文獻[13]將Graph路由和AODV做比較，指出Graph路由在吞吐量和延遲方面具有一定的優(yōu)勢。文獻[14]提出的路由算法采用分層Graph的思想，但沒有涉及到節(jié)點離開及更新機制。文獻[15]提出了一種GRAPH路由生成算法ELHFR和路由更新機制，根據拓撲Graph和BFS樹來構建子圖，其路由更新機制是周期性的重新生成子圖，這種方法必然會產生網絡的大面積變動。文章還提出了加入過程和離開過程，其加入過程是通過構建臨時路由然后再等周期更新來獲得正式的路由，這種方法導致節(jié)點加入過慢。文獻[16]提出一種基于BFS算法得到最短路徑Graph路由的方法，引入RSL作為鏈路質量衡量標準，剔除質量較差的鏈路和設置每跳的鄰居數上限而簡化Graph路由，但其同樣不支持節(jié)點逐個加入，且路由開銷大。

無線HART的Graph路由方式可靠性高，維護難，開銷大，在保證網絡的可靠性的基礎上，盡量減少無用的路由路徑，降低路由開銷，同時也降低了路由對通信資源的需求，對于網絡的優(yōu)化和減負具有重要的意義。本文為了解決無線HART網絡中Graph路由的高開銷的問題，提出了一種實用的路由策略。

2 路由算法及實現(xiàn)

無線HART網絡具有此特點:節(jié)點到網關的數據流遠遠大于網關到節(jié)點的數據流，而且節(jié)點到網關的服務一般是非ACK服務，即不需要端到端應答和不需要端到端的重發(fā)，具有較高的實時性要求，容易造成堵塞;而網關到節(jié)點的服務一般是ACK服務，即需要端到端應答，如果未收到應答則會重發(fā);而且點對點之間具有重發(fā)和跳頻的功能，增加了路由的可靠性?；谶@些特點，同時為了減少Graph的存儲空間，本文通過構造雙樹結構，將Graph拓撲簡化為兩棵樹，網關到節(jié)點的路由由多路徑路由代替，而節(jié)點到網關的路由則是全冗余Graph路由。

2．1 網絡結構模型

本研究引入雙樹結構，如圖2所示，圖2(a)為原始Graph拓撲，圖2(b)為轉化后的雙樹拓撲，左邊那棵樹稱為母系樹，右邊的稱為父系樹。

圖2 雙樹拓撲結構

本文給予雙樹一些假定規(guī)則:

①同輩(層數即Level相同)之間不允許通信;

②相差兩輩或兩輩以上的節(jié)點之間不允許通信;

③父母親必須是同輩關系;

④每個節(jié)點的總孩子個數具有上限;

⑤每個節(jié)點均有父母親，若父母親均斷則該節(jié)點從雙樹中離開;

⑥樹枝斷掉后可嫁接修復，并不會破壞斷枝中的連接關系;

規(guī)則①、②和③保證了節(jié)點和網關之間的路由路徑長度均是相等的，且是最短路徑;規(guī)則4使整個網絡更加均衡;規(guī)則5和6增加了網絡的可靠性，即使父母親有一個斷了仍然能夠正常通信，而且能夠很快的修復雙樹。另外，網絡管理器僅需存儲雙樹即可快速獲得每個節(jié)點的路由，而不需要存儲每個路由，從而減小了網絡管理器的路由存儲開銷，同時也減小了節(jié)點的路由表存儲開銷。

2．2 路由算法

無線HART網絡是一種集中管理控制型網絡，無論是路由生成、回收還是維護都需要網絡管理器進行計算，并下發(fā)命令配置給路由路徑中的每個節(jié)點。本節(jié)基于上節(jié)所描述的雙樹拓撲結構提出Graph路由方式的實現(xiàn)算法。本節(jié)詳細描述對于網絡節(jié)點加入、離開和鏈路失敗等網絡拓撲的改變Graph路由相應的實現(xiàn)算法。

2．2．1 節(jié)點加入

當網絡生成時就會生成一個到達網關的上行路由(GraphId=0，以下簡稱路由0)，當節(jié)點加入網絡時，網絡管理器必須更新路由0，并為該節(jié)點生成新路由。以下是詳細的算法描述。

以圖3為例，假設節(jié)點7是正申請加入的節(jié)點，定時到時時獲得了雙向鄰居 3、4、5、6，其中 3、4、5離網關距離較近且相同，則母系樹從左到右搜索，優(yōu)先選擇了母系孩子數最少的節(jié)點4作為母親，同理父系樹從右到左搜索，選擇了3作為父親。最終添加到雙樹中。

圖3 雙樹生長

此算法使得所生成的路由路徑最短，從而減小了傳輸延時;雙樹父母親搜索方向的不同使雙樹之間的關聯(lián)小，即使其中一棵樹斷了仍然能夠正常通信。而且新加入節(jié)點成為樹的葉子節(jié)點從而不會對網絡中其他節(jié)點的下行路由造成影響，只需增加加入節(jié)點的下行路由以及更新路由0，涉及的節(jié)點減少，所需的管理維護配置開銷也就減小。

2．2．2 節(jié)點鏈路失敗

當節(jié)點從雙樹斷開時，形成斷枝(由該節(jié)點與其子孫構成)，會影響斷枝節(jié)點的下行路由和路由0，網絡管理器必須更新相應路由，回收相關路由路徑。算法如下。

此算法由于節(jié)點的離開只對樹結構下的斷枝節(jié)點的下行路由以及路由0造成影響，而且由于斷枝節(jié)點之間并未斷開，因此不需要刪除它們之間的Connections，所以路由配置開銷也相應減少。

2．2．3 節(jié)點路由定時更新

網絡管理器定期掃描路由樹，通過選擇繼父母來修復路由樹。以下是詳細的算法描述。

此算法在更新時只對樹結構下的斷枝節(jié)點的下行路由以及路由0造成影響。由于雙樹是嫁接修復的，在路由回收時，斷枝節(jié)點之間的Connections并未回收，因此不需要為斷枝節(jié)點增加新的下行路由Connections。所以路由配置開銷也相應減少。

如果節(jié)點未離開網絡，均可沿著雙樹路徑達到該節(jié)點，如果該節(jié)點雙樹中的雙路徑均不能到達，則網絡管理器使用臨時的Source路由來修復雙樹。

圖4 Source路由方式修復雙樹

3 結論與分析

3．1 建立實驗環(huán)境

實驗測試平臺為搭建的無線HART基本網絡，包括網絡管理器、網關、AP和現(xiàn)場設備，均是在CC2430－f128通信模塊實現(xiàn)的，其中采用了文獻[17－18]提出的同步策略。網絡管理器和網關通過有線連接，而網關和AP捆綁在一塊。另外網絡管理器和網關均與PC機相連，用于監(jiān)測整個網絡的情況以及觀測現(xiàn)場設備采集的數據，如圖5所示。

圖5 無線HART基本網絡和監(jiān)測

選用的拓撲圖如圖6所示，共16個節(jié)點，其中0號節(jié)點是網關，其余的均是普通節(jié)點。每個節(jié)點，都有多個鄰居節(jié)點以保證冗余度。在生成樹之后，相同Level的節(jié)點的鄰居是相同的，且鄰居的通信質量也是相同的，因此是等價的，以便于分析。由于網絡的運行，除了路由之外還需要網絡管理器進行通信資源的調度，本文采用靜態(tài)調度方式，超幀長度為100，超幀中為每個Connection分配一個通信資源。圖7簡單的示意了分配的超幀。

圖6 實驗拓撲圖

3．2 實驗測試

3．2．1 成功率

設置干擾源，分別以3%(弱干擾)和10%(強干擾)的概率干擾全網絡，然后實測端到端的單向傳送成功率。網絡中端到端傳送均采用無重發(fā)模式，而點對點保留重發(fā)和跳頻功能，重發(fā)次數為M次，測試結果見圖8。

實驗結果顯示，本方案的端到端的傳送成功率實測值由于自身鏈路的質量以及程序的影響，較低于理論值，且低于不使用本方案的Graph路由，但相差并不是很大。當全網干擾時，下行雙路徑路由的成功率比上行Graph路由的成功率略低，但基本相同。這是由于無線HART網絡中點對點的重發(fā)和跳頻機制降低了下行雙路徑路由的失敗率，使得下行雙路徑路由仍然具有較高的可靠性。而在強干擾的情況下，只要提高重發(fā)次數即可保證較高的可靠性。

圖7 超幀示意圖

圖8 端到端傳送成功率測試圖

設置干擾源，分別以3%(弱干擾)和10%(強干擾)的概率干擾全網絡，然后實測端到端的雙向通信成功率。一次雙向通信成功指的是發(fā)送方接收到接收方的應答包。端到端傳送采用重發(fā)模式，重發(fā)次數為N次，而點對點保留重發(fā)和跳頻功能，重發(fā)次數M=2次，測試結果如圖9所示。

圖9 端到端雙向通信成功率測試圖

而實驗結果顯示，本方案的下行端到端的通信成功率在重發(fā)的機制下變得相對的可靠，高于無線HART網絡對網絡通信可靠性的要求(3σ，99．730 020 4%)。而在強干擾的情況下，只要提高端到端的重發(fā)次數即可保證較高的可靠性。而無線HART規(guī)范中定義的默認重發(fā)次數為5。因此本文所提出的路由方案雖然簡化了Graph路由，但仍然具有較高的可靠性。

3．2．2 路由存儲開銷

網絡中的節(jié)點，既要存儲到達網關上行路由表，又要存儲所有的需要其作為路由器的下行路由表，當網絡規(guī)模變大時，存儲空間就會變得很緊張。如圖10所示，縱坐標Connection開銷指的是節(jié)點所需存儲路由的Connection的個數，從圖中可知越靠近網關路由存儲開銷越大，本方案減小了路由存儲的開銷，并且越靠近網關節(jié)點所需存儲Connection的個數增加的幅度減小。另外，網絡管理器需要存儲整個網絡必要的路由信息，使得能夠快速獲得每個節(jié)點的路由。本文策略中僅需存儲雙樹即可表示整個網絡的路由信息以及快速獲得每個節(jié)點的路由，而不需要存儲每個路由，從而減小了網絡管理器的路由存儲開銷。

圖10 connection開銷示意圖

3．2．3 路由維護開銷

路由維護開銷主要來自3部分，分別是節(jié)點加入、離開和更新時產生的開銷。以下對路由維護開銷的評估均分為2部分:影響路由，即Graph的個數和維護路由所需管理命令的個數。其中影響Graph個數在一定程度上體現(xiàn)了網絡的拓撲變化對整個網絡的影響大小，而維護管理命令個數直接體現(xiàn)了路由維護開銷的大小。

①加入過程

分別測試對于不同Level的申請加入節(jié)點的加入過程的路由維護開銷。如圖11所示，本文策略由于加入節(jié)點成為樹的葉子節(jié)點從而不會對網絡中其他節(jié)點的下行路由造成影響，只需增加節(jié)點的下行路由以及更新路由0，因此其影響的Graph個數固定為2。加入節(jié)點距離網關越近，它新增加的路由路徑短，所涉及的節(jié)點少，所需的配置開銷也就越少。而未使用本方案的Graph路由則相反，當距離網關越近，所影響的Graph越多，那么所需的配置開銷也相應越多。

圖11 加入過程路由開銷示意圖

從圖中可知，未使用本方案的Graph路由所下發(fā)的管理命令較多，影響范圍大，嚴重影響了網絡的效率，加入速度慢。本文提出的方案對于節(jié)點加入時所需的路由維護開銷較小，影響范圍小，并支持單節(jié)點逐個加入網絡。

②離開過程

圖12 離開過程路由開銷示意圖

分別測試不同Level的申請離開節(jié)點的離開過程的路由維護開銷。如圖12所示，本文策略由于節(jié)點的離開只對樹結構下的斷枝節(jié)點的下行路由以及路由0造成影響。而未使用本方案的Graph路由策略，節(jié)點離開會對網絡中層次大于離開節(jié)點的大部分節(jié)點造成影響。因此相比之下，本文策略影響的節(jié)點個數減少，影響的Graph個數也減少，配置開銷也減少。

③更新過程

分別測試對于不同Level的節(jié)點路由更新過程的路由維護開銷。本測試所采用的情形是刪除一條路徑并增加一個新的路徑。圖13中只顯示了單個節(jié)點的開銷情況。測試結果表明，本文策略由于節(jié)點路徑的刪除和增加只對樹結構下的斷枝節(jié)點的下行路由以及路由0造成影響，從而影響的節(jié)點個數減少，影響的Graph個數也減少，配置開銷也減少。

圖13 更新過程路由開銷示意圖

4 結論

本文針對無線HART網絡的特點，提出了一種基于雙樹結構的路由策略。該方法簡化了無線HART協(xié)議中提出的Graph路由，得到了較好結果。本文以CC2430通信模塊為實驗平臺進行測試，實測表明:雖然簡化了Graph路由，但其可靠性仍然較高，卻減小了路由存儲和維護的開銷，并很好的支持節(jié)點逐個加入和離開。此方法提高了網絡的效率，為無線HART的路由算法提出了一種實用的方案。

[1]彭瑜．無線HART協(xié)議——種真正意義上的工業(yè)無線短程網協(xié)議的概述和比較[J]．儀器儀表標準化與計量，2007(5):40－46．

[2]The Hart Communication Foundation．HCF_LIT－89．WirelessHART Technical Data Sheet[S]．USA，2007．

[3]The Hart Communication Foundation．HCF_SPEC－285，WirelessHART Device Specification(Revision 1．1)[S]．USA，2008．

[4]Perkins C E．Ad-Hoc on-Demand Distance Vector Routing[C]//Proceedings—2nd IEEE Workshop on Mobile Computing Systems and Applications，USA:IEEE Computer Society，1999．90－100．

[5]馬祖長，孫怡寧，梅濤．無線傳感器網絡綜述[J]．通信學報，2004，25(4):114－124．

[6]周賢偉，劉賓，覃伯平．無線傳感器網絡的路由算法研究[J]．傳感技術學報，2006，19(2):463－467．

[7]Lim A O，Wang X，Kado Y．A Hybrid Centralized Routing Protocol for 802．11s WMNs[J]．Mobile Networks and Applications，2008(13):117－131．

[8]Al-Hemyari A，Noordin N K，Ismail A．Centralized Scheduling，Routing Tree in WiMAX Mesh Networks[C]//2008 International Conference on Innovations in Information Technology，USA:Inst of Elec and Elec Eng Computer Society，2008:539－543．

[9]Al-Hemyari A，Ng C K，Noordin N K．Constructing Routing Tree for Centralized Scheduling Using Multi-ChannelSingle Transceiver System in 802．16 Mesh Mode[C]//2008 IEEE International RF and Microwave Conference，USA:IEEE Computer Society，2008．191－195．

[10]Lo S，Ou L．Efficient Algorithms for Routing and Centralized Scheduling for IEEE 802．16 Mesh Networks[C]//International Conference on Scalable Computing and Communications—The 8th International Conference on Embedded Computing，USA:IEEE Computer Society，2009．212－217．

[11]Ramasubramanian S，Krishnamoorthy H，KrunzM．Disjoint Multipath Routing Using Colored Trees[J]．Computer Networks，2007，51(8):2163－2180．

[12]Medard M，F(xiàn)inn S G，Barry R A．Redundant Trees for Preplanned Recovery in Arbitrary Vertex-Redundant or Edge-Redundant Graphs[J]．IEEE-ACM Transactions on Networking，1999，7(5):641－652．

[13]孫健波，孫強，申巍，等．對無線HART網絡的圖表路由算法的研究[J]．鐵路計算機應用，2011，20(8):35－38．

[14]Li D，Quan J，Zhang S，et al．An Innovative Routing and Resource Optimization Strategy for WirelessHART[C]//Proceedings of the 2012 International Conference on Technology and Management，Germany:Springer Verlag，2012．353－360．

[15]Zhao J，Liang Z，Zhao Y．ELHFR:A Graph Routing in Industry Wireless Mesh Network[C]//2009 IEEE International Conference on Information and Automation，USA:IEEE Computer Society，2009．106－110．

[16]黨魁，沈繼忠，董利達．基于RSL篩選的WirelessHART最短路徑路由算法[J]．計算機工程與應用，2012，48(6):69－72．

[17]華苗苗，董利達，傅健豐，等．基于閉環(huán)調整策略的無線HART時間同步方法[J]．傳感技術學報，2012，25(3):391－196．

[18]Hua M，Dong L．A Closed-Loop Adjusting Strategy for WirelessHART Time Synchronization[C]//11th InternationalSymposium on Communications and Information Technologies，USA:IEEE Computer Society，2011．131－135．