ZigBee網絡自剪裁路由算法

舒紅

(重慶郵電大學 重慶市移動通信重點實驗室，重慶 400065)

ZigBee網絡自剪裁路由算法

舒紅

(重慶郵電大學 重慶市移動通信重點實驗室，重慶 400065)

ZigBee網絡中的AODVjr算法通過全網廣播路由請求RREQ消息而獲得分組發送的最短路徑，但節點大量廣播RREQ消息增加了網絡控制開銷，導致網絡節點耗能劇增，同時網絡堵塞的可能性也大大提升。針對AODVjr算法存在的網絡節點耗能劇增問題，在AODVjr算法基礎上，結合節點鄰居表，提出篩選RREQ消息轉發節點，從而限制RREQ消息轉發次數的路由算法ZigBee樹節點自剪裁轉發算法(ZigBee On-tree Self-pruning Rebroadcast Algorithm，ZOSR)和ZigBee轉發節點選擇算法(ZigBee On-tree Forwarding Node Selection Algorithm，ZOFNS)。仿真結果表明，算法能有效降低網絡節點的轉發次數，從而降低網絡整體功耗，延長網絡工作時間。

ZigBee；自剪裁；AODVjr；RREQ；路由

0 引言

ZigBee網絡是近幾年出現的一種新興網絡技術，因其低功耗、低成本、低復雜度、短時延、大網絡容量及高節點集成度等特點，被廣泛應用于短距離低速率的數據傳輸場景中。然而由于ZigBee網絡中節點的能量資源有限，故ZigBee網絡路由算法必須以能量有效性為首要的設計要素。經典AODVjr算法通過全網廣播RREQ消息而獲得發送數據的最短路徑，節點因大量廣播RREQ消息，而耗能迅速，同時網絡堵塞的可能性也大大增加［1］。

如何優化ZigBee路由算法、降低網絡能量消耗一直是各國學者研究關注的熱點［2－5］。文獻［2］提出通過控制RREQ消息洪泛范圍，以降低網絡整體功耗。文獻［3］提出利用分層拓撲信息來減少AODVjr算法中的路由開銷，該算法為了平衡網絡能耗，將節點剩余能量作為路由度量。文獻［4］提出定向轉發RREQ消息，該算法能有效減少冗余RREQ消息的轉發，從而減少節點功耗。文獻［5］提出Mesh拓撲混合路由優化算法，該算法在鄰居表基礎上，控制RREQ消息的轉發范圍和轉發方向，并在選擇路徑時避開剩余能量較少的節點。上述算法在一定程度上限制RREQ消息的轉發次數，降低了網絡能量消耗，但都以節點已知其他節點位置信息為前提，而這在實際中很難實現。

針對ZigBee網絡路由算法存在問題，在AODVjr算法基礎上，結合節點鄰居表，提出通過篩選RREQ消息的轉發節點，能有效減少RREQ消息的轉發次數，從而有效降低網絡整體功耗的路由算法。

1 ZigBee網絡

1.1 地址分配方式

ZigBee網絡節點類型分為協調器節點(ZigBee Coordinator，ZC)、路由器節點(ZigBee Router，ZR)和終端節點(ZigBee End Device，ZED)3種。每一個無線個域網(WPAN)中僅僅包含一個ZC節點，它負責初始化網絡和管理網絡結構［6］。

ZigBee網絡有2種地址分配方式，即分布式地址分配機制(Distributed Address Assignment Mechanism，DAAM)和隨機地址分配機制(Stochastic Address Assignment Mechanism，SAAM)［7］。樹型網絡拓撲中節點默認采用DAAM獲得唯一的16 bit網絡地址。ZC節點首先進行參數設置:Cm是網絡中任一父節點最大子節點數目;Lm是網絡最大深度; Rm是網絡中任一父節點最大路由子節點數目。則網絡深度為d的父節點為其子節點分配網絡地址時，通過式(1)計算地址偏移量Cskip(d)［8］。網絡中，只有Cskip(d)＞0的節點才具有為其子節點分配網絡地址，供其加入網絡的能力。

ZigBee網絡組網時，優先讓ZR節點加入網絡，這樣能減少ZR節點向周圍節點廣播拓撲變化產生的廣播開銷。具體的地址分配機制［9］如下:

①ZC節點先將自身的網絡地址和網絡深度分別設置為0;

②對于網絡深度為d，網絡地址為A的父節點，其第n個ZC子節點對應的網絡地址如式(2)所示;

③其第m個ZED子節點對應的網絡地址如式(3)所示:

由上可知，ZigBee網絡中任意節點可根據DAAM計算得到自身樹鄰居節點(即父節點和子節點)的地址。

1.2 AODVjr路由算法

ZigBee網絡中基于路由請求的路由算法AODVjr是在AODV算法基礎上做出的改進［10］。AODVjr算法中一旦節點有路由需求，節點則會以洪泛方式向鄰居節點廣播RREQ消息，中間節點會向鄰居節點轉發接收到的RREQ消息。目的節點一旦接收到RREQ消息，將沿RREQ消息的反向轉發路徑發送路由回復(Route Reply，RREP)消息，直到源節點接收到RREP消息后，路由建立完成。通過AODVjr算法可以得到源節點與目的節點之間的最短路徑，但此算法在尋路過程中需轉發大量RREQ消息，這就增加了全網的路由控制開銷，導致網絡節點因大量轉發RREQ消息而能量消耗過快，造成網絡分割。所以，如何降低AODVjr算法中RREQ消息的轉發次數，從而降低網絡控制開銷和節點能量消耗一直是各國學者研究的重點。

2 自剪裁廣播算法

2.1 假設與定義

為了更好地描述算法，在表1中給出如下定義，這里的A代表的是任意節點或節點集合。

表1 符號定義

由于ZigBee網絡的資源限制，進行如下假設:

①任意節點之間的距離和具體位置不可知;

②任意節點的發送功率固定且相同;

③網絡拓撲不一定是以ZC節點為圓心的圓，但節點間鄰居關系是對稱的:若節點i是節點j的鄰居節點，則節點j也是節點i的鄰居節點;

④使用分布式地址分配機制DAAM，任意節點在沒有信息交換的的前提下，可獲得父節點和子節點地址;

⑤任意節點維護一跳鄰居表，任意鄰居表記錄由鄰居網絡地址和子節點數量組成。

2.2 ZigBee樹節點自剪裁轉發算法

通常Ad hoc網絡的自剪裁廣播算法中，節點v接收到RREQ消息后不會直接轉發，而會先判斷是否需要轉發RREQ消息［12］。若節點v的所有鄰居節點都已經接收到節點u轉發的RREQ消息，即N(v)－N(u)=φ，那么節點v就沒必要轉發RREQ消息了。這就需要節點獲悉兩跳鄰居表信息，而這對于能量和帶寬有限的ZigBee網絡來說是不可能實現的，所以，提出ZigBee樹節點自剪裁算法ZOSR。ZOSR算法步驟如下:

①一旦有路由請求，源節點就會向鄰居節點廣播RREQ消息;

②若中間節點v首次接收到RREQ消息則將RREQ消息緩存，并啟動定時器;

③節點v根據DAAM地址分配方式計算TN(v)，令TC(v)=TN(v);

④節點v接收到節點u發送的相同RREQ消息，則節點v根據DAAM地址分配方式計算TN(u)，并計算TC(v)=TC(v)－TN(u);

⑤若TC(v)=φ，節點v丟棄該RREQ消息，并停止計時器;

⑥重復步驟④和步驟⑤，直到定時器超時;

⑦若定時器超時，則轉發緩存中的RREQ消息;

⑧RREQ消息到達目的節點之前，重復步驟②～⑦;

⑨目的節點接收到RREQ消息后，沿RREQ反向路徑回復RREP消息;

⑩源節點接收到RREP消息后建立到目的節點之間的路由。

2.3 ZigBee轉發節點選擇算法

為了進一步減少RREQ消息的轉發次數，在ZOSR算法基礎上提出一種ZigBee轉發節點選擇算法ZOFNS，此算法根據一定準則，進一步地在未被覆蓋的樹鄰居節點中挑選最優的轉發節點進行RREQ消息的轉發。ZOFNS算法具體步驟如下:

①一旦節點v有路由需求，則向鄰居節點廣播RREQ消息，并初始化轉發節點集合，令F(v)=φ;

②利用式(4)分別計算節點v的備選轉發節點集S(v)和覆蓋節點集C(v);

③節點v若接收到節點u轉發的RREQ消息，則根據式(5)更新節點v的備選轉發節點集合覆蓋節點集;

④根據N(v)中節點網絡地址對節點進行排序;

⑤對于節點v的任意鄰居節點w，若w∈S(v)，則令節點w的狀態為“初始”狀態，反之，則令w狀態為“已轉發”狀態;

⑥初始化當前深度值，令CurrentLevel=Lm;

⑦對于處于當前深度，且為“初始狀態”的任意節點x，若x沒有子節點或所有子節點深度均為CurrentLevel+1，則將x的狀態更新為“不轉發”，反之將x的狀態更新為“轉發”;

⑧對于任意深度為CurrentLevel+1，狀態不為“已轉發”，且父節點x深度不為CurrentLevel的節點y，若節點y的狀態為“不轉發”且節點x的父節點深度為CurrentLevel－1，則將節點x的狀態設置為“轉發”。否則，將節點y的狀態設置為“轉發”;

⑨更新當前深度值，令CurrentLevel=CurrentLevel－1;

⑩重復步驟⑦～⑨，直到CurrentLevel=0;

?僅狀態為“轉發”的節點轉發RREQ消息。

3 仿真分析

為了有效地評價ZOSR算法和ZOFNS算法的性能，采用MATLAB軟件來進行仿真。將ZOSR算法和ZOFNS算法與ZigBee經典路由算法AODVjr分別在節點數目為20～100個的不同場景下進行了仿真比較:包括轉發節點數目和網絡轉發次數等指標。

仿真時網絡節點靜止且隨機分布，并假定仿真是在MAC層和物理層都不會有數據包丟失的理想狀態下進行的，取5次仿真的平均值為最終結果，其他仿真參數如表2所示。

表2 仿真參數設置

當仿真節點數目為90時，AODVjr、ZOSR和ZOFNS 3種算法的轉發節點分布圖分別如圖1(a)、(b)、(c)所示，圖中實心節點為RREQ消息的轉發節點，空心節點為無需轉發RREQ消息的節點。

圖1 ZOFNS算法轉發節點分布圖

由仿真結果可得出AODVjr、ZOSR和ZOFNS算法的轉發節點數分別為100、26和20，且算法均能覆蓋全部網絡節點。這說明ZOSR、ZOFNS算法能有效減少網絡中轉發節點數目，這是因為ZOSR算法中節點接收到RREQ消息后不會直接轉發，而是等待一段時間，根據所有樹鄰居節點是否已接收到RREQ消息來決定當前節點是否轉發RREQ消息。而ZOFNS算法在ZOSR算法基礎上，將一跳樹鄰居關系推廣到兩跳，即若當前節點的所有鄰居節點的樹鄰居節點全部已經接收到RREQ消息，則當前節點無需轉發RREQ消息。

3.1 轉發節點數

隨著節點數從20增加到90(間隔設置為10)，3種算法的轉發節點數目都呈正比例增長，如圖2所示。其中，AODVjr算法的轉發節點數目與網絡節點總數大致相等，因為AODVjr算法中一旦節點接收到RREQ消息，會向鄰居節點廣播RREQ消息，則網絡中所有節點都會轉發RREQ消息;而ZOSR算法和ZOFNS算法中，隨著節點總數的增加，節點密度隨之增加(因為仿真區域固定)，從而當前節點的鄰居節點數目增加，能有效減少覆蓋全網所需的轉發節點數目。所以，隨著節點數目增加，ZOSR和ZOFNS算法中轉發節點數目漲幅遠遠小于AODVjr算法，且ZOFNS算法在一定程度上優于ZOFNS算法。

3.2 轉發次數

隨著網絡節點總數的增加，3種算法中網絡總轉發次數增加，如圖3所示。

圖3 各算法轉發次數比較

其中，AODVjr算法的任意節點一旦接收到RREQ消息后，會將RREQ消息直接轉發，所以隨著節點數量增加，網絡總轉發次數增長較快;然而，ZOSR算法中，雖然網絡節點數量增加，但轉發節點數目漲幅不大，所以網絡總轉發次數隨著網絡節點總數增加而緩慢增長;由于ZOFNS算法改進思想類似于ZOSR算法，且轉發節點的數目更少，所以ZOFNS算法隨節點總數增加，網絡總轉發次數增長趨勢類似于ZOSR算法，但較ZOSR算法更優。

4 結束語

在經典ZigBee路由算法AODVjr基礎上，提出了ZigBee樹鄰居節點自剪裁轉發算法ZOSR、ZigBee轉發節點選擇算法ZOFNS。仿真結果顯示，ZOSR和ZOFNS算法均能有效減少網絡轉發節點數目，從而減少網絡中RREQ消息的總轉發次數，最終減少網絡路由開銷，降低網絡能量消耗。同時，由轉發次數曲線可知，網絡規模越大，ZOSR和ZOFNS算法較AODVjr算法優勢越明顯。然而，由于ZOSR和ZOFNS算法在選擇轉發節點時會等待隨機時間，ZOSR和ZOFNS算法的全網覆蓋時間必然會增加。所以，今后的工作將主要集中于優化ZOSR和ZOFNS算法網絡覆蓋時間問題上。

［1］周武斌．ZigBee無線組網技術的研究[D]．長沙:中南大學，2009:38－39．

［2］Lin Z，Meng M Q H，Liang H．ARoute Discovery Method Based on Limited Flooding in Zigbee Networks［C］∥Automation and Logistics，2008．ICAL 2008．IEEE International Conference on．IEEE，2008:3039－3044．

［3］Ren Z，Tian L，Cao J，et al．AnEfficient Hybrid Routing Algorithm for Zigbee Networks［C］∥Instrumentation＆Measurement，Sensor Network and Automation(IMSNA)，2012 International Symposium on．IEEE，2012，2:415－418．

［4］Mu J．ADirectional Broadcasting Algorithm for Routing Discovery in ZigBee Networks[J]．EURASIP Journal on Wireless Communications and Networking，2014，2014 (1):1－9．

［5］Shan C，Zhang W，Li X．Hybrid Routing Algorithm Optimization for ZigBee Mesh Network［C］∥Computer Applications and Communications(SCAC)，2014 IEEE Symposium on:142－146．

［6］穆嘉松，劉開華，史偉光．ZigBee網絡中基于節點移動性的路由選擇策略[J]．天津大學學報，2012，45(4): 301－308．

［7］杜娟，賈海瑞，李眾立．基于邏輯區域的ZigBee網絡地址分配算法[J]．傳感器與微系統，2014，33(1): 126－129．

［8］錢志鴻，朱爽，王雪．基于分簇機制的ZigBee混合路由能量優化算法[J]．計算機學報，2013，36(3): 485－493．

［9］任智，李鵬翔，姚玉坤，等．基于分段的ZigBee網絡按需可擴展地址分配算法[J]．通信學報，2012，33 (5):131－137．

［10］羅華．基于ZigBee的無線傳感器網絡路由算法研究[D]．長沙:中南大學，2010:42－46．

［11］謝川．基于ZigBee的AODVjr算法研究[J]．Computer Engineering，2011，37(10):87－89．

［12］Kim T，Kim S H，Yang J，et al．Neighbor Table Based Shortcut Tree Routing in ZigBee Wireless Networks[J]．IEEE Transactions on Parallel and Distributed Systems，2014:25(3):706－716．

Self-pruning Routing Algorithm in ZigBee Network

SHU Hong
(Chongqing Key Lab of Mobile Communications Technology，Chongqing University of Posts and Telecommunications，Chongqing 400065，China)

Although the AODVjr algorithm can obtain the shortest path of packet through broadcasting route request RREQ message to the whole ZigBee network，a large amount of RREQ messages increase the network control overhead，the energy consumption of network nodes，and the possibility of network congestion．Considering the dramatic increase of network nodes'energy consumption in AODVjr algorithm，based on AODVjr and combined with nodes'neighbor table，two algorithms called ZigBee On-tree Self-pruning Rebroadcast Algorithm(ZOSR)and ZigBee On-tree Forwarding Node Selection Algorithm(ZOFNS)are proposed，which limit the number of RREQ messages by screening the forwarding nodes that broadcast RREQ messages．Simulation results show that the algorithms effectively reduce the forwarding number of network nodes，thereby reduce the whole network power consumption and expand the network lifetime．

ZigBee;self-pruning;AODVjr;RREQ;routing

TP393

A

1003－3114(2015)05－41－5

10.3969/j.issn.1003－3114.2015.05.11

舒紅．ZigBee網絡自剪裁路由算法［J］．無線電通信技術，2015，41(5):41－45．

2015－05－11

長江學者和創新團隊發展計劃(IRT1299);重慶市科委項目(CSTC2012jjA40044，cstc2013yykfA40010);重慶市科委重點實驗室專項經費

舒紅(1991—)，女，碩士研究生，主要研究方向:移動通信和無線傳感網絡。