ZigBee網(wǎng)絡(luò )Cluster-Tree優(yōu)化路由算法研究

摘要：通過(guò)分析ZigBee協(xié)議中Cluster-Tree和AODVjr算法的優(yōu)缺點(diǎn)，提出一種基于Cluster-Tree+AODVjr的優(yōu)化路由算法。該算法利用ZigB ee協(xié)議中的鄰居表，通過(guò)定義分區來(lái)確定目的節點(diǎn)的范圍，從而控制廣播RREQ分組的跳數，防止無(wú)效的RREQ泛洪。此優(yōu)化算法能夠有效地減小路由跳數，縮短傳輸時(shí)延，減少網(wǎng)絡(luò )中死亡節點(diǎn)的數量，提高數據傳送的成功率。
關(guān)鍵詞：ZigBee；路由算法；Cluster-Ttee+AODVjr；鄰居表；分組

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

1 ZigBee路由算法研究
依據設備的能力，ZigBee網(wǎng)絡(luò )中的設備可以分為全功能設備(Full Function Device，FFD)和半功能設備(Reduced Function Device，RFD)。FFD能轉發(fā)其他設備的數據幀，RFD則不能。當FFD加入一個(gè)網(wǎng)絡(luò )時(shí)，它可以作為協(xié)調器。協(xié)調器會(huì )周期性地廣播數據幀，周?chē)腞FD能夠發(fā)現并加入網(wǎng)絡(luò )，形成一個(gè)星型拓撲網(wǎng)絡(luò )。在星型拓撲中，協(xié)調器負責控制整個(gè)網(wǎng)絡(luò )，所有終端設備都直接與協(xié)調器通信，并且由它維護。
ZigBee網(wǎng)絡(luò )層還支持樹(shù)型和網(wǎng)狀網(wǎng)絡(luò )。樹(shù)型網(wǎng)絡(luò )采用分級路由的策略在網(wǎng)絡(luò )中傳送數據和控制信息，而網(wǎng)狀網(wǎng)絡(luò )則可以進(jìn)行點(diǎn)對點(diǎn)的通信。在樹(shù)型網(wǎng)絡(luò )中，根節點(diǎn)(協(xié)調器節點(diǎn))和所有的內部節點(diǎn)(路由器節點(diǎn))是FFD，而RFD只能作為葉子節點(diǎn)(終端節點(diǎn))。當協(xié)調器或路由器加入網(wǎng)絡(luò )時(shí)，它必須被分配唯一的網(wǎng)絡(luò )地址。
1．1 網(wǎng)絡(luò )地址分配
ZigBee協(xié)議規范使用一個(gè)分布式地址方案分配網(wǎng)絡(luò )地址，它設計為給每個(gè)潛在父節點(diǎn)提供一個(gè)有限的網(wǎng)絡(luò )地址子塊。當一個(gè)設備成功加入網(wǎng)絡(luò )后，其父節點(diǎn)給該節點(diǎn)自動(dòng)分配一個(gè)唯一的網(wǎng)絡(luò )地址。
1．2 ZigBee路由算法
網(wǎng)絡(luò )層支持Cluster-Tree、AODVjr和Cluster-Tree+AODVjr算法(以下簡(jiǎn)稱(chēng)C+A算法)等多種路由算法，因此ZigBee網(wǎng)絡(luò )的路由協(xié)議兼具樹(shù)型網(wǎng)絡(luò )和網(wǎng)狀網(wǎng)絡(luò )的特性。
1．2．1 Cluster-Tree算法
樹(shù)路由機制是根據網(wǎng)絡(luò )地址和節點(diǎn)間的父子關(guān)系來(lái)實(shí)現路由的。如果目的地址設備不是該路由器的子孫，則直接將數據幀轉發(fā)給該路由器的父節點(diǎn)，其父節點(diǎn)將按照同樣的步驟進(jìn)行路由。
1．2．2 AODVjr算法
AODVjr是對AODV算法的一種簡(jiǎn)化改進(jìn)，當源節點(diǎn)要尋找到達目的節點(diǎn)的路徑時(shí)，先向其鄰居節點(diǎn)組播RREQ分組。收到該分組的鄰居節點(diǎn)若具備路由能力，則建立指向源節點(diǎn)的反向路由回復，同時(shí)繼續向自己的鄰居節點(diǎn)組播該RREQ分組。若不具備路由能力，則通過(guò)Cluster-Tree路由算法將該分組交由其子孫節點(diǎn)或父節點(diǎn)進(jìn)行轉發(fā)。當目的節點(diǎn)接收到此RREQ分組后，通過(guò)單播的方式向源節點(diǎn)回復RREP分組，同時(shí)，所有接收到此RREP分組的節點(diǎn)都將更新記錄自己的鄰居表，路由建立成功。實(shí)驗證明，AODVjr算法在保持了AODV原始功能的基礎上，控制開(kāi)銷(xiāo)比AODV算法更小，因此更節能。
1．2．3 Cluster-Tree+AODVjr算法
在此算法中，網(wǎng)絡(luò )中的節點(diǎn)被分成了4類(lèi)：Coordinator、RN+、RN-和RFD。其中RN+具有足夠的存儲空間和能力來(lái)進(jìn)行AODVjr協(xié)議；而RN-則因存儲空間受限，不能夠進(jìn)行AODVjr協(xié)議。Coordinator、RN+、RN-都具有路由功能，在通信時(shí)，如果目的節點(diǎn)不是鄰居節點(diǎn)，RN+將會(huì )啟動(dòng)AODVjr，主動(dòng)查找到達目地節點(diǎn)的最佳路徑；RN-節點(diǎn)只能通過(guò)樹(shù)路由算法來(lái)尋找下一跳的節點(diǎn)。仿真證明，采用Cluster-Tree和AODVjr相結合的路由協(xié)議在保證分組遞交率的情況下，具有比單獨使用其中一種路由協(xié)議更低的控制開(kāi)銷(xiāo)和平均時(shí)延。

2 優(yōu)化ZigBee路由算法
2．1 ZigBee路由算法問(wèn)題
Cluster-Tree算法必須按照簇樹(shù)型結構地址分配方式來(lái)尋址，路由效率低，并且源節點(diǎn)到目的節點(diǎn)的傳輸路徑由于跳數過(guò)多，會(huì )影響網(wǎng)絡(luò )時(shí)延。
AODVjr算法在路由發(fā)現過(guò)程中，會(huì )產(chǎn)生分組大量泛洪問(wèn)題。例如，當目的節點(diǎn)是源節點(diǎn)的子節點(diǎn)時(shí)，若采用AODVjr向鄰居節點(diǎn)發(fā)送RREQ分組，則向其父節點(diǎn)以上的節點(diǎn)發(fā)送RREQ分組是多余的；若目的節點(diǎn)不是源節點(diǎn)的子節點(diǎn)，則采用AODVjr向其子節點(diǎn)方向發(fā)送RREQ分組是多余的。假設網(wǎng)絡(luò )的最大深度是1，則數據幀可能被轉發(fā)的最長(cháng)路徑是21，因此當跳數大于21時(shí)，就應停止對RREQ分組的繼續廣播，將其丟棄；假設從源節點(diǎn)到目的節點(diǎn)的最小跳數為M，當RREQ分組被轉發(fā)的次數大于M時(shí)，再繼續轉發(fā)是多余的。由于每一次AODVjr路由都要產(chǎn)生大量的RREQ泛洪，因此會(huì )使節點(diǎn)能量消耗嚴重。
鑒于以上問(wèn)題，本文提出一種基于C+A算法的優(yōu)化路由算法，用以解決Cluster-Tree路由的低效率和AODVjr路由的泛洪嚴重及能量消耗問(wèn)題。
2．2 優(yōu)化路由算法思想
在一個(gè)傳感器網(wǎng)絡(luò )中，傳感節點(diǎn)只能和與它相鄰的，并且在它的射頻傳輸范圍之內的節點(diǎn)直接通信。樹(shù)型網(wǎng)絡(luò )中每個(gè)節點(diǎn)的鄰居表中都包含有其射頻覆蓋范圍內各個(gè)鄰居節點(diǎn)的相關(guān)信息。在優(yōu)化路由算法中利用鄰居表中記錄的有效信息，可以使源節點(diǎn)發(fā)送給目的節點(diǎn)的數據幀經(jīng)過(guò)一跳到達。
在A(yíng)ODVjr路由發(fā)現過(guò)程中，為了避免RREQ分組無(wú)選擇性的大量泛洪，在優(yōu)化路由算法中依據不同的情況，添加對RREQ分組廣播跳數的限制條件，使大于限制條件的多余路由不能啟用。這樣能有效地減少RREQ分組泛洪次數，縮小RREQ廣播范圍，限制RREQ分組傳播方向，從而降低網(wǎng)絡(luò )的能量消耗。
2．3 優(yōu)化路由算法設計
優(yōu)化路由算法的具體步驟如下：
①對樹(shù)型網(wǎng)絡(luò )進(jìn)行分區，并設定輔助變量number的初始值為1(number值代表分區次數)。分區原則如下：以協(xié)調器為根節點(diǎn)，將根節點(diǎn)的每一個(gè)子樹(shù)看作一個(gè)區域，并為其編號。記錄每一個(gè)區域中的最大地址Amax和最小地址Amin。由樹(shù)地址分配機制可以得出，在同一區域中的節點(diǎn)地址An均滿(mǎn)足Amin≤An≤Amax，即此區域的地址范圍是[Amin，Amax]，并且每一個(gè)區域的地址范圍之間是不相交關(guān)系，即一個(gè)確定的地址在且僅在一個(gè)區域內。
②判斷源節點(diǎn)的類(lèi)型。若為RFD則直接將數據幀轉發(fā)給其父節點(diǎn)；若為FFD則判斷目的節點(diǎn)是否為源節點(diǎn)的子節點(diǎn)。若是，則向下啟動(dòng)AODVjr路由轉發(fā)數據幀，并將RREQ分組的最大廣播跳數限制為|Dd-Ds|(Ds為源節點(diǎn)的網(wǎng)絡(luò )深度，Dd為目的節點(diǎn)的網(wǎng)絡(luò )深度)，超出范圍則丟棄；若不是，則進(jìn)行第下一步。
③源節點(diǎn)向鄰居節點(diǎn)發(fā)送RREQ分組，鄰居節點(diǎn)判斷自身地址是否與目的地址相等。如果相等，則向上層傳遞，由其上層對數據幀進(jìn)行解析，并將RREQ分組的最大廣播跳數限制為1，超出范圍則丟棄。如果不等，則進(jìn)行第④步。
④判斷目的地址在哪個(gè)區域中。若目的節點(diǎn)和源節點(diǎn)在同一區域中，進(jìn)行第⑥步；若不在同一區域中，則進(jìn)行第⑤步。
⑤判斷源節點(diǎn)的鄰居節點(diǎn)中是否有和目的節點(diǎn)在同一區域的節點(diǎn)。如果有，將數據幀轉發(fā)給該節點(diǎn)，并進(jìn)行第⑥步；如果沒(méi)有，則進(jìn)行第⑦步。
⑥number值加1。將目的節點(diǎn)所在區域看作一個(gè)樹(shù)型網(wǎng)絡(luò )，將其最小地址節點(diǎn)看作該樹(shù)的根節點(diǎn)，并按照第①步的分區原則將其進(jìn)行分區。判斷目的節點(diǎn)和當前節點(diǎn)是否在同一區域中。若是，重復第⑥步；若不是，則進(jìn)行第⑦步。
⑦將數據幀經(jīng)由樹(shù)路由轉發(fā)到第number次分組的根節點(diǎn)，然后啟動(dòng)AODVjr路由，由此根節點(diǎn)將RREQ分組廣播至目的節點(diǎn)的相應分組內，尋找目的節點(diǎn)，并將RREQ分組的最大廣播跳數限制為|Dd-number+1|，超出范圍則丟棄。