（信号与信息处理专业论文）无线mesh网络qos路由算法研究.pdf

无线m e s h 网络q o s 路由算法研究 摘要 无线路由技术是无线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 具有服务质量( q o s ) 保障能 力，为此以w m n 的应用为背景的q o s 路由算法相继开发出来。但这些算法仍存在算 法复杂度高、效率低、寻优准确度不够以及不能同时满足多个q o s 指标约束等多方面的 缺陷。因此对于w m n 的q o s 路由算法研究仍然是目前的一个热点课题。 针对单播路由的情况，本文提出了基于免疫遗传算法的w m n 中q o s 路由算法， 在遗传算法的基础上引入免疫原理，对带宽、时延、丢包率三个参数进行综合优化，在 提高收敛速度的同时，克服了以往算法易陷于局部最优，寻优不准确的缺陷。针对多播 路由的情况，本文提出了基于混合蚁群算法的w m n 中q o s 多播路由算法，采用粒子 群算法中粒子的自适应搜索能力，来训练蚁群算法中的控制参数，不仅克服了标准蚁群 算法中的控制参数需要靠人工经验或反复试验选取的缺陷，而且提高了算法的稳定性和 运行效率。本文所进行的两个方面的研究均通过仿真取得了较为理想的效果，具有广泛 的应用价值。 ， 关键词：无线m e s h 网络；q o s 路由；免疫遗传算法；混合蚁群算法 哈尔滨t 程人学硕十学何论文 a b s t r a c t w i r e l e s sr o u t i n gi sa nk e yt e c h n o l o g yo fw m n ( w i r e l e s sm e s hn e t w o r k ) ，o nt h eo t h e r h a n d ，w i t ht h ep o p u l a r i z a t i o no fm u l t i m e d i ab u s i n e s s ，w m ni sr e q u i r e dt op r o v i d es t r o n g q o s ( q u a l i t yo fs e r v i c e ) h o w e v e rt h e s ea l g o r i t h m sh a v es l o wc o n v e r g e n c ea n da r eh a r dt o f i n dt h eo p t i m a lp a t ho fq o s t h e r e f o r e ，t h er e s e a r c ho n q o sr o u t i n ga l g o r i t h mo fw m ni s a l s oa nh o tt o p i ca n ds i g n i f i c a n ti nt h e o r ya n dp r a c t i c e t h i sp a p e rp r e s e n t sa na l g o r i t h mb a s e di m m u n eg e n e t i ca l g o r i t h mw h i c hi m p r o v e df r o m t h eg e n e t i ca l g o r i t h mf o rw m ns i n g l e c a s tq o sr o u t i n g ，t h ea l g o r i t h mi n v o l v e st os e v e r a l p a r a m e t e r s ( b a n d w i d t h ，t i m ed e l a y ，p r o b a b i l i t y o f u n r e c e i v e dp a c k e t s ) a n dh a sah i g h c o n v e r g e n c es p e e da n dd o e s n tg e ts t u c ka tal o c a lo p t i m u m t h i sp a p e ra l s or e s e a r c h e so n q o sm u l t i c a s tr o u t i n gb a s e do nh y b r i da c o ( a n tc o l o n yo p t i m i z a t i o n ) a l g o r i t h mf o rw m n ， t h ea l g o r i t h mi m p r o v e df r o mp s o ( p a r t i c l es w a r mo p t i m i z a t i o n ) t oi m p r o v et h es t a n d a r da n t c o l o n yo p t i m i z a t i o n sp a r a m e t e r s i m u l a t i o nr e s u l t ss h o wt h a tt h ec o n v e r g e n c es p e e do f m u l t i c a s tr o u t i n ga l g o r i t h mb a s e do ni m p r o v e da c oi sf a s ta n dt h ep e r f o r m a n c ei ss t a b l e t w or e s e a r c h e so ft h i sp a p e rh a v eg o o dp e r f o r m a n c ea n di sw i d e l yu s e di np r a c t i c e k e yw o r d s ：w i r e l e s sm e s hn e t w o r k ；q o sr o u t i n g ；i m m u n eg e n e t i ca l g o r i t h m ； h y b r i da n tc o l o n yo p t i m i z a t i o n 第1 章绪论 第1 章绪论 1 1课题研究的背景及目的意义 近几年，通信领域的快速发展已经使得人们进入了前所未有的信息化时代。移动电 话的发展使人们之间的沟通越来越便捷，甚至能够实现在“任何时问 ，“任何地点 ， “任何人”之间的沟通。i n t e m e t 的迅速发展更使我们的生活发生了翻天覆地的巨大变 化。音乐、视频、网络新闻、b b s 、游戏等五花八门的应用，使得用户的范围非常广泛。 随着科学技术进步，人们的需求也在不断的升级。由于线缆的局限性，有线网络已 经逐渐不能满足人们对于灵活移动的要求，因此无线网络应运而生，且成为网络服务的 一大亮点。目前的无线网络技术主要包括蓝牙技术，红外技术、无线城域网w i m a x 、无 线局域网( w i r e l e s sl o c a la r e an e t w o r k ，w l a n ) 等。 由于无线局域网具有应用方便和部署简单的优点，已经被人们普遍接受，在个人以 及中小企业等用户中获得了广泛应用。然而，在网络结构方面，传统的w l a n 仅仅是 单一的星型网络连接方式，即接入点( a c c e s sp o i n t ，a p ) 与接入点之问均是末级网元，设 备与设备之间、用户与用户之问的通信最终还要通过与有线网络的连接完成。如果a p 与a p 可以直接经过无线链路完成信息的交换，这种结构在网络覆盖规模的扩展上定然 会方便许多。为了能实现无线通信无处不在的通信e l 标，则需要在移动a dh o c 网络【卜2 】 的技术基础上，开发出一种完全适合用于民用通信的无线多跳形式的网络技术，因此无 线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 3 1 技术随之出现。无线m e s h 网络的a p 连 接方式如图1 1 所示。 糊幽蛾蠢o 交换机 囊豳糊雌= = 掣瞄嘲髓， 凡 ，1 ，o l 。f a p 灌m。一：薹。：溢 “1 彳。_ ) ；。ja p a p 圆 。_ 一一。彳ap 皇，a p 匆。一 。一乏t ? 。乡 j 无线m e s h 网络作为解决无线接入的“最后一公里”瓶颈问题的一种关键技术受到 哈尔滨t 程大学硕七学位论文 了越来越多的关注，它融合了无线宽带网w b a n t 4 1 、无线局域网w l a n 和移动a dh o c 网络的优点，己被认为是3 g 和下一代移动数据通信领域的主要竞争对手。w m n 与 w l a n 、w b a n 和移动a dh o c 网络的关系如图1 2 所示。 图1 2w m n 与移动a d h o c 网络、w b a n 和w l a n 的关系示意图 无线m e s h 网络作为一个新兴的研究领域，在理论框架及实现技术两个方面面临着 许多富有挑战性的研究课题。无线路由技术是w m n 中的一个关键问题，它在很大程度 上直接会影响网络的性斛5 1 。另外，多媒体业务的迅速普及和商业应用的快速进展对于 w m n 提供服务质量( q o s ) 保障的能力提出了越来越严格的要求。由于w m n 具有异构 特性【6 1 ，因此其路由端到端q o s 保障是一个非常具有挑战性的课题，如果解决不好，将 会成为w m n 发展和应用道路上的障碍。因此，对于w m n 的q o s 路由算法研究有着 重要实际意义。基于此，以w m n 的应用为背景的q o s 路由算法相继被开发出来。目 前，对于这一课题进行研究的文献比较少，且存在算法复杂度高、效率低、寻优准确度 不够以及不能同时满足多个q o s 指标约束等多方面的缺陷【_ 卜1 3 】。本课题的主要目的就是 对w m n 中的q o s 路由算法进行研究，找到适合于w m n 路由寻径，又能满足q o s 保 障的高效路由算法。主要进行以下两个内容的研究： 1 基于免疫遗传算法的w m n 中q o s 单播路由算法研究 目前对于w m n 中q o s 单播路由算法的研究中，应用效果最好的是基于遗传算法 ( g a ，g e n e t i ca l g o r i t h m ) 的w m n q o s 路由算法【8 】，该算法能够较为快速找到最优路径， 但是由于遗传算法自身存在易陷入局部最优的缺陷，不能保证每次都获得最优路径。本 文提出了一种基于免疫遗传算法【1 4 ( i g a ，i m m u n eg e n e t i ca l g o r i t h m ) 的w m n 中q o s 多 约束路由算法，对带宽、时延、丢包率三个q o s 约束参数进行综合优化，得到从源节点 到目的节点满足约束条件的最小代价路径。 2 基于混合蚁群算法的w m n 中q o s 多播路由算法研究 2 第1 章绪论 目前对w m n 中q o s 多播路由算法这一课题的研究文献中，应用效果最好的是基 于蚁群算法( a c o ，a n tc o l o n yo p t i m i z a t i o n ) 的多播路由算法【7 j ，该算法能较为快速的找到 近似最优多播路径，但是由于蚁群算法中的四个控制参数 ，p ，p ，q ) 的选取需要大量的 反复实验获得，并且很难找到使算法性能达到最好的参数组合，由此影响了获得最优多 播路径的性能，增加了算法的复杂度。本文利用混合蚁群算法，在给定带宽、时延、丢 包率三个q o s 参数约束下，采用粒子群算法【1 5 】来训练蚁群算法中的四个参数，使得蚁群 算法中的参数不必靠人工经验或反复试验选取，而是通过粒子搜索自适应选取，从而提 高了算法的性能。 1 2 课题的国内外研究现状 1 2 1无线m e s h 网路的国内外研究现状 2 1 世纪初期的几年，通信行业的几个重大事件引起了很多人的关注，其中之一是美 国的i t t 公司将其专门为美国军方研究的战术移动通信系统的某些专利技术转让给 m e s hn e t w o r k s 公司，m e s hn e t w o r k s 公司在此基础上开发出一系列拥有自主知识产权的 无线多跳民用网络产品无线m e s h 网络全套技术产品，并且在市场上获得了巨大的 成功1 1 6 。同时，诺基亚、t r o p o s 、s k y p i l o t 、北电网络、f i r e t i d e 和r a d i a n | n e t w o r k s 等多 家公司开发的w m n 产品也相继问世。从此w m n 迈入了飞速发展时期，同时也为移动 a d h o c 网络的发展注入了新的活力。其中，摩托罗拉公司甚为看好m e s h n e t w o r k s 公司 的发展，并于2 0 0 5 年成功将其收于麾下【l7 】。 从2 0 0 4 年到现在，w m n 在新加坡、费城、旧金山、新奥尔良等国家和地区已经 进行了大规模的商用部署，不仅建设了覆盖整个城市的无线网络，而且提供了无线宽带、 公共安全和市政管理等功能。t e l a b r i a 公司在英国k e n t 州建立的w m n 利用双载波实现 与8 0 2 1 1 兼容【1 8 】，完成家庭和办公地点的室内外覆盖；诸多大学也通过w m n 覆盖校 园。r i c e 大学的w m n 成功部署经验促进了休斯敦t x 的全能网络技术( t e c h n o l o g yf o r a l l ，t f a ) 1 9 】计划的实施，该计划目的在于为低收入人群提供无线网络连接，消除数字 鸿沟。另外，伦敦、洛杉矶等城市也部署了城域w i f im e s h 网络。 2 0 0 6 年，无线m e s h 网络才在中国内地城市中出现，在北京市的公共安全覆盖、后 海酒吧街区的室外无线覆盖和天津滨海新区的数字港口建设等方面均有了相关的应用。 一旦天津滨海开发区的覆盖计划完成，将会实现2 0 0 多个监控点，覆盖超过3 0 平方公 里的无线视频监控1 2 。2 0 0 8 年9 月份，国内唯一的专业m e s h 设备厂商上海寰创通 哈尔滨t 程大学硕七学位论文 信科技有限公司g b c o m 在与欧美众多一线厂家的激烈竞争中取得胜利，成功中标蛇口 集装箱码头的无线覆盖一期项目【2 l 】。 目前在国内，北电m e s h 网络已经为不少单位解决了区域覆盖，典型的案例如下【2 2 】： 1 、暨南大学校园网 暨南大学的校园本部用北电m e s h 网络实现了校园的全覆盖，采取的是以室外a p 向室内覆盖为主，而室内a p 为辅的设计方案。全网分为两期工程进行建设，一期工程 配置3 0 多个a p ，主要是覆盖科学馆( 包括国际会议厅) 、新行政办公大楼、理工大楼 ( 包括南海楼) 、校友楼、生物学院大楼、老医学院大楼、文学院大楼、学生食堂饭厅、 新医学院大楼等。二期工程增加2 0 多个a p ，覆盖了校本部绝大部分地区，学校师生可 以通过该网络在校园的任何地方实现网络的访问和无缝漫游。 2 、广东电信无线机动大队 广东电信无线机动大队的主要任务是负责广东电信的无线应急通信和无线网络评 估等重要无线通信的保障工作。针对各个影剧院、运动场馆等公共场所的无线通信需求， 该大队特意准备了两辆应急通信工程车，每台通信车上安装一套北电无线m e s h 网络系 统，每个网络系统包含3 个阿络接入点n a p ，通过无线中继方式，将网络延伸至体育馆 和其它公共场所内，在公共场所内，搁置s t a n da l o n ea p ，通过与n a p 建立无线中继实 现公共场所的无线接入覆盖。 3 、汕尾市供电局 汕尾市供电局采用北电m e s h 网络实现移动办公需求，公司员工可以通过w i f i 无线网络在公司的任何地方连接到公司网络并实现i n t e m e t 访问，且能够实现a p 与a p 之间的无缝漫游，为员工更好的展开工作提供了方便。 此外，由于在边远农村特别是在西部农村建设有线的通信设施，经济效益不明显。 投入高、运营费用高、收入低是目前影响通信运营商加大对农村通信网络建设投资的最 大障碍，投入的成本问题己成为制约信息化建设的主要因素。基于此，我国教育部提出 了科技创新工程重大培育基金项目“基于i e e e8 0 2 1 1 的低成本边远乡村远程宽带无线 m e s h 接入网络技术【2 3 】 ，针对边远农村地域广阔，村落距离远的特点，提出一种基于 8 0 2 1 1 标准的低成本远程宽带无线m e s h 接入网解决方案。在现存较为成熟的、价格低 廉的8 0 2 1 1 设备和低廉的全向、定向天线的基础之上，解决长距离传输的关键问题，利 用自主研发的网络设备以及网络协议搭建接入网络，为用户提供高性能低成本的、灵活 的宽带接入服务。此项目已于2 0 0 8 年启动，计划将于2 0 11 年完成。远程宽带无线m e s h 接入解决方案如图1 3 所示。 4 第1 章绪论 bq 图1 4 中国无线m e s h 市场规模发展 1 2 2 o o s 路由算法的国内外研究现状 2 c r l l f 当前，有关w m n 中q o s 保障的研究不断出现。从丌放式系统互联的参考模型( o s i 一 一r k 一防。乳噌 0 0 0 0 0 0 0 0 0 0 0 善加加加 哈尔滨t 程大学硕十学位论文 r m ) 角度看，相关的研究主要集中于下三层( 物理层、数据链路层、网络层) 以及 跨层设计；而在上三层( 会话层、表示层、应用层) 主要涉及它们所支持的相关应用， 例如i n t e m e t 接入、多媒体业务等等；在传输层，通常采用传输控制协议( t c p ) 、用 户数据报协议( u d p ) 以及它们的改进形式等。显然，上述协议层的研究并不是q o s 保障的关键。w m n 网络层的研究主要集中在路由协议上，因此又称之为路由协议层， 其采用的协议是互联网协议( i p ) ；对于数据链路层的研究主要集中在媒体接入控制子 层( m a c ) ，却较少考虑链路控制子层，因而被简化成m a c 层；而物理层的研究集中 于o f d m 、m i m o 、智能天线等先进的物理层技术。 路由层利用路由协议寻找从源节点到目的节点之间的路由、并建立路由从而实现无 线网络节点之间的相互通信，其研究内容分为路由协议和路由算法两大内容。与有线网 络、蜂窝网络以及w l a n 不同，由于w m n 具有无线多跳和无中心控制的特性使得其 中的每一个节点都应当具有独立发现路由以及转发分组的能力，因此需要研究专门适用 于w m n 的路由协议和算法。基于此，以w m n 的应用为背景的路由协议和算法相继被 开发出来。 现有的大部分路由协议一般都侧重在网络中寻找一条最短路径或次短路径，在拓扑 结构状态发生变化时进行路由维护，以至于提供尽力而为的数据业务，这些路由协议并 不一定能够满足语音和视频等多媒体业务对q o s 保障的要求。因此对于上述的路由协议 有必要引入新的q o s 保障路由协议和算法。事实上，路由层的q o s 保障研究是各协议 层中受到的关注最多的，也是最为重要的一个领域。 目前涌现出来的w m n 中的q o s 路由算法主要分为：基于时延的q o s 路由，基于 吞吐量的q o s 路由，基于丢包率的q o s 路由等。下面分别做以简单介绍。 1 基于吞吐量的q o s 路由算法是寻找端到端之间吞吐量较高的路由。文献 2 4 1 选取 期望传输次数e t x 作d s r 和d s d v 的路由选择判据，从而获得吞吐量较高的路径。文献 2 5 提出了一种针对w m n 的高吞吐量路由协议s r c r r ，用自适应传输速率控制算法和快 速获取链路丢包率机制，大大提高了所选路由的性能。 2 基于时延的q o s 路由算法是寻找端到端之间时延较低的路由。文献【2 6 】在d s r 路 由协议基础上，以累积处理的总延时作为路由选择判据，从而获取时延较低特性的路由。 文献 2 7 贝j j 提出了一种基于时延的按需q o s 路由协议，此协议考虑节点的m a c 层竞争信 息来估计竞争时延，并且考虑节点的接口队列长度来估计队列的时延，从而为实时业务 选择具有时延保障的路由。当w m n 不同边缘子网的节点之间通过m e s h 路由器进行通信 时，如果由于节点移动导致从当前的m e s h 路由器切换到别的m e s h 路由器，则需要重新 6 第1 章绪论 寻找路由，因而产生了不必要的延时。因此为了避免上述延时，文献 2 8 1 中提出了预切 换路由发现算法。 3 基于丢包率的q o s 路由算法是寻找端到端之间丢包率较低的路由。由于w m n 的 时变特性，有可能导致无线信道的平均丢包率较低而即时丢包率却很高。此时，若将平 均丢包率作为路由判据显然不合理。因此文献 2 9 1 将修正的期望传输次数m e t x 以及有 效传输次数e n t 作路由判据，从而能够在无线信道条件恶劣的情况下选择即时丢包率和 平均丢包率均较低的路由。 总体来说，在w m n 的路由层q o s 保障研究领域涌现出了大量的算法，但是由于 w m n 的动态特性，单一的q o s 路由判据也许不能满足业务上的需求。因此在某些应用 中，要选择同时满足多个q o s 指标约束的路由【3 0 - 3 2 。然而，这类多判据的q o s 路由算 法过于复杂，是典型的n p 完全问题，因此，设计在复杂度和性能上折衷的良好多判据 路由算法具有非常重要的实际意义，也即是本文的主要研究内容。 1 3 本文主要研究内容和章节安排 本文主要研究w m n 中具有多个q o s 约束条件的路由算法，该问题已被证明了是 一个n p c o m p l e t e 问题。针对这一问题的求解，现今并没有很有效的近似算法，一般采 用启发式算法求解。本文首先对目前存在q o s 单播路由算法的缺点进行了有效的分析和 总结，并将免疫算法引入到q o s 单播路由算法求解中，目的在于准确找到全局最优解， 并提高运算速度。然后，又对更为复杂的q o s 多播路由算法进行了研究和分析，提出了 基于混合蚁群算法的q o s 多播路由算法，实现了控制参数的自动调整，并获得了比一般 算法更优的多播树路径以及更快的收敛速度。 本文的具体内容安排如下： 第1 章为绪论。首先介绍了课题研究的背景及目的意义，然后介绍了无线m e s h 网 络、q o s 路由算法的国内外发展现状，最后简要介绍本文的主要研究工作和内容安排。 第2 章，首先介绍了无线m e s h 网络的结构、特点等基本概念以及几个关键技术； 然后说明了无线m e s h 网络的标准及协议和路由算法；接着对a o d v j r 路由算法的原理 进行了介绍，最后又对改进的基于捎带技术的a o d v j r 路由算法的过程进行了分析。 第3 章，介绍免疫遗传算法的思想、原理以及将免疫遗传算法应用到w m n 的q o s 单播路由的实现过程，并分别对三种不同规模的网络进行了仿真实验，且与现有的最好 方法做了对比，实验结果表明，本章提出的算法不容易限于局部最优的缺陷，而且能有 效提高寻找最优路径的速度，尤其在网络规模增大时，更能体现算法的优越性。 7 哈尔滨t 程大学硕士学位论文 第4 章，介绍了混合蚁群算法的思想、原理以及将混合蚁群算法应用到w m n 的 q o s 多播路由的实现过程，并进行了仿真实验，且与现有的最好方法做了对比，实验结 果表明，本章提出的算法实现了控制参数的自动调整，并获得了比一般算法更优的多播 树路径以及更快的收敛速度。 最后本文将对一年来在无线m e s h 网络q o s 路由算法研究过程中所做的工作进行总 结归纳，并对其不足和今后的发展进行展望。 8 第2 章课题相关理论知识 第2 章课题相关理论知识 2 1无线m e s h 网络的结构及特点 z 1 1m e s h 概念 在m e s h 结构网中，所有节点之间相互连接。这种连接方式称为全网状结构( f u l l m e s h ) ，如图2 1 所示。此结构中的每个节点到其它各节点均有一个直接链接，形成一 个非常有用的排列。但随着节点数量的增加，节点间的链接数量变得与实际不符。链接 的数量( l ) f l - i 节点的数量( n ) 决定，表示二者关系的公式如下：l = n f n 一1 ) 2 。 图2 1 f u l lm e s h 结构图 一 由上述的公式可知，连接2 0 台电脑就需要1 9 0 个链接，这简直就是配线工作和硬 件的噩梦。所以，实际应用的网络通常采用总线拓扑、星形拓扑、环形拓扑以及其它网 络拓扑，和一些接入方式减少节点间相互链接的数量。目前，互联网是唯一被广泛应用 的有线m e s h 网络。 无线化使得m e s h 网变得既可用又便宜。另外，部分网状结构( p a r t i a lm e s h ) 具备全 网状结构的基本优点，结构如图2 2 所示。 图2 2 p a r t i a lm e s h 无线链接图 9 哈尔滨t 程大学硕十学位论文 在部分网状结构中，不是所有的节点都与另外的各个节点相连，只需要有足够的链 接，就可获得令人意想不到的好处。部分网状结构最大的好处就是每个节点的覆盖范围 扩大了几倍。大多数短距离无线技术均有一个典型的最大覆盖范围：l o 米或更短。然而 部分网状结构却没有最大通信距离的限制，这是因为其所有节点都可被用作路由器或中 继器，信号可以从一个节点传送至另一个节点，使覆盖范围无限地扩大。 2 1 2 无线m e s h 网络的结构 无线m e s h 网络是与传统无线网络完全不同的一种网络。传统的无线接入技术主要 采用点到点或点到多点的拓扑结构。这类拓扑结构一般都存在一个中心节点，如移动通 信系统的基站、8 0 2 1 1 无线局域网的接入点( a p ) 等。中心节点与各个无线终端之间通过 单跳的无线链路相连接，控制着各无线终端访问无线网络，用户之间如果要进行相互通 信，首先必须访问一个固定的接入点( a p ) ，然后通过有线链路完成与有线骨干网的连接。 在无线m e s h 网络中，采用一种多点到多点的网状m e s h 拓扑结构。各网络节点通 过与之相邻的其它节点，以无线多跳形式相连。在此m e s h 网络结构中，任何一个无线 设备节点均可同时作为路由器和a p ，网络中的任一节点都可以发送和接收信号，且每 个节点都可与一个或多个对等节点直接进行通信。这种结构最大的好处在于：如果最近 的a p 因流量过大而导致拥塞，那么数据包可以重新路由到一个通信流量相对较小的邻 近节点进行传送。依此类推，数据包还可根据网络的情况，继续选择与之最近的下一个 节点进行路由传输，直到达到最终目的地为止，此种访问方式即为多跳访问。例如在图 2 2 的网络中，节点a 要传送数据到节点l 可以通过以下的路径：a d g m l ，另一替 代路径为：a bhf l ，还存在其它多条冗余的路径。首先把要传输的数据放在一个数 据包里，然后数据包从一个节点“跳跃至另外一个节点，直到到达目的地为止。 在无线m e s h 网络中包括两种类型的节点：无线m e s h 路由器节点和无线m e s h 客户 端节点。w m n 的系统结构按照节点功能的不同可分为三类：骨干网m e s h 结构、客户 端m e s h 结构和混合结构【3 3 】。混合结构的无线m e s h 网络如图2 3 所示，其中虚线表示 无线连接，实线表示有线连接。 1 0 第2 章课题相关理论知识 因特网 w i - f i l b 机m c s b 终端 i 一：j j ：_ i l 线近：嵌 ! = = ! = = ! 塑丝一j 幽2 3 混台绌构无线m e s h 刚络 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 网络互连的功能，能够通过无线多跳通信，以较低的发射功率获 得同样大的无线覆盖范围。 2 客户端m e s h 结构 客户端m e s h 结构是由m e s h 客户端之问互连构成的一个小型对等通信网络，为用 户设备之间提供点到点的服务。无线m e s h 网络的用户终端可以是手机、笔记本电脑、 p d a 等安装有无线网卡和天线的用户设备。m e s h 客户端结构实质上是一个a dh o e 网络， 能够在没有现存的网络基础设施情况下提供一种较为可靠的通信支撑。 3 混合结构 m e s h 客户端通过m e s h 路由器接入m e s h 骨干网络就形成了m e s h 网络的混合结构， 混合结构能够提供与其它一些网络结构的连接，例如因特网、w i m a x 、w l a n 、蜂窝和 传感器网络。这种结构可以利用客户端的路由功能增加无线m e s h 网络的连接性、扩大 网络的覆盖范围。 哈尔滨1 ：程大学硕十学位论文 2 1 3无线m e s h 网络的特点 无线m e s h 网络拥有诸多其它网络不可比拟的优势，可以应用到各种场合中，例如 宽带家庭网、企业网络、社区网络、城域网络、楼宇自动化、交通系统、健康医疗系统、 灾难应急网络、安全监控系统、端到端通信等等【3 4 j 。无线m e s h 网络的主要优势体现在 ， 以下几个方面： ， 1 安装简单和快速部署。安装m e s h 节点非常简单，若要添加新的设备，只需简单 的接上电源即可。由于安装非常简单，用户可以通过随意增加新的节点来扩展无线网络 的覆盖范围。在无线m e s h 网络中，不是所有的m e s h 节点都需用有线电缆连接，这是 它与有线网络a p 最大的不同。w m n 的设计目标就是要将有线设备与有线a p 的数量 降到最少，如此大大降低安装时间和总拥有成本，这样的设计带来的成本节省是非常可 观的。w m n 的配置和其它网管功能与传统的w l a n 相同，用户可以将使用w l a n 的 经验很容易的移植到m e s h 网络上。 2 非视距传输( n l o s ) 。利用无线m e s h 网络技术很容易实现n l o s 的配置，因 此在室外以及公共场所应用前景广泛。与发射台之间存在直接视距的用户先接收无线信 号，再将接收到的无线信号转发给与发射台之间无直接视距的用户。信号按照这种方式 能够自动选择最佳路由，从一个用户跳转到另一用户，直到无直接视距的目标用户。如 此，具有直接视距的用户就为无直接视距的相邻用户提供了无线宽带接入功能。w m n 的非视距传输特性极大的扩展了无线宽带的覆盖范围和应用领域。 3 可靠性。如果一条路径由于信号通道阻塞、节点失效或者多重路径衰减失败了， 信号还能找到另外一条或多条替代路径。若某个节点的电池没电了，节点会从网络中退 出，其它节点能经过可供选择的跳跃来转发数据。m e s h 网络不依赖于某个单一节点的 性能，因此比单跳网络更健壮。如果单跳网络的某一个节点出现故障，那么整个网络也 就随之瘫痪了；而在m e s h 结构网络中，每个节点都有一条或多条传输数据的路径，若 最近的节点受到干扰或者出现故障，数据包会自动路由到备选路径继续进行传输，因此 不会影响整个网络的正常运行。 4 结构灵活。在单跳结构的网络中，设备之间必须共享a p 。如果几个设备同时访 问网络，就可能会产生通信拥塞而导致系统的运行速度降低。但在多跳结构的网络中， 多个设备可以经过不同的节点同时访问网络，因此不会导致网络性能的降低。 5 负载平衡。m e s h 网络提供了更大的通信负载平衡功能和冗余机制。在无线m e s h 网络中，每个设备都有多条可用的传输路径，网络可根据每个节点的通信负载情况动态 1 2 第2 章课题相关理论知识 的分配路由，因此，有效地避免了节点的通信拥塞问题。然而目前的单跳网络并不能动 态处理通信干扰及接入点的超负荷问题。 6 高带宽。无线通信的特性决定了无线通信传输距离越短越容易获得高带宽，这 是因为随着传输距离的增加，各种通信干扰和其它一些导致数据丢失的因素会随之增 加。因此，选择经过多个短跳的方式传输数据是获得高带宽一种很有效的方法，这也正 是无线m e s h 网络的优势所在。在无线m e s h 网络中，一个节点不仅能发送和接收信息， 而且还能充当路由器转发其附近节点的信息，随着更多节点之间的相互连接，可供选择 的路径数量增加，总的带宽也大大增加。 7 节能特性。由于每个短跳的传输距离短，因此传输数据所需的功率也较小，并 且一些节点还可以用电池运行。因为节点以脉冲形式传送数据包，这些节点也许会处于 睡眠状态，引起的电流只有微安培，仅在要发送信息或要转接信号时才会醒过来，大大 地减少了功率损耗。电池寿命可长达数月甚至数年，无需经常维护。由于多跳网络通常 使用较低的功率把数据传输给邻近的节点，因此节点问的无线信号干扰也比较小，网络 的信道质量以及信道利用效率大大提高，因此可以实现更高的网络容量。例如在高密度 的城市网络中，删能够使得无线网络的相邻用户间的干扰大大减少，从而提高信道 的利用率。 ： 无线m e s h 网络具有白组织、自均衡、自愈合等诸多优点，但同时也存在着缺陷， 主要是安全问题。如果没有得到适当的保护，删会被黑客入侵和盗取。因此需要用 加密的方法实现保护，例如高级加密系统( a e s ) 1 3 5 】。 对某些应用来说，无线m e s h 网络的另一个缺点就是延时。睡眠节点要花费一定的 时间苏醒过来才能传递数据。并且，每一次跳跃转发也需要耗费一定的时间，因此节点 间的延时总和可达5 3 0 毫秒。对于某些有决定性作用的工业控制应用而言，这样的速 度也许不能满足要求。然而，在很多情况下，这样的延时不是制约性问题。 2 1 4 无线m e s h 网络的关键技术 设计无线m e s h 网络不仅需要考虑多址接入控制、天线设计等无线传输问题，而且还 需考虑网络层的各种功能实现以及上下层功能之间的相互影响，这使得w m n 的设计过 程要远比传统的无线接入网络更复杂。w m n 需要解决的几个关键技术问题如下： 1 多址接入控制技术问题 正交分割多址接入技术( q d m a ) 是m e s hn e t w o r k s 公司专为广域范围通信最优化及 移动m e s h 网络系统设计的一项专利技术。q d m a 使用的调制技术是直接序列扩频调制。 哈尔滨t 程大学硕十学位论文 由于q d m a 在m a c 子层采用多信道方式( 一个控制信道和三个数据信道) ，因此，与单信 道方式相比更适用于高密度的w m n 终端设备。q d m a 可以在较大的移动通信范围内提 供较强的纠错能力，同时提高了信号灵敏度，增强了抗干扰能力，在高速移动环境下能 提供高达6 m b p s 的峰值数据传输速率。 w m n 的物理层可以采用正交频分复用( o f d m ) 技术，将高速数据流经过串并变 换，分配到传输速率较低的若干个正交子信道中，然后在各个子信道进行窄带调制和传 输。o f d m 技术结合分集、时空编码、信道间干扰抑制及智能天线技术等，可最大程度 的提高系统性能，使w m n 的性能得到进一步优化。 2 天线技术问题 w m n 中的天线设计对于整个系统的性能影响重大。由于w m n 中每个节点需要和各 个方向上多个节点进行通信，因此采用全向天线是一种最简单的方案。这种方案能简化 系统的安装和使用，但由于多个用户节点共享同一信道，干扰现象严重，致使系统的频 谱效率大大降低，网络容量减小。另一种方案是使用定向天线，用户节点间通过点到点 的连接方式，降低所需的发射功率，同时减小路径之间的同频干扰，实现很高的频谱效 率。但仍存在几个其它方面的问题，如每个用户节点需多个定向天线，以保持与相邻节 ：点的连接，这样，单个用户节点的成本也相应增加；采用定向天线时，任意两点间都需 要精确对准，以保证天线的增益，如此则增加了安装的难度；当某节点加入或退出网络 导致网络的拓扑结构发生变化时，需要重新调整定向天线，即增加了使用难度。另外， 在一个w m n 中混合使用这几种天线也是一种有效的方案，比如在网络的边缘节点采用 定向天线，在网络的内部节点采用区域天线全向天线。 一种更合适的方案是使用智能天线技术，能够提高系统性能，简化其安装和使用。 采用智能天线技术，用户节点能够根据周围节点的状态，利用软件控制调整波束方向， 使其分别对应多个相邻节点，起空分复用的作用，提高系统容量。此外，当系统工作在 低频段时，采用智能天线还可增强系统抗多径衰落和抗频率性衰落的能力。最后，当网 络结构发生变化时，能够通过自动调整波束方向重新建立用户节点间的联系。 3 管理技术和信道资源分配问题 无线宽带接入系统频谱资源有限，因而必须使信道资源尽可能地被用户使用。i e e e 8 0 2 1 6 a 标准规定，基于w m n 的宽带接入网络带宽分配方式可以采用集中式调度或分布 式调度。若采用集中调度方式，就由m e s h 路由器( m r ) 收集所有m e s h 终端的资源请求 信息，并分别分配一定数量的带宽资源；若采用分布调度方式，网络所有节点的信道资 源需要相互协调，实现带宽的动态分配。 1 4 第2 章课题相芙理论知识 j i 宣i 宣i 暑i ；i 置i 宣i i i 萱量置膏薯暑暑皇置置i i i 毒i i 暑宣i i 置宣i i i i 宣i i i i i - i ni ii i | |i i 薯置；i j i i i i 葺宣i 置 由于w m n 采用的是无线传输媒质，所以它不可避免的存在隐藏终端和暴露终端的 问题。由此专门设计了请求发送允许发送协议( r t s c t s 协议) ，然而尽管通过握手机制 可减少隐藏终端问题数据报文冲突的概率，但节点问控制报文的冲突依然存在，且不能 解决暴露终端问题。w m n 本质是种特殊的a dh o e 网络，可根据a dh o e 网络中的一些 成熟方案解决这两个问题。 一c 4 路由选择问题 、 w m n 是多跳网络，具有动态拓扑特点，因此路由算法应具有一定的健壮性：一方 面可以快速同步于网络拓扑的变化，且适应网络规模的不断扩大；另一方面，当某个节 点或某条路径发生故障，能够通过一个快速的恢复过程重新寻找到路由。在任意的源节 点和目的节点间可能存在多条路径，因此选择哪条路径就成为一个关键问题，将直接影 响系统的性能。此外，由于w m n 直接面向用户节点，当所有的用户同时访问一个热点 资源时，例如视频点播，网络中会产生大量的冗余业务量，从而发生拥塞，因此w m n 中的路由技术还需能支持组播功能。 评价w m n 网络层的路由协议的性能，应该综合考虑多个指标，最终达到网络全局 性能的最优化。比如，衡量成簇的分级路出协议，需要考虑成簇复杂性以及不够灵活的 缺点；再如，衡量地理路由协议需g p s 或者定位系统的辅助，这样也会增加路由协议的 复杂度和代价。所以，需建立综合性能指标进行衡量。 从设计路由协议与m a c 协议联合来考虑，在网络层引入m a c 层的性能指标是一种 非常有效的办法。另外，鉴于m a c 和网络层的紧密联系，不单交换两者信息，将两者的 功能整合则是更有f i 途的方法。 除了上述几个关键技术外，w m n 中还需要解决一些商用化的问题，比如，如何识 别新加入的用户节点身份并且对空中传输用户的数据进行加密，来保证w m n 的安全性； 如何提供简单的界面对全网进行管理( 配置、计费、监控等) ；在使用同一频段时，w m n 如何与其它系统( 如无线局域网络、点到多点的固定宽带无线接入网络等) 共存。 当前的研究成果表明，基于现有技术构建的w m n 的性能与理论值有一定的差距， 还有很多问题急待解决。基于目前路由协议、m a c 协议和传输协议的w m n 无法随节点 数目以及多跳数目的变化而灵活调整，因此性能较为低下。采用高速射频技术或多天线 多信道技术能够提高网络的容量，在一定程度上可以减轻以上问题，但并不会提高资源 利用率，无法真正增强w m n 的灵活性。所以，为获得灵活性，必须为w m n 设计全新的 路由协议、m a c 协议和传输协议。 哈尔滨t 程大学硕十学位论文 2 2 无线m e s h 网络的路由协议及算法介绍 随着无线m e s h 网络的应用范围越来越广泛，制定出相关的标准已经成为迫切需要。 目前的国际标准化组织，尤其是i e e e 正在致力于无线m e s h 网络的标准化研究工作。目 前，在i e e e8 0 2 1 l s 、8 0 2 1 5 、8 0 2 1 6 d e 以及8 0 2 2 0 等标准中均对m e s h 组网技术做出了规 范1 3 6 1 ，在网络的第二协议层中完成接入控制、链路拥塞控制、网状组网、路由、切换支 持、快速移动和安全认证等功能。现在的w m n 主要采用基于8 0 2 1 l a b g 的标准及 8 0 2 15 。4l 掏z i g b e e 协议m 。 z i g b e e 协议是运行在基于i e e e8 0 2 1 5 4 标准的m a c 层和物理层以上的高层协议，它 明确定义了网络层的三种拓扑结构：簇型、星型和m e s h 结构。其中，在m e s h 网络结构 中，所有的无线节点都相同，它们之间可以直接相互通信，每次网络都会选择一条或多 条路径进行多跳传输，将所要传送的数据传输到中心节点，如图2 4 所示。m e s h 结构的 每个节点都有多条到达中心节点的路径，因此容故障能力较强；同时，这种多跳结构的 系统以多跳形式代替了单跳的远距离传输，降低了源节点所需要的发射功率。 图2 4z i g b e e 协议中的m e s h 结构 2 2 1 a o d v j r 路由算法 w m n 网络层的基本路由协议按照发现路由的驱动方式大体可将这些路由协议