摘要：通過分析ZigBee協(xié)議中Cluster-Tree和AODVjr算法的優(yōu)缺點，提出一種基于Cluster-Tree+AODVjr的優(yōu)化路由算法。該算法利用ZigB ee協(xié)議中的鄰居表，通過定義分區(qū)來確定目的節(jié)點的范圍，從而控制廣播RREQ分組的跳數(shù)，防止無效的RREQ泛洪。此優(yōu)化算法能夠有效地減小路由跳數(shù)，縮短傳輸時延，減少網(wǎng)絡中死亡節(jié)點的數(shù)量，提高數(shù)據(jù)傳送的成功率。
關(guān)鍵詞：ZigBee；路由算法；Cluster-Ttee+AODVjr；鄰居表；分組
引言
無線通信和嵌入式微傳感器技術(shù)的快速發(fā)展促進了無線傳感器網(wǎng)絡的崛起。ZigBee協(xié)議基于IEEE 802．15．4無線標準制定，包括應用層、網(wǎng)絡層、安全層等，實現(xiàn)了網(wǎng)絡的自組織和自維護的功能。在無線傳感器網(wǎng)絡中，節(jié)點的能量是有限的，如果節(jié)點在最后因為自身的能量消耗殆盡而死亡，將會對整個網(wǎng)絡的傳輸性能造成很大影響。因此，在實際應用中，根據(jù)不同的網(wǎng)絡情況來選擇最符合應用需求的路由協(xié)議，讓路由協(xié)議根據(jù)網(wǎng)絡拓撲選擇合適的路徑，平均分布節(jié)點的傳輸能量，降低網(wǎng)絡的功耗是網(wǎng)絡層必須要考慮的任務。
1 ZigBee路由算法研究
依據(jù)設備的能力，ZigBee網(wǎng)絡中的設備可以分為全功能設備（Full FuncTIon Device，F(xiàn)FD）和半功能設備（Reduced FuncTIon Device，RFD）。FFD能轉(zhuǎn)發(fā)其他設備的數(shù)據(jù)幀，RFD則不能。當FFD加入一個網(wǎng)絡時，它可以作為協(xié)調(diào)器。協(xié)調(diào)器會周期性地廣播數(shù)據(jù)幀，周圍的RFD能夠發(fā)現(xiàn)并加入網(wǎng)絡，形成一個星型拓撲網(wǎng)絡。在星型拓撲中，協(xié)調(diào)器負責控制整個網(wǎng)絡，所有終端設備都直接與協(xié)調(diào)器通信，并且由它維護。
ZigBee網(wǎng)絡層還支持樹型和網(wǎng)狀網(wǎng)絡。樹型網(wǎng)絡采用分級路由的策略在網(wǎng)絡中傳送數(shù)據(jù)和控制信息，而網(wǎng)狀網(wǎng)絡則可以進行點對點的通信。在樹型網(wǎng)絡中，根節(jié)點（協(xié)調(diào)器節(jié)點）和所有的內(nèi)部節(jié)點（路由器節(jié)點）是FFD，而RFD只能作為葉子節(jié)點（終端節(jié)點）。當協(xié)調(diào)器或路由器加入網(wǎng)絡時，它必須被分配唯一的網(wǎng)絡地址。
1．1 網(wǎng)絡地址分配
ZigBee協(xié)議規(guī)范使用一個分布式地址方案分配網(wǎng)絡地址，它設計為給每個潛在父節(jié)點提供一個有限的網(wǎng)絡地址子塊。當一個設備成功加入網(wǎng)絡后，其父節(jié)點給該節(jié)點自動分配一個唯一的網(wǎng)絡地址。
1．2 ZigBee路由算法
網(wǎng)絡層支持Cluster-Tree、AODVjr和Cluster-Tree+AODVjr算法（以下簡稱C+A算法）等多種路由算法，因此ZigBee網(wǎng)絡的路由協(xié)議兼具樹型網(wǎng)絡和網(wǎng)狀網(wǎng)絡的特性。
1．2．1 Cluster-Tree算法
樹路由機制是根據(jù)網(wǎng)絡地址和節(jié)點間的父子關(guān)系來實現(xiàn)路由的。如果目的地址設備不是該路由器的子孫，則直接將數(shù)據(jù)幀轉(zhuǎn)發(fā)給該路由器的父節(jié)點，其父節(jié)點將按照同樣的步驟進行路由。
1．2．2 AODVjr算法
AODVjr是對AODV算法的一種簡化改進，當源節(jié)點要尋找到達目的節(jié)點的路徑時，先向其鄰居節(jié)點組播RREQ分組。收到該分組的鄰居節(jié)點若具備路由能力，則建立指向源節(jié)點的反向路由回復，同時繼續(xù)向自己的鄰居節(jié)點組播該RREQ分組。若不具備路由能力，則通過Cluster-Tree路由算法將該分組交由其子孫節(jié)點或父節(jié)點進行轉(zhuǎn)發(fā)。當目的節(jié)點接收到此RREQ分組后，通過單播的方式向源節(jié)點回復RREP分組，同時，所有接收到此RREP分組的節(jié)點都將更新記錄自己的鄰居表，路由建立成功。實驗證明，AODVjr算法在保持了AODV原始功能的基礎上，控制開銷比AODV算法更小，因此更節(jié)能。
1．2．3 Cluster-Tree+AODVjr算法
在此算法中，網(wǎng)絡中的節(jié)點被分成了4類：Coordinator、RN+、RN-和RFD。其中RN+具有足夠的存儲空間和能力來進行AODVjr協(xié)議；而RN-則因存儲空間受限，不能夠進行AODVjr協(xié)議。Coordinator、RN+、RN-都具有路由功能，在通信時，如果目的節(jié)點不是鄰居節(jié)點，RN+將會啟動AODVjr，主動查找到達目地節(jié)點的最佳路徑；RN-節(jié)點只能通過樹路由算法來尋找下一跳的節(jié)點。仿真證明，采用Cluster-Tree和AODVjr相結(jié)合的路由協(xié)議在保證分組遞交率的情況下，具有比單獨使用其中一種路由協(xié)議更低的控制開銷和平均時延。
2 優(yōu)化ZigBee路由算法
2．1 ZigBee路由算法問題
Cluster-Tree算法必須按照簇樹型結(jié)構(gòu)地址分配方式來尋址，路由效率低，并且源節(jié)點到目的節(jié)點的傳輸路徑由于跳數(shù)過多，會影響網(wǎng)絡時延。
AODVjr算法在路由發(fā)現(xiàn)過程中，會產(chǎn)生分組大量泛洪問題。例如，當目的節(jié)點是源節(jié)點的子節(jié)點時，若采用AODVjr向鄰居節(jié)點發(fā)送RREQ分組，則向其父節(jié)點以上的節(jié)點發(fā)送RREQ分組是多余的；若目的節(jié)點不是源節(jié)點的子節(jié)點，則采用AODVjr向其子節(jié)點方向發(fā)送RREQ分組是多余的。假設網(wǎng)絡的最大深度是1，則數(shù)據(jù)幀可能被轉(zhuǎn)發(fā)的最長路徑是21，因此當跳數(shù)大于21時，就應停止對RREQ分組的繼續(xù)廣播，將其丟棄；假設從源節(jié)點到目的節(jié)點的最小跳數(shù)為M，當RREQ分組被轉(zhuǎn)發(fā)的次數(shù)大于M時，再繼續(xù)轉(zhuǎn)發(fā)是多余的。由于每一次AODVjr路由都要產(chǎn)生大量的RREQ泛洪，因此會使節(jié)點能量消耗嚴重。
鑒于以上問題，本文提出一種基于C+A算法的優(yōu)化路由算法，用以解決Cluster-Tree路由的低效率和AODVjr路由的泛洪嚴重及能量消耗問題。
2．2 優(yōu)化路由算法思想
在一個傳感器網(wǎng)絡中，傳感節(jié)點只能和與它相鄰的，并且在它的射頻傳輸范圍之內(nèi)的節(jié)點直接通信。樹型網(wǎng)絡中每個節(jié)點的鄰居表中都包含有其射頻覆蓋范圍內(nèi)各個鄰居節(jié)點的相關(guān)信息。在優(yōu)化路由算法中利用鄰居表中記錄的有效信息，可以使源節(jié)點發(fā)送給目的節(jié)點的數(shù)據(jù)幀經(jīng)過一跳到達。
在AODVjr路由發(fā)現(xiàn)過程中，為了避免RREQ分組無選擇性的大量泛洪，在優(yōu)化路由算法中依據(jù)不同的情況，添加對RREQ分組廣播跳數(shù)的限制條件，使大于限制條件的多余路由不能啟用。這樣能有效地減少RREQ分組泛洪次數(shù)，縮小RREQ廣播范圍，限制RREQ分組傳播方向，從而降低網(wǎng)絡的能量消耗。
2．3 優(yōu)化路由算法設計
優(yōu)化路由算法的具體步驟如下：
?、賹湫途W(wǎng)絡進行分區(qū)，并設定輔助變量number的初始值為1（number值代表分區(qū)次數(shù)）。分區(qū)原則如下：以協(xié)調(diào)器為根節(jié)點，將根節(jié)點的每一個子樹看作一個區(qū)域，并為其編號。記錄每一個區(qū)域中的最大地址Amax和最小地址Amin。由樹地址分配機制可以得出，在同一區(qū)域中的節(jié)點地址An均滿足Amin≤An≤Amax，即此區(qū)域的地址范圍是［Amin，Amax］，并且每一個區(qū)域的地址范圍之間是不相交關(guān)系，即一個確定的地址在且僅在一個區(qū)域內(nèi)。
②判斷源節(jié)點的類型。若為RFD則直接將數(shù)據(jù)幀轉(zhuǎn)發(fā)給其父節(jié)點；若為FFD則判斷目的節(jié)點是否為源節(jié)點的子節(jié)點。若是，則向下啟動AODVjr路由轉(zhuǎn)發(fā)數(shù)據(jù)幀，并將RREQ分組的最大廣播跳數(shù)限制為|Dd-Ds|（Ds為源節(jié)點的網(wǎng)絡深度，Dd為目的節(jié)點的網(wǎng)絡深度），超出范圍則丟棄；若不是，則進行第下一步。
?、墼垂?jié)點向鄰居節(jié)點發(fā)送RREQ分組，鄰居節(jié)點判斷自身地址是否與目的地址相等。如果相等，則向上層傳遞，由其上層對數(shù)據(jù)幀進行解析，并將RREQ分組的最大廣播跳數(shù)限制為1，超出范圍則丟棄。如果不等，則進行第④步。
?、芘袛嗄康牡刂吩谀膫€區(qū)域中。若目的節(jié)點和源節(jié)點在同一區(qū)域中，進行第⑥步；若不在同一區(qū)域中，則進行第⑤步。
?、菖袛嘣垂?jié)點的鄰居節(jié)點中是否有和目的節(jié)點在同一區(qū)域的節(jié)點。如果有，將數(shù)據(jù)幀轉(zhuǎn)發(fā)給該節(jié)點，并進行第⑥步；如果沒有，則進行第⑦步。
?、辬umber值加1。將目的節(jié)點所在區(qū)域看作一個樹型網(wǎng)絡，將其最小地址節(jié)點看作該樹的根節(jié)點，并按照第①步的分區(qū)原則將其進行分區(qū)。判斷目的節(jié)點和當前節(jié)點是否在同一區(qū)域中。若是，重復第⑥步；若不是，則進行第⑦步。
?、邔?shù)據(jù)幀經(jīng)由樹路由轉(zhuǎn)發(fā)到第number次分組的根節(jié)點，然后啟動AODVjr路由，由此根節(jié)點將RREQ分組廣播至目的節(jié)點的相應分組內(nèi)，尋找目的節(jié)點，并將RREQ分組的最大廣播跳數(shù)限制為|Dd-number+1|，超出范圍則丟棄。
下載文檔
