无线网状网络的路由协议研究

摘要无线网状网络是一种新型的宽带无线网络，主要用于因特网的无线接入。路由是WMN中的一项关键技术。本文先介绍路由技术的概念以及一般有线网络的路由，然后以Ad hoc为例介绍无线多跳网络中的路由，并比较它们与有线网络路由的区别。接着着重介绍WMN路由协议。最后本文详细介绍分析一种适用于无线网状接入网的TBR协议及其改进协议。
关键词 WMN；Ad hoc；路由协议；TBR

1 引言
如今，无线通信技术正以前所未有的速度发展着，并日益广泛地融入到人们的生活之中。蜂窝移动通信网技术比较成熟，网络覆盖能力强，然而它在数据业务支持方面明显不足。无线局域网在近年来得到了较快的发展，成为无线接入的有效手段，但是它的覆盖范围又很有限。下一代无线通信网络究竟该朝哪个方向发展？虽然还没有定论，但能同时提供大覆盖范围、高数据速率和移动性支持则是共识。近年来，无线网状网络（Wireless Mesh Network，WMN）以其特有的优势引起了人们的广泛关注，并可能成为下一代无线网络和因特网的重要组成部分。
2 WMN概述
WMN是一种从移动Ad hoc网络中发展起来的新型网络技术，因此也是一种动态自组织、自配置的多跳宽带无线网络。与Ad hoc网络不同，WMN可以通过位置相对固定的无线路由器，将多种网络技术进行互联，并提供高速的骨干网。该结构已经被纳入到802.16e，802.11s等标准中。WMN作为未来无线城域核心网最理想的方式之一，具有可能挑战3G技术的能力，是构建B3G/4G的潜在技术之一。
WMN由客户节点、路由器节点和网关节点组成。客户节点也可以分为普通WLAN客户节点和具有路由与信息转发功能的客户节点两类。与传统的无线路由器相比，WMN路由器在很多地方均作了增强，除了提升多跳环境下的路由功能外，对MAC协议、多无线接口等技术也有所改进。网关节点具有到Internet有线宽带的连接，WMN通过其网关节点接入Internet。WMN接入网的结构图如图1所示。

图1 WMN接入网结构图

按照结构层次，WMN的网络结构可以分为平面网络结构、多级网络结构和混合网络结构。其中，平面网络结构中所有节点均为对等结构，适用于节点数少又不连入核心网的场合；多级网络结构可以分为上下层两个部分，上层为MESH结构的路由器网关网络，下层为普通WLAN客户节点，它们只能通过接入上层的网络才能实现相互间的通信；混合网络结构即以上两种结构的混合，网络也分为上下两层，但其下层是具有路由与信息转发功能的客户节点。
3 Internet路由协议与Ad hoc网络路由协议
路由是WMN中的一项关键技术，本文主要针对无线网状网络的路由协议进行研究。
3.1 路由技术的概念
路由技术是计算机和通信技术相结合的产物，它随着网络的迅速发展而发展。简而言之，路由技术是指采用一种或多种策略，为数据分组从源地址到目的地址的转发选择一条或几条理想的路径。它是通过在路由设备（如路由器等）上运行路由协议来实现的。路由器间可进行相互通信，从而在每个路由器都建立一张路由表，用于存放网络中的路由转发信息。通过查找路由表中相应表项（下一跳地址等）来转发数据分组。
3.2 Internet路由协议
Internet路由协议根据其设计理念，主要分为为两大类：距离向量路由协议和链路状态路协议。
距离向量路由协议（如RIP）主要优点是简单且有效率，但是，这种方法存在收敛慢、易出现路由环路等问题。链路状态路由协议（如OSPF）的特点是，所有路由器均保存全网络拓扑信息并做周期更新，并且任何一个环节的改变引发即时更新。相对于传统的距离向量路由协议，链路状态路由协议有全网拓扑信息，因此可以防止出现路由环路且收敛速度较快。然而，这种协议通过全网广播来传递最新信息，因此，尤其是在高移动性（或严重无线电干扰）造成链路状态改变的时候，此类协议会耗费大量的网络资源并产生过多的控制开销，而使其变得不可行。
传统的Internet路由协议（如OSPF，RIP）是专为有线网络设计的。它们不能够很好处理无线网状网环境中常见的拓扑结构和链接质量的快速变化。因此，在无线网络中不能直接使用传统的Internet路由协议，而要使用为无线网络专门设计的路由协议。
3.3 Ad hoc网络路由协议
Ad hoc网络是一种没有有线基础设施支持的无线移动网络，网络中的节点均由移动主机构成，移动主机之间可以直接通信，移动主机既是主机又是路由器，通过移动主机自由的组网实现通信。
如图2所示，根据发现路由的驱动模式不同， Ad hoc网络的路由协议一般分为以下两种：一种称为表驱动（Table Driven）路由，或者预先式（Proactive）路由，如DSDV（Dynamic Destination-Sequenced Distance Vector）是一种典型的表驱动路由协议，基于Bellman-Ford算法；另一种称为按需（On Demand）路由，或者反应式（Reactive）路由，如DSR （Dynamic Source Routing）是一种典型的按需路由协议。此外，还有一种混合式路由协议——ZRP（Zone Routing Protocol）[1]。

图2 Ad Hoc路由协议按驱动方式的分类

表驱动路由协议通过连续地检测链路质量，时刻维护准确的网络拓扑和路由信息。其优点是发送报文时可立即得到正确的路由信息，然而表驱动路由需要大量的控制报文，开销太大，不具有良好的扩展性。而按需路由协议则有所不同，其节点仅当需要时才查找相应路由，节省了路由维护的开销，但在进行数据传输时需要寻找路由，造成不可预测的路由延迟，因而不适应对时延敏感性应用。从上述的分析中可以看出，无论是表驱动路由还是按需路由，对规模较大的自组织网络的支持都不是很好，而混合式又过于复杂而不适合实际应用。
4 WMN路由协议
4.1 WMN与Ad hoc的比较
虽然在WMN的路由设计时可以参考一些现有的用于ad hoc网络的路由协议。但事实上WMN与移动Ad hoc网络（MANET）还是有较大区别的。主要体现在：
（1）MANET的网络拓扑注重的是移动，而WMN的移动性低，网络拓扑总体呈现静态或弱移动。
（2）MANET的节点能量有限，功率节省是其路由设计的一个重要方面，而WMN关注的是高吞吐量的路由协议，侧重无线宽带大容量传输。
（3）MANET的业务侧重于网内通信，而WMN的业务侧重于网间通信，主要用于因特网或宽带多媒体接入。
（4）此外，MANET的节点类型单一，即兼具路由与主机功能、地位平等的客户端节点，而WMN的节点类型一般有三种。
正是由于WMN和Ad hoc网络两者之间的差别决定了为Ad Hoc网络设计的路由协议可能不适合WMN，因此，我们必须充分考虑WMN的特点，设计最适合WMN的路由协议，以提高WMN的性能。
4.2 WMN路由协议的设计因素
根据无线多跳网络的路由设计思想结合WMN自身的特点，在设计WMN路由时要考虑下面若干因素：
（1）多路由判据：许多以最小跳数作为路由判据的路由协议往往不是最优的。为了解决因为路径质量差而影响网络吞吐量等性能的问题，要求WMN采用新的由多种路由判据结合，且能正确反映出链路质量对各指标的影响的路

由。参考文献中对几种典型的路由判据进行了比较研究。链路质量源路由（LQSR）根据链路质量来选择路由，它有三个路由判据，分别为期望传输次数（ETX），每跳的往返时间（per-hop RTT），每跳数据对（per-hop Packet-Pair）。文中将这三个路由判据与使用最小跳数（HOP，Hop Count）作为判据进行比较。对于WMN中的固定节点，ETX可以获得最好的性能，而最小跳数方法在节点移动时获得的性能最佳。这也说明在参考文献中所使用的路由判据在WMN中加入移动节点时的性能还不够完善。
（2）可扩展性：随着网络规模的增大，利用广播机制进行路由查找的方法会消耗很多网络资源。同时，由于大规模网络建立路径时将花费很长时间，使端到端的延时变大，一旦路径建立起来，由于路径发生变化又需要消耗很大的网络资源进行路由重建。此外，由于分级路由比较复杂并且不易于管理，而基于地理位置信息的路由取决于GPS或类似的定位设备，这些都增加了WMN的成本与复杂性。这就要求新的可扩展的路由协议。
（3）负载均衡能力：在WMN中，所有节点通过路由协议共享网络资源。因此，WMN路由协议必须满足负载均衡的这一要求。如当网络中某些节点发生拥塞，并成为整个网络的瓶颈节点时，新的业务流应能“绕过”该节点。
（4）路由容错能力：在WMN中，路由发生错误时，需要尽快完成路由重建，以避免服务中断。在WMN中，由于MR移动性小，路由错误往往是由数据冲突造成的，并非实际链路断裂造成，这就要求WMN的路由协议必须具有较强的容错能力。
4.3 WMN路由协议方案
目前出现的一些WMN路由协议的方案主要有以下几种类型：
（1）跨层路由：以往的研究都集中在网络层上，然而对于WMN，因为网络的时变特性，路由性能并不理想，所以可以从MAC层中提取一些状态参数信息作为路由判据。此外，还可以综合考虑合并MAC层与路由层之间的一些功能。文献提出基于跨层设计的思想，提出从底层采集路由判据的方法来进行路由选择，考虑了MAC层冲突、包成功传输率与数据成功传输率等参数。在路由协议中，根据这些判据可以选择具有较少发生冲突、数据包传输可靠和高数据传输率的路径进行数据传输。研究表明，跨层设计可以使路由协议收集到底层的实际数据传输情况，从而做出正确的路径选择，这对网络性能的提高具有很大的意义。
（2）多路径路由：在源节点与目的节点间有多条路径可供选择，使用多路径路由的主要目的是为了达到更好的负载均衡能力和更高的容错能力。当一条链路因为链路质量下降或移动而断开时，另一条可用路径将会被选用。而不像传统路由，等待重新建立一条新的路径，从而使端到端的时延、吞吐量、容错能力等都有所增强。多路径路由是目前的一个研究热点，文献中提到基于DSR的多径源路由协议（MSR，Multi-path Source Routing）。然而多路径路由的缺点是比较复杂，尤其对于仅依靠表驱动的路由协议。采用多径技术后数据包到达顺序可能得不到保证。此时，上层协议是否需要修改还有待研究。
（3）分级路由：在文献中提到分级路由，它要求有一定的自组织配置把网络节点进行分簇。每个分簇有一个或多个簇头。通过使用分级技术，在簇内和簇间使用不同的路由协议，分别发挥各种路由的优点，从而实现大规模的WMN路由。若所有的数据业务都通过簇头转发，那么簇头将成为整个网络的瓶颈。若数据业务不通过簇头转发，该路由协议的设计将变得更加复杂。
（4）基于地理位置信息的路由：与基于拓扑结构的路由机制的相比，基于地理位置路由机制只根据邻近的或目的的节点的位置信息转发数据包，见文献。因此，比起其它路由协议，拓扑结构的变化对按地理位置信息路由的影响较小。但是基于地理位置信息的路由需要依靠GPS或类似的定位设备，从而增加了成本与复杂性，并且获得目的节点的位置信息还要给网络带来很大的开销。
4.4 TBR协议及其改进协议
下面本文将详细介绍分析一种实用的适用于无线网状接入网的路由协议——TBR（Tree-Base Routing）协议及其改进协议。
1）TBR协议
TBR协议是一种表驱动路由协议，适合弱移动性的无线网状网络。
在TBR协议中首先要确定网络的根节点，可以是一个也可以多个，本文中只考虑仅有一个根节点的情况。当确定好根节点后，就可以使用TBR协议确定网络的拓扑树了。根节点周期性广播出RANN（Root Announcement）消息，用累加的序列号来区别每个RANN。每个收到RANN的节点将发出这些RANN消息的源节点地址缓存，作为其潜在父节点，然后再把RANN用更新的累加参数广播出去。在经过一个预定周期收到所有可能的父节点发来的RANN消息后，该节点选择一个到根节点有最佳参数的潜在父节点作为父节点，并更新自己的路由表。这样，该节点就可以获得到根节点的确定路径，然后该节点发出RREP消息到根节点进行注册。每一个中间节点都收到这个RREP消息，然后向其选定的上一级节点转发，并且更新前一个发出RREP的节点为其下一跳子节点。
按这种方式，根节点就可以知道所有的参与节点并且建立了一个拓扑树，可到达任一个节点。如果一个节点在规定的时间内没有收到RANN消息，就不参与这个树的建立过程，直到收到有效的RANN。由于网络的拓扑是动态变化的，根节点需要周期性地发送RANN来维护拓扑。TBR协议可以通过经常性地广播路由信息来提高稳定性及降低延迟，但它的开销较高、可扩展性较差。
如果子节点丢失，父节点会产生路由错误信息并转发至根节点。相反，如果父节点丢失，则子节点会查看它的路由缓存表并选择一个新的父节点（如果有），然后单播一个经过此父节点到根节点的RREP消息。
对于TBR协议中网内节点间的通信的情况，当源节点要发送消息给目的节点时，源节点如果没有直接到达目的节点的路径，就会发送消息到根节点，再由根节点发给目的节点。这样做的缺点是：网内的节点经常发送数据流经过根节点，使根节点容易拥塞，导致网络性能下降与能量资源浪费。
2）TBR的改进协议
文献提出了一种TBR的改进协议，其核心理念是创新的采用一种根驱动路由协议来解决网内通信问题。
此协议首先要求根节点在全网范围提供最佳路由。要求根节点不仅要建立拓扑树，而且还要建立全网网络拓扑。要做到这一点，可以在收到RANN消息后，每个节点在返回的RREP消息中捎带自身邻节点信息，包括所有相邻节点的地址及相应通信开销参数，该参数可以是跳数或其它开销。
其次，文中采用了两个额外的消息：Route Set （RSET）和Route Notification （RNTF）。当源节点要发送数据给目的节点时，根节点可以推荐一个最佳参数路由，由根节点单播发送RSET消息，把路由信息告诉目的节点。然后，收到RSET的目的节点再单播发送RNTF消息来通知中间节点。
对于网内路由的优化，文献中采用的方法是：节点只在第一次拓扑图建立时才在发送的RREP消息中捎带上邻节点信息。拓扑图的计算，采用Dijkstra算法。根节点在收到全部的信息后，进行一次最佳路由计算。而后只有节点的链路状况发生改变时，才在此节点用RREP消息捎带上更新的邻节点信息给根节点，根节点再算出新的最佳路由，从而减少了开销和Dijkstra算法的计算次数。
文中提出将这种根驱动的路由协议用于WMN网内通信，而网间通信采用原来的TBR协议，可以在Mesh WLAN中达到较好的性能。
当然这种基于根驱动的路由协议，也有其不足之处。文献中仅考虑单个根节点的情况，而采用多个根节点可以将计算分布到各个根节点，并且这样有利于增强网络的扩展性，单个根节点的失效不会引发全网瘫痪，所以采用多个根节点才是符合实际应用的最佳选择。
5 结语
WMN作为一种新型的宽带无线网络具有许多独特的优点，在家庭、企业和公共场所等诸多领域都有广阔的应用前景。WMN的路由协议作为其关键技术，具有重要的理论意义和实际意义。本文在简要地概括了有线网络和Ad Hoc网络路由协议的基础上，根据WMN网络特点，介绍了几种WMN的路由协议。应当指出，这方面的工作还有许多值得探索的课题，如考虑安全性能及Qos保障的路由协议。
参考文献
[1] Z. J. Hass, M. R. Pearlman. “The Zone Routing Protocol （ZRP） for Ad Hoc Networks”, Internet Draft, 1997, Available from. draft-ietf-manet-zone-zrp-00.txt
Luigi Iannone, et al. “Cross-Layer Routing in Wireless Mesh Networks”, Computer Networks. March 2005,445~487
R. Draves, J. Padhye, and B. Zill. “Comparisons of Routing Metrics for Static Multi-Hop Wireless Networks,” ACM Annual Conf. Special Interest Group on Data Communication （SIGCOMM）, Aug. 2004, pp. 133-44
方旭明等.下一代无线因特网技术:无线Mesh网络. 人民邮电出版社. 2005年5月第1版. pp. 108–110
Lei Wang, lianfang Zhang, Yantai Shu and Miao Dong. “Multipath Source Routing in Wireless Ad hoc Network”. 2000 Canadian Conference on Electrical and Computer Engineering, Vol.1, pp.479-483
E. M. Belding-Royer. “Multi-level Hierarchies for Scalable ad hoc Routing,” ACM/Kluwer Wireless Networks （WINET）, vol. 9, no. 5, Sept. 2003,pp. 461-78
H. Frey. “Scalable Geographic Routing Algorithms for Wireless Ad Hoc Networks,” IEEE Network Mag., July/Aug. 2004, pp. 18-22
A. O. Lim, Y. Kado, B. Zhang, and X. Wang,. “A Study of Root Driven Routing Protocol for Wireless LAN Mesh Networks”, To appear in Wireless Internet Conference (WICON 2007), Austin, TX, Oct. 2007