（计算机应用技术专业论文）ieee+80211s路径选择协议的性能研究.pdf

摘要 目前，无线网格网( w i r e l e s sm e s hn e t w o r k ) 已经成为日益关注的焦点。自 2 0 0 4 年7 月i e e e8 0 2 1 1t g s ( 8 0 2 1 1 s 任务组) 正式成立以来，已有三个i e e e8 0 2 工作组在制定相应的w m n 标准。 本文首先研究并分析了传统m a n e t 协议和8 0 2 1 l s 默认的路由协议，同时 结合路由协议研究了传统的路由尺度，并通过仿真分析了传统路由尺度的性能差 异。在研究了w m n 结构的基础上，提出了基于链路类型的路径参数计算方案， 同时考虑了拥塞控制。本文同时对传统的e t x ，e t t ，w c e t t 进行了扩展，尝 试使e t x 支持多传输速率，并在此基础上推导出支持多速率的w c e t t ，以替 代默认的a i r t i m e 链路参数，并应用到路径计算方案中。本文还引入了精确的链 路参数测量方案e a r ，同时通过仿真实验验证该测量方案的性能。 本文最后的仿真结果表明，默认的链路参数由于仅仅提供了网络间的互操作 的兼容性，因而性能不佳。修改后的w c e i q 在保证对多速率支持的前提下，提 供了网络间路径选择算法互操作的兼容性，并在性能上优于默认的链路参数 a i r t i m e 。 由于8 0 2 1 l s 提供了对传统8 0 2 网络的支持，在考虑链路特性的前提下，基 于链路类型的路径参数计算方案有助于在具有骨干架构的移动网络环境下，找到 更稳定的路径。仿真结果也表明相关的改进是有效的。 关键词：8 0 2 1 1s ；期望传输计数；期望传输时间；累积权期望传输时间 a bs t r a c t c u r r e n t l y , w i r e l e s sm e s hn e t w o r k sh a v er e c e i v e di n c r e a s e da t t e n t i o no v e rt h e l a s ty e a r s i n c e8 0 2 11t g sf o u n d e do nj u l y , 2 0 0 4 ，t h r e ew g so ft h ei e e ep r o j e c t8 0 2 h a v ew o r ko nw m n t h em a i nc h a r a c t e r i s t i co fw m ni st h ec o m m u n i c a t i o nb e t w e e nn o d e so v e r m u l t i p l ew i r e l e s sh o p so nam e s hn e t w o r kg r a p h e f f i c i e n tr o u t i n gp r o t o c o l sp r o v i d e p a t h st h r o u g ht h ew i r e l e s sm e s ha n dr e a c tt od y n a m i cc h a n g e si nt h et o p o l o g y , s ot h a t m e s hn o d e sc a l lc o m m u n i c a t ew i t he a c ho t h e re v e ni ft h e ya r en o ti nd i r e c tw i r e l e s s r a n g e i n t e r m e d i a t en o d e so nt h ep a t hw i l lf o r w a r dt h ep a c k e t st ot h ed e s t i n a t i o n m a n e ti sb a s e do nt h es a m ep r i n c i p l e - w i r e l e s sm u l t i - h o pc o m m u n i c a t i o na n d m o b i l i t yo ft h en o d e s s o ，t h em u t i n gp r o t o c o l sd e v e l o p e df o rm a n e t a r eo f t e n a p p l i e dt ow m n t h ed i s s e r t a t i o nf i r s t l ys t u d ya n da n a l y z et h et r a d i t i o n a lr o u t i n gp r o t o c o l so f m a n e ta n dd e f a u l tp r o t o c o l so f8 0 2 1ls ，a n dt h e nm a k e sar e s e a r c ho ft h et r a d i t i o n a l r o u t i n gm e t r i c sw i t hr o u t i n gp r o t o c o l s w ep r o p o s e da ni n t e g r a t e ds c h e m eo fp a t h m e t r i cb a s e do nl i n kt y p e ，a n dm a k ea ne x t e n s i o nb a s e do nm u l t i - r a t et ot h et r a d i t i o n a l e t x ，e r 丌a n dw c e t r m e a n w h i l e ，w ei n t r o d u c ea ne f f e c t i v ea n da c c u r a t el i n k m e a s u r e m e n tc a l l e de a rf o rg e t t i n gt h ea c c u r a t el i n km e t r i ct oi m p r o v et h e p e r f o r m a n c eo fp a t hs e l e c t i o n t h el i n kt y p em e t r i cs u p p o r tt of i n dt h em o r es t a b l e p a t ha n dt h em o d i f i e dw c e t tb a s e do nm u l t i r a t es u p p o r tt h ec o m p a t i b i l i t yt o m u l t i - r a t ea n dt ot r a d i t i o n a l8 0 2n e t w o r k s t h er e s u l to fs i m u l a t i o nr e v e a l st h a tt h e s e m e a s u r e si m p r o v et h en e t w o r kp e r f o r m a n c eb e t t e rt h a nw h a tt h ed e f a u l tm e t r i c a i r t i m ea n dp a t hm e t r i cc o m p u t a t i o ns c h e m eo f8 0 2 1lsc a nd o k e yw o r d ：8 0 2 1 l s ：e t x ：e t t ：w c e t t 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个入或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 储虢p 苏伊 吼僻月彩日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名：产伊 日期硼解j 月矽日 导师签名： 冬吼渺睁厂眺日 第一章绪论 1 1 无线网格网的研究背景 无线网格网( w i r e l e s sm e s hn e t w o r k ，w m 是一种新型的宽带无线网络结 构，一是一种高容量，高速率的分布式网络f l j 。w m n 与移动a dh o c 网络相似，但总 体来说，网络节点的移动性较弱，拓扑变化较小。在单跳接入上，w m n 可以看 成是一种特殊的无线局域网( w l a n ) 。w m n 也可以被认为是移动a dh o c 网络的 一种特殊形态。它的早期研究与开发均源于移动a dh o e 网络的相关工作。如1 9 9 7 年，美国国防部高级研究规划署( d a r p a ) 为加强战术通信系统的可靠性和r r r 公 司合作研究的最新集无线组网，路由和定位一体化技术的先进战术通信系统 ( a t c s ) 。目前，w m n 已开始用于商业、消防、智能交通监控和宽带因特网接入 等众多领域，并有望继续扩大应用领域。 宽带无线接入技术根据覆盖范围和应用模式可划分为无线个域网( w p a n ) ， 无线局域网( w l a n ) ，无线城域网( w m a 和无线广域网技术。分别由i e e e 8 0 2 1 5 ，8 0 2 1 l ，8 0 2 1 6 ，8 0 2 2 0 这四个工作组进行标准的研究和制定，其中i e e e 8 0 2 1 1 和8 0 2 1 6 发展最为迅速，也最具代表性。8 0 2 。1 1 在百米范围内提供高速 无线接入。8 0 2 1 6 在几公里和几十公里范围内提供宽带无线接入，它们分别依托 其产业联盟w i f i 和w i m a x 进行产品标准认证和市场推广工作。当前，无线宽 带网络正在逐步的向多跳的网格网发展。无线网格网利用最后的几公里来扩展位 于有线网络边缘的移动用户的互联网接入。发达国家的商业化w m n 已经开始部 署。有些大城市已经开始部署城际规模的网状网络( m e s hn e t w o r k ) ，如美国的明 尼苏达的c h a s k a ，宾夕法尼亚的费城，厄勒冈州的m e d f o r d ，为当地的公司，企 业和居民提供了商业化的互联网接入。 无线网格网提供的解决“最后几公里”瓶颈问题的组网方案i z 】，是由8 0 2 1 6 ( w i m a x ) 无线宽带接入工作组负责制定的。无线网格网提供的对本地网络的多跳 覆盖和移动性支持方案分别由i e e e8 0 2 1 5m e s h 和的i e e e8 0 2 1 l sm e s h 工作组 负责制定。因此，无线网格网将成为未来无线城域n ( w m a n ) 核心网一部分，是 迄今为止唯一一种建立大规模移动a dh o c 网络的可行性技术。 1 2 无线网格网的结构和特性 在无线网格网中，节点分成网格路由器( m e s hr o u t e r ) 【r 2 3 j 和网格客户端( m e s h c l i e n t ) 两种类型。每个节点既要担当主机( h o s t ) 的角色，也要担当路由器的 角色。由于目标节点不总是在单跳的无线传输范围之内，因而转发来自其他节点 的数据是最常见的任务。无线网格网中所有节点都具有自组织和自配置的能力， 它们自动建立并维护由它们自己构成的网络。 如图1 1 所示，无线网格网的结构可以分为三大类【4 j 。 图1 1 无线网格网分层结构 1 基础架构骨干网络( i n f r a s t r u c t u r e b a c k b o n ew i r e l e s sm e s hn e t w o r k ) 骨干网络中，网格路由器提供了无线环境下骨干节点的基本结构。这与传统 的w l a n 有些类似的地方，关键的差别在于有线的骨干节点被替换为无线的多 跳网络。网格客户端直接通过网格路由器接入网络。这种结构下，网格客户端只 是被动的角色，对网格网的基本架构没有任何影响。 2 客户终端网格网络( c l i e n tw i r e l e s sm e s hn e t w o r k ) 在客户终端网格网络架构中，网络完全由移动的网格客户端组成。没有明确 的网络结构，因而网格客户端需要执行完整的网络的功能，如路由和转发。一个 完全由网格客户端组成的w m n 就是传统意义上的纯a dh o c 网络【5 】。 3 基于上两种结构的混合无线网格网( h y b r i dw i r e l e s sm e s hn e t w o r k ) 混合无线网格网是最常见的w m n ，结合了骨干网络架构和客户终端网格网 络架构。静态的网格路由器担当网络中的骨干节点，移动节点网格客户端通过执 行路由和数据包转发功能而作为网络静态结构的动态扩展。 无线网格网是一种多跳的无线网络。节点的移动性是主要特点之一。为了研 究的方便，通常假设网格路由器节点是固定的，且认为网格路由器是没有电力消 耗限制的。而网格客户端节点则既可以是固定节点也可以是移动节点，并只具备 有限电力供应。无线网格网提供了多种接入方式，同时支持回程( b a c k h a u l ) 接 入和p e e r - t o p e e r 通讯。此外，由于无线网格网需要和其他网络进行整合，因而 必须提供对多种标准的兼容性和对现有标准的向下兼容性。 1 3 无线网格网相关标准 当前，有三个i e e e8 0 2 工程组正在制定相关的无线网格网标准。其中， 8 0 2 1 l s 负责制定基于w l a n 的m e s h 标准，称为( w l a nm e s hn e t w o r k ，w m n ) 。 8 0 2 1 5 负责制定基于无线个人区域网( w i r e l e s sp e r s o n a la r e an e t w o r k ，w p 州) 的m e s h 标准，即8 0 2 1 5 5 。8 0 2 1 6 也为无线城域网( w i r e l e s sm e t r o p o l i t a na r e a n e t w o r k ，w m a n ) 定义了m e s h 拓扑。成立不久的8 0 2 1 6 j 正在定义基于m e s h 拓扑的移动多跳中继网( m o b i l em u l t i h o pr e l a y ，m m r ) 。 1 3 1i e e e8 0 2 1 l sm e s h 无线局域网 w i f im e s h 能够在骨干网络架构和客户终端网格网络架构两个基本模式下运 行。前者形成了一个具有基础架构的扩展服务集( e s s ) ，接入点通过无线链路 互相连接。客户端和接入点相关联。骨干网络架构在接入点之间或无线路由器间 建立了无线回程m e s h 。为了提供一个i e e e 8 0 2 1 1e s sm e s h ，8 0 2 1 l s 定义了基 于8 0 2 1 1 的无线分布式系统( w d s ) ，在m a c 层使用r a d i o a w a r e 的参数，支 持广播，多播和单播递交。客户终端网格网架构模式是一个第三层a dh o e 独立 基本服务集i b s s ，使用p 路由。客户终端网格网络架构使得客户终端设备间可 以形成无线p e e r - t o p e e r 网络，不需要任何网络基础结构支持。 8 0 2 1 l s 项目已于今年1 月完成，核准工作将于2 0 0 8 年1 2 月3 1 号结束。 1 3 2i e e e8 0 2 1 5 5m e s h 无线个人区域网 8 0 2 1 5 注重于高速无线个人区域网解决方案的研究，当前阶段，t g 5 正在解 决传统的8 0 2 1 5 3 集中式m a c 对m e s h 的支持问题。8 0 2 1 5 采用完全m e s h 拓 扑或部分m e s h 拓扑之一提供连接管理。 8 0 2 1 5 5 项目于去年，即2 0 0 6 年1 2 月完成，核准工作于2 0 0 8 年底结束。 1 3 3i e e e8 0 2 1 6 j 移动多跳中继网 所谓的“最后一英里解决方案”即指8 0 2 1 6 的m e s h 解决方案。其目标是建 立城域范围的宽带服务。尽管8 0 2 1 6 也定义了m e s h 拓扑，但直到目前，该结构 还没有被完全定义和使用。这是由于集中调度结构限制了8 0 2 1 6m e s h 的可扩展 性。同时，8 0 2 1 6m e s h 是基于无连接m a c 的，所以实时q o s 服务很难保证。 而隐藏终端问题也使8 0 2 1 6 网格架构饱受困绕。新的8 0 2 1 6 j 定义了基于星型拓 扑的中继方案。8 0 2 1 6 j 需要固定的基础架构，提供漫游，固定和移动三种中继 方式。w i m a x 是8 0 2 1 6 标准中最成熟的商业运用。w i m a x 预期提供长距离的， 视距和非视距内的宽带无线接入。现在的研究目标是基于中继的w i m a x 方案。 8 0 2 1 6 j 项目预计将在今年9 月完成，最终的核准将在2 0 1 0 年年底。 1 4 本文所做的主要工作和文章结构安排 本文首先详细介绍与8 0 2 1 l sm e s hw l a n 路径选择协议相关的协议，即 m a n e t 路由协议。重点研究与8 0 2 1 l s 默认路由协议h w m p 和可选路由协议 r a o l s r 相关的先验式和反应式协议，并比较它们之间的异同点。在此基础上， 详细讨论8 0 2 1 l s 邻节点发现，链路状态获取，链路参数计算和节点间链路的建 立和维护过程。最后提出根据链路类型来计算路径参数以提高路径选择稳定性的 方案。同时，说明如何采用新的链路参数以及如何得到更精确的链路参数测量结 果。 本文所做的工作主要集中于： 1 本文主要研究了链路类型及其参数，链路参数的测量，路径参数的计算 方式等对8 0 2 1 1 s 路径选择机制带来的影响。在考虑链路类型的前提下，对路径 选择算法进行优化，并考虑了这种优化在骨干链路上可能导致的拥塞问题。 4 2 本文提出了8 0 2 1l s 多速率支持下，对传统的链路参数的改进方案，并引 入了更精确的测量方案e a r 。 本文主要章节内容安排如下： 第2 章详细介绍并分析与8 0 2 1 l s 相关的m a n e t 路由协议。详细研究这些 协议的思想及所使用的技术。同时对传统的a dh o e 路由尺度进行研究分析，并 通过仿真实验了解它们的性能差异。同时研究8 0 2 1 l s 默认的路径选择协议和默 认的路由尺度，并与传统m a n e t 路由协议进行比较。 第3 章从研究w m n 和8 0 2 1 l s 的结构入手，提出基于链路类型的路径参数 计算方案并给出计算公式。同时考虑在采用了基于链路类型的路径参数计算方案 后可能产生的拥塞并进行负载平筏的研究，并提出了一种新的拥塞控制方案。 第4 章引入新的路由尺度测量方案以得到更精确的测量结果，并通过实验对 该测量方案进行研究。 第5 章对传统的链路参数进行扩展，定义了支持多速率的e t x ，并在m a c 层用m s d u 的统计结果对e t x 做出改进，使其更符合8 0 2 1i s 默认的m a c 层 路径选择协议。随后详细介绍如何对e t x 进行多速率扩展，并最终得到多速率 支持的路径e 1 盯和w c e t t 参数，使之可以应用在8 0 2 。l l s 中。最后将结合基于 w m n 链路类型的路径计算方案和多速率支持的w c e t t 得到新的路径计算方 案。 第6 章给出相应的仿真结果。由于8 0 2 1 1 s 标准的制定工作在本文编写结束 前半月才获得通过，且最后的核准工作还没有结束，因而无法获得更确切的路径 选择方案的详细信息。仿真是建立在原有相关协议基础上的，无法和目前8 0 2 1i s 确认使用的协议有所对比。同时本章对全文进行了总结和分析并提出了后续工作 的设想。一个基于h w m p 先验式扩展所建立的树拓扑的集中式路径选择扩展方 案也将在本章结尾处提出。 第二章w m n 路由协议及路由参数的研究分析 由于无线网格网与移动a dh o e 网具有一些相同的特性，如多跳性和移动性， 因而m a n e t 的路由协议常常被应用到w m n 中。尽管a dh o e 路由协议对 m a n e t 来说是有效的，但应用到w m n 中却性能不佳。这是由多方面的原因造 成的。如w m n 和m a n e t 对电力效率，移动性的不同要求。在w m n 中，骨 干网中的网格路由器具有很小的移动性，且对电力消耗没有限制，而网格客户端 通常就需要具有支持移动性和电力管理的路由协议的支持。这些区别隐含着为 m a n e t 设计的路由协议不完全适合w m n 网络。 路由尺度是评价无线链路性能最主要的参数。多年来，a dh o e 路由协议都 注重研究节点的移动性，时变的拓扑和网络的可扩展性，而较少关注如何发现具 有较高质量的路由路径。本章在研究a dh o e 路由协议的同时，也分析传统a dh o e 路由尺度的特点和所存在的问题，并用仿真实验来验证这些路由尺度的性能差 异。 本章的最后将分析路由协议和路由尺度组合的合理性。由于8 0 2 1 l s 默认的 路由尺度以提供兼容性为主，所以为了提高性能，尝试使用已有的传统路由尺度 来代替8 0 2 1 1 s 默认的链路尺度以获得更好的性能。分析的结论表明传统的 w c e t t 适合a o d v 路由协议，但不适合o l s r 协议。这也从一个侧面表明， w c e t t 适用于8 0 2 1 l s 默认路由协议h w m p ，但不适用于可选路由协议 r a o l s r 。 2 1 无线网格网相关路由协议的研究分析 m a n e t 路由协议被认为是混合无线网格网路由协议最适合的替代者。通常 而言，路由方案可以被分成两类8 1 。一类是适应性路由，另一类是非适应性路由。 适应性路由可以对网络拓扑的动态变化做出响应，而非适应性路由则使用固定的 表格。 对于a dh o e 而言，根据协议使用的适应性策略，路由方案又分为反应式路 由按需路由，先验式路由表驱动路由和混合路由。 反应式路由按需路由仅在需要时才计算路由，所有的节点不会保留路由信 6 息。 先验式路由表驱动路由在需要路由之前就已经计算好路由，所有节点需要 随时维护路由信息，并保持路由时刻更新。路由表格更新分为事件驱动更新和定 期更新。事件驱动更新为仅当节点知道有变化发生才更新路由。 混合路由是反应式路由和先验式路由在同一时间使用。如在网内使用先验式 路由，在网间使用反应式路由。 从另一个角度看，路由方案又可以分为距离向量路由方案和链路状态路由方 案。距离向量路由方案需要计算到所有节点的距离，并仅与邻节点交换这些信息。 链路状态路l h 贝, u 衡量到邻节点的距离或其他路径参数，并与所有节点交换这些信 息。 根据对路由请求的发送方案。路由协议又可分为四种不同的方案。本地多播 路由方案仅对传输距离内的部分节点发送路由请求。本地广播路由方案对传输距 离内的所有节点发送路由请求。全网广播路由方案即是所谓的洪泛( f l o o d i n g ) 路由请求。受限全网广播方案通常指洪泛带有一个t t l ( t i m e t o l i v e ) 限制。 路由方案实质上是一种路径选择的策略。基干考虑的侧重点不同，路径选择 也有多种策略可选。目前常见的有：电力敏感的路由策略，信号强度敏感的路由 策略，考虑链路稳定的策略，最短路径策略，链路状态距离向量策略，基于方 向位置地理信息的路由策略，基于链路带宽保留的策略和多路径策略。 w m n 和传统8 0 2 1 1 的主要区别之在于多跳性和单跳性。因而，路由又可 以分为多跳路由和传统的单跳路由。 由于单个设备上多接口的出现，因而又出现了单波路由和多波路由的区别。 如微软提出的多波链路质量源路由协议( m r - l q s r ) 属于多波路由方案。源路 由方案主要指仅有路由请求的发送者才可指定路由。 多跳性是w m n 和m a n e t 所共有的特性，因而m a n e t 路由协议典型是 多跳路由方案1 1 0 1 。我们将从路由方案的适应性策略分类，即先验式方案，反应 式方案和混合方案来考虑本文所关注的三种路由协议。它们分别是属于先验式方 案的o l s r t l 8 1 和f s r 。属于反应式方案的a o d v 14 1 。介绍这几个路由协议的原 因是本文研究的目标8 0 2 1 l s 指定的默认路由协议h w m p 7 】提供的按需路由服务 是基于射频参数的a o d v 的改进协议，称为r m a o d v 7 , i o 】，并对r m a o d v 7 进行了先验式扩展。8 0 2 1 1 s 指定的可选路由协议r a o l s r l 6 1 是基于o l s r 和 f s r 的修改和扩展。 在先验式路由方案中，节点需要维护全局状态信息，以保持路由信息的一致 性。路由信息需要存储在所有节点的路由表内。先验式路由方案都会持续检测网 络拓扑和链路状态的变化。当网络拓扑发生变化时，节点发送的路由更新信息会 传播到整个网络以更新状态信息。所以先验式路由方案能比较及时的反映网络的 变化。 2 1 1 优化链路状态路由协议o l s r o l s r 是一种基于链路状态的表驱动协议。每个节点定期广播h e l l o 消息与 指定的邻节点交换信息。收到该信息的节点建立自己的路由表。节点使用最短路 径算法计算到每个它想要通讯的目标节点的路由。 o l s r 的每个节点都需要存储一张到所有目标节点的路由表。当检测到邻节 点变化时，或到一个目标节点的路由过期时，或检测到更短的路径时就更新路由 表项。 o l s r 的特色在于需要依靠中继节点。“多点中继节点是由它的邻节点选 择的。假设节点a 在其所有的邻节点中选取一个由部分邻节点构成m p r 集，这 些被选中的节点即为m p r ，节点a 称为s e l e c t o r 。在路由过程中，只有s e l e c t o r 和其m p r 集中的节点才会参与路由过程，且只有m p r 节点才产生链路状态更 新并中转链路状态更新。 m p r 有助于降低广播信息在网络中的洪泛。每个节点使用h e l l o 消息向邻节 点通告它的m p r 集。在收到h e l l o 消息后，节点就记录它的s e l e c t o r 节点。m p r 可以减少h e l l o 消息包的大小。因为h e l l o 消息中仅包含同一m p r 集内的节点。 所以h e l l o 传播的仅仅是部分拓扑信息。m p r 集中的每个节点只有它们的 s e l e c t o r 才可到达。 o l s r 的优点在于延迟较小。o l s r 链路状态算法适用于高密度和大规模的 网络。由于每个节点在所有的时间都保留有到每个目标节点的路由表项，因而避 免了额外的寻路，所以提供了较低的单播延迟。 o l s r 的缺点在于当网络是稀疏网络时，一个节点的所有邻节点有可能都被 选为m p r ，o l s r 也就变成了普通的链路状态协议。同时，o l s r 也有很高的控 r 制信息负载，需要额外的存储空间。 2 1 2f s r f s r 】是对g s r 协议的改进。这两者都是基于链路状态的协议。f s r 也是 一个表驱动的协议。f s r 的每个节点都要维护拓扑表，邻近链路状态表，路由表。 拓扑表是根据链路状态消息包中的信息建立的。每个目标节点在拓扑表中都有一 个表项。每个表项含有两部分，链路状态信息和目标节点序号。每个节点基于拓 扑表来计算路由表，在路由表计算过程中可以获得距离信息。距离信息用于对节 点的作用域( f i s h e y es c o p e ) 进行分类。一旦节点收到一个链路状态消息，它就 立即更新并记录邻节点列表中与发送该链路状态消息的节点相关的信息。如果在 规定时间内没有收到任何信息，相应的节点信息就从邻节点列表中删除。路由表 主要是为了转发数据包而提供下一跳的信息。路由表项根据拓扑表的变化而更 新。 在f s r 中，更新信息不包含网络中所有节点的信息。若节点彼此靠近，则 信息交换频率较高。反之，信息交换率较低，这样就降低了更新信息的大小。 中央节点具有所有内层节点的最新信息，信息的精确性随着节点间距离的增 大而降低。在每个节点上都会执行把网络划分为不同等级作用域的过程，因而这 是一个独立于中央实体的过程。即便一个节点没有远距离节点的精确信息，但由 于路由信息会变的越来越精确，因而数据会越来越靠近目标节点，最终到达目标 节点。 当每个节点都维护了一张到每个目标节点的路由表时，f s r 的功能就类似于 l s 协议，用定期交换来替代事件驱动的交换方案。拓扑表仅发送到本地的相邻 节点，而不是洪泛到整个网络。 当路由表项中相应的节点都在- d , 块区域内时，由于邻近节点信息的交换频 率很高，所以对内层节点来说，f s r 的作用域信息的更新方案具有很高的精确性。 外层节点由于距离较远，信息交换的间隔时间较长，因而信息就相对不精确。f s r 的作用域技术允许根据作用域的不同距离使用不同的信息交换间隔时间，因而降 低了链路状态消息包的大小。 当使用最新最短路由时，f s r 协议就相当的简单。当仅与邻节点交换部分路 由更新信息时，f s r 体现出对高速移动网络的路由健壮性。 q 2 1 3a dh o c 按需距离向量路由协议( a o d v ) 反应式路由协议又称为按需路由协议。它们的共性是：仅当源节点需要和某 个目标节点通讯，路由表中没有相应的表项时才进行选路计算。源节点按需启动 一个路由发现进程，在一条路由发现后，源节点建立并维护发现的路由路径直到 这条路径断开或不再需要。已经发现的路由可以存放在节点的缓存内以备后用， 使用前必须确认路由有效。 a o d v 是基于d s d v 的反应式路由协议。a o d v 的特征之一是每个路由表 项都有一个目标节点序号。该序号由目标节点建立，并被包含在路由请求和路由 响应中发送到请求路由的节点。序号用于避免循环。节点也通过序号确认路由的 更新程度，即若一个节点有到达同一目标的两个路由选择，则必然选择具有最大 序号的路由。 源节点启动一个路由发现进程后，源节点广播路由请求到所有邻节点。当路 由请求从源节点出发到达不同的节点时，所有节点都会自动设置反向路径。收到 路由请求的邻节点再次转发路由请求给它们的邻节点，直到目标节点收到路由请 求或者路由请求到达一个具有到达目标节点有效路由的中间节点。 若一个中间节点的路由表中有到达目标节点的路由项目，则将其路由表中目 标节点的序号与它收到的路由请求中目标节点的序号相比较。若路由请求中的序 号大于路由表中序号，则中间节点就不能产生路由响应，而需要重新广播该路由 请求。当路由表中的序号大于或等于路由请求的序号，才产生路由响应。 节点只转发第一个收到的路由响应。若继续收到路由响应，仅当后收到的路 由响应中目标节点的序号大于先收到的路由响应中的序号，或序号相同但跳计数 小于先前收到的路由响应中的跳计数，它才更新路由表并再次转发路由响应。 路由响应沿反向路径返回源节点时，沿着路由响应前进路径上的所有节点将 设置指向目标节点的转发指针。不在转发路径上的节点在超时计数到期后，将删 除反向指针。 一旦下一跳不可达，节点就要从断开处的上行链路产生一个路由响应，并伴 有一个新的序号，该序号大于先前已知的序号，同时跳计数变成无穷大，并发送 到所有活动的上行邻节点。这些活动的邻节点随后就转发该消息直到所有相关源 节点得到关于该断链的通告。 1 0 无论什么时候，一个节点收到来自邻节点的广播后都会更新它的本地连接信 息，以确保在它的邻节点表内包含这个邻节点。若在一个h e l l o 消息的间隔期间 内，节点a 没有发送任何数据包到它的所有活动下行邻节点，它就需要给所有 邻节点广播一个h e l l o 消息。h e l l o 消息包含了a 的i d 和序号。序号在h e l l o 消 息传输时不会发生变化，且该消息不会被转发。所有接收到h e l l o 消息的邻节点 都会更新与a 的连接信息。收到一个广播；收到一个来自新的邻节点的h e l l o 消 息或者没有收到来自原有邻节点的h e l l o 消息，都说明本地连接发生了变化。如 果没有从沿着活动路径的下跳节点收到h e l l o 消息，则这个节点的邻节点就需 要被通告一个链路失效。一旦接收到断链或链路失效通告，源节点就重新启动路 由发现进程。 2 2 路由协议与路由尺度相关性分析 为了确保路由尺度与路由协议相结合后能体现出较好的性能，需要对协议和 尺度进行综合的研究。与传统的有线网络相比，无线m e s h 网带给我们额外的一 些问题，简要概括如下： 1 节点移动性。无线m e s h 网的节点可能是移动的，因而，链路就可能随时断 开，拓扑也可能频繁变化。从图论的角度来说，连接图随着时间快速变化， 这就使路由维护更加复杂。 2 无线信号的传播现象。在无线环境下，节点传输是一种物理广播，属于射频 传播。因而就会遇到信号衰减等问题。这就使即便是静态链路也有可能遭遇 链路质量的波动，并有可能导致在网络内出现突发性灰区，即该区域内链路 质量很差，但仍能出现一些成功的传输。这种情况会引发频繁的路由重建。 3 电力受限。在很多情况下，预留一些电力并延长电池的使用时间是进行持续 网络操作的首要任务。当我们还没有完全意识到这个问题的时候，设备所提 供的电力是否持续可用将成为又一个即将出现的性能瓶颈。尤其当节点移动 而长期无法接入到固定电源时，电力受限就表现的尤其严重。 4 缺乏集中控制。无线m e s h 网最吸引人的特性之一可能就是完全的自组织性。 功能的变化完全是通过分布式方法来完成的，如媒介接入控制和路由。缺陷 是很明显的。因为绝大多数决定都由节点自身做出，而节点做出的决定是依 据其周围的环境，这就使的网络的优化具有边缘性而不是全局性。 1 1 本节将对以往的路由尺度进行分类和分析，部分路由尺度将会详细介绍，因 为我们认为这些协议对改进8 0 2 1 1 s 默认协议是有帮助的。 路由尺度是否适合路由协议主要从如下几个方面来判断。 首先，路由尺度不能引起频繁的路由变化，即不能导致路由震荡，以确保网 络的稳定性。路径成本的稳定性严重影响网络的性能。频繁的变化会产生额外的 路由更新信息，频繁的路由更新将使路由协议无法收敛。 路径的稳定性由被路由尺度所捕获的路径特性所决定。如负载敏感的路由尺 度在数据流量进入或离开时可能会频繁的发生变化。而拓扑独立的路由尺度，如 跳计数，通常更稳定。 负载敏感的路由尺度和拓扑独立的路由尺度都分别适用于不同的路由协议。 按需路由协议通常忽略路径成本的频繁变化，如d s r 。因而负载敏感的参数比 较适用于按需路由协议。此外，先验式协议和按需协议通常在数据传输的t t l 未到期时更新路由，如a o d v 。路由尺度的微小变化可能导致路由更新，因而 若路径上流量不稳定，则负载敏感的链路尺度对网络的稳定性非常不利。因而， 如前所述，负载敏感的链路尺度仅适合用于按需路由协议但也有较高负载。所 以该类链路尺度是适用于w m n 。而拓扑独立的链路尺度则同时适用于按需路由 协议和先验式路由协议。 其次，路由尺度必须能够准确的捕获网格网的特性，以确保计算出的最小成 本路径具有最好的性能 路由协议的目标就是根据特定的路由参数路由数据通过最小成本的路径。为 了确保网络资源能够被有效利用，路由尺度必须能够反映网络的特性。 路径的第一个特性就是路径长度。由于每跳都引入了额外的延迟和潜在的丢 包率，路径越长就意味着端到端延迟的增加和吞吐量的降低。因而，路由尺度在 路径变长时应能提高路径的成本值。 路径的第二个特性是链路容量。两个无线节点问最大的传输速率与这两个节 点的物理距离直接相关。随着距离的增加，信道的质量就会衰退。由于现在的无 线网卡允许根据信道质量调节它们的传输速率，因而当节点间距离增加时，链路 容量就会降低。所以，尽管增大节点间距离有助于降低跳计数，但是距离跟容量 是不可同时获得的。因而路由尺度应该要能在这一对矛盾间取得折中。 1 2 第三个特性是丢包率。不同的无线链路可能有不同的丢包率。丢包造成的多 次重传会影响吞吐量并造成延迟，因而路由尺度必须能够捕获链路的丢包率以确 保良好的性能。 第四个特性是干涉。无线链路的带宽是和邻节点所共享的。数据流经过某条 链路时不但消耗这条链路的带宽，且会与该条链路邻近的节点竞争带宽。如内部 数据流之间的干涉就会导致带宽耗尽。为了避免这种无谓的消耗，路由尺度必须 要能够帮助路由协议选择既能平衡负载，又能降低网络内部数据流之间的干涉。 对无线网格网路由尺度的有效分析必须是建立在对如下两个问题的理解之 上的，即用于无线网格网中的路由协议是什么? 无线网格网的特性是什么? 首 先，由于不同的路由协议可能使用不同的网络成本计算方法，因而了解哪种类型 的路由协议适合网格网是首要解决的问题。其次，无线网格网的特性如无线链路 的共享性使得我们无法得到明确的带宽。这是由于邻节点的传输可能也在竞争同 样的波段。 2 3 典型的w m n 路由参数研究 在这一节，我们将讨论为网格网提出的四种路由尺度。这四个路由尺度分别 是跳计数( h o pc o u n t ) ，期望传输计数( e x p e c t e dt r a n s m i s s i o nc o u n t ，e t x ) ， 期望传输时间( e x p e c t e dt r a n s m i s s i o nt i m e ，e t t ) 和累积权期望传输时间( w e i g h t c u m u l a t i v ee t t ，w c e t t ) 。所有这四个参数都是拓扑独立的，每个后提出的路 由尺度的性能都优于前一个。 2 3 1 跳计数 跳计数是现存路由协议旱最常用的路由尺度，它把每条链路都看成相同的单 元，独立于链路的质量和其他特性。跳计数的简单性使之成为应用最广泛的路由 尺度，成为许多流行无线网格路由协议的默认尺度，如d s r ，a o d v ，o l s r 等。 最小化跳计数的原理是简单明了的。在数据传输路径上，跳数越少隐含着延迟越 小，吞吐量越大，并降低网络资源浪费的意义，而不去考虑是否涉及了链路缓存， 传输速率和丢包率的差异，也没有考虑无线网络中的干涉等问题。跳计数的个 隐含的假设是链路是无错的。对于有线链路来说，这个假设是可行的，但是对于 无线链路来说，没有一个网格无线链路可以被看成是无错的。在无线传播的环境 中，外部的和网络内部的干涉，节点的移动性都导致了连接性的断断续续。最小 跳计数倾向于选择距离更长的链路，根据传输电力的选择，一个节点可以有两种 选择： 1 节点可以增加传输的电力以达到更远的传输距离，并在更长的距离上提高传 输成功的概率，因而最小化跳计数就增加了电力的消耗。这是很多由电池供 点的设备最关心的问题。 2 另一方面，节点的传输电力可以是固定的，因而链路越长，数据丢失的概率 越大。在传统的电力消耗水平上，网络内的干涉更频繁，最终增加了延迟。 图2 1 单跳和两跳路径 在图2 1 中，假设节点s 和d 间的双向丢包概率是p 1 。节点s ，h ，d 间的 双向丢包概率是p 2 。当使用8 0 2 1 l x 单播传输模式时，一次成功的传输被定义为 前向数据的正确接收和反向a c k 的正确接收。假设重传是无限的，那最小跳计 数路径s d 的延迟是否大于两跳路径s h d 呢? 若前向丢包和反向丢包概率是一 样的，则一跳上成功传输一次的概率是( 1 p ) 2 ，这意味着期望传输次数是1 ( 1 - p ) 2 。 s d 和s h d 正常的端到端延迟是： 。= 南；。泐= 南 因而： 。舳 _ d s l i dj 南南j 旨压j 只j 每护 所以，为了比两跳路径有更小的延迟，假设p 2 为0 ，p l 最小应为0 2 9 。 以同样的方法来计算图2 2 。 1 4 o 1 。 巩 图2 2多跳路径 s 2 46d 和s 1 3 5 7 d 正常的端到端延迟是： d s - 2 - 4 - 6 - d = 南； d s - l - 3 - 5 - 7 - d = 南 j 鲁鱼2 p 乩2j 小等1 些1 2 1 一。 所以，为了比s - 1 357 d 路径有更小的延迟，假设p 2 为0 ，p l 最小应为 正如图2 1 和图2 2 所说明的，沿多跳路径使用最小跳计数，丢包概率要小 的多，而最小跳计数尺度不会选用丢包概率小的路径。 2 3 2 期望传输计数 e t x 是第一个基于主动探询测量方案的移动a dh o c 网路由尺度。e t x 被定 义为在无线链路上的一个数据包进行一次成功的传输在m a c 层所需要的期望传 输次数。路径的成本被定义为沿着该路径所有链路的e t x 值的总和。一个显而 易见的问题是丢包率低的长路径和丢包率高的短路径可能具有相同的e t x 值， 因而可以说e t x 可以捕获丢包率和路径长度对网络的影响。但是e t x 没有考虑 干涉，也没有考虑不同的链路可能具有不同的传输率。e t x 是为单信道网络设 计的，因而无法发现信道差异