一種ZigBee網絡中孤立節點自主配置的方法

曹 曉，毛燕琴，沈蘇彬

(1.南京郵電大學 物聯網學院，江蘇 南京 210003；2.南京郵電大學 計算機學院，江蘇 南京 210003)

一種ZigBee網絡中孤立節點自主配置的方法

曹 曉1，毛燕琴2，沈蘇彬2

(1.南京郵電大學 物聯網學院，江蘇 南京 210003；2.南京郵電大學 計算機學院，江蘇 南京 210003)

ZigBee網絡設備結構簡單，硬件資源能力有限，因此會出現通信距離或節點失效等因素導致網絡鏈路發生故障，從而產生孤立節點和孤立節點蔓延等問題。孤立節點的發生會造成網絡異常，甚至造成網絡混亂。ZigBee標準協議的孤立節點重新加入網絡處理機制比較局限，無法有效使節點恢復網絡連接。針對孤立節點的自恢復網絡連接問題，提出代理子樹轉移加入(ASTJ)方法，一方面通過代理子樹節點將子樹網絡作為整體重新請求加入網絡，另一方面通過節點轉移的方式釋放飽和節點的地址空間，有效利用網絡地址。該方法能夠防止孤立節點蔓延，提高孤立節點的自主配置能力，修復網絡故障，加強網絡穩定性。仿真實驗結果表明，ASTJ能夠提高孤立節點加入率，有效修復網絡故障，并盡可能維持網絡原有的結構形態。

無線傳感器網絡；ZigBee；自主配置；孤立節點；加入率

0 引 言

傳感器網絡是將物品接入網絡的最基本要素，是物聯網的重要環節。由于物品的分布廣泛性、移動性，決定了傳感器網絡以無線形態為主，無線傳感器網絡(WSN)[1]有多種技術，如Bluetooth、Wi-Fi、移動通信技術(3G/4G)、ZigBee等。ZigBee[2]是基于IEEE802.15.4[3]協議標準開發的一種具有組網能力強、低功耗、低成本等特性的短距離無線組網通信技術。ZigBee協議具備自組網，孤立節點重新加入網絡(ReJoin)等相關的自主配置能力，盡可能地減少外部的介入就能夠保證系統穩定、可靠地運行。然而，ZigBee網絡中會因為網絡參數配置或無線鏈路失效等原因產生孤立節點[4]，標準的ZigBee協議對這一問題的解決能力有限，無法保證網絡的健壯性。文中針對標準ZigBee協議中孤立節點自主配置方法進行擴展，提出代理子樹轉移加入(ASTJ)機制，進一步提高孤立節點的自恢復能力，從而提高系統的穩定性。

1 技術分析及相關研究

1.1 ZigBee技術

ZigBee將設備分為三種[5]：協調器(ZC)、路由器(ZR)、終端設備(ZED)。其中協調器負責啟動、維護和控制網絡，允許路由器和終端設備加入網絡。路由器能夠加入網絡，并允許其他路由器或終端設備加入網絡。終端設備只能夠加入網絡。

ZigBee支持三種網絡拓撲：星型、樹型、網狀型。星型網絡拓撲要求所有節點位于與協調器單跳無線通信范圍之內，所有節點直接與協調器連接。網狀型網絡節點可以和其他節點以多跳的形式進行通信，采用AODV的簡化路由協議—AODVjr[6]。樹型網絡拓撲采用分布式地址分配方式(DAAM)[7]，協調器構建網絡后采用0x0000作為自己的短地址，當路由器和終端設備加入網絡后，使用父節點給它分配的16位短地址來通信。

地址計算公式[8]如下：

Cskip(d)=

A(Rn)=Aparent+1+Cskip(d)*(n-1),ZR地址

A(En)=Aparent+Cskip(d)*Rm+n,ZED地址

其中，Aparent是深度為d的父節點地址；Cskip指父節點的路由器子節點的地址間隔；A(Rn)是給第n個路由器子節點的分配地址；A(En)是給第n個終端子節點的分配地址；Lm,Cm,Rm是決定整個網絡架構的三個重要參數，Lm為網絡的最大深度，Cm為每個父節點擁有子節點的最大個數，Rm為在Cm個子節點中最多包含的路由節點個數。

分布式地址分配機制根據Lm,Cm,Rm的值確定整個網絡設備地址[9]。樹型路由根據分布式地址分配的特點使路由變得簡單，不需要保存路由表信息，節省存儲資源，減少路由操作，降低節點功耗，另外樹型拓撲具備多跳結構，能夠覆蓋較大的通信范圍，因此多數智能家居應用場景采用ZigBee樹型網絡拓撲[10]。

1.2 孤立節點問題

在ZigBee網絡中孤立節點是指無法與無線射頻通信范圍內的ZR/ZC節點連接的節點，形成孤立節點的原因主要有以下兩種：

(1)ZigBee網絡參數限制導致孤立節點發生。

ZigBee網絡中，每個節點都有一個64位的MAC地址，當設備獲得16位的短地址才說明設備成功加入網絡。協調器在構建網絡前需要確定參數Lm,Cm,Rm，參數確定后可能會導致有些節點在加入網絡時，因鄰居節點中沒有可用的地址空間，從而無法加入網絡，但此時整個網絡中還有充足的地址空間，稱這一現象為孤立節點問題[4]。

如圖1所示，節點ZR-A請求加入網絡，在通信范圍內的鄰居節點中，只能向節點ZR-B發起加入請求，由于節點ZR-B已經擁有子節點ZR-C,ZR-D和ZED，達到了網絡參數Cm=3的限制，沒有多余地址空間再分配給ZR-A節點，但是此時整個網絡中遠遠沒有達到飽和狀態，其他節點還有充足的地址空間。此時，ZR-A節點因為網絡參數配置的限制成為了孤立節點。

圖1 ZigBee樹型網絡示例

(2)鏈路、節點損壞導致孤立節點發生。

ZigBee標準對功耗要求比較嚴格，用普通干電池供電就能夠維持節點運行數月的時間，所以ZigBee節點往往采用功耗較低的嵌入式處理器，其計算能力較弱、存儲資源有限，這些硬件上的限制可能會導致設備發生不可預期的錯誤，比如系統崩潰、鏈路失效、重置等。盡管ZigBee標準提供了簡單的自配置和自修復機制，即失去連接的孤立節點啟動重新加入進程，但其仍很難維持網絡的連接性，使得一些節點成為孤立節點并無法再次和網絡構建連接，甚至會造成孤立節點蔓延問題[10]，使網絡的狀態變得更加混亂。

在樹型拓撲中，協調器在MAC層周期性向網絡廣播同步信標(Beacon)消息[11]，網絡中的節點通過同步信標消息保持同步，如果一個節點長時間未接收到同步信標消息，就可以認為鏈路失效或父節點失效，把自己標記為孤立節點，并啟動重新加入進程，查找新的父節點加入[10]。孤立節點蔓延問題是指在孤立節點啟動加入進程時，并不會向子節點發送同步信標消息，一旦孤立節點長時間沒有成功再次加入到網絡中，那么它的子節點也會因沒有接收到同步信標消息而變成孤立節點，那么最壞的情況下，所有孤立節點的子節點都會變成孤立節點。

如圖2所示，圖中表示ZigBee樹型網絡通過信標進行同步，節點ZC和節點ZR1間的鏈路發生故障導致無法傳播同步信標消息給子節點，節點ZR1的所有后代節點都將會和網絡失去同步，那么整個樹型網絡變成如圖3所示，ZR1節點及其所有后代節點都將變成孤立節點，這一現象稱為孤立節點蔓延。

圖2 樹型網絡發生鏈路故障示意圖

圖3 孤立節點蔓延示意圖

1.3 相關研究工作

針對ZigBee網絡孤立節點問題有一些研究提出了相應的解決方案，比如文獻[12]提出主動式和被動式方式來防止和解決孤立節點問題，該方法需要不斷檢測父節點和鏈路的狀況，會給網絡增加額外的通信開銷。文獻[13]提出一種動態選擇網絡參數的機制，這種方法一方面需要大量的數據交換，增加了不必要的功耗，另一方面會使得設備間的標準不夠統一，無法實現兼容性。文獻[14]針對由于參數限制導致的孤立節點，提出了通過轉移子節點，讓一些飽和節點釋放一部分地址空間給孤立節點，但是對當多孤立節點同時發起加入請求時，候選父節點如何去選擇最優的孤立節點并允許加入的情形欠缺考慮。文獻[10]提出了孤立節點蔓延問題，并針對該問題提出動態重構樹的結構來快速恢復，通過向子節點發送凍結信息來阻止孤立節點的蔓延。該文獻解決了孤立節點蔓延問題，但在節點重新加入網絡的過程沒有考慮最佳候選父節點的選擇，使用標準的重新加入進程無法保證節點能夠重新連接，也不能有效地利用地址空間。

文中針對文獻[10]提出的孤立節點蔓延問題，在其解決方案基礎上，增加最佳候選父節點的選擇以及最佳孤立節點選擇機制，并借鑒文獻[14]的孤立節點轉移方案，提出代理子樹轉移加入算法。圖2中ZR1未接收到信標消息的時間超過最大限制時，把自己標記為孤立節點，為了避免孤立節點蔓延，把自己作為子樹網絡的代理協調器，同步子樹網絡，代理整棵子樹發起重新加入請求，并通過孤立節點轉移方案提高加入網絡的成功率，充分利用網絡地址空間。

2 代理子樹轉移加入網絡算法

針對ZigBee網絡中由于鏈路故障或節點損壞導致包含子樹的節點與網絡失去連接而形成的孤立節點問題，文中設計了代理子樹轉移加入網絡算法(Agent Subtree Transfer Join,ASTJ)。該類孤立節點包含子節點，所以首先需要考慮孤立節點蔓延問題。首先向子樹網絡發送代理同步信標消息，使得子樹網絡中的節點能夠保持同步，然后孤立節點向候選父節點發送加入網絡請求，候選父節點通過轉移子節點的方式給孤立節點提供網絡地址。該方法能夠增加孤立節點加入網絡的成功率，維持網絡原有結構，提升網絡修復能力。

代理子樹轉移加入算法流程：

(1)孤立節點成為子樹網絡的代理協調器并向子節點發送代理同步信標消息，讓整個子網絡保持同步，避免所有子節點與網絡失去同步而造成孤立節點蔓延，并向子樹發送高度Lsub和子節點個數Csub統計信息請求。

(2)子樹中的節點接收到代理信標消息后，向代理協調器發送高度和子節點個數應答。

(3)代理協調器接收到應答，記錄子樹高度和子樹節點個數。遍歷鄰居節點列表向候選父節點發送加入請求NLME-JOIN.request{RejoinNetwork}，并將子樹高度和子樹節點個數作為參數發送。

(4)候選父節點接收到孤立節點發起的請求后，根據參數Lsub決定是否滿足作為父節點的條件，如果自己的深度+Lsub大于Lm的限制，那么將發送拒絕加入的應答消息；若滿足將遍歷子節點列表查看是否有地址空間。如果有，生成網絡地址并發送允許加入應答消息NLME-JOIN.confirm{Admission}；如果沒有，查看是否有可轉移子節點。可轉移子節點指除了當前連接的父節點外還能夠接入其他的節點作為父節點的節點，如果有將發送參數為可轉移子節點的應答消息NLME-JOIN.confirm{Transferable}，其他情況發送拒絕加入應答消息NLME-JOIN.confirm{Refuse}。

(5)孤立節點接收到所有候選父節點的應答消息后，如果有允許加入應答，選擇最佳父節點加入網絡，執行步驟(12)；如果只有參數為可轉移子節點的應答消息，則執行步驟(6)；如果全部都是拒絕加入應答消息，那么將退化成單一的孤立節點，放棄子樹網絡，重新發起加入網絡請求，執行步驟(11)。

(6)孤立節點選擇最佳的能夠轉移子節點的候選父節點發起轉移加入網絡請求NLME-JOIN.request{TransferRejoin}。

(7)候選父節點接收到孤立節點發送的請求后，將遍歷子節點列表選擇合適的子節點，如果發送請求的子樹節點數Csub大于Cskip/2，則發送NLME-LEAVE.request{TwoHop}，否則發送NLME-LEAVE.request{OneHop}。

(8)可轉移子節點接收到轉移請求后，如果參數為OneHop則向單跳范圍內的候選父節點發送加入請求NLME-JOIN.request{RejoinNetwork}；如果參數是TwoHop，那么將向候選父節點發送NLME-JOIN.request{TransferRejoin}請求。根據轉移結果向父節點發送應答消息。

(9)候選父節點接收到應答后，如果有子節點轉移成功，則向孤立節點發送允許加入應答，如果子節點轉移失敗，則向孤立節點發送拒絕加入應答。

(10)孤立節點接收到候選父節點的應答后，如果是允許加入則執行步驟(12)；如果拒絕加入，那么將向其他的候選父節點發起加入請求重復步驟(6)；如果沒有其他候選父節點可選擇時將退化成單一的孤立節點，放棄子樹網絡，重新發起加入網絡請求，執行步驟(11)。

(11)此時代理子樹加入網絡失敗，那么將退化成單一的孤立節點向候選父節點加入網絡請求，此時NLME-JOIN.request的子樹高度和子樹節點個數參數均為1，執行步驟(3)。

(12)如果代理子樹成功加入網絡，將向子樹網絡廣播更新節點信息消息，重新分配網絡地址；如果代理子樹退化成單一孤立節點成功加入網絡，則更新自身信息；如果仍然失敗，則經過一定時間間隔重新嘗試，執行步驟(3)。

在上述執行步驟中，需要解決如下幾個問題：

(1)候選父節點如何選擇最佳孤立節點：當候選父節點接收到多個孤立節點同時發起加入請求時，將會根據Csub/Cskip來選擇把地址優先提供給哪一個孤立節點。其中，Csub指孤立節點代理的子樹上的子節點個數，Cskip指候選父節點的單個路由子節點所能容納子節點的個數。Csub/Cskip越大即指孤立節點代理子樹包含的子節點個數占據候選父節點子節點容量的比例越高，優先級越大，能夠盡可能接納更多節點，提高網絡加入率。

(2)孤立節點如何選擇最佳候選父節點：當孤立節點接收到多個候選父節點的允許加入應答，應當首先根據候選父節點的深度來選擇，深度越小優先級越大，其次考慮鏈路狀態。

(3)候選父節點如何選擇最佳轉移子節點：如果有多個子節點可以被轉移，那么優先選擇單一的子節點，包含子節點最少的可轉移子節點。

(4)可轉移子節點在查找其他父節點時，也可以通過轉移子節點的方式來尋找，為了避免廣播帶來的額外通信負荷，規定最大通過兩跳來尋找其他父節點，即NLME-LEAVE.request{TwoHop}參數最大為TwoHop。

3 測試與分析

文中設計仿真實驗來驗證ASTJ算法的性能，主要驗證ASTJ算法是否能夠提高因鏈路失效而形成的孤立節點重新加入率，并與標準ZigBee協議處理孤立節點的方法進行對比分析，驗證是否能提升網絡鏈路故障恢復能力。ZigBee標準協議中規定，當節點與網絡失去同步時發起孤立節點重新加入網絡請求(Rejoin)，一方面孤立節點不會顧及子樹上的節點，另一方面在向候選父節點發起加入請求時，候選父節點僅查看自己是否有空余的地址空間，如果有則允許加入，否則拒絕加入。

實驗是在MATLAB仿真平臺上[15]實現，將ZigBee節點的屬性抽象成數據模型，并為每個節點建立鄰居表、子節點列表。實驗場地模擬為100m*100m，ZC位于場地中心，其他ZR和ZED隨機分布，假設節點并不移動，變化ZR和ZED節點的比率分別進行測試。仿真環境參數配置的具體詳情見表1。根據不同的參數生成相應的網絡拓撲，對同一網絡拓撲設置相同的鏈路故障，使其產生孤立節點，分別采用標準ZigBee和ASTJ方法來修復網絡故障。

表1 仿真參數配置

圖4表示固定ZED=50，變化ZR個數，故障發生前和故障修復后孤立節點加入率的結果。其中，節點加入率=接入網絡的節點數/總節點個數。網絡拓撲由于參數配置限制導致部分節點未能夠加入網絡而形成孤立節點，網絡中隨ZR數目的增加，加入率也在提升。在鏈路故障發生后，ASTJ機制的節點恢復能力比ZigBee標準機制有大約8%～13%的提升，提高了節點的加入率。

圖4 固定ZED個數，故障前后加入率實驗結果

圖5表示固定ZR=70，變化ZED個數，當ZED在節點中比例越高其孤立節點率急劇上升。在修復鏈路故障后，ASTJ機制的修復能力比ZigBee標準協議修復能力有所提高，但隨ZED比例的提高，其修復能力有所減弱，最后接近于標準ZigBee協議。

圖5 固定ZR個數，故障前后加入率實驗結果

4 結束語

文中分析了ZigBee網絡中孤立節點形成原因及孤立節點蔓延問題，提出ASTJ算法降低孤立節點的發生，并在故障發生后，減少孤立節點的發生，防止孤立節點蔓延，提高網絡節點接入率。最后通過仿真實驗驗證，與ZigBee標準協議相比，ASTJ算法對網絡故障恢復能力有明顯提升。

[1] 錢志鴻,王義君.面向物聯網的無線傳感器網絡綜述[J].電子與信息學報,2013,35(1):215-227.

[2]AllianceZB,SpecificationsZB.ZigBeespecification[EB/OL].2008.http://www.zigbee.org.

[3]IEEEStandardCommittee.IEEEstandard802,part15.4:wi-relessmediumaccesscontrolandphysicallayerspecificationsforlow-ratewirelesspersonalareanetworks(LR-WPANs)[S].[s.l.]:IEEEStandardCommittee,2003.

[4]PanMS,TsaiCH,TsengYC.TheorphanprobleminZigBeewirelessnetworks[J].IEEETransactionsonMobileComputing,2009,8(11):1573-1584.

[5] 杜軍朝,劉 惠,劉傳益,等.ZigBee技術原理與實戰[M].北京:機械工業出版社,2015:28-29.

[6] 謝 川.基于ZigBee的AODVjr算法研究[J].計算機工程,2011,37(10):87-89.

[7]FarahaniS.ZigBeewirelessnetworksandtransceivers[M].[s.l.]:Newnes,2011.

[8] 韓敬海,李瑞改,張玉星,等.Zigbee開發技術及實踐[M].西安:西安電子科技大學出版社,2014.

[9] 黃學哲,鄧慶緒,金順希.ZigBee分布式地址分配機制與研究現狀[J].信息技術,2012(11):40-42.

[10]HwangKI.DesigningrobustZigBeenetworkswithenhancedself-configuration[C]//Digestoftechnicalpapersinternationalconferenceonconsumerelectronics.[s.l.]:IEEE,2009:1-2.

[11] 高廣恩,劉全利,賈靈利,等.一種基于超幀機制的Zigbee時間同步算法研究與實現[J].大連理工大學學報,2012,52(5):719-724.

[12]AttiaSB,CunhaA,KoubaA,etal.Fault-tolerancemechanismsforZigBeewirelesssensornetworks[C]//Work-in-Progress(WiP)sessionofthe19thEuromicroconferenceonreal-timesystems.Pisa,Italy:[s.n.],2007:37-40.

[13]HuSC,LinCK,TsengYC.AutomaticparameterselectionfortheZigBeedistributedaddressassignmentmechanism[C]//24thinternationalsymposiumonpersonalindoorandmobileradiocommunications.[s.l.]:IEEE,2013:2062-2066.

[14]SongTW,YangCS.AconnectivityimprovingmechanismforZigBeewirelesssensornetworks[C]//IEEE/IFIPinternationalconferenceonembeddedandubiquitouscomputing.[s.l.]:IEEE,2008:495-500.

[15] 陳 杰.MATLAB寶典[M].北京:電子工業出版社,2011.

A Self-configuration Scheme of Orphan Nodes in ZigBee Network

CAO Xiao1，MAO Yan-qin2，SHEN Su-bin2

(1.School of Internet of Things，Nanjing University of Posts and Telecommunications,Nanjing 210003,China；2.School of Computer，Nanjing University of Posts and Telecommunications, Nanjing 210003,China)

The structure of ZigBee device is simple and hardware is circumscribed,so the communication range or node failure may lead to link failure,then orphan nodes and orphan propagation problems are produced in ZigBee network and would cause anomalies and even chaotic.The mechanism of standard ZigBee protocol is limitation to resolve orphan node.Aiming at this problem,the Agent Sub-tree Transfer Join (ASTJ) method is proposed to resolve the renewed connection for the orphan nodes,that is,orphan nodes as a whole sub-tree network rejoins the network and utilizes the network address by the way of nodes transfer.The method can prevent the spread of orphan nodes,improve the self-configuration capability of the orphan node,fix the network fault,and increase stability of the network.As the experimental result shows,ASTJ can improve the join ratio evidently,repair network fault effectively,and maintain the network structure as soon as possible.

WSN;ZigBee;self-configuration;orphan nodes;join ratio

2016-01-20

2016-05-17

時間：2016-10-24

江蘇省未來網絡前瞻性研究(BY2013095-1-08)；南京郵電大學自然科學基金(NY211115)

曹 曉(1991-),男，碩士研究生，研究方向為無線傳感器網絡；沈蘇彬，研究員，博士生導師，研究方向為計算機網絡、下一代電信網及網絡安全。

http://www.cnki.net/kcms/detail/61.1450.TP.20161024.1113.038.html

TP393

A

1673-629X(2016)11-0172-05

10.3969/j.issn.1673-629X.2016.11.038