（计算机应用技术专业论文）无线mesh网络中可扩展性路由策略的研究.pdf

南京邮电大学硕士研究生学位论文 摘要 摘要 无线m e s h 网络是一种新型的宽带无线通信网络，它既类似于a dh o e 网络具有自形成、 自组织、自修复、多跳通信等特点，又因为其移动性较低、拓扑结构相对稳定等特点区别 于a dh o c 网络，可以看成是w l a n 和a dh o e 网络的融合。从理论上来说，这种开放式 的网络架构可以获得较好的可扩展性，然而无线m e s h 网络的大规模组网却面临着较多的 实际问题，现有的通信协议随着网络规模的扩大，都存在些实现的难题和不足。无线 m e s h 网络的路由协议多是借鉴于a dh o e 网络的路由协议，随着网络规模的扩大，路由协 议的开销急剧上升，算法收敛困难，路由延迟增大，路由修复困难，网络性能严重下降。 因此根据无线m e s h 网络自身的特点，设计出一种路由策略，来提高其可扩展性，是一项 富有挑战性的研究课题。 本文立足于无线m e s h 网络区别于其它移动自组织网络的特点，分析比较了现有的路 由协议在可扩展性方面的特点和不足，然后借鉴核心树的逻辑拓扑结构和自适应地址块分 配机制，定义了m e s h 适配树的逻辑拓扑结构，提出并实现了m e s h 树分布式链路状态 ( m ，m l s ) 路由策略，理论上证明m t d l s 的可扩展性之后，用o p n e t 仿真工具对算法 进行了仿真。 所提出的m t d l s 路由策略通过将网络拓扑反映在逻辑地址上，然后根据每个节点所 维护的邻居节点状态列表，可以判断出一个数据包该往哪个方向( 区别于下一跳) 转发。 下一跳地址是从每个转发节点的邻居节点状态列表中得到的。在数据转发时，路由的实施 过程将不再需要经历传统的路由发现，从而就省去了数据包转发之前路由路径的发现时 间，同时每个节点仅仅维护自己的n 跳的邻居节点的信息，相比传统的路由协议中需要维 护大量的路由表节省了很多存储空间，并且减少了通信开销以及能量消耗。仿真结果证明 了算法的有效性。 关键词：无线m e s h 网络；可扩展性；路由协议；分布式算法 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 ( w m n ) i sak i n do fn e w l y d e v e l o p e dw i r e l e s sc o m m u n i c a t i o n n e t w o r k w i t hc h a r a c t e r i s t i c so fs e l f - f o r m i n g ，s e l f - o r g a n i z a t i o n ，s e l f - h e a l i n ga n dm u l t i h o p c o m m u n i c a t i o n , w m ni ss i m i l a rt oa dh o en e t w o r k s ，b u tn o te q u a lt o b e c a u s eo fi t sl o w e r m o b i l i t ya n dm o r es t a b l en e t w o r kt o p o l o g y i tt a i lb er e g a r d e da st h em e r g e n c eo fw l a n a n d a dh o cn e t w o r k s i nt h e o r y , t h i so p e nn e t w o r ka r c h i t e c t u r ec a l lr e a c hb e t t e rs c a l a b i l i t y ；h o w e v e r t h el a r g es c a l eo fw m ni ss t i l lf a c i n gl o t so fp r a c t i c a lp r o b l e m s ，i e ，i m p l e m e n t a t i o np r o b l e m s f o rt h ee x i s t i n gc o m m u n i c a t i o np r o t o c o l s m a n yr o u t i n gp r o t o c o l so f 、v l v n sw h i c ha r em o s t l y r e f e r r i n gt oa dh o en e t w o r k sh a v ec e r t a i np r o b l e m sw h i c hm a y l i m i tt h e i rs c a l a b i l i t yt ol a r g e n e t w o r k s ，s u c ha sr a p i dr i s eo ft h er o u t i n go v e r h e a d ，t r o u b l eo fa l g o r i t h mc o n v e r g e n c e ，i n c r e a s e d m u t i n gl a t e n c y ，d i f f i c u l t i e si nr o u t i n gr e p a i r i n g ，w h i c hr e s u l t si ns e r i o u sd e c r e a s eo fn e t w o r k p e r f o r m a n c e t h e r e f o r e ，b a s e do nt h ec h a r a c t e r i s t i c so ft h ew m n s ，d e s i g n i n gab r a n d n e wr o u t e s t r a t e g yt oi m p r o v ei t ss c a l a b i l i t yi sar e s e a r c ht o p i cw i t hg r e a tc h a l l e n g i n g t h et h e s i ss t a n d so nt h ec h a r a c t e r i s t i c so fw m n sd i s t i n g u i s h e df r o mo t h e rw i r e l e s s n e t w o r k s ，a n a l y z e st h ea d v a n t a g e sa n ds h o r t a g e so fe x i s t i n gr o u t i n gp r o t o c o l si ns c a l a b i l i t y , d e f i n e sal o g i cn e t w o r kt o p o l o g y ( m e s ha d a p t i v et r e e ) r e f e r r e dt ok e r n e lt r e et o p o l o g ya n d a d a p t i v eb l o c ka d d r e s s i n gs c h e m e ，b r i n g sf o r w a r da n dr e a l i z e st h ep r o t o c o ls t r a t e g yc a l l e d m e s ht r e ed i s t r i b u t e dl i n ks t a t e ( m t d l s ) a r e rp r o v i n gt h es c a l a b i l i t yo fm t d l si nt h e o r y , o p n e ti su s e dt os t i m u l a t i n g l ya n a l y z ei t sv a r i o u sp e r f o r m a n c em e t r i c s b yr e f l e c t i n gt h en e t w o r kt o p o l o g yt ol o g i ca d d r e s s e s ，m t d l sc a nt e l lt o w a r d sw h i c h d i r e c t i o n ( r a t h e rt h a nn e x th o p ) ap a c k e ts h o u l db er e l a y e d t h en e x th o pi sd e r i v e df r o me a c h r e l a y i n gn o d e sn e i g h b o rl i s tt a b l e d u r i n gd a t ar e l a y i n g ，r o u t i n gi sc a r r i e do u tw i t h o u tg o i n g t h r o u g ht r a d i t i o n a lr o u t ed i s c o v e r ya n de a c hn o d ej u s tm a i n t a i n si t sn h o p sn e i g h b o rl i s t t h i s s c h e m e ，c o m p a r i n gw i t ho t h e rr o u t i n gp r o t o c o l ，e l i m i n a t e st h ei n i t i a lr o u t ed i s c o v e r yl a t e n c y , s a v e ss t o r a g es p a c eo t h e r w i s en e e d e df o rr o u t i n gt a b l e ，a n dr e d u c e st h ec o m m u n i c a t i o no v e r h e a d a n de n e r g yc o n s u m p t i o n t h ee f f e c to ft h ea l g o r i t h m sh a sb e e nt e s t i f i e db yt h es i m u l a t i o nr e s u l t s k e yw o r d s ：w i r e l e s sm e s hn e t w o r k s ；s c a l a b i l i t y ；r o u t i n gp r o t o c o l ；d i s t r i b u t e da l g o r i t h m i l 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也 不包含为获得南京邮电大学或其他教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文 中作了明确的说明并表示了谢意。 研究生签名：奎秘日期i 丝鸳& 坐 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保 留本人所送交学位论文的复印件和电子文档，可以采用影印、缩印 或其它复制手段保存论文。本人电子文档的内容和纸质论文的内容 相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授 权南京邮电大学研究生部办理。 研究生签名：旌恁泣导师签名： 南京邮电大学硕士研究生学位论文 第一章绪论 1 1 课题研究背景及意义 1 1 1 课题背景 第一章绪论 无线网络的发展日新月异，新的技术和标准不断涌现，新的无线网络架构也不断被提 出；随着无线用户对高速宽带接入的需求，无线m e s h 网络( w i r e l e s sm e s hn e t w o r k ，w m n ) 技术应运而生【1 1 。“m e s h 的中文含义为“网孔”，m e s h 网络是指所有的节点( 如路由器、 交换机、主机等) 都相互连接。实际中绝大多数的m e s h 网络只是通过部分节点相互连接， 各用户节点可以通过相邻的用户节点，并以多跳通信方式实现到骨干网的连接，新用户节 点可以通过它周围的其它用户节点很方便地接入到网络中。在网络扩展时，由于不再需要 中心节点，从而可以极大地减少整个网络的建设成本1 2 】。过去的无线网络，无论是移动a d h o c 网，还是无线区域网( 无线个人域网w p a n 、无线局域网，a n 、无线城域网w m a n 、 无线广域网w w a n ) ，以及蜂窝移动网络，都还没有和无线m e s h 网络一样能够支持迄今 为止最大的无线宽带覆盖【3 】。无线m e s h 技术的出现代表着无线网络技术的又一大跨越， 被认为是未来无线通讯技术发展的方向之一，有着极为广阔的应用前景【1 ，4 1 。 无线网络技术是当前获得迅速发展的技术之一，它允许移动用户采用更加灵活方便的 方式接入网络。典型的无线网络w l a n 通常具有两种组网形式1 5 】：中心结构网络 ( i n f r a s t r u c t u r e dn e t w o r k ) 和a dh o e 网络( i n f r a s t u r c t u r e l e s sn e t w o r k ) 。中心结构网络由移 动主机和包含固定有线网关的网络组成。在无线覆盖范围内，移动主机与基站( 固定有线 网关) 进行通信，并可在通信过程中移动。当移动主机离开原基站的无线覆盖范围后，它 可与另一个基站建立连接并通过该基站继续进行通信。在这种组网和通信方式中，基站的 位置是固定不变的，g s m 系统就是采用这种网络组织形式。a dh o e 网络是无线网络的另 一种组织方式；在该网络中，所有节点都处于平等位置，它们之间都可能有通信关系存在， 同时每个节点还有参与组网和中继的义务，网络中的所有节点都具有路由发现和维护的功 能。 无线m e s h 网络可以看成是一种特殊的w l a n ，除移动性较低外，它本质上是一种a d h o e 网络闱。无线m e s h 网络也称为“多跳网络，它是一种与传统无线网络完全不同的新 壹室塑皇盔兰堡主婴塞生兰垡笙奎 蔓二童堡垒 型无线网络技术。在传统的各种无线接入网络中，拓扑结构主要采用点到点或者点到多点， 一般都用一个中心节点与骨干网直接相连，如接入点( a c c e s sp o i n t ，a p ) 、基站等。中心节 点负责控制各用户节点的接入，并提供它到骨干网的网络接口，每个客户端通过一条与中 心节点相连的无线链路来访问网络，用户如果要进行相互通信的话，必须首先访问一个固 定的接入点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 网络来加以缓解。 2 南京邮电大学硕士研究生学位论文 第一章绪论 1 1 2 研究现状 无线m e s h 网络是一种典型的多跳通信网络，具有开放式的网络架构，它不同于传统 的任何有线与无线网络，可以看成是一种w l a n 和a dh o c 网络的融合，并且同时兼顾了 两者的优势，具有独特的特点。无线m e s h 结构作为可以解决“最后一公里”网络接入瓶 颈问题的方案，已被写入i e e e8 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 1l sm e s h 标准中。 无线m e s h 网络和w l a n 一个最大的差别就是其路由功能【4 】。路由技术是无线多跳通 信网络中一项关键性问题，路由算法的好坏直接影响到整个无线m e s h 网络的性能。但由 于无线m e s h 网络是一种新兴的网络技术，目前还没有专门针对无线m e s h 网络路由协议的 正式标准，而国内外对移动a dh o e 网络的自组织算法和路由算法已经有很多成熟的研究 和应用，所以用于无线m e s h 网络的路由协议多数来源于a dh o c 网络路由协议。一个好的 m e s h 路由协议应满足一定的网络性能指标( 如最小跳数、最短往返时延) ，并具有差错容 忍程、负载均衡、可扩展性等特点，同时能支持路由器与客户端的自适应。目前可用于无 线m e s h 网络的路由协议有以下几种【1 ，4 】： ( 1 ) 多判据路由 许多现有的路由协议均以最小“跳数( h o p ) 为标准来选择路由路径。研究表明1 6 一， 该种判据在大多数情况下并非有效，比如在链路质量较差或者网络拥挤的情况下，选择出 来的路由往往都不是最优路由。文献 6 】对几种典型路由判据( 期望传输次数e t x 、往返时 间r 1 阿、数据对延迟时间p k t p a i r ) 与h o p 进行了比较，当节点完全静止时，e t x 的性能 最好，r 1 盯与p k t p a i r 由于冲突的影响性能稍差，但是当网络中节点移动时，h o p 则优于 其他3 种判据。同时，单一的路由判据往往很难反映出链路质量给各个性能指标带来的影 响，多路由判据仍有待研究开发。 ( 2 ) 多信道路由 无线m e s h 网络中，使用多信道的方式有很多种，如单收发器多信道、多收发器多信 道等。文献【8 】对多信道与多收发器的方案进行了理论分析，结果表明，它们都能较大地提 高网络的吞吐量。用于该类路由的新型路由判据加权积累期望传输时间( w c e t t ) 1 9 1 的提出综合考虑了链路质量和最小跳数，在延时和吞吐量之间进行了很好的折衷。 ( 3 ) 多径路由 在源节点与目的节点之间选择多条路径进行数据传输，可以在充分利用带宽等网络资 3 南京邮电大学硕士研究生学位论文 第一章绪论 源的同时获得较好的负载平衡和路由容错。但是，研究表明f l o 】，多径路由较为复杂，尤其 对于仅靠路由表驱动的路由协议。采用多径问题技术后数据包到达的顺序可能得不到保 证，此时，上层协议是否需要做相应的改动等问题还有待研究。目前对多径路由协议的研 究仍然是一个热点。 ( 4 ) 分级路由 随着网络规模的扩大，传统利用广播机制来进行路由查找的方法使得路由开销显著上 升。同时，由于大规模网络将花费很长时间建立路径，从而使得端到端的延时变大，一旦 建立好的路径发生变化，又将需要消耗大量的网络资源，才能进行路由重建。对于这个问 题通常是采用分级路由的思想1 来解决。通过分级技术，在簇内与簇间使用不同的路由， 分别发挥各种路由的特点，从而实现大规模网络的路由。若所有的数据业务都需要通过簇 头转发，那么簇头将成为整个网络的瓶颈；若数据业务不通过簇头转发，该路由的设计将 变得更加复杂。 ( 5 ) 跨层路由 在无线网络中，传输媒介的变化以及干扰的不可预测导致了网络性能在时间和空间上 剧烈波动。路由协议的跨层设计打破现有的网络分层结构设计理念，将分散在各层的网络 信息通过跨层管理模块传递到网络层，可以在最大程度上挖掘无线网络的潜在优势。在过 去的几年时间里，对于跨层路由技术的研究很多，也提出了很多跨层路由协议设计的理论 和方案。在这些研究结果中，有多速率、物理层m a c 层关联的路由协议p a r m a 1 1 】、以 a o d v 为基础进行跨层设计的c l a o d v ( c r o s s l a y e ra o d v ) 路由算法【1 2 】以及巴黎皮埃尔 和玛丽居里大学的研究者提出的一种专用于无线m e s h 网络的，基于干扰估计、分组成功 率和数据传输速率的跨层设计方案【1 3 】。 ( 6 ) 基于地理位置的路由【4 1 与基于拓扑的路由协议相比，基于地理位置信息的路由协议根据节点的地理位置信息 来传送数据包。这类路由协议需要依靠g p s 或类似的定位设备，从而增加了网络成本和复 杂性，并且获得目的节点的位置信息也会给网络带来较大的开销。 可扩展性是路由层中的关键问题之一【1 1 。无线m e s h 网络的可扩展性可以广义地理解 为：当网络规模变大或者网络中存在大量可移动节点的情况下，网络能否维持良好的性能， 并能为用户提供可接受的通信业务。从理论上来说，这种开放式的网络架构可以获得较好 的扩展性【2 1 。然而，在实际的系统中，无线m e s h 网络的大规模组网却面临着较多的实际 问题，现有的通信协议( 包括m a c 协议、路由协议以及传输协议等) 随着网络规模的扩 4 查室坚皇盔堂堡堑塞生堂垡迨塞 墨= 雯丝鎏 大，都存在一些实现的难题和不足【1 4 j 。为了解决无线m e s h 网络在扩展性方面的问题，信 道分配、智能路由、多天线、节点分类和q o s 分级、协作传输等关键技术不断被提出和研 究。 无线网络中，许多路由协议 2 7 , 2 8 , 3 0 ，3 1 1 在进行路径发现时采取对全网进行广播路由请求 信息的机制，但这种机制只适用于小型网络，随着网络规模的扩大，路由开销显著上升并 且网络带宽利用率严重下降。当已经建立起来的路由路径发生链路断裂时，一部分路由协 议 2 7 , 2 8 】采取向所有使用这条断裂链路的相关节点发送错误报告的方法来修复路由路径。对 于小型网络，相关节点能够尽快的收到错误报告，从而采取相应的修复动作，但是随着网 络规模的扩大，网络中平均路由路径长度会显著增加，错误报告发送到相关节点也需要经 过更长的路径，在相关节点收到错误报告进行路由修复前，很可能由于大规模无线链路的 不稳定或者网络中存在快速移动节点使得路由路径中又有其它链路断裂，增加了路由恢复 的难度和效率。因此，这种路由恢复机制很难适合于这种大规模或者存在大量移动节点的 网络。 相对于广播机制，另外一些路由协议【1 9 , 2 2 , 2 3 , 2 4 , 2 9 , 3 2 】采用单播的方法来增强网络的可扩 展性，分簇和分级的路由协议 1 9 , 2 3 , 2 4 , 3 2 贝, 1 j 是其中的代表。分簇路由协议把网络内的所有节 点按照某种规律分成若干簇，每簇选定一个或多个簇头节点，其余节点或与簇头直接相邻 或经过几跳后与簇头相连。簇与簇之间通过某些起网关作用的节点相互连通，实现通信。 通过分级技术，在簇与簇之间的路由和簇内节点间的路由可以采取不同的路由算法来完 成，分别发挥了各种路由的优点。然而，分簇路由协议也有其缺点，网络中的节点需要周 期性的发送信息来维护簇。这些周期性的信息就造成了一部分控制报文的开销和带宽利用 率的下降以及更长的通信时延。另外，如果路由的源节点和目的节点不处于同一簇中，需 要经过网关节点进行转发，则很有可能造成迂回路径。最后，由于节点分组所带来的复杂 性也成为采用分级路由的最大障碍。 除了以上的路径策略，还有其他一些路由协谢18 2 0 ，2 1 , 2 5 , 2 6 是基于距离一向量路由算法 或者是链路一状态路由算法。因为距离一向量路由算法和链路- 状态路由算法不仅仅用到 周期性的状态更新，还在链路状态改变时采用触发更新的方法，这些对于网络中无线链路 不稳定以及存在大量移动性节点的情况也不是完全适用。 1 1 3 课题意义 多跳通信是无线m e s h 网络中普遍使用的一种通信方式，然而当网络规模扩大时，网 5 童室塑皇盔堂塑圭婴壅生兰垡迨窒 蔓= 童堑迨 - - _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ i _ _ _ _ i _ 。- _ _ _ _ - _ - - _ _ _ - _ 。- _ _ _ _ _ 。- _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 。_ _ _ _ - _ _ _ _ _ _ - 。_ _ 。_ _ _ 。_ _ 。一一 络性能会显著下降，路由协议也许无法找到一条可靠的( 路由) 路径，传输协议也许会释 放连接，而m a c 协议也会经历吞吐量的显著下降。造成网络可扩展性较差的原因是随着 网络规模的扩大，端到端的可靠性急剧下降。 在无线m e s h 网络中，由于多跳通信的原因，提高容量与增大覆盖范围成为一对矛盾 体【3 9 l ，因此，研究无线m e s h 网络可扩展性相关技术，其目标是在保持容量的情况下扩大 覆盖范围。众所周知，对于多跳自组织网方式，通信协议面临着可扩展性问题【s 8 1 5 l 。现有 协议包括m a c 协议、路由协议以及传输协议都存在一些实现的难题和不足，典型的协议 如i e e e8 0 2 1 1m a c 协议随着规模扩大，端到端可靠性降低，从而导致t c p 吞吐量性能 明显下降i 引。此外，在一个很大的无线网络中建立一条路由可能会花费较长时间，并且端 到端延时也会很大，甚至即使路由己经建好，路径上节点状态也可能会变化，路由协议将 无法找到一条可靠的( 路由) 路径1 1 6 l 。而现有的无线m e s h 网络的路由协议大多借鉴于a d h o e 网络的路由协议，因此如何根据无线m e s h 网络自身的特点，设计出一种路由策略，来 提高无线m e s h 网络的可扩展性，是一项富有挑战性的研究课题【l 】。 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 ha d a p t i v et r e e ，m a t ) 的概念和自适应地址块( a d a p t i v eb l o c k a d d r e s s i n g ，a b a ) 的机制，提出m e s h 树分布式链路状态( m e s ht r e ed i s t r i b u t e dl i n ks t a t e m t d l s ) 的路由策略和算法来提高无线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 网络的组网结构和网络特点，然后对现有的路由策略进行分析，并重 6 南京邮电大学硕士研究生学位论文第一章绪论 点描述了无线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 网络路由节点移动性较小、 路由信息更新慢等特点，提出了m e s h 树分布式链路状态( m t d l s ) 路由算法，最后对该 协议在可扩展性方面进行了理论分析。 第五章仿真比较：对m t d l s 路由算法进行仿真分析，并与a o d v 路由协议进行比 较，证明该协议在可扩展性方面的优点。 第六章总结和展望：对本文工作进行了总结，并指出需要进一步改进的内容。 7 南京邮电大学硕士研究生学位论文 第二章无线m e s h 网络路由相关技术 第二章无线m e s h 网络路由相关技术 2 1 无线m e s h 网络的组网结构 无线m e s h 网络是使用无线多跳通信方式的网络结构，数据流量进出有线i n t e m e t 网关。 与平面a dh o c 网络相比，无线m e s h 网络呈现分层的特点。无线m e s h 网络中的节点，按 其功能可以分为m e s h 路由器( m e s hr o u t e r , m r ) 和m e s h 客户端( m e s hc l i e n t ，m c ) l i j 两种类型的节点。 无线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 a c 协议，还能使得它在多跳m e s h 网络环境下具有更好的可扩展性。 m e s h 客户端则兼备主机和路由器两种角色：一方面，节点作为主机运行相关的应用程 序；另一方面，节点作为路由器需要运行相关的路由协议，参与路由发现、路由维护等路 由操作。此外，和m e s h 路由器相比，m e s h 客户机通常只有一个无线接口，在硬件和软件 方面都要简单，在灵活性方面也要强于m e s h 路由器。 在组网模式上，无线m e s h 网络有三种典型结构【4 l ：基础设施网状结构，客户端网状 结构，以及混合式结构。 基础设施网状结构中只有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 。带有以太网接口的传统用户可以通过以太 网连接到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 南京邮电大学硕究生学位论文第二章无线m c n 网络路由相关拄术 图2 - 1 所示。 v 1 m 日镕 图2 - i 基础设施的m e s h 网络 客户端结构的m e s h 网络只有m e s h 客户端，如图2 - 2 所示。在这种结构的网络中，终 端用户自身配置无线收发装置通过无线信道的连接形成一个点到点的对等网络，即a dh o g 网络。它们完成路由、自配置和向客户提供终端应用的功能因此不需要m e s h 路由器。 这是一种任意网格的拓扑结构节点的任意移动可能导致网络拓扑结构也随之发生变化。 m e s h 客p 端 m e s h 客户端 图2 - 2 客户端的m e s h 结构 在这种环境中，由于终端的无线通信覆盖范围有限，两个无法直接通信的用户终端可 9 堕塞苎皇查兰堡主堡墨皇兰垡堡苎蔓三里墨垫竺苎旦垡壁虫塑苎堑查 以借助其他终端的分组转发进行数据通信。在任意时刻，终端设备在不需要其他基础设施 的条件下可独立运行，它可支持移动终端较高速率的移动，快速形成宽带网络。通常，在 客户端上只使用一种无线电技术，网络结构比较简单，因此部署也比较容易，但客户端往 往具有一定的移动性，对于路由设计和服务质量等都提出了挑战。 w 1 m 日镕 图2 - 3 混合m e s h 网络结构 如图2 - 3 所示混合式结构的无线m e s h 网络是基础设施结构和客户端结构的结合。 m e s h 客户端可以通过m e s h 路由器接入网络，同时也可以和其他m e s h 客户端直接组成 m e s h 网。骨干网提供到i n t e r a c t 、w i f i 、w i m a x 、蜂窝网以及传感器网络等的连接，客户 端的路由功能可以从内部增强m e s h 网络的连接和覆盖能力，这种混合型的结构是最具有 应用价值的方式。 2 2 无线m e s h 网络的特点 无线m e s h 网络的组织方式与传统的蜂窝网络迥然不同，它不仅可以看作是w l a n 与 移动a d h o c 网络的融合，也可看作是因特网的一种无线版本。概括来看，无线m e s h 网络 有以下主要特点1 4 1 ： 1 ) 多跳无线网络。在不牺牲信道容量的情况下，扩展当前无线网络的覆盖范围是m e s h 南京邮电大学硕士研究生学位论文 第二章无线m e s h 网络路由相关技术 网络最重要的目标之一。无线m e s h 网络的另一个目标是为处于非视距范围的用户提供非 视距连接。通过m e s h 网络连接，只需要短距离的链路，经受较少的干扰，就可以为网络 提供较高的吞吐量和较高的频谱复用效率。 2 ) a dh o c 网络结构，具有自形成、自组织和自修复能力。由于无线m e s h 网络灵活 的网络结构、便利的网络配置、较好的容错能力和网络连通性，使得无线m e s h 网络大大 提升了现有网络的性能，在较低的前期投资下，可以根据需要逐步扩展。 3 ) 移动性取决于节点的类型。通常有两类节点，分别具有不同的移动性特征。m e s h 网关和m e s h 路由器的移动性通常都较低，而m e s h 客户端则既可以是静态的，又可以是任 意的移动节点。 4 ) 多种网络接入方式。在无线m e s h 网络中，既可以支持到因特网的接入，也可以支 持端到端的通信方式。此外，可以通过无线m e s h 网络与其他无线网络的集成，向终端用 户提供各种多媒体业务。 5 ) 功耗限制取决于节点类型。m e s h 路由器通常有外部供电，受功耗限制不严格，而 m e s h 客户端就如同蜂窝移动通信网络的手机样，需要有有效的节能机制。 6 ) 与现有无线网络的兼容性及互操作性。基于现有网络技术或标准( 如8 0 2 1 1 ) 的无 线m e s h 网络必须在支持原标准上与这些标准相兼容，同时还需要与其他无线网络( 如 w i m a x ，w i f i 和蜂窝网络等) 有互操作性。 2 3 路由策略分类 路由的主要任务是发现和维护从源节点到目的节点的路径，并指引数据分组从源节点 正确到达目的节点。路由问题是计算机网络中的经典问题，因而对它已有较深入的研究， 并有一些较成熟和得到广泛应用的协议，如路由信息协议( r i p ) 和优先开放最短路径 ( o s p f ) 协议。传统网络的路由协议包括距离一向量路由协议、链路一状态路由协议。 r i p 是一种分布式的、基于b e l l m a n - f o r d 的算法，属于距离一向量路由协议。o s p f 协议 则属于链路状态路由协议。 无线m e s h 网络与一般无线网络有很大的区别，在无线m e s h 网络中每一个覆盖区域的 节点都是运动的，可能从一个区域跨越到另一个区域，路由随时可以变化，在同一个区域 内，网络终端的数量可能非常的大，需要维护的路由信息也非常多：除了维护无线接入终 端的路由信息外，也可能要对许多骨干节点进行管理和控制，因此同样需要对骨干节点的 拓扑进行准确的描述和表现；骨干网络节点间的通信是通过无线方式进行的，而无线链路 南京邮电大学硕士研究生学位论文 第二章无线m e s h 网络路由相关技术 具有动态变化和不可靠的特点，需要多次的路由中继，因此每个中间节点都需要知道到达 目的节点的路由信息等等。故而无线m e s h 网络的路由必须在受到多重约束条件和动态环 境下j 才能保证数据的可靠传输。 由于无线m e s h 网络是一种新兴的网络技术，它既有传统有线网络的骨干节点拓扑较 为稳定，路由相对变化较慢的特点，又因为每个骨干节点通过无线进行连接和移动终端可 以运动而具有了无线网络中链路不稳定、终端的拓扑结构变化较大的特点。为了解决移动 性和无线通讯的特点带来的问题，目前已经提出了许多的路由协议。按不同的标准，这些 协议可分为不同的类型。 ( 1 ) 源路由协议与分布式路由协议 在传统的源路由协议中，要求计算路由的节点具有整个网络的拓扑结构信息。由此计 算出来的路径信息被包含在源节点发送的消息中，网络的其他节点按此路径传递消息。由 于无线m e s h 网络的拓扑结构可能时常变化，为了使路由的计算节点保持准确的网络拓扑 信息，网络将增加大量的更新消息，从而带来比较大的开销。因此这种方式只适合于网络 结构相对稳定的有限情况。为解决此问题，提出了按需路由的源路由协议。该种路由协议 可以避免分布式路由协议中出现路由环等问题，而且简单、易于实现。 在分布式路由协议中，路由的计算由网络中的节点分布完成，并且路径信息被分布存 储在网络的每个节点中。网络中的节点根据自己的路由表进行消息的转发选择。分布式路 由协议的可伸缩性较好，然而，一些分布式路由协议( 如o s p f ) 仍要在网络节点中维护 网络全局状态信息，这种协议不适合于拓扑结构变化频繁的网络。有一些分布式路由协议 ( 如t o r a ) 不要求节点维护网络的全局状态信息，但设计这类协议时应避免路由中出现 路由环，或应在路由环出现时采取有效措施消除。 ( 2 ) 层次型路由协议与平面型路由协议 在层次型路由协议中，按区域将节点划分为多个组，而在高层将每个组视作一个逻辑 节点。组内节点之间采用一般的非层次的路由算法。每个节点主要维护同一层次同一组内 的节点的状态信息，因此具有很好的可伸缩性。层次型路由协议还可以解决分离的节点群 之间的通讯问题。它所存在的问题是如何在高层逻辑节点中表示底层网络的状态信息，以 及在拓扑结构不断变化的情况下如何选择高层逻辑节点，这种协议相对较复杂。非层次的 路由协议即为平面型路由协议。 ( 3 ) 先验式、反应式以及混合式路由协议 先验式路由协议又称为主动式协议，其最大的特点是周期性对路由信息的获取操作。 1 2 南京邮电大学硕士研究生学位论文 第二章无线m e s h 网络路鱼塑垡技术 传统的路由协议一般属于此类。这类协议又可再分为距离一向量路由协议和链路一状态路 由协议。前一类如r i p 、d s d v 协议，后一类有o s p f 、o l s r 协议等。 反应式路由协议又称为按需路由协议。这类协议中，只有单节点需要传输数据包且没 有目标节点的路径时，才通过路由发现过程来获得所需要的路由信息。当网络拓扑发生变 化时，通过路由维护过程来修补失效的路径或利用路由发现过程来得到新路径。 混合式路由协议一般基于簇或区域将节点分层次组织起来，在簇内或区域内采用先验 式获取路由信息方式，而在全局范围内采用反应式。 2 4 自组织网络路由协议 鉴于无线m e s h 网络是a dh o c 网络基础上发展起来的，还是一种新兴的网络技术，目 前还没有专门针对无线m e s h 网络路由协议正式标准，而国内外对