基于鄰居表查詢的ZigBee多播路由算法

白樂強，王佳林，張士宏

（沈陽建筑大學(xué) 信息與控制工程學(xué)院，遼寧 沈陽 110168）

ZigBee是一種開放性的低功耗、低成本、低數(shù)據(jù)速率、低復(fù)雜度、低分本、自組織的新型短距離無線通信技術(shù)［1］，是基于IEEE802.15.4標(biāo)準(zhǔn)的個域網(wǎng)協(xié)議［2］.ZigBee采用IEEE802.15.4制定的物理層（PHY）和媒體訪問控制層（MAC）制定的標(biāo)準(zhǔn)，ZigBee的高層標(biāo)準(zhǔn)采用ZigBee聯(lián)盟制定的網(wǎng)絡(luò)層（NWK）、應(yīng)用層（APL）等.ZigBee設(shè)備可以分為ZigBee協(xié)調(diào)器（ZC）、ZigBee路由（ZR）、ZigBee終端設(shè)備 （ZED）等三種.由于ZigBee網(wǎng)絡(luò)是自組織網(wǎng)絡(luò)，每個路由節(jié)點對于整個網(wǎng)絡(luò)通信的可靠性都起到關(guān)鍵性作用，工作方式不當(dāng)造成的節(jié)點失效會造成網(wǎng)絡(luò)的部分癱瘓，所以改進ZigBee傳輸算法是提高ZigBee網(wǎng)絡(luò)可靠性的有效方法.

文獻［3］提出多播樹傳動比算法 ，該算法是量化了多播樹的成本，考慮無線多播信道的鏈路質(zhì)量，以及無線多播的特點提出的一種算法.文獻［4］提出的網(wǎng)型多播算法是一種考慮到節(jié)約能量的無線傳感器算法.針對節(jié)點移動的無線傳感網(wǎng)絡(luò)文獻［5］提出了智能多播路由器發(fā)現(xiàn)機制的移動多播，文獻［6］提出了本地樹更改多播協(xié)議.對于實時性文獻［7］提出了實時多跳無線多播路由算法，這些算法都適用于Ad-hoc形式網(wǎng)絡(luò)，不能直接在WSN中應(yīng)用，因為這些算法都是對于高存儲高計算節(jié)點來設(shè)計的，文獻［8］提出適用于ZigBee網(wǎng)絡(luò)的多播算法、Z-CAST路由算法.然而Z-CAST算法是根據(jù)樹形結(jié)構(gòu)路由表轉(zhuǎn)發(fā)原理基礎(chǔ)上進行信息的傳送，在提高使用節(jié)點能量優(yōu)化方面沒有進行考慮.

本文在Z-Cast算法基礎(chǔ)上，針對轉(zhuǎn)發(fā)多播信息過程中轉(zhuǎn)發(fā)節(jié)點的浪費問題提出了ZigBee鄰居多播路由算法（ZNMR）.該算法綜合考慮目的節(jié)點的位置及規(guī)模來選擇轉(zhuǎn)發(fā)路徑，對不同形式的多播組采用不同的路由算法，算法計算量小，適用于ZigBee網(wǎng)絡(luò)多播信息的發(fā)送.

1 模型的建立

1.1 分布式地址分配

ZigBee網(wǎng)絡(luò)同其他無線傳感器網(wǎng)絡(luò)主要的不同之處在于其采用地址分配方式，它給每個潛在父節(jié)點提供一個有限的網(wǎng)絡(luò)地址子塊.整個網(wǎng)絡(luò)的地址在一個特定的網(wǎng)絡(luò)內(nèi)是唯一的，由一個父節(jié)點分配給它的子節(jié)點.分配方案由分布式算法根據(jù)一系列網(wǎng)絡(luò)自定義參數(shù)確定，網(wǎng)絡(luò)協(xié)調(diào)者決定了整個網(wǎng)絡(luò)的最大子設(shè)備數(shù).每個設(shè)備有一個相關(guān)的深度，表示只使用父子鏈路傳輸?shù)囊粋€幀到達ZigBee協(xié)調(diào)器，必須經(jīng)過的最少跳數(shù).其中協(xié)調(diào)者自身的連接深度為0，其直接子設(shè)備為1.ZigBee協(xié)調(diào)器首先根據(jù)需要規(guī)定3個參數(shù)：網(wǎng)絡(luò)的最大深度nwkMaxDepth（Lm），一個父節(jié)點可以有的子節(jié)點最大個數(shù)的值nwkMaxChildren（Cm）和一個父節(jié)點可以有的路由器子節(jié)點的最大個數(shù)nwkMaxRouters（Rm），其中Cm 應(yīng)大于等于Rm，這樣就可以保證協(xié)調(diào)器或者路由器可以連接至少Cm-Rm個終端節(jié)點.網(wǎng)絡(luò)深度為d的路由節(jié)點所能分配的地址空間Cskip（d）滿足公式（1）

如果一個父節(jié)點它的深度是d，它的地址是Aparent，那么第n個子路由節(jié)點的地址如公式（2）：

而它的第n個子節(jié)點地址如公式（3）：

一個Cskip（d）值大于0的父節(jié)點設(shè)備必須接收子節(jié)點設(shè)備，根據(jù)子節(jié)點設(shè)備是否具有路由器功能，并給它們分配不同的地址.一個父節(jié)點給它的第一個路由功能子節(jié)點設(shè)備分配一個地址1，大于它自己的地址.ZigBee協(xié)調(diào)器為每一個ZigBee設(shè)備分配了一個固定的ID.并且每一個ZigBee節(jié)點不僅記錄了父節(jié)點與子節(jié)點ID，而且記錄了自己一跳鄰居節(jié)點的ID.

1.2 ZigBee網(wǎng)絡(luò)轉(zhuǎn)發(fā)模型

Z-Cast的樹形路由算法是根據(jù)父子關(guān)系進行信息轉(zhuǎn)發(fā)，不需要路由選擇，如圖1所示，圖中S為信息源節(jié)點，N3、N5、N6、N8、N10、N11為目的節(jié)點，ZC為協(xié)調(diào)器，信息從S向外轉(zhuǎn)發(fā).轉(zhuǎn)發(fā)過程如虛線箭頭所示，S通過N1、N2將信息發(fā)送給協(xié)調(diào)器，協(xié)調(diào)器再根據(jù)目的地址發(fā)送給子路由，最終信息到達目的節(jié)點.

圖1 樹形路由算法的信息轉(zhuǎn)發(fā)路徑選擇示意圖Fig.1 Schematic diagram of Tree routing algorithm forwarding path selection

該算法有兩個問題，一是即使目的節(jié)點是信息源的鄰居節(jié)點，多播信息也會根據(jù)父子邏輯關(guān)系，經(jīng)過多跳才到達目的節(jié)點.二是該多播方法會消耗過多路由，尤其是Lm較小的節(jié)點.ZigBee鄰居多播路由算法針對這兩個問題進行了改進.信息源在轉(zhuǎn)發(fā)信息之前首先給自己的鄰居節(jié)點發(fā)送目的地址判斷信息，鄰居節(jié)點根據(jù)自己的鄰居表來判斷周圍是否存在目的節(jié)點，根據(jù)存在情況選擇是否接受信息源節(jié)點信息并轉(zhuǎn)發(fā).如圖2所示，S將信息轉(zhuǎn)發(fā)給N1、N4，兩節(jié)點分別將信息轉(zhuǎn)發(fā)給N3、N5.N5沒有直接將信息轉(zhuǎn)發(fā)給目的節(jié)點N6，而是轉(zhuǎn)發(fā)給鄰居節(jié)點中目的節(jié)點較多的N7節(jié)點，如此做可以節(jié)約轉(zhuǎn)發(fā)路由數(shù)量及轉(zhuǎn)播跳數(shù)，提高了網(wǎng)絡(luò)的轉(zhuǎn)發(fā)效率.

圖2 ZigBee鄰居多播路由算法的多播信息轉(zhuǎn)發(fā)路徑選擇示意圖Fig.2 Schematic diagram of ZigBee neighbor multicast routing algorithm forwarding path selection

2 ZigBee鄰居多播路由算法

ZigBee鄰居多播路由算法定義一個轉(zhuǎn)發(fā)優(yōu)先級參數(shù)ForwardingLevel，F(xiàn)orwardingLevel初始化為-1.ForwardingLevel是一個整數(shù)，表示信息源節(jié)點一跳鄰居節(jié)點的鄰居表中未接受信息的目的節(jié)點的數(shù)量，目的節(jié)點越多Forwarding Level值越大，最大值為該節(jié)點一跳鄰居節(jié)點數(shù)量，即該節(jié)點鄰居節(jié)點都為目的節(jié)點，最小為0即沒有目的節(jié)點.信息源轉(zhuǎn)發(fā)多播信息之前首先比較本節(jié)點的鄰居表，將信息轉(zhuǎn)發(fā)給一跳鄰居節(jié)點本身就是目的節(jié)點的節(jié)點，這些節(jié)點做出標(biāo)記表示已接收該多播信息，以免重復(fù)接收信息.然后信息源所有一跳鄰居節(jié)點根據(jù)ID從小到大開始確定轉(zhuǎn)發(fā)優(yōu)先級，開始尋找優(yōu)先級最大轉(zhuǎn)發(fā)節(jié)點.

信息源確認(rèn)一跳鄰居節(jié)點的鄰居表中未接受信息的目的節(jié)點數(shù)量，記為ForwardingLevel.若鄰居表中無目的節(jié)點或目的節(jié)點都已接受該組多播信息則ForwardingLevel為0.當(dāng)信息源確認(rèn)過所有鄰居節(jié)點優(yōu)先級，選取ForwardingLevel最大的節(jié)點作為轉(zhuǎn)發(fā)節(jié)點.若兩個節(jié)點優(yōu)先級相同則根據(jù)ID進行判斷，ID小的優(yōu)先級比ID大的優(yōu)先級高.信息源其他一跳鄰居節(jié)點Forwarding Level不變，以供信息源再次挑選轉(zhuǎn)發(fā)節(jié)點時使用.

當(dāng)轉(zhuǎn)發(fā)節(jié)點準(zhǔn)備發(fā)送信息時，首先從信息源接受信息，然后將多播信息發(fā)送給未接受信息目的節(jié)點.轉(zhuǎn)發(fā)節(jié)點將信息轉(zhuǎn)發(fā)給所有鄰居表中的目的節(jié)點后，該節(jié)點轉(zhuǎn)發(fā)優(yōu)先級ForwardingLevel置0，不再作為轉(zhuǎn)發(fā)節(jié)點.信息源重新計算Forwarding Level大于0的信息源一跳鄰居節(jié)點轉(zhuǎn)發(fā)優(yōu)先級，選擇新的轉(zhuǎn)發(fā)節(jié)點.直到信息源所有一跳鄰居節(jié)點ForwardingLevel都為0，該信息源節(jié)點轉(zhuǎn)發(fā)信息完畢，將自身的轉(zhuǎn)發(fā)優(yōu)先級Forwarding Level置0.根據(jù)ID從小到大在已接受信息的目的節(jié)點中重新尋找新的節(jié)點作為信息源，直到網(wǎng)絡(luò)中所有目的節(jié)點都已經(jīng)收到信息，該組多播信息發(fā)送完畢.ZigBee鄰居多播路由算法流程圖如圖3所示.

圖3 ZigBee鄰居多播路由算法流程圖Fig.3 Flow chart of ZigBee neighbor multicast routing algorithm

3 數(shù)據(jù)仿真及分析

本文采用MATLAB平臺進行仿真，對ZigBee鄰居多播路由算法的可行性進行仿真以及對結(jié)果進行分析，在200m×200m的空間內(nèi)隨機生成50到200個ZigBee節(jié)點，按一定的比例從中產(chǎn)生目的節(jié)點.每個節(jié)點的最大傳輸范圍為40m，節(jié)點能容納最大子節(jié)點數(shù)Cm為6，節(jié)點深度Lm為4，并且所有節(jié)點都是穩(wěn)定的.模型運行時假設(shè)物理層與數(shù)據(jù)鏈路層都正常工作.對ZCAST算法和ZigBee鄰居多播路由算法進行試驗.

試驗選取了50、75、100、125、150、175和200七種ZigBee節(jié)點數(shù)量規(guī)模的網(wǎng)絡(luò)場景，其中隨機各選擇10%～50%比例節(jié)點作為目的節(jié)點，在隨機生成場景的前提下，兩種算法對隨機選擇信息源節(jié)點與選擇ZigBee協(xié)調(diào)器（ZC）作為源節(jié)點兩種情況進行仿真，每種場景仿真100次，統(tǒng)計仿真結(jié)果來求取平均值，取得的數(shù)據(jù)如表1～表4.

表1 目的節(jié)點比例為20%信息源隨機選取結(jié)果Table 1 Results of destination node ratio is 20%and the source is selected randomly

表2 節(jié)點數(shù)量為100信息源隨機選取結(jié)果Table 2 Results of the number of nodes is 100and the source is selected randomly

表3 目的節(jié)點比例為20%信息源選取ZC結(jié)果Table 3 Results of destination node ratio is 20%and the source is ZC

表4 節(jié)點數(shù)量為100信息源選取ZC結(jié)果Table 4 Results of the number of nodes is 100and the source is ZC

圖4 Z-Cast算法的信息轉(zhuǎn)發(fā)路徑選擇圖Fig.4 Z-Cast algorithm forwarding path selection

圖5 ZigBee鄰居多播路由算法的信息轉(zhuǎn)發(fā)路徑選擇圖Fig.5 ZigBee neighbor multicast routing algorithm forwarding path selection

圖4、圖5為100節(jié)點目的節(jié)點比為20%條件下隨機生成的兩算法的多播信息轉(zhuǎn)發(fā)路徑選擇圖，空心點表示ZigBee普通節(jié)點，十字節(jié)點表示目的節(jié)點，實心點表示轉(zhuǎn)發(fā)節(jié)點，三角形表示信息源，坐標(biāo)（100，100）的節(jié)點為ZigBee協(xié)調(diào)器，每一條黑色虛線表示節(jié)點之間傳輸信息.圖4中信息源節(jié)點首先將信息發(fā)送給信息源的父節(jié)點，直到ZigBee協(xié)調(diào)器，協(xié)調(diào)器再將信息根據(jù)目的地址通過父子關(guān)系的路由節(jié)點轉(zhuǎn)發(fā)給各目的節(jié)點.即使目的節(jié)點就在信息源附近，信息源也不會將信息直接發(fā)送給目的節(jié)點，這樣對于整個網(wǎng)絡(luò)的能量是一種浪費，而且每次新一組多播信息的發(fā)送都會使用Lm較小的路由節(jié)點，使上層路由過多的損耗，長期下去會影響網(wǎng)絡(luò)可靠性.圖5中ZigBee鄰居多播路由算法使節(jié)點在轉(zhuǎn)發(fā)信息之前進行判斷，使信息呈放射狀向整個網(wǎng)絡(luò)的目的節(jié)點轉(zhuǎn)發(fā)，每一次轉(zhuǎn)發(fā)信息都有多個接收者，而且信息不必須經(jīng)過協(xié)調(diào)器.這樣轉(zhuǎn)發(fā)不僅減少了轉(zhuǎn)發(fā)節(jié)點，而且減少了Lm較小的路由的使用，提高了網(wǎng)絡(luò)的可靠性.

由表1可以看出在目的節(jié)點比例為20%情況下，隨著節(jié)點個數(shù)不斷增加，兩算法的轉(zhuǎn)發(fā)節(jié)點都隨之增加.但ZNMR算法轉(zhuǎn)發(fā)節(jié)點明顯少于Z-CAST算法，且節(jié)點越多ZNMR算法的優(yōu)勢越明顯.由表2可以看出在目的節(jié)點數(shù)量確定而目的節(jié)點比例不斷增加的情況下，ZNMR算法轉(zhuǎn)發(fā)個數(shù)也少于Z-CAST算法.但是當(dāng)目的節(jié)點比例很大時，該算法轉(zhuǎn)發(fā)節(jié)點個數(shù)逐漸接近Z-CAST算法，這是因為許多較上層的路由節(jié)點也成為了目的節(jié)點，所以無論使用何種算法轉(zhuǎn)發(fā)節(jié)點個數(shù)都沒有明顯差距.對比表1表3，表2表4可以看出當(dāng)ZigBee協(xié)調(diào)器作為信息源轉(zhuǎn)發(fā)信息時，兩算法轉(zhuǎn)發(fā)節(jié)點都有少量的減少，但由表3表4可以看出ZNMR算法仍然適用于該網(wǎng)絡(luò)，即信息源位置的選取對于不同算法之間轉(zhuǎn)發(fā)節(jié)點數(shù)量的影響是不大的.

4 結(jié) 論

本文基于鄰居表查詢和ZigBee分布式地址分配特點，結(jié)合傳統(tǒng)的無線傳感器多播路由算法提出了ZigBee鄰居多播路由算法.采用MATLAB進行仿真，實驗結(jié)果表明該算法減少了ZigBee多播路由轉(zhuǎn)發(fā)節(jié)點，提高了多播算法效率，在節(jié)約能量方面有了很大改進.該算法對于大規(guī)模ZigBee網(wǎng)絡(luò)多播信息發(fā)送是一個可改進的算法.

［1］ ZigBee Alliance.Document 053474r17ZigBee specification［S］.2008.

［2］ The LANMAN Standards Committee.IEEE Std 802.15.4TM-2003 ［S］.New York，USA：the Institute of Electrical and Electronics Engineers，2003.

［3］ Jung Y，Choi S，Hwang I，et al.Cost-Effective Multicast Routings in Wireless Mesh Networks［J］.Communications in Computer and Information Science，2011（262）PART 1：262-271.

［4］ Zeng G，Wang C，Xiao L.Grid Multicast：An Energy-Efficient Multicast Algorithm for Wireless Sensor Networks［C］.4th International Conference on Networked Sensing Systems，INSS 2007：267-274.

［5］ Lee H，Han S.Intelligent Multicast Router Discovery Mechanism in Mobile Multicast［C］.Advanced Industrial Conference on Telecommunications／Service Assurance with Partial and Intermittent Resources Conference／E-Learning on Telecommunications Workshop AICT／SAPIR／ELETE 2005：152-156.

［6］ Srinivasan T，Chandrasekar R，Vijaykumar V，et al.Localized Tree Change Multicast Protocol for Mobile Ad Hoc Networks［C］.Second International Conference on Wireless and Mobile Communications，ICWMC 2006.

［7］ Yi J，Poellabauer C.Real-Time Multicast for Wireless Multihop Networks ［J］. Computers and Electrical Engineering，2010（36）：313-327.

［8］ Gaddour O，KoubaaA，Cheikhrouhou O，et al.Z-Cast：A Multicast Routing Mechanism in ZigBee Cluster-Tree Wireless Sensor Networks［C］.IEEE 30th International Conference on Distributed Computing Systems Workshops 2010：171-179.