【正文】 議有 DSDV, LSR, WRP 等。節(jié)點(diǎn)不需要維護(hù)及時(shí)準(zhǔn)確的路由信息，當(dāng)需要發(fā)送數(shù)據(jù)時(shí)才Ad Hoc 網(wǎng)絡(luò)路由協(xié)議 主動路由協(xié)議 被動路由協(xié)議 混合路由協(xié)議 DSDV OLSR ZRP WRP DSR AODV DSDV TORA 湖南人文科技學(xué)院畢業(yè)設(shè)計(jì) 發(fā)起路由發(fā)現(xiàn)過程。另外，被動式路由協(xié)議在進(jìn)行路由發(fā)現(xiàn)時(shí)普遍采用廣播方式，這會導(dǎo)致許多控制信息重復(fù)地被傳送，進(jìn)而產(chǎn)生冗余、碰撞和競爭。 混合路由協(xié)議 混合路由協(xié)議， Ad hoc 無線網(wǎng)絡(luò)中單純采用主動式或被動式路由協(xié)議都不能完全解決路由問題，因此，許多學(xué)者提出了結(jié)合主動式和被動式路由協(xié)議優(yōu)點(diǎn)的混合式路由協(xié)議，這種主動被動混合式的路由能使在網(wǎng)絡(luò)一端新鏈路的產(chǎn)生對于本地是重大事件，而對另一端影響很小。每個(gè)節(jié)點(diǎn)必須記錄區(qū)域半徑內(nèi)所有節(jié)點(diǎn)的信息。典型的混合協(xié)議如 ZRP 協(xié)議。 湖南人文科技學(xué)院畢業(yè)設(shè)計(jì) Ad Hoc 網(wǎng)絡(luò)中典型路由協(xié)議 目前 Ad Hoc 網(wǎng)絡(luò)路由逐步由表驅(qū)動協(xié)議向按需路由協(xié)議以及混合路由協(xié)議轉(zhuǎn)變，這樣路由信息只在需要時(shí)才會計(jì)算出來，降低了額外負(fù)擔(dān)，但是其路由發(fā)現(xiàn)過程通常任然運(yùn)用洪泛實(shí)現(xiàn)。接下來就介紹幾種流行的 Ad Hoc 路由協(xié)議。 DSDV以路由信息協(xié)議為基礎(chǔ)。依據(jù) DSDV，網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)都保存有一個(gè)記錄所有目的節(jié)點(diǎn)和到目的節(jié)點(diǎn)條數(shù)的路由表。標(biāo)有更大 序列號的路由信息總是被接受。路由表更新分組在全網(wǎng)內(nèi)周期性的廣播而使路由表保持連貫性。它是從 IPANEMA 和 PRIMA 計(jì)劃所發(fā)展出來的，協(xié)議中節(jié)點(diǎn)周期性的交換包括 Hello 分組和 TC(Topology Control)分組在內(nèi)的各種控制分組，進(jìn)行分布式計(jì)算來建立網(wǎng)絡(luò)拓?fù)?。在掌握鏈路和鄰居信息的情況下，節(jié)點(diǎn)在自己鄰居節(jié)點(diǎn)中選擇一部分作為自己的 MPR，節(jié)點(diǎn)自己則成為 MS(MPR Selector)。同時(shí)在 TC 分組中， MPR 僅向全網(wǎng)通告自己 MS 節(jié)點(diǎn)的拓?fù)湫畔?。圖 就是一個(gè) OLSR 協(xié)議中多點(diǎn)中繼節(jié)點(diǎn)的示例。 路徑尋找時(shí)當(dāng)有封包要傳送，在查詢節(jié)點(diǎn)內(nèi)的路由快取表時(shí)，并沒有發(fā)現(xiàn)到有關(guān)目的的端的路徑記錄，此時(shí)節(jié)點(diǎn)就會發(fā)出路徑尋找的封包來搜尋可用路徑，路徑尋找的封包是運(yùn)用廣播的方式，對整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)來尋找有關(guān)目的端的路徑信息，當(dāng)其它節(jié)點(diǎn)中的路徑記錄，包含有關(guān)于目的端的路由信息，就會回復(fù)給發(fā)送端一個(gè)響應(yīng)信息，讓發(fā)送端來更新自己路由快取表，再由這條路徑來傳送封包，這就是路徑尋找所操作的過程。如圖 ，節(jié)點(diǎn) A 要傳信息給節(jié)點(diǎn) E，原本的路徑為 A— B— C— D— E，而因?yàn)槟承┰蚴沟霉?jié)點(diǎn) C 偵測不到節(jié)點(diǎn) D 的存在時(shí)，節(jié)點(diǎn) C 就會再傳送幾次請求封包到節(jié)點(diǎn) D，若還是得不到回應(yīng)，則節(jié)點(diǎn) C 會回復(fù)一個(gè)路徑錯(cuò)誤的信息節(jié)點(diǎn) A，告知節(jié)點(diǎn) A 此路徑的鏈接狀態(tài)，而節(jié)點(diǎn) A 會根據(jù)此更新信息將此路徑從路由快取表中刪除：信息是否要重新發(fā)送時(shí)由上層協(xié)議來決定，若有重新發(fā)送的需要，可以用兩種方式來達(dá)成： (1) 有其它的路徑傳送信息到節(jié)點(diǎn) E：由于 DSR 是屬于多重路徑，在發(fā)送端的路由快取表中可能會有不同的路徑到達(dá)目的端，當(dāng)其中一條路徑不可用時(shí)，發(fā)湖南人文科技學(xué)院畢業(yè)設(shè)計(jì) 送端可以選擇其它的路徑來原有的路徑，以 此達(dá)到重新發(fā)送的功能。 圖 路徑錯(cuò)誤時(shí)的機(jī)制運(yùn)作 AODV 路由協(xié)議 AODV(Ad Hoc OnDemand Distance Vector Routing)路由協(xié)議是在 DSDV 協(xié)議基礎(chǔ)上結(jié)合類似 DSR 中的按需路由機(jī)制進(jìn)行改進(jìn)后提出的，既借用了 DSR 的路由發(fā)現(xiàn)和路由維護(hù)機(jī)制，有利于了 DSDV 的逐跳路由、順序編號和路由維持階段的周期性更新?；谝陨咸攸c(diǎn)， AODV 協(xié)議成為自組網(wǎng)絡(luò)路由協(xié)議研究中的熱點(diǎn)。中間節(jié)點(diǎn)收到 RREQ 時(shí)，首先根據(jù)該 RREQ 提供的信息建立到上一跳的反間路由，接著查找自己的路由表，如果發(fā)現(xiàn)有到目的節(jié)點(diǎn)的有效路由，則通過反向路由傳送應(yīng)答 RREP(Route Reply)，包括源節(jié)點(diǎn)地址、目的節(jié)點(diǎn)地址、目 的節(jié)點(diǎn)序列號、跳數(shù)和生存時(shí)間。當(dāng) RREP 沿反向路徑回傳時(shí)建立前向路由條目，這樣源節(jié)點(diǎn)收到 RREP 時(shí)，從源到目的節(jié)點(diǎn)的路由就建立了。如果鏈路上不再有數(shù)據(jù)包傳遞，一段時(shí)間之后，鏈路就會過期，最終路由信息將會從中間節(jié)點(diǎn)的路湖南人文科技學(xué)院畢業(yè)設(shè)計(jì) 由表中刪除。 RERR 包括無法到達(dá)的節(jié)點(diǎn)地址和序列號，所有收到 RERR 的節(jié)點(diǎn)將相應(yīng)的路由設(shè)置為無效，并同理廣播RERR，源節(jié)點(diǎn)收到 RERR 后將重啟路由建立過程。另外，AODV 協(xié)議在路由發(fā)現(xiàn)時(shí)采用盲目洪泛 (Blind Flood)方式。因此， ADOV在路由發(fā)現(xiàn)時(shí)所采用的方式存在很大的冗余。在區(qū)內(nèi)使用主動路由算法，中心節(jié)點(diǎn)使用區(qū)內(nèi)路由協(xié)議 IARP(Intrazone Routing Protocol)維持一個(gè)到區(qū)內(nèi)其他成員的路由表，對區(qū)外節(jié)點(diǎn)的路由使用被動路由，利用區(qū)間路由協(xié)議 IERP(Interzone Routing Protocol)建立臨時(shí)的路由。也就是說，關(guān)于鄰居的信息部遙遠(yuǎn)的目的地節(jié)點(diǎn)的信息更重要。如圖 中節(jié)點(diǎn) S 維護(hù)兩跳的網(wǎng)絡(luò)拓?fù)洌虼巳绻?jié)點(diǎn) S 有數(shù)據(jù)要發(fā)送到節(jié)點(diǎn) H，可以使用主動路由協(xié)議直接發(fā)送數(shù)據(jù)，而如果 S 有數(shù)據(jù)要發(fā)送的節(jié)點(diǎn) L，由于 S 沒有 L 的信息，因此 S 執(zhí)行按需路由協(xié)議發(fā)送路由請求信息至邊緣節(jié)點(diǎn) G、 H、 I、 J、 K，節(jié)點(diǎn) J 和節(jié)點(diǎn) K 發(fā)現(xiàn)目的節(jié)點(diǎn)并發(fā)送路由回復(fù)。但目前 ZRP 采用預(yù)置固定區(qū)域半徑的做法，這無疑限制了它的適用性。 主動路由協(xié)議需要維持一張到網(wǎng)絡(luò)中所有節(jié)點(diǎn)的路由表，且當(dāng)拓?fù)渥兓瘯r(shí)，節(jié)點(diǎn)需將這一變化告知網(wǎng)絡(luò)中所有的節(jié)點(diǎn)，因而主動路由協(xié)議的存儲復(fù)雜度和通信復(fù)雜度很高。同時(shí)，節(jié)點(diǎn)要將拓?fù)渥兓l(fā)送到網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的控制開銷非常大。相比之下，按需路由僅在需要時(shí)維護(hù)路由信息，因此存儲復(fù)雜度和控制開銷均小于主動路由協(xié)議，所以在網(wǎng)絡(luò)負(fù)載較小并且節(jié)點(diǎn)移動速度較慢時(shí)可擴(kuò)展性很好。同樣，當(dāng)節(jié)點(diǎn)移動速度快時(shí)，節(jié)點(diǎn)間建立的路由很容易失效，這就需要重復(fù)發(fā)起路由請求。特別是DSR 協(xié)議采用源 路由轉(zhuǎn)發(fā)方式，每個(gè)數(shù)據(jù)分組都攜帶了路徑信息，造成的開銷很大，因此可擴(kuò)展性不強(qiáng)。 ZRP 協(xié)議綜合了主動路由協(xié)議和按需的優(yōu)點(diǎn)，在區(qū)域內(nèi)采用主動路由策略，以維護(hù)本地小范圍內(nèi)的路由狀態(tài) 。但在 ZRP 協(xié)議區(qū)域半徑的選擇、簇的選擇和維護(hù)、主動和被動路由協(xié)議的合理選擇以及網(wǎng)絡(luò)工 作的大流量等問題使 ZRP 協(xié)議很難實(shí)施。湖南人文科技學(xué)院畢業(yè)設(shè)計(jì) 第 4 章 Ad Hoc 網(wǎng)絡(luò)廣播 廣播是一種一對多的傳輸模式，主要目的是將一份信息傳輸給網(wǎng)絡(luò)上的所 有節(jié)點(diǎn)，也是維持網(wǎng)絡(luò)正常運(yùn)作的重要功能之一。 Ad Hoc 網(wǎng)絡(luò)中的廣播及其特點(diǎn) 廣播是 無線網(wǎng)絡(luò)中基本且重要的操作，可用于傳遞網(wǎng)絡(luò)控制信息、呼叫特定主機(jī)、發(fā)送報(bào)警信號等。洪泛是最直觀和常見的一種廣播算法，在這種算法中，任一主機(jī)對于相同的廣播消息都精確轉(zhuǎn)播一次。 Ad Hoc 網(wǎng)絡(luò)是一個(gè)由移動節(jié)點(diǎn)組成的網(wǎng)絡(luò)，節(jié)點(diǎn)只能與自己相鄰范圍內(nèi)的節(jié)點(diǎn)直接相互通信。 Ad Hoc 網(wǎng)絡(luò)的移動性決定了需要周期性地進(jìn)行廣播，如為了尋找路徑，路徑的維護(hù)與更新，但大量的廣播消息給網(wǎng)絡(luò)帶來的負(fù)面影響要遠(yuǎn)大于其實(shí)際效應(yīng)。本文假設(shè)在 MANET 中，移動主機(jī)共享單一的普通載波偵聽多路訪問信道。 (2)廣播 是不可靠的。此外，主機(jī)可能因?yàn)殡x線，臨時(shí)與網(wǎng)絡(luò)失去連通或者是遭遇重復(fù)的碰撞而丟失廣播消息。 (3)不采用請求發(fā)送 /清除發(fā)送 (RTS/CTS)對話機(jī)制。 (4)主機(jī)能夠發(fā)現(xiàn)重復(fù)的廣播信息。 Ad Hoc 網(wǎng)絡(luò)中廣播風(fēng)暴 當(dāng)前尚無一種專門為 Ad hoc 網(wǎng)絡(luò)設(shè)計(jì)的廣播協(xié)議。泛洪式廣播法是一種簡單的執(zhí)行策略，在這個(gè)策略下，所有的節(jié)點(diǎn)不論何時(shí)收到第一個(gè)廣播包都有義務(wù)將這個(gè)廣播包繼續(xù)傳給它鄰近的節(jié)點(diǎn)。 廣播信息冗余分析 移動 Ad Hoc 網(wǎng)絡(luò)中的節(jié)點(diǎn)一般使用全向天線，其覆蓋范圍內(nèi)的節(jié)點(diǎn)都可以收到信號。產(chǎn)生冗余的主要原因是來自不同發(fā)射天線的無線信號很容易相互重疊。 圖 廣播冗余示意圖 湖南人文科技學(xué)院畢業(yè)設(shè)計(jì) 我們來對廣播冗余來簡單分析，由于轉(zhuǎn)發(fā)廣播信息帶來了信號覆蓋面積的增益。用 S a 和S b 分別 表示 A 和 B 的傳輸覆蓋面積，陰影部分 S ba 表示 B 轉(zhuǎn)發(fā)的額外覆蓋面積。同樣，還可以得到額外覆蓋面積的平均 值。現(xiàn)在考慮如果主機(jī) C 收到 A 和 B 的廣播后決定繼續(xù)廣播， C 轉(zhuǎn)發(fā)可以獲得的額外面積為 |Sc A∩ B| ≈ [12] ，這表明在此情況下通過廣播轉(zhuǎn)發(fā)來找新主機(jī)的可能性事非常小的。當(dāng) k ≥4 時(shí)，額外覆蓋面積小于 5%[16]。當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)密度大時(shí)，產(chǎn)生競爭的幾率就會變大。 分析當(dāng) N=2 的簡單情況。當(dāng) C 位于 SA∩ B 的時(shí)候，就會產(chǎn)生競爭，所以競爭的概率是 |SA∩B| / ∏ r2。如果 在 A 的傳輸范圍內(nèi)隨機(jī) 存在 的 N 臺主機(jī)中 K 臺主機(jī)轉(zhuǎn)發(fā)廣播信息不發(fā)生競爭的概率為 CF(n, k)，所有 N 臺主機(jī)發(fā)生競爭的概率在 N≥ 6 時(shí)迅速增加到 [3]以上。再者，幾乎不存在多臺主機(jī) (k≥ 2)發(fā)送時(shí)不發(fā)生信道爭搶的情況。因此，對于使用 IEEE 802． 11Mac 分類的中心協(xié)調(diào)方式 (PCF)工作模式不予考慮，而主要研究在分布式協(xié)調(diào) 方式 (DCF)工作模式下的行為。執(zhí)行退避程序時(shí)，首先要從現(xiàn)有的退避窗口隨 機(jī)選取了 一 個(gè)整數(shù)作為計(jì)數(shù)，如果主機(jī)的信道清除評估 (CCA)機(jī)制探測 到在過去的時(shí)間間隙內(nèi) ( 一個(gè)固定的時(shí)期 )信道空閑，計(jì)數(shù)器就減 1。 考慮幾個(gè)相鄰主機(jī)都接收到主機(jī) x 廣播信息的情形下，產(chǎn)生碰撞的原因有以下幾個(gè)。那么，當(dāng)收到廣播消息后，它們就可能 同時(shí)開始轉(zhuǎn) 發(fā)此廣播信息。第二，由于在廣播傳輸 中沒有使用 RTS／ CTS 預(yù)警對話機(jī)制，碰撞將會更加嚴(yán)重。 現(xiàn)有應(yīng)對 Ad Hoc 網(wǎng)絡(luò)廣播風(fēng)暴的機(jī)制 由于廣播風(fēng)暴產(chǎn)生的主要原因是廣播報(bào)文的重復(fù)傳送，進(jìn)而導(dǎo)致競爭和碰撞的情況 。當(dāng) 下比較常用的廣播方法有這幾類：基于概率的方法、基于計(jì)數(shù)器的方法、基于距離的方法、基于位置的方法、基于角度的方法、基于角度的方法。 概率型算法 概率算法 (Probabilistic Scheme)，它與洪泛相似，只是當(dāng)節(jié)點(diǎn)收到一個(gè)廣播信息時(shí)僅以概率 p 轉(zhuǎn)發(fā)該信息。概率的減小會降低廣播風(fēng)暴的作用，覆蓋范圍也隨之減小。 考慮到信道爭搶和碰撞的問題，應(yīng)該在轉(zhuǎn)發(fā)消息 前加上一個(gè)小的隨機(jī)時(shí)延，這樣就可以使得轉(zhuǎn)發(fā)在世間上更加分散。但是，在這種算法中，要實(shí)時(shí)地對節(jié)點(diǎn)進(jìn)行評估，所以該算法可能不能找到源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最佳路徑，而且，對某以網(wǎng)絡(luò)結(jié)果的最佳概率 p并不一定是另一個(gè)網(wǎng)絡(luò)結(jié)構(gòu)的最佳概率。當(dāng)節(jié)點(diǎn)首次收到一個(gè)報(bào)文時(shí)啟動一個(gè)計(jì)數(shù)器 (其初始值為 1) 和一個(gè)定時(shí)器 RAD(其 超時(shí)時(shí)間在 0s 到 T max之間隨湖南人文科技學(xué)院畢業(yè)設(shè)計(jì) 機(jī)選擇 )。當(dāng)計(jì)時(shí)器超時(shí)且計(jì)時(shí)器小于一個(gè)門限值 C，則節(jié)點(diǎn)對該報(bào)文進(jìn)行轉(zhuǎn)發(fā)，否則丟棄該報(bào)文?，F(xiàn)節(jié)點(diǎn) 1 發(fā)送一個(gè)廣播報(bào)文，節(jié)點(diǎn) 2 和節(jié)點(diǎn) 3 收到該報(bào)文后啟動定時(shí)器并分別是c=1。由于節(jié)點(diǎn) 2 的 c 值已經(jīng)達(dá)到 C(C=2)，所以不對報(bào)文進(jìn)行轉(zhuǎn)發(fā)。另外，隨機(jī)時(shí) 延的引入會導(dǎo)致報(bào)文傳輸時(shí)間延長。 圖 計(jì)數(shù)器算法示意圖 根據(jù)本文 節(jié)所介紹的，接收到同一條消息 k 次后再轉(zhuǎn)發(fā)所能獲得的額外覆蓋范圍 EAC(k)，它隨著 k 的增加而迅速減小。具體的說，用一個(gè)計(jì)數(shù)器 c 來跟蹤記錄廣播消息收到的次數(shù)。 這種算法于洪泛相比，在主機(jī)分布密集的時(shí)候，計(jì)數(shù)器算法可以減少許多冗余廣播包，但它在 一定程度上增加了每個(gè)節(jié)點(diǎn)的時(shí)延。 基于距離算法 基于距離的算法 (DistanceBased Scheme)，算法根據(jù)主機(jī)之間的距離判斷節(jié)點(diǎn)是否需要對廣播報(bào)文進(jìn)行轉(zhuǎn)發(fā)。如果 d 很小，則 H 對來自 S 的報(bào)文的轉(zhuǎn)發(fā)所獲得的額外覆蓋面積也就小，否則額外覆蓋面積就大。反之，如果 S 與 H 之間的距離等于節(jié)點(diǎn)的傳輸半徑，則 H 對報(bào)文的轉(zhuǎn)發(fā)可獲得最大的額外面積。若節(jié)點(diǎn)與廣播上一跳節(jié)點(diǎn)的距離小于一個(gè)預(yù)先給定的值 D，則丟棄該報(bào)文。我們?nèi)砸詧D 為例，假定網(wǎng)絡(luò)中的節(jié)點(diǎn)執(zhí)行基于距離的廣播算法，如果節(jié)點(diǎn) 1 與節(jié)點(diǎn) 2 的距離以及節(jié)點(diǎn) 1 與節(jié)點(diǎn) 3 的距離都未超過極限值 D，則節(jié)點(diǎn) 4 不會收到來自節(jié)點(diǎn) 1 的信息。如果計(jì)算出的額外面積小于一個(gè)門限值，節(jié)點(diǎn)將不對接收到的報(bào)文轉(zhuǎn)發(fā)。如果在等待期間內(nèi)接收到相同的消息，節(jié)點(diǎn)重新計(jì)算額外覆蓋面積并與門限值比較。 該算法需要節(jié)點(diǎn)的具體位置來計(jì)算出額外覆蓋面積 EAC(A)，這就可以利用位置裝置如全球定位系 統(tǒng) GPS 提供服務(wù)。那么我們可以用該值與預(yù)定的覆蓋門限 A 相比較來決定是否將接收到的消息重新廣播。在只有四個(gè)圓的時(shí)候，計(jì)算 AC 就已經(jīng)比較難了。下面我們通過圖形來 分析。通過上述觀察，我們可以規(guī)定只有當(dāng)主機(jī)不在凸多變形內(nèi)時(shí)才能進(jìn)行轉(zhuǎn)發(fā)。如果 X 在多邊形內(nèi)，通過 邊形測試禁止主機(jī) X 轉(zhuǎn)發(fā)，那么最多有 22%[4]的額外覆蓋面積丟失。所能獲得的額外覆蓋面積最大。此外要得到額外覆蓋面積需要計(jì)算很多圓的交集，開銷很大，這樣會消耗節(jié)湖南人文科技學(xué)院畢業(yè)設(shè)計(jì) 點(diǎn)寶貴的能量資源。 假設(shè)我們已知主機(jī)節(jié)點(diǎn) S 和它們的鄰居節(jié)點(diǎn) N 以及它們的覆蓋半徑 RS， RN如圖 所示。取 S 的正東方以 RS為班級的圓