（计算机系统结构专业论文）基于蚁群算法的组播路由优化与仿真.pdf

f， | 原创性声明和关于论文使用授权的说明f y 1 793839ifjlllllijilllflllllflllllrfllfllff i l i i f r l u p f 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名： 盗苤 日期： 至里竺车业芯日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：丝盗导师签名： 丫、汁 丛 一 j 雏 山东大学硕士学位论文 目录 摘要i a b s t r a c t 第1 章绪论l 1 1 组播路由问题提出的背景1 1 2 组播路由问题提出的意义2 1 3 组播发展历史2 1 4 计算机网络中的通信方式3 1 4 1 单播4 1 4 2 广播4 1 4 3 组播5 1 5 论文主要研究内容6 1 6 论文组织框架7 第2 章q o s 组播路由9 2 1 组播技术基础9 2 1 1 组播定义及基本思想9 2 1 2 组播地址9 2 1 3 组播转发树1 0 2 2 组播路由协议1 4 2 2 1 网络二层组播相关协议1 4 2 2 2 域内组播路由协议( p i m s m ) 1 4 2 2 3 域间组播路由协议1 6 2 3 组播路由算法1 7 2 3 1 基于最短路径思想的算法1 7 2 3 2 基于最小生成树思想的算法1 8 2 3 3k m b 算法1 8 2 3 4m p h 算法1 8 2 3 5a d h 算法1 9 山东大学硕士学位论文 2 3 6 智能优化算法1 9 2 4 网络的服务质量q o s 2 2 2 5q o s 组播路由问题的分类一2 3 2 5 1s t e i n e r 树问题2 5 2 5 2 多q o s 约束的组播路由问题2 5 2 6 本章小结2 7 第3 章蚁群优化算法2 8 3 1 双桥实验2 8 3 2 传统蚁群算法原理3 l 3 3 基本蚁群算法及其改进算法3 2 3 3 1 蚂蚁系统3 2 3 3 2 精华蚂蚁系统3 3 3 3 3 基于排列的蚂蚁系统3 3 3 3 4 最大最小蚂蚁系统3 3 3 4 本章小结3 4 第4 章生长森林的蚁群优化算法3 5 4 1s t e i n e r 树的定义3 5 4 2a c o f 的基本思想3 5 4 3a c o f 的基本操作3 6 4 3 1 森林的生长3 6 4 3 2 树的剪枝一3 7 4 3 3 信息素的更新3 7 4 4a c o f 的步骤描述3 7 4 5a c o f 的空间复杂度和时间复杂度分析4 1 4 6 仿真实验与结果分析4 1 4 6 1 仿真软件m r s i m 简介4 2 4 6 2 仿真实验结果4 4 4 7 本章小结4 9 第5 章可以分布式实现的蚁群优化算法5 0 “ ， 山东大学硕士学位论文 5 1 多o o s 约束的组播路由的定义5 0 5 2d a c o 的基本思想5 l 5 3d a c o 的基本操作5 3 5 3 1 预剪枝一5 3 5 3 2 森林的生长5 3 5 3 3 树的剪枝5 5 5 3 4 判断组播树是否满足q o s 约束一5 5 5 3 5 信息素的更新5 5 5 4d a c o 的步骤描述5 6 5 5d a c o 空间和时间复杂度分析5 7 5 6 仿真实验与结果分析一5 8 5 6 1 预剪枝操作对算法的影响实验5 8 5 6 4 算法优秀性验证实验5 9 5 7 本章小结6 l 第6 章总结与展望6 2 参考文献一6 4 致谢6 8 攻读学位期间发表的学术论文目录6 9 攻读学位期间参与的科研项目7 0 山东大学硕士学位论文 t a b l eo fc o n t e n t s a b m r a c ti nc h i n e s e i a b s t r a c ti ne n g l i s h c h a p t e r1i n t r o d u c t i o n 1 1 1b a c k g r o u n do f m u l t i c a s tr o u t i n gp r o b l e m 1 1 2s i g n i f i c a n c eo f m u l t i c a s tr o u t i n gp r o b l e m 2 1 3h i s t o r yo f m u l t i c a s t 2 1 4c o m m u n i c a t i o ni nc o m p u t e rn e t w o r k s 3 1 4 1u n i c a s t 4 1 4 2b r o a d c a s t 4 】【4 3m u l t i c a s t 。! ； 】【5m a i ns t u d yc o n t e n t 6 】【6p a p e rf r a m e w o r ka n dc h a p t e r a r r a n g e m e n t 7 c h a p t e r2q o sm u l t i c a s tr o u t i n g 9 2 1m u l t i c a s tt e c h n o l o g yb a s e 9 2 1 1c o n c e p ta n db a s i ci d e ao f m u l t i c a s t 9 2 1 2m u l t i c a s ta d d r e s s 9 2 1 3m u l t i c a s tf o r w a r d i n gt r e e 1 0 2 2m u l t i c a s tr o u t i n gp r o t o c 0 1 1 1 4 2 2 1n e t w o r kt w o - l a y e rm u l t i c a s tr e l a t e dp r o t o c o l s 1 4 2 2 2i n t r a - d o m a i nm u l t i c a s tr o u t i n gp r o t o c o l ( p i m - s m ) 15 2 2 3i n t e r - d o m a i nm u l t i c a s tr o u t i n gp r o t o c o l 1 7 2 3m u l t i c a s tr o u t i n ga l g o r i t h m 1 7 2 3 1a l g o r i t h mb a s e do ns h o r t e s tp a t h 18 2 3 2a l g o r i t h mb a s e do nm i n i m u ms p a n n i n gt r e e 1 8 2 3 3k m b a l g o r i t h m 1 8 2 3 4m p h a l g o r i t h m 1 9 2 3 5a d h a l g o r i t h m 1 9 么 山东大学硕士学位论文 2 3 6i n t e l l i g e n to p t i m i z a t i o na l g o r i t h m 2 0 2 4q u a l i t yo f s e r v i c e ( q o s ) 2 2 2 5c l a s s i f i c a t i o no fq o sm u l t i c a s tr o u t i n gp r o b l e m 2 3 2 5 1s t e i n e rt r e ep r o b l e m 2 5 2 5 2m u l t i c o n s t r a i n tq o sm u l t i c a s tr o u t i n gp r o b l e m 2 5 2 6s u m m a r y 2 7 c h a p t e r 3a n t c o l o n yo p t i m i z a t i o na l g o r i t h m 2 8 3 1d o u b l eb r i d g ee x p e r i m e n t 2 8 3 2t r a d i t i o n a la n tc o l o n ya l g o r i t h mp r i n c i p l e 3 1 3 3b a s i ca n tc o l o n ya l g o r i t h ma n di m p r o v e da l g o r i t h m 3 2 ：i 3 1a n ts y s t e m 3 2 3 3 2a l i t i s ts t r a t e g yf o ra n ts y s t e m 3 3 3 3 3a n ts y s t e mb a s e do nr a n k 3 3 3 3 4m a x - m i na n ts y s t e m 3 3 3 4s u m m a r y 3 4 c h a p t e r4a n tc o l o n yo p t i m i z a t i o na l g o r i t h mb a s e do i lf o r e s tg r o w t h 3 5 4 1d e f i n i t i o no fs t e i n e rt r e e 一3 5 4 2b a s i ci d e ao f a c o f 一3 5 4 3b a s i co p e r a t i o no f a c o f 3 6 4 3 1f o r e s tg r o w t h 3 6 4 3 2t r e e sp r u n i n g 3 7 4 3 3u p d a t i n gp h e r o m o n e 3 7 4 4s t e pd e s c r i p t i o n 3 7 4 5s p a c ec o m p l e x i t ya n dt i m ec o m p l e x i t ya n a l y s i s 4 1 4 6s i m u l a t i o ne x p e r i m e n t sa n dr e s u l t sa n a l y s i s 4 1 4 6 1m r s i m s i m u l a t i o ns o f t w a r ei n t r o d u c t i o n 4 2 4 6 2s i m u l a t i o nr e s u l t s 4 4 4 7s u m m a r y 4 9 c h a p t e r 5d i s t r i b u t e da n t c o l o n yo p t i m i z a t i o na l g o r i t h m 5 0 5 1d e f i n i t i o no fm u l f i - c o n s t r a i n t e dq o sm u l t i c a s tr o u t i n g 5 0 v 山东大学硕士学位论文 5 2b a s i ci d e ao f d a c o 5 1 5 3b a s i co p e r a t i o no f d a c o 5 3 5 3 1p r e _ p r u n i n g 5 3 5 3 2f o r e s tg r o w t h j 5 3 5 3 3t r e e sp r u n i n g 5 4 5 3 4j u d g e m e n to fq o sc o n s t r a i n t s 5 5 5 3 5u p d a t i n gp h e r o m o n e - - - 5 5 5 4s t e pd e s c r i p t i o n 5 6 5 5s p a c ec o m p l e x i t ya n dt i m ec o m p l e x i t ya n a l y s i s 5 7 5 6s i m u l a t i o ne x p e r i m e n t sa n dr e s u l t sa n a l y s i s 5 8 5 6 1e x p e r i m e n t so f i n f l u e n c eo f p r e _ p r u n i n g ：5 8 5 6 2s i m u l a t i o ne x p e r i m e n t s 5 9 5 7s u m m a r y 6 1 c h a p t e r6c o n c l u s i o n & e x p e c t a t i o n 6 2 i 沁f e r e n c e s 6 4 a c k n o w l e d e g m e n t s 6 8 a c a d e m i cp a p e rd u r i n gm a s t e rd e g r e es t u d y i n g j 6 9 r e s e a r c hp r o j e c tj o i n e dd u r i n gs t u d y i n g 7 0 v i f 。 厶 ， 山东大学硕士学位论文 摘要 i n t e m e t 网络传输和处理能力的大幅提高使得基于网络的应用越来越多，如远 程教学、视频会议、数据分发和网络游戏等网络多媒体应用。这些多媒体应用有 着数据量大、时延要求高、持续时间长等特点，需要采用不同于传统单播和广播 机制的转发技术及服务质量( q u a l i t yo f s e r v i c e ，简称q o s ) 保证机制来实现，组播 技术正是解决这个问题的理想方案。组播( m u l t i c a s 0 是一种有效的支持多点通信 的机制，一般指的是一个或多个源节点向多个目的节点发送信息的通信方式。它 是指在口网络中将数据包以尽力传送( b e s t - e f f o r t ) 的形式发送到网络中的某个确 定节点子集，这个子集称为组播组( m u l t i c a s tg r o u p ) 。q o s 是网络在传输业务流时， 业务流对网络服务的需求的集合，其中业务流是指与特定q o s 相关的从源到目的 地的分组流。t f 已经提出了多种服务模型和机制来满足各种q o s 组播的需求。 实时应用往往会对延时，延时抖动，带宽，丢失率，业务代价等多个参数同时提 出性能要求。这些参数相互独立时，选择满足多个参数限制的最优组播路由就成 为n p 完全问题。 本文在对组播问题和蚁群优化算法作深入研究的基础上，提出了可以解决组 播路由问题的生长森林的蚁群优化算法和可以分布式实现的蚁群优化算法： ( 1 ) 针对多播树费用最小化问题，即s t e i n e r 树问题，它是指使用树最优化函 数构建最优的多播树，本文提出一种可以解决s t e i n e r 树问题的新的蚁群算法， 生长森林的蚁群优化算法。蚂蚁行动过程中形成的是森林，每只蚂蚁走出的每一 步都只是使当前的森林进一步生长，蚂蚁行动的目标就是森林中所有的树连接成 一棵树且这棵树包含了所有的目标节点。本文分别使用s t e i n l a br e p o s i t o r y 中b 类拓扑图和m r s i m 中的拓扑生成器生成的w a x m a n 模型作为测试的拓扑，仿真 试验结果表明，算法的性能明显优于k m b 、s p h 、c d k s 和传统蚁群算法等生 物启发式算法。本算法在速度上与传统蚁群算法、遗传算法相比要快得多，并且 在拓扑规模增大时，有更好的表现。此算法有效地解决了无约束多播树费用最小 化问题。 ( 2 ) 对于多q o s 约束的组播路由问题，本文提出了一种可以分布式实现的蚁 群优化算法，算法考虑了多种q o s 约束条件，包括带宽、延迟、延迟抖动和丢 山东大学硕士学位论文 包率。在此算法中蚂蚁行动过程中形成的是组播树的森林。在开始时森林中只有 源节点和目的节点。蚂蚁走出一步是使森林中的每棵树都选择一条边加入。若某 一步结束时森林中仅剩下一棵树，则蚂蚁达到目标，停止行动。算法最为重要的 一个优点是可以分布式实现。仿真结果表明算法在寻优能力和收敛速度方面都优 于a m i - e t 、传统蚁群和遗传等算法，而且拓扑规模越大，优秀性越明显。可 以分布式实现的蚁群优化算法既能并行性和分布式实现，又能以较快的速度收敛 到一个理想的结果。 关键词：组播；多约束；s t e i n e t 树问题；蚁群优化算法；生长森林；分布 式实现 i i t i 山东大学硕士学位论文 a b s tr a c t t h ei m p r o v e m e n to fi n t e m e tn e t w o r kt r a n s m i s s i o na n dp r o c e s s i n gc a p a b i l i t i e s e n a b l e sas u b s t a n t i a li n c r e a s ei nw e b - b a s e da p p l i c a t i o n s ，s u c ha sr e m o t ee d u c a t i o n ， v i d e oc o n f e r e n c e ，d a t a d a t ad i s t r i b u t i o na n do n l i n e g a m i n ga n ds o o n t h e s e m u l t i m e d i aa p p l i c a t i o n sh a v et h ec h a r a c t e r i s t i c so fb i gd a t aq u a n t i t y , h i g hl a t e n c y , l o n gd u r a t i o na n ds oo n ，s oi tn e e d st oa d o p tf o r w a r d i n gt e c h n o l o g yt h a ti sd i f f e r e n t f r o mt r a d i t i o n a lu n i c a s ta n db r o a d c a s ta n dq u a l i t yo fs e r v i c ea s s u r a n c em e c h a n i s m s m u l t i c a s tt e c h n o l o g yi st h ei d e a ls o l u t i o nt os o l v et h i sp r o b l e m m u l t i c a s ti sa m e c h a n i s mw h i c hc a ns u p p o r t sm u l t i - p o i n tc o m m u n i c a t i o ne f f i c i e n t l y , a n dg e n e r a l l y i tr e f e r st ot h ec o m m u n i c a t i o nt h a ts e n d sm e s s a g e sf r o mo n eo rm o r eo ft h es o u r c e n o d et o m u l t i p l e d e s t i n a t i o nn o d e s t h i s a p p r o a c h m a k e si pm u l t i c a s t r e s o u r c e - e f f i c i e n ti nd e l i v e r i n gd a t at oag r o u po fm e m b e r ss i m u l t a n e o u s l ya n dt h i s s u b s e ti sc a l l e dm u l t i c a s tg r o u p q o si sad e m a n ds e tw h i c hi st r a f f i cf l o wt on e t w o r k s e r v i c ew h e nn e t w o r kt r a n s m i t st h et r a f f i cf l o w , a n dt h et r a f f i cf l o wi sp a c k e tf l o w a s s o c i a t e dw i t l las p e c i f i cq o sf r o mt h es o u r c et ot h ed e s t i n a t i o n i e t fh a sp r o p o s e d av a r i e t yo fs e r v i c em o d e l sa n dm e c h a n i s m st om e e tt h en e e d so fav a r i e t yo fq o s m u l t i c a s t t h er e a l - t i m ea p p l i c a t i o n so f t e nm a k ep e r f o r m a n c er e q u i r e m e n t st od e l a y , d e l a yji t t e r , b a n d w i d t h ，l o s s r a t e ，o p e r a t i o n a lc o s t sa n do t h e rp a r a m e t e r sa tt h es 锄e t i m e w h e nt h e s ep a r a m e t e r sa r ei n d e p e n d e n to fe a c ho t h e r , s e l e c t i n gt h eo p t i m a l m u l t i c a s tr o u t i n gt om e e tm u l t i p l ep a r a m e t e r sr e s t r i c t i o n sb e c o m e san pc o m p l e t e p r o b l e m i nt h i sp a p e r , b a s e do ni n d e p t hs t u d yo ft h em u l t i c a s tr o u t i n gp r o b l e ma n da n t c o l o n yo p t i m i z a t i o na l g o r i t h m , t w oa l g o r i t h m sa r ep r o p o s e dt o s o l v et h eq o s m u l t i c a s tr o u t i n gp r o b l e m t h e ya lea n tc o l o n yo p t i m i z a t i o na l g o r i t h mb a s e do nf o r e s t g r o w t ha n dd i s t r i b u t e da n tc o l o n yo p t i m i z a t i o na l g o r i t h m ： ( 1 ) f o rt h e m u l t i c a s tt r e e c o s tm i n i m i z a t i o np r o b l e m , n a m e l yt h es t e i n e rt r e e p r o b l e m ，w h i c hr e f e r st oc o n s t r u c tt h eo p t i m a lm u l t i c a s tt r e eu s i n gt r e eo p t i m i z a t i o n f u n c t i o n ，an e wa n tc o l o n ya l g o r i t h mi sp r o p o s e dt os o l v et h es t e i n e rt r e ep r o b l e m i i i 厶瓢伊 山东大学硕士学位论文 t h a ti sa n tc o l o n yo p t i m i z a t i o na l g o r i t h mb a s e do nf o r e s tg r o w t h i nt h i sa l g o r i t h m , a f o r e s ti sf o r m e dd u r i n gt h ea n tm o v e m e n tp r o g r e s s ，a n df o re v e r ya n t ，e a c hs t e pi t t a k e si st om a k ec u r r e n tf o r e s tg r o w t h eo b je c t i v eo fa n tm o v e m e n ti st oc o n n e c ta l l t h et r e e si nt h ef o r e s tt of o r mas i n g l et r e e ，w h i c hc o n t a i n sa l lt a r g e tn o d e s bc l a s s t o p o l o g yi nt h es t e i n l a br e p o s i t o r ya n dw a x m a nt o p o l o g ym o d e lg e n e r a t e db y m r s i mt o p o l o g yg e n e r a t o ra r eu s e da st h et e s tt o p o l o g y s i m u l a t i o ne x p e r i m e n t s i n d i c a t et h a tp e r f o r m a n c eo ft h ea l g o r i t h mi ss u p e r i o rt ok m b 、s p h 、c d k sa n d t r a d i t i o n a lb i o - h e u r i s t i ca l g o r i t h m s t h e a l g o r i t h mi s m u c hf a s t e rt h a n 、 ，i t ht h e t r a d i t i o n a la n tc o l o n ya l g o r i t h m , g e n e t i ca l g o r i t h mi n s p e e d , a n dh a s b e t t e r p e r f o r m a n c ew h e nt h et o p o l o g y ss i z ei n c r e a s e s t h i sa l g o r i t h mh a ss o l v e dt h e u n c o n s t r a i n e dm u l t i c a s tt r e ec o s tm i n i m i z a t i o np r o b l e me f f e c t i v e l y ( 2 ) f o rt h em u l t i c o n s t r a i n e dq o sm u l t i c a s tr o u t i n gp r o b l e m , ad i s t r i b u t e da n t c o l o n yo p t i m i z a t i o na l g o r i t h mi sp r o p o s e d t h ea l g o r i t h mt a k e si n t oa c c o u n tav a r i e t y o fq o sc o n s t r a i n t s ，i n c l u d i n gb a n d w i d t h ，d e l a y , d e l a yj i t t e ra n dp a c k e tl o s s r a t e i nt h i s a l g o r i t h m , am u l t i c a s tt r e e sf o r e s ti sf o r m e dd u r i n gt h ea n tm o v e m e n tp r o g r e s s t h e o b j e c t i v eo fa n tm o v e m e n ti st oc o n n e c ta l lt h et r e e si nt h ef o r e s tt of o r mas i n g l et r e e t h em o s ti m p o r t a n ta d v a n t a g eo ft h ea l g o r i t h mi sd i s t r i b u t e di m p l e m e n t a t i o n s i m u l a t i o ne x p e r i m e n t ss h o wt h a tt h i sa l g o r i t h mp e r f o r m sb e t t e rt h a na n t n e t 、 t r a d i t i o n a la n tc o l o n ya l g o r i t h m 、g e n e t i ca l g o r i t h ma n do t h e ra l g o r i t h m sb o t hi n r e s u l t sa n dc o n v e r g e n c es p e e da n dh a sb e t t e rp e r f o r m a n c ew h e nt h et o p o l o g y ss i z e i n c r e a s e s t h ed i s t r i b u t e da n tc o l o n yo p t i m i z a t i o na l g o r i t h mc a nb ei m p l e m e n t e d p a r a l l e la n dd i s t r i b u t e d ，b u ta l s oc o n v e r g e st oad e s i r e dr e s u l ti naf a s t e rs p e e d k e y w o r d s ：t l u i t i c a s t ：m u i t i _ c o n s t r a i n t e d ：s t e i t i e rt r e ep r o b i a m ：a n t c o i o n ya i g o ri t h m ；f o r e s tg r o w t h ：d i s t ri b u t e di m p i e m e n t a t i o n i v 式 静 ， 硪 山东大学硕士学位论文 第1 章绪论 1 1 组播路由问题提出的背景 近年来计算机网络飞速发展，网络功能日益强大。i n t e m e t 网络传输和处理能 力的大幅提高使得基于网络的应用越来越多，特别是音频和视频压缩技术的发展 和成熟，使得网上音频、视频应用成为i n t e m e t 上最重要的应用之一，出现了如远 程教学、视频会议、数据分发和网络游戏等网络多媒体应用。这些多媒体应用和 一般网络应用相比，有着数据量大、时延要求高、持续时间长等特点( 见表1 1 t u ) ， 而目前的i n t e m e t 仅提供尽力而为( b e s t e f f o r ts e r v i c e ) 的传送服务，业务量尽快传 送，没有明确的时间和可靠性保障。显然，现有的尽力传送服务已无法满足这些 应用对网络传输质量的不同要求，需要i n t e m e t 提供有多种服务质量( q u a l i t yo f s e r v i c e ，简称q o s ) 类型的业务，需要采用不同于传统单播和广播机制的转发技术 及q o s 保证机制来实现，组播技术正是解决这个问题的理想方案。q o s 组播路由 技术作为分布式的网络多媒体业务的关键技术，而一度成为人们的研究热点，在 这方面已有不少的研究成果。i e t f 已经提出了多种服务模型和机制来满足各种 q o s 组播的需求。实时应用往往会对延时，延时抖动，带宽，丢失率，业务代价 等多个参数同时提出性能要求【2 1 ，这些参数相互独立时，选择满足多个参数限制 的最优组播路由就成为n p 完全问题【3 4 】。 表1 1 各种应用和q o s 要求 应用时延敏感度带宽要求 p 电话高小 电视会议系统高大 音乐 由由 图像 由 大 w 曲 由 中 e m a i l 低 小 a 厶 ll。l 山东大学硕士学位论