趙　博，吳　靜

(1.西南科技大學 信息工程學院，四川 綿陽 621010；2.特殊環(huán)境機器人技術四川省重點實驗室，四川 綿陽 621010)

基于ZigBee無線網(wǎng)絡的Cluster-Tree路由算法研究*

趙博1，2，吳靜1，2

(1.西南科技大學 信息工程學院，四川 綿陽 621010；2.特殊環(huán)境機器人技術四川省重點實驗室，四川 綿陽 621010)

針對ZigBee無線網(wǎng)絡中Cluster-Tree算法只依靠父子關系路由且ZigBee技術傳輸帶寬的限制，致使網(wǎng)絡中負載較重的鏈路不能及時傳遞信息，而造成網(wǎng)絡擁塞、丟包和較低的吞吐量問題，提出了一種改進算法 Z-DMHCTR。該算法針對負載超過一定限度的節(jié)點，除了按照原等級樹算法路由之外，結合引入的鄰居列表信息，尋找節(jié)點不與原路徑相交的路徑同時進行信息傳輸，從而提高網(wǎng)絡帶寬利用率，達到提升網(wǎng)絡的吞吐量的目的。仿真實驗主要從網(wǎng)絡吞吐量、端到端數(shù)據(jù)傳輸延時等方面入手進行對比。結果表明，改進算法能夠有效地提高網(wǎng)絡吞吐量，并降低了傳輸數(shù)據(jù)的延時。

ZigBee網(wǎng)絡；Cluster-Tree算法；Z-DMHCTR算法；鄰居列表

0　引言

無線傳感器網(wǎng)絡技術(Wireless Sensor Network，WSN)是物聯(lián)網(wǎng)的關鍵技術，是全球未來四大技術產(chǎn)業(yè)之一［1］。而 ZigBee技術因其低成本、低功耗、低復雜度、高可靠性等特點，在工業(yè)自動化、農(nóng)業(yè)、交通運輸、智能家居、醫(yī)療等領域都得到廣泛應用［2］。ZigBee網(wǎng)絡拓撲結構主要有星型(Star)、樹形(Tree)和網(wǎng)狀(Mesh)3種網(wǎng)絡結構［3］。其中ZigBee樹型拓撲結構因擴展方便覆蓋范圍廣，且Cluster-Tree算法僅依靠父子關系路由，不需要進行路由發(fā)現(xiàn)和路由列表維護，因而很大程度上降低了網(wǎng)絡泛洪壓力，節(jié)省了網(wǎng)絡帶寬，降低了開銷和能耗，所以被廣泛的應用到低功耗、低成本的無線傳感器網(wǎng)絡中［4］。

然而，當所構建的網(wǎng)絡中要采集大量信息時，承擔較大業(yè)務量的底層節(jié)點往往因依據(jù) Cluster-Tree算法進行路由不能及時傳輸信息，而造成丟包和傳輸延時。同時信息量傳輸大的路徑上，節(jié)點能耗快，因而容易導致網(wǎng)絡分割。比如煤礦開采［5］等環(huán)境復雜多變的情況下，采集節(jié)點平時需要傳輸?shù)臄?shù)據(jù)比較少。但當出現(xiàn)突發(fā)事件時，需要緊急傳輸大量詳細信息。此時網(wǎng)絡中容易出現(xiàn)擁塞、丟包等問題，不利于控制中心的處理。如何降低網(wǎng)絡擁塞，提升網(wǎng)絡吞吐量是目前面臨的重要問題。

目前對ZigBee樹型拓撲結構的改進算法中，如參考文獻［6-9］中提到的HCTR算法、ENTR算法、一種改進的Cluster-Tree算法和SATR算法，往往是通過結合引入的鄰居列表,從距離上優(yōu)化路由的下一跳，而并未考慮其所選下一跳是否發(fā)生擁塞，或是否在發(fā)生擁塞的路徑上，以及當節(jié)點發(fā)生擁塞后如何處理的問題。因此本文提出Z-DMHCTR算法，不僅使一跳范圍內(nèi)的傳輸可以直接通過鄰居列表送達，而且對于緩存區(qū)剩余容量小于一定數(shù)值的節(jié)點，可利用其鄰居列表尋找額外的路徑進行傳輸。在額外路徑的選取中，首先要考慮轉發(fā)節(jié)點的緩沖區(qū)大小；然后通過選中的節(jié)點轉發(fā)數(shù)據(jù)時，要避免選用發(fā)生擁塞的節(jié)點所在的源傳輸路徑上的節(jié)點進行轉發(fā)，以此降低再次發(fā)生擁塞的可能性，提升網(wǎng)絡吞吐量。

1　ZigBee無線網(wǎng)絡Cluster-tree路由機制

ZigBee無線網(wǎng)絡中根據(jù)設備功能不同分為兩類：可用來充當協(xié)調器和路由器的全功能設備FFD和僅用來充當終端葉子節(jié)點的精簡功能設備RFD。在ZigBee網(wǎng)絡中，每個節(jié)點都具有 64位的 IEEE擴展地址作為其唯一的標識。此外，還會獲得由其父節(jié)點動態(tài)分配的16位網(wǎng)絡地址［10］。以下分別介紹ZigBee網(wǎng)絡層地址分配機制和等級樹路由過程。

1.1ZigBee網(wǎng)絡地址分配

ZigBee網(wǎng)絡地址分配涉及到 3個重要參數(shù)：Lm(網(wǎng)絡的最大深度)、Cm(父節(jié)點最多可擁有的子節(jié)點的個數(shù))、Rm(子節(jié)點中最多可為路由節(jié)點的個數(shù))。以上參數(shù)由協(xié)調器設定。網(wǎng)絡中父節(jié)點為子節(jié)點進行地址分配時，地址偏移量 Cskip(d)可由式(1)計算得出，其中 d為父節(jié)點深度［10］。

根據(jù)子節(jié)點類型不同，地址分配分別依據(jù)式(2)和式(3)進行。

其中Ap為深度為d的父節(jié)點地址。

1.2Cluster-tree路由算法實現(xiàn)過程

Cluster-tree路由算法依靠父子關系進行。根據(jù)以上ZigBee網(wǎng)絡地址分配公式，當節(jié)點收到目的地址為D的數(shù)據(jù)包后，可依照式(4)判斷 D是否為自己的后代節(jié)點。若是則按照式(5)進一步計算下一跳地址，否則向上發(fā)給父節(jié)點［10］。

其中A為深度為d的節(jié)點的地址。

2　改進算法設計

通過引入鄰居列表，使空間相近的節(jié)點可以直接送達，從而不僅可以降低傳輸延時，還可以節(jié)省能量。同時在該鄰居列表中添加鄰居節(jié)點的剩余緩沖區(qū)大小和鄰居節(jié)點擁塞示警位，以便在傳輸過程中降低發(fā)生擁塞的可能性。如果當節(jié)點檢測到自身緩沖區(qū)達到某預定值，則發(fā)起尋找到目的節(jié)點的額外的與自身傳輸路徑不相交的路徑進行信息的傳輸，從而避免再次發(fā)生擁塞，提高網(wǎng)絡吞吐量。

2.1擁塞示警機制

首先在鄰居列表中設置了剩余緩沖區(qū)大小(Buffer size)和擁塞警示位(Congestion alarm)。其中，剩余緩沖區(qū)大小由節(jié)點緩存隊列的剩余值表示，并根據(jù)節(jié)點收發(fā)數(shù)據(jù)情況進行動態(tài)更新。當節(jié)點緩沖區(qū)大小高于特定值時，擁塞警示位置0，節(jié)點按照正常方式進行路由；否則，擁塞警示位置1，節(jié)點會尋找額外路徑進行轉發(fā)，同時盡量避開已發(fā)生擁塞的節(jié)點。鄰居列表的更新是通過對收到的數(shù)據(jù)包的包頭進行分析進行的。

2.2Z-DMHCTR算法

改進算法的目的是能夠使 ZigBee等級樹路由算法更好地處理大量或高速率數(shù)據(jù)的傳輸問題。因此當節(jié)點發(fā)生擁塞時，可通過尋找額外的節(jié)點不相交的路徑同時進行信息傳輸，從而提高網(wǎng)絡的帶寬利用率，增加網(wǎng)絡吞的吐量。尋找節(jié)點不相交路徑是為了降低再次發(fā)生擁塞的可能性，因為所選中下一跳節(jié)點可能與發(fā)生擁塞的節(jié)點具有相同的公共傳輸節(jié)點。

2.2.1算法描述

假設網(wǎng)絡中所有信息都傳輸至匯聚節(jié)點 sink(協(xié)調器或簇首節(jié)點)，在ZigBee樹型拓撲結構中，依據(jù)上節(jié)描述，Z-DMHCTR算法中每個路由節(jié)點維護一個鄰居列表。當網(wǎng)絡中傳輸數(shù)據(jù)量較低時，僅結合鄰居列表進行判斷一跳范圍內(nèi)的直接傳輸，否則按照原路由方式進行。若當某一節(jié)點緩沖隊列的剩余大小等于鄰居節(jié)點個數(shù)時擁塞示警位置1，則發(fā)起尋找額外的節(jié)點不相交路徑的過程。發(fā)生擁塞的節(jié)點對鄰居列表中非父節(jié)點進行篩選，將數(shù)據(jù)包轉發(fā)至擁塞警示位為0且剩余緩沖區(qū)大的節(jié)點處。作為轉發(fā)的中間節(jié)點，則需要依靠樹型路徑信息，從鄰居列表中挑選出不與上發(fā)送節(jié)點相交的傳輸路徑進行數(shù)據(jù)傳輸。對于挑選出的節(jié)點，再進一步判斷緩存區(qū)大小，從而挑選出適合的節(jié)點進行轉發(fā)。

2.2.2樹型路徑信息

為了降低發(fā)生擁塞的可能性，通過引入ZigBee樹型拓撲結構中父子關系路徑信息，來挑選節(jié)點不相交的路徑進行信息傳輸。其中父子關系路徑信息指的是依據(jù)ZigBee網(wǎng)絡地址所計算出的當前子節(jié)點為其父節(jié)點的第幾個子節(jié)點。例如給定一個地址為Ai的節(jié)點，其深度為di∈［1，Lm］，則在ZigBee樹型網(wǎng)絡中從節(jié)點Ai到sink節(jié)點的父子關系路徑信息可以定義為一個集合ZTPi= (C1，C2，…，Cdi)，其中 Ck(1≤k≤di)取整，表示位于 k-1層的父節(jié)點的第Ck個子節(jié)點。Ck可通過式(6)計算。

當Ck取0時表明路徑已經(jīng)終止。根據(jù)節(jié)點類型不同，集合 ZTPi分為以下兩種類型：

轉發(fā)節(jié)點通過式(6)計算出父子關系路徑信息的集合，然后同發(fā)送節(jié)點的集合中元素進行對比，從而可以判斷其公共節(jié)點所在的位置和深度。避免在依據(jù)等級樹路由方式路由時，采用相同節(jié)點轉發(fā)數(shù)據(jù)。

2.2.3Z-DMHCTR算法實現(xiàn)

在源節(jié)點s向sink節(jié)點發(fā)送數(shù)據(jù)包的過程中：

(1)發(fā)送節(jié)點（可能為源節(jié)點，也可能為中間節(jié)點）檢測到自身擁塞標志位γ=1后將相關信息封裝至分組頭部后，發(fā)起額外路徑尋找過程。

(2)通過查詢鄰居列表篩選出非父節(jié)點到一個結合中，對集合中節(jié)點的擁塞警示位進行判斷，若集合中節(jié)點均發(fā)生擁塞，則跳轉至步驟(5)執(zhí)行，否則繼續(xù)執(zhí)行；

(3)優(yōu)先挑選鄰居列表中，剩余緩沖區(qū)較大的節(jié)點進行轉發(fā)；

(4)中間節(jié)點收到數(shù)據(jù)包并獲取分組頭信息后，若發(fā)現(xiàn)分組中擁塞標志位置1，則將自身的路徑信息集合與發(fā)送節(jié)點的路徑信息進行對比。設變量l、i。l表示當前節(jié)點的集合中最后一個不為0的元素，i表示兩集合中最先出現(xiàn)不同的元素為第i個元素：

①若i=1，則相同節(jié)點為sink節(jié)點，執(zhí)行步驟(5)；

②若i=l，則兩節(jié)點共父，跳轉至步驟(2)執(zhí)行；

②若1＜i＜l，則該中間節(jié)點同源節(jié)點在深度 i-1處有公共父節(jié)點，執(zhí)行步驟(5)；

(5)仍按等級樹路由方式路由至下一跳節(jié)點；

(6)傳輸過程中節(jié)點按照步驟(1)～(4)執(zhí)行，直至信息傳輸?shù)絪ink節(jié)點。

算法具體傳輸過程舉例如下：因算法所挑選的路徑的數(shù)目會受到協(xié)調器子節(jié)點數(shù)目和發(fā)送節(jié)點鄰居節(jié)點數(shù)目的影響，所以建立如下環(huán)形網(wǎng)絡。其中(Lm，Cm，Rm)= (3，4，4)，協(xié)調器位于圓心，其余不同深度i的子節(jié)點部署在半徑為iR的同心圓上，如圖1所示。

其中 s為源節(jié)點，d為匯聚節(jié)點。根據(jù)式(1)結合所設定的參數(shù)可計算出深度為 0，1，2時地址塊 Cskip分別為21，5，1。然后結合式(2)計算出各節(jié)點地址。TR為所設定的節(jié)點的通信范圍，確保一個節(jié)點在其通信范圍內(nèi)除父節(jié)點外，至少存在兩個鄰居節(jié)點，以增加找到額外路徑的幾率。比如源節(jié)點 s，其鄰居節(jié)點為 i，f，g。正常情況下數(shù)據(jù)包的傳輸路徑為s→f→a→d，結合式(6)計算所得的等級樹路徑信息記為ZTPs=(1，1，1)。即s為其父節(jié)點f的第一個子節(jié)點，f為其父節(jié)點a的第一個子節(jié)點，依次類推。如果當源節(jié)點s擁塞標志位置1后，節(jié)點s依據(jù)其鄰居列表尋找額外的路徑。當選擇節(jié)點g為其下一跳并轉發(fā)數(shù)據(jù)包后，節(jié)點g通過將自身的樹路徑信息集合 ZTPg=(1，1，2)，與源節(jié)點 s的進行對比，可知其第一個不同元素出現(xiàn)的位置為集合中第3個元素，則可判斷兩節(jié)點s和g共父節(jié)點。所以節(jié)點g從其鄰居列表中挑選非父的節(jié)點k為其下一跳。當k收到數(shù)據(jù)包后同樣將 ZTPk=(2，1，1)與 ZTPs進行對比，其第一個不相同的元素位于第一位，由此可知節(jié)點k同節(jié)點s只有在sink節(jié)點處才相交。因此節(jié)點k可按照等級樹路由方式進行路由，由此尋找到的第二條路徑為s→g→k→p→b→d。同樣如果 s選擇的下一跳節(jié)點為 i，由同樣的過程可以得出另一條傳輸路徑為s→i→h→j→c→d。如此可以在避免二次發(fā)生擁塞的情況下，將數(shù)據(jù)傳輸至 sink節(jié)點，從而降低丟包率，提升網(wǎng)絡吞吐量。

圖1　傳輸路徑示意圖

3　Z-DMHCTR路由協(xié)議性能仿真與分析

3.1仿真環(huán)境

仿真基于NS2平臺，重點將傳輸過程中，ZDMHCTR算法在網(wǎng)絡平均吞吐量、分組遞交率和端到端的平均傳輸延時與 Cluster-Tree算法進行比較分析。仿真結果證明了改進算法是有效的。

本實驗利用IEEE802.15.4的PHY層和MAC層來實現(xiàn)網(wǎng)絡層的仿真，網(wǎng)絡覆蓋區(qū)域大小為150 m×150 m，網(wǎng)絡布局依照同心圓建立。協(xié)調器節(jié)點位于網(wǎng)絡中心，同心圓半徑為節(jié)點所在深度倍的R。所有仿真數(shù)據(jù)通過對網(wǎng)絡獨立運行20次取平均值所得。仿真過程中通過 Trace文件對實驗數(shù)據(jù)追蹤記錄，并通過 gawk工具對其進行提取和處理，最后通過 gnuplot工具繪制二維圖形并對結果進行分析。具體仿真環(huán)境的參數(shù)如表1所示。

3.2仿真結果與分析

實驗過程中通過將節(jié)點緩沖隊列設置的較小，并且采用Pareto分布流量產(chǎn)生器，從而使節(jié)點緩沖隊列長時間處于擁塞狀態(tài)。仿真結果如圖2所示。

圖2所示的分組遞交率是通過式(8)計算所得，其中僅包括發(fā)生在路由層的傳輸包。

表1　仿真參數(shù)及取值

圖2　分組投遞率

從圖中可以看出改進后算法的分組遞交率優(yōu)于改進前算法。尤其在網(wǎng)絡運行至80 s時，改進前后算法的分組頭地率有最大差值，此時改進前后算法的分組投遞率分別為9.742%、11.932%,改進后算法提高了2.19%。

圖3中平均吞吐量指的是單位時間內(nèi)成功傳輸?shù)臄?shù)據(jù)量，可由式(9)計算。

其中 N為成功傳送的分組數(shù)，Psize為一個封包的大小，tstart和 tend分別為仿真模擬的開始和結束時間。

圖3　平均吞吐量

雖然隨著網(wǎng)絡的運行，改進前后算法的吞吐量均呈下降趨勢，在50 s～80 s間改進后算法平均吞吐量明顯高于改進前算法，從表2中可以看出在70 s處兩者出現(xiàn)最大差值2 760。說明改進后算法通過多條路徑傳輸確實改善了網(wǎng)絡吞吐量。

表2　改進前后算法在不同時刻網(wǎng)絡平均吞吐量

圖4為發(fā)送節(jié)點數(shù)目增加時，網(wǎng)絡整體的平均吞吐量變化情況。

圖4　全網(wǎng)平均吞吐量

Z-DMHCTR算法所挑選的路徑數(shù)目會受到鄰居節(jié)點等的影響，而且大量傳輸包發(fā)送至匯聚節(jié)點容易發(fā)生碰撞而導致丟包，因此增加發(fā)送節(jié)點個數(shù)進行仿真?？梢钥吹?，改進前后算法網(wǎng)絡整體吞吐量增長情況均變緩，但Z-DMHCTR算法通過尋找額外的傳輸路徑與原算法相比仍提升了網(wǎng)絡的吞吐量。

圖5所示的平均端到端延時是通過式(10)計算所得：

其中 N為成功傳送的分組數(shù)，tr(i)為分組傳輸至目的節(jié)點的時間，ts(i)為分組被發(fā)送的時刻。雖然改進后算法通過非父子關系路徑傳輸數(shù)據(jù)時可能使傳輸條數(shù)增多而增加部分延時，但同時也降低了數(shù)據(jù)包在節(jié)點處緩存而引發(fā)的延時。從實驗結果可以看出，雖然延時相差非常小，但改進算法因為所選路徑不為最短所造成的網(wǎng)絡延時并未影響網(wǎng)絡整體性能。

圖5　平均端到端延時

4　結束語

目前，ZigBee技術依然是最適合傳感器網(wǎng)絡接入端的短距離無線通信技術。而其樹型拓撲結構也因為支持節(jié)能操作和輕量級路由并且已擴展而得到了廣泛應用。但因Cluster-tree路由特點和 ZigBee技術本身傳輸帶寬限制，使其對突發(fā)大量數(shù)據(jù)的傳輸或圖像傳輸?shù)纫恍└邤?shù)據(jù)速率應用的處理存在問題。本文針對上情況提出改進的Z-DMHCTR算法，使網(wǎng)絡中節(jié)點發(fā)生擁塞前能夠尋找額外路徑傳輸數(shù)據(jù)，從而不僅可以提升網(wǎng)絡吞吐量，降低丟包率，還可以均衡網(wǎng)絡負載，避免部分節(jié)點因過度使用而死亡造成網(wǎng)絡分割，從而提升了網(wǎng)絡整體的性能。

［1］唐寅.基于ZigBee的傳統(tǒng)路由協(xié)議研究與優(yōu)化［D］.武漢：湖北大學，2013.

［2］袁安娜.基于ZigBee網(wǎng)絡的能量均衡路由算法研究［D］.哈爾濱：哈爾濱理工大學，2014.

［3］馬海潮.ZigBee網(wǎng)絡可擴展性及分簇路由協(xié)議研究［D］.西安：西安電子科技大學，2014.

［4］赫曉萌.基于ZigBee的無線糧情檢測系統(tǒng)中路由協(xié)議的研究［D］.北京：北京郵電大學，2009.

［5］劉國梅，謝曉廣，白首華.基于煤礦安全監(jiān)測的 ZigBee路由協(xié)議改進［J］.工業(yè)安全與環(huán)保，2015，41(1)：99-102.

［6］吳非.基于 ZigBee技術的無線傳感器網(wǎng)絡路由算法研究［D］.北京：北京郵電大學，2015.

［7］Feng Shuo，Wang Mingan，Yu Qilin，et al.Improved neighbor table-based tree routing strategies in ZigBee［C］.Information Science and Technology(ICIST)5th International Conference，2015：513-518.

［8］班艷麗，柴喬林，王芳.改進的ZigBee網(wǎng)絡路由算法［J］.計算機工程與應用，2009，45(5)：95-97.

［9］Chen Shyr-Kuen，Wang Pi-Chung.Shortcut anycast tree routing in MANETs［C］.Advanced Information Networking and Applications(AINA)26th International Conference，2012：635-640.

［10］錢志鴻，朱爽，王雪.基于分簇機制的 ZigBee混合路由能量優(yōu)化算法［J］.計算機學報，2013，36(3)：485-493.

Research on Cluster-Tree algorithm based on ZigBee wireless network

Zhao Bo1，2，Wu Jing1，2
(1.School of Information Engineering，Southwest University of Science and Technology，Mianyang 621010，China；2.Robot Technology Used for Special Environment Key Laboratory of Sichuan Province，Mianyang 621010，China)

For Cluster-tree algorithm only relays on parent-child relationship to rout in ZigBee wireless network and the limited bandwidth of ZigBee technology will result in that the heavily loaded link can′t timely transmit information and so prone to network congestion,packet loss and lower network throughput problem，this paper proposes an optimization algorithm,the Z-DMHCTR algorithm,which combines with neighbor list among the nodes to find a node disjoint paths with the original path to transmit information，thereby improving network bandwidth utilization and increasing the network throughput.Through the simulation,this paper compares the difference of improved algorithm and the original algorithm in the network throughput,end data transmission delay and other aspects of difference.The result shows that the improved algorithm effectively improves the network throughput,and reduces the time delay of data transmission simultaneously.

ZigBee network；Cluster-Tree algorithm；Z-DMHCTR algorithm；neighbor list

TP393

A

10.16157/j.issn.0258-7998.2016.04.032

四川省 2014年科技計劃項目（2014JY0215）

2015-12-23)

趙博(1989－)，女，碩士研究生，主要研究方向：ZigBee技術、物聯(lián)網(wǎng)。

吳靜(1963－)，女，副教授，碩士研究生導師，主要研究方向：無線傳感器網(wǎng)絡、通信技術、三網(wǎng)融合、物聯(lián)網(wǎng)。

中文引用格式：趙博，吳靜.基于ZigBee無線網(wǎng)絡的Cluster-Tree路由算法研究［J］.電子技術應用，2016，42(4)：116-119，123.

英文引用格式：Zhao Bo，Wu Jing.Research on Cluster-Tree algorithm based on ZigBee wireless network［J］.Application of Electronic Technique，2016，42(4)：116-119，123.