（计算机应用技术专业论文）基于蚁群优化的多网关wmn多路径选播路由算法研究.pdf

7j 舢删j 舢m 删舢f f j f 舢舢 | y 1 7 3 9 0 。2 “。9 。”。 广西大学学位论文原创性声明和学位论文使用授权说明 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果和相 关知识产权属广西大学所有。除已注明部分外，论文中不包含其他人已经发表过的研究 成果，也不包含本人为获得其它学位而使用过的内容。对本文的研究工作提供过重要帮 助的个人和集体，均已在论文中明确说明并致谢。 论文作者签名： 嗜 学位论文使用授权说明 矽如年占月叫日 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 本人保证不以其它单位为第一署名单位发表或使用本论文的研究内容； 按照学校要求提交学位论文的印刷本和电子版本； 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： 曲即时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 论文作者签名： 髻上、 导师签名： 弘辟多月列日 基于蚁群优化的多网关w m n 多路径选播路由算法研究 摘要 无线网状网( w m n ，w i r e l e s sm e s hn e t w o r k ) 作为下一代无线网络的 关键技术，近年来得到了快速的发展与应用。w m n 融合了移动自组网络 ( m a n e t ，m o b i l ea dh o en e t w o r k ) 和无线局域网络( w l a n ，w i r e l e s s l o c a la r e an e t w o r k ) 的特点，作为一种新型的无线宽带接入技术，主要是 为底层终端用户提供因特网接入服务，其显著特点是业务汇聚于m e s h 路由 器网关，容易造成局部网络拥塞，网关往往会成为制约整个网络性能的瓶 颈，可通过设置多个网关以缓解瓶颈问题，而通信过程中如何在这样的多 网关w m n 中选取一个合适的网关节点来接入因特网就成为提高w m n 性 能的关键问题之一，可以将这种网关选择看成是一种典型的网络选播服务。 蚁群算法具有自发建立、自动布置和任意移动的特性，适用于无线网络， 可以应用到w m n 以优化其路由选择。本文根据蚂蚁寻径与选播路由的相 似性，将源地址与目标地址分别作为蚁巢和食物，相同选播目标地址的多 个w m n 网关可以作为位置分散的多个食物，将选播路由问题看作是一只 蚂蚁寻找蚁巢与食物之间最优路径的问题。 本文对w m n 路由与移动自组网选播路由研究现状进行了阐述，分析 了几种典型w m n 结构及其特点，并详细给出了在w m n 路由协议设计中 应该考虑的一些因素以及研究思路和方向。基于以上研究构建了基于选播 和跨层设计的多路径w m n 网关选取模型，在分析了按需多路径距离矢量 路由协议( a o m d v ，a dh o eo n d e m a n dm u l t i p a t hd i s t a n c ev e c t o r ) 优势的 基础上，考虑其以最小跳数为路由准则的不足，结合蚁群算法和w m n 特 点，对a o m d v 协议进行了扩展，首先提出了一种基于蚁群优化的w m n 多路径路由协议( a a o m d v ) ，该协议能建立多条到目的节点的有效路由， 根据网络状况更新路由，选路时能避开拥塞区域，选择负载轻，跳数小的 路径，然后在此基础上结合选播机制提出了一种基于蚁群优化的多网关 w m n 多路径选播路由协议( m m a m b a ) 。仿真结果表明，m m a m b a 可 根据蚂蚁收集的网络信息用参数优化方法白适应解决多网关w m n 的选播 问题，有效提高w m n 接入因特网的性能。 关键词：多路径多网关蚁群算法无线m e s h 网络选播路由 m e s hr o u t e r so rg a t e w a y , s ol o c a lc o n g e s t i o nm a yo c c u ra n dt h eg a t e w a yo f t e n b e c o m et h eb o t t l e n e c ko ft h en e t w o r k b o t t l e n e c kc a nb er e l i e v e db yi n c r e a s i n g g a t e w a y s ，b u th o w t os e l e c ta na p p r o p r i a t eg a t e w a yn o d et oa c c e s st h ei n t e m e t i nt h ec o u r s eo fc o m m u n i c a t i o ni ns u c ham u l t i g a t e w a yv v 2 v i nh a sb e c o m eo n e o fk e yi s s u e st oi m p r o v et h ep e r f o r m a n c eo fw m n i nf a c t ，t h i ss e l e c t i o nf o r g a t e w a y c a nb ec o n s i d e r e da sat y p i c a ln e t w o r ka n y c a s ts e r v i c e s a n tc o l o n y a l g o r i t h mh a sf e a t u r e so fs e l f - b u i l d ，a u t o m a t i cl a y o u ta n da n ym o v i n g ，a n di ti s s u i t a b l ef o rw i r e l e s sn e t w o r k ，s oi tc a nb ea p p l i e dt ot h ew m nf o ro p t i m i z i n gi t s r o u t i n g b a s e do nt h es i m i l a r i t yo fa n tr o u t i n ga n da n y c a s tr o u t i n g ，t h i sa r t i c l e t r e a t st h es o u r c ea d d r e s sa n dd e s t i n a t i o na d d r e s sa sn e s t sa n df o o d ，a n dr e g a r d s t h em u l t i p l eg a t e w a y sw i t ht h es a m ea n y c a s td e s t i n a t i o na d d r e s sa sn u m e r o u s i - f o o di ns c a t t e r e dl o c a t i o n s ，s oa n y c a s tr o u t i n gp r o b l e mc a nb es e e na st h a ta l l a n tf i n d i n gt h eo p t i m a lp a t hb e t w e e nn e s ta n df o o di s s u e s i nt h i st h e s i s ，w m nr o u t i n ga n da n y c a s tr o u t i n gi nm a n e tr e s e a r c hh a s b e e ns u r v e y e di nd e t a i l ，s t r u c t u r ea n dc h a r a c t e r i s t i c so ft y p i c a lw l v i na r ea l s o a n a l y z e d ，s o m er e s e a r c hi d e a sa n dd i r e c t i o n sw h i c hs h o u l db ec o n s i d e r e di nt h e d e s i g no fs o m ef a c t o r so f ，m nm u t i n gp r o t o c o l sa r ep r e s e n t e di nv i e wo f a b o v es t u d y , w m ng a t e w a ys e l e c t i o nm o d e lw a sc o n s t r u c t e db a s e do na n y c a s t a n dc r o s s - l a y e rd e s i g no f m u l t i p a t h a f t e ra n a l y z i n gt h ea d v a n t a g e so fa o m d v p r o t o c o l ，c o n s i d e r i n gi t ss h o r t a g eo fr o u t i n gg u i d e l i n e sw i t hm i n i m u mh o p ， c o m b i n i n gw i t hc h a r a c t e r i s t i c so fa n tc o l o n ya l g o r i t h ma n dw m n ，t h ea o m d v p r o t o c o lh a sb e e ne x t e n d e d f i r s t l y , aw m nm u l t i - p a t hr o u t i n gp r o t o c o lb a s e d o na n tc o l o n yo p t i m i z a t i o n ( a - a o m d v ) w a sp r o p o s e d ，w h i c hc a nf i n da n u m b e ro fe f f e c t i v er o u t i n g ，u p d a t em u t i n gb a s e do nn e t w o r kc o n d i t i o n s ，a v o i d c o n g e s t e da r e a s ，c h o o s et h el o a dl i g h t ，s m a l lh o p sp a t h ，o nt h i sf o u n d a t i o n ，a n a n y c a s tm e c h a n i s mw a sp r e s e n t e db a s e d o na n t c o l o n yo p t i m i z a t i o no f m u l t i - g a t e w a yw m nm u l t i - p a t ha n y c a s tr o u t i n gp r o t o c o l ( m m a m b a ) t h e s i m u l a t i o nr e s u l t ss h o wt h a tt h ea n y c a s to fm u l t i g a t e w a yw m ni ss o l v e d a d a p t i v e l yt h r o u g hm m a m b ab yu s i n gt h ep a r a m e t e ro p t i m i z a t i o nb a s e do n t h en e t w o r ki n f o r m a t i o nc o l l e c t e db ya n t s ，t h ea c c e s s i n gp e r f o r m a n c e so fw m n a r ei m p r o v e de f f e c t i v e l y k e y w o r d s ：m u l t i - p a t h ；m u l t i - - g a t e w a y ；a n tc o l o n ya l g o r i t h m ；w m n ； a n y c a s tr o u t i n g 目录 摘要i a b s t r a c t i i i 目录v 第一章绪论。1 1 1 课题研究的背景及意义1 1 1 1 课题研究的背景1 1 1 2 论文选题的目的和意义2 1 2 课题的国内外研究现状3 1 2 1w m n 网络路由研究3 1 2 2 移动自组网选播路由研究现状5 1 3 本文的研究内容和主要创新点6 1 3 1 本文的研究内容6 1 3 2 本文的主要创新点6 1 4 本文的组织结构7 第二章无线m e s h 网络路由技术8 2 1 无线m e s h 网络的网络结构与特点8 2 2 无线m e s h 网络路由技术分析1 l 2 2 1w m n 路由协议设计要求1 1 2 2 2w m n 路由协议研究方向与趋势13 2 3 小结一1 7 第三章基于蚁群优化的w m n 多路径路由1 8 3 1 蚁群算法简介18 3 2a o m d v 协议2 0 3 3a a o m d v 算法设计2 1 3 3 1 扩展a o m d v 2 l 3 3 2 主要规则2 2 3 3 3 算法描述2 3 3 4a a o m d v 协议仿真与性能分析2 5 3 4 1 仿真场景与参数设置2 5 3 4 2 仿真结果与分析2 5 3 5 小结。2 7 第四章基于蚁群优化的多网关w m n 多路径选播路由2 8 4 1 多路径w m n 网关选取优化模型2 8 4 2 基于蚁群优化的多网关w m n 选播路由算法的研究2 9 4 2 1m m a m b a 算法设计的基本思想2 9 4 2 2 三个主要规则3 0 4 2 3 扩展a o m d v 。3 2 4 2 4 算法描述3 4 4 3 m m a m b a 算法的仿真与性能分析3 7 4 3 1 仿真场景与参数设置3 7 4 3 2 仿真结果与分析3 9 4 1 4 2 4 2 4 3 4 4 4 9 5 0 5 0 基于蚁群优化的多网关1 】l l 心多膜吒毫选播路由：算法研究 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 l a n ) 、移动自组刚l 】( m o b i l ea dh o en e t w o r k ，m a n e t ) 等技术在其发展应用过程中局限性日益体现，无线m e s h 网络正是在 这种需求下被推出的，作为一种结合m a n e t 和w l a n 技术优势的新型网络结构形态， 具有自配置、自组织和自愈等特点，有很强的扩展性，可以与其他异构网络相结合，能 方便快捷低成本地扩展无线接入系统的覆盖率，同时可以提高无线系统的带宽容量以及 通信可靠性【2 1 。目前已经纳入到i e e e 8 0 2 1 5 、8 0 2 1 6 、8 0 2 2 0 和8 0 2 1 1 s 标准中，也是4 g ( 4 t hg e n e r a t i o n ) 无线移动通信系统的主要组网方式之一。 w m n 由m e s h 路由器( m e s hr o u t e r ) 和m e s h 客户端( m e s hc l i e n t ) 两种类型的 节点自动组建成网络且维持网状结构。m e s h 路由器通常装配有多个能与不同无线技术 网络互连的无线接口，因此m e s h 路由器除了具有数据转发的功能外，还可以通过多跳 传输的方式实现与其他网络的互连，为用户提供接入服务。m e s h 客户端只配备一个无 线接口，同时也兼具路由功能。w m n 作为一种新型的接入网技术，它更多的是为用户 提供无线宽带接入服务，实现与因特网的相连。不同于w l a n 需要花费大量成本建设 接入点( a c c e s sp o i n t ，a p ) 来实现大范围的信号覆盖，w m n 不依赖任何基础设施， 可以通过多跳转发的方式实现的廉价和快速信号覆盖，所以即使在偏远的地区通过w m n 技术也可以低成本的实现宽带接入服务。w m n 有着广泛的发展前景，自从诞生以来 直广受关注，国内外许多研究机构和公司都投入到其产品和技术的研究当中，无线m e s h 网络将会进入飞速发展的时期。 基于蚁群优化的多网关w m n 多届搬选播路由算法研究 1 1 2 论文选题的目的和意义 w m n 在家庭、企业和公共场所等诸多领域具有广阔的应用前景【3 】。例如家庭式 w m n 联网可以连接台式p c 机、笔记本和手持计算机、h d t v 、d v d 播放器、游戏控 制台，以及其他各种消费类电子设备，而不需要复杂的布线和安装过程；校园m e s h 网 络能够实现室内、室外、礼堂、宿舍、图书馆、公共场所等之间的无缝漫游；m e s h 网 络还能以最低的成本为比较偏远的旅游场所提供宽带服务。国际上著名的厂商如i n t e l 、 m o t o r o l a 、c i s e o 、m i c r o s o f t 等跨国公司也开始加入到w m n 的研究当中，各个大学研究 机构也都纷纷建立了w m n 网络的试验床，如美国麻省理工大学的r o o f n e t 项目、加州 大学圣塔芭芭拉分校的m e s h n e t 项目、普度大学的m a p 项目等。国内的清华大学、暨 南大学、中国海洋大学、河北廊坊大学城等许多院校相继建设了w m n 网络实证网，西 南交通大学等大学的w m n 网络也正在建设之中。 w m n 主要是为底层终端用户提供因特网接入服务，不同于m a n e t 的对等业务模 式，w m n 业务汇聚于m e s h 路由器网关，容易造成局部网络拥塞，使得很难维护网 络全局最优路由，网关往往会成为制约整个网络性能的瓶颈，可通过设置多个网关以缓 解瓶颈问题，而通信过程中如何在这样的多网关w m n 中选取一个合适的网关节点来接 入因特网就成为提高w m n 性能的关键问题之一。可见w m n 的路由协议性能需求与传 统的m a n e t 路由协议应有很大区别。传统的m a n e t 路由协议基本上都是以最少跳数 为准则，研究表吲4 。5 】，该准则在大多数情况下并不是最优的，它不能满足w m n 在网 络吞吐量与用户需求保证上的要求。因此，需要研究和设计新的路由协议和算法，提高 w m n 的网络吞吐量、负载均衡及容错等能力，通过网络整体性能的提升来达到满足用 户的需求。 选播( a n y c a s t ) ”】是一种应用非常广阔的新型网络通信服务，它采用“尽力而为”的 方式，将选播报文至少传输到一个具有选播地址的“最近 的主机，最好仅仅传输到一 个主机【7 1 。由于越来越多的应用需要选播服务，因此在i p v 6 中把它定义为一种标准的通 信服务模型【6 1 。选播的特性对于大幅度地简化某些网络应用有着广泛的前景，例如：可 支持分布式的复制服务器，实现“最优 服务的选择【8 9 】；支持主机自动配置，为应用 提供透明服务( 如域名服务、镜像网站等) 【8 】；支持移动m 本地代理的查找，从而使选 播逐渐成为实现移动组播的关键技术【l o 】，等等。选播作为一类新的通信协议，具有平衡 网络负载、优化网络资源、有效提高网络资源利用率等性能。在w m n 中可将终端用户 基于蚁群优化的多网关聊d n 多髭阿龟选播路由算法研究 如何选择适当的网关节点看成是一种典型的网络选播服务。蚁群算法具有自发建立、自 动布置和任意移动的特性，适用于无线网络，可以应用到w m n 以优化其路由选择。 本文将创新性地建立多网关w m n 的选播模型，并利用参数优化理论启发式地解决 w m n 多网关选取优化问题。该模型可以综合考虑时延、跳数、节点间链路剩余带宽、 网关负载等参数和用户q o s ( q u a l i t yo f s e r v i c e 服务质量) 要求，提高w m n 无线宽带 接入网的性能。在分析了a o m d v ( a dh o co n d e m a n dm u l t i p a t hd i s t a n c ev e c t o r 按需多 路径距离矢量路由协议) 的基础上，考虑其优点与不足，拟将蚁群算法与a o m d v 协议 相结合，充分考虑多目标多路径路由技术的特性，用选播机制解决w m n 中的网关选取 问题，提出一种基于蚁群算法的启发式多网关w m n 多路径选播路由算法，该算法以链 路层、网络层性能参数为路径选择权重来建立概率数学模型，并避免蚂蚁求解所有路径 权重的过程，提高w m n 路由的抗毁性，保证网络和网关的负载分布均衡，缓解w m n 接入网拥塞问题。 对用户提供可靠服务是w m n 的关键技术之一，将对w m n 的网络性能起着重要作 用。目前在w m n 中关于w m n 路由算法的研究还相对较少，也还没有路由协议的 统一正式标准，需要针对w m n 的特殊性设计专门适用于w m n 的高效路由协议。因此， 多网关w m n 选播关键技术问题的研究是这一领域中非常必要和重要的课题。 1 2 课题的国内外研究现状 1 2 1w m n 网络路由研究 目前，有关w m n 网络的路由研究主要采用两种方案：一是在现有的m a n e t 路由 协议的基础上进行改进，使之适用于w m n 网络【l l - 13 1 。二是设计新的w m n 网络解决方 案，设计私有的路由协议。 多射频链路质量源路由协议m r l q s r 5 1 ( 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 路由协议。该协议采用加 权累积传输时间w c e t r ( w e i g h t e dc u m u l a t i v ee t t ) 作为路由判据，除了考虑最小跳 数因素外还考虑了带宽等链路性能参数，协议能够在网络吞吐量与延时之间获得一种平 衡【1 4 - 15 1 。 可预测的无线路由协议p w r p ( p r e d i c t i v ew i r e l e s sr o u t i n gp r o t o c 0 1 ) 1 6 】是t r o p o s 公 司开发的应用于“w i f i 蜂窝网络户外系统”的私有路由协议。该协议在考虑跳数的同时 基于蚁群优化的多网关w m n 多磋阡垒选播路由算法研究 还通过比较数据误包率及其他网络条件来确定特定环境下的最优路径。该路径是可达到 最大吞吐量的路径，而且由于在业务传输中选用的是性能最佳的路径，可以有效的减小 射频干扰、路径故障以及业务载荷等因素的影响。 基于链路质量选择路由的协谢1 7 】是s r i k r i s h n a 于2 0 0 4 年1 月申请的m e s h 网路由专 利。该协议以到达因特网接入点( m e s h 网关节点) 的路径质量为判据选择最优路径。所有 节点接收来自接入点的路由数据包，该数据包记录了到达接入点的路由信息，具有最大 数据传输率的路由将被选中。 其他公司的w m n 路由协议还有比如l o c u s tw o r l d 公司的m e s h a p 方案； m e s h n e t w o r k 公司开发的m s r ( m e s h n e t w o r k ss c a l a b l er o u t i n g ) us 】协议结合了先应式路 由与反应式路由的优点；还有f i r e t i d e 公司的f i r e t i d e m e s h 路由协谢1 9 】( f m r p ) 等。 由于w m n 业务集中于网关，所以针对网关选取的路由设计也是重点。目前对网关 选取策略的研究尚处在起步阶剧2 0 1 ，近几年也出现了许多研究成果。文献 2 1 提出了一 个多网关接入模型m g a ( m u l t i g a t e w a y a s s o c i a t i o n ) ，论证与单网关接入相比的优越性。 文献 2 2 提出了一个无线自组网域内网关切换方案。该方案以分组往返时间、丢包率的 路径质量和网关负载为网关选择和切换指标，并通过网关的预发现和预注册优化网关切 换的性能。文献 2 3 】提出了一种无线m e s h 网络网关选取策略，网关通过网关通告消息 的t t l 控制网关通告的传输范围和调整网关所服务的m e s h 节点的范围，对于没有在任 何网关服务范围内的m e s h 节点，传送数据之初要主动发起网关搜索帧，该协议能够有 效的减少网络开销，平衡网络负载。 在无线网络中，由于无线环境的不确定因素，导致无线信道容量和误比特率等特性 发生时变，传统的分层路由设计方法无法保证网络的最佳资源利用率和用户业务的需 求。为了改善无线网络的性能，进行协议的跨层设计是十分必要的。在过去的几年时间 里，对于跨层路由技术的研究有很多，也提出了很多跨层路由协议设计的理论和方案。 在这些研究中，有应用于a dh o c ( i n f r a s t r u c t u r e l e s sn e t w o r k ) 网络多速率、物理层m a c 层关联的路由协议p r a m a 驯；应用于无线m e s h 网络基于d s r ( d y n a m i cs o u r c er o u t i n g 动态源路由) 的可预测公平感知路由协议算法p f r p 1 2 】( p r e d i c t i v ea n df a i r n e s s a w a r e r o u t i n gp r o t o c 0 1 ) ；以及巴黎皮埃尔和玛丽居里大学研究者提出的一种专用于无线m e s h 网络的基于干扰估计，分组成功率和数据速率的跨层设计方案2 5 - 2 6 等。 虽然上述提出的路由协议可以应用到w m n 网络中来，但是在性能方面或通用性方 面存在一定的不足。w m n 网络对路由协议有着更多更复杂的要求，因此，研究真正适 广西大掌硕士掌位论文基于蚁群优化的多网关w m n 多髭哺乏选播路由算法研究 用于w m n 的通用的路由协议是十分必要的。 1 2 2 移动自组网选播路由研究现状 目前，在因特网中对选播服务模型的研究主要有两种方式：一是基于应用层选播， 通过目标服务器的选择实现选播服务、优化网络应用【2 刀；二是基于网络层选播，利用选 播路由技术实现选播服务、提高网络通信的效率和服务的负载均衡【2 8 圆】。在m a n e t 网 络中，选播路由研究的难点在于其高动态和路由频繁变化的特性【3 0 1 。从目前m a n e t 网 络中选播路由的研究成果来看，研究主要从两个方面着手【3 l 】：在现有路由协议基础上进 行扩展以支持选播服务和设计实现基于虚节点的选播路由协议。 在m a n e t 中，已经存在多种路由协议，如a o d v ( o n d e m a n dd i s t a n c ev e c t o r r o u t i n g 按需距离矢量路由) 、d s r 、t o r a ( t e m p o r a l l yo r d e r e dr o u t i n g a l g o r i t h m 临时 按序路由算法) 【3 2 1 等。s w a m i n a t h a n 等提出了扩展a o d v 协议以支持选播服务的思想【3 3 】； 中南大学王建新等提出了一个基于a o d v 的选播路由协议a a o d v t 3 4 】和基于d s r 的选 播路由协议a d s r 3 s 】，并利用n s 2 仿真分析了协议的可用性和有效性；文献 3 6 】的作 者修改了t o r a 协议，结合选播路由协议与泛洪协议，提出了g e o c a s t 服务的概念和 g e o c a s t i n g 算法。这一方面的研究主要是利用了m a n e t 中已有的路由协议和寻路机制， 通过扩充选播组概念，利用单播和选播的映射关系来实现选播服务【3 l 】。 在基于虚节点的选播路由协议的研究方面，人们把选播服务表示为“虚节点”，请 求选播服务的节点只要把报文发往虚节点就可获得选播服务【3 7 - 3 8 1 。基于虚节点的概念， p a r k 等扩展了相应链路状态、距离向量和链路反转等单播通信协议来完成选播服务 3 7 - 3 8 1 ，g u l a t i 等通过改进现有的d s r 、a o d v 和t o r a 协议来完成选播通信协谢3 9 1 。 这些方法非常直观，但是性能得不到保障。 除此以外，i n t a n a g o m w i w a t 等提出一个基于汇聚节点“s i n k ”的a dh o c ( 无线自组 网) 选播路由协议s a r p 4 0 1 ，可应用于分布式控制或数据收集领域：中南大学王建新等 针对m a n e t 传输路径容易断裂的特点，提出了一种有效的选播路由协议e a r p 4 1 - 4 2 ， 可有效用于选播路由维护。北京大学严伟等采用启发式环索算法，对m a n e t 中的选播 路由作了一定的研究【4 3 1 。 综上所述，在m a n e t 中，路由技术和基于网络层的选播服务研究已经取得一些进 展，并取得了一些相关研究成果。尽管w m n 是m a n e t 的一种特殊形态，但因为它们 的拓扑移动性和业务模式的不同，使得在m a n e t 中已有的研究成果很难直接适用于 基于蚁群优化的多网关w m n 多鼹哺乏选播路由算法研究 w m n 网络【4 4 。4 7 1 。w m n 在未来无线宽带接入领域中将扮演着重要的角色，随着人们对 因特网接入服务质量的不断提高，如何提升w m n 网络的性能，路由协议的设计将是十 分重要的。 1 3 本文的研究内容和主要创新点 1 3 1 本文的研究内容 本文的研究内容主要包括以下几个方面 1 ) 研究基于选播的网关选择优化问题，将网关选取看作网络选播通信来处理，构 建基于选播和跨层设计的w m n 网关选取优化模型； 2 ) 研究a o m d v 路由协议并进行改进和优化，结合蚁群算法提出基于蚁群优化和 跨层策略的w m n 负载均衡路由方案( a a o m d v ) ； 3 ) 研究选播通信服务及其实现技术，对基于选播的移动自组网路由协议进行研究， 将蚁群算法应用于选播，建立一种基于蚁群优化的多路径多网关w m n 网络选播路由算 法( m m a m b a ) ； 4 ) 在仿真平台n s 2 ( n e t w o r ks i m u l a t o rv 2 ) 下，对提出的路由协议进行性能仿真 实验，通过比较端到端平均时延、分组成功投递率和平均路由开销，分析验证了本文提 出的算法正确性和有效性。 1 3 2 本文的主要创新点 本文的创新主要有以下两点： 1 ) 建立多网关w m n 的选播模型，并利用参数优化理论启发式地解决w m n 多网 关选取优化问题。该模型可以综合考虑时延、跳数、节点间链路剩余带宽、网关负载等 参数，提高w m n 无线宽带接入网的性能。 2 ) 采用跨层路由设计的思想，提出一种基于蚁群优化的多网关w m n 选播路由算 法。算法拟将蚁群算法与m a n e t 路由协议相结合，充分考虑多目标多路径路由技术的 特性，构建以链路层、网络层参数为路径选择权重的概率数学模型，并避免蚂蚁求解所 有路径权重的过程，提高w m n 路由的抗毁性，保证网络和网关的负载分布均衡，缓解 w m n 接入网拥塞问题，满足用户需求。 广西大学硕士学位论文基于蚁群优化的多网关w m n 多路径选播路由算法研究 1 4 本文的组织结构 论文结构安排如下： 第一章，作为绪论，介绍课题的研究背景和意义，阐述课题的研究现状、论文的研 究内容和主要创新点，简述论文的总体组织结构。 第二章，介绍无线m e s h 网络的几种典型网络结构与特点，分析设计无线m e s h 网 络协议时必须考虑的几个因素，并阐述w m n 路由协议设计的思路和研究方向。 第三章，简单介绍蚁群算法与a o m d v 协议的基本原理。引入了蚁群算法的思想对 a o m d v 进行了改进，提出了基于蚁群优化的w m n 多路径路由算法( a a o m d v ) ， 并对所提出的算法( a - a o m d v ) 与a o m d v 协议进行了仿真比较。 第四章，构建基于选播和跨层设计的多路径w m n 网关选取优化模型，在第三章的 基础上将a o m d v 协议扩展成多目标多路径路由并结合选播机制，提出了基于蚁群优化 的多网关w m n 多路径选播路由算法( m m a m b a ) 。通过仿真工具n s 2 对所提出的路 由协议( m m a m b a ) 与a o m d v 协议在w m n 网络环境实验环境下进行了仿真实验， 并分析实验结果，验证m m a m b a 在w m n 中良好的网络性能。 第五章，对论文研究工作进行总结与展望，提出了本文研究的不足以及将来可以进 一步解决的问题。 广西大掌硕士掌位论文基于蚁群馋化的多网关m 烈多路径选播路由算法研究 第二章无线m e s h 网络路由技术 2 1 无线m e s h 网络的网络结构与特点 w m n 是由移动a dh o c 网络发展而来，并沿袭了w l a n 技术的特点，网内节点可 以任意分布相互连接而形成网状拓扑结构，具有自组织、自配置和自治愈的特点，各节 点通过多跳的路由转发方式来进行通信和接入核心网络，可以方便低成本地扩大网络的 覆盖范围，是一种高容量，高速率、低成本的分布式网络。 w m n 一般由两种类型的节点组成【4 8 】：m e s h 路由器( m e s hr o u t e r ) 和m e s h 客户 端( m e s hc l i e n t ) ，能够自动组建成网络且维持网状连接。为了进一步提高w m n 网络 的灵活性，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 m n 本 质上是m a n e t 网络的一种特殊形态，它与后者最大的区别就在于其业务主要是接入因 特网，路由器节点移动相对较少，更注重保证q o s 问题。w m n 通过网关节点实现与因 特网的高速互连，家庭或办公室等终端用户可以通过直接或多跳的方式与网关相连。对 于网关节点信号覆盖之外的区域，可以通过非网关m e s h 路由器或用户节点的中继转发 来实现大范围的廉价和快速信号覆盖。根据这些特点可以将无线m e s h 网络划分为三种 结构形式：骨干网结构、客户端结构和混合结构：【3 4 8 】 ( 1 ) 骨干网结构 w m n 骨干网结构是由m e s h 路由器互连构建而成，如图2 1 所示，在这些路由器 中有一种只负责数据转发( m e s h 路由器) 另一种具有网关功能( m e s h 网关路由器) ，负 责与其他网络相连，为用户端提供接入服务，并能实现不同通信子网之间的互联，如图 中的w i f i 网络( w l a n ) ，蜂窝网络，w i m a x ( w o r l d w i d ei n t e r o p e r a b i l i t yf o rm i c r o w a v e a c c e s s ) 网，传感器网络等。客户端和其他无线网络还可以通过m e s h 网关路由器连接 i n t e r n e t 网络，访问i n t e m e t 资源。无线m e s h 网络的骨干网结构是w m n 数据传输的主 要线路，一般而言在整个网络中只需要一个网关接i n t e m e t 网络，所有网络节点都可以 通过该网关接入i n t e r n e t ，不过这样往往会造成单网关由于负载过重而服务质量下降的 基于蚁群优化的多网关w m n 多厦卜圣垒选播路由算法研究 情形，所以一般在网络中要根据实际情况部署适当的网关与i n t e m e t 相连。 图2 - 1 骨干m e s h 结构 f i g 2 - 1b a c k b o n en e t w o r ks t r u c t u r e ( 2 ) 客户端m e s h 结构 w m n 的客户端结构实际上可以看作a dh o c 网络，只是在移动性上有所不同，如图 2 2 所示，整个结构由对等的m e s h 客户端组成一个具有自组织、自配置的小型网络， 为用户提供点到点的终端服务。在这种结构中，当任意节点间需要进行通信时都可以通 过多个节点的转发来实现，中间节点起到了路由器的功能。 图2 2 客户端m e s h 结构 f i g 2 - 2c l i e n tn e t w o r ks t r u c t u r e ( 3 ) 混合结构 如图2 3 所示，w m n 混合结构是骨干网结构和客户端结构两种结构的有机结合。 广西大掌硕士学位论文 基于蚁群优化的多网关1 j 1 7 小多叠酎瞪选播路由算法研究 混合结构的w m n 具有更广的应用范围，能够实现与其他网络的互联，如因特网、 w l a n 、w i m a x 、蜂窝和传感器网络等，整合有线网络和无线网络在内的各种异构网 络，充分利用现有资源。在混合结构中终端节点需要同时具有接入上层网络m r ( m e s h r o u t e rm e s h 路由器) 和本层转发的功能。这种结构是w m n 中最常见的组网结构，也 是最有普遍研究意义的结构。 ”冒列挪函嘲量l 稚f 啊 图2 3 混合m e s h 结构 f i g 2 - 3h y b 硼w m n s 由上可知w m n 结合了移动自组网和w l a n 的特点，m e s h 路由器可以通过多跳的 方式实现通信，客户终端既可以通过骨干网实现与其他网络的相连，又可以直接与终端 通信，还可以转发数据，起到路由器的作用。继承了传统无线接入技术诸多优点同时又 与传统无线接入技术不同，总体来看w m n 主要有以下特点【4 9 巧1 】： ( 1 ) 多跳路由 w m n 采