ZigBee網(wǎng)絡(luò)的路由算法分析

王惠清，周 雷，王 靜/Wang Huiqing，Zhou Lei，Wang Jing

（1．瀘州醫(yī)學(xué)院現(xiàn)代教育技術(shù)中心 瀘州646000；2.中南大學(xué)信息科學(xué)與工程學(xué)院 長沙410083）

1 引言

ZigBee網(wǎng)絡(luò)是一種近距離的無線傳感網(wǎng)絡(luò)，具有低數(shù)據(jù)量、低能耗、靈活組網(wǎng)的特點(diǎn)，在局域區(qū)域中使用廣泛。ZigBee 是建立在IEEE 802.15.4 標(biāo)準(zhǔn)的基礎(chǔ)上，在數(shù)千個(gè)微小的傳感器之間相互協(xié)調(diào)實(shí)現(xiàn)通信[1]。2003年12月，IEEE 正式發(fā)布了該技術(shù)物理層和媒體接入層（MAC）所采用的標(biāo)準(zhǔn)協(xié)議，即IEEE 802.15.4 協(xié)議標(biāo)準(zhǔn)，作為ZigBee 技術(shù)的網(wǎng)絡(luò)層和媒體接入層的標(biāo)準(zhǔn)協(xié)議。2004年12月，ZigBee聯(lián)盟在IEEE 802.15.4 定義的物理層和MAC的基礎(chǔ)上，定義了網(wǎng)絡(luò)層和應(yīng)用層，正式發(fā)布了基于IEEE 802.15.4的ZigBee 標(biāo)準(zhǔn)協(xié)議[2]。本文在分析ZigBee網(wǎng)絡(luò)配置、組網(wǎng)和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的基礎(chǔ)上，對比常用的幾種ZigBee網(wǎng)絡(luò)路由算法，并且利用Matlab 軟件對其網(wǎng)絡(luò)性能進(jìn)行仿真實(shí)驗(yàn)。

2 ZigBee網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

ZigBee網(wǎng)絡(luò)層支持3 種拓?fù)浣Y(jié)構(gòu)： 星型拓?fù)?、樹型拓?fù)浜途W(wǎng)狀型拓?fù)鋄3]。其拓?fù)浣Y(jié)構(gòu)如圖1所示。星型拓?fù)渚W(wǎng)絡(luò)主要為一個(gè)節(jié)點(diǎn)與多個(gè)節(jié)點(diǎn)的通信設(shè)計(jì)； 樹型拓?fù)渚W(wǎng)絡(luò)采用基于信標(biāo)的方式進(jìn)行通信，使用分級路由策略來傳送控制信息和數(shù)據(jù)；網(wǎng)狀型拓?fù)渚W(wǎng)絡(luò)是一種骨干網(wǎng)，由若干個(gè)FFD 節(jié)點(diǎn)連接在一起組成。在網(wǎng)狀型拓?fù)浣Y(jié)構(gòu)中，網(wǎng)絡(luò)節(jié)點(diǎn)之間進(jìn)行通信需要預(yù)先設(shè)定一個(gè)節(jié)點(diǎn)作為整個(gè)ZigBee網(wǎng)絡(luò)的協(xié)調(diào)點(diǎn)。

圖1 ZigBee網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

3 ZigBee網(wǎng)絡(luò)組網(wǎng)

ZigBee網(wǎng)絡(luò)的組網(wǎng)分為以下幾個(gè)步驟。

①初始化ZigBee網(wǎng)絡(luò)環(huán)境并將網(wǎng)絡(luò)設(shè)備節(jié)點(diǎn)加入到ZigBee網(wǎng)絡(luò)，網(wǎng)絡(luò)初始化的主要工作是確定ZigBee的節(jié)點(diǎn)協(xié)調(diào)點(diǎn)。

②為了避免節(jié)點(diǎn)干擾，需要對信道進(jìn)行掃描，以準(zhǔn)確獲取節(jié)點(diǎn)信息。

③對網(wǎng)絡(luò)的節(jié)點(diǎn)ID 進(jìn)行設(shè)置，獲取合適的信道后，協(xié)調(diào)器選取一個(gè)標(biāo)識符作為網(wǎng)絡(luò)標(biāo)識符（PAN ID），PAN ID 在信道中必須唯一，且不能為廣播地址，這樣就實(shí)現(xiàn)了ZigBee 網(wǎng)狀網(wǎng)絡(luò)的初始化。

④最后將選取的設(shè)備節(jié)點(diǎn)加入ZigBee網(wǎng)絡(luò)中，主要有兩種節(jié)點(diǎn)加入情況：一種情況是有新的節(jié)點(diǎn)需要加入網(wǎng)絡(luò)；另一種情況是已失效的節(jié)點(diǎn)重新喚醒，申請加入網(wǎng)絡(luò)。第一種需要原來保存的路由信息向父節(jié)點(diǎn)發(fā)起申請； 第二種則需要FFD網(wǎng)絡(luò)節(jié)點(diǎn)向協(xié)調(diào)器發(fā)出連接請求，協(xié)調(diào)器根據(jù)實(shí)際網(wǎng)絡(luò)情況決定是否允許其連接，建立連接后，才能實(shí)現(xiàn)數(shù)據(jù)的收發(fā)。

ZigBee網(wǎng)絡(luò)組網(wǎng)時(shí)，節(jié)點(diǎn)網(wǎng)絡(luò)地址的獲得基于樹型地址分配機(jī)制[4]，其主要步驟為：ZigBee網(wǎng)絡(luò)中選定的協(xié)調(diào)器需要建立一個(gè)新的網(wǎng)絡(luò)，首先利用樹形分配算法給網(wǎng)絡(luò)分配地址0，網(wǎng)絡(luò)深度Depth0，新節(jié)點(diǎn)i 加入網(wǎng)絡(luò)并且與節(jié)點(diǎn)k 連接，這里，節(jié)點(diǎn)k 稱為節(jié)點(diǎn)i的父節(jié)點(diǎn)。節(jié)點(diǎn)k 本身的網(wǎng)絡(luò)地址為Ak，網(wǎng)絡(luò)深度為Depthi=Depthk+1。ZigBee網(wǎng)絡(luò)自身的協(xié)調(diào)器節(jié)點(diǎn)深度定義為0，作為根節(jié)點(diǎn)，且它的子節(jié)點(diǎn)深度定義為1。父節(jié)點(diǎn)k 為子節(jié)點(diǎn)i 分配網(wǎng)絡(luò)地址的關(guān)系為

若新增加的子節(jié)點(diǎn)為FFD 設(shè)備，并且為路由節(jié)點(diǎn)，則給它分配網(wǎng)絡(luò)地址

4 ZigBee 路由算法

ZigBee網(wǎng)絡(luò)層支持Tree、AODV 和EHRP 等多種路由協(xié)議，ZigBee網(wǎng)絡(luò)進(jìn)行路由選擇主要有以下幾個(gè)步驟。

①ZigBee網(wǎng)絡(luò)源節(jié)點(diǎn)以廣播的方式發(fā)送路由請求報(bào)文。

②目的節(jié)點(diǎn)在網(wǎng)絡(luò)報(bào)文中接收到請求報(bào)文后，發(fā)送響應(yīng)回答報(bào)文。

③路由路徑上的網(wǎng)絡(luò)節(jié)點(diǎn)對收到的響應(yīng)回答報(bào)文進(jìn)行計(jì)算和分析，得到所有路由路徑的跳數(shù)和數(shù)據(jù)時(shí)延。

④將計(jì)算和分析后的最優(yōu)路徑信息記錄到此路徑網(wǎng)絡(luò)節(jié)點(diǎn)的路由表中。

考慮到ZigBee網(wǎng)絡(luò)低能耗和簡單配置等各項(xiàng)特點(diǎn)，對ZigBee網(wǎng)絡(luò)中的典型路由算法，如Tree算法、AODV算法[5]、EHPR算法、Cluster-Tree+AODVjr算法等進(jìn)行對比分析，在此基礎(chǔ)上對這些算法進(jìn)行改進(jìn)和完善，使其適應(yīng)不同的網(wǎng)絡(luò)環(huán)境。

4.1 Tree 路由算法

Tree 型路由機(jī)制主要包括樹形地址的分配和樹形地址的路由選擇，其Tree 型路由算法的核心就是尋找網(wǎng)絡(luò)中源節(jié)點(diǎn)到目的節(jié)點(diǎn)之間的路由路徑。例如，設(shè)某路由節(jié)點(diǎn)向目的地址為D的節(jié)點(diǎn)發(fā)送報(bào)文，其中，A 為路由節(jié)點(diǎn)的網(wǎng)絡(luò)地址，d 為網(wǎng)絡(luò)深度，判斷目的節(jié)點(diǎn)位置的表達(dá)式為

若當(dāng)前節(jié)點(diǎn)是目的節(jié)點(diǎn)的祖先節(jié)點(diǎn)，則當(dāng)前節(jié)點(diǎn)的下一跳地址為

Tree 路由算法的優(yōu)點(diǎn)主要是通過簡單的路由計(jì)算便可獲得節(jié)點(diǎn)的數(shù)據(jù)傳輸路徑，且需要的路由開銷小，節(jié)點(diǎn)功耗低以及網(wǎng)絡(luò)節(jié)點(diǎn)維護(hù)簡單；缺點(diǎn)主要是層次低的節(jié)點(diǎn)會成為祖先節(jié)點(diǎn)，其作為數(shù)據(jù)傳輸?shù)穆酚陕窂降目赡苄源?，隨著網(wǎng)絡(luò)規(guī)模逐漸增大，拓?fù)浣Y(jié)構(gòu)樹中根節(jié)點(diǎn)附近的路由數(shù)據(jù)負(fù)載會越來越嚴(yán)重，進(jìn)而造成網(wǎng)絡(luò)擁塞和延遲，最終導(dǎo)致網(wǎng)絡(luò)的整體性能降低。

4.2 AODV 路由算法

DSDV 協(xié)議是一個(gè)基于傳統(tǒng)的BellmanFord 路由機(jī)制的表驅(qū)動算法，被認(rèn)為是最早的無線自組網(wǎng)絡(luò)路由協(xié)議。DSDV 在傳統(tǒng)Distance-Vector算法的基礎(chǔ)上采用了序列號機(jī)制，用于區(qū)分路由的新舊程度，防止Distance-Vector算法可能產(chǎn)生的路由環(huán)路。DSDV 采用時(shí)間驅(qū)動和事件驅(qū)動技術(shù)控制路由表的傳送，即每個(gè)移動節(jié)點(diǎn)在本地都保留一張路由表，包括所有有效目的節(jié)點(diǎn)、路由跳數(shù)、目的節(jié)點(diǎn)路由序列號等信息，目的節(jié)點(diǎn)路由序列號用于區(qū)別有效和過期的路由信息，以避免環(huán)路的產(chǎn)生[6]。

AODV 路由協(xié)議在DSDV 協(xié)議的跳路由、序列號、定期廣播機(jī)制的基礎(chǔ)上，加入了DSR 按需路由發(fā)現(xiàn)和維護(hù)機(jī)制。AODV 路由算法在此基礎(chǔ)上有所改進(jìn)，主要是引入路由表，在網(wǎng)絡(luò)節(jié)點(diǎn)的路由表中保存路由信息，減少網(wǎng)絡(luò)中廣播的次數(shù)。AODV算法作為無線傳感網(wǎng)絡(luò)中的經(jīng)典算法，運(yùn)用十分廣泛，算法復(fù)雜度高，消耗的網(wǎng)絡(luò)資源多。針對這種情況，對其路由算法進(jìn)行改進(jìn)，涉及以下幾個(gè)方面：簡化了路由表的項(xiàng)目，刪除了路由跳數(shù)和節(jié)點(diǎn)的先驅(qū)節(jié)點(diǎn)項(xiàng)；簡化了路由路徑的查詢過程，只授權(quán)網(wǎng)絡(luò)的目的節(jié)點(diǎn)對請求數(shù)據(jù)幀發(fā)送響應(yīng)；改進(jìn)了路由維持的機(jī)制，若源節(jié)點(diǎn)在時(shí)鐘定時(shí)器內(nèi)無法接收到目的節(jié)點(diǎn)的確認(rèn)幀，路由算法重新對路徑進(jìn)行計(jì)算，規(guī)劃新的路由路徑； 改進(jìn)了路由環(huán)路形成的條件，基于AODV 路由算法所需開銷小，對其運(yùn)用最優(yōu)化的原理，使用節(jié)點(diǎn)序列號對路由更新情況進(jìn)行區(qū)分，而且目的節(jié)點(diǎn)僅響應(yīng)RREQ 報(bào)文分組。故改進(jìn)后的AODV 路由算法開銷更小、路由路徑更短。

4.3 EHRP 路由算法

EHRP 路由算法是在Tree 路由算法的基礎(chǔ)上進(jìn)行改進(jìn)，以適應(yīng)動態(tài)變化的網(wǎng)絡(luò)環(huán)境。Tree 路由算法的路由選擇只適用于父節(jié)點(diǎn)與子節(jié)點(diǎn)的路由選擇，而EHRP 路由算法在此基礎(chǔ)上增加了路由尋址功能，并在網(wǎng)絡(luò)節(jié)點(diǎn)中增加了一個(gè)路由鄰接表，路由選擇過程中EHRP 路由算法先按照Tree 路由算法計(jì)算路由開銷S1，然后在鄰接路由表中計(jì)算源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路由開銷S2，最后判斷S1和S2+1的大小，將分組發(fā)送到開銷較小的路由節(jié)點(diǎn)上，后續(xù)的節(jié)點(diǎn)類似，直到到達(dá)目的節(jié)點(diǎn)。EHPR算法的路由開銷小，選擇最短路徑進(jìn)行數(shù)據(jù)報(bào)轉(zhuǎn)發(fā)。

5 算法比較及仿真

算法的對比分析采用Matlab 軟件模擬仿真，其過程為：首先組建一個(gè)仿真ZigBee網(wǎng)絡(luò)，在ZigBee組網(wǎng)實(shí)驗(yàn)中，選取70 個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，從分布在網(wǎng)絡(luò)中的70 個(gè)節(jié)點(diǎn)中，選取出一個(gè)ZigBee網(wǎng)絡(luò)的協(xié)調(diào)節(jié)點(diǎn)，同時(shí)，還需要選擇40 個(gè)路由器節(jié)點(diǎn)用來轉(zhuǎn)發(fā)分組，30 個(gè)連接到網(wǎng)絡(luò)中的設(shè)備節(jié)點(diǎn)，用來實(shí)現(xiàn)設(shè)備的連通性，其節(jié)點(diǎn)分布情況如圖2所示。組網(wǎng)過程中，運(yùn)用Tree 型路由拓?fù)浣Y(jié)構(gòu)分配節(jié)點(diǎn)地址，其ZigBee網(wǎng)絡(luò)組網(wǎng)結(jié)果如圖3所示。

圖2 ZigBee網(wǎng)絡(luò)節(jié)點(diǎn)分布情況

圖3 ZigBee網(wǎng)絡(luò)節(jié)點(diǎn)組網(wǎng)結(jié)果

對比分析相同的源節(jié)點(diǎn)和目的節(jié)點(diǎn)的路由選擇算法，對網(wǎng)絡(luò)中的節(jié)點(diǎn)分別采用Tree 路由算法、EHRP 路由算法和AODV 路由算法，然后計(jì)算路由路徑長度。由圖4 可知，Tree 路由算法路徑最長，EHRP 路由算法次之，AODV 路由算法路徑最短。通過對3 種路由算法的對比分析可知，Tree 路由算法路徑的建立可通過計(jì)算網(wǎng)絡(luò)節(jié)點(diǎn)的地址得到；EHRP 路徑的建立則需要建立鄰接表，然后對節(jié)點(diǎn)路徑進(jìn)行計(jì)算和比較，最后獲得最優(yōu)路徑；AODV 路由算法路徑的建立，首先需要建立路由表，即自適應(yīng)路由，通過目的節(jié)點(diǎn)的反饋信息建立路由路徑，最后獲得最短路徑。

圖4 3 種路由算法的路由路徑

綜合分析可知，從節(jié)點(diǎn)能量消耗和存儲使用角度來看，Tree 路由算法節(jié)點(diǎn)能量耗費(fèi)最少，EHRP 路由算法的存儲空間消耗較少，AODV 路由算法的性能最佳。然而在實(shí)際的網(wǎng)絡(luò)環(huán)境中，需要依據(jù)節(jié)點(diǎn)的能量消耗、時(shí)延和負(fù)載均衡等各項(xiàng)性能指標(biāo)選擇最佳的路由算法。一般而言，ZigBee網(wǎng)絡(luò)依據(jù)設(shè)備節(jié)點(diǎn)和直接連接的路由節(jié)點(diǎn)進(jìn)行通信的情況以及當(dāng)路由節(jié)點(diǎn)因能量消耗無法進(jìn)行主動路由的情況，均采用“Cluster-Tree +AODV”混合的路由算法，可以使網(wǎng)絡(luò)的性能達(dá)到最優(yōu)。

6 結(jié)束語

本文主要介紹了ZigBee網(wǎng)絡(luò)的體系結(jié)構(gòu)和組網(wǎng)過程，對ZigBee網(wǎng)絡(luò)常用的幾種路由算法進(jìn)行了分析，重點(diǎn)對Tree算法、EHPR算法和AODV算法的路由開銷、功耗進(jìn)行對比分析。最后，對ZigBee網(wǎng)絡(luò)中的源節(jié)點(diǎn)和目的節(jié)點(diǎn)分別運(yùn)用Tree 路由算法、EHRP 路由算法和AODV 路由算法進(jìn)行模擬仿真，計(jì)算路由路徑。

實(shí)驗(yàn)結(jié)果顯示，根據(jù)具體的節(jié)點(diǎn)能量消耗、數(shù)據(jù)傳輸時(shí)延和數(shù)據(jù)負(fù)載等各項(xiàng)網(wǎng)絡(luò)性能指標(biāo)選擇合適的路由算法，才能使網(wǎng)絡(luò)性能達(dá)到最佳。因此，隨著無線傳感網(wǎng)絡(luò)的發(fā)展，ZigBee 技術(shù)被廣泛應(yīng)用于各個(gè)領(lǐng)域的生產(chǎn)生活中，如智能電網(wǎng)、智能家居等。

[1]ZigBee specification[EB/OL].http://www.zigbee.org.

[2]劉麗鈞，童麗麗.ZigBee 技術(shù)網(wǎng)絡(luò)層的路由算法分析[J].計(jì)算機(jī)與信息技術(shù)，2008，（1）.

[3]ZigBee Alliance.ZigBee architecture overview[EB/OL].http://www.zigbee.org/ en/events/documents，2005.

[4]JAE Y H，SUNGHYUN C，WOOK H K.EHRP:enhanced hierarchical routing protocol for ZigBee mesh networks[J].IEEECommunications Letters，2007.

[5]杜煥軍，張維勇.ZigBee網(wǎng)絡(luò)的路由協(xié)議研究[J].合肥工業(yè)大學(xué)學(xué)報(bào)，2008，31（10）： 1618-1621.

[6]趙新偉,鄭洪飛.Ad hoc網(wǎng)絡(luò)路由協(xié)議分析與仿真[J].計(jì)算機(jī)安全，2011，（7）.