基于節(jié)點轉(zhuǎn)移的ZigBee網(wǎng)絡(luò)路由改進算法

李躍 黃希玲 賈海瑞

摘 要：ZigBee網(wǎng)絡(luò)的一個主要的目標(biāo)就是降低網(wǎng)絡(luò)的耗能，以延長網(wǎng)絡(luò)的使用時間。但ZigBee協(xié)議中的網(wǎng)絡(luò)結(jié)構(gòu)和路由算法并沒有完整的討論能量消耗問題。該文提出一種改進的分布式路由算法，該算法盡可能通過電源供電路由節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)，最終減少電池供電路由節(jié)點的能量消耗來延長網(wǎng)絡(luò)的生存時間。仿真結(jié)果表明，該算法只需少量的通訊開銷就可以明顯地減少電池供電路由節(jié)點的耗能。

關(guān)鍵詞：ZigBee協(xié)議 能耗有效 路由 算法

中圖分類號：TP393 文獻標(biāo)識碼：A 文章編號：1674-098X（2015）02（b）-0013-03

Improved Algorithm of ZigBee Network Based on Node-Transporting

Li Yue1 Huang xiling1 Jia Hairui2

（1.City College of Southwest University of Science and Technology，Mianyang，621010，China；2.Sichuan airport consciousness Technology Co. Ltd.Chengdu，610000，China）

Abstract：One of the primary goals of ZigBee is low power consumption and therefore long-living networks.Current network formation and routing protocols described in the ZigBee specification do not completely discuss power consumption issues.Distributed routing algorithm to reduce power consumption of battery-powered devices by routing the communication through mains-powered devices is proposed.The proposed algorithm works in tree topologies supported by ZigBee and requires only minor modifications to the current specification. The simulation results showed that the algorithm is able to reduce the power consumption of battery-powered devices significantly with minimal communication overhead.

Key Words：ZigBee Standard； Energy Efficient； Routing；Algorithm

ZigBee技術(shù)是一種低成本、低功耗、低速率的基于IEEE 802.15.4無線標(biāo)準(zhǔn)有關(guān)組網(wǎng)、安全和應(yīng)用軟件方面的短距離雙向無線通信技術(shù)，該技術(shù)主要針對低速率無線傳感器網(wǎng)絡(luò)和控制網(wǎng)絡(luò)而設(shè)計，能夠滿足小型化，低成本設(shè)備（如智能家居，工業(yè)控制和傳感器網(wǎng)絡(luò)等）的無線網(wǎng)絡(luò)要求，廣泛地應(yīng)用于工業(yè)、建筑等無線通信應(yīng)用場合[1]。

ZigBee協(xié)議中的網(wǎng)絡(luò)結(jié)構(gòu)和路由算法并沒有完整的討論節(jié)點能量消耗問題[2]。文獻[3]討論了通過引入鄰居表，在選擇路由的時候考慮節(jié)點的剩余能量，盡量避開剩余能量較低的節(jié)點。文獻[4]分析了ZigBee傳感器網(wǎng)絡(luò)協(xié)議棧不同層的能量效率。文獻[5]提出了根據(jù)數(shù)據(jù)包的到達率，采用動態(tài)的信標(biāo)間隔來增加節(jié)點的休眠時間以節(jié)約能量。文獻[6]提出了一種使用跨層費用計算函數(shù)構(gòu)造樹路由的算法，該函數(shù)綜合考慮了剩余能量，信道質(zhì)量和路由跳數(shù)。同樣在文獻[7]中提出在ZigBee網(wǎng)絡(luò)的路由發(fā)現(xiàn)階段，采用構(gòu)造的函數(shù)來選擇能量滿足的路徑，延遲受限制的路徑。

但現(xiàn)有的文獻資料對在ZigBee無線網(wǎng)絡(luò)中電源供電設(shè)備和電池供電設(shè)備共存的情況沒有深入的研究，而有關(guān)大量ZigBee無線傳感器網(wǎng)絡(luò)的應(yīng)用設(shè)計中，不同電源類型的設(shè)備可以共存，例如，智能家居、樓宇自動化以及工業(yè)控制等[1]，在這些應(yīng)用中部分節(jié)點能夠使用外接持續(xù)電源。網(wǎng)絡(luò)中電池供電的節(jié)點設(shè)備和電源供電的節(jié)點設(shè)備可以共存，電源供電的節(jié)點設(shè)備能夠降低維修的費用，而電池供電的節(jié)點設(shè)備使用在不容易布線或布線代價較高的位置。該文深入研究了ZigBee網(wǎng)絡(luò)的組網(wǎng)技術(shù)及其路由算法，結(jié)合電源供電設(shè)備和電池供電設(shè)備的特點，構(gòu)建了相應(yīng)的算法模型，提出了一種基于ZigBee樹型網(wǎng)絡(luò)的電源感知路由算法（Power-Aware Routing Algorithm， PARA）。PARA算法基于簇樹型網(wǎng)絡(luò)拓?fù)洌脕頊p少ZigBee網(wǎng)絡(luò)中電池供電節(jié)點的能量消耗，延長網(wǎng)絡(luò)運行時間。

1 算法模型構(gòu)建與分析

由ZigBee網(wǎng)絡(luò)的樹路由算法可知，路由完全依賴父節(jié)點和子節(jié)點的關(guān)系。這樣在ZigBee網(wǎng)絡(luò)中就存在以下幾個問題：（1）即使目的節(jié)點在轉(zhuǎn)發(fā)節(jié)點的一跳通信范圍內(nèi)，數(shù)據(jù)包也必須沿樹拓?fù)鋫魉偷侥康墓?jié)點，而無法直接發(fā)送到目的節(jié)點[3]。（2）某些實用的網(wǎng)絡(luò)拓?fù)渲校掷m(xù)電源設(shè)備與電池供電設(shè)備共存，如果采用現(xiàn)有的樹路由算法，所有的路由都是單一的，這樣網(wǎng)絡(luò)中某些電池供電節(jié)點會過早耗盡電池的能量，縮短網(wǎng)絡(luò)的使用時間。

分析圖1構(gòu)建的ZigBee簇樹混合電源節(jié)點網(wǎng)絡(luò)模型，圖中C是網(wǎng)絡(luò)的協(xié)調(diào)器節(jié)點，標(biāo)號R1～R13的節(jié)點是FFD節(jié)點，RFD節(jié)點略去，電源供電的路由節(jié)點用實線表示，電池供電的路由節(jié)點用虛線表示。當(dāng)路由節(jié)點R6與路由節(jié)點R3、R5通信時，其路由分別是R6 -R2-C-R3，R6 -R2-C-R1-R4-R5。以上路由中，需要電池供電結(jié)點R1、R2和R4轉(zhuǎn)發(fā)數(shù)據(jù)，使得電池供電節(jié)點消耗能量增加，網(wǎng)絡(luò)容易因個別電池供電節(jié)點能量的耗盡而中斷。

2 電源感知路由算法

2.1 算法思想

電源感知路由算法思想是盡可能的通過持續(xù)電源節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)，減少電池供電節(jié)點的數(shù)據(jù)轉(zhuǎn)發(fā)量。樹型網(wǎng)絡(luò)拓?fù)渲校瑑晒?jié)點間只有一條路由通路，樹型網(wǎng)絡(luò)形成后，就沒有可選擇的路由來減少電池供電設(shè)備的數(shù)據(jù)轉(zhuǎn)發(fā)量[2]。一個可行的方案是依據(jù)流量的動態(tài)分布改變樹型網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，通過持續(xù)電源節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)，減少電池供電節(jié)點的數(shù)據(jù)轉(zhuǎn)發(fā)量，降低網(wǎng)絡(luò)中電池供電路由節(jié)點的總負(fù)載。

例如將圖1中節(jié)點R6與節(jié)點R2的連接斷開，而將節(jié)點R6連接到節(jié)點R7，將節(jié)點R5與R4斷開并與結(jié)點R6建立連接。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)改變后，節(jié)點R6與節(jié)點R3和節(jié)點R5的路由均不通過電池供電的路由節(jié)點，這樣就減少了電池供電節(jié)點的數(shù)據(jù)轉(zhuǎn)發(fā)量。

當(dāng)網(wǎng)絡(luò)中有新節(jié)點加入或原有節(jié)點離開時，協(xié)調(diào)器會檢測到網(wǎng)絡(luò)結(jié)構(gòu)的改變，此時啟動路由改進算法重構(gòu)網(wǎng)絡(luò)，使得路由算法能夠動態(tài)適應(yīng)網(wǎng)絡(luò)的變化。恰當(dāng)?shù)馗木W(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可整體降低電池供電節(jié)點的數(shù)據(jù)轉(zhuǎn)發(fā)量。此外，不同路徑上流量的變化也會引起網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的改變。

2.2 算法初始條件計算

ZigBee樹型拓?fù)渲校獙崿F(xiàn)上述算法，路由節(jié)點需要獲取以下信息：（1）節(jié)點轉(zhuǎn)發(fā)的數(shù)據(jù)流量；（2）已知網(wǎng)絡(luò)中數(shù)據(jù)轉(zhuǎn)發(fā)時的路由；（3）路由中包含的電池供電節(jié)點；（4）路由節(jié)點可連接的其他路由節(jié)點信息。由ZigBee樹型網(wǎng)絡(luò)結(jié)構(gòu)的特征可知，一個路由節(jié)點只需要極少的流量就可獲得這些信息[3] [4]。當(dāng)數(shù)據(jù)經(jīng)過某路由節(jié)點轉(zhuǎn)發(fā)時，該路由節(jié)點能夠檢測到數(shù)據(jù)的源節(jié)點和目的結(jié)點，以及該結(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)的比重。獲取節(jié)點設(shè)備的電源類型需要額外的信息，算法中通過搜集每個節(jié)點的信息，協(xié)調(diào)器記錄電池供電節(jié)點的信息，其它節(jié)點訪問協(xié)調(diào)器獲取所需信息。數(shù)據(jù)轉(zhuǎn)發(fā)的路由在樹型網(wǎng)絡(luò)中可由具有路由能力的節(jié)點直接計算獲得。通過（1）式計算網(wǎng)絡(luò)中電池供電路由節(jié)點的總負(fù)載[5]，其中TotalLoad是電池節(jié)點的總負(fù)載，P是路由中電池供電節(jié)點的數(shù)目，n為網(wǎng)絡(luò)中的總路由數(shù)，T是該條路由轉(zhuǎn)發(fā)數(shù)據(jù)量的比重。

（1）

為獲取可連接的鄰居節(jié)點的信息，該文中引入了鄰居表[8]，如果某路由節(jié)點在另一路由節(jié)點的直接通信范圍內(nèi)，則兩節(jié)點互為鄰居節(jié)點，網(wǎng)絡(luò)中只針對FFD節(jié)點儲存鄰居節(jié)點信息，每個FFD節(jié)點通過鄰居列表記錄下該節(jié)點與其他節(jié)點的鄰接關(guān)系。鄰居表中記錄如圖2所示，在鄰居表中ADDR是鄰居節(jié)點地址，DType是鄰居節(jié)點電源類型。

2.3 重構(gòu)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)算法流程

當(dāng)網(wǎng)絡(luò)中有新的節(jié)點加入或有節(jié)點離開時，網(wǎng)絡(luò)重構(gòu)會發(fā)生，用（1）式計算所有可重構(gòu)的新拓?fù)渚W(wǎng)絡(luò)中的電池供電節(jié)點總負(fù)載，若總負(fù)載最小的網(wǎng)絡(luò)結(jié)構(gòu)，也即最好的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，其總負(fù)載小于當(dāng)前網(wǎng)絡(luò)的總負(fù)載時，算法更改網(wǎng)絡(luò)拓?fù)洌駝t維持原有網(wǎng)絡(luò)拓?fù)洹Ｒ粋€路由節(jié)點依據(jù)電池供電節(jié)點的總負(fù)載量來決定其父節(jié)點，需要改變網(wǎng)絡(luò)拓?fù)鋾r，該路由節(jié)點就斷開與原父節(jié)點的連接，并與新的父節(jié)點建立連接，新父節(jié)點的路徑深度要求不大于原父節(jié)點的路徑深度，避免該節(jié)點的子節(jié)點無法獲得足夠的網(wǎng)絡(luò)地址，網(wǎng)絡(luò)重構(gòu)選擇新父節(jié)點的具體算法如下。

（1）初始化網(wǎng)絡(luò)中的電池供電設(shè)備總負(fù)載為load。

（2）依次取得網(wǎng)絡(luò)中具有路由能力的節(jié)點Cn。

（3）依次取得節(jié)點Cn的鄰居節(jié)點An，若無鄰居節(jié)點時轉(zhuǎn)向第（2）步。

（4）如果節(jié)點An的深度小于節(jié)點Cn的網(wǎng)絡(luò)深度，算法繼續(xù)，否則轉(zhuǎn)到第（3）步。

（5）使用（1）式計算當(dāng)節(jié)點Cn連接到父節(jié)點An時網(wǎng)絡(luò)中電池供電節(jié)點的總負(fù)載newload，如果新找到網(wǎng)絡(luò)拓?fù)渲须姵毓╇姽?jié)點的總負(fù)載小于已發(fā)現(xiàn)的網(wǎng)絡(luò)拓?fù)湄?fù)載時，將load值更改為newload，并且記錄節(jié)點An和節(jié)點Cn。

（6）轉(zhuǎn)到第（2），繼續(xù)查找使得網(wǎng)絡(luò)中電池供電節(jié)點的總負(fù)載最小的節(jié)點對An和Cn，直到分析完網(wǎng)絡(luò)中所有具有路由能力的節(jié)點。

（7）將節(jié)點Cn連接到節(jié)點An，父節(jié)點An給節(jié)點Cn分配新地址Rn，選擇父節(jié)點的過程結(jié)束。

由ZigBee樹型網(wǎng)絡(luò)的地址分配機制可知，當(dāng)路由節(jié)點的父節(jié)點改變后，該節(jié)點的地址及其所有子節(jié)點的地址都需要重新分配。重構(gòu)網(wǎng)絡(luò)時，改變父節(jié)點的重構(gòu)子樹的根節(jié)點將原有地址和新分配的地址發(fā)送給各后代節(jié)點，每個后代節(jié)點利用該信息計算其父節(jié)點、子節(jié)點或自身的地址。重構(gòu)子樹的節(jié)點更改地址后，按ZigBee網(wǎng)絡(luò)中獨立節(jié)點方式加入網(wǎng)絡(luò)拓?fù)渲小Ｍㄟ^以下算法可修改網(wǎng)絡(luò)結(jié)構(gòu)改變后重構(gòu)子樹中節(jié)點的地址，具體流程如下。

（1）初始化函數(shù)參數(shù)，R是子樹根節(jié)點原地址，R是子樹根節(jié)點新地址，D是后代節(jié)點原地址，函數(shù)返回結(jié)果是后代節(jié)點新地址Dn

（2）若節(jié)點D是子樹根節(jié)點R的后代節(jié)點

（3）將D賦值為R，A賦值為R。

（4）遞歸查找地址A，使其指向節(jié)點D

（5）遞歸計算節(jié)點D在新網(wǎng)絡(luò)拓?fù)渲械刂?/p>

更改設(shè)備地址算法的偽代碼如下：

UpdateAddress（R，R，D）

{if（ R< D&& D< （R+ C（depth-1）））

{D=R；A=R；

While（A！= D）

{skip=C（depth）；skip=C（depth）；

index=

A=A+1+index*skip

D=D+1+index*skip }}}

return Dn

網(wǎng)絡(luò)中節(jié)點的地址改變后，網(wǎng)絡(luò)中其余的節(jié)點應(yīng)該獲取改變地址節(jié)點的信息，以便能夠正確的發(fā)送數(shù)據(jù)包。同時修改協(xié)調(diào)器中存儲的節(jié)點信息，使修改后的節(jié)點地址與電源類型一致，以便能夠正確的計算網(wǎng)絡(luò)中電池供電節(jié)點的總負(fù)載。當(dāng)某個網(wǎng)絡(luò)拓?fù)渲袛?shù)據(jù)流量穩(wěn)定時，網(wǎng)絡(luò)重構(gòu)會生成一個新的穩(wěn)定的網(wǎng)絡(luò)拓?fù)洌碌木W(wǎng)絡(luò)拓?fù)渲袝M可能避免使用電池供電節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)，當(dāng)發(fā)現(xiàn)網(wǎng)絡(luò)中電池供電節(jié)點的總負(fù)載減少時，即有更好的網(wǎng)絡(luò)拓?fù)鋾r，網(wǎng)絡(luò)繼續(xù)進行重構(gòu)。因為路由節(jié)點會不斷地檢測轉(zhuǎn)發(fā)的數(shù)據(jù)包，并且做相應(yīng)的記錄，因此該算法也能處理網(wǎng)絡(luò)流量動態(tài)改變的情況，當(dāng)網(wǎng)絡(luò)中總流量或部分路由中的流量發(fā)生變化時，新的網(wǎng)絡(luò)拓?fù)渲貥?gòu)會進行以適應(yīng)新的網(wǎng)絡(luò)流量狀態(tài)。

3 仿真結(jié)果分析

算法仿真分別在使用了PSAR算法和未使用PSAR算法兩種情況下進行。仿真中所有變量保持不變，改變以下變量來測量算法的運行效果。這些變量是電池供電節(jié)點的數(shù)據(jù)轉(zhuǎn)發(fā)總量，網(wǎng)絡(luò)規(guī)模和電池供電節(jié)點占網(wǎng)絡(luò)總節(jié)點數(shù)的比例。表示算法效率的變量是網(wǎng)絡(luò)中電池供電節(jié)點總負(fù)載的耗能減少百分率（Reduction），定義見（2）式。

（2）

改進算法通過仿真實驗和傳統(tǒng)樹路由算法進行了比較，主要比較優(yōu)化前后兩種網(wǎng)絡(luò)拓?fù)渲须姵毓╇姽?jié)點轉(zhuǎn)發(fā)數(shù)據(jù)的總負(fù)載。仿真結(jié)果證明了使用改進算法重構(gòu)的網(wǎng)絡(luò)中能使電池供電節(jié)點的總負(fù)載平均減少50%以上，證明了改進算法的有效性。

仿真工具采用Omnet++，網(wǎng)絡(luò)覆蓋面積為400×400，網(wǎng)絡(luò)中路由節(jié)點數(shù)分別為40和100個，網(wǎng)絡(luò)中的節(jié)點都是具有路由能力的FFD節(jié)點，網(wǎng)絡(luò)協(xié)調(diào)器參數(shù)初始化Cm =5，Rm=5，Lm=5，網(wǎng)絡(luò)中電池供電節(jié)點比例的值依次是10，30，…，90%。仿真實驗結(jié)果如圖3和圖4所示。

圖3記錄了仿真網(wǎng)絡(luò)中分別為40和100時，網(wǎng)絡(luò)中電池供電節(jié)點的總負(fù)載隨電池供電節(jié)點占網(wǎng)絡(luò)節(jié)點比例的變化。分析可知，當(dāng)采用改進后的PARA算法，可使電池供電節(jié)點的總負(fù)載較原網(wǎng)絡(luò)拓?fù)淦骄鶞p少近50%，同時網(wǎng)絡(luò)中隨著電池供電節(jié)點比例以及節(jié)點密度的增大，PARA算法對網(wǎng)絡(luò)拓?fù)渲貥?gòu)后電池供電節(jié)點總負(fù)載的影響也相應(yīng)減小。說明該算法更適用于電源供電節(jié)點占一定比例的網(wǎng)絡(luò)。

實驗結(jié)果同時分析了PARA算法的網(wǎng)絡(luò)路由代價，即控制信息數(shù)據(jù)量占實際數(shù)據(jù)量的比重。算法費用主要來自記錄或詢問設(shè)備的電源類型，請求潛在父節(jié)點的連接，重構(gòu)子樹節(jié)點的地址更改，網(wǎng)絡(luò)重構(gòu)后通知其它節(jié)點重構(gòu)子樹節(jié)點的新地址。由圖4 可知，控制信息的數(shù)據(jù)量比率低于0.6%，算法對網(wǎng)絡(luò)流量的影響小，算法的穩(wěn)定性較好。網(wǎng)絡(luò)規(guī)模在40和100時，控制報文的比率相差不大，說明網(wǎng)絡(luò)規(guī)模對該比率并無顯著的影響，這是因為當(dāng)網(wǎng)絡(luò)規(guī)模增大時，控制信息的數(shù)據(jù)量與網(wǎng)絡(luò)的總數(shù)據(jù)量在同比增加。

4 結(jié)語

該文在深入研究了ZigBee網(wǎng)絡(luò)的組網(wǎng)技術(shù)及其路由算法的基礎(chǔ)上，結(jié)合電源供電設(shè)備和電池供電設(shè)備的特點，提出了一種基于ZigBee樹型網(wǎng)絡(luò)的電源感知路由算法（PARA），并分析了改進算法的性能。由仿真評估可知PARA算法比樹路由算法（DAAM）有效的減少了網(wǎng)絡(luò)中電池供電節(jié)點的數(shù)據(jù)轉(zhuǎn)發(fā)量，算法只需少量的通訊開銷就可以明顯地減少電池供電路由節(jié)點的耗能，延長了網(wǎng)絡(luò)的生存時間。但該算法僅適應(yīng)于持續(xù)電源節(jié)點占一定比例的網(wǎng)絡(luò)，且網(wǎng)絡(luò)中需含有完全由持續(xù)電源節(jié)點組成的路徑，該算法研究為特定應(yīng)用環(huán)境中網(wǎng)絡(luò)節(jié)點的布置提供了理論基礎(chǔ)。

參考文獻

[1] IEEE Std.802.15.4，Wireless Medium Access Control（MAC） and Physical Layer（PHY）Specification for Low-Rate Wireless Personal Area network， October 1，2003.

[2] ZigBee Standards Organization.（2006）.ZigBee specification.

[3] Shah，p.，Shaikh，T.，Ghan，l，Shilaskar，S.Power mana- gement using ZigBee wireless sencor network.Emerging trends in engineering and technology，2008.First International Conference on2008：242-245.

[4] Egan，D.The emergence of ZigBee in building automation and industrial control[J].Computering and Control Engineering Journal，2005，16（2），14-19.

[5] Chen，M.Yang，L.T.Kwon，T. Zhou，L.&Jo，M.Itinerary planning for energy efficient agent communications in wireless sensor networks[J].Vehicular Technology，IEEE Transactions on，2011，60（7）：3290-3299.

[6] I.Hwang，J.Baek.Wireless Access Monitoring and Control System based on Digital Door Lock，IEEE Trans[J].Consumer Electron，2007，53（4）.

[7] 薛艷亮，胡建萍，王江柱.基于分布式編址機制的ZigBee組網(wǎng)技術(shù)研究[J].杭州電子科技大學(xué)學(xué)報，2008，28（2）：33-36.

[8] 戚劍超，魏臻.ZigBee樹型路由算法的改進[J].合肥工業(yè)大學(xué)學(xué)報，2010，33（4）：529-532.