文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.2016.04.032
中文引用格式： 趙博，吳靜. 基于ZigBee無線網絡的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.
0 引言
無線傳感器網絡技術(Wireless Sensor Network，WSN)是物聯(lián)網的關鍵技術，是全球未來四大技術產業(yè)之一[1]。而ZigBee技術因其低成本、低功耗、低復雜度、高可靠性等特點，在工業(yè)自動化、農業(yè)、交通運輸、智能家居、醫(yī)療等領域都得到廣泛應用[2]。ZigBee網絡拓撲結構主要有星型(Star)、樹形(Tree)和網狀(Mesh)3種網絡結構[3]。其中ZigBee樹型拓撲結構因擴展方便覆蓋范圍廣，且Cluster-Tree算法僅依靠父子關系路由，不需要進行路由發(fā)現和路由列表維護，因而很大程度上降低了網絡泛洪壓力，節(jié)省了網絡帶寬，降低了開銷和能耗，所以被廣泛的應用到低功耗、低成本的無線傳感器網絡中[4]。
然而，當所構建的網絡中要采集大量信息時，承擔較大業(yè)務量的底層節(jié)點往往因依據Cluster-Tree算法進行路由不能及時傳輸信息，而造成丟包和傳輸延時。同時信息量傳輸大的路徑上，節(jié)點能耗快，因而容易導致網絡分割。比如煤礦開采[5]等環(huán)境復雜多變的情況下，采集節(jié)點平時需要傳輸的數據比較少。但當出現突發(fā)事件時，需要緊急傳輸大量詳細信息。此時網絡中容易出現擁塞、丟包等問題，不利于控制中心的處理。如何降低網絡擁塞，提升網絡吞吐量是目前面臨的重要問題。
目前對ZigBee 樹型拓撲結構的改進算法中，如參考文獻[6-9]中提到的HCTR算法、ENTR算法、一種改進的Cluster-Tree算法和SATR算法，往往是通過結合引入的鄰居列表,從距離上優(yōu)化路由的下一跳，而并未考慮其所選下一跳是否發(fā)生擁塞，或是否在發(fā)生擁塞的路徑上，以及當節(jié)點發(fā)生擁塞后如何處理的問題。因此本文提出Z-DMHCTR算法，不僅使一跳范圍內的傳輸可以直接通過鄰居列表送達，而且對于緩存區(qū)剩余容量小于一定數值的節(jié)點，可利用其鄰居列表尋找額外的路徑進行傳輸。在額外路徑的選取中，首先要考慮轉發(fā)節(jié)點的緩沖區(qū)大小；然后通過選中的節(jié)點轉發(fā)數據時，要避免選用發(fā)生擁塞的節(jié)點所在的源傳輸路徑上的節(jié)點進行轉發(fā)，以此降低再次發(fā)生擁塞的可能性，提升網絡吞吐量。
1 ZigBee無線網絡Cluster-tree路由機制
ZigBee無線網絡中根據設備功能不同分為兩類：可用來充當協(xié)調器和路由器的全功能設備FFD和僅用來充當終端葉子節(jié)點的精簡功能設備RFD。在ZigBee網絡中，每個節(jié)點都具有64位的IEEE擴展地址作為其唯一的標識。此外，還會獲得由其父節(jié)點動態(tài)分配的16位網絡地址[10]。以下分別介紹ZigBee網絡層地址分配機制和等級樹路由過程。
1.1 ZigBee網絡地址分配
ZigBee網絡地址分配涉及到3個重要參數：Lm(網絡的最大深度)、Cm(父節(jié)點最多可擁有的子節(jié)點的個數)、Rm(子節(jié)點中最多可為路由節(jié)點的個數)。以上參數由協(xié)調器設定。網絡中父節(jié)點為子節(jié)點進行地址分配時，地址偏移量Cskip(d)可由式(1)計算得出，其中d為父節(jié)點深度[10]。
根據子節(jié)點類型不同，地址分配分別依據式(2)和式(3)進行。
其中Ap為深度為d的父節(jié)點地址。
1.2 Cluster-tree路由算法實現過程
Cluster-tree路由算法依靠父子關系進行。根據以上ZigBee網絡地址分配公式，當節(jié)點收到目的地址為D的數據包后，可依照式(4)判斷D是否為自己的后代節(jié)點。若是則按照式(5)進一步計算下一跳地址，否則向上發(fā)給父節(jié)點[10]。
其中A為深度為d的節(jié)點的地址。
2 改進算法設計
通過引入鄰居列表，使空間相近的節(jié)點可以直接送達，從而不僅可以降低傳輸延時，還可以節(jié)省能量。同時在該鄰居列表中添加鄰居節(jié)點的剩余緩沖區(qū)大小和鄰居節(jié)點擁塞示警位，以便在傳輸過程中降低發(fā)生擁塞的可能性。如果當節(jié)點檢測到自身緩沖區(qū)達到某預定值，則發(fā)起尋找到目的節(jié)點的額外的與自身傳輸路徑不相交的路徑進行信息的傳輸，從而避免再次發(fā)生擁塞，提高網絡吞吐量。
2.1 擁塞示警機制
首先在鄰居列表中設置了剩余緩沖區(qū)大小(Buffer size)和擁塞警示位(Congestion alarm)。其中，剩余緩沖區(qū)大小由節(jié)點緩存隊列的剩余值表示，并根據節(jié)點收發(fā)數據情況進行動態(tài)更新。當節(jié)點緩沖區(qū)大小高于特定值時，擁塞警示位置0，節(jié)點按照正常方式進行路由；否則，擁塞警示位置1，節(jié)點會尋找額外路徑進行轉發(fā)，同時盡量避開已發(fā)生擁塞的節(jié)點。鄰居列表的更新是通過對收到的數據包的包頭進行分析進行的。
2.2 Z-DMHCTR算法
改進算法的目的是能夠使ZigBee等級樹路由算法更好地處理大量或高速率數據的傳輸問題。因此當節(jié)點發(fā)生擁塞時，可通過尋找額外的節(jié)點不相交的路徑同時進行信息傳輸，從而提高網絡的帶寬利用率，增加網絡吞的吐量。尋找節(jié)點不相交路徑是為了降低再次發(fā)生擁塞的可能性，因為所選中下一跳節(jié)點可能與發(fā)生擁塞的節(jié)點具有相同的公共傳輸節(jié)點。
2.2.1 算法描述
假設網絡中所有信息都傳輸至匯聚節(jié)點sink(協(xié)調器或簇首節(jié)點)，在ZigBee樹型拓撲結構中，依據上節(jié)描述，Z-DMHCTR算法中每個路由節(jié)點維護一個鄰居列表。當網絡中傳輸數據量較低時，僅結合鄰居列表進行判斷一跳范圍內的直接傳輸，否則按照原路由方式進行。若當某一節(jié)點緩沖隊列的剩余大小等于鄰居節(jié)點個數時擁塞示警位置1，則發(fā)起尋找額外的節(jié)點不相交路徑的過程。發(fā)生擁塞的節(jié)點對鄰居列表中非父節(jié)點進行篩選，將數據包轉發(fā)至擁塞警示位為0且剩余緩沖區(qū)大的節(jié)點處。作為轉發(fā)的中間節(jié)點，則需要依靠樹型路徑信息，從鄰居列表中挑選出不與上發(fā)送節(jié)點相交的傳輸路徑進行數據傳輸。對于挑選出的節(jié)點，再進一步判斷緩存區(qū)大小，從而挑選出適合的節(jié)點進行轉發(fā)。
2.2.2 樹型路徑信息
當Ck取0時表明路徑已經終止。根據節(jié)點類型不同，集合ZTPi分為以下兩種類型：
轉發(fā)節(jié)點通過式(6)計算出父子關系路徑信息的集合，然后同發(fā)送節(jié)點的集合中元素進行對比，從而可以判斷其公共節(jié)點所在的位置和深度。避免在依據等級樹路由方式路由時，采用相同節(jié)點轉發(fā)數據。
2.2.3 Z-DMHCTR算法實現
在源節(jié)點s向sink節(jié)點發(fā)送數據包的過程中：
(1)發(fā)送節(jié)點（可能為源節(jié)點，也可能為中間節(jié)點）檢測到自身擁塞標志位γ=1后將相關信息封裝至分組頭部后，發(fā)起額外路徑尋找過程。
(2)通過查詢鄰居列表篩選出非父節(jié)點到一個結合中，對集合中節(jié)點的擁塞警示位進行判斷，若集合中節(jié)點均發(fā)生擁塞，則跳轉至步驟(5)執(zhí)行，否則繼續(xù)執(zhí)行；
(3)優(yōu)先挑選鄰居列表中，剩余緩沖區(qū)較大的節(jié)點進行轉發(fā)；
(4)中間節(jié)點收到數據包并獲取分組頭信息后，若發(fā)現分組中擁塞標志位置1，則將自身的路徑信息集合與發(fā)送節(jié)點的路徑信息進行對比。設變量l、i。l表示當前節(jié)點的集合中最后一個不為0的元素，i表示兩集合中最先出現不同的元素為第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í)行，直至信息傳輸到sink節(jié)點。
算法具體傳輸過程舉例如下：因算法所挑選的路徑的數目會受到協(xié)調器子節(jié)點數目和發(fā)送節(jié)點鄰居節(jié)點數目的影響，所以建立如下環(huán)形網絡。其中(Lm，Cm，Rm)=(3，4，4)，協(xié)調器位于圓心，其余不同深度i的子節(jié)點部署在半徑為iR的同心圓上，如圖1所示。
其中s為源節(jié)點，d為匯聚節(jié)點。根據式(1)結合所設定的參數可計算出深度為0，1，2時地址塊Cskip分別為21，5，1。然后結合式(2)計算出各節(jié)點地址。TR為所設定的節(jié)點的通信范圍，確保一個節(jié)點在其通信范圍內除父節(jié)點外，至少存在兩個鄰居節(jié)點，以增加找到額外路徑的幾率。比如源節(jié)點s，其鄰居節(jié)點為i，f，g。正常情況下數據包的傳輸路徑為s→f→a→d，結合式(6)計算所得的等級樹路徑信息記為ZTPs=(1，1，1)。即s為其父節(jié)點f的第一個子節(jié)點，f為其父節(jié)點a的第一個子節(jié)點，依次類推。如果當源節(jié)點s擁塞標志位置1后，節(jié)點s依據其鄰居列表尋找額外的路徑。當選擇節(jié)點g為其下一跳并轉發(fā)數據包后，節(jié)點g通過將自身的樹路徑信息集合ZTPg=(1，1，2)，與源節(jié)點s的進行對比，可知其第一個不同元素出現的位置為集合中第3個元素，則可判斷兩節(jié)點s和g共父節(jié)點。所以節(jié)點g從其鄰居列表中挑選非父的節(jié)點k為其下一跳。當k收到數據包后同樣將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ā)生擁塞的情況下，將數據傳輸至sink節(jié)點，從而降低丟包率，提升網絡吞吐量。
3 Z-DMHCTR路由協(xié)議性能仿真與分析
3.1 仿真環(huán)境
仿真基于NS2平臺，重點將傳輸過程中，Z-DMHCTR算法在網絡平均吞吐量、分組遞交率和端到端的平均傳輸延時與Cluster-Tree算法進行比較分析。仿真結果證明了改進算法是有效的。
本實驗利用IEEE802.15.4的PHY層和MAC層來實現網絡層的仿真，網絡覆蓋區(qū)域大小為150 m×150 m，網絡布局依照同心圓建立。協(xié)調器節(jié)點位于網絡中心，同心圓半徑為節(jié)點所在深度倍的R。所有仿真數據通過對網絡獨立運行20次取平均值所得。仿真過程中通過Trace文件對實驗數據追蹤記錄，并通過gawk工具對其進行提取和處理，最后通過gnuplot工具繪制二維圖形并對結果進行分析。具體仿真環(huán)境的參數如表1所示。
3.2 仿真結果與分析
實驗過程中通過將節(jié)點緩沖隊列設置的較小，并且采用Pareto分布流量產生器，從而使節(jié)點緩沖隊列長時間處于擁塞狀態(tài)。仿真結果如圖2所示。
圖2所示的分組遞交率是通過式(8)計算所得，其中僅包括發(fā)生在路由層的傳輸包。
從圖中可以看出改進后算法的分組遞交率優(yōu)于改進前算法。尤其在網絡運行至80 s時，改進前后算法的分組頭地率有最大差值，此時改進前后算法的分組投遞率分別為9.742%、11.932%,改進后算法提高了2.19%。
圖3中平均吞吐量指的是單位時間內成功傳輸的數據量，可由式(9)計算。
其中N為成功傳送的分組數，Psize為一個封包的大小，tstart和tend分別為仿真模擬的開始和結束時間。
雖然隨著網絡的運行，改進前后算法的吞吐量均呈下降趨勢，在50 s～80 s間改進后算法平均吞吐量明顯高于改進前算法，從表2中可以看出在70 s處兩者出現最大差值2 760。說明改進后算法通過多條路徑傳輸確實改善了網絡吞吐量。
圖4為發(fā)送節(jié)點數目增加時，網絡整體的平均吞吐量變化情況。
Z-DMHCTR算法所挑選的路徑數目會受到鄰居節(jié)點等的影響，而且大量傳輸包發(fā)送至匯聚節(jié)點容易發(fā)生碰撞而導致丟包，因此增加發(fā)送節(jié)點個數進行仿真。可以看到，改進前后算法網絡整體吞吐量增長情況均變緩，但Z-DMHCTR算法通過尋找額外的傳輸路徑與原算法相比仍提升了網絡的吞吐量。
圖5所示的平均端到端延時是通過式(10)計算所得：
其中N為成功傳送的分組數，tr(i)為分組傳輸至目的節(jié)點的時間，ts(i)為分組被發(fā)送的時刻。雖然改進后算法通過非父子關系路徑傳輸數據時可能使傳輸條數增多而增加部分延時，但同時也降低了數據包在節(jié)點處緩存而引發(fā)的延時。從實驗結果可以看出，雖然延時相差非常小，但改進算法因為所選路徑不為最短所造成的網絡延時并未影響網絡整體性能。
4 結束語
目前，ZigBee技術依然是最適合傳感器網絡接入端的短距離無線通信技術。而其樹型拓撲結構也因為支持節(jié)能操作和輕量級路由并且已擴展而得到了廣泛應用。但因Cluster-tree路由特點和ZigBee 技術本身傳輸帶寬限制，使其對突發(fā)大量數據的傳輸或圖像傳輸等一些高數據速率應用的處理存在問題。本文針對上情況提出改進的Z-DMHCTR算法，使網絡中節(jié)點發(fā)生擁塞前能夠尋找額外路徑傳輸數據，從而不僅可以提升網絡吞吐量，降低丟包率，還可以均衡網絡負載，避免部分節(jié)點因過度使用而死亡造成網絡分割，從而提升了網絡整體的性能。
參考文獻
[1] 唐寅.基于ZigBee的傳統(tǒng)路由協(xié)議研究與優(yōu)化[D].武漢：湖北大學，2013.
[2] 袁安娜.基于ZigBee網絡的能量均衡路由算法研究[D].哈爾濱：哈爾濱理工大學，2014.
[3] 馬海潮.ZigBee網絡可擴展性及分簇路由協(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技術的無線傳感器網絡路由算法研究[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混合路由能量優(yōu)化算法[J].計算機學報，2013，36(3)：485-493.