魏长虎

摘要：无线自组织网因其快速自动组网和无中心节点等特性，得到越来越广泛的应用。无线自组网的核心技术包括MAC层接入技术和网络节点间的路由算法。不同的路由算法应用于不同的场景，也各有其优缺点，本文主要介绍几种常用路由算法，并对其做简要对比。

关键词：自组网;OLSR;AODV

1.引言

无线自组网具有在无中心节点参与的情况下自行组网的特点，特别适合应用于某些特殊场景。MAC层接入技术和路由算法作为其核心，一直都是专家们研究的热点内容。MAC层接入技术主要有竞争机制和预留机制以及混合机制三种方式，而路由算法主要分表驱动路由和按需路由，以及在某些应用中两种方式的结合，即混合式路由。本文将分别介绍每一分类的特点及其典型的代表算法，并简要对比其优缺点。

2. 路由算法

无线自组织网络具有节点多跳可达、节点快速移动等等特点，这些特点使得承载其上的应用灵活方便，但也需要健壮且稳定的路由协议予以支持。自组网路由协议必须能够在节点快速移动时快速收敛路由表，并维持网络连接的可靠性和稳定性。无线自组织网络路由协议的主要功能是实现分包路由，确保分包从源节点到目的节点的逐跳正确传输。除此以外，自组织网络宝贵的带宽资源、无线通信信道不对称等特点，也对承载其运行的路由协议提出了严格要求。路由算法的分类方法有很多，按照路由条目的生成时机可分为表驱动路由协议、按需路由协议和混合路由协议（图1）。

2.1 表驱动路由

表驱动路由协议也叫先验式路由协议。使用这类路由协议的节点全程保存并动态更新一张全网可达的路由表。当节点有数据要发送时，可以实时的查到下一跳路由，因此此类路由最大的优势是实时性强。这类路由协议一般需要定期发送路由帧，来更新和维持路由条目，所以其开销较大。下面简要介绍典型的表驱动协议OLSR协议。

2.1.1 OLSR

OLSR是优化链路状态路由协议的简称。通过在全网范围内周期性地交换网络拓扑信息和链路状态信息，运行OLSR协议的每个节点都维护全网路由条目。该协议采用了多点中继（Multiple Point Relay，MPR）算法来减少路由帧的发送和转发数量，即只有MPR节点才能转发控制帧，而不是全网洪范，这将节省大量的网络开销。MPR节点的计算有一套比较复杂的步骤，为了全网有一个统一的计算结果，节点需要使用“HELLO”消息发布全网在线节点，实际就是自己的一跳邻居节点。从“HELLO”报文的在线节点向量表中，节点学习到一个一跳邻居集合，通过该集合中的一跳邻居节点，可以到达所有的二跳邻居，节点利用学习到的全网拓扑图，就可以计算出到达所有其它节点的最优路径，一般是最短路径，生成最终的路由条目，并将其存储在路由表中，路由表常驻内存。这种以空间换时间的思想，使得节点发送数据业务时能够最快速的查找到路由条目，具有最高的实时性和最短的业务时延。

优点：业务时延可忽略，并且优化了链路状态路由协议算法，尽量减少了协议开销。

缺点：节点依然需要定期维护路由，因此不支持休眠;路由收敛较慢;开销较大。

2.2 按需路由

顾名思义，按需路由[4]协议在节点发送数据业务并且查找不到合适的路由条目时，会启动路由发现过程，这点与表驱动路由不同。由于是按需建立路由，所以节点维护的路由一般仅仅是网络拓扑的一小部分，其需要的协议开销非常小。按需路由分为路由发现和路由维护两个阶段。此类路由协议的主要差别体现在路由发现的过程、计算和维持信息的方法、数据传输的方法。此类路由主要有AODV、DSR等协议。

2.2.1 DSR

DSR（Dynamic Source Route）的路由[1]发现过程：如图2所示，节点S发送报文给节点D，先查找路由表，发现没有相应的路由条目，于是节点S发起到节点D的路由发现。源节点S洪泛一个Route Request（RREQ）;每一个中间节点在转发该RREQ的时候，都将自己的地址信息加在RREQ中。目的节点D收到RREQ后，发送一个Route Reply（RREP），RREP中保存了从S到D的中间节点，及S到D的路由信息;RREP的发送依据的是将RREQ中保存的节点路径反转;节点S收到RREP帧之后，可学习到S到D的路由条目;

DSR的路由维护过程：当节点S向D发送数据的时候，整个路由信息都包含在报文头部，中间节点就依据报文头中的路由信息来转发。因此使用该路由算法，报文的头部大小与路由长短有关系。

优点：

1）源路由，可保证无环路;

2）不要求中继节点缓存全网路由，允许侦听建立局部路由信息;

3）由于是按需路由，降低了路由规模和开销;

4）支持单向链路;

缺点：

1）每个数据包头带有完整路由信息，额外开销;

2）泛洪路由搜索，可能导致冲突和短暂广播风暴;

3）路由缓存，路由过期失效。

2.2.2 AODV

本节描述AODV（Ad Hoc On-Demand Distance Vector Routing）协议[2]的路由发现过程。在节点需要发送数据而又查不到路由条目时，开启路由发现过程，使用广播报文发送RREQ分组。AODV协议支持已有链路上的中间节点回应RREQ请求。找到可用路由条目，则中间节点或目的节点将采用单播的方式向源节点回复一个RREP报文，RREP刚刚建立的反向路由逐跳传输。因此，AODV要求链路必须时双向可用的。与DSR不同的是，AODV在节点上维护路由表，所以数据包不需要再头部携带路由信息，提高了帧效率。AODV的路由发现过程如图3所示。

2.3 混合式路由

802.11s HWMP（Hybrid Wireless Mesh Protocol） [3]。该协议融合了表驱动式和按需式两种路由路由思想。HWMP的表驱动式路由是一种基于树的路由，主要用于拓扑相对静态的环境中，使用主动式路由需要确定一个根节点，根节点周期性地广播路由路径请求包（PREQ），HWMP协议据此构建和维护树形逻辑拓扑。HWMP协议中的按需路由使用PREQ和PREP机制在两节点之间建立路由，节点间使用PREQ和PREP消息进行度量信息交互，并且在PREQ中采用序列号来保证路由的时效性。

2.4 表驱动路由与按需路由比较

使用表驱动路由协议，由于节点全程维护一张全网路由表，所以节点发送数据时可实时的获取到下一跳，业务的延迟较小，但为此产生的周期性路由控制报文开销也是巨大的。随着网络规模的增加，表驱动路由的开销将带来巨大的影响甚至无法使用。与之不同的是，按需路由协议无需维持全网路由表，在路由开销方面的表现优秀。但因为发送数据时可能需要比较复杂的路由发现过程，故业务的时延方面表现略差。

按需路由协议和表驱动路由协议各有其优缺点，一般来讲，应该根据自组网使用场景的不同选取合适的路由协议。目前越来越多的研究将表驱动路由与按需路由结合，取长补短，这将更能提升自组织网络的系统性能。

3. 结束语

在自组网中，路由算法的优劣直接决定了数据转发经过几跳可达、路由查找是否实时，对业务的性能影响很大。因此根据网络的规模、具体的业务场景、以及成本的考虑，选择合适的路由算法尤为重要。本文介绍了几种常用路由算法的原理，但由于時间原因，还没有给出对应算法的仿真结果。对算法的仿真将是本人下一步的研究重点。

参考文献

[1] 张简丽，许洪光. 基于DSR的路由协议综述[J]. 通信技术. 2009. （204）：137-139.

[2] C. Perkins， E. Belding-Royer， S.Das. Ad hoc On-Demand Distance Vector（AODV） Routing. July 2003.

[3] 李艳，王娜. 基于HWMP协议的无线MESH动态备份路由协议[J]. 福建师大福清分校学报. 2016. （5）：6-9.

[4] 张立明，唐海涛，王健，魏晓辉，张仲明. DSR和AODV路由协议虚拟仿真实验平台设计[J]. 《实验室科学期刊》. 2018. （6）：21-3.BC88E35E-4677-4FB4-AD3E-D944F6A698AB