常赟杰　張位勇　李桂香

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

1　引言

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

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

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

本文在深入分析ZigBee樹路由協(xié)議的基礎(chǔ)上，從數(shù)據(jù)包的發(fā)送時(shí)延和能量均衡兩個(gè)角度出發(fā)，將跳數(shù)、剩余能量和鏈路質(zhì)量三個(gè)因素綜合考慮，以達(dá)到均衡網(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)進(jìn)行傳遞。其工作原理基于式（1～3）所示的分層地址分配辦法。

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

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

2.2　ZigBee樹路由算的缺陷

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

圖1　ZigBee樹路由

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

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

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

3.1　鄰居表

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3　算法描述

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

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

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

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

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

4　仿真結(jié)果分析

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

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

圖3　死亡節(jié)點(diǎn)數(shù)對(duì)比

圖4　網(wǎng)絡(luò)時(shí)延對(duì)比

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

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

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

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

5　結(jié)語

本文提出的基于鄰居表的ZigBee樹路由綜合加權(quán)算法，綜合了最短跳數(shù)、剩余能量和鏈路質(zhì)量三個(gè)因素，在鄰居表中選取最優(yōu)的節(jié)點(diǎn)進(jìn)行數(shù)據(jù)包轉(zhuǎn)發(fā)。實(shí)驗(yàn)結(jié)果表明，本算法從網(wǎng)絡(luò)能耗、死亡節(jié)點(diǎn)數(shù)量和網(wǎng)絡(luò)時(shí)延等方面都優(yōu)于ZigBee樹路由協(xié)議和鄰居表路由協(xié)議，均衡了網(wǎng)絡(luò)中節(jié)點(diǎn)的能量消耗，提高了網(wǎng)絡(luò)生存周期。此外，算法采用樹索引TI來計(jì)算源節(jié)點(diǎn)到目的節(jié)點(diǎn)的跳數(shù)，大大減少了數(shù)據(jù)包轉(zhuǎn)發(fā)過程中的計(jì)算開銷。因此，本算法在大規(guī)模、存儲(chǔ)和計(jì)算能力有限、低功耗的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é)文，王強(qiáng)，張振利.基于能量感知與能量均衡的ZigBee網(wǎng)絡(luò)樹路由算法研究［J］.工礦自動(dòng)化，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］.小型微型計(jì)算機(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.