動態(tài)源路由 dynamic source routing(DSR)

初始節(jié)點(diǎn)S 通過洪泛 發(fā)送 RREQ（route request 路由請求包）

每個經(jīng)過的節(jié)點(diǎn)都將自己的標(biāo)識加入到控制包中（慢慢的形成一條路徑）

目標(biāo)節(jié)點(diǎn)D收到第一個RREQ之后，根據(jù)RREQ中的路由反轉(zhuǎn)，發(fā)送RREP（route reply 路由回復(fù)包），RREP包含了S到D的路由信息。

• RREP 只能在半雙工傳輸鏈路中傳送，因此發(fā)送RREQ的時候應(yīng)該只發(fā)送給滿足半雙工傳輸路徑的節(jié)點(diǎn)（即發(fā)給他，他也能發(fā)給我，全雙工是能同時收發(fā)，半雙工是雙向收發(fā)，但不能同時）
• 如果路徑中的節(jié)點(diǎn)允許非全雙工（非對稱）那么可能目標(biāo)節(jié)點(diǎn)還需要發(fā)現(xiàn)到S的路由。（即不能反轉(zhuǎn)S到D的路由，還得重新尋找回去的路）
  • 如果路由D已經(jīng)知道了到S的路由，那么RREP會經(jīng)過這個路由發(fā)送

源節(jié)點(diǎn)S收到目標(biāo)節(jié)點(diǎn)D的RREP之后

• S將會捕獲S到D的路由信息
• S發(fā)送給D的數(shù)據(jù)包中，在頭部將會包含整條路由信息（hence the name source routing)
• 中間負(fù)責(zé)轉(zhuǎn)發(fā)的節(jié)點(diǎn)根據(jù)數(shù)據(jù)包頭部的souce route來決定轉(zhuǎn)發(fā)給哪個節(jié)點(diǎn)

什么時候執(zhí)行路由發(fā)現(xiàn)：當(dāng)節(jié)點(diǎn)S要發(fā)送數(shù)據(jù)包給D但是不知道S到D的路徑的時候。（廢話）

改進(jìn)DSR優(yōu)化：路由緩存 route caching

在路由發(fā)現(xiàn)過程中可以充分利用所有涉及的節(jié)點(diǎn)已知的信息。

路由緩存的使用

情景一：當(dāng)節(jié)點(diǎn)S獲知到節(jié)點(diǎn)D的路由中斷的時候，它會從路由緩存中找到一條可行的路由。否則就發(fā)送RREQ進(jìn)行路由發(fā)現(xiàn)。

情景二：中間節(jié)點(diǎn)X如果收到了一個路由請求并且知道從X到目標(biāo)節(jié)點(diǎn)的路由，那么X可以直接發(fā)送RREP給S。

• 可以加速路由發(fā)現(xiàn)
• 可以減少路由請求的傳輸

路由緩存需要注意的

• 過期的路由緩存會影響性能stale caches
• 隨著時間流逝和終端的移動，已經(jīng)獲知的路由信息可能會無效/過期。
• 發(fā)送者可能需要多次嘗試才能找到一條好的路由

DSR優(yōu)點(diǎn)

• 只有必要的節(jié)點(diǎn)之間才進(jìn)行路由保持連接
• 路由緩存能夠進(jìn)一步減少路由發(fā)現(xiàn)的開銷
• 一個路由發(fā)現(xiàn)過程可能會產(chǎn)生許多到目標(biāo)節(jié)點(diǎn)的路由。因?yàn)橹虚g節(jié)點(diǎn)從本地緩存中進(jìn)行回復(fù)。

DSR缺點(diǎn)

• 路由長度過長，包的頭部過大（可能會導(dǎo)致負(fù)載降低，即包頭比數(shù)據(jù)還大）
• 路由請求信息洪泛可能會到達(dá)所有的節(jié)點(diǎn)
• 需要避免相鄰節(jié)點(diǎn)之間的路由請求沖突：在轉(zhuǎn)發(fā)RREQ之前設(shè)置隨機(jī)延遲（即，隱藏終端問題）
• 沖突加劇：如果大量的節(jié)點(diǎn)用本地緩存路由信息進(jìn)行回復(fù)
  • 路由回復(fù)風(fēng)暴問題 route reply storm problem（后面有風(fēng)暴問題的解決方案）
  • 當(dāng)一個節(jié)點(diǎn)獲知別的節(jié)點(diǎn)有更短的路由RREP已經(jīng)發(fā)送的時候就不用再發(fā)RREP了，這樣可以緩解路由回復(fù)風(fēng)暴問題。
• 一個中間節(jié)點(diǎn)的本地緩存路由信息可能是過時的，而它用這個信息進(jìn)行回復(fù)會**污染其他的緩存。**polluteing other caches
• 這個問題可以通過引入某種凈化機(jī)制來緩解。
• 一些可行的凈化方案
  • 靜態(tài)超時 static timeouts設(shè)置超時時間（時間到了就清除路由緩存信息，或者使用一個隊(duì)列，將比較久的信息清除）
  • adaptive timeouts based on link stability 根據(jù)鏈接穩(wěn)定性設(shè)置動態(tài)的超時時間，例如鏈接不穩(wěn)定的時候超時時間短（鏈路不穩(wěn)定的狀態(tài)下，路由信息失效更快）

洪泛控制包的時候

• 如何減少路由請求洪泛的范圍
  • LAR 位置輔助路由
  • Query localization 查詢本地化
• 如何減少冗余的廣播
  • 廣播風(fēng)暴問題

位置輔助路由LAR

Location Aided Routing

位置可以通過GPS獲得，或者其他什么方式。

期望區(qū)域Expected Zone：即目標(biāo)節(jié)點(diǎn)可能的區(qū)域范圍，基于之前的目標(biāo)節(jié)點(diǎn)的位置信息以及目標(biāo)節(jié)點(diǎn)移動的速度

請求區(qū)域Request Zone：包含目標(biāo)節(jié)點(diǎn)期望域和發(fā)送節(jié)點(diǎn)的區(qū)域

LAR算法：

• 只有在請求域內(nèi)的節(jié)點(diǎn)才轉(zhuǎn)發(fā)請求（請求域外內(nèi)的節(jié)點(diǎn)收到請求即丟棄，不轉(zhuǎn)發(fā)，這樣能縮小洪泛范圍）
• 在請求頭中顯式地包含了路由請求的請求域（即物理劃定的范圍，節(jié)點(diǎn)知道自己的物理信息，能判斷自己是否在該范圍內(nèi)）
• 每個節(jié)點(diǎn)都必須知道自己的位置以決定是否轉(zhuǎn)發(fā)收到的請求
• 如果Sender初始化的請求域太小以至于沒找到目標(biāo)節(jié)點(diǎn)，那么一段時間后重新初始化一個較大的請求域（請求范圍），最大的范圍可能包含整個網(wǎng)絡(luò)（相當(dāng)于完全洪泛）
• 其余的部分同DSR（動態(tài)源路由協(xié)議）

LAR優(yōu)化：動態(tài)請求域 adaptive request zone

• 每個節(jié)點(diǎn)可以根據(jù)自己掌握的信息更改請求域（請求域逐漸縮小）
• 更新后的請求域使用的是最新的、較為準(zhǔn)確的位置信息，可能比原始的請求域小

LAR優(yōu)化：模糊請求域implicit request zone

• 之前的模式中，路由請求顯式地包含了請求域，這次不包含而是由節(jié)點(diǎn)決定是否轉(zhuǎn)發(fā)
• 如果節(jié)點(diǎn)X相對于節(jié)點(diǎn)Y更接近目標(biāo)節(jié)點(diǎn)，那么節(jié)點(diǎn)X就轉(zhuǎn)發(fā)節(jié)點(diǎn)Y的請求
• 動機(jī)是：盡可能地讓路由請求在每一次轉(zhuǎn)發(fā)之后更接近目標(biāo)節(jié)點(diǎn)
• 基于這樣一個假設(shè)：在路由發(fā)現(xiàn)過程中，節(jié)點(diǎn)X的位置Y是知道的

LAR優(yōu)點(diǎn)

• 減少了路由請求洪泛的范圍
• 減少了路由發(fā)現(xiàn)的開銷

LAR缺點(diǎn)

• 每個節(jié)點(diǎn)都必須知道自己的物理位置
• 沒有考慮在信號傳輸過程中可能存在的障礙物 obstructions for radio transmissions

Distance Routing Effect Algorithm for Mobility(DREAM)

移動的距離路由效應(yīng)算法

注意：LAR洪泛的是控制包，而DREAM洪泛的是數(shù)據(jù)包，不需要事先知道路由（不需要發(fā)起路由發(fā)現(xiàn)的過程）

• 利用位置信息和速度（同LAR）
• 直接洪泛數(shù)據(jù)包（不同于LAR）
  

如上圖所示，S發(fā)送數(shù)據(jù)包給在圓錐區(qū)域內(nèi)的所有鄰接節(jié)點(diǎn)（它知道目標(biāo)節(jié)點(diǎn)的大概方位，但是不知道路徑）

• 收到數(shù)據(jù)包的節(jié)點(diǎn)A在一個更小的圓錐區(qū)域內(nèi)轉(zhuǎn)發(fā)請求（它也知道目標(biāo)節(jié)點(diǎn)大概的方位，但是不知道路徑）
• 所有收到數(shù)據(jù)包的節(jié)點(diǎn)都如同A一樣操作直到找到目標(biāo)節(jié)點(diǎn)

前提是，所有的節(jié)點(diǎn)都要知道自己的位置以及鄰接節(jié)點(diǎn)的位置

• 節(jié)點(diǎn)需要周期性地廣播自己的物理位置
• 廣播的范圍應(yīng)該也是圓錐區(qū)域（而不是全網(wǎng)），所以距離自己近的節(jié)點(diǎn)更新頻繁，距離遠(yuǎn)的節(jié)點(diǎn)更新就慢。
• Distance Effect：距離遠(yuǎn)的節(jié)點(diǎn)相對于距離近的節(jié)點(diǎn)以較慢的角速度移動
• 使用TTL來控制廣播信息/數(shù)據(jù)包發(fā)送的距離。如果TTL短，發(fā)送的距離也短，TTL（time to live存活時間)到了就認(rèn)為失敗。

Relative Distance Micro-Discovery Routing（RDMAR）

相對距離微發(fā)現(xiàn)路由

• 發(fā)送節(jié)點(diǎn)先評估到目標(biāo)節(jié)點(diǎn)的跳數(shù)
• 根據(jù)以上的評估來設(shè)置TTL
• 評估依據(jù)是：之前的目標(biāo)節(jié)點(diǎn)到發(fā)送節(jié)點(diǎn)之間的物理距離以及傳輸范圍

Gerographic Distance Routing（GEDIR）

地理距離的路由

• 假設(shè)目標(biāo)節(jié)點(diǎn)的位置是已知的
• 每個節(jié)點(diǎn)都知道自己的鄰接節(jié)點(diǎn)的位置
• 每個節(jié)點(diǎn)轉(zhuǎn)發(fā)包給距離自己最近的鄰接節(jié)點(diǎn)
• 但是可能會存在不可達(dá)的情況，因?yàn)榫植孔疃搪窂饺植灰欢ㄊ亲疃痰?#xff0c;甚至是不可達(dá)的
• 如果相同的邊遍歷了兩次，認(rèn)為路由發(fā)現(xiàn)失敗（不可達(dá)），即C發(fā)給G，G又發(fā)給C。

Routing with Guaranteed Delivery

保證交付的路由

• 基于GEDIR改進(jìn)：保證轉(zhuǎn)發(fā)，即提供一條確定存在的源到目標(biāo)的路徑
• Guarantees delivery(using location information) provided that a path exists from source to destination
• 必要的時候路由可以繞道，回溯。routes around obstacles if necessary

Query Localization查詢本地化

• limits route request flood without using physical information 在不需要物理信息的前提下限制洪泛范圍
• route requests are propagated only alone paths that are close to the previously known route 路由請求的轉(zhuǎn)發(fā)只基于之前已知的路由路徑
• the closeness property is defined without using physical location information 所謂的最近定義不基于物理位置信息
• path locality heuristic(啟發(fā)式的，探索式的)：look for a new path that contains at most K nodes that were not present in the previously known route 尋找一條新的路徑包含最多K個新節(jié)點(diǎn)，這K個節(jié)點(diǎn)并不包含在最近已知的路徑中。
• route request is forwarded only if the accumulated route in the route request contains at most k new nodes that were absent in the old route,this limits propagation of the route request.
• 只有當(dāng)路由請求頭中的節(jié)點(diǎn)包含至多K個新的節(jié)點(diǎn)（之前的路由中沒有出現(xiàn)過的節(jié)點(diǎn)）時，本次路由才會轉(zhuǎn)發(fā)，這大大限制了路由轉(zhuǎn)發(fā)的數(shù)量。

查詢本地化的優(yōu)勢

• 在不用物理位置信息的前提下減少了路由轉(zhuǎn)發(fā)的開銷
• 可以在舊路由的鄰近區(qū)域搜索新路由，在有障礙物的情況下表現(xiàn)更好

查詢本地化的缺點(diǎn)

可能會產(chǎn)生比LAR更長的路由，最短的路由可能包含了超過K個新節(jié)點(diǎn)，所以找到的路由不一定是最短的。

看這個例子，之前已知道的路由SAD（舊的路由），現(xiàn)在D移動了位置變成了右邊的樣子。

這樣只需要在舊的路由的基礎(chǔ)上，最多再洪泛兩個節(jié)點(diǎn)，即SABE，或者SABC.失敗了就增大K。

而F節(jié)點(diǎn)不會轉(zhuǎn)發(fā)請求，因?yàn)榧由螰節(jié)點(diǎn)就是新增三個節(jié)點(diǎn)了，這樣能夠控制洪泛的范圍。

廣播風(fēng)暴問題 Broadcast Storm Problem

• 冗余:一個節(jié)點(diǎn)可能會收到許多節(jié)點(diǎn)的相同信息
• 概率模式：一個節(jié)點(diǎn)第一次收到請求的時候，它以概率P來決定是否轉(zhuǎn)發(fā)
• 或者：不同節(jié)點(diǎn)延遲轉(zhuǎn)發(fā)，采取碰撞避免機(jī)制。如果同時轉(zhuǎn)發(fā)到一個節(jié)點(diǎn)，很容易會導(dǎo)致碰撞。wait a random delay when channel is idle(無事可做的)
• 計(jì)數(shù)模式：如果一個節(jié)點(diǎn)E接收到超過K個鄰居的路由請求，不進(jìn)行轉(zhuǎn)發(fā)。（這意味著這個節(jié)點(diǎn)E周圍已經(jīng)有很多洪泛數(shù)據(jù)了）
  • 直覺上認(rèn)為這K個鄰居已經(jīng)轉(zhuǎn)發(fā)給這個節(jié)點(diǎn)E的所有鄰居了。
• **基于距離模式：**如果E接收到節(jié)點(diǎn)Z的請求轉(zhuǎn)發(fā)，而節(jié)點(diǎn)E和Z的距離小于d,則E不進(jìn)行轉(zhuǎn)發(fā)。
  • 直覺上認(rèn)為：E和Z太近了，E和Z覆蓋的區(qū)域相差不大，即便E進(jìn)行了轉(zhuǎn)發(fā)，所能通知到的新節(jié)點(diǎn)也寥寥無幾。

廣播風(fēng)暴問題總結(jié)

• 概率轉(zhuǎn)發(fā)，延遲轉(zhuǎn)發(fā)，計(jì)數(shù)模式，距離模式
• 洪泛會導(dǎo)致：碰撞，冗余
• 碰撞問題：通過延遲轉(zhuǎn)發(fā)解決，waiting for a random interval before propagating the flood
• 冗余問題：通過選擇性的轉(zhuǎn)發(fā)來解決

Ad Hoc On-Demand Distance Vector Routing (AODV) 按需距離矢量路由協(xié)議

總結(jié)：只有需要的時候才發(fā)起路由請求，路由信息保存在每個節(jié)點(diǎn)上，每個節(jié)點(diǎn)只保存到下一跳的信息。

• 動態(tài)源路由頭部包含了路由信息，這導(dǎo)致頭部越來越大，可能會讓負(fù)載有效率降低，即頭部比負(fù)載信息還大。
• AODV將路由表保存在節(jié)點(diǎn)，這樣數(shù)據(jù)包就不用包含路由信息了
• AODV和DSR一樣只有節(jié)點(diǎn)之間需要通信的時候才保持連接。
• RREQ發(fā)送的過程同DSR
• 當(dāng)一個節(jié)點(diǎn)轉(zhuǎn)發(fā)請求的時候，它反轉(zhuǎn)路徑指向源節(jié)點(diǎn)，AODV假設(shè)是全雙工的
• 當(dāng)目標(biāo)節(jié)點(diǎn)接收到請求的時候，它根據(jù)反轉(zhuǎn)的路徑發(fā)送RREP
• 一個中間節(jié)點(diǎn)可能會發(fā)送RREP提供一個最新的到目標(biāo)節(jié)點(diǎn)的路徑。
• 但是這個中間節(jié)點(diǎn)發(fā)送RREP的概率比DSR低，因?yàn)楣?jié)點(diǎn)S發(fā)起的RREQ設(shè)置了一個更大的序列號，而中間節(jié)點(diǎn)的序列號較小無法發(fā)送RREP。（當(dāng)序列號足夠大時才認(rèn)為它掌握的信息是最新的）

timeouts

• 一個路由表維護(hù)的逆向路徑在一段時間后（timeout 超時時間）將會被清除
  • timeout的設(shè)置應(yīng)該能保障RREP回到發(fā)送節(jié)點(diǎn)
• 一個路由表維護(hù)的逆向路徑在一段時間內(nèi)（active_route_timeout 活動路由時間)沒有使用，將會被清除。
  • 即便這個路勁信息依然是有效的

Link Failure Reporting 連接失敗報(bào)告

Route Error

• 當(dāng)節(jié)點(diǎn)X無法轉(zhuǎn)發(fā)數(shù)據(jù)包P的時候，它就生成一個RERR消息
• 節(jié)點(diǎn)X加大目標(biāo)節(jié)點(diǎn)的序列號，序列號將被包含在RERR中
• 節(jié)點(diǎn)S收到RERR之后，重新開始路由發(fā)現(xiàn)過程，這時對目標(biāo)節(jié)點(diǎn)設(shè)置的序列號至少比N大（每一跳之后序列號就增加）

AODV總結(jié)

• routes need not be inclued in packet headers包頭不用包含路由
• nodes maintain routing tables containing entries only for routes that are in active use節(jié)點(diǎn)只需要維護(hù)需要使用的路由表實(shí)體
• at most one next-hop per destination maintained at each node 最多只需要維護(hù)一跳的信息就行（一個節(jié)點(diǎn)只需要維護(hù)到鄰居的路徑即可）
  • dsr may maintain serveral routes for a single destination（DSR需要維護(hù)很多，可能是整條完整的路徑）
• unuserd routes expire enve if topology dose not change 即便網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)沒有發(fā)生改變，那些長期未使用的路由也會被清除

Link Reversal Algorithm 鏈路反轉(zhuǎn)算法

• 首先要求鏈路是bi-directional 半雙工的（可發(fā)可收，但是不能同時發(fā)和接收）
• 為每一個目標(biāo)節(jié)點(diǎn)維護(hù)一個有向無環(huán)圖（Directed acyclic graph DAG)
• 除了目標(biāo)節(jié)點(diǎn)，任何沒有出路的節(jié)點(diǎn)都將入的鏈路反向
• 注意到之前反向過得鄰居還會再次被反向：每次都是整個網(wǎng)絡(luò)滿足條件的節(jié)點(diǎn)反向。 full reversal method 全鏈路反向方法
• partial reversal method 局部鏈路反向算法：之前反向過得不用再反向

鏈路反向算法的優(yōu)點(diǎn)

• link reversal methods attempt to limit updates to routing tables at nodes in the vicinity of a broken link
  • partial reversal method tends to be better than full reversal method
• each node may potentially have multiple routes to a destination 可能會有多條路徑到目標(biāo)節(jié)點(diǎn)

缺點(diǎn)

• need a mechanism to detect link failure（需要引入檢測鏈路失敗的機(jī)制）
  • hello messages may be used 發(fā)送hello message來檢測連通性
  • but hello message can add to contention
• if network is partitioned（分割），link reversal continue indefinitely (陷入死循環(huán))

總結(jié)

以上是生活随笔為你收集整理的《高级计算机网络》之移动自组网——大连理工大学研究生课程整理笔记（非常详细，通俗易懂）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。