Ad Hoc無線網(wǎng)絡(luò)路由協(xié)議研究與展望1引言
　　Ad Hoc無線網(wǎng)絡(luò)又稱移動(dòng)自組網(wǎng)、多跳網(wǎng)絡(luò)，最初起源于20世紀(jì)70年代的美國(guó)軍事研究領(lǐng)域，是一種特殊的在不借助中心管理的情況下，在有限的范圍內(nèi)實(shí)現(xiàn)多個(gè)移動(dòng)總端的臨時(shí)互聯(lián)，它為局域網(wǎng)內(nèi)的移動(dòng)通信網(wǎng)絡(luò)提供了一種靈活的互聯(lián)方式。Ad Hoc無線網(wǎng)絡(luò)組網(wǎng)靈活、快捷，不受有線網(wǎng)絡(luò)的影響，可廣泛應(yīng)用于軍事通信、發(fā)生地震或水災(zāi)后的營(yíng)救等無法或不便預(yù)先敷設(shè)網(wǎng)絡(luò)設(shè)施的場(chǎng)合，具有廣闊的發(fā)展前景，這方面的研究工作正在不斷展開。 2Ad Hoc無線網(wǎng)絡(luò)的結(jié)構(gòu)和特點(diǎn)
　　 Ad Hoc無線網(wǎng)絡(luò)具有自身的特殊性，在組建實(shí)際使用的無線工作網(wǎng)絡(luò)時(shí)，必須充分考慮網(wǎng)絡(luò)的應(yīng)用規(guī)模和擴(kuò)展性，以及應(yīng)用的可靠程度及實(shí)時(shí)性要求，選擇合適的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。另外，由于Ad Hoc網(wǎng)絡(luò)自身結(jié)構(gòu)的特殊性，設(shè)計(jì)或組建網(wǎng)絡(luò)時(shí)應(yīng)充分考慮Ad Hoc無線網(wǎng)絡(luò)的特點(diǎn)，有助于我們?cè)O(shè)計(jì)出適合特定網(wǎng)絡(luò)結(jié)構(gòu)的路由協(xié)議，最大限度地發(fā)揮整個(gè)網(wǎng)絡(luò)的工作性能。
　　2.1Ad Hoc無線網(wǎng)絡(luò)的結(jié)構(gòu)
　　Ad Hoc無線網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)可分為兩種：對(duì)等式平面結(jié)構(gòu)和分級(jí)結(jié)構(gòu)。在對(duì)等式平面結(jié)構(gòu)中，所有網(wǎng)絡(luò)節(jié)點(diǎn)地位平等。
　　 而在分級(jí)結(jié)構(gòu)的Ad Hoc無線網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，整個(gè)網(wǎng)絡(luò)是以簇為子網(wǎng)組成，每個(gè)簇由一個(gè)簇頭和多個(gè)簇成員組成，簇頭形成高一級(jí)網(wǎng)絡(luò)，高一級(jí)網(wǎng)絡(luò)又可分簇形成更高一級(jí)網(wǎng)絡(luò)。每一個(gè)簇中的簇頭和簇成員是動(dòng)態(tài)變化、自動(dòng)組網(wǎng)。分級(jí)結(jié)構(gòu)根據(jù)硬件的不同配置，又可以分為單頻分級(jí)結(jié)構(gòu)和多頻分級(jí)結(jié)構(gòu)。單頻分級(jí)結(jié)構(gòu)使用單一頻率通信，所有節(jié)點(diǎn)使用同一頻率；而在多頻分級(jí)結(jié)構(gòu)中，若存在兩級(jí)網(wǎng)絡(luò)，則低級(jí)網(wǎng)絡(luò)通信范圍小，高級(jí)網(wǎng)絡(luò)通信范圍大，簇成員用一個(gè)頻率通信，簇頭節(jié)點(diǎn)用一個(gè)頻率與簇成員通信，用另一個(gè)頻率來維持與簇頭之間的通信。
　　 對(duì)等式平面結(jié)構(gòu)和分級(jí)結(jié)構(gòu)使用時(shí)各存在優(yōu)缺點(diǎn)：對(duì)等式平面結(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)簡(jiǎn)單，各節(jié)點(diǎn)地位平等，源節(jié)點(diǎn)與目的節(jié)點(diǎn)通信時(shí)存在多條路徑，不存在網(wǎng)絡(luò)瓶頸，而且網(wǎng)絡(luò)相對(duì)比較安全，但最大的缺點(diǎn)是網(wǎng)絡(luò)規(guī)模受到限制，當(dāng)網(wǎng)絡(luò)規(guī)模擴(kuò)大時(shí)路由維護(hù)的開銷指數(shù)增長(zhǎng)而消耗掉有限的帶寬；分級(jí)結(jié)構(gòu)網(wǎng)絡(luò)規(guī)模不受限制，可擴(kuò)充性好，而且由于分簇，路由開銷相對(duì)小一些，雖然分級(jí)結(jié)構(gòu)中需要復(fù)雜的簇頭選擇算法，但由于分級(jí)網(wǎng)絡(luò)結(jié)構(gòu)具有較高的系統(tǒng)吞吐量，節(jié)點(diǎn)定位簡(jiǎn)單，目前Ad Hoc無線網(wǎng)絡(luò)正逐漸呈現(xiàn)分級(jí)化的趨勢(shì)，許多網(wǎng)絡(luò)路由算法都是基于分級(jí)結(jié)構(gòu)網(wǎng)絡(luò)模式提出的。
　　2.2Ad Hoc無線網(wǎng)絡(luò)的特點(diǎn)
　　 Ad Hoc無線網(wǎng)絡(luò)是一種移動(dòng)通信和計(jì)算機(jī)網(wǎng)絡(luò)相結(jié)合的網(wǎng)絡(luò)，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都兼有路由器和主機(jī)兩種功能。Ad Hoc網(wǎng)絡(luò)的特點(diǎn)主要體現(xiàn)在以下4方面：
　　（1)動(dòng)態(tài)變化的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)：Ad Hoc網(wǎng)絡(luò)中沒有固定的通信設(shè)施和中央管理設(shè)備，網(wǎng)絡(luò)節(jié)點(diǎn)可以隨機(jī)地以任意速度朝任何方向移動(dòng)，加上無線發(fā)射裝置發(fā)送功率的變化、環(huán)境的影響以及信號(hào)之間的互相干擾等因素，都會(huì)造成網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的動(dòng)態(tài)變化。
　�。�2)有限的資源：提供給Ad Hoc網(wǎng)絡(luò)中移動(dòng)主機(jī)的工作能量是有限的，而且移動(dòng)主機(jī)損耗能量越多，將降低Ad Hoc網(wǎng)絡(luò)功能；另一方面，網(wǎng)絡(luò)本身提供帶寬有限以及信號(hào)之間的沖突和干擾，使移動(dòng)主機(jī)可得到的有限的傳輸帶寬將遠(yuǎn)遠(yuǎn)小于理論上的最大帶寬。
　�。�3)多跳通信：兩個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)由于受到可用資源的限制，不能處在同一個(gè)覆蓋網(wǎng)絡(luò)內(nèi)，可采用Ad Hoc網(wǎng)絡(luò)多跳通信，實(shí)現(xiàn)不同覆蓋網(wǎng)絡(luò)之間的源主機(jī)與目的主機(jī)之間的通信。
　　（4)較低的安全性：Ad Hoc網(wǎng)絡(luò)節(jié)點(diǎn)間通信通過無線信道，傳輸?shù)男畔⒎浅Ｈ菀资艿奖O(jiān)聽、重發(fā)、篡改、偽造等各種攻擊，如果路由協(xié)議一旦遭受到上述惡意攻擊，整個(gè)自組網(wǎng)絡(luò)將無法正常工作。這些特點(diǎn)對(duì)設(shè)計(jì)Ad Hoc網(wǎng)絡(luò)路由算法提出了特殊的要求，一個(gè)合理的路由算法必須考慮有限的網(wǎng)絡(luò)資源、動(dòng)態(tài)變化的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、提高網(wǎng)絡(luò)吞吐量等方面的因素。
　　3Ad Hoc無線網(wǎng)絡(luò)路由協(xié)議
　　3.1Ad Hoc無線網(wǎng)絡(luò)路由協(xié)議的設(shè)計(jì)要求
　　Ad Hoc網(wǎng)絡(luò)設(shè)計(jì)中的一個(gè)關(guān)鍵問題是開發(fā)能夠在兩個(gè)節(jié)點(diǎn)之間提供高質(zhì)量高效率通信的路由協(xié)議。網(wǎng)絡(luò)節(jié)點(diǎn)的移動(dòng)性使得網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不斷變化，傳統(tǒng)的基于因特網(wǎng)的路由協(xié)議無法適應(yīng)這些特性，需要有專門的應(yīng)用于Ad Hoc網(wǎng)絡(luò)的路由協(xié)議，根據(jù)前文對(duì)Ad Hoc網(wǎng)絡(luò)結(jié)構(gòu)和特點(diǎn)的闡述，設(shè)計(jì)的路由協(xié)議必須滿足以下的條件：
　�。�1)必須對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動(dòng)態(tài)變化具有快速應(yīng)變的能力，并且盡量避免路由環(huán)路的發(fā)生，提供方便簡(jiǎn)單的網(wǎng)絡(luò)節(jié)點(diǎn)定位法。
　�。�2)必須高效地利用有限的帶寬資源，盡可能壓縮不必要的開銷。
　�。�3)實(shí)施多跳通信的中間轉(zhuǎn)接次數(shù)也是有限的，一般不要超過3次。
　�。�4)必須盡可能減少發(fā)射時(shí)間和發(fā)射的數(shù)據(jù)量，節(jié)約有限的工作能源。
　�。�5)在可能的條件下，使設(shè)計(jì)的路由協(xié)議具有安全性，降低遭受攻擊的可能性。
　　3.2Ad Hoc無線網(wǎng)絡(luò)的路由協(xié)議分析
　　根據(jù)Ad Hoc無線網(wǎng)絡(luò)路由協(xié)議的特殊性，近年來提出了多種Ad hoc網(wǎng)絡(luò)路由協(xié)議。IETF的MANET工作小組目前正專注于Ad Hoc網(wǎng)絡(luò)路由協(xié)議的研究，提出了許多協(xié)議草案，如DSR，AODV，ZRP等路由協(xié)議；另外，專業(yè)研究人員也發(fā)表了大量關(guān)于Ad Hoc網(wǎng)絡(luò)路由協(xié)議的相關(guān)文章，提出了許多關(guān)于Ad Hoc的網(wǎng)絡(luò)路由協(xié)議，如DSDV，WRP等。根據(jù)路由觸發(fā)原理，目前的路由協(xié)議大致可以分為先驗(yàn)式路由協(xié)議、反應(yīng)式路由協(xié)議和混合式路由協(xié)議3種。
　　3.2.1先驗(yàn)式路由協(xié)議
　　先驗(yàn)式路由協(xié)議又稱表驅(qū)動(dòng)路由協(xié)議，每個(gè)節(jié)點(diǎn)維護(hù)一張包含到達(dá)節(jié)點(diǎn)的路由信息的路由表，并根據(jù)網(wǎng)絡(luò)拓?fù)涞淖兓�隨時(shí)更新路由表，所以路由表可以準(zhǔn)確地反映網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)；源節(jié)點(diǎn)一旦要發(fā)送報(bào)文，可以立即獲得到達(dá)目的節(jié)點(diǎn)的路由，這類的路由協(xié)議通常是通過修改現(xiàn)有的有線路由協(xié)議來適應(yīng)Ad Hoc無線網(wǎng)絡(luò)要求，如通過修改路由信息協(xié)議(RIP)得到的目的節(jié)點(diǎn)序列距離矢量協(xié)議（DSDV）。因此這種路由協(xié)議的時(shí)延較小，但是協(xié)議需要大量的路由控制報(bào)文路由，協(xié)議的開銷較大。常用的先驗(yàn)式路由協(xié)議有DSDV，HSR，GSR，WRP等。
　　 DSDV協(xié)議通過給每個(gè)路由設(shè)定序列號(hào)避免了路由環(huán)路的產(chǎn)生，采用時(shí)間驅(qū)動(dòng)和事件驅(qū)動(dòng)技術(shù)控制路由表的傳送，即每個(gè)移動(dòng)節(jié)點(diǎn)在本地都保留一張路由表，其中包括所有有效信宿點(diǎn)、路由跳數(shù)、信宿路由序列號(hào)等信息，信宿路由序列號(hào)用于區(qū)別新舊路由以避免環(huán)路的產(chǎn)生。每個(gè)節(jié)點(diǎn)周期性地將本地路由表傳送給鄰近節(jié)點(diǎn)，或者當(dāng)其路由表發(fā)生變化時(shí)，也會(huì)將其路由信息傳給鄰近點(diǎn)，當(dāng)無節(jié)點(diǎn)移動(dòng)時(shí)使用間隔較長(zhǎng)的大數(shù)據(jù)包（包括多個(gè)數(shù)據(jù)單元）進(jìn)行路由更新；鄰近節(jié)點(diǎn)收到包含修改的路由表信息后，先比較信源K信宿路由序列號(hào)的大小，信宿路由序列號(hào)大的路由將被采用，而信宿路由序列號(hào)小的路由則被淘汰，若相同，則采用最佳制式的路由（如最短路徑）。
　　 HSR(Hierarchical State Routing)是一種用于分級(jí)網(wǎng)絡(luò)的路由協(xié)議，高級(jí)節(jié)點(diǎn)保存它所有子孫節(jié)點(diǎn)的位置信息，沿從最高級(jí)的根節(jié)點(diǎn)到最低級(jí)的葉節(jié)點(diǎn)的路徑為節(jié)點(diǎn)分配邏輯序列地址，可以用序列地址進(jìn)行節(jié)點(diǎn)尋址。
　　 GSR稱為全局狀態(tài)路由協(xié)議，其工作原理與DSDV協(xié)議類似，采用鏈路狀態(tài)路由算法，但避免了路由報(bào)文的泛洪，它包括一個(gè)鄰近節(jié)點(diǎn)表、網(wǎng)絡(luò)拓?fù)浔�、下一跳路由表和距離表。
　　 無線路由協(xié)議WRP是一種距離—矢量路由協(xié)議，每個(gè)節(jié)點(diǎn)都維持一個(gè)距離表、路由表、鏈路開銷表和報(bào)文重傳表，通過其鄰近節(jié)點(diǎn)的最短路徑生成數(shù)SST（Short path Spanning Tree）生成自己的SST后，再向鄰節(jié)點(diǎn)傳遞更新信息。當(dāng)網(wǎng)絡(luò)路由表沒有任何變化時(shí)，接收節(jié)點(diǎn)需回傳一個(gè)空閑報(bào)文以示連接，否則，修改距離表，尋找更優(yōu)路徑。這種算法的特點(diǎn)是當(dāng)檢測(cè)到任意相鄰節(jié)點(diǎn)變化時(shí)，則檢查所有相鄰節(jié)點(diǎn)的堅(jiān)固性以消除回路，具有較快的收斂性。
　　3.2.2反應(yīng)式路由協(xié)議
　　 反應(yīng)式路由協(xié)議又稱隨選路由或者按需路由，是一種當(dāng)需要時(shí)才查找路由的路由選擇方式。節(jié)點(diǎn)不需要維護(hù)及時(shí)準(zhǔn)確的路由信息，當(dāng)需要發(fā)送數(shù)據(jù)時(shí)才發(fā)起路由查找過程。與先驗(yàn)式路由協(xié)議相比，反應(yīng)式路由協(xié)議的開銷小，但是數(shù)據(jù)報(bào)傳送的時(shí)延較大，不適合于實(shí)時(shí)性的應(yīng)用。常用的反應(yīng)式路由協(xié)議有AODV，DSR，TORA等。 AODV（Ad hoc On�瞕emand Distance Vector Routing）協(xié)議：源節(jié)點(diǎn)發(fā)送數(shù)據(jù)前先廣播一個(gè)路由請(qǐng)求消息，附近節(jié)點(diǎn)收到后再次廣播，直到請(qǐng)求消息到達(dá)目的節(jié)點(diǎn)或到達(dá)知道目的節(jié)點(diǎn)路由的中間節(jié)點(diǎn)，目的節(jié)點(diǎn)或中間節(jié)點(diǎn)沿原來路徑返回響應(yīng)消息，源節(jié)點(diǎn)收到響應(yīng)后就知道到達(dá)目的節(jié)點(diǎn)的路由。
　　 DSR協(xié)議稱為動(dòng)態(tài)源路由協(xié)議，是一種源路由協(xié)議，每個(gè)分組的分組頭中包含了源—目的整條路由信息。它采用路由緩存技術(shù)，用于存儲(chǔ)源路由信息，當(dāng)學(xué)習(xí)到新的路由時(shí)則修改路由緩存內(nèi)容，該協(xié)議包含兩個(gè)方面：路由發(fā)現(xiàn)和路由維護(hù)。
　　 TORA協(xié)議稱為臨時(shí)預(yù)定路由算法，是一種源初始化按需路由選擇協(xié)議，它采用鏈路反轉(zhuǎn)的分布式算法，具有高度自適應(yīng)、高效率和較好的擴(kuò)充性，比較適合高度動(dòng)態(tài)移動(dòng)、多跳的無線網(wǎng)絡(luò)，其主要特點(diǎn)是控制報(bào)文定位在最靠近拓?fù)渥兓�的一小部分�?jié)點(diǎn)處，因此節(jié)點(diǎn)只保留鄰近點(diǎn)的路由信息。該算法中路由不一定是最優(yōu)的，常常使用次優(yōu)路由以減少發(fā)現(xiàn)路由的開銷。TORA協(xié)議包括3個(gè)基本模塊：路由的創(chuàng)建、路由的維護(hù)和路由的刪除。
　　3.2.3混合式路由協(xié)議
　　 Ad hoc無線網(wǎng)絡(luò)中單純采用先驗(yàn)式或反應(yīng)式路由協(xié)議都不能完全解決路由問題，因此，許多學(xué)者提出了結(jié)合先驗(yàn)式和反應(yīng)式路由協(xié)議優(yōu)點(diǎn)的混合式路由協(xié)議，如ZRP協(xié)議。ZRP協(xié)議是一個(gè)先驗(yàn)式和反應(yīng)式路由協(xié)議的組合，網(wǎng)絡(luò)內(nèi)的所有節(jié)點(diǎn)都有一個(gè)以自己為中心的虛擬區(qū)，區(qū)內(nèi)的節(jié)點(diǎn)數(shù)與設(shè)定的區(qū)半徑有關(guān)，因此區(qū)是重疊的，這是與分群路由的區(qū)別；在區(qū)內(nèi)使用先驗(yàn)式路由算法，中心節(jié)點(diǎn)使用區(qū)內(nèi)路由協(xié)議IARP維持一個(gè)到區(qū)內(nèi)其他成員的路由表,對(duì)區(qū)外節(jié)點(diǎn)的路由使用按需路由，利用區(qū)間路由協(xié)議IERP建立臨時(shí)的路由。但是，實(shí)施混合式路由也面臨著很多困難，如族的選擇和維護(hù)、先驗(yàn)式和反應(yīng)式路由協(xié)議的合理選擇以及網(wǎng)絡(luò)工作的大流量等問題。
　　4總結(jié)和展望
　　 本文首先闡述了Ad Hoc無線網(wǎng)絡(luò)結(jié)構(gòu)和特點(diǎn)，提出了設(shè)計(jì)Ad Hoc網(wǎng)絡(luò)協(xié)議時(shí)需要滿足的條件，并對(duì)目前存在的路由協(xié)議進(jìn)行了詳細(xì)分析。但是Ad Hoc網(wǎng)絡(luò)中路由功能是由移動(dòng)主機(jī)來執(zhí)行，因此路由器的位置是移動(dòng)的；Ad Hoc網(wǎng)絡(luò)有限的工作能源也無法提供復(fù)雜的路由功能；網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的動(dòng)態(tài)變化性使得目前認(rèn)為是最優(yōu)的路由協(xié)議也可能會(huì)被中斷或不是最優(yōu)，這些問題使得Ad hoc網(wǎng)絡(luò)中的路由算法成為當(dāng)前研究的一個(gè)熱點(diǎn)。
　　 近年來，越來越多的研究者開始重視移動(dòng)代理技術(shù)的應(yīng)用，并有學(xué)者提出了基于移動(dòng)代理技術(shù)的移動(dòng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)構(gòu)造和有線網(wǎng)絡(luò)動(dòng)態(tài)路由算法實(shí)現(xiàn)等理論。移動(dòng)代理技術(shù)具有移動(dòng)性、自主性等特點(diǎn)，因此它適用于移動(dòng)網(wǎng)絡(luò)，研究基于移動(dòng)代理技術(shù)的Ad hoc無線網(wǎng)絡(luò)路由協(xié)議將成為今后Ad hoc無線網(wǎng)絡(luò)路由技術(shù)研究的重點(diǎn)。