一种无线自组织网络动态路由协议

姜永广，田永春

（中国电子科技集团公司第三十研究所， 四川 成都 610041）

0 引言

无线自组织移动网（Mobile Ad-hoc Network，MANET）是一种新型的无中心、分布控制的无线移动通信网络，不需要建设网络基础设施，具有快速开设能力，早期主要应用于军事通信。与其他移动通信系统相比，MANET无固定的基站，具有高效的自组性，支持动态变换的网络拓扑结构和多跳转发技术，采用分布式控制，系统鲁棒性和抗毁性较高，已广泛运用于军事战术环境、事故突发现场、抢险救灾等紧急环境。

然而在无线通信环境中，特别是战场和抢险救灾等环境，无线信道变化快速，节点移动、加入、退出，地形、地物等都会引起网络拓扑结构的动态变化。路由协议的作用就是在这种环境中，监控跟踪网络拓扑结构的变化，及时交换网络连通性变化信息，产生、维护和选择最优路由，并根据选择的路由转发数据，从而提供上层业务的连续性。目前，已存在数十种MANET路由协议[1-2]，可以划分为：

①主动路由（Proactive Routing Protocol）：一类表驱动协议，网络中所有节点都周期性的维护网络拓扑，比较典型的有：按序距离矢量协议（DSDV）、优化链路状态协议（OLSR）、鱼眼状态协议（FSR）、模糊视野链路状态协议（FSLS）等；

②被动路由（Reactive Routing Protocol）：主要是针对主动路由协议开销大，不能适应拓扑快速响应的缺陷而发展的，其基本思想是各节点不再按周期维护网络拓扑，而是在有业务需求时通过协议去发现最短路径，比较典型的有：动态源路由协议（DSR）、按需距离矢量协议（AODV）等；

③混合路由（Hybrid Routing Protocol）：为了改善主动路由开销大、被动路由实时性差而发展的一类协议，比较典型的有：分区路由协议（ZRP）、界标特殊路由协议（LANMAR）等；

④地理辅助路由[3]（Geographic Position Aided Rou-ting）：把节点的网络拓扑位置与地理位置结合起来。在 GP S位置信息的支持下，按照方向进行数据分组的转发，可极大地节省路由开销，比较典型的有位置辅助路由协议（LAR）。

这些协议各有优缺点，但应用到窄带电台环境，还需要在分布式控制、环路避免、减小开销、路由快速建立等多方面进行优化设计。本文介绍一种基于稀疏树的自组织路由协议（STRP）。

1 基于稀疏树的自组织路由协议（STRP）

STRP是一个在所有节点中维护全网路由信息的表驱动路由协议，综合了距离矢量和链路状态路由协议的优点，由邻居维护（Hello协议）、拓扑更新协议、路径寻找算法三个主要部分组成，每个节点维邻居距离表与路由表。

邻居维护：采用Hello协议周期性地检测与邻居间的连通状态。每个hello分组中携带了节点的邻居列表。接收节点通过hello报文建立节点的邻居关系，通过hello报文中携带的邻居列表进行信道状态的判断。

拓扑更新：节点利用收到的Hello消息建立一跳的路由关系，生成最基本的路由表。这个新的路由表会通过拓扑更新协议被传递出去，每个邻居节点收到该更新后，检查是否存在环路并修改更新消息里的代价后把它存入邻居距离表对应该邻居的表项中，此后通过该邻居距离表节点生成自己的路由表，而路由表的生成是通过计算邻居距离表中到目的节点的最短路径稀疏树（SST，Shortest path Spanning Tree)来实现的，到某个目的节点的路由也是到该目的节点的稀疏树。在发生路由改变时，该节点将把稀疏树发生了改变的部分传递出去，它的邻居存储该消息到邻居距离表中，同时根据接收到的ST重新计算自己的ST或路由表。

改进的路径寻找算法：路径算法采用改进的路径发现算法（APFA），一方面计算路径，一方面消除环路。网络各节点依据自己建立的SST执行Dijkstra算法分散计算各自的路由表，实质上，STRP实现的Dijkstra最短路径算法是在一个分级图上分布实现的，分级图代表网络的连接性。

根据 STRP协议的思想，协议的大部分流程都和常规的路由协议类似，这里不再赘述。这里仅介绍在 STRP里采用的避免计数到无穷与环路消除算法。

2 改进的路径查找算法

由于STRP依据自己的SST执行Dijkstra算法分散计算各自的路由表，其实质是STRP实现的Dijkstra最短路径算法是在一个分级图上分布实现的，分级图代表了网络的连接性。该算法是路径发现算法（Path-finding Algorithm，PFA）的一个改进版本（APFA）。

在STRP中，每个节点路由表都包含了目的地址、距离、下一跳和去目的节点的倒数第二跳信息，APFA正是利用距离和路由上的“倒数第二跳节点”信息，使每个节点利用本地信息就可以推导出隐含路由，而路由存储信息和路由更新信

息都不需要增加过多的开销。网络中节点路由表如表1所示。

表1 由倒数第二跳推导隐含路由

“倒数第二跳节点”定义为沿源节点到目的节点的整个最短路由上，去往目的节点的前一跳节点。如下所示：

下面说明 APFA利用倒数第二跳信息推导隐含路由和消除网络拓扑快速变化带来环路的过程。如图1所示，网络由a、b、c、d、e、f、g七个节点构成，节点a的路由表如表1由倒数第二跳推导隐含路由1所示。

举例推导从节点a到节点c的路由，查寻节点c的表项，可以知道从a到c路由上的倒数第二跳是b；而在节点b的路由表中，从a到b的倒数第二跳是g；在节点g路由表中，倒数第二跳是a，从而可以推导从a到c的路由是a→g→b→c。

APFA可快速消除分布式Bellman-Ford算法中计数到无穷的问题，并及时发现稳定的环路，加速算法的收敛速度，但不能避免网络快速变化而带来的临时环路的产生[4]。如图1所示。

图1 路径发现算法中的临时环路举例

在网络拓扑快速变化过程中，在网络拓扑变化前，c到h的下一跳为d，由于网络变化c到d的链路中断（图1中过程①），而更新到h的下一跳为e，在此路由更新消息还未交换到g之前，a与g之间链路失效（图1中过程②），g会选择b作为自己到h的下一跳，从而产生了c→e→g→b→c的临时环路。

为了消除临时环路，参考Cisco EIGRP协议采用APFA ，它利用邻居间的同步机制消除临时环路。

APFA引入了可行距离（Feasible Distance，FD）的概念。如下：

3 仿真分析

STRP协议是针对网络拓扑变化快、传输带宽窄的网络而设计的，为了比较本文所提出的路由算法的性能，把它与无线 OSPF（WOSPF）作对比进行仿真。仿真场景设置如下：节点数32个，采用的电台速率为288 kb/s，信道接入方式为TDMA，电台单跳通信距离为 12 km，节点均匀分布在一个40×40 km2的范围内，其中8个节点随机移动。

图2与图3是协议收敛时间的对比，其中横轴是仿真时间，纵轴是路由协议的收敛时间。图2是节点静止时协议收敛时间对比，图3是节点移动时两者收敛时间的对比。

图2 节点静止时收敛时间对比

由图2可见在静止时，STRP收敛时间远比WOSPF要小，主要是稀疏树算法对无线网络拓扑进行了剪裁，网络链路数少，而WOSPF要达到全网链路状态数据库的同步，需要的时间较长。由图3可见节点移动时，STRP收敛更快速，主要原因是引入了可行距离的思想，并对移动性进行了吸收，将其变化限制在网络的局部，而 WOSPF则是进行全网的变化与同步。

图4与图5是两者在节点运动时协议开销的对比，其中图4是开销的时间平均值，图5是开销的瞬时值。

由图4,图5可见，STRP的开销明显低于WOSPF，主要原因是STRP可以把节点在移动时对网络拓扑的影响限制在其1跳周围内，所引起的链路变化不会传递到全网，因此开销较小。而WOSPF需要维持全网拓扑数据库的一致，因此路由开销较大。从仿真来看，STRP协议具有收敛快，开销小、自动限制移动性影响等特性，能够较好地适应窄带无线通信环境的需要。

图3 节点移动时收敛时间对比

图4 节点运动时路由开销瞬时值对比

图5 节点运动时路由开销平均值对比

4 结语

移动自组织网主要使用在军事通信等没有固定基础设施的场合，这些场合的无线通信带宽通常较窄，具有动态拓扑、波动的通信质量以及单向信道等特点，传统的路由协议难以适应这种网络环境的需要。目前出现了很多自组织路由协议，它们解决问题的思路各不相同。本文从简单、实用的角度，提出了综合DV和LS算法特点的STRP协议，采用稀疏树算法来降低协议的开销，采用快速路径搜索算法来消除环路实现网络的快速收敛，具有轻量、可靠、快速等优点，可以满足较为严酷无线通信环境的需要。

[1] Hong X Y, Xu K X, Gerla M.Scalable Routing Protocols for Mobile ad hoc Networks[J].IEEE Network,2002,16(04):11-21.

[2] Ying C,Lv Q,Liu Y,et al.Routing Protocols Overview and Design Issues for Self-Organized Network[C]//Proceedings of 16th World Computer Congress & International Conference on Communication Technology. Beijing, China: [s.n.], 2000:275-282.

[3] Ko Y B,Vaidya N H.Location-Aided Routing(LAR)in Mobile Ad hoc Networks[C]//Proceedings of ACM/IEEE MOBICOM’98.Dallas,TX:IEEE,1998:66-75.

[4] Murthy S,Garcia-Luna-Aceves J J.A Path-find Algorithm for Loop-free Routing[J].IEEE ACM Transactions on Networking,1997,5(01):148-160.