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

引言

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

1 ZigBee路由算法研究

依據(jù)設(shè)備的能力，ZigBee網(wǎng)絡(luò)中的設(shè)備可以分為全功能設(shè)備(Full Function Device，F(xiàn)FD)和半功能設(shè)備(Reduced Function Device，RFD)。FFD能轉(zhuǎn)發(fā)其他設(shè)備的數(shù)據(jù)幀，RFD則不能。當(dāng)FFD加入一個(gè)網(wǎng)絡(luò)時(shí)，它可以作為協(xié)調(diào)器。協(xié)調(diào)器會(huì)周期性地廣播數(shù)據(jù)幀，周?chē)�的RFD能夠發(fā)現(xiàn)并加入網(wǎng)絡(luò)，形成一個(gè)星型拓?fù)渚W(wǎng)絡(luò)。在星型拓?fù)渲�，協(xié)調(diào)器負(fù)責(zé)控制整個(gè)網(wǎng)絡(luò)，所有終端設(shè)備都直接與協(xié)調(diào)器通信，并且由它維護(hù)。

ZigBee網(wǎng)絡(luò)層還支持樹(shù)型和網(wǎng)狀網(wǎng)絡(luò)。樹(shù)型網(wǎng)絡(luò)采用分級(jí)路由的策略在網(wǎng)絡(luò)中傳送數(shù)據(jù)和控制信息，而網(wǎng)狀網(wǎng)絡(luò)則可以進(jìn)行點(diǎn)對(duì)點(diǎn)的通信。在樹(shù)型網(wǎng)絡(luò)中，根節(jié)點(diǎn)(協(xié)調(diào)器節(jié)點(diǎn))和所有的內(nèi)部節(jié)點(diǎn)(路由器節(jié)點(diǎn))是FFD，而RFD只能作為葉子節(jié)點(diǎn)(終端節(jié)點(diǎn))。當(dāng)協(xié)調(diào)器或路由器加入網(wǎng)絡(luò)時(shí)，它必須被分配唯一的網(wǎng)絡(luò)地址。

1．1 網(wǎng)絡(luò)地址分配

ZigBee協(xié)議規(guī)范使用一個(gè)分布式地址方案分配網(wǎng)絡(luò)地址，它設(shè)計(jì)為給每個(gè)潛在父節(jié)點(diǎn)提供一個(gè)有限的網(wǎng)絡(luò)地址子塊。當(dāng)一個(gè)設(shè)備成功加入網(wǎng)絡(luò)后，其父節(jié)點(diǎn)給該節(jié)點(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ù)路由機(jī)制是根據(jù)網(wǎng)絡(luò)地址和節(jié)點(diǎn)間的父子關(guān)系來(lái)實(shí)現(xiàn)路由的。如果目的地址設(shè)備不是該路由器的子孫，則直接將數(shù)據(jù)幀轉(zhuǎn)發(fā)給該路由器的父節(jié)點(diǎn)，其父節(jié)點(diǎn)將按照同樣的步驟進(jìn)行路由。

1．2．2 AODVjr算法

AODVjr是對(duì)AODV算法的一種簡(jiǎn)化改進(jìn)，當(dāng)源節(jié)點(diǎn)要尋找到達(dá)目的節(jié)點(diǎn)的路徑時(shí)，先向其鄰居節(jié)點(diǎn)組播RREQ分組。收到該分組的鄰居節(jié)點(diǎn)若具備路由能力，則建立指向源節(jié)點(diǎn)的反向路由回復(fù)，同時(shí)繼續(xù)向自己的鄰居節(jié)點(diǎn)組播該RREQ分組。若不具備路由能力，則通過(guò)Cluster-Tree路由算法將該分組交由其子孫節(jié)點(diǎn)或父節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)。當(dāng)目的節(jié)點(diǎn)接收到此RREQ分組后，通過(guò)單播的方式向源節(jié)點(diǎn)回復(fù)RREP分組，同時(shí)，所有接收到此RREP分組的節(jié)點(diǎn)都將更新記錄自己的鄰居表，路由建立成功。實(shí)驗(yàn)證明，AODVjr算法在保持了AODV原始功能的基礎(chǔ)上，控制開(kāi)銷(xiāo)比AODV算法更小，因此更節(jié)能。

1．2．3 Cluster-Tree+AODVjr算法

在此算法中，網(wǎng)絡(luò)中的節(jié)點(diǎn)被分成了4類(lèi)：Coordinator、RN+、RN-和RFD。其中RN+具有足夠的存儲(chǔ)空間和能力來(lái)進(jìn)行AODVjr協(xié)議；而RN-則因存儲(chǔ)空間受限，不能夠進(jìn)行AODVjr協(xié)議。Coordinator、RN+、RN-都具有路由功能，在通信時(shí)，如果目的節(jié)點(diǎn)不是鄰居節(jié)點(diǎn)，RN+將會(huì)啟動(dòng)AODVjr，主動(dòng)查找到達(dá)目地節(jié)點(diǎn)的最佳路徑；RN-節(jié)點(diǎn)只能通過(guò)樹(shù)路由算法來(lái)尋找下一跳的節(jié)點(diǎn)。仿真證明，采用Cluster-Tree和AODVjr相結(jié)合的路由協(xié)議在保證分組遞交率的情況下，具有比單獨(dú)使用其中一種路由協(xié)議更低的控制開(kāi)銷(xiāo)和平均時(shí)延。

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

2．1 ZigBee路由算法問(wèn)題

Cluster-Tree算法必須按照簇樹(shù)型結(jié)構(gòu)地址分配方式來(lái)尋址，路由效率低，并且源節(jié)點(diǎn)到目的節(jié)點(diǎn)的傳輸路徑由于跳數(shù)過(guò)多，會(huì)影響網(wǎng)絡(luò)時(shí)延。

AODVjr算法在路由發(fā)現(xiàn)過(guò)程中，會(huì)產(chǎn)生分組大量泛洪問(wèn)題。例如，當(dāng)目的節(jié)點(diǎn)是源節(jié)點(diǎn)的子節(jié)點(diǎn)時(shí)，若采用AODVjr向鄰居節(jié)點(diǎn)發(fā)送RREQ分組，則向其父節(jié)點(diǎn)以上的節(jié)點(diǎn)發(fā)送RREQ分組是多余的；若目的節(jié)點(diǎn)不是源節(jié)點(diǎn)的子節(jié)點(diǎn)，則采用AODVjr向其子節(jié)點(diǎn)方向發(fā)送RREQ分組是多余的。假設(shè)網(wǎng)絡(luò)的最大深度是1，則數(shù)據(jù)幀可能被轉(zhuǎn)發(fā)的最長(zhǎng)路徑是21，因此當(dāng)跳數(shù)大于21時(shí)，就應(yīng)停止對(duì)RREQ分組的繼續(xù)廣播，將其丟棄；假設(shè)從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最小跳數(shù)為M，當(dāng)RREQ分組被轉(zhuǎn)發(fā)的次數(shù)大于M時(shí)，再繼續(xù)轉(zhuǎn)發(fā)是多余的。由于每一次AODVjr路由都要產(chǎn)生大量的RREQ泛洪，因此會(huì)使節(jié)點(diǎn)能量消耗嚴(yán)重。

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

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

在一個(gè)傳感器網(wǎng)絡(luò)中，傳感節(jié)點(diǎn)只能和與它相鄰的，并且在它的射頻傳輸范圍之內(nèi)的節(jié)點(diǎn)直接通信。樹(shù)型網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的鄰居表中都包含有其射頻覆蓋范圍內(nèi)各個(gè)鄰居節(jié)點(diǎn)的相關(guān)信息。在優(yōu)化路由算法中利用鄰居表中記錄的有效信息，可以使源節(jié)點(diǎn)發(fā)送給目的節(jié)點(diǎn)的數(shù)據(jù)幀經(jīng)過(guò)一跳到達(dá)。

在AODVjr路由發(fā)現(xiàn)過(guò)程中，為了避免RREQ分組無(wú)選擇性的大量泛洪，在優(yōu)化路由算法中依據(jù)不同的情況，添加對(duì)RREQ分組廣播跳數(shù)的限制條件，使大于限制條件的多余路由不能啟用。這樣能有效地減少RREQ分組泛洪次數(shù)，縮小RREQ廣播范圍，限制RREQ分組傳播方向，從而降低網(wǎng)絡(luò)的能量消耗。

2．3 優(yōu)化路由算法設(shè)計(jì)

優(yōu)化路由算法的具體步驟如下：

①對(duì)樹(shù)型網(wǎng)絡(luò)進(jìn)行分區(qū)，并設(shè)定輔助變量number的初始值為1(number值代表分區(qū)次數(shù))。分區(qū)原則如下：以協(xié)調(diào)器為根節(jié)點(diǎn)，將根節(jié)點(diǎn)的每一個(gè)子樹(shù)看作一個(gè)區(qū)域，并為其編號(hào)。記錄每一個(gè)區(qū)域中的最大地址Amax和最小地址Amin。由樹(shù)地址分配機(jī)制可以得出，在同一區(qū)域中的節(jié)點(diǎn)地址An均滿(mǎn)足Amin≤An≤Amax，即此區(qū)域的地址范圍是[Amin，Amax]，并且每一個(gè)區(qū)域的地址范圍之間是不相交關(guān)系，即一個(gè)確定的地址在且僅在一個(gè)區(qū)域內(nèi)。

②判斷源節(jié)點(diǎn)的類(lèi)型。若為RFD則直接將數(shù)據(jù)幀轉(zhuǎn)發(fā)給其父節(jié)點(diǎn)；若為FFD則判斷目的節(jié)點(diǎn)是否為源節(jié)點(diǎn)的子節(jié)點(diǎn)。若是，則向下啟動(dòng)AODVjr路由轉(zhuǎn)發(fā)數(shù)據(jù)幀，并將RREQ分組的最大廣播跳數(shù)限制為|Dd-Ds|(Ds為源節(jié)點(diǎn)的網(wǎng)絡(luò)深度，Dd為目的節(jié)點(diǎn)的網(wǎng)絡(luò)深度)，超出范圍則丟棄；若不是，則進(jìn)行第下一步。

③源節(jié)點(diǎn)向鄰居節(jié)點(diǎn)發(fā)送RREQ分組，鄰居節(jié)點(diǎn)判斷自身地址是否與目的地址相等。如果相等，則向上層傳遞，由其上層對(duì)數(shù)據(jù)幀進(jìn)行解析，并將RREQ分組的最大廣播跳數(shù)限制為1，超出范圍則丟棄。如果不等，則進(jìn)行第④步。

④判斷目的地址在哪個(gè)區(qū)域中。若目的節(jié)點(diǎn)和源節(jié)點(diǎn)在同一區(qū)域中，進(jìn)行第⑥步；若不在同一區(qū)域中，則進(jìn)行第⑤步。

⑤判斷源節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中是否有和目的節(jié)點(diǎn)在同一區(qū)域的節(jié)點(diǎn)。如果有，將數(shù)據(jù)幀轉(zhuǎn)發(fā)給該節(jié)點(diǎn)，并進(jìn)行第⑥步；如果沒(méi)有，則進(jìn)行第⑦步。

⑥number值加1。將目的節(jié)點(diǎn)所在區(qū)域看作一個(gè)樹(shù)型網(wǎng)絡(luò)，將其最小地址節(jié)點(diǎn)看作該樹(shù)的根節(jié)點(diǎn)，并按照第①步的分區(qū)原則將其進(jìn)行分區(qū)。判斷目的節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)是否在同一區(qū)域中。若是，重復(fù)第⑥步；若不是，則進(jìn)行第⑦步。

⑦將數(shù)據(jù)幀經(jīng)由樹(shù)路由轉(zhuǎn)發(fā)到第number次分組的根節(jié)點(diǎn)，然后啟動(dòng)AODVjr路由，由此根節(jié)點(diǎn)將RREQ分組廣播至目的節(jié)點(diǎn)的相應(yīng)分組內(nèi)，尋找目的節(jié)點(diǎn)，并將RREQ分組的最大廣播跳數(shù)限制為|Dd-number+1|，超出范圍則丟棄。

目的節(jié)點(diǎn)接收到RREQ分組后，將向?qū)ふ衣酚傻脑垂?jié)點(diǎn)回復(fù)一個(gè)RREP分組，其傳送路徑為路由建立過(guò)程的反向路由。所有接收到RREP分組的節(jié)點(diǎn)將此路由信息替換并且記錄，正向路由從源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)建立成功。優(yōu)化路由算法的流程圖如圖1所示。

具體實(shí)現(xiàn)過(guò)程舉例如下：假設(shè)一樹(shù)型網(wǎng)絡(luò)，網(wǎng)絡(luò)參數(shù)Cm=4，Lm=4，Rm=3，依據(jù)前面的網(wǎng)絡(luò)地址分配方式給網(wǎng)絡(luò)中各節(jié)點(diǎn)分配相應(yīng)地址，選定源節(jié)點(diǎn)為37，在其射頻覆蓋范圍內(nèi)的鄰居節(jié)點(diǎn)是25、36和90。具體網(wǎng)絡(luò)節(jié)點(diǎn)分布圖如圖2所示。

　　首先將樹(shù)型網(wǎng)絡(luò)按照自定義的方式進(jìn)行分區(qū)，分區(qū)后的網(wǎng)絡(luò)如圖3所示。其中，原樹(shù)型網(wǎng)絡(luò)被分為I、II、III、IV4個(gè)區(qū)域。

樹(shù)型網(wǎng)絡(luò)的分區(qū)步驟如下：

①當(dāng)目的節(jié)點(diǎn)是41時(shí)，直接轉(zhuǎn)發(fā)，并將RREQ分組傳播跳數(shù)限制為|4-3|=1。

②當(dāng)目的節(jié)點(diǎn)是90時(shí)，由于90是源節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，直接將數(shù)據(jù)幀轉(zhuǎn)發(fā)，并將RREQ分組傳播跳數(shù)限制為1。

③當(dāng)目的節(jié)點(diǎn)是8時(shí)，由于目的節(jié)點(diǎn)和源節(jié)點(diǎn)屬于同一區(qū)域I，則number=number+1，即number=2。并且將區(qū)域I繼續(xù)分區(qū)，第二次分區(qū)后的樹(shù)型網(wǎng)絡(luò)如圖4所示。此時(shí)，節(jié)點(diǎn)8和節(jié)點(diǎn)37不屬于同一區(qū)域，則將數(shù)據(jù)幀沿樹(shù)路由轉(zhuǎn)發(fā)給第2次分區(qū)的根節(jié)點(diǎn)，即節(jié)點(diǎn)1。然后，由節(jié)點(diǎn)1向區(qū)域I-1內(nèi)的節(jié)點(diǎn)廣播RREQ分組，并限制RREQ分組的跳數(shù)為|Dd-number+1|=2。

④當(dāng)目的節(jié)點(diǎn)是72時(shí)，由于鄰居節(jié)點(diǎn)中有和目的節(jié)點(diǎn)同區(qū)域的節(jié)點(diǎn)90，則先將數(shù)據(jù)幀轉(zhuǎn)發(fā)給節(jié)點(diǎn)90，然后再由其通過(guò)和③類(lèi)似的步驟轉(zhuǎn)發(fā)給目的節(jié)點(diǎn)。

3 仿真與實(shí)驗(yàn)結(jié)果分析

為了比較優(yōu)化算法與C+A算法的性能，在相同的仿真環(huán)境下分別對(duì)兩種算法進(jìn)行了仿真，重點(diǎn)比較了兩者在網(wǎng)絡(luò)剩余節(jié)點(diǎn)數(shù)、路由平均跳數(shù)、數(shù)據(jù)包發(fā)送成功率及端到端時(shí)延等方面的差別。仿真結(jié)果表明，該優(yōu)化算法具有更優(yōu)越的性能。但是在節(jié)點(diǎn)數(shù)目相同的情況下，優(yōu)化算法的傳輸時(shí)延還是比C+A算法要小很多。這是因?yàn)樗惴▋?yōu)化后，數(shù)據(jù)幀從源節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)的傳輸路徑變短，因而傳輸時(shí)延減少。

結(jié)語(yǔ)

在分析了ZigBee路由協(xié)議中Cluster-Tree和AODVjr算法的基礎(chǔ)上，提出了一種基于C+A算法的優(yōu)化路由算法。優(yōu)化路由算法利用ZigBee協(xié)議中的鄰居表，使數(shù)據(jù)幀的傳送跳數(shù)減少，并通過(guò)將樹(shù)型網(wǎng)絡(luò)自定義分區(qū)，來(lái)控制路由發(fā)現(xiàn)過(guò)程中RREQ分組傳播的跳數(shù)，從而防止無(wú)效的RREQ泛洪，節(jié)省了網(wǎng)絡(luò)的能量。仿真結(jié)果證明，優(yōu)化的路由算法能夠有效地減小路由跳數(shù)，延長(zhǎng)網(wǎng)絡(luò)的壽命，提高路由效率，從而使網(wǎng)絡(luò)整體能耗減低。

作者：曹 越 胡方明 黨妮 來(lái)源：現(xiàn)代電子技術(shù)