【文章內(nèi)容簡介】 RIP)。一種是基于鏈路狀態(tài)的路由協(xié)議(如OSPF協(xié)議).這兩類協(xié)議都是針對固定網(wǎng)絡(luò)而設(shè)計的, Hoc網(wǎng)絡(luò)帶寬較窄,拓撲變化頻繁等因素,這些傳統(tǒng)的用于固定網(wǎng)絡(luò)的路由協(xié)議不適用于Ad Hoc網(wǎng)絡(luò),主要體現(xiàn)在以下幾個方面:1) ,網(wǎng)絡(luò)拓撲結(jié)構(gòu)則表現(xiàn)較為穩(wěn)定,拓撲結(jié)構(gòu)的變化通常是由于鏈路狀態(tài)的變化(如鏈路擁塞,或是設(shè)備故障等)而引起的.2) 周期性地廣播拓撲信息會占用大量的無線信道資源,耗費電池能源, Hoc網(wǎng)絡(luò)環(huán)境中,可能在路由算法還未收斂時,網(wǎng)絡(luò)的拓撲結(jié)構(gòu)又發(fā)生了變化.3) , Hoc網(wǎng)絡(luò)中,由于無線收發(fā)設(shè)備不同或周圍環(huán)境對無線信道的影響,可能會造成單向的無線傳輸信道.路由協(xié)議包括傳播拓撲變化信息和計算到目標節(jié)點的更新路由兩部分。路由協(xié)議按照其路由機制可分為基于路由表的路由協(xié)議（Tabledriven）、根據(jù)需要的源路由（Ondemand source routiong）以及兩者的混合方式3類。基于路由表的路由協(xié)議根據(jù)拓撲的變化連續(xù)地更改網(wǎng)絡(luò)中的陸由，可保證一旦有分組要傳送，需要的路由已經(jīng)存在并可立即采用。這類路由協(xié)議要求每個節(jié)點維護一個或多個表存儲路由信息，采用該路由機制的不同協(xié)議的區(qū)別在于所要維護的路由表的數(shù)目以及廣播網(wǎng)絡(luò)結(jié)構(gòu)變化的方法。典型的路由表路由協(xié)議有目的排序的距離矢量路由（DSDV）、簇頭網(wǎng)關(guān)交換路由(CGSR)、無線路由協(xié)議(WRP)等。根據(jù)需要的源路由協(xié)議只有當需要傳送分組，且無到達目標節(jié)點的路由時才啟動路由發(fā)現(xiàn)協(xié)議。與前一種路由方式相比，根據(jù)需要的源路由在發(fā)送分組之前要進行全網(wǎng)或局部的路徑搜索，因而會有相當長的時延，但因不用進行頻繁的路由更新，故其路由信令信息占用帶寬小、效率高。典型的根據(jù)需要的源路由協(xié)議有Ad Hoc按需距離矢量路由（AODV）、動態(tài)源路由（DSR）、暫時排序路由算法(TORA)、基于聯(lián)系的路由(ABR)及信號穩(wěn)定性路由(SSR)等，其路由發(fā)現(xiàn)方法具有更大的靈活性和多樣性。為了滿足延時及有效性的折衷要求，某些網(wǎng)絡(luò)結(jié)構(gòu)如分層網(wǎng)絡(luò)結(jié)構(gòu)（包括主節(jié)點層和從屬節(jié)點層等）會采用兩種路由機制的混合方式，例如在主節(jié)點層采用基于路由表的路由協(xié)議，而在主節(jié)點控制范圍內(nèi)采用根據(jù)需要的源路由協(xié)議，反之亦可，這樣可提高網(wǎng)絡(luò)路由的可擴展性。無論是那種路由機制，其路由設(shè)計的目標均可包括以下幾點：分布式實現(xiàn)；有效利用網(wǎng)絡(luò)帶寬，及盡量減少控制信令；有效利用電池容量；快速路由更新；保證無迂回路由；優(yōu)化路由選擇依據(jù)，路由選擇依據(jù)依網(wǎng)絡(luò)優(yōu)化的目標不同包括最大化端到端吞吐量、最小化端到端延時、最短路徑/最小hop數(shù)、最小功耗、負荷平衡（及最少擁塞路徑）、最小冗余（有效利用帶寬）、自適應(yīng)動態(tài)拓撲變化等；可支持單向鏈路，有些因素如鏈路的不對稱性和信號干擾等會造成鏈路的單向特性，設(shè)計可運行于單向鏈路的路由算法會具有更廣的應(yīng)用適應(yīng)性。Ad Hoc移動網(wǎng)絡(luò)路由協(xié)議按照發(fā)現(xiàn)路由的策略可以分為兩類：（1）預(yù)先路由。網(wǎng)絡(luò)中的主機通過周期性交互路由信息得到所有其它主機的路由，大多數(shù)的傳統(tǒng)路由采用這種機制。（2）按需路由。主機只查找和維護自己需要使用的路由，而不是到所有主機的路由。 預(yù)先路由中主機之間要不斷地交互路由信息，會占用大量的網(wǎng)絡(luò)帶寬，交換的這些路由中有許多路由信息可能并不需要，這些無用信息浪費了有限的網(wǎng)絡(luò)資源。因此，預(yù)先路由方法不太適合Ad Hoc移動網(wǎng)絡(luò)的特性，按需路由很好地解決了這些問題，主機之間不需要周期性地交互路由信息，主機只在需要某個路由時才進行查找和維護。目前提出的Ad Hoc路由協(xié)議大多采用按需路由方式。Ad Hoc按需路由一般包含兩個階段：路由查找和路由維護。路由查找一般采用詢問/回答方式，當主機S要發(fā)送數(shù)據(jù)給D時，S首先檢查是否有到D的路由，若有，則按需路由發(fā)送數(shù)據(jù)，否則S發(fā)送路由請求報文，查找需要的路由，主機D或沿途有到D路由信息的主機收到請求報文后，會發(fā)送回答給S，S由此獲得路由。路由維護是指當某個鏈路斷開導(dǎo)致相應(yīng)的路由實效時，主機通知路由源或重新查找路由，以免使用失效路由發(fā)送數(shù)據(jù)而造成數(shù)據(jù)的丟失，目前一般使用按需維護，即當主機需要使用失效路由時，才通知相應(yīng)的源主機路由失效，由此減小路由維護的開銷。主機一般使用主動應(yīng)答、被動應(yīng)答或周期性的廣播報文來檢測鏈路是否斷開，主動應(yīng)答是指主機收到報文后要向發(fā)送該報文的鄰近主機（上游主機）發(fā)應(yīng)答。被動應(yīng)答是指主機通過監(jiān)聽下游主機發(fā)送的數(shù)據(jù)信息來確定它們之間的鏈路是否仍然存在。周期性的廣播是指主機周期性的向所有鄰居發(fā)報文，若主機在給定時間內(nèi)沒有收到某個鄰居的廣播報文，則認為它們之間的鏈路斷開。目前提出的具有代表性Ad Hoc按需路由主要DSR,ABR,AODV,LAR,CBRP,RDMAR和ZRP。下面我們將這幾種路由協(xié)議按照層次結(jié)構(gòu)、查找范圍分為平面泛洪、平面受限（或平面位置距離輔助）和層次路由三類分別進行說明。 平面泛洪路由網(wǎng)絡(luò)中的主機處于同一平面，彼此之間沒有層次概念，所有主機都是平等的。在路由查找中主機將收到的路由請求報文轉(zhuǎn)發(fā)給所有相鄰主機，這種方法的缺點是路由查找的開銷大，可能會導(dǎo)致整個網(wǎng)絡(luò)都充斥著請求報文，網(wǎng)絡(luò)的擴展性差，優(yōu)點是簡單、可靠。采用這種路由機制的有動態(tài)源路由協(xié)議（Dynamic Source Routing Protocol,DSR），基于結(jié)合關(guān)系的路由協(xié)議(Associativity Based Routing Protocol,ABR)，Ad Hoc按需距離向量路由協(xié)議(Ad Hoc Ondemand Distance Vector Routing,AODV)和區(qū)域路由協(xié)議(Zone Routing Protocol,ZRP)。 DSRDSR的特點在于使用了源路由的路由機制，在報文的頭部攜帶要經(jīng)過的路由，路由器按照該路由序列來轉(zhuǎn)發(fā)報文。協(xié)議包括兩部分：路由發(fā)現(xiàn)和路由維護。（1）路由發(fā)現(xiàn)當主機S需要到D的路由時，S廣播“路由請求”報文，每個請求報文通過序列號和S標識唯一確定。收到“路由請求”報文的主機，若滿足：（a）該主機不是目的主機D.（b）請求報文頭部的源路由序列中不包含該主機。（c）該主機沒有接收過同樣的路由請求報文。（d）主機的路由表中沒有到目的主機D的路由信息。主機將自己的地址附加到“路由請求”報文頭部的路由序列中，并將報文轉(zhuǎn)發(fā)給所有相鄰主機，若(b),(c)不滿足，主機將刪除報文，防止循環(huán)處理，若(a),(b)不滿足，主機將發(fā)送“路由回答”給S,回答中包含了從S到D的路由，該路由從請求報文中攜帶的路由序列或主機自己路由表中記錄的路由信息中得到。S獲得路由后，使用源路由進行數(shù)據(jù)通信。（2）路由維護DSR支持主動應(yīng)答和被動應(yīng)答兩種鏈路狀態(tài)檢測方法，一旦主機在發(fā)送數(shù)據(jù)時發(fā)現(xiàn)需要使用的連接鏈路斷開，它發(fā)送“路由出錯”報文給這些斷開路由的源主機，源主機收到報文后將失效路由從路由表中刪除，沿途轉(zhuǎn)發(fā)“路由出錯‘的主機也從自己的路由表中刪除包含該斷開鏈路的所有路由。（3）DSR協(xié)議評價1）主機不需要周期性的發(fā)送報文，節(jié)省了電池能源和網(wǎng)絡(luò)帶寬，尤其是當沒有主機要發(fā)送數(shù)據(jù)時，網(wǎng)絡(luò)中沒有通信開銷，支持主機睡眠。2）支持中間主機回答，能使源主機快速獲得路由，但會引起過時路由問題。3)每個報文都需要攜帶完整的路由信息，降低了網(wǎng)絡(luò)帶寬的利用率。 ABRABR有兩個獨特之處：一是依據(jù)路由的持久性和質(zhì)量來選擇路由，另一個是路由失效時通過路由重組來快速查找路由。協(xié)議包含兩部分：路由發(fā)現(xiàn)和路由重組。（1）路由發(fā)現(xiàn)ABR的路由發(fā)現(xiàn)包括廣播查找(BQ)和回答兩部分，當源主機S需要到D的路由時，S廣播“廣播查找”，收到查找報文的主機將主機標識、主機間結(jié)合計數(shù)值（該值通過主機間周期性交互的信標報文獲得）路由的轉(zhuǎn)發(fā)負載、鏈路的傳輸負載、網(wǎng)段計數(shù)信息附加在查找報文中并轉(zhuǎn)發(fā)給所有鄰居。D收到查找報文后，選擇長持久性和質(zhì)量（轉(zhuǎn)發(fā)能力和傳輸能力）高的路由，并通過選擇的路由反向?qū)ⅰ奥酚苫卮稹卑l(fā)給S，回答報文中包含S到D的完整路由，沿途轉(zhuǎn)發(fā)回答報文的主機根據(jù)回答中的路由更新各自的路由表，包括源、宿、下游主機地址等。S獲得路由后，就可以和D通信了。（2）路由重組ABR通過周期性的廣播信標報文來監(jiān)視鏈路狀態(tài)，當主機在使用某個鏈路時發(fā)現(xiàn)該鏈路斷開，將通過路由重組來查找新的路由，過程如下：(a)斷開鏈路的下游主機DN向目的主機D發(fā)送“路由通知”(RN)報文，通知沿途的主機該路由失效，收到該報文的主機從路由表中將該路由刪除。(b)斷開鏈路的上游主機UP執(zhí)行局部查詢(LQ)查找到D的新路由。LQ和BQ很類似，只是LQ中設(shè)定的TTL值要比BQ中的小的多，UP找到新路由后，從S發(fā)來得報文將沿著S….源路由….UP….UP新查找的路由….D的路徑到達D。(c)若UP超時未找到D的路由，將發(fā)送RN報文給直接的上游主機。由上游主機再重新進行局部查找，若上游主機也未找到，則繼續(xù)向上回朔，LQ查找次數(shù)的上限為源路由的一半。此時若仍未找到，主機將直接發(fā)送RN給源主機S，由S重新查找路由。（3）ABR協(xié)議評價1）選擇的路由持久性和質(zhì)量比較高。2）路由維護中采用了局部查找，不像 DSR總是讓源主機查找路由，這樣可以減少路由恢復(fù)的時間和路由維護的開銷。3）在路由查找中必須由目的主機選擇路由，可以避免過時路由問題。但這樣做會增加S獲得路由的等待時間。4）需要周期性的報文，需要消耗一定的電池能源和網(wǎng)絡(luò)帶寬。5）路由重組中需要合理設(shè)置 UP 的局部查找范圍，若UP在給定的有限范圍內(nèi)沒有找到路由，要回朔查找，這樣會增加新路由查找的延遲和開銷。 AODVAODV是基于距離向量的路由協(xié)議。協(xié)議比較有特色的是每個路由都有目的序列號，該號由目的主機產(chǎn)生用于防止循環(huán)，每當目的的主機和相鄰主機之間的拓撲發(fā)生變化，它就會將目的序列號加1，并將該號附加在路由回答中。AODV同時還支持多址通信，協(xié)議由兩部分組成：路由請求和路由維護。（1）路由請求AODV的路由請求和DSR,ABR基本類型，不同的是AODV在請求報文(RREQ)中攜帶了主機記錄的目的序列號，收到請求報文的主機，查看路由表中是否記錄有到目的主機“更新”的路由，所謂“更新”是指目的序列號大于或等于請求報文中的序列號。若沒有，主機記錄請求報文的源主機、目的主機、上游主機地址和目的序列號并廣播，若有或主機是目的主機，將發(fā)送“路由回答”(RREP)給源主機，回答中包含“更新”的目的序列號和路由，轉(zhuǎn)發(fā)“路由回答”的主機根據(jù)回答更新路由表，設(shè)置路由的下游主機、目的序列號、有效時間信息，并根據(jù)先前記錄的上游主機地址將RREP報文轉(zhuǎn)發(fā)給上游主機，直到源主機S。（2）路由維護AODV通過周期性的廣播hello報文來監(jiān)視鏈路狀態(tài)，若主機在使用某個鏈路時發(fā)現(xiàn)該鏈路斷開，主機將從路由表中刪除包含該斷開鏈路的路由，并發(fā)送“路由出錯”報文(RRER)通知那些因鏈路斷開而不可達的主機將對應(yīng)路由從路由表中刪除，沿途轉(zhuǎn)發(fā)RRER的主機也刪除自己路由表中的對應(yīng)路由。（3）AODV協(xié)議評價1） 基于傳統(tǒng)的距離向量路有機制，思路簡單、易懂。2） 通過使用目的序列號有效地防止了循環(huán)的發(fā)生，解決了傳統(tǒng)的基于距離向量路由協(xié)議存在的無限計數(shù)問題，并且易于編程實現(xiàn)。3） 支持中間主機回答，能使源主機快速獲得路由，但存在過時路由問題。4） 需要周期性的報文，需要消耗一定的電池能源和網(wǎng)絡(luò)帶寬。 ZRPZRP是預(yù)先路由協(xié)議和按需路由協(xié)議的結(jié)合。該協(xié)議將網(wǎng)絡(luò)分為若干個互相重疊的區(qū)域，每個區(qū)域的半徑長度由用戶設(shè)定。例圖，假定區(qū)域半徑為2，對于主機S，和它相距兩個網(wǎng)段距離的主機即A,B,C,D,E,F,G,H在Z中，而I,J,K,L,M不在Z中。ZRP中，同一區(qū)域內(nèi)的主機通信使用區(qū)內(nèi)路由協(xié)議，跨區(qū)的主機通信使用區(qū)間路由協(xié)議。 ZRP路由協(xié)議（1）區(qū)內(nèi)路由協(xié)議ZRP的區(qū)內(nèi)路由采用傳統(tǒng)的預(yù)先路由法，支持距離向量和鏈路狀態(tài)兩種路由策略。主機和相鄰主機之間通過周期性的交互路由表獲得到區(qū)內(nèi)各主機的最新路由。（2）區(qū)間路由協(xié)議ZRP區(qū)間路由采用按需方式，如圖中，S要和M通信，因為MZ,S發(fā)請求給本區(qū)域的邊界主機,即Z,中的G,H,B,C,E,這些主機在各自的區(qū)域查找是否有到M的路由,若有,例M∈Z,E發(fā)送回答給S,告訴它到M的路由,若沒有,則將請求報文發(fā)給本區(qū)的邊界主機,依次不斷循環(huán)查找,這些主機都會發(fā)路由回答給S,S將選擇其中的最短路由。ZRP的路由維護也是混合的,在區(qū)域路由維護中當主機需要使用的鏈路斷開時,主機選擇通知源主機或進行局部查找路由,其局部查找方法和區(qū)間路由協(xié)議中的路由查找相同,只是查找的范圍小。（3）ZRP協(xié)議評價1)區(qū)內(nèi)通信使用預(yù)先路由,沒有按需路由中的初始延遲問題,且區(qū)域范圍有限,路由更新的代價不大。2)區(qū)間通信采用了按需方式,避免預(yù)先通信路由交互開銷大的問題。3)區(qū)間查找路由時,將請求報文發(fā)給邊界主機,提高了路由的查找速度。4)只允許目的區(qū)域內(nèi)的主機回答,延長了源主機獲得路由的時間。5)需要周期性的廣播報文，需要消耗一定的電池能源和網(wǎng)絡(luò)帶寬。此外,區(qū)域半徑設(shè)置將直接影響路由的效率,因此如何根據(jù)網(wǎng)絡(luò)的實際通信環(huán)境設(shè)置一個最佳的區(qū)域半徑是決定ZRP效率的一個重要因素。 平面受限路由 平面受限路由和平面泛洪路由類似,不同的是在路由查找過程中,對請求報文的傳播范圍進行了限制,只有在給定區(qū)域內(nèi)的主機才參與路由查找,這種方法的優(yōu)點是路由查找的開銷小,速度快,網(wǎng)絡(luò)的擴展性好。缺點是若在給定的范圍內(nèi)沒有找到路由,則需要擴大范圍重新查找,(LocationAided Routing LAR)和相對距離微觀發(fā)現(xiàn)路由(Relative Distance Mierodiscovery AD hoc Routing,RDMAR)。 LAR :(GPS)獲得自己的當前位置(X,Y)源主機在發(fā)送的”路由請求”中攜帶自己的當前位置和時間,目的主機也在”路由回答”中攜帶自己的當前位置和時間,沿途轉(zhuǎn)發(fā)請求或回答報文的主機可以得到源主機或目的主機的位置信息,通過這種方法主機可以獲得其它主機的位置信息。協(xié)議決定每個主機知道其它主機的平均移動速度。