ZigBee路由算法的研究和改進(jìn)

劉多多 吳靜

摘 要：ZigBee技術(shù)作為一種新興的短距離無線通信技術(shù)，具有自組網(wǎng)、低成本和低功耗的優(yōu)勢。伴隨著物聯(lián)網(wǎng)等高新科技的發(fā)展，對ZigBee技術(shù)的改進(jìn)成為了關(guān)鍵問題。文中首先論述了ZigBee技術(shù)的基本協(xié)議和網(wǎng)絡(luò)配置，之后針對簇樹拓?fù)浣Y(jié)構(gòu)，分別對Cluster-Tree算法和AODVjr算法進(jìn)行了重點(diǎn)解析和研究。針對網(wǎng)絡(luò)中AODVjr算法路由發(fā)現(xiàn)過程中的RREQ分組導(dǎo)致洪泛的缺點(diǎn)，從分簇角度出發(fā)，對傳統(tǒng)ZigBee路由算法進(jìn)行了優(yōu)化和改進(jìn)。并通過NS-2模擬仿真實(shí)驗(yàn)，主要從報文發(fā)送成功率和端到端時延等方面入手進(jìn)行對比。實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法能實(shí)現(xiàn)網(wǎng)絡(luò)負(fù)載均衡，使網(wǎng)絡(luò)生存時間最大化。

關(guān)鍵詞：ZigBee網(wǎng)絡(luò)；Cluster-Tree；AODVjr；路由算法；NS-2

中圖分類號：TP391 文獻(xiàn)標(biāo)識碼：A 文章編號：2095-1302（2018）04-00-03

0 引 言

ZigBee技術(shù)得益于其距離較短、復(fù)雜度較低、能耗較低和成本較低的優(yōu)勢，不僅適用于無線傳感器網(wǎng)絡(luò)領(lǐng)域，在軍事、環(huán)境監(jiān)控、醫(yī)療健康、智能家居和工業(yè)應(yīng)用等領(lǐng)域也有著廣泛的應(yīng)用。

ZigBee協(xié)議基于IEEE 802.15.4定義的物理層（PHY）和媒體介質(zhì)訪問層（MAC）制定，之后ZigBee聯(lián)盟在此基礎(chǔ)上對傳輸層（TL）、網(wǎng)絡(luò)層（NWK）和應(yīng)用層（APL）進(jìn)行了完善[1]。其中，網(wǎng)絡(luò)層主要負(fù)責(zé)網(wǎng)絡(luò)的組件、發(fā)現(xiàn)新路由及維護(hù)已有路由，路由算法是網(wǎng)絡(luò)層的核心。

1 ZigBee網(wǎng)絡(luò)概述

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

ZigBee網(wǎng)絡(luò)通常包括三種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)：星型拓?fù)浣Y(jié)構(gòu)、簇樹型拓?fù)浣Y(jié)構(gòu)和網(wǎng)狀型拓?fù)浣Y(jié)構(gòu)。其設(shè)置可根據(jù)不同的實(shí)際需求進(jìn)行變化[2]。常見拓?fù)浣Y(jié)構(gòu)如圖1所示。

1.2 ZigBee網(wǎng)絡(luò)配置

ZigBee聯(lián)盟和IEEE 802.15.4對網(wǎng)絡(luò)中設(shè)備的定義有所區(qū)別。根據(jù)功能的不同，IEEE 802.15.4將網(wǎng)絡(luò)中的設(shè)備分為全功能設(shè)備（FFD）和精簡功能設(shè)備（RFD）[3]。其中，F(xiàn)FD可擔(dān)任網(wǎng)絡(luò)協(xié)調(diào)器， 也能用作終端設(shè)備，與RFD 或其他FFD通信。而RFD僅支持星型結(jié)構(gòu)，只能與FFD通信。ZigBee聯(lián)盟根據(jù)設(shè)備功能的區(qū)別劃分了協(xié)調(diào)器、路由器和終端設(shè)備等。協(xié)調(diào)器和路由器均為FFD節(jié)點(diǎn)，通常網(wǎng)絡(luò)最外圍的終端節(jié)點(diǎn)由RFD來充當(dāng)。

1.3 ZigBee網(wǎng)絡(luò)地址分配

ZigBee采用分布式尋址方式分配網(wǎng)絡(luò)地址[4]。當(dāng)網(wǎng)絡(luò)中的一個節(jié)點(diǎn)同意外部節(jié)點(diǎn)通過自己加入該網(wǎng)絡(luò)時，兩個節(jié)點(diǎn)建立父子關(guān)系。此后，父節(jié)點(diǎn)會為該新入節(jié)點(diǎn)分配獨(dú)一無二的網(wǎng)絡(luò)地址。整個網(wǎng)絡(luò)結(jié)構(gòu)的地址分配涉及三個參數(shù)：Lm（網(wǎng)絡(luò)的最大深度），Cm（每個父節(jié)點(diǎn)最多擁有的子節(jié)點(diǎn)數(shù)量）， Rm（子節(jié)點(diǎn)最多可作為路由器節(jié)點(diǎn)的個數(shù)）[5]。上述3個參數(shù)均由協(xié)調(diào)器決定。

當(dāng)網(wǎng)絡(luò)中的父節(jié)點(diǎn)為子節(jié)點(diǎn)分配地址時，若d表示父節(jié)點(diǎn)的深度，則Cskip（d）地址偏移量可分配地址段的大小為：

首先將協(xié)調(diào)器深度設(shè)為0，則其余節(jié)點(diǎn)按照排列順序依次將深度加1。有路由能力的子節(jié)點(diǎn)設(shè)備分配地址用Cskip（d）表示，依據(jù)式（2）進(jìn)行地址分配，依據(jù)式（3）為終端設(shè)備進(jìn)行地址分配：

2 ZigBee路由算法分析

ZigBee網(wǎng)絡(luò)層支持樹型（Cluster-Tree），AODVjr和ZBR三種算法 。

2.1 樹型（Cluster-Tree）路由算法

該算法中，當(dāng)?shù)刂窞锳，深度為d的ZigBee節(jié)點(diǎn)收到目的節(jié)點(diǎn)地址為D的數(shù)據(jù)包后，可通過（4）式對該節(jié)點(diǎn)的真實(shí)性進(jìn)行驗(yàn)證，即：

若是，則通過式（5）計算下一跳地址，即：

若不是，則數(shù)據(jù)包順著樹結(jié)構(gòu)被轉(zhuǎn)發(fā)至父節(jié)點(diǎn)。Cluster-Tree算法處理流程如圖2所示。

2.2 AODVjr 路由算法

AODVjr是在AODV基礎(chǔ)上優(yōu)化路由的發(fā)現(xiàn)和維護(hù)過程所得[6]。AODVjr和AODV的主要區(qū)別如下：

（1）AODVjr路由算法中去掉了AODV路由算法中的目的節(jié)點(diǎn)序列號。為了使路由不存在回路，AODVjr路由算法中規(guī)定只有目的節(jié)點(diǎn)可以進(jìn)行相應(yīng)的RREQ分組，即便中間節(jié)點(diǎn)有到目的節(jié)點(diǎn)的路徑也不可以回復(fù)RREQ。

（2）AODVjr路由算法通過目的節(jié)點(diǎn)向源節(jié)點(diǎn)發(fā)送相應(yīng)連接信息維系路由。若沒有收到目的節(jié)點(diǎn)發(fā)來的相應(yīng)信號，則判斷此路徑失效，必要時重新進(jìn)行路由發(fā)現(xiàn)。

（3）AODVjr路由算法中去掉了AODV 中的“先驅(qū)節(jié)點(diǎn)列表”，以簡化路由表結(jié)構(gòu)。

當(dāng)源節(jié)點(diǎn)中沒有直接到達(dá)目的節(jié)點(diǎn)的路由時，便會向鄰居節(jié)點(diǎn)廣播RREQ包，請求幫忙查詢路徑。當(dāng)某個節(jié)點(diǎn)接收到 RREQ包時，首先會判斷自己是否有到達(dá)目的節(jié)點(diǎn)的路徑。若有到達(dá)的路徑，則會依據(jù)路由代價的評估確定是否更新其路由表；若沒有路徑，則接著廣播此RREQ包，同時建立相應(yīng)的反向路由[7]。AODVjr路由查找模式如圖3所示。

2.3 ZBR算法

ZBR算法既具有Cluster-Tree算法出色的實(shí)時性，又保留了AODVjr進(jìn)行動態(tài)路由選擇的優(yōu)勢，由前兩種算法有機(jī)結(jié)合而產(chǎn)生[8]。

按照拓?fù)浣Y(jié)構(gòu)中存儲空間和節(jié)點(diǎn)能量的差異，ZBR算法把網(wǎng)絡(luò)中的主干節(jié)點(diǎn)分為兩類，即RN+節(jié)點(diǎn)和RN-節(jié)點(diǎn)[9]，且均為全功能節(jié)點(diǎn)。RN+節(jié)點(diǎn)由于具有高能量和大內(nèi)存的特點(diǎn)，可以同時運(yùn)行Cluster-Tree和AODVjr兩種路由算法，而RN-節(jié)點(diǎn)只能運(yùn)行Cluster-Tree一種路由算法[10]。ZBR路由算法處理流程如圖4所示。

3 路由算法的優(yōu)化策略

Cluster-Tree算法雖然有縮短時延和數(shù)據(jù)聚合方面的優(yōu)勢，但也有缺點(diǎn)，即由于非自適應(yīng)算法的特性，使其在網(wǎng)絡(luò)生存時延最大化方面有所不及。而AODVjr算法雖然在路由查找功能方面具有靈活多變的優(yōu)勢，但因需要維護(hù)路由表而產(chǎn)生延遲，且容易產(chǎn)生RREQ廣播風(fēng)暴。

為此，本文提出了一種簇樹網(wǎng)絡(luò)路由策略，即對Cluster-Tree + AODVjr進(jìn)行優(yōu)化，該算法融合了上述兩種改進(jìn)算法的優(yōu)點(diǎn)。

3.1 簇的建立過程

首先將ZigBee 網(wǎng)絡(luò)分成若干簇，通過選定簇首→廣播簇首→建立簇→生成相應(yīng)調(diào)度機(jī)制 。

單個簇包括多個節(jié)點(diǎn)，根據(jù)功能分為3種類型：網(wǎng)關(guān)節(jié)點(diǎn)、簇成員和簇首。簇建立的規(guī)則如下：

（1）將中心節(jié)點(diǎn)當(dāng)作簇首；

（2）充當(dāng)簇首的節(jié)點(diǎn)必須擁有路由能力；

（3）充當(dāng)簇首的節(jié)點(diǎn)網(wǎng)絡(luò)深度必須為偶數(shù)；

（4）若節(jié)點(diǎn)網(wǎng)絡(luò)深度為奇數(shù)，則屬于其父節(jié)點(diǎn)的簇；

（5）終端節(jié)點(diǎn)的簇屬于其父節(jié)點(diǎn)的簇。

簇首負(fù)責(zé)在建立路由后進(jìn)行廣播，建立簇結(jié)構(gòu)，負(fù)責(zé)對簇成員的數(shù)據(jù)進(jìn)行收集，并在融合處理后發(fā)送給網(wǎng)關(guān)節(jié)點(diǎn)。

形成簇之后，判斷網(wǎng)絡(luò)深度，若該節(jié)點(diǎn)的網(wǎng)絡(luò)深度為偶數(shù)，則向外廣播RREQ。當(dāng)一個節(jié)點(diǎn)收到RREQ時，便向源節(jié)點(diǎn)發(fā)送確認(rèn)信息，發(fā)送RREQ的源節(jié)點(diǎn)將收到的確認(rèn)信息與規(guī)定的最小信號強(qiáng)度進(jìn)行比較，若大于該值，則在鄰居表中添加此節(jié)點(diǎn)。最后，通過對比鄰居表中周圍節(jié)點(diǎn)的數(shù)目將節(jié)點(diǎn)數(shù)最多的節(jié)點(diǎn)選作為簇首，同時，將此節(jié)點(diǎn)的短地址作為該簇的標(biāo)簽。

若一個節(jié)點(diǎn)被選作簇首節(jié)點(diǎn)，則向其周圍節(jié)點(diǎn)發(fā)送廣播報文，收到廣播報文的節(jié)點(diǎn)發(fā)送簇加入報文，當(dāng)簇首發(fā)送對應(yīng)的加入響應(yīng)后，成功加入到該簇。

3.2 路由過程的建立與維護(hù)

當(dāng)源節(jié)點(diǎn)需要給目標(biāo)節(jié)點(diǎn)發(fā)送數(shù)據(jù)時，首先在路由表中查尋目標(biāo)節(jié)點(diǎn)的路徑。若路由存在且有效，則直接發(fā)送數(shù)據(jù)；若路由不存在，則源節(jié)點(diǎn)通過泛洪進(jìn)行路由發(fā)現(xiàn)。建立路由后，源節(jié)點(diǎn)向周圍節(jié)點(diǎn)廣播由其創(chuàng)建的一個路由請求包RREQ。若一個鄰居節(jié)點(diǎn)收到RREQ，則通過計算得出目的節(jié)點(diǎn)的簇標(biāo)簽，并將該簇標(biāo)簽的一個路由接入點(diǎn)加入到其鄰居表中。若一個中間節(jié)點(diǎn)收到RREQ，則進(jìn)行路由成本的比較，若該路由成本較低，則更新路由搜索表信息，并且在到達(dá)目的節(jié)點(diǎn)之前持續(xù)廣播。

當(dāng)目標(biāo)節(jié)點(diǎn)收到路由請求后，建立反向路徑，并生成一個RREP包，該RREP包中含有最新的各類信息，沿反向路徑送至源節(jié)點(diǎn)。當(dāng)源節(jié)點(diǎn)和中間節(jié)點(diǎn)收到RREP包后，開始進(jìn)行目標(biāo)節(jié)點(diǎn)路由的建立和系列號等信息的更新。該路由過程建立完成后，源節(jié)點(diǎn)向其簇首發(fā)送一個攜帶有路由信息的路由確認(rèn)包，簇首在收到該確認(rèn)包后再廣播一個路由更新信息，簇成員收到該信息后，完成節(jié)點(diǎn)新建路由信息的共享。

此改進(jìn)表現(xiàn)出了對分簇思想應(yīng)用路由算法的巨大優(yōu)勢，簇頭負(fù)責(zé)融合數(shù)據(jù)，減少了數(shù)據(jù)通信量。同時，分布式算法又可以在拓?fù)浣Y(jié)構(gòu)得到巨大的施展空間，在大規(guī)模網(wǎng)絡(luò)場景下有著良好的發(fā)揮余地。并且由于簇內(nèi)節(jié)點(diǎn)長時間關(guān)閉通信模塊，又達(dá)到了網(wǎng)絡(luò)時延的效果。

4 實(shí)驗(yàn)結(jié)果分析

采用NS-2軟件對改進(jìn)后的算法和AODVjr進(jìn)行仿真實(shí)驗(yàn)比較，從發(fā)送報文的成功率和平均時延兩個方面進(jìn)行分析。

報文發(fā)送成功率比較如圖5所示，從圖中可以看出，新算法發(fā)送報文的成功率與原算法相比有了明顯提升。

兩種算法的平均時延對比如圖6所示。由圖6可知，在源節(jié)點(diǎn)數(shù)目等同的實(shí)驗(yàn)條件下，隨著節(jié)點(diǎn)數(shù)目增加，時延呈上升態(tài)勢。經(jīng)分析可知，超過正常范圍數(shù)目的源節(jié)點(diǎn)增加了網(wǎng)絡(luò)擁塞程度，從而增加了成功接收數(shù)據(jù)包的時間。而在源節(jié)點(diǎn)數(shù)目相同的情況下，優(yōu)化后的算法擁有較小時延。

5 結(jié) 語

本文在分析ZigBee路由算法的基礎(chǔ)上，提出了一種改進(jìn)算法。將鄰居列表引入改進(jìn)后的算法，在數(shù)據(jù)傳輸過程中，對路由跳數(shù)等方面進(jìn)行了重新考量，同時從基本策略方面對AODVjr進(jìn)行了改進(jìn)，考慮到能量的維度，使網(wǎng)絡(luò)生存時間得到了有效延長，提升了網(wǎng)絡(luò)效率，并通過相關(guān)仿真實(shí)驗(yàn)對以上結(jié)論進(jìn)行了驗(yàn)證。

參考文獻(xiàn)

[1] 唐寅.基于 ZigBee 的傳統(tǒng)路由協(xié)議研究與優(yōu)化 [D]. 武漢：湖北大學(xué)，2013.

[2] 耿萌.ZigBee 路由協(xié)議研究與分析 [D].鄭州： 中國人民解放軍信息工程大學(xué) ，2006.

[3] 袁安娜.基于 ZigBee 網(wǎng)絡(luò)的能量均衡路由算法研究 [D].哈爾濱：哈爾濱理工大學(xué)，2014.

[4] 班艷麗，柴喬林，王芳.改進(jìn)的 ZigBee 網(wǎng)絡(luò)路由算法[J].計算機(jī)工程與應(yīng)用，2009，45（5）：95-97.

[5] 凌志浩，周怡頲，鄭麗國.ZigBee無線通信技術(shù)及其應(yīng)用探討[J]. 華東理工大學(xué)學(xué)報（自然科學(xué)版），2006， 32（7）：801-805.

[6] 彭瑜.低功耗、低成本、高可靠性、低復(fù)雜度的無線電通信協(xié)議——ZigBee[J].自動化儀表，2005，26（5）：1-4.

[7] 鮑鳳卿.基于NS-2的ZigBee網(wǎng)絡(luò)節(jié)點(diǎn)接入的研究[J].信息技術(shù)，2008，11（5）：95-98.

[8] 錢志鴻，朱爽，王雪.基于分簇機(jī)制的 ZigBee 混合路由能量優(yōu)化算法[J].計算機(jī)學(xué)報，2013， 36（3）：485-493.

[9] 吳非.基于ZigBee技術(shù)的無線傳感器網(wǎng)絡(luò)路由算法研究[D].北京：北京郵電大學(xué)，2015.

[10] 蔣培成，陳鳴，李兵.一種優(yōu)化ZigBee性能的綜合加權(quán)路由算法[J].小微型計算機(jī)系統(tǒng)，2013，34（9）：2014-2017.

[11] CHEN S K，WANG P C.Shortcut anycast tree Routing in MANETs[J].IEEE international conference on advanced information networking & applications，2012，11（1）：635-640.

[12] FENG S，WANG M G，Yu Q L，et al.Improved neighbor table-based tree routing strategies in ZigBee wireless networks[C]. International Conference on Information Science & Technology，2015 ： 513-518.

[13] HOU T C，TSAI T J.An Access based clustering protocol for multihop wireless Ad-Hoc networks[J].IEEE joumal on selected areas in communications，2001，19（7）：1201-1210.