（通信与信息系统专业论文）无线mesh网络路由协议的研究与实现.pdf

武汉理工大学硕士学位论文 摘要 作为一种自组织、自配置的新型多跳宽带无线网络，无线m e s h 网络具有更 容易的组网方式、更高的速率、更稳定的性能和更低的成本等优点。同时无线 m e s h 网络还可以解决多种异构无线网络之间的相互联通的问题。路由是无线 m e s h 网络最重要的技术之一，确保网络能够正确运行的关键就是要求具有高效 率以及高质量通信的路由协议。所以，开发和研究适合于无线m e s h 网络的路由 协议在理论与应用中都具有非常重要的意义。 本文首先对无线m e s h 网络的两类路由协议：主动式路由协议和被动式路由 协议进行了研究，其中重点分析了d s d v 、d s r 和a o d v 这三个典型的路由协 议。并利用网络仿真软件n s 2 3 3 分别在静止和移动的环境下，对这两类路由协 议的性能进行了仿真分析和比较。然后，本文在a o d v 协议的基础上提出了一 种考虑节点的网络拓扑结构变化的路由协议n t a o d v 。n t a o d v 路由协议通过 引入抑制因子，对网络中拓扑结构变化快的节点进行抑制，优先选取具有稳定 的拓扑结构的节点来建立一条更可靠、生命力更强的路由链路。在n t a o d v 协 议中，设计了新的路由判据以及路由判据的权值函数。新的路由判据综合考虑 了跳数、节点的网络拓扑结构变化和抑制因子，并设计了线性和指数两种形式 的权值函数。 接着，本文对n t a o d v 路由协议的基本结构和具体实现进行了详细的分析， 通过修改并重新编译n s 一2 3 3 中a o d v 协议的源代码得到改进之后的n t a o d v 协议。并设置不同的抑制因子取值和节点的移动速率，对n t a o d v 协议进行仿 真分析。仿真过程包括两部分：第一部分是分析了抑制因子对网络性能的影响， 通过仿真结果，得到了抑制因子理想的取值范围；第二部分是研究节点的拓扑 变化对网络性能的影响。仿真结果表明，改进之后的n t a o d v 协议对网络的封 包送达比例和封包平均点到点延迟时间这两个性能指标都有着显著的提高，特 别是在节点拓扑结构变化频繁的网络环境中。最后，本文在n t a o d v 协议的基 础上通过整合e v a l v i d 和n s 2 来构建一个无线多媒体图像传输的仿真和p s n r 评 估系统m y e v a l v i d 。 关键词：无线m e s h 网络，n t a o d v 路由协议，抑制因子，权值函数 武汉理工大学硕士学位论文 a b s t r a c t a san e w t y p eo fs e l f - o r g a n i z a t i o n , s e l f - c o n f i g u r i n ga n dam u l t i h o pb r o a d b a n d w i r e l e s sn e t w o r k ，w i r e l e s sm e s hn e t w o r kh a sh i g h e rr a t e ，e a s i e rn e t w o r k i n gm o d e ， l o w e rc o s t ，m o r es t a b l ep e r f o r m a n c ea n do t h e ra d v a n t a g e s i ti sa b l et os o l v eav a r i e t y o fi n t e r c o r m e c t i o nb e t w e e nh e t e r o g e n e o u sw i r e l e s sn e t w o r k s r o u t i n gp r o t o c o li so n e o ft h em o s tc r i t i c a lt e c h n o l o g i e sf o rw i r e l e s sm e s hn e t w o r k ，s oah i g h q u a l i t y r o u t i n gi sa b l e t oe n s u r et h a tt h en e t w o r kc a nw o r kc o r r e c t l y t h e r e f o r e ，i ti sv e r y i m p o r t a n tt or e s e a r c ha n dd e v e l o pam o r es u i t a b l er o u t i n gp r o t o c o lf o rw i r e l e s sm e s h n e t w o r kb o t l li nt h et h e o r ya n da p p l i c a t i o n s f i r s t , t h er o u t i n gp r o t o c o l so fa c t i v er o u t i n ga n dp a s s i v er o u t i n gh a v eb e e n r e s e a r c h e d ，a n das i m u l a t i o na n a l y s i so nt h e s et w ot y p e so fr o u t i n gp r o t o c o l s ( d s d v , d s ra n da o d v ) h a sb e e nf i n i s h e db yn s 一2 3 3i ns t a t i o n a r ya n dm o b i l ee n v i r o n m e n t r e s p e c t i v e l y t h e n ，o nt h eb a s i so fa o d v , t h i sp a p e rp r e s e n t sar o u t i n gp r o t o c o l n t a o d v , i nw h i c hc h a n g i n go fn o d e s n e t w o r kt o p o l o g y a r ec o n s i d e r e d i n n t a o d v , t h en o d e 、析t l las t a b l et o p o l o g yi ss e l e c t e dt oe s t a b l i s ham o r er e l i a b l ea n d s t r o n g e rv i t a l i t yr o u t i n gl i n kb yi n t r o d u c i n gi n h i b i t o r yf a c t o r i nn t a o d v , an e w r o u t i n gc r i t e r i aa n dan e wr i g h t v a l u e df u n c t i o na r ed e s i g n e d t h en e wr o u t i n gc r i t e r i a t a k ei n t oa c c o u n to fr o u t i n gh o p s ，t h ec h a n g i n go fn o d e s n e t w o r kt o p o l o g ya n d i n h i b i t i n gf a c t o r a n dt w ok i n d so fl i n e a ra n de x p o n e n t i a lf o r m so fr i g h t - v a l u e d f u n c t i o n sa r ed e s i g n e d t h e n , t h eb a s i cs t r u c t u r ea n dr e a l i z a t i o no f n t a o d va r es t u d i e d t h en t a o d v i sr e a l i z e db ym o d i f y i n ga n dr e - c o m p i l i n gt h es o u r c ec o d ef o ra o d vi nn s 2 3 3 a s i m u l a t i o no fn t a o d vi sd o n ei nt h ed i f f e r e n ti n h i b i t o r yf a c t o ra n dd i f f e r e n ts p e e d o fn o d e s t h es i m u l a t i o np r o c e s si sc o n s i s t e db yt w o p a r t s t h ef i r s tp a r ti st oa n a l y z e t h ei m p a c to fi n h i b i t o r yf a c t o ro nn e t w o r kp e r f o r m a n c e t h ei d e a lv a l u eo fi n h i b i t o r y f a c t o rc a nh eo b t a i n e db yt h es i m u l a t i o nr e s u l t s t h es e c o n dp a r ti st oa n a l y z et h e i m p a c to fn o d e s s p e e do nn e t w o r kp e r f o r m a n c e i ts h o w st h a tt h ei m p r o v e dr o u t i n g p r o t o c o lo fn t a o d vh a sas i g n i f i c a n ti m p r o v e m e n to nn e t w o r k sp a c k e td e l i v e r y f r a c t i o na n da v e r a g ee n d - t o e n dd e l a y , e s p e c i a l l yi nt h en e t w o r ke n v i r o n m e n tw i m t h et o p o l o g yo fn o d e sc h a n g i n gf r e q u e n t l y 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 ；r o u t i n gp r o t o c o lo fn t a o d v ；i n h i b i t o r yf a c t o r ； r i g h t - v a l u e df u n c t i o n n 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其它教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 签名： 兰l 】幺缸日期：碰壁：6 ：丝 学位论文使用授权书 研究生( 签名) 主d 石如导师( 签；艺萝2 才期切( 扎厂伊 武汉理工大学硕士学位论文 第1 章绪论 1 1 课题研究的背景、目的及其意义 在各种无线通信技术蓬勃发展的同时，一种新的无线网络技术一无线 m e s h 网络正逐渐成为了人们关注的焦点之一。无线m e s h 网络( 即无线网状网) 也称为无线多跳网，可以和多种宽带无线接入技术如i e e e 8 0 2 1 1 、8 0 2 1 6 、8 0 2 2 0 以及3 g 移动通信等技术相结合，组成一个含有多跳无线链路的网状网络【。这种 无线网状网不仅仅可以大幅度扩展无线系统的覆盖范围，同时还能提高无线系 统的带宽容量和通信可靠性，是一种非常有发展前途的宽带无线接入技术【2 1 。 无线m e s h 网络不同于传统的无线网络，它是一种新型的宽带无线网络结构， 也是一种大容量、高速率的分布式网络。它可以看成是无线局域网( w l a n ) 和移动自组织网络( a d h o e ) 的融合，并发挥了两者的优势，是因特网的无线版 本【3 1 。 在传统的无线局域网中，每一个客户端都需要通过一条与接入点( a p ) 相 连接的无线链路来访问网络，用户之间必须首先接入一个固定的接入点，才能 进行相互通信，这种网络结构称之为单跳网络；而在无线m e s h 网络中，任何无 线设备节点都可以同时作为a p 和路由器使用，网络中的每个节点都可以发送和 接收信号，每一个节点都可以与一个或者多个对等节点直接通信，这种接入方 式也就是多跳接入。这样，传统w l a n 中一直存在的可伸缩性低和健壮性差等 诸多问题由此迎刃而解。无线m e s h 技术的出现，代表着无线技术的又一大跨越， 在家庭、企业和公共场所等等多个领域中都有着非常广阔的应用前景1 4 1 。 然而，作为一种新型的应用网络，无线m e s h 网络想要成功的实现无线m e s h 网络产品，最终形成实用的高效的网络，仍有相当多的关键技术需要我们来解 决。根据通信网络的分层思想看来，目前各个层最关键的一些技术问题有【5 1 ：物 理层的天线技术，因为每一个节点都需要和各个方向上的多个节点进行通信， 如果简单的采用全向天线，覆盖的范围会非常有限，而且还会带来干扰，这样 就会导致频谱利用率的下降以及网络容量的减小，因此我们需要研制出适合于 无线m e s h 网络特点的新型天线技术；m a c 层的动态带宽分配管理技术，因为宽 带无线接入设备的频谱资源通常都是有限的，所以必须充分的利用信道资源， 武汉理工大学硕士学位论文 当前人们的研究集中怎样提高系统的容量、吞吐量等方面；网络层的路由选择 技术，影响网络性能的一个主要的因素就是它的路由协议，一个高质量和高效 率的路由协议是确保这个网络能够高效正确运行的关键。传统的因特网路由协 议主要是针对固定的有线网络而开发的，他们都不适合于无线m e s h 网络。移动 自组织网络( a dh o c ) 的路由协议研究虽然已经取得了一定的成果。无线m e s h 网络虽然是继承了移动自组织网络的优点，但是无线m e s h 网络和传统的移动自 组织网络在节点的移动性、业务的模式等方面还是有所区别的1 6 ，因此，先前的 针对移动自组织网络所开发的一些路由协议也就不能够被直接应用到无线m e s h 网络了。于是，研究和开发适用于无线m e s h 网络自身特点的路由协议在理论与 实际应用中就显得尤为重要了。 1 2 国内外研究现状 长期以来，虽然国内外针对无线m e s h 网络的路由协议进行过相当多的讨论 和研究，但是，到目前为此，还没有针对无线m e s h 网络以及移动自组织网络的 正式标准的路由协议m 。不过，根据目前国内外一些对无线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 网络的自身特点考虑下面的四个因素【8 】： ( 1 ) 路由的健壮性。对于任何一个网络而言，路径度量的不稳定对其性 能来讲都是不利的，改变太频繁会导致大量的路由更新，并且路由协议在路 由更新频繁的情形下不能够形成一致，而且可能会破坏常规的网络运转。路 径衡量的健壮性取决于被路由策略捕捉到的路径的类型，其具体类型可以分 为拓扑依赖型与负载感知型。 ( 2 ) 确保拥有最好性能的路径的权重最小。设计出的路由判据要可以捕 捉影响到网络路由性能的一些参数，以保证无线m e s h 网络的资源被有效的利 用，这些参数主要有链路的容量、路径的长度、干扰以及丢包率等。 ( 3 ) 确保没有路由环路存在。通过保序性能够判断路由中是否会存在路 由环路。 ( 4 ) 能够找到有效的算法用来计算出最小代价的路径。保序性除了决定 2 武汉理工大学硕士学位论文 是否会存在环路路由外，同时路由判据必须保序是存在这个有效算法的充分 和必要的条件。 目前，国内外针对无线m e s h 网络的路由协议算法的研究主要有以下几种： 基于跳数( h o pc o u n t ) 的路由协议算法1 9 1 ：基于h o p 的路由协议算法普 遍使用在目前的路由协议( 如d s r 、d s d v 、a o d v 、t o r a ) 中，它能够避免 产生路由环路，因为它拥有保序性。j o s hb r o t h 等人利用n s 2 网络仿真工具， 在同样的仿真环境中，仿真和比较了d s d v 、a o d v 、d s r 和t o r a 这四种路 由协议的性能。最后得出这样的结论【1 0 1 在暂停时间长( 节点移动率与移动的速 率都不高) 时，d s d v 协议基本上能够传送所有的数据封包，但是d s d v 协议 的收敛性会随着节点移动速率的增加而越来越差。此外，d s d v 协议的运行有一 定的可预测性。在四种协议当中t o r a 协议的性能是最差的，t o r a 协议会随 着数据源的不断增加而生成许多路由控制报文，从而使网络不能够容纳而引起 数据封包大量的丢失。d s r 协议在各种移动速率情况下运行的都非常好，数据 封包的送达比例通常在9 5 以上，因为d s r 协议使用了源路由，所以d s r 协议 增加了数据封包头部的长度。在各种移动速率的情况下，a o d v 协议减少了数 据封包头部的字节数的同时，可以达到与d s r 协议相同的效果。但是与d s r 协 议相比，a o d v 协议需要发送更多的路由控制报文，尽管它减少了数据封包的 字节数。 s a m i rr d a s 等人在不同的网络大小、网络负载以及节点移动速率的环境下， 对a o d v 和d s r 这两种按需路由协议的性能进行了研刭1 1 1 ，结果表明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 协议可以通过目的序列号机制来防止产生路由环路。在节点总数少、 负载低和移动速率小的情况下，就网络吞吐量和节点端到端平均时延来说d s r 协议的性能要优于a o d v 协议；反之，在负载较高、移动速率较大时a o d v 协议 的性能比d s r 协议好。总的来讲，d s r 协议的路由开销l 匕a o d v 协议低。 张海林在a o d v 协议的基础上提出了改进的a o d v 路由算、法【1 2 】，在新的路由 算法里，路由层采用跨层操作，而不是使用周期性地发送h e l l o 消息封包，当路 由层每次要发送控制报文或者数据报文时，都会将本节点的最新序列号信息放 置在报文中一并传到m a c 层，由于m a c 层采用i e e e 8 0 2 1 1 协议，而该协议指出： m a c 层的数据帧头部字段中的a d d r e s s 4 ( 该字段用于存放b s s i d ) 这个字段在网 武汉理工大学硕士学位论文 络没有进行分群时闲置没用，于是，可以使用m a c 层的数据帧中a d d r e s s 4 这个 头部字段来放置该节点的序列号的值。当某个节点的m a c 层收到了从邻居节点 传送过来的数据帧( 控制数据) 时，该节点首先从接收到的数据帧头部中提取邻 居节点的m a c 地址和最新序列号值，然后将其上传到路由层更新路由表项。当 源节点向目标节点发送数据封包时，如果在路由表项中找不到可用的路由，则 源节点向其邻居节点广播路由请求报文，邻居节点收到路由请求报文后，判断 自己是不是目标节点或者有没有到目标节点的路由，没有则继续广播路由请求 报文直到找到有到目标节点路由的节点或者找到目标节点本身。但是如果频繁 的进行此步骤，则会 j 1 居l j m e s h 网络的网络负担。 任智等人则提出了改进之后的c l a o d v 与a l a r 路由协议。c l a o d v 协议 中【1 3 1 ，路由层通过收到的m a c 数据帧( 单播广播) 所携带的信息来更新路由表 的表项，而不需要传送h e l l o 消息，如果在一定的时间期限内m a c 层没有发送数 据帧，则生成w l a n ch e l l o 帧来替代h e l l o 帧，采用这种机制，可以减少网络中相 应的控制报文的数量，从而节省了网络的资源；在a l a r t # 议中，如果可以确任 目的节点的大概位置，则只需向目的节点的这个大致位置所在的方向上广播路 由请求报文，这样就减少了网络中产生的路由请求报文的数量，从而节省了网 络的带宽资源。 k oy o u n g b a e 等人提出了使用l a r ( l o c a t i o n a i d e dr o u t i n g ) 【1 4 】，该协议通 过g p s ( g l o b a lp o s i t i o ns y s t e m ) 定位获取源节点以及目标节点的位置从而大大 降低了路由请求报文的洪泛范围，进而解决了大量的路由请求报文的问题。 基于期望传输次数的路由协议算法：k o k s a lce 等人提出了期望传输次 数路由协议算法1 1 5 】。定义期望传输次数( e t x ) 路由协议算法为m a c 层使用 一条链路成功传送一个数据封包需要的期望传输次数。利用在数据链路层发 送广播包，来对e t x 进行估计。路径上所有链路的e t x 的和被定义为该路径 的权重，协议选择最小权重的路径。e t x 具有很多的优点：e t x 量度拥有保 序性，它能够保证最小代价路径和避免了环路路由的产生；e t x 量度还能够 捕捉到数据封包的丢失率以及路径长度的影响；节点使用广播包来代替以前 的单播包，在一定程度上减小了网络的开销。e t x 量度的最主要的缺点是它 没有直接考虑数据传输速率以及链路的负载，同时它也没有考虑到可能存在 的干扰问题。 基于期望传输时间的路由协议算法：d r a v e sr 等人提出了期望传输时 间路由协议算法【l6 1 ，单个链路上的期望传输时间值( e t t ) 被定义为m a c 层 4 武汉理工大学硕士学位论文 使用一条链路成功交付一个数据封包需要的期望传输时间。与e t x 类似，路 径上各个链路的e t t 值的和被定义为该路径的权重，协议选择拥有最小权重 的路径。e t t 路由协议算法考虑了数据传输速率这个因素，它是对期望传输 次数e t x 算法的一种改进。e t t 算法和e t x 路由协议算法一样也是保序的。 该算法的缺点在于依旧没有考虑流内和流间的干扰。 加权的累计传输时间路由协议算法：k r a v e t sr 等人提出了加权的累计 传输时间( w c e t t ) 路由协议算法【1 7 l ，该算法弥补了e t t 算法没有考虑流内 干扰的问题，可以降低流内干扰带来的影响，w c e t t 使用的方法是尽可能减 少在一个数据流所经过的路径上采用同一信道中的节点的数量。w c e t t 路由 协议算法的缺陷是忽略了流间干扰的影响；其次也是致命的一点是它不具有 保序性，因此，它不能保证最小代价路径和避免环路路由的产生 此外，还有消息完整性检查( m i c ) 路由协议算法等，m i c 算法是对 w c e t t 算法的改进【l s l ，主要解决了数据流间干扰以及不保序的问题。 根据以上各人对相应的算法进行分析和仿真之后，从丢包率、吞吐量、 延时、保序等方面得到了以上无线m e s h 网络路由判据性能的综合评价表【1 9 1 。 表1 1路由判据性能综合评价 判据名称 丢包率吞吐量延时保序负载均衡 数据流数据流 指标 内干扰间干扰 h o p 是 否否否 e t x 考虑考虑是 否否否 e t t 考虑考虑是 否否否 w c e t t考虑考虑考虑否否是 否 m i c 考虑考虑考虑直接应用时否 否是是 在上面提到的研究成果中都没有将网络节点的移动性考虑其中，无线m e s h 网络作为一种自组织的网络结构，其网络节点的移动性具有不可预测性，如果 节点频繁的高速移动，则网络的拓扑结构也会频繁的发生变化，可能导致之前 建立的路由失效，需要不断的进行路由发现和路由维护的过程，造成网络开销 大，频繁的路由发现过程还会造成寻找新路由的时间开销，影响网络的实时性。 本文提出的n t a o d v 路由协议充分考虑节点的网络拓扑结构变化，引入了抑制 因子，对移动速度大的节点进行抑制，使选择的路由更可靠，生命力更强。 武汉理工大学硕士学位论文 1 3 本文的主要工作 全文共分5 章，内容安排如下： 第一章论述本文的研究背景及其意义，介绍了国内外相关技术的研究现状， 并总结了课题研究中所做的主要工作。 第二章对无线m e s h 网络的路由协议进行研究。首先分析无线m e s h 网络路由 协议的特点；然后对无线m e s h 网络的两类路由协议：主动式路由协议和被动式 路由协议进行了深入的研究，其中主要分析d s d v 、d s r 和a o d v 这三个典型的 路由协议；最后利用网络仿真工具n s 2 3 3 分别在静止和移动的环境下对无线 m e s h 网络的两类路由协议( d s d v 、d s r 和a o d v ) 的性能进行了仿真，并对仿 真结果进行了详细分析。 第三章在前一章节的基础上，提出一种考虑节点网络拓扑结构变化的路由 协议n t a o d v 。首先详细阐述了n t a o d v 协议的设计思想；然后解析了 n t a o d v 协议的基本结构和具体实现过程；最后设计了新的路由判据和两种权 值函数：线性权值函数和指数权值函数。 第四章利用n s 一2 3 3 对n t a o d v 路由协议进行仿真分析研究。首先简要介绍 了本文使用的网络仿真工具n s 2 ；然后详细阐述了n t a o d v 路由协议在n s 2 3 3 中a o d v 协议源码基础上进行改进的具体实现过程，并设置了n t a o d v 协议在 n s 一2 3 3 中的仿真环境；接着对n t a o d v 协议进行了仿真分析和研究，仿真过程 包括两大部分：第一部分是分析了抑制因子对网络性能的影响；第二部分是研 究节点的拓扑变化对网络性能的影响。对这两部分的仿真结果进行了详细的分 析。最后，在n t a o d v 协议的基础上通过整合e v a l v i d 和n s 2 来构建一个无线多 媒体图像传输的仿真和p s n r 评估系统m y e v a l v i d 。 第五章对全文进行工作总结和下一步工作的展望。 6 武汉理工大学硕士学位论文 第2 章无线m e s h 网络的路由协议研究 2 1 无线m e s h 。网络概况 m e s h 路由器域一 。乒一卜争 i ，, , i i： ； i ， m e s h 终端域昏：! 一二争 疑￥一笃 7 武汉理工大学硕士学位论文 扑结构。这种拓扑结构中一般都存在一个中心节点，例如移动通信系统中的 基站、8 0 2 1 1 无线局域网( w l a n ) 中的接入点( a p ) 等等。中心节点与各个无 线终端通过单跳无线链路相连，控制各无线终端对无线网络的访问；同时， 又通过有线链路与有线骨干网相连，提供到骨干网的连接。而在无线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 路由器中的网关和网桥与各种现有的无线网络进行集成， 如无线传感器网络、w i f i 和w i m a x 。因此，通过综合的无线m e s h 网络，终 端用户就可以同时使用多种无线网络。 在无线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 路由器网状互连形成的，无线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 2 i 。m e s h 网用户终端可以是手提电脑、 手机、p d a 等装有无线网卡、天线的用户设备。这种结构实际上就是一个 a dh o e 网络，可以在没有或不便使用现有的网络基础设施的情况下提供一种 通信支撑，客户端m e s h 结构中的各个用户终端除了收发数据包外，还应该 具有路由和自组织功能，任意一个节点发送的数据包都可以通过其他的客户 端进行转发到达目的节点。值得关注的是，在客户端m e s h 结构中，终端用 户的移动性是一个具有挑战性的问题，因为网络拓扑结构和连接性会随着用 户的移动而不断的变化。 8 武汉理工大学硕士学位论文 m e s h 客户端可以通过m e s h 路由器接入骨干m e s h 网络形成m e s h 网络的 混合结构，这种结构提供与其他一些网络结构的连接，增强了连接性，扩大 了覆盖范围【2 3 1 。 2 2 无线m e s h 网络路由协议的特点 在上一章节中提到无线m e s h 网络路由协议的研究通常都遵循着一个同样的 模式，那就是首先是分析目前已经相当成熟的a dh o c 网络中比较经典的路由协 议，然后结合无线m e s h 网络自身的特点来选择对协议中的某一个角度进行改进。 最后，就得到了适用于无线m e s h 网络的路由协议。无线m e s h 网络作为一种自 组织、自配置的动态网络，其路由协议应该具有一些特点【2 4 】。 ( 1 ) 移动性。在上一章节中谈到，无线m e s h 网络主要是由m e s h 路由器和 m e s h 终端构成f 2 5 】。其中，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 网络中，无线链路的质量会由于 无线环境的变化而不断变化，因而路由算法必须能够应对链路质量的变化，而 且，当某个链路无效时，路由算法必须快速提供被选的路由【2 6 】。 ( 3 ) 分布式。无线m e s h 网络路由算法必须是分布式的，因为不可能利用 一个集中式的实体来为所有的路由器计算路由。因此，每个路由器都必须能够 为每个数据分组自动计算转发路由决策。 除此之外，无线m e s h 网络的路由算法在多射频等环境中还必需具有一些其 它的特点【2 刀。 2 3 无线m e s h 网络的路由协议的研究 根据路由协议的建立过程不同，将无线m e s h 网络的路由协议分为：主动式 路由协议和被动式路由协议。 9 武汉理工大学硕士学位论文 2 3 1 无线m e s h 网络主动式路由协议的研究 主动式路由协议又称之为先验式路由协议和表驱动路由协议【2 8 】。主动式路由 协议在数据传输之前就已经确定了传输路径，它提前计算路由表，并通过周期 性的更新消息来维护路由表信息。图2 2 是部分主动式路由协议。 图2 2 主动式路由选择协议 在主动式路由协议中，每一个节点都维护了j 张或者多张该节点到网络中 其他节点的路由信息表，记录了本节点到其它所有节点的最新路由信息，并且， 节点之间通过交互信息来响应网络拓扑结构的变化以更新路由表，维护网络拓 扑结构和路由信息的一致性和准确性。上图中的这些协议之间的主要区别是各 个协议维护的路由信息表的类型和数量不同以及网络拓扑结构发生变化时路由 更新信息在网络中传输的方式不同。 主动式路由协议中最典型的是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 r o u t i n g ) 基于目的顺序号距离矢量协议【2 9 1 。d s d v 是在经典的b e l l m a n f o r d 路由 机制的基础上改进的表驱动路由协议，其中的一个改进点就是避免了在路由表 中产生路由环路，网络中的每个节点都维护了一个包含跳数的到网络中其它节 点的路由表，每一个路由表项都记录了到目的节点的跳数和下一跳节点的地址。 每一个路由表项都被目的节点分配了一个序列号。这个序列号用来区分过期的 路由和最新的路由，节点优先选择序列号大的路由，如果序列号相同，则优先 选择跳数少的路由，这样就可以避免路由环路的产生。更新的路由信息被周期 性的在网络中传输，用来维护路由表的一致性。路由更新消息可以采用两种类 型的方式：第一种被称之为全清除方式，它包含所有可能的路由信息，需要多 1 0 武汉理工大学硕士学位论文 个网络协议数据单元( n e t w o r kp r o t o c o ld a t au n i t s ，n p d u s ) 。第二种是数据更 小的增量更新方式，它只传输那些在最后一次全清除之后发生变化的路由信息， 因此，减少了网络的流量，这些路由信息应该被放置在一个标准的n p d u 中。新 的路由广播消息包含了【3 0 l ：目的地址、到目的地址的跳数、序列号以及唯一的广 播号。拥有最新序列号的路由被节点优先选择，序列号相同时，就选择具有最 小跳数的路由。对于节点移动速率大、拓扑结构变化频繁的m e s h 网络而言，主 动式路由协议会频繁产生大量的路由更新消息来实时的维护路由表的一致性， 这样，就会占用大量的网络带宽资源，从而影响网络的其他性能。 2 3 2 无线m e s h 网络被动式路由协议的研究 被动式路由协议也称为按需路由协议【3 1 1 。被动式路由协议不提前计算路由 表，只有当收到数据请求之后才会执行路由发现过程，图2 3 是部分被动式路由 协议。 图2 3 被动式路由协议 在被动式路由协议中，与主动式路由协议不同，节点平时不需要维护网络 的路由信息表，只有当源节点需要时才建立路由，当一个节点需要发送数据包 到目的节点并且源节点的路由缓存中没有到目的节点的路由时，它首先初始化 个路由发现过程，向邻居节点广播一个包含目的节点信息的路由请求消息， 一旦找到了到达目的节点的路由，则路由发现过程就完成了。 武汉理工大学硕士学位论文 d = 商i 路由响应消息i 一 i _ _ _ _ - _ - _ - - _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ 一 图2 4 路由发现过程 图2 - 4 为被动式路由协议的路由发现过程。当源节点1 有数据要发送到目的节 点6 时，源节点1 就会启动路由发现过程，向邻居节点( 上图中是2 、3 、4 ) 广播 路由请求消息，如此反复，中间节点转发路由请求消息只至目的节点6 ( 假设中 间节点的路由缓存中没有到目的节点的路由) ，目的节点收到从多条路径上转 发来的路由请求消息后，生成一个路由响应消息，并选择适当的路径返回路由 响应消息给源节点1 ，源节点l 收到路由响应消息后便获得了到目的节点6 的路 由，这样路由发现过程就完成了。 在被动式路由协议中，d s r 和a o d v 是应用最为广泛的具有代表性的按需 路由协议【3 2 1 。d s r ( d y n a m i cs o u r c er o u t i n g ，d s r ) 也称为动态源路由协议【3 3 1 ， d s r 的路由请求消息( r r e q ) 中的路由记录字段记录了源节点到目的节点的所 有中间节点的路由信息，图2 5 是d s r 路由请求消息的主要字段内容。 剩余跳数表示该路由请求消息还可以在网络中传输的跳数数，它避免了 r r e q 在网络中无限制的广播下去，初始值为最大跳数值，每经过一个中间节点 时，值减一，当值为0 时，就丢弃该g g e q ；路由大小的初始值为0 ，每一次中间 镒l 目盟点l 剩扩i 路由舯l 请彻l 消息类型陋标识l 路由记录 图2 5d s r 路由请求消息 武汉理工大学硕士学位论文 节点的地址加入到路由记录中时，路由大小的值就) j i l l ；请求i d 是r r e q 的标识 符；跳数标识是最大跳数限制；路由记录字段记录了从源节点到目的节点的所 有中间节点信息。中间节点收至i j r r e q 后，首先检查r r e q 中的源节点和请求i d 序列对是否存在于该节点的路由请求表( 记录了该节点发起和转发的r r e q ) 中， 若存在，则丢弃该r r e q ，表示本节点已经转发过这个r r e q ，不用重复转发了； 若不存在，则查看r r e q q b 的路由记录字段是否已经包含了本节点的地址，如果 包含，则丢弃该r r e q ，不用处理；如果不包含，继续查看r r e q 中的目的地址 是不是本节点的地址，如果是，则本节点就是目的节点，r r e q 中的路由记录字 段的节点地址序列就构成了源节点到本节点的路由。本节点将产生一个路由响 应消息( 砌迮p ) 给源节点，并将路由记录字段中的内容复制到i u 也p 中，源节 点收到目的节点的r r e p 后，路由发现过程就结束了；如果r r e q 中的目的地址 不是本节点，将本节点添加到路由记录字段中，同时向邻居节点广播该r r e q ， 继续路由发现过程。 a o d v ( a dh o eo 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 ) 也称为按需距 离矢量路由协议1 3 4 1 。a o d v 路由协议基于前面提到的d s d v 协议，不过，a o d v 协议只有在需要路由时才广播路由请求报文来建立路由，而不用像d s d v 协议那 样，每个节点都需要维护一个完整的路由协议表。a o d v 路由协议只支持双向链 路的网络。a o d v 包括路由发现和路由维护两个部分1 3 卯。 ( 1 ) 路由发现 当源节点需要向目的节点发送数据并且源节点没有到目的节点的路由时， 源节点就会启动路由发现过程。a o d v 路由协议有着与d s r 类似的路由发现过 程，在a o d v 的路由发现过程中，反向路由和前向路由被建立。如图2 6 是a o d v 协议的路由发现过程状态图。与d s r 协议不同，a o d v 的路由请求消息( r r e q ) 中不需要路由记录字段来记录源节点到目的节点的路由信息，a o d v 的r r e q 包 含下面的几个字段【3 6 l ：源地址、源序列号、广播i d 、目的地址、目的序列号和 跳数计数器。它采用了d s d v 协议的序列号机制，源序列号保证了反向路由的有 效性，它用在r r e q 的广播过程当中；目的序列号保证了前向路由的有效性。 1 3 武汉理工大学硕士学位论文 源节点广播r r e q 妻曩经收挈刈丢弃该nreqrreq 过该 7 i “”“ 否 矗絮哆0 谁勰 刮记瓣盛继 是 节点发送r r e p 是 l 三瓦 图2 6a o d v 协议的路由发现过程 图2 6 所示的路由发现过程中，节点通过源地址和广播i d 序列对来判断收到 的r r e q 是否重复。中间节点需要记录的路由信息有【3 7 】：上游节点( 向本节点发 送r r e q 的节点) 的地址、目的地址、源地址、广播i d 、反向路由超时时长以及 源序列号，用来形成反向路由。另外跳数计数器的值加l 。目的节点( 或有到目 的节点的最新路由的中间节点) 沿着反向路由发送路由响应消息( i u 汪p ) ，当 源节点收到姬p 时，中间节点也相应的生成了前向路由，源节点通过前向路由 可以发送数据报文给目的节点了。 ( 2 ) 路由维护 a o d v 协议的路由维护