一種基于鄰居表的ZigBee樹路由綜合加權(quán)改進算法

常赟杰　張位勇　李桂香

（湖南工學(xué)院計算機與信息科學(xué)學(xué)院　衡陽　421002）

1　引言

近年來，ZigBee技術(shù)以其功耗低、數(shù)據(jù)傳輸可靠、組網(wǎng)靈活、數(shù)據(jù)傳輸安全性好和低成本的優(yōu)勢在低速物聯(lián)網(wǎng)中獲得了越來越多的應(yīng)用。在網(wǎng)絡(luò)層，ZigBee采用樹路由和AODVjr兩種路由協(xié)議。樹路由協(xié)議無需路由表，也沒有路由發(fā)現(xiàn)的過程。數(shù)據(jù)包根據(jù)節(jié)點在ZigBee網(wǎng)絡(luò)中的父子關(guān)系進行傳遞，這避免了路由發(fā)現(xiàn)過程的消息洪泛，降低了路由開銷和整體網(wǎng)絡(luò)能量消耗［1］。因此，樹路由協(xié)議特別適合在存儲和計算能力都有限WPAN中使用。

樹路由協(xié)議存在兩個缺點：一是根據(jù)父子關(guān)系來傳輸數(shù)據(jù)包，數(shù)據(jù)傳遞的線路并不是最優(yōu)路線。二是靠近協(xié)調(diào)器的節(jié)點會花費很多能量來轉(zhuǎn)發(fā)來自子孫節(jié)點的數(shù)據(jù)包，使之過早的耗盡電量，造成網(wǎng)絡(luò)分割，通信中斷。

為了解決樹路由協(xié)議的缺點，研究人員提出使用鄰居表來尋找數(shù)據(jù)包傳遞的最優(yōu)路線。文獻［2～7］提出從鄰居表中選擇下一跳轉(zhuǎn)發(fā)節(jié)點，以減少數(shù)據(jù)包傳遞的跳數(shù)，降低端對端時延。這些算法僅從最少跳數(shù)的角度改進數(shù)路由協(xié)議，忽視了節(jié)點的負(fù)載平衡問題，雖然能減少數(shù)據(jù)包的傳輸時延，但是對整個網(wǎng)絡(luò)的生命周期和負(fù)載平衡方面貢獻不大。文獻［8～9］從剩余能量出發(fā)，在數(shù)據(jù)包轉(zhuǎn)發(fā)過程中避免選擇能量低的節(jié)點，平衡網(wǎng)絡(luò)整體能耗。文獻［10］提出通過尋找路由開銷最小的網(wǎng)絡(luò)路徑來降低網(wǎng)絡(luò)總體能耗。以上的解決方案重點關(guān)注了網(wǎng)絡(luò)中的能耗均衡，提高了網(wǎng)絡(luò)生命周期，但是忽略了數(shù)據(jù)包的轉(zhuǎn)發(fā)跳數(shù)和網(wǎng)絡(luò)時延。

本文在深入分析ZigBee樹路由協(xié)議的基礎(chǔ)上，從數(shù)據(jù)包的發(fā)送時延和能量均衡兩個角度出發(fā)，將跳數(shù)、剩余能量和鏈路質(zhì)量三個因素綜合考慮，以達到均衡網(wǎng)絡(luò)的整體能耗，提高網(wǎng)絡(luò)了網(wǎng)絡(luò)生存周期的目的。

2　ZigBee樹路由算法

2.1　ZigBee樹路由協(xié)議

ZigBee網(wǎng)是一種靜態(tài)路由協(xié)議，數(shù)據(jù)包沿著分層樹結(jié)構(gòu)進行傳遞。其工作原理基于式（1～3）所示的分層地址分配辦法。

式（1）的Cskip(d)為地址偏移量，Cm為最大子節(jié)點數(shù)，Lm為網(wǎng)絡(luò)的最大深度，Rm為子節(jié)點中的最大路由節(jié)點數(shù)，d為網(wǎng)絡(luò)深度。深度為d的路由節(jié)點的它給第k個路由子節(jié)點分配的地址按照式（2）計算，給第n個終端子節(jié)點的地址按照式（3）計算。

當(dāng)節(jié)點成功加入網(wǎng)絡(luò)后，它的父節(jié)點給它分配一個全網(wǎng)唯一的網(wǎng)絡(luò)地址。地址為A深度為d的一個節(jié)點發(fā)送數(shù)據(jù)包，如果目的節(jié)點的地址D滿足式（4），則表明D為自己的后代節(jié)點，下一條地址按照式（5）確定；否則，數(shù)據(jù)包傳給自己的父節(jié)點。

2.2　ZigBee樹路由算的缺陷

ZigBee樹路由發(fā)送數(shù)據(jù)包發(fā)送過程如圖1所示，假設(shè)節(jié)點S發(fā)送數(shù)據(jù)包給節(jié)點D，采用傳統(tǒng)樹路由協(xié)議的路徑為S-A-E-O-F-D，經(jīng)過5跳到達目的節(jié)點。若采用鄰居表的方式，數(shù)據(jù)傳播路徑為S-B—D，或者S-C-D，2跳即可到達目的節(jié)點。單從最短跳數(shù)來考慮，B和C節(jié)點是最佳轉(zhuǎn)發(fā)節(jié)點。但是，網(wǎng)絡(luò)長期運行后，頻繁使用B，C節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)包，則會導(dǎo)致這兩個節(jié)點因能量過早的耗盡而導(dǎo)致通信中斷。所以，從能量均衡的角度考慮，B和C并不一定是最佳節(jié)點。本文提的算法，從S的鄰居節(jié)點A、B、C中，綜合跳數(shù)，剩余能量和鏈路質(zhì)量三個因素選一個最佳節(jié)點進行數(shù)據(jù)轉(zhuǎn)發(fā)。

圖1　ZigBee樹路由

3　樹路由綜合加權(quán)改進算法

式（6）中，Cj代表深度為i的節(jié)點為深度為i-1的父節(jié)點的第 j個子節(jié)點。Ck值為0表示樹路徑的終止，若 Ck=0，則有 Cj=0（j=K+1，…，Lm），則此節(jié)點的深度為k-i。圖1中每個節(jié)點左上方的三位數(shù)即是節(jié)點的TI值。

通過使用TI的值，可以輕易的計算出源節(jié)點和目的節(jié)點之間的跳數(shù)。采用鄰居表算法的樹路由協(xié)議中源節(jié)點和目的節(jié)點之間的跳數(shù)按照式（7）計算。

3.1　鄰居表

ZigBee網(wǎng)絡(luò)中每一個節(jié)點都會維護一個一跳通信范圍內(nèi)的鄰居表。當(dāng)節(jié)點加入網(wǎng)絡(luò)、離開網(wǎng)絡(luò)的時候，鄰居表信息就會被更新。本算法的鄰居表儲存的信息包括：鄰居節(jié)點的網(wǎng)絡(luò)深度（D），鄰居節(jié)點的地址（A），設(shè)備類型（DT），鏈路質(zhì)量（LQI），剩余能量（E），樹地址索引（TI）。

設(shè)備類型DT表示節(jié)點的設(shè)備類型，值為1表明設(shè)備為路由節(jié)點；為0代表終端節(jié)點。

鏈路質(zhì)量LQI表示接收信號的質(zhì)量，可以通過接收機的能量探測和者估算信噪比的方式得到。LQI的數(shù)值為0～255之間的整數(shù)，值越大代表鏈路質(zhì)量越好。LQI的值過低，表明鏈路質(zhì)量差，會導(dǎo)致數(shù)據(jù)包多次重傳，會加劇節(jié)點能量消耗［11］。

樹地址索引（TI）表示ZigBee協(xié)調(diào)器沿著樹路徑到達到節(jié)點的關(guān)系。TI的值根據(jù)文獻［4］給出計算方法，按照式（6）計算

式（7）中，dn為鄰居節(jié)點的深度，dd為目的節(jié)點的深度，dnd為鄰居節(jié)點和目的節(jié)點之間的最大深度公共父節(jié)點的深度。

深度為 dn，地址為 An的節(jié)點，TI的值為…0…0)。深度為dd，地址為 Ad節(jié)點，TI的值為(…0…0)。如果=(j=1，2，…，k)并且滿足1＜k＜Lm-1和這兩個條件，那么An和Ad的最大公共父節(jié)點的深度就是k。如果k不存在，這兩個節(jié)點的公共父節(jié)點為協(xié)調(diào)器。如圖1所示，節(jié)點C和H的最大深度父節(jié)點的深度為1。

剩余能量定義如下：假設(shè)深度為di路由節(jié)點Ri的初始能量為E0，其剩余能量E(Ri)按照式（3）計算：

式（8）中，c為節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)包的次數(shù)，節(jié)點每轉(zhuǎn)發(fā)一次數(shù)據(jù)包，c的值自動加1，節(jié)點修改自身的E(Ri)的值，其他鄰居節(jié)點通過監(jiān)聽的方式獲取這個值，然后更新鄰居表中該字段的值。k為特定系數(shù)，用于調(diào)節(jié)能量衰減速度。由公式可以看出：節(jié)點的剩余能量隨著轉(zhuǎn)發(fā)數(shù)據(jù)包的增加減少，隨著網(wǎng)絡(luò)深度的增加而增加。本文采用局部平均能耗比P(Ri)：

式（9）中，P(Ri)為節(jié)點i的剩余能耗比，E(Ri)為節(jié)點i的剩余能量，為鄰居表中所有鄰居節(jié)點的平均剩余能量，按照下式計算：

綜合以上三個公式，得到節(jié)點i的剩余能量比P(Ri)為

從式（11）中可以看出，節(jié)點i的剩余能量比是節(jié)點i和鄰居表內(nèi)所有鄰居節(jié)點的比值，這個值越大，它的相對能量就越多，就更適合進行數(shù)據(jù)轉(zhuǎn)發(fā)。網(wǎng)絡(luò)經(jīng)過長時間運行后，在所有的節(jié)點剩余能量都不多的情況下，采用此方法可以找出剩余能量相對多的節(jié)點。最后大家的能量全部耗盡以后，網(wǎng)絡(luò)癱瘓，通信中斷。在數(shù)據(jù)轉(zhuǎn)發(fā)過程中，盡量避免轉(zhuǎn)發(fā)數(shù)據(jù)包多、深度低靠近協(xié)調(diào)器的節(jié)點，避免了這些節(jié)點過多地參與數(shù)據(jù)包轉(zhuǎn)發(fā)而導(dǎo)致能量過早的耗盡。既避免了網(wǎng)絡(luò)數(shù)據(jù)擁塞，又均衡了網(wǎng)絡(luò)能耗。

3.2　節(jié)點權(quán)值的定義

在使用鄰居表選擇下一跳路由節(jié)點的時候，從最短跳數(shù)、鏈路質(zhì)量和剩余能量這三個方面來綜合來計算路由代價。公式如下：

3.3　算法描述

本算法在數(shù)據(jù)包轉(zhuǎn)發(fā)過程中，從最短跳數(shù)、剩余能量和鏈路質(zhì)量三個角度綜合考慮，從鄰居表中選取最優(yōu)的節(jié)點進行數(shù)據(jù)包轉(zhuǎn)發(fā)。源節(jié)點S發(fā)送數(shù)據(jù)包給目標(biāo)節(jié)點D，選擇下一跳節(jié)點n的步驟如下：

1）若節(jié)點n為目標(biāo)節(jié)點，數(shù)據(jù)直接發(fā)給n；

2）否則，查找節(jié)點n的鄰居表；

3）如果D在鄰居表中，則下一跳節(jié)點就是目標(biāo)節(jié)點D，直接發(fā)送數(shù)據(jù)包給D；

4）否則，根據(jù)式（12）計算鄰居表中每個節(jié)點到目的節(jié)點的路由代價，選擇具有最小值TC值的節(jié)點作為下一跳節(jié)點。

4　仿真結(jié)果分析

本文提出的算法在NS 2.35環(huán)境下進行仿真。在仿真場景中，節(jié)點首先為已經(jīng)加入網(wǎng)絡(luò)，并且具備分配子節(jié)點能力的父節(jié)點搜索自己的鄰居。當(dāng)子節(jié)點加入網(wǎng)絡(luò)后，子節(jié)點和父節(jié)點進行交換入網(wǎng)請求和應(yīng)答信息來指定樹索引TI。當(dāng)所有的節(jié)點都加入網(wǎng)絡(luò)后，局域網(wǎng)建立完畢。在仿真場景中，網(wǎng)絡(luò)節(jié)點數(shù)分別為50、100、150、200、250、300的情況下，各自運行50次仿真，各項參數(shù)取平均值。仿真參數(shù)設(shè)置為：網(wǎng)絡(luò)規(guī)模100m×100m；網(wǎng)絡(luò)中的節(jié)點隨機分布，位置固定；發(fā)送節(jié)點的最大通信距離25m；接收節(jié)點的最大距離30m；Lm/Cm/Rm=6/4/4；節(jié)點的初始能量9J，仿真時間1200s；數(shù)據(jù)包類型為CBR，數(shù)據(jù)包發(fā)送間隔1個/s。本文設(shè)定式（12）的權(quán)值為α=0.5、β=0.3、γ=0.2。通過對本文提出的路由協(xié)議、文獻［2］提出的鄰居表路由和ZigBee標(biāo)準(zhǔn)的樹路由三種協(xié)議做仿真比較，結(jié)果如圖2～4。

圖2　網(wǎng)絡(luò)能耗對比

圖3　死亡節(jié)點數(shù)對比

圖4　網(wǎng)絡(luò)時延對比

網(wǎng)絡(luò)能耗對比如圖2所示，本文提出的算法基于跳數(shù)、節(jié)點的剩余能量和鏈路質(zhì)量三者均衡考慮，數(shù)據(jù)包在轉(zhuǎn)發(fā)過程中，在鄰居表中選擇轉(zhuǎn)發(fā)數(shù)據(jù)包少，相對剩余能量高的節(jié)點，鏈路質(zhì)量好的節(jié)點，隨著節(jié)點數(shù)的增多，本算法的能量消耗優(yōu)于其他兩種算法，因此網(wǎng)絡(luò)存活的時間更長。

死亡節(jié)點數(shù)對比如圖3所示。其他兩種算法中，隨著節(jié)點數(shù)的增多，死亡的節(jié)點數(shù)量直線上升，而本文提出算法，節(jié)點死亡數(shù)量增加平穩(wěn)，明顯少于其他兩種算法。

網(wǎng)絡(luò)時延對比如圖4所示。由于鄰接表路由協(xié)議在數(shù)據(jù)的轉(zhuǎn)發(fā)過程中，只考慮最少的跳數(shù)，因此在網(wǎng)絡(luò)節(jié)點數(shù)少的情況下具有最小的網(wǎng)絡(luò)時延，但是隨著節(jié)點數(shù)的增加，仿真時間的延長，死亡節(jié)點數(shù)量增多以后，網(wǎng)絡(luò)通信時延開始增大。本文提出的算法在節(jié)點數(shù)增多以后，由于死亡節(jié)點數(shù)量少，因此網(wǎng)絡(luò)時延也小于其他兩種算法。

從仿真實驗結(jié)果可以看出：本算法使用樹索引TI的值來計算源節(jié)點到目的節(jié)點的跳數(shù)，通過選擇最小跳數(shù)降低了數(shù)據(jù)包的網(wǎng)絡(luò)時延；通過選擇轉(zhuǎn)發(fā)數(shù)據(jù)包少，相對剩余能量高的節(jié)點，實現(xiàn)了有效的網(wǎng)絡(luò)能量均衡，降低了整體網(wǎng)絡(luò)能耗；通過選擇具有較高的鏈路質(zhì)量的節(jié)點，減少了死亡節(jié)點數(shù)量，避免了網(wǎng)絡(luò)擁塞，進一步降低了網(wǎng)絡(luò)整體能耗。

5　結(jié)語

本文提出的基于鄰居表的ZigBee樹路由綜合加權(quán)算法，綜合了最短跳數(shù)、剩余能量和鏈路質(zhì)量三個因素，在鄰居表中選取最優(yōu)的節(jié)點進行數(shù)據(jù)包轉(zhuǎn)發(fā)。實驗結(jié)果表明，本算法從網(wǎng)絡(luò)能耗、死亡節(jié)點數(shù)量和網(wǎng)絡(luò)時延等方面都優(yōu)于ZigBee樹路由協(xié)議和鄰居表路由協(xié)議，均衡了網(wǎng)絡(luò)中節(jié)點的能量消耗，提高了網(wǎng)絡(luò)生存周期。此外，算法采用樹索引TI來計算源節(jié)點到目的節(jié)點的跳數(shù)，大大減少了數(shù)據(jù)包轉(zhuǎn)發(fā)過程中的計算開銷。因此，本算法在大規(guī)模、存儲和計算能力有限、低功耗的ZigBee網(wǎng)絡(luò)中具有廣泛的應(yīng)用前景。

［1］Cuomo F，Della Luna S，Monaco U，etal.Routing in Zig-Bee：Benefits from Exploiting the IEEE 802.15.4 Association Tree［C］//IEEE International Conference on Communications，Icc.IEEE，2007：3271-3276.

［2］Kim T，Kim SH，Yang J，et al.Neighbor Table Based Shortcut Tree Routing in ZigBee Wireless Networks［J］.Parallel&Distributed Systems IEEE Transactions on，2014，25（3）：706-716.

［3］Qiu W，Hao E SA P.Enhanced tree routing for wireless sensor networks［J］.Ad Hoc Networks，2009，7（3）：638-650.

［4］Ha JY，Park H S，Choi S，et al.EHRP：Enhanced hierarchical routing protocol for zigbee mesh networks［J］.Communications Letters IEEE，2007，11（12）：1028-1030.

［5］Tsai C，Pan M.Self-Learning Routing for ZigBee WirelessMesh Networks［J］.IEEEAsia，2009.

［6］Ahn S，Ko D，Kim B，etal.Energy-Efficient Tree Routing Algorithm-Based Destination Family Group in ZigBee Networks［C］//InternationalConference on Sensor Technologies&Applications，2010，1（303）：1-6.

［7］Dan L，Zhihong Q，Xu Z，et al.Research on Tree Routing Improvement Algorithm in ZigBee Network［C］//InternationalConference on Multimedia&Information Technology.IEEE，2010：89-92.

［8］Dan L，Zhihong Q，Xu Z，et al.Research on Tree Routing Improvement Algorithm in ZigBee Network［C］//International Conference on Multimedia&Information Technology.IEEE，2010：89-92.

［9］Zhou H，Zhang S.An Improvement of ZigBee Tree Routing in the Application of Intelligent Irrigation［C］//International Conference on Intelligent System Design&Engineering Application.IEEE，2010：255-260.

［10］何學(xué)文，王強，張振利.基于能量感知與能量均衡的ZigBee網(wǎng)絡(luò)樹路由算法研究［J］.工礦自動化，2013，39（10）：44-47.HE Xuewen，WANG Qiang，ZHANG Zhenli.Research of ZigBee network tree routing algorithm based on energy awareness and energy balance［J］.Industry and Mine Automation，2013，39（10）：44-47.

［11］蔣培成，陳鳴，李兵.一種優(yōu)化ZigBee性能的綜合加權(quán)選路算法［J］.小型微型計算機系統(tǒng)，2013，34（9）：2014-2017.JIANG Peicheng，CHEN Ming，LI Bing.Compositive Weighted Routing Algorithm Optimizing ZigBee Performance［J］.Journal of Chinese Computer Systems，2013，34（9）：2014-2017.