ZigBee路由算法分析

1、摘要基于標(biāo)準(zhǔn)的ZigBee網(wǎng)絡(luò)是一種具有強大組網(wǎng)能力的新型無線個域網(wǎng)，其 中的路由算法是研發(fā)工作的重點。本文介紹了標(biāo)準(zhǔn)及ZigBee規(guī)范的協(xié)議模型，重點研究了 ZigBee協(xié)議網(wǎng)絡(luò)層的路由算法，分析了 Tree路由及Z-AODV路由算 法，在此基礎(chǔ)上提出了 ZigBee網(wǎng)格型網(wǎng)絡(luò)中基于數(shù)據(jù)特性的路由選擇機制，該 機制在網(wǎng)絡(luò)性能和低功耗方面有明顯的優(yōu)勢， 并且可以平衡節(jié)點能量， 最后簡單 介紹了 ZigBee節(jié)點的硬件實現(xiàn)。關(guān)鍵詞ZigBee協(xié)議；網(wǎng)絡(luò)；路由算法；Tree路由；Z-AODV路由1 概述ZigBee技術(shù)是由英國Invensys公司、日本三菱電氣公司、美國摩托羅拉公司 以及荷蘭飛利浦

2、等公司在 2002年 10月共同提出設(shè)計研究開發(fā)的具有低成本、 體 積小、能量消耗小和傳輸速率低的無線通信技術(shù)。2000 年 12 月，IEEE 802無線個域網(wǎng)（WPAN, Wireless Personal Area Network 小組成立，致力于 WPAN無線傳輸協(xié)議的建立。2003年12月，IEEE正式發(fā)布了 該技術(shù)物理層和MAC層所采用的標(biāo)準(zhǔn)協(xié)議，即IEEE協(xié)議標(biāo)準(zhǔn)，作為ZigBee技 術(shù)的網(wǎng)絡(luò)層和媒體接入層的標(biāo)準(zhǔn)協(xié)議。2004年12月，ZigBee聯(lián)盟在IEEE定義 的物理層（PHY和媒體接入層（MAC）的基礎(chǔ)上定義了網(wǎng)絡(luò)層和應(yīng)用層，正式 發(fā)布了基于IEEE的ZigBee標(biāo)準(zhǔn)協(xié)議

3、。2 網(wǎng)絡(luò)層的研究ZigBee技術(shù)的體系結(jié)構(gòu)主要由物理層（PHY、媒體接入層（MAC）、網(wǎng)絡(luò)/安全層以及應(yīng)用框架層組成，各層之間的分布如圖 1 所示應(yīng)用框鬆ZigBeethTEEE8d21541 :圖1 ZigBee技術(shù)協(xié)議組成PHY層的特征是啟動和關(guān)閉無線收發(fā)器、能量檢測、鏈路質(zhì)量、信道選擇、清除信道評估（CCA以及通過物理媒體對數(shù)據(jù)包進行發(fā)送和接收。MAC層可以實現(xiàn)信標(biāo)管理、信道接入、時隙管理、發(fā)送確認(rèn)幀、發(fā)送連接及斷開連接請求，還 為應(yīng)用合適的安全機制提供一些方法。它包含具有時間同步信標(biāo)的可選超幀結(jié) 構(gòu)，采用免碰撞的載波偵聽多址訪問（CSMA-CA。安全層主要實現(xiàn)密鑰管理、 存取等功能。

4、網(wǎng)絡(luò)層主要用于 ZigBee的LR-WPAN網(wǎng)的組網(wǎng)連接、數(shù)據(jù)管理等。 應(yīng)用框架層主要負(fù)責(zé)向用戶提供簡單的應(yīng)用軟件接口（API），包括應(yīng)用子層支持APSApplication Sub-layer Support）、ZigBee設(shè)備對象 ZD（ZigBee Device Object 等，實現(xiàn)應(yīng)用層對設(shè)備的管理，為 ZigBee技術(shù)的實際應(yīng)用提供一些應(yīng)用框架模 型等，以便對ZigBee技術(shù)的開發(fā)應(yīng)用。網(wǎng)絡(luò)層的定義包括網(wǎng)絡(luò)拓?fù)?、網(wǎng)絡(luò)建立、網(wǎng)絡(luò)維護、路由及路由的維護。ZigBee的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)ZigBee定義了三種拓?fù)浣Y(jié)構(gòu)：星型拓?fù)浣Y(jié)構(gòu)（Star），主要為一個節(jié)點與多個 節(jié)點的簡單通信設(shè)計；樹型拓?fù)?/p>

5、結(jié)構(gòu)（Tree），使用分等級的樹型路由機制；網(wǎng) 格型拓?fù)浣Y(jié)構(gòu)（Mesh），將Z-AODV和分等級的樹型（Tree）路由相結(jié)合的混合 路由方法。三種拓?fù)浣Y(jié)構(gòu)如圖2所示。圖2網(wǎng)絡(luò)的三種拓?fù)浣Y(jié)構(gòu)ZigBee定義了三種設(shè)備類型：ZigBee協(xié)調(diào)器(ZigBee Coordinator, ZC),用于 初始化網(wǎng)絡(luò)信息，每個網(wǎng)絡(luò)只有一個ZC; ZigBee路由器(ZigBee Route，ZR)，它起監(jiān)視或控制作用，但它也是用跳頻方式傳遞信息的路由器或中繼器；ZigBee終端設(shè)備(ZigBee End Device ZED)，它只有監(jiān)視或控制功能，不能做路由或中 繼之用。在IEEE標(biāo)準(zhǔn)中，ZED被稱為精簡

6、功能設(shè)備(Reduced-Function Device RFD)， ZC和 ZR被稱作全功能設(shè)備(Full-Function Device FFD)。網(wǎng)絡(luò)層路由算法的分析網(wǎng)絡(luò)層支持Tree、Z-AODV Tree + Z-AODV等多種路由算法。2.2.1 AODV路由協(xié)議DSDV (destination-sequeneed distance-vector)協(xié)議是一個基于傳統(tǒng)的Bellma nFord路由機制的表驅(qū)動算法，被認(rèn)為是最早的無線自組網(wǎng)絡(luò)路由協(xié)議。 DSDV在傳統(tǒng)的distance-vector算法的基礎(chǔ)上采用了序列號機制，用于區(qū)分路由 的新舊程度，防止distance-vect

7、or算法可能產(chǎn)生的路由環(huán)路。DSDV采用時間驅(qū) 動和事件驅(qū)動技術(shù)控制路由表的傳送，即每個移動節(jié)點在本地都保留一張路由 表，其中包括所有有效目的節(jié)點、路由跳數(shù)、目的節(jié)點路由序列號等信息，目的 節(jié)點路由序列號用于區(qū)別有效和過期的路由信息以避免環(huán)路的產(chǎn)生。DSR( dyn amic source rout ing)協(xié)議是最早采用按需路由思想的路由協(xié)議，包括路由發(fā)現(xiàn)和維護兩個過程。它的主要特點是使用了源路由機制進行數(shù)據(jù)包轉(zhuǎn)發(fā)。AODV(ad-hoc on-dema nd dista nee vector協(xié)議在 DSDV協(xié)議的逐跳路由、序列號、定期廣播機制基礎(chǔ)上，加入了 DSR的按需路由發(fā)現(xiàn)和維護機制。

8、AODV在每個中間節(jié)點隱式保存了路由請求和應(yīng)答的結(jié)果，并利用擴展環(huán)搜索(expanding ring research的辦法限制搜索發(fā)現(xiàn)目的節(jié)點的范圍。AODV支持組播功能，支持QoS,而且AODV使用IP地址，便于同In ternet連接。但AODV 基 于雙向信道的假設(shè)，路由應(yīng)答數(shù)據(jù)包直接沿著路由請求的反方向回溯到源節(jié)點， 因而不支持單向信道。與 DSDV保存完整的路由表不同的是，AODV通過建立按 需路由來減少路由廣播的次數(shù)，這是 AODV對DSDV的重要改進。與DSR相比， AODV的好處在于源路由并不需要包括在每一個數(shù)據(jù)包中，這樣會降低路由協(xié)議 的開銷。AODV是一個純粹的按需路由協(xié)

9、議，那些不在路徑內(nèi)的節(jié)點不保存路由 信息，也不參與路由表的交換。2.2.2 Z-AOD V能量平衡路由在ZigBee路由規(guī)范中沒有過多的考慮能量控制，但是對于ad hoc無線網(wǎng)絡(luò)來說，能量控制非常重要。因此提出了能量控制策略來改進ZigBee路由。它將使節(jié)點避免用盡所有能量以至于過早的失去作用。當(dāng)節(jié)點想要選擇路徑時，它將考慮路徑上的節(jié)點的剩余能量。Z-AODV算法是針對AODV(Ad hoc按需距離矢量路由協(xié)議)算法的改進，AODV 是基于序列號的路由，它總是選擇最新的路由。Z-AODV是基于路徑的能量消耗的路由，考慮到節(jié)能、應(yīng)用方便性等因素，簡化了AODV的一些特點，但仍保持AODV的原始功

10、能。在路由選擇和路由維護時，ZigBee的路由算法使用了路由成本的度量方法來比較路由的好壞。假定一個長度為 L的路由P,則它的路由成本為：其中， '月廠口 I'表示從節(jié)點 D到節(jié)點Di+i的鏈路成本。對于鏈路I,鏈路成本可按照下面的表達式計算:mill7 .round其中，pi為鏈路I中發(fā)送數(shù)據(jù)包的概率在ZigBee規(guī)范中沒有涉及到pi的具體計算方法。pi可通過實際計算收到的信 標(biāo)和數(shù)據(jù)幀來進行估計，即通過觀察幀的響應(yīng)序列號來檢測丟失的幀，這就通常 被認(rèn)為最準(zhǔn)確地測量接收概率的方法。 但是，對于所有的方法來說，最直接和有 效的方法就是基于IEEE的MAC層和PHY層所提供的每一

11、幀的LQI通過平均所計算的值。即使使用其他方法，最初的成本估計值也是基于平均的LQI值?？梢愿鶕?jù)驅(qū)動函數(shù)表來映射平均LQI值與C I 值的關(guān)系（見表1）。表1 LQI值與鏈路成本的關(guān)系LQI鏈路成本大于75150了53小于507能量平衡運算要考慮許多因素來選擇路由。這些因素包括臨近節(jié)點的能量、節(jié)點自身的能量和鏈路質(zhì)量。剩余能量Eocai可以在每一個ZigBee幀中的保留域發(fā)送，這樣每個節(jié)點都能得到它的鄰居節(jié)點最新的能量分配Ei, E2-IE 02.2.3樹型（Tree）路由樹型路由機制包括配置樹型地址和樹型地址的路由。當(dāng)協(xié)調(diào)器建立一個新的網(wǎng)絡(luò)，它將給自己分配網(wǎng)絡(luò)地址 0，網(wǎng)絡(luò)深度Deptho=

12、O。如果節(jié)點（i）想要加入 網(wǎng)絡(luò)，并且與節(jié)點（k）連接，那么節(jié)點（k）將稱為節(jié)點（i）的父節(jié)點。根據(jù) 自身的地址Ak和網(wǎng)絡(luò)深度Depthk，節(jié)點（k）將為節(jié)點（i）分配網(wǎng)絡(luò)地址A和 網(wǎng)絡(luò)深度Depthi=Depthk+1。網(wǎng)絡(luò)深度表示僅僅采用父子關(guān)系的網(wǎng)絡(luò)中，一個傳送幀傳送到ZigBee協(xié)調(diào)器所傳遞的最小跳數(shù)。ZigBee協(xié)調(diào)器自身深度為0,而它 的子設(shè)備深度為1。圖3為ZigBee樹型結(jié)構(gòu)。參數(shù)nwkMaxChildren(Cm表示路由器或協(xié)調(diào)器在網(wǎng)絡(luò)中允許擁有子設(shè)備數(shù)量的最大值。參數(shù)nwkMaxRouters(Rm表示子節(jié)點中路由 器的最大個數(shù)，而剩下的設(shè)備數(shù)為終端設(shè)備數(shù)。圖3 ZigBe

13、e樹型結(jié)構(gòu)一個新的RFD節(jié)點(i)，它沒有路由能力，它與協(xié)調(diào)器連接作為協(xié)調(diào)器的第 n個子節(jié)點。根據(jù)它的深度d，父節(jié)點(k)將為子節(jié)點(i)分配網(wǎng)絡(luò)地址：Ai=Ak+Cskip (d) Rm+n 其中 1 < n( Cm-Rm)如果是新的子節(jié)點FFD,它有路由能力，父節(jié)點(k)將給它分配網(wǎng)絡(luò)地址:Ai=Ak+1+Cskip (d) (n-1)其中，Cskip二i 4- CmLm- N -1),如果Rm 二 1U + Cm- Rm - CmRm否則，參數(shù)nwkMaxDepth (Lm)表示網(wǎng)絡(luò)的最大深度。假設(shè)一個路由器向網(wǎng)絡(luò)地址為 D的目的地址發(fā)送數(shù)據(jù)包，路由器的網(wǎng)絡(luò)地址 為A,網(wǎng)絡(luò)深度為d

14、。路由器將首先通過表達式：A v Dv A + Cskip( d-1 )判斷該目的節(jié)點是否為自己的子節(jié)點。如果目的節(jié)點是自己的子節(jié)點，貝U下一跳節(jié)點的地址為：D,如果是終端設(shè)備N =. D-(衛(wèi) + 1)ZxCfap(d)否則，下一跳節(jié)點是該路由器的父節(jié)點。224 Tree+Z-AODV路由算法的分析根據(jù)上文對Tree和Z-AODV兩種路由算法的分析，在我們的 ZigBee網(wǎng)絡(luò)中將 二者結(jié)合，使用Z-AODV和分等級的樹型（Tree）路由相結(jié)合的混合路由方法， 構(gòu)成網(wǎng)格型拓?fù)浣Y(jié)構(gòu)（Mesh）的網(wǎng)絡(luò)。具體實現(xiàn)方法是在數(shù)據(jù)幀幀頭的 DiscoverRouter域指定路由。該域可以是如下 三種值：抑

15、制路由發(fā)現(xiàn)：它使用已經(jīng)存在的路由表。當(dāng)路由表中沒有相應(yīng)的目的節(jié) 點的地址時，參數(shù)nwkUseTreeRouting的值為TRUE網(wǎng)絡(luò)將使用樹型路由。 使能路由發(fā)現(xiàn)：如果在路由表中有路由地址，將按照該路由表進行路由。 否則，路由器將使用Z-AODV路由算法初始路由發(fā)現(xiàn)。如果該節(jié)點沒有初始路由 發(fā)現(xiàn)的能力，它將使用樹型路由。 強制路由發(fā)現(xiàn)：不管是否有相應(yīng)的路由表，節(jié)點都強制使用Z-AODV路由算法初始化路由發(fā)現(xiàn)。在ZigBee規(guī)范中提出了將 AODV和 Tree路由混合的路由機制。但在ZigBee規(guī) 范中并沒有說明如何配置參數(shù)來選擇路由策略，沒有使兩者平衡的設(shè)計方法。根據(jù)上面Tree路由和Z-AO

16、DV的分析，我們提出了基于數(shù)據(jù)特性的路由方法，即在兩種路由算法構(gòu)成的網(wǎng)格型網(wǎng)絡(luò)中， 根據(jù)節(jié)點間傳輸數(shù)據(jù)特性的不同，通過設(shè)置 數(shù)據(jù)幀幀頭的DiscoverRouter域,選擇不同的路由方法。對于捆綁型的連續(xù)數(shù)據(jù)， ZigBee應(yīng)用層應(yīng)選擇使用使能路由的方法。即采用 Z-AODV路由首先建立路由發(fā)現(xiàn)，然后選擇跳數(shù)少的路由，成為最佳路徑；對于爆發(fā)型的不連續(xù)數(shù)據(jù)則使用抑 制路由發(fā)現(xiàn)的方法，即在路由表中沒有響應(yīng)的目的節(jié)點的地址時，采用Tree路由方法。因為這種路由不需要建立路由表，因此對傳輸?shù)臄?shù)據(jù)響應(yīng)較快。圖4為節(jié)點接收到上層或其他節(jié)點發(fā)送的數(shù)據(jù)包時，網(wǎng)絡(luò)層處理程序的流程 圖。圖4路由算法流程圖總結(jié)Tr

17、ee路由是一種由網(wǎng)絡(luò)協(xié)調(diào)器展開生成樹狀網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，適合于節(jié)點靜 止或者移動較少的場合，屬于靜態(tài)路由，不需要存儲路由表。樹型路由對傳輸數(shù) 據(jù)包的響應(yīng)較快，因為樹型路由不需要建立路由表。其缺點是所選擇的路由并非 是最佳的路由，不能獲得最小路由。樹型路由適用于爆發(fā)型的數(shù)據(jù)傳輸。Z-AODV需要首先建立路由發(fā)現(xiàn)，然后選擇跳數(shù)少的路由，成為最佳路徑。 Z-AODV適用于連續(xù)的數(shù)據(jù)傳輸。在ZigBee規(guī)范中，設(shè)計了 Z-AODV和Tree路由混合的路由策略，這里我們提 出了基于數(shù)據(jù)服務(wù)的ZigBee路由選擇策略。根據(jù)上述分析可以看出，這種路由 選擇機制在網(wǎng)絡(luò)性能和低功耗方面有明顯的優(yōu)勢；并且根據(jù)能量控

18、制機制，可以 有效地平衡節(jié)點能量，避免節(jié)點耗盡能量而過早地失去作用。3 ZigBee模塊硬件設(shè)計模塊集無線收發(fā)器、微處理器、存儲器和用戶API等軟硬件于一體，可實現(xiàn)版 ZigBee協(xié)議棧的功能。IC圖5 ZigBee模塊框圖圖5是模塊的硬件框圖，射頻芯片采用 Chipcon公司生產(chǎn)的符合標(biāo)準(zhǔn)的模塊CC2420控制射頻芯片的微處理器可以根據(jù)需要選擇Atmel公司的AVR系列單片機或者Silicon Labs公司的8051內(nèi)核單片機。單片機與射頻芯片之間通過SPI通信。單片機與外部設(shè)備之間通過串口通信，單片機自帶若干ADC或者溫度傳感器，可以實現(xiàn)簡單的模數(shù)轉(zhuǎn)換或者溫度監(jiān)控。為了方便代碼移植到不同的硬件平臺，模塊固件采用標(biāo)準(zhǔn)C語言編寫代碼實現(xiàn)。參考文獻1 蔣挺，趙