白樂(lè)強(qiáng)，王佳林，張士宏

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

ZigBee是一種開(kāi)放性的低功耗、低成本、低數(shù)據(jù)速率、低復(fù)雜度、低分本、自組織的新型短距離無(wú)線通信技術(shù)［1］，是基于IEEE802.15.4標(biāo)準(zhǔn)的個(gè)域網(wǎng)協(xié)議［2］.ZigBee采用IEEE802.15.4制定的物理層（PHY）和媒體訪問(wèn)控制層（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ò)，每個(gè)路由節(jié)點(diǎn)對(duì)于整個(gè)網(wǎng)絡(luò)通信的可靠性都起到關(guān)鍵性作用，工作方式不當(dāng)造成的節(jié)點(diǎn)失效會(huì)造成網(wǎng)絡(luò)的部分癱瘓，所以改進(jìn)ZigBee傳輸算法是提高ZigBee網(wǎng)絡(luò)可靠性的有效方法.

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

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

1 模型的建立

1.1 分布式地址分配

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

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

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

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

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

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

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

該算法有兩個(gè)問(wèn)題，一是即使目的節(jié)點(diǎn)是信息源的鄰居節(jié)點(diǎn)，多播信息也會(huì)根據(jù)父子邏輯關(guān)系，經(jīng)過(guò)多跳才到達(dá)目的節(jié)點(diǎn).二是該多播方法會(huì)消耗過(guò)多路由，尤其是Lm較小的節(jié)點(diǎn).ZigBee鄰居多播路由算法針對(duì)這兩個(gè)問(wèn)題進(jìn)行了改進(jìn).信息源在轉(zhuǎn)發(fā)信息之前首先給自己的鄰居節(jié)點(diǎn)發(fā)送目的地址判斷信息，鄰居節(jié)點(diǎn)根據(jù)自己的鄰居表來(lái)判斷周圍是否存在目的節(jié)點(diǎn)，根據(jù)存在情況選擇是否接受信息源節(jié)點(diǎn)信息并轉(zhuǎn)發(fā).如圖2所示，S將信息轉(zhuǎn)發(fā)給N1、N4，兩節(jié)點(diǎn)分別將信息轉(zhuǎn)發(fā)給N3、N5.N5沒(méi)有直接將信息轉(zhuǎn)發(fā)給目的節(jié)點(diǎn)N6，而是轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)中目的節(jié)點(diǎn)較多的N7節(jié)點(diǎn)，如此做可以節(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鄰居多播路由算法定義一個(gè)轉(zhuǎn)發(fā)優(yōu)先級(jí)參數(shù)ForwardingLevel，F(xiàn)orwardingLevel初始化為-1.ForwardingLevel是一個(gè)整數(shù)，表示信息源節(jié)點(diǎn)一跳鄰居節(jié)點(diǎn)的鄰居表中未接受信息的目的節(jié)點(diǎn)的數(shù)量，目的節(jié)點(diǎn)越多Forwarding Level值越大，最大值為該節(jié)點(diǎn)一跳鄰居節(jié)點(diǎn)數(shù)量，即該節(jié)點(diǎn)鄰居節(jié)點(diǎn)都為目的節(jié)點(diǎn)，最小為0即沒(méi)有目的節(jié)點(diǎn).信息源轉(zhuǎn)發(fā)多播信息之前首先比較本節(jié)點(diǎn)的鄰居表，將信息轉(zhuǎn)發(fā)給一跳鄰居節(jié)點(diǎn)本身就是目的節(jié)點(diǎn)的節(jié)點(diǎn)，這些節(jié)點(diǎn)做出標(biāo)記表示已接收該多播信息，以免重復(fù)接收信息.然后信息源所有一跳鄰居節(jié)點(diǎn)根據(jù)ID從小到大開(kāi)始確定轉(zhuǎn)發(fā)優(yōu)先級(jí)，開(kāi)始尋找優(yōu)先級(jí)最大轉(zhuǎn)發(fā)節(jié)點(diǎn).

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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

［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.