（计算机系统结构专业论文）基于蚁群的聚合组播优化算法研究.pdf

厂 v 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：丛 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：堡耋叁导师签名：业 4 l j ， ， ， 2 1 聚合组播问题描述一6 2 2 聚合组播的网络模型及定义7 2 3 聚合组播算法分析8 2 3 1 静态模式9 2 3 2 动态模式一l o 2 4 聚合组播相关协议1 1 2 4 1 集中式协议1 1 2 4 2 分布式协议1 2 2 4 3 聚合组播在大规模域中的实现1 3 2 4 4 满足q o s 约束的聚合组播协议1 4 2 5 本章小结l5 第三章蚁群算法1 7 3 1 蚁群算法的基本原理1 7 3 2 蚁群算法的研究成果1 9 3 2 1 蚂蚁系统1 9 3 2 2 蚂蚁系统的改进1 9 3 2 3 蚁群与其他仿生优化算法的融合2 0 3 3 蚁群算法在网络路由问题中的应用2 l 3 3 1 分布式求解路由问题的蚁群算法2 l 3 3 2 解决q o s 组播路由问题的蚁群算法2 2 3 3 3 应用于移动a dh o c 网络的蚁群算法2 2 3 4 本章小节2 3 第四章基于蚁群优化的聚合组播算法2 4 4 1 聚合组播的n p c 证明2 4 4 2 基于蚁群优化的聚合组播算法的基本思想2 5 4 2 1 树的选择2 7 4 2 2 聚合树的权重2 7 4 2 3 树选择结果的评价值2 8 4 2 4 信息素更新2 8 5 3 2 相似度函数4 3 5 3 3 同类候选组集合及组播组潜力值4 3 5 3 4 同类组的选择4 5 5 3 5 聚类结果评价值4 7 5 3 6 信息素更新4 8 5 4 基于聚类聚合组播的蚁群优化算法的实现流程4 9 5 5 算法时间复杂度分析5 0 5 6 仿真实验及数据分析5 1 5 6 1 仿真环境说明5 l 5 6 2 仿真实验结果及分析5 2 5 7 本章小结5 6 第六章总结与展望5 7 6 1 总结5 7 6 2 展望5 8 参考文献5 9 致谢一6 4 攻读学位期间发表的主要学术论文一6 5 在读期间参与的科研项目情况6 6 i 【ji 东大学硕十学位论文 t a b l eo fc o n t e n t s a b s t r a c ti nc h i n e s e 】 a b s t r a c ti ne n g l i s h c h a p t e rli n t r o d u c t i o n 。1 1 1m u l t i c a s tf o r w a r d i n gs t a t e sp r o b l e m l 1 ：! c u r r e n tr e s e a r c hs t a t u s 】【 1 2 1s u p p r e s s i n gm u l t i c a s ts t a t ea tr o u t e r s 2 1 2 2a g g r e g a t i n gm u l t i c a s ts t a t ea tp o u t e r s 3 1 2 3a g g r e g a t e dm u l t i c a s t 3 1 3m a i nr e s e a r c hc o n t e n t 4 1 4p a p e rf r a m e w o r k 4 c h a p t e r2a g g r e g a t e dm u l t i c a s t 6 2 1p r o b l e md e s c r i p t i o no f a g g r e g a t e dm u l t i c a s t 6 2 2n e t w o r km o d e la n dd e f i n i t i o no f a g g r e g a t e dm u l t i c a s t 7 2 3a l g o r i t h ma n a l y s i so f a g g r e g a t e dm u l t i c a s t 8 2 3 1s t a t i cm o d e 9 2 3 2d y n a m i cm o d e 1 0 2 4r e l a t e dp r o t o c o lo f a g g r e g a t e dm u l t i c a s t 1l 2 4 1c e n t r a l i z e dp r o t o c 0 1 】【1 【 2 4 2d i s t r i b u t e dp r o t o c 0 1 】【：2 ： 2 4 3a g g r e g a t e dm u l t i c a s ti nl a r g ed o m a i n s 1 3 2 4 4a g g r e g a t e dm u l t i c a s tw i t i lq o sc o n s t r a i n t s 1 4 2 5s u m m a r y 11 ； c h a p t e r3a n tc o l o n ya l g o r i t h m 1 7 3 1t h eb a s i cp r i n c i p l eo f a n tc o l o n ya l g o r i t h m 1 7 3 2r e s e a r c ho f a n tc o l o n ya l g o r i t h m 1 9 3 2 1a n ts y s t e m 1 9 3 2 2i m p r o v e m e n to f a n ts y s t e m 1 9 3 2 3t h eh y b r i do f a n tc o l o n ya l g o r i t h mw i t ho t h e rb i o n i ca l g o r i t h m 2 0 3 3a n tc o l o n ya l g o r i t h mi nn e t w o r kr o u t i n gp r o b l e m 2 1 3 3 1a n tc o l o n ya l g o r i t h mi nd i s t r i b u t e dn e t w o r kr o 嘶n g 2 l 3 3 2a n tc o l o n ya l g o r i t h mi nm u l t i c o n s t r a j n tm u l t i c a s tr o u t i n g 2 2 3 3 3a n tc o l o n ya l g o r i t h mi nm o b i l ea dh o cn e t w o r k 2 2 3 4s u m m a r y ：! ：； c h a p t e r4a n tc o l o n yo p t i m i z a t i o nf o ra g g r e g a t e dm u l t i c a s t 2 4 4 11 1 1 en p cp r o v e m e n to f a g g r e g a t e dm u l t i c a s t 2 4 4 2t h eb a s i ci d e ao f a c o a m 2 5 4 2 1t r e es e l e c t i o n 2 7 4 2 2w 萌g h to f a g g r e g a t e dt r e e 2 7 4 2 3 h eo f t r e es e l e c t i o n 2 8 4 2 4p h e r o m o n eu p d a t e ：1 8 山东大学硕十学位论文 4 2 5c o n v e r g e n c ej u d g m e n t 2 9 4 3o p e r a t i o nf l o wo f a c o a m 2 9 4 3 1c a n d i d a t et r e eg e n e r a t i o n 3 0 4 3 2t r e es e l e c t i o n ：；1 4 3 3g r o u p t 0 t r e em a t c h i n g 3 2 4 4s i m u l a t i o na n da n a l y s i s 3 3 4 4 1s i m u l a t i o ns e t t i n g 3 3 4 4 2a n a l y s i so fs i m u l a t i o nr e s u l t 3 4 4 5s u m m a r y 3 7 c h a p t e r5c l u s t e r i n gf o ra g g r e g a t e dm u l t i c a s tb ya n tc o l o n yo p t i m i z a t i o n 3 8 5 1t i m ec o m p l e x i t ya n a l y s i so ft r a d i t i o n a la g g r e g a t e dm u l t i c a s t 38 5 2c l u s t e r i n gi n t r o d u c t i o n 4 0 5 3t h eb a s i ci d e ao f c a m a c o 4 l 5 3 1m a t h e m a t i c a lm o d e lo f c l u s t e r i n gf o r a g g r e g a t e dm u l t i c a s t 4 2 5 3 2s i m i l a rd e g r e e 4 3 5 3 3c a n d i d a t eg r o u ps e to fs a m ec l u s t e r i n ga n dp o t e n t i a l u e 4 3 5 3 4s e l e c t i o no fs a m ec l u s t e r i n g 4 5 5 3 5v m u eo f c l u s t e r i n gr e s u l t 4 7 5 3 6p h e r o m o n eu p d a t e 4 8 5 4o p e r a t i o nf l o wo f c a m a c o 4 9 5 5t i m ec o m p l e x i t ya n a l y s i s 5 0 5 6s i m u l a t i o na n da n a l y s i s 5 1 5 6 1s i m u l a t i o ns e t t i n g 5 l 5 6 2a n a l y s i so fs i m u l a t i o nr e s u h 5 2 5 7s u m m a r y 5 6 c h a p t e r6c o n c l u s i o na n de x p e c t a t i o n 5 7 6 1c o n c l u s i o n 5 7 6 2e x p e c t a t i o n 5 8 r e f e r e n c e s 5 9 a c k n o w l e d e g m e n t s 6 4 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 6 5 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 6 6 广 i ii 东大学硕十学位论文 摘要 伴随着互联网的高速发展，涌现了大量的大规模多用户应用，如视频会议、 远程教育、分布式交互仿真等。这些应用的出现带来了带宽的急剧消耗和网络拥 塞等问题，而p 组播是有效支持这些应用的重要技术。 在传统组播中，组播组数据由一棵覆盖所有组成员的组播树进行转发，树上 路由器必须保存每一个组播组的转发状态。当大量组播组并存于网络时，数量庞 大的转发状态表占用了大量内存资源并且减缓了组播地址查询过程。同时，大量 控制开销用于维持大规模并存的组播树，这些都导致网络性能急剧下降。这就是 组播状态可扩展问题，该问题已成为p 组播大规模应用的重要瓶颈。 由u c l a 网络实验室提出的聚合组播使域内的多个组播组共用同一棵聚合 树来转发组播数据包。组播组的聚合使得网络中组播树的数量减少，路由器需要 维持的组播转发状态和传递控制信息带来的控制开销都大大降低。其核心思想是 不超过带宽浪费门限的情况下最小化聚合树的数量，使之覆盖所有组播组。传统 的聚合组播包括三个主要步骤，分别是候选树生成，树选择和组树匹配。其数学 思想本质是最小集合覆盖问题，是一个n p c 问题。 本文在对传统聚合组播模型深入研究的基础上，提出了优化组播状态可扩展 问题的两种方案g 基于蚁群优化的聚合组播算法和基于聚类聚合组播的蚁群优化 算法。 1 基于蚁群优化的聚合组播算法是针对传统聚合组播算法容易收敛到局部 最优解，因此难以达到理想的聚合效果的问题而提出的聚合组播解决方案。该方 案对集合覆盖问题进行了适当的转化，通过蚁群算法的自组织、分布式协作产生 的集体的正反馈效果，使得聚合效果不断向全局最优解进化。 试验结果表明，基于蚁群优化的聚合组播与传统的贪婪算法所得到的局部最 优解和拉格朗日松弛算法通过放宽约束条件得到近似的优解相比在聚合度、状态 转发降低率这些反应聚合组播效果的优劣的指标上存在明显的优势。 2 基于聚类聚合组播的蚁群优化算法是针对大规模网络拓扑环境情况下或 允许大带宽浪费情况下，可扩展链路数增多，传统聚合组播算法的时间复杂度呈 山东大学硕十学位论文 指数增长的问题而提出的新的聚合组播方案。该方案在新的基于约束条件聚类问 题的数学模型基础上，依据聚合组播问题的特性并融合了蚁群算法的优化方法， 在各项变量及参数综合影响下优化聚合组播的聚类结果。 实验结果表明，在可扩展链路较大的实验环境下，基于聚类聚合组播的蚁群 一 优化算法与传统聚合组播算法相比有着明显的时间性能优势。 关键词：聚合组播；蚁群算法；贪婪算法；聚类思想；最小集合覆盖； u ， 一 w i t ht h er a p i dd e v e l o p m e n to ft h ei n t e r n e t , m a n yl a r g es c a l em u l t i u s e r a p p l i c a t i o n sa r ee m e r g e d ，s u c ha sv i d e oc o n f e r e n c e ，r e m o t ee d u c a t i o n ，d i s t r i b u t e d i n t e r a c t i v es i m u l a t i o n t h ee m e r g e n c eo ft h e s ea p p l i c a t i o n sh a sb r o u g h tas h a r p b a n d w i d t hc o n s u m p t i o na n dn e t w o r kc o n g e s t i o na n ds oo n i pm u l t i c a s ti sa l l i m p o r t a n tm e c h a n i s mw h i c hc a ns u p p o nt h e s ea p p l i c a t i o n se 伍c i e n t l y i nt r a d i t i o n a li pm u l t i c a s t ，d a t af o rag i v e ng r o u pi sf o r w a r d e dt h r o u g hat r e e s t r u c t u r ec o v e r i n gt h em e m b e r so ft h i sg r o u p t h eo n t r e er e u t e r sm u s tm a i n t a i na p e r - g r o u pf o r w a r d i n gs t a t e w h e nt h e r ea r el a r g en u m b e r so fm u l t i c a s tg r o u p si nt h e n e t w o r k ，l a r g ef o r w a r d i n gt a b l e si n d u c el a r g em e m o r yr e q u i r e m e n t sa n ds l o wd o w n t h ea d d r e s sl o o k - u pp r o c e s s m o r e o v e r ，m a i n t a i n i n gm u l t i c a s tt r e e sr e q u i r e s 锄 e x c h a n g eo fc e n t r e lm e s s a g e sc a u s i n ga ni m p o r t a n to v e r h e a d h e n c e ，t h en e t w o r k p e r f o r m a n c ew i l lb et r e m e n d o u s l yd e g r a d e d t h i si s s u ei sr e f e f r e dt o 嬲m u l t i c a s t s t a t es c a l a b i l i t yp r o b l e m 1 1 1 es t a t es c a l a b i l i t yp r o b l e mh a sr e s t r i c t e dt h ea p p l i c a t i o n o fs e a l a b l em u l t i c a s t a g g r e g a t e dm u l t i c a s ti sar e c e n ta p p r o a c hp r o p o s e db yt h eu c l an e t w o r k l a b o r a t o r y i nt h i sa p p r o a c h ，m u l t i p l eg r o u p ss h a r et h es a m ea g g r e g a t e dt r e ew i t h i na d o m a i n w i t hm u l t i c a s tt r e ea g g r e g a t i o n ，f e w e rt r e e sa r em a i n t a i n e dw h i c ha m o u n t st o r e d u c eb e t ht h en u m b e ro ff o r w a r d i n gs t a t e si nr e u t e r sa n dt h eo v e r h e a di n d u c e db y c e n t r e lm e s s a g e s t h ec o r ei d e ao fa g g r e g a t e dm u l t i c a s ti st om i n i m i z et h en u m b e ro f m u l t i c a s tt r e e sw i t h o u tv i o l a t i n gag i v e nb a n d w i d t hw a s t et h r e s h o l d 朗a b l i n gt h e s e t r e e st oc o v e ra l lt h eg r o u p s t h et r a d i t i o n a la g g r e g a t e dm u l t i c a s tw a sd i v i d e dt h e p r o b l e mi n t ot h r e es u b p r o b l e m s ，n a m e l y ，c a n d i d a t et r e eg e n e r a t i o n ，t r e es e l e c t i o na n d g r o u p t o - t r e em a p p i n g t h et r e es e l e c t i o ni sa t t r i b u t e dt om i n i m a ls e tc o v e rp r o b l e m , w h i c hi s 锄n p - c o m p l e t ep r o b l e m i nt h i sp a p e lt w od i f f e r e n ta l g o r i t h m sa r ep r o p o s e dt os o l v et h ef o r w a r d i n gs t a t e s p r o b l e mo fm u l t i c a s ta f t e ra c h i e v i n ge x t e n s i v ea n di n t e n s i v er e s e a r c ho nt h ea r e ao f t r a d i t i o n a la g g r e g a t e dm o d e lo fm u l t i c a s t ：o n es c h o m ei sa n t c o l o n yo p t i m i z a t i o nf o r a g g r e g a t e dm u l t i c a s tt h eo t h e ri sc l u s t e r i n gf o ra g g r e g a t e dm u l t i c a s tb ya n tc o l o n y o p t i m i z a t i o n 1 t r a d i t i o n a la g g r e g a t e dm u l t i c a s ta l g o r i t h m sa r ee a s yt oc o n v e r g et ot h el o c a l o p t i m a ls o l u t i o na n dc o u l dn o tr e a c hi d e a la g g r e g a t i o np e r f o r m a n c e a i m i n ga tt h a t p r o b l e m ，a n tc o l o n yo p t i m i z a t i o nf o ra g g r e g a t e dm u l t i c a s ti sp r o p o s e d w h i c h p r o v i d e sa p p r o p r i a t e t r a n s f c i r m a t i o no n s e t - c o v e r i n gp r o b l e m , a n d e v o l v e s a g g r e g a t i o np e r f o r m a n c et og l o b a lo p t im a ls o l u t i o nb yu s i n gt h ep o s i t i v e - f e e d b a c k g e n e r a t e db yt h es e l f - o r g a n i z e da n dd i s t r i b u t e dc o o p e r a t i o no fa c o s i m u l a t i o nr e s u l t sd e m o n s t r a t et h a tc o m p a r e dt ot h el o e a lo p t i m a ls o l u t i o n g a i n e db yt r a d i t i o n a lg r e e d ya l g o r i t h ma n da p p r o x i m a t eo p t i m a ls o l u t i o ng a i n e db y l a g r a n g er e l a x a t i o n ，t h ea n tc o l o n yo p t i m i z a t i o nf o ra g g r e g a t e dm u l t i c a s ta c h i e v e s d i s t i n c ta d v a n t a g eo nc r i t e r i as u c ha sa g g r e g a t i o nd e g r e ea n ds t a t er e d u c t i o nr a t i o 2 w h e ni nt h ec o n d i t i o no fl a r g es c a l en e t w o r k t o p o l o g yo rh i g hb a n d w i d t h i i i 山东大学硕十学位论文 w a s t eb a n d w i d t h ，t h en u m b e ro fe x p a n d a b l el i n k sa r eg r e a t l yi n c r e a s e d ，a n dt h et i m e c o m p l e x i t yo ft r a d i t i o n a la g g r e g a t e dm u l t i c a s ta l g o r i t h m sg r o w sr e l a t i v e l y c l u s t e r i n g f o ra g g r e g a t e dm u l t i c a s tb ya n tc o l o n yo p t i m i z a t i o ni san e w l yp r o p o s e ds o l u t i o n ， w h i c hi sb a s e do nan e wm o d e lo fc o n s t r a i n e dc l u s t e r i n g ，c o m b i n e sa g g r e g a t e d m u l t i c a s tw i t ha n tc o l o n yo p t i m i z a t i o n ，a n do p t i m i z e sc l u s t e r i n gp e r f o r m a n c ef o r a g g r e g a t e dm u l t i c a s tr e c e i v i n gt h ec o m p r e h e n s i v ee f f e c t so fd i f f e r e n tv a r i a b l e sa n d p a r a m e t e r s s i m u l a t i o nr e s u l t sd e m o n s t r a t et h a tw i t hl a r g en u m b e ro fe x p a n d a b l el i n k s ， c l u s t e r i n gf o ra g g r e g a t e dm u l t i c a s tb ya n tc o l o n yo p t i m i z a t i o nh a so b v i o u s l y a d v a n t a g e i np r o g r a me x e c u t i o nt i m ec o m p a r e dt ot r a d i t i o n a la l g o r i t h m k e yw o r d s ：a g g r e g a t e dm u l t i c a s t ；a n tc o l o n ya l g o r i t h m ；g r e e d ya l g o r i t h m ； c l u s t e r i n gt h o u g h t ；m i n i m a ls e tc o v e r ； i v 一 ，一 组播作为一种有效的支持多点通信的机制，自d e e r i n g 博士【1 1 1 9 8 8 年提出以 来一直是人们的研究热点。尽管经过2 0 多年的理论研究和工程实践，研究人员 在组播实现机制上取得了丰硕的研究成果，并且提出了一系列组播协议，然而组 播始终没能在i n t e r n e t 上大规模部署，其中状态可扩展性问题1 2 l 是阻碍组播 部署的重要技术障碍之一。 在传统的m 组播中，组播组的数据通过一棵覆盖全体组成员的树结构进行 数据转发。每一个组播组对应着一棵组播转发树，组播组数据包在树的分支节点 处复制，在每条链路上仅转发一次，组播树上节点记录并维持每一个组的转发状 态。通过这种机制可以使全网范围内组播分组复制的数量最少，因而大大提高了 组播转发效率，降低了组播带宽消耗并且缓解了网络拥塞。但是，转发节点上的 转发状态会随着经过它的组播组的数量的增加而线性增长。 当互联网上并行的组播组的数量规模增大，特别是在存在大量并行组播组会 话的骨干网，路由器上保持的转发状态将非常庞大。庞大的转发表在导致大量的 内存消耗的同时也大大降低了每个分组转发地址查找的速度，转发过程随之减 缓，同时大量组播树的建立和维护带来大量控制开销，消耗了路由器大量的存储 空间和c p u 资源。这就是组播状态可扩展问题，它严重影响了网络性能，已经 成为组播技术发展的瓶颈。 1 2 国内外研究现状 针对组播可扩展问题国内j , i - 众多学者进行了大量的相关研究，并提出了一系 列的解决方案，这些方案大体可被划分为以下三种类型：1 在全部或部分路 由器上抑制组播状态的方案；2 在路由器上聚合组播状态的方案：3 聚合组播 方案。 山东大学硕十学位论文 1 2 1 路由器抑制组播状态方案 路由器抑制组播状态方案可以进一步分为两个子类：1 在非分支路由器中 消除组播状态：2 在路由器中使用新的组播框架完全消除组播状态。 第一种子类的例子如文献3 弓1 中所提出的方案。这些方案在非分支路由器( 即 路由器只有一个出口来为组播组转发接收到的组播数据包) 中消除组播状态。文 献【3 】中，t i a n 和n e u f e l d 提出对非分支路径动态建立通道来减少状态转发。然而 该方案需要设计复杂的方法来辨别非分支路由器。文献【4 】中，s t o i c a 等设计了一 个叫做r e u n i t e 的协议，组播状态只在分支节点设立，包的转发则基于单播路 径。文献【5 j 为了适应特定源的抽象通道对r e u n i t e 方案进行了调整以简化组播 地址分配。应注意到的是，所有上述方案基于一个假设：网络中存在大量稀疏的 组。并且它们都只考虑到了减少路由器上的组播状态而没有考虑解决控制开销问 题。 第二种子类是建立新的组播框架，在路由器上完全消除组播状态如应用层组 播或x c a s t 。应用层组播的组播功能( 如组管理和数据复制) 完全部署在终端主 机上，因此它对于路由器来说是透明的。这个方案的相关文献可以分为两类：结 构化的 6 1 和非结构化的7 1 。结构化的应用层组播方案作用于基于分布式哈希表 ( d h t ) 的覆盖网络，同时在覆盖网络上建立组播转发树。非结构化方案中，自组 织的组播树是建立在显示或隐式的底层m e s h 覆盖网上。应用层组播是i p 组播的 一个有用的替代以促进组播更大范围的部署。然而，值得注意的是，没有中间路 由器的明确支持，这些方案的组播效率有所下降。非结构化方案对于大规模的如 网络电视这样拥有百万个组成员的应用同样是困难的，因为这些应用层组播协议 需要发现并维持所有或几乎所有组成员。 x c a s t 提出在组播包中对一系列的目的地址进行编码，这样路由器不需要维 持组的状态信息。然而，它将导致每一个路由器在转发数据包时产生额外运算开 销并且由于需要传输更大的数据包导致了更多的带宽浪费。因此它只适合于小规 模组应用。 最近，文献8 1 中y a n g 等人融合了x c a s t 和在非分支节点减少组播状态方案3 弓1 的好处，设计出一种方案，在路由器上进行灵活的状态分配。这个方案相对于 x c a s t 对于组播组的大小有着更好的扩展性，并且也平衡了路由器中的状态分布。 2 ， 一 i i i 东大学硕十学位论文 但与以上所述的状态抑制方法相似，这个方案也没有考虑到控制开销问题。 路由器聚合组播状态方案 第二类方案通过状态聚合来减少状态，例如文献【州1 1 。t h a l e r 和h a n d l e , s , 在 文献【l i 】中提出了使用一个输入聋5 i 出过滤模型来分析转发状态的聚合。r a d o s