FSR(路由協定)

FSR協定（Fisheye State Routing Protocol）是一種先應式的鏈路狀態協定，但是綜合採用了距離矢量和鏈路狀態兩種協定的思想。

基本介紹

• 中文名：魚眼狀態路由
• 外文名：Fisheye State Routing
• 外語縮寫：FSR
• 類型：路由協定

基本思想

FSR協定基於一種“魚眼”（fusheye）技術，模仿魚眼的功能，通過對不同距離的節點採用不同的路由更新頻率，使得距離越近的節點，掌握的路由信息越準確。另外它的路由更新分組僅在鄰節點之間交換，減少了用於路由的控制開銷。

關鍵技術問題

1、魚眼技術

模仿魚眼的生理特徵，FSR協定採用了以下作法：一是劃分節點不同層次的魚眼範圍（scope of fisheye），二是在不同魚眼範圍內採用不同的路由更新頻率，由此維護遠近不同精度的路由信息。

節點i的魚眼範圍定義為從i出發，在N跳內可達的節點集合。如圖1-1所示，節點11有3個魚眼範圍：範圍1為節點11一跳可達的節點集合，範圍2為節點11兩跳可達的節點集合，範圍3為節點11多於兩跳可達的節點集合。魚眼範圍的層次數和半徑由網路的大小來確定。

圖1-1 FSR協定的魚眼範圍

FSR協定採用周期性傳送鏈路狀態信息分組的方法來更新路由表。魚眼範圍不同，路由的更新頻率也不同，魚眼範圍越小，其路由更新頻率越高，這樣可以大大地降低路由的開銷。目的節點距離自己的距離不同路由信息的精度也不相同，目的節點距離越遠，路由信息就越不準確。

2、路由分組的傳遞方法

FSR協定是一種鏈路狀態協定，網路中的節點間需要交換鏈路狀態信息分組，但是不同於普通的鏈路狀態協定。FSR協定的鏈路狀態信息分組僅在鄰節點之間交換，而普通的鏈路狀態協定採用洪泛的方法。

路由協定描述

設自組網的模型為無向圖G=（V,E），V為節點的集合，E為連線V中節點的無向邊。每個節點代表自組網中的一個無線移動設備，有唯一的標識符，傳輸範圍為R且有無窮的存儲空間。節點何以自主移動，改變速度及方向等。當兩個節點i，j之間的距離小於或等於傳輸範圍R時，i,j之間就形成一條無向邊（i,j）；當節點i,j運動導致兩者之間的距離大於傳輸範圍R時，就需從圖G中刪除無向邊（i,j）。

1、信息種類

（1） 存儲的訊息

每個節點i都維護一個列表和三張表，如下所述。

1）鄰居列表A_i

為節點i的鄰節點列表

2）拓撲表TT_i

每個節點j，均在該表中有一個路由條目。該表的結構如圖1-2所示。

節點標識符j

鏈路狀態LS（j）

時間戳SEQ（j）

圖1-2 FSR協定節點的拓撲表

LS（j）欄位中存儲節點j報告的鏈路狀態，SEQ（j）欄位中存儲節點j產生該鏈路信息的時間戳。

3）下一跳表NEXT_i

NEXT_i(j)給出到達目的節點j最短路徑上的下一跳地址。

4）距離表D_i

D_i(j)給出從節點i到節點j最短路徑的長度。可以使用不同的加權函式來計算，本算法使用跳數來計算最短路徑，即如果兩個節點之間存在一跳邊，則兩者之間的權值為1；否則兩者之間的權值為無窮。

（2） 交換的訊息

鄰節點之間周期性地交換拓撲表中的鏈路狀態信息，如圖1-3所示，離節點的距離越近，更新的頻率越高，圖中字型加黑且傾斜的條目比不加黑不傾斜的條目更新頻率高。

圖1-3 使用FSR協定後控制訊息的變化

2、工作過程

（1） 節點的初始化

協定開始運行時，每個節點的鄰居列表A_i和拓撲表TT_i均為空。

（2） 路由分組的處理

假設一個節點只能收到鄰節點傳送的鏈路狀態分組，這樣當節點i收到鏈路狀態分組時，就會將該分組的傳送者添加至自己的鄰居列表A_i，並更新本地存儲的拓撲表TT_i。對每個TT_i中的節點j，檢查pkt.SEQ(j)與本地的TT_i.SEQ(j)，如果前者的序列號新，則使用pkt.LS(j)替換本地的TT_i.LS(j)，同時pkt.SEQ(j)替換本地的TTi.SEQ(j)。

（3） 修改鄰居列表和拓撲表

處理完接收到的路由分組後，節點i將檢驗本地鄰居列表A_i中節點的有效性，用新的A_i修改拓撲表TT_i中的TT_i.LS(i)。

（4） 計算最短路徑

根據最新的拓撲表TT_i，使用選定的最短路徑計算節點i至所有其他節點的最短路徑，更新NEXTi表及D_i表。

（5） 向鄰節點傳送最新的鏈路狀態信息

掃描本地的拓撲信息表TTi，對每一個條目TTi.LS(j)，根據D（j）是否在FSR協定規定的範圍層次n內，決定是否將TTi.LS(j)加入到欲傳送的路由分組中。FSR協定有不同的範圍層次，不同的範圍層次有不同的更新頻率，離節點的距離越近，更新的頻率越高。

生成路由分組後，向鄰節點廣播並進入下一輪的路由分組處理過程。

（6） 數據分組轉發

每個節點根據自己計算的“最短”路徑轉發數據分組。在轉發節點與目的節點之間距離較遠的情況下，受鏈路狀態傳播時延和節點移動性的影響，該“最短”路徑未必最短。隨著數據分組距離目的節點越來越近，轉發節點存儲的路由信息也越來越精確，直至數據分組最終到達目的節點。

總結

FSR協定是一種先應式的自組網路由協定，它運用魚眼技術對不同距離的節點採用不同的路由更新頻率，並且路由分組僅在鄰節點之間交換，降低了路由的控制開銷。通過恰當選擇魚眼範圍層次和半徑大小，可以提供比較準確的路由信息。該協定存在的問題是路由表的大小仍然隨網路的增大而線性增加，到達遠處目的節點的路徑可能是過時的。