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

摘要 无线网状网络( w i r e i e s sm e s hn e t w o r k ，简称w m n ) ，作为一种新型网络结 构形态，被纳入2 0 0 4 年的8 0 2 1 6 、8 0 2 1 6 e 和即将制定的8 0 2 1 1 s 标准。无线网 状网的自组织性、自愈性，有效的移动用户管理和跟踪机制，高容量和高速率的 特性，迫切需要高性能的路由算法。 论文提出了一种无线网状网络的路由算法w i m e ( w i r e l e s si n t e l l j 譬e n c em e s h n e t w o r kr o u t i n 曲。w i m e 路由算法借鉴a o d v 路由协议的无线网状网路由协议， 以多跳的无线网状网络体系结构为基础，通过按需路由和泛洪控制来寻找路由。 新的路由准则结合路由发现与维护等过程，支持基本的路由寻找和异地子网的终 端相互通信并具有良好的路由特性。 论文在研究中实现了w i m e 算法的仿真，实验结果验证了该算法具有良好的 路由特性，实现了冗余路由的去除，实现了不同子网终端的通信。 关键词：网状网分布式路由协议有线接入点 a b s t r a c t w m n ( s h o r tf o rw i r e l e s sm e s hn e t w o r k ) ，i san e ws t n l c t u r eo ft h en e t w o r ka n di s a c c e p t e db y t h c8 0 2 1 6 ，8 0 2 1 6 ea j l dt h ef u t u r e8 0 2 1 1 s p m t o c o ls t 柚d a r d t h e s e l f - o 唱a n i z e ， s e l f i a i da i l de f - e c t i v em a n a g c m e n to ft h em o b i l eu s e r sn e e da h i g h p e r f 0 加a n c er o u t i n ga 1 9 0 r i t h m aw i r e l e s sb a c k b o n e _ b a s e dd i s t r i b u t e dm e s hn e 咐o r kr o u t i n gp r o t o c o l ( w i m e ) b a s e do na dh o cd e m 孤dd i s t a n c ev e c t o lw h i c hi ss u i t a b l ef o rm i d d l es c a l ew i r e l e s s m e s hn e t w o r k ，i sp r o p o s e d 如t h i sp a p e r t h ep m t o c o lc a ns u p p o n st w ow i r e l e s sc l i c n t s i nd j f f e r c n tb s s ( b a s i cs e r v i c es e t ) c o m m u n i c a t ew i t he a c ho t h e rb yw i r e l e s sr e l a y i n g r e d u n d a i l c ym e s s a g e sc a nb es i g i l 访c a i l t l yr e d u c e db ye x c h 卸g i n gl o a di n f o 肌a t i o n b e t w e e nc e n t r a in o d e sa n dl o o pp a t hi se i i m i n a t e d t h ep a p e ri m p l e m e n t st h es i m u l a t i o no ft l l ew l m ea 1 9 0 d t l l m n er e s u l t0 ft h e s t u d yv a l i d a t e st h a tt h ea i g o f i t h mh a sh 塘hr o u t j n gp e d o r i l l a n c ew 】1 i l ef c d u c i n gt h e r e d u n d a i l tr o u t ea n di m p l 锄e n t i n gt h ec o m m u n j c a t i o nb e m e e t e 瑚i n a l si nd i f f c r e n t s l l b n e t k e y w o r d s ：m e s hn e t w o r l 【 d s t r i b u t e dr o u u n gp r d t o c o is u p e r j o i n t 创新性声明 y8 5 8 9 五7 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：幽主 q 1 一 日期： 印百，f 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密在年解密后适用本授权书。 本人签名： 童qj 车 导师签名：烫苦；z 一导师签名：返鱼! 三 日期：逸! ! ：! 日期： 丝! ! ：! 第一章绪论 第一章绪论 1 1 课题背景 近十年来，网络服务的爆炸已经对电信的发展造成了巨大影响，并推动了传 统电路交换向分组交换的技术变革。作为现代通信技术的两个重要领域，1 p 技术 和移动通信技术正在全球范围内快速发展和应用，两种技术的结合也日益称为当 今通信技术发展的一个趋势。 i p 覆盖技术和基于i p 的各种服务成为炙手可热的研究课题和发展方向。i p 技术以其实现简单、廉价和有效的特点，在有线商用网中取得了巨大的成功。它 有效地解决了异构网之间的互连。另一方面，无线移动通信提供了相当高的自由 度给使用者，使用者不再囿于连接线路的长度、地理环境的限制，可以带着资讯 设备到处移动。这种崭新的使用形态促进了新一代资讯设备的成长与变化。结合 无线移动通信和i p ( 因特网) 这通信领域目前研究的两大热点，探讨无线i p 网 络的技术方法，是一件非常有意义的工作。 本课题正是着眼于此，研究无线网状网络。无线网状网( 、i r c l e s sm e s hn e t w o r k ， w m n ) 是一种多跳、具有自组织和自愈特点的宽带无线网络结构，即一种高容量、 高速率的分布式网络。它旨在探索无线移动通信与i p 技术的结合，研究在小型区 域范围内允许多个网络同时存在、不同网络自动区分、拓扑结构动态可变、具有 多跳和动态路由能力的自组织网络结构形式。 美国早在8 0 年代初即提出了自组织网络的概念，目前其研究重点在移动a d h o c 网络( m a n e t ) 。我国从七五后期开始自组织网络技术研究。无线网络技术 是当前获得迅速发展的技术，它允许移动用户采用更加灵活方便的方式接入网络。 典型的无线网络( 帅e l e s sl 丑n ) w n 通常具有两种组织形式：中心结构网络 ( i n 丘嬲t r u c t u f e dn e t w o f k ) 和a dh 0 c 网络( i n f f a s t n l c t l l r e l e s sn e 咐o r k ) 。中心结 构网络由包含固定有线网关的网络组成。在无线覆盖范围内，移动主机与基站( 固 定有线网关) 进行通信，并可在通信过程中移动。当移动主机离开原基站的无线 覆盖范围后，它可与另一个基站建立连接并通过该基站继续进行通信。在这种组 网和通信方式中，基站位置是固定不动的。g s m 系统即是采用这种网络组织形式。 a dh o c 网络是无线网络的另一种组织方法。在a d l o c 网络中，所有节点都处于 平等地位，它们之间都可能有通信关系存在，同时每个节点还承担着组网和为其 它节点中继的义务。网络中的所有节点都像路由器一样参与路由的发现和维护。 2 无线网状网路由协议的研究 无线m e s h 网( w i f e l e s sm e s hn e m o r k ，w m n ) w m n 可以看成是一种特殊 的w l 气n ，除移动性较低外，w m n 本质上是一种a dh o c 网络。目前主要观 点认为， 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 1 s 标准中。 目前，国内外对移动a dh o c 网络的自组织算法和路由算法有非常多研究。 但在移动a dh o c 网络和w m n 上，还没有路由协议正式标准。m e s h 路由协议 基本同a dh o c 网络路由协议，但需要针对w m n 的特点设计专门适用于w m n 的高效路由协议。 目前几种典型的路由协议有：d s d v ( 目的序列距离矢量路由协议) 、d s r ( 动 态源路由协议) 、t o r a ( 临时按需路由算法) 和a o d v ( a l dh o c 按需距离矢量 路由协议) 等。 w m n 无线移动自组织网络具有组网方式灵活、环境适应性强和快速应变的 特点，因而能够广泛应用于没有现存网络支持或现有网络不能满足机动性要求的 应用环境，将会在军事和民用方面得到广泛的应用。 1 2 项目来源 本项目来源于实验室与上海普罗通信公司的合作项目8 0 2 1 l 无线网状网 技术。主要的研究目标是提供一种分布式的无线路由协议，实现无线接入节点 ( a d c e s sp o i n t ) 通过无线中继进行无线网络的部署，并能够支持接入因特网进而 支持各种数据业务，并对路由协议进行设计实现和验证。主要是要在解决“无线 路由”的基础上，根据网状网的特点解决网络的规模控制以及实现i n t e m e t 网接入 的问题。主要的研究内容是无线路由协议的设计实现和验证。 1 3 本文工作 本课题的目标是研究适应于无线移动自组织网状网络特点的快速、准确、高 效和可扩展的动态路由技术。在组网体制上，无线骨干节点问通过无线信道沟通 和自组织，形成无线互联网络，实现网络的拓扑构成、中继与路由、接入控制和 用户管理等功能。与传统的a dh o c 网络相比，w m n 是一种由无线链路连接路 由器和终端设备的静态无线网络，是i i l t e m e t 的无线版本。 本文将在分析比较现有的各种w m n 路由协议的基础上，提出种新的路由 协议和算法w i m e ( w i r e l e s si 【i t e l l i g e c em e s hn e t w o r k ) ，并在o p n e t 中实现这个 协议并进行仿真。在以下各章中，首先介绍无线网状网络基本情况，包括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 n 的应用力案等# 接下 来将详细分析现有的无线自组织网络的路由技术，并做出比较；然后提出基于 a o d v 路由算法的新的路由协议w i m e ；最后给出w i m e 的实现和仿真结果，并 对结果加咀分析。 第二章无线网状网络 第二章无线网状网络 2 1 无线网状网的背景与起源 1 9 9 7 年，美国d a r p a 开始组织战场鲁棒战术移动通信系统的研发。在投入 大量资金、持续6 年多的研发之后，有关移动a dh o c 网络的一些理论与技术问 题得以解决，从而彻底改变了过去构建无线网络的规则。d a r p a 的目标是：无传 统的通信基础设置；采用多跳转发的传输机制；宽带数据数率；端到端的口支持； 除了数据业务以外，还要支持话音和视频业务；内置定位系统( 非g p s 系统) ； 能支持高达2 5 0 英里，j 、时的车辆移动速度。特别是近几年，美国通过一些大型国 防项目，攻克了a dh o c 网络的一些关键技术，其中，r r r 持有了其中的核心的 自主知识产权技术。 可是，除了战术无线通信以外，真正的商业应用在那里? 这是业界一直困惑 的一个问题。2 0 0 0 年初，i t t 将专有技术转让给了美国m e s h n e 咐o r k s ，用于商 业化产品的开发，至此，a dh o c 网络的商业化进程开始显现。2 0 0 2 年，h l t e l 开 始关注并认可a dh o c 网络技术，m e s h n e 哳o r k s 和1 r o p o s 等公司开始相继开发 出适用于商业应用的相关产品。 这些产品和方案主要定位于移动性较小或静止的a dh o c 网络无线m e s h 网络。于是，无线m e s h 网络的概念得到人们的关注。值得一提的是，自2 0 0 0 年 3 月m e s h n e 铆o r k s 成立以后，它成功地开发了一系列相关产品，基于其良好的 成长性，目前被m o t o m 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 曲业务模式发展；电路交换的电话 业务向i p 电话与多媒体业务发展；需要许可证的蜂窝电话向非许可证的无线业 务发展。 无线网状网路由协议的研究 集。 i 控制与镑理 霹p 机般务器模式 分散拄髑与餐理 ，e b 监务摸式 辫2 一l 黎巾向铃敬的凝嶷趋势 2 2 无线网状网的结构与关键技术 2 2 1 什么是无线网状网w m n 无线网状网( w i r e l c s sm e s l ln e t w o r k ，w m n ) w m n 是一种多跳、具有自组织 和自愈特点的宽带无线网络结构，即一种高容量、高速率的分布式网络。目前主 要观点认为，w m n 是一种由无线链路连接路由器和终端设备的静态无线网络， 是i n t e m e t 的无线版本。w m n 不同于传统的无线网络，可以看成是w n ( 单 跳) 和移动a dh o c 网络( 多跳) 的融合，且发挥了两者的优势。作为一种新型网 络结构形态，m e s h 结构已被纳入到8 0 2 1 6 _ 2 0 0 4 、8 0 2 1 6 c 和即将制定的8 0 2 1 1 s 标准中。w m n 可以通过一些中间节点连接互相远离不能直接连接的无线路由器。 2 2 2w m n 与w l a n 网络的区别 无线m e s h 网w m n 可以看成是一种特殊的无线局域网w i a n ，除移动性 较低外，w m n 本质上是一种a dh o c 网络。在拓扑结构上，w i 。a n 在最后一 跳的接入上采用无线方式，而w m n 无网络基础设施，是多跳无线网络，可实现 网络自形成、自伸缩、自愈和自诊断等。 在网络设备上，w b 气n 的a p 负责终端设备的接入，而广义的w m n 的所 有节点均能承担本地接入与其他节点的信息转发功能，即具有路由器和中继器功 能。 在路由协议上，w l a n 固定路由，而w m n 则采用动态路由，路由冗余和 自愈能力强。 在w l a n 中，两个彼此相邻的设备不能直接通信，必须借助a p 的接入与 第二章无线网状网络 转发，如2 2 所示。 匿拉一2 信i 磁蛳i f i 网络拓扑结构 在广义的w m n 中，典型情况下，两个彼此相邻的设备可以直接通信，如 图2 3 所示。 围2 3 无啦网状罔删e s hm ”k ) 拓扑结构 2 2 3w m n 的网络结构 基础设旃形态： 无线网状网路由协议的研究 图2 _ 4 无线网状网基础设施 无线m e s h 网具有网络基础设置，m e s h 网延伸了i n t e m e t ，在a p 与终端设 备之间形成无线回路。终端设备( 如8 0 2 ，1 1 b g 设备) 通过a p 或无线路由器( w r ) 的路由选择和中继功能，与无线网关( w g ) 形成无线链路。 a p ，w r 通过路由选择及管理控制等功能为终端设备选择与目标终端设备通 信的最佳路径，从而形成无线的回路。通过w g 连接其他网络，即可实现无线宽 带接入。 终端设备通过自身的网络互联功能连接形成一个点到点的网络，节点可以任 意移动，网络拓扑结构也随之变化。 两个无法直接通信的终端设备可以借助其他终端设备的转发功能实现通信。 终端设备在不需要其他基础设施的条件下可独立运行，可支持终端的移动接入， 快速自形成和网络自愈。 虽然广义的网状网络中任意两个对等结点只要是相互挨着，都可以进行通信。 然而由于实际需要，绝大多数现代的网状网络只是通过部分结点相互连接。由于 在网状网的应用中，终端结点一般是手持设备。因此，终端结点受到了能源和发 射功率等等影响而约柬了其的作用。在更为实际的情况下，无线网状网是通过某 些骨干结点之间的相互连接来进行组网的。由于在实际中，无线网状网的骨干结 点一般是固定不变而且有固定电源的，因此不用考虑电源供给等问题。而且，在 这种组网结构下，原始的终端协议可以不作任何的改变，需要做的只是在骨干节 第二章无线网状网络 点中加入无线网状网路由协议，如图2 5 所示。 2 2 4w m n 的关键技术 图2 - 5 实际运用中的网状网络拓扑结构 1 ) 多址接入技术 正交分割多址接入技术( q d m a ) 是m e s h n e t w o r l 【s 公司的一项专利技术。 q d m a 使用d s s s 调制技术，工作在2 4 g h z 的i s m 频段。由于q d m a 在 m a c 子层使用多信道方式( 三个数据信道和一个控制信道) ，因此，与单信道相 比，更能适用于高密度的w m n 终端设备。q d m a 提供较强的纠错能力，同时 增强了抗干扰能力和信号的灵敏度，在高速移动环境下可提供达6 m b p s 的峰值数 据传输速率。q d m a 内置定位技术能够对通信设备进行精确定位，而不依赖于 g p s ，误差不超过1 0 米。 此外，o f d m 技术也列入到8 0 2 1 l a 旭( 即将支持m e s h ) 和8 0 2 1 6 ( 已经支 持m e s h ) 标准中。 2 1 天线技术 无线m e s h 宽带网络中一个重要的问题就是天线的使用，因为每个节点必须和 各个方向上的多个节点通信，很简单的一种方式就是采用全向天线，但是这样覆 盖范围有限，并会带来干扰，导致频谱利用率下降，网络容量减小，所以不建议 采用全向天线。美国的s k y p i i o t 公司将智能天线技术应用于无线m e s h 网络，允许 频谱重复使用，从而大大提高了频谱的利用率，同时减小了干扰。在i e e e8 0 2 1 6 a 宽带无线接入标准中也建议把智能天线技术应用到无线m e s h 宽带接入网络中。 3 1 m e s h 路由技术 在移动a dh o c 网络和w m n 上，目前还没有路由协议正式标准。m e s h 路 由协议基本同a dh o c 网络路由协议，但需要针对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 c 按需距离矢量路由协议) 等。 钔m a c 协议及资源分配与管理 在w u 埘m a c 协议的基础上，对于单信道方案，要解决单信道方式下的隐 藏终端等问题，如采用m a c a 协议、控制信道和数据信道分裂的双信道方案和 基于定向天线的m a c 协议等。 解决多种业务和多优先级业务的公平接入信道问题，以提高系统的综合接入 能力和q o s ，如对w l a n8 0 2 1 1 e 的改进和扩展。解决系统调度策略对于实时性 要求较高的业务端到端q o s 保障问题。 5 1m a c 协议及资源分配与管理 可采用多信道技术f i ) m a 、t d m a 、c d m a ( 传统的d s 一c d m a 、 f h c d m a ，u w b ) 、q d m a 、s d m a 和以上混合，消除干扰和隐藏终端等问题。 6 ) 安全结构与管理 网状网络的安全结构与管理方案，可以抵御干扰和攻击等。 2 3 无线m e s h 网的特点与应用 2 3 1w m n 的优点与缺点 1 、自愈性：w m n 可以提供完全的端到端的多重冗余路由，这就意味着若由于某 种原因某个链路失效，网络能自动地更换路由。 2 1 可靠性：为了提高链路质量，可通过增加中间节点，即缩短节点之间的距离来 实现。 3 1 自配置能力；w m n 是一种自组织网络，不需要或很少需要人工配制网络。因 而，网络能够自动判断并更新网络相关配置。 4 ) 分散管理问题：由于w m n 的分散性，很难实现象有线网络那样那个的集中 管理，即使对于低移动性的w m n ，网络配置与管理仍然是一个不易解决的问 题。 5 1 共存干扰问题：对于非许可证频段的w m n 必然存在与其他共存网络的无线 干扰问题。安全问题：由于w m n 结构本身的脆弱性，极易遭受其他恶意节 点的攻击、干扰和窃听，所以安全问题是w m n 需要解决的重要问题之一。 2 3 2w m n 的应用 无线网状网技术的研究是为了满足中小规模移动接入因特网络的需要。一般 来说，移动网袄网络通常可用于以下场合。 有线资源匮乏的地区，比如不发达国家和地区 第二章无线网状网络 不宜进行有线部署的地区，比如旧的楼宇，医院，宾馆等等 需要建立一个私有的无线通信网络的地区，比如学校和社区的网络 无线网状网在军事领域和民用领域都有许多潜在的应用，尤其适合于民用通 信。在民用通信淋浴，无线网状网技术可用来构建私有的无线接入网络，或用于 有线覆盖网络的延伸以降低部署的成本和提供移动特性。具体的讲，它可用于以 下的通讯任务 作为无线局域网的扩展 作为传统移动通信系统的后备网络 信息家电的互联以及家庭无线互联网 社区无线网络的互联 可靠，有效的通讯保障是网络成功的一个重要条件。对民用移动通信系统来 说，它应该满足以下要求： 1 ) 易组织性。构建网络不需要专业的背景知识，购买设备后直接可以建立起自己 的移动通信系统。 2 ) 公平性。对于在接入网络内的每一个客户，如果没有特别的指定，那么每个客 户应该公平的共享带宽。 3 ) 移动性。对于在无线网络中的客户应该支持无缝隙的漫游移动特性。不会因为 越区而使通信中断。 钔廉价性。进行布网的设备和工程应该是经济廉价的，不需要太多的资金和人力 便可以进行部署。 无线网状网络的特点，使得它成为民用移动通信系统重要的一种选择。由于 它不依赖于有线网络，因此具有方便部署和需求的资金和工程量小的特点。通过 分布式的路由选择协议使得它能够进行网络自组织，不需要任何专业的背景知识 便可以建立网络。为了在节点移动造成网络拓扑变化时保持正常的通讯那里，协 议设计中往往要考虑链路终端的情况，协议需具有路由熏构，连接恢复，备份路 由等能力。无线网状网中所有通信设备均通过无线方式进行中继，因而打破了蜂 窝系统受单一基站覆盖范围的限制，为部署可扩展的无线网络提供了较强的能力。 研究并设计实现高性能的网状网络，具有重要的应用价值和意义。 第三章无线网状网路由技术 第三章无线网状网路由技术 路由协议的主要任务是发现和维护从源节点到目的节点的路由，并指引数据 分组从源节点正确的到达目的节点。传统网络的路由协议包括距离向量类协议状 态类协议。无线网状网与一般无线网络有很大的区别，在无线网状网中每一个覆 盖区域的节点都是运动的，可能从一个区域跨越到另一个区域，路由随时可以变 化：在同一个区域内，网络终端的数量可能非常的大，需要维护的路由信息也非 常多；除了维护无线接入终端的路由信息之外，由于可能要对骨干节点进行管理 和控制，因此也要对骨干节点的拓扑进行准确的描述和表现；骨干网络节点间的 通信是通过无线方式进行的，而无线链路具有动态变化和不可靠的特点：需要多 次的路由中继，因此每个中间节点都需要知道到达目的节点的路由信息等等。故 而无线网状网的路由必须在受到多重约束条件和动态环境下，能够保证数据的可 靠传输。本章首先讨论了相关的网络协议，然后提出了一种适应于无线网状网的 分布式路由的思想和协议，并对该路由协议的建立过程，发现过程，维护过程和 路由的环路与路由的备份进行了概念上的讨论。 3 1 相关网络协议研究 3 1 1 协议的分类 由于无线网状网是一种新兴的网络技术，它既有传统有线网络的骨干节点拓 扑较为稳定，路由相对变化较慢的特点。又因为每个骨干节点通过无线进行连接 和移动终端可以运动而具有了无线网络中链路不稳定，终端的拓扑结构变化较大 的特点。为了解决移动性和无线通讯的特点带来的问题，目前己提出了许多的路 由协议。按不同的标准，这些协议可分为不同的类型。 1 ) 源路由协议与分布路由协议 在传统的源路由协议中，要求计算路由的节点具有整个网络的拓扑结构信息。 由此计算出来的路径信息被包含在源节点发送的消息中，网络的其他节点按此路 径传递消息。由于无线网状网的拓扑结构可能时常变化，为了使路由的计算节点 保持准确的网络拓扑信息，网络将增加大量的更新消息，从而带来比较大的开销。 因此，此种方式只适合与网络结构相对稳定的有线情况。为解决此问题，提出了 按需路由的源路由协议。源路由协议可以避免分布式路由协议中出现路由环等问 题，而且简单、易于实现。 1 4 无线网状网路由协议的研究 在分布路由协议中，路由的计算由网络中的节点分布完成，并且路径信息被 分布存储在网络中个结点中。网络中的节点根据自己的路由表进行消息的转发选 择。分布路由协议的可伸缩性较好。然而，一些分布式路由协议( 如o s p f ) 仍要 求在网络节点中维护网络全局状态信息，这种协议不适合于拓扑结构变化频繁的 网络。有一些分布式路由协议( 如t o r a ) 不要求结点维护网络的全局状态信息， 但设计这类协议时应避免路由中出现路由环，或应在路由环出现时采取有效措施 消除。 2 、层次路由协议与非层次的路由协议 在层次路由协议中，按区域将节点划分为多个组，而在高层将每个组视作一 个逻辑节点。组内节点之间采用一般的分层次路由算法。每个节点主要需维护同 一层次同一组内的节点的状态信息，因而具有很好的可伸缩性。层次路由协议还 可以解决分离的节点群之间的通讯问题。它所存在的问题时如何在高层逻辑节点 中表示底层网络的状态信息，以及在拓扑结构不断变化的情况下如何选择高层逻 辑节点。这种协议相对较复杂。 3 1 主动式、按需路由及混和路由协议 主动式协议最大的特点是周期性的路由信息获取操作。传统的路由协议一般 属于此类。这类协议又可再分为距离向量类协议和链路状态类协议。前一类如 r 口、d s d v 协议，后一类有0 s p f 、o l s r 协议等。 按需路由协议又称反应式协议。这类协议中，只有单节点需要传输数据包且 没有目标节点的路径时，才通过路由发现过程来获得所需要的路由信息。当网络 拓扑发生变化时，通过路由维护过程来修补失效的路径或利用路由发现过程来得 到新路径。 混和式路由协议一般基于簇或区域将节点分层次组织起来，在簇内或区域内 采用主动获取路由信息的方式，而在全局范围内采用按需路由方式。 3 1 2 已有网络协议介绍 由于无线网状网属于无线中继动态网络，与自组织网络类似。这里我们对自 组织网络的相关协议进行介绍，对无线网状网的路由协议设计有很好的借鉴意义。 1 1 传统路由协议 路由问题是计算机网络中的经典问题，因而对他已有较深入的研究，并有一 些较成熟和得到广泛应用的协议，如路由信息协议( r 口) 和o s f p 协议。r i p 基 于分布的b e l l m a n f o r d 算法，属于距离向量类协议。o s f p 协议则属于链路，状态 类协议。 2 、t o r a 协议 p a r k 等提出的t o r a ( t e m p o r a l l y o r d c r e dr o u t i n ga l g o r i t h m ) 【2 】中，通过构造 第三章无线网状网路由技术 个有向的无环图( ad i r e c t e da c y c l i cg r a p h ) 来实现网络路由。t o r a 源于g a f n i 和b e r t s e k a s 提出的算法叽算法分布执行，通过多次迭代来建立到目的端的多条 无环路径。t o r a 的主要过程为： 路由建立过程：当节点需要一个目标节点的路由时，它向网络中广播一个 请求消息。消息在网络中传播，直到被目标节点或具有相应有效路由信息 的结点收到。接受结点再广播一个更新( u p d a t a ) 消息，其他结点据此调 节路由参数，最终形成从源结点到目标结点的多条路径。 路由维护过程：当结点发现一个到一个目标结点的路由不再有效，它根据 邻居结点的路由信息调节路由参数或发起路由建立过程，从而建立到目标 结点的路径。 t o r a 的优点是算法的分布性较好，没有周期性的广播操作。其缺点是： 依赖于i m e p ( h l t e m e tm a n e te n c a p s u l a t i o np m t o c 0 1 ) h ( 或其他数据链路 层协议) ，为其提供可靠按需传输服务。 路由建立过程的广播开销较大，再网络拓扑变化较快的情况下将会产生较 多的路由控制报文，甚至使得算法不能较快的收敛。 不支持单向链路。 3 1d s d v 协议 d s d v ( d e s t i n a t i o n s e q u c n c e dd i s t a n c ev c c t o r ) 协议【5 j 与r i p 协议类似，但协 议中使用目的端顺序好( d c s t i a t j o s e q u e c cn u m b e r ) 来避免因使用过时路由信息 丽产生无效的路径( 包括路由环或中断的路径1 。每一个目标结点的路由记录对应有 一个目的端顺序号，这个顺序号由目标结点产生。当结点从邻居结点的距离，向量 报文中得到某一目标结点的另一个路由记录时，若新记录的顺序号比已有记录的 新，则结点使用新路由记录；若两个路由记录的顺序号相同，则结点使用路径长 度更短的记录；否则，目标结点的路由记录不变。 d s d v 的优点是可避免出现路由环，协议分布执行，在网络链路状态改变时 协议收敛较快。其缺点有：周期地广播距离向量报文要占用网络资源：触发性路 由更新可能带来较大地网络开销；基于双向链路的假设。 4 1 动态源路由( d s r ) 协议 d s r ( d y n a m i cs o u r c er o u t i n 曲1 6 】协议是一种按需路由协议，当需要发送消息时 才进行路由计算，从而避免了主动式协议周期地发送路由控制报文带来地开销。 网络中每个结点均维护一个路由缓冲器( c a c h e ) ，记录从此结点可达地目标结点地路 径信息。协议地主要过程为： 路由发现过程：当发送报文时，若没有可用地路由信息，源结点发起一次 路由发现过程。结点使用扩展环地搜索( e x p a i l d i n g 渤gs e a r c h ) 方法向网络中 其他结点广播一个路由请求( r o u t cr c q u e s t ) 报文，由目的端或由相应有效 无线网状网路由协议的研究 路由信息地中间结点返回路由应答报文。 路由维护过程：当结点发送或转发一个报文失败( 如未收到应答消息或数 据链路层指示发送失败) 时，认为链路中断。此时结点将向源结点返回一 个路由出错( f o u t i n ge r r o r ) 报文，使得路径上的结点将中断的链路从路由缓 冲器中删除。源结点使用其他有效路径发送报文或发起路由发现过程来获 得目标结点地路径。 由于采用源路由方式，因而路由过程中可避免出现路由环，同时中间结点不 必存储转发消息所需地路由信息。d s r 协议采用按需路由地方式，没有周期性地 广播操作，因而减少了网络开销，并且在存在单项链路地情况下仍可正确得到数 据传输路径。 d s r 存在如下地缺点：当一跳链路中断时，所有包含此链路地路由均将失效， 由于链路状态的更新不是在全网络范围内进行，因而存在过时路由问题。再数据 流突发性较强的情况下，按需的链路中断检测方式可能会带来较大地丢失率。结 点侦听相邻结点发送的消息中的源路由信息，加大了结点的处理开销，且不利于 支持无线便携设备的睡眠操作。另外，源路由方式增加了报文首部的开销。 5 1a o d v 协议 a o d v f a dh o co nd e m a n dd i s t a n c ev c c o t 科1 】协议结合了d s d v 协议和d s r 协议的特点，是一种改进了的距离向量路由协议，同时也是按需路由协议。它使 用目的端顺序号来避免产生无效的路径，当它不使用d s d v 中周期地更新路由的 方法，而是采用了d s r 中按需路由的途径。其主要过程为： 路由发现过程：与d s r 中的过程类似 路由维护过程：结点周期地广播一个眦u d 消息给邻居结点，表明自己 的存在，结点通过接受邻居结点发送的l 妇i l i 。0 消息来正式他们之间链路 的有效性。结点也可以使用数据链路层的机制来监视链路的状态。当检测 到链路中断时，对当前通过此结点的活跃路径上的上有结点，分别向他们 发送一个路由应答消息，将路径中断消息传送给他们。接受到此消息的结 点进行相同的路由更新过程，知道活跃路径上的所有上有结点更新其路由 表。 a o d v 协议同样具有按需路由的优点，同时协议中也可避免出现路由环。 a o d v 仍需要在相邻结点之间周期地交换h e u d 消息，具有比d s r 协议大的网 络开销。 6 、g s r 协议 g s r ( g l o b a l s t a t er o u t i n 曲【7 】【8 1 协议是一种结合了距离向量协议特点的链路状 态路由协议。g s r 协议的基本过程与链路状态路由协议相同，区别在于g s r 采 用了不同的方式来传播链路状态信息。在g s r 中，结点只周期性的和邻居结点交 第三章无线网状网路由技术 换它所获得的链路状态信息，这种交换方式与距离向量路由协议的方式相同。由 于移动自组织网络的直径( 任两个结点之间的最大距离) 通常不大，因而链路状态改 变的信息可望在不多的几个路由更新周期内传播到网络中所有结点。g s r 的优点 是，链路状态改变的信息只在相邻结点之间传递，因而避免了广播带来的开销。 协议分布执行。 g s r 的缺点是，链路状态改变的信息需要多个周期的时间才能传播给网络中 所有的结点，使得出现路由环的概率增大，因而协议只适合与直径不大的网络。 同时，周期性的路由信息交换操作带来了一定的协议开销。 7 、0 l s r 协议 o l s r ( o p t i m i z e dl i i i ks t a t er o u t i n 9 j 协议时一个基于链路状态算法的协议， 可用于结点密集的较大网络。o l s r 协议可建立与i m e p 【4 】协议之上，利用i m e p 的链路状态监视功能、多点传递( n m l t i p o i n tr e l a yf o 删删i n 曲功能、安全认证功能 等。协议中，结点周期的广播它的多点传递结点的信息，并根据从其他结点得到 的这些信息计算通过多点传递结点的路径。当链路状态发生改变、到某一个目标 结点的路径过期或发现到某一目标结点的更短路径时，结点更新存储的路径信息。 协议采用逐段( h o p - b y - h o p ) 路由方式，不是源路由方式。 o l s r 协议在网络链路状态改变时路由算法收敛较快，同时采用多点传递技 术较大地减少了路由广播操作的开销。其缺点由：链路信息的广播操作仍具有较 大的开销；报文只在双向链路( 包括相邻结点之间的两跳方向相反的单项链路) 上传 送，不能利用单项链路来优化传输路径。 8 1z r p 协议 z r p ( z 叽er o u t i n g p r o t o c 0 1 ) 使用路由区( r 0 1 n i n g z o n e ) 的概念，是一种混合式 的路由协议。一个结点的区包括离它的距离不超过区的半径的所有结点。区的半 径为协议预定义的数值，通常为一个较小的整数( 如2 ) 。每个结点维护它的区内的 结点的路由信息。z r p 假定数据链路层协议提供邻居结点的发现和维护功能。区 内结点的通信通过l 啄p ( i n l f a 2 咖er o u t m g p m t o c 0 1 ) 来实现。z r p 中未定义l 堰p ， 而是使用已有的协议( 如a o d v 、o s p f 等) 作为i a r p 。跨区通信使用 r p ( i n t e r z o n er o u t i n 曲。m r p 采用类似于按需路由的技术，在路由发现时使用边 界广播( b o r d e r c 弱t i n 曲的操作。源结点根据所存储的区的信息将路由查询报文发送 给区的边界结点。若目的结点在边界结点的区内，则边界结点向源结点返回路由 应答报文，报文包含收集到的路径信息；否则，边界结点充当源结点进行同样的 过程直到发现目的结点。当检测到路径中断时，结点向路径的源结点返回一个路 由出错报文。源结点可以发起新的路由查询过程来建立新路径。 z r p 中使用区和边界广播的机制，有效地限制了路由查询时报文的广播范围， 降低了路由发现的开销。通过层次组网的方式使得协议具有较好的可伸缩性。其 无线网状网路由协议的研究 缺点为：结点同时要支持i a r p 和i e r p ，增加了协议的复杂性和结点的处理开 销。此外，协议性能受协议参数设置的影响较大。 9 1c b r p 协议 c b r p ( c i u s t c rb a s e di b u t i i l gp r o t o c o 一1 1 】是一个基于簇的层次路由协议。c b r p 中使用簇形成算法将网络中的结点划分到多个簇中。c b r p 使用源路由方式传送 消息，协议的主要过程为： 链路状态的监视：结点周期地广播一个h e u d 消息给邻居结点，在h e u d 消息中包含结点的邻居列表。当结点接受到邻居的h e u d 消息时，相应 地更新到邻居的链路状态。 簇形成与维护算法：根据标识号( i d ) 最低的原则选择簇首并形成簇。结点 的状态信息在h e u d 消息中表明。利用h e u d 消息中的信息，簇首还 可以知道通过那些结点可以邻近的簇，这些结点成为网关。 路由发现过程：采用按需路由的方式。与d s r 的不同指出在于，路由请 求消息从一个簇首传送给相邻簇的簇首，而不是在全网内广播。 路由维护过程：当链路中断时：结点将消息发送给本簇的簇首，由后者进 行路径的修补，同时向源结点返回路由差错信息。若路径不能修正，源结 点可以发起新的路由发现过程来获得数据传输路径。 c b r p 采用簇的组网方式，减少了路由查询过程中的广播开销，使得协议具 有较好的可伸缩性。并且，c b r p 还一定程度地支持单项链路的使用。c b r p 中 簇的维护需要一定的开销，适合与规模较大的网络。 1 0 1 利用结点位置的路由协议 上述协议军事基于网络拓扑信息的路由协议。l 气r ( l d c a t i o n 粕d e dr o u t i n 曲旧 中提出利用结点位置信息来辅助送行路由计算。其要点是利用结点的位置信息来 限制路由发现过程的搜索( 广播) 范围，从而减少协议开销。网络结点的位置信息可 以通过g p s 系统或其他一些定位系统获得。如同广播中一样，利用位置信息仍存 在位置消息的时效性、可能没有反映真实的网络连接等问题。 3 2 无线网状网路由协议 由上一节对移动网络路由协议的整体介绍和分析。我们发现基于移动网络的 路由协议总体可以分为几种方式 是否通过广播方式向周围的邻居结点报告结点信息或者链路状态 是否支持单向链路 是否进行按需路由请求 是否对网络进行分层和分簇 第三章无线网状网路由技术 1 9 由于按需路由算法对动态链路有快速适应能力，且具有占用网络资源少，的 存储开销等优点。此外，在网络结点中，结点不需要维护非通信状态结点的路由 信息，且能够对断链和拓扑变化作出快速反应。因此在本文的协议中，采用了按 需路由的方式来发现路由。 由于在网状网里，骨干结点的位置是固定不变的，而 且骨干结点是通过电源进行供电，并且采用的是相同的设备，因此对于无线网状 网络的骨干结点而言，链路是几乎对成的，并且不需