（通信与信息系统专业论文）面向高速交通系统的移动无线网络路由技术研究.pdf

摘要 在高速移动环境下实现宽带无线i p 接入已经成为当前的研究热点和难点，无线 m e s h 网络和移动路由技术是实现高速移动环境下宽带无线i p 接入的关键技术。 论文研究了无线m e s h 网络的路由协议，根据网络中节点的运动规律，将移动 预测的思想与多径路由的不相关性相结合，在动态源路由( d s r ) 协议的基础上， 提出了一种新的基于移动预测的动态多径源路由算法( d m s r m p ) ，并进行了性能 分析。结果表明，d m s r m p 算法可以减少网络拓扑结构的变化对于路由及上层业 务的影响。 论文分析了网络移动基本支持协议( n e m o ) ，考虑高速移动环境下宽带无 线i p 接入的特点，对嵌套移动子网协议进行了改进，提出了适用于多级嵌套的移 动子网中的路由优化机制。 关键词：无线m e s h 网络基于移动预测的动态多径源路由协议网络移动基本 支持协议嵌套移动网络 a bs t r a c t t h ei m p l e m e n to fb r o a d b a n dw i r e l e s si pa c c e s si nt h e h i 曲- s p e e dm o b i l e e n v i r o n m e n th a sb e e nh o tp o i n t sa n dd i f f i c u l ti s s u e s w i r e l e s sm e s hn e t w o r k sa n d m o b i l ew i r e l e s sr o u t i n gt e c h n o l o g ya r et h ek e yt e c h n o l o g i e st oa c h i e v eb r o a d b a n d w i r e l e s si pa c c e s si nh i 曲- s p e e dm o b i l ee n v i r o n m e n t w i r e l e s sm e s hn e t w o r k sr o u t i n gp r o t o c o l sw e r ea n a l y z e di nt h et h e s i s a c c o r d i n g t ot h em o b i l i t yp a t t e r n st h a tm o b i l en o d e se x h i b i t ，an e w d y n a m i cm u l t i p a t hr o u t i n g p r o t o c o l ( d s m r m p ) w h i c hc o m b i n e dt h ei d e ao fm o b i l i t yp r e d i c t i o na n dt h e i r r e l e v a n c eo f m u l t i p l er o u t i n gp a t h sw a sp r e s e n t e d a na n a l y s i so ft h ep e r f o r m a n c eo f t h er o u t i n gp r o t o c o lw a sm a d ei nt h et h e s i s a n dr e s u l t sd e m o n s t r a t e dd s m r m pc a n r e d u c et h ei n f l u e n c e so fr o u t e sa n du p p e rl a y e rs e rv i c ew h i c hw e r ec a u s e db yt h e c h a n g e s i nt h et o p o l o g yo fn e t w o r k s n e t w o r km o b i l i t yb a s i cs u p p o r tp r o t o c o l ( n e m o ) w a sa n a l y z e d c o n s i d e r e dt h e f e a t u r eo fb r o a d b a n dw i r e l e s si pa c c e s s ，t h ei m p r o v e m e n to fn e s t e ds u b n e t w o r k s p r o t o c o lw a sm a d ea n dt h eo p t i m i z a t i o no fr o u t i n gm e c h a n i s mt h a tw a sa p p l i e dt o m u l t i l e v e ln e s t e dm o b i l en e t w o r k s k e y w o r d s ：w i r e l e s sm e s hn e t w o r k d y n a m i cm u l t i - p a t hr o u t i n gs o u r c e p r o t o c o lb a s e dm o b i l i t yp r e d i c t i o nn e t w o r km o b i l i t yb a s i cs u p p o r tp r o t o c o l n e s t e dm o b i l en e t w o r k s 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名： 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 同期堕：兰：仝 日期孚卜 第章绪论 第一章绪论 进入2 l 世纪以来，移动通信进入了飞速发展的时代，人们期望可以随时随地、 ， 及时可靠地进行信息交流。对于高速交通系统的应用环境，无论系统控制，还是 旅客通信，都期望能够使用先进的通信技术，进行可靠、高速的信息传输。本章 首先介绍论文的研究背景，然后阐明无线m e s h 网络和网络移动基本支持协议的研 究现状，最后介绍论文的主要研究内容和结构安排。 1 1 研究背景 随着交通工具的迅速发展和日常生活节奏的加快，人们对交通工具的使用越 来越频繁，耗费在交通工具上的时间比例越来越高，人们在乘坐大型交通工具( 如 轮船，飞机，火车等) 的同时也希望能够接入互联网，享受无时无刻不在的网络服 务。高速化是未来交通系统发展的必然趋势，同时，随着通信技术的不断进步， 将无线移动通信应用于高速移动环境已成为一个重要的发展趋势【l 】。 伴随着无线用户对于高速宽带接入的需求，无线m e s h 网络应运而生。无线 m e s h 网络( w i r e l e s sm e s hn e t w o r k w m n ) ，即无线网状网，是一种新型的无线通信 网络。它具有自组织性和自愈的特点，并具有有效的移动用户管理和跟踪机制， 是一种高容量、高速率的分布式无线网络，它既能提供相对稳定的网络骨干结构， 又允许终端节点以a dh o c 自组织的方式进行组网。它可以和多种宽带无线接入技 术相结合，增加无线系统的覆盖范围，提高无线网络的带宽容量以及通信可靠性， 是“最后一公里 宽带无线接入的一个理想解决方案。 对于高速交通系统上的终端，彼此之间相对拓扑稳定。人们将这些集中移动 的终端看作一个整体，称之为移动网络或网络移动( n e t w o r km o b i l i t y ，n e m o ) 。国 际互联网标准组织i e t f 专门成立了n e m o 工作组，研究一个移动子网作为一个整 体在全球互联网范围内变换接入位置时的移动管理和路由可达性问题。移动网络 内部的拓扑结构相对固定，通过一台或多台移动路由器连接至全球的互联网。网 络的移动对网络内部的节点是完全透明的，即内部节点不需要感知网络的移动， 不需要支持移动功能。 2 面向高速交通系统的移动无线网络路由技术研究 1 2 1 无线m e s h 网络的结构 1 2 无线m e s h 网络 作为无线自组织网络的成员之一，无线m e s h 网络是一种与传统的无线网络完 全不同的网络。传统的无线网络必须首先访问集中的接入点才能进行无线连接。 这样，即使两个节点实际上是互相挨着的，它们也必须通过接入点才能进行通信。 而在无线m e s h 网络中，每个节点都可以与一个或者多个对等节点进行直接通信。 m e s h 网络技术原是一项军方技术，随着人们对无线局域网技术了解的深入，m e s h 网络才逐步成为企业界和消费者瞩目的焦点。 在无线m e s h 网络中包括两种类型的节点：无线m e s h 路由器和无线m e s h 终端。 其中，组成网络骨干的路由器移动性很小，它们提供网状网与其他网络( 如i n t e m e t 、 蜂窝网、传感器网络) 连接的网关和路桥功能；终端可以是静止或是移动的，终 端之间可自己组网或与网状网的路由器共同组网。w m n 的系统结构根据节点功能 的不同分为三类：骨干网m e s h 结构、客户端m e s h 结构、混合结构【2 1 。 ( 1 ) 骨干网m e s h 结构是由m e s h 路由器网状互连形成的，无线m e s h 骨干网再 通过其中的m e s h 路由器与外部网络相连。m e s h 路由器除了具有传统的无线路由 器的网关、中继功能外，还具有支持m e s h 网络互连的路由功能，而且可以通过无 线多跳通信，以低得多的发射功率获得同样的无线覆盖范围。m e s h 路由器通常具 有多个无线接口，这些无线接口可以是基于相同的无线接入技术构建，也可以是 基于不同的无线接入技术。 ( 2 ) 客户端m e s h 结构是由m e s h 终端之间互连可以构成一个小型对等通信网 络，在用户设备间提供点到点的服务。m e s h 终端可以是手提电脑、手机、p d a 等 装有无线网卡、天线的用户设备，。这种结构实际上就是一个a dh o c 网络，可以 在没有或不便使用现有的网络基础设施的情况下提供一种通信支撑。m e s h 终端具 有一定的m e s h 网络互连和分组转发功能，但是一般不具有网关桥接功能。通常， m e s h 终端通常只具有一个无线接口，实现复杂度远小于m e s h 路由器。 ( 3 ) m e s h 终端可以通过m e s h 路由器接入骨干m e s h 网络形成m e s h 网络的混合结 构，骨干网还提供对其他网络，如w i f i 、w i m a x 、蜂窝网和传感器网络接入的 支持。这种结构网络的功能最强，对终端的要求也最高。如图1 1 所示，其中虚线 和实线分别表示无线和有线连接。这种结构提供了与其他一些网络结构的连接， 增强了连接性，扩大了覆盖范围。 第一章绪论 二、 f - 麓陬、 箭严、窍警h 终。基) 。盆遵：2 9 “ 1 2 2 无线m e s h 网络的特点 无线m e s h 网络的特点【3 】包括： ( 1 ) 无线多跳网络。通过降低无线节点的发射功率，实现了节点间的多跳传输， 既有效降低节点能耗，又降低了节点问的干扰，提高了无线信道的空间复用度， 从而提高了网络的容量。 ( 2 ) 具有自组织、自管理、自愈能力。无线网状网组网方式灵活，易于配置， 可自我修复，节点呈网状分布，网络扩展性很强，可实现多点到多点的无线通信。 ( 3 ) 多种网络的接入与融合。接入方式灵活多样。在无线m e s h 网中，既支持 无线终端接入骨干网，又支持无线终端之间的对等网络通信。此外，把无线m e s h 网技术与其他无线网络相结合，可以通过无线m e s h 网给这些无线网络的终端用户 提供无线接入业务。 ( 4 ) 移动性、功耗限制取决于节点类型。无线m e s h 路由器节点的移动性小， 客户端可灵活移动。通常情况下，对路由器节点的耗能没有严格的限制，而对于 客户端节点需要执行功率有效的协议。 ( 5 ) 兼容性及互操作性。与现有无线网络的兼容良好，互操作性强。 4 面向高速交通系统的移动无线网络路由技术研究 1 2 3 无线m e s h 网络的应用场景 无线m e s h 网络主要的应用领域包括： ( 1 ) 宽带家用网 目前的宽带家用网是在i e e e8 0 2 11 w l a n 上实现的，其主要的缺陷是存在某 些服务覆盖不到的通信盲区。为了解决这个问题，通常需要部署多个无线接入点 ( a c c e s sp o i n t ，a p ) ，这种方法花费昂贵，对于家用来说是不切合实际的。而w m n 的一个重要用处就是用于建立家庭无线网络。家庭式无线网状联网可以连接台式 p c 机、笔记本、d v d 播放器、以及其他各种消费类电子设备，而不需要复杂的布 线和安装过程。w m n 应用家庭环境中的另外一个优点是它能够支持带宽高度集中 的应用，如高清晰度视频等。 ( 2 ) 商用网 目前，企业的无线通信系统大都采用无线局域网，但是a p 之间的连接仍然是 通过有线的方式，这无疑大了网络建造成本。而w m n 既可以用于小型办公环境， 也可以应用于大规模企业场所( 比如多个写字楼之间的通信) ，配置灵活、安装和使 用成本低。 ( 3 ) 城域网 无线m e s h 网络的节点传输速率远远大于蜂窝网的节点，并且无需依赖有线骨 干网，这些都是无线m e s h 网络用于组建城域网的优势所在。将可以为政府与市政 应用，为城内公共场所等地的市民提供宽带无线接入。 ( 4 ) 交通系统 通过在汽车，轮船，火车等地方安置无线网状路由器或无线网状终端，基于 无线m e s h 网络的交通系统可以为乘客和驾驶员提供各种各样的服务，比如乘客信 息服务，安全监视，道路交通信息，气象信息，驾驶员通信服务等。但是这种应 用给网状网络的设计提出了新的挑战，因为交通工具一般都是以比较高的速度运 动，所以在设计的时候要充分考虑移动性对网络性能的影响。列车内的通信设备 组成的无线m e s h 网络结构如图1 2 所示。 ( 5 ) 快速部署和临时安装 对于那些需要快速部署或临时安装的地方，如展览会、灾难救援等，无线m e s h 网络无疑是最经济有效的组网方法，特别是在通信基础设施遭受破坏的突发事件 现场更加重要。 第一章绪论 嗍麓 扩一一一一。 9 - 令 - 7 - ， 一，一一，。7 ，n 一- 二n 由一一一一一 一。 ! 虻鼢曩 、， o 。b i 、 彰j 汐 砌陬 图1 2 列车内的无线m e s h 网络结构 1 3 网络移动基本支持协议 随着通信技术的进步，人们需求的变化，简单的终端移动方式已经不能满足 未来应用的要求，网络移动的概念随之诞生，n e m o 解决了m o b i l ei p 中网络移动 支持性的部分问题。 目前，对于互联网移动性管理理论和协议的研究工作基本上是针对移动节点 的。i e t f 标准化了移动i p v 4 协议和移动i p v 6 协议，并相继提出了一系列的相关标准 和草案，实现了对节点移动性的支持。这两个版本的移动i p 协议均采用代理和隧道 技术，通过设置移动节点的当前转交地址与家乡地址的绑定条目提供数据包的收 发功能，是比较典型的面向终端运动的解决方案。移动网络以无线方式作为接入 手段，运动主体是一个相对稳定的网络整体，移动过程中改变的是整个网络的接 入点，移动网络内部可以是简单的网络，也可以是复杂的网络。比如最简单的情 况就是移动网络仅由一个移动路由器和一台主机组成。比较复杂的情况是移动网 络包括多个i p 子网，这些i p 子网通过本地路由器连接在一起，而且，移动网络可以 通过一个或多个移动路由器接入互联网，移动网络内部链接是有有线的形式，也 可以是无线的形式，但通常都保持一个相对稳定的拓扑结构。 移动网络作为一个整体移动，不同于一般子网中移动节点作为独立个体分别 移动，通过移动i p 协议分别进行通信的情况，网络环境要复杂许多： 6 面向高速交通系统的移动无线网络路由技术研究 ( 1 ) 移动网络内的节点不一定都支持移动性协议； ( 2 ) 移动网络内的节点不一定都能感知链路层切换； ( 3 ) 移动网络内可能存在嵌套网络。 需要指出的是，如果大量的节点一起移动，每个移动节点分别通过网络接入 点连接网络，不属于移动网络的范畴，视为多个移动节点进行处理。显然，移动i p v 4 和移动i p v 6 协议不能满足移动网络的需求，难以提供对移动网络的有效移动性管 理，需要针对移动网络的特点设计新型的网络移动性管理方案。 当前，移动网络作为一种提供网络移动性的新方法已经得到广泛的关注，且 必然将得到迅速发展。为了提供对网络整体移动的支持，众多标准化组织和科研 机构投入到网络移动性研究工作。2 0 0 2 年l o 月，i e t f 成立了n e m o t 作组，在移 动i p v 6 协议的基础上开始对移动网络的研究，其工作主要是基于移动i p 的隧道技术 来制定相应的网络移动性协议。2 0 0 5 年1 月，i e t f 正式发布了第一个有关移动网络 的标准：r f c 3 9 6 3 4 】网络移动基本支持协议，标志着对网络移动性的研究和标化准 工作取得了实质性的进展。该协议是基于移动i p v 6 协议的扩展，其定义的移动网络 是指由一个或多个子网组成，能够接入互联网并作为一个整体移动，具有动态改 变网络接入点、保证移动过程中路由可达性能力的网络。移动路由器( m o b i l er o u t e r ， m r ) 作为该移动网络的默认网关接入互联网，并负责维护移动网络内部的移动性管 理。 虽然网络移动基本支持协议很好的解决了移动子网中各种用户的移动通信问 题。但在该协议中，但数据包采用多层隧道封装方式进行传输，效率很低，子网 中的节点和通信对端通信时不支持路由优化，必须使用m r 和其家乡代理( h o m e a g e n t ，h a ) 的双向隧道，而且也未对分层嵌套【5 】的移动子网的操作进行说明，所以 该协议并没有获得最优的通信性能，还有很多值得改进之处。 目前n e m o 的主要研究方向集中在：m r 多家乡问题，m r 的路由优化，安全， 嵌套网络等。 1 4 论文的主要内容和结构安排 论文主要研究面向高速交通系统的无线m e s h 网络的路由问题和移动网络的路 由优化技术，主要包括以下几个方面： ( 1 ) 对无线m e s h 网络和网络移动基本支持协议的研究现状的分析。 ( 2 ) 对当前几种常见的无线m e s h 网络的路由协议和多径路由算法的研究。 ( 3 ) 提出基于移动预测的动态多径源路由算法( d m s r o m p ) ，并对其工作机制 进行详细表述。 ( 4 ) 对网络移动基本支持协议的工作过程进行分析，提出了适用于多级嵌套的 第一章绪论 移动网络的路由优化机制。 论文分为六章，具体安排如下： 第一章是绪论部分，介绍了无线m e s h 网络的结构、特点、应用场景以及网络 移动基本支持协议的研究现状。 第二章对无线m e s h 网络中的路由协议和多径路由算法进行研究。主要以a d h o e 网络的路由协议为参考。 第三章提出了基于移动预测的动态多径源路由算法。 第四章研究了网络移动基本支持协议，提出了多级嵌套的移动子网的路由优 化机制。 第五章是仿真数据和性能分析。 第六章是结束语。 最后是致谢和参考文献。 第二章无线m e s h 网络的路由协议 9 第二章无线m e s h 网络的路由协议 无线m e s h 网络设计中的一个关键问题是开发能够在两个节点之间提供高质量 高效率通信的路由协议。本章首先介绍无线m e s h 网络路由协议的设计要求。重点 研究几种典型的路由协议，最后对无线m e s h 网络路由算法的研究热点一多径路由 加以分析。 2 1 无线m e s h 网络路由协议的设计要求 无线m e s h 网路由协议是无线m e s h 网技术的核心内容之一。网络节点的移动性 使得网络拓扑结构不断变化，传统的基于i n t e m e t 的路由选择协议，如距离矢量方 法的r i p 6 】和链路连接状态方法的o s p f 7 】等不适合在无线m e s h n 络中使用。原因如 下： ( 1 ) 常规路由协议不适应动态变化的网络拓扑结构。常规路由协议是为有线固 定网络设计的。有线网络不会出现大的网络拓扑结构变化，而无线m e s h 网络的网 络拓扑结构会动态变化。常规路由协议通常是没有考虑这一点的。产生的后果就 是在无线m e s h 网络环境中，当网络拓扑结构变化后，常规路由协议需要花费很长 的时间才能到达收敛状态，而拓扑结构可能在达到收敛状态之前又发生了变化。 所以造成这样的一种情况：无线m e s h 网络主机在花费了很高的代价( 如网络带宽、 c p u 资源等) 之后得到了网络的临时拓扑结构，而由于动态变化的拓扑结构导致这 个结果中的大部分内容变得陈旧，协议状态始终处于不收敛状态。 ( 2 ) 无线传输信道与有线传输信道具有不同的特性。自组织网中主机间的无线 信道可能存在单向信道，常规路由协议设计中常常没有考虑这个问题或者必须以 双向链路作为工作的前提假设，由此计算出来的路由可能无法准确反映无线m e s h 网络的拓扑结构，也没有考虑单向信道的存在。此外，某些常规路由协议需要的 复杂计算使得c p u 始终处于很高的负载下，这也同样消耗了大量的能源。这将对 无线m e s h 终端有限的主机能源带来更多的压力。 正是由于传统的基于固定网络的路由选择协议无法适应无线网络的传输需 求，所以有必要设计专用于无线m e s h 网络的路由选择协议。 考虑到无线m e s h 网络结构和特点的特殊性，在设计w m n 路由协议时，必须考 虑以下因素： ( 1 ) 路由判据。现有的很多路由协议均以最小跳数作为路由判据。研究表明， 在大多数情况下，该路由判据的性能并不是最优的【8 9 】。例如两节点之间选择跳数 最小的路径，由于干扰冲突、通信距离等因素的影响，使该路径的链路质量恶化， l o 面向高速交通系统的移动无线网络路由技术研究 端到端的吞吐量、误码率等性能将变得非常差。因此在选择路由路径时就不能只 考虑最小跳数，还应该综合考虑网络的连接质量和往返时延等因素，设计一种合 理的路径选择算法。 ( 2 ) 负载均衡。在w m n 中，所有节点通过路由协议共享网络资源。因此，w m n 路由协议必须满足负载均衡的这一要求。如当网络中某些节点发生拥塞，并成为 整个网络的瓶颈节点时，新的业务流应能“绕过该节点。可以从两个方面来解 决该问题：通过路由发现机制在业务流建立阶段“绕过 网络中的拥塞区；利用 路由维护机制在链路发现拥塞时，自动选择其他路径进行数据传输。此外，以节 点往返时间延迟作为性能判据在一定程度上达到负载均衡的目的。但由于往返时 间延迟受链路质量影响，并不对所有情况都有效。总之，路由判据需要在一定程 度上满足负载均衡的要求。 ( 3 ) 路由容错。w m n 的目标之一就是在出现连接失败的情况下确保网络的健 壮性，也就是说，如果一个连接失败了，路由协议必须很快地选出另外一条路径 以避免出现服务中断。一般有两种重建方法：一种是利用缓存路由进行数据发送； 另一种是通过重新执行路由查找过程实现路由重建。 ( 4 ) 网络容量。随着网络规模的增大，利用广播机制进行路由查找的方法会消 耗很多网络资源。同时，由于大规模网络建立路径时将花费很长时间，使端到端 的延时变大，旦路径建立起来，由于路径发生变化又需要消耗很大的网络资源 进行路由重建。 ( 5 ) 如何在w m n 中为用户提供q o s 保证是一个新的研究课题。特别是对于实 时业务，如何提供q o s 支持更是迫切需要解决。q o s 路由的主要思想是首先需要选择 满足用户各种q o s 要求的到达目的节点的路径；其次，在路径建立后，若当前路径 已经不能满足用户q o s 需求，则节点需要寻找新的路由。 作为w m n 中的关键技术之一，w m n 路由技术将在未来无线宽带领域扮演至 关重要的角色。如何提升w m n 的网络性能，成为w m n 路由协议进一步研究的重 点问题。 2 2 无线m e s h 网络中典型的路由协议 无线m e s h 路由协议基本同a dh o c 网络路由协议，目前几种典型的路由协议有： 目的序列距离矢量路由协议、动态源路由协议、“群首”网关路由协议和a dh o e 按需距离矢量路由协议等。按照路由触发的原理，现有的a dh o c 网络路由协议可 以分为三种：先验式( p r o a c t i v e ) 路由协议、反应式( r e a c t i v e ) 路由协议和混合式路由 协议。 第二章无线m e s h 网络的路由协议 2 2 1 先验式路由协议 先验式路由协议又称为表驱动( t a b l e d r i v e n ) 路由选择协议，它的发现策略与传 统路由协议类似，节点通过周期性地广播路由信息分组，交换路由信息，主动发 现路由。同时，每个节点维护一张或多张表格，这些表格包含到达网络中其它所 有节点的路由信息。当检测到网络拓扑结构发生变化时，节点在网络中发送路由 更新信息。收到更新信息的节点更新自己的表格，以维护一致的、及时的、准确 的路由信息。不同的先验式路由协议的区别在于拓扑更新信息在网络中传输的方 式和需要存储的表的类型。先验式路由协议不断的检测网络拓扑和链路质量的变 化，根据变化更新路由表，所以路由表可以准确地反映网络的拓扑结构。源节点 一旦需要发送报文，可以立即得到到达目的节点的路由。但是周期性的路由更新 需要花费较大开销，而动态变化的拓扑结构可能使得这些路由更新变成过时信息， 路由协议始终处于不收敛状态。所以，先验式路由协议有逐渐被反应式路由协议 所替代的趋势。 在自组织网络路由协议的研究初期，主要思路是修改有线网络的路由协议以 适应在自组织网络环境中运行，这些路由协议大多属于先验式路由协议，包括目 的节点序列距离向量路由协议( d e s t i n a t i o ns e q u e n c e dd i s t a n c ev e c t o rr o u t i n g , d s d v ) 、“群首”网关路由协议( c l u s t e rg a t e w a ys w i t c hr o u t i n g ，c g s r ) 等。下面 对d s d v 和c g s r 进行简要介绍。 ( 1 ) d s d v 是一种基于经典的贝尔曼一福德, ( b e l l m a n f o r d ) 算法【l o 】的先验式路 由协议，它对贝尔曼一福德路由机制的改进主要在于避免在路由表中形成路由环 路。 在这种算法当中，每一个节点维护一张包括网内所有可能目的地和到它们的 路由跳数的路由表，表的内容为路由的“下一跳 节点。每一条记录带有一定的 序列号标记，该序列号是由目标节点分配的。这一序列号使得移动节点可以区分 过时的路由和最近的路由，从而可以避免路由环的形成。 路由表周期性地做全网更新以维护全网的通信有效性。通常，为了减少由于 路由表更新而产生的大量路由信息传递，减少网络路由开销，可以采用两种路由 更新方式。第一种是全清除方式( f u l ld u m p ) ，即通过多个网络协议数据单元将路由 更新信息在全网中传输。如果网络内终端出现移动，则产生的新路由分组信息不 定期地传达至网络内所有终端。第二种是部分更新方式( i n c r e m e n t a l ) ，即在最后一 次全清除传输后，只传递那些涉及变化了的路由信息传输，这些信息通常被放置 在一个标准网络协议数据单元里，从而减少路由信息的传递量。新路由信息的广 播信息包含目标节点的地址、到每个目标节点的跳进次数、接收信息的序列号， 以及独有的广播序列号。新路由信息使用最新的序列号。如果两次更新具有相同 1 2 面向高速交通系统的移动无线网络路由技术研究 的序列号，则具有跳数较小的那条路由。 ( 2 ) c g s r 是一种典型的基于簇的分级路由。它利用一个稳定的分簇算法来将 整个网络分成多个簇，并且在每个簇中选举一个簇头。簇和簇之间的连接是通过 分别属于两个或多个簇的网关节点来实现的，这里所谓的网关节点是指在两个或者 更多簇首的通信范围内的节点。在任何需要通信的源节点和目的节点之间的数据 包都是以“簇头网关簇头。网关的形式传送。 c g s r 将d s d v 作为下层的协议，因此许多协议头与d s d v 相同。每个移动节 点维护两张表，一张是簇成员表，另一个是距离矢量路由表。簇成员表中记录了 网络中每个节点所在簇的簇头，并周期性地广播这张表。接收到这个广播包的节 点可以根据它来更新自己的簇成员表。在路由表中，对每个簇只记录一条到达它 的簇头的路由信息。为了路由一个数据包，当前节点首先在簇成员表中查找目的 节点所在簇的簇头，然后它会在路由表中查找到达目的簇的下一跳路由( 即下一个 簇头) 。到达目的簇头后，由目的簇头把数据包发送给目的节点。 c g s r 的一个主要优点是相比较一般距离矢量协议，它大大减少了路由表的大 小。因为对于同一个簇内的所有节点在路由表中只需要一条记录，这样路由表的 广播包大小也相应地减少。这些特性使得c g s r 可以适合于大的移动m e s h 网络。虽 然在每个节点要多维护一张簇成员表，这个表的大小只决定于网络中簇的多少。 c g s r 的缺点是在一个移动环境中维护簇结构比较困难。分簇算法增加了额外的 开销和复杂性。 2 2 2 反应式路由协议 反应式路由又称为按需( o n d e m a n d ) 路由，是一种当需要发送数据分组时才查 找路径的路由算法。在这类路由协议中，节点不需要维护即时准确的路由信息， 当向目的节点发送数据分组时，源节点才一开始路由发现操作以找到相应的路径。 按需路由主要由路由发现( r o u t ed i s c o v e r y ) 和路由维护( r o u t em a i n t e n a n c e ) 两部分 组成。路由发现的目的在于发现从源节点到达目的节点的路由，源节点通过广播 路由请求分组发起路由发现过程。路由发现过程可以划分为如下几个子过程：路 由请求( r o m er e q u e s t ，r r e q ) 发送、路由请求转发、路由应答( r o u t er e p l y , r r e p ) 发送和路由应答转发。当正在进行通信的路由失效后，节点会通过路由维护进行 路由的切换。与先验式路由协议相比，反应式路由协议不需要周期性的路由信息 广播，降低了对网络带宽和能量的过度消耗。但是当节点需要发送数据分组时， 如果没有去往目的节点的路由，数据分组需要等待因路由发现引起的延时。典型 的反应式路由协议有动态源路由协议( d y n a m i cs o u r c er o u t i n g ，d s r ) 、a dh o c 按需 距离矢量路由协( a dh o co n d e m a n dd i s t a n c ev e c t o rr o u t i n & a o d v ) 等。下面对 第二章无线m e s h 网络的路由协议 d s r 和a o d v 进行简要介绍。 ( 1 ) d s r i l l 】是一种基于源路由的按需路由协议，它使用源路由算法而不是逐跳 路由的方法。每一个分组的分组头中包含整条路由的信息，其优点是中间节点不 需要维持当前的路由信息，分组自己带有路由信息。 d s r 协议包括两个过程：路由发现和路由维护。路由发现过程使用泛洪路由 ( f l o o d i n gr o u t i n g ) 。当源节点s 向目的节点d 发送数据时，它首先检查缓存是否存在 未过期的到目的节点的路由，如果存在，则直接使用可用的路由，否则启动路由 发现过程。具体过程如下：源节点s 使用泛洪法发送路由请求报文，该r r e q 包括 源节点的地址、目的节点的地址、请求序列号i d 、路由记录。其中“路由记录 字段用于记录从源节点到目的节点路由中的中间节点地址，当路由请求报文到达 目的节点时，该字段中的所有节点地址即构成了从源节点到目的节点的路由。“请 求i d 字段由源节点管理，中间节点维护 源节点地址，请求i d 序列对列表， 源 节点地址，请求i d 序列用于惟一标识一个r r e q ，以防止收到重复的路由请求。 每个接收至t j r r e q 的节点首先检查自己是否是目的节点。如果是，则向源节点发送 一个路由应答信息报文；如果不是，将自己的地址添j i l l 至t j r r e q 的路径记录中，然 后继续转发。为了限铝t j r r e q 在网络中的无限广播，收至i j r r e q 的节点只转发那些 新的、从没有收到过的和无自身地址的报文。对于已有自身地址的数据报文，则 不予处理。因此，在转发之前必须检查路由记录表中是否己包括本节点地址。r r e q 在转发过程中，有两种可能的途径可以发现目的节点：其一是报文转发到目的节 点，转发停止；其二是报文转发到某个中间节点，该节点缓存有效的、能够到达 目的节点的路由信息，则转发亦停止。无论是那种情况，目的节点或中间节点都 给源节点发送一个r r e p 。 如图2 1 所示，虽然节点e 、g 、d 可能接收到多次r r e q ，但只有最早到达的 达的才可能被这些节点做有效处理，并给出处理结果，即继续转发或给出应答信 息。 图2 1d s r 路由发现过程中的路由记录 无线链路 r r e q 传输路径 1 4 面向高速交通系统的移动无线网络路由技术研究 当建立一条路径信息的时候，如果发送r r e p 的是目的节点，则它直接将r r e q 中路由记录表中的内容放至i j r r e p 中。如果是某个中间节点发送了r r e p ，它将 r r e q 中的路由记录和它自己高速缓存中记录的路由信息合并在一起，放入r r e p 中。为有效地将r r e p 传回源节点，发送节点需要一条可到达源节点的路径，这条 路径可能存在于发送节点的高速缓存中，如果没有，它就必须通过以下措施来建 立：如果网络支持对称传输，则它就利用r r e q q h 路由记录表的内容，沿相反的顺 序传输；如果网络不支持对称传输，它就启动自己的路由建立过程，建立路由路 径。 如图2 2 所示，目的节点d 向原节点发送r r e p ，网络中允许对称传输，所以应 答信息沿所发现路由的反向路径传输。假定s a efd 代表最小跳数路由。 图2 2d s r 路由发现过程中的路由戍答 在路由建立之后，进入数据传递和路由的维护过程。当传输链路发生严重的 错误时，中间节点可以使用缓存中的可用路由来代替含有失败链路的原路由，同 时，向源节点发送路由错误报文( r o u t ee r r o r r r e r ) 。监听到路由错误报文的节点 删除失败路由来减小缓存错误路由信息的影响。如果路由失败，则由源节点重新 开始一次新的路由发现过程。除了路由错误分组报文之外，网络也建立正确连接 的确认机制，比如一个节点具备确认下一个节点是否能够成功转发数据报文的能 力。如果节点在传输数据报文的过程中，发现数据报头部的源路由中包括自己的 地址，例如由于拓扑变化而产生更短的路由，可以主动发送路由响应报文告知源 节点存在更短路由。 ( 2 ) a o d v 1 2 是d s d v 算法的改进，但它与d s d v 的区别在于它是反应式路由协 议。与d s r 协议相同，a o d v 协议包括两个过程：路由发现和路由维护。当源节点 没有到达目的节点的已知路由时，广播一个路由请求报文。接收到该请求的中间 节点反向记录下指向源节点的目的向量，然后向周围节点广播此请求报文直到该 分组被送到一个知道目的节点路由信息中间节点或目的节点本身。一个节点将丢 嬲 一 第二章无线m e s h 网络的路由协议 弃重复收到的请求分组，路由请求分组中的序列号是用来防止路由环路的，并能 判断中间节点是否响应了相应的路由请求。当路由请求报文到达目的节点时，目 的节点利用记录在报文中的反向目的向量为路由发送路由响应报文。如果中间节 点知道最新的指向目的节点的路由，它就代替目的节点直接发送路由响应报文。 当路由响应报文返回源节点时，每个中间节点相应产生“正向 目的向量，源节， 点就可以沿着新建立的路由开始发送数据。 图2 3 和2 4 为a o d v 中的路由发现过程中，包括建立反向路由和建立正向路由 两个过程。 图2 3a o d v 路由发现过程中反向路由的建立 正向路由的建立 无线链路 图2 4a o d v 路由发现过程中正向路由的建立 a o d v 的目的向量算法仍然可能产生路由环。与d s d v 类似，a o d v 采用由目 的节点产生的序列号来保证路由的时效性。每个路由请求报文都标记源节点可以 从目的节点获得的最大序列号。当且仅当中间节点记录的指向目的节点的路由的 序列号大于等于请求报文中的序列号并且该路由仍然有效时，中间节点才可以代 替目的节点向源节点发送路由响应报文。如果是由目的节点发送路由响应报文， 则该报文中的序列号反应了目的节点所知的最新的拓扑变化。 1 6 面向高速交通系统的移动无线网络路由技术研究 在路由建立之后，进入路由维护过程。在路由维护过程中，a o d v 协议使用了 一种周期性广播h e l l o 报文，以检测节点周边链路的变更情况。h e l l o 报文是一种非 常小的控制报文，对它的周期性广播和接收不会造成节点能量和网络有效带宽的 巨大浪费。并且，通过接收周边节点( 一跳距离内) 的h e l l o 报文，节点维护一张邻居 节点列表，当恰好需要与邻居节点通信时，省去了不必要的建立路径泛洪广播。 当节点发现某条链路失败时，发出主动的路由错误分组到使用该链路的每个邻居 节点，将报文中距离设为无穷大并将序列号m i l l 。该路由错误分组将到达所有使用 到这条失败链路的源节点，从而在源节点引发新的路由发现过程。目的节点检测 到与其相连的链路发生错误时，将其序列号加l ，但不产生主动的路由错误分组。 2 2 3 混合式路由协议 混合式路由是将前面二者结合起来，在局部范围内使用先验式路由协议，可 以维护准确的路由信息，并可缩小路由控制消息传播的范围；当目标节点较远时， 则可以使用反应式路由协议查找发现路由。这样既可以减少路由协议的开销，时 延特性也得到了改善，如分区区域路由协议( z o n er o u t i n gp r o t o c 0 1 z r p ) 协议。 z r p 1 3 】协议是第一个混合使用先验式和反应式路由策略的路由协议。在z r p 协议中，网络内的所有节点都有一个以自己为中心的虚拟区；区内的节点数与设 定的区半径有关，因此区是重叠的，这是与分层路由的区别；在区内使用先验式 路由算法，中心节点使用区内路由协议维持一个到区内其他成员的路由表，对区 外节点的路由使用按需路由，利用区间路由协议建立临时的路由。混合式路由综 合考虑了先验式和反应式路由的优点，它能在尽量减少分组时延的前提下降低路 由的开销，必将是无线自组织网络路由协议研究的一个热点方向。但是，要实施 混合式路由还面临着很多困难，如族的选择和维护、区内先验式路由和区外反应 式路由协议的合理选择等必须解决的问题。 2 3 各种协议之间的比较 2 3 1 先验式路由协议和反应式路由协议的比较 在先验式路由协议中，不管有无通信需求，都要在网络内广播路由更新消息 来掌握网路自然拓扑结构及其发生的变化，更新路由信息。源节点一旦要发送报 文，可以立即获得到达目的节点的路由，寻路所需的时延较小，而且通过这些拓 扑信息，比较容易实现路由的优化及q o s 路由。但是路由更新需要的开销较大，而 且动态变化的拓扑结构可能使路由信息过时，不易收敛。 第一二章无线m e s h 网络的路由协议 1 7 在反应式路由协议中，j t i d s r 、a o d v 等，只有在需要一条路径时才开始建立。 如果节点在发送分组时没有到目的节点的路由时，需要启动相应的路由发现机制 搜寻路由，这样将会产生一定的时延，不利于实时业务的传输。 随着网络规模的扩大，节点移动速度的增加，网络的拓扑变化更加频繁，要 想用先验式路由协议实时维护拓扑结构需要大量的、频繁的路由更新信息，这些 控制信息将会占用大量的无线信道资源，从而影响用户数据报文的发送，降低系 统的吞吐量；尤其是在网络拓扑结构变化较频繁的环境中，可能路由算法还没有 收敛时，网络的拓扑结构就又发生了变化，严重影响了用户数据的传输。 因此，在高速移动的m e s h 网络环境中，拓扑变化频繁应采用反应式路由协议； 而在网络拓扑结构相对稳定的环境中，如果业务对实时性要求较高时，应尽量采 用先验式路由协议。先验式路由协议和反应式路由协议的路由延迟、控制开销、 耗电量和带宽开销的比较如表2 1 所示。 表2 1 先验式路由协议与反应式路由协议的性能比较 先验式路由协议反应式路由协议 路由获取延迟低高 控制开销 高 低 耗电量高低 带宽开小高低 2 3 2 a o d v 和d s r 的比较 a