0 引言

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

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

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

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

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

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

    ZigBee網(wǎng)絡(luò)地址分配涉及到3個重要參數(shù)：L_m(網(wǎng)絡(luò)的最大深度),、C_m(父節(jié)點最多可擁有的子節(jié)點的個數(shù))、R_m(子節(jié)點中最多可為路由節(jié)點的個數(shù)),。以上參數(shù)由協(xié)調(diào)器設(shè)定,。網(wǎng)絡(luò)中父節(jié)點為子節(jié)點進行地址分配時，地址偏移量C_skip(d)可由式(1)計算得出,，其中d為父節(jié)點深度^[10],。

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

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

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

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

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

2 改進算法設(shè)計

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

2.1 擁塞示警機制

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

2.2 Z-DMHCTR算法

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

2.2.1 算法描述

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

2.2.2 樹型路徑信息

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    其中s為源節(jié)點,，d為匯聚節(jié)點,。根據(jù)式(1)結(jié)合所設(shè)定的參數(shù)可計算出深度為0，1,，2時地址塊C_skip分別為21,，5，1,。然后結(jié)合式(2)計算出各節(jié)點地址,。TR為所設(shè)定的節(jié)點的通信范圍，確保一個節(jié)點在其通信范圍內(nèi)除父節(jié)點外，至少存在兩個鄰居節(jié)點,，以增加找到額外路徑的幾率,。比如源節(jié)點s，其鄰居節(jié)點為i,，f,，g。正常情況下數(shù)據(jù)包的傳輸路徑為s→f→a→d,，結(jié)合式(6)計算所得的等級樹路徑信息記為ZTP_s=(1，1,，1),。即s為其父節(jié)點f的第一個子節(jié)點，f為其父節(jié)點a的第一個子節(jié)點,，依次類推,。如果當源節(jié)點s擁塞標志位置1后，節(jié)點s依據(jù)其鄰居列表尋找額外的路徑,。當選擇節(jié)點g為其下一跳并轉(zhuǎn)發(fā)數(shù)據(jù)包后,，節(jié)點g通過將自身的樹路徑信息集合ZTP_g=(1，1,，2),，與源節(jié)點s的進行對比，可知其第一個不同元素出現(xiàn)的位置為集合中第3個元素,，則可判斷兩節(jié)點s和g共父節(jié)點,。所以節(jié)點g從其鄰居列表中挑選非父的節(jié)點k為其下一跳。當k收到數(shù)據(jù)包后同樣將ZTP_k=(2,，1,，1)與ZTP_s進行對比，其第一個不相同的元素位于第一位,，由此可知節(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)絡(luò)吞吐量,。

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

3.1 仿真環(huán)境

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

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

3.2 仿真結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

參考文獻

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

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

[3] 馬海潮.ZigBee網(wǎng)絡(luò)可擴展性及分簇路由協(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技術(shù)的無線傳感器網(wǎng)絡(luò)路由算法研究[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)絡(luò)路由算法[J].計算機工程與應(yīng)用，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.