FSR网络路由协议研究

恋々风

包剑 冀常鹏 李义杰

    辽宁工程技术大学 电子与信息工程系 阜新 123000

　　1 Ad hoc网络的特点

　　Ad hoc网络是一种新颖的移动计算机网络，它既可以作为一种独立的网络运行，也可以作为当前具有固定设施网络的一种补充形式。Ad hoc网络是一种无中心自组织的多跳无线网络，是一群终端为了完成一项任务而临时组建的一种网络。它不需任何已有的固定设施作为基础，可随时随地进行组建，并且随着无线通信技术的发展和移动终端性能的提高，特别是人们对个人通信日益增长的需求，使得移动Ad hoc网络的应用范围正逐步扩大。Ad hoc网络中的每个节点都是平等的，没有中心。从技术上讲，Ad hoc网络是一种移动通信技术和计算机网络技术相结合的网络。一方面，它采用无线信道进行通信，而且用户终端都可以随意移动；另一方面，各节点的信息交换采用了计算机网络中的分组交换机制，因此Ad hoc中的各节点兼有主机和路由器两种功能。

　　Ad hoc除了是无中心、自组织平等式的网络外，它还有如下的特点：

　　（1）网络拓扑动态变化频繁。Ad hoc网络中，用户终端的移动性具有很大的随机性，它们可以随时移动，也可以随时开机和关机。再加上无线发射装置发送功率的变化、无线信道间的相互干扰以及地形等因素的影响，网络的拓扑结构可能随时发生变化，而且这种变化无法预先知晓。

　　（2）多跳的无线网。网络中节点如果在相互辐射覆盖范围内，则它们可以通过无线信道直接进行通信；否则，它们必须借助中间节点的转发才能通信。在Ad hoc网络中，这种转发不是由专门的路由器完成的，而是由平等的普通节点完成的。

　　（3）传输带宽有限。Ad hoc网络的通信手段是无线传输技术，而无线信道本身的带宽相对有限网络非常之有线，再加上无线信道中的信号的冲突、干扰、衰减等因素使得无线带宽非常宝贵。

　　（4）存在单向链路。在无线通信中，由于通信设备频率的强弱和地形环境因素的影响，使得单向链路常常存在。比如，车载台终端发送功率比手持终端大很多，所以有时手持终端可以收到来自车载台的信号而车载台却无法接受到手持终端的信号，即存在一条从车载终端到手持终端的单向信道。

　　2 目前路由方案的问题

　　不管是无线网络还是有线网络，大部分路由协议是基于DBF（Distributed Bellman Ford）和LS（Link State）设计的。由于DBF具有分布式的特点，因此它简单而且计算效率较高，这是它的优势。但其路由收敛较慢，而且有形成环形路由的可能，因此不适合拓扑高度变化的Ad hoc网络。虽然有些方案已解决了环形路由问题，但是到目前为止还没有解决DBF收敛较慢这一难题。

　　由于DBF存在着这些问题，人们开始使用LS。在LS路由协议中，每个节点都维护着一个全局拓扑结构表，因而很容易避免环形路由。而且链路的任何变化都会马上触发链路更新，这样收敛到新的拓扑结构所需要的时间远远小于DBF。但是LS依靠泛洪去分发路由更新信息，可能会带来过多的带宽开销，特别是在链路变化频繁的无线Ad hoc网络中，大量的更新信息会占用相当多的宝贵带宽。

　　第三种方案是按需路由思想，该方法只有在需要路由时才去发现路由。按需路由都使用了query/response的方法去发现和维护路由，由于query使用的也是洪泛技术，因此在移动性较高的无线网络中这种方案的效率不高，而且路由发现时延较大，根本不能满足实时通信的需要。

　　3 鱼眼状态路由协议FSR

　　“鱼眼”技术是Klein rock和Stevens提出来的，这种技术可以用来减少表示图形图像的数据。鱼眼能清晰地捕捉焦点附近的像素，但清晰度随着离焦点的距离增大而降低。“鱼眼”技术在路由中用来维护精确的距离和路由质量信息，但也会随着距离的变大而逐渐不精确。鱼眼域就是在一定跳数范围内的节点的集合。FSR（Fisheye State Routing）是一个先验式（表驱动的）的路由协议。它使用了鱼眼技术，在不同鱼眼域中的节点以不同的频率（由节点距离决定的）只向邻居节点广播链路更新信息，这能够减少链路状态更新信息，从而降低了泛洪的开销。通过节点之间相互交换链路状态消息，每个FSR路由器都能获知全网的拓扑信息。根据这些最新的信息，FSR为每个目的节点计算最短路径。由于链路更新频率由距离决定，因此对于域内的节点路由都是精确的，而对于域外的节点，离目的节点越远，路由的精确度便越低，这是因为距离较近的更新较快，较远的更新较慢。但不会像按需路由那样需要花时间去寻找路由，因此能维持较低的时延。而且随着离目的节点越来越近，路由信息越来越精确，正好弥补了路由的不精确性。在移动网络中，逐渐精确的路由减小了节点移动对路由精确度的影响。

　　当链路崩溃时，FSR不会发出任何控制信息，而且也不包含在下一个更新信息中，而是简单删除邻居列表和拓扑结构表中的信息，因此适合于拓扑高度变化的网络环境。目的序列号的使用不仅使得FSR能使用最新的链路状态信息去维护拓扑结构，而且还避免了环形路由的形成，因此较适合高移动性的无线网络。

　　4 FSR路由交换方案

　　FSR在功能上与链路状态路由相似，因为它们都要在每个节点处维护一个全局拓扑结构图。主要的区别是路由信息分发的方法。链路状态路由的更新消息要占用相当多的带宽，如果更新周期小的话可能要占用更多的带宽。为了减少更新信息的数量而不严重影响路由的精确度，FSR使用了鱼眼技术。拓扑结构表中距离最小的节点的记录，将被高频率地分发给邻居节点，而其他记录则用低频率分发出去。因此，相当多的链路信息在一个特殊的更新周期内不会分发出去，这样便减少了更新消息的数量。总之，通过对路由表中的不同记录使用不同的交换周期，路由更新开销将地减少。这种策略对于较近的节点能及时更新信息，但对于较远的节点会带来较大的反应时间。不过，随着数据包离目的节点越来越近，路由也变得越来越精确，这正好是对较远节点路由不精确的弥补。随着网络规模的变大，为了保证低的控制开销，可将网路划分为多个域，并使用不同的更新频率来分发更新信息。

　　在链路状态协议中，当一个节点检测到拓扑发生变化时（如两个节点间的无线链路可能会不断地断开连接），便会产生链路状态更新信息包并洪泛到网络中，从而导致过多的开销。而在鱼眼状态路由中，链路状态包不会被洪泛，相反只会周期性地与本地的邻居进行交换。而不是由事件来驱动的，这样地减少了控制信息的开销。这种信息交换方案也被用于邻居发现，每一个节点在监听到邻居的广播消息后都会增加邻居或更新它的邻居列表，同时也会更新拓扑表。各节点是从邻居那里得到更新信息的，而信息的最新性是由目的序列号来维护的。在FSR中，被传播的是链路状态而不是距离矢量。在节点密集的网络里，一个节点可能发现它所有的邻居对于另一节点有同样的更新信息，这时使用这一原则会减少很多不必要的信息分发。通过去掉这样的记录，使得有效的记录包含在链路状态更新消息中，可以减少更新消息的数量。

　　5 FSR协议的操作

　　5.1 信息的分发

　　每个节点都向它们的邻居广播最近的链路状态信息。FSR根据拓扑表中各记录中离节点的跳数来用不同的时间间隔分发信息。为了精确，较近节点对应的记录分发的频率比较远节点对应的频率高。鱼眼域i的更新时间间隔是Update Interval_i。当更新鱼眼域i的拓扑信息时，FSR浏览拓扑表从而获得相应的节点。如果更新消息有效，而且这些节点与当前节点的距离在域i内，那么它们将被包含在更新消息中。如果当前节点包含在链路状态消息中，那么它的序号将加1。对应于域i的一个记录的Need To Send标记为真，那么它将被选择。这个消息发送之后，域i内所有记录的标记都被重新设置为假，而且先前的序列号都将被当前的序列号所代替。

　　5.2 信息的接收

　　当节点接收到链路状态更新信息后，它首先检查邻居列表。如果发送者是一个新节点，那么将它插入到列表中，否则更新列表中发送者的时间戳。对于链路状态更新信息中的每条记录，应考虑以下几种情况：

　　（1）如果信息发送者是一个新的目的节点，便会产生一个新的拓扑记录，同时填充相应的信息。标志“Need To Send”为真；

　　（2）否则，用最新的拓扑信息更新拓扑表。如果接受的信息的序列号比表中相应节点记录的序列号大，那么用接受的信息代替表中的记录。标志“Need To Send”为真。

　　（3）对于不满足上述两点的目的来说，如果接受信息的序列号比本地记录的序列号小，那么接受的信息将被丢弃，节点拓扑表中的相应的记录将在下一个更新周期内被送出。标志“Need To Send”为真。

　　不管怎样，一旦拓扑表有变化，路由表将被重新计算。

　　5.3 链路崩溃

　　在移动Ad hoc网络中，链路崩溃是经常发生的事情。每个节点都用软状态方法去探测链路是否崩溃，即如果在时间间隔NEIGHBOR_TIMEOUT之内，节点还没有从邻居那里接收到链路状态消息，那么它就认为该链路崩溃了。节点就会从邻居列表中删除这个邻居，同时也从拓扑表中删除它的链路状态记录。

　　FSR不依赖MAC的反馈，如果MAC能在链路崩溃时提供反馈，FSR将利用这些反馈去更新邻居表，同时提供更新的路由信息。这一操作和上面的相同。链路崩溃发现得越早越好。

　　5.4 路由表的计算

　　拓扑结构表的任何变化都会触发路由表的重新计算。路由计算是基于最新的拓扑表进行的，因此在计算之前要检查拓扑表以去掉旧的记录。为了在计算最短路径时同时生成下一跳表NEXTi（）和距离表Di（），FSR将Dijstra算法进行了一定的修改。

　　以节点i为例。FindSP（i）将集合P初始化为（i），其中集合p表示已找到最短路径的终点集，距离集Di（i）初始化为{0}，对于其他节点x初始化相应的值Di（x）= weight（i，x）。然后进行迭代，直到P与所有的节点集相等为止。在每一次迭代中，算法都会从集合V-P中寻找一个节点j，使得Di（k）+ weight（k，j）的值最小，其中k是集合P中的一个节点。一旦找到节点j，那么j就被合并到集合P中，Di（j）的值被赋为Di（k）+ weight（k,j），NEXTi（j）的值被赋为NEXTi（k），从中可知，从节点i到j的最短路径不得不经过节点k，因此从节点i到j和从节点i到k的最短路径的后继者相同，即从节点i到目的节点k或j的路由中，对节点i来说有相同的下一跳。

　　 权值函数weight（）被用作计算链路的距离。在FSR中由于用跳数来度量距离，因此，当两节点直接相连时就简单返回值1，当不相连时就返回0。由于度量值不一样，函数weight（）可能返回不同的值。

　　6 路由精确度的考虑

　　对于较远的节点，FSR了解的路由信息不太精确，这种不精确是受路由的更新间隔影响的。更新时间越长路由信息越不精确。然而，FSR的特点减小了这种不精确。在FSR中，路由错误用距离进行了加权，因此它对网络规模的敏感性地减少了。这样一来，收到的远处节点以低频率发出的更新信息不会在很大程度上影响路由的精确度。而且，随着离目的节点越来越近，路由信息越来越精确。在移动网络中，逐渐精确的路由减小了节点移动对路由精确度的影响。

　　增加域半径会提高路由的精确度，但是较大的半径会增加路由更新包，会带来更多的控制开销。FSR路由技术使用了鱼眼技术，以不同的周期分发不同鱼眼域的信息，使得链路更新信息地减少，节约了宝贵的无线带宽。另外，路由的不精确度用距离进行了加权，因此，对网络规模的敏感程度降低了，较适用于较大规模的网络。同时，逐渐精确的路由减少了移动性的影响，因此FSR技术也较适用于移动网络使用。

信息来源：《中国数据通信》