FSR

路由协议

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

基本思想

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）邻居列表Ai

为节点i的邻节点列表

2）拓扑表TTi

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

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

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

3）下一跳表NEXTi

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

4）距离表Di

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

（2）交换的消息

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

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省

云南省