ZigBee網絡路由算法研究與優化①

黃 靜,陳 蘭

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

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

1 ZigBee路由機制

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

1.1 ZigBee地址分配

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

為了便于理解,圖1為ZigBee網絡樹狀結構圖.

圖1 ZigBee網絡樹狀結構圖

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

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

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

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

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

1.2 ZigBee路由算法

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

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

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

圖2 ZBR算法處理流程圖

2 改進的ZigBee路由算法

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

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

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

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

(2)定義能量閾值

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

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

(3)傳播范圍計算

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

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

圖3 dF 計算流程圖

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

(4)路徑規劃

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

圖4 d D 計算流程圖

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

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

2.2 路由發現過程

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

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

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

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

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

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

第7步:當前節點轉發RREQ分組包,并更新自身剩余能量.

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

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

3 實驗結果分析

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

表1 仿真參數設置

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

圖6 網絡平均延遲對比圖

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

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

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

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

圖8 分組投遞率對比圖

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

4 結束語

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