FSR

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

1、魚眼技術

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

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

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的鄰節點列表

2）拓撲表TT

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

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

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

3）下一跳錶NEXT

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

4）距離表D

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

（2）交換的消息

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

2、工作過程

（1）節點的初始化

協議開始運行時，每個節點的鄰居列表A和拓撲表TT均為空。

（2）路由分組的處理

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

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

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

（4）計算最短路徑

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

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

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

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

（6）數據分組轉發

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

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