（通信与信息系统专业论文）无线网状网络的流量均衡路由技术研究.pdf

摘要 摘要 无线网状网络是一种高速率、高容量的多点对多点网络，是一种新型的解决 “最后一英里”问题的分布式网络，可以把它看成是a dh o c 网络的特殊版本。近些 年来，w l a n 得到定的发展，但是w l a n 接入点覆盖范围比较有限，若要在一 个较大区域内布设w l a n ，则需要配置多个接入点，这样会增加网络成本。而无 线网状网络可以克服这种缺陷，因为在无线网状网络中，每一个节点均可转发数 据，这样，就可以延伸传输距离。路由是无线网状网络中的一项关键技术。本文 主要针对无线网状网络中以流量均衡为目的的路由协议进行了深入研究。 本文提出了一种以流量均衡为目的的路由算法c l l b r ( c r o s s i n gl a y e rl o a d b a l a n c er o u t i n g ) 。该算法是一种典型的按需路由算法，它利用r r e q 分组携带路径 负载信息，由目的节点根据这些信息选择最优路径逆向发送r r e p 分组，来告知源 节点目前最优的传输路径。c l l b r 是在保持最短路径的约束条件下，增加了最轻 负载和最小负载均衡度这两个约束条件，因此可以根据网络节点当前的业务量， 动态的选择最佳路径，降低网络的平均时延，提高网络吞吐量。 关键词：无线网状网络路由协议流量均衡节点负载 摘要 a b s t r a c t w i r e l e s sm e s hn e t w o r ki sah i g hb i t - r a t ea n dh i g h c a p a b i l i t yn e t w o r k ，i ti san e w d i s t r i b u t e dn e t w o r ka s “t h el a s tm i l e ”r e s o l u t i o n a n di tc a nb ec o n s i d e r e da sas i m p l e v e r s i o no f a dh o en e t w o r k f o rr e c e n ty e a r s ，w l a nh a sd e v e l o p e dw e l l ，b u td u et ot h e l i m i t a t i o no ft h ec o v e r a g er a n g eo fi t sa p , l o t so fa p sa l er e q u i r e dt os e tw l a nf o ra l a r g ea r e a , w h i c hw i l lb ee x p e n s i v e w i r e l e s sm e s hn e t w o r k ( w m n ) c o u l d s o l v et h i s p r o b l e m b e c a u s ee a c hn o d ei nw m n c o u l dt r a n s f e rd a t aa n dt h i sc o u l de x p a n dt h e t r a n s m i s s i o nd i s t a n c eo fw l a n r o u t i n gi sa ni m p o r t a n tt e c h n o l o g yi nw i v l n i nt h i s t h e s i s ，t h er o u t i n gp r o t o c o lw h o s ea i mi sa tl o a db a l a n c ei nw i r e l e s sm e s hn e t w o r ki s s t u d i e d an o v dr o u t i n gp r o t o c o l - c l l b rw i t ht h ec a p a c i t yo f l o a db a l a n c ei sp r o p o s e di n t h i sp a p e r t h i sa l g o r i t h mi sat y p i c a lo n - d e m a n dr o u t i n gp r o t o c 0 1 u s i n gc l l b rt h e d e s t i n a t i o nn o d ec a l ls e l e c tt h el o w e s tl o a dp a t ha n dr e p l ya nr r e pp a c k e tt os o u r c e n o d ea c c o r d i n gt ot h el o a di n f o r m a t i o nc a r r i e db yr r e qp a c k e t ，a n dt h i sc o u l dm a k e t h es o u r c en o d ea w a r et h eb e s tr o u t ep a t hi nt h en e t w o r lc l l b rr o u t i n gp r o t o c o li s m a d eb yf o l l o w i n gc o n s t r a i nc o n d i t i o n s ，t h es h o r t e s tp a t h ，t h el e a s tl o a da n dt h el e a s t l o a db a l a n c ed e g r e e s oc l l b rc o u l ds e l e c tt h eb e s tr o u t i n gp a t ha c c o r d i n gt ot h e c u r r e n tl o a dd i s t r i b u t i o no ft h en e t w o r k , i tc o u l dd e c r e a s et h ea v e r a g ep a c k e t t r a n s m i s s i o nd e l a ya n dr a i s et h et h r o u g h p u to f t h ew m n k e y w o r d ：w i r e l e s sm e s hn e t w o r k ( w m n )r o u t i n gp r o t o c o l l o a db a l a n c e n o d el o a d 独创性( 或创新性) 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学 或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：吕当建日期塑堡：坦 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研 究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证 毕业离校后，发表论文或使用论文( 与学位论文相关) 工作成果时署名单位仍然 为西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文： 学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段 保存论文。( 保密的论文在解密后遵守此规定) 本人签名：虽当远日期丝堕：理 导师签名： 鹰善捧 日期 第一章绪论 第一章绪论 1 1 研究背景与意义 1 9 9 7 年，美国d a r p a 开始组织战场鲁棒战术移动通信系统的研发。在投入 大量资金、持续6 年多的研发之后，有关移动a dh o c 网络的一些理论与技术问题 得以解决，从而彻底改变了过去构建无线网络的规则。d a r p a 的目标是：无传统 的通信基础设置；采用多跳转发的传输机制；宽带数据数率传输：端到端的i p 支 持；除了数据业务以外，还要支持话音和视频业务；内置定位系统( 非g p s 系统) ； 能支持高达2 5 0 英里，j 、时的车辆移动速度等。特别是近几年，美国通过一些大型 国防项目，攻克了a d h o e 网络的一些关键技术，其中，i t t 持有了其中的核心的 自主知识产权技术。可是，除了战术无线通信以外，真正的商业应用在那里? 这是 业界一直困惑的一个问题。2 0 0 0 年初，i t t 将专有技术转让给了美国 m e s h n e t w o r k s ，用于商业化产品的开发，至此，a d h o e 网络的商业化进程开始显 现。2 0 0 2 年，i n t e l 开始关注并认可a dh o e 网络技术，m e s h n e t w o r k s 和t r o p o s 等 公司开始相继开发出适用于商业应用的相关产品。这些产品和方案主要定位于移 动性较小或静止的a dh o e 网络无线网状网络( w 沁l e s sm e s hn e t w o r k s ， w m n s ) 。于是，无线m e s h 网络的概念得到人们的关注。f l v n s 是无线自组织 网络( a dh o e ) 的一种特殊形态，它的早期研究均源于移动a dh o e 网络的研究与 开发。 近年来，w l a n 依其所具有的巨大数据传输速率在接入领域中得到了迅速发 展，但、地a n 最主要的一个不足之处是其接入点的覆盖范围较为有限，若要在一 个相对较大的区域提供无线覆盖，就需要在该地区内配置多个接入点，因而增加 了建设基于w l a n 的公共宽带网的成本。虽然人们对此提出了一些解决方法，如 通过多种无线技术的共存来提高无线的覆盖和位置的适应性等等，但这些方法中 大多是以增加接入点或降低网络运行效率为代价。于是人们把目光转向了无线网 状网络，希望通过这种全新的网络结构来克服传统无线网络中所存在的固有缺点， 实现无线宽带领域中的一次变革。它是一种高容量高速率的分布式网络，不同于 传统的无线网络，可以看成是一种w l a n 和a dh o e 网络的融合，且发挥了两者 的优势，作为一种可以解决“最后一公里”瓶颈问题的新型网络结构l j j 。 与传统的w l a n 相比，无线m e s h 网络具有几个无可比拟的优势： 1 快速部署和易于安装。安装m e s h 节点非常简单，只要将设备接上电就可 以直接使用。由于极大地简化了安装，用户可以很容易增加新的节点来扩 无线网状网络的流量均衡路由技术研究 大无线网络的覆盖范围和网络容量。 2 非视距传输( n l o s ) 。利用无线m e s h 技术可以很容易实现n l o s 配置，因 此在室外和公共场所有着广泛的应用前景。无线m e s h 网络非视距传输的 特性大大扩展了无线宽带的应用领域和覆盖范围。 3 健壮性。实现网络健壮性通常的方法是使用多路由器来传输数据。如果某 个路由器发生故障，信息由其它路由器通过备用路径传送。m e s h 网络比 单跳网络更加健壮，因为它不依赖于某个单一节点的性能。在单跳网络中， 如果节点a p 出现故障，则整个网络也就随之瘫痪。而在m e s h 网络结构中， 由于每个节点都有一条或几条传送数据的路径，如果最近的节点出现故障 或者受到干扰，数据包将自动路由到备用路径继续进行传输，整个网络的 运行不会受到影响。 4 结构灵活。在单跳网络中，设备必须共享a p ，如果几个设备要同时访问 网络，就可能产生通信拥塞并导致系统的运行速度降低。而在多条网络中， 设备可以通过不同节点同时连接到网络，因此不会导致系统性能的降低。 m e s h 网络还可提供通信负载平衡功能。在无线m e s h 网络中，每个设备都 有多个传输路径可用，网络可以根据每个节点的通信负载情况动态地分配 通信路由，从而有效地避免了节点的拥塞，而目前的单跳网络并不能动态 地处理通信干扰和接入点的超载问题。 5 高带宽。无线通信的物理特性决定了通信传输的距离越短就越容易获得高 带宽，因为随着无线传输距离的增加，各种干扰和其它导致数据丢失的因 素随之增加。因此选择经多个短跳来传输数据将是获得更高网络带宽的一 种有效方法，而这正是m e s h 网络的优势所在。在m e s h 网络中，一个节点 不仅能传送和接收信息，还能充当路由器对其附近节点转发信息，随着更 多节点的相互连接和可能的路径数量的增加，总的带宽也大大增加。 无线m e s h 网络是一种与传统的无线网络完全不同的网络。传统的无线网络必 须首先访问集中的接入点( a p ) 才能进行无线连接。这样的话，即使两个物理位 置相邻的8 0 2 1 l b 的节点，它们也必须通过接入点才能进行通信。而在无线m e s h 网 络中，每个节点都可以与一个或者多个对等节点进行直接通信。“m e s h ”这个词原 来的意思就是指所有的节点都互相连接，当然实际上绝大多数现代的m e s h 网络只 是通过部分节点相互连接。m e s h 网络技术一度曾是一项军方技术，随着人们对 8 0 2 1 l a 、b g l g 等l a n 技术了解的深入，m e s h 网络才逐步成为企业界和消费者瞩目 的焦点。w m n s 作为一种新型的应用网络，因其自身特点以及在家庭、企业和公 共场所等诸多领域广阔的应用前景，因此具有重要的理论意义和实际意义。 第章绪论 1 2 无线m e s h 网络的技术特性 无线网状网络是由网状路由器( m e s hr o u t e r ) 和网状终端( m e s hc l i e n t ) 这两 种网络实体组成的。其中网状路由器一般情况下是固定的并且组成了整个无线网 状网络的骨干网，它们具有路由及数据转发的功能，并且担任着连接无线网络和 有线网络( 如i n t e m e t ) 以及使用不同无线协议( 如8 0 2 1 l ，8 0 2 1 5 ，8 0 2 1 6 ) 的无 线网络的网关和桥接功能。网状终端可以是静止的或是移动的，它同样具备路由 及数据转发的功能，但是不具备网关功能，它既是业务的使用者也是业务的提供 者。终端节点可以通过其它相邻终端节点或路由器以多跳的方式实现骨干网的接 入，从而增强了网络的覆盖能力。w 仆i s 可以看成是一种特殊的w l a n ，除移动 性较低外，w m n s 本质上是一种a dh o e 网络。目前主要观点认为，w 州s 是一种 由无线链路连接路由器和终端设备的静态无线网络，是i n t e r n e t 的无线版本。作为 一种新型网络结构形态，w m n s 结构已经被纳入n 8 0 2 1 6 ，8 0 2 1 6 e ，8 0 2 ，l l s 等标 准中。 无线网状网络的几个关键技术问题需进一步研究解决，这些问题包括： ( 1 ) 天线技术 为了进一步提高传输速率和性能，一些新的带宽传输调制技术比如o f d m 、 u w b 已经开始应用到实际系统中了。无线网状网络中一个重要的问题就是天线的 使用问题，因为每个节点必须和各个方向上的多个节点通信，很简单的一种方式 就是采用全向天线，但是这样覆盖范围有限，并会带来干扰，导致频谱效率下降， 网络容量减小，所以不建议采用全向天线。目前很多的新的天线技术已经浮出水 面，为w m n s 天线技术提供了很多解决方案。这些新的技术主要包括：方向天线， 智能天线，多输入多输出系统( m i m 0 ) ，可重配置天线，频率感知天线，软天线 等。尽管其中很多技术仍处于起步阶段，但是预期将被以后无线网络广泛应用。 ( 2 ) 媒体接入控制技术 为了更好的利用新的物理层技术带来的优势，高层协议特别是m a c 层协议应 该更好的被设计以充分发挥整个系统的性能。无线网状网络m a c 层协议与传统的 无线网络有很大的区别，主要表现在：无线网状网络的m a c 层协议设计时要考虑 多跳方式下的通信，从而存在隐藏终端、暴露终端等问题；无线网状网络是一种 多点对多点的分布式的通信网络，网络中没有控制中心用于协调节点间的通信， 所以m a c 层协议必须保证所有节点能够协同工作；节点移动性对m a c 性能的影 响；因为无线网状网络中节点的特点，那些负责连接支持不同无线协议的网状路 由器的m a c 层必须要保证能够使得支持8 0 2 1 l ，8 0 2 1 6 ，8 0 2 1 5 等协议的节点无 无线网状网络的流量均衡路由技术研究 缝的工作。目前国外对m a c 层的研究主要集中在如何提高系统容量吞吐量以及公 平性等方面上，此外很多论文都是针对多信道或多网卡的m a c 层设计。 ( 3 ) 路由选择技术 w m n s 另外一个很重要的问题是路由选择，例如从节点a 到节点b ，可以经 过不同的用户站中转，存在多条路径，于是选择哪条路径就成为一个关键问题， 这将直接影响系统的性能。而且，当节点增加或是减少时，无线m e s h 网络的拓扑 结构会发生变化，路由选择问题变得更加复杂。采用无线m e s h 还会带来“隐藏终 端”问题，这些都需要进一步研究解决。对于a dh o c 网络和w m n s ，目前还没有正 式的路由协议标准。这两种网络的路由协议既有相同点又有区别，在路由协议的 设计上，要根据具体情况进行专门的设计。 ( 4 ) 动态带宽分配技术及q o s 保障 宽带无线接入系统的频谱资源有限，因此必须使信道资源尽可能被充分利用。 在i e e e8 0 2 1 6 标准中规定的点到多点( p m p ) 宽带无线接入网络中采用了动态按 需时分多址分配d a m at d m a 方式，在这种网络中资源的管理和分配由基站负 责。而在i e e e8 0 2 1 6 a 标准中规定，对于基于无线m e s h 技术的宽带接入网络，带 宽的分配可以采用集中调度方式，或者采用分布调度方式。如果采用集中调度方 式，由m e s hb s 节点收集所有m e s hs s 节点的资源请求信息，分别为它们分配一 定数量的带宽资源。如果采用分布调度方式，包括m e s hb s 和m e s hs s 在内的所 有节点应该相互协调，充分利用资源。任何一个节点发送数据时，不能和两跳以 内的邻近区域的其它节点发送的数据产生碰撞。不同于a dh o c 网络，w m n s 主要 应用在宽带服务中，所以除了端到端延时和公平性等性能参数需要保证外，还要 满足很多其它q o s 参数。 1 3 本文主要研究内容 我们首先讲述了无线网状网络现有的经典路由协议，然后对这些路由协议进 行分类讨论，并给出其适用的工作环境。接着我们简单介绍了现有的流量均衡算 法，着重分析了它们的负载衡量方法和为了改善路由性能所采取的优化手段。最 后我们在d s r 路由的基础上，根据无线网络其自身的特点提出了新的以流量均衡 为目的的路由协议c l l b r ，最后对其性能进行分析。 第一二章无线网状网络路由协议分析 第二章无线网状网络路由协议分析 在第一章中我们提到w m n 是a dh o e 网络的一种特殊形式，因此w m n 可 以借鉴a dh o e 网络的路由协议。移动a dh o c 网络中的路由技术给网络的设计和 维护都提出了严峻的考验，这主要由于a dh o c 网络自身的限制，如节点的移动 性、动态的网络拓扑结构、节点能量受限、传输带宽受限、链路容量时变性和高 误码率等等。a dh o c 网络的路由必须受到多重约束条件，必须能够在动态环境下， 保证数据的可靠传输。如表2 1 所示，a d h o e 网络的路由协议大致可以分为以下 三类： 1 平面式路由，即网络中的所有节点都处于同一层次上，各节点获得的网络路 由信息基本相同。我们又根据其设计的具体原则进一步将平面式路由分为表 驱动路由算法和按需路由算法。 2 分层式路由，即网络按一定的规则划分为多个不同的层次，在不同层次中又 可以有不同的路由策略。 3 基于地理位置辅助的路由协议，即网络中的节点可以获得节点的地理位置信 息，通过这些信息可以有效的减低路由算法中用户用于路由建立和维护的开 销。 表2 - 1a dh o e 网络路由协议分类 a d h o c 路由协议 平面式路由分层式路由地理位置辅助的路由 表驱动路由按需路由 d s d va o d vz r pg e o c a s w r pd s r h s rl a r f s rt o r a c g s rd r e a m f s l ss s rl a n m a rg p s r 下面我们简要讨论一下各类不同路由协议。 2 1 表驱动路由 表驱动路由要求网络中每一个节点至少用一个或多个路由表来存储到整个网 络中任一节点的路由信息。当网络拓扑发生变化时，网络中节点需要将拓扑变化 传送到整个网络，收到该信息的节点更新自己的路由表信息，从而保证每个节点 无线网状网络的流量均衡路由技术研究 所保存的网络路由信息是一致的，最新的，准确的。 表驱动路由的路由表可以准确的反映网络的拓扑结构，源节点一旦有数据分 组要发送，可以立即获得到达目的节点的路由。因此这种路由协议的反应时延较 小，但是表驱动路由协议有一个显著的缺陷在于资源的浪费，每一节点都会维护 一张到达网络中所有节点的路由表，其中有很多路由信息并不需要，且更新这些 不需要的路由信息要进行信息交换，这样就造成了资源的浪费。当网络变化较大 的时候，会产生大量的控制信息( 指为了维护路由信息而产生的分组) ，且所有的 控制信息都要广播遍整个网络，这样会造成大量的额外开销，这是我们所不希望 看到的。 不同的表驱动路由协议的区别在于用于存储路由信息的表的个数不同和将网 络拓扑变化广播至整个网络方式的不同。典型的表驱动路由协议有d s d v 、c g s r 和w r p 。 表驱动路由主要有两部分组成： 1 路由表建立； 2 路由表维护。 下面我们从这两个方面对表驱动路由进行分析。 2 1 1 d s d v ( d e s t i n a t i o n s e q u e n c e dd i s t a n c e - v e c t o rr o u t i n g ) 目的节点排序距离向量路由协议d s d v l 2 】是传统的b e l l m a n f o r d 路由协议的改 进。其工作原理是：每一个节点均维护一个到网络中任一节点的路由表，表的内 容为路由的“下一跳”节点。在此方案中，网络内所有的移动终端都建立一个路由表， 包括所有的目标节点和到达各个目标节点的跳数。同时每条路由信息都包含一个 序列号，序列号使移动终端可以区分当前有效路由路径和已过时的路由路径。 ( 1 ) 路由表建立 在组网阶段或有新节点加入时，节点通过广播来告诉其它节点自己的存在， 邻居节点收到这个广播分组后就将信息插到路由表中，并立即广播新的路由表， 这样经过一段时间后，每个节点均可建立一个完整的路由表，表中包括了到网络 内部所有可能目的节点的路由。 路由表包含如下信息：目的地址、下一跳地址、路由跳数、发送序列号以及 路由建立时间和路由稳定时间。 但) 路由表的维护 在a dh o c n 络中节点之间主要是通过传播路由更新分组来维护路由，每个节 第一二章无线网状网络路由协议分析 点周期性地在全网广播路由更新分组，把完整的路由信息发送给邻居节点。考虑 到节点收到的更新信息可能是过期的，因此在目的节点端，每个路由表项都被赋 予一个序列号。节点广播路由更新分组时，将自己的序列号加偶数再发出去。邻 居节点收到更新分组后，先来比较一下序列号，如果序列号大于路由表中相应目 的节点的序列号，则删除旧的信息，添加这条新的信息；如果相等，就比较跳数 值，选择跳数小的：否则忽略更新分组，保留原路由表。 由于d s d v 依靠周期性的广播机制进行路由，所以一条有效路由的建立是需 要收敛时间的。如果在静止的网络中，该收敛时间可以忽略不计。然而在拓扑变化 频繁的a dh o c 网络中，收敛时间会有所增加。 为了减少周期性广播给整个网络带来的大量控制开销，该协议采用了两种不 同包格式一种称为完整更新，它包含整个路由表的信息；另一种称为增量更新， 只携带在最后一次完全更新后发生改变的路由表信息。完全更新用于网络拓扑经 常变化时；而增量更新用于网络拓扑不经常变化的时候，从而使得路由协议的控 制开销减少。但是使用增量跟新时，节点需要另外维护一张增量路由信息表，以 保存增量更新发送的路由信息。 2 1 2 w r p ( w i r e l e s sr o u t i n gp r o t o c 0 1 ) 无线路由协议w r p 3 i 是一距离矢量路由协议。每个节点都维护以下四个表： 1 距离表：记录通过其每个邻节点到达任意目的节点的跳数以及每个目的节 点前一跳节点； 2 路由表：记录到达目的节点的距离，通过展短路径选择算法得到的下一跳 节点以及目的节点的前一跳节点，路由表更新标志位； 3 链路开销表：记录通过任意邻节点转发数据所需花费； 4 报文重传表：记录了更新信息的序列号，重传计数标志，是否响应确认信 息的标志量，以及更新报文中的更新信息。 ( 1 ) 路由表建立 在组网阶段或有新节点加入时，新入网的节点向其邻节点发送h e l l o 分组，当 其它节点接收到新的节点发出的h e l l o 分组时，便将新节点的信息加入自己的路由 表，并向其邻节点转发自己的最新路由表信息。 ( 2 ) 路由表维护 移动节点通过更新信息的传送来通知其它节点链路的改变。更新信息仅仅在 相邻节点问传递，并且包含更新信息：目的地址、路径权值以及目的地址的前一 无线网状网络的流苗均衡路由技术研究 跳节点。当一个节点收到其邻节点发来的更新信息时，该节点将更改自己的路由 表信息并向发送节点发送确认，同时将更新信息向其它邻节点转发。当一个节点 在一定的时问期限内没有数据要发送时，它必须发送h e l l o 数据包到其它节点，以 表明链路仍然可达。否则，其它节点将认为到该节点的连接中断，继而发出错误 的更新信息。 图2 1 说明了当网络中链路失效的时候，w r p 协议是如何更新路由表的。其中 每条链路边上所显示的数字为链路权值即链路消耗，括号中的内容为到达目的节 点j 所需的消耗以及目的节点的前一跳节点，如图2 1 ( a ) 所示，节点b 路由表的 一项为( 2 ，k ) ，其含义是根据最短路径算法，b 节点n j 节点的路径总消耗为2 ， 到达目的节点j 的前一跳节点为k ，其它节点括号中内容含义相同。当u 链路失效 后，节点k 和j 将分别发送更新信息给它们的邻节点，这里我们以k 节点为例，如 图2 1 ( b ) 所示，此时k 节点到达j 节点的路径权值设为无穷大。当b ，i 节点收 到了来自k 节点的路由更新信息后，它们将分别更新其距离表，并且根据最短路 径算法重新选择一条到达目的节点j 的路径。比如节点i 将选择i j ，其链路消耗 为l o ，目的节点前一跳节点为其自身。之后b 和j 将发送更新信息给其邻节点， 如图2 1 ( c ) 所示。当节点k 收到更新信息后，更新距离表并选择一条最佳路由， 并发送更新信息，如图2 1 ( d ) 所示，当节点b 和l 收到来自k 的更新信息后， 因为更新序列号相同，所以不会对它们的路由表产生任何影响。 k ( 0 j )( 0 j ) 南南 ( 1 卫)( u f f m l 审一) 图2 1w r p 协议路由表的更新 2 2 按需路由 1 0 ，d 按需路由认为在动态变化的a dh o c 网络环境中，没有必要去维护网络路由 信息。仅需在发送时，如果源节点没有去往目的节点的路径时进行寻路，此时的 隆 j k 黔 第二章无线网状网络路由协议分析 拓扑信息和路由表只是整个网络路由信息的一部分。由于没有周期性的广播网络 路由信息，因此可以大大降低用于维护整个网络路由信息所带来的大量的额外开 销，从而节省了网络资源，如有效的带宽和电池。但是当有分组要发送时，如果 没有去往目的节点的路由信息，数据分组则需要等待，从而引起了时延。 按需路由协议主要由两部分组成： 1 路由发现； 2 路由维护。 下面我们从这两个方面对按需路由进行分析。 2 2 1d s r ( d y n a m i cs o u r c er o u t i n g ) 动态源路由协议d s r f 4 l 是专门为无线a dh o c 网络设计的一种简单高效的多跳 路由协议。d s r 协议允许网络中的每个节点拥有到某个目的节点的多条路径。当 网络中一个节点需要向一目的节点发送数据包时。它会按照某个准则从路由表中 选择一条最短路径( 如选择最小跳数路由) 。d s r 协议还拥有其它的一些特点， 如，可以保证路由无环路，支持单向链路，在网络拓扑发生变化时路由的快速修 复，可以支持拥有多达2 0 0 个运动节点的无线a dh o e 网络，且支持节点的高速运 动。 ( 1 ) 路由发现 当移动节点有一个分组需要发送时，它先查询本地路由表。如果有到目的节 点的路由，就使用该路由信息发送数据分组；否则，源节点广播r r e q 分组，启动 路由发现过程。每个收到“路由请求”分组的节点首先判断，是否有去往目的节 点的路由。如果没有，就要转发这个“路由请求”分组1 5 】。同时，将自己的地址加 入r r e q 分组的“路径信息”中。为了避免多次转发同一个r r e q 分组，节点对每 个r r e q 分组只转发一次。每个r r e q 分组由源节点、目的节点和发送序号唯一确 定。 如果某一节点收至i j r r e q 分组后，发现有去往所请求的目的节点的路由信息， 于是向源节点返回一个r r e p 分组。r r e p 分组中记录了由源节点到目的节点的完 整路径。如果传输链路支持双向链路，可以将r r e p 分组按照r r e q 分组的逆向路 径传输；如果不支持双向链路，该节点就发起另一次路由请求( 去往要答复的源 节点的) ，并在r r e q 分组中捎带r r e p 分组的信息。 ( 2 ) 路由维护 路由维护阶段涉及到r e r r 分组和“确认”a c k 分组。当节点的数据链路层检 0 无线网状网络的流苗均衡路由技术研究 测到链路中断时，就会发送r e r r 分组。任何收到r e r r 分组的节点，都会在路由 缓冲区中去掉前往该出错节点的路由，同时将经过该节点的路由截断至出错节点 处。监听a c k 分组也是一种判断链路中断的方式，这其中包括被动确认( 监听下 一跳节点是否转发了自己刚才发送的数据包) 。 2 2 2a o d v ( 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 g ) 按需距离矢量路由协议a o d v 6 是在d s d v 协议的基础上改进而来的，它 对d s d v 的改进在于仅仅在需要的时候才广播路由信息，而不是定期广播到达所 有目的节点的路由信息，从而减少了给网络带来的额外开销。a o d v 采用逐跳转 发分组，且只支持双向链路，因为r r e p 是按原路径返回的。 ( 1 ) 路由发现 当源节点不具备一条到目的节点的路由而又要发送数据到目的节点时，源节 点广播r r e q 消息给其邻节点。邻节点接收r r e q 分组，建立一条到源的逆向路 径( 即存储传送该r r e q 包的上一跳节点) ，并设置逆向路径的生存期。如果该 节点没有到目的节点的路由，就把收到的r r e q 分组转给自己的邻节点，直到到 达目的节点，或者到达某个具有前往目的节点路由信息的中间节点。如果序号小于 缓存的路由序号或者已经超过跳计数的规定，则中间节点丢弃该r r e q 分组。 目的节点收至i j r r e q ，就建立到源节点的逆向路由，返回一个r r e p 路由应答报 文。单播该r r e p 给源节点。中间节点收到r r e p ，就建立到目的节点的正向路由。 ( 2 ) 路由维护 a o d v 路由协议采用h e l l o 消息机制进行链路连通性管理，从而对有效路由进行 维护。具有有效路由的节点每隔一固定时间t 便广播一个h e l l o 消息。邻节点收到 h e l l o 消息，可对各自的相应路由进行建立或更新。若节点在连续的几个t 的时间内 未收到有效路由中相邻节点的h e l l o 消息便认为该链路中断，并由发生问题的链路 的上游节点向它的上游节点发送r e r r ，直到源节点收到该r e r r 。这样就可以清 除所有用到这条断开链路的路由。 当发现链路断开时，可以由源节点重新发, m , r r e q 查找路由。但是，目前多用局 部修复，即断开处的节点试图修复断开的活跃路由，如果一次修复尝试失败则由源 节点重新发r r e q 查找路由。 第二章无线网状网络路由协议分析 2 2 3a b r ( a s s o c i a t i v i t y - b a s e dr o u t i n g ) a b r i s 中路由的选择是以节点间的连接稳定性作为度量依据的。根据这种尺度 选择的路由具有较长的生命周期。网络中所有节点周期性的给邻节点发送h e l l o 分 组以告知其自己的存在性。当一个邻居节点收到来自节点a 的h e l l o 分组，它将更新 自己的连接表，具体做法是将本节点与a 节点的连接度加1 。连接稳定度反映了任 意两个节点之间空间和时间上的连接稳定性，稳定度越高则节点移动速度越慢； 反之稳定度越低，节点移动速度越侠。只有当节点移出邻域，连接度才会被初始 化。a b r 的目标是为a d h o e 网络寻找生命期较长的路由。 1 ) 路由发现 路由发现时通过广播查询包b e a c o nq u e r y ( b q ) 和等待对b q 包的回复 ( b q r e p l y ) 来搜索具有到目的节点路由的节点。当中间节点收到b q 包后，它 将自己的地址和它与周围所有邻节点连接度加n b q 包，并继续广播发送。随后的 节点除了保留上一节点与本节点的连接度条目，将上一节点的所有其它连接度条 目删除。当目的节点收至i j b q 包的时候，里面已经包含了整条路由所有中闻节点间 的连接度。由目的节点最后从中选择一条最佳的路由。如果有多条路由具有相同 的连接度，那么跳数最少的一条路径将被选为传输路径。之后目的节点沿这条路 由的逆向给源节点发送b q r e p l y ，沿途转发r e p l y 的节点将它们的路由标志位 设为可用，其它的路由将被置为不活跃，这是为了避免包的重复发送。 ( 2 ) 路由维护 路由维护阶段包含局部路由发现，不可用路由删除，可用路由更新以及新路 由发现几个子阶段，当然这是基于中间节点的移动。源节点的移动将导致新的路 由发现过程，并且采用r o u t en o t i f i c a t i o n ( r n ) 消息来删除源节点所有下行节点中 与该路由相关的条目。如果目的节点移动，那么与目的节点直接连接的节点d 1 将 删除它到目的节点间的路由，之后发起l o c a l i z e dq u e r y ( l q ) 过程( 即局部路由 发现过程) ，如果目的节点收到来自d 1 的i t n ，那么表明目的节点仍可达，此时目 的节点发送r e p l y 给d 1 ；如果不能收到，那么将d l 节点的上行节点d 2 与目的节 点的路由删除，并由d 2 发起局部路由发现过程。依此类推，如果这种过程持续了 超过一半的路由长度( 跳数) 目的节点仍然不可达，那么该过程将被放弃，源节 点将重新发起一次新的路由发现过程。当一条路由不再需要的时候，源节点将发 起路由删除( r d ) 广播。所有收到r d 的节点，将删除其相应的路由条目。 无线网状网络的流苗均衡路由技术研究 2 3 分层式路由协议 在大规模的a dh o c 网络中，无论是表驱动路由协议还是按需路由协议都难以 单独承担寻找路由的重任。如果仅仅采用表驱动的策略，则在大规模的网络中每 个节点都要维护到全网所有节点的路由，这将占用大量的系统资源；同时周期性 的交换路由信息也势必会加大无线信道的负荷，从而大大降低网络的性能。如果 仅仅是采用按需路由的策略，由于网络中的节点可能分布在很广泛的范围内，则 建立路由所需要的等待时间就会比较长，这对于对实时性要求比较严格的语音或 视频业务显然是不可取的。 所以针对这个问题，h a a s 等人提出t z r p ( 9 - 1 0 】协议，在该协议中每个节点都维 护一个域，该域包含以节点自己为中心r 跳范围之内的所有节点，并且使用表驱动 路由来维护这个域中所有节点的路由，域间节点的通信则是采用按需路由方式。 一旦源节点所要寻找的目的节点不在其管理域内，源节点将根据其路由表中的信 息将路由询问信息直接发给它所在域内的边缘节点。z r p 协议充分利用了表驱动路 由和按需路由的优点，实验证明z r p 协议具有良好的扩展性。 呻d e n o t e sr o u t er e q u e s t d s n o t 的r 川t er e p i y 图2 2z r p 路由建立全过程 图2 2 给出了z r p 路由建立过程的一个简单示意图。在该图中，z r p 的每个节点 半径都为2 ，在这个跳数范围内，所有节点都按表驱动的路由算法建立区域内路由， 而区域问则采用按需方式发送路由建立分组来建立路由。当节点s 有业务要发送给 目的节点d 时，它首先检测自己的路由表，发现路由表中没有通往目的节点的路由 信息，于是，源节点s 根据路由表中信息直接给所属区域的边界节点发送寻路请求。 边界节点a 和c 发现自己仍然没有通往节点d 的路径信息，于是继续给自己的边界 节点广播寻路分组。e 在收到从c 节点广播来的寻路分组后，查询自己的路由表， 第一二章无线嗍状网络路由协议分析 发现有通往目的节点d 的路径信息，然后节点e 按寻路分组所记录的路径信息向源 节返回它所需要的路径信息，这样整个寻路过程结束。 2 4 基于地理位置辅助的路由协议 目前由于有很多网络可以获得g p s 信息，所以基于地理位置辅助的路由协议 也成为了a dh o c 网络路由算法研究中的一个热点问题。在该类协议中节点利用地 理位置信息，计算出每一个节点的可能的相对位置，然后将泛洪发送的数据限制 在某一有限的区域内，从而达到减少网络冗余传输的目的。由于有了地理位置信 息，网络中的节点可以充分了解网络拓扑的形状，有效的减小路由请求中被影响 的节点。这对于资源非常有限的无线信道来说是非常重要的。 在此我们简单介绍一下l a r ( 1 0 c a t i o n - a i d e dr o u t i n g ) 协议l 。该协议是一种 类似于d s r 的按需路由协议，它的目标是提高路由请求的效率，利用位置信息选 择路由请求分组的泛洪方向，限制路由请求过程中被影响的节点数目。 l a r 是一基于位置的路由，它增强了传统按需路由协议的路由发现阶段的性 能。传统的按需路由使用泛洪的方法作为路由发现策略，l a r 利用目的节点的位 置信息来限制泛洪的区域大小。协议预测出期望域，只有在请求域内的节点才转 发r r e q 分组，从而限制了查找过程中被影响到的节点，减少了不必要的复制转发。 l a r 根据节点与目的节点之间的距离选择转发节点，逐步将r r e q 发送到离目的节 点更近的节点，最终到达目的节点。 2 4a dh o e 网络路由协议性能比较 前面我们说过a dh o e 网络路由协议可分为三类：平面式路由、分层式路由 和基于地理位置辅助的路由协议。在这里我们不考虑分层路由，而是将路由协议 简单地分为两大类，表驱动路由和按需路由，下面我们对这两类路由协议进行详 细的比较。 2 4 1 表驱动路由 基于表2 2 我们对表驱动路由的性能进行了比较。正如我们前面所说，d s d v 路由协议基于b e l l m a n f o r d 路由协议，只是在避免环路和路由信息更新方面作了 简单的改进。在众多可传输路径中，源节点只选择最短路径进行传输。为了减少 广播更新信息给网络带来的额外开销，d s d v 提供两种更新信息，且二者大小不 样。小的更新信息用于网络拓扑经常发生变化的情况，这样可以节省路由信息 4 无线网状网络的流量均衡路由技术研究 带来的额外丌销。但是由于d s d v 周期性广播路由更新信息并没有考虑网络拓扑 变化的情况，使得网络的负荷与o ( n 2 ) 成正比，从而限制了接入网络的节点数目。 w r p 路由协议要求每个节点维护四个路由表，这就需要大的存储量，尤其当 网络规模很大时。同时w r p 路由协议在没有数据包要发送的时候仍然发送h e l l o 分组，这样会浪费系统带宽，且不停的发送h e l l o 包使得节点不能进入休眠状态， 从而浪费能量。 我们刚刚讨论了现有表驱动路由的工作方式和特性，接下来我们简单说明它 们之间的区别。当链路发生断路的时候，在更新网络路由信息方面w r p 比d s d v 需要较短的时间，因为它只要告诉它的邻节点链路变化状况，并不是整个网络。 而路由协议c g s r 的路由性能依靠网络中的特殊节点，可能是群首，网关或普通 节点，如果是与群首相关的链路出现问题，它需要花大量的时间重新选择群首， 因此它在重建路由所花费的时间方面要比w r p 高。 由于d s d v ，c g s r 和w r p 都是以最短路径为选路标准的路由协议，因此在 通信复杂度方面它们是相同的。 表2 2 a dh o e 网络表驱动路由的性能比较 比较参数 d s d vc g s rw r p 时间复杂度( 添加链路断路)o ( d )o ( d )o ( h ) 通信复杂度( 添加链路断路)o ( x = n )o ( x = n )o ( x = n ) 路由结构平面式分层式平面式 环路避免是是是 支持多播 否否“否 每个节点维护路由表数224 更新信息传输频率周期性或事件周期性周期性或事 驱动件驱动 更新信息的传输对象邻1 0 点邻节点和群首邻节点 发送序号 有有 有 h e l l o 分组有无有 重要节点 无有无 选路准则最短路径最短路