Zigbee的ZBR路由算法的優(yōu)化研究

陳益瑩

(西華師范大學(xué)計(jì)算機(jī)學(xué)院， 四川南充 637000)

0 引言

當(dāng)前無線傳輸?shù)闹饕夹g(shù)主要有Wifi、 藍(lán)牙、 超帶寬和Zigbee等. 經(jīng)過對比發(fā)現(xiàn)， Zigbee有低功耗、 低成本、 高安全等優(yōu)勢， 適合大規(guī)模低速無線傳感的建立. 如今， Zigbee技術(shù)日益成熟， 已經(jīng)廣泛應(yīng)用到各個(gè)領(lǐng)域. 由于種種制約， 國內(nèi)暫無成熟的自主研發(fā)產(chǎn)品， 但是很多高校和研究機(jī)構(gòu)已經(jīng)開始對無線組網(wǎng)技術(shù)進(jìn)行研究.

1 ZBR路由算法

在Zigbee網(wǎng)絡(luò)中， Zigbee協(xié)議主要采用Cluster-Tree算法(樹型網(wǎng)絡(luò)結(jié)構(gòu)路由算法)和AODVjr算法(Ad-Hoc On-Demand Distance Vector， 按需距離矢量路由算法).

Cluster-Tree算法包括地址的分配與尋址路由兩部分. 以樹型拓?fù)錇榛A(chǔ)的Cluster-tree算法是指沿著樹型拓?fù)溥M(jìn)行消息傳輸?shù)乃惴ǎ?它是靜態(tài)的， 不需要存儲(chǔ)路由表， 適用于節(jié)點(diǎn)靜止或者移動(dòng)較少的場合.

AODVjr算法是在AODV算法的基礎(chǔ)上， 對其進(jìn)行簡化提出來的， 其是按需分配的協(xié)議， 只有在路由節(jié)點(diǎn)接到數(shù)據(jù)包， 并且其數(shù)據(jù)包的目的節(jié)點(diǎn)地址不在該路由節(jié)點(diǎn)的路由表中時(shí)才會(huì)進(jìn)行路由發(fā)現(xiàn)， 所以， 路由表中的內(nèi)容是按需建立的.

作為兩種算法的結(jié)合體， 即ZBR算法， 在Zigbee網(wǎng)絡(luò)中， 節(jié)點(diǎn)可以按照樹型結(jié)構(gòu)的父子關(guān)系使用Cluster-Tree算法選擇路徑， 使不具有路由功能的節(jié)點(diǎn)間通過與各自的父節(jié)點(diǎn)間的通信仍然可以發(fā)送數(shù)據(jù)分組和控制分組. 但網(wǎng)絡(luò)中同時(shí)也允許具有路由功能的節(jié)點(diǎn)使用AODVjr算法去發(fā)現(xiàn)路由， 讓具有路由功能的節(jié)點(diǎn)可以不按照父子關(guān)系而直接發(fā)送信息到其通信范圍內(nèi)的其他節(jié)點(diǎn). 但是傳統(tǒng)ZBR算法， AODVjr算法是占了大多數(shù)部分， 而Cluster-tree算法只是在判斷節(jié)點(diǎn)為終端節(jié)點(diǎn)時(shí)， 將其發(fā)送給父節(jié)點(diǎn). 所以ZBR算法并沒有解決AODVjr算法中易引起廣播風(fēng)暴的問題.

2 改進(jìn)算法

本文主要是針對ZBR路由算法， 改進(jìn)Cluster-tree算法和AODVjr算法的不足. 這方面很多人都有研究， 如謝川提出的算法[2]， 就是避免能量較低的節(jié)點(diǎn)， 并對RREQ分組的廣播方向和傳輸距離進(jìn)行控制； 劉瀟花和彭勇提出的算法[3]， 是路由發(fā)現(xiàn)前利用路由節(jié)點(diǎn)來尋找目的節(jié)點(diǎn)， 路由發(fā)現(xiàn)階段， 又通過提出的最短路徑尋址， 提高了節(jié)點(diǎn)生存率； 白樂強(qiáng)等人提出的算法[6]則是基于分簇基礎(chǔ)上， 對轉(zhuǎn)發(fā)任務(wù)進(jìn)行最小化， 以減少能量消耗； Leqiang Bai等提出了基于節(jié)點(diǎn)簇標(biāo)簽的混合算法[7]和基于節(jié)點(diǎn)深度的AODVjr算法[8]； 而王寧提出的則是針對AODVjr故障對其進(jìn)行改進(jìn)， 降低其路由開銷[10].

本文提出的新的改進(jìn)算法， 是在CLuster-tree算法的地址分配基礎(chǔ)上， 控制RREQ分組的廣播方向和廣播跳數(shù)兩個(gè)方面， 從而達(dá)到減少路由開銷的目的.

2.1 限制廣播方向

ZBR算法結(jié)合了兩種算法. 假設(shè)在一個(gè)樹簇網(wǎng)絡(luò)中，Cm=5，Rm=4，Lm=5， 由luster-tree算法的地址分配算法為

(1)

由(1)可知， 深度d=0時(shí)， 就只有協(xié)調(diào)器一個(gè)節(jié)點(diǎn)； 深度d=1時(shí)，Cskip(d)=106； 深度d=2時(shí)，Cskip(d)=26； 深度d=3時(shí)，Cskip(d)=6； 深度d=4時(shí)，Cskip(d)=1. 根據(jù)Cskip可得此樹簇網(wǎng)絡(luò)的節(jié)點(diǎn)結(jié)構(gòu)圖如圖1所示.

圖1 樹簇網(wǎng)絡(luò)節(jié)點(diǎn)結(jié)構(gòu)圖

父節(jié)點(diǎn)根據(jù)公式(1)， 對入網(wǎng)的子節(jié)點(diǎn)分配完地址后， 需要對這個(gè)網(wǎng)絡(luò)進(jìn)行分簇， 已知Cskip(1)=106. 劃分簇時(shí)， 因?yàn)閰f(xié)調(diào)器的地址為0， 那么從協(xié)調(diào)器的地址+1， 第一次劃分簇的計(jì)算公式為

(2)

第一次劃分簇的節(jié)點(diǎn)地址范圍的計(jì)算為：

(3)

分簇完的網(wǎng)絡(luò)， 廣播分組方向存在著兩種情況：

(1)目的節(jié)點(diǎn)和源節(jié)點(diǎn)地址不在同一個(gè)簇， 需要判斷其傳遞信息廣播分組的方向；

(2)目的節(jié)點(diǎn)和源節(jié)點(diǎn)地址在同一個(gè)簇， 進(jìn)行第二次甚至更多次分簇， 來判斷簇內(nèi)兩節(jié)點(diǎn)廣播的方向.

首先判斷兩個(gè)節(jié)點(diǎn)是否在同一個(gè)簇內(nèi). 根據(jù)下列公式(4)得出目的節(jié)點(diǎn)和源節(jié)點(diǎn)所在簇的數(shù)字An和A(D是源節(jié)點(diǎn)地址，Dn是目的節(jié)點(diǎn)地址)，

(4)

再判斷A和An的大小，A=An， 則源節(jié)點(diǎn)和目的節(jié)點(diǎn)在同一簇；A≠An， 則不在同一簇. 判斷出源節(jié)點(diǎn)和目的節(jié)點(diǎn)屬于第一種情況(A≠An)， 接下來就是判斷從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的廣播分組方向. 存在的情況有以下幾種：

1)協(xié)調(diào)器連接的子節(jié)點(diǎn)所在簇集中在一個(gè)方向， 就只能沿著一個(gè)方向傳播；

2)協(xié)調(diào)器連接的子節(jié)點(diǎn)所在簇均勻分布， 簇與簇之間都可以進(jìn)行路由廣播；

3)協(xié)調(diào)器連接的子節(jié)點(diǎn)所在簇相隔甚遠(yuǎn)， 超出了路由廣播范圍， 只能依靠協(xié)調(diào)器進(jìn)行轉(zhuǎn)發(fā).

這里只針對協(xié)調(diào)器連接的子節(jié)點(diǎn)所在簇均勻分布的情況， 限制其廣播方向. 根據(jù)其Cm參數(shù)， 可以知道分簇的最大簇?cái)?shù)為Cm， 那么這個(gè)數(shù)用C來表示， 即C=Cm. 那么可得限制廣播方向的公式：

(5)

如圖1，C=Cm=5， 則C/2=2.5. 假設(shè)目的節(jié)點(diǎn)簇?cái)?shù)An=1， 源節(jié)點(diǎn)簇?cái)?shù)A=3， 那么|An-A|=2C/2， 再比較An>A， 所以源節(jié)點(diǎn)到目的節(jié)點(diǎn)的廣播方向是往左. 通過這樣的方式， 可以限制不同節(jié)點(diǎn)所在簇之間的廣播方向.

對于第二種情況(A=An)， 同第一次分簇一樣， 直接利用Cskip(d)繼續(xù)分簇. 首先， 計(jì)算出下一級深度Cskip(d)的值， 然后再根據(jù)公式(5)判斷出目的節(jié)點(diǎn)和源節(jié)點(diǎn)是否在同簇， 再循環(huán)以上步驟， 直至傳送到目的節(jié)點(diǎn).

2.2 限制廣播分組跳數(shù)

在AODVjr算法中， 限制其廣播方向只能避免一部分的路由開銷， 所以， 在分簇限制廣播方向的基礎(chǔ)上提出了一種理想跳數(shù)的說法. 這個(gè)理想跳數(shù)就是指在分簇的基礎(chǔ)上， 簇間利用Cluster-Tree算法進(jìn)行傳遞信息， 因?yàn)檫@種算法路由消耗低. 而簇間， 則用AODVjr算法， 這樣可以避免Cluster-Tree算法明顯的缺點(diǎn).

網(wǎng)絡(luò)中加入理想跳數(shù)后的流程圖如圖2所示.

圖2 理想跳數(shù)流程圖

由圖2的流程圖可知， 對圖1所示網(wǎng)絡(luò)， 假設(shè)節(jié)點(diǎn)9到節(jié)點(diǎn)28， 通過公式(4)除以Cskip(1)可以判斷出第一次分簇在同一個(gè)簇內(nèi)， 再通過公式(4)除以Cskip(2)判斷出第二次分簇不在同一簇， 為相鄰簇. 所以將節(jié)點(diǎn)9先廣播一次， 看是否可以廣播到相鄰簇， 可以則直接從節(jié)點(diǎn)9廣播出去， 不可以則將信息傳遞到上一級深度， 繼續(xù)廣播一次， 直至深度為2.

源節(jié)點(diǎn)首先一次廣播， 然后傳到上一級深度父節(jié)點(diǎn)再進(jìn)行一次廣播， 用這樣的方法， 來達(dá)到一個(gè)簇內(nèi)低開銷， 簇間少跳數(shù)的目的， 這就是理想跳數(shù)的基礎(chǔ). 理想跳數(shù)L的公式為：

(6)

這個(gè)理想跳數(shù)就是在簇內(nèi)利用Cluster-Tree算法， 在簇間利用AODVjr算法， 同時(shí)避免簇內(nèi)兩個(gè)節(jié)點(diǎn)多余的開銷， 并利用多次分簇， 循環(huán)這個(gè)步驟， 使得一個(gè)節(jié)點(diǎn)除了其父節(jié)點(diǎn)和子節(jié)點(diǎn)需要Cluster-Tree算法外， 其余的可以利用AODVjr算法廣播分組. 同時(shí)， 在理想跳數(shù)的基礎(chǔ)上， 簇間源節(jié)點(diǎn)不用向其子節(jié)點(diǎn)傳遞信息， 除非這個(gè)節(jié)點(diǎn)知道為其子節(jié)點(diǎn)還是其父節(jié)點(diǎn).

3 仿真實(shí)驗(yàn)及其結(jié)果分析

為了驗(yàn)證改進(jìn)的結(jié)果， 用NS-2.35進(jìn)行仿真. 先是在NS-2.35自帶路由算法的基礎(chǔ)上添加ZBR算法， 然后在路由開銷控制方面對其AODVjr算法進(jìn)行改進(jìn).

對ZBR改進(jìn)算法的實(shí)驗(yàn)， 沒有考慮節(jié)點(diǎn)移動(dòng)情況， 仿真的是靜止的節(jié)點(diǎn)， 需要確定一些必須確定的參數(shù)： 網(wǎng)絡(luò)節(jié)點(diǎn)分布范圍為200m×200m； 采用CBR作為數(shù)據(jù)信息源；Cm、Rm、Lm的值； 節(jié)點(diǎn)通信半徑為30m； 網(wǎng)絡(luò)中節(jié)點(diǎn)的結(jié)構(gòu)圖； 實(shí)驗(yàn)仿真時(shí)間為50s.

節(jié)點(diǎn)結(jié)構(gòu)圖為圖1， 節(jié)點(diǎn)一共有27個(gè)， 節(jié)點(diǎn)名稱依次設(shè)置為node_(0)-node_(26),其中將對應(yīng)地址為29,55,10,36,37,110,347的節(jié)點(diǎn)設(shè)置為RN-， 其它默認(rèn)RN+. 實(shí)驗(yàn)中使用的是ZBR算法， 如果源節(jié)點(diǎn)為以上節(jié)點(diǎn)， 將其信息傳送給其父節(jié)點(diǎn)， 再利用父節(jié)點(diǎn)傳遞到其它節(jié)點(diǎn)； 除此之外， 其它節(jié)點(diǎn)同AODVjr算法中一致.

在仿真實(shí)驗(yàn)中， 源節(jié)點(diǎn)選擇了兩個(gè)： 節(jié)點(diǎn)3和節(jié)點(diǎn)55， 發(fā)送的目的節(jié)點(diǎn)分別為節(jié)點(diǎn)107和節(jié)點(diǎn)214. 節(jié)點(diǎn)3到節(jié)點(diǎn)107的信息， 開始時(shí)間為0.5s， 結(jié)束時(shí)間為49.5s； 而節(jié)點(diǎn)55到節(jié)點(diǎn)214的信息， 開始時(shí)間為1s， 結(jié)束時(shí)間為49s.

3.1 端到端時(shí)延delay

端到端時(shí)延， 是由三部分組成： 傳輸時(shí)延、 封裝時(shí)延和排隊(duì)時(shí)延. 計(jì)算端到端延遲， 就是計(jì)算一個(gè)數(shù)據(jù)包目的節(jié)點(diǎn)的接收時(shí)間與源節(jié)點(diǎn)的發(fā)送時(shí)間之差， 也就是說， 接收端節(jié)點(diǎn)收到數(shù)據(jù)包的時(shí)間Ts減去發(fā)送端節(jié)點(diǎn)發(fā)出數(shù)據(jù)包的時(shí)間Tf就是端到端延遲delay， 計(jì)算公式如下：

delay=Ts-Tf

(7)

然后寫出計(jì)算端到端時(shí)延delay的awk文件， 再根據(jù)仿真得到的.tr文件得出繪制三種算法的抖動(dòng)率文件CL_delay、 AODVjr_delay、 new_delay， 最后利用gnuplot繪制出Cluster-tree算法、 AODVjr算法和改進(jìn)后ZBR算法關(guān)于端到端時(shí)延delay的比較圖， 其比較圖如圖3所示.

圖3 三種算法端到端時(shí)延delay比較圖

Cluster-tree算法， ZBR算法和改進(jìn)后的算法， 讓兩個(gè)不同源節(jié)點(diǎn)在不同時(shí)間段發(fā)送信息， 對比這三種算法下的端到端時(shí)延delay. 仿真結(jié)果表明， Cluster-tree算法會(huì)因?yàn)槠渌垂?jié)點(diǎn)發(fā)送信息. 而導(dǎo)致時(shí)延增加， 后其它節(jié)點(diǎn)停止發(fā)送信息， 則其端到端時(shí)延delay又變回以前的時(shí)延值； 在ZBR算法中， 同樣也是兩個(gè)源節(jié)點(diǎn)在不同時(shí)間段發(fā)送信息， 但由圖3可以看出， 在仿真前期， ZBR算法時(shí)延較低， 并沒有因?yàn)槠渌垂?jié)點(diǎn)的加入而導(dǎo)致時(shí)延增加， 但隨著仿真時(shí)間的增長， 特別是20～30s期間， 其端到端時(shí)延delay急劇增加， 增加之后其端到端時(shí)延delay波動(dòng)較大， 且高居不下； 而改進(jìn)后的算法， 因?yàn)槎啻问褂昧薈luster-tree算法， 且還用AODVjr算法進(jìn)行輔助， 所以其端到端時(shí)延delay較低， 而且比較穩(wěn)定， 并沒有因?yàn)槠渌垂?jié)點(diǎn)和隨著時(shí)間而有所變化.

3.2 抖動(dòng)率jitter結(jié)果比較

抖動(dòng)率是時(shí)延的變化量， 即最大時(shí)延和最小時(shí)延的時(shí)間差， 主要是表示一個(gè)網(wǎng)絡(luò)的穩(wěn)定性. 抖動(dòng)率越小， 網(wǎng)絡(luò)越穩(wěn)定； 抖動(dòng)率越大， 網(wǎng)絡(luò)越不穩(wěn)定. 對于一個(gè)網(wǎng)絡(luò)而言， 理論上是越穩(wěn)定越好， 即抖動(dòng)率越小越好. 抖動(dòng)率的計(jì)算方法是將兩個(gè)相鄰數(shù)據(jù)包時(shí)延時(shí)間差除以這兩個(gè)相鄰數(shù)據(jù)包的序號差得到， 即

(8)

寫出計(jì)算抖動(dòng)率的awk文件， 再根據(jù)仿真得到的.tr文件得出繪制三種算法的抖動(dòng)率文件CL_jitter、 AODVjr_jitter、 new_jitter， 最終利用gnuplot繪制出Cluster-tree算法、 AODVjr算法和改進(jìn)后ZBR算法關(guān)于抖動(dòng)率jitter的比較圖， 如圖4所示.

圖4 三種算法抖動(dòng)率jitter比較圖

其中， 黑色的線條代表Cluster-tree算法， 在另一個(gè)源節(jié)點(diǎn)開始發(fā)送信息時(shí)， 抖動(dòng)率增加， 結(jié)束發(fā)送信息時(shí)， 抖動(dòng)率恢復(fù)， 一直平穩(wěn). 而黃色線條代表的AODVjr算法， 抖動(dòng)率時(shí)增時(shí)減， 幅度較大， 說明此算法中網(wǎng)絡(luò)不穩(wěn)定. 最后則是紅色線條代表的改進(jìn)后的新算法， 在數(shù)據(jù)傳輸過程中， 較少使用AODVjr算法， 抖動(dòng)幅度較小， 且一直平穩(wěn).

3.3 丟包率loss結(jié)果比較

丟包率是在實(shí)驗(yàn)過程中， 丟失的數(shù)據(jù)包數(shù)量占據(jù)發(fā)送數(shù)據(jù)包的比例. 寫出計(jì)算丟包率loss的awk文件， 再根據(jù)仿真得到的.tr文件得出繪制三種算法的抖動(dòng)率文件CL_loss、 AODVjr_loss、 new_loss. CL_loss丟包率如圖5所示、 AODVjr_loss丟包率如圖6所示、 new_loss丟包率如圖7所示.

圖5 CL_loss丟包率

圖6 AODVjr_loss丟包率

圖7 new_loss丟包率

在三種算法比較圖中， 發(fā)現(xiàn)三種算法中AODVjr算法發(fā)送最多， 其次是Cluster-tree算法， 最后是改進(jìn)后的新算法.

3.4 吞吐量throughout結(jié)果比較

吞吐量是指在單位時(shí)間內(nèi)， 某個(gè)節(jié)點(diǎn)發(fā)送和接收的數(shù)據(jù)量. 寫出計(jì)算吞吐量throughout的awk文件， 再根據(jù)仿真得到的.tr文件得出繪制三種算法的抖動(dòng)率文件CL_throughout、 AODVjr_throughout、 new_throughout， 最終利用gnuplot繪制出Cluster-tree算法、 AODVjr算法和改進(jìn)后ZBR算法關(guān)于吞吐量throughout的比較圖， 如圖8所示.

圖8 三種算法吞吐量throughout比較圖

同樣將Cluster-tree算法、 AODVjr算法和改進(jìn)后的算法進(jìn)行比較， 讓兩個(gè)源節(jié)點(diǎn)發(fā)送信息， 對比三種情況下的吞吐量. 通過圖8的仿真比較圖可以看出， Cluster-tree算法吞吐量最大， 改進(jìn)后的算法緊隨其后排第二， 最后的是AODVjr算法， 吞吐量最低. 因?yàn)閆BR算法為兩種算法的結(jié)合， 所以在單位時(shí)間內(nèi)， 改進(jìn)后的ZBR算法的吞吐量比Cluster-tree算法低， 但是比AODVjr算法要高.

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

在Cluster-tree算法中， 節(jié)點(diǎn)傳送比較單一， 不需要存儲(chǔ)路由表， 對信息傳送的響應(yīng)也較快， 所以很明顯看出不管是端到端時(shí)延delay、 抖動(dòng)率jitter、 丟包率loss還是吞吐量throughout， 都是具有優(yōu)勢的. 但是其缺點(diǎn)也比較明顯， 就是目的節(jié)點(diǎn)即使就在附近也不能對其進(jìn)行直接傳送， 必須要從其拓?fù)浣Y(jié)構(gòu)傳送. 這會(huì)導(dǎo)致傳送速度變慢， 在根節(jié)點(diǎn)附近的節(jié)點(diǎn)也會(huì)多次轉(zhuǎn)發(fā)利用導(dǎo)致其能量消耗過快， 出現(xiàn)過早“死亡”. 這就是為什么Cluster-tree算法有優(yōu)勢卻很少使用的原因， 但因?yàn)槠鋬?yōu)勢， 又不能放棄樹簇算法， 所以將樹簇算法和AODVjr算法初步結(jié)合的ZBR算法進(jìn)行改進(jìn)得到一個(gè)新的算法. 通過對比， 發(fā)現(xiàn)改進(jìn)后的新算法雖然比起Cluster-tree算法還有所欠缺， 但添加了AODVjr算法， 可以避免Cluster-tree算法的劣勢， 又比AODVjr算法具有一定優(yōu)勢.

4 結(jié)語

Zigbee網(wǎng)絡(luò)是一種新興的無線傳感器網(wǎng)絡(luò)， 具有廣闊的應(yīng)用場合和發(fā)展前景. 本文僅僅是對傳統(tǒng)Zigbee網(wǎng)絡(luò)中的Cluster-tree和AODVjr算法的一種缺點(diǎn)進(jìn)行分析改進(jìn)， 提出一種改進(jìn)算法， 該算法針對AODVjr中傳輸數(shù)據(jù)包的方向和跳數(shù)進(jìn)行了限制， 可以有效降低傳輸過程中多余的路由損耗， 以降低路由開銷. 下一步的工作將會(huì)在此基礎(chǔ)上在能量方面對能量均衡和節(jié)能方面做更多改進(jìn)， 爭取達(dá)到在降低路由開銷的同時(shí)延長網(wǎng)絡(luò)壽命.