基于定向的ZigBee網絡節能路由算法

劉天琛 譚長庚

(中南大學軟件學院 湖南 長沙 410075)

0 引 言

隨著物聯網技術的發展，ZigBee技術成為解決物聯網中的最后100 m問題的關鍵技術之一。要將ZigBee技術應用到物聯網中，使用ZigBee技術的節點能耗問題成為了業界重視的難點。如何降低整個ZigBee網絡能耗，以及如何解決個別節點的耗能較快問題，一直是研究的熱點[1]。

在如何降低網絡能耗方面，有大量的專家致力于此。一個比較明確的研究方向是優化ZigBee網絡協議中的路由算法，降低整個ZigBee網絡中RREQ路由請求分組的數量。同時，ZigBee協議中的兩大路由算法——AODVjr算法與Cluster-Tree算法具有各自的優缺點[2-3]。兩種算法如何合理平衡地相互結合，也是研究的重要領域。

為解決以上提到的問題，文獻[4]中提出了一種改進的Cluster-Tree算法，部分結合了AODVjr算法，通過計算鄰居節點的父節點地址判斷目的節點是否是其子孫節點，從而進行轉發決策。該方法雖對請求分組數量進行了限制，但控制條件較簡單，當節點數量較多時，結果基本與只使用Cluster-Tree算法相同，無法很好解決較低深度節點負擔過大的問題。文獻[5]中則提出了基于分簇的CLZBR算法，在簇內使用Cluster-Tree算法，簇間使用AODVjr算法，同時計算目的節點的父輩簇節點，在簇首節點進行路由時可直接轉發該父輩簇首節點。該算法較好地減少了請求分組數，平衡了兩種路由算法，但加重了簇首節點的負擔。文獻[6]提出DBDR算法，將網絡分區域使用定向AODVjr算法，但并未考慮高深度節點使用AODVjr時請求分組數量增長較快的問題。

本文通過研究發現，雖然ZigBee網絡層選取AODVjr[7]+Cluster-Tree的混合路由算法，路由過程中路由請求分組冗余問題以及網絡整體能耗較高的問題沒有得到較好的解決，因此本文將主要嘗試解決這方面的問題。

1 ZigBee路由算法

1.1 分布式地址分配機制

在ZigBee網絡中，整個網絡中的節點都被分配了16位短地址，采用的是一種分布式的地址分配方式[8]。其中協調器節點的地址為0，其余的節點在加入網絡時實行地址的分配。分配規則如下所述：

對請求加入ZigBee網絡的節點進行地址分配時，首先要確定以下參數：父節點能夠接受的最大子節點個數Cm、網絡最大深度Lm、新節點加入網絡后的父節點的網絡深度d、一個非終端的路由節點允許鏈接其他路由子節點的最大值Rm。確定以上幾個參數后，就可以為要加入網絡的新節點分配地址。

首先計算新節點相對于父節點的地址偏移量Cskip(d)，具體計算如公式所示：

Cskip(d)=

(1)

偏移量計算完成后，加入網絡設備地址的計算取決于該節點的類型。當節點類型為路由節點時，地址計算如公式所示：

Raddr(d)=Paddr+1+(x-1)×Cskip(d)

(2)

式中：Paddr表示父節點地址、x-1表示父節點已有的路由子節點個數。

節點類型為終端節點時，計算如公式所示：

Eaddr(d)=Paddr+Cskip(d)×Rm+n

(3)

式中：n表示當前節點是第幾個終端節點。

1.2 路由算法

1.2.1 AODVjr路由算法

作為AODV算法的簡化版[7]，AODVjr路由算法減少了路由發現過程中的部分的回復分組，基本過程為：當某個路由節點發起路由發現時，會向周圍的鄰居節點廣播RREQ請求分組。當鄰居節點接收到RREQ請求分組后，根據自身節點類型，進行下面的步驟：當節點為終端節點時，若自身為目標節點，則向發送該RREQ分組的上一節點發送RREP回復分組，否則丟棄分組。當節點為路由節點時，若本身是目標節點，則反向發送RREP回復分組，否則將該分組轉發至所有鄰居節點。網絡中接受到RREQ的節點都會重復以上步驟。當中間節點接收到RREP分組后，會將該分組轉發至上一個發送對應RREQ分組的節點，直到轉發至源節點。通過這樣不斷地轉發請求分組，找到最佳的路由路徑，進行數據的傳輸。

AODVjr算法可以找到目標節點與源節點之間的最佳路徑，但在路徑發現期間需要大量轉發RREQ分組。當網絡中的節點較多時，極易形成分組風暴，造成網絡擁塞，造成較大的數據傳輸延遲。同時不斷地向鄰居節點轉發請求分組，會很快地消耗節點存儲的電量。當節點的能量耗盡時，會造成部分甚至大面積的網絡癱瘓。

1.2.2 Cluster-Tree路由算法

Cluster-Tree路由算法基于分布式地址分布機制，沿樹狀拓撲進行路由發現。首先根據式(1)計算Cskip(d-1)，然后根據式(4)判斷目標節點是不是該節點的子孫節點。

A

(4)

式中：D表示目的節點地址，A表示當前節點地址。

當目的節點滿足式(4)時，則當前節點首先根據式(1)計算Cskip(d)，然后根據式(5)計算下一跳節點地址，并將RREQ請求分組轉發至該節點。

(5)

式中：NS表示下一跳地址，函數int返回任何數的整數部分，即向下取整。

當目標節點不滿足式(4)時，當前節點將RREQ請求分組轉發至父節點。父節點接收到RREQ分組后，若自身是目標節點，則向發送該RREQ分組的上一節點發送RREP回復分組，建立反向路由。否則選擇下一跳節點。當請求分組被轉發至協調器節點時，將直接根據式(5)計算下一跳地址[9]。終端節點則直接將分組轉發至父節點。

Cluster-Tree路由算法基于已有的分布式地址分配機制，復雜度低、易于實現。但只依靠樹狀網絡進行路由，會加大深度較小的、具有較多子樹的路由節點的負擔，一旦這些節點能量耗盡，極易引發網絡癱瘓。

大部分ZigBee網絡使用的路由算法都是上文提到的兩種路由算法的結合[10]。一般根據某些指標進行條件設置，當節點能量等狀態滿足特定的條件時，靈活地選擇路由算法，以此達到網絡的最大利用。但是許多方法都無法很好地將兩者的優缺點進行結合，使得二者達到一種平衡，同時也不能很好地解決整個ZigBee網絡的能耗問題。

2 改進算法描述

本文為了解決上述問題，提出了一種新的路由算法——DZBR算法。該算法基于定向的策略，通過對路由發起過程中轉發的RREQ分組進行定向轉發，從而達到限制路由發現過程中請求分組數量的目的，以此降低網絡能耗。

2.1 區域劃分

區域劃分工作在進行ZigBee組網時進行。協調器需要維護區域順序表。區域順序表是一張環形鏈表，主要保存各個區域的順序，以及各個區域中的可分配地址區間。當有路由節點成為協調器節點的子節點時，協調器通過該路由節點與相鄰節點的位置關系，計算出其成為新區域節點的位置，插入到區域順序表中，并將更新后的區域順序表向全網通報。如圖1中區域劃分所示。

圖1中協調器具有五個子節點，在對其進行地址分配后，建立區域順序表，順序為I、II、III、IV、V，如圖1中(a)圖所示。當新節點要加入ZigBee網絡，并確定成為協調器節點的子節點時，可以通過與除協調器節點外的鄰居節點進行相關的位置計算，以此確定鄰居區域為II、III。此時協調器節點將更新區域順序表，此時的順序為I、II、VI、III、IV、V，如圖1中(b)圖所示。更新后協調器節點向全網廣播更新后的區域順序表，為路由發現時的區域定向做準備工作。

圖1 區域劃分示意圖

2.2 區域內分組轉發

每一個具有路由功能的ZigBee節點，都會維護一張路由表與鄰居表。當某一節點有路由請求時，首先會遍歷路由表，尋找已經存在的路由項進行數據傳輸。當沒有找到對應的路由項，或者已存在的路由項失效時，節點將遍歷鄰居表，尋找鄰居節點中是否存在目的節點。如果鄰居表中不存在目的節點，當前結點將發起路由發現。首先判斷目標節點是否與源節點處于同一區域。因為在區域順序表中已經記錄了各個區間的可分配地址，所以只需要遍歷區域順序表即可。當目標節點與源節點處于同一區域時，進行區域內分組轉發。具體步驟如下：

(1) 源節點深度可以從節點自身信息中獲得，故只需要計算目標節點深度。當目標節點地址為0時，返回深度d=0。當目標節點地址不為0時，將初始深度記為d=0，根據式(5)計算下一跳節點的地址，并與目標節點地址比較，如果下一跳地址與目標節點地址相同，則返回d=d+1；否則d++，繼續循環計算下一跳節點的下一跳地址。偽代碼如算法1所示。

算法1計算節點深度偽代碼

輸入：節點地址D;

輸出：節點深度

1 設置深度獲取成功標識GetDeep = false;

2 設置當前深度deep = 0;

3 下一跳節點地址source = 0;

4 while(!GetDeep)

5 {

6 利用式(1)計算Cskip;

7 利用式(5)計算下一跳節點地址nextStep;

8 if(nextStep == D)

9 GetDeep = true;

10 else

11 {

12 source = nextStep;

13 deep ++;

14 }

15 }

16 返回當前深度deep++;

(2) 當獲得源節點深度與目標節點深度后，將其與網絡深度閾值dm進行比較，以決定采用的路由算法。為避免高深度節點群內路由發現時，采用AODVjr算法會出現需要跨過較多節點尋找目的節點的情況，本算法中建議在高深度不采用AODVjr算法。同時為避免低深度時，采用樹狀路由發現的路由路徑并非最佳路徑，并加重父節點或祖輩節點負擔的情況，低深度不采用Cluster-Tree路由。為此設置深度閾值dm=xLm(0

(3) 當源節點深度與目的節點深度均小于dm時，則遍歷鄰居表，挑選節點進行AODVjr路由算法。此時設置新的路由深度閾值dn=yLm(x

(4) 當源節點的深度大于dm，而目標節點深度小于dm時，源節點遍歷鄰居表，挑選節點進行經過裁剪的AODVjr路由算法。遍歷鄰居表時，首先判斷節點深度。當節點深度大于源節點深度時，忽略該節點，否則計算鄰居表中該節點與目的節點的最小公共子樹路徑長度SND，并與源節點與目的節點的最小公共子樹路徑長度SSD進行比較。當SND≤SSD時將該鄰居節點加入轉發RREQ請求分組隊列，否則忽略該節點。計算最小公共子樹路徑長度的偽代碼如算法2所示。

算法2計算最小公共子樹路徑長度偽代碼

輸入：源節點地址Source，目的節點地址D，源節點深度sourceDeep，目的節點地址DDeep;

輸出：最小公共子樹路徑長度

1 設置獲取最小公共子樹根節點標識GetCommonNode = false;

2 設置當前深度deep = 0;

3 協調器作為起始公共樹節點CommonNode = 0;

4 while(!GetCommonNode)

5 {

6 利用式(1)計算Cskip;

7 利用式(5)計算源節點的下一跳節點sourceNextStep;

8 利用式(5)計算目的節點的下一跳節點DNextStep;

9 if (sourceNextStep != DNextStep)

10 GetCommonNode = true;

11 else

12 {

13 BeginNode = sourceNextStep;

14 deep++;

15 }

16 }

17 返回最小公共子樹路徑長度SSD= sourceDeep-(deep-1)+ DDeep-(deep-1);

(5) 當目的節點深度大于dm時，而源節點深度小于dm時，源節點遍歷鄰居表，篩選節點進行AODVjr路由算法。此時同樣設置路由深度閾值dn=yLm(x

(6) 當源節點深度與目標節點深度均大于dm時，則采取Cluster-Tree路由算法，將RREQ請求分組轉發至父節點。

(7) 中間節點收到RREQ請求分組后，重復以上(1)至(6)步，直到找到目標節點，建立反向路由。

區域內分組轉發流程如圖2所示。

圖2 區域內分組轉發流程圖

2.3 區域間分組轉發

當目標節點與源節點處于不同的區域時，進行跨區域間的分組轉發。具體步驟為：

(1) 遍歷區域順序列表獲得目的節點所在區域。同時可以獲得正向的路由區域順序列表。然后反向遍歷區域順序列表，獲得反向的路由區域順序列表，與正向路由區域順序列表進行比較，保留最短路由區域順序列表。

(2) 遍歷鄰居表節點，并結合最短路由區域順序列表，判斷鄰居節點中是否存在不屬于本區域的節點。

(3) 當發現不屬于本區域的節點，判斷其所屬區域是否為下一跳區域，若是則將去加入轉發RREQ請求分組隊列，否則忽略。

(4) 對于與源節點屬于同一區域的鄰居節點。首先計算目的節點深度dD，與鄰居節點深度di進行比較，當di>dD時忽略該節點。否則計算該鄰居節點與目的節點的最小公共子樹路徑長度SND，然后將源節點與目的節點的最小公共子樹路徑長度SSD進行比較。當SND≤SSD時，將該鄰居節點加入轉發RREQ請求分組隊列，否則忽略該節點。

(5) 當遍歷鄰居表發現存在下一跳區域節點時，將遍歷轉發分組隊列中的下一跳區域節點，并轉發請求分組。否則遍歷整個轉發分組隊列并依次轉發請求分組。

區域內分組轉發流程如圖3所示。

圖3 區域間分組轉發流程圖

3 仿真分析

為了有效地評價本文提出的算法在降低整個ZigBee網絡能耗方面的效果，本文采用了NS3，結合NS3中已實現的IEEE 802.15.4協議層，部分實現ZigBee的網絡層，以進行網絡層路由算法的仿真。進行仿真前，對一些重要的參數進行設定：父節點能夠接受的最大子節點個數Cm= 5、網絡最大深度Lm=5、非終端路由節點允許鏈接其他路由子節點的最大值Rm=3，路由深度閾值dm=1/2Lm、dn=2/3Lm。將本文所提出的算法與文獻[5]中提出的CLZBR算法以及文獻[6]提出的DBRD算法進行比較。分別在節點數為10～100個的不同場景下進行了仿真實驗，仿真時隨機分布節點，隨機選取源節點與目標節點，記錄路由發起過程中產生的數據包個數、成功送達目的節點的包的個數、以及從路由發起到結束網絡剩余能量的變化。每個節點數的實驗運行20次，對相關數據進行記錄后取平均值。每個算法對以下指標進行計算：請求分組成功投遞率，網絡剩余能量，并進行比較。其他仿真參數如表1所示，其中為了使數據差異明顯，將轉發能耗進行了適當調高。

表1 部分仿真參數設置

3.1 請求分組成功投遞率

請求分組成功投遞率衡量的是路由發現過程中的路由開銷。通過對進行路由發現時目的節點接收到的RREQ請求分組數與整個路由發起過程中轉發的RREQ請求分組數進行比較，衡量算法在路由發現時的路由開銷。當請求分組成功投遞率越高時，說明了路由算法的可靠性越好，同時說明算法減少了網絡中在進行路由發現時轉發的RREQ請求分組，降低了分組冗余。具體計算如公式所示：

(6)

圖4為三種算法的請求分組成功投遞率的比較。當節點較少時，CLZBR算法基本等于樹形路由，請求分組數量較少。節點數目增加，網絡中請求分組數量也隨之增加，請求分組成功投遞率因此降低。而DBRD算法未限制高深度節點采用AODVjr算法時請求分組轉發大量增加的問題，請求分組成功投遞率一直處于偏低的狀態。由于本文提出的算法通過定向策略以及不同深度采用不同算法的策略，減少了網內整體的進行路由發現的RREQ分組數量，所以性能相對好于另外兩種算法。

圖4 請求分組成功投遞率

設置并發，使網絡中同時存在有3個路由發現過程，運行實驗，獲得圖5中的結果，從圖中可以清楚地看出，隨著網絡負載的增加，請求分組成功投遞率都出現了較大的降低，其中DBRD算法下降明顯。而CLZBR算法前期較好，后期隨著簇的增多，網絡內分組顯著增多，進行請求時節點能量降低較快，甚至出現能量耗盡，請求分組成功投遞率出現明顯增多。DZBR算法請求分組成功投遞率也出現了下降，但相比另兩種算法較優。

圖5 提高負載后的請求分組成功投遞率

改變網絡的拓撲結構，使得網絡拓撲中節點不均勻分布，而使某一區間中節點分布較為集中，取消并發，再次實驗得到如圖6的結果。此時，CLZBR算法在節點數較少的情況下表現較佳，但隨著節點數增多，由于節點分布不均勻的問題，網絡內頻繁地使用AODVjr算法，請求分組數量大幅增加，請求分組成功投遞率均下降明顯。其中CLZBR算法中，簇與簇之間使用沒有限制的AODVjr算法，加大了網絡內的請求分組數量，請求分組成功投遞率因此降低明顯。而由于節點的分布不均，節點深度增加較大，區域數也變多，DBRD算法在多個區域間以及高深度下使用AODVjr算法，網絡內的轉發分組數量大幅增加，請求分組成功投遞率一直較低。DZBR算法由于在深度上的限制，雖然請求分組成功投遞率同樣偏低，卻優于其他兩種路由算法。

圖6 改變網絡拓撲后的請求分組成功投遞率

3.2 網絡剩余能量百分比

剩余能量百分比能夠真正體現算法對整個ZigBee網絡能耗控制方面的有效性，剩余能量百分比越高，算法的能耗控制效果越好。剩余能量百分比指的是ZigBee網絡中剩余的能量與網絡初始能量的比值，具體計算如式(7)所示：

(7)

當仿真結束時，圖7為第一次實驗時三種算法對應的ZigBee網絡剩余能量百分比的比較，可以看出，當節點較少時，CLZBR算法因為采用樹形路由，能耗相對較少。隨著節點數目增多，CLZBR算法中簇開始增多，采用AODVjr算法的路由簇節點也隨之增加，不定向的AODVjr路由消耗了較多的能量，剩余能量百分比有所降低。DBRD算法則因為高深度節點間大量的請求分組轉發導致剩余能耗百分比偏低。由于DZBR算法通過定向轉發請求分組，減少了網絡中的RREQ分組，同時對不同深度節點采用不同路由算法的策略，對能耗進行了平衡，故隨著節點數的增多，DZBR算法在網絡剩余能量方面表現更好。其他的兩次實驗結果與之類似，不再一一敘述。

圖7 網絡剩余能量百分比

4 結 語

本文通過對ZigBee網絡層路由算法節能問題的研究，提出了一種新的路由算法，通過對節點進行區域劃分，并確定路由過程中的最短區域順序，以達到在路由過程中對RREQ請求分組進行定向的目的，減少網絡中冗余的分組。同時結合節點的深度選擇合適的路由算法，當路由節點深度較低時，選擇使用AODVjr算法，當節點深度較高時，選擇使用Cluster-Tree簇樹路由算法，以此避免高深度時大規模轉發RREQ請求分組的問題，從而在保證路由算法發現路徑較佳的同時，降低整體網絡的能耗。該算法平衡了AODVjr算法與Cluster-Tree算法的優缺點，較為有效地降低網絡整體能耗，提高了ZigBee網絡整體性能。

[1] 錢志鴻,王義君.面向物聯網的無線傳感器網絡綜述[J].電子與信息學報,2013,35(1):215-227.

[2] 謝川.基于ZigBee的AODVjr算法研究[J].計算機工程,2011,37(10):87-89.

[3] 謝川.ZigBee中改進的Cluster-Tree路由算法[J].計算機工程,2011,37(7):115-117.

[4] 徐沛成,胡國榮.改進的ZigBee網絡路由算法[J].計算機工程與設計,2013,34(9):3019-3023.

[5] 錢志鴻,朱爽,王雪.基于分簇機制的ZigBee混合路由能量優化算法[J].計算機學報,2013,36(3):485-493.

[6] Mu J.A directional broadcasting algorithm for routing discovery in ZigBee networks[J].EURASIP Journal on Wireless Communications and Networking,2014,2014(1):94.

[7] Chakeres I D,Klein-Berndt L.AODVjr,AODV simplified[J].Acm Sigmobile Mobile Computing & Communications Review,2002,6(3):100-101.

[8] Kim T,Kim S H,Yang J,et al.Neighbor Table Based Shortcut Tree Routing in ZigBee Wireless Networks[J].IEEE Transactions on Parallel & Distributed Systems,2014,25(3):706-716.

[9] 朱旭,牛存良,白曉麗.改進的ZigBee樹路由算法[J].計算機工程與應用,2016,52(5):114-118.

[10] Xie H F,Zeng F,Zhang G Q,et al.Simulation Research on Routing Protocols in ZigBee Network[C]//Proceedings of the 6th International Asia Conference on Industrial Engineering and Management Innovation.Atlantis Press,2016.