一種基于能耗均衡的ZigBee網(wǎng)絡(luò)高效混合路由算法*

曹建玲，劉文朋，彭 雙，任 智

(重慶郵電大學(xué)移動通信技術(shù)重慶市重點實驗室，重慶 400065)

1 引言

隨著無線網(wǎng)絡(luò)通信技術(shù)的發(fā)展，近距離、低速率、低成本的無線技術(shù)吸引了眾多人的關(guān)注。目前使用較為廣泛的近距離無線通信技術(shù)有藍牙、無線局域網(wǎng)、紅外等，同時具有發(fā)展?jié)摿Φ慕酂o線技術(shù)標準也備受關(guān)注，如 ZigBee、超寬頻(Ultra Wide Band，UWB)、短距通信(Near Field Communication，NFC)［1］等。ZigBee 技術(shù)［2］是基于 IEEE802.15.4標準的短距離、低功耗、低速率、低成本的無線通信技術(shù)，主要適合用于自動控制和遠程監(jiān)控，在工業(yè)、農(nóng)業(yè)、軍事、醫(yī)療等領(lǐng)域有廣闊的應(yīng)用前景。

ZigBee標準提出了樹路由算法 (Tree Routing，TR)和AODVjr［3］兩種路由算法。TR算法根據(jù)樹狀網(wǎng)絡(luò)拓撲設(shè)計，需與ZigBee標準規(guī)定的分布式地址分配機制配合使用，它將數(shù)據(jù)分組沿著樹形結(jié)構(gòu)向上層的父節(jié)點或者下層的子節(jié)點轉(zhuǎn)發(fā)，因此數(shù)據(jù)分組的傳輸無需事先建路，但路徑不一定最優(yōu)，時延有可能偏大。AODVjr算法通過在全網(wǎng)范圍內(nèi)廣播RREQ分組找到并使用最優(yōu)路徑，但全網(wǎng)性的廣播操作會浪費較多的帶寬、內(nèi)存和能量資源，還有可能引起廣播風(fēng)暴。近年來，為了綜合利用TR算法的快捷和AODVjr算法能夠獲得最優(yōu)路徑的優(yōu)點，在ZigBee網(wǎng)絡(luò)中出現(xiàn)了表驅(qū)動－按需混合路由算法，如Lin等提出的LF－ZAODV(Limited Flooding Zig-Bee Ad－h(huán)oc On － demand Distance Vector)算法［4］。錢志鴻等［5］提出基于節(jié)點特性的能量優(yōu)化混合路由算法，限制RREQ分組的轉(zhuǎn)發(fā)跳數(shù)并借助TR算法減小了RREQ廣播的范圍，同時在RREQ分組中加入能量標志位，使目的節(jié)點選擇一條能量充足的路徑回復(fù)RREP分組，延長了網(wǎng)絡(luò)壽命;但仍然使用了廣播RREQ分組的方式且其能量閾值是人為設(shè)定。由上可知，現(xiàn)有基于表驅(qū)動－按需混合路由算法在廣播尋路分組RREQ的過程中因使用泛洪操作而存在冗余開銷，而且建路時未考慮均衡網(wǎng)絡(luò)節(jié)點的能耗，從而影響了路由算法的效率和網(wǎng)絡(luò)的壽命，有進一步改善的需要。

本文后續(xù)內(nèi)容安排如下:第1節(jié)介紹ZigBee技術(shù)的特點及其應(yīng)用，以及相關(guān)研究工作;第2節(jié)給出ZigBee網(wǎng)絡(luò)的數(shù)學(xué)模型、能量模型、問題描述及算法的設(shè)計，第3節(jié)仿真驗證所提協(xié)議的性能，最后總結(jié)全文并簡介未來工作。

2 網(wǎng)絡(luò)模型

2.1 ZigBee網(wǎng)絡(luò)數(shù)學(xué)模型

ZigBee網(wǎng)絡(luò)的數(shù)學(xué)模型為:G=(V，E)，其中V表示所有節(jié)點的集合，V={t}∪Vr∪Ve，t表示網(wǎng)絡(luò)協(xié)調(diào)器/Sink節(jié)點，Vr表示所有路由節(jié)點的集合，Ve表示所有終端節(jié)點的集合;E表示所有對稱無線通信鏈路的集合，網(wǎng)絡(luò)中存在的每一條鏈路是E的一個子集;鏈路的代價可以是數(shù)據(jù)傳輸?shù)亩说蕉藭r延、鏈路長度(跳數(shù))等。

2.2 能量模型

本文所采用的能量模型如下:當(dāng)節(jié)點A向距離為d的節(jié)點B發(fā)送k b的信息，A消耗的能量由發(fā)射電路損耗和功率放大電路損耗兩部分組成(本能量模型具有通用性)，即

式中，Eelec表示發(fā)送k b信息發(fā)射電路的損耗，εfs表示發(fā)送k b信息功率放大所需的能量。當(dāng)節(jié)點B接收A發(fā)送的信息時，其無線接收裝置所需能量為

2.3 問題描述

網(wǎng)絡(luò)中節(jié)點的能量消耗用于信息的發(fā)送(包括轉(zhuǎn)發(fā))和接收，即

式中，Esi、Eti、Eri分別表示網(wǎng)絡(luò)中節(jié)點發(fā)送、轉(zhuǎn)發(fā)和接收信息所消耗的能量。

在現(xiàn)有的ZigBee網(wǎng)絡(luò)混合路由算法中，存在大量冗余的RREQ信息，這些冗余的RREQ信息的收發(fā)增大了網(wǎng)絡(luò)中每個節(jié)點發(fā)送、轉(zhuǎn)發(fā)和接收的信息比特數(shù)，增加了網(wǎng)絡(luò)開銷和節(jié)點的能耗。此外，現(xiàn)有混合路由算法在選路時沒有考慮節(jié)點的剩余能量，當(dāng)節(jié)點剩余能量不足時，如果繼續(xù)轉(zhuǎn)發(fā)數(shù)據(jù)，可能會導(dǎo)致網(wǎng)絡(luò)中節(jié)點能耗不均衡，進而導(dǎo)致路徑的斷裂，影響網(wǎng)絡(luò)性能。

2.4 能耗均衡的高效混合路由算法設(shè)計

針對ZigBee網(wǎng)絡(luò)現(xiàn)有混合路由算法在尋路開銷和節(jié)點能耗等方面的不足，本文提出一種基于能耗均衡的ZigBee網(wǎng)絡(luò)高效混合路由算法——EHCA。EHCA算法采用跨層泛聽兩跳范圍內(nèi)所有的鄰居的信息方式，減少了部分尋路分組的轉(zhuǎn)發(fā);并將節(jié)點深度和剩余能量加入選路標準，達到能耗均衡效果。

2.4.1 EHCA 算法描述

EHCA算法在ZigBee網(wǎng)絡(luò)已使用DAAM機制進行組網(wǎng)和節(jié)點地址分配之后運行，包括以下面兩個階段。

2.4.1.1 兩跳范圍內(nèi)所有的鄰居信息的獲取和發(fā)布

Step 1:節(jié)點在1跳范圍內(nèi)廣播RREQ尋路分組，利用RREQ中的保留字段1 b攜帶是否有橫向鄰居信息。若節(jié)點有橫向鄰居，標識為“1”;否則，標識為“0”。

Step 2:若源節(jié)點通過跨層信息共享感測到橫向鄰居信息，立即向其父輩節(jié)點發(fā)布自己的橫向鄰居信息，直到本節(jié)點與橫向鄰居節(jié)點的深度最大的公共父節(jié)點。

2.4.1.2 路由建立及數(shù)據(jù)轉(zhuǎn)發(fā)

Step 1:源節(jié)點判斷目的節(jié)點是否是自己或子孫節(jié)點的橫向鄰居，若是則直接或通過子孫節(jié)點向該橫向鄰居節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)分組;否則，執(zhí)行Step 2。

Step 2:源節(jié)點產(chǎn)生并組播1個RREQ尋路分組，它的跳數(shù)閾值為源、目的節(jié)點之間的樹路由跳數(shù)減1，組播對象為父節(jié)點、橫向鄰居節(jié)點、所在分支有橫向鄰居節(jié)點的子節(jié)點;如果上述3類節(jié)點中后兩類不存在，則向父節(jié)點單播RREQ。

Step 3:中間節(jié)點收到RREQ后，做如下操作:

(1)判斷該RREQ是否曾收到或者經(jīng)歷的跳數(shù)大于跳數(shù)閾值，若是，則刪除該請求;否則執(zhí)行(2);

(2)若當(dāng)前節(jié)點是目的節(jié)點的父輩或者子孫節(jié)點，則計算自己到目的節(jié)點的跳數(shù)，然后判斷該值加上RREQ經(jīng)歷跳數(shù)是否超出跳數(shù)閾值，若是，刪除該請求;否則，用樹路由向目的節(jié)點轉(zhuǎn)發(fā)該請求;

(3)若當(dāng)前節(jié)點是RREQ發(fā)送節(jié)點的橫向鄰居節(jié)點，則參照Step 2處理該請求;

(4)若RREQ的發(fā)送節(jié)點是當(dāng)前節(jié)點的父節(jié)點，則判斷當(dāng)前節(jié)點及子孫節(jié)點是否有橫向鄰居，如果有，則向它們組播RREQ;否則，刪除該請求;

(5)若RREQ的發(fā)送節(jié)點是當(dāng)前節(jié)點的子節(jié)點，且既不是源、目的節(jié)點的公共父節(jié)點，也不是源、目的節(jié)點的最大深度公共父節(jié)點的子節(jié)點，則參照Step 2處理該請求;若當(dāng)前節(jié)點是源、目的節(jié)點的最大深度公共父節(jié)點的子節(jié)點，則判斷本節(jié)點有無橫向鄰居節(jié)點或與源節(jié)點不同樹枝的子節(jié)點，若有，則向它們組播該請求;否則，刪除該請求。

Step 4:目的節(jié)點收到源節(jié)點發(fā)來的RREQ后，若RREQ經(jīng)歷的跳數(shù)沒有超出跳數(shù)閾值，則沿用RREQ的來路向源節(jié)點發(fā)送RREP。RREP中包含中間節(jié)點深度和(初值為0)、路徑中節(jié)點最小剩余能量(初值為目的節(jié)點的剩余能量)、路徑查找請求經(jīng)過的與源節(jié)點在同一樹枝的節(jié)點個數(shù)等字段。

Step 5:中間節(jié)點收到RREP后，建立到目的節(jié)點的路由，并更新RREP中相應(yīng)字段的值，然后用單播方式向源節(jié)點轉(zhuǎn)發(fā)RREP。

Step 6:源節(jié)點收到RREP后，建立到目的節(jié)點的路由，并存儲RREP攜帶的中間節(jié)點深度和、節(jié)點最小剩余能量、跳數(shù)等信息。

2.4.2 路由判據(jù)新參數(shù)——合成深度

在EHCA算法中，我們提出一種新的路由判據(jù)參數(shù)——合成深度(Integrated Depth)，用于在源節(jié)點收到不同路徑傳來的路由響應(yīng)的情況下，為源節(jié)點選擇整體上離協(xié)調(diào)器更遠、節(jié)點剩余能量更多的路徑。路徑的合成深度dI定 義為

式中，dj表示路徑上與源節(jié)點在同一樹枝的第j個節(jié)點的深度，0＜j≤f，f為該類節(jié)點個數(shù);dk表示路徑上與源節(jié)點不在同一樹枝的第k個節(jié)點(不包括目的節(jié)點)的深度，0＜k≤n，n為該類節(jié)點個數(shù);f和n的值可根據(jù)路由響應(yīng)攜帶的跳數(shù)信息并輔以“地址－位置”關(guān)系通過計算得到;E0、Er分別表示節(jié)點的初始能量和鏈路上節(jié)點最小剩余能量。

3 仿真與分析

3.1 仿真統(tǒng)計量

(1)節(jié)點能耗均方差

節(jié)點能耗均方差反映網(wǎng)絡(luò)中節(jié)點能量消耗的離散程度，其值越小，則節(jié)點的能耗越均衡。節(jié)點能耗均方差的計算公式如下:

式中，Ci表示網(wǎng)絡(luò)中第i個節(jié)點的能量消耗，N表示網(wǎng)絡(luò)中節(jié)點總數(shù)。

(2)網(wǎng)絡(luò)開銷

網(wǎng)絡(luò)開銷用于評價算法的效率，兩者呈負相關(guān)關(guān)系，即網(wǎng)絡(luò)開銷越小，算法效率越高。設(shè)C為網(wǎng)絡(luò)開銷，有

式中，Ns表示發(fā)送和轉(zhuǎn)發(fā)的分組包含的比特數(shù)，Nd表示到達目的節(jié)點的數(shù)據(jù)分組包含的比特數(shù)。

(3)網(wǎng)絡(luò)壽命

網(wǎng)絡(luò)壽命指網(wǎng)絡(luò)的運行時間，是衡量網(wǎng)絡(luò)性能的一個重要指標。設(shè)網(wǎng)絡(luò)啟動時間為TS，終止運行的時間為TE，則網(wǎng)絡(luò)壽命T為

(4)數(shù)據(jù)分組傳送成功率

數(shù)據(jù)分組傳送成功率指網(wǎng)絡(luò)中成功接收數(shù)據(jù)分組數(shù)占發(fā)送數(shù)據(jù)分組總數(shù)的比例，計算公式為

其中，k表示網(wǎng)絡(luò)中節(jié)點的個數(shù)，Ri表示第i個節(jié)點成功接收的數(shù)據(jù)分組的個數(shù)，Si表示第i個節(jié)點發(fā)送的數(shù)據(jù)分組的個數(shù)。

3.2 仿真設(shè)置

仿真實驗使用OPNET14.5作為軟件平臺，主要仿真參數(shù)設(shè)置如表1所示。我們所采用的網(wǎng)絡(luò)模型是由一個協(xié)調(diào)器節(jié)點和若干個信息采集節(jié)點組成的ZigBee網(wǎng)絡(luò)，定義節(jié)點初始能量為10 J，節(jié)點能量低于初始能量的5%時節(jié)點死亡，當(dāng)節(jié)點死亡個數(shù)超過網(wǎng)絡(luò)中節(jié)點總數(shù)的20%時，網(wǎng)絡(luò)結(jié)束運行，協(xié)調(diào)器節(jié)點在場景中心，網(wǎng)絡(luò)中的節(jié)點隨機均勻分布在協(xié)調(diào)器周圍。

表1 仿真參數(shù)設(shè)置Table 1 Setting of simulation parameters

3.3 仿真結(jié)果及分析

(1)節(jié)點能耗均方差

圖1為節(jié)點能耗均方差比較，與TR算法相比，EHCA算法節(jié)點能耗均方差更小(平均減小10.95%);和LF－ZAODV算法相比，EHCA算法節(jié)點能耗均方差平均減小5.35%，說明EHCA算法中節(jié)點的能量消耗與能耗平均值的差異更小，節(jié)點能耗更均衡。在TR算法中，離協(xié)調(diào)器近的節(jié)點業(yè)務(wù)量較大，能量消耗較快，而下層節(jié)點能量消耗相對較慢，網(wǎng)絡(luò)中節(jié)點能耗不夠平均，因此能耗均方差相對較大，最大達到2.88。LF－ZAODV算法以樹路由的路徑長度減1來限制RREQ的泛洪深度，沒有考慮到節(jié)點的能量消耗。EHCA算法在選路時優(yōu)先使用深度較大、剩余能量較多的節(jié)點，減少了深度小的節(jié)點的能量消耗，均衡了網(wǎng)絡(luò)中節(jié)點的能量消耗。所以與TR算法和LF－ZAODV算法相比，EHCA算法的能耗均方差更小，網(wǎng)絡(luò)中節(jié)點能耗更均衡。

圖1 節(jié)點能耗均方差比較Fig.1Comparison of nodes energy consumption

(2)網(wǎng)絡(luò)開銷

網(wǎng)絡(luò)開銷的仿真結(jié)果如圖2所示。

圖2 網(wǎng)絡(luò)開銷比較Fig.2 Comparison of network overhead

圖2顯示，與TR算法相比，EHCA算法能夠有效減少歸一化網(wǎng)絡(luò)開銷(平均21.4%);和 LFZAODV算法相比，EHCA算法能夠有效減少網(wǎng)絡(luò)開銷0.7%(25個節(jié)點)～11%(150個節(jié)點)。LFZAODV算法和EHCA算法能夠找到傳送數(shù)據(jù)的最優(yōu)路徑，因此減少了數(shù)據(jù)分組的轉(zhuǎn)發(fā)次數(shù);而且EHCA算法在尋路過程中利用了節(jié)點的橫向鄰居節(jié)點信息，無需泛洪RREQ就能找到最優(yōu)路徑，在尋路效果相同的前提下，減少RREQ的轉(zhuǎn)發(fā)，從而進一步減小網(wǎng)絡(luò)開銷，具有更高的效率。

(3)網(wǎng)絡(luò)壽命

網(wǎng)絡(luò)中節(jié)點能量小于初始能量的5%時認為節(jié)點死亡，節(jié)點不再執(zhí)行任何功能。當(dāng)死亡節(jié)點數(shù)大于網(wǎng)絡(luò)中總節(jié)點個數(shù)的20%時，網(wǎng)絡(luò)停止運行，統(tǒng)計網(wǎng)絡(luò)壽命。仿真結(jié)果如圖3所示。

圖3 網(wǎng)絡(luò)壽命比較Fig.3 Comparison of network lifetime

圖3顯示，EHCA算法較TR算法網(wǎng)絡(luò)壽命平均延長34.36%，其中50節(jié)點的場景增幅最大，達到75.6%，和LF－ZAODV算法相比，EHCA算法平均延長網(wǎng)絡(luò)的運行時間16.8%。由于EHCA算法在建立路由時，考慮橫向鄰居節(jié)點，盡量在深度較大、節(jié)點剩余能量較多的層面上建立路由，減少了深度較小節(jié)點的死亡，使節(jié)點能耗更均衡，延長了網(wǎng)絡(luò)壽命。LF－ZAODV算法全網(wǎng)廣播RREQ分組，尋找最短路徑，并按最短路徑發(fā)送數(shù)據(jù)分組，但是沒有考慮到節(jié)點的剩余能量。當(dāng)節(jié)點能量不足時，若繼續(xù)轉(zhuǎn)發(fā)數(shù)據(jù)，會導(dǎo)致節(jié)點的死亡。TR算法中，離Sink節(jié)點(協(xié)調(diào)器)越近的節(jié)點，承擔(dān)越多的路由任務(wù)，消耗更多的能量，節(jié)點死亡越快，所以在網(wǎng)絡(luò)條件相同時，EHCA算法的網(wǎng)絡(luò)壽命比LF－ZAODV算法和TR算法的網(wǎng)絡(luò)壽命長。

(4)數(shù)據(jù)分組傳送成功率

在網(wǎng)絡(luò)中死亡節(jié)點出現(xiàn)之前，數(shù)據(jù)分組的傳送成功率如表2所示。

表2 數(shù)據(jù)分組傳送成功率比較Table 2 Comparison of data packet delivery success rate

從表2中數(shù)據(jù)可看出，與LF－ZAODV算法和TR算法一樣，EHCA算法的數(shù)據(jù)傳送成功率也達到100%，說明EHCA算法在減少控制開銷和均衡節(jié)點能耗的同時保持了數(shù)據(jù)傳送成功率性能。

4 結(jié)束語

本文提出EHCA路由算法，在路由建立時利用節(jié)點的兩跳內(nèi)橫向鄰居節(jié)點信息，限制RREQ分組轉(zhuǎn)發(fā)范圍，在一定程度上減少了網(wǎng)絡(luò)開銷;同時，以節(jié)點的深度參數(shù)和剩余能量參數(shù)作為路徑選擇的因素，盡量在深度較大、節(jié)點剩余能量較多的層面建立路由，實現(xiàn)節(jié)點能耗均衡。理論分析和仿真結(jié)果驗證EHCA算法較TR算法和LF－ZAODV算法在節(jié)點能耗均衡和網(wǎng)絡(luò)開銷等方面提升了性能。

在未來工作中，我們將以EHCA算法為基礎(chǔ)，研究設(shè)計綠色的混合路由算法，從整體上減少網(wǎng)絡(luò)的能量消耗，構(gòu)建綠色的ZigBee網(wǎng)絡(luò)。

［1］ Roy W.Near field communication［J］.IEEE Pervasive Computing，2011，10(3):4－7.

［2］ Wang Wei，He Guangyu，Jun Liwan.Research on Zigbee wireless communication technology［C］//Proceedings of 2011 International Conference on Electrical and Control Engineering.Yichang:IEEE，2011:1245 －1249.

［3］ 朱向慶，陳志雄.采用Tree及AODVjr－PB路由算法的無線家庭網(wǎng)絡(luò)設(shè)計［J］.重慶郵電大學(xué)學(xué)報，2011，21(3):343－348.ZHU Xiang－qing，CHEN Zhi－xiong.Design of home wireless network using routing algorithm of Tree and AODVjr－ PB［J］.Journal of Chongqing University of Posts and Telecommunications，2011，21(3):343 －348.(in Chinese)

［4］ Lin Zijing，Meng Q H，Liang Huawei.A Route Discovery Method based on Limited Flooding in ZigBee Networks［C］//Proceedings of 2008 IEEE International Conference on Automation and Logistics.Qingdao:IEEE，2008:3039 －3044.

［5］ 錢志鴻，張曉帆，王義君，等.基于節(jié)點特性的 LRWPAN網(wǎng)絡(luò)能量優(yōu)化路由算法［J］.通信學(xué)報，2010(10):238－243.QIAN Zhi－h(huán)ong，ZHANG Xiao－fan，WANG Yi－jun，et al.Node characteristics based LR －WPAN routing algorithm research for network energy optimization［J］.Journal on Communications，2010(10):238 －243.(in Chinese)