陳 偉

(安慶職業(yè)技術(shù)學(xué)院 電子信息系, 安徽 安慶 246000)

基于ZigBee網(wǎng)絡(luò)的路由算法研究

陳 偉

(安慶職業(yè)技術(shù)學(xué)院 電子信息系, 安徽 安慶 246000)

ZigBee網(wǎng)絡(luò)的傳統(tǒng)算法(簇樹路由算法和AODVjr路由算法)在發(fā)現(xiàn)路由過程中節(jié)點(diǎn)能耗較大。為此，結(jié)合節(jié)點(diǎn)能量、簇樹路由算法和AODVjr路由算法，提出一種改進(jìn)的ZigBee網(wǎng)絡(luò)路由算法。該路由算法選擇路由時(shí)盡量避免能量較低的節(jié)點(diǎn)，選擇最佳路徑,維持網(wǎng)絡(luò)穩(wěn)定性。仿真結(jié)果表明，改進(jìn)后的算法能有效降低整個(gè)網(wǎng)絡(luò)總體能耗，合理分配網(wǎng)絡(luò)負(fù)載，大大降低了死亡節(jié)點(diǎn)數(shù)量，從而延長整個(gè)網(wǎng)絡(luò)的使用壽命。

ZigBee網(wǎng)絡(luò)；簇樹路由算法；AODVjr 路由算法；能量均衡；網(wǎng)絡(luò)拓?fù)?/p>

0 引言

無線通信技術(shù)逐漸成為通信技術(shù)的發(fā)展方向?；赯igBee技術(shù)的無線傳感器網(wǎng)絡(luò)技術(shù)是無線通信中面向短距離、低速率、低功耗和低成本的一項(xiàng)重要技術(shù)。它采用直接序列擴(kuò)頻(DSSS)技術(shù)，工作頻率為868MHz、915MHZ和2.4GHz。ZigBee網(wǎng)絡(luò)以良好的技術(shù)特性廣泛應(yīng)用于無線傳感器網(wǎng)絡(luò)中，ZigBee網(wǎng)絡(luò)的路由算法和機(jī)制也獲得了不斷發(fā)展[1-2]，但在ZigBee網(wǎng)絡(luò)中，能量問題一直是發(fā)展瓶頸。本文對(duì)ZigBee網(wǎng)絡(luò)協(xié)議的路由進(jìn)行了分析，針對(duì)傳統(tǒng)路由協(xié)議存在的問題，對(duì)傳統(tǒng)的ZigBee網(wǎng)絡(luò)路由算法進(jìn)行優(yōu)化，將路徑中能量的消耗與傳統(tǒng)路由算法結(jié)合，提出新的ZigBee路由算法，以提高ZigBee網(wǎng)絡(luò)性能，延長網(wǎng)絡(luò)使用時(shí)間。

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

ZigBee網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)[3]有星形拓?fù)洹湫瓮負(fù)浜途W(wǎng)形拓?fù)洹?/p>

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

節(jié)點(diǎn)通信規(guī)則:

(1)星形拓?fù)渲兄挥袇f(xié)調(diào)節(jié)點(diǎn)和終端節(jié)點(diǎn)，節(jié)點(diǎn)間的數(shù)據(jù)通信只有唯一的一條路徑。

(2)樹形拓?fù)渲泄?jié)點(diǎn)向另外節(jié)點(diǎn)發(fā)送數(shù)據(jù)，必須沿著父節(jié)點(diǎn)上傳，一直傳遞到最近的協(xié)調(diào)節(jié)點(diǎn)后，再傳遞到目標(biāo)節(jié)點(diǎn)。

(3)網(wǎng)形拓?fù)涫且环N特殊的點(diǎn)對(duì)點(diǎn)自組通信網(wǎng)絡(luò)，其網(wǎng)絡(luò)中的路由可以自動(dòng)建立和維護(hù)，而且自愈能力特別強(qiáng)。網(wǎng)絡(luò)通信可以多跳方式來傳輸數(shù)據(jù)到達(dá)目標(biāo)節(jié)點(diǎn)，網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)目多而且網(wǎng)絡(luò)的深度深，是ZigBee網(wǎng)絡(luò)中最復(fù)雜的一種網(wǎng)絡(luò)拓?fù)洹?/p>

2 ZigBee網(wǎng)絡(luò)地址分配及鏈路節(jié)點(diǎn)能量

ZigBee網(wǎng)絡(luò)同其它無線傳感器網(wǎng)絡(luò)不同，主要在于其采用兩種不同分配方式，即分布式地址分配和隨機(jī)地址分配。如果節(jié)點(diǎn)加入網(wǎng)絡(luò)，必須要通過已存在網(wǎng)絡(luò)中的路由器或協(xié)調(diào)器。當(dāng)一個(gè)節(jié)點(diǎn)加入網(wǎng)絡(luò)后，會(huì)自動(dòng)獲得唯一的網(wǎng)絡(luò)地址。網(wǎng)絡(luò)建立開始，規(guī)定3個(gè)基本參數(shù)：網(wǎng)絡(luò)中最大深度Lm；網(wǎng)絡(luò)中父節(jié)點(diǎn)連接子節(jié)點(diǎn)最多數(shù)目Cm；網(wǎng)絡(luò)中節(jié)點(diǎn)連接路由節(jié)點(diǎn)的最多數(shù)目Rm。網(wǎng)絡(luò)深度為d的路由節(jié)點(diǎn)所能分配地址時(shí)的空間為Cskip(d)，則 計(jì)算Cskip(d)為路由節(jié)點(diǎn)分配地址的個(gè)數(shù)。

Cskip(d)

(1)

父節(jié)點(diǎn)Afather分配給第I路由節(jié)點(diǎn)地址Ai滿足：

(2)

分配給第M終端節(jié)點(diǎn)地址Am滿足：

(3)

ZigBee網(wǎng)絡(luò)一般是基于分布式網(wǎng)絡(luò)，支持AODVjr路由算法。它的算法工作原理是通過路由請(qǐng)求包(RREQ)和路由回復(fù)包(RREP)，尋找路由節(jié)點(diǎn)之間傳輸信息最短的路徑，并記錄保存到路由表中。

ZigBee網(wǎng)絡(luò)中，假設(shè)路徑M的長度為T，則路徑中所消耗的能量為路徑每條鏈路上的損耗之和。其中C[Mi,Mi+1]是節(jié)點(diǎn)Di到Di+1鏈路上所損耗的能量。

(4)

3 ZigBee網(wǎng)絡(luò)路由方式

3.1 Cluster-Tree路由算法分析

簇樹路由算法是一種以網(wǎng)絡(luò)協(xié)調(diào)器為中心的樹狀網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),它主要適用于靜態(tài)路由，節(jié)點(diǎn)上不需要存儲(chǔ)路由表。樹形拓?fù)浣Y(jié)構(gòu)中的大部分設(shè)備為FFD(全功能設(shè)備),RFD(半功能設(shè)備)只能作為樹形結(jié)構(gòu)的末端節(jié)點(diǎn)。節(jié)點(diǎn)成功加入網(wǎng)絡(luò)時(shí)，父節(jié)點(diǎn)根據(jù)網(wǎng)絡(luò)地址分配機(jī)制為其動(dòng)態(tài)分配該網(wǎng)絡(luò)中唯一的網(wǎng)絡(luò)地址。若一個(gè)終端節(jié)點(diǎn)(RFD)發(fā)送數(shù)據(jù)包到其它節(jié)點(diǎn)時(shí)，首先直接發(fā)送數(shù)據(jù)給父節(jié)點(diǎn)，然后由父節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包。若一個(gè)父節(jié)點(diǎn)(FFD)接收到數(shù)據(jù)包，則先要判斷目的節(jié)點(diǎn)是否是自己，如果是則向上層回復(fù)；否則，判斷是否為子節(jié)點(diǎn)，如果是則轉(zhuǎn)發(fā)給子節(jié)點(diǎn)，否則，為下一跳的父節(jié)點(diǎn)[4]。

3.2 AODVjr 路由算法分析

AODVjr路由算法是應(yīng)用于網(wǎng)形拓?fù)浣Y(jié)構(gòu)的路由算法，是AODV(多跳網(wǎng)絡(luò)距離矢量路由協(xié)議)算法的精簡版[5]，非常適用于ZigBee網(wǎng)絡(luò)路由算法，并且還保留原始的AODV算法。主要工作原理是：通過傳送路由數(shù)據(jù)包來查找和記錄路由信息，路由數(shù)據(jù)包由兩部分組成：路由請(qǐng)求包和路由回復(fù)包。如果收到數(shù)據(jù)包后立即查找該節(jié)點(diǎn)的路由表，有到目的節(jié)點(diǎn)最小損耗路由路徑，則立即傳送數(shù)據(jù)，否則就需要啟動(dòng)ADOVjr算法尋找新的路由路徑，由節(jié)點(diǎn)發(fā)送請(qǐng)求(RREQ)包查找。若收到目的節(jié)點(diǎn)的回復(fù)(RREP)包，則網(wǎng)絡(luò)中該路由路徑是最優(yōu)路徑，數(shù)據(jù)包立即按此路由路徑發(fā)送。在ZigBee網(wǎng)絡(luò)中對(duì)AODV-jr路由算法進(jìn)行改進(jìn)，取消了HELLO消息的發(fā)送和ADOV中的先驅(qū)節(jié)點(diǎn)列表，這樣可避免出現(xiàn)無效的回復(fù)(RREP)包和數(shù)據(jù)包在路徑中循環(huán)的問題。只有目的節(jié)點(diǎn)才能發(fā)送回復(fù)(RREP)包,而且目的節(jié)點(diǎn)會(huì)定期向發(fā)送節(jié)點(diǎn)發(fā)送生命周期時(shí)間(KEEP-ALIVE)包來維持節(jié)點(diǎn)在路由表存在的時(shí)間[6-7]。圖2是AODVjr算法尋找路由的方式,可看到請(qǐng)求包(RREQ)廣播和(RREP)回復(fù)的過程。其中,A為源節(jié)點(diǎn),H為目的節(jié)點(diǎn)。

4 改進(jìn)路由算法

簇樹路由是一種靜態(tài)路由, 明知兩個(gè)節(jié)點(diǎn)間的路由路徑,簇樹路由沒有路由表,沒有發(fā)現(xiàn)路由過程，也沒有初始延遲過程。但是簇樹尋找路由不一定是最佳路徑而且也不能自適應(yīng)網(wǎng)絡(luò)。AODVjr路由算法具有動(dòng)態(tài)查找功能，能快速適應(yīng)動(dòng)態(tài)路由環(huán)境，具有組播功能，會(huì)引起廣播風(fēng)暴增加功耗。所以在請(qǐng)求包(RREQ)中增加一個(gè)標(biāo)簽flag。flag=0則當(dāng)前為父節(jié)點(diǎn)可以轉(zhuǎn)發(fā)，當(dāng)flag=1則當(dāng)前為子節(jié)點(diǎn)不可轉(zhuǎn)發(fā)，丟棄該分組。

本文通過結(jié)合AODVjr 路由算法和簇樹路由算法以及鏈路消耗能量改進(jìn)路由算法，不會(huì)單純計(jì)算兩個(gè)節(jié)點(diǎn)的最短路徑，而是結(jié)合ZigBee網(wǎng)絡(luò)樹路由算法，根據(jù)路由節(jié)點(diǎn)能量，通過比較周圍節(jié)點(diǎn)能量尋找最合適的下一個(gè)路由節(jié)點(diǎn)。通過能量均衡策略從有剩余能量的節(jié)點(diǎn)中選擇合適的節(jié)點(diǎn)進(jìn)行數(shù)據(jù)發(fā)送[8]，能維持網(wǎng)絡(luò)生命周期，提高網(wǎng)絡(luò)健壯性。具體步驟如下：

(1)節(jié)點(diǎn)接收到RREQ 分組時(shí)，先查看RREQ分組的目的節(jié)點(diǎn)是否為本節(jié)點(diǎn)，如果是則回復(fù)，否則轉(zhuǎn)(2)。

(2)判斷本節(jié)點(diǎn)的剩余能量，如果數(shù)據(jù)轉(zhuǎn)發(fā)所需的能量大于節(jié)點(diǎn)的剩余能量，則丟棄該分組，否則轉(zhuǎn)(3)。

圖3 改進(jìn)算法流程

(3)判斷RREQ分組中的標(biāo)簽flag值。如果flag=0，則此節(jié)點(diǎn)為父節(jié)點(diǎn)，可以轉(zhuǎn)發(fā)數(shù)據(jù)，否則轉(zhuǎn)(4)。

(4)flag=1，則此節(jié)點(diǎn)為子節(jié)點(diǎn)，不能轉(zhuǎn)發(fā)數(shù)據(jù)，丟棄分組。

(5)找到目的節(jié)點(diǎn)后回復(fù)RREQ 分組。

5 仿真實(shí)驗(yàn)結(jié)果

為了測(cè)試改進(jìn)后的路由算法性能，分別在NS2 環(huán)境中對(duì)傳統(tǒng)算法和改進(jìn)后的算法進(jìn)行仿真實(shí)驗(yàn)，對(duì)比前后兩種算法性能。主要對(duì)網(wǎng)絡(luò)總體能耗、網(wǎng)絡(luò)中死亡節(jié)點(diǎn)數(shù)量等進(jìn)行比較。仿真結(jié)果表明，改進(jìn)后的路由算法基本上達(dá)到預(yù)定效果，能增強(qiáng)網(wǎng)絡(luò)的健壯性，提高網(wǎng)絡(luò)和節(jié)點(diǎn)壽命。仿真環(huán)境參數(shù)設(shè)置如下：網(wǎng)絡(luò)范圍為：600×600，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量為100個(gè)，數(shù)據(jù)包大小為512B 。首先初始化每個(gè)節(jié)點(diǎn)的能量為1000 J，Cm=6，Rm=5，Lm=7。其次設(shè)置節(jié)點(diǎn)的工作能量閾值為400J，當(dāng)節(jié)點(diǎn)能量小于400J時(shí)，該節(jié)點(diǎn)就為無效節(jié)點(diǎn)。

圖4 ZigBee網(wǎng)絡(luò)總體能耗對(duì)比

圖5 ZigBee網(wǎng)絡(luò)死亡節(jié)點(diǎn)對(duì)比

由圖4和圖5比較發(fā)現(xiàn)，改進(jìn)后的算法和網(wǎng)絡(luò)總體能耗明顯降低。ZigBee網(wǎng)絡(luò)中無效節(jié)點(diǎn)個(gè)數(shù)隨時(shí)間變化 ，剛開始改進(jìn)的算法由于節(jié)點(diǎn)能量充足，不會(huì)產(chǎn)生無效節(jié)點(diǎn)。隨著時(shí)間的增長，傳統(tǒng)算法中無效節(jié)點(diǎn)大量出現(xiàn)，而且出現(xiàn)比較早，主要是傳統(tǒng)算法沒有考慮到節(jié)點(diǎn)剩余能量的保存。而改進(jìn)后的算法不僅考慮路由路徑選擇，同時(shí)還考慮到節(jié)點(diǎn)的剩余能量，均衡網(wǎng)絡(luò)負(fù)載，提高了網(wǎng)絡(luò)的健壯性。

6 結(jié)語

本文對(duì)ZigBee網(wǎng)絡(luò)的傳統(tǒng)路由算法進(jìn)行了改進(jìn)，提高了網(wǎng)絡(luò)的可靠性，延長了網(wǎng)絡(luò)的使用壽命，節(jié)省了網(wǎng)絡(luò)能量。下一步將在節(jié)能方面對(duì)算法進(jìn)行優(yōu)化和改進(jìn)。

[1] 徐小濤，孫少蘭，熊華，等.ZigBee無線傳感器網(wǎng)絡(luò)的路由機(jī)制[J].數(shù)據(jù)通信,2009(3):19-22.

[2] SINEM COLERI ERGEN. ZigBee/IEEE 802.15.4 summary[EB/OL]. [2004-9].http://www.eecs.berkeley.edu/csinem/academic/publications/Zig Bee.pdf.

[3] ZigBee V1. 0 Architecture overview[EB/OL]. [2005-09-16].http:∥www.ZigBee.org Mar 2006-Open-House-Pres-entations/ZigBee%20 Architecture2.pdf.

[4] 郭瑞星,王慶生.ZigBee路由算法的研究與改進(jìn)[J].電腦開發(fā)與應(yīng)用, 2011,24(5):32-34.

[5] 李巖，袁安娜，柳培新，等.一種改進(jìn)的ZigBee網(wǎng)絡(luò)能量均衡簇樹路由算法[J].哈爾濱理工大學(xué)學(xué)報(bào)，2013，18(5)：56-60.

[6] 杜煥軍, 張維勇, 劉國田. ZigBee 網(wǎng)絡(luò)的路由協(xié)議研究[J]. 合肥工業(yè)大學(xué)學(xué)報(bào), 2008, 31(10): 1617-1621.

[7] 謝川.基于ZigBee的AODVjr算法研究[J].計(jì)算機(jī)工程，2011,37(10)：87-89.

[8] 丁飛,張西良,張世慶.基于ZigBee的無線通信技術(shù)及其應(yīng)用[J]．江蘇通信技術(shù)，2006，22(5):24-27.

(責(zé)任編輯：杜能鋼)

Research of Routing Algorithm Based on ZigBee Network

In view of the traditional algorithm of ZigBee network,the cluster tree routing alg-orithm and AODVjr routing algorithm in the routing discovery process, the node's energycon-sumpti-on is relatively large. To this end, an improved ZigBee network routing algorithm ispr-oposed by combining the node energy and the cluster tree routing algorithm and the AODVjr routing algorithm. The routing algorithm chooses the route to avoid the lower energy of the node. And select the best path, maintain network stability. Simulation results show that the improved algorithm can effectively reduce the overall energy consumption of the entire net-work, capable of rational allocation of network load equilibrium, to a large extent reduce the number of dead nodes, and prolong the service life of the entire network.

ZigBee Network; Cluster Tree Routing Algorithm;AODVjr Routing Algorithm;Energy Balance;Network Topology

安徽省質(zhì)量工程教學(xué)研究項(xiàng)目(2015jyxm540)

陳偉(1983-)，男，安徽桐城人，碩士，安慶職業(yè)技術(shù)學(xué)院電子信息系助教，研究方向?yàn)榫W(wǎng)絡(luò)信息安全、無線傳感器網(wǎng)絡(luò)。

10.11907/rjdk.162446

TP312

A

1672-7800(2017)003-0042-03