無線隨意網路路由協定 (Routing Protocols for MANET)----DSDV

無線隨意網路路由協定 (Routing Protocols for MANET)

8.1 無線隨意網路簡介 
8.2 主動式路由策略 
8.3 回應式路由策略 
8.4 主動式與回應式路由之比較
8.5 位置輔助路由 (location-based routing)策略 
8.6 結語

8.1 無線隨意網路

特性:

1.移動性(影響路由)
2.多點跳躍(multi-hop)

3.自我組態(self-configuration):node可以決定自己的參數[IP、路由表、位置]

4.可延伸性
5.安全性

無線隨意網路可隨時隨地可建立，無固定基礎架構，不需事先規劃與佈置；由自我(self)組態而 自動(auto)組織而成，成員可隨時加入或離開，通訊方法：單播(uni-cast)，群播 (multi-cast)。

大型的隨意(Ad-Hoc)網路封包傳輸須中繼站轉播 -->多點跳躍 (multi-hop) --> 路由(routing) ) 

[不同於(802.11)中定義的IBSS屬 單點跳躍(one-hop)可直接溝通無中繼站轉播,故無路由問題]

而單播(uni-cast)]路由策略又分以下四種:

1.主動式 (proactive)：事先建立 (又稱 table-driven) [8.2] 

2.回應式 (reactive)：只尋找與維護有需要的路由 [8.3] 

3.位置輔助 (Location-based)：利用節點的位置資訊 [8.4] 

4.混合式 (Hybrid)：主動式及回應式的混合[8.5]

8.2 主動式(proactive)路由策略

(無線隨意網路)主動式路由可分為：
距離向量 (Distance Vector, DV)法：記錄自己到網路中所 有節點的距離及要往該節點路由的下一個節點(向量)。 節點間交換距離向量(DV)資訊，從而計算出自己到各節 點的最佳路由。

連結狀態 (Link State)法：記錄自己的連結狀態。節點間 交換連結狀態，從而計算出自己到各節點的最佳路由。

距離向量(DV)不適用於隨意網路 (ad-hoc networks) ，因為網路連結失敗造成 路由迴圈 (Routing Loops)產生跳躍數無限 (Count to Infinity)，所以須要另找協定避免上述問題 ，

ex:目的地序列距離向量 (Destination-Sequenced Distance-Vector, DSDV) 協定

距離向量(Distance-Vector)路由協定

DSDV 協定:

DSDV是基於傳統Bellman-Ford路由選擇演算法所 改良而發展出來的，是一個以路由表(routing table)為基礎的通訊協定。 故每一個行動節點必須儲存一張路由表。須紀錄所有與該節點可能進行連結節點的距離。除給自己節點一個序列編號外，路由表內的每筆紀錄 同時還包含了一個目的地序列編號(destination sequence number)：用來判斷路徑的新舊，以避免迴路的產生。

當網路拓樸變動比較不頻繁時，並不需要將路由表的所有資料進行交換。DSDV在每個節點內再加了一個table，用來記錄其路由表從上次交換至今所更改的部分。如果更改很多[或定期地]，就進行全部資料的交 換，稱為全路由更新 (full routing update)；如果 改變很少，就只針對改變部分交換，稱為累加式路由更新 (incremental routing update)。

特性:

保有距離向量 (Distance Vector)的簡易性 

1.保證無迴路 ->路由表內新增一表項目 (Table Entry)：目的地序列編號 (Destination Sequence Number) 

3.對拓樸改變反應迅速??? 

       ->當路由表有顯著改變；立即做路由廣告(route advertisement)。 

       ->但對未穩定路由(unstable routes)採等待策略；而不立即做路由廣告 (damping             fluctuations) 

路由選取:

更新資訊與路由表比較： 

1. 選取目的地的序號 (destination sequence number) 較高的路由 (保證使用來自目 的地的最新資訊) 

2. 當目的地的序號一樣時，選取量度(Metric) [=至目的地的hop counts]較佳的路由

路由表範例

新節點加入:

無迴路，無跳躍數無限:

降低路由表的波動:

對每一個特殊目的地，保留關於最先到來的路由和最佳路由的到來的時間長度的資料。

依據這資料，决定延遲廣告 (可能將很快改變的) 路由 ，因而降低路由表的波動 (damping (抑制/降低) fluctuations )。通常為了減少相同序號編號之路由廣告的重播的數量 會延遲可能不穩定之路由廣告 。

何謂路由表的波動 :

路由表A中的項目D：[D, Q, 14, D-100] 

D 廣播序列編號 D-102  A 由P 收到D 的更新廣播：(D, 15, D-102) 

路由表A中的項目D：[D, P, 15, D-102] A 必須立即散播(propagate)此路由。

A 由Q收到D 的更新廣播：(D, 14, D-102)

路由表A中的項目D：[D, Q, 14, D-102] A 必須立即散播(propagate)此路由。

若不立即散播由P 收到的D 之更新廣播而延遲一 段時間，也許只要散播由Q 收到的D 之更新廣播 這可能發生在每一次在點D或其他節點做它的 更新廣播後導致在網路 上多餘的路由廣告，即 所謂波動 (fluctuations)。

如何緩和路由表波動:

於個別的表格上記錄上一次的決定時 間(Settling Time)與決定時間的平均。 [ 一個序列编号的第一個路由到來與最 佳的路由到來的時間間隔叫做決定時 間 (Settling Time)。]

當一個較新的特定序列编号的第一個 路由到來時，節點A仍然必須更新它的 路由表；但是它會等待一段時間才將 它散播。建議的等待時間約為平均決 定時間的兩倍。

在大型網路中像這的波動可以被降低 以避免多餘的廣告，因而節省了頻寬。

連結狀態(link-state)路由協定:

多重傳遞點(Multipoint Relay, MPR)概念：

1.單點跳躍 (1-hop)：節點A 與節點B能直接相互通訊時，我 們稱A與B為(直接) [單點跳躍 (1-hop)]鄰居；又稱A到B或 B到A為單點跳躍(1-hop) 。[單向通訊vs.雙向通訊???]

2.覆蓋：節點B與節點A為一單點跳躍的關係；我們可以說 節點B為節點A (或節點A為節點B)所覆蓋。 

3.兩點跳躍 (2-hop)：節點A與節點B及節點B與節點C皆為單 點跳躍(1-hop)的關係；但節點A與節點C無單點跳躍(1- hop)的關係時->節點A與節點C為一兩點跳躍(2-hop)的關係。又稱節點A為節點C[或節點C為節點A]的兩點跳躍(2- hop)鄰居

4.在節點A的單點跳躍 (1-hop)鄰居內選出一組特殊節 點；稱這些節點集合為”多重傳遞點” (Multipoint Relay, MPR)。

這些特殊節點要愈少愈好且滿足：節點A選出的MPR集合要能覆蓋節點A的所有兩點跳躍(2- hop)鄰居。PS:此最佳化問題為一NP-hard的問題