FSR

FSR协议（Fisheye State Routing Protocol）是一种先应式的链路状态协议，但是综合采用了距离矢量和链路状态两种协议的思想。

FSR基本思想

FSR协议基于一种“鱼眼”（fusheye）技术，模仿鱼眼的功能，通过对不同距离的节点采用不同的路由更新频率，使得距离越近的节点，掌握的路由信息越准确。另外它的路由更新分组仅在邻节点之间交换，减少了用于路由的控制开销。

FSR关键技术问题

1、鱼眼技术

模仿鱼眼的生理特征，FSR协议采用了以下作法：一是划分节点不同层次的鱼眼范围（scope of fisheye），二是在不同鱼眼范围内采用不同的路由更新频率，由此维护远近不同精度的路由信息。

图1-1 FSR协议的鱼眼范围节点i的鱼眼范围定义为从i出发，在N跳内可达的节点集合。如图1-1所示，节点11有3个鱼眼范围：范围1为节点11一跳可达的节点集合，范围2为节点11两跳可达的节点集合，范围3为节点11多于两跳可达的节点集合。鱼眼范围的层次数和半径由网络的大小来确定。

FSR协议采用周期性发送链路状态信息分组的方法来更新路由表。鱼眼范围不同，路由的更新频率也不同，鱼眼范围越小，其路由更新频率越高，这样可以大大地降低路由的开销。目的节点距离自己的距离不同路由信息的精度也不相同，目的节点距离越远，路由信息就越不准确。

2、路由分组的传递方法

FSR协议是一种链路状态协议，网络中的节点间需要交换链路状态信息分组，但是不同于普通的链路状态协议。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）邻居列表Ai

为节点i的邻节点列表

2）拓扑表TTi

每个节点j，均在该表中有一个路由条目。该表的结构如图1-2所示。

节点标识符j

链路状态LS（j）

时间戳SEQ（j）

图1-2 FSR协议节点的拓扑表

LS（j）字段中存储节点j报告的链路状态，SEQ（j）字段中存储节点j产生该链路信息的时间戳。

3）下一跳表NEXTi

NEXTi(j)给出到达目的节点j最短路径上的下一跳地址。

4）距离表Di

Di(j)给出从节点i到节点j最短路径的长度。可以使用不同的加权函数来计算，本算法使用跳数来计算最短路径，即如果两个节点之间存在一跳边，则两者之间的权值为1；否则两者之间的权值为无穷。

（2） 交换的消息

图1-3 使用FSR协议后控制消息的变化邻节点之间周期性地交换拓扑表中的链路状态信息，如图1-3所示，离节点的距离越近，更新的频率越高，图中字体加黑且倾斜的条目比不加黑不倾斜的条目更新频率高。

2、工作过程

（1） 节点的初始化

协议开始运行时，每个节点的邻居列表Ai和拓扑表TTi均为空。

（2） 路由分组的处理

假设一个节点只能收到邻节点发送的链路状态分组，这样当节点i收到链路状态分组时，就会将该分组的发送者添加至自己的邻居列表Ai，并更新本地存储的拓扑表TTi。对每个TTi中的节点j，检查pkt.SEQ(j)与本地的TTi.SEQ(j)，如果前者的序列号新，则使用pkt.LS(j)替换本地的TTi.LS(j)，同时pkt.SEQ(j)替换本地的TTi.SEQ(j)。

（3） 修改邻居列表和拓扑表

处理完接收到的路由分组后，节点i将检验本地邻居列表Ai中节点的有效性，用新的Ai修改拓扑表TTi中的TTi.LS(i)。

（4） 计算最短路径

根据最新的拓扑表TTi，使用选定的最短路径计算节点i至所有其他节点的最短路径，更新NEXTi表及Di表。

（5） 向邻节点发送最新的链路状态信息

扫描本地的拓扑信息表TTi，对每一个条目TTi.LS(j)，根据D（j）是否在FSR协议规定的范围层次n内，决定是否将TTi.LS(j)加入到欲发送的路由分组中。FSR协议有不同的范围层次，不同的范围层次有不同的更新频率，离节点的距离越近，更新的频率越高。

生成路由分组后，向邻节点广播并进入下一轮的路由分组处理过程。

（6） 数据分组转发

每个节点根据自己计算的“最短”路径转发数据分组。在转发节点与目的节点之间距离较远的情况下，受链路状态传播时延和节点移动性的影响，该“最短”路径未必最短。随着数据分组距离目的节点越来越近，转发节点存储的路由信息也越来越精确，直至数据分组最终到达目的节点。

FSR总结

FSR协议是一种先应式的自组网路由协议，它运用鱼眼技术对不同距离的节点采用不同的路由更新频率，并且路由分组仅在邻节点之间交换，降低了路由的控制开销。通过恰当选择鱼眼范围层次和半径大小，可以提供比较准确的路由信息。该协议存在的问题是路由表的大小仍然随网络的增大而线性增加，到达远处目的节点的路径可能是过时的。