ZigBee網(wǎng)絡路由算法研究與優(yōu)化①

黃 靜,陳 蘭

(浙江理工大學 信息學院,杭州 310018)

近些年來,物聯(lián)網(wǎng)行業(yè)發(fā)展越來越迅速,人們越來越離不開物聯(lián)網(wǎng).ZigBee技術是物聯(lián)網(wǎng)的核心技術之一[1],它具有能耗小、成本小、復雜度低等優(yōu)點,對于資源匱乏、注重綠色發(fā)展的當今社會來說,它的研究價值非常高.雖然ZigBee網(wǎng)絡已經(jīng)有低功耗低成本的優(yōu)點了,但是研究發(fā)現(xiàn),ZigBee網(wǎng)絡在能耗方面的減少還具有很大空間,為了減少ZigBee網(wǎng)絡的能耗,大量的專家學者進行了研究.Ha和Pack等人[2]提出網(wǎng)絡路由分層協(xié)議,利用分層策略找到最短路徑,降低能耗.李志明[3]等人則引入了差分算法對最小生命周期求解,使路由節(jié)點選擇生命周期最長的簇進行通信.王飛[4]則通過 GA-PSO 算法通過對簇類節(jié)點優(yōu)化而找到最優(yōu)路徑.Li和Meng[5]等人提出對RREQ分組的泛洪進行控制,從而降低能耗.高霞、徐海峰[6,7]等則提出將沒有工作的節(jié)點進行休眠來減少網(wǎng)絡的能耗.通過以上的這些研究,給本文研究提供了理論基礎.而本文則結(jié)合傳統(tǒng)ZBR路由算法進行改進,并對改進的ZBR算法進行驗證,旨在為當前的無線網(wǎng)路由優(yōu)化提供另外的一種借鑒.

1 ZigBee路由機制

當前ZigBee協(xié)議采用的是按需距離矢量路由(AODVjr)和樹形網(wǎng)絡結(jié)構(gòu)路由(Cluster-tree)混合作為自身的路由算法,其主要作用是發(fā)現(xiàn)和維護路由.ZigBee網(wǎng)絡中的節(jié)點既可以當作中繼節(jié)點,也可以直接通過所連接的傳感器采來監(jiān)控和采集數(shù)據(jù).

1.1 ZigBee地址分配

ZigBee網(wǎng)絡中的節(jié)點都擁有兩個地址,一個是64位的MAC地址,它是節(jié)點唯一的標識,由制造商或者被安裝的時候設置,另一個是16位的,類似于IP地址,是節(jié)點加入網(wǎng)絡的時候,由路由器分配的.僅在網(wǎng)絡內(nèi)部使用,只負責數(shù)據(jù)間的傳輸[8].網(wǎng)絡地址分配時會涉及3個參數(shù),這3個參數(shù)由協(xié)調(diào)器決定.

為了便于理解,圖1為ZigBee網(wǎng)絡樹狀結(jié)構(gòu)圖.

圖1 ZigBee網(wǎng)絡樹狀結(jié)構(gòu)圖

由圖中參數(shù)可知節(jié)點可連接的終端節(jié)點最大數(shù)量為Cm?Rm.其中,網(wǎng)絡深度是指該節(jié)點到協(xié)調(diào)器的最短跳數(shù);終端節(jié)點是指沒有路由功能的節(jié)點.若父節(jié)點網(wǎng)絡深度為d,那么該節(jié)點為子節(jié)點分配地址的偏移量為Cskip(d).

只有當Cskip(d)＞0時才允許子節(jié)點接入網(wǎng)絡[9].首先預設協(xié)調(diào)器的深度為0,假定父節(jié)點地址為Ap,加入此節(jié)點第一個擁有路由能力的子節(jié)點地址為Ap+1,協(xié)調(diào)器為第i個有路由能力子節(jié)點分配的地址如式(2)所示;為第k個終端節(jié)點分配的地址如式(3)所示.

根據(jù)節(jié)點分配的方式,我們可以通過式(4)來判斷目的節(jié)點是否為當前節(jié)點的后代節(jié)點[9].

假定當前節(jié)點的地址是A,深度是d,若地址為D的目的節(jié)點地址滿足式(4),則目的節(jié)點是當前節(jié)點的后代節(jié)點,那么當前節(jié)點的下一跳地址D根據(jù)式(5)確定.

若目的節(jié)點地址D不滿足于式(4),則當前節(jié)點會講數(shù)據(jù)傳給自己的父節(jié)點,即下一跳為當前節(jié)點父節(jié)點.

1.2 ZigBee路由算法

目前ZigBee支持3種算法,分別是cluster-tree、AODVjr和ZBR.在cluster-tree算法中,當?shù)刂窞锳,深度為d的節(jié)點收到數(shù)據(jù)后會根據(jù)式(4)判斷下一跳,若滿足,則下一跳的地址可以經(jīng)過式(5)得到;若不滿足,下一跳為其父節(jié)點.Cluster-tree 算法的優(yōu)點是可以一定程度上減少縮短端到端的延遲,但是由于他的非自適應算法的特點,使得它無法動態(tài)進行路由的選擇,使該算法在網(wǎng)絡時延的最大化方面還有所不足.AODVjr算法的一次路由建立過程分成3步:路由發(fā)現(xiàn)、反向路由建立和正向路由建立.該算法的優(yōu)點是,相對于有線網(wǎng)絡的路由協(xié)議而言,它不需要周期性的路由信息廣播,節(jié)省了一定的網(wǎng)絡資源.缺陷在于它的路由發(fā)現(xiàn)過程只有在有需求的時候才會進行,那樣就會增加數(shù)據(jù)傳輸?shù)侥康牡刂返臅r間,并且在路由發(fā)現(xiàn)的過程中也容易引起RREQ風暴.

目前常用的ZBR算法是由cluster-tree和AODVjr兩種算法結(jié)合產(chǎn)生的,圖2為ZBR算法處理流程圖.

首先利用cluster-tree路由算法將ZigBee網(wǎng)絡構(gòu)建好,有助于分組信息有方向的傳輸,然后通過AODVjr路由算法來尋找最佳路徑,以減少時間延遲和能量消耗,結(jié)合了兩種算法的優(yōu)點,但依舊沒有很好地解決路由發(fā)現(xiàn)時的問題,當AODVjr路由算法在進行路由發(fā)現(xiàn)這個過程時,所有節(jié)點都會參加RREQ分組轉(zhuǎn)發(fā),大量無用的RREQ分組容易造成RREQ泛洪,并且距離協(xié)調(diào)器愈近的點,轉(zhuǎn)發(fā)分組次數(shù)就會愈多,能量的耗費也就愈快,以致節(jié)點失效,造成傳感器網(wǎng)絡癱瘓.

圖2 ZBR算法處理流程圖

2 改進的ZigBee路由算法

2.1 改進路由算法的解決方案

光具有波粒二象性,也就是具有波動性和粒子性,研究通過計算機數(shù)字圖像處理手段,把一些光學現(xiàn)象清晰地展示出來,便于觀察和研究,在實驗結(jié)果中顯示的光流擾動現(xiàn)象恰好像一些顆粒狀的東西在做漂流運動,與光的粒子性和波動性是吻合的.為了改善ZBR算法在路由發(fā)起過程中的缺點,本文提出了一種分層能量的控制方法,從限制RREQ控制分組的范圍著手,并考慮能量的消耗,對混合路由算法進行改進,主要從以下幾個方面來解決問題.

(1)將ZigBee網(wǎng)絡分成若干個簇

通常一個簇擁有多個節(jié)點,依據(jù)功能分為網(wǎng)關節(jié)點、簇頭、簇成員和備用節(jié)點4種類型.由于在ZigBee網(wǎng)絡中節(jié)點地址分配嚴格按照分布式地址分配機制進行,因此我們引入路由深度作為劃分簇和選擇簇頭節(jié)點的標準,當ZigBee網(wǎng)絡由協(xié)調(diào)器建立起來后,其自身首先成為第一個簇的簇頭,第一個簇建立完畢后,然后計算路由器的深度,第一個簇的網(wǎng)關節(jié)點會將深度為偶且連接的子節(jié)點最多的的節(jié)點選為下一個簇的簇頭,最后將深度為奇的節(jié)點和終端節(jié)點均劃分到其父節(jié)點所在的簇中,以此類推,直到所有的節(jié)點都劃分完畢.

(2)定義能量閾值

簇劃分完畢后,將每一個處在該ZigBee網(wǎng)絡中的節(jié)點都添加一個能量閾值,剩余能量低于該值的節(jié)點將會休眠,若該節(jié)點為簇頭節(jié)點,那么網(wǎng)絡則會啟用備用節(jié)點,各邏輯簇僅有一個簇頭,若簇頭未失效,則備用節(jié)點與簇成員相同;若簇首能耗過大而超過預設閾值,則由備用節(jié)點替代簇首[9].在定義節(jié)點閾值的同時,我們距離主協(xié)調(diào)器或者簇頭越近的節(jié)點,轉(zhuǎn)發(fā)分組包數(shù)量越龐大,能量消耗的越快,因此我們需要對協(xié)調(diào)器附近的節(jié)點進行一些保護,即負載均衡策略,距離協(xié)調(diào)器越近深度越小的節(jié)點,閾值越高;距離協(xié)調(diào)器越遠深度越大的的點,閾值越低.從而使ZigBee網(wǎng)絡的使用壽命增長.在實際應用中,隨時間長度的增加,節(jié)點的能耗必然也會增加,考慮到這一特性,那么隨時間長度增加,能量閾值降低.根據(jù)以上參數(shù)的相關性,定義能量閾值的公式如下:

其中,節(jié)點的初始能量設為P;節(jié)點i的深度設為di;節(jié)點的閾值設為Ei;t為運行的時間;α為權(quán)因子,用來調(diào)節(jié)閾值的實際大小;(di+1)是為了避免分母為0的情況的出現(xiàn).由(6)式可知,當t→無窮大時,Ei→0;隨著時間t的增大,一些休眠的節(jié)點會被喚醒;在網(wǎng)絡啟動工作后,網(wǎng)絡中節(jié)點的能量普遍很低.當有路由請求時,若節(jié)點的能量power＜E時,就會產(chǎn)生中斷,并發(fā)送報警信息給源節(jié)點,并將該報警信息擴散至其臨近的節(jié)點,使它們的路由表中這一項失效,然后這些節(jié)點再依次廣播下去[10].

(3)傳播范圍計算

對RREQ傳播的范圍進行限制,使超過范圍的節(jié)點丟棄不必要的RREQ分組,從而節(jié)約在路由發(fā)現(xiàn)過程中節(jié)點的能耗.假設源節(jié)點地址為S,深度為ds[10],目的節(jié)點地址為D,深度為dD,RREQ請求包最大傳輸范圍為Lm,其中dD和Lm未知,其他已知.在路由請求發(fā)送過程中,首先判斷源節(jié)點和目的節(jié)點的關系,若為父子節(jié)點,則請求的最大傳播范圍等于兩節(jié)點深度之差的絕對值,即Lm=|ds?dD|;若不存在父子關系,則分組包的最大傳播范圍等于它們分別與該父節(jié)點進行深度差計算并疊加后的值:

其中,dF共同的父節(jié)點網(wǎng)絡深度,其定義為當源節(jié)點是父輩節(jié)點時,dF=ds,則Lm=dD?ds;當目的點是父輩節(jié)點時,dF=dD,則Lm=ds?dD.dF可通過式(4)、式(5)計算得到:由ZigBee網(wǎng)絡地址分配機制可得上式.式中,A和d分別表示為轉(zhuǎn)發(fā)路由節(jié)點的網(wǎng)絡地址和深度.該路由節(jié)點地址若在式(4)范圍內(nèi),則表示目的節(jié)點為其子節(jié)點,那么下一跳的地址可通過式(5)得到;反之,則目的節(jié)點不為轉(zhuǎn)發(fā)路由節(jié)點的子節(jié)點,那么下一跳的地址為該節(jié)點的父節(jié)點.由于在最中心的協(xié)調(diào)器為所有節(jié)點的父輩節(jié)點,dF為0,我們默認地址A也為0,并假設從協(xié)調(diào)器到目的節(jié)點開始尋址,便可計算出下一跳的地址,并判斷源節(jié)點是否為它的后代節(jié)點,若是dF+1,循環(huán)往復,知道源節(jié)點不是它的后代節(jié)點為止,便可得到dF值,dF計算流程如圖3所示.

圖3 dF 計算流程圖

同理設dD為0,通過式(4)、式(5)計算下一跳地址,每計算一次dD加1,循環(huán)往復,知道其等于目的節(jié)點地址時結(jié)束.并通過求得的dF和dD可以得到RREQ的最大傳輸范圍Lm=ds+dD?2dF,dD計算流程如圖4所示.

(4)路徑規(guī)劃

ZigBee網(wǎng)絡中的節(jié)點收到RREQ分組包后經(jīng)由式(3)來決定其父節(jié)點是否轉(zhuǎn)發(fā)RREQ分組包,為了降低整個網(wǎng)絡的能耗,我們通過式(3)判斷節(jié)點轉(zhuǎn)發(fā)分組的大致參考方向,并通過節(jié)點的能量閾值,深度和能傳播的最大范圍來找出最優(yōu)路徑.在此過程中,為了便于判斷源節(jié)點和目的節(jié)點之間的父子關系,我們在分組包中添加一個標志項r.

圖4 d D 計算流程圖

r=0時,當前節(jié)點的父節(jié)點需丟棄RREQ消息分組包(存在父子關系).

r=1時,當前節(jié)點的子節(jié)點需丟去RREQ消息分組包(不存在父子關系).

2.2 路由發(fā)現(xiàn)過程

第1步:當源節(jié)點S發(fā)起到目的節(jié)點D的路由發(fā)現(xiàn),在此過程中當前節(jié)點P從源節(jié)點接收到RREQ消息分組包,首先判斷該節(jié)點是否為目的節(jié)點D,如果是的話,則不考慮自身剩余能量的情況下回復RREQ消息分組包,若不是則進入下一步.

第2步:判斷當前節(jié)點P自身剩余能量大小和該節(jié)點能量閾值,若小于,則丟棄RREQ分組包;若大于,則進行下一步.

第3步:判斷當前節(jié)點P深度,若為奇數(shù),則丟棄RREQ分組包,使用cluster-tree算法沿樹路由方式發(fā)送數(shù)據(jù)分組;若為偶數(shù),則進行下一步.

第4步:深度為偶數(shù)且通過對比鄰居表中周圍節(jié)點的數(shù)目,不為簇頭的節(jié)點,則丟棄RREQ分組包,沿樹路由方式發(fā)送數(shù)據(jù)分組;若為簇頭,則進行下一步.

第5步:通過查找標志位R來判斷源節(jié)點和目的節(jié)點之間是否存在父子關系,當R=0時存在父子關系,那么若當前節(jié)點為源節(jié)點的父節(jié)點時,則丟棄RREQ分組包;如果不是,再判斷當前節(jié)點是否為目的節(jié)點的父節(jié)點,若是,則進入下一步;如果不是,便令R=1進入循環(huán);當r=1時源節(jié)點目的節(jié)點間不存在父子關系,若當前節(jié)點為源節(jié)點的子節(jié)點,則丟棄RREQ分組;若不是,再判斷當前節(jié)點是否為目的節(jié)點的父節(jié)點,若是,進入下一步;若不是,令R=0進入循環(huán).

第6步:判斷由式(4)、式(5)、式(7)計算出的RREQ分組包最大傳輸范圍Lm,如果當前節(jié)點接收到分組包中目的節(jié)點跳數(shù)hops大于Lm,則丟棄RREQ分組包結(jié)束;若小于,則進入下一步.

第7步:當前節(jié)點轉(zhuǎn)發(fā)RREQ分組包,并更新自身剩余能量.

改進的路由算法工作流程如圖5所示.

圖5 改進的ZBR算法工作流程圖

3 實驗結(jié)果分析

本文的仿真使用的是NS-2仿真平臺,該仿真平臺自帶 IEEE802.15.4 定義的媒體接入層與物理層的協(xié)議模塊,仿真的時候只需編寫網(wǎng)絡層算法的協(xié)議模塊.將仿真出來的結(jié)果使用AWK進行數(shù)據(jù)處理分析后繪圖,然后使用Excel進行圖表繪制.本文將ZBR算法和改進后的ZBR算法分別在節(jié)點數(shù)為10～100個不同的場景下進行仿真比較,數(shù)據(jù)取運行50次的平均值,仿真時隨機分布節(jié)點,隨機并發(fā)8個數(shù)據(jù)流,平均速度為0.5 packets/s,其他的仿真參數(shù)設置如表1所示.

表1 仿真參數(shù)設置

仿真實驗后,我們從平均時間延遲、剩余能量和分組投遞率3個方面進行分析.網(wǎng)絡平均延遲比較如圖6 所示,分簇機制減少了通信量,由簇頭進行數(shù)據(jù)融合,減少了時間延遲.由圖可以看出改進后的算法時間相對于改進前的發(fā)算法延遲減少了12.4%.

圖6 網(wǎng)絡平均延遲對比圖

剩余能量對比圖比較如圖7所示.剩余能量百分比時網(wǎng)絡中剩余能量和網(wǎng)絡中初始能量的比值,它可以有效衡量算法的能量使用情況,剩余能量百分比越高,節(jié)能效果越好[11].

圖7 剩余能量百分比對比圖

由圖7可以看出,改進后的算法剩余能量比高于改進錢的算法,隨著節(jié)點的增加,剩余能量百分比降低,并且隨著時間越久,下降越平緩,這也符合實際情況,由于減少了不必要的RREQ分組的轉(zhuǎn)發(fā),使得網(wǎng)絡整體能量消耗降低.

分組投遞率是檢測網(wǎng)絡傳輸性能的關鍵指標,它能反映出網(wǎng)絡的穩(wěn)定與可靠程度,分組投遞率是接收的數(shù)據(jù)分組和發(fā)送數(shù)據(jù)分組數(shù)量的比值,它和網(wǎng)絡性能成正比,圖8為改進前后算法的分組投遞率比較.

圖8 分組投遞率對比圖

由圖8可知,丟棄了多余的RREQ分組后的算法,分組投遞率變高了.

4 結(jié)束語

本文在分析 ZigBee 路由算法的基礎上,提出了一種改進了的ZBR算法即分層能量控制算法.改進后的算法通過控制節(jié)點能量閾值、限制RREQ分組的傳播范圍、限制網(wǎng)絡深度入手以丟棄不必要的RREQ分組,從而達到減少網(wǎng)絡的能耗.并通過NS2仿真實驗,從端到端的延遲、剩余能量、分組投遞率3方面和未改進的算法進行比較,實驗結(jié)果表明改進后的算法能在保證網(wǎng)絡傳輸穩(wěn)定的同時降低端到端的延遲和能量的消耗,使得網(wǎng)絡負載均衡,網(wǎng)絡生存時間最大化.