基于能量均衡的ZigBee路由算法優(yōu)化

李予東， 黃宏光， 向西西

(四川大學電氣信息學院，四川成都610065)

0 引 言

ZigBee是一種低成本、低功耗、低速率的短距離雙向無線通信技術，主要針對低速率的無線傳感網絡而設計。文獻[1]針對ZigBee無線通信協(xié)議從物理層、數據鏈路層到網絡層、應用匯聚層進行了全面地剖析，給出了各層協(xié)議實現(xiàn)技術的細節(jié)。文獻[2-3]在介紹ZigBee網絡配置、網絡拓撲結構和網絡層各項關鍵技術的基礎上進行仿真，得出AODVjr[4]的控制開銷小于AODV；Cluster-Tree[5]適合存儲能力受限的節(jié)點，具有較大的平均端到端時延，不需要路由發(fā)現(xiàn)過程，然而在節(jié)點分布不均勻的網絡中，容易造成業(yè)務量分布不均衡；AODVjr需要足夠的存儲空間來儲存路由表，而且具有較高的控制開銷；Cluster-Tree+AODVjr算法能夠找到最優(yōu)或相對于Cluster-Tree較優(yōu)的路由，減少平均端到端時延，使網絡中業(yè)務量分布不均衡的情況也得到了緩解，在保證分組遞交率的情況下，具有較低的控制開銷和平均時延。

通常通信網絡路由算法主要考慮如何實現(xiàn)較少的路由跳數和較短的端到端時延。考慮到WSN網絡的具體情況，節(jié)點的能量供應采用電池形式，在能量耗盡后無法更換電池既成為死亡節(jié)點，不能繼續(xù)承擔收發(fā)數據的功能，導致路由鏈的斷裂，甚至割裂整個WSN網絡，致使通信中斷。因此在WSN網絡中犧牲一定的路由跳數和端到端時延來換取節(jié)點更長的生存時間就成為一種必要。本文在Cluster-Tree+AODVjr算法基礎上詳細闡述了對現(xiàn)有基于能量均衡的ZigBee路由算法的改進方案并輔以仿真，對比分析加以說明。

1 問題的提出

1.1 鄰居表

文獻[6]針對節(jié)點間的父子關系提出了一種改進方案，即當目的節(jié)點為當前節(jié)點的父類節(jié)點時，不適合向當前節(jié)點的后裔子節(jié)點發(fā)送RREQ分組，反之當目的節(jié)點為當前節(jié)點后裔子節(jié)點時，不適合向當前節(jié)點的父類節(jié)點發(fā)送RREQ分組。但考慮到節(jié)點間的位置關系，如目的節(jié)點在當前節(jié)點一跳或者較少跳范圍內時，仍然可以發(fā)現(xiàn)高效的路由路徑，因此需要對其做出改進，本文中加入鄰居表，保證在適當控制AODVjr泛洪方向的同時能尋找到比文獻[6]有效的路由。如表1所示定義了鄰居表。

表1 鄰居表定義

ZigBee網絡中的每個節(jié)點被分成4種類型：Coordinator、RN+、RN-、RFD。如果待發(fā)送數據的目的節(jié)點是自己的鄰居，直接通信即可。Coordinator和RN+可以啟動AODVjr，主動查找到目標節(jié)點的最佳路由，且可以扮演路由代理的角色，幫助其它節(jié)點查找路由；RN-只能使用Cluster-Tree算法，它可通過計算判斷把數據包交給自己的父節(jié)點還是由某個子節(jié)點轉發(fā)；而RFD只能充當Cluster-Tree的葉子，把數據交給父節(jié)點轉發(fā)。除RFD節(jié)點外每個節(jié)點都存儲一張鄰居表，記錄該節(jié)點與其它節(jié)點的鄰居關系，在鄰居表中有四個字段：

Address：鄰居節(jié)點的地址；

NodeType：鄰居節(jié)點的設備類型，0表示該鄰居節(jié)點不具有路由功能，只能接收數據或者轉發(fā)給其父節(jié)點，1具有路由功能；

RoutingCost為該鄰居節(jié)點的路由代價；若節(jié)點為類型為RFD，因其不具備路由功能，則該值為無效值0xFFFF，表示路由代價無限大。

RNRouting為RN-節(jié)點鄰居表的特殊值，由于RN-節(jié)點不能存儲路由表，該值為1表示該節(jié)點是RN-節(jié)點的下一跳，用于路由建立后轉發(fā)數據，為0表示該節(jié)點是RN-節(jié)點的上一跳，用于接收路由建立時由目的節(jié)點向源節(jié)點返回的 RREP包。在 Coordinator、RN+節(jié)點的鄰居表中該值被置為無效值0xFFFF。

RN-節(jié)點只能使用Cluster-Tree算法，它可通過計算判斷該把數據包交給自己的父節(jié)點還是由某個子節(jié)點轉發(fā)。文獻[7]針對Cluster-Tree提出了一種計算鄰居表內節(jié)點到目的節(jié)點路由的思路，但僅比較了目的地為非當前節(jié)點的子節(jié)點的情況。文獻[8]僅基于節(jié)點能量來計算Cluster-Tree算法的路由路徑代價。本文充分利用鄰居表，比較鄰居表中節(jié)點與Cluster-Tree算法中下一條節(jié)點的路由代價，選擇路由代價最小的節(jié)點作為下一跳節(jié)點，從而達到針對RN-節(jié)點改進Cluster-Tree算法的目的。

1.2 路由代價

文獻[9]中對節(jié)點路由代價定義僅劃分了中心協(xié)調器和普通路由節(jié)點，而忽略了各個普通路由節(jié)點仍有很大的特性，本文中對除RFD節(jié)點以外的所有節(jié)點定義了統(tǒng)一的路由代價如下公式所示

路由代價用于表示路由發(fā)現(xiàn)過程中該節(jié)點被選擇為新的路由節(jié)點的概率，路由代價越大，則被選為新的路由節(jié)點的概率越小。

PowerRemaining表示該節(jié)點的剩余能量，剩余能量越多則成為新路由節(jié)點的概率越大，以減少剩余能量較小節(jié)點成為新的路由節(jié)點的概率；

Count用于計數當前節(jié)點作為路由節(jié)點的次數，即每次發(fā)現(xiàn)路由過程中若該節(jié)點被選為路由節(jié)點則其計數值加1，用于表示該節(jié)點可能承擔的路由分量。因其一旦作為路由節(jié)點，則在之后就有可能大量的轉發(fā)數據、消耗節(jié)點能量。因此該值越大，則在新的路由發(fā)現(xiàn)過程中被選為路由節(jié)點的概率就越小。

Suns表示該節(jié)點所擁有的子孫節(jié)點數，Depth表示該節(jié)點的深度，擁有的子孫節(jié)點數越多，在樹結構中的深度越小則在Cluster-Tree算法中越有可能作為路由節(jié)點，因此應當在發(fā)送RREQ分組選擇新路由節(jié)點過程中盡量繞過這樣的節(jié)點。

1.3 節(jié)點能量等級

文獻[9]中將節(jié)點能量劃分為4個等級，根據不同的能量狀況，在接收到RREQ分組選擇不同的處理機制。但已經判斷過是否為目的節(jié)點，警戒狀態(tài)再次判斷沒有意義，而瀕臨失效的節(jié)點對目的節(jié)點為自身的節(jié)點也不回應，既相當于是死亡節(jié)點。本文中將節(jié)點能量劃分為3個等級：充足、偏低和綜合警戒、瀕臨失效節(jié)點為警戒一種節(jié)點。能量充足節(jié)點可以根據節(jié)點類型選擇Cluster-Tree算法或AODVjr算法發(fā)現(xiàn)路由，能量偏低節(jié)點根據一定的公式延遲發(fā)送AODVjr泛洪包，能量警戒節(jié)點只對目的地址是自身的做出回應。

文獻[6，9-10]分別定義了不同的節(jié)點能量警戒值，均為動態(tài)更新，以便警戒節(jié)點在一定條件下能夠重新恢復為有效路由節(jié)點。但充足能量值和偏低能量值均為固定值，不能隨網絡能量狀況的改變而改變，導致大量節(jié)點能量等級處于偏低狀態(tài)，影響路由發(fā)現(xiàn)。文獻[6]中的警戒值為網絡運行時間的函數，網絡運行時間越長，警戒值越低，但僅以時間為變量，不能充分描述網絡中節(jié)點能量的具體情況。文獻[9-10]則以成為警戒節(jié)點的計數為變量，但公式較復雜。本文簡化文獻[9-10]的公式，并定義動態(tài)更新的節(jié)點能量充足值、偏低值和警戒值如下

Power為節(jié)點的初始能量值，、和 為固定系數，N為初始值為1的計數值。當警戒節(jié)點個數與所有節(jié)點個數比Waring Nodes/Nodes達到一定臨界值Threshold時則N計數加1。

2 路由算法優(yōu)化

2.1 初始化

在初始化階段，中心協(xié)凋器Coordinator根據網絡地址分配機制[11]為每個節(jié)點分配惟一的網絡地址；網絡中除RFD節(jié)點外每個節(jié)點初始化本身的鄰居列表，記錄所有鄰居節(jié)點的相關信息；并且將自身剩余能量值與節(jié)點能量等級部分定義的各個臨界值相比較，判斷出該節(jié)點所在的能量區(qū)域，從而在傳輸數據的時候選擇不同的路由策略。

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

如圖1所示，路由發(fā)現(xiàn)階段當節(jié)點作為中間節(jié)點接收到RREQ包時，將按如下步驟處理：

(1)判斷本身是否為目的地，若是則返回RREP包，否則進入下一步。

圖1 中間節(jié)點對RREQ包處理流程

(2)檢測自身剩余能量是否處于警戒狀態(tài)，若是則直接丟棄RREQ包，并向Coordinator節(jié)點發(fā)送數據并由Coordinator節(jié)點更新警戒節(jié)點計數WaringNodes，同時向其所有鄰居節(jié)點發(fā)送數據，由其鄰居節(jié)點更新各自的鄰居表，將該警戒節(jié)點的Nodetype置0，以便之后不再向其發(fā)送RREQ包；否則進入下一步。

(3)判斷目的節(jié)點是否在鄰居表內，若是則向目的節(jié)點發(fā)送RREQ包；否則進入下一步。

(4)判斷節(jié)點類型是否為RN-，若是則掃描鄰居表中是否有RNRouting值為1的節(jié)點，若有則向該節(jié)點發(fā)送RREQ包，若無則比較鄰居表中節(jié)點的路由代價 RoutingCost，并選擇RoutingCost最小的節(jié)點作為下一跳節(jié)點(根據Cluster-Tree算法計算得出的下一跳節(jié)點也必然在鄰居表內)轉發(fā)RREQ包，并將鄰居表中該節(jié)點的RNRouting置1，同時將鄰居表中上一跳節(jié)點RNRouting置0以便其可以接收到返回的RREP包，從而結合鄰居表根據節(jié)點能量等級達到優(yōu)化Cluster-Tree算法的目的；否則進入下一步。

(5)判斷目的節(jié)點是否在當前節(jié)點的父親節(jié)點或子節(jié)點的鄰居表內，若是則向父親節(jié)點或子節(jié)點轉發(fā)RREQ包；否則進入下一步。

(6)檢測自身剩余能量是否充足，若是則判斷目的節(jié)點為當前節(jié)點的父類節(jié)點或是后裔節(jié)點：若是父類節(jié)點，則只向父親節(jié)點轉發(fā)RREQ包，若是后裔節(jié)點則只向子節(jié)點轉發(fā)RREQ包，與步驟5結合達到適當控制AODVjr泛洪方向的目的，否則進入下一步。

(7)此時節(jié)點能量等級必為偏低，則按照步驟6轉發(fā)RREQ包，在轉發(fā)RREQ包時加入一定的延時T

(8)RFD節(jié)點則根據節(jié)點能量等級選擇延遲或直接轉發(fā)RREQ包給其父節(jié)點。

AODVjr算法中節(jié)點只接受最先到達的RREQ包，這樣若節(jié)點已經接收到RREQ包，則會丟棄該由于延遲而較晚到達的RREQ包，從而變相的選擇了路由代價較小的路由路徑。

當目的節(jié)點接收到RREQ包時則向源節(jié)點沿該RREQ包發(fā)送路徑返回RREP包，源節(jié)點接收到RREP包則路由路徑建立。

2.3 路由更新與維護

在數據傳遞過程中，需要對路由和節(jié)點狀態(tài)進行實時的更新與維護，以反映網絡能量狀態(tài)的變化：節(jié)點一旦成為路由節(jié)點則其成為路由節(jié)點的計數Count加1；節(jié)點在每次轉發(fā)數據后都會更新自己的能量值，判斷能量等級是否發(fā)生變化，若節(jié)點能量等級更新為PowerWaring，則向源節(jié)點發(fā)送數據表示該路由失效進而使源節(jié)點重新啟動路由發(fā)現(xiàn)，同時向Coordinator節(jié)點更新WaringNodes計數，若警戒節(jié)點個數與所有節(jié)點個數比WaringNodes/Nodes達到臨界值Threshold則N計數加1從而根據公式更新節(jié)點能量等級值。

3 仿真實現(xiàn)與分析

本仿真實驗利用OMNeT++4.0和MF模型實現(xiàn)。網絡覆蓋面積為100m×100m，網絡節(jié)點數目設置為100個，節(jié)點初始能量均為1000J，、和 分別為0.75、0.5和0.25，為100，Threshold為0.5，采用的傳輸信道數據傳輸率為250KB，數據包長度為128bit。

如圖2所示，由于本文算法引入了鄰居表，選擇路由節(jié)點時考慮了較文獻[10]更多的因素，能量等級均為動態(tài)變化且真正實現(xiàn)了AODVjr算法和Cluster-Tree算法的結合，因此能夠選擇出能量消耗更小的路由路徑。雖然在網絡初始化階段網絡總體能量消耗與文獻[10]算法基本相當，但一旦路由建立，本文算法在網絡總體能量消耗上明顯優(yōu)于原算法和文獻[10]算法。

圖2 網絡總體能量消耗

圖3 網絡死亡節(jié)點個數

如圖3所示，在網絡初始化階段，每個節(jié)點的能量都很充足，3種算法均不會產生死亡節(jié)點，隨著網絡運行時間的增長，原算法沒有考慮節(jié)點能量狀況，有的節(jié)點頻繁作為路由節(jié)點消耗很大的能量，最先出現(xiàn)死亡節(jié)點。本文考慮節(jié)點能量狀況的同時適當控制RREQ包的轉發(fā)，并且在Cluster-Tree算法中也加入了對節(jié)點能量狀況的考慮，能夠更好的選擇能量狀況較好的節(jié)點作為路由節(jié)點，均衡了網絡能量消耗，最大化網絡生存時間，較文獻[10]在死亡節(jié)點出現(xiàn)時間和死亡節(jié)點個數上均有較大優(yōu)化。

4 結束語

本文針對原ZigBee路由算法和現(xiàn)有能量均衡算法中的不足，分別提出了基于能量均衡的AODVjr算法和Cluster-Tree算法改進方案，并結合兩種算法，有效使用鄰居表實現(xiàn)RN-節(jié)點的路由功能同時控制RREQ包轉發(fā)方向；提出了基于節(jié)點剩余能量、成為路由節(jié)點次數、子孫數目和深度的能夠全面體現(xiàn)節(jié)點現(xiàn)有和將來能量狀況的路由代價；提出了動態(tài)更新的節(jié)點能量等級，使網絡能夠選擇出能量代價最小的路由路徑，同時均衡整個網絡的能量消耗。仿真表明本文算法確實優(yōu)化了ZigBee網絡的能量消耗狀況。

[1] 任秀麗,于海斌.ZigBee無線通信協(xié)議實現(xiàn)技術的研究[J].計算機工程與應用,2007,43(6):143-145.

[2] 杜煥軍,張維勇,劉國田.ZigBee路由協(xié)議的研究[J].合肥工業(yè)大學學報,2008,10(31):1617-1621.

[3] 耿萌,于宏毅,張效義.ZigBee路由協(xié)議分析與性能評估[J].計算機工程與應用,2007,43(26):116-120.

[4] Fechner J.ZigBee in industrial applications[C].Nurnberg,Germany:Proceedingsofthe 2006International Conference on Power Electronics Intelligent Motion and Power Quality,2006:61-62.

[5] Leek K,Kims H,Choiy S,et al.A mesh routing protocol using cluster label in the ZigBee network[C].New York:IEEE International Conference on Mobile Ad Hoc and Sensor Systems,2006:801-806.

[6] 班艷麗,柴喬林,王芳.改進的ZigBee網絡路由算法[J].計算機工程與應用,2009,45(5):95-116.

[7] 李剛,陳俊杰,葛文濤.一種改進的ZigBee網絡Cluster-Tree路由算法[J].測控技術,2009,28(9):52-55.

[8] 王琛,柴喬林,王芳.基于樹形結構的ZigBee能量均衡協(xié)議研究[J].計算機工程與設計,2009,30(15):3534-3586.

[9] 王芳,柴喬林,班艷麗.一種改進的ZigBee mesh網絡路由算法[J].計算機應用,2008,28(11):3534-3586.

[10]班艷麗,柴喬林,王琛.基于能量均衡的ZigBee網絡樹路由算法[J].計算機應用,2008,28(11):2791-2794.

[11]Asano Y,Imai H,Toyoda M,et al.Finding neighbor communities in the web using an inter-site graph[J].IEICE Transactions on Information and Systems,2004(9):2163-2170.