無線隨意網路路由協定 (Routing Protocols for MANET)---DSR&AODV&TORA

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

8.1 無線隨意網路簡介 

8.2 主動式路由策略 

8.3 回應式路由策略 

8.4 主動式與回應式路由之比較

8.5 位置輔助路由 (location-based routing)策略 

8.6 結語

8.3 回應式路由策略

回應式(reactive)路由又稱On-demand routing (經需求路由)

主動式(路由表) vs. 回應式 ->8.4

回應式路由只尋找與維護有需要的路由

主動式路由則不論需要與否所有路由均須維護

回應式路由

優點： 省去一些不必要的路由維護

             適合偶發訊務(traffic)且一但發生則有大量的訊務；通訊只涉及少 數節點

缺點： 首次尋找耗時較多時間做路徑尋找造成封包延遲

回應式路由例子：

            動態來源路由 (Dynamic Source Routing , DSR)

            隨意依需求距離向量路由(Ad hoc On-demand Distance Vector, AODV) 

            臨時排序路由演算法 (Temporally Ordered Routing Algorithm, TORA)

回應式路由協定 –DSR(Dynamic Source Routing)

來源路由(Source routing)的基本精神：

1.封包的整個路由在來源地(source)已決定並置放在該節點的路由快取貯存區 (route cache) 

2.路由路徑資訊在封包標頭中；中繼節點按此資訊傳送封包。 

(要到的目地地無路由時) 啟動路由探索程序(Route discovery procedure)：

1.由節點送出路由請求(route request, RREQ)封包來啟動

2.中繼節點收到RREQ時，若收過此封包則丟棄，不然就更新封包內部資訊後繼續廣播此RREQ封包 

當此封包到達目的地或中繼節點的route cache中有目的地節點資訊時則回覆路由回應(Route Reply, RREP)封包

RREP封包利用來源路由(Source routing)的策略回傳至來源節點

當來源節點收到RREP封包後可開始傳輸資料封包 

路由錯誤(Route Error, RERR)封包 : 

1.在DSR協定中，當連結失敗 (即傳送封包給下一站時遇到 失敗)則會產生”路由錯誤(RERR)”封包送回並告知來源地

2.沿途的節點會把該路由資訊清除 

3.當來源地收到REER封包後會重新啟動路由探索程序找替代路徑 

DSR使用來源路由(Source routing)及路由快取貯存區 (route cache)策略有下列優點：

1.避免路由迴圈的產生(Routing Loop free) 

2.RREQ與RREP皆有整個路由路徑資訊

3.各節點可記錄路由 路徑資訊於route cache 

4.加速封包傳輸  RREQ與RREP皆有路由路徑資訊

5.可以有多條路由路徑

6.增加可靠性 (reliability)

回應式路由協定 –AODV(Ad-hoc On-Demand Distance Vector Routing)

AODV：使用如同DSR的路由探索使用RREQ與RREP 廣播機制找尋路徑。

但採用不同機制維護路由資訊： 使用傳統路由表 (目地、下一、跳躍數) 。

AODV捨棄 source routing而依靠著中繼節點機動地建立的路由表項 目(route table entries)。 

AODV 使用:

             1.DSDV的目的地序列編號演算法

                           距離向量 

                           序列編號 

             2.使用計時器(timer)保持路由新鮮。

回應式 (on-demand)產生路由：不在路由路徑(selected path)上的節點不需保有路由資訊與交換路由資訊。

目標：降低廣播經常費用(overhead)與傳輸延遲

對每一目的地路由表有一列資訊包含 :
<destination addr , next-hop addr , destination sequence number , life tine>

• 目的地 

• 下一節點 

• 量度 (metric) : 跳躍數 (hop count) 

• 目的地序號 (Sequence number) 

• 路由表項目過期時間[計時器]:被用過即重置，否則expire掉

• 來源節點廣播RREQ封包

• 中繼節點轉送至目的地節點

• 目的地節點以<broadcastID,src-address>來分辨RREQ 封包；且當收到第一個RREQ 封包時回應RREP封包

AODV-Route Discovery:

1.先檢查table->Yes 送
2.No->Source送RREQ
RREQ封包內容:<source IP addr , source current sequence number , destination IP addr , destination seq number>
封包也有Broadcast ID number(src 給)
所以當有Broadcast ID and Source IP addr就可以知道具唯一性。

Reverse Route Entry:

當node收到RREQ，會在route table建立一個reverse route entry
格式:<Source IP Address , Source seq. number , number of hops to source node , IP address of node from which RREQ was received>
使用這個reverse route entry去送RREP回Source，本身entry也具Life Time

RREP格式: <IP addr of source and destination>

If RREP sent by destination:
<current seq# of destination , hop-count= 0 , life-tine>

If sent by intermediate node
<destination seq number , hop-count=its distance to destination , its value of the life-tine>

When a node received a RREP means it can set up a forward path entry
<IP addr of destination , IP addr of node from which tje entry arrived , hop-count to destination , life-time>

When a node received multiple RREP 
- only forwards the first RREP
- May forward another RREP if that has greater destination seq number or a smaller hop-count
- Rest are discarded


NOTE:若Table中可以找到一個entry且Seq, number >= RREQ那可以直接送去destination
否則繼續轉送RREQ並增加hop-count

回應式路由協定 –TORA(：Temporally Ordered Routing Algorithm)

TORA : 為一回應式路由協定

路由探索程序：算出多條通往目的地之路徑->目的地導向的有向無迴圈圖(directed acyclic graph, DAG*) 

NOTE:*無線隨意網 路可被視為無方向的圖 (undirected graph) 但TORA將此圖的邊(edges)給與方向：朝向目的地節點。 

每個節點會記錄至任一目的地的距離又稱高度值。 封包送往目的地依其高度值遞減如水往下流。 

如何建立高度值：使用詢問(query) /更新(update) 機制 

當一節點嘗試送出封包時會發出詢問(Query)封包， 該封包廣播至整個網路直到目的地或有至目的地路 由的節點。接著此點會回覆更新(update)封包(包含自 己高度資訊)。

當其它結點收到更新(update)封包後…會更新其高度 值。

各節點的高度值建立成功，形成一以目的地導向的DAG 

當連結失敗時，節點發現它的高度值為局部最小時；則 會將其高度值提高並發出更新(update)封包

8.4 主動式與回應式路由之比較

定義：流量密度/差異(traffic diversity) ？[流量分布的情 形]

低流量密度：集中於網路的少數節點

高流量密度：平均分散於網路的每個節點

回應式路由能適應不同流量密度(較適合低流量密度)； 路徑非最佳，主動式路由則不受流量密度所影響。

高流量密度：路由負擔相當但：回應式路由->次佳路徑； 主動式路由->最佳路徑 

低流量密度：回應式路由->表現較佳 

->混合式路由(ZRP)

ZRP為一混合式路由協定。

一節點的區域(Zone)：半徑(= hop counts) 內的所有節點。

邊緣節點(Border node)：半徑上的所有節點。

Zone內使用連結狀態(link state)的主動式路由協定

 Zone間使用回應式路由協定的路由探索程序，其路由 請求封包只送往邊緣節點直到目的地的邊緣節點後回 覆。 

回應式路由 在路由探索(route discovery)造成較 長的延遲  不適用於對延遲 敏感(delay sensitive)和極短暫的應用(如問答)