资源描述：
《改进人工鱼群算法及其在qos组播路由问题中的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、广西民族大学学报(自然科学版)第16卷第1期JOURNALOFGUANGXIUNIVERSITYFORNATIONALITIESVol.16No.12010年2月(NaturalScienceEdition)Feb.2010改进人工鱼群算法及其在QoS组播路由问题中的应用*余高,何登旭,刘桂青(广西民族大学数学与计算机科学学院,广西南宁530006)摘要:提出了一个基于蚁群算法和人工鱼群算法相结合的QoS组播路由算法.首先利用改进的Salama网络拓扑随机生成算法,随机生成一个网络拓扑图,再利用蚁群算法并行搜索的特点找出大
2、量满足约束条件的可行路径,创建备选路径集,最后使用人工鱼群算法在所创建的备选路径集中,通过执行觅食、聚群、追尾等行为求解最优组播树.仿真结果表明,该算法跟基本的鱼群算法相比有着更高更快的效率,能够尽快的找到最优的组播树,并具有更好的全局优化性能,适合于高速的、实时的多媒体传输网络.关键词:QoS组播路由问题;人工鱼群算法;蚁群算法中图分类号:TP183文献标识码:A文章编号:1673-8462(2010)01-0058-050引言为了提供更好的网络服务,研究人员都在试图寻找一个最优的组播树.这是多约束QoS路由问题,已计算机技术和通信技术的发展推动了计算机互[2]经被证明是
3、一个NP完全问题,目前还没有很好的联网络(Internet)的发展,在网络速度和网络规模迅解决方法.本文尝试将人工鱼群算法与蚁群算法结速增长的同时,互联网所承担的业务也日益增多,除合,利用蚁群算法并行搜索和人工鱼群算法快速收敛了传统的业务之外,各类多媒体应用,如:语音通话、特点,提出了一种用来解决具有延时和带宽约束的视频通讯、远程教育、网上虚拟现实等应用也越来越QoS组播路由问题的改进算法.仿真结果表明,该算多.如何有效的为互联网用户提供各种多媒体应用是法跟基本的人工鱼群算法相比,具有更高更快的求解我们目前首要解决的一个棘手问题,其中包括带宽、效率,能尽快找到最优组播树.延迟(
4、时延)、费用、丢包率、延迟抖动、跳数等很多服务质量参数.网络带宽与网络速度依然是一个瓶颈问题,现有的尽力而为的服务显然已不能满足需1QoS组播路由问题的数学[1][3]要,因此,在目前有限的带宽资源条件下,研究如何模型满足应用的QoS要求(如:带宽、延时、延时抖动、丢QoS组播路由问题通常包含链路费用、延时、带包率、可靠性、安全性等)是现实而有意义的.宽、抖动延时、包丢失等QoS约束条件.然而,为了简*收稿日期:20091220.基金项目:广西民族大学研究生教育创新计划项目(gxun-chx2009090).作者简介:余高(1981),男(壮族),广西南宁人,广西民族
5、大学党委宣传部工程师,硕士研究生,主要研究方向:智能算法及其应用、计算机网络.582010年第1期)余高,何登旭,刘桂青改进人工鱼群算法及其在QoS组播路由问题中的应用化模型,本文仅仅考虑了组播树的费用、延时和带宽2基于人工鱼群一蚁群算法的限制,网络拓扑图如图1所示.QoS组播路由算法网络拓扑可以用一个无向赋权图G=(V,E)表2.1人工鱼群算法简介示(如图1所示),其中V=(v1,v2,!,vN)表示网络人工鱼群算法(artificialfishswarmalgorithm,节点集,N表示网络节点数;E=(e1,e2,!,eP)表示[4]AFSA)是近年来提出的
6、一种模拟鱼群行为的随机双向链路集,P表示网络链接数;s(s∀V)是组播的搜索方法,是群智能思想的一个具体应用.该算法通源节点,M(MV-{s})是组播传送经过的节点集;+过仿真鱼的觅食、聚群、追尾行为快速获得最优解.其d(d∀M)是组播的目的节点;R是一组实数.对于主要思想是:在水中,鱼试图跟踪其他大的鱼群发现任意链路ei∀E,在其上定义了三种度量:+食物,因此水中有大量食物聚集的地方才有大量的鱼费用函数:Cost(e):E#R+生存.人工鱼群算法就是基于这种特性.首先,它构建延时函数:Delay(e):E#R+一些人工鱼做为初始鱼群,每个人工鱼是关于某个问带宽函数:Band
7、with(e):E#R题的可选的解的解空间.仿真鱼的觅食、聚群、追尾行用T(s,M)表示组播树.源节点s到目的节点为使该算法获得优化.d(d∀M)的路径标识为PT(s,d),那么自从人工鱼群算法提出后,算法在解决函数优组播树的总的费用函数:[4,5]化、组合优化等问题上取得成功.最近,人工鱼群Cost(T(s,M))=∃Cost(e)e∀T(s,M)算法被用来解决网络路由优化问题.文献[6]提出了组播树在路径PT(s,d)上的延时:一个改进的人工鱼群算法去解决单播路由问题;文献Delay(P
