基于“新型核心樹(shù)自組織動(dòng)態(tài)路由算法”的改進(jìn)算法

摘要：本文說(shuō)明了無(wú)線Mesh網(wǎng)和Ad hoc網(wǎng)路由協(xié)議的特殊性，并簡(jiǎn)單介紹了無(wú)線Mesh網(wǎng)和Ad hoc網(wǎng)路由協(xié)議存在的現(xiàn)狀。對(duì)一種“新型核心樹(shù)自組織動(dòng)態(tài)路由算法”從理論上做了較為詳細(xì)的分析，提出了一些問(wèn)題，并在此之上給出一些建議，對(duì)算法做了些改進(jìn)，從而期望得到更進(jìn)一步完善的路由算法。

關(guān)鍵詞：無(wú)線Mesh；Ad hoc網(wǎng)絡(luò)；路由算法

中圖分類(lèi)號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2008)17-21467-02

1 引言

無(wú)線Mesh網(wǎng)和Ad hoc網(wǎng)是一種不依靠固定網(wǎng)絡(luò)設(shè)備，而由各節(jié)點(diǎn)通過(guò)無(wú)線信道傳輸可自組織，能動(dòng)態(tài)路由的網(wǎng)絡(luò)。由于此類(lèi)網(wǎng)絡(luò)節(jié)點(diǎn)頻繁動(dòng)態(tài)變化的性質(zhì)，因此這就對(duì)如何設(shè)計(jì)一個(gè)高性能的路由算法及協(xié)議提出了更高的要求。無(wú)線網(wǎng)絡(luò)技術(shù)發(fā)展至今，各種有關(guān)Ad hoc與無(wú)線Mesh網(wǎng)絡(luò)的路由協(xié)議正逐步完善，使用較廣泛的如：目的序列距離矢量路由協(xié)議（DSDV）， 按需距離矢量路由協(xié)議（AODV）， 動(dòng)態(tài)源路由協(xié)議（DSR）等。本文基于一種新型的核心樹(shù)自組織動(dòng)態(tài)路由算法的分析，給出一些新的建議及改進(jìn)算法。

2 無(wú)線網(wǎng)動(dòng)態(tài)路由協(xié)議的特點(diǎn)及要求

無(wú)線Mesh網(wǎng)和Ad hoc網(wǎng)具許多不同于常規(guī)有線網(wǎng)絡(luò)的諸多特性，這些特性對(duì)路由協(xié)議提出了更多的要求，主要特性有：

2.1 頻繁變化的拓?fù)浣Y(jié)構(gòu)

無(wú)線Mesh網(wǎng)和Ad hoc網(wǎng)中節(jié)點(diǎn)的任意移動(dòng)導(dǎo)致拓?fù)浣Y(jié)構(gòu)隨機(jī)，快速的變化，使得傳統(tǒng)的路由協(xié)議中各節(jié)點(diǎn)交換的路由信息大大增加，并且會(huì)使路由信息的收斂性存在嚴(yán)重的問(wèn)題。

2.2 帶寬資源受限，鏈路容量變化不定

無(wú)線網(wǎng)絡(luò)的帶寬資源較有線網(wǎng)絡(luò)有限的多，再加上多址接入，衰落和干擾等因素，帶寬將更為緊張。這就要求網(wǎng)絡(luò)中發(fā)送的路由信息要盡可能的少，從而節(jié)省帶寬。

2.3 安全可靠性

無(wú)線Mesh網(wǎng)和Ad hoc網(wǎng)是容易受到攻擊的，而對(duì)于分布式控制方式的特性使其在受到攻擊時(shí)有一定的自恢復(fù)能力。所以要求在路由設(shè)計(jì)時(shí)，對(duì)網(wǎng)絡(luò)受到攻擊時(shí)能迅速找到新的傳輸路徑。

根據(jù)以上特性要求在設(shè)計(jì)無(wú)線Mesh網(wǎng)和Ad hoc網(wǎng)協(xié)議時(shí)，不僅要考慮傳統(tǒng)路由協(xié)議的最優(yōu)性、簡(jiǎn)單、健壯、穩(wěn)定、低開(kāi)銷(xiāo)、快速收斂、適應(yīng)性強(qiáng)外，還應(yīng)具有以下要求：

(1)分布式運(yùn)行：要求在網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)既充當(dāng)通信終端又承擔(dān)路由任務(wù)，路由協(xié)議在每個(gè)節(jié)點(diǎn)上都有相應(yīng)的處理。

(2)收斂迅速：無(wú)線Mesh網(wǎng)和Ad hoc網(wǎng)的拓?fù)浣Y(jié)構(gòu)是動(dòng)態(tài)的，隨時(shí)處于變化狀態(tài)，所以要求我們的路由協(xié)議對(duì)拓?fù)涞淖兓哂锌焖俜从车哪芰Γ芗皶r(shí)更新路由信息。

(3)盡量控制路由信息傳輸開(kāi)銷(xiāo)：無(wú)線網(wǎng)絡(luò)中傳輸帶寬有限，路由信息的傳輸必然會(huì)占用一定的帶寬，為了更有效的利用帶寬，需要減小這種開(kāi)銷(xiāo)。

(4)簡(jiǎn)單實(shí)用性：簡(jiǎn)單有助于提高安全可靠性，簡(jiǎn)單還能減少各種開(kāi)銷(xiāo)。

目前的各種協(xié)議很難完全做到上述要求，各有優(yōu)缺點(diǎn)，協(xié)議在不同的場(chǎng)合要求也不盡相同，只有在研究中逐步的的完善。下面是對(duì)其中一種路由算法的分析及建議。

3 新型核心樹(shù)自組織動(dòng)態(tài)路由算法[1]的分析

該算法包括核心樹(shù)的生成過(guò)程、核心樹(shù)的動(dòng)態(tài)維護(hù)過(guò)程和基于核心樹(shù)的路由選擇過(guò)程。

核心樹(shù)的生成過(guò)程采用以下步驟：

步驟1確定根節(jié)點(diǎn)，根節(jié)點(diǎn)可以由手動(dòng)指定或自動(dòng)選擇，將根節(jié)點(diǎn)選擇為與有線網(wǎng)絡(luò)連接的節(jié)點(diǎn)，在沒(méi)有有線網(wǎng)絡(luò)連接的情況下，可以選擇為接近有線網(wǎng)絡(luò)區(qū)域中心的任意一個(gè)節(jié)點(diǎn)；

步驟2:樹(shù)節(jié)點(diǎn)周期地在無(wú)線信道上廣播樹(shù)的維護(hù)消息，收到樹(shù)的維護(hù)消息的試圖加入核心樹(shù)的孤立節(jié)點(diǎn)依據(jù)樹(shù)的生成策略（“最高級(jí)別策略”或“最近最快策略” ），選擇自己的候選父節(jié)點(diǎn)，并通過(guò)“三次握手”的加入交互機(jī)制與其中一個(gè)候選父節(jié)點(diǎn)建立父子鄰居關(guān)系；

步驟3:孤立節(jié)點(diǎn)成為樹(shù)節(jié)點(diǎn)后，將自己定級(jí)為Ｎ＋１，其中，Ｎ是父節(jié)點(diǎn)的級(jí)別；父節(jié)點(diǎn)將新節(jié)點(diǎn)的加入情況通告給更上一級(jí)的父節(jié)點(diǎn)，同時(shí)，新加入的樹(shù)節(jié)點(diǎn)開(kāi)始在無(wú)線信道上廣播樹(shù)的維護(hù)消息；

步驟4:重復(fù)步驟2、3，直到所有收到樹(shù)的維護(hù)消息的孤立節(jié)點(diǎn)都加入到核心樹(shù)中；

核心樹(shù)的動(dòng)態(tài)維護(hù)過(guò)程采用以下步驟：

步驟1:樹(shù)節(jié)點(diǎn)定期檢查與父節(jié)點(diǎn)和子節(jié)點(diǎn)的關(guān)系存續(xù)狀態(tài)（可以通過(guò)定期的消息交換或這些節(jié)點(diǎn)發(fā)生通信的情況來(lái)進(jìn)行）；

步驟2:根據(jù)步驟1的檢查結(jié)果，

(1)如果樹(shù)節(jié)點(diǎn)檢測(cè)到與某個(gè)子節(jié)點(diǎn)的通信關(guān)系不存在了（如子節(jié)點(diǎn)移動(dòng)出無(wú)線覆蓋范圍），就將該鄰居從自己的鄰居記錄中刪除，并向父節(jié)點(diǎn)報(bào)告；

(2)當(dāng)樹(shù)節(jié)點(diǎn)發(fā)現(xiàn)與父節(jié)點(diǎn)的通信關(guān)系不存在了，則將這一情況通告其所有的子節(jié)點(diǎn)，促使這些子節(jié)點(diǎn)重新開(kāi)始一次加入過(guò)程；父節(jié)點(diǎn)的丟失將觸發(fā)本節(jié)點(diǎn)及所有子孫節(jié)點(diǎn)的重加入過(guò)程；

基于核心樹(shù)的路由選擇過(guò)程采用以下步驟：

對(duì)于一次從源節(jié)點(diǎn)經(jīng)由若干中繼節(jié)點(diǎn)到目的節(jié)點(diǎn)的通信，樹(shù)節(jié)點(diǎn)的路由選擇方法如下：

步驟1:節(jié)點(diǎn)查找自己的子孫節(jié)點(diǎn)記錄；

步驟2:根據(jù)步驟１的查找結(jié)果：（1）如果有目的節(jié)點(diǎn)，就直接沿相應(yīng)的下行樹(shù)枝送到該節(jié)點(diǎn)；（2）如果目的節(jié)點(diǎn)不在子孫節(jié)點(diǎn)記錄中，則把數(shù)據(jù)沿上行樹(shù)枝遞交給父節(jié)點(diǎn)，由父節(jié)點(diǎn)重復(fù)以上過(guò)程向目的節(jié)點(diǎn)轉(zhuǎn)交；（3）如果目的地址位于有線網(wǎng)絡(luò)中，那么，不管源節(jié)點(diǎn)位于核心樹(shù)中的任何位置，數(shù)據(jù)最終都將通過(guò)上行樹(shù)枝匯聚到根節(jié)點(diǎn)，再由根節(jié)點(diǎn)轉(zhuǎn)交到有線網(wǎng)絡(luò)。

對(duì)于此算法可很好的實(shí)現(xiàn)無(wú)環(huán)路由，具有收斂迅速，可靠性較高的特點(diǎn)，但是理論上存在如下問(wèn)題：

(1)在生成核心樹(shù)的過(guò)程中如有圖一情況時(shí)會(huì)生成這樣一個(gè)樹(shù)：

A(B(E)、C(D))，而各節(jié)點(diǎn)只保存子節(jié)點(diǎn)與父節(jié)點(diǎn)信息。若按照上述路由算法，有D向E發(fā)送信息則需經(jīng)過(guò)B、A、C轉(zhuǎn)發(fā)，然而D，E是在同一個(gè)信號(hào)范圍內(nèi)，可直接建立信道傳輸，最優(yōu)的路徑應(yīng)該是D—E。由此類(lèi)推可知：會(huì)出現(xiàn)2個(gè)可直接建立通信信道進(jìn)行傳輸?shù)慕狱c(diǎn)需經(jīng)過(guò)N次轉(zhuǎn)發(fā)。

(2)樹(shù)的維護(hù)中，采用檢測(cè)與某個(gè)子節(jié)點(diǎn)的通信關(guān)系來(lái)進(jìn)行路由表的更新的方法，會(huì)對(duì)更新的速度有一定的影響，需要對(duì)什么樣的子節(jié)點(diǎn)進(jìn)行通信檢測(cè)，應(yīng)該做更進(jìn)一步的說(shuō)明，例如：A節(jié)點(diǎn)級(jí)別為N，若檢測(cè)與其一個(gè)2N的子節(jié)點(diǎn)的通信，這樣用在檢測(cè)上就會(huì)花費(fèi)很多的時(shí)間，直接影響收斂的速度。

(3)在路由算法上，上述算法可能會(huì)導(dǎo)致對(duì)某一條信道的利用率非常的高，可能同時(shí)N條信息在一條信道上傳輸而其它通信路徑空閑，實(shí)際上其它信道也是可以利用的。例如圖2中若有A與D、E、F，I與D、E、F的通信都會(huì)選擇A—B這個(gè)信道，這樣導(dǎo)致多條通信共用一個(gè)信道，而A—C空閑。

4 算法改進(jìn)

基于上述分析可對(duì)“新型核心樹(shù)自組織動(dòng)態(tài)路由算法”做如下改進(jìn)：

(1)在核心樹(shù)生成的過(guò)程中，新節(jié)點(diǎn)加入選擇父節(jié)點(diǎn)時(shí)，優(yōu)先考慮“最高級(jí)別策略”，若在信號(hào)范圍內(nèi)出現(xiàn)多個(gè)級(jí)別相同節(jié)點(diǎn)的時(shí)候，把多個(gè)節(jié)點(diǎn)都作為此節(jié)點(diǎn)的父節(jié)點(diǎn)。如圖2采用此方法生成的樹(shù)則變?yōu)閳D3所示。

(2)對(duì)節(jié)點(diǎn)路由表可做如下處理：

①每個(gè)節(jié)點(diǎn)保存其直接父節(jié)點(diǎn)和所有子節(jié)點(diǎn)信息，應(yīng)保存相關(guān)節(jié)點(diǎn)信息的名稱(chēng)及級(jí)別。

②保存所有能夠直接建立通信的節(jié)點(diǎn)信息，稱(chēng)為鄰接節(jié)點(diǎn)表

(3)在節(jié)點(diǎn)刪除中，采用讓所有節(jié)點(diǎn)檢查其路由表中鄰接節(jié)點(diǎn)表是否有節(jié)點(diǎn)移出，若有，采用“新型核心樹(shù)自組織動(dòng)態(tài)路由算法”中方法進(jìn)行刪除。

5 路由算法

①若A節(jié)點(diǎn)與B節(jié)點(diǎn)進(jìn)行通信時(shí)，先檢查A節(jié)點(diǎn)的鄰接節(jié)點(diǎn)表中是否有B節(jié)點(diǎn)，若有則直接通信。

②在選擇路徑時(shí)綜合考慮路徑長(zhǎng)度、負(fù)載、及延遲等因素，采用“基于平均分組時(shí)延和分組能量消耗乘積最小的路由路徑算法”[2]。

例：圖1中D若與E進(jìn)行通信時(shí)，D會(huì)檢查其路由表中鄰接節(jié)點(diǎn)表，則E在其表中，可直接建立通信；而讓節(jié)點(diǎn)檢測(cè)其鄰接節(jié)點(diǎn)表中節(jié)點(diǎn)的通信鏈路狀況，來(lái)作出判斷，可有效提高收斂速度；圖2中節(jié)點(diǎn)的關(guān)系樹(shù)會(huì)生成如圖3所示的核心樹(shù)。采用上述路由算法則會(huì)充分利用A—B和A—C兩條信道。

6 結(jié)束語(yǔ)

路由協(xié)議的設(shè)計(jì)是一項(xiàng)非常復(fù)雜的工作，對(duì)與無(wú)線Mesh網(wǎng)和Ad hoc網(wǎng)絡(luò)更是如此。在設(shè)計(jì)路由算法時(shí)要考慮眾多因素，本節(jié)只是對(duì)“新型核心樹(shù)自組織動(dòng)態(tài)路由算法”作出一定的改進(jìn)，至于其適用性，高效性和應(yīng)用性等，還須進(jìn)一步的驗(yàn)證與研究。

參考文獻(xiàn)：

[1] 電子科技大學(xué).一種新型核心樹(shù)自組織動(dòng)態(tài)路由算法：200410021667[P].

[2] 李新.移動(dòng)Ad hoc網(wǎng)絡(luò)若干技術(shù)研究[D].北京郵電大學(xué)博士學(xué)位論文，2005.

[3] 鄒濤.網(wǎng)絡(luò)與無(wú)線通信.人民郵電出版社[M].2004.

[4] Anany Levitin.Introduction to the design and analysis of alogorithms[M].S.1. Addison-Wesley，2002.

[5] Goupta P，Kumar P R.The capacity of wireless networks[J].IEEE Transactions on Information Theory，2000，46(2):338-404.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文