改進的ZigBee網(wǎng)狀網(wǎng)絡路由算法研究

劉瀟花，彭 勇

(江南大學物聯(lián)網(wǎng)工程學院，江蘇無錫 214122)

1 概述

ZigBee是一種低速率、低功耗、適應性強的短距離無線通信技術，在智能家居、家庭保健以及環(huán)境監(jiān)測等無線通信場合得到了廣泛應用［1-2］。ZigBee網(wǎng)絡節(jié)點是依靠電池供電的，由于節(jié)點體積小，因此節(jié)點能量十分有限。當節(jié)點的能量消耗殆盡，容易導致網(wǎng)絡分割，甚至會造成ZigBee網(wǎng)絡癱瘓。所以，提高節(jié)點生存率、降低網(wǎng)絡能耗是解決阻礙ZigBee網(wǎng)絡應用發(fā)展前景的關鍵［3］。ZigBee主要支持3種網(wǎng)絡拓撲，包括星型拓撲(star)、樹形拓撲(tree)和網(wǎng)狀拓撲(mesh)［4］。其中，網(wǎng)狀網(wǎng)絡是具有“自恢復”能力和高可靠性的網(wǎng)絡，可以為節(jié)點提供多條數(shù)據(jù)傳輸路徑。Mesh網(wǎng)絡拓撲一般采用AODVjr路由算法，AODVjr路由算法是在AODV的基礎上發(fā)展而來的，它支持端到端的傳輸［5］。AODVjr算法采用最短路徑傳輸機制，目的節(jié)點回復最先達到的RREQ分組建立路由路徑。正是由于這樣的傳輸機制，AODVjr算法的一些節(jié)點易于因頻繁參與數(shù)據(jù)轉發(fā)而造成節(jié)點死亡。為解決AODVjr算法的這些問題，文獻［6］基于節(jié)點角色差異性和節(jié)點能量狀態(tài)提出一種改進的AODVjr路由算法，文獻［7-8］提出基于能量均衡的改進ZigBee路由算法，文獻［9］基于分層思想提出的網(wǎng)狀網(wǎng)絡路由算法，都在一定程度上降低了節(jié)點死亡率和網(wǎng)絡能耗。

本文在深入分析ZigBee網(wǎng)絡路由算法的基礎上，針對現(xiàn)有AODVjr算法節(jié)點利用率低、網(wǎng)絡能量消耗大的問題，提出一種改進的 F-AODVjr路由算法。

2 AODVjr路由算法

采用AODVjr路由算法的網(wǎng)狀網(wǎng)絡采用預先地址分配方式，網(wǎng)絡中存在3類節(jié)點:中心協(xié)調器，路由器和終端節(jié)點。協(xié)調器和路由器存儲容量大、計算能力強，是全功能設備(Full Function Device，F(xiàn)FD)，可以作為父節(jié)點為新加入的子節(jié)點分配網(wǎng)絡地址，而終端節(jié)點為精簡功能設備(Reduced Function Device，RFD)，只有數(shù)據(jù)收發(fā)功能，作為網(wǎng)絡葉節(jié)點。

網(wǎng)絡中，父節(jié)點能夠接納子節(jié)點的最大數(shù)量為Cm，其中，路由器數(shù)量最大為Rm，網(wǎng)絡中的最大深度為Lm，可通過式(1)定義深度為d的父節(jié)點所擁有的地址空間Cskip(d)［10］:

入網(wǎng)子節(jié)點的類型不同，分配給子節(jié)點的地址的計算方法也不一樣，如果子節(jié)點為第n個加入的路由器節(jié)點，父節(jié)點分配給子路由器的地址A由式(2)計算，父節(jié)點的地址為Ap。若子節(jié)點是第n個加入的終端節(jié)點，則使用式(3)為其分配網(wǎng)絡地址:

AODVjr路由分為路由發(fā)現(xiàn)和路由維護2個過程。在發(fā)現(xiàn)路由環(huán)節(jié)中，存儲路由信息必須通過路由表以及路由發(fā)現(xiàn)表來實現(xiàn)。其中，路由表的條目可以保存很長時間，是持續(xù)的，而路由發(fā)現(xiàn)表條目僅能持續(xù)一個路由發(fā)現(xiàn)操作的期限。

3 AODVjr路由算法存在的問題

ZigBee網(wǎng)絡中每個節(jié)點都維護離自己一跳距離的鄰居節(jié)點信息，每個具有路由功能的節(jié)點都維護一張路由表，記錄本節(jié)點與其他節(jié)點已經存在的路徑信息。AODVjr路由算法分組傳輸如圖1所示。

當源節(jié)點C向目的節(jié)點L傳輸數(shù)據(jù)時，如果C中存在到L的路由表項，則根據(jù)該路由表項轉發(fā)數(shù)據(jù)分組。如果不存在則開啟路由發(fā)現(xiàn)，發(fā)送RREQ分組搜索目的節(jié)點。當開啟路由發(fā)現(xiàn)時，C向周圍節(jié)點廣播RREQ分組，直到找到目的節(jié)點為止。目的節(jié)點收到RREQ分組后，選擇最先達到的RREQ分組進行回復建立傳輸路徑，如圖1中的C－A－B－L路徑。此時，算法存在以下問題:(1)在發(fā)起RREQ尋址之前，若能利用鄰居表找到目的節(jié)點，則可避免開啟路由發(fā)現(xiàn)過程，減少能量消耗，但AODVjr算法在尋址前沒有使用鄰居表;(2)AODVjr算法最短路徑的尋址思想使得網(wǎng)絡中的一些節(jié)點，如A，B由于頻繁參與轉發(fā)數(shù)據(jù)而使節(jié)點能量很快偏低，若繼續(xù)使用這些能量偏低節(jié)點，容易造成其死亡進而引起網(wǎng)絡能耗增大甚至網(wǎng)絡癱瘓問題。本文為優(yōu)化AODVjr算法，解決以上影響AODVjr算法性能的2個主要問題，提出改進的FAODVjr路由算法。

圖1 AODVjr算法分組傳輸

4 改進的ZigBee網(wǎng)狀網(wǎng)絡路由算法設計

4.1 鄰居表

由于鄰居表是每個ZigBee節(jié)點自動維護的，不需要額外的能量消耗，因此在啟動路由發(fā)現(xiàn)之前，如果能根據(jù)鄰居表尋址到目的節(jié)點，將能降低網(wǎng)絡能量消耗。網(wǎng)絡初始化時每個節(jié)點都更新離自己一跳距離的鄰居節(jié)點信息，鄰居表存儲內容如表1所示。

路由節(jié)點在啟動路由發(fā)現(xiàn)過程前，執(zhí)行下列偽代碼，實現(xiàn)鄰居表搜索目的節(jié)點功能。

4.2 路由發(fā)現(xiàn)

如果目的節(jié)點不在鄰居表傳輸范圍內，則開啟路由發(fā)現(xiàn)，發(fā)送洪泛到目的節(jié)點的RREQ分組。RREQ分組只考慮路徑跳數(shù)，雖然能找到最短路徑，但會使某些節(jié)點過度使用成為死亡節(jié)點。在網(wǎng)絡運行后期，死亡節(jié)點無法再轉變?yōu)槟芰砍渥愎?jié)點參與路由轉發(fā)，其他節(jié)點傳輸數(shù)據(jù)時必須繞過死亡節(jié)點，能量消耗巨大。所以，為減少死亡節(jié)點數(shù)和降低網(wǎng)絡能量消耗，在路由發(fā)現(xiàn)時，需解決以下問題:(1)盡量避免低能量節(jié)點的使用，降低死亡節(jié)點率;(2)改進原算法只將路徑跳數(shù)作為路徑代價進行路徑選擇的思想，結合剩余能量、鏈路質量綜合考慮路由成本，達到降低網(wǎng)絡開銷的目的。路由成本最少的路徑為最優(yōu)路徑，數(shù)據(jù)傳輸時路由代價較小。

4.2.1 節(jié)點死亡率

為降低節(jié)點死亡率，改進算法根據(jù)剩余能量和能量閾值劃分節(jié)點等級，使網(wǎng)絡在運行時能夠判斷哪些節(jié)點為能量不足節(jié)點，從而在路由時盡量避開這些節(jié)點，由能量充足節(jié)點充當主要路由角色，以此減少死亡節(jié)點數(shù)，降低節(jié)點死亡率。

改進算法設定一個動態(tài)更新的能量閾值Ex(n)，當剩余能量大于Ex(n)時為能量充足節(jié)點;當剩余能量小于Ex(n)時為能量偏低節(jié)點。能量充足節(jié)點可以用于數(shù)據(jù)傳輸，而能量偏低節(jié)點只轉發(fā)目的節(jié)點在一跳范圍內的數(shù)據(jù)分組或者接收目的節(jié)點為自身的數(shù)據(jù)分組，在路由過程中盡量避免使用低能量節(jié)點。Ex(n)可按式(4)計算:

其中，當n=1時，Ex(1)=ε，Ex(1)為網(wǎng)絡設定的初始能量閾值，ε為特定系數(shù)，用來調整初始閾值的設定。Ex(n－1)表示更新之前的能量閾值，σ為一特定系數(shù)，作用在于控制能量閾值的減小速度。Ntotal指總節(jié)點個數(shù)，為常量，n為變量。為中心協(xié)調器設置2個內部計數(shù)器C1，C2。如果一個節(jié)點的剩余能量值低于當前Ex(n)值，則應向協(xié)調器發(fā)送本節(jié)點能量偏低消息，協(xié)調器使計數(shù)器C1的計數(shù)值加1。根據(jù)計數(shù)器C1的計數(shù)值，中心協(xié)調器可以算出能量偏低節(jié)點與網(wǎng)絡總節(jié)點的個數(shù)比值q。設定一個閾值Etreshold(0＜Etreshold＜1)，當 q＞Etreshold時，協(xié)調器使C2計數(shù)值加1，n值即為C2的計數(shù)值。這樣n值加1發(fā)生改變，使得 Ex(n)值完成一次更新。更新完Ex(n)值，C1置0，C2不變。由式(4)可得Ex(n)值為:

由Ex(n)計算方法可知，在網(wǎng)絡運行初期，能量閾值Ex(n)遞減緩慢，而當n增大，Ex(n)值的遞減幅度越來越小。在網(wǎng)絡運行后期，節(jié)點能量普遍不足，F(xiàn)AODVjr算法能量閾值遞減幅度變慢可以使大部分節(jié)點都能作為能量充足節(jié)點參與路由轉發(fā)，避免因參與路由節(jié)點過少而引發(fā)的網(wǎng)絡擁塞現(xiàn)象，減少因網(wǎng)絡擁塞造成能量的浪費。

4.2.2 路由成本

避開低能量節(jié)點使用后的AODVjr算法還需進一步優(yōu)化。不同的RREQ分組達到目的節(jié)點后，使網(wǎng)絡中存在多條可傳輸路徑。本文從這些路徑中，選擇路由成本最低的路徑為最優(yōu)傳輸路徑，路由成本越低，數(shù)據(jù)傳輸時路由代價越小。路由成本根據(jù)式(5)確定，式(5)綜合考慮了跳數(shù)、剩余能量和鏈路質量對路由成本的影響。

F-AODVjr路由算法更全面地考慮了影響路由性能的因素。在網(wǎng)絡運行初期，節(jié)點性能相同，F(xiàn)AODVjr路由算法優(yōu)勢不明顯。網(wǎng)絡運行一段時間后，節(jié)點剩余能量、鏈路質量發(fā)生變化，改進算法可以選擇一條路由成本最低的路徑，并使數(shù)據(jù)有更高的發(fā)送成功率，從而降低網(wǎng)絡能量消耗。

4.3 算法流程

路由發(fā)現(xiàn)過程如圖2所示。

圖2 路由發(fā)現(xiàn)過程

算法流程具體如下:

(1)在網(wǎng)絡初始化時，中心協(xié)調器為每個網(wǎng)絡節(jié)點分配唯一的網(wǎng)絡地址，每個節(jié)點初始化自己的鄰居表，中心協(xié)調器廣播Ex(1)值。中心協(xié)調器根據(jù)式(4)計算能量閾值，每當能量閾值發(fā)生變化，中心協(xié)調器便向各節(jié)點重新廣播能量閾值。

(2)源節(jié)點查看鄰居表(包括父節(jié)點和子節(jié)點)，若目的節(jié)點在鄰居表中，則直接發(fā)送給目的節(jié)點;否則轉步驟(3)。

(3)查看目的節(jié)點與源節(jié)點的鄰居表(包括父節(jié)點與子節(jié)點)，若存在相同節(jié)點，則將數(shù)據(jù)分組轉發(fā)給此相同節(jié)點，否則轉步驟(4)。

(4)此時，目的節(jié)點必在離源節(jié)點兩跳之外。由于RFD節(jié)點不具有路由功能，因此如果源節(jié)點為FFD節(jié)點則直接開啟一個路由發(fā)現(xiàn)過程，若不是，則交由父節(jié)點開啟路由發(fā)現(xiàn)過程，當一個RFD節(jié)點收到RREQ分組時就立即丟棄。如果目的節(jié)點為RFD節(jié)點，則由其父節(jié)點轉交。路由發(fā)現(xiàn)過程按以下步驟執(zhí)行:1)RREQ分組達到一個節(jié)點，該節(jié)點若不是FFD節(jié)點則丟棄RREQ分組，如果是FFD節(jié)點則轉步驟2)。2)判斷自己是否為目的節(jié)點或者為RFD節(jié)點的父節(jié)點，如果是則回復路由應答(Route Reply，RREP)分組建立路由路徑，否則轉步驟3)。3)查看自己的剩余能量，根據(jù)能量閾值判斷是否是低能量節(jié)點，若是則丟棄RREQ分組，并向中心協(xié)調器發(fā)送能量偏低信息，使計數(shù)器C1加1，若不是低能量節(jié)點轉步驟4)。4)查看自己是否已存在到源節(jié)點的路由表項，如果存在則轉步驟5)，如果不存在則轉步驟6)。5)比較路由表和RREQ分組中的路由成本TC。路由成本越小，表明傳輸數(shù)據(jù)付出的代價越小。如果RREQ分組中的路由成本高于路由表中的路由成本，則丟棄RREQ分組。否則根據(jù)式(5)計算并更新兩者的路由成本，繼續(xù)廣播RREQ分組。6)建立到源節(jié)點的路由表項，并繼續(xù)廣播RREQ分組。

(5)中心協(xié)調器設置目的節(jié)點等待RREQ分組到達的時間常數(shù)T［12］，超過設置的時間則停止等待。目的節(jié)點收到RREQ分組后選擇路由成本最低的路徑建立路由路徑，回復RREP。

5 算法分析與仿真實驗

5.1 算法分析

改進算法針對節(jié)點的能量狀況，根據(jù)式(4)不斷動態(tài)更新能量閾值，使得不同狀態(tài)節(jié)點對RREQ分組采取不同的處理方式，從而保護低能量節(jié)點。更重要的是，能量閾值的更新速度變慢，使得低能量節(jié)點在網(wǎng)絡運行后期轉為能量充足節(jié)點重新參與路由，防止了網(wǎng)絡擁塞現(xiàn)象。在路由發(fā)現(xiàn)階段，路由成本公式計算簡單，由各節(jié)點獨立計算完成。在搜索鄰居表時，假設鄰居節(jié)點個數(shù)為n，算法遍歷每個鄰居節(jié)點，此時，算法時間復雜度為O(n)，算法在多項式時間內完成。

5.2 仿真實驗結果及分析

為評估改進算法的性能，在NS2仿真軟件中對原AODVjr算法、改進的F-AODVjr算法和文獻［6］中的改進的AODVjr算法進行仿真。通過網(wǎng)絡的能量消耗、節(jié)點生存率和平均分組成功投遞率進行對比分析。仿真實驗的網(wǎng)絡范圍為300×300，通信半徑為15 m，節(jié)點初始能量為10 J，數(shù)據(jù)流類型為CBR，數(shù)據(jù)流大小為80 Byte，仿真時間為80 s，數(shù)據(jù)分組的源節(jié)點和目標節(jié)點隨機選擇。

表2為3種算法的數(shù)據(jù)分組成功投遞率仿真對比，數(shù)據(jù)分組成功投遞率指的是目的節(jié)點正確接收到的數(shù)據(jù)分組個數(shù)與源節(jié)點發(fā)送的全部數(shù)據(jù)分組個數(shù)的比值。用Ps表示源節(jié)點發(fā)送的分組數(shù)目，Pr表示成功接收到的分組數(shù)目，數(shù)據(jù)分組成功投遞率為:

由表2可知，當設置網(wǎng)絡節(jié)點個數(shù)為50時，3種算法都具有較高的成功投遞率，都在95%以上。隨著節(jié)點個數(shù)增多，網(wǎng)絡變得復雜，數(shù)據(jù)在傳輸時發(fā)生碰撞幾率增大，所以，3種算法的數(shù)據(jù)分組成功投遞率都有所下降。節(jié)點在傳輸數(shù)據(jù)時，如果目的節(jié)點死亡，數(shù)據(jù)分組將永遠不可達，而中間節(jié)點的死亡，會導致網(wǎng)絡擁塞，阻礙分組投遞。F-AODVjr和改進的AODVjr算法盡量避開了能量不足節(jié)點的使用，所以，數(shù)據(jù)分組成功投遞率大于AODVjr。在此基礎上，F(xiàn)-AODVjr在數(shù)據(jù)分組傳輸時還考慮了節(jié)點的鏈路質量，使節(jié)點具有更高的成功投遞率。

表2 數(shù)據(jù)分組成功投遞率 %

3種算法的剩余能量百分比如圖3所示。

圖3 剩余能量百分比

在網(wǎng)絡初始運行時，網(wǎng)絡節(jié)點的剩余能量、鏈路質量相同，3個算法的剩余能量百分比相差不大。隨著網(wǎng)絡運行，開始出現(xiàn)能量偏低節(jié)點。AODVjr算法繼續(xù)使用能量偏低節(jié)點造成其死亡，在網(wǎng)絡運行后期，當大部分節(jié)點能量偏低時，低能量節(jié)點變?yōu)槟芰砍渥愎?jié)點繼續(xù)用以傳輸數(shù)據(jù)。而AODVjr算法由于死亡節(jié)點無法再變成充足節(jié)點繼續(xù)使用，其他節(jié)點在傳輸數(shù)據(jù)時都要繞過這些死亡節(jié)點，大量消耗網(wǎng)絡能量，其剩余能量百分比降低幅度增大，而改進的AODVjr算法與F-AODVjr算法卻避免了這一現(xiàn)象的產生，遞減幅度小于 AODVjr算法。雖然改進的AODVjr算法能量不足節(jié)點不再用于數(shù)據(jù)傳輸，但仍參與路由發(fā)現(xiàn)，所以，其能量消耗大于F-AODVjr算法。并且網(wǎng)絡運行一段時間后，路徑剩余能量、鏈路質量都發(fā)生變化，跳數(shù)最少的路徑并不一定最優(yōu)，F(xiàn)AODVjr算法能找到一條路由成本最低的路徑，所以，F(xiàn)-AODVjr算法的剩余能量百分比始終高于AODVjr算法和改進的AODVjr算法。

3種算法的節(jié)點生存率如圖4所示。

圖4 節(jié)點生存率

節(jié)點生存率為網(wǎng)絡可用節(jié)點率。如果一個節(jié)點的剩余能量低于初始能量的3%，則被看作是死亡節(jié)點。網(wǎng)絡運行結束后，計算生存節(jié)點個數(shù)。節(jié)點生存率計算公式為:

其中，Nable是網(wǎng)絡運行結束后生存節(jié)點個數(shù);Ntotal是網(wǎng)絡總節(jié)點個數(shù)。在網(wǎng)絡運行初期，節(jié)點能量充足，節(jié)點生存率降低幅度不大。由于F-AODVjr算法盡量避免使用低能量節(jié)點參與路由，因此節(jié)點死亡數(shù)較少，節(jié)點生存率始終高于AODVjr算法和改進的AODVjr算法。在網(wǎng)絡運行后期，雖然三者的節(jié)點生存率下降幅度都有所增大，但F-AODVjr算法和改進的AODVjr算法的網(wǎng)絡拓撲分割現(xiàn)象不嚴重，所以，節(jié)點生存率下降幅度都小于AODVjr算法。

6 結束語

本文針對AODVjr算法存在的問題提出了一種改進的F-AODVjr算法。改進算法在進行發(fā)現(xiàn)路由過程前，使用ZigBee節(jié)點自身維護的鄰居表尋找目的節(jié)點，如果能通過鄰居表找到目的節(jié)點，將大大降低網(wǎng)絡能量消耗。如果目的節(jié)點不在鄰居表傳輸范圍內，則進行路由發(fā)現(xiàn)。在路由發(fā)現(xiàn)過程中，改進算法能提高節(jié)點生存率、降低網(wǎng)絡能量消耗和增大數(shù)據(jù)分組成功投遞率。但改進算法的不足之處是沒有考慮網(wǎng)絡節(jié)點的移動情況，在路由過程中會因產生對尋址無效的RREQ分組而浪費能量。所以，今后將進一步探討如何減少路由過程中RREQ分組的洪泛并將其投入到實際應用中。

［1］李文仲，段朝玉.ZigBee2006無線網(wǎng)絡與無線定位實戰(zhàn)［M］.北京:北京航空航天大學出版社，2008.

［2］Baronti P，Pillai P，Chook V W C，et al.Wireless Sensor Networks:A Survey on the State of the Art and the 802.15.4 and Zigbee Standards［J］.Computer Communications，2007，30(7):1655-1695.

［3］蔣 挺，趙成林.ZigBee技術及其應用［M］.北京:北京郵電大學出版社，2006.

［4］陳 波.Zigbee路由算法分析及改進［D］.天津:南開大學，2009.

［5］Chakeres I D，Berndt K.AODVjr，AODV Simplified［J］.Mobile Computing and Communication Review，2002，6(3):100-101.

［6］王 芳，柴喬林，班艷麗.一種改進的ZigBee Mesh網(wǎng)絡路由算法［J］.計算機應用，2008，28(11):2788-2794.

［7］李予東，黃宏光，向西西.基于能量均衡的Zigbee路由算法優(yōu)化［J］.計算機工程與設計，2011，32(2):397-400.

［8］Ran P，Sun M H，Zou Y M.ZigBee Routing Selection Strategy Based on Date Services and Energy Balanced Zigbee Routing［C］//Proceedings of 2006 IEEE Asia Pacific Conference on Services Computing.Washington D.C.，USA:IEEE Computer Society，2006:400-404.

［9］Ha J Y，Park H S，Choi S，et al.Enhanced Hierarchical Routing Protocol for ZigBee Mesh Networks［J］.IEEE Communications Letters，2007，11(12):1028-1030.

［10］張 擎，劉淑美，柴喬林.能量高效的Zigbee網(wǎng)絡改進路由策略［J］.計算機工程，2010，36(7):108-111.

［11］Ashraf U，Abdellatif S，Juanole G.An Interference and Link-quality Aware Routing Metric for Wireless Mesh Network［C］//Proceedings of the 68th Vehicular Technology Conference.［S.l.］:IEEE Press，2008:1-5.

［12］謝 川.Zigbee中改進的Cluster-Tree路由算法［J］.計算機工程，2011，37(7):115-117.