OLSR路由協定
- 概述
-
- 兩種分組
- 路由發現與維護
- 算法步驟
-
- 鍊路感覺
- 鄰居偵聽
- MPR選擇
- 拓撲建立
- 路由表的建立與維護
- 總結
概述
- 優化鍊路狀态路由（Optimized Link State Routing）協定，即 OLSR 路由協定是一種平面拓撲的先驗式路由協定（主動式路由協定）。
- 節點通過周期性地與自己的鄰居節點交換分組資訊來完成鍊路感覺和鄰居偵測過程，進而建立起自己的拓撲結構。并通過接收拓撲控制分組獲知全網的拓撲資訊，以此為依據計算出一張從自身節點到達全網各個節點傳輸路徑的路由表。
- 當節點有通信需求時可以通過查詢路由表獲得所需的路由資訊。
- 通過HELLO分組的周期性互動，執行鍊路檢測、鄰居發現的功能；
- 通過拓撲控制（TC）分組的周期性互動執行多點中繼節點（MPR）資訊聲明功能；
- 最終以這些分組所建立起來的拓撲結構為基礎，進行基于 MPR 的路由計算。
兩種分組
OLSR 協定中主要用到兩種分組格式，為 HELLO 消息和 TC 分組。
- HELLO 消息主要用于鍊路感覺、鄰居偵聽過程，節點之間通過交換 HELLO 消息建立自己的本地連接配接庫、鄰居資訊庫；
- TC 分組為拓撲控制分組，用于節點建立拓撲資訊庫，然後據此計算節點到網絡中每個目的節點的路由。
路由發現與維護
算法步驟
鍊路感覺
每個節點都要探測與其鄰節點間的鍊路，由于無線傳播的不确定性，某些鍊路可能會被認為是單向的。是以，所有鍊路必須雙向驗證才被認為是可用的。可以雙向互動的鍊路是對稱鍊路，可以雙向互動的兩個節點是對稱節點。
鍊路感覺是通過 HELLO 分組的周期性互動實作的。本地鍊路資訊表存儲了該節點到鄰居節點的鍊路資訊。節點發送 HELLO 分組時，本地鍊路資訊表作為消息的内容。節點收到 HELLO 分組，更新本地鍊路資訊表。
鄰居偵聽
每個節點必須檢測它與哪些鄰節點間具有雙向鍊路。HELLO 分組中攜帶了節點的鄰節點資訊和鍊路狀态。HELLO 分組隻在一跳範圍内傳輸。通過 HELLO 分組的周期性互動，節點生成了鄰居資訊庫。
鄰居偵聽的過程如下圖 所示，在初始化階段，當節點 A 收到一個來自于鄰居節點 B 的 HELLO分組，A 将 B 放入自己的鄰居集中，并将到 B 的鍊路标記為非對稱狀态，然後，在 A 向 B 發送 HELLO 分組時，在 HELLO 分組中就包含有 B 是 A 的非對稱狀态的鄰居節點的資訊，當 B 收到該 HELLO 分組時，B 将在鄰居集中将 A 的狀态更新為對稱狀态。同理，在 B 再次向 A 發送 HELLO 分組時，HELLO 分組中就包含了 A 是 B 的對稱狀态的鄰居節點的資訊，當 A 收到該 HELLO 分組時，A 就在鄰居集中将 B 的狀态更新為對稱狀态。之後，A、B 再分别計算自己的 MPR，在後面的 HELLO 分組互動中會包含各自的 MPR 資訊。
從一個對稱鄰居中接收到一個 HELLO 分組，節點應更新其兩跳鄰居集。
MPR選擇
多點廣播中繼即 MPR 技術作為 OLSR 路由協定中的一個重要組成部分，可以有效地減少網絡中控制分組的發送數量，其基本思想就是網絡中的每個節點都要選出本地節點的部分 1 跳鄰居節點加入 MPR 集，隻有 MPR 節點才能參與拓撲控制消息（即 TC 分組）的轉發，相較于傳統協定中所有鄰居節點參與轉發的洪泛機制，MPR 技術在很大程度上減小了網絡開銷。
每個節點都會從自己的 1 跳對稱鄰居節點内進行 MPR 節點的選擇，在優先考慮節點的轉發意願的基礎上，把嚴格對稱 2 跳鄰居集内節點連接配接度高的節點選作MPR 節點，MPR 集的詳細計算過程将在後文進行細緻的介紹與分析。 僅有MPR 中的節點有權利将收到的節點資訊進行轉發，而其他鄰節點僅處理資訊而不轉發。
節點A的——
1跳鄰居集合： N N N
2跳鄰居集合： N 2 \ N_2 N2
MPR集合： M M M
D ( y ) D(y) D(y)：N中節點y的連接配接度（除N中節點和A外，y的對稱鄰居數量）
N 2 \ N_2 N2中不包括：
（1）隻通過集合 N 中轉發意願為 WILL_NEVER 的節點才可達的節點；
（2）執行 MPR 集計算的 A 節點本身；
（3）節點 A 的所有對稱鄰居，即與節點 A 之間存在直接的對稱鍊路的節點。
選擇算法：
- 把 N 中的所有轉發意願為 WILL_ALWAYS 的節點加入M；
- 計算集合 N 中的所有節點 y 的連接配接度 D(y)；
- 将 N 中對 N2 中的某個節點 b 提供唯一可達性的節點添加進 M 中，移除N2中可通過M中節點到達的節點；
- 如果在N2 中存在某節點通過M不可達，則計算 N 中節點的可達性（即通過此節點可達的現在 N2 中節點的數目），對比 N 中節點的可達性，在所有可達性非 0 的節點中，将轉發意願 N_willingness 最高的節點加入 M 。如果多個節點的轉發意願相同，則選擇可達性最高的節點；如果可達性相同，則選擇連接配接度 D(y) 最高的節點。然後，移除N2中可通過M中節點到達的節點；
- 若 N2 集不為空，則回退到步驟（3）；N2 集為空，則集合 M 為節點 A 最終的 MPR 集。
拓撲建立
OLSR 協定通過MPR節點在全網範圍内周期性地發送和轉發拓撲控制（TC）分組來擷取拓撲資訊，并形成一個拓撲資訊表。其中，TC隻能由MPR節點産生和轉發，且其分組内容至少包括其MPR選擇集的所有節點。通過這個表，節點可以知道網絡中各個MPR節點以及它的選擇方的拓撲資訊。節點接收到MPR的TC分組時的處理過程如圖所示。
路由表的建立與維護
OLSR 協定中每個節點都需要計算并維持一張不斷更新的路由表。節點依據本地鍊路資訊庫和拓撲資訊表中儲存的資訊，根據 Djisktra 算法以最小跳數為依據建立路由表。由于路由表是基于本地鍊路資訊庫和拓撲資訊表中的資訊建立的，是以每當網絡中拓撲發生鍊路斷裂、拓撲變更、鍊路到期等變化時，節點的本地鍊路資訊庫或拓撲資訊表中的内容也會發生相應變化，此時節點會自發的進行路由表的重新計算。
總結
OLSR 協定特别适用于大型和密集的網絡，因為 MPR 機制的引入使得OLSR 協定的路由開銷相對固定，隻與網絡規模成正相關，與網絡負載的關系較小。此外，由于 OLSR 協定采用主動路由的方式建立與維護路由表，不需要臨時發起路由發現過程，是以 OLSR 協定的資料傳輸的平均端到端時延往往很低，是以 OLSR 協定在網絡流量分布随機且節點位置分布稀疏的網絡條件下通常有較好的傳輸性能。