（通信与信息系统专业论文）无线mesh网络的路由算法研究(1).pdf

摘要 本论文着重研究并改进无线m e s h 网络中的路由算法。无线m e s h 网络 ( w i r e l e s sm e s hn e t w o r k ) 简称w m n ，是种新型的无线通信网络。无线 m e s h 网具有自组织性和自愈的特点， 制，是一种多跳的宽带无线网络结构 络。 并具有有效的移动用户管理和跟踪机 也是种高容量、高速率的分布式网 无线m e s h 网w m n 可以看成是一种特殊的w l a n ，除移动性较低外， w m n 本质上是一种a d h o e 网络。目前主要观点认为，w m n 是一种由无线 链路连接路由器和终端设备的静态无线网络，是i n t e m e t 的无线版本。作为 一种新型网络结构形态，m e s h 结构已被纳入到8 0 2 1 6 2 0 0 4 、8 0 2 1 6 e 和即将 制定的8 0 2 1 l s 标准中。 本文的主要内容是提出一种无线m e s h 网络的新的路由算法s q o r ( s e l e c t i v eq u a l i t yo n d e m a n dr o u t i n g ) ，并对它进行了研究与仿真。s q o r 路 由算法是一种基于a o d v 路由协议的关于路由准则的无线m e s h 路由协议。 受到m i c r o s o f t 最近提出的基于d s r 的m r l q s r ( m u l t ir a d i o l i n kq u a l i t y s o u r c er o u t i n g ) 算法的启发，以多跳多射频的无线m e s h 网络体系结构为基 础，研究多个频率对网络性能的影响。将系统吞吐量、链路速率等参数作为 新的路由准则，利用多射频的特性，提高网络利用率。 本文首先阐述了无线m e s h 网络结构，分析比较了过去典型的几种无线 自组织网路由协议的设计思想，然后对s q o r 路由算法的设计进行了充分阐 述。本文使用仿真的方法对协议进行了形式化描述和验证，关键流程均给出 了详细说明。 本文所研究的是无线m e s h 网络路由协议实现的基础。新的路由准则结 合路由发现与维护等过程，与硬件平台设计、链路层驱动和用户认证管理部 分相配合，将为提高无线m e s h 网络系统的效率做好了准备。 关键词：，无线m e s h ，路由，a o d v ，多射频 t k sd i s s e r t a t i o ni sa b o u tt h es t u d ya n di m p r o v e m e n to f r o u t i n ga l g o r i t h m i n w i r e l e s sm e s hn e t w o r k t h ew i r e l e s sm e s hn e t w o r k ( w m n ) i san e wt y p eo f w i r e l e s sc o m r n u n i c a t i o nn e t w o r k w a 岔7i s c a p a b l eo fs e l f - o r g a n i z a t i o n a n d m u l t i - h o pm u t i n g ，a sw e l la si t sc a p a b i l j 巧o f m o b i l el l s e rm a n a g e m e n ta n d t r a c i n g i ti sam u l t i - h o pb r o a db a n d w i d t h d i s t r i b u t i n gw i r e l e s sn e t w o r kw i t hh i g hc a p a c i t y a n dh i 幽t r a n s m i s s i o nr a t e w 心i sas p e c i a l 肌a n i ti si ns u b s t a n c eak i n do f a dh o cw i t hl o wm o b i l i t y n o wm a n yp e o p l eb e l i e v et h a tw l v l ni saw i r e l e s s v e r s i o no fi u t e m e ta sas t a t i cw i r e l e s sn e t w o r kw i t hr o u t e r sa n dn o d e sw i t h w i r e l e s sl i n k s a san e wt y p eo fn e t w o r ks l a u c t u m ，m e s hi si n c l u d e di n t o 8 0 2 1 6 2 0 0 4 、8 0 2 1 6 ea n dt h ec o m i n g8 0 2 1 l ss t a n d a r d s d e s i g no ft h es q o r ( s e l e c t i v eq u a l i t yo n - d e m a n dr o u t i n g ) a l g o r i t h mi s t h em a i np a r to ft h i sd i s s e r t a t i o n s q o ri saw i r e l e s sm e s h r o u t i n ga l g o r i t h m b a s e do na o d v r o u t i n gp r o t o c 0 1 i l l u m i n e db y t h em r - l q s r ( m u l t ir a d i o l i n k q u a l i t ys o u r c er o u t i n g ) p r o t o c o lp r o p o s e db ym i c r o s o f t , a n d b a s e do nt h es y s t e m s t r u c t u r eo fm u l t i h o pn e t w o r k sw i t hm u l t i p l er a d i o s ，an e ws t a n d a r df o rm u t i n gi s p u tf o r w a r dc o n c e m i n gs y s t e mt h r o u g h p u ta n dl i n kd a t ar a t e ，e t c t h i si m p r o v e s t h eu t i l i z a t i o na n de f f i c i e n c yo fw m n i ti sf i r s ti n t r o d u c e dt h mw h a tt h e w t r e l e s sm e s hn e t w o r ki s t h e ni t g i v e s as n a p s h o to fs o m ef o r m e rt y p i c a l w i r e l e s s s e l f - o r g a n i z i n g n e t w o r km u t i n gp r o t o c o l s t h e p r i n c i p a l s o ft h e s e p r o t o c o l s a n dt h ed e s i g no fs q o ra r ee l a b o r a t e d 髂t h em a i np a r to ft h i s d i s s e r t a t i o n a l s ot h es i m u l a t i o n sa r ew o r k e do u tt od e s c r i b ea n dv e i l f yt h e a l g o r i t h m , a n dk e y f l o w sa r eg i v e ni nd e t a i l a l lt h ec o m p l e t e dw o r kd e s c r i b e dh e r ep l a y sab a s i ca n d i m p o r t a n t r o l ei nt h e r e a l i z a t i o no fw i r e l e s sm e s h r o u t i n gp r o t o c o l s t h en e w s h o u l db es t a n d a r dw i t h r o u t i n gc o m b i n e dw i 也r o u t i n gd i s c o v e r ya n dr o u t i n gm a i n t e n a n c ep r o c e s s e s a n d c o o p e r a t e 谢t hh a r d w a r ep l a t f o r m 1 i n kl a y e r d r i v e ra n du s e ra u t h e n t i c a t i o n m a n a g e m e n t w o r kg r o u p s i th a sm a d eap r e p a r a t i o nf o rt h ei m p r o v e m e n to ft h e w h o l ew i r e l e s sm e s hn e t w o r ks y s t e m k e y w o r d s ：w i r e l e s s m e s h ，r o u t i n g ，a o d v , m u l t i p l e r n d i o s i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 l 确的说明并表示谢意。 签名：圣鱼坠丛日期：2 。5 年5 月2 3 曰 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：墨查坠熬导师签名：查里坠 日期：2 口d 多年5 月2 3 曰 缩略字表 w a d ! w 扛e l e s sm e s hn e t w o r k ，w i v i n i v i r - l q s rm u l t i - r a d i ol i n k - q u a l i t ys o u r c er o u t i n g c d p dc e l l u l a rd i g i t a lp a c k e td a t a w g d s d v d e s t i n a t i o n - s e q u e n c e d d i s t a n c e - v e c t o r r o u t i n g c g s r c l u s t c r h c a d & a t c w a ys w i t c hr o m i n g w r pt h ew i r e l e s s r o u t i n g p r o t o c o l a o d va dh o e0 n - d e m a n dd i s t a n c ev e c t o r d s r d y n a m i cs o u r c er o u t i n g t o r a t e m p o r a l l y o r d e r e d r o u t i n ga l g o r i t h m s q o r s e l e c t i v eq u a l i t yo n d e m a n d r o u t i n g w c e t r w 西g h m ic 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 nt i m e e 1 x 唧 s e t t e x p e c t e d n u m b e ro f t r a n s m i s s i o n s e x p e c t e d t r a n s m i s s i o nt i m e s u mo f e l v r s b g - e t tb o t t l e n e c kg r o u pe t t t i u t p t t t h r o u g h p u t - r e l a t e dt r a n s m i s s i o nt i m e p r a c t i c a lt r a n s m i s s i o nt i m e s w t ts e l e c t i v ew e i g h t e dt r a n s m i s s i o nt i m e v 电子科技大学硕士学位论文 1 1 课题背景 第一章引言 近十年来，网络服务的爆炸已经对电信的发展造成了巨大影响，并 推动了传统电路交换向分组交换的技术变革。作为现代通信技术的两个 重要领域，i p 技术和移动通信技术正在全球范围内快速发展和应用，两 种技术的结合也日益称为当今通信技术发展的一个趋势。 m 覆盖技术和基于p 的各种服务成为炙手可热的研究课题和发展 方向。口技术以其实现简单、廉价和有效的特点，在有线商用网中取得 了巨大的成功。它有效地解决了异构网之间的互连。另一方面，无线移 动通信提供了相当高的自由度给使用者，使用者不再囿于连接线路的长 度、地理环境的限制，可以带着资讯设备到处移动。这种崭新的使用形 态促进了新一代资讯设备的成长与变化。结合无线移动通信和1 p ( 因特 网) 这通信领域目前研究的两大热点，探讨无线p 网络的技术方法，是 一件非常有意义的工作。 本课题正是着眼于此，研究无线m e s h 网络。无线m e s h 网( w i r e l e s s m e s h n e t w o r k ，w m n ) 是一种多跳、具有自组织和自愈特点的宽带无线 网络结构，即一种高容量、高速率的分布式网络。它旨在探索无线移动 通信与p 技术的结合，研究在小型区域范围内允许多个网络同时存在、 不同网络自动区分、拓扑结构动态可变、具有多跳和动态路由能力的自 组织网络结构形式。 美国早在8 0 年代初即提出了自组织网络的概念，目前其研究重点在 移动a dh o e 网络( m a n e t ) 。我国从七五后期开始自组织网络技术研 究。无线网络技术是当前获得迅速发展的技术，它允许移动用户采用更 加灵活方便的方式接入网络。典型的无线网络( w b l e s sl a n ) w l a n 通常具有两种组织形式：中心结构网络( i n f r a s t r u c t u r e dn e t w o r k ) 和a d h o e 网络( i n f r a s t r u e t u r e l e s sn e t w o r k ) 。中心结构网络由包含固定有线 网关的网络组成。在无线覆盖范围内，移动主机与基站( 固定有线网关) 进行通信，并可在通信过程中移动。当移动主机离开原基站的无线覆盖 范围后，它可与另一个基站建立连接并通过该基站继续进行通信。在这 第一章引言 种组网和通信方式中，基站位置是固定不动的。g s m 系统即是采用这种 网络组织形式。a dh o c 网络是无线网络的另一种组织方法。在a d h o e 网络中，所有节点都处于平等地位，它们之间都可能有通信关系存在， 同时每个节点还承担着组网和为其它节点中继的义务。网络中的所有节 点都像路由器一样参与路由的发现和维护。 无线m e s h 网( w i r e l e s sm e s hn e t w o r k , w m n ) w m n 可以看成是一种特 殊的w l a n ，除移动性较低外，w m n 本质上是一种a dh o c 网络。目前主 要观点认为，w v l n 是一种由无线链路连接路由器和终端设备的静态无线网 络，是i m t e r n e t 的无线版本。 作为一种新型网络结构形态，m e s h 结构已被纳入到8 0 2 1 6 - 2 0 0 4 、8 0 2 1 6 e 和即将制定的8 0 2 1 l s 标准中。 目前，国内外对移动a dh o e 网络的自组织算法和路由算法有非常多研 究。但在移动a dh o e 网络和w m n 上还没有路由协议正式标准。m e s h 路 由协议基本同a dh o e 网络路由协议，但需要针对w m n 的特点设计专门适用 于w m n 的高效路由协议。 目前几种典型的路由协议有：d s d v ( 目的序列距离矢量路由协议) 、d s r ( 动态源路由协议) 、t o r a ( 临时按序路由算法) 和a o d v ( a d h o e 按需距 离矢量路由协议) 等。微软公司最近提出了一种多r f 收发器、多跳无线网 络的路由协议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 ys o u r c er o u t i n g ) ，在 d s r 协议的基础上采用最大吞吐量准则。课题将要研究的是基于a o d v 路 由算法的m e s h 网络路由改进，使其能提高吞吐量，减少数据丢失。 w m n 无线移动自组织网络具有组网方式灵活、环境适应性强和快速应 变的特点，因而能够广泛应用于没有现存网络支持或现有网络不能满足机动 性要求的应用环境，将会在军事和民用方面得到广泛的应用。 1 2 本论文的安排 本课题的目标是研究适应于无线移动自组织m e s h 网络特点的快速、准 确、高效和可扩展的动态路由技术。在组网体制上，无线节点间通过无线信 道沟通和自组织，形成无线互联网络，实现网络的拓扑构成、中继与路由、 接入控制和用户管理等功能。与传统的a d h o c 网络相比，w m n 是一种由无 2 电子科技大学硕士学位论文 线链路连接路由器和终端设备的静态无线网络，是i n t e m e t 的无线版本。 本文将在分析比较现有的各种w m n 路由协议的基础上，提出新的路由 协议和算法。在以下各章中，首先介绍无线m e s h 网络基本情况，包括w m n 的背景与起源、w m n 的主要优点和缺点、w m n 与w l a n 和a dh o c 网络的 区别、w m n 的网络结构形态、w m n 的关键技术、w m a ) 【的m e s h 方案、 w m n 的应用方案等；接下来将详细分析现有的无线自组织网络的路由技术， 并作出比较；然后提出基于a o d v 路由算法的新的路由协议；最后给出仿真 结果，并对结果加以分析。 第二章无线m e s h 网络 第二章无线m e s h 网络 21 1 1 无线m e s h 网的背景与起源 1 9 9 7 年，美国d a r p a 开始组织战场鲁棒战术移动通信系统的研发。在 投入大量资金、持续6 年多的研发之后，有关移动a dh o e 网络的一些理论与 技术问题得以解决，从而彻底改变了过去构建无线网络的规则。d a r p a 的 目标是：无传统的通信基础设置；采用多跳转发的传输机制；宽带数据数率； 端到端的口支持：除了数据业务以外，还要支持话音和视频业务；内置定位 系统( 非g p s 系统) ；能支持高达2 5 0 英里孙时的车辆移动速度。特别是近 几年，美国通过一些大型国防项目，攻克了a dh 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 dh o c 网络的商业化进程开始显现。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 网络无线 m e s h 网络。于是，无线m e s h 网络的概念得到人们的关注。值得一提的是， 自2 0 0 0 年3 月m e s h n e t w o r k s 成立以后，它成功地开发了一系列相关产品， 基于其良好的成长性，目前被m o t o r o l a 收购。另一方面，2 0 0 2 年8 月，美国 f c c 宣布停止c d p d ( c e l l u l a rd i g i t a lp a c k e td a t a ) 业务，一些采用c d p d 的企业开始寻求其替代技术，如w i - f i ( 8 0 2 1 1 ) 等技术，因此基于w i f i 的 多跳网络技术进入人们视野。除此之外，目前网络设计的理念也开始从集中 趋向分散：集中控制与管理向分散控制与管理发展；客户机服务器模式向 w e b 业务模式发展；集中式的目录向联合式的标识发展；电路交换的电话业 务向p 电话与多媒体业务发展；需要许可证的蜂窝电话向非许可证的无线 业务发展。 电子科技大学硕士学位论文 集中控制与管理 客户机一服务器模式 分散控制与管理 w e b 业务模式 图2 - 1 集中向分散的发展趋势 2 2 无线m e s h 网的结构与关键技术 2 2 1 什么是无线m e s h 网w m n 无线m e s h 网( w i r e l e s s m e s h n e t w o r k ，w m n ) w l v l n 是一种多跳、具有 自组织和自愈特点的宽带无线网络结构，即一种高容量、高速率的分布式网 络。目前主要观点认为，w m n 是一种由无线链路连接路由器和终端设备的 静态无线网络，是i n t e m e t 的无线版本。w m n 不同于传统的无线网络，可以 看成是w l a n ( 单跳) 和移动a dh o c 网络( 多跳) 的融合，且发挥了两者 的优势。作为一种新型网络结构形态，m e s h 结构己被纳入到8 0 2 1 6 2 0 0 4 、 8 0 2 1 6 e 和即将制定的8 0 2 1 1 s 标准中。w m n 可以通过一些中间节点连接互 相远离不能直接连接的无线路由器。 2 2 2w m n 与w l a n 和a d h o c 网络的区别 无线m e s h 网w m n 可以看成是一种特殊的无线局域网w l a d q ，除移动 性较低外，w m n 本质上是一种a dh o c 网络。 在拓扑结构上，w l a n 在最后一跳的接入上采用无线方式，而w o i 无 第二章无线m e s h 网络 网络基础设施，是多跳无线网络，可实现网络自形成、自伸缩、自愈和白诊 断等。 在网络设备上，w l a n 的a p 负责终端设备的接入，而w m n 的所有节 点均能承担本地接入与其他节点的信息转发功能，即具有路由器和中继器功 能。 在路由协议上，w l a n 固定路由，而w m n 则采用动态路由，路由冗余 和自愈能力强。 在w l a n 中，两个彼此相邻的设备不能直接通信，必须借助a p 的接入 与转发，如2 2 所示。 c l i e n t 。 b a c k b o e 图2 - 2t r a d i t i o n a lw i f in e t w o r kt o p o l o g y ：“h u b - a n d - s p o k e ”m o d e l 酒， 豁， 。 i b)、， 9 i _ f l 目 (j， h呷0 | 譬、拶 电子科技大学硕士学位论文 在w m n 中，典型情况下，两个彼此相邻的设备可以直接通信，如图2 3 所示。 图2 - 3w i r e l e s sc o m m u n i t yn e t w o r k ：m e s hn e t w o r km o d e l 7 第二章无线m e s h 网络 2 2 3 协似的网络结构 基础设施m e s h 形态： n e t w o r ka 图2 4 无线m e s h 网基础设施 无线m e s h 网具有网络基础设置，m e s h 网延伸了i n t e r n e t ，在a p 与终端 设备之间形成无线回路。终端设备( 如8 0 2 ，l l b g 设备) 通过a p 或无线路由 器( w r ) 的路由选择和中继功能，与无线网关( w g ) 形成无线链路。 a p w r 通过路由选择及管理控制等功能为终端设各选择与目标终端设 备通信的最佳路径，从而形成无线的回路。通过w g 连接其他网络，即可实 现无线宽带接入。 电子科技大学硕士学位论文 终端设备m e s h 形态： 图2 - 5 无线m e s h 网终端设备 终端设备通过自身的网络互联功能连接形成一个点到点的网络，节点可 以任意移动，网络拓扑结构也随之变化。 两个无法直接通信的终端设备可以借助其他终端设备的转发功能实现通 信。终端设备在不需要其他基础设施的条件下可独立运行，可支持终端的移 动接入，快速自形成和网络自愈。 第二章无线m e s h 网络 图2 - 6 为w i m a x 基于m e s h 的无线宽带接入结构图。 锚i r s tt幽lc-r。p黑tp o r pivi霉p蒸器 黜蛐 d e s t i n a t i o n - + 啬e l e s sl i n k 一一一一一- s e n d p a c k e t 路由发现过程： 1 当源节点没有到达目的节点的路由时，广播一个路由请求报文。 2 每个收到该报文的中间节点附加上自己的i d 然后重新广播( 忽略 重复请求和已经包含自身d 的报文) 。 3 当路由请求到达目的节点( 或者某个知道某条到达目的节点的路由 的中间节点) 时，目的节点可以确定一条到达目的节点的完整的源路由。 4 目的节点( 或中间节点) 将所得的源路由包含在路由响应报文中， 然后沿着反向路由发送回源节点( 或者附带在目的节点的路由请求报文中) 。 电子科技大学硕士学位论文 5 源节点收到路由响应报文后，将源路由存入缓存，并添加到每个数 据报的头部。中间节点根据数据报头中的源路由转发数据报。 在d s r 中结合了许多基于积极缓存和拓扑信息分析的优化措施。例如， 中间节点可以从数据报的头部获得到达所有下游节点的路由，通过合并多条 路径的路由信息还可以推演出更多的拓扑信息。此外，如果设置节点的网络 接口工作在混杂模式下，通过监听邻居节点使用的路由，节点还可能获得更 多的拓扑信息。通过这些方式，节点可以将越来越多的“感兴趣”的网络拓 扑信息存入缓存以提高路由查找的命中率。高的缓存命中率意味着可以减少 进行路由发现过程的频率，节约网络带宽。不过，积极缓存也会增加将过期 的路由信息注入到网络中的可能性。 路由维护过程 1 如果在数据报的逐跳传输过程中发现链路失败，则可以由中间节点 使用缓存中的可用路由来代替原头部中含有失败链路的路由，同时向源节点 发送路由错误报文。 2 中间节点监听路由错误报文以删除失败路由( 减小缓存错误路由信 息的影响) 。 3 如果路由失败，则由源节点重新开始一次新的路由发现过程。4 如 果节点发现数据报头部的源路由中包括自己的i d ( 例如由于拓扑变化而产 生更短的路由) ，可以主动发送路由响应报文告知源节点存在更短路由。 3 2 3 t o r a ( t e m p o r a l l y o r d e r e d r o u t i n ga l g o r i t h m ) t o r a 是一种基于链路反转概念的高度自适应的、高效、可扩展的分布 式路由选择算法。t o r a 在早期的“链路反转”( 1 i n kr e v e r s a l ) 算法的基 础上发展而来，它为每个目的节点构造一个基于目的的有向无环图。如果链 路变化导致某个节点失去其所有的输出链路，则该节点“反转”部分或全部 输入链路的方向。t o r a 的主要特点是，控制信息被限制在拓扑变化点附近 的一组非常少的节点之中。因此，节点需要维护邻近节点的路由信息。t o r a 包括三个基本功能：路由创建、路由维护和路由删除。 2 1 第三章无线m e s h 网络的路由技术 每个节点包含五个相关参数 链路失败的逻辑时间 用于定义新的参考层的唯一的节点i d 反应指示比特 传播排序参数 节点的唯一i d 前三个参数共同表示参考层。当节点因链路失败丢失了最近的下行链路 时，算法将定义新的参考层。后两个参数定义相对于参考层的增量。 t o r a 使用q r y 和u p d 分组迸行路由创建。路由创建算法初始时将 目的节点高度( 传播排序参数) 设为0 ，其它所有节点高度设为n u l l ( 即 未定义) 。源节点广播一个带有目的节点i d 的q r y 分组，具有非n u l l 高 度值的节点使用带有自己高度值的u p d 分组响应。收到u p d 分组的节点 将自己的高度值设置为比发送u p d 分组的节点的高度值大h 具有较大高 度值的节点视为上游节点，较小高度值的节点视为下游节点。用这个方法， 算法可以构造出一个从源节点到目的节点的有向无环图。 2 2 电子科技大学硕士学位论文 图3 - 3 为t o r a 中的路由创建过程。 ( 0 , 2 )( 0 ，1 ) ( 0 ，0 ) d e s t i n a t i o n 图3 - 3t o r a 中的路由创建 w i r e l e s sl i n k s e n dp a c k e t 上图表示了t o r a 的路由创建过程。第一个图中，如果节点5 已经先 收到并传播了从节点2 发来的q r y 分组，那么它就不传播从节点3 收到 的q r y 分组。第二个图中，源节点( 节点1 ) 可能也要收到从节点2 或 节点3 发来的u p d 分组。但是由于节点4 给出的高度值更小，所以它保 持原值不变。 第三章无线m e s h 网络的路由技术 图3 4 为t o r a 中的路由重建过程。 ( o ，2 )( o ，1 ) 图3 4t o r a 中的路由重建 当节点发生移动而导致路由改变时，路由维护机制将为同一个目的节点 一条新的路由。如果节点的最后一个下游链路失败，节点就将自己的高度设 对于失败链路的本地最大值( “链路反转”) 并将自己的高度用更新消息广播 这时节点适应新的参考层，链路发生反转。在路由删除阶段，t o r a 在网络 泛一个广播清除分组( c l r ) 来删除无效路由。 3 3 算法分析和比较 本章简要介绍了a dh o c 网络的三种表驱动路由协议和三种按需路由 协议。在表驱动路由协议中，每个节点都要保存到网络内其它所有节点的最 新路由信息。相反，在按需路由协议中，节点只有在希望向目的节点发送数 据时才去寻找到该节点的路径。 0 n 电子科技大学硕士学位论文 表3 - 1 六种a dh o c 路由协议的特点 协议 特点 表驱动d s d v每个节点维护全网路由信息、周期更新 路由避免路由环、提供唯一路由 c g s r采用多级分簇和逻辑分区的分层路由协议 协议 w r p维护四个路由表、固定的h e l l o 机制 避免临时路由环 按需a o d v对等的、基于目的节点的按需路由 d s r对等的、基于网络拓扑的按需路由 路由 t o r a基于链路反转算法的自适应按需路由 协议 d s d v 路由协议是对b e l l m 甑- f o r d 路由算法的改进，它保证避免路由环 路，并提供了一个简单的更新机制。d s d v 根据最短跳数寻找最短路径，仅 提供唯一的一条路由。d s d v 效率很低，因为它要求周期性的更新路由信息， 而不论网络拓扑有多少发生变化。这一性质也限制了使用d s d v 的网络的大 ，j 、。 在c g s r 中，d s d v 被用作下层路由协议。路由在串首节点与网关之间 进行，并且借点需要维护更多的一个关于串首节点的信息表。随着网络的变 化频繁地在改变串首，会造成路由协议效率低下，因为个协议节点不是忙于 数据包转发而是忙于串首选举协议的实行。因而一种改进的l c c ( l e a s t c l u s t e rc h a n g e ) 协议产生了。在l c c 中，仅在需要选出串首进行通行或者一 个节点进入非任何串首能通信的节点领域时，才进行选举。它的一个优点在 于可以使用许多自发式的办法来提高协议的实行，包括优先令牌调度机制， 网关码调度机制( g a t e w a y c o d es c h e d u l i n g ) ，以及路由预留机制等等。 w r p 协议于其他协议有很大不同，它需要节点维护四个信息表，这将造 成对存贮能力的要求，特别是当网络节点总多的时候。更重要的是，它使用 “h e l l o ”机制无论有没有数据需要传送，这造成了不必要的通信量。但是， 它甚至能够避免临时的路由环路，这是其他协议做不到的。 第三章无线m e s h 网络的路由技术 a o d v 协议与d s r 采用了类似的路由发现机制，但是二者也有不同。 d s r 的r r e q 包头比a o d v 大，因为它的包内必须包括所有的路由信息， 面a o d v 只需要目标节点的地址。同样，r r e p 也是d s r 的比较大，需要 包含所有路由节点的地址。a o d v 还有一个优点是，它不要求网络是对称的， 同时还支持多播。暂时没有看到没有任何其他的路由协议支持多播。 d s r 最主要的特点是使用源路由。印发送者完全知道该经过哪些中间节 点一跳跳地到达目的地：这些路由存储在一个缓行中：数据包在它的包头携 带所需的源路由信息。d s r 非常依赖于源路由和路由缓存技术。 a o d v 和d s r 一样都是按需路由协议，即它也是在需要时才发起相似 的路出发现过程。但是a o d v 在维护路由信息上采用完全不同的机制：它使 用传统的路由表，通常每个目的节点只有一条路由记录，而d s r 在缓存中对 每个目的节点可以有多条路由。 t o r a 从源节点开始为每个节点指定参考层和相对高度，利用这些参数 为节点建立逻辑关系，并根据高度值建立路由。 通过研究我们知道，在互联网上，如果一个路由器发生故障，信息由其 他路由器，通过备用路径传送。同样，m e s h 的自愈体现在网络中某一装置或 其链接发生故障时，信息通过其他装置传送，给信息提供新的路由无需人工 介入；而且，一个或几个节点出现故障，不会影响网络运行。这一特点也是 企业要求增强其连通性所必需的。m e s h 的路由算法与传统的蜂窝通信网络和 固定通信网络也就有着更灵活、更主动、更分散等特点。由于它是基于无线 信道的网络路由算法，因此对可靠程度有更高的挑战性。 结合本文上一章提出对路由协议的几个基本要求和现有协议的启示，我 们设计了一种基于吞吐量的路由选择准则。 电子科技大学硕士学位论文 第四章无线m e s h 路由算法s q o r 最初设计的国防军用a d h o c 网络中各节点具有高速运动的特性，因而其主要的 挑战之一在于如何控制其移动性。而对于针对商用的无线m e s h 网络，更多的重 点是放在如何提高其网络吞吐量、增大网络容量。 微软公司最近提出了一种多r f 收发器、多跳无线网络的路由协议 m r - l q s r ( m u l t i - r a d i ol i n k q u a l 埘s o u r c er o u t i n g ) ，在d s r 协议的基 础上采用最大吞吐量准则。 通过研究表明，a o d v 路由算法有其固有优势，如不会形成路由环；当 一条链路不可用时，可以高效地在整个网络中删除所有要利用这条无效链路 的路由等。 因此，在a o d v 的基础上，考虑多r f 收发器，以提高网络吞吐量为目 标，通过对各种影响网络性能的参数进行分析，实现最优路径的选择，从而 提出一种新的路e h 算法s q o r - - s e l e c t i v eq u a l i t yo n - d e m a n dr o u t i n g 。 4 1 多r f 对网络性能的影响 对于单一射频的网络，每一个节点不能够同时接收和发送信息。 s s s o u r c em e s hr o u t e rd e s t i n a t i o n 第四章无线m e s h 路由算法s q o r 对于具有两个r f 收发器的网络节点，如果将两个收发器调到互不干扰 的不同频道，节点将可以同时接收和发送信息。 s o u r c em e s hr o u t e rd e s t i n a t i o n 图4 - 2t w or a d i o st u n e dt o n o n i n t e r f e r i n gc h a n n e l s 现在a o d v 的路由距离矢量是路径的跳数，这对于现有的多r f 网络 而言不足以很好地代表网络的吞吐量特性。 1 8 m b p s 斗书 1 8 m b p s 斗书 s o u r c e m e s hr o u t e rd e s t i n a t i o n 7 1 1 m b p s1 1 m b d s s h o r t e s t p a t h ：2m b p s p a t hw i t hf a s t e s ti i n k s ：9m b p s b e s tp a t h ：1 1m b l o s 在图4 3 中：以最短的路径跳数为准则，将选用一跳的路径，其吞吐量 为2 m b p s 。如果以选择最快的路径，其吞吐量为9 m b p s 。而选用吞吐量最好 的路径时，其吞吐量可达到l l m b p s 。 2 8 电子科技大学硕士学位论文 4 2m r l q s r 对多r f 的和j 用 微软最近提出的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 ys o u r c er o u t i n g ) 是在d s r 协议的基础上，基于某些准则的高吞吐率w m n 路由协议，即基于 各个链路的期望传输时间( e t t ) 给每个链路赋权值。在这一协议中，提出 了一种新的路由矢量：w c e t t ( 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 ) 。 期望传输计数值e t x ( e x p e c t e dn u m b e ro ft r a n s m i s s i o n s ) 是链路上估计 的重传次数。 e t x = k + s ( k ) = 击 k 1 其中p 为分组从x 传输到】，不成功的概率，是通过网络测量统计得到的 链路分组丢失率。 s 为经过k 次尝试之后成功传输的概率。 链路的期望传输时间e t t ( e x p e c t e dt r a n s m i s s i o nt i m e ) 是链路分组丢失 率和链路带宽b 的函数。 e t t = ( 量) 木e t x 其中s 表示数据分组大小。 较小的e t t 值表示传输质量和速率较好的链路。如图4 - 4 所示。 第四章无线m e s h 路由算法一s q o r 11 m b p s l o l o s s e t t ：0 8 0m s 10 0 0 b y t e p a c k e t i 三嚣l 呻o s s 1 0 飞 e t t ：0 8 0m s 1 8 m b p s 5 0 l o s s e t t ：0 8 9m s 图4 4 链路的期望传输时间e t t 将路径上的所有链路的e t t 简单相加，得到一条路径的矢量s e t l 丫s u m o f e t t s ) s e t t = s u mo f e t t so f l i n k so i lp a t h 3 0 电子科技大学硕士学位论文 较小的s e t t 值表示传输质量和速率较好的路径。 而s e t t 仅仅代表了较短的路径，而不能很好利用频率分集。如图4 - 5 所示。 6 m b p s n o l o s s e t t = 1 3 3 m s 习惨 卜。p - f r e q u e n c y1 。f r e q u e n c y2 6 m b 6 m b p s 圣鎏 e t t = 1 3 3 m s 霹 _ c n 矽 s o u r c em e s hr o u t e r d e s t i m a t i o n ( a ) s e t t = 2 6 6 m s t h r o u g h p u t ；3m b p s 1 8 m b p s 3 参 s o u r c em e s hr o l n e