一種降低節點能量開銷的ZigBee路由算法優化

焦慧平 孔國利

摘 要： 為解決ZigBee網絡由于不合理的路由策略導致節點能量浪費和網絡陷入局部死亡的問題，提出一種降低節點能量開銷的ZBR路由算法。所提ZBR優化算法在路由發送階段，利用節點自動維護的鄰居表信息，優先實現兩跳路由傳輸；在路由發現過程中，根據最大傳輸跳數和節點間的父子關系，控制ZigBee網絡中RN+節點RREQ分組的洪泛，減少能量浪費；在路由選擇時，設計節點能量標志位和能量感知的路由成本函數，減少能量偏低節點的使用概率，降低網絡開銷和提高節點生存率。通過與原ZBR算法及其他幾種改進ZBR算法進行剩余能量和節點生存率對比仿真實驗，結果表明：改進的ZBR算法的平均剩余能量提高了7.74%，在網絡運行80 s時節點生存率提高了20.29%，也高于其他幾種改進ZBR算法，該算法可有效減少網絡能量消耗，大大提高節點生存率。

關鍵詞： ZigBee網絡； 路由策略； 能量開銷； 能量標志； 節點生存率

中圖分類號： TN926?34； TP393.2 文獻標識碼： A 文章編號： 1004?373X（2016）08?0068?04

Optimization of a ZigBee routing algorithm for reducing node energy consumption

JIAO Huiping， KONG Guoli

（Information Engineering College， Zhongzhou University， Zhengzhou 450044， China）

Abstract： Due to unreasonable routing algorithm， the ZigBee networks encounter node energy over?consumption and partial death. To solve these problems， a ZigBee routing（ZBR） optimization algorithm for reducing node energy consumption is proposed. The proposed ZBR optimization algorithm， in the routing delivery stage， makes use the nodes to maintain neighbor table information automatically， and takes priority for a two?hop routing transmission； in the discovery process of routing， controls the RREQ packet of RN+ node to reduce energy dissipation according to the maximum hop number and the father?son relationship among the nodes； during routing selection， adds energy flags to the RN? node to reduce the transmission probability of low energy nodes and utilizes an energy?aware routing cost function designed to cut down the network energy cost and improve the node's survival rate. Compared with the original ZBR algorithm and several other improved ZBR algorithms of the residual energy and node survival rate in the simulation experiment， the average remaining energy of the improved ZBR algorithm is increased by 7.74% and the node survival rate is increased by 20.29% in 80 s running of the network. The algorithm can effectively reduce the network's energy consumption and improve node's survival rate.

Keywords： ZigBee network； routing strategy； energy expenditure； energy flag； node survival rate

0 引 言

ZigBee是一種短距離、低功耗和低速率的無線通信技術，ZigBee網絡節點主要依靠電池供電，由于節點體積小，節點的能量十分有限[1]，所以降低網絡能耗是解決阻礙ZigBee網絡應用發展的關鍵。ZigBee無線網絡根據拓撲結構的不同主要采用AODVjr路由和Cluster?tree路由兩種算法[2]。Cluster?tree算法是靜態路由算法，由簇樹之間的父子關系進行路由，但路由效率較低，能量開銷和服務時延較大。AODVjr算法則通過大量洪泛來尋找最優路由路徑，其路由開銷較大。ZBR（ZigBee routing）算法結合了兩種算法特性，以求滿足不同的應用需求，是當前最適用于ZigBee無線網絡的算法[3?4]。此外RFD節點因不具有路由功能，由其父節點完成路由，但是由于AODVjr和Cluster?tree兩種算法的固有不足，ZBR算法在能量效率和負載控制方面還有較大改進空間。

為了解決ZBR算法存在網絡能量消耗大和節點死亡率高的問題，班艷麗等將節點臨界能量機制引入到ZigBee路由算法中[5]，且控制RREQ的大致傳輸方向，減少死亡節點數，降低網絡能量消耗，算法完全避免使用低能量節點進行路由轉發，但全由RN+節點組成的傳輸路徑卻不一定是最優路徑。張擎等在對Cluster?tree結構進行改進以節省路由開銷和均衡負載[6]，之后對RREQ和RREP分組處理，以保護能量偏低節點；然而該方案缺乏對RN-節點相應的改進。Taehong K等考慮路由成本提出了利用鄰居表建立短路徑路由協議算法[7]。

本文首先分析了ZBR算法中RN+，RN-節點采用算法存在的缺點，然后提出了一種改進的ZBR路由算法。改進方案通過利用鄰居列表完成兩跳范圍之內的傳輸和對RN+節點RREQ冗余分組的減少和丟棄，減少了網絡能量的浪費。此外，在RN-節點設置能量標志位，以減少RN-節點的使用概率，延長網絡的整體壽命。

1 ZBR算法存在的問題

RREQ分組冗余：AODVjr算法采用廣播通信機制，雖然可以找到最短路徑，但AODVjr算法在路由發現過程中會產生大量的RREQ分組。隨著網絡規模的增加，這些RREQ分組數量顯著增加。大量的RREQ分組為了降低分組傳輸時延，提高分組遞交率，在ZigBee網絡中形成洪泛。部分RREQ分組的尋址范圍超過網絡的最大跳數，當傳輸次數達到時會被節點丟棄，造成網絡能力的浪費。此外，現有RREQ分組的路由方法沒有考慮簇樹的父子關系，形成冗余洪泛。冗余RREQ分組會浪費網絡能量，降低網絡整體能量消耗可通過降低RREQ分組洪泛開銷來實現。

能效不均衡的路由策略：RN-節點雖然采用Cluster?tree算法節約了能量，但能量偏低的RN-節點如果繼續被頻繁用于數據傳輸，當能量耗盡時會成為死亡節點。在網絡運行后期，當節點能量普遍不足時，RN-節點將變為RN+節點參與路由，但死亡節點無法轉變，其他節點傳輸數據時必須繞過死亡節點，造成能量浪費，所以在路由時應盡量降低RN-節點作為傳輸節點的概率。

缺乏高效的鄰居節點路由：RN+，RN-節點為路由節點，都自動存儲維護一張鄰居表，擁有離自己一跳距離的相鄰節點信息，如果目的節點可以通過源節點的鄰居節點傳輸，則可以通過使用鄰居表減少能量消耗[8]。網絡節點分布如圖1所示。從圖1中可看出，若不考慮鄰居節點的使用，節點7到節點10的數據傳輸路徑為7?4?0?3?10，若使用鄰居節點，數據傳輸路徑為7?12?10，縮短了路由路徑，且避免廣播RREQ分組，降低網絡能量消耗，但原ZBR算法卻忽略了鄰居表的使用。

本文針對ZBR算法的三個主要問題，提出各自的解決方案，達到降低網絡功耗、提高節點生存率的目的。

圖1 鄰居節點路由

2 降低節點能量開銷的ZBR路由算法

2.1 基于鄰居表的兩跳傳輸機制

網絡在初始化時每個RN+，RN-節點都更新維護自己的鄰居表信息。鄰居表存儲內容如表1所示。

表1 鄰居表格式

在圖1中，節點4的鄰居表存儲其鄰居節點1，3，7，13的相關信息。在尋找目的節點時，RN+，RN-節點都應首先充分使用鄰居表，避免開啟路由發現時洪泛RREQ尋址消耗能量。具體機制為：如果目的節點在鄰居表內，就直接轉發分組到目的節點，如果將數據從節點4發給目的節點3，只需一跳傳輸即可發送數據。如果與目的節點存在共同節點，則將數據發送給共同節點，然后由共同節點將數據轉發給目的節點，在兩跳范圍內完成數據傳輸，如路徑7?12?10。

2.2 RN+節點中RREQ冗余分組的處理

RN+節點在數據傳輸時存在冗余RREQ分組，其中一種冗余產生的原因是由于RREQ分組的傳輸跳數超過了ZigBee網絡的最大傳輸跳數。最大傳輸跳數定義為源節點到目的節點的深度之和：

[L=d+d0-2dc] （1）

式中：d為源節點深度；d0為目的節點深度；dc為源節點與目的節點的公共父節點的深度。當RREQ分組的尋址范圍大于[L]，該分組會在傳播次數耗盡時丟棄，而對尋找目的節點沒有意義，浪費網絡能量。此類RREQ分組的大量洪泛還會引起網絡擁塞現象，因此，當節點收到此類RREQ分組時應立即丟棄。

另外一種冗余RREQ分組的產生的原因是RN+節點采用廣播通信機制時沒有考慮網絡中存在的父子關系引起的。并不是所有的鄰居節點都能尋找出最優路徑，因此需要對RREQ分組進行定向，去除冗余RREQ分組[9]。

2.3 能量標志位

為防止RN-節點被過度使用而使節點死亡，改進的ZBR算法在RREQ分組中加入能量標志位E?flag。能量標志位表示當前分組的傳輸路徑中存在RN-節點。將E?flag置為1，表明路徑中存在能量偏低節點，路由選擇算法應該避免使用低能量節點。避免使用低能量節點之后，ZBR算法還需要進一步優化，以提高全網能量使用效率。原ZBR算法中，路由成本函數考慮了跳數，剩余能量和鏈路質量，能夠很好表征路徑的能量效率。路由P的成本為：

[C（P）=i=1L-1TC[Di，Di+1]] （2）

式中：TC{[Di，Di+1]}為節點Di到Di+1鏈路成本；L為鏈路最大長度。鏈路成本的函數表達式如下：

[TCl=7min（7，round（1P4l））] （3）

考慮節點剩余能量對路徑選擇的影響，提高網絡整體有效壽命，本文方案設計了能效優化的鏈路成本函數Pl，定義Pl如下：

[Pl=α·LQI+β·REnergy] （4）

式中：α，β（0≤α，β≤1，α+β=1）為固定系數，用來權衡每個影響因素的重要性；[LQI]是MAC層和PHY層所提供的每一幀的LQI的平均值；REnergy則表示節點剩余能量。由于改進的路由成本函數考慮了節點的剩余能量，使得路徑中含有低能量節點的路由成本增加。在路由選取階段，含有低能量節點的路由能夠以較低的概率被使用，避免了低能量節點被過度使用導致網絡死亡。

因此，當目的節點收到RREQ分組后，查看其能量標志位。若能量標志位為1，表明路徑中含有能量偏低的RN-節點。此時，應當優先選擇能量標志位為0的路徑進行傳輸。其次，在能量標志位為1的路徑集合中選擇路由成本最低的路徑進行傳輸。由于路由成本公式考慮了節點剩余能量的影響，含有RN-節點的路徑代價增大，降低其被選中概率。

2.4 改進ZBR算法路由策略

改進算法的路由策略主要分三個階段，分別為查詢鄰居表階段、RREQ尋址階段和目的節點選擇路徑階段。節點處理RREQ分組的過程如下：

Step1：當一個分組到達節點時，該節點查找鄰居表。若存在目的節點，則直接轉發給目的節點；若與目的節點存在共同節點，則定向發送給共同節點。

Step2：通過Step1無法尋址到目的節點時，節點開啟路由發現，轉發RREQ分組前待轉發節點首先判斷與目的節點父子關系，而后RN+和RN-節點根據自己的功能特性轉發RREQ分組。若在轉發節點的后裔簇樹中存在目的節點，則轉發節點將RREQ分組遞交到該后裔簇樹的根節點。否則該分組信息轉發到轉發節點的父節點處理。另外RREQ分組到達一個不具有路由功能的RFD節點時，該分組直接被遞交回該RFD節點的父節點。

Step3：ZigBee網絡中等待路由時間是由中心協調器設置，一般為某個常數，超過設置的時間則停止等待[10]。等待時間結束后，目的節點會收到來自不同路徑的RREQ分組。目的節點首先根據能量標志位E?flag進行路由分類，在E?flag為0的路由中選擇路由成本最小的路徑進行數據傳輸。由于從式（4）中得出，剩余能量越大的路由成本越小。因此該路由選擇算法能夠達到降低能量節點傳輸數據的概率，延長節點壽命的目的。

以上改進算法在路由傳播階段，針對節點的能量狀況，在RREQ分組中添加E?flag標志位，避免能量偏低的過度使用，提高節點生存率，延長網絡壽命。在路由發現階段，對RREQ分組根據最大跳傳輸限制進行丟棄，然后對剩余RREQ分組根據簇樹結構的父子關系進行定向傳播，避免過多RREQ分組洪泛的產生。在路由選擇階段，路由成本由式（4）計算，公式簡單，且可由各節點獨立計算完成。假設鄰居節點個數為n，各節點查找鄰居表時，算法遍歷每個鄰居節點，算法的時間復雜度為O（n），算法可在多項式時間內完成。

3 仿真實驗結果

為驗證改進算法的性能，通過系統仿真對網絡的關鍵性指標進行考察。網絡仿真平臺使用開源的NS2，平臺實現了IEEE 802.15.4協議的PHY層和MAC層。整個網絡范圍設置為100 m×100 m，信息源采用CBR作為數據信息源，網絡節點數為100，節點一跳傳輸距離為15 m，節點初始能量10 J。

仿真主要通過文獻[5]和文獻[6]提出的改進ZBR 路由算法和本文提出的改進ZBR算法、原ZBR算法在網絡能量消耗和節點生存率上進行對比分析。

3.1 剩余能量

仿真實驗中，節點剩余能量與時間的關系如表2所示。從表2可以看出，本文提出的改進ZBR算法利用了節點自身維護的鄰居表尋址目的節點，通過鄰居表能找到目的節點將能大大降低網絡能量消耗，而原ZBR算法和文獻[5]卻忽略了鄰居表的使用，所以能量消耗比ZBR和文獻[6]大。再者，本文的改進ZBR算法降低了RREQ分組引起的能量浪費，雖然文獻[5]和文獻[6]也控制了RREQ分組的冗余，但對于能量偏低的RN-節點卻沒有相應的改進。而改進ZBR算法利用公式（4）降低RN-節點參與路由轉發的概率，減少RN-節點死亡引發的網絡能量浪費現象。由表2數據得出，改進的ZBR算法降低了網絡能量消耗，比原ZBR算法的平均剩余能量提高了7.74%，且始終高于文獻[5]和文獻[6]的兩種改進算法。

3.2 節點生存率

節點生存率為網絡可用節點率。如果一個節點的剩余能量低于初始能量的3%，則被看作是死亡節點。網絡運行結束后，計算生存節點個數。節點生存率公式為：

[λ=NableNtotal×100%] （5）

式中：Nable是網絡運行結束后生存節點個數；Ntotal是網絡總節點個數。四種算法的仿真實驗結果如圖2所示。

在網絡運行初期，節點能量充足，節點生存率降低幅度不大。在網絡運行后期，節點能量普遍不足，節點死亡速度加快，各算法的節點生存率下降幅度都有所增大，原ZBR算法下降幅度最為明顯。本文改進ZBR算法首先通過控制RREQ分組的冗余降低了RN+節點的能量消耗，延長了RN+節點退化為RN-節點的時間；其次，算法降低了RN-節點被使用的概率，減少了RN-節點的死亡幾率。圖2表明改進ZBR算法在網絡運行80 s時節點生存率比原ZBR算法提高了20.29%，且始終高于文獻[5]和文獻[6]的兩種改進算法。

4 結 語

ZigBee是一種易部署和適應性強的短距離無線通信技術，但因其使用電池供電，常常由于不合理的路由算法導致網絡過早死亡。為此，本文從利用鄰居表兩跳傳輸優先、設置能量標志位和能量感知的路由成本函數和根據節點的父子關系減少RREQ分組冗余三個方面著手，提出了能量均衡的改進ZBR路由算法。在開啟路由發現過程前充分使用節點鄰居表，減少網絡發送尋址RREQ的能量消耗，提高網絡能量利用效率。在路由發現階段，利用父子關系控制RREQ分組的轉發取向，減少RREQ分組洪泛帶來的能量損耗。在路由選擇階段，利用能量標志位和能效感知的路由成本函數均衡全局節點剩余能量。通過仿真實驗，改進的ZBR算法比原ZBR算法的平均剩余能量提高了7.74%，在網絡運行80 s時的生存率提高了20.29%，也高于引用文獻中的方法。

參考文獻

[1] 李小龍，彭美平.基于OPNET的改進型Zigbee傳感器網絡仿真系統[J].江蘇大學學報（自然科學版），2012，33（6）：671?677.

[2] 樓亮亮，周苗，何為，等.基于ZigBee協議OTA技術的改進方法研究[J].現代電子技術，2014，37（23）：1?4.

[3] 穆嘉松，劉開華，史偉光.ZigBee網絡中基于節點移動性的路由選擇策略[J].天津大學學報（自然科學與工程技術版），2012，45（4）：301?308.

[4] 吳許俊，王永利.基于兩跳鄰居的ZigBee網絡借地址分配算法[J].科學技術與工程，2013，13（28）：8333?8338.

[5] 班艷麗，柴喬林，王芳.改進的ZigBee網絡路由算法[J].計算機工程與應用，2009，45（5）：95?97.

[6] 張擎，劉淑美，柴喬林.能量高效的zigbee網絡改進路由策略[J].計算機工程，2010，36（7）：108?111.

[7] TAEHONG K， DAEYOUNG K， NOSEONG P， et al. Shortcut tree routing in ZigBee networks [C]// Proceedings of the 2nd International Symposium on Wireless Pervasive Computing. [S.l.]： ISWPC， 2007： 42?47.

[8] 陳建銳，何增穎.基于動態優化因子的Zigbee協議優化仿真算法[J].計算機仿真，2013，30（7）：272?275.

[9] 錢志鴻，朱爽，王雪.基于分簇機制的ZigBee混合路由能量優化算法[J].計算機學報，2012，36（3）：485?493.

[10] 劉麗君，陳志奎.一種適用于密集傳感器網絡中的DV?Hop改進算法[J].微電子學與計算機，2010，27（7）：190?193.