基于能量均衡的ZigBee路由算法優化

李予東， 黃宏光， 向西西

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

0 引 言

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

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

1 問題的提出

1.1 鄰居表

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

表1 鄰居表定義

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

Address：鄰居節點的地址；

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

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

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

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

1.2 路由代價

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

路由代價用于表示路由發現過程中該節點被選擇為新的路由節點的概率，路由代價越大，則被選為新的路由節點的概率越小。

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

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

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

1.3 節點能量等級

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

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

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

2 路由算法優化

2.1 初始化

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

2.2 路由發現

如圖1所示，路由發現階段當節點作為中間節點接收到RREQ包時，將按如下步驟處理：

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

圖1 中間節點對RREQ包處理流程

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

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

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

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

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

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

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

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

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

2.3 路由更新與維護

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

3 仿真實現與分析

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

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

圖2 網絡總體能量消耗

圖3 網絡死亡節點個數

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

4 結束語

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

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

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

[3] 耿萌,于宏毅,張效義.ZigBee路由協議分析與性能評估[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能量均衡協議研究[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.