（计算机应用技术专业论文）无线网状网路由算法研究与实现.pdf

北京邮电大学硕士学位论文无线网状网路由算法研究与实现 无线网状网路由算法研究与实现 摘要 无线网状网( w i r e l e s sm e s hn e t w o r k ，简称w m n ) 是一种新型 的无线通信网络。无线网状网具有自组织性和自愈性的特性，是一种 多跳的宽带无线网络结构。目前，无线网状网的研究受到学术界和工 业界的广泛重视，可用带宽测量技术、路由协议等关键技术已成为研 究重点。 在8 0 2 1lm a c 监听机制基础上，论文提出了一种基于网络分配 矢量统计的可用带宽测量算法。它采用m a c 层统计节点网络分配矢 量，测量当前节点的可接入信道时间，使用可接入信道时间占测量时 间的比例来计算可用带宽。仿真结果表明，基于网络分配矢量统计的 可用带宽测量算法能够准确地测量可用带宽，其被动式测量的方式拥 有更高的稳定性，更小的开销。 在无线网状网的路由技术以及常用路由判据基础上，论文提出了 一种无线网状网基于跨层设计的综合判据路由算法一e a o d v 。它 通过在m a c 层和网络层之间增加跨层设计模块，统计节点的可用带 宽及负载，利用综合判据准则计算端到端路径的质量，以此为节点选 择一条较优的路径。仿真结果表明，e a o d v 优化算法具有较低的端 到端时延，较高的系统吞吐量，有效地均衡网络负载，能有效提高网 络性能。 关键词：无线网状网可用带宽路由协议跨层设计e a o d v r e s e a r c ha n dd e s i g no n r o u t i n gp r o t o c o lf o r te l e ss s h 卜咂t w o i a b s t r a c t w i r e l e s sm e s hn e t w o r k( 删)i san e wb r o a d b a n dw i r e l e s s n e t w o r ka r c h i t e c t u r ew i t ht h ef e a t u r e so fs e l f - o r g a n i z a t i o n a n d s e l f - h e a l i n g s i n c en o w a d a y st h e r e s e a r c h e so nw 7 m nh a v e b e e n e m p h a s i z e do nb o t ha c a d e m i c a l l ya n di n d u s t r i a l l y , t h ep o t e n t i a ls o l u t i o n o fa v a i l a b l eb a n d w i d t hm e a s u r e m e n ta n dr o u t i n gp r o t o c o li sb e i n gh o t t o p i c i nt h i sp a p e r , a na v a i l a b l eb a n d w i d t hm e a s u r e m e n ta l g o r i t h mb a s e d o nn e t w o r ka l l o c a t i o nv e c t o ri sg i v e n n ea l g o r i t h mo b t a i n st h en a v i n f o r m a t i o no fi t sn e i g h b o r st h r o u g hm a c “l i s t e n i n g m e c h a n i s m ，s t o r e s t h ei n f o r m a t i o ni n t oi t sb u f f e r s 。a n dc a l c u l a t e st h ea v a i l a b l eb a n d w i d t ho f t h ei n v e s t i g a t e dn o d eb yt h er a t i oo fi t sc h a n n e la c c e s s i b l et i m et ot h e m e a s u r e m e n td u r a t i o n t h ea l g o r i t h mu s e s ap a s s i v em e a s u r e m e n t m e t h o dw i t h o u ta d d i t i o n a lc o m m u n i c a t i o n sl o a dt ow i r e l e s s m e s h n e t w o r k t h es i m u l a t i o nr e s u l t ss h o wt h ep r o p o s e ds c h e m e ，c o m p a r e d w i t ho t h e ra v a i l a b l eb a n d w i d t hm e a s u r e m e n ta l g o r i t h m s ，i sm o r ea c c u r a t e a n dh a ss m a l l e rc o s t s ，w h i c hc a nc o m p l e t e l yr e f l e c tt h ec o l l i s i o na n d c o n t e n t i o nb e t w e e nn o d e s t h es e c o n dp a r to ft h i sp a p e rw h e r ean e wr o u t i n gp r o t o c o le a o d v b a s e do nt h ea o d vi sp r o p o s e d t h en e wr o u t i n gp r o t o c o lm a k eu s eo f ac r o s s 1 a y e r e dm o d e lb e t w e e nn e t w o r kl a y e ra n dm a cl a y e rt oo b t a i n t h ea v a i l a b l eb a n d w i d t ha n dl o a d so ft h en o d e ，c a l c u l a t e st h ee n d t o - e n d l i n k sq u a l i t yt h r o u g ham e t h o do fi n t e g r a t e dm e t r i c s ，a n dt h e nc h o o s e sa b e t t e rr o u t i n g t h es i m u l a t i o nr e s u l t ss h o wt h a tt h ep r o p o s e de a o d v p r o t o c o li m p r o v e st h ed e l a ya n dt h et h r o u g h p u t o fw i r e l e s sm e s hn e t w o r k i i 北京邮电大学硕士学位论文 无线网状网路由算法研究与实现 s i g n i f i c a n t l ya n db a l a n c e sl o a ds i m u l t a n e o u s l y k e yw o r d s ：w q v i na v a i l a b l eb a n d w i d t h r o u t i n gp r o t o c o l c r o s s l a y e rd e s i g ne a o d v 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处， 本人签名： 盔敛 本人承担一切相关责任。 日期：学上4 二 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论 文注释：本学 本人签名 导师签名 适用本授权书。 日期：驾丝盟一 日期：雌k 之l 一 北京邮电大学硕士学位论文无线网状网路由算法研究与实现 1 1 研究背景 第一章绪论 随着人们对网络通信需求的不断提高，人们希望不论何时、何地、与何人都 能够进行快速、准确的通信，提高工作效率，并且能够克服现有通信系统的缺点， 达到通信的“无所不在 【。 针对移动通信业务以及移动性方面的特点，业界在移动自组织网络( m o b i l e a dh o cn e t w o r k s ，m a n e t s ) 的技术基础上，开发出一种适用于移动通信的无线 多跳网络技术无线网状网( w m n ，w i r e l e s sm e s hn e t w o r k s ) i s 。w m h 3 】 是移动自组织网络( a dh o c 网络) 的一种特殊形态，并承袭了部分w l a n 技术 的新的网络技术，可以看成是一种w l a n 和a dh o c 网络的融合，且发挥了两者 的优势。它的早期研究均源于移动a dh o e 网络的研究与开发，它是一种高容量、 高速率的分布式网络。作为一种可以解决“最后一公里一瓶颈问题的新型网络结 构，w m n 代表着无线网络技术的又一大跨越，已经被写入了i e e e 8 0 2 1 6 无线 城域网( w i r e l e s sm u n i c i p a la r e an e t w o r k , w m a n ) 标准和i e e e8 0 2 1 5 系列标 准之中，i e e e 8 0 2 1 1 工作组正式专门成立了网状研究组和网状任务组，准备将 w m n 纳入i e e e 8 0 2 1 i s 标准的制定中。 无线网状网由无线网状网路由器( m e s hr o u t e r ) 和无线网状网终端用户 ( m e s hc l i e n t ) 这两种网络实体组成【4 】。其中，无线网状网路由器一般情况下 是固定的，具有路由及数据转发的功能，并且担任着连接无线网络和有线网络( 如 i n t e m e t ) 以及使用不同无线协议( 如8 0 2 11 ，8 0 2 1 5 ，8 0 2 1 6 ) 的无线网络之间 的网关和桥接功能。无线网状网终端可以是静止的或是移动的，它同样具备路由 及数据转发的功能，但是不具备网关功能，它既是业务的使用者，也是业务的提 供者。终端节点可以通过其它相邻终端节点或路由器以多跳的方式实现骨干网的 接入，从而增强了网络的覆盖能力。目前主要观点认为，w m n 是一种由无线链 路连接路由器和终端设备的准静态无线网络，是i n t e r n e t 的无线版本【5 】。 与传统的无线网络相比，无线网状网具有以下几个方面的特剧3 】： ( 1 ) 多跳无线网络 无线m e s h 网络具有灵活的网络结构，能够自形成、自愈以及自组织，能 北京邮电大学硕士学位论文无线网状网路由算法研究与实现 够在不牺牲当前信道容量的情况下，扩展当前无线网络的覆盖范围，为处于非视 距范围的用户提供非视距连接。通过m e s h 方式的网络连接，只需要短距离的链 路，经受较少的干扰，就可以为网络提供较高高的吞吐量。 ( 2 ) 频谱效率高 在无线m e s h 网络中，用户节点和邻近节点路径很短，其发射功率只要能 满足该路径承载的业务q o s 要求即可，对其他用户节点造成的干扰很小。这意 味着同一频段几乎可以在无线m e s h 网络中无限制地重复使用，增强了系统效 率。 ( 3 ) 系统容量大 由于传输距离缩短，无线信号可以采用高阶调制，增大了系统容量。无线 m e s h 网络的系统容量需要综合考虑频谱利用率、网络拓扑和网关节点数目等多 种因素的影响。 ( 4 ) 覆盖率高 用户节点既是客户端，又是路由器，可以方便的采用多跳方式链接到网关节 点。由于节点间距很短，无线传输受到障碍物阻挡的可能性降低，便于采用视距 和准视距传输。 ( 5 ) 扩展性好 自组网功能也方便了网络的扩展。可以在用户较少地区设置一些种子节点， 以便用户接入。由于网络覆盖率高，因此可以吸收大量的用户，一旦系统总的用 户数达到一定的容量，种子节点就可以收回，投入到新的地区使用。 ( 6 ) 可靠性强 无线m e s h 网中，每个用户节点存在多跳路径与其他网关节点相连，某个 网关或用户节点即使发生故障，用户节点也可以通过其他节点实现接入。因此， 无线m e s h 网具有较好的可靠性，可以应用在一些特殊领域，如军事、工业控制 左盘 奇o ( 7 ) 系统安装灵活 无线m e s h 网中基站选址不再是很重要的问题，当采用全向天线或智能天线 时，无线m e s h 网可以很快安装和投入使用，因此提高了网络的柔韧性与可行性。 ( 8 ) 投资成本低 无线m e s h 网的初建成本低，无线网状网路由器一旦投入使用，其位置基 本固定不变，因此节省了网络资源。无线m e s h 网一般采用非许可证频段，易 扩容，应用范围广，节省支出，可短期之内获得盈利。 2 北京邮电大学硕士学位论文无线网状网路由算法研究与实现 1 2 研究现状 目前，国内外对无线网状网有非常多的研究。尤其在应用基础理论与技术研 究上，已经取得了众多成果，主要有以下方面： ( 1 ) 路由协议的研究，协议的核心是适应网络无中心控制和网络时变的特 征。代表成果有d s d v ，a o d v ，d s r ，t o r a 等。 ( 2 ) m a c 层研究，其涉及多个方面：一是m a c 层的资源估计与预测，是 q o s 保证重要组成部分【6 】，如可用带宽测量技术；一是解决隐藏终端和提高接入 能力的问题，如m a c a 协议、控制信道和数据信道分裂的双信道方案和基于定 向天线的m a c 协议等。 ( 3 ) 在网络连接性方面，主要的背景是无线传感器网络，探讨问题的核心 是节点密度与分布问题。 ( 4 ) 在多播组播协议、t c p 协议、地址和带宽等网络资源分配、功率控制、 安全性问题、分布式算法、q o s 等方面有一些研究成果。 其中，路由协议作为无线m e s h 网络的关键技术之一，对其网络性能起着 十分重要的作用，但至今没有正式的移动无线m e s h 网络路由协议标准。因此， 需要针对无线m e s h 网络的特点设计专门适用的高效路由协议。 目前，无线m e s h 网络的路由协议都是在a d h o c 网络的路由协议的基础上， 针对自身网络的特点进行改进的，改进的方向主要有以下几种： ( 1 ) 多判据路由【7 ，射 常见的路由判据有：期望传输次数e t x ( e x p e c t e dt r a n s m i s s i o nc o u n t ) 川、 往返时间l 盯( r o u t e - t r i pt i m e ) 【8 】、数据对延时时间p k t p a i r ( p a c k e t p a i r l a t e n c y ) 、最小跳数h o p ( h o pc o u n t ) 等。路由协议将根据不同网络的特点 选择不同的一个或者几个判据。在实际应用中，网络的变化很复杂，有时单一的 路由判据很难反映出链路质量给各个性能指标带来的影响，所以在制定路由判据 时，应使用综合准则来解决此矛盾。 ( 2 ) 多信道路由【9 】 使用多信道的方式有很多种，如单收发器多信道、多收发器多信道方式。它 们都能较大地提高w m n 的网络吞吐量。 微软公司研发的多信道w m n 路由协议m r - l q s r ( m u l t i r a d i ol i n k q u a l i t y s o u r c er o u t i n g ) 【9 】采用多收发器多信道方式，它采用一种新的路由性能判据，称 为加权累计传输时间w c e t r ( w e i g h t e dc u m u l a t i v ee x p e c t e dt r a n s m i s s i o n t i m e ) ，综合考虑了带宽等链路性能参数以及最小跳数等因素。因此该协议能在 吞吐量与延时之间获得一种平衡。 北京邮电大学硕士学位论文无线网状网路由算法研究与实现 ( 3 ) 多径路由【1 0 】 在源节点和目的节点之间选择多条路径进行数据传输称为多径路由。多径路 由技术可以很好地避免单径路由时的网络震荡的影响，还可以在充分利用带宽等 网络资源的同时实现负载均衡、路由容错等。在某条链路因为信道质量恶化而不 能正常工作时，其他链路可以继续工作，因此，也可以在路由故障时避免路由重 建等操作。 m e s hn e t w o r k 公司开发的混合a dh o c 路由协议m s r ( m u l t i p a t hs o u r c e r o u t i n g ) 协议【1 0 】，该协议结合先应式路由与反应式路由的优点，在d s r 基础上采 用多径路由。 ( 4 ) 分级路由【l l 】 随着网络规模的增多，传统的利用广播机制来查找路由的方法会消耗很多的 网络资源，使端到端的时延变大。文献【l l 】提出了一种分级路由的方法，该方法在 簇间和簇内使用不同的路由，簇内路由协议为基于d s r 的反应式路由协议，该 协议能够很好的适应簇内用户移动快的特点；簇间则使用先应式路由协议，适应 簇间移动性小的特点。但在分级路由中，所有的数据业务都需要通过簇头转发， 簇头将成为这个网络的瓶颈，簇头一旦出现死机、拥塞或者能源耗尽现象时，将 影响整个网络的数据传输。 ( 5 ) 跨层路由【1 2 , 1 3 因为网络的时变特性，运行在网络层的路由协议性能并不理想，所以可以从 第二层提取一些状态参数信息作为路由判据。跨层设计【1 2 , 1 3 可以从底层采集路由 判据的方法来进行路由选择，考虑了m a c 层冲突、包传输成功率与数据传输成 功率等参数，路由选择时，可以根据这些判据选择具有较少冲突、数据包传输可 靠和高传输率的路径进行数据传输。 1 3 主要研究内容 在无线网状网中，无线信道是一种共享介质，信道的竞争而引起节点之间碰 撞冲突不可避免，给节点m a c 层资源估计与测量带来极大的挑战。本文给出了 一种基于网络分配矢量统计的可用带宽测量算法，被考察节点通过监听m a c 帧 中的持续时间i d 域统计邻居节点的网络分配矢量，将对应节点的网络分配矢量 以表的形式记录在自己的缓存中，对测量时间内同一节点的网络分配矢量叠加， 并减去被考察节点的退避时间，最终计算出测量时间内当前节点的可接入信道时 间，使用可接入信道时间占测量时间的比例来计算可用带宽。该算法采用被动测 量的方法，不会给网络带来额外的通信负载，仿真结果表明能够较准确地测量可 4 北京邮电大学硕士学位论文无线网状网路由算法研究与实现 用带宽，充分反映节点繁忙程度。 无线网状网是一种由无线链路连接路由器和终端设备组成的半静态无线网 络，要实现高速的传输数据，需要适合于无线网状网特点的快速、准确、高效和 可扩展的动态路由技术。本文比较了常用的两种路由算法( a o d v 与d s r ) 在 无线网状网中的性能，指出a o d v 路由协议更符合无线网状网在移动性以及网 络性能方面的要求。 目前，无线网状网常用的路由协议都是采用最小跳为路由判据，最小跳判据 倾向于选择传输距离远、跳数少的路径，但最小跳判据并没有考虑其他的测量指 标，比如链路衰落情况，链路包时延等，不能保证选出最佳路径。本文提出了一 种基于跨层设计的综合判据路由算法e a o d v 。它通过在m a c 层和网络层 之间建立跨层设计模块，统计节点的可用带宽及负载，利用综合判据准则计算端 到端路径的质量，以此为节点选择一条较优的路径。仿真结果表明，e a o d v 优 化算法具有较低的端到端时延，较高的系统吞吐量，有效地均衡网络负载，能有 效提高网络性能。 1 4 本文结构 本文主要研究无线网状网路由算法，以及其改进与实现。全文的结构如下： 第一章介绍无线网状网技术的背景，介绍本文研究内容的选取原因，综述研 究工作的范围和本文的结构。 第二章主要介绍了无线网状网的基本概念、网络结构，详细分析了无线网状 网路由算法、常用路由判据以及可用带宽测量技术。 第三章根据无线网状网中无线信道共享以及竞争特质，利用m a c 层的监听 机制提出基于网络分配矢量的可用带宽测量算法，并且通过仿真分析算法性能。 第四章在无线m e s h 环境下仿真比较了a o d v 路由协议和d s r 路由协议， 给出了仿真结果。并在a o d v 路由算法基础上，对基于跨层设计的a o d v 路由 协议进行了路由机制的设计，协议采用m a c 层统计的链路质量作为路由判据， 并对路由建立过程进行了修改，使用备份路由机制。最后给出了改进后路由协议 的实现和仿真结果，并对结果加以分析。 第五章为论文总结和下一步的研究工作。 5 北京邮电大学硕士学位论文 无线网状网路由算法研究与实现 第二章无线网状网概述 2 1 无线网状网网络结构 无线网状网的结构与传统意义上的移动a dh o e 网络结构有一定的差异。无 线网状网包括两种类型的节点无线网状网路由器m r 和无线网状网终端用 户m c 。通常无线网状网终端用户可以是笔记本电脑、p d a 、w i f i 手机、r f i d 阅读器等，无线网状网路由器可以是普通的p c ，也可以是专用的嵌入式系统。 其中，无线网状网终端用户节点也可以分为两类：一类是普通的w l a n 客户节 点，这类节点不具有移动a dh o e 网络典型意义下的信息转发功能，只是作为普 通终端设备接入网络；另一类节点既具有普通终端节点的接入功能，又具有路由 和信息转发功能，即兼具了无线路由器的功能，但通常这类节点不具备网关或网 桥节点的功能。 按照节点的不同功能，网络结构可以分为基础设旋的网络结构、终端设备的 网络结构和混合结构。按照结构层次，网络结构又可以分为平面结构、多级结构 和混合结构【3 】三类。两种分层思想本质是相似的，基础设施的网络结构就是一种 多级结构，而终端设备的网络结构就是一种平面结构。 2 1 1 平面网络结构 图2 1 所示为无线网状网中最简单的平面结构。图中所有的节点为对等结构， 具有完全一致的特征，即每个节点均既具有客户端节点的功能，也具有能够转发 业务的路由器节点的功能。但是，显然网络中的节点与现有的w l a n 等技术不 直接兼容，这种技术适用于节点数目较小且不需要接入到核心网络的应用场合。 平面网络结构也称为终端设备网络结构，网络中的节点为具有m e s h 路由 器功能的增强型终端用户设备。终端用户自身配置射频装置，通过无线信道的连 接形成一个点到点的网络。节点可以任意移动，网络拓扑结构也会动态变化。由 于终端的无线通信覆盖范围有限，两个无法直接通信的用户终端可以借助其他终 端的分组转发功能进行数据通信。在任意时刻，终端设备在不需要其他基础设备 的条件下可以独立的运行，支持移动终端较高速率的移动，快速形成宽带网络。 6 北京邮电大学硕士学位论文 无线网状网路由算法研究与实现 2 1 2 多级网络结构 图2 - 1 平面网络结构 图2 - 2 所示为无线网状网的典型多级结构，分为上、下两层。在这个结构中， 终端节点可以是普通的无线分组业务终端，它们通过无线网状网路由器接入到上 层结构的网格中，实现网络节点的互联互通。 图2 - 2 多级网络结构 该结构模式在接入点( 无线网状网路由器) 与终端用户之间形成无线回路。 移动终端通过m r 的路由选择和中继功能与网关节点形成无线链路，网关节点通 过路由选择及管理控制功能为移动终端选择与其目的节点通信的最佳路径，从而 形成无线回路。同时移动终端通过网关节点也可与其他网络相连，从而实现无线 宽带接入。 7 北京邮电大学硕士学位论文无线网状网路由算法研究与实现 2 1 3 混合网络结构 图2 3 所示的混合结构为以上两种结构的混合。在这种结构中，终端节点已 经不是目前市面上仅仅支持w l a n 的普通设备，而是增强了具有转发和路由功 能的m e s h 设备，设备之间可以以a dh o e 方式互联，直接通信。一般来说，终 端节点设备需要同时能够支持接入上层网络无线网状网路由器和本层网络对等 节点的功能。 2 2 无线网状网特点 图2 - 3 混合网络结构 无线网状网具有以下一些结构或技术上的特点【4 】： ( 1 ) 多跳无线网络。在不牺牲当前信道容量的情况下，扩展当前无线网络 的覆盖范围是无线网状网最重要的目标之一。无线网状网的另一个目标是为处于 非视距范围的用户提供非视距连接。通过m e s h 方式的网络连接，只需要短距 离的链路，经受较少的干扰，就可以为网络提供较高高的吞吐量，以及较高的频 谱复用效率。 ( 2 ) 支持a d h o e 网络结构，具有自形成、自愈和自组织能力。无线网状网 灵活的网络结构、便利的网络配置、容错能力和网络连通性，大大提升了现有网 络的性能。在较少的前期投资下，无线网状网可以根据需要逐步扩展。 ( 3 ) 移动性取决于节点的类型。m e s h 网关和路由器的移动性通常较低， 客户终端既可以是静止的，也可以是任意的移动节点。 ( 4 ) 多种网络接入方式。在无线网状网中，既可以支持回程到因特网的接 入，又可以支持端到端方式的通信。此外，可以通过无线网状网与其他无线网络 北京邮电大学硕士学位论文无线网状网路由算法研究与实现 的集成，向终端用户提供各种多媒体业务。 ( 5 ) 功耗限制取决于节点的类型。m e s h 路由器通常由外部供电，受功耗 限制不严格，客户终端则需要有效的节能机制。 ( 6 ) 与现有的无线网络兼容。无线网状网技术是基于现有的w i f i 、w i m a x 、 a dh o e 等网络技术实现的，因此和现有的无线网络具有较好的兼容性。 2 3 无线网状网与现有无线网络的区别 2 3 1 无线网状网与蜂窝网络的主要区别 无线网状网区别于蜂窝网络的特点主要表现在可靠性、传输速率、投资成本 和配置和维护性能上。 ( 1 ) 可靠性提高。在无线网状网中，链路为网状结构，如果其中一条链路 出现故障，节点可以自动转向其他可以接入的链路，因而对网络的可靠性有较高 的保障，而在采用星型结构的蜂窝移动通信系统中，一旦某条链路出现故障，可 能造成大范围的中断。 ( 2 ) 传输速率提高。在无线网状网中，可以融合其他网络技术，理论上速 率可以达到5 4 m b i v s 。而目前的3 g 技术，理论传输速率最高也才2 m b i v s 。 ( 3 ) 投资成本降低。无线网状网大大节省了骨干网络的建设成本，而且a p 、 无线路由器等基础设备比蜂窝移动通信系统的基站等设备便宜很多。 ( 4 ) 网络配置和维护简便快捷。传统的蜂窝移动通信系统需要维护建设在 高塔上的基站，而无线网状网的基础设施小巧，便于安装和维护，而且网络扩展 比较方便，只需要增加一些必要的设备。 2 3 2 无线网状网与无线局域网的主要区别 从拓扑结构上看，无线局域网是典型的点对多点( p m p ，p o i n tt om u l t i p l e p o i n t s ) 网络，而且采用单跳方式，数据不可以转发。无线局域网可以在热点地 区内提供高速数据服务，但是典型的覆盖范围仅限于几百米；对于无线网状网而 言，则可以通过无线路由器对数据进行转发，直到到达目的节点，从而把接入服 务的覆盖范围延伸到几公里远。 9 北京邮电大学硕士学位论文无线网状网路由算法研究与实现 从协议上看，无线局域网的m a c 层协议完成的只是本地业务的接入，而无 线网状网则有两种可能，一种是本地业务的接入，另一种是其他节点业务的转发。 对于路由协议，无线局域网是静态路由协议和移动i p 的组合；而无线网状网则 主要是动态的按需发现的路由协议，具有较短暂的生命周期。 2 3 3 无线网状网与移动a dh o c 网络的主要区别 无线网状网与移动a dh o c 网络很类似，可以把无线网状网当作移动a dh o c 网络的一个特例，但两者仍然存在一些各自的特点。 ( 1 ) 虽然无线网状网与移动a dh o c 网络均是点对点( p 2 p ，p o i n tt op o i n t ) 的自组织的多跳网络，但从根本上来说，无线网状网由无线路由器构成的无线骨 干网组成，提供大范围的信号覆盖与节点连接。而移动a dh o c 网络的节点都兼 有路由器和终端功能，节点地位平等，健壮性比无线网状网要差。 ( 2 ) 无线网状网节点移动性低于移动a dh o c 网络中的节点。从网络结构来 看，无线网状网多为静止或者弱移动的拓扑，而移动a dh o c 网络多为随意移动 的网络拓扑。 ( 3 ) 无线网状网与移动a dh o c 网络的业务模式不同，无线网状网节点的主 要业务是来往于因特网的业务；移动a dh o c 网络节点的主要业务是任意一对节 点之间的业务流。 ( 4 ) 从应用来看，无线网状网主要用于宽带无线多媒体业务的接入，而移 动a dh o c 网络主要用于军事或其他专业通信。 2 4 无线网状网路由协议 由于无线网状网是一种新兴的网络技术，它既有传统有线网络的骨干节点拓 扑较为稳定，路由相对变化较慢的特点。又因为每个骨干节点通过无线进行连接 和移动终端可以运动而具有了无线网络中链路不稳定，终端的拓扑结构变化较大 的特点。为了解决移动性和无线通讯的特点带来的问题，目前已提出了许多的路 由协议【1 4 1 。按不同的标准，这些协议可分为三种类型：先应式路由协议 1 5 】、反 应式路由协议和混合式路由协议。 2 4 1 先应式路由协议1 5 1 6 , 1 7 , 1 8 , 1 9 2 0 ，2 1 ，2 2 2 3 l 先应式( p r o a c t i v e ) 路由协议又称为表驱动( t a b l e d r i v e n ) 路由协议，是一 l o 北京邮电大学硕士学位论文无线网状网路由算法研究与实现 种基于表格的路由协议【1 5 1 。在这种路由协议中，每个节点维护一张或多张表格， 这些表格包含到达网络中其它节点的路由信息。当检测到网络拓扑结构发生变化 时，节点在网络中发送更新消息。收到更新消息的节点更新自己的表格，以维护 一职的、及时的、准确的路由消息。不同的先应式路由协议的区别在于拓扑更新 信息在网络中传播的方式和需要存储的表的类型和数量。 先应式路由协议的优点是当节点需要发送一个到达其他节点的数据分组时， 只要路由存在，发送分组的延时就很小；缺点是先应式路由协议不断检测网络拓 扑和链路质量的变化，需要花费较高代价( 如带宽、电源、c p u 资源等) ，才能 使路由表能够跟上当前网络拓扑结构的变化，然而动态变化的拓扑结构又可能使 高代价得来的路由表中内容变成无效信息，路由协议始终处于不收敛状态。 d s d v 路由协议 d s d v ( 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 r ) 路由协议【1 6 ，r 7 】是一种无环路 距离向量路由协议，需要每个节点周期的广播其路由更新信息。最大的优势是它 能够保证避免路由回环。在这种算法中，每一个节点维护一张包括网内所有可能 目的地和到他们的路由跳数的路由表。每一条记录带有一定的序列号标记，该序 列号是由目标节点分配的。 w j t d p 路由协议 w r p ( w i r e l e s sr o u t i n gp r o t o c 0 1 ) 1 8 1 也是一种距离向量路由协议，每个节点 包括距离表、路由表、链路权值和消息重传表四张表。其中距离表记录通过其每 个邻节点到达任意目的节点的跳数以及每个目的节点前一跳节点；路由表记录到 达目的节点的距离，通过最短路径选择算法得到的目的节点的前一跳节点以及后 一跳节点，路由表更新标志位；链路权值表记录通过任一个邻节点转发数据所需 花费；消息重传表中的每一条记录包含了更新信息的序列号，一个重传计数标志， 是否响应确认信息的标志量，以及更新报文中的更新消息。 移动节点通过更新消息的传送来通知其它节点链路的改变。更新信息仅仅在 相邻节点间传递，并且包含一串更新信息：目的地址、路径权值以及目的地址的 前一个节点。当一个节点收到其它邻居节点发来的更新消息，更改自己的表信息 并向发送节点发送确认，同时将更新信息想其它邻居节点转发。移动节点需要周 期性发送h e l l o 包给邻居节点说明链路可达。该方法需要维护四张表，并且周 期性的发送h e l l o 信息，都在一定程度上增加了网络的负担。 g s r 路由协议 g s r ( g l o b a ls t a t er o u t i n g ) 【1 9 】是一种基于网络拓扑结构的链路状态路由协 议，它周期性的与邻节点交换链路状态信息，从而避免路由信息泛洪给网络带来 的负担。在g s r 协议中每个节点存储邻居列表、拓扑表、下一跳表和距离表四 北京邮电大学硕士学位论文无线网状网路由算法研究与实现 张表格。 f s r 路由协议 f s r ( f i s h e y es t a t er o u t i n g ) 2 0 , 2 1 】对g s r 进行了改进，其更新消息只包含附 近节点的信息而不是所有节点的，同时链路状态表中的不同条目的更新周期也不 尽相同，从而显著地减少了更新消息的大小。与邻居节点的信息交换远远频繁与 距离远的节点，所以每个节点能够及时地获得邻近节点的准确消息，并且消息的 详细程度和准确度随着与该节点距离的增加而减小。尽管源节点没有距离较远的 目的节点的准确信息，但是当数据包距离目的节点越近那么路由信息越准确，所 以数据包能够被正确的发送至目的节点。f s r 的优点在于使用于大范围的以及高 速移动的网络环境中，但是因为该协议只能获取小范围内准确的路由和链路信 息，而无线网状网的通信流量主要发生在网关链路上，从而远离网关的节点不能 及时地察觉到该网关的负载情况，从而有可能进一步加重拥塞。 s r 路由协议 h s r ( h i e r a r c h i c a ls t a t er o u t i n g ) 瞄】是一种用于分级网络的路由协议。高级 的节点保存它所有子孙节点的位置信息。沿着从最高级的根节点到最低级的叶节 点的路径为节点分配逻辑序列地址。序列地址指示了节点的位置，可以简单地使 用序列地址进行寻址。 分级结构路由协议的优点主要有：减少了大多数节点路由表的大小；能够支 持更多的节点；簇首节点能够监控该簇内所有节点的通信流量；簇首节点能够为 一些实时应用提供q o s 保障。缺点包括：簇首节点选举的公平性和对网络负载 的影响；源节点到目的节点的跳数可能增加；协议复杂性增加；如果簇首节点失 效则该簇内节点无法通信。最主要的，在无线网状网中如果选择的簇首不具备足 够的计算能力以及信道容量，采用分级结构的路由协议很难实现。 z i t l s 路由协议 z h l s ( z o n e - b a s e dh i e r a r c h i c a ll i n ks t a t e ) 路由协议【2 3 1 是一种基于区域的路 由算法。网络被分割成不重叠的区域，区域与簇不同，它没有域首节点，并定义 了两级拓扑节点级和区域级。节点级拓扑指一个区域内的节点的物理连接。 区域级拓扑指各个区域如何互相连接。网络中存在两种链路状态分组：节点链路 状态分组和区域链路状态分组。通过分区可以减少路由控制分组的个数。 2 4 2 反应式路由协议【2 蟠 2 6 2 7 l 反应式路由协议，又称为按需路由( o n d e m a n dr o u t i n g ) ，是一种当需要时 才查找路由的路由选择方式。节点不保存及时准确的路由消息。当源节点要向目 1 2 北京邮电大学硕士学位论文无线网状网路由算法研究与实现 的节点发送分组时，源节点在网络中发起路由查找过程，找到相应的路由后，才 开始发送分组。反应式路由算法的优点是不需要周期性的广播路由信息，节省了 一定的网络资源；缺点是在发送数据分组时，若没有到达目的节点的路由，要启 动路由发现过程来寻找路由，所以数据分组需要等待一定时间的延时。 目前，业界研究无线网状网的公司，如l o c u s tw o r l d ，t r o p e s ，b e l a i r 等， 它们主要侧重于反应式路由算法的研究。鉴于反应式路由协议的普遍应用，本文 将重点介绍其中具有代表性的a o d v ( a d h o co n d e m a n dd i s t a n c e v e c t o r ) 按需 距离矢量协议【2 4 ，2 5 】和d s r ( d y n a m i cs o u r c er o u t i n g ) 动态源路由协议【2 6 矧。 a o d v 按需距离矢量路由协议 a o d v ( a d - h o co n d e m a n dd i s t a n c e - v c 娥o r ) 阱，2 5 】是专为a dh o c 网络设计的 一种路由协议，现在也广泛应用在m e s h 网络中。它是按需式和表驱动式的一 种结合，具备了两种思想的优点，它的处理过程和存储开销都很小，能对链路状 态的变化做出快速的反应。a o d v 通过引入序列号的方法解决了不会形成路由 环的问题。 a o d v 包括3 个部分：路由发现，路由维护和路由删除。 路由发现：当节点要传送数据分组时，源节点先检查缓存中是否有到信宿的 路由信息，若有非过期的路由则可直接采用，否则洪泛广播发送路由请求r r e q ( r o u t e r e q u e s t ) 包。每个节点接收后判断是否有到目的节点的路由，若没有， 则将r r e q 包转发给邻节点；若有，则再判断是否允许中间节点回复，不允许则 将r r e q 包转发给邻节点，允许则直接向源节点回复路由回复r r e p ( r o u t e r e p l y ) 分组。若是目的节点就返回应答，发送路由回复r r e p 包，源节点接收到 路由回复后，则路由发现过程结束。 路由维护：源节点通过路由维护机制可以检测出网络拓扑的改变，从而知道 到目的节点的路由是否可用。路由维护探测到某条使用中的路由出现了问题，就 会发送k e r r ( 路由错误报文) 给源节点。源节点在收到该r e r r 后，就会从它 的路由缓存中删除所有包含有该故障链路的路由。 a o d v 的路由维护需要节点周期性地广播h e l l o 包来表明自己的存在，节 点通过接收邻节点发送的h e l l o 消息来证实他们之间链路的有效性。节点也可 以使用数据链路层的机制来监视链路的状态。当检测到链路中断时，对当前通过 此节点的活跃路径上的所有节点，分别向他们发送一个路由应答消息，将路径中 断消息传送给他们。接收到此消息的节点进行相同的路由更新过程，知道活跃路 径上的所有上有节点更新其路由表。 路由删除：当前节点如果收到r r e r 包，或者路由表中路径过期，节点删 除对应无效路径。 1 3 北京邮电大学硕士学位论文无线网状网路由算法研究与实现 a o d v 支持单播、组播和广播通信，适用于对称链路。对于非对称链路， a o d v 通过使用特殊的路由错误信息，可以快速删除非法路由。a o d v 能 及时对影响动态路由的拓扑变化做出反应。另外，在建立路由时，除了路由控制 分组以外，没有其他的网络开销，路由开销也很小。 但是a o d v 路由协议仍然存在以下问题： ( 1 ) 在a o d v 路由协议的路由发现过程中，由于网络拓扑结构的不断变化， 路由需要进行不断的更新，这就需要节点经常启动路由发现过程。 ( 2 ) 在路由维持过程中，a o d v 协议周期性的发送消息包，增加了网络的资 源开销。 d s r 动态源路由协议 d s r ( d y i l a m i es o u r c er o u t i n g ) 动态源路由协议【2 6 2 7 l 是一种按需路由协议， 它允许节点动态的发现到目的节点的多跳路由。所谓源路由，是指在每个数据分 组的头部携带在到达目的节点之前所有分组必须经过的节点的列表，即分组中含 有到目的节点的完整路由。 协议包括路由发现和路由维护两部分。 d s r 的路由发现过程与a o d v 类似，但是d s r 的分组头比a o d v 的大。 因为每个d s r 分组必须携带完整的路由信息，而a o d v 分组只需包含目的地址。 d s r 的路由响应也比a o d v 的大，因为它们包含沿着路由的每个节点的地址， 而a o d v 路由响应只需携带目的端i p 地址和序列号。d s r 的内存开销也稍微大 一些，因为d s r 需要记录全部路由，而在a o d v 中仅记录下一跳信息。 由于采用源路由方式，d s l 渤议在路由过程中可避免出现路由环，同时中间 节点不必存储转发消息所需的路由信息。路由发现搜索和路由维护是以纯粹的 “按需打的方式工作的。不同于其他的路由协议，d s r 协议本身完全不要求发送 任何形式的路由报文。由于d s r 不发送周期性的路由报文，所以当网络中所有的 节点都近似静止并且相互通信的节点都具备到达彼此的路由的情况