舒紅
(重慶郵電大學(xué) 重慶市移動通信重點實驗室,重慶 400065)
ZigBee網(wǎng)絡(luò)自剪裁路由算法
舒紅
(重慶郵電大學(xué) 重慶市移動通信重點實驗室,重慶 400065)
ZigBee網(wǎng)絡(luò)中的AODVjr算法通過全網(wǎng)廣播路由請求RREQ消息而獲得分組發(fā)送的最短路徑,但節(jié)點大量廣播RREQ消息增加了網(wǎng)絡(luò)控制開銷,導(dǎo)致網(wǎng)絡(luò)節(jié)點耗能劇增,同時網(wǎng)絡(luò)堵塞的可能性也大大提升。針對AODVjr算法存在的網(wǎng)絡(luò)節(jié)點耗能劇增問題,在AODVjr算法基礎(chǔ)上,結(jié)合節(jié)點鄰居表,提出篩選RREQ消息轉(zhuǎn)發(fā)節(jié)點,從而限制RREQ消息轉(zhuǎn)發(fā)次數(shù)的路由算法ZigBee樹節(jié)點自剪裁轉(zhuǎn)發(fā)算法(ZigBee On-tree Self-pruning Rebroadcast Algorithm,ZOSR)和ZigBee轉(zhuǎn)發(fā)節(jié)點選擇算法(ZigBee On-tree Forwarding Node Selection Algorithm,ZOFNS)。仿真結(jié)果表明,算法能有效降低網(wǎng)絡(luò)節(jié)點的轉(zhuǎn)發(fā)次數(shù),從而降低網(wǎng)絡(luò)整體功耗,延長網(wǎng)絡(luò)工作時間。
ZigBee;自剪裁;AODVjr;RREQ;路由
ZigBee網(wǎng)絡(luò)是近幾年出現(xiàn)的一種新興網(wǎng)絡(luò)技術(shù),因其低功耗、低成本、低復(fù)雜度、短時延、大網(wǎng)絡(luò)容量及高節(jié)點集成度等特點,被廣泛應(yīng)用于短距離低速率的數(shù)據(jù)傳輸場景中。然而由于ZigBee網(wǎng)絡(luò)中節(jié)點的能量資源有限,故ZigBee網(wǎng)絡(luò)路由算法必須以能量有效性為首要的設(shè)計要素。經(jīng)典AODVjr算法通過全網(wǎng)廣播RREQ消息而獲得發(fā)送數(shù)據(jù)的最短路徑,節(jié)點因大量廣播RREQ消息,而耗能迅速,同時網(wǎng)絡(luò)堵塞的可能性也大大增加[1]。
如何優(yōu)化ZigBee路由算法、降低網(wǎng)絡(luò)能量消耗一直是各國學(xué)者研究關(guān)注的熱點[2-5]。文獻(xiàn)[2]提出通過控制RREQ消息洪泛范圍,以降低網(wǎng)絡(luò)整體功耗。文獻(xiàn)[3]提出利用分層拓?fù)湫畔頊p少AODVjr算法中的路由開銷,該算法為了平衡網(wǎng)絡(luò)能耗,將節(jié)點剩余能量作為路由度量。文獻(xiàn)[4]提出定向轉(zhuǎn)發(fā)RREQ消息,該算法能有效減少冗余RREQ消息的轉(zhuǎn)發(fā),從而減少節(jié)點功耗。文獻(xiàn)[5]提出Mesh拓?fù)浠旌下酚蓛?yōu)化算法,該算法在鄰居表基礎(chǔ)上,控制RREQ消息的轉(zhuǎn)發(fā)范圍和轉(zhuǎn)發(fā)方向,并在選擇路徑時避開剩余能量較少的節(jié)點。上述算法在一定程度上限制RREQ消息的轉(zhuǎn)發(fā)次數(shù),降低了網(wǎng)絡(luò)能量消耗,但都以節(jié)點已知其他節(jié)點位置信息為前提,而這在實際中很難實現(xiàn)。
針對ZigBee網(wǎng)絡(luò)路由算法存在問題,在AODVjr算法基礎(chǔ)上,結(jié)合節(jié)點鄰居表,提出通過篩選RREQ消息的轉(zhuǎn)發(fā)節(jié)點,能有效減少RREQ消息的轉(zhuǎn)發(fā)次數(shù),從而有效降低網(wǎng)絡(luò)整體功耗的路由算法。
1.1 地址分配方式
ZigBee網(wǎng)絡(luò)節(jié)點類型分為協(xié)調(diào)器節(jié)點(ZigBee Coordinator,ZC)、路由器節(jié)點(ZigBee Router,ZR)和終端節(jié)點(ZigBee End Device,ZED)3種。每一個無線個域網(wǎng)(WPAN)中僅僅包含一個ZC節(jié)點,它負(fù)責(zé)初始化網(wǎng)絡(luò)和管理網(wǎng)絡(luò)結(jié)構(gòu)[6]。
ZigBee網(wǎng)絡(luò)有2種地址分配方式,即分布式地址分配機(jī)制(Distributed Address Assignment Mechanism,DAAM)和隨機(jī)地址分配機(jī)制(Stochastic Address Assignment Mechanism,SAAM)[7]。樹型網(wǎng)絡(luò)拓?fù)渲泄?jié)點默認(rèn)采用DAAM獲得唯一的16 bit網(wǎng)絡(luò)地址。ZC節(jié)點首先進(jìn)行參數(shù)設(shè)置:Cm是網(wǎng)絡(luò)中任一父節(jié)點最大子節(jié)點數(shù)目;Lm是網(wǎng)絡(luò)最大深度; Rm是網(wǎng)絡(luò)中任一父節(jié)點最大路由子節(jié)點數(shù)目。則網(wǎng)絡(luò)深度為d的父節(jié)點為其子節(jié)點分配網(wǎng)絡(luò)地址時,通過式(1)計算地址偏移量Cskip(d)[8]。網(wǎng)絡(luò)中,只有Cskip(d)>0的節(jié)點才具有為其子節(jié)點分配網(wǎng)絡(luò)地址,供其加入網(wǎng)絡(luò)的能力。
ZigBee網(wǎng)絡(luò)組網(wǎng)時,優(yōu)先讓ZR節(jié)點加入網(wǎng)絡(luò),這樣能減少ZR節(jié)點向周圍節(jié)點廣播拓?fù)渥兓a(chǎn)生的廣播開銷。具體的地址分配機(jī)制[9]如下:
①ZC節(jié)點先將自身的網(wǎng)絡(luò)地址和網(wǎng)絡(luò)深度分別設(shè)置為0;
②對于網(wǎng)絡(luò)深度為d,網(wǎng)絡(luò)地址為A的父節(jié)點,其第n個ZC子節(jié)點對應(yīng)的網(wǎng)絡(luò)地址如式(2)所示;
③其第m個ZED子節(jié)點對應(yīng)的網(wǎng)絡(luò)地址如式(3)所示:
由上可知,ZigBee網(wǎng)絡(luò)中任意節(jié)點可根據(jù)DAAM計算得到自身樹鄰居節(jié)點(即父節(jié)點和子節(jié)點)的地址。
1.2 AODVjr路由算法
ZigBee網(wǎng)絡(luò)中基于路由請求的路由算法AODVjr是在AODV算法基礎(chǔ)上做出的改進(jìn)[10]。AODVjr算法中一旦節(jié)點有路由需求,節(jié)點則會以洪泛方式向鄰居節(jié)點廣播RREQ消息,中間節(jié)點會向鄰居節(jié)點轉(zhuǎn)發(fā)接收到的RREQ消息。目的節(jié)點一旦接收到RREQ消息,將沿RREQ消息的反向轉(zhuǎn)發(fā)路徑發(fā)送路由回復(fù)(Route Reply,RREP)消息,直到源節(jié)點接收到RREP消息后,路由建立完成。通過AODVjr算法可以得到源節(jié)點與目的節(jié)點之間的最短路徑,但此算法在尋路過程中需轉(zhuǎn)發(fā)大量RREQ消息,這就增加了全網(wǎng)的路由控制開銷,導(dǎo)致網(wǎng)絡(luò)節(jié)點因大量轉(zhuǎn)發(fā)RREQ消息而能量消耗過快,造成網(wǎng)絡(luò)分割。所以,如何降低AODVjr算法中RREQ消息的轉(zhuǎn)發(fā)次數(shù),從而降低網(wǎng)絡(luò)控制開銷和節(jié)點能量消耗一直是各國學(xué)者研究的重點。
2.1 假設(shè)與定義
為了更好地描述算法,在表1中給出如下定義,這里的A代表的是任意節(jié)點或節(jié)點集合。
表1 符號定義
由于ZigBee網(wǎng)絡(luò)的資源限制,進(jìn)行如下假設(shè):
①任意節(jié)點之間的距離和具體位置不可知;
②任意節(jié)點的發(fā)送功率固定且相同;
③網(wǎng)絡(luò)拓?fù)洳灰欢ㄊ且訸C節(jié)點為圓心的圓,但節(jié)點間鄰居關(guān)系是對稱的:若節(jié)點i是節(jié)點j的鄰居節(jié)點,則節(jié)點j也是節(jié)點i的鄰居節(jié)點;
④使用分布式地址分配機(jī)制DAAM,任意節(jié)點在沒有信息交換的的前提下,可獲得父節(jié)點和子節(jié)點地址;
⑤任意節(jié)點維護(hù)一跳鄰居表,任意鄰居表記錄由鄰居網(wǎng)絡(luò)地址和子節(jié)點數(shù)量組成。
2.2 ZigBee樹節(jié)點自剪裁轉(zhuǎn)發(fā)算法
通常Ad hoc網(wǎng)絡(luò)的自剪裁廣播算法中,節(jié)點v接收到RREQ消息后不會直接轉(zhuǎn)發(fā),而會先判斷是否需要轉(zhuǎn)發(fā)RREQ消息[12]。若節(jié)點v的所有鄰居節(jié)點都已經(jīng)接收到節(jié)點u轉(zhuǎn)發(fā)的RREQ消息,即N(v)-N(u)=φ,那么節(jié)點v就沒必要轉(zhuǎn)發(fā)RREQ消息了。這就需要節(jié)點獲悉兩跳鄰居表信息,而這對于能量和帶寬有限的ZigBee網(wǎng)絡(luò)來說是不可能實現(xiàn)的,所以,提出ZigBee樹節(jié)點自剪裁算法ZOSR。ZOSR算法步驟如下:
①一旦有路由請求,源節(jié)點就會向鄰居節(jié)點廣播RREQ消息;
②若中間節(jié)點v首次接收到RREQ消息則將RREQ消息緩存,并啟動定時器;
③節(jié)點v根據(jù)DAAM地址分配方式計算TN(v),令TC(v)=TN(v);
④節(jié)點v接收到節(jié)點u發(fā)送的相同RREQ消息,則節(jié)點v根據(jù)DAAM地址分配方式計算TN(u),并計算TC(v)=TC(v)-TN(u);
⑤若TC(v)=φ,節(jié)點v丟棄該RREQ消息,并停止計時器;
⑥重復(fù)步驟④和步驟⑤,直到定時器超時;
⑦若定時器超時,則轉(zhuǎn)發(fā)緩存中的RREQ消息;
⑧RREQ消息到達(dá)目的節(jié)點之前,重復(fù)步驟②~⑦;
⑨目的節(jié)點接收到RREQ消息后,沿RREQ反向路徑回復(fù)RREP消息;
⑩源節(jié)點接收到RREP消息后建立到目的節(jié)點之間的路由。
2.3 ZigBee轉(zhuǎn)發(fā)節(jié)點選擇算法
為了進(jìn)一步減少RREQ消息的轉(zhuǎn)發(fā)次數(shù),在ZOSR算法基礎(chǔ)上提出一種ZigBee轉(zhuǎn)發(fā)節(jié)點選擇算法ZOFNS,此算法根據(jù)一定準(zhǔn)則,進(jìn)一步地在未被覆蓋的樹鄰居節(jié)點中挑選最優(yōu)的轉(zhuǎn)發(fā)節(jié)點進(jìn)行RREQ消息的轉(zhuǎn)發(fā)。ZOFNS算法具體步驟如下:
①一旦節(jié)點v有路由需求,則向鄰居節(jié)點廣播RREQ消息,并初始化轉(zhuǎn)發(fā)節(jié)點集合,令F(v)=φ;
②利用式(4)分別計算節(jié)點v的備選轉(zhuǎn)發(fā)節(jié)點集S(v)和覆蓋節(jié)點集C(v);
③節(jié)點v若接收到節(jié)點u轉(zhuǎn)發(fā)的RREQ消息,則根據(jù)式(5)更新節(jié)點v的備選轉(zhuǎn)發(fā)節(jié)點集合覆蓋節(jié)點集;
④根據(jù)N(v)中節(jié)點網(wǎng)絡(luò)地址對節(jié)點進(jìn)行排序;
⑤對于節(jié)點v的任意鄰居節(jié)點w,若w∈S(v),則令節(jié)點w的狀態(tài)為“初始”狀態(tài),反之,則令w狀態(tài)為“已轉(zhuǎn)發(fā)”狀態(tài);
⑥初始化當(dāng)前深度值,令CurrentLevel=Lm;
⑦對于處于當(dāng)前深度,且為“初始狀態(tài)”的任意節(jié)點x,若x沒有子節(jié)點或所有子節(jié)點深度均為CurrentLevel+1,則將x的狀態(tài)更新為“不轉(zhuǎn)發(fā)”,反之將x的狀態(tài)更新為“轉(zhuǎn)發(fā)”;
⑧對于任意深度為CurrentLevel+1,狀態(tài)不為“已轉(zhuǎn)發(fā)”,且父節(jié)點x深度不為CurrentLevel的節(jié)點y,若節(jié)點y的狀態(tài)為“不轉(zhuǎn)發(fā)”且節(jié)點x的父節(jié)點深度為CurrentLevel-1,則將節(jié)點x的狀態(tài)設(shè)置為“轉(zhuǎn)發(fā)”。否則,將節(jié)點y的狀態(tài)設(shè)置為“轉(zhuǎn)發(fā)”;
⑨更新當(dāng)前深度值,令CurrentLevel=CurrentLevel-1;
⑩重復(fù)步驟⑦~⑨,直到CurrentLevel=0;
?僅狀態(tài)為“轉(zhuǎn)發(fā)”的節(jié)點轉(zhuǎn)發(fā)RREQ消息。
為了有效地評價ZOSR算法和ZOFNS算法的性能,采用MATLAB軟件來進(jìn)行仿真。將ZOSR算法和ZOFNS算法與ZigBee經(jīng)典路由算法AODVjr分別在節(jié)點數(shù)目為20~100個的不同場景下進(jìn)行了仿真比較:包括轉(zhuǎn)發(fā)節(jié)點數(shù)目和網(wǎng)絡(luò)轉(zhuǎn)發(fā)次數(shù)等指標(biāo)。
仿真時網(wǎng)絡(luò)節(jié)點靜止且隨機(jī)分布,并假定仿真是在MAC層和物理層都不會有數(shù)據(jù)包丟失的理想狀態(tài)下進(jìn)行的,取5次仿真的平均值為最終結(jié)果,其他仿真參數(shù)如表2所示。
表2 仿真參數(shù)設(shè)置
當(dāng)仿真節(jié)點數(shù)目為90時,AODVjr、ZOSR和ZOFNS 3種算法的轉(zhuǎn)發(fā)節(jié)點分布圖分別如圖1(a)、(b)、(c)所示,圖中實心節(jié)點為RREQ消息的轉(zhuǎn)發(fā)節(jié)點,空心節(jié)點為無需轉(zhuǎn)發(fā)RREQ消息的節(jié)點。
圖1 ZOFNS算法轉(zhuǎn)發(fā)節(jié)點分布圖
由仿真結(jié)果可得出AODVjr、ZOSR和ZOFNS算法的轉(zhuǎn)發(fā)節(jié)點數(shù)分別為100、26和20,且算法均能覆蓋全部網(wǎng)絡(luò)節(jié)點。這說明ZOSR、ZOFNS算法能有效減少網(wǎng)絡(luò)中轉(zhuǎn)發(fā)節(jié)點數(shù)目,這是因為ZOSR算法中節(jié)點接收到RREQ消息后不會直接轉(zhuǎn)發(fā),而是等待一段時間,根據(jù)所有樹鄰居節(jié)點是否已接收到RREQ消息來決定當(dāng)前節(jié)點是否轉(zhuǎn)發(fā)RREQ消息。而ZOFNS算法在ZOSR算法基礎(chǔ)上,將一跳樹鄰居關(guān)系推廣到兩跳,即若當(dāng)前節(jié)點的所有鄰居節(jié)點的樹鄰居節(jié)點全部已經(jīng)接收到RREQ消息,則當(dāng)前節(jié)點無需轉(zhuǎn)發(fā)RREQ消息。
3.1 轉(zhuǎn)發(fā)節(jié)點數(shù)
隨著節(jié)點數(shù)從20增加到90(間隔設(shè)置為10),3種算法的轉(zhuǎn)發(fā)節(jié)點數(shù)目都呈正比例增長,如圖2所示。其中,AODVjr算法的轉(zhuǎn)發(fā)節(jié)點數(shù)目與網(wǎng)絡(luò)節(jié)點總數(shù)大致相等,因為AODVjr算法中一旦節(jié)點接收到RREQ消息,會向鄰居節(jié)點廣播RREQ消息,則網(wǎng)絡(luò)中所有節(jié)點都會轉(zhuǎn)發(fā)RREQ消息;而ZOSR算法和ZOFNS算法中,隨著節(jié)點總數(shù)的增加,節(jié)點密度隨之增加(因為仿真區(qū)域固定),從而當(dāng)前節(jié)點的鄰居節(jié)點數(shù)目增加,能有效減少覆蓋全網(wǎng)所需的轉(zhuǎn)發(fā)節(jié)點數(shù)目。所以,隨著節(jié)點數(shù)目增加,ZOSR和ZOFNS算法中轉(zhuǎn)發(fā)節(jié)點數(shù)目漲幅遠(yuǎn)遠(yuǎn)小于AODVjr算法,且ZOFNS算法在一定程度上優(yōu)于ZOFNS算法。
3.2 轉(zhuǎn)發(fā)次數(shù)
隨著網(wǎng)絡(luò)節(jié)點總數(shù)的增加,3種算法中網(wǎng)絡(luò)總轉(zhuǎn)發(fā)次數(shù)增加,如圖3所示。
圖3 各算法轉(zhuǎn)發(fā)次數(shù)比較
其中,AODVjr算法的任意節(jié)點一旦接收到RREQ消息后,會將RREQ消息直接轉(zhuǎn)發(fā),所以隨著節(jié)點數(shù)量增加,網(wǎng)絡(luò)總轉(zhuǎn)發(fā)次數(shù)增長較快;然而,ZOSR算法中,雖然網(wǎng)絡(luò)節(jié)點數(shù)量增加,但轉(zhuǎn)發(fā)節(jié)點數(shù)目漲幅不大,所以網(wǎng)絡(luò)總轉(zhuǎn)發(fā)次數(shù)隨著網(wǎng)絡(luò)節(jié)點總數(shù)增加而緩慢增長;由于ZOFNS算法改進(jìn)思想類似于ZOSR算法,且轉(zhuǎn)發(fā)節(jié)點的數(shù)目更少,所以ZOFNS算法隨節(jié)點總數(shù)增加,網(wǎng)絡(luò)總轉(zhuǎn)發(fā)次數(shù)增長趨勢類似于ZOSR算法,但較ZOSR算法更優(yōu)。
在經(jīng)典ZigBee路由算法AODVjr基礎(chǔ)上,提出了ZigBee樹鄰居節(jié)點自剪裁轉(zhuǎn)發(fā)算法ZOSR、ZigBee轉(zhuǎn)發(fā)節(jié)點選擇算法ZOFNS。仿真結(jié)果顯示,ZOSR和ZOFNS算法均能有效減少網(wǎng)絡(luò)轉(zhuǎn)發(fā)節(jié)點數(shù)目,從而減少網(wǎng)絡(luò)中RREQ消息的總轉(zhuǎn)發(fā)次數(shù),最終減少網(wǎng)絡(luò)路由開銷,降低網(wǎng)絡(luò)能量消耗。同時,由轉(zhuǎn)發(fā)次數(shù)曲線可知,網(wǎng)絡(luò)規(guī)模越大,ZOSR和ZOFNS算法較AODVjr算法優(yōu)勢越明顯。然而,由于ZOSR和ZOFNS算法在選擇轉(zhuǎn)發(fā)節(jié)點時會等待隨機(jī)時間,ZOSR和ZOFNS算法的全網(wǎng)覆蓋時間必然會增加。所以,今后的工作將主要集中于優(yōu)化ZOSR和ZOFNS算法網(wǎng)絡(luò)覆蓋時間問題上。
[1]周武斌.ZigBee無線組網(wǎng)技術(shù)的研究[D].長沙:中南大學(xué),2009:38-39.
[2]Lin Z,Meng M Q H,Liang H.ARoute Discovery Method Based on Limited Flooding in Zigbee Networks[C]∥Automation and Logistics,2008.ICAL 2008.IEEE International Conference on.IEEE,2008:3039-3044.
[3]Ren Z,Tian L,Cao J,et al.AnEfficient Hybrid Routing Algorithm for Zigbee Networks[C]∥Instrumentation&Measurement,Sensor Network and Automation(IMSNA),2012 International Symposium on.IEEE,2012,2:415-418.
[4]Mu J.ADirectional Broadcasting Algorithm for Routing Discovery in ZigBee Networks[J].EURASIP Journal on Wireless Communications and Networking,2014,2014 (1):1-9.
[5]Shan C,Zhang W,Li X.Hybrid Routing Algorithm Optimization for ZigBee Mesh Network[C]∥Computer Applications and Communications(SCAC),2014 IEEE Symposium on:142-146.
[6]穆嘉松,劉開華,史偉光.ZigBee網(wǎng)絡(luò)中基于節(jié)點移動性的路由選擇策略[J].天津大學(xué)學(xué)報,2012,45(4): 301-308.
[7]杜娟,賈海瑞,李眾立.基于邏輯區(qū)域的ZigBee網(wǎng)絡(luò)地址分配算法[J].傳感器與微系統(tǒng),2014,33(1): 126-129.
[8]錢志鴻,朱爽,王雪.基于分簇機(jī)制的ZigBee混合路由能量優(yōu)化算法[J].計算機(jī)學(xué)報,2013,36(3): 485-493.
[9]任智,李鵬翔,姚玉坤,等.基于分段的ZigBee網(wǎng)絡(luò)按需可擴(kuò)展地址分配算法[J].通信學(xué)報,2012,33 (5):131-137.
[10]羅華.基于ZigBee的無線傳感器網(wǎng)絡(luò)路由算法研究[D].長沙:中南大學(xué),2010:42-46.
[11]謝川.基于ZigBee的AODVjr算法研究[J].Computer Engineering,2011,37(10):87-89.
[12]Kim T,Kim S H,Yang J,et al.Neighbor Table Based Shortcut Tree Routing in ZigBee Wireless Networks[J].IEEE Transactions on Parallel and Distributed Systems,2014:25(3):706-716.
Self-pruning Routing Algorithm in ZigBee Network
SHU Hong
(Chongqing Key Lab of Mobile Communications Technology,Chongqing University of Posts and Telecommunications,Chongqing 400065,China)
Although the AODVjr algorithm can obtain the shortest path of packet through broadcasting route request RREQ message to the whole ZigBee network,a large amount of RREQ messages increase the network control overhead,the energy consumption of network nodes,and the possibility of network congestion.Considering the dramatic increase of network nodes'energy consumption in AODVjr algorithm,based on AODVjr and combined with nodes'neighbor table,two algorithms called ZigBee On-tree Self-pruning Rebroadcast Algorithm(ZOSR)and ZigBee On-tree Forwarding Node Selection Algorithm(ZOFNS)are proposed,which limit the number of RREQ messages by screening the forwarding nodes that broadcast RREQ messages.Simulation results show that the algorithms effectively reduce the forwarding number of network nodes,thereby reduce the whole network power consumption and expand the network lifetime.
ZigBee;self-pruning;AODVjr;RREQ;routing
TP393
A
1003-3114(2015)05-41-5
10.3969/j.issn.1003-3114.2015.05.11
舒紅.ZigBee網(wǎng)絡(luò)自剪裁路由算法[J].無線電通信技術(shù),2015,41(5):41-45.
2015-05-11
長江學(xué)者和創(chuàng)新團(tuán)隊發(fā)展計劃(IRT1299);重慶市科委項目(CSTC2012jjA40044,cstc2013yykfA40010);重慶市科委重點實驗室專項經(jīng)費
舒紅(1991—),女,碩士研究生,主要研究方向:移動通信和無線傳感網(wǎng)絡(luò)。