陈军健 徐海川 鄢楚平
华北计算技术研究所通信工程研究室
摘要 随着无线通信技术的发展和移动终端性能的提高，Ad hoc的应用越来越广泛。无线Ad hoc 是一种不依赖于任何基础设施，无中心自组织的多跳无线网络。本文从Ad hoc 网络的特点出发，在分析当前路由协议设计思想的基础上，对Ad hoc 的路由协议FSR进行了研究。
关键词 Ad hoc 多跳无线网 网络拓扑 路由更新 鱼眼域 FSR
1 前言
Ad hoc 网络是一种无中心自组织的多跳无线网络，它不以任何已有的固定设施为基础而能随时随地组建临时性的网络。由于这种方便性，并且随着无线通信技术的发展和移动终端性能的提高，特别是人们对个人通信日益增长的需求，使得移动ad hoc网络的应用范围正逐步扩大。在军用领域，它可以支持野外侦察联络、独立战斗群通信和舰队战斗群通信、无人侦察与情报传输等；在民用领域，它支持诸如移动会议、移动网络、个人局域网、灾难营救过程中的信息交换以及临时交互式通信组等。我们可以预测，这种技术在未来移动通信的领域中将起到非常重要的作用。
2 Ad hoc 网络的特点
Ad hoc 网络是一群终端为了完成一项任务而临时组建的一种网络。它不需任何已有的固定设施作为基础，随时随地进行组建，因而网络中的每个节点都是平等的，没有中心。从技术上讲，Ad hoc 网络是一种移动通信技术和计算机网络技术相结合的网络。一方面，它采用无线信道进行通信，而且用户终端都可以随意移动；另一方面，各节点的信息交换采用了计算机网络中的分组交换机制，因此Ad hoc中的各节点兼有主机和路由器两种功能。
Ad hoc除了是无中心、自组织平等式的网络外，它还有如下的特点：
（1）网络拓扑动态变化频繁。 Ad hoc 网络中，用户终端的移动性具有很大的随机性，它们可以随时移动，也可以随时开机和关机。再加上无线发射装置发送功率的变化、无线信道间的相互干扰以及地形等因素的影响，网络的拓扑结构可能随时发生变化，而且这种变化无法预先知晓。
（2）多跳的无线网。 网络中节点如果在相互辐射覆盖范围内，则它们可以通过无线信道直接进行通信；否则，它们必须借助中间节点的转发才能通信。在Ad hoc网络中，这种转发不是由专门的路由器完成的，而是由平等的普通节点完成的。
（3）传输带宽有限。Ad hoc 网络的通信手段是无线传输技术，而无线信道本身的带宽相对有限网络非常之有线，再加上无线信道中的信号的冲突、干扰、衰减等因素使得无线带宽非常宝贵。
（4）存在单向链路。在无线通信中，由于通信设备频率的强弱和地形环境因素的影响，使得单向链路常常存在。比如，车载台终端发送功率比手持终端大很多，所以有时手持终端可以收到来自车载台的信号而车载台却无法接受到手持终端的信号，即存在一条从车载终端到手持终端的单向信道。
Ad hoc 网络的多跳性使得借鉴固定网络的路由协议成为可能，但其网络拓扑动态变化、传输带宽有限、单向链路的存在使得固定网络的路由协议不能直接应用到无线Ad hoc 网络中。节点的移动使得网络拓扑不断变化，这样传统的固定网络路由协议很难及时地准确地反映网络的拓扑结构，而且为了维护网络拓扑所使用的控制信息不断地分发到网络中去，要占用大量的无线带宽。另外，传统网络协议在设计时没考虑或者要求不存在单向链路，但在无线Ad hoc 网络中，单向链路往往是存在的，因此Ad hoc 路由协议必须支持单向链路。
3 当前使用的路由思想
不管是无线网络还是有线网络，大部分路由协议是基于DBF（Di- stributed Bellman Ford）和LS（Link State）设计的。由于DBF具有分布式的特点，因此它简单而且计算效率较高，这是它的优势。但其路由收敛较慢，而且有形成环形路由的可能，因此不适合拓扑高度变化的Ad hoc 网络。虽然有些方案已解决了环形路由问题，但到目前为止还没有较好的方案能解决DBF收敛较慢这一问题。
正是由于DBF的这些问题，人们才找到一种全新的方案LS。在LS路由协议中，每个节点都维护着一个全局拓扑结构表，因而很容易避免环形路由。而且链路的任何变化都会立即触发链路更新，这样收敛到新的拓扑结构所需要的时间远远小于DBF。但是LS依靠泛洪去分发路由更新信息，可能会带来过多的带宽开销，特别是在链路变化频繁的无线Ad hoc 网络中，大量的更新信息会占用相当多的宝贵带宽。
第三种方案是最近提出的按需路由思想，该方法只有在需要路由时才去发现路由。按需路由都使用了query/reponse的方法去发现和维护路由，由于query使用的也是洪泛技术，因此在移动性较高的无线网络中这种方案的效率不高，而且路由发现延时较长根本不能满足适时应用的需要。
4 鱼眼状态路由协议FSR
“鱼眼”技术是Kleinrock和Stevens提出来的，这种技术可以用来减少表示图形图像的数据。鱼眼能清晰地捕捉焦点附近的像素，但清晰度随着离焦点的距离增大而降低。"鱼眼"技术在路由中用来维护精确的距离和路由质量信息，但也会随着距离的变大而逐渐不精确。
FSR（Fisheye State Routing）是一个先验式（表驱动的）的路由协议。它使用了鱼眼技术，在不同鱼眼域中的节点以不同的频率（这个频率是由节点距离决定的）只向邻居节点广播链路更新信息，这能够大大减少链路状态更新信息，从而降低了泛洪的开销。通过节点之间相互交换链路状态消息，每个FSR路由器都能获知网络全局的拓扑信息。根据这些最新的拓扑信息， FSR为每个目的节点计算最短路径。由于链路更新频率由距离决定，因此对于域内的节点路由都是精确的，而对于域外的节点，离目的节点越远，路由的精确度便越低，这是因为距离较近的更新较快，较远的更新较慢。但不会像按需路由那样需要花时间去寻找路由，因此能维持较低的延时。而且随着离目的节点越来越近，路由信息越来越精确，正好弥补了路由的不精确性。在移动网络中，逐渐精确的路由减小了节点移动对路由精确度的影响。
当链路崩溃时，FSR不会发出任何控制信息，而且也不包含在下一个更新信息中，而是简单地删除邻居列表和拓扑结构表中的信息，因此适合于拓扑高度变化的网络环境。目的序列号的使用不仅使得FSR能使用最新的链路状态信息去维护拓扑结构，而且还避免了环形路由的形成，因此较适合高移动性的无线网络。
4.1 鱼眼域
鱼眼域就是在一定跳数范围内的节点的集合。
4.2 FSR路由交换方案
FSR在功能上与链路状态路由相似，因为它们都要在每个节点处维护一个全局拓扑结构图。主要的区别是路由信息分发的方法。链路状态路由的更新消息要占用相当多的带宽，如果更新周期小的话可能要占用更多的带宽。为了减少更新信息的数量而不严重影响路由的精确度，FSR使用了鱼眼技术。拓扑结构表中距离最小的节点的记录，将被高频率地分发给邻居节点，而其他记录则用低频率分发出去。因此，相当多的链路信息在一个特殊的更新周期内不会分发出去，这样便减少了更新消息的数量。总之，通过对路由表中的不同记录使用不同的交换周期，路由更新开销将大大地减少。这种策略对于较近的节点能及时更新信息，但对于较远的节点会带来较大的反应时间。不过，随着数据包离目的节点越来越近，路由也变得越来越精确，这一事实正好是对较远节点路由不精确的弥补。随着网络规模的变大，为了保证低的控制开销，可将网路划分为多个域，并使用不同的更新频率来分发更新信息。
在链路状态协议中，当一个节点检测到拓扑发生变化时（或周期性地），便会产生链路状态包并洪泛到网络中。而在鱼眼状态路由中，链路状态包不会被洪泛，相反只会周期性地与本地的邻居进行交换。这种信息交换方案也被用于邻居发现，每一个节点在监听到邻居的广播消息后都会增加邻居或更新它的邻居列表，同时也会更新拓扑表。各节点是从邻居那里得到更新信息的，而信息的最新性是由目的序列号来维护的。这有点像目的序列距离矢量路由协议（DSDV，Destination-Sequenced Distance-Vector Routing）中的矢量交换，在目的序列距离矢量路由协议中，距离的更新是根据节点的时间戳或序列号来进行的。不过，在FSR中，被传播的是链路状态而不是距离矢量。更何况，在链路状态路由中，每个节点都保存着全局的拓扑结构表，并且最短路径也是根据这个表来计算的。
在无线环境中，两个节点间的无线链路可能会不断地断开连接。在这种情况下，链路状态路由协议也会不断地发布链路状态更新信息，这些信息会被洪泛到网络中从而导致过多的开销。鱼眼状态路由避免了这一问题，它是周期性地交换拓扑信息，而不是由事件来驱动的，这样大大地减少了控制信息的开销。在FSR中不是任何信息都会被分发出去的，它根据消息的分发能使邻居节点的拓扑表更新这一原则，来选择广播的消息中所包含的记录（注：不产生影响的记录不会被广播出去）。在节点密集的网络里，一个节点可能发现它所有的邻居对于另一节点有同样的更新信息，这时使用这一原则会减少很多不必要的信息分发。通过去掉这样的记录，使得只有有效的记录包含在链路状态更新消息中，可以减少更新消息的数量。
4.3 FSR协议的操作
4.3.1 信息的分发
每个节点都向它们的邻居广播最近的链路状态信息。FSR根据拓扑表中各记录中离节点的跳数来用不同的时间间隔分发信息。为了精确，较近节点对应的记录分发的频率比较远节点对应的的频率高。鱼眼域i的更新时间间隔是UpdateInterval_i。当更新鱼眼域i的拓扑信息时，FSR浏览拓扑表从而获得相应的节点。如果更新消息有效，而且这些节点与当前节点的距离在域i内，那么它们将被包含在更新消息中。如果当前节点包含在链路状态消息中，那么它的序号将加1。怎样获得域i链路状态消息的有效部分呢？如果对应于域i的一个记录的NeedToSend标记为真，那么它将被选择。这个消息发送之后，域i内所有记录的标记都被重新设置为假，而且先前的序列号都将被当前的序列号所代替。
4.3.2 信息的接收
当节点接收到链路状态更新信息后，它首先检查邻居列表。如果发送者是一个新的节点，那么将它插入到列表中，否则它会更新列表中发送者的时间戳。对于链路状态更新信息中的每条记录，应考虑以下几种情况：
（1）如果信息发送者是一个新的目的节点，便会产生一个新的拓扑记录，同时填充相应的信息。标志“NeedToSend”为真；
（2）否则，用最新的拓扑信息更新拓扑表。如果接受的信息的序列号比表中相应节点记录的序列号大，那么用接受的信息代替表中的记录。标志“NeedToSend”为真。
（3）对于不满足上述两点的目的来说，如果信息较当前节点的旧，即接受信息的序列号比本地记录的序列号小，那么接受的信息将被丢弃，节点拓扑表中的相应的记录将在下一个更新周期内被送出。标志“NeedToSend”为真。
不管怎样，一旦拓扑表有变化，路由表将被重新计算。
4.3.3 链路崩溃
在移动ad hoc 网络中，链路崩溃是经常发生的事情。每个节点都用软状态方法去探测链路是否崩溃，即如果在时间间隔NEIGHBOR_TIMEOUT之内，节点还没有从邻居那里接收到链路状态消息，那么它就认为该链路崩溃了。节点就会从邻居列表中删除这个邻居，同时也从拓扑表中删除它的链路状态记录。
FSR不依赖MAC的反馈，如果MAC能在链路崩溃时提供反馈，FSR将利用这些反馈去更新邻居表，同时提供更新的路由信息。这一操作和上面的相同。链路崩溃发现得越早越好。
4.3.4 路由表的计算
拓扑结构表的任何变化都会触发路由表的重新计算。路由计算是基于最新的拓扑表进行的，因此在计算之前要检查拓扑表以去掉旧的记录。为了在计算最短路径时同时生成下一跳表（NEXTi( )）和距离表（Di( )），FSR将缔杰斯特拉算法进行了一定的修改。
以节点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( )可能返回不同的值。
4.4 路由精确度的考虑
对于较远的节点，FSR了解的路由信息不太精确，这种不精确是受路由的更新间隔影响的。更新时间越长路由信息越不精确。然而，FSR的特点减小了这种不精确。在FSR中，路由错误用距离进行了加权，因此它对网络规模的敏感性大大地减少了。这样一来，收到的远处节点以低频率发出的更新信息不会在很大程度上影响路由的精确度。而且，随着离目的节点越来越近，路由信息越来越精确。在移动网络中，逐渐精确的路由减小了节点移动对路由精确度的影响。
增加域半径会提高路由的精确度，但是较大的半径会增加路由更新包，会带来更多的控制开销。
5 结束语
Ad hoc 网络具有不依赖任何固定设施、无中心、自组织、多跳性等特点，使得它的应用越来越广泛。也正是这些特点使得Ad hoc 网络技术，特别是路由技术面临着许多困难。FSR路由技术使用了鱼眼技术，以不同的周期分发不同鱼眼域的信息，使得链路更新信息大大地减少，节约了宝贵的无线带宽。另外，路由的不精确度用距离进行了加权，因此，对网络规模的敏感程度大大降低了，较适用于较大规模的网络。同时，逐渐精确的路由减少了移动性的影响，因此FSR技术也较适用于移动网络。
使用
参 考 文 献
[1] Robertazzi T G,Sarachik.Self-organizing communication network[j].IEEE Communmag,1986,24(1):28-33
[2] G. Pei, M. Gerla, and T.-W. Chen, "Fisheye State Routing:
A Routing Scheme for Ad Hoc Wireless Networks", Proceedings of ICC 2000, New Orleans, LA, Jun. 2000
[3] G. Pei, M. Gerla, and T.-W. Chen, "Fisheye State Routing in Mobile Ad Hoc Networks", Proceedings of Workshop on Wireless
Networks and Mobile Computing, Taipei, Taiwan, Apr. 2000.
[4] 赵志峰，郑少仁.ad hoc网络.中国数据通信，2002,4(9)：1-5
[5] 杨盘隆,郑少仁.Ad Hoc网络中的路由算法.军用通信技术，2001，22（3）：49-53
----《中国数据通信》
|
