0 引言

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

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

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

1 ZigBee無線網絡Cluster-tree路由機制

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

1.1 ZigBee網絡地址分配

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

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

其中A_p為深度為d的父節點地址。

1.2 Cluster-tree路由算法實現過程

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

其中A為深度為d的節點的地址。

2 改進算法設計

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

2.1 擁塞示警機制

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

2.2 Z-DMHCTR算法

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

2.2.1 算法描述

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

2.2.2 樹型路徑信息

    當C_k取0時表明路徑已經終止。根據節點類型不同，集合ZTP_i分為以下兩種類型：

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

2.2.3 Z-DMHCTR算法實現

    在源節點s向sink節點發送數據包的過程中：

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

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

    (3)優先挑選鄰居列表中，剩余緩沖區較大的節點進行轉發；

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

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

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

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

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

    (6)傳輸過程中節點按照步驟(1)～(4)執行，直至信息傳輸到sink節點。

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

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

3 Z-DMHCTR路由協議性能仿真與分析    

3.1 仿真環境

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

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

3.2 仿真結果與分析

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

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

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

    圖3中平均吞吐量指的是單位時間內成功傳輸的數據量，可由式(9)計算。

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

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

    圖4為發送節點數目增加時，網絡整體的平均吞吐量變化情況。

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

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

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

4 結束語

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

參考文獻

[1] 唐寅.基于ZigBee的傳統路由協議研究與優化[D].武漢：湖北大學，2013.

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

[3] 馬海潮.ZigBee網絡可擴展性及分簇路由協議研究[D].西安：西安電子科技大學，2014.

[4] 赫曉萌.基于ZigBee的無線糧情檢測系統中路由協議的研究[D].北京：北京郵電大學，2009.

[5] 劉國梅，謝曉廣，白首華.基于煤礦安全監測的ZigBee路由協議改進[J].工業安全與環保，2015，41(1)：99-102.

[6] 吳非.基于ZigBee技術的無線傳感器網絡路由算法研究[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網絡路由算法[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混合路由能量優化算法[J].計算機學報，2013，36(3)：485-493.