AD-HOC路由協(xié)議在AdHoc網(wǎng)絡(luò)中，隨著節(jié)點(diǎn)移動(dòng)，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)在不斷變化。如何迅速準(zhǔn)確地選擇到達(dá)目的節(jié)點(diǎn)的路由（即網(wǎng)絡(luò)的路由選擇問(wèn)題），是AdHoc網(wǎng)絡(luò)的一個(gè)重要和核心的問(wèn)題。1.AdHoc網(wǎng)絡(luò)與傳統(tǒng)移動(dòng)通信系統(tǒng)在路由問(wèn)題上的區(qū)別1．AdHoc網(wǎng)絡(luò)與蜂窩移動(dòng)通信系統(tǒng)的區(qū)別蜂窩移動(dòng)通信系統(tǒng)網(wǎng)絡(luò)結(jié)構(gòu)比較穩(wěn)定。而在AdHoc網(wǎng)絡(luò)環(huán)境下，節(jié)點(diǎn)的頻繁隨意移動(dòng)，造成網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生經(jīng)常性的變化，使得路由表項(xiàng)經(jīng)常改變。2．AdHoc網(wǎng)絡(luò)與無(wú)線局域網(wǎng)的區(qū)別無(wú)線局域網(wǎng)是一個(gè)單跳的網(wǎng)絡(luò)。而AdHoc網(wǎng)絡(luò)則是一個(gè)多跳的網(wǎng)絡(luò)。2.傳統(tǒng)Internet網(wǎng)絡(luò)路由協(xié)議目前在Internet中常用的內(nèi)部網(wǎng)關(guān)路由協(xié)議主要有兩種。基于距離矢量的路由協(xié)議（如RIP協(xié)議）基于鏈路狀態(tài)的路由協(xié)議（如OSPF協(xié)議）。這兩類(lèi)協(xié)議都是針對(duì)固定網(wǎng)絡(luò)而設(shè)計(jì)的，它們都需要周期性地交換信息維護(hù)網(wǎng)絡(luò)正確的路由表或網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖。AdHoc網(wǎng)絡(luò)帶寬有限、拓?fù)渥兓l繁，這些傳統(tǒng)的用于固定網(wǎng)絡(luò)的路由協(xié)議不適用于AdHoc網(wǎng)絡(luò)，主要體現(xiàn)在以下幾個(gè)方面。（1）動(dòng)態(tài)變化的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。（2）周期性地廣播拓?fù)湫畔?huì)占用大量的無(wú)線信道資源，耗費(fèi)電池能源，將會(huì)嚴(yán)重降低系統(tǒng)的性能。尤其是在拓?fù)渥兓l繁的AdHoc網(wǎng)絡(luò)環(huán)境中，可能當(dāng)路由算法還未收斂時(shí)，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)就又發(fā)生了變化。（3）單向的無(wú)線傳輸信道。3.AdHoc網(wǎng)絡(luò)路由協(xié)議的分類(lèi)根據(jù)發(fā)現(xiàn)路由的驅(qū)動(dòng)模式的不同，可以將這些路由協(xié)議分為表驅(qū)動(dòng)路由協(xié)議（TableDrivenProtocols）在表驅(qū)動(dòng)路由協(xié)議中，每個(gè)節(jié)點(diǎn)需要實(shí)時(shí)地維護(hù)路由信息，當(dāng)網(wǎng)絡(luò)規(guī)模較大、拓?fù)渥兓^快的環(huán)境中，大量的拓?fù)涓滦畔?huì)占用過(guò)多的信道資源，使得系統(tǒng)效率下降。按需路由協(xié)議（Source-InitiatedOn-DemandProtocols）按需路由協(xié)議的路由發(fā)現(xiàn)過(guò)程根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的差異，又可以將它們分為平面結(jié)構(gòu)的路由協(xié)議（FlatProtocols）分簇路由協(xié)議（ClusteredProtocols）。AdHoc網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)在平面結(jié)構(gòu)的路由協(xié)議中網(wǎng)絡(luò)結(jié)構(gòu)簡(jiǎn)單網(wǎng)絡(luò)中的節(jié)點(diǎn)都處于平等的地位它們所具有的功能完全相同各節(jié)點(diǎn)共同協(xié)作完成節(jié)點(diǎn)間的通信。隨著網(wǎng)絡(luò)規(guī)模的逐步擴(kuò)大，網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)不斷增加，每個(gè)節(jié)點(diǎn)要想維護(hù)整個(gè)網(wǎng)絡(luò)的拓?fù)湫畔⒒蜻x擇到遠(yuǎn)端節(jié)點(diǎn)合適的路由將十分困難，由此產(chǎn)生了分簇式路由協(xié)議。在分簇式路由協(xié)議中，網(wǎng)絡(luò)節(jié)點(diǎn)按照不同的分簇算法分成相應(yīng)的簇（或群）。簇中的每個(gè)節(jié)點(diǎn)完成的功能是不相同的簇首節(jié)點(diǎn)維護(hù)和管理本簇范圍內(nèi)節(jié)點(diǎn)，負(fù)責(zé)簇內(nèi)節(jié)點(diǎn)的通信，同時(shí)為簇間節(jié)點(diǎn)通信提供合適的路由信息；網(wǎng)關(guān)節(jié)點(diǎn)負(fù)責(zé)與相鄰簇節(jié)點(diǎn)通信。分簇式路由協(xié)議中分層結(jié)構(gòu)圖4.評(píng)價(jià)AdHoc網(wǎng)絡(luò)路由協(xié)議的標(biāo)準(zhǔn)評(píng)價(jià)一種AdHoc網(wǎng)絡(luò)路由協(xié)議的性能主要包括以下幾個(gè)方面的指標(biāo)端到端的數(shù)據(jù)吞吐量和時(shí)延：通過(guò)報(bào)文傳輸質(zhì)量的好壞來(lái)衡量路由協(xié)議性能的好壞。路由請(qǐng)求的時(shí)間：即統(tǒng)計(jì)節(jié)點(diǎn)有數(shù)據(jù)需要發(fā)送到數(shù)據(jù)成功發(fā)送的時(shí)間，這主要用于按需路由方式的AdHoc網(wǎng)絡(luò)路由協(xié)議的性能評(píng)價(jià)；路由協(xié)議的效率：即完成路由任務(wù)的控制信息與用戶(hù)數(shù)據(jù)信息的比率。尤其是在控制信息與數(shù)據(jù)信息共享同一信道的情況下，該性能將直接影響到整個(gè)系統(tǒng)效率的高低。需要注意的是：即使是同一個(gè)路由協(xié)議，在不同的環(huán)境中，其性能好壞可能有很大的差異AdHoc網(wǎng)絡(luò)組網(wǎng)環(huán)境主要涉及的內(nèi)容有：網(wǎng)絡(luò)的規(guī)模大小，即網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)的多少；網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)變化速度；節(jié)點(diǎn)的移動(dòng)速度；信道的傳輸帶寬和單向信道的比率“休眠”節(jié)點(diǎn)的比率等。因此，在分析比較各種AdHoc網(wǎng)絡(luò)路由協(xié)議性能時(shí),要注意環(huán)境因素對(duì)各路由協(xié)議的影響。5.幾種典型的AdHoc網(wǎng)絡(luò)路由協(xié)議DSDV（Destination-SequencedDistance-VectorRouting）路由協(xié)議DSDV協(xié)議是基于傳統(tǒng)Bellman-Ford路由選擇算法經(jīng)改良而發(fā)展出來(lái)的，是一個(gè)基于表驅(qū)動(dòng)的路由協(xié)議，它的最大優(yōu)點(diǎn)是解決了傳統(tǒng)距離矢量路由協(xié)議中的無(wú)窮環(huán)路問(wèn)題。在DSDV路由協(xié)議中，每個(gè)節(jié)點(diǎn)都維護(hù)一張路由表，該路由表表項(xiàng)包括目的節(jié)點(diǎn)跳數(shù)下一跳節(jié)點(diǎn)目的節(jié)點(diǎn)序號(hào)每個(gè)節(jié)點(diǎn)周期性地與鄰節(jié)點(diǎn)交換路由信息，或者根據(jù)路由表的改變來(lái)觸發(fā)路由更新。路由表更新有兩種方式：一種是全部更新（Fulldump），即拓?fù)涓孪⒅袑ㄕ麄€(gè)路由表，主要應(yīng)用于網(wǎng)絡(luò)變化較快的情況；另一種方式是部分更新（Incrementalupdate），更新消息中僅包含變化的路由部分，通常適用于網(wǎng)絡(luò)變化較慢的情況。在DSDV中只使用序列號(hào)最高的路由，如果兩個(gè)路由具有相同的序列號(hào)，那么將選擇最優(yōu)的路由（如跳數(shù)最短）。DSDV優(yōu)缺點(diǎn)DSDV路由協(xié)議中，節(jié)點(diǎn)維護(hù)著整個(gè)網(wǎng)絡(luò)的路由信息，這樣在有數(shù)據(jù)報(bào)文需要發(fā)送時(shí)，可以立即進(jìn)行傳送，因而適用于一些對(duì)實(shí)時(shí)性要求較高的業(yè)務(wù)和網(wǎng)絡(luò)環(huán)境。但是在拓?fù)浣Y(jié)構(gòu)變化頻繁的無(wú)線網(wǎng)絡(luò)環(huán)境中，DSDV可能存在一定的問(wèn)題，一是節(jié)點(diǎn)維護(hù)準(zhǔn)確路由信息的代價(jià)高，要頻繁地交換拓?fù)涓滦畔ⅲ欢怯械臅r(shí)候可能剛得到的路由信息隨即又失效了。因此，DSDV協(xié)議主要用于網(wǎng)絡(luò)規(guī)模不是很大，網(wǎng)絡(luò)拓?fù)渥兓鄬?duì)不是很頻繁的網(wǎng)絡(luò)環(huán)境，而在拓?fù)渥兓l繁的網(wǎng)絡(luò)中必須采用其他的方法。DSR（DynamicSourceRouting）路由協(xié)議DSR協(xié)議是一種基于源路由方式的按需路由協(xié)議。在DSR協(xié)議中，當(dāng)發(fā)送者發(fā)送報(bào)文時(shí)，在數(shù)據(jù)報(bào)文頭部攜帶到達(dá)目的節(jié)點(diǎn)的路由信息，該路由信息由網(wǎng)絡(luò)中的若干節(jié)點(diǎn)地址組成，源節(jié)點(diǎn)的數(shù)據(jù)報(bào)文就通過(guò)這些節(jié)點(diǎn)的中繼轉(zhuǎn)發(fā)到達(dá)目的節(jié)點(diǎn)。與基于表驅(qū)動(dòng)方式的路由協(xié)議不同的是，在DSR協(xié)議中，節(jié)點(diǎn)不需要實(shí)時(shí)維護(hù)網(wǎng)絡(luò)的拓?fù)湫畔?，因此在?jié)點(diǎn)需要發(fā)送數(shù)據(jù)時(shí)，如何能夠知道到達(dá)目的節(jié)點(diǎn)的路由是DSR路由協(xié)議需要解決的核心問(wèn)題。DSR路由協(xié)議主要由路由發(fā)現(xiàn)和路由維護(hù)兩部分組成。路由發(fā)現(xiàn)過(guò)程主要用于幫助源節(jié)點(diǎn)獲得到達(dá)目的節(jié)點(diǎn)的路由。DSR協(xié)議通過(guò)路由維護(hù)過(guò)程來(lái)監(jiān)測(cè)當(dāng)前路由的可用情況，當(dāng)監(jiān)測(cè)到路由故障時(shí)，將調(diào)用新的一輪路由發(fā)現(xiàn)過(guò)程。如路由中的節(jié)點(diǎn)由于移動(dòng)、關(guān)機(jī)等原因無(wú)法保證到達(dá)目的節(jié)點(diǎn)時(shí)，當(dāng)前的路由就不再有效了。同時(shí)為了提高系統(tǒng)性能，在DSR協(xié)議中，還引入了一系列的優(yōu)化技術(shù)，如路由緩沖（RouteCache）等。下面分別介紹這三部分內(nèi)容。1．路由發(fā)現(xiàn)節(jié)點(diǎn)通過(guò)路由發(fā)現(xiàn)過(guò)程獲得到達(dá)其他節(jié)點(diǎn)的路由。源節(jié)點(diǎn)首先向其鄰節(jié)點(diǎn)廣播“路由請(qǐng)求”（RouteRequest）報(bào)文。報(bào)文中包括“目的節(jié)點(diǎn)地址”、“路由記錄”以及“請(qǐng)求ID”等字段。其中“路由記錄”字段用于記錄從源節(jié)點(diǎn)到目的節(jié)點(diǎn)路由中的中間節(jié)點(diǎn)地址，當(dāng)路由請(qǐng)求報(bào)文到達(dá)目的節(jié)點(diǎn)時(shí)，該字段中的所有節(jié)點(diǎn)地址即構(gòu)成了從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路由?！罢?qǐng)求ID”字段由源節(jié)點(diǎn)管理分配中間節(jié)點(diǎn)維護(hù)<源節(jié)點(diǎn)地址，請(qǐng)求ID>序列對(duì)列表，<源節(jié)點(diǎn)地址，請(qǐng)求ID>序列用于惟一標(biāo)識(shí)一個(gè)路由請(qǐng)求報(bào)文，防止收到重復(fù)的路由請(qǐng)求。中間節(jié)點(diǎn)在收到源節(jié)點(diǎn)的路由請(qǐng)求報(bào)文后，按照以下步驟處理報(bào)文：（1）如果路由請(qǐng)求報(bào)文的<源節(jié)點(diǎn)地址，請(qǐng)求ID>存在于本節(jié)點(diǎn)的序列對(duì)列表中，表明此請(qǐng)求報(bào)文已經(jīng)收到過(guò)，節(jié)點(diǎn)不用處理該請(qǐng)求；否則轉(zhuǎn)步驟（2）；（2）如果節(jié)點(diǎn)的地址已在路由記錄字段中存在，節(jié)點(diǎn)不用處理該請(qǐng)求；否則轉(zhuǎn)步驟3；（3）如果請(qǐng)求報(bào)文的目的節(jié)點(diǎn)就是本節(jié)點(diǎn)，則路由記錄節(jié)點(diǎn)中的節(jié)點(diǎn)地址序列構(gòu)成了從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路由。節(jié)點(diǎn)向源節(jié)點(diǎn)發(fā)送“路由響應(yīng)”報(bào)文，同時(shí)將該路由拷貝到“路由響應(yīng)”報(bào)文中；否則轉(zhuǎn)步驟（4）；4）該節(jié)點(diǎn)是中間節(jié)點(diǎn)。將節(jié)點(diǎn)地址附在報(bào)文的“路由記錄”字段后，同時(shí)向鄰節(jié)廣播該路由請(qǐng)求。通過(guò)這種方法，路由請(qǐng)求報(bào)文將最終到達(dá)目的節(jié)點(diǎn)。如下圖所示為節(jié)點(diǎn)A到節(jié)點(diǎn)D的路由請(qǐng)求過(guò)程。虛線箭頭代表路由請(qǐng)求消息發(fā)送，括號(hào)中的內(nèi)容代表消息中的路由記錄。DSR路由請(qǐng)求過(guò)程幾個(gè)注意的問(wèn)題：（1）由于節(jié)點(diǎn)B已經(jīng)收到節(jié)點(diǎn)A的路由請(qǐng)求，因此不再處理節(jié)點(diǎn)F的路由請(qǐng)求消息；（2）節(jié)點(diǎn)D可能會(huì)同時(shí)收到節(jié)點(diǎn)C和E的路由請(qǐng)求消息，造成消息碰撞，反而收不到正確的路由請(qǐng)求，因此在AdHoc網(wǎng)絡(luò)中，廣播并非完全可靠?？梢圆捎靡欢ǖ牟呗詠?lái)避免，如節(jié)點(diǎn)隨機(jī)延時(shí)發(fā)送，或者節(jié)點(diǎn)間采用證實(shí)機(jī)制等。目的節(jié)點(diǎn)根據(jù)收到的源節(jié)點(diǎn)路由請(qǐng)求報(bào)文回送“路由響應(yīng)”報(bào)文。目的節(jié)點(diǎn)在將“路由響應(yīng)”報(bào)文轉(zhuǎn)發(fā)到源節(jié)點(diǎn)時(shí)，需要考慮這樣幾種情況：（1）目的節(jié)點(diǎn)有到達(dá)源節(jié)點(diǎn)的路由。此時(shí)目的節(jié)點(diǎn)可以直接使用該路由回送響應(yīng)報(bào)文；（2）如果目的節(jié)點(diǎn)沒(méi)有到源節(jié)點(diǎn)的路由，此時(shí)需要考慮節(jié)點(diǎn)通信信道問(wèn)題：①如果網(wǎng)絡(luò)中所有節(jié)點(diǎn)間的通信信道是對(duì)稱(chēng)的，此時(shí)目的節(jié)點(diǎn)到源節(jié)點(diǎn)的路由即為源節(jié)點(diǎn)到目的節(jié)點(diǎn)的反向路由；②如果信道是非對(duì)稱(chēng)的，目的節(jié)點(diǎn)就需要發(fā)起到源節(jié)點(diǎn)的路由請(qǐng)求過(guò)程，同時(shí)將路由響應(yīng)報(bào)文捎帶在新的路由請(qǐng)求中。如下圖所示為DSR的路由響應(yīng)過(guò)程。假設(shè)信道是雙向信道，節(jié)點(diǎn)D根據(jù)最短路由原則選擇了路由（A-B-C-D）作為最終路由，將此信息通過(guò)反向路由發(fā)送至源節(jié)點(diǎn)A。DSR路由響應(yīng)過(guò)程如果信道是單向呢？2．路由維護(hù)傳統(tǒng)的路由協(xié)議中通過(guò)周期性廣播路由更新消息將路由發(fā)現(xiàn)和路由維護(hù)過(guò)程合二為一。而在DSR協(xié)議中，由于沒(méi)有這種周期性的廣播，節(jié)點(diǎn)必須通過(guò)路由維護(hù)過(guò)程檢測(cè)路由的可用性。按照路由維護(hù)的不同檢測(cè)方法，可以將路由維護(hù)分為以下兩種：（1）點(diǎn)到點(diǎn)證實(shí)機(jī)制，又稱(chēng)為逐跳證實(shí)機(jī)制。即相鄰節(jié)點(diǎn)間通過(guò)數(shù)據(jù)鏈路層的消息證實(shí)或者高層應(yīng)用層之間的消息證實(shí)機(jī)制，來(lái)檢測(cè)路由中各鄰節(jié)點(diǎn)的可達(dá)性。當(dāng)發(fā)現(xiàn)節(jié)點(diǎn)間的傳輸故障，即路由不再有效時(shí)，向上級(jí)節(jié)點(diǎn)發(fā)送“路由差錯(cuò)”報(bào)文，收到路由差錯(cuò)報(bào)文的節(jié)點(diǎn)根據(jù)此信息將該路由從本節(jié)點(diǎn)的路由緩沖區(qū)中刪除。（2）端到端證實(shí)機(jī)制。在有些應(yīng)用中要求端到端節(jié)點(diǎn)間的證實(shí)，通過(guò)端到端的證實(shí)機(jī)制可以用來(lái)檢測(cè)整個(gè)路由的有效性。3．路由緩沖技術(shù)優(yōu)化策略在DSR協(xié)議中，為了提高系統(tǒng)效率，協(xié)議中采用了路由緩沖優(yōu)化策略。由于無(wú)線廣播信道的特點(diǎn)，節(jié)點(diǎn)可以處于“混合監(jiān)聽(tīng)”狀態(tài)，即可以聽(tīng)到相鄰節(jié)點(diǎn)發(fā)出的所有報(bào)文，包括路由請(qǐng)求、路由響應(yīng)等。這些報(bào)文中攜帶了網(wǎng)絡(luò)的一些路由信息，節(jié)點(diǎn)通過(guò)緩存這些路由信息，可以盡量減少每次發(fā)送新報(bào)文時(shí)啟動(dòng)的路由發(fā)現(xiàn)

過(guò)程，以提高系統(tǒng)的效率。如下圖所示，節(jié)點(diǎn)A通過(guò)發(fā)起目的節(jié)點(diǎn)為D的路由請(qǐng)求過(guò)程，獲得路由A-B-C-D，同時(shí)節(jié)點(diǎn)A也獲得了到達(dá)該路由中所有節(jié)點(diǎn)（如節(jié)點(diǎn)B、C）的路由，節(jié)點(diǎn)B等中間節(jié)點(diǎn)也獲得了到達(dá)節(jié)點(diǎn)D的路由。DSR路由緩沖技術(shù)同時(shí)，中間節(jié)點(diǎn)在收到源節(jié)點(diǎn)的路由請(qǐng)求時(shí)，如果本節(jié)點(diǎn)路由緩沖區(qū)中有到目的節(jié)點(diǎn)的路由，可以直接回復(fù)路由響應(yīng)消息。如節(jié)點(diǎn)F在發(fā)起到節(jié)點(diǎn)D的路由請(qǐng)求時(shí)，當(dāng)報(bào)文到達(dá)節(jié)點(diǎn)B時(shí)，節(jié)點(diǎn)B中有緩沖路由B-C-D，此時(shí)節(jié)點(diǎn)B可以直接回復(fù)路由響應(yīng)（F-B-C-D）。這樣一方面加快了路由請(qǐng)求的響應(yīng)，同時(shí)也減少了路由請(qǐng)求消息的廣播。盡管路由緩沖技術(shù)能夠在一定程度上提高系統(tǒng)的效率，但同時(shí)一些錯(cuò)誤或過(guò)期的路由緩沖信息（如由于某些節(jié)點(diǎn)的移動(dòng)使得路由失效）也會(huì)對(duì)網(wǎng)絡(luò)帶來(lái)負(fù)面影響，這些錯(cuò)誤的路由信息可能會(huì)影響和感染其他節(jié)點(diǎn)。對(duì)此，可以采用一定的策略來(lái)減少其影響。如為緩沖路由設(shè)定有效期，超過(guò)有效期的路由將被認(rèn)為無(wú)效，將其從緩沖區(qū)中刪除。4．DSR協(xié)議的優(yōu)缺點(diǎn)DSR協(xié)議具有以下幾個(gè)優(yōu)點(diǎn)：（1）僅在需要通信的節(jié)點(diǎn)間維護(hù)路由，減少了路由維護(hù)的代價(jià)；（2）路由緩沖技術(shù)可進(jìn)一步減少路由發(fā)現(xiàn)的代價(jià)；（3）由于采用了路由緩沖技術(shù)，因此在一次路由的發(fā)現(xiàn)過(guò)程中，會(huì)產(chǎn)生多種到達(dá)目的節(jié)點(diǎn)的路徑；（4）支持非對(duì)稱(chēng)傳輸信道模式。DSR協(xié)議存在一些問(wèn)題和不足：（1）由于采用源節(jié)點(diǎn)路由，每個(gè)數(shù)據(jù)報(bào)文的頭部都要攜帶路由信息，增加了報(bào)文長(zhǎng)度；（2）用于路由發(fā)現(xiàn)的控制報(bào)文可能會(huì)波及全網(wǎng)各節(jié)點(diǎn)，造成一定的耗費(fèi)；一種可行的優(yōu)化方法是控制路由發(fā)現(xiàn)報(bào)文的傳輸距離（如跳數(shù)），如果本輪路由發(fā)現(xiàn)失敗，后續(xù)的路由發(fā)現(xiàn)過(guò)程中再加大傳輸距離；（3）“路由響應(yīng)風(fēng)暴”（RouteReplyStorm）問(wèn)題。由于采用路由緩沖技術(shù)，中間節(jié)點(diǎn)根據(jù)自己的緩沖路由，對(duì)路由請(qǐng)求直接應(yīng)答，源節(jié)點(diǎn)會(huì)同時(shí)收到多個(gè)路由響應(yīng)，造成路由響應(yīng)信息之間的競(jìng)爭(zhēng)；（4）“錯(cuò)誤”緩沖路由對(duì)其他節(jié)點(diǎn)的影響。如果中間節(jié)點(diǎn)的路由緩沖記錄已經(jīng)過(guò)時(shí)，當(dāng)該節(jié)點(diǎn)根據(jù)緩沖路由回復(fù)路由請(qǐng)求時(shí)，其他監(jiān)聽(tīng)到此“錯(cuò)誤”路由的節(jié)點(diǎn)會(huì)更改自己的緩沖路由記錄，造成“錯(cuò)誤”緩沖路由的污染傳播。LAR（Locationaidedrouting）路由協(xié)議在DSR中，用于路由發(fā)現(xiàn)的控制報(bào)文可能會(huì)波及全網(wǎng)各節(jié)點(diǎn)，造成一定的耗費(fèi)。為了減少耗費(fèi)，有些路由協(xié)議采用一定的策略來(lái)減少路由發(fā)現(xiàn)報(bào)文的廣播。LAR協(xié)議就是利用位置信息來(lái)減少路由發(fā)現(xiàn)的廣播。這些物理的位置信息可以通過(guò)GPS系統(tǒng)獲得。兩個(gè)重要的概念——“預(yù)期區(qū)域”和“請(qǐng)求區(qū)域”。預(yù)期區(qū)域（ExpectedZone）和請(qǐng)求區(qū)域（RequestZone）假設(shè)當(dāng)前時(shí)間為t1，源節(jié)點(diǎn)S請(qǐng)求到目的節(jié)點(diǎn)D的路由。源節(jié)點(diǎn)S知道在t0歷史時(shí)刻（t0<t1）時(shí)目的節(jié)點(diǎn)D的位置為X。（1）預(yù)期區(qū)域：在t1時(shí)刻，節(jié)點(diǎn)D可能存在區(qū)域Y，如下圖中圓形陰影部分所示。源節(jié)點(diǎn)S通過(guò)在t0時(shí)刻目的節(jié)點(diǎn)D的位置和平均移動(dòng)速率V來(lái)判定節(jié)點(diǎn)D的預(yù)期區(qū)域Y。其中，r是預(yù)期區(qū)域的半徑，r=(t1-t0)×V。預(yù)期區(qū)域Y就是以X為圓心，以r為半徑的圓形區(qū)域。（2）請(qǐng)求區(qū)域：請(qǐng)求區(qū)域主要用于限定源節(jié)點(diǎn)洪泛其路由請(qǐng)求消息的范圍，它包含源節(jié)點(diǎn)S和“預(yù)期區(qū)域”的區(qū)域，如下圖中的矩形框部分所示。2．LAR協(xié)議的基本思路LAR協(xié)議的基本思路是通過(guò)請(qǐng)求區(qū)域來(lái)限定路由請(qǐng)求報(bào)文的洪泛范圍。在路由請(qǐng)求報(bào)文頭部攜帶請(qǐng)求區(qū)域信息，網(wǎng)絡(luò)中節(jié)點(diǎn)都知道自己當(dāng)前的物理位置。當(dāng)收到鄰節(jié)點(diǎn)的路由請(qǐng)求報(bào)文時(shí)，首先判斷自己當(dāng)前是否處在請(qǐng)求區(qū)域范圍中，如果不在請(qǐng)求范圍，則丟棄該路由請(qǐng)求報(bào)文。這樣就限定了路由請(qǐng)求報(bào)文的洪泛范圍，使得路由請(qǐng)求報(bào)文朝著正確的方向傳播。如下圖所示，節(jié)點(diǎn)A在收到節(jié)點(diǎn)S的路由請(qǐng)求報(bào)文時(shí)，由于它不在請(qǐng)求區(qū)域內(nèi)，因此不再轉(zhuǎn)發(fā)該路由請(qǐng)求。需要注意的是，在某些情況下，僅僅依靠請(qǐng)求區(qū)域中的節(jié)點(diǎn)可能無(wú)法找到到達(dá)目的節(jié)點(diǎn)的路由。如下圖所示，節(jié)點(diǎn)S和節(jié)點(diǎn)B之間無(wú)法直接通信，必須通過(guò)節(jié)點(diǎn)A轉(zhuǎn)接，而節(jié)點(diǎn)A又不在請(qǐng)求區(qū)域中，因此節(jié)點(diǎn)S在一段時(shí)間后收不到路由響應(yīng)報(bào)文時(shí)，必須擴(kuò)大請(qǐng)求區(qū)域（如圖中的虛線矩形框所示），重新發(fā)起新的路由請(qǐng)求。在極端情況下，請(qǐng)求區(qū)域可能會(huì)包含整個(gè)網(wǎng)絡(luò)。LAR協(xié)議中擴(kuò)大的請(qǐng)求區(qū)域LAR協(xié)議中的其他部分和DSR協(xié)議類(lèi)似。與DSR協(xié)議相比，LAR協(xié)議利用位置信息在一定程度上減少了路由請(qǐng)求報(bào)文的洪泛。但是，考慮到一些特殊的情況，在LAR中路由請(qǐng)求可能需要多次。這樣，一方面延長(zhǎng)了路由發(fā)現(xiàn)的時(shí)間，同時(shí)也增加了路由請(qǐng)求報(bào)文的發(fā)送次數(shù)，在某些極端情況下（如請(qǐng)求區(qū)域擴(kuò)大至整個(gè)網(wǎng)絡(luò)），其性能可能還不如DSR協(xié)議，因此在LAR協(xié)議中，需要折衷考慮路由發(fā)現(xiàn)時(shí)延和路由請(qǐng)求消息的耗費(fèi)問(wèn)題。3．LAR協(xié)議的幾種變化和更新在LAR協(xié)議中，針對(duì)不同的環(huán)境，采用了一些技術(shù)更新，如自適應(yīng)請(qǐng)求區(qū)域（AdaptiveRequestZone）、基于距離的轉(zhuǎn)發(fā)策略等。1）自適應(yīng)請(qǐng)求區(qū)域：在傳統(tǒng)的LAR協(xié)議中，請(qǐng)求區(qū)域由源節(jié)點(diǎn)確定，在路由請(qǐng)求的過(guò)程中請(qǐng)求區(qū)域大小不變。而在自適應(yīng)請(qǐng)求區(qū)域方式中，每個(gè)中間節(jié)點(diǎn)在收到路由請(qǐng)求報(bào)文時(shí)，根據(jù)自己的物理位置和目的節(jié)點(diǎn)的位置、移動(dòng)速度等信息，重新計(jì)算請(qǐng)求區(qū)域，在轉(zhuǎn)發(fā)的路由請(qǐng)求報(bào)文頭部攜帶自己更新的請(qǐng)求區(qū)域。LAR協(xié)議中的自適應(yīng)請(qǐng)求區(qū)域如下圖所示，實(shí)線矩形區(qū)域?yàn)樵垂?jié)點(diǎn)S的請(qǐng)求區(qū)域，虛線矩形區(qū)域?yàn)楣?jié)點(diǎn)B的請(qǐng)求區(qū)域。相對(duì)于源節(jié)點(diǎn)，節(jié)點(diǎn)B更接近目的節(jié)點(diǎn)，其請(qǐng)求區(qū)域也更小。因此，通過(guò)更新請(qǐng)求區(qū)域，可以進(jìn)一步縮小路由請(qǐng)求報(bào)文的洪泛范圍，使得路由請(qǐng)求報(bào)文朝著更加準(zhǔn)確的方向傳播。（2）基于距離的轉(zhuǎn)發(fā)策略：傳統(tǒng)的LAR協(xié)議中，節(jié)點(diǎn)是否轉(zhuǎn)發(fā)路由請(qǐng)求報(bào)文完全取決于自己的物理位置是否在請(qǐng)求區(qū)域中。在基于距離的轉(zhuǎn)發(fā)策略中，則是通過(guò)比較本節(jié)點(diǎn)與目的節(jié)點(diǎn)間的距離來(lái)決定是否轉(zhuǎn)發(fā)路由請(qǐng)求報(bào)文。DISTi表示節(jié)點(diǎn)與目的節(jié)點(diǎn)之間的距離，（Xd,Yd）表示目的節(jié)點(diǎn)D在t0時(shí)刻的位置坐標(biāo)，如下圖所示。節(jié)點(diǎn)I在向鄰節(jié)點(diǎn)轉(zhuǎn)發(fā)路由請(qǐng)求報(bào)文時(shí)，在報(bào)文頭部攜帶目的節(jié)點(diǎn)的坐標(biāo)（Xd,Yd）以及到目的節(jié)點(diǎn)的距離DISTi等信息。節(jié)點(diǎn)J在收到上游節(jié)點(diǎn)I的路由請(qǐng)求報(bào)文時(shí)，根據(jù)目的節(jié)點(diǎn)的坐標(biāo)計(jì)算本節(jié)點(diǎn)到目的節(jié)點(diǎn)的距離DISTj，并通過(guò)比較DISTi的大小來(lái)判斷是否應(yīng)轉(zhuǎn)發(fā)該路由請(qǐng)求消息。如果DISTi＋δ≥DISTj（δ≥0），即節(jié)點(diǎn)J至多比節(jié)點(diǎn)I距離目的節(jié)點(diǎn)遠(yuǎn)δ，節(jié)點(diǎn)J轉(zhuǎn)發(fā)該路由請(qǐng)求報(bào)文，同時(shí)用DISTj更新請(qǐng)求報(bào)文頭部的距離字段DISTi。當(dāng)δ=0時(shí)，表示節(jié)點(diǎn)J比節(jié)點(diǎn)I更靠近目的節(jié)點(diǎn)。引入δ變量主要是針對(duì)在某些特殊情況下，如上圖中的節(jié)點(diǎn)A，需要采用局部的迂回來(lái)尋找路由（類(lèi)似前面提到的擴(kuò)展請(qǐng)求區(qū)域）。如果DISTi＋δ<DISTj（δ≥0），節(jié)點(diǎn)J丟棄該路由請(qǐng)求報(bào)文。（3）位置信息的獲得和更新：節(jié)點(diǎn)的位置信息以及速率等信息是LAR協(xié)議中的重要因素。節(jié)點(diǎn)在發(fā)起路由請(qǐng)求的過(guò)程中，需要知道目的節(jié)點(diǎn)的位置和移動(dòng)速率，這些信息可以通過(guò)自己發(fā)起的或從網(wǎng)絡(luò)中監(jiān)聽(tīng)到的路由請(qǐng)求以及路由響應(yīng)等消息中獲得，位置信息隨著時(shí)間的變化實(shí)時(shí)更新，為以后的路由發(fā)現(xiàn)過(guò)程作準(zhǔn)備。節(jié)點(diǎn)也可以在發(fā)送的任何消息中攜帶自己的位置信息節(jié)點(diǎn)也可以主動(dòng)分發(fā)其位置信息。4．LAR協(xié)議的特點(diǎn)與DSR協(xié)議相比，LAR協(xié)議利用位置信息來(lái)限制路由請(qǐng)求消息的洪泛，從而在一定程度上減少了路由發(fā)現(xiàn)過(guò)程的耗費(fèi)，這是LAR協(xié)議最主要的優(yōu)點(diǎn)。但是，從另一個(gè)方面來(lái)看，為了獲得這些位置信息，網(wǎng)絡(luò)中的節(jié)點(diǎn)需要引入相應(yīng)的設(shè)備（如GPS等），增加位置信息的交互過(guò)程；4．LAR協(xié)議的特點(diǎn)同時(shí)這些位置信息也僅僅是物理坐標(biāo)信息，并不能完全代表節(jié)點(diǎn)間的可達(dá)性，例如節(jié)點(diǎn)之間雖然位置靠近，但由于中間有障礙物阻擋，可能節(jié)點(diǎn)無(wú)法直接通信；考慮到一些特殊的網(wǎng)絡(luò)環(huán)境，LAR協(xié)議可能需要多次發(fā)起路由請(qǐng)求過(guò)程才能最終成功。因此路由發(fā)現(xiàn)的時(shí)延以及耗費(fèi)等性能指標(biāo)在某些情況下未必比DSR協(xié)議優(yōu)越。AODV（Ad-hocOn-DemandDistanceVectorAlgorithm）協(xié)議在DSR中，采用了源節(jié)點(diǎn)路由方式，每個(gè)數(shù)據(jù)報(bào)文頭部都攜帶路由信息，增加了報(bào)文長(zhǎng)度，降低了傳輸效率，尤其是在數(shù)據(jù)報(bào)文本身很短的情況下，其耗費(fèi)尤為明顯。在AODV協(xié)議中，路由中的每個(gè)節(jié)點(diǎn)都維護(hù)路由表，因而數(shù)據(jù)報(bào)文頭部不再需要攜帶完整的路由信息，從而提高了協(xié)議的效率。 1．路由發(fā)現(xiàn)過(guò)程AODV協(xié)議采用與DSR協(xié)議類(lèi)似的廣播式路由發(fā)現(xiàn)機(jī)制。與DSR協(xié)議相比，AODV的路由依賴(lài)于中間節(jié)點(diǎn)建立和維護(hù)的動(dòng)態(tài)路由表。AODV的路由發(fā)現(xiàn)過(guò)程由反向路由的建立和前向路由的建立兩部分組成。反向路由指從目的節(jié)點(diǎn)到源節(jié)點(diǎn)的路由，用于將路由響應(yīng)報(bào)文回送至源節(jié)點(diǎn)。如下圖（a）所示，反向路由可能會(huì)有多條。前向路由指從源節(jié)點(diǎn)到目的節(jié)點(diǎn)方向的路由，用于以后數(shù)據(jù)報(bào)文的傳送。如下圖（b）所示。AODV的路由建立過(guò)程AODV的路由發(fā)現(xiàn)過(guò)程如下：（1）源節(jié)點(diǎn)首先發(fā)起路由請(qǐng)求過(guò)程，在發(fā)起的路由請(qǐng)求報(bào)文中攜帶以下信息字段：<源地址，源序列號(hào)，廣播ID，目的地址，目的序列號(hào)，跳數(shù)計(jì)數(shù)器>其中，序列對(duì)<源地址，廣播ID>惟一標(biāo)識(shí)一個(gè)路由請(qǐng)求。（2）中間節(jié)點(diǎn)在收到路由請(qǐng)求報(bào)文時(shí)，比較本節(jié)點(diǎn)和目的節(jié)點(diǎn)的地址，①如果自己是目的節(jié)點(diǎn)，則回復(fù)路由響應(yīng)報(bào)文。否則轉(zhuǎn)步驟②；②根據(jù)<源地址，廣播ID>判斷是否收到過(guò)該請(qǐng)求消息，如果收到過(guò)則丟棄該請(qǐng)求消息，否則轉(zhuǎn)向步驟③；③記錄相應(yīng)的信息，以形成反向路由。記錄的信息包括：上游節(jié)點(diǎn)地址（即向本節(jié)點(diǎn)發(fā)送路由請(qǐng)求消息的節(jié)點(diǎn)）、目的地址、源地址、廣播ID、反向路由超時(shí)時(shí)長(zhǎng)和源序列號(hào)等。同時(shí)跳數(shù)計(jì)數(shù)器加1，向鄰節(jié)點(diǎn)轉(zhuǎn)發(fā)該路由請(qǐng)求報(bào)文。2．路由表管理及維護(hù)AODV路由協(xié)議中的路由表主要包括目的節(jié)點(diǎn)下一跳節(jié)點(diǎn)距離目的節(jié)點(diǎn)的跳數(shù)目的節(jié)點(diǎn)序列號(hào)本路由的活躍鄰節(jié)點(diǎn)本路由的超期時(shí)長(zhǎng)等信息。同時(shí)，在AODV協(xié)議中，節(jié)點(diǎn)還存儲(chǔ)一些與路由表相關(guān)的信息。以下幾點(diǎn)是其中比較重要的。（1）路由請(qǐng)求超時(shí)定時(shí)器：和反向路由相關(guān)的定時(shí)器，當(dāng)定時(shí)器超期后，節(jié)點(diǎn)仍未收到路由響應(yīng)報(bào)文時(shí)，節(jié)點(diǎn)則認(rèn)為該反向路由無(wú)效，刪除該反向路由。（2）活躍超時(shí)時(shí)長(zhǎng)：和前向路由相關(guān)的時(shí)長(zhǎng)。當(dāng)超過(guò)活躍時(shí)長(zhǎng)時(shí)間后，節(jié)點(diǎn)仍然無(wú)數(shù)據(jù)利用該路由發(fā)送時(shí)，刪除該路由（即使該路由可能有效）。3．AODV協(xié)議的特點(diǎn)從前面介紹的DSDV協(xié)議和DSR協(xié)議來(lái)看，AODV協(xié)議綜合了兩者的特點(diǎn)。與基于表驅(qū)動(dòng)方式的DSDV協(xié)議相比，AODV協(xié)議采用了按需路由的方式，即網(wǎng)絡(luò)中的節(jié)點(diǎn)不需要實(shí)時(shí)維護(hù)整個(gè)網(wǎng)絡(luò)的拓?fù)湫畔?，而只是在發(fā)送報(bào)文且沒(méi)有到達(dá)目的節(jié)點(diǎn)的路由時(shí)，才發(fā)起路由請(qǐng)求過(guò)程；與DSR協(xié)議相比，在AODV協(xié)議中，由于通往目的節(jié)點(diǎn)路徑中的節(jié)點(diǎn)建立和維護(hù)路由表，數(shù)據(jù)報(bào)文頭部不再需要攜帶完整路徑，減少了數(shù)據(jù)報(bào)文頭部路由信息對(duì)信道的占用，提高了系統(tǒng)效率。因此，協(xié)議的帶寬利用率高，能夠及時(shí)對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化作出響應(yīng)，同時(shí)也避免了路由環(huán)路現(xiàn)象的發(fā)生。但是在AODV協(xié)議中也存在一些問(wèn)題。（1）AODV協(xié)議僅適用于雙向傳輸信道的網(wǎng)絡(luò)環(huán)境。由于在路由請(qǐng)求消息的廣播過(guò)程中建立了反向路由，供路由響應(yīng)報(bào)文尋路，因此網(wǎng)絡(luò)要滿(mǎn)足雙向傳輸信道的要求；（2）路由表中僅維護(hù)一條到指定的目的節(jié)點(diǎn)的路由，而在DSR協(xié)議中，源節(jié)點(diǎn)可以維護(hù)多條到目的節(jié)點(diǎn)的路由。如果節(jié)點(diǎn)間存在多條路由，當(dāng)某條路由失效時(shí)，源節(jié)點(diǎn)可以選擇其他的路由而不需要重新發(fā)起路由發(fā)現(xiàn)過(guò)程，這在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化頻繁的環(huán)境中尤其重要；（3）由于AODV協(xié)議采用了超時(shí)刪除路由的機(jī)制，因此即使路由未失效，在超過(guò)時(shí)限后也將被刪除。ZRP路由協(xié)議（ZoneRoutingProtocol）ZRP（ZoneRoutingProtocol）是一種利用集群結(jié)構(gòu)、混合使用表驅(qū)動(dòng)和按需路由策略的AdHoc網(wǎng)絡(luò)路由協(xié)議。在ZRP中，集群被稱(chēng)作域（Zone）。為了綜合利用按需路由和表驅(qū)動(dòng)路由的各自?xún)?yōu)點(diǎn)，ZRP規(guī)定每個(gè)節(jié)點(diǎn)在區(qū)域內(nèi)部采用表驅(qū)動(dòng)路由協(xié)議，對(duì)于區(qū)域外節(jié)點(diǎn)的路由則采用類(lèi)似于DSR中的按需路由機(jī)制尋找路由。ZRP中的區(qū)域、邊界節(jié)點(diǎn)。1．區(qū)域及邊界節(jié)點(diǎn)在ZRP中，域形成算法較為簡(jiǎn)單，它是通過(guò)一個(gè)重要的協(xié)議參數(shù)——區(qū)域半徑（以跳數(shù)為單位），指定每個(gè)節(jié)點(diǎn)維護(hù)的區(qū)域大小，即所有距離不超過(guò)區(qū)域半徑的節(jié)點(diǎn)都屬于該區(qū)域。一個(gè)節(jié)點(diǎn)可能同時(shí)從屬于多個(gè)區(qū)域。如下圖所示，橢圓形虛線部分表示為節(jié)點(diǎn)A的半徑為2（即2跳之內(nèi)）的區(qū)域，節(jié)點(diǎn)B、C、D、E、F都是節(jié)點(diǎn)A的域內(nèi)節(jié)點(diǎn)，節(jié)點(diǎn)G則是域外節(jié)點(diǎn)。需要注意的是，節(jié)點(diǎn)E既可以由B轉(zhuǎn)接到達(dá)（距離節(jié)點(diǎn)A兩跳），也可以由C-F轉(zhuǎn)接到達(dá)（距離節(jié)點(diǎn)A三跳），由于協(xié)議約定最小距離小于或等于區(qū)域半徑的節(jié)點(diǎn)都?xì)w屬于域內(nèi)節(jié)點(diǎn)，因此節(jié)點(diǎn)E是節(jié)點(diǎn)A的域內(nèi)節(jié)點(diǎn)。邊界節(jié)點(diǎn)是指最小距離正好等于區(qū)域半徑的節(jié)，在下圖中，節(jié)點(diǎn)D、E、F都是節(jié)點(diǎn)A的邊界節(jié)點(diǎn)。ZRP中的域及邊界節(jié)點(diǎn)（節(jié)點(diǎn)A，半徑為2）2．IARP和IERPZRP由兩個(gè)過(guò)程組成：（1