基于權(quán)重和均衡能量的ZigBee改進路由算法

狄萬昕,江 明

(安徽工程大學(xué)電氣工程學(xué)院,安徽蕪湖 241000)

?

基于權(quán)重和均衡能量的ZigBee改進路由算法

狄萬昕,江 明?

(安徽工程大學(xué)電氣工程學(xué)院,安徽蕪湖 241000)

摘要:針對ZigBee路由協(xié)議中存在路由不穩(wěn)定、時延大以及能量不平衡等問題,提出了一種基于權(quán)重和均衡能量的ZigBee改進路由算法(ZigBee-new)．在滿足權(quán)重的路徑查找中優(yōu)先挑選能量高的節(jié)點充當(dāng)中繼,而低能量的節(jié)點反饋能量狀態(tài),由源端主動斷開舊鏈路,進而轉(zhuǎn)變路徑．采用NS2平臺對ZigBee和ZigBee-new進行了仿真實驗和性能分析,仿真實驗結(jié)果表明,改進后的ZigBee-new路由算法比較明顯地改進了原ZigBee路由算法的性能．

關(guān) 鍵 詞:ZigBee路由協(xié)議;移動自組織網(wǎng)絡(luò);權(quán)重;均衡能量

無線網(wǎng)絡(luò)(Wireless Sensor Network)[1-3]是一種不需要基礎(chǔ)設(shè)施的自組織和自管理網(wǎng)絡(luò),網(wǎng)絡(luò)中所有節(jié)點同時具有終端和路由器的功能,節(jié)點可通過路由發(fā)現(xiàn)機制轉(zhuǎn)發(fā)分組,并進行路由維護．隨機部署的節(jié)點可能由于自然因素損壞或者被人為干擾,需要補充能量,但是網(wǎng)絡(luò)中的節(jié)點通常由電池供電,使得能量不便再次添加,因此,設(shè)計一個好的路由協(xié)議要考慮維護網(wǎng)絡(luò)的穩(wěn)健性和網(wǎng)絡(luò)中能量損壞的均衡性．

為了滿足ZigBee[4-8]網(wǎng)絡(luò)低功耗、高可靠性、低成本的設(shè)計目標(biāo),在ZigBee網(wǎng)絡(luò)按節(jié)點身份的不同,采用了兩種路由協(xié)議:按需距離矢量路由(AODV-jr,Ad-hoc On Demand Distance vector Routing)和按照父子關(guān)系選擇路徑方式的Cluster-Tree路由算法．使用Cluster-Tree路由算法帶來了大的數(shù)據(jù)傳輸延時和分組遞交率的降低．使用AODv-jr路由算法時,網(wǎng)絡(luò)中的數(shù)據(jù)傳輸時延降低,分組遞交率得到提高,但是過多的路由發(fā)現(xiàn)可能造成更多的能量消耗．

現(xiàn)有研究表明[9-12],傳統(tǒng)的ZigBee路由協(xié)議對延遲、帶寬、丟包率和能量等都沒有加以約束,即都沒有考慮到QOS因素的限制,如時延、帶寬、能量的差異等問題．這會造成網(wǎng)絡(luò)的節(jié)點擁塞、時延大等缺點,某些節(jié)點的能量被很快地消耗,縮短了網(wǎng)絡(luò)的生存周期．為此,在ZigBee路由協(xié)議的基礎(chǔ)上,提出了基于權(quán)重和均衡能量的ZigBee改進路由算法ZigBee-new．通過引入一些QOS參數(shù)的約束,以更符合在實際網(wǎng)絡(luò)中對服務(wù)質(zhì)量的進一步要求．

1 ZigBee-new的算法

1．1 基于權(quán)重的策略

在WSN場景下,為了準(zhǔn)確討論QOS問題,把WSN網(wǎng)絡(luò)看做一個加權(quán)圖G(V,E)．其中,V可以表示為Ad hoc移動節(jié)點的集合;E可代表Ad hoc移動節(jié)點間形成的鏈路的集合;且每一個Ad hoc節(jié)點的傳輸半徑一樣．假使在已知的源節(jié)點與目的節(jié)點之間存在路徑K(s→i→…→j→d),該路由滿足跳數(shù)、能量以及鏈路質(zhì)量這3個QOS約束條件．則該WSN路由協(xié)議可以抽象為在加權(quán)圖G(V,E)中,在已知的源節(jié)點與目的節(jié)點之間尋找滿足QOS約束要求的可行路由,然后通過計算各條可行路由的路由權(quán)重值Weight,再選取Weight值最大的可行路由進行數(shù)據(jù)傳輸．權(quán)重大的節(jié)點獲得轉(zhuǎn)發(fā)路徑的優(yōu)先級高,更容易被選中成為網(wǎng)絡(luò)中的中繼節(jié)點．

1．2 基于鏈路質(zhì)量反饋的策略

在路徑維護的過程中同時預(yù)測鏈路的生存狀態(tài)．傳統(tǒng)ZigBee路由協(xié)議AODV-JR建立路由是參照最小跳數(shù)作為度量參數(shù)的,忽略了路由上鏈路的傳輸質(zhì)量,造成路由整體性能較差．鏈路質(zhì)量的好壞取決于節(jié)點繁忙程度,其表示了節(jié)點無線信號使用的連續(xù)程度,根據(jù)無線信道的特性,信道越繁忙則傳輸質(zhì)量越差．該參數(shù)可以通過統(tǒng)計路徑上所有節(jié)點的空閑時間Tidk與工作時間Tbusy比得到,即:

1．3 基于均衡能量的策略

當(dāng)能量低于某一設(shè)定值或者發(fā)生鏈路斷開的情況時,標(biāo)記鏈路的狀態(tài),置flag為0．在數(shù)據(jù)包攜帶節(jié)點的能量信息進行傳播的過程中,當(dāng)節(jié)點的能量低于閥值時,認(rèn)為節(jié)點的能量將消耗完,該節(jié)點攜帶低能量的信息被其他節(jié)點接收并最終轉(zhuǎn)發(fā)至數(shù)據(jù)包的源節(jié)點．當(dāng)源節(jié)點接收此數(shù)據(jù)包時,從路由表中剔除低能量節(jié)點的鏈路,再重新發(fā)起路徑請求,尋找更優(yōu)的路徑充當(dāng)中繼．能量閥值的反饋效果對網(wǎng)絡(luò)的鏈路狀態(tài)起到了警示作用,從而讓源節(jié)點主動變更路徑．利用節(jié)點的能量特性引入一個參數(shù)ETsd(能量的閥值Threshold),系數(shù)K為一個和時間成正比的函數(shù),即:

2 基于權(quán)重和均衡能量的ZigBee改進路由算法

2．1 數(shù)學(xué)模型

節(jié)點距離協(xié)調(diào)器的跳數(shù)越多,鏈路代價就越大,因此,在鏈路的選擇過程中,跳數(shù)越少越好．將一跳的權(quán)重設(shè)為β,即路徑上每多1個節(jié)點其在跳數(shù)上的權(quán)重就大．節(jié)點剩余能量過低說明信道質(zhì)量太差,這種鏈路在網(wǎng)絡(luò)中十分不穩(wěn)定,因此,在選路過程中要避免通過該類鏈路通信．僅當(dāng)節(jié)點剩余能量達到一定閾值時,鏈路信道質(zhì)量相對較好,鏈路代價較小,可以作為通信鏈路．為了對節(jié)點碰撞、負載情況進行很好地描述,基于網(wǎng)絡(luò)測量技術(shù)得到最近60 s內(nèi)的忙與空閑時間之比Tidk/Tbusy,該值越高表明節(jié)點越繁忙．

(1)算法的參數(shù)模型．為了方便研究,把Ad Hoc網(wǎng)絡(luò)定義為圖G＝(V,E,t),其中,V為節(jié)點;E為邊; t為邊的權(quán)值,表示鏈路的剩余時間,即一條邊還能保持通路的時間值．

(2)路由權(quán)重函數(shù)．為了選擇出最佳路由,需要構(gòu)建一個路由權(quán)重函數(shù),t(i,j)代表節(jié)點i與j之間鏈路的剩余時間值．該函數(shù)的表示形式為:節(jié)點剩余能量Ei、跳數(shù)H、節(jié)點繁忙程度B,3個因素結(jié)合形成路由代價Cti．路由度量計算如下,定義在t時刻,鏈路通過節(jié)點i的代價為:

式中,Ei表示當(dāng)前時刻節(jié)點i的剩余能量,可從節(jié)點中直接獲取;E為節(jié)點初始能量;Hi為跳數(shù);β是加權(quán)因子0≤β≤1．

考慮鏈路質(zhì)量,則t時刻路徑代價為:

式中,Bti為t時刻節(jié)點所處物理信道的評價繁忙程度,Bti＝Tidk/Tbusy．

最后選擇的路由為F＝min{Dj|j∈Q}的路徑,其中Q為可選路由集．

試驗中β的值為0．6,取值為試驗測試選擇的經(jīng)驗值．

從表示形式可看出,此路由權(quán)重函數(shù)由兩部分組成．跳數(shù)和能量之所以將跳數(shù)也作為代價函數(shù)的參數(shù)之一,是因為如果只將能量作為函數(shù)的考慮因素,雖然可以起到延長網(wǎng)絡(luò)生存時間的作用,但網(wǎng)絡(luò)的其他一些性能將會惡化很多．路由的跳數(shù)對節(jié)省節(jié)點能量也起一些作用,數(shù)據(jù)傳輸時所用路由的跳數(shù)越少,路由就越穩(wěn)定,越不容易發(fā)生路由斷裂的情況,從而有效地避免數(shù)據(jù)重傳以及再次發(fā)起路由發(fā)現(xiàn)過程,這對于節(jié)點移動性較強無線網(wǎng)絡(luò)作用尤為明顯．

(3)加權(quán)因子．加權(quán)因子β決定了跳數(shù)和能量這兩個參數(shù)在路由權(quán)重函數(shù)中的比重．CM MBCR協(xié)議根據(jù)網(wǎng)絡(luò)中節(jié)點剩余能量的不同情況采取不同的路由選擇策略．借鑒這一思想,加權(quán)因子的值將根據(jù)路由候選集中各條路由組成節(jié)點的剩余能量情況來確定．

假設(shè)網(wǎng)絡(luò)中所有節(jié)點的初始能量值相同,則有:

式中,vn、l表示路由rn中的節(jié)點;p(vn,l)表示節(jié)點vn、l的剩余能量;Po表示節(jié)點的初始能量．

可以看出,當(dāng)各條路由中節(jié)點的能量狀況較好時,β值較大,此時跳數(shù)在路由權(quán)重函數(shù)中所占的比重較大．該算法傾向于選擇跳數(shù)較少的路由(反之,當(dāng)能量狀況較差時,β值較小),此時能量參數(shù)所占的比重較大．該算法傾向于選擇有效生存期較長的路由,從而起到保護剩余能量較低的瓶頸節(jié)點,盡可能延長網(wǎng)絡(luò)生存時間的目的．

2．2 路由算法的描述

該算法的前提是基于網(wǎng)絡(luò)中所有鏈路均為雙向,且節(jié)點可以隨時提供剩余能量的假設(shè)．

假設(shè)S為源節(jié)點,D為目的節(jié)點．一次數(shù)據(jù)傳輸過程的主要步驟如下:

(1)利用ZBR路由機制進行路由發(fā)現(xiàn),但在報文中需添加節(jié)點最小剩余能量域re、鏈路最小剩余時間域rt與節(jié)點剩余能量和域sum;

(2)D開啟一個定時器,保存該時間內(nèi)收到的所有RREQ報文中的路由;

(3)D根據(jù)路由信息計算出每條路由的路由權(quán)值Di,選出具有最大權(quán)值的路由F;

(4)D沿反向路由發(fā)送RREQ報文到S,進行數(shù)據(jù)傳輸;

輸入:節(jié)點集合和權(quán)重參數(shù)Di

輸出:優(yōu)化的邏輯樹

1 for i←1 to n do//n為要加入的網(wǎng)絡(luò)節(jié)點數(shù)

2 Di＝0;//Di位節(jié)點i到達協(xié)調(diào)器的總代價

3 m＝Scan AvailableNetwork();//搜索可加入的網(wǎng)絡(luò)數(shù)目m

4 if m＝＝0 do//如果節(jié)點i周圍無可加入的節(jié)點

5 Node[i]．Sleep(100);//則讓節(jié)點休眠100 ms

6 Continue;//循環(huán)跳入下一個待加入節(jié)點繼續(xù)進行

7 for j←1 to m do

8 if Ei＞ETsd do//節(jié)點剩余能量大于節(jié)點的能量閥值

9 cij＝0

10 for enery node k in Path[j]do

11 cij＝cij＋Dk

12 k加入到TempPath[j]鏈表中;

13 end for

14 else do

15 cij＝∞

16 end for

17 選擇使得cij最小的可接入節(jié)點j作為父節(jié)點加入,并使Di＝cij

18 將節(jié)點i連接到父節(jié)點j上構(gòu)成邏輯樹;

19 Path[i]＝TempPath[j];

20 end for

2．3 仿真工具和仿真參數(shù)的設(shè)置

目前無線自組網(wǎng)的路由協(xié)議仿真國內(nèi)外大部分科研院校都采用NS2．移植算法在NS2框架下,配置的場景如下:CBR為業(yè)務(wù)源的通信場景文件的數(shù)據(jù)流包括一個50個移動節(jié)點、10對通信連接和每秒鐘發(fā)送2個的分組．移動場景設(shè)置為一個具有50個節(jié)點、節(jié)點在每個地點停留0秒(即不停留)、最大移動速度20 m/s、仿真時間300 s、長1 000 m和寬300 m的移動場景文件．其中暫停的時間可變,用于比較ZigBee路由協(xié)議改進前向的參數(shù)性能．仿真參數(shù)列表如表1所示．

在實驗過程中,選用setdest工具設(shè)定節(jié)點傳輸場景文件和cbrgen工具生成傳輸負載,使用awk工具來說明tcl腳本生成的trace文件,最后使用Matlab工具繪圖．

表1 仿真參數(shù)列表

2．4 仿真結(jié)果與分析

ZigBee和ZigBee-new分組投遞率對比如圖1所示．由圖1可知,當(dāng)暫停時間越長表明節(jié)點移動性越慢,當(dāng)節(jié)點的移動暫停時間為300 s,而仿真的總時間為300 s,表明節(jié)點不移動,此時分組投遞率的成功率越高．當(dāng)節(jié)點的移動暫停時間為0 s時,節(jié)點一直在移動,此時分組投遞率的成功率較低,丟包率比較明顯．ZigBee-new由于考慮基于鏈路質(zhì)量的反饋作用,避開了繁忙節(jié)點,相對于原ZigBee算法選出的路徑更加穩(wěn)定,表現(xiàn)為接收的分組投遞率高．

ZigBee和ZigBee-new平均延時對比如2所示．由圖2可知,暫停時間越長表明節(jié)點移動性越慢、路由越穩(wěn)定,端到端的平均延時越?。甖igBee-new考慮到刪除帶寬較小、延時較大、跳數(shù)較大的路徑,剔除了一些不滿足最佳QOS的次要路徑,實現(xiàn)選出路徑為優(yōu)化后的結(jié)果,表現(xiàn)為ZigBee-new端到端的延時更短．

圖1 ZigBee和ZigBee-new分組投遞率對比

圖2 ZigBee和ZigBee-new平均延時對比

ZigBee和ZigBee-new不同節(jié)點剩余能量對比如圖3所示．由圖3可知,ZigBee-new算法選擇的路徑更加穩(wěn)定,用于路由發(fā)起的控制包減少,網(wǎng)絡(luò)中的能量避免了因偵聽到過多的控制廣播而產(chǎn)生大量能量消耗．使得ZigBee-new相比ZigBee,網(wǎng)絡(luò)中節(jié)點剩余能量得到更好地節(jié)省,進一步延長了網(wǎng)絡(luò)的生存時間．

ZigBee和ZigBee-new網(wǎng)絡(luò)抖動性比較如圖4所示．由圖4可知,ZigBee-new由于考慮到網(wǎng)絡(luò)中節(jié)點的能量以及鏈路的質(zhì)量通信情況,相比ZigBee進行了預(yù)警信息,并且主動變更了即將斷開的鏈路與通信質(zhì)量不佳的鏈路,因此路徑變更的概率減小,表現(xiàn)為ZigBee-new算法網(wǎng)絡(luò)穩(wěn)定,抖動幅度?。?/p>

圖3 ZigBee和ZigBee-new不同節(jié)點剩余能量對比

圖4 ZigBee和ZigBee-new網(wǎng)絡(luò)抖動性比較

3 結(jié)論

ZigBee是為WSN網(wǎng)絡(luò)設(shè)計的路由協(xié)議,但是沒有QOS保障,當(dāng)節(jié)點存在能量差異時,容易選中能量低的節(jié)點充當(dāng)中繼,從而縮短網(wǎng)絡(luò)的生存時間,且低能量節(jié)點能量將耗盡時,也無法感知網(wǎng)絡(luò)的鏈路即將變更信息．提出了一種ZigBee-new路由算法,該算法在查找路徑正向發(fā)送路由請求的過程中,選擇鏈路質(zhì)量、跳數(shù)、能量3個方面的因素,滿足時延和帶寬要求,并且剩余能量大的節(jié)點充當(dāng)中繼節(jié)點的權(quán)重高、延時低,從而獲得比較高的優(yōu)先級．在數(shù)據(jù)包發(fā)送的過程中,低能量的節(jié)點反饋能量狀態(tài),并且剩余能量大,獲取鏈路質(zhì)量好的反向路徑．當(dāng)能量較低或者通信質(zhì)量較差時,主動報告源端,源端主動斷開舊鏈路,變更新路徑．仿真結(jié)果表明,改進后的ZigBee-new算法有效地改進了ZigBee路由不穩(wěn)定、時延大和能量不平衡等缺點,有效地提升了ZigBee的性能．

參考文獻:

[1] 柯志亨,程榮祥,鄧德雋．NS2仿真實驗-多媒體和無線網(wǎng)絡(luò)通信[M]．北京:電子工業(yè)出版社,2009．

[2] 孫利民,李建中．無線傳感器網(wǎng)絡(luò)[M]．北京:清華大學(xué)出版社,2010．

[3] 高蔚藍．ZigBee:新一代無線網(wǎng)絡(luò)的綜述[M]．北京:中國學(xué)術(shù)期刊電子出版社,2010．

[4] 胡柯,郭壯輝,汪鐳．無線通信技術(shù)ZigBee研究[J]．電腦知識與技術(shù),2008(6):1 049-1 051．

[5] 徐小濤,孫少蘭,胡東華,等．ZigBee協(xié)議的最新發(fā)展[M]．北京:中國學(xué)術(shù)期刊電子出版社,2009．

[6] 耿萌,于宏毅,張效義．ZigBee路由協(xié)議分析與性能評估[J]．計算機工程與應(yīng)用,2007(43):116-120．

[7] 張棟．ZigBee無線傳感器網(wǎng)絡(luò)路由協(xié)議研究與優(yōu)化[D]．濟南:山東大學(xué),2009．

[8] 李文仲,段朝玉．ZigBee無線網(wǎng)絡(luò)技術(shù)入門與實戰(zhàn)[M]．北京:北京航空航天大學(xué)出版社,2007．

[9] 徐沛成,胡國榮．改進的ZigBee網(wǎng)絡(luò)路由算法[J]．計算機工程與設(shè)計,2013,34(9):3 019-3 023．

[10]徐艷,王茜,武劍．ZigBee路由協(xié)議優(yōu)化仿真研究[J]．計算機仿真,2013,30(60):292-295．

[11]K K Lee,S H Kim,H S Park．Cluster label-based ZigBee routing protocol with high scalability[C]//The Second International Conference on Systems and Networks Communicatio(ICSNC 2007),Cap Esterel:Editions Masson,2007,240:12-16．

[12]A Bhatia,P Kaushik．A cluster based minimum battery cost AODV routing using multipath route for ZigBee[C]//Proceedings of the 2008 16 International Conference on Networks(ICON 2008),New Delhi:Eastem Book Linkers,2008:1-7．

An improved ZigBee routing algorithm based on weight and equilibrium energy

DI Wan-xin,JIANG Ming?
(College of Electrical Engineering,Anhui Polytechnic University,Wuhu 241000,China)

Abstract:Unstable routing,long delay and unbalanced energy existed in ZigBee routing algorithm．Aiming at these shortages,based on weight and equilibrium energy,an improved routing algorithm is proposed．Nodes with higher energy are selected to act as a repeater in the path of meeting the weight and nodes with lower energy are used to feed back energy state in the process of data packets transmission．The source disconnects actively with the old link,thus changing the path．The NS2 platform is used to conduct a simulation experiment and performance analysis between ZigBee-new and ZigBee．The simulation results show that the improved ZigBee-new algorithm promotes the performance obviously．

Key words:ZigBee routing protocol;ad hoc network;weight;equilibrium energy

中圖分類號:TP393

文獻標(biāo)識碼:A

收稿日期:2015-10-27

基金項目:國家自然科學(xué)基金資助項目(6121377)

作者簡介:狄萬昕(1990-),男,江蘇南京人,碩士研究生．

通訊作者:江 明(1965-),男,安徽蕪湖人,教授,碩導(dǎo)．