Chapter 8 無線隨意網路路由
簡介 ( 一 ) 無線隨意網路 :MANET = Mobile Ad Hoc Networks a set of mobile hosts, each with a transceiver no base stations; no fixed network infrastructure multi-hop communication needs a routing protocol which can handle changing topology 2
簡介 ( 二 ) 無線網路不同於有線網路的特性 : 目的位址 (Destination Address) 不等於目的位置 (Destination Location) 無線訊號強度會因處於不同環境而有不同程度之衰減 無線網路具有動態網路拓撲之結構 同屬一個無線網路集合將會共用同一個傳輸媒介 資料傳輸過程未受保護, 故易受外界干擾且保密安全性低 省電之課題 具有分散式執行功能 無迴路 (Loop-free) 結構 具有多重中繼段 (Multi-hop) 路由 對動態鏈結作快速地適應 不可靠的廣播機制 3
簡介 ( 三 ) 無線網路路由通訊協定在功能與設計之考慮 : 路徑的建立是主動或被動 是否需週期性更新路徑 是否需維護多條路由 網路架構為叢集式或平面式 是否提供安全機制 是否支援群播功能 建立路徑所需花費之時間 工作站電源管理的考量 通訊頻寬的需求 所需之參考資訊表格數量 4
簡介 ( 四 ) 兩種路由方法 表格驅動式路由 (Table Driven Routing) 主動式 Proactive 路由 需求式路由 (On-demand Routing) 回應式 Reactive 路由 5
簡介 ( 五 ) 表格驅動式路由 (Table Driven Routing): 每一個節點 ( 工作站 ) 都會各自維護自己的路由表 (Routing Table), 再利用各個節點週期性地廣播自己的路由資訊, 來彼此交換與更新訊息並藉此得以主動發現所需之封包傳送路徑 循序的目的地距離向量路由協定 (Destination-sequenced Distancevector Routing,DSDV) 群首閘道交換路由協定 (Clusterhead Gateway Switch Routing, CGSR) 無線路由協定 (Wireless Routing Protocol,WRP) 6
簡介 ( 五 ) 需求式路由 (On-demand Routing): 當有某一節點需要一條路徑以傳送封包給目的節點時才開始建構 而各節點本身並不會週期性與主動性地傳送路由更新資訊給網路上其他節點 輕量移動路由協定 (Lightweight Mobile Routing,LMR) 暫時性順序路徑演算法 (Temporally-ordered Routing Algorithm, TORA) 動態來源端路由協定 (Dynamic Source Routing,DSR) 無基礎式需求距離向量路由協定 (Ad Hoc On-demand Distance Vector Routing Protocol,AODV) 關聯性基礎路由協定 (Associativity-based Routing, ABR) 輔助定位路由通訊協定 (Location-aided Routing,LAR) 7
表格驅動式路由演算法 表格驅動式路由協定有兩類主要的演算法 : 距離向量路由 (Distance-vector Routing,DVR) 鏈路狀態路由 (Link-state Routing,LSR) 8
距離向量 (Distance) 與鏈結狀態 (Link state) 路由演算法 距離向量與鏈結狀態演算法最主要的差別 : 距離向量演算法需藉由其鄰近節點所告知之 距離 資訊做為其是否選擇該節點為路徑的依據 鏈結狀態演算法則是每一節點經由鄰近節點的告知, 獲得所有網路 鏈結狀態 的資訊 ( 亦即擁有網路的全貌 ) 後, 再做為選徑的依據 9
距離向量演算法 (DVR) 使用距離向量的路由器都會自行維護一個路由表, 他會記錄到每一個已知目的地的最佳距離到自己的路由表中 最典型的代表就是 Bellman-Ford Routing Algorithm 當機器開機時, 路由器中只有自己本身的路由資訊, 然後會和鄰近的路由器以廣播的方式, 彼此交換自己的路由表內的資訊, 藉由這樣的交換訊息, 很快的就可以得知整個網路的連結狀態 10
Example 11
Example From A to Interface Metric From B to Interface Metric A local 0 B local 0 From C to Interface Metric From D to Interface Metric C local 0 D local 0 From E to Interface Metric From F to Interface Metric E local 0 F local 0 From G to Interface Metric G local 0 12
From A to Interface Metric From B to Interface Metric A local 0 B local 0 B S0 1 A S0 1 D S1 1 C S1 1 F S2 1 From C to Interface Metric From D to Interface Metric C local 0 D local 0 B S0 1 A S0 1 E S1 1 E S2 1 G S1 1 From E to Interface Metric From F to Interface Metric E local 0 F local 0 C S0 1 A S0 1 D S1 1 G S1 1 From G to Interface Metric G local 0 D S0 1 F S1 1 13
From A to Interface Metric From B to Interface Metric A local 0 B local 0 B S0 1 A S0 1 D S1 1 C S1 1 F S2 1 D S0 2 C S0 2 F S0 2 E S1 2 E S1 2 G S1 2 From C to Interface Metric From D to Interface Metric C local 0 D local 0 B S0 1 A S0 1 E S1 1 E S2 1 A S0 2 G S1 1 D S1 2 B S0 2 F S0 2 C S2 2 From E to Interface Metric From F to Interface Metric E local 0 F local 0 C S0 1 A S0 1 D S1 1 G S1 1 B S0 2 B S0 2 A S1 2 D S0 2 G S1 2 From G to Interface Metric G local 0 D S0 1 F S1 1 A S0 2 E S0 2 14
From A to Interface Metric From B to Interface Metric A local 0 B local 0 B S0 1 A S0 1 D S1 1 C S1 1 F S2 1 D S0 2 C S0 2 F S0 2 E S1 2 E S1 2 G S1 2 G S0 3 From C to Interface Metric From D to Interface Metric C local 0 D local 0 B S0 1 A S0 1 E S1 1 E S2 1 A S0 2 G S1 1 D S1 2 B S0 2 F S0 3 F S0 2 G S0 3 C S2 2 From E to Interface Metric From F to Interface Metric E local 0 F local 0 C S0 1 A S0 1 D S1 1 G S1 1 B S0 2 B S0 2 A S1 2 D S0 2 G S1 2 C S0 3 F S1 3 E S1 3 From G to Interface Metric G local 0 D S0 1 F S1 1 A S0 2 E S0 2 B S0 3 C S0 3 15
距離向量演算法 - 無限計數 因為每一網路節點不需掌握網路整體拓撲, 因此在選徑時就有可能會有形成迴圈的現象, 甚至有可能會使得路徑的選擇產生無限計數 (Count to infinity) 的問題 16
經一段時間後, 路由器各自之完整的路由表如下 : A B C D E S0 S0 S1 S0 S1 S0 S1 S0 From A to Interface Metric From B to Interface Metric A local 0 A S0 1 B S0 1 B local 0 C S0 2 C S1 1 D S0 3 D S1 2 E S0 4 E S1 3 From C to Interface Metric From D to Interface Metric A S0 2 A S0 3 B S0 1 B S0 2 C local 0 C S0 1 D S1 1 D local 0 E S1 2 E S1 1 From E to Interface Metric A S0 4 B S0 3 C S0 2 D S0 1 E local 0 17
假設 A-B 之間的鏈路斷了,B 無法到達 A, 但是 B 卻從 C 得知有一條到 A 的路 徑, 於是 B 就更新自己的路由表, 如下表 From B to Interface Metric A S1 3 B local 0 C S1 1 D S1 2 E S1 3 然而過一段時間,C 必須再次跟鄰居交換訊息, 發現到 A 這個 entry 必須更新, 於是 C 就更新自己的路由表, 如下表 From C to Interface Metric A S0 4 B S0 1 C local 0 D S1 1 E S1 2 18
距離向量演算法 解決無限計數的方法 : Maximum hop count: 限制其跳躍數 Split horizon: 這個方法的原則是不回送資料, 所以當 A- B 之間斷了,C 不會再把 A 的訊息告訴 B, 因為到 A 的訊息是由 B 告訴 C 的 Hold Down: 利用 Hold down timer, 若 hold down timer 過期前的任何時間裡, 從不同的路由器接到更新資訊, 但指標較差, 則不理會更新資訊 在 hold down timer 時效範圍內, 不理會指標較差的更新資訊, 則能有更多時間將中斷的改變資訊傳播到整個網路上 19
Split horizon Network 1 Router1 Router2 Router2 不能告訴 Router1 有關 Network 1 的資訊, 因為那是 Router 1 告訴 Router 2 的 20
鏈結狀態路由演算法 鏈結狀態演算法在一般圖形理論中也稱為最短路徑 (Shortest Path First, SPF) 演算法, 它保持一份網路整體拓撲的資料庫 再利用圖形理論中的最短路徑演算法找出該節點到各點之最短路徑 圖形理論中, 最短路徑的演算法有許多種, 但其中以 Dijkstra 演算法最有名, 而 Dijkstra 演算法也被引用為 OSPF (Open Shortest Path First) 演算法中 21
鏈結狀態路由演算法 : Dijkstra s Algorithm Initial State: each host only knows its direct neighbors 22
Evolution of States in C Comments: This is a centralized algorithm, not appropriate. 23
鏈結狀態路由演算法 Optimal Link State Routing (OLSR): OSPF 最佳化版本 使用多重傳遞節點 (MPR) 減少鏈結狀態更新的封包數量 MPR: 挑選 1-hop 鄰居, 使得能夠完全覆蓋全部 2-hop 鄰居 15 次廣播 4 次廣播 24
鏈結狀態路由演算法 鏈結狀態演算法有下列優點 : 無迴圈 (Loopless): 路徑的決定是在擁有整個網路資訊後才決定, 因此不會找出有迴圈的路徑 多路徑 (Multiple paths) 到目的地 : 既然每一節點能獲知網路全貌, 因此每一節點可依需要找出到目的地且不共用鏈結之多條路徑, 而找出多條路徑的目的, 可以是為了做路徑保護 ( 備用路徑 ), 或是分擔訊務使用 25
表格驅動式路由協定 : 循序的目的地距離向量路由協定 (DSDV) DSDV: 針對 DVR 進行修正而得 DSDV 多了目的地循序號碼 (Destination-sequenced Number) 的記錄 利用目的地循序號碼來判斷路徑是否需要更新, 避免因產生迴路效應而使路徑發生錯誤 26
表格驅動式路由協定 : 循序的目的地距離向量路由協定 (DSDV) 目的地 Destinati on 下一個節點 Next Hop 路徑節點數 Metric 循序號碼 Sequence Number 第一次相連時間 Install DSDV 通訊協定中每一個節點內都必須存有一個路由表 目的地 (Destination): 可到達之節點 下一個節點 (Next Hop): 在到達某一目的節點之路徑上的第一個相鄰節點 所需節點數 (Metric): 到達目的節點中間所會經過的節點個數 循序號碼 (Sequence Number): 每個節點進行週期性資訊時所附上之號碼 初始時之編號是隨機產生, 而後每次進行更新時號碼會加二 第一次相連時間 (Install): 各個節點第一次與其他節點進行通訊時所記錄之時間 27
表格驅動式路由協定 : 循序的目的地距離向量路由協定 (DSDV) 當網路拓撲結構有改變的時候, 皆透過週期性的傳送廣播封包來告知新的路由資訊 這些路由資訊中不會改變的部分包含每一個節點第一次與其他節點通訊之時間 (Install) 當某一節點在進行路由表更新時, 對於具有相同目的節點之數條路徑 : 此節點通常會選擇具有最新循序號碼之路徑 若是遇到具有相同循序號碼之路徑, 則將會選擇具有較少中繼節點數者 28
表格驅動式路由協定 : 循序的目的地距離向量路由協定 (DSDV) 在動態網路中, 擁有鏈結 (Links) 的節點可能會移動 其鄰近之節點若是在經過一段時間內沒再收到此一節點的更新訊息時, 其鄰近節點會認為此一節點已經離開, 則這些鄰近節點會將各自的路由表中凡與此移動節點有關之路徑的路徑節點數設成無限大, 並建立一個新的循序號碼將其廣播出去 一般節點所發出的循序號碼都會被設定為偶數, 而擁有無限大路徑節點數的循序號碼會被設定為奇數 29
表格驅動式路由協定 : 循序的目的地距離向量路由協定 (DSDV) 基本上每一個節點都會同時維護兩個路由表 : 一個是自己建立路徑時所需之路由表 另一個則是要廣播路由更新資訊給相鄰節點用的路由表 每一個節點為了確保自己可以收到最好的路徑, 都會保留之前的路徑資訊 在 DSDV 通訊協定中, 採用具較少中繼節點數者來更新自己路由表之方式來防止路徑迴圈發生 路由表中的節點都會是以最短路徑 (Shortest Path) 的方式到達目的端節點 30
表格驅動式路由協定 : 循序的目的地距離向量路由協定 (DSDV) 在 DSDV 通訊協定中, 為防止各節點內之路由表不會常常被更改, 而使網路較容易穩定下來之作法 : 阻尼變動 (Damping Fluctuations): 是描述如何去設置一個時間表, 以防止路由表不斷的被改變 讓某些節點在接收到類似這樣的訊息封包後延遲將它送出 此延遲之時間最好大於兩個平均散佈之時間 所謂的平均散佈的時間為網路內每個節點傳送訊息給其它結點 所需之時間平均 31
表格驅動式路由協定 : 循序的目的地距離向量路由協定 (DSDV) Example: 節點 MH1 在無線網路當中移動之情形 目的地 Destination 下一個節點 Next Hop 路徑節點數 Metric 循序號碼 Sequence number 第一次相連時間 Install MH 1 MH 2 2 S216_MH 1 T001_MH 4 MH 2 MH 2 1 S328_MH 2 T001_MH 4 MH 3 MH 2 2 S546_MH 3 T001_MH 4 MH 4 MH 4 0 S602_MH 4 T001_MH 4 MH 5 MH 5 1 S312_HM 5 T002_MH 4 MH 6 MH 5 2 S056_MH 6 T001_MH 4 MH 7 MH 5 2 S128_MH 7 T002_MH 4 節點 MH1 在 Ad Hoc 網路中移動之情形 MH 8 MH 5 3 S056_MH 8 T002_MH 4 MH4 初始的路由表 32
表格驅動式路由協定 : 循序的目的地距離向量路由協定 (DSDV) 目的地 Destination 路徑節點數 Metric 循序號碼 Sequence number MH 1 2 S216_MH 1 MH 2 1 S328_MH 2 MH 3 2 S546_MH 3 MH 4 0 S602_MH 4 MH 5 1 S312_HM 5 MH 6 2 S056_MH 6 MH 7 2 S128_MH 7 MH 8 3 S056_MH 8 MH4 一開始所送出的更新路由資訊 節點 MH1 移動至節點 MH7 與 MH8 附近 MH2 發現 MH1 離開後, 其將自行更改到 MH1 的路徑節點數為無限大, 並且更改其循序號碼為奇數 同時 MH2 會將這個消息廣播出去讓整個網路節點都知道 MH2 現在與 MH1 已經斷訊 33
表格驅動式路由協定 : 循序的目的地距離向量路由協定 (DSDV) 目的地 Destination 下一個節點 Next Hop 路徑節點數 Metric 循序號碼 Sequence number 第一次相連時間 Install MH 1 MH 2 S217_MH 1 T001_MH 4 MH 2 MH 2 1 S328_MH 2 T001_MH 4 MH 3 MH 2 2 S546_MH 3 T001_MH 4 MH 4 MH 4 0 S602_MH 4 T001_MH 4 MH 5 MH 5 1 S312_HM 5 T002_MH 4 MH 6 MH 5 2 S056_MH 6 T001_MH 4 MH 7 MH 5 2 S128_MH 7 T002_MH 4 MH 8 MH 5 3 S056_MH 8 T002_MH 4 節點 MH1 移動至 MH7 與 MH8 附近 節點 MH4 收到 MH2 發出與 MH1 中斷連線之封包後的更新路由表 34
表格驅動式路由協定 : 循序的目的地距離向量路由協定 (DSDV) 目的地 Destination 下一個節點 Next Hop 路徑節點數 Metric 循序號碼 Sequence number 第一次相連時間 Install MH 1 MH 5 3 S336_MH 1 T510_MH 4 MH 2 MH 2 1 S448_MH 2 T001_MH 4 MH 3 MH 2 2 S666_MH 3 T001_MH 4 MH 4 MH 4 0 S722_MH 4 T001_MH 4 MH 5 MH 5 1 S432_MH 5 T002_MH 4 MH 6 MH 5 2 S176_MH 6 T001_MH 4 MH 7 MH 5 2 S238_MH 7 T002_MH 4 MH 8 MH 5 3 S176_MH 8 T002_MH 4 節點 MH4 再次更新後的路由表 目的地 Destination 路徑節點數 Metric 循序號碼 Sequence number MH 4 0 S722_MH 4 MH 1 3 S336_MH 1 MH 2 1 S448_MH 2 MH 3 2 S666_MH 3 MH 5 1 S432_MH 5 MH 6 2 S176_MH 6 MH 7 2 S238_MH 7 MH 8 3 S176_MH 8 節點 MH4 在 MH1 移動至 MH7 跟 MH8 附近後所送出的更新路由資訊 35
表格驅動式路由協定 : 循序的目的地距離向量路由協定 (DSDV) DSDV 協定的處理流程 36
表格驅動式路由協定 : 群首閘道交換路由協定 (CGSR) 以 DSDV 為基礎並結合叢集路由機制設計而成的 在多重中繼段和移動式無線網路中, 讓節點加入某一叢集中, 並受到此叢集之群首 (Clusterhead) 的控制 在叢集式架構中會使用分散式演算法 (Distributed Algorithm), 來選出某一個節點作為某一叢集之群首 在一群首通訊範圍內的所有節點均可加入此一叢集, 而成為此叢集之成員 在叢集中之所有節點均可以與群首直接進行通訊 一個叢集中之節點可分為三種角色 : 群首 (Clusterhead) 閘道 (Gateway) 一般節點 (Node) 37
表格驅動式路由協定 : 群首閘道交換路由協定 (CGSR) 演算法 : 一個叢集的複雜度 (Complexity) 主要取決於 群首選擇 的方法 : 一般有兩種分散式叢集演算法可採用 : 最低識別碼叢集演算法 (Lowest-ID Clustering Algorithm) 最高連通性叢集演算法 (Highest-connectivity(Degree)Clustering Algorithm) 無線網路中, 維護一個叢集最重要的準則是穩定性, 倘若群首太常變更將不利於此叢集之效能 討論另一種演算法 :LCC 叢集演算法 (Least Cluster Change Clustering Algorithm) 此演算法只有在兩種情況下才會導致群首的變更 : 當某一個群首進入另外一個群首的通訊範圍時 當某一個群首脫離所有叢集的通訊範圍時 38
表格驅動式路由協定 : 群首閘道交換路由協定 (CGSR) LCC 演算法 : 先採用 最低識別碼 (Lowest-ID) 或 最高聯通性 (Highestconnectivity) 叢集演算法, 來創造一個初始的叢集 當某一個原屬於叢集 A 的非群首節點移動到叢集 B 時, 則叢集 A 和 B 中之群首並不會改變 ( 只是叢集中之成員會變少或變多 ) 若某一個非群首節點離開它的叢集, 且沒有進入到其它叢集時 ( 即指未進入其他叢集之通訊範圍內 ), 則它將會成為一個新的群首, 並形成一個新的叢集 當叢集 A 之群首節點離開叢集 A 並進入到叢集 B 時, 則此一進入之群首節點將會和原本叢集 B 之群首節點互相競爭 再根據 最低識別碼 或 最高聯通性 叢集演算法 ( 或其他較好的優先權方案 ) 來競爭, 勝出者將成為此叢集 B 的新群首 當叢集 A 之群首節點離開叢集 A 時, 則此叢集 A 將會根據 最低識別碼 或 最高聯通性 叢集演算法, 重新計算以產生新的群首 39
表格驅動式路由協定 : 群首閘道交換路由協定 (CGSR) 某兩個節點彼此停留在彼此的通訊範圍內且有穩定的訊號能源, 則此兩個節點間會形成鏈結 (Link) 每個叢集都會有屬於自己的傳輸代碼 (Transmission Code), 且每一個節點都會記錄著自己所屬叢集的傳輸代碼 兩個節點會因為彼此的傳輸代碼不同, 而無法互相傳輸 定義上述兩個使用不同代碼的節點, 彼此間之鏈結為偽鏈結 (Pseudo Links), 並且從連線狀態中移除 群首將會與叢集中的每一個成員進行鏈結 40
表格驅動式路由協定 : 群首閘道交換路由協定 (CGSR) 在形成叢集之前的各節點鏈結情形 形成叢集後的各節點鏈結情況 ( 黑點代表群首, 灰點代表閘道節點, 白點代表一般節點 ) 41
表格驅動式路由協定 : 群首閘道交換路由協定 (CGSR) 頻道存取演算法 : 相互交叉的叢集中, 可藉由使用 分碼多重存取 (CDMA) 之方式來增加相互交叉的叢集彼此間平行傳輸 (Parallel Transmission) 的效能 在叢集內部各節間點的運作, 一般可使用 群首控制符記 (Token) 的 輪詢協定 ( 即 Polling) 來依序分配頻道給其中某一個節點使用, 以避免各節點間因傳輸競爭而產生的碰撞情況 安排給予群首傳輸優先權, 使群首具有更多的傳送機會 每一個叢集中只有得到允許符記的節點可以使用被分配的傳輸代碼 ( 即 CDMA 方法中的編碼 ) 來存取頻道 群首需具有重新發出允許符記之能力, 原因 : 在一些情況中允許符記可能會遺失 42
CDMA In Code Division Multiple Access (CDMA), every communicator will be allocated the entire spectrum all of the time. CDMA uses codes to identify connections. 43
CDMA (Cont.) 44
表格驅動式路由協定 : 群首閘道交換路由協定 (CGSR) 採用輪詢協定的頻道存取演算法 45
CGSR 路徑選擇 : 表格驅動式路由協定 : 群首閘道交換路由協定 (CGSR) 封包的傳送路徑只由群首節點與閘道節點交替建構而成 C1, G1, C2, G2,,Cn 最後到達目的地叢集的群首節點, 再由目的地群首節點將封包轉送至目的地節點 其優點在於群首節點會有較多的傳送機會, 而閘道節點則是唯一可在各叢集之間轉送封包的節點 每個節點有兩種數據結構 : 叢集成員表 : 描述每個目標節點所在叢集的群首 每個節點會使用 DSDV 協定週期性的與鄰近節點交換叢集成員表以更新表項內容, 並且使用循序號碼來避免老舊路徑資訊的傳播 路由表 : 記錄了位於通往目的地群首路徑上的下一個節點 ( 群首或閘道 ) 46
表格驅動式路由協定 : 群首閘道交換路由協定 (CGSR) CGSR 的運作示意圖 : 由節點 1 傳送封包到節點 13 之範例 47
表格驅動式路由協定 : 群首閘道交換路由協定 (CGSR) DSDV 與 CGSR 的比較 : 最主要的不同之處在於 CGSR 可以避免閘道對閘道的傳送 雖然增加路徑長度 不同方法會走不同路線, 黑箭頭表 CGSR 方法, 白箭頭表 DSDV 方法 模擬結果 CGSR 比 DSDV 有較少的平均延遲時間 48
需求式路由協定 : 輕量移動路由協定 (LMR) 在被動式建立路由演算法中, LMR 會考慮以下幾點 : 有需要時, 才建立路徑 在網路拓撲發生改變前, 此演算法仍可以被使用 已存在的路徑被毀壞或改變時, 則需迅速地反應以重建新的路徑 LMR 乃是利用一種詢問與回應 (Query-reply Process) 的處理機制, 藉由簡短的控制封包來建立路由之集合, 以維護多路徑之結果 當網路拓撲改變或存在之路徑損壞時, 詢問與回應的機制會主動地刪除無效的路徑並快速地重建新的路由集合 LMR 的另一個新的特點就是來源端的初始化 (Source-initiated) 來源端的初始化是指給定一個目的地端 (DEST), 而此演算法只會針對那些要求路由的來源端 (Source) 進行路徑的維護工作, 並不會同時對整個網路路由都進行維護 49
需求式路由協定 : 輕量移動路由協定 (LMR) 路由的建立與維護 : LMR 的執行可以被分成三個基本階段 : 路由建立階段 : 建立一個初始的路由集合 路由維護階段 : 當路徑有遭受毀壞, 且又有資料傳輸需要使用該路徑時, 即立即重新建立一條新的路徑以維護整個拓撲 路由消失階段 50
需求式路由協定 : 輕量移動路由協定 (LMR) LMR 定義與格式 : 網路拓撲 : 假設圖形 G=(N,L) 為包含 N 個有限節點與 L 條無方向性鏈結之集合 在此圖形 G 中, 任兩個相鄰之節點可以相互溝通 節點 j 與節點 i 之間存在一個鏈結 l i,j, 而此鏈結可以是有方向性或沒有 若此鏈結之方向為從節點 i 到節點 j, 則節點 i 為節點 j 之 上游 (Upstream,UP) 且稱節點 i 為節點 j 的 上游相鄰節點 反之, 節點 j 則為節點 i 之 下游 (Downstream,DN) 且稱節點 j 為節點 i 的 下游相鄰節點 51
需求式路由協定 : 輕量移動路由協定 (LMR) 在鏈結層上的通訊協定有以下幾項假設 : 每個節點 i 在所有時間點上都知道其所有的相鄰節點 傳輸的封包皆會被正確的接收 資料封包和控制封包使用不同的通道 LMR 具有三個不同型態的控制封包 : 詢問 (Query,QRY) 回應 (Reply,RPY) 錯誤詢問 (Failure-query,FQ) 詢問 (QRY) SID DID SEQ XID 回應 (RPY) DID XID 錯誤詢問 (FQ) DID XID 控制封包欄位 52
需求式路由協定 : 輕量移動路由協定 (LMR) 欄位說明 : 來源節點識別碼 (Source Node Identifier,SID) 目的節點識別碼 (Destination Node Identifier,DID) 循序計數器 (Sequence Counter,SEQ) 交換識別碼 (Transmitting Node Identifier,XID) SID 是用來識別發送 QRY 的來源節點, 而 DID 則是接收此 QRY 的目的端 在 LMR 中, 這目的節點即是指 DEST 不同來源節點對不同目的節點都會擁有各自的 SEQ 序列號碼 如此, 此三個欄位 (SID,DID,SEQ) 即形成一個用來區分不同 QRY 的唯一識別區 XID 欄位用來識別最近廣播的封包和得到更新 QRY 傳播的節點 XID 是會改變的, 而此改變會隨著 QRY 所傳播的節點不同而不同 53
需求式路由協定 : 輕量移動路由協定 (LMR) 對於每個鄰居節點 j, 節點 i 包含著一個鏈結的狀態表 (Link State) LS j 而對於一個主動鏈結會具有以下六個狀態中之一種 : 未指定 (Unassigned,UN): 未指定方向之鏈結 上游 (Upstream,UP): 指向上游節點之鏈結 下游 (Downtream,DN): 指向下游節點之鏈結 阻擋向下游 (Downstream-blocked,DN-B): 阻擋指向下游節點之鏈結 未指派等待 (Unassigned-waiting,UN-W): 等待被指定方向之鏈結 等待廣播 (Awaiting-broadcast,A-BR): 等待接受廣播之鏈結 若某一節點 i 並未與其相鄰節點 j 鏈結, 則此相鄰節點 j 將會標記 NULL 以表示此鏈結為被動鏈結 在鏈結的標記方面, 若此鏈結被標記為 UN UN-W 或是 A-BR 則代表此鏈結為無方向性的 否則, 此鏈結則為有方向性 54
需求式路由協定 : 輕量移動路由協定 (LMR) LMR 演算法流程 : 詢問與回應 (QRY-RPY) 機制 : 由 SRC 送 QRY 給其鄰點, 那些沒有路徑之節點在接收到一個 QRY, 將會重新廣播或轉遞 QRY 當某一節點有路徑則會廣播一個 RPY, 此 RPY 將朝著發 QRY 的來源節點方向反向泛濫, 路由因此而被建立 55
需求式路由協定 : 輕量移動路由協定 (LMR) 錯誤詢問與回應 (FQ-RPY) 機制 : 假如發生鏈結錯誤的節點沒有其他節點之路徑通過它到 DEST, 且其亦有上游節點, 則朝著它的上游節點發一個 FQ 56
建立 維護與消失路由的方式 : 在網路開始的時候, 除了鄰近 DEST 的節點外, 其餘節點的鏈結都是無方向性 建立路由階段 : (QRY-RPY 機制 ) 需求式路由協定 : 輕量移動路由協定 (LMR) 57
需求式路由協定 : 輕量移動路由協定 (LMR) 維護與消失路由階段 (1): 在下游鏈結錯誤後路由重建階段 (QRY-RPY 機制 ) 58
需求式路由協定 : 輕量移動路由協定 (LMR) 維護與消失路由階段 (2): 無效路由刪除, 路由重建階段 (FQ-RPY 機制 ) 59
需求式路由協定 : 動態來源路由協定 (DSR) DSR 是由來源節點進行主動尋路的一種無線網路路由技巧 任一來源節點皆可透過對自身路由快取的維護, 或是藉由路徑探知而動態產生路徑, 並以此決定使用較適合之路徑 DSR 相較於其他主動式路由協定 : DSR 不需額外產生一些與路由相關的週期性資訊, 也就是沒有任何的週期性路由資訊在節點之間氾濫, 這將會節省許多頻寬上的浪費 來源節點決定了所有封包在傳遞時所需經過的中間節點順序, 此路由的資訊將會被放在封包的頭端 (Header) 部份, 而此封包將會依此順序來傳遞至目的節點 DSR 包含了兩個主要的階段 : 路徑探知階段 路徑維護階段 DSR 允許網路內的任一個節點能同時擁有多條路徑 60
需求式路由協定 : 動態來源路由協定 (DSR) 在無基礎式網路內 DSR 路由協定的運作流程圖 假設這些節點皆能夠轉送來自網路中任一節點所產生之封包, 且在網路剛形成之初, 所有節點內之路由快取皆是空的 61
需求式路由協定 : 動態來源路由協定 (DSR) DSR 路由協定 : 當網路處於初始狀態, 或某一來源節點在其路由快取中搜尋不到任何與目的節點有關之路徑時, 則此來源節點將進入路由探知階段 在路由探知階段, 來源節點會產生一個 路由請求 (Route Request, RREQ) 之封包, 再透過廣播方式將此請求封包送至其鄰近之節點 在 RREQ 封包的表頭檔裡, 存在有一個名為 路由記錄 之欄位 當接收到此 RREQ 封包之節點不是目的節點, 且在此欄位中亦無自己位址之記錄時, 此節點將會把自身的位址依序填入此記錄中, 再將此 RREQ 封包繼續廣播出去, 直到此封包達到目的節點為止 當目的節點接收到一個 RREQ 封包時, 此目的節點將會產生一個名為 路由回應 (Route Reply,RREP) 之封包 其中包含了此 RREQ 封包中所收集的路由記錄 在廣播的過程中, 當任何中間節點在接收到 RREQ 封包時, 若當時該節點之路由快取內已擁有有關到目的節點的路徑資訊, 則此中間節點將會把此路徑資訊直接附在 RREP 封包內, 再由此節點直接送回給來源節點, 而不再繼續廣播 RREQ 封包 62
需求式路由協定 : 動態來源路由協定 (DSR) 路由探知階段之流程圖 63
需求式路由協定 : 動態來源路由協定 (DSR) Route Discovery Route Reply 64
需求式路由協定 : 動態來源路由協定 (DSR) 65
需求式路由協定 : 動態來源路由協定 (DSR) 節點都會維護一個所謂的 傳送暫存區 (Send Buffer) 當節點想要傳送封包時, 若其無法在路由快取內馬上找到一條適合的路徑時, 此封包將會先被存於傳送暫存區中以等待新的路由探知結果 為避免此暫存區因儲存過多暫存性封包而發生溢位之情況, 節點本身必須採用先進先出 First In First Out, 簡稱 FIFO 或其他之演算法來對存於此暫存區之封包進行篩選 節點內所維護的傳送暫存區 66
需求式路由協定 : 動態來源路由協定 (DSR) Example 1: 在路由探知階段, 來源節點 A 欲尋找至目的節點 E 之路徑而廣播其 RREQ 封包卻發生重複路徑之情況 F 發現重複路徑之發生故其將不會發出 RREP 67
需求式路由協定 : 動態來源路由協定 (DSR) Example 2: 在某些網路環境下,DSR 路由協定會產生一種名為 路由回應風暴 (RREP Storms) 之問題 當某一個節點 A 把對某一目的節點 G 之 RREQ 封包廣播出去時, 若是其數個鄰近節點 ( 如 : 節點 B, C, D, E, F) 之路由快取中皆存有對此目的節點 G 之路徑, 而不約而同地發出其各自的 RREP 封包 如此一來, 除了會大量浪費網路頻寬之外, 更可能產生網路內 RREP 封包間的碰撞而使節點 A 無法正確收到任何回應之封包, 如下圖所示 Random Delay to wait the data sent from A 68
需求式路由協定 : 無基礎式需求距離向量路由協定 (AODV) AODV 是以循序的目的地距離向量路由協定 (DSDV) 與動態來源端路由協定 (DSR) 為基礎發展而得 AODV 同時採用了 DSDV 中的逐跳路由 (Hop by Hop) 序列號碼 (Sequence Number) DSR 中的需求式路由機制 ( 即指路由的探知與維護方式 ) AODV 與 DSDV 不同之處在於,AODV 會因應當時所需之路徑來進行操作而減少了廣播路由尋找封包的次數 而與 DSR 相比, AODV 的封包並不需要像 DSR 包含該條路由所有節點的資訊, 以減低網路頻寬的浪費 69
需求式路由協定 : 無基礎式需求距離向量路由協定 (AODV) AODV 的運作 : AODV 是利用封包中網際網路表頭 (IP Header) 部份的資訊來處理整個網路的路由運作 在 AODV 架構下所有封包皆是利用網際網路中 UDP/IP 協定, 並使用埠號 (Port Number):654 與 255.255.255.255 的網際網路位址 (IP Address) 對整個網路進行封包的廣播 AODV 中的序列號碼 : 在每個節點所記錄的路由表中, 除了有目的節點的 IP 位址之外, 還多記錄了目的節點的路由序列號碼, 而這組序列號碼即稱之為 目的地序列號碼 (Destination Sequence Number), 用來維持 AODV 路由資訊的更新 AODV 定義之序列號碼範圍為 32 位元的正整數, 即 0 至 223-1 因此, 當序列號碼到達其上限值時, 如果再增加則數值會重回為 0 70
需求式路由協定 : 無基礎式需求距離向量路由協定 (AODV) AODV 節點中之路由表 : 在 AODV 中, 每個節點內部都會擁有一個路由表來維持其路徑資訊 而此路由表中所記錄的除了上述序列號碼之外, 也記錄了一些有用的資訊, 如下所述 : 目的節點 (Destination) 位址 : 記錄著目的節點的 IP 位址 下一個中繼節點 (Next Hop): 記錄位於通往目的節點之路徑上的下一個中繼節點 中繼節點個數 (Number of Hops): 記錄本節點到目的節點間所需經過的中繼節點個數 目的節點序列號碼 (Sequence Number for the Destination): 記錄該目的節點之序列號碼 路徑有效時間 (Expiration Time for the Route Table Entry): 記錄該路徑資訊存在路由表中的有效時間 活躍的鄰居節點 (Active Neighbor): 在一節點的路由表中, 每條路徑的上游節點 71
需求式路由協定 : 無基礎式需求距離向量路由協定 (AODV) AODV 協定中定義了四種控制封包格式 : 路徑請求 (Route Request, 簡稱 RREQ) 封包 : 當某個來源節點欲傳送資料至另一個目的節點, 如果此來源節點在本身之路由表中找不到可以到達該目的節點之路徑, 或是此路徑資訊已經過期而被註記為無效時 這時來源節點將會廣播 路徑請求 (RREQ) 封包以搜尋能夠到達該目的節點之新路徑, 如下圖所示 72
需求式路由協定 : 無基礎式需求距離向量路由協定 (AODV) 路徑回覆 Route Reply(RREP) 封包 : 在整個網路中, 收到 RREQ 封包之節點會根據 RREQ 封包上之發起者 IP 位址與 UDP/IP 表頭內容資訊搜尋本身之路由表, 然後對發起此 RREQ 封包之發起者進行逆向路徑之更新或建立以利將來 RREP 封包的回送 同樣地, 收到 RREP 封包之節點, 也會建立或更新前往目的節點之路徑, 以確保路徑資訊的最新狀態 等回送的 RREP 封包被發起者收到後, 一條具有雙向路徑資訊的通道就被建立完成如下圖所示 建立從來源節點至目的節點之雙向路徑, 而右邊兩個節點則因無法找到目的節點, 因而丟棄 RREQ 封包, 只保留對來源節點的反向路徑 73
需求式路由協定 : 無基礎式需求距離向量路由協定 (AODV) 在 AODV 協定中, 會發出 RREP 封包之節點有兩種 : 一種是 RREQ 封包中所記錄之目的節點 另一種則是介於來源節點與目的節點之間的中繼節點 RREP 封包回送至發起者之範例 74
需求式路由協定 : 無基礎式需求距離向量路由協定 (AODV) 路徑錯誤 Route Errors(RERR) 封包 : 一般在 AODV 協定下, 某一節點要處理路徑錯誤 (Route Error) 鏈結毀損 (Link Breakage) 或是路徑刪除 (Route Deletion) 時將會依照下列幾個步驟 : 首先, 先把該路徑設為無效 列出因此受到影響之所有目的節點 檢查是否有鄰近之節點亦會受到影響 送出 Route Errors(RERR) 封包給這些受影響之鄰近節點 75
需求式路由協定 : 無基礎式需求距離向量路由協定 (AODV) 一個節點會發出 RERR 封包之情況, 可分為以下三種 : 當某一節點在傳輸資料時, 發現原本可用之路徑 (Active Route) 發生鏈結毀損 (Link Breakage), 並嘗試自行修復路徑 (Route Repair) 無效時 當某一節點收到一個已經具有預設目的節點之資料封包時, 卻發現本身並無此目的節點之有效的路徑 當某一節點收到一個 RERR 封包, 且其上所通知之路徑與本節點記錄中之一條或多條有效路徑有關時 76
需求式路由協定 : 無基礎式需求距離向量路由協定 (AODV) Example 1: 根據 AODV 協定與時間點描述之方式來示範節點 A 如何傳送資料封包到節點 H 此網路中具有八個節點, 而各節點間之連線則代表各節點存在路由表中已知之路徑 假設節點 A 為來源節點, 節點 H 為目的節點 網路拓撲示意圖 77
需求式路由協定 : 無基礎式需求距離向量路由協定 (AODV) AODV 運作流程 (1): 78
需求式路由協定 : 無基礎式需求距離向量路由協定 (AODV) AODV 運作流程 (2): 79
需求式路由協定 : 無基礎式需求距離向量路由協定 (AODV) Example 2: 節點 F 突然毀損或離開而發生了所謂的路徑錯誤 (Route Error) 之情況 節點 C 開始進行區域修復 (Local Repair) 80
需求式路由協定 : 關聯性基礎路由協定 (ABR) ABR 是一個介於廣播 (Broadcast) 與點對點 (Point-to-point) 的折衷路由方法 在 ABR 協定下, 每個節點不需擁有路由資訊, 而路徑之選擇乃建立於所謂的關聯性 (Associativity) 狀態 此關聯性狀態常常會暗示節點是否正處於一個穩定之狀態, 因此路徑不需要時常被要求重新更新 在一般傳統的路由協定中, 此路由準則之考量如下 : 對於連結 (Link) 變化的快速適應性 考量到達目的節點所需之中繼節點 (Hop) 傳送延遲 (Propagation Delay) 迴路的避免 連結的能力 81
需求式路由協定 : 關聯性基礎路由協定 (ABR) 在 ABR 協定中, 另一套新的路由準則被引用, 而這些考量與節點之關聯穩定度 (Association Stability) 皆有關系, 其描述如下 : 路徑壽命 (Route Longevity) 中間節點 (Intermediate Node,IN) 的轉送負載 (Relaying Load) 被選擇的路徑中, 其具有連結能力的資訊 關聯性刻度 (Associaticity Ticks) 82
需求式路由協定 : 關聯性基礎路由協定 (ABR) 關聯性刻度表示一個移動式主機 (Mobile Host, 簡稱 MH) 在時間 空間上其連線的穩定度 當一個 MH 移動時, 其與鄰近節點之間的關聯就會發生變化 而在此變化發生之期間, 即可用關聯性刻度來表示 在無線網路環境中, 每一個移動式節點會周期性的產生一個訊標 (Beacon) 藉由此訊標節點可以更新自己與其鄰近節點間的關聯性刻度 網路中當某一個鄰近節點具有較高的關聯性刻度時, 則我們會認為此節點正處於穩定之狀態 83
需求式路由協定 : 關聯性基礎路由協定 (ABR) 下圖即表示一個 MH 在 Ad Hoc 無線網路環境中移動時, 與其鄰居間在時間與空間上之關聯性刻度 84
需求式路由協定 : 關聯性基礎路由協定 (ABR) ABR 協定概述 : ABR 協定包含了三個重要的階段 : 路徑探知階段 (Route Discovery) 路徑重建階段 (Route Reconstruction,RRC) 路徑刪除階段 (Route Delete,RD) 當來源節點 (Source,SRC) 需要一條路徑以傳送資料封包時, 此節點即會進入路徑探知階段 若是因 SRC 目的節點 (Destination,DEST) 或者是路徑中某中間節點之移動而造成此路徑變更時, 則此時 SRC 將會進入路徑重建階段 若是此路徑已不再被需要時, 則 SRC 將會進入路徑刪除階段, 以刪除此一路徑 85
需求式路由協定 : 關聯性基礎路由協定 (ABR) ABR 路徑探知階段 : ABR 路徑探知階段是由廣播要求 (Broadcast Query,BQ) 與等待回應 (Wait Reply,REPLY) 兩個所形成的循環階段 當 SRC 需要路徑來傳資料封包到某個 DEST 時, 此時 SRC 會在網路中廣播一個 BQ 封包, 以搜尋並建立到 DEST 之路徑 右圖為 BQ 控制封包格式, 其中包括 : TYPE: 封包種類 SRC ID: 來源節點 ID DEST ID: 目的節點 ID LIVE: 此封包所經過的中繼節點數 IN IDs: 中繼節點 ID METRICS: 關聯性刻度參數 SEQ NO.: 封包序列號碼 CRC: 封包錯誤檢查碼 86
需求式路由協定 : 關聯性基礎路由協定 (ABR) 所有接收到此 BQ 封包之 INs 將先確認, 是否在此之前已經處理過相同之封包, 若已經處理過便丟棄此封包 INs 本身亦會檢查自己是否為 DEST 若不是, 則將自己的 MH 位址填入此封包內, 再將此封包繼續以廣播之方式傳送給其鄰近節點 節點本身之關聯性刻度與其他路由準則參數也會被包在此封包之內 BQ 封包上關聯性刻度資訊的變化之過程 87
需求式路由協定 : 關聯性基礎路由協定 (ABR) 當 DEST 接收到一個 BQ 封包, 從此封包中便可得到一條從 SRC 至 DEST 之路徑 在經歷一段收集時期後 DEST 將會收到許多 BQ 封包, 亦因此而獲得許多可用之路徑 透過最佳路徑演算法,DEST 可以在眾多的路徑中選出一條最佳之路徑 ( 即最穩定之路徑 ), 再透過 REPLY 封包將此路徑之資訊回傳給 SRC 在 ABR 協中, 最佳路徑的意思並非為最短路徑 此演算法利用由 BQ 封包所蒐集到 INs 間之關聯性刻度而得知其路徑之穩定性, 故可能會選擇較穩定但較長之路徑 REPLY 控制封包格式 88
需求式路由協定 : 輔助定位路由通訊協定 (LAR) LAR 協定之運作方式類似動態來源端路由 (DSR) 協定, 其乃是利用位置資訊來改善通訊路由協定之效能 在移動的無基礎式無線網路中 (Ad-hoc Network),LAR 協定會利用全球定位系統 (Global Positioning System, GPS) 提供網路節點在二維平面上之位置資訊進而得知一個可移動主機之位置, 然後使用位置資訊去減少節點在二維平面上路由的額外花費 利用訊息泛濫來尋找路由 : 類似於 DSR,LAR 使用泛濫之方式來找尋路徑 當節點 S 欲找尋一路徑到達節點 D, 則節點 S 將會廣播一個路徑要求訊息封包給它所有之鄰近節點 網路中任何一個節點在收到這個路徑要求訊息封包時, 會先比較此封包中所載之目的節點是否為自己 若為自己, 表示已找到目的節點 反之, 此節點將會繼續轉送此訊息封包 89
需求式路由協定 : 輔助定位路由通訊協定 (LAR) 在訊息封包氾濫的過程中, 為了避免在網路中傳送多餘的要求訊息, 節點在轉送訊息封包給其鄰近節點時, 只會廣播一次 ( 節點會使用自身的序列計數器來檢測重複接收之訊息封包 ) 若經歷一段時間後目的節點沒有收到任何路徑要求訊息或來源節點沒有收到任何路徑回應 ( 可能是封包遺失或損壞等 ), 都會造成此次的廣播封包逾時 (Timeout) 而無效 LAR 使用訊息泛濫之方式來找尋路徑 90
需求式路由協定 : 輔助定位路由通訊協定 (LAR) 預期區域與要求區域 (Expected Zone and Request Zone): 所謂的 預期區域 是指 : 某一節點 S 欲找尋一條路徑至某一節點 D, 若在時間為 t 0 時節點 S 知道節點 D 在位置 L 處 而當時間點為 t 1 時, 節點 D 之移動平均速度為 v, 故節點 S 可假定節點 D 在時間點為 t 1 時之位址是在以 L 為中心點,v(t 1 -t 0 ) 為半徑之圓的範圍內, 如下圖 (a) 所示 圖中灰色所涵蓋之範圍即為預期區域 然而, 若節點 D 之實際移動速率大於平均速率, 則在時間為 t 1 時, 此目的節點 D 將可能會位於預期區域之外 另一方面, 若節點 S 若能擁有較多關於可移動目的節點之資訊, 則將可以產生出一個較很小的預期區域 例如節點 S 知道目的節點 D 欲往北移動, 則此預期區域將會是圖 (a) 所示之圓的一半, 如圖 (b) 所示 Y v (t 1 -t 0 ) D (Lx, Ly) Y v (t 1 -t 0 ) D (Lx, Ly) X (a) (b) X 91
需求式路由協定 : 輔助定位路由通訊協定 (LAR) 所謂的 要求區域 是指 : 某一節點 S 欲找尋一條路徑至某一節點 D, 則此節點 S 會先設定一個要求區域, 如下圖所示 92
需求式路由協定 : 輔助定位路由通訊協定 (LAR) 若來源節點 S 不在預期區域內, 則從節點 S 到節點 D 之路徑上將會擁有預期區域外之節點 故此類節點所形成之額外的範圍將會被含括在要求區域中, 如前圖 (c) 所示 以此類推節點 S 與節點 D 兩者會逐漸被至於要求區域 93
演算法 : 需求式路由協定 : 輔助定位路由通訊協定 (LAR) 第一類 LAR 協定演算法 : 此方法使用一個矩形的要求區域來尋找路徑, 如下圖所示 在第一類演算法中, 首先需先定義要求區域為一個最小之矩形且其邊需個別平行於 X 軸與 Y 軸 而在此矩形中將包含著目前的節點 S 與預期區域 A (Xs, Yd+R) P (Xd, Yd+R) B (Xd+R, Yd+R) A (Xd-R, Yd+R) P (Xd, Yd+R) B (Xd+R, Yd+R) 整個網路空間 J (Xj, Yj) R D (Xd, Yd) 預期區域要求區域 I (Xi, Yi) Q (Xd+R, Yd) U (Xd-R, Yd) 整個網路空間 預期區域 S (Xs, Ys) D (Xd, Yd) R 要求區域 Q (Xd+R, Yd) B (Xd-R, Yd-R) T (Xd, Yd-R) C (Xd+R, Yd-R) S (Xs, Ys) C (Xd+R, Ys) (a) 來源節點 S 在預期區域範圍外 (b) 來源節點 S 在預期區域範圍內 94
需求式路由協定 : 輔助定位路由通訊協定 (LAR) 一開始, 來源節點 S(Xs, Ys) 會先計算出要求區域之四個角落 在路徑要求訊息封包氾濫時, 若有一非位於矩形內之節點收到此一訊息封包, 則其將會丟棄此封包 否則, 會將其再轉送至鄰近節點以尋找路徑 ( 限制廣播 ) 第二類 LAR 協定演算法 : 在第一類演算法中, 來源節點會明確地在訊息封包中指出要求區域 在此類演算法中, 要求區域已不再被需要, 而是需要考慮與目的節點之幾何距離 來源節點所發出之路經要求訊息封包中將會包含兩筆資訊 : 在尋路之時, 假設來源節點 S 知道目的節點 D 之位置為 (X d, Y d ) 則節點 S 會計算 (X d, Y d ) 到它自己之距離 ( 以 DISTs 表示 ), 而此距離值將會被包含在節點 S 所發出之訊息封包中 此外, 此訊息封包內亦會包含目的節點 D 之位置座標 (X d, Y d ) 95
需求式路由協定 : 輔助定位路由通訊協定 (LAR) 當某一節點 I 收到從節點 S 送出之訊息封包, 此節點 I 將會計算 (X d, Y d ) 到它自己之距離 ( 以 DISTi 表示 ), 同時再考慮 : 某一參數 δ, 若 (DISTs+δ DISTi), 則節點 I 將會繼續廣播此訊息封包到鄰近節點, 且此訊息封包包含了 DISTi 和 (X d, Y d ) 之資訊 反之, 若 (DISTs+δ DISTi), 則節點 I 將丟棄此訊息封包 當某一節點 J 收到從節點 I 送出之訊息封包 : 倘若節點 J 先前已接收過此相同之封包, 則其會丟棄此封包 否則節點 J 將會計算 (X d, Y d ) 到它自己之距離 ( 以 DISTj 表示 ) 同時再考慮 : 若 (DISTi+δ DISTj), 則節點 J 將會繼續廣播此訊息封包到鄰近節點, 且此訊息封包中之 DISTi 值將被 DISTj 值所取代 反之, 若 (DISTi+δ DISTj), 則節點 J 將丟棄此訊息封包 96
需求式路由協定 : 輔助定位路由通訊協定 (LAR) 第一 二類 LAR 協定演算法之比較 : 整個網路空間 D (Xd, Yd) R 整個網路空間 D (Xd, Yd) 預期區域要求區域 DISTs DISTn N DISTi DISTk N I K I S (Xs, Ys) K S (Xs, Ys) (a) 第一類 LAR 協定演算法 (b) 第二類 LAR 協定演算法 97
需求式路由協定 : 輔助定位路由通訊協定 (LAR) 演算法流程 1: LAR 協定 : 利用位置資訊來減少尋路時所需搜尋之範圍 98
需求式路由協定 : 輔助定位路由通訊協定 (LAR) 演算法流程 2: LAR 協定 : 藉由全球定位系統來尋找路徑 99
需求式路由協定 : 輔助定位路由通訊協定 (LAR) 區域搜尋 (Local Search): 在 LAR 協定中, 任何中繼節點 ( 如節點 I) 偵測到路徑發生錯誤或損壞時, 此節點 I 會送出一個路徑錯誤封包給來源節點 S, 如下圖所示 當來源節點 S 收到此封包, 其將會重新進行另一個新路徑的初始化程序, 以找尋另一條可到達目的節點 D 之新路徑 然而, 因從來源節點 S 至節點 I 之間之路徑並無損壞, 故初始化之尋路範圍將僅被侷限於節點 I 與目的節點 D 之間 S 路由錯誤封包 I WLAN D S 節點 S 的要求區域 I WLAN D S I 節點 I 的要求區域 WLAN D (a) (b) (C) 100
ZRP (Zone Routing Protocol) The Zone Routing Protocol (ZRP) for Ad Hoc Networks Cornell University Z.J. Haas and M.R. Pearlman draft-ietf-manet-zone-zrp-01.txt, 1998 101
ZRP Outline Hybrid of table-driven and on-demand!! From each node, there is a concept of zone. Within each zone, the routing is performed in a table-driven manner (proactive). However, a node does not try to keep global routing information. For inter-zone routing, on-demand routing is used. This is similar to DSR. 102
ZRP Example 103
Route Discovery By an operation called boardercast : sending the route-request to boarder nodes 104
集中式與分散式操作 主動式與需求式路由方式 週期性更新 多路徑維護 單向 / 雙向路徑 平面 / 叢集 分組轉送機制 路徑度量選擇 特殊節點 特殊硬體需求 支援群播功能 服務品質 (QoS) 結論與比較 105
結論與比較 DSDV CGSR WRP LMR TORA DSR AODV ABR LAR 分散式操作是是是是是是是是是 主動需求主動主動主動需求需求需求需求需求需求 週期性更新是是是是否否否否是 維護多條路徑否是否是是是否否是 單向 / 雙向路徑雙向雙向雙向單向雙向單向雙向雙向雙向 省能源否否否否否否否否否 平面群集平面群集平面平面平面平面平面平面平面 分組轉送機製逐跳逐跳逐跳逐跳逐跳源路由逐跳逐跳逐跳 提供安全機製無無無無無無無無無 路由度量選擇 最短路徑 最短路徑 最短路徑 最短路徑 存在特殊節點否有否否否否否否否 特殊硬體需求否否否否 GPS 否否否否 支援群撥功能否否否否否否否否否 Qos 否否否否否否否否否 最短路徑 最短路徑 最短路徑 最短路徑 最短路徑 106