認知視角下能量感知的ZigBee網絡樹型路由優化算法

滕志軍， 張明儒， 張 力， 許建軍

(東北電力大學 信息工程學院， 吉林 吉林 132012)

?

認知視角下能量感知的ZigBee網絡樹型路由優化算法

滕志軍， 張明儒， 張 力， 許建軍

(東北電力大學 信息工程學院， 吉林 吉林 132012)

為解決ZigBee Cluster-Tree路由算法路徑選擇不優的問題，提出了一種能量感知的ZigBee樹型路由EZTR(Energy-Aware ZigBee tree routing)算法. 該算法利用每個節點感知的地址信息，按照ZigBee網絡樹型結構計算下一跳鄰居節點到目的節點之間的跳數可避免網絡的環路效應，通過引入認知概念，在跳數集合中選出最短路徑以降低跳數. 在ZigBee網絡節點能量的感知過程中，當所選路徑存在低能量節點時，及時啟用備用節點，從而避免節點因能量過度消耗成為失效節點. NS2(Network simulator version 2)仿真實驗表明，EZTR算法可提高網絡分組遞交率，有效減少節點轉發跳數和平均網絡延時，減小網絡整體能耗，為提高網絡的實時性和延長網絡生命周期提供理論支持.

無線傳感器網絡；認知；能量感知；ZigBee樹型路由算法

以IEEE 802.15.4標準為底層技術的ZigBee技術具有高可靠性、低功耗以及低成本等優勢[1-3]，廣泛應用于電力系統、火災預警、智能農業、智能交通、現代化軍事以及智能家居等領域[4-6]. ZigBee樹型路由ZTR(ZigBee Cluster-Tree routing)算法由于沒有任何路由發現和低的存儲耗能而被廣泛應用，但選擇路徑不是最優的.

國內外學者對無線傳感器網絡路由算法研究較多，但是針對ZigBee網絡樹型路由算法研究較少. Taehong Kim等[7]提出了采用鄰居表改進的最短ZigBee路由改進算法，利用ZigBee網絡路由分配機制和父子節點之間的關系，選擇出最短路徑，但是選擇的路徑未考慮鄰居節點的剩余能量和網絡的擁塞程度，會造成網絡傳輸的擁堵或者因節點過度消耗能量而成為失效節點. Wanzhi Qiu等[8]提出一種增強型的ZigBee路由算法，除利用父子節點之間的鏈路關系外，還利用一跳范圍內的鄰居表來尋找最短路徑，同樣存在未考慮節點的剩余能量問題. Atefeh Khatiri等[9]提出一種能量高效的路由(Energy shortcut tree routing，ESTR)算法，考慮通信鏈路的品質指示、跳數以及節點的忙碌狀態，通過權重因子來綜合加權選擇最優路徑，但權重因子不容易選擇，很容易陷入局部最優. L.K. Wadhwa等[17]提出一種通過分擔數據量多路徑傳輸的優化ZigBee路由算法，在一定程度上雖然避免了網絡的擁塞，但并未降低平均網絡延時.

隨著認知技術在無線傳感器網絡WSN(Wireless sensor network)中的應用逐漸擴大，MOUGY[10]和SULEIMAN Z等[11]提出的認知路由協議，已被用來提高網絡性能. 傳感器節點性能取決于處理、存儲和能量3個因素，其中能量是最需要著重考慮的. 能量路由試圖使能耗最小化，但一個節點可能同時被多條路徑選擇，可能導致其利用率過高，從而使得其為失效. 因此，本文在選擇出最短路徑的同時，還兼顧了節點的忙碌狀態和節點的剩余能量，通過對ZigBee網絡節點能量的認知過程，及時啟用備用節點.

1 ZigBee路由算法

1.1 ZigBee地址分配機制

(1)

Ak=Ap+Cskip(d)·Rm+k. (1≤k≤Cm-Rm)

式中:Ai為ZigBee網絡中協調器或路由節點分配給第i個路由節點的地址，Ak為ZigBee網絡中協調器或者路由節點分配給第k個終端節點的地址.

1.2 Cluster-Tree路由算法

由ZigBee網絡分配機制可知，ZTR算法數據傳輸方向可分為向上傳輸和向下傳輸，邏輯樹結構如圖1所示. 如果節點地址滿足D

圖1 邏輯樹結構

1.3 鄰居表

在ZigBee無線傳感器網絡中，單跳范圍內可以直接相互通信的節點稱為鄰居節點，每個節點都維護其鄰居表. 鄰居表主要由鄰居節點PAN標識符、鄰居節點IEEE擴展地址、鄰居節點網絡地址、鄰居節點的類型(RFD或FFD)、鄰居節點與當前節點之間的關系以及鄰居節點的剩余能量等組成[17]，其結構如圖2所示. 由ZigBee路由分配機制可知，ZigBee樹型路由算法只能向上或向下傳輸，雖然網絡中存在節點鄰居表，但是數據實際傳輸時并未充分利用其優勢. 因此，本文借助鄰居表進行路徑選擇，以降低平均網絡延時，進一步提高ZigBee網絡的性能.

圖2 鄰居表的結構

2 ZigBee網絡樹型路由優化算法

2.1 EZTR算法描述

由ZigBee路由分配機制可知，節點加入網絡時會自動建立鄰居表. 本文提出的算法在IEEE802.15.4標準框架下，利用節點感知地址信息和鄰居表選擇最佳路由策略，通過對ZigBee網絡節點能量的認知，及時啟用備用節點. EZTR算法的優化，不但降低節點的轉發跳數，而且還保證了IEEE802.15.4標準的體系化. EZTR算法流程如圖3所示.

當節點接收到數據包時，首先判斷自己是否為目的節點，若是則直接接收數據，否則，根據節點維護的鄰居表(含有節點地址信息、單跳范圍內節點的關系、鄰居節點的剩余能量等信息)判斷目的節點是否為當前節點的子節點、父節點或鄰居節點，若目的節點與當前節點是父子關系，直接按照樹型結構向上或向下傳遞數據包，否則向下一跳節點發送帶有目的地址的路由請求，采用輪詢方式計算所有鄰居節點到達目的節點的跳數，利用每個節點感知的地址信息選擇最短路徑. 若網絡中存在多條最短路徑，選取剩余能量最多的節點作為下一跳鄰居節點. 判斷在最少跳數的路徑中節點是否為空閑狀態，若路徑中所有節點均處于空閑狀態，選擇此路徑為最優路徑；若在最優路徑中存在能量過低的節點，使用備用節點代替，通過設置標志位(Flag)實現節點與備用節點間的替換. Flag=0表示能量過低的節點，Flag=1表示忙碌節點，Flag=2表示備用節點. 此后的中繼節點轉發也依據此方式進行，不斷更新節點維護的單跳范圍內的鄰居表，直到數據發送到目的節點.

為了盡可能減小因備用節點影響ZigBee網絡的拓撲結構，備用節點選取與原節點直接相鄰的節點，即選擇單跳范圍內節點作為備用節點，同時為了避免備用節點再次成為失效節點，選取單跳范圍內剩余能量最多的節點作為備用節點，采用輪詢的方式將原節點的信息全部復制給備用節點. 如果在一段時間內沒有收到“低能量節點” 請求消息或“節點忙碌”請求消息，則備用節點進入睡眠狀態，降低因備用節點的存在而使網絡付出更多的能量代價.

圖3 EZTR算法流程圖

圖4以EZTR算法路由選擇為例分析說明ZTR算法和EZTR算法的傳輸機制，其中實線代表ZTR算法的路由實現過程，虛線代表EZTR算法的路由實現過程. 從圖中可以看出，與ZTR算法相比，圖4(a)節省4跳，圖4(b)節省5跳，圖4(c)節省4跳. 由于傳統的ZigBee路由算法完全按照父子之間的關系選擇最短路徑，所以轉發數據需要公共父節點的參與，而EZTR算法利用鄰居表和節點地址進行路徑選擇，不需要公共父節點的參與，因此降低了轉發跳數. 另外，從圖中也可以看出，越靠近最大公共父節點的節點轉發數據越頻繁，能量很快耗盡，從而很快就變為失效節點，可能造成網絡的中斷.

2.2 最佳路徑的判斷

利用每個節點感知的地址信息選擇最短路徑. 為了避免ZigBee網絡的環路響應，該算法通過樹型結構來計算下一跳節點到目的節點之間的路由開銷.

節點跳數的計算方法為：找到最大的公共父節點的地址，然后借助最大公共父節點的深度計算EZTRN節點到目的節點之間的跳數，如圖5所示. 跳數計算公式和最少跳數選取公式分別為

Count=(Nd-Do)+(Dd-D0)=Nd+Dd-2D0,

min_count=min{counti}, i∈{1,2,3,…,n}.

式中：count為跳數，Nd為鄰居節點的深度，Dd為目的節點的深度，D0為最大公共父節點的深度，最少跳數為min_count，counti為第i條鄰居節點到目的節點轉發跳數. 其中尋找最大公共父節點的方法為：根據ZigBee路由分配機制，當節點的深度小于網絡最大深度(Lm)時，依據式(1)采用輪詢的方式來實現.

(a)鄰居節點的父節點

(b)鄰居節點的子節點

(c)在鄰居節點的鄰居表中

2.3 低能量節點判斷

在WSN實際應用中，某些節點(如圖4中最大公共父節點附近的節點)頻繁使用，導致能量過度消耗，而其他節點被閑置，會造成節點能量不均衡，因此部分節點因過早失效而引起在最優路徑下的“能量空洞”現象，可能會導致網絡數據傳輸中斷或出現網絡擁塞現象.

圖5 源節點和目的節點之間的路由消耗

Fig.5 Routing consumption between the source node and the destination node

式中:E0為節點的初始能量，di為網絡中第i個節點的深度.

3 仿真及分析

3.1 搭建ZigBee能量模型

ZigBee網絡數據傳輸的總能耗E包括ET(k，d)為節點A發送k bit數據包到節點B所需能耗和ER(k)為節點B接收k bit數據包所需能耗，d為兩個節點之間的通信距離. ZigBee能量模型如圖6所示.

節點發送k bit 數據包消耗的能量為

式中:Eelec為發射電路發送1 bit數據包的能耗，εamp為發射放大器處理1 bit數據包傳輸單位距離所需要的能耗. 假設接收電路與發射電路有相同的能量消耗，則接收k bit數據包的能量消耗為

采用此模型，則一個路由節點的總能耗為

式中M和dm分別是路由節點的跳數和第m跳的發送距離.

圖6 能量模型

3.2 評價指標定義

式中: Ri表示第i個節點成功接收的數據分組的個數，Sk表示第k個節點發送數據分組的個數.

式中: NMAC為MAC層轉發N個數據包，因為MAC層的作用是確認數據傳送和接收; Msour為源節點發送M個數據包.

式中:Tr(i)為接收第i個數據包的時刻，Ts(i)為發送第i個數據包的時刻，Mdes為目的節點成功接收M個數據包.

式中: Ei為第i個節點剩余能量，E0為ZigBee網絡中M個節點的初始能量.

3.3 NS2.35仿真參數設置

為了驗證EZTR算法的性能，利用IEEE 802.15.4 PHY/MAC協議進行ZTR(經典的ZigBee樹型路由)、EZTR(本文提出的優化樹型路由)以及參考文獻[9]提出的ESTR(能量高效的樹型路由)進行網絡層協議仿真. 將節點隨機分布在100 m×100 m區域中，使用cbrgen產生CBR數據流，實驗發送數據包的大小為70 bytes，CBR數據流的帶寬為1 Mbit/s.

實驗采用表1所列的節點仿真參數，利用awk測試腳本提取Trace文件中的節點數據. 仿真動畫效果如圖7所示. NAM動畫仿真之后，自動生成一個以.tr為格式的trace跟蹤文件，該文件可以記錄ZigBee節點整個通信過程，使用AWK語言獲取需要的數據信息.

表1 節點仿真參數

圖7 仿真動畫

3.4 仿真結果及分析

分組遞交率隨節點數目的變化曲線如圖8所示. EZTR在分組遞交率方面優于ZTR和ESTR，EZTR、ZTR及ESTR的整體分組遞交率分別為85.64%、71.81%及80.30%，相應提高了13.83%和5.34%，主要是由于本文提出的EZTR算法考慮了鏈路的忙碌狀態和節點的剩余能量，如果存在能量過低的節點，有可能造成丟包現象；如果鏈路處于忙碌狀態，EZTR算法引入備用節點，避免因數據堵塞而造成丟包現象. 其次，該算法按照樹型結構計算路由跳數，避免了網絡的環路響應. 最后，EZTR算法選擇的路徑是最短的，減少了隊列的延時，一定程度上也提高了網絡的分組遞交率.

圖8 節點的平均分組遞交率隨節點數目變化

節點的平均跳數隨網絡節點數目的變化曲線如圖9所示. 隨著傳感器節點的不斷加入，網絡拓撲結構越復雜. 3種算法的轉發跳數均增加，但是ZTR算法跳數遠多于ESTR和EZTR算法，EZTR、ZTR及ESTR的整體跳數分別為4.99、6.92及5.39，相應降低了27.78%和7.42%. 由于EZTR算法在確保鏈路為空閑狀態傳輸數據和采用備用節點的前提下，選擇EZTRN節點到目的節點最少跳數，因此采用EZTR算法轉發跳數低于ZTR和ESTR的跳數.

圖9 節點的平均跳數隨節點數目變化

隨著傳感器節點數目的增加，不但節點跳數增加，平均網絡延時也不斷增加. 3種算法的平均網絡延時隨網絡節點數目變化曲線如圖10所示. 從圖10可以看出，由于EZTR算法不但考慮轉發跳數和鏈路忙碌狀態，還較大幅度地減少轉發跳數，雖然在一定程度上因增加算法的復雜度導致程序運行時間增加，但該算法優化節點傳輸的路徑，在實時性方面仍然優于ZTR和EZTR算法，EZTR、ZTR及ESTR的整體時延分別為0.017、0.031及0.022，相應降低了45.01%和22.68%，提高無線傳感網絡在線監測的實時性.

圖10 平均網絡延時隨節點數目變化

節點平均剩余能量百分比隨節點數目變化如圖11所示. EZTR、ZTR及ESTR的整體剩余能量百分比分別為0.79、0.67及0.74，相應提高了19.85%和6.75%，主要是由于EZTR算法大幅度降低了節點的轉發跳數，雖然一定程度上增加了因算法復雜度提高而消耗一部分能量，但是由于該算法優化了節點轉發路徑，總體上仍然節約ZigBee網絡的能耗.

圖11 節點平均剩余能量百分比隨節點數目變化

Fig.11 The average percentage of residual energy with the number of nodes changes

為了客觀公正的評價EZTR算法的性能，對ZTR算法和EZTR算法在路由控制開銷方面進行了仿真實驗，路由控制開銷仿真結果如圖12所示. 從圖中可以看出，ZTR算法沒有任何路由控制開銷，是因為ZTR算法在數據通信時只根據父子節點之間的關系進行數據的傳遞. ESTR算法與EZTR算法相比，在尋找最優路徑時，由于需要額外考慮鏈路品質因數和合理選取綜合加權因子等因素，路由控制開銷多于EZTR算法.

圖12 路由控制開銷隨節點數目的變化

4 結 論

本文利用單跳范圍內的鄰居節點和父子節點之間的關系，在認知視角下提出一種能量感知的ZigBee樹型路由(EZTR)算法. 該算法不但在IEEE802.15.4標準體系化框架下能夠選出最短路徑，還兼顧了節點的忙碌狀態和節點的剩余能量，通過對ZigBee網絡節點能量的認知，當網絡中所選路徑存在低能量節點時，及時啟用備用節點. NS2仿真結果表明，EZTR算法的性能優于ESTR、ZTR算法. 由于經典的樹型路由(ZTR)算法在數據傳輸時只在父子節點之間進行數據傳輸，無任何路由控制開銷，而EZTR算法需感知最短路徑，與ZTR算法相比需要付出增加路由控制開銷和占用傳輸帶寬等代價，同時會增加節點的存儲和計算能力，該算法的性能還有待于進一步優化.

[1] 龐毅,王超,孫青林,等. Zigbee網絡環狀分層方法的仿真與實現[J].哈爾濱工業大學學報,2013,45(3):123-128.

PANG Yi,WANG Chao,SUN Qinglin,et al. Simulation and realization of zigbee network annular stratification[J]. Journal of Harbin Institute of Technology,2013,45(3):123-128.

[2]張云洲,蔣培,高亮,等.基于DSP和雙目視覺的多媒體傳感器網絡節點設計與實現[J].通信學報,2014,35(12):210-216.

ZHANG Yunzhou,JIANG Pei,GAO Liang,et al. Design and implementation of wireless multimedia sensor network node based on DSP and binocular vision[J]. Journal on Communications,2014,35(12):210-216.

[3] SHARIFF F, RAHIMA N A, HEW W P. Zigbee based data acquisition system for online monitoring of grid connected photovoltaic system[J]. Expert Systems with Applications,2015,35(42):1730-1742.

[4] SANG Shengbo,FAN Xiao,TANG Xiaoliang,et al. Portable surface stress biosensor test system based on ZigBee technology for health care[J]. Biotechnology & Biotechnological Equipment,2015,45(29):798-804.

[5] NIU Jianwei,WANG Bowei,SHU Lei,et al. An energy-efficient indoor localization system using ZigBee radio to detect WiFi fingerprints[J]. Selected Areas in Communications,2015,33(7):1431-1442.

[6] ChEN S K,KAO T,CHAN C T,et al. A reliable transmission protocol for ZigBee-based wireless patient monitoring[J].IEEE Trans Information Technology in Biomedicine,2012,16(1):6-16.

[7] KIM T, KIM S H,YANG J,et al. Neighbor table based shortcut tree routing in ZigBee wireless networks[J]. IEEE Transcations on Parallel and Distributed Systems,2014,25(3):706-715.

[8] QIU Wanzhi,PENG Hao.Enhanced tree routing for wireless sensor networks[J]. Ad Hoc Networks,2009,39(7):638-650.

[9] KHATIRI A, MIRJALITY G. Energy Efficient Shortcut Tree Routing in ZigBee Networks[C]//Communication Systems and Networks,2012 Fourth International Conference on Computational Intelligence. Harbin: ACM, 2012:117-122.

[10]MOUGY A E,EI Z H,IBNKAHLA,M. Cognitive approaches to routing in wireless sensor networks[C]//IEEE Global Telecommunications Conference.2010.

[11]SULEIMAN Z,NORSHEILA F. Reliable geographical forwarding in cognitive radio sensor networks using virtual clusters[J]. Sensors,2014,14(5):8996-9026.

[12]錢志鴻,朱爽,王雪.基于分簇機制的ZigBee混合路由能量優化算法研究[J].計算機學報,2013,36(3):485-493.

QIAN Zhihong,ZHU Shuang,WANG Xue. An cluster-based ZigBee routing algorithm for Network energy optimization[J]. Chinese Journal of Computers,2013,36(3):485-493.

[13]HUANG Y K,PANG A C,HSIV PC,et al. Distributed throughput optimization for ZigBee cluster-tree networks[J].IEEE Trans. Parallel and Distributed Systems,2012,23(3):513-520.

[14]KIM T, KIM D,PAK N,et al. Shortcut tree routing in ZigBee networks[C]//2007 2nd International Symposium on Wireless Pervasive Computing. 2007:42-47.

[15]YANG Guisong, WANG Zhongjie, WU Chunxue, et al. One-hop expansion ETR protocol for wireless sensor networks[J].Journal of Convergence Information Technology,2012,7(11):169-178.

[16]KWON K, HA M, KIM T, et al. The stateless point to point routing protocol based on shortcut tree routing algorithm for IP-WSN[C]//Proceedings of 2012 International Conference on the Internet of Things. 2012:167-174.

[17]WADHWA L K,RASHMI R S,PRIYE V.Extended shortcut tree routing for ZigBee based wireless sensor network[J]. Ad Hoc Networks,2016,37(2):295-300.

(編輯 王小唯 苗秀芝)

Energy-aware tree routing optimization algorithm for ZigBee networks: a cognitive perspective

TENG Zhijun，ZHANG Mingru， ZHANG Li，XU Jianjun

(School of Information Engineering, Northeast Dianli University, Jilin 132012, Jilin, China)

To improve the problem of failing to well select optimal path for ZigBee Cluster-Tree routing algorithm, ZigBee routing based on Energy-Aware (EZTR) algorithm was proposed. Firstly, using each node perceiving its own address, this algorithm calculated packet forwarding hop-counts that the next hop of node to destination node according to tree structure for avoiding the loop response, by introducing the concept of cognitive for ZigBee network, and selected the shortest routing in hop-counts set to reduce hop-counts. Besides, in order to avoid excessive energy consumption of nodes, which caused nodes to be ineffective, through energy cognitive processing, when there is a low energy nodes selected path, EZTR algorithm timely adopted alternate node. Through comparative analysis of NS2 simulation experiments, packet delivery ratio is improved, hop-counts and average delay are reduced, and network energy consumption is saved, which can provide theoretical support for improving network real-time and extend network lifetime.

wireless sensor network; cognitive; energy-aware; ZigBee tree routing algorithm

10.11918/j.issn.0367-6234.2016.11.017

2015-12-11

國家自然科學基金(51277023)

滕志軍(1973—)，男，博士，教授

張明儒，894205629@qq.com

TP393.1

A

0367-6234(2016)11-0109-07