摘要：通過分析ZigBee協議中Cluster-Tree和AODVjr算法的優缺點，提出一種基于Cluster-Tree+AODVjr的優化路由算法。該算法利用ZigB ee協議中的鄰居表，通過定義分區來確定目的節點的范圍，從而控制廣播RREQ分組的跳數，防止無效的RREQ泛洪。此優化算法能夠有效地減小路由跳數，縮短傳輸時延，減少網絡中死亡節點的數量，提高數據傳送的成功率。

關鍵詞：ZigBee；路由算法；Cluster-Ttee+AODVjr；鄰居表；分組

引言

無線通信和嵌入式微傳感器技術的快速發展促進了無線傳感器網絡的崛起。ZigBee協議基于IEEE 802．15．4無線標準制定，包括應用層、網絡層、安全層等，實現了網絡的自組織和自維護的功能。在無線傳感器網絡中，節點的能量是有限的，如果節點在最后因為自身的能量消耗殆盡而死亡，將會對整個網絡的傳輸性能造成很大影響。因此，在實際應用中，根據不同的網絡情況來選擇最符合應用需求的路由協議，讓路由協議根據網絡拓撲選擇合適的路徑，平均分布節點的傳輸能量，降低網絡的功耗是網絡層必須要考慮的任務。

1 ZigBee路由算法研究

依據設備的能力，ZigBee網絡中的設備可以分為全功能設備(Full Function Device，FFD)和半功能設備(Reduced Function Device，RFD)。FFD能轉發其他設備的數據幀，RFD則不能。當FFD加入一個網絡時，它可以作為協調器。協調器會周期性地廣播數據幀，周圍的RFD能夠發現并加入網絡，形成一個星型拓撲網絡。在星型拓撲中，協調器負責控制整個網絡，所有終端設備都直接與協調器通信，并且由它維護。

ZigBee網絡層還支持樹型和網狀網絡。樹型網絡采用分級路由的策略在網絡中傳送數據和控制信息，而網狀網絡則可以進行點對點的通信。在樹型網絡中，根節點(協調器節點)和所有的內部節點(路由器節點)是FFD，而RFD只能作為葉子節點(終端節點)。當協調器或路由器加入網絡時，它必須被分配唯一的網絡地址。

1．1 網絡地址分配

ZigBee協議規范使用一個分布式地址方案分配網絡地址，它設計為給每個潛在父節點提供一個有限的網絡地址子塊。當一個設備成功加入網絡后，其父節點給該節點自動分配一個唯一的網絡地址。

1．2 ZigBee路由算法

網絡層支持Cluster-Tree、AODVjr和Cluster-Tree+AODVjr算法(以下簡稱C+A算法)等多種路由算法，因此ZigBee網絡的路由協議兼具樹型網絡和網狀網絡的特性。

1．2．1 Cluster-Tree算法
樹路由機制是根據網絡地址和節點間的父子關系來實現路由的。如果目的地址設備不是該路由器的子孫，則直接將數據幀轉發給該路由器的父節點，其父節點將按照同樣的步驟進行路由。

1．2．2 AODVjr算法
AODVjr是對AODV算法的一種簡化改進，當源節點要尋找到達目的節點的路徑時，先向其鄰居節點組播RREQ分組。收到該分組的鄰居節點若具備路由能力，則建立指向源節點的反向路由回復，同時繼續向自己的鄰居節點組播該RREQ分組。若不具備路由能力，則通過Cluster-Tree路由算法將該分組交由其子孫節點或父節點進行轉發。當目的節點接收到此RREQ分組后，通過單播的方式向源節點回復RREP分組，同時，所有接收到此RREP分組的節點都將更新記錄自己的鄰居表，路由建立成功。實驗證明，AODVjr算法在保持了AODV原始功能的基礎上，控制開銷比AODV算法更小，因此更節能。

1．2．3 Cluster-Tree+AODVjr算法
在此算法中，網絡中的節點被分成了4類：Coordinator、RN+、RN-和RFD。其中RN+具有足夠的存儲空間和能力來進行AODVjr協議；而RN-則因存儲空間受限，不能夠進行AODVjr協議。Coordinator、RN+、RN-都具有路由功能，在通信時，如果目的節點不是鄰居節點，RN+將會啟動AODVjr，主動查找到達目地節點的最佳路徑；RN-節點只能通過樹路由算法來尋找下一跳的節點。仿真證明，采用Cluster-Tree和AODVjr相結合的路由協議在保證分組遞交率的情況下，具有比單獨使用其中一種路由協議更低的控制開銷和平均時延。

2 優化ZigBee路由算法

2．1 ZigBee路由算法問題

Cluster-Tree算法必須按照簇樹型結構地址分配方式來尋址，路由效率低，并且源節點到目的節點的傳輸路徑由于跳數過多，會影響網絡時延。

AODVjr算法在路由發現過程中，會產生分組大量泛洪問題。例如，當目的節點是源節點的子節點時，若采用AODVjr向鄰居節點發送RREQ分組，則向其父節點以上的節點發送RREQ分組是多余的；若目的節點不是源節點的子節點，則采用AODVjr向其子節點方向發送RREQ分組是多余的。假設網絡的最大深度是1，則數據幀可能被轉發的最長路徑是21，因此當跳數大于21時，就應停止對RREQ分組的繼續廣播，將其丟棄；假設從源節點到目的節點的最小跳數為M，當RREQ分組被轉發的次數大于M時，再繼續轉發是多余的。由于每一次AODVjr路由都要產生大量的RREQ泛洪，因此會使節點能量消耗嚴重。

鑒于以上問題，本文提出一種基于C+A算法的優化路由算法，用以解決Cluster-Tree路由的低效率和AODVjr路由的泛洪嚴重及能量消耗問題。

2．2 優化路由算法思想

在一個傳感器網絡中，傳感節點只能和與它相鄰的，并且在它的射頻傳輸范圍之內的節點直接通信。樹型網絡中每個節點的鄰居表中都包含有其射頻覆蓋范圍內各個鄰居節點的相關信息。在優化路由算法中利用鄰居表中記錄的有效信息，可以使源節點發送給目的節點的數據幀經過一跳到達。

在AODVjr路由發現過程中，為了避免RREQ分組無選擇性的大量泛洪，在優化路由算法中依據不同的情況，添加對RREQ分組廣播跳數的限制條件，使大于限制條件的多余路由不能啟用。這樣能有效地減少RREQ分組泛洪次數，縮小RREQ廣播范圍，限制RREQ分組傳播方向，從而降低網絡的能量消耗。

2．3 優化路由算法設計

優化路由算法的具體步驟如下：
①對樹型網絡進行分區，并設定輔助變量number的初始值為1(number值代表分區次數)。分區原則如下：以協調器為根節點，將根節點的每一個子樹看作一個區域，并為其編號。記錄每一個區域中的最大地址Amax和最小地址Amin。由樹地址分配機制可以得出，在同一區域中的節點地址An均滿足Amin≤An≤Amax，即此區域的地址范圍是[Amin，Amax]，并且每一個區域的地址范圍之間是不相交關系，即一個確定的地址在且僅在一個區域內。
②判斷源節點的類型。若為RFD則直接將數據幀轉發給其父節點；若為FFD則判斷目的節點是否為源節點的子節點。若是，則向下啟動AODVjr路由轉發數據幀，并將RREQ分組的最大廣播跳數限制為|Dd-Ds|(Ds為源節點的網絡深度，Dd為目的節點的網絡深度)，超出范圍則丟棄；若不是，則進行第下一步。
③源節點向鄰居節點發送RREQ分組，鄰居節點判斷自身地址是否與目的地址相等。如果相等，則向上層傳遞，由其上層對數據幀進行解析，并將RREQ分組的最大廣播跳數限制為1，超出范圍則丟棄。如果不等，則進行第④步。
④判斷目的地址在哪個區域中。若目的節點和源節點在同一區域中，進行第⑥步；若不在同一區域中，則進行第⑤步。
⑤判斷源節點的鄰居節點中是否有和目的節點在同一區域的節點。如果有，將數據幀轉發給該節點，并進行第⑥步；如果沒有，則進行第⑦步。
⑥number值加1。將目的節點所在區域看作一個樹型網絡，將其最小地址節點看作該樹的根節點，并按照第①步的分區原則將其進行分區。判斷目的節點和當前節點是否在同一區域中。若是，重復第⑥步；若不是，則進行第⑦步。
⑦將數據幀經由樹路由轉發到第number次分組的根節點，然后啟動AODVjr路由，由此根節點將RREQ分組廣播至目的節點的相應分組內，尋找目的節點，并將RREQ分組的最大廣播跳數限制為|Dd-number+1|，超出范圍則丟棄。
目的節點接收到RREQ分組后，將向尋找路由的源節點回復一個RREP分組，其傳送路徑為路由建立過程的反向路由。所有接收到RREP分組的節點將此路由信息替換并且記錄，正向路由從源節點到目標節點建立成功。優化路由算法的流程圖如圖1所示。

圖1 優化路由算法的流程圖

具體實現過程舉例如下：假設一樹型網絡，網絡參數Cm=4，Lm=4，Rm=3，依據前面的網絡地址分配方式給網絡中各節點分配相應地址，選定源節點為37，在其射頻覆蓋范圍內的鄰居節點是25、36和90。具體網絡節點分布圖如圖2所示。

圖2 樹型網絡節點分布圖

首先將樹型網絡按照自定義的方式進行分區，分區后的網絡如圖3所示。其中，原樹型網絡被分為I、II、III、IV4個區域。

圖3 第一次分區后的樹型網絡

樹型網絡的分區步驟如下：
①當目的節點是41時，直接轉發，并將RREQ分組傳播跳數限制為|4-3|=1。
②當目的節點是90時，由于90是源節點的鄰居節點，直接將數據幀轉發，并將RREQ分組傳播跳數限制為1。
③當目的節點是8時，由于目的節點和源節點屬于同一區域I，則number=number+1，即number=2。并且將區域I繼續分區，第二次分區后的樹型網絡如圖4所示。此時，節點8和節點37不屬于同一區域，則將數據幀沿樹路由轉發給第2次分區的根節點，即節點1。然后，由節點1向區域I-1內的節點廣播RREQ分組，并限制RREQ分組的跳數為|Dd-number+1|=2。

圖4 第二次分區后的樹型網絡

④當目的節點是72時，由于鄰居節點中有和目的節點同區域的節點90，則先將數據幀轉發給節點90，然后再由其通過和③類似的步驟轉發給目的節點。

3 仿真與實驗結果分析

為了比較優化算法與C+A算法的性能，在相同的仿真環境下分別對兩種算法進行了仿真，重點比較了兩者在網絡剩余節點數、路由平均跳數、數據包發送成功率及端到端時延等方面的差別。仿真結果表明，該優化算法具有更優越的性能。但是在節點數目相同的情況下，優化算法的傳輸時延還是比C+A算法要小很多。這是因為算法優化后，數據幀從源節點到達目的節點的傳輸路徑變短，因而傳輸時延減少。

結語

在分析了ZigBee路由協議中Cluster-Tree和AODVjr算法的基礎上，提出了一種基于C+A算法的優化路由算法。優化路由算法利用ZigBee協議中的鄰居表，使數據幀的傳送跳數減少，并通過將樹型網絡自定義分區，來控制路由發現過程中RREQ分組傳播的跳數，從而防止無效的RREQ泛洪，節省了網絡的能量。仿真結果證明，優化的路由算法能夠有效地減小路由跳數，延長網絡的壽命，提高路由效率，從而使網絡整體能耗減低。