无线自组织网络中的路由技术研究

李　昕　周剑刚　李　珂　李　玲

【摘要】路由技术是无线自组织网络组网的基础和关键环节。文章介绍了当前无线自组织网络路由技术研究的现状,在此基础上,详述了无线自组织网络中具有代表性的路由协议,并对这一领域未来的发展趋势作了展望。

【关键词】无线自组织网络 路由技术 路由重建 路由修复 CBRP

1 引言

无线自组织网络具有无基础设施依托、临时组建、拓扑动态变化、节点能力有限等特点,用于为地理上相邻但散布区域超过单个节点无线传输范围的一组节点之间提供信息传递服务。这一需求首先来自军事领域,以美国国防部相继推出的PRNET(Packet Radio Network)、SURAN(Survivable Adaptive Radio Networks)以及全球移动信息系统(GloMo)计划为代表。无线自组织网络研究在民用领域的兴起始于上世纪90年代,以无线通信技术的快速发展以及便携、小型化的计算设备的迅速普及为契机。无论是在军用还是民用领域,路由技术都是无线自组织网络组网的基础和关键环节,因此受到长期的关注和研究。本文将对这一领域的研究现状作较为深入的分析和介绍,并对其发展趋势进行展望。

2 无线自组织网络路由技术研究现状

路由协议开发是无线自组织网络研究领域最具挑战性的工作之一,除了必须适应无线信道特性以外,还需面临网络环境与网络拓扑变化无常、节点资源有限等问题,并需要特别考虑无线通信物理层和MAC层特性对网络层的影响。

早期的无线自组织网络路由技术研究仍然承袭了来自固定网的基本思路,把路由查询建立在对全网路由信息精确掌握的基础之上,并将控制平面与数据平面分离。但由于无线自组织网络稳态持续时间很短,有时甚至在很长时间内无法进入稳态,因此早期的研究者不得不面对这样一种困境:提高拓扑信息更新的速度必然引起巨大的网络开销以及频繁的路由震荡,而要克服这两个问题又必须以牺牲路由选择的准确性为代价。

针对无线自组织网络的特性,目前在路由技术研究领域有两种主流的解决方案:

(1)仍然将控制平面与数据平面分离,但不保证路由表具备100%的准确性和实时性,这一类型的协议包括ZRP[1]、FSR[2]、CBRP[3]等;

(2)将控制平面与数据平面融合,以数据流触发路由查找过程,以提高路由查询开销为代价换取路由信息的实时性,代表性的协议有AODV[4]、DSR[5]。

3 现有解决方案

3.1 改进的传统路由协议

在无线自组织网络路由协议研究的早期,通过改进传统路由协议以满足无线自组织网络组网的需求受到极高的关注。尽管此类研究的最终结果并不理想,但却有助于人们认识无线自组织网络中路由查询所面临的主要问题。

此类协议包括目的端赋序的距离矢量路由协议[6](DSDV,Destination-Sequenced Distance-Vector Routing)、群首网关交换路由协议[3](CGSR,Clusterhead Gateway Switch Routing)以及鱼眼路由协议(FSR,Fisheye State Routing Protocol)。前两种协议以距离矢量路由算法为核心,采用比水平分割毒性逆转更为有效的环路避免机制,并通过控制路由控制信息的数量来减少开销,两者的区别仅仅在于广播拓扑变更信息的方式以及运行协议所需路由表的数量有所不同。FSR则属于链路状态路由协议,采用Dijkstra算法进行选路。

采用距离矢量路由算法的协议通过维护和使用全网一致的路由表,在网络拓扑变化缓慢、节点数量不大的情况下,通常能够获得较高的路由转发效率;但仍然存在开销过大和可扩展性差的问题,不能适应动态性较强的网络环境。FSR协议的工作原理与OSPF较为相似,不同之处在于FSR通过在链路状态信息广播的范围(以广播源为圆心,若干跳为半径)与广播的周期之间建立正比的关系来限制网络中链路状态信息的数量,其代价则是使距离较远的节点之间交换链路状态信息的频率很低,无法保证全网路由信息的一致性。

3.2 按需驱动的路由协议

脱胎于固定网络的设计思想最终没有成为主流,更多的研究者彻底放弃了传统的设计原则,将控制平面与数据平面融合,采用按需驱动路由查找方式[4,5]。源端发起按需驱动路由协议与表驱动路由协议最重要的差异就在于前者从不主动发布和收集网络拓扑信息,也不维护全网一致的路由表作为转发依据。只有在有数据需要传输的时候,路由器才主动发起到目的地的路由查找过程,以较长的(相对于固定网络中表驱动的路由协议而言)路由搜寻时间为代价,换取在特定时间和特定场景下较为精确的局部路由信息。

为了对付随时可能发生的路由中断,按需驱动路由协议通常采用两种路由维护方式:路由重建与路由修复。路由重建即当路由中的某一条链路发生中断时,源端路由器重新通过全网广播方式寻找路由。路由修复即在链路中断发生时,由中断链路的上游节点发起寻找下游节点或目的节点。路由修复曾经一度是无线自组织网络路由协议研究领域的一个热点,但最终路由重建方式得到了广泛的认可。其中的原因在于,无线自组织网络中,某一条路由的强壮性会随着路由中链路数量的增加而出现指数级递减,路由修复尽管能够解决局部的路由重建问题,但却有可能令路由强壮性下降。而且,路由修复方式仅适合于解决路由中的单链路失效问题,当一条路由中的多条链路同时或相继中断时,便无法发挥应有效能。

按需驱动的路由协议种类较多,比较有代表性的包括Ad-Hoc按需距离矢量路由协议(AODV,Ad-Hoc On-Demand Distance Vector Routing)、动态源路由协议(DSR,Dynamic Source Routing)、基于相关性的路由协议(ABR,Associativity-Based Routing)、基于群组的路由协议[7](CBRP,Cluster-Based Routing Protocol)等。AODV采用与DSDV相同的选路和环路避免机制,其改进之处在于完全按需搜索路由并只要求数据转发路径上的路由器保存和更新与该路径有关的路由信息。DSR和AODV最大的区别就在于采用了源路由的方式,这使DSR可以使用单向无线链路构成非对称的往返路径,具有比AODV更大的灵活性,但这样做的代价则是增加了每个数据包的开销。

ABR[8]的特别之处在于采用了与AODV和DSR完全不同的度量值——联系稳定度(degree of association stability)作为路由选择的依据。联系度的值越低,就表明相应节点的移动性越强,链路状态越不稳定。因此,ABR所选择的路由稳定性最好,但有可能不是跳数最少的。

前面提到的几种路由协议都采用扁平结构,优点是较为灵活,缺点则表现为不能在大规模的网络中进行扩展。CBRP是一种分层式的路由协议,通过在网络中建立自发的群组来克服这种不足。在运行CBRP的网络中,节点被划分为三类:群组首节点、网关节点和普通节点。群组首节点通过某种机制(例如在一组相邻节点中选举路由器ID最大者或与其他路由器连接性最佳者为群组首节点)在某一特定范围内(例如一跳或两跳半径范围内)的相邻节点中选举产生,群组首节点ID即作为该群组的标识符。为了维护群组的结构,每个节点定期向其邻居广播HELLO信息,其中包括本节点的状态、邻居列表以及与之相邻的群组首节点列表。在路由查找的过程中,只有群组首节点执行泛洪式搜索的功能,网关节点仅仅负责将收到的路由查询信息转发给邻近的群组首节点,不对外进行广播。在CBRP中,群组首节点和网关节点共同构成了一个类似于骨干的网络,从而有效地降低了路由查找的复杂性。