短波自组网网络层协议研究（－）
摘要自组网是一种不依赖于固定基础设施，能快速、简单组网的临时自治系统，适宜于军事行动、抢险救灾等特点场合的应用。在组网的物理信道方面，短波通信则因其具有的良好抗毁性而成为军事远距离通信的重要手段。短波和自组网技术的结合就产生了短波自组网。短波自组网是以短波信道作为物理介质的自组网。网络层协议是短波自组网组网技术的核心，其主要研究内容为路由协议、网络层地址标识、网络层内部各模块的交互以及网络层与数据链路层和上层的接口。
自组网的路由协议可依表驱动或按需驱动而触发，按需驱动路由协议的网络开销较小，但是寻径延迟较表驱动大。由于短波信道具有带宽低、信道质量差的缺点，这势必要求其路由协议消耗尽可能低的网络开销并以链路质量为选径标准。由于短波自组网主要用于非实时业务，能容忍较长的路由发现延迟，故按需驱动路由算法更适应于短波组网。本文在分析第三代短波通信网美军标路由协议的基础上，提出了以链路质量为寻径标准的按需驱动路由协议HFRR，该协议还在路由发现和路由维护的开销方面进行了尽力缩减。短波通信网除可以采用自适应路由协议外，还可以采用人工源路由、静态路由，在一定的网络规模和拓朴下应合理选择这些路由协议，并非自适应路由协议为最佳。
第三代短波通信网美军标以ASCII字符串作为网络层地址，在海军某预研项目中，本文对其进行了改进，增加了应用层和网络层间的地址转换。整个协议栈中进行了两次地址转换，分别发生在应用层－网络层和网络层－数据链路层之间。
短波通信网当前的最重要应用为HF email，HF email协议应依据短波通信网网络层和数据链路层协议的特点对传统的POP3和SMTP等协议进行必要的改进，在HF email协议中，对命令采用了批处理方式，改“一问一答”为“多问多答”。高频网络管理协议在短波通信网中作用巨大，也需对SNMP协议针对短波特点进行必要的改进。
本文还对上述协议在海军某预研项目中的实现进行了探讨。
关键字：短波 自组网 路由 高频电子邮件 高频网络管理
AbstractMobile ad hoc network (MANET) is a multi-hop temporary autonomous system of mobile nodes with wireless transmitters and receivers without the aid of pre-established network infrastructure. Because of good performance in resisting-destroy, short wave communication becomes important means of long-range communication in military. The combination of short wave communication and MANET technology has produced HF MANET. HF MANET is a kind of MANET that uses short wave channel as the physics medium. Network layer protocols are the core of HF MANET to become a network.
On-demand driven routing is a kind of special routing for MANET. It needs less overhead, but delays more long than table-driven routing because it searches routing only when source node wants to send information to destination node. The characteristic of the short-wave channel is that the bandwidth is low and channel quality is poor. So, routing protocols in HF MANET require the low expenses, and they should choose the routing according to link quality. HF MANET is used in the transmission of the business of none real-time data mainly. It can tolerance the delay of routing discovery of On-demand driven routing. So on-demand driven routing protocol adapts to HF MANET even more than table driven protocol. According to the designing requirement of HF MANET routing protocol, this paper proposes HFRR routing protocol. This protocol is a kind of On-demand driven routing, and it uses link quality as the basis to select routing. HFRR does the best to reduce the expenses of the routing discovery and maintaining. For a HF network, adaptive routing is not the only kind of routing which can be adopted, other routing like source routing, static routing maybe can work better. We should select routing according to the scale of the special network. Adaptive routing is not always the best routing.
US Military Standard of The third generation HF networks use ASCII string as network layer address. This paper amends it, and add a new address transition in a navy preparation research project. There are two times of address transition in the whole protocol stack. One happens between application layer and network layer, another happens between network layer and data link layer.
HF email is the most important application in HF commutation networks. The POP3 and SMTP protocol must be improved to adapt the characteristic of data link layer and network layer of HF networks. Batch process of commands is used to keep down network overhead of email transmission. The model of “one question with one answer” is changed to “multi-questions with multi-answers ”.HF network management also plays a important role in HF network. The SNMP protocol is modified to HNMP which expends less overwork on network management.
On the side, this paper discusses on fulfill technology of these protocols in a navy preparation project.
Key words: mobile ad-hoc networks, HF, routing, HF email, HF network management
1 绪论
1.1研究背景在现代化战场上,各种军事车辆、舰船、战斗机及其它各种武器设备、战士之间都需要保持密切的联系, 以完成集中统一指挥, 协调作战。这样的通信网络需要具备能临时搭建、不依赖基础设施的特点。另外，在发生地震、水灾后的营救等应用场合也不可能预先铺设网络设施，要求能临时快速组网，节点可以任意移动。
正是基于这样的需求，20 世纪70年代，美国国防部高级研究计划局（DARPA） 资助研究了战地无线分组数据网（PRNET）[1]项目。后来，DARPA又于1983 年和1994年分别资助进行了抗毁自适应网络（Survivable Adaptive Network，SURAN）[2]和全球移动信息系统（Global Information Systems，GloMo）[3]两个项目的研究，以便能够建立某些特殊环境或紧急情况下的无线通信网络。自组网（mobile ad hoc networks）正是吸取了PRNET、SURAN 以及GloMo等项目的组网思想，而产生的一种新型的网络结构。
自组网是一种由一些带有无线收发装置的移动节点组成的无需依赖任何基础设施的多跳的临时自治系统。不同于有中心的集中式控制的蜂窝移动通信系统，自组网中各节点相互作为其邻居节点的路由器，通过节点转发实现节点间通信。
短波通信目标小，不易被摧毁，即使遭受破坏也容易修复。在战争状态下，短波通信的安全可靠度要高于卫星等其它通信手段。鉴于这一点，短波通信在军事通信中获得了广泛的应用。使用短波信道作为物理层传输介质的自组网即为短波自组网。短波自组网的研究不仅具有重要的社会和经济意义, 也具有十分重要的战略意义。
相对于ISM（Industrial,Scientific,Medical）频段的无线信道而言，短波信道的传输带宽很低，链路质量也很差。因此作为短波组网核心技术的网络层路由等协议的设计就面临着更多的难题。
1.2国内外研究概况1.2.1自组网网络层协议研究现状1999年1月Internet工程工作组（IETF） RFC2501[4]详细给出了移动自组网的应用场景、特征和性能要求。目前，IEEE 802.11[5]，Bluetooth[6]等标准均支持ad hoc方式。IETF成立了MANET 工作组,负责ad hoc相关协议的标准化工作。MANET 工作组早期集中从事自组网单播路由协议及其性能评定的研究，现已发布了一些路由草案。这些路由协议的提出一方面继承了有线网络路由协议，仍然依据表驱动的思想，依赖周期性的心跳进行路由更新和维护；另一方面针对自组网的特性提出了许多新的观点，其中最重要的发展即为按需驱动路由协议的思想，它只在源节点需要传输报文给目标节点时才启动到达目标节点的路由发现过程。
根据网络的拓朴结构的不同，现有两类路由协议被提出，一是完全基于平面结构的路由，二是基于层次结构的路由。
国内许多专家学者也纷纷提出新的路由协议和改进的路由协议，在支持单向路径[7]、支持QoS（服务质量）路由协议[8]、路由负载平衡[9]、路由节能[10]、路由协议安全性[11]等方面展开了研究并发表了相关学术论文。
在自组网网络层协议的仿真方面，NS-2仿真软件[12-13]整合了多数路由协议。它由LNBL(Lawrence Berkeley National Laboratory)网络研究组于1989年开始研究，它是一种可扩展的、容易配置的和可编程的事件驱动网络仿真引擎。
1.2.2外军短波组网研究现状
美国、澳大利亚、北约等国家和组织启动了多个短波自组网项目，其中包括：
美军高频特混编队内通信网络(high frequency intra-task force，HFITF)[14]，其目的是为海军特遣舰队提供超视距话音和数据通信。 HFITF 网络主要依靠地波传播信息，其网络中的节点（舰只、飞机或潜艇）可分布在一直径为300英里的海域内，并实现相互之间的通信。该网络采用分簇结构，网络中的所有节点可以3种形式之一存在：簇头节点、网关节点和普通节点，节点形式的确定是用完全分布式算法实现的。簇头作为该簇中所有节点的控制中心，网关节点则作为簇与簇之间通信的中继站，簇头、网关节点以及它们之间的通信链路构成骨干网，使整个网络连为一体。
美军HF舰/岸网络(HFSS)[15]是无线岸/船通信网络，网络采用集中网控构造，由岸站和水面大量舰船节点组成，依靠天波传输。HFSS由岸站充当中心节点，所有网络业务都需通过中心节点，并不是严格意义上的自组网。
增强型HF数字网络（IHFDN）[16]则综合HFITF和HFSS网络的优点，混合适用天波和地波组成一个更大规模的HF网络。
美军近期数字电台（near term digital radio）[17]采用了双频分级结构，每个用户群（簇）都有一部高速数字电台设备充当簇头，簇成员与簇头一跳可达。簇头之间形成骨干网，采用OSPF路由协议。簇头负责维护本簇的拓扑，本簇的拓扑信息不向外传播。簇头节点有两个频率，频率1用于簇头与簇成员的通信，而频率2用于簇头之间的通信。
澳大利亚的LONGFISH型高频网络[18]的网络结构类似于GSM，采用多星状拓朴。网络由分布于澳大利亚本土上的四个基站和多个分布在岛屿、舰艇上的移动站组成，基站之间以光缆或卫星链路相连。
北约也在大力发展包括HF网络在内的无线通信系统，如应用在预警机系统上的加密通信终端、超视距的短波互连网网关、海上网关和STANAG-5066[19]等短波研究项目。在STANAG－5066中定义了短波子网络的构造，提出了与电子邮件、文件传输等协议的接口，强调了互操作性。
另外，国外的一些商业机构也开展了短波组网技术的研究。如美国加州全球无线公司的海上数据网络（marine data network）,在全球设置了多个中继站，通过短波24小时为全球的舰船提供新闻、气象等广播服务，同时提供岸舰之间的电子邮件和文件传输数据通信服务。Collins 公司开发了一种名为 HF MESSENGER 的数据通信产品，其提供一种服务器，帮助用户使用短波调解器和电台传送各种数据，并控制 HF网络中各种设备，将 HF 链路连接到个人计算机网络中。
美国军方从多个实验项目中逐渐总结经验，到目前为止，美国军方的HF全自动短波网络已经走过了第一代和第二代，在这个时期美国军方出台的相应军标主要有MIL-STD-188-141A[20]、MIL-STD-188-110A[21]、MIL-STD-187-721C[22]等；目前美国军方正在建设性能更加优良的第三代HF全自动短波网络，出台的相应的美国军标有MIL-STD-188-141B[23]、MIL- STD- 188-110B[24]、MIL-STD-187-721D[25]等。
1.2.3我军短波组网研究现状
我军于1994年参照美军标MIL-STD-188-141A制定了GJB 2077-94标准[26]，对短波自适应通信系统自动链路建立进行了标准规范。该标准所规定的HF自适应系统可以保证可靠的链路建立以及自适应链路建立（ALE）技术的互操作性。GJB 2077-94标准的制定与执行，使我军短波自适应通信有了依据，取得了良好的军事经济效益。
然而，HF网络应用的增加使人们对HF自适应技术提出了更高的要求，这些要求包括：数据链路层更快的建链速度、更高的信道利用率；网络层更灵活的路由协议，对上层更多应用的支持以及与Internet和其它网络的互连等。这势必要求我国在该领域进行更深入的研究，并出台相应的新标准。
1.3本文的主要工作及结构安排短波自组网网络层协议研究的主要工作为网络拓朴结构及对应路由协议的研究、网络层内部各模块交互的研究以及其与数据链路层和上层协议接口的研究。
当前，有大量的自组网路由协议被提出，本文对其进行了分类研究，比较了各类路由协议的特点和性能，并根据短波信道的特性和短波自组网的应用需求，分析得出了适合于短波组网的路由协议类型。在分析适合短波组网协议类型的基础上，本文详细阐明了第三代短波通信网网络层协议，探讨了不同规模、不同拓朴结构的短波网络所需的路由协议，并由此给出了短波自组网路由协议的设计要求。本文按照短波组网路由协议的设计要求提出了一种新的按需驱动路由协议HFRR(HF Reactive Routing)，并以Petri网模型[27-28]对之进行了验证，分析了其适用范围。运行于HF网络之上的HF email基高频网络管理协议均需针对HF信道的特点、HF MAC协议和路由协议的特点对传统协议标准进行改进，本文也对这些问题进行了探讨。
在海军某预研项目中，实践了以上协议，本文对协议实现过程中的重要问题进行了阐述。最后，本文给出了关于未来我国大规模短波通信网网络拓朴的设计构想。
本文第1章介绍短波自组网的研究背景和国内外研究现状；
第2章对自组网的路由协议进行了详尽地分类比较和分析；
第3章分析了短波信道的特点和短波网络的应用需求，由此分析得出短波组网路由协议的设计要求。对美第三代短波通信网军标短波组网网络层协议进行了阐述和分析，并阐明了不同类型短波组网路由协议所适用的短波网络规模；
第4章提出了一种新的按需驱动短波自组网路由协议——HFRR，对其进行了阐述，采用Petri网模型对其进行了验证分析，并给出了其适用范围。
第5章阐明了短波组网协议在海上高频无线分组网中的应用，海上高频无线分组数据传输网项目的网络层设计概况及本文对未来我国大规模短波网络的架构构想。
2 自组网路由协议与单跳的无线网络不同，自组网节点之间需通过多跳数据转发机制进行数据交换，每个节点都可能充当其它节点的路由器。无线信道质量的不规则变化，节点的移动、加入和退出等均会引起网络拓扑结构的动态变化。自组网路由协议的作用就是在这种环境中，监控网络拓扑结构的变更，交换路由信息，定位目的节点位置，产生、维护和选择路由，提供网络的连通性。路由协议是移动节点互相通信的基础。
常规的路由协议，如路由信息协议（RIP）[29]和开放式最短路径互连（OSPF）[30]是为有线网络而设计的，它们的拓扑结构相对固定，不会出现大的网络结构变化。自组网结构则是动态变化的，若仍使用常规路由协议，则将会在路由发现和维护上付出很大的代价，而全网路由也可能始终处于不收敛状态。除此之外，自组网不能采用常规路由协议还包含如下几种方面的原因：
（1） 自组网中主机间的无线信道可能是单向的；
（2） 若仍使用常规路由，则无线信道的广播特性将产生许多冗余链路；
（3） 常规路由协议路由信息的周期性广播更新报文会消耗大量的网络带宽。由于无线信道本身的物理特性，它所能提供的网络带宽相对有线信道要低得多。此外，考虑到竞争共享无线信道产生的碰撞、信号衰减、噪音干扰、信道间干扰等多种因素，节点可得到的实际带宽是远远小于理论上的最大带宽值；
（4） 无线移动终端的局限性。移动终端在带来移动性、灵巧、轻便等好处的同时，其固有的特性，例如采用电池一类可耗尽能源提供电源，内存较小，CPU性能较低等要求路由算法简单有效，实现的程序代码短小精悍，需要考虑如何节省能源等。而常规路由协议通常基于高性能路由器作为运行的硬件平台，没有上述的限制。
由于自组网路由协议对自组网的重要性，它便成了研究的一个热点。到目前为止，已经有相当多的标准和草案推出。当前提出的自组网路由协议可依两种标准进行分类，一是以触发时机进行分类，一是以网络拓扑结构进行分类。
2.1依据触发时机分类根据路由触发原理，目前的路由协议可分为三类：
1）基于路由表驱动（Table Driven）的路由协议
2）按需驱动（On-Demand Driven）的路由协议
3）表驱动和按需驱动的混合
2.1.1表驱动路由表驱动路由（又称先验路由、主动路由）继承了传统的路由算法，但在消除路由环路和已过时路由等方面进行了适应于自组网特性的改进。传统有线网络的经典路由算法包括链路状态协议和距离矢量两种。链路状态协议中每个节点都要保存整个网络的拓扑信息以及每条链路的开销，为了使所有节点中保存的路由保持一致，每个节点必须周期性地广播其与周围邻居节点的路由信息，其它节点在收到这些信息时更新网络拓扑，以最短路径算法来计算到达目的节点的下一跳节点。然而，某些节点保存的路由可能因为传播的延迟等原因与实际网络中的状态不一致，这时就可能会在网络中生成路由环路。距离矢量算法也会导致路由环路的生成。路由环路问题在无线环境下表现地更为明显，所以继承传统路由协议的表驱动路由协议需在此方面进行了改进。
表驱动路由协议中无论路由是否被用到，每个节点都要进行周期性地路由信息交换以维护路由表。表驱动路由协议的优点是在有信息传送时不需要等待建立路由，源节点一旦要发送报文，可以立即获得到达目的节点的路由。而其在无需通信节点之间的路由维护则浪费了大量的网络带宽。常见的表驱动路由协议有DSDV[31]，HSR[32]，GSR[33]，WRP[34]，FSR[35]等。
DSDV（Destination-Sequenced Distance-Vector Routing）协议通过修改RIP协议而得到，它基于Bellman-Ford算法。DSDV在每条路由信息中加人由目的节点产生的序列号，以避免路由环。
在DSDV协议中，每个节点周期性地广播它当前的路由表（路由信息包括对应于每个目的节点的距离及最大序列号，还包含发送者自身的序列号，每广播一次就自动加1）。每个收到该广播报文的节点将报文中的对应各目的节点的序列号与自身路由表中相应表项比较，如果报文中的序列号较高，则更新自己的路由表，将发送者指定为下一跳，并将距离增加一跳。在序列号相等但是报文中路由距离更小的情况下，节点也要更新自己的路由表。
当一个节点发现链路失效时，它将所有通过该节点转发的路由的距离设为无穷并将其序列号加1。由于更新了序列号，因此这一消息会传播到整个网络。这样所有这些目的路由指向的目的节点都有效地与此节点断开，直到有新的序列号产生并包含新的路由信息。
HSR(Hierarchical State Routing)是一种用于分级网络的路由协议，高级节点保存它所有子孙节点的位置信息，沿从最高级的根节点到最低级的叶节点的路径为节点分配逻辑序列地址，可以用序列地址进行节点寻址。
GSR(Global State Routing)协议的工作原理与DSDV协议类似，在该算法中，每个节点维护邻居列表、拓扑表、下一跳节点表和距离表。邻居列表记录所有能侦听到该节点信息的节点列表。对于每个目标节点，拓扑表记录链路状态信息和该信息的时间戳（timestamp），下一跳节点表记录分组转发的下一跳节点，而距离表则记录到达目的节点的最短路径。当链路的状态发生变化时，通过比较报文与本地拓扑表中的目的节点路由序列号大小，决定网络拓扑表的修改，若拓扑表发生变化则广播给其它节点。
GSR协议中，较长的路由修改报文会浪费相当大的网络带宽，针对这一缺陷，FSR(Fisheye State Routing)对GSR进行了修改，FSR的路由信息报文中并不包含所有节点的信息，因此可大大缩短报文的大小。与中心节点的距离越近，信息交换越频繁，每个节点都可获得其邻近节点准确详尽的信息；而随着与中心节点距离的加大，交换频率开始减小，超过节点的鱼眼范围时，信息的准确性降低，但并不影响路由的正确选择。通过这种算法，可大大降低路由修改信息对网络的负荷。这种算法的拓扑组织结构像鱼的眼睛（如图2.1）,所以称之为FSR。
图2.1 Fisheye State Routing
WRP(Wireless Routing Protocol) 是一种距离向量路由算法,每个节点维护距离表、路由表、链路开销表和信息重传列表。信息重传节点列表记录信息更新报文中需要传送的信息序列以及需要对该信息更新报文作出确认的节点列表。节点周期性或者在链路状态改变的情况下交换路由表，信息更新报文中反馈节点列表中的节点需要确认其接收。如果从上次广播更新报文后节点没有新的路由信息需广播，则其需发送HELLO报文，以确认节点之间的连通性。如果节点没有发送HELLO信息,则认为节点的链路信息无效。当节点收到来自邻居节点的信息更新报文后,修改自身的距离表依据该报文寻找更好的路由。如果某个移动节点收到了新节点的HELLO信息,则把新节点信息填入路由表,并且把它自己的路由表发给新节点。
2.1.2按需驱动路由与表驱动路由相反，源始发的按需驱动路由（又称反应路由）认为在动态变化的自组网环境中，没有必要维护去往其它所有节点的路由。按需驱动路由因其更适合自组网特性，近些年来更被关注。按需路由一般分为路由建立和路由维护两个过程。它仅在需要给目的节点发送报文而又没有去往目的节点路由的时候才按需进行路由发现。因此，路由表是按需建立的，它可能仅仅是整个拓扑结构信息的一部分。它的优点是不需要周期性的路由信息广播，节省了一定的网络资源。缺点是发送数据分组时，如果没有去往目的节点的路由，数据分组需要等待因路由发现引起的延时，不适合于实时性要求高的应用。
常用的按需驱动路由协议有DSR[36]，AODV[37]，TORA[38]，LAR[39]等。
DSR(Dynamic Source Routing)协议是最早被提出的按需驱动路由协议。DSR的路由发现过程如图2.2所示，当源节点没有到达目的节点的路由时，它广播一个路由请求报文。每个收到该报文的中间节点附上自身的ID然后重新广播。当路由请求到达目的节点(或者某个知道某条到达目的节点的路由的中间节点)时，它就可以决定一条到达目的节点的完整的源路由。目的节点(或中间节点)将所得的源路由包含在路由响应报文中，然后沿着所得路由反向发送回源节点，也可以附带在目的节点的路由请求报文中。源节点收到路由响应报文后，它将源路由存人缓存，并置入每个数据报的报头。中间节点根据数据报头中的路由信息中转数据报文。
图2.2 DSR的路由发现过程
路由维护过程也需要使用缓存信息。如果数据报在逐跳传输过程中发现链路失败，则可以由中间节点用缓存中的可用路由来代替报头中含有失效链路的路由，同时向源节点发送一个路由错误报文。和其它路由控制报文一样，路由错误报文可以被中间节点监听到，并且根据它将中间节点中的失效路由删除掉。这样可以使缓存中的错误路由信息的影响最小。如果路由失效，源节点则重新开始一个新的路由发现过程。
AODV（Ad hoc On demand Distance Vector Routing）协议是在DSDV协议的基础上结合类似DSR中按需驱动的思想而提出的。它与DSR协议的不同之处在于报头并不携带路由信息，中继节点依据自身的路由表逐跳转发。因为在AODV协议中，各节点隐式地将路由请求和路由应答分组中的路由信息保存于自身的路由表中，而DSR却将完整地路由信息显示地保存在分组中。AODV基于双向路径的假设，不支持单向路径。
TORA（temporarily-ordered routing algorithm）协议是在有向无环图DAG（directed acyclic graphic）算法的基础上提出的一种按需驱动路由协议。它分为路由发现，路由维护，路由消除三个过程。TORA协议与其它按需驱动路由协议一样，首先在网中发送路由请求分组，但是在路由应答部分，则采用了DAG算法。其主要思想是：对于某一目标节点，网络中每个节点都保留了相对于它的“势能”。势能可以通过从目标节点的反向广播来获得。离目标节点越远的节点，势能越高，目标节点势能最低。在数据传播过程中，数据包会从高势能的节点向低势能的节点转发，最终流向目标节点。当局部链路发生变化时，只需要局部势能的调整，这种改变一般不会影响到全局。TORA协议的主要特点是控制报文定位在最靠近拓扑变化的一小部分节点处，因此节点只保留邻近点的路由信息。该算法中路由不一定是最优的，常常使用次优路由以减少发现路由的开销。
LAR（location aided routing）协议是一种依据节点物理位置信息而获得路由信息的算法。LAR协议从GPS获得位置信息，且每个节点需知道其它节点的平均运动速度。在路由请求分组中携带寻径范围信息，寻径范围依据位置信息和节点平均运动速度而得到。这样，只有在寻径范围内的节点才转发路由请求分组。当源节点在当前寻径范围内寻径失败时，它将扩大寻径范围。LAR协议的优点是在小范围内寻径，减少了寻径开销；缺点是依赖GPS提供的位置信息，限制了其应用范围。
2.1.3混合式路由协议Ad hoc无线网络中单纯采用表驱动或按需驱动路由协议都不能完全解决路由问题，因此，许多学者提出了结合表驱动和按需驱动路由协议优点的混合式路由协议。
ZRP（zero routing protocol）协议[40]是一个表驱动和按需驱动路由协议的组合，网络内的所有节点都有一个以自己为中心的虚拟区。在区内使用表驱动路由算法，中心节点使用区内路由协议IARP（Intra-zone Routing protocol）维持一个到区内其它成员的路由表，对区外节点的路由使用按需路由，利用区间路由协议IERP(Inter-zone Routing protocol)建立临时的路由。
混合式路由协议在小范围局部区域内使用表驱动路由协议，局部区域间则采用按需路由协议。这样可将表驱动路由协议的周期性广播限定在一个局部区域内，从而减轻由全网广播带来的路由负荷。混合路由协议实现了按需路由协议和表驱动路由协议强弱互补，具有相对低的带宽消耗和路由发现延迟。
2.1.4性能比较衡量路由协议好坏的两个重要指标是路由发现延迟和路由开销[4,41]。路由延迟是指源节点获取一个新的到达目的节点的路由所需的时间。平均路由发现延迟最小的是表驱动路由协议，其次是混合型路由协议，按需路由协议最长。
文献[42]对比了DSDV、AODV、TORA、DSR四种路由协议的性能，图2.3给出了该文仿真所得的路由开销对比。显然，在网络拓朴变更的情况下，表驱动的DSDV协议的路由开销是基本不变的。在拓朴变更不明显的情况下（pause time较大），按需驱动的DSR、AODV、TORA协议的路由开销远小于表驱动的DSDV协议。实际上，自组网总是要工作在拓朴变更较慢的情况下。因为，当拓扑结构变化快到一定程度时，任何基于路由协议的数据包转发已经成为不可能，泛洪(flooding)方式成为数据包传输的唯一选择，而泛洪将会耗费大量的网络带宽。
图2.3 路由协议网络开销比较
表驱动路由协议的负荷随着节点运动的加快虽基本保持不变，但在拓朴变更加快的情况下，无法及时收敛，从而造成大量的不可靠路由和路由环，引起丢包。图2.4给出的报文发送率证明了这一点。当拓朴变更剧烈时，DSDV的报文发送率急剧下降，此时按需驱动的路由协议表现较好。
图2.4 四种算法报文发送率的比较
根据上面的结果可以得出结论，在路由开销和报文发送率方面，按需方式的路由算法要比表驱动的路由算法在性能上有明显的优势。如果某类网络对报文发送的实时性要求不高，能容忍路由发现延迟，则应优先考虑按需驱动的路由协议。
2.2依据网络拓朴分类按网络的拓朴结构分，ad hoc网络路由协议可分为：
1) 平面结构路由
2) 层次结构路由
2.2.1平面结构路由在平面结构中，网络中的所有节点都在同一水平位置并且节点的地位是平等的,彼此之间没有层次概念，不存在特殊节点，路由协议的鲁棒性好，通信流量平均地分散在网络中，此类协议主要用在小型网络中。DSR、AODV、ZRP、TORA、GSR、DSDV等都是基于平面结构的路由。平面结构路由的缺点是当网络规模很大时，可能会导致整个网络都充斥着路由信息报文,网络的可扩展性差。
2.2.2层次结构路由当网络变得很大时，如果仅使用平面结构路由，则每个节点要维护的路由信息量很大，路由信息到达边缘节点也将花费很长的时间。对于规模较大的网络，层次结构（基于簇）路由可以被用来解决上面的问题。在层次结构的路由中，网络由多个簇组成，如图2.4，节点分为三种类型：普通节点、簇首节点和网关，处于同一簇的簇首节点和普通节点共同维护所在簇内的路由信息，簇首节点负责所管簇的拓扑信息处理，簇间通过网关通信。分簇结构可以提高网络规模和减少路由开销，可扩展性好，符合人类管理大型系统的习惯，适合管理超大型网络。
图2.4 自组网的分簇结构
图2.5给出了平面结构和层次结构的对比。左边的自组网是一个平面结构的网络，而右边的则是一个二级结构的自组网。根据网络的规模，可以将自组网分为N层。簇头组成高一级的网络，而在这个高一级的网络中又可以再次分簇，形成更高一级的网络，直至最高级。同一簇内簇成员之间的通信都要通过各自的簇头来中转。随着层数的增加，层的管理算法也越来越复杂，分簇结构的产生及维护将产生一定的开销。
图2.5 平面结构 vs. 分级结构
分层协议主要包括成簇协议，簇维护协议，簇内路由算法和簇间路由协议。成簇协议解决如何在动态分布式网络环境下使移动节点高效地聚集成簇，它是分层路由协议的关键。簇维护协议要解决在节点移动过程中的簇结构维护，其中包括移动节点退出簇和加入新簇，而簇本身又会随着节点的加入和退出而产生和消亡。典型的分层结构协议有CBRP（cluster based routing protocol）[43]、CGSR(Cluster head Gateway Switch Routing)[44]等，前者为按需驱动，否则为表驱动。
2.3小结根据路由触发的时机，自组网路由协议分为表驱动、按需驱动路由协议以及表驱动和按需驱动融合模式路由协议。按需驱动是自组网路由协议引入的新思想，它只在源节点需要传输报文给目的节点时才启动路由发现过程，不依赖于传统表驱动路由协议的周期性路由交换，而且只维护需要通信节点间的路由，减小了路由开销。其缺点是传输前需要等待路由建立。但如果数据传输的实时性要求不高，则可以忽略这个因素。
根据网络拓朴结构，自组网路由协议分为平面结构和层次结构。对于小规模网络而言，平面结构路由简单而有效；但当网络拓朴变得很大时，层次结构路由协议则更适合，层次结构可以避免大规模网络结构中如果只采用平面结构路由则需要维护大量路由信息的问题，但是该结构也需要在簇形成和维护上付出开销。
月影孤鸿 21cnbao@sohu.com（华中科技大学计算机学院硕士研究生）
