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