劉天琛 譚長庚

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

0 引 言

隨著物聯(lián)網(wǎng)技術(shù)的發(fā)展，ZigBee技術(shù)成為解決物聯(lián)網(wǎng)中的最后100 m問題的關(guān)鍵技術(shù)之一。要將ZigBee技術(shù)應(yīng)用到物聯(lián)網(wǎng)中，使用ZigBee技術(shù)的節(jié)點(diǎn)能耗問題成為了業(yè)界重視的難點(diǎn)。如何降低整個(gè)ZigBee網(wǎng)絡(luò)能耗，以及如何解決個(gè)別節(jié)點(diǎn)的耗能較快問題，一直是研究的熱點(diǎn)[1]。

在如何降低網(wǎng)絡(luò)能耗方面，有大量的專家致力于此。一個(gè)比較明確的研究方向是優(yōu)化ZigBee網(wǎng)絡(luò)協(xié)議中的路由算法，降低整個(gè)ZigBee網(wǎng)絡(luò)中RREQ路由請求分組的數(shù)量。同時(shí)，ZigBee協(xié)議中的兩大路由算法——AODVjr算法與Cluster-Tree算法具有各自的優(yōu)缺點(diǎn)[2-3]。兩種算法如何合理平衡地相互結(jié)合，也是研究的重要領(lǐng)域。

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

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

1 ZigBee路由算法

1.1 分布式地址分配機(jī)制

在ZigBee網(wǎng)絡(luò)中，整個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)都被分配了16位短地址，采用的是一種分布式的地址分配方式[8]。其中協(xié)調(diào)器節(jié)點(diǎn)的地址為0，其余的節(jié)點(diǎn)在加入網(wǎng)絡(luò)時(shí)實(shí)行地址的分配。分配規(guī)則如下所述：

對請求加入ZigBee網(wǎng)絡(luò)的節(jié)點(diǎn)進(jìn)行地址分配時(shí)，首先要確定以下參數(shù)：父節(jié)點(diǎn)能夠接受的最大子節(jié)點(diǎn)個(gè)數(shù)Cm、網(wǎng)絡(luò)最大深度Lm、新節(jié)點(diǎn)加入網(wǎng)絡(luò)后的父節(jié)點(diǎn)的網(wǎng)絡(luò)深度d、一個(gè)非終端的路由節(jié)點(diǎn)允許鏈接其他路由子節(jié)點(diǎn)的最大值Rm。確定以上幾個(gè)參數(shù)后，就可以為要加入網(wǎng)絡(luò)的新節(jié)點(diǎn)分配地址。

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

Cskip(d)=

(1)

偏移量計(jì)算完成后，加入網(wǎng)絡(luò)設(shè)備地址的計(jì)算取決于該節(jié)點(diǎn)的類型。當(dāng)節(jié)點(diǎn)類型為路由節(jié)點(diǎn)時(shí)，地址計(jì)算如公式所示：

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

(2)

式中：Paddr表示父節(jié)點(diǎn)地址、x-1表示父節(jié)點(diǎn)已有的路由子節(jié)點(diǎn)個(gè)數(shù)。

節(jié)點(diǎn)類型為終端節(jié)點(diǎn)時(shí)，計(jì)算如公式所示：

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

(3)

式中：n表示當(dāng)前節(jié)點(diǎn)是第幾個(gè)終端節(jié)點(diǎn)。

1.2 路由算法

1.2.1 AODVjr路由算法

作為AODV算法的簡化版[7]，AODVjr路由算法減少了路由發(fā)現(xiàn)過程中的部分的回復(fù)分組，基本過程為：當(dāng)某個(gè)路由節(jié)點(diǎn)發(fā)起路由發(fā)現(xiàn)時(shí)，會(huì)向周圍的鄰居節(jié)點(diǎn)廣播RREQ請求分組。當(dāng)鄰居節(jié)點(diǎn)接收到RREQ請求分組后，根據(jù)自身節(jié)點(diǎn)類型，進(jìn)行下面的步驟：當(dāng)節(jié)點(diǎn)為終端節(jié)點(diǎn)時(shí)，若自身為目標(biāo)節(jié)點(diǎn)，則向發(fā)送該RREQ分組的上一節(jié)點(diǎn)發(fā)送RREP回復(fù)分組，否則丟棄分組。當(dāng)節(jié)點(diǎn)為路由節(jié)點(diǎn)時(shí)，若本身是目標(biāo)節(jié)點(diǎn)，則反向發(fā)送RREP回復(fù)分組，否則將該分組轉(zhuǎn)發(fā)至所有鄰居節(jié)點(diǎn)。網(wǎng)絡(luò)中接受到RREQ的節(jié)點(diǎn)都會(huì)重復(fù)以上步驟。當(dāng)中間節(jié)點(diǎn)接收到RREP分組后，會(huì)將該分組轉(zhuǎn)發(fā)至上一個(gè)發(fā)送對應(yīng)RREQ分組的節(jié)點(diǎn)，直到轉(zhuǎn)發(fā)至源節(jié)點(diǎn)。通過這樣不斷地轉(zhuǎn)發(fā)請求分組，找到最佳的路由路徑，進(jìn)行數(shù)據(jù)的傳輸。

AODVjr算法可以找到目標(biāo)節(jié)點(diǎn)與源節(jié)點(diǎn)之間的最佳路徑，但在路徑發(fā)現(xiàn)期間需要大量轉(zhuǎn)發(fā)RREQ分組。當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)較多時(shí)，極易形成分組風(fēng)暴，造成網(wǎng)絡(luò)擁塞，造成較大的數(shù)據(jù)傳輸延遲。同時(shí)不斷地向鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)請求分組，會(huì)很快地消耗節(jié)點(diǎn)存儲(chǔ)的電量。當(dāng)節(jié)點(diǎn)的能量耗盡時(shí)，會(huì)造成部分甚至大面積的網(wǎng)絡(luò)癱瘓。

1.2.2 Cluster-Tree路由算法

Cluster-Tree路由算法基于分布式地址分布機(jī)制，沿樹狀拓?fù)溥M(jìn)行路由發(fā)現(xiàn)。首先根據(jù)式(1)計(jì)算Cskip(d-1)，然后根據(jù)式(4)判斷目標(biāo)節(jié)點(diǎn)是不是該節(jié)點(diǎn)的子孫節(jié)點(diǎn)。

A

(4)

式中：D表示目的節(jié)點(diǎn)地址，A表示當(dāng)前節(jié)點(diǎn)地址。

當(dāng)目的節(jié)點(diǎn)滿足式(4)時(shí)，則當(dāng)前節(jié)點(diǎn)首先根據(jù)式(1)計(jì)算Cskip(d)，然后根據(jù)式(5)計(jì)算下一跳節(jié)點(diǎn)地址，并將RREQ請求分組轉(zhuǎn)發(fā)至該節(jié)點(diǎn)。

(5)

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

當(dāng)目標(biāo)節(jié)點(diǎn)不滿足式(4)時(shí)，當(dāng)前節(jié)點(diǎn)將RREQ請求分組轉(zhuǎn)發(fā)至父節(jié)點(diǎn)。父節(jié)點(diǎn)接收到RREQ分組后，若自身是目標(biāo)節(jié)點(diǎn)，則向發(fā)送該RREQ分組的上一節(jié)點(diǎn)發(fā)送RREP回復(fù)分組，建立反向路由。否則選擇下一跳節(jié)點(diǎn)。當(dāng)請求分組被轉(zhuǎn)發(fā)至協(xié)調(diào)器節(jié)點(diǎn)時(shí)，將直接根據(jù)式(5)計(jì)算下一跳地址[9]。終端節(jié)點(diǎn)則直接將分組轉(zhuǎn)發(fā)至父節(jié)點(diǎn)。

Cluster-Tree路由算法基于已有的分布式地址分配機(jī)制，復(fù)雜度低、易于實(shí)現(xiàn)。但只依靠樹狀網(wǎng)絡(luò)進(jìn)行路由，會(huì)加大深度較小的、具有較多子樹的路由節(jié)點(diǎn)的負(fù)擔(dān)，一旦這些節(jié)點(diǎn)能量耗盡，極易引發(fā)網(wǎng)絡(luò)癱瘓。

大部分ZigBee網(wǎng)絡(luò)使用的路由算法都是上文提到的兩種路由算法的結(jié)合[10]。一般根據(jù)某些指標(biāo)進(jìn)行條件設(shè)置，當(dāng)節(jié)點(diǎn)能量等狀態(tài)滿足特定的條件時(shí)，靈活地選擇路由算法，以此達(dá)到網(wǎng)絡(luò)的最大利用。但是許多方法都無法很好地將兩者的優(yōu)缺點(diǎn)進(jìn)行結(jié)合，使得二者達(dá)到一種平衡，同時(shí)也不能很好地解決整個(gè)ZigBee網(wǎng)絡(luò)的能耗問題。

2 改進(jìn)算法描述

本文為了解決上述問題，提出了一種新的路由算法——DZBR算法。該算法基于定向的策略，通過對路由發(fā)起過程中轉(zhuǎn)發(fā)的RREQ分組進(jìn)行定向轉(zhuǎn)發(fā)，從而達(dá)到限制路由發(fā)現(xiàn)過程中請求分組數(shù)量的目的，以此降低網(wǎng)絡(luò)能耗。

2.1 區(qū)域劃分

區(qū)域劃分工作在進(jìn)行ZigBee組網(wǎng)時(shí)進(jìn)行。協(xié)調(diào)器需要維護(hù)區(qū)域順序表。區(qū)域順序表是一張環(huán)形鏈表，主要保存各個(gè)區(qū)域的順序，以及各個(gè)區(qū)域中的可分配地址區(qū)間。當(dāng)有路由節(jié)點(diǎn)成為協(xié)調(diào)器節(jié)點(diǎn)的子節(jié)點(diǎn)時(shí)，協(xié)調(diào)器通過該路由節(jié)點(diǎn)與相鄰節(jié)點(diǎn)的位置關(guān)系，計(jì)算出其成為新區(qū)域節(jié)點(diǎn)的位置，插入到區(qū)域順序表中，并將更新后的區(qū)域順序表向全網(wǎng)通報(bào)。如圖1中區(qū)域劃分所示。

圖1中協(xié)調(diào)器具有五個(gè)子節(jié)點(diǎn)，在對其進(jìn)行地址分配后，建立區(qū)域順序表，順序?yàn)镮、II、III、IV、V，如圖1中(a)圖所示。當(dāng)新節(jié)點(diǎn)要加入ZigBee網(wǎng)絡(luò)，并確定成為協(xié)調(diào)器節(jié)點(diǎn)的子節(jié)點(diǎn)時(shí)，可以通過與除協(xié)調(diào)器節(jié)點(diǎn)外的鄰居節(jié)點(diǎn)進(jìn)行相關(guān)的位置計(jì)算，以此確定鄰居區(qū)域?yàn)镮I、III。此時(shí)協(xié)調(diào)器節(jié)點(diǎn)將更新區(qū)域順序表，此時(shí)的順序?yàn)镮、II、VI、III、IV、V，如圖1中(b)圖所示。更新后協(xié)調(diào)器節(jié)點(diǎn)向全網(wǎng)廣播更新后的區(qū)域順序表，為路由發(fā)現(xiàn)時(shí)的區(qū)域定向做準(zhǔn)備工作。

圖1 區(qū)域劃分示意圖

2.2 區(qū)域內(nèi)分組轉(zhuǎn)發(fā)

每一個(gè)具有路由功能的ZigBee節(jié)點(diǎn)，都會(huì)維護(hù)一張路由表與鄰居表。當(dāng)某一節(jié)點(diǎn)有路由請求時(shí)，首先會(huì)遍歷路由表，尋找已經(jīng)存在的路由項(xiàng)進(jìn)行數(shù)據(jù)傳輸。當(dāng)沒有找到對應(yīng)的路由項(xiàng)，或者已存在的路由項(xiàng)失效時(shí)，節(jié)點(diǎn)將遍歷鄰居表，尋找鄰居節(jié)點(diǎn)中是否存在目的節(jié)點(diǎn)。如果鄰居表中不存在目的節(jié)點(diǎn)，當(dāng)前結(jié)點(diǎn)將發(fā)起路由發(fā)現(xiàn)。首先判斷目標(biāo)節(jié)點(diǎn)是否與源節(jié)點(diǎn)處于同一區(qū)域。因?yàn)樵趨^(qū)域順序表中已經(jīng)記錄了各個(gè)區(qū)間的可分配地址，所以只需要遍歷區(qū)域順序表即可。當(dāng)目標(biāo)節(jié)點(diǎn)與源節(jié)點(diǎn)處于同一區(qū)域時(shí)，進(jìn)行區(qū)域內(nèi)分組轉(zhuǎn)發(fā)。具體步驟如下：

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

算法1計(jì)算節(jié)點(diǎn)深度偽代碼

輸入：節(jié)點(diǎn)地址D;

輸出：節(jié)點(diǎn)深度

1 設(shè)置深度獲取成功標(biāo)識GetDeep = false;

2 設(shè)置當(dāng)前深度deep = 0;

3 下一跳節(jié)點(diǎn)地址source = 0;

4 while(!GetDeep)

5 {

6 利用式(1)計(jì)算Cskip;

7 利用式(5)計(jì)算下一跳節(jié)點(diǎn)地址nextStep;

8 if(nextStep == D)

9 GetDeep = true;

10 else

11 {

12 source = nextStep;

13 deep ++;

14 }

15 }

16 返回當(dāng)前深度deep++;

(2) 當(dāng)獲得源節(jié)點(diǎn)深度與目標(biāo)節(jié)點(diǎn)深度后，將其與網(wǎng)絡(luò)深度閾值dm進(jìn)行比較，以決定采用的路由算法。為避免高深度節(jié)點(diǎn)群內(nèi)路由發(fā)現(xiàn)時(shí)，采用AODVjr算法會(huì)出現(xiàn)需要跨過較多節(jié)點(diǎn)尋找目的節(jié)點(diǎn)的情況，本算法中建議在高深度不采用AODVjr算法。同時(shí)為避免低深度時(shí)，采用樹狀路由發(fā)現(xiàn)的路由路徑并非最佳路徑，并加重父節(jié)點(diǎn)或祖輩節(jié)點(diǎn)負(fù)擔(dān)的情況，低深度不采用Cluster-Tree路由。為此設(shè)置深度閾值dm=xLm(0

(3) 當(dāng)源節(jié)點(diǎn)深度與目的節(jié)點(diǎn)深度均小于dm時(shí)，則遍歷鄰居表，挑選節(jié)點(diǎn)進(jìn)行AODVjr路由算法。此時(shí)設(shè)置新的路由深度閾值dn=yLm(x

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

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

輸入：源節(jié)點(diǎn)地址Source，目的節(jié)點(diǎn)地址D，源節(jié)點(diǎn)深度sourceDeep，目的節(jié)點(diǎn)地址DDeep;

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

1 設(shè)置獲取最小公共子樹根節(jié)點(diǎn)標(biāo)識GetCommonNode = false;

2 設(shè)置當(dāng)前深度deep = 0;

3 協(xié)調(diào)器作為起始公共樹節(jié)點(diǎn)CommonNode = 0;

4 while(!GetCommonNode)

5 {

6 利用式(1)計(jì)算Cskip;

7 利用式(5)計(jì)算源節(jié)點(diǎn)的下一跳節(jié)點(diǎn)sourceNextStep;

8 利用式(5)計(jì)算目的節(jié)點(diǎn)的下一跳節(jié)點(diǎn)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) 當(dāng)目的節(jié)點(diǎn)深度大于dm時(shí)，而源節(jié)點(diǎn)深度小于dm時(shí)，源節(jié)點(diǎn)遍歷鄰居表，篩選節(jié)點(diǎn)進(jìn)行AODVjr路由算法。此時(shí)同樣設(shè)置路由深度閾值dn=yLm(x

(6) 當(dāng)源節(jié)點(diǎn)深度與目標(biāo)節(jié)點(diǎn)深度均大于dm時(shí)，則采取Cluster-Tree路由算法，將RREQ請求分組轉(zhuǎn)發(fā)至父節(jié)點(diǎn)。

(7) 中間節(jié)點(diǎn)收到RREQ請求分組后，重復(fù)以上(1)至(6)步，直到找到目標(biāo)節(jié)點(diǎn)，建立反向路由。

區(qū)域內(nèi)分組轉(zhuǎn)發(fā)流程如圖2所示。

圖2 區(qū)域內(nèi)分組轉(zhuǎn)發(fā)流程圖

2.3 區(qū)域間分組轉(zhuǎn)發(fā)

當(dāng)目標(biāo)節(jié)點(diǎn)與源節(jié)點(diǎn)處于不同的區(qū)域時(shí)，進(jìn)行跨區(qū)域間的分組轉(zhuǎn)發(fā)。具體步驟為：

(1) 遍歷區(qū)域順序列表獲得目的節(jié)點(diǎn)所在區(qū)域。同時(shí)可以獲得正向的路由區(qū)域順序列表。然后反向遍歷區(qū)域順序列表，獲得反向的路由區(qū)域順序列表，與正向路由區(qū)域順序列表進(jìn)行比較，保留最短路由區(qū)域順序列表。

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

(3) 當(dāng)發(fā)現(xiàn)不屬于本區(qū)域的節(jié)點(diǎn)，判斷其所屬區(qū)域是否為下一跳區(qū)域，若是則將去加入轉(zhuǎn)發(fā)RREQ請求分組隊(duì)列，否則忽略。

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

(5) 當(dāng)遍歷鄰居表發(fā)現(xiàn)存在下一跳區(qū)域節(jié)點(diǎn)時(shí)，將遍歷轉(zhuǎn)發(fā)分組隊(duì)列中的下一跳區(qū)域節(jié)點(diǎn)，并轉(zhuǎn)發(fā)請求分組。否則遍歷整個(gè)轉(zhuǎn)發(fā)分組隊(duì)列并依次轉(zhuǎn)發(fā)請求分組。

區(qū)域內(nèi)分組轉(zhuǎn)發(fā)流程如圖3所示。

圖3 區(qū)域間分組轉(zhuǎn)發(fā)流程圖

3 仿真分析

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

表1 部分仿真參數(shù)設(shè)置

3.1 請求分組成功投遞率

請求分組成功投遞率衡量的是路由發(fā)現(xiàn)過程中的路由開銷。通過對進(jìn)行路由發(fā)現(xiàn)時(shí)目的節(jié)點(diǎn)接收到的RREQ請求分組數(shù)與整個(gè)路由發(fā)起過程中轉(zhuǎn)發(fā)的RREQ請求分組數(shù)進(jìn)行比較，衡量算法在路由發(fā)現(xiàn)時(shí)的路由開銷。當(dāng)請求分組成功投遞率越高時(shí)，說明了路由算法的可靠性越好，同時(shí)說明算法減少了網(wǎng)絡(luò)中在進(jìn)行路由發(fā)現(xiàn)時(shí)轉(zhuǎn)發(fā)的RREQ請求分組，降低了分組冗余。具體計(jì)算如公式所示：

(6)

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

圖4 請求分組成功投遞率

設(shè)置并發(fā)，使網(wǎng)絡(luò)中同時(shí)存在有3個(gè)路由發(fā)現(xiàn)過程，運(yùn)行實(shí)驗(yàn)，獲得圖5中的結(jié)果，從圖中可以清楚地看出，隨著網(wǎng)絡(luò)負(fù)載的增加，請求分組成功投遞率都出現(xiàn)了較大的降低，其中DBRD算法下降明顯。而CLZBR算法前期較好，后期隨著簇的增多，網(wǎng)絡(luò)內(nèi)分組顯著增多，進(jìn)行請求時(shí)節(jié)點(diǎn)能量降低較快，甚至出現(xiàn)能量耗盡，請求分組成功投遞率出現(xiàn)明顯增多。DZBR算法請求分組成功投遞率也出現(xiàn)了下降，但相比另兩種算法較優(yōu)。

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

改變網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，使得網(wǎng)絡(luò)拓?fù)渲泄?jié)點(diǎn)不均勻分布，而使某一區(qū)間中節(jié)點(diǎn)分布較為集中，取消并發(fā)，再次實(shí)驗(yàn)得到如圖6的結(jié)果。此時(shí)，CLZBR算法在節(jié)點(diǎn)數(shù)較少的情況下表現(xiàn)較佳，但隨著節(jié)點(diǎn)數(shù)增多，由于節(jié)點(diǎn)分布不均勻的問題，網(wǎng)絡(luò)內(nèi)頻繁地使用AODVjr算法，請求分組數(shù)量大幅增加，請求分組成功投遞率均下降明顯。其中CLZBR算法中，簇與簇之間使用沒有限制的AODVjr算法，加大了網(wǎng)絡(luò)內(nèi)的請求分組數(shù)量，請求分組成功投遞率因此降低明顯。而由于節(jié)點(diǎn)的分布不均，節(jié)點(diǎn)深度增加較大，區(qū)域數(shù)也變多，DBRD算法在多個(gè)區(qū)域間以及高深度下使用AODVjr算法，網(wǎng)絡(luò)內(nèi)的轉(zhuǎn)發(fā)分組數(shù)量大幅增加，請求分組成功投遞率一直較低。DZBR算法由于在深度上的限制，雖然請求分組成功投遞率同樣偏低，卻優(yōu)于其他兩種路由算法。

圖6 改變網(wǎng)絡(luò)拓?fù)浜蟮恼埱蠓纸M成功投遞率

3.2 網(wǎng)絡(luò)剩余能量百分比

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

(7)

當(dāng)仿真結(jié)束時(shí)，圖7為第一次實(shí)驗(yàn)時(shí)三種算法對應(yīng)的ZigBee網(wǎng)絡(luò)剩余能量百分比的比較，可以看出，當(dāng)節(jié)點(diǎn)較少時(shí)，CLZBR算法因?yàn)椴捎脴湫温酚?，能耗相對較少。隨著節(jié)點(diǎn)數(shù)目增多，CLZBR算法中簇開始增多，采用AODVjr算法的路由簇節(jié)點(diǎn)也隨之增加，不定向的AODVjr路由消耗了較多的能量，剩余能量百分比有所降低。DBRD算法則因?yàn)楦呱疃裙?jié)點(diǎn)間大量的請求分組轉(zhuǎn)發(fā)導(dǎo)致剩余能耗百分比偏低。由于DZBR算法通過定向轉(zhuǎn)發(fā)請求分組，減少了網(wǎng)絡(luò)中的RREQ分組，同時(shí)對不同深度節(jié)點(diǎn)采用不同路由算法的策略，對能耗進(jìn)行了平衡，故隨著節(jié)點(diǎn)數(shù)的增多，DZBR算法在網(wǎng)絡(luò)剩余能量方面表現(xiàn)更好。其他的兩次實(shí)驗(yàn)結(jié)果與之類似，不再一一敘述。

圖7 網(wǎng)絡(luò)剩余能量百分比

4 結(jié) 語

本文通過對ZigBee網(wǎng)絡(luò)層路由算法節(jié)能問題的研究，提出了一種新的路由算法，通過對節(jié)點(diǎn)進(jìn)行區(qū)域劃分，并確定路由過程中的最短區(qū)域順序，以達(dá)到在路由過程中對RREQ請求分組進(jìn)行定向的目的，減少網(wǎng)絡(luò)中冗余的分組。同時(shí)結(jié)合節(jié)點(diǎn)的深度選擇合適的路由算法，當(dāng)路由節(jié)點(diǎn)深度較低時(shí)，選擇使用AODVjr算法，當(dāng)節(jié)點(diǎn)深度較高時(shí)，選擇使用Cluster-Tree簇樹路由算法，以此避免高深度時(shí)大規(guī)模轉(zhuǎn)發(fā)RREQ請求分組的問題，從而在保證路由算法發(fā)現(xiàn)路徑較佳的同時(shí)，降低整體網(wǎng)絡(luò)的能耗。該算法平衡了AODVjr算法與Cluster-Tree算法的優(yōu)缺點(diǎn)，較為有效地降低網(wǎng)絡(luò)整體能耗，提高了ZigBee網(wǎng)絡(luò)整體性能。

[1] 錢志鴻,王義君.面向物聯(lián)網(wǎng)的無線傳感器網(wǎng)絡(luò)綜述[J].電子與信息學(xué)報(bào),2013,35(1):215-227.

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

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

[4] 徐沛成,胡國榮.改進(jìn)的ZigBee網(wǎng)絡(luò)路由算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2013,34(9):3019-3023.

[5] 錢志鴻,朱爽,王雪.基于分簇機(jī)制的ZigBee混合路由能量優(yōu)化算法[J].計(jì)算機(jī)學(xué)報(bào),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] 朱旭,牛存良,白曉麗.改進(jìn)的ZigBee樹路由算法[J].計(jì)算機(jī)工程與應(yīng)用,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.