一种基于遗传禁忌昆合策略的时延约束组播路由算法

《一种基于遗传禁忌昆合策略的时延约束组播路由算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第19卷第6期2010年12月运筹与管理OPERATl0NSRESEARCHANDMANAGEMENTSCIENCEV01．19．No．6Dec．2010一种基于遗传禁忌混合策略的时延约束组播路由算法黄林1’2(1．中国计最学院数学系，浙江杭州3lool8；2．大连理工大学应用数学系．辽宁大连116023)摘要：提出了一种基于遗传算法和禁忌搜索法相结合混合策略的时延约束最小代价组播路由算法(GATSA)。该算法利用Dijkstra第^最短路径算法找出源节点到每一个目的节点满足最大时延限制的路径，通过遗传禁忌

2、混合策略的选择、交叉与变异等操作，求出满足条件的组播树。仿真实验结果表明本算法性能和算法性能稳定，其代价性能接近目前性能最好的BsMA算法，并具有快速，低时延的特。关键词：组播；遗传算法；禁忌搜索法；时延约束中图分类号：F224．3文章标识码：A文章编号：1007．3221(20lO)06．0157．08AnAlgorithmBasedOntheGeneticTabuHybridStrategyfOrDelay-COnstrainedMultjcastROutjngHUANGLinl·2(1．D印口疗me，

3、lI矿朋么琥em口￡妇。C^讯口脚口ngun觇乃蚵舶ng咖Du，310018；2．Dep口厅mem矿讹咖em口t洳，D口脑，l妇泌船毋可死c^nojo盯阢^口n。1l6023)Abstract：Annovelalgorithmba8edonthehrbridstrategyofthegeneticalgorithmandthetabusearchmethodfordelay·constrainedleast-costmultica8tmuting(GATSA)isproposedtosolvedelay-c

4、onstminedmultic躺troutingproblem．ThealgorithmusesDijkstraKthshortestpathalgorithmto6earchoutpathsf如mthe80urcetoalldesti·nationnodess8ti6fyingthemaximamdelaycostraint，byoperationsofselection、cr08soverandmumationinthegenetictabuhybrid8strategy，findsthemultica

5、stree8ati8fyingconstraint．Simulation88howth8tperfbmanceofthealgorithmissteady，anditscosti8c108etoBSMAalgorithmwhoseperfbmancei8bestatpresent．Finally，thealgorithmh88characteristicsofquicknessandlowerdelay．KeywOrd8：multicastmutng；eneticalorithm；tabusearchmet

6、hod；delayconstmint0引言组播是一种将信息从源节点同时发送到网络中多个目的节点的通信形式，这是网络中大量业务存在着点到多点通信需求的必然结果。许多对时延敏感的新兴多媒体业务，如电视会议、视频点播等包括多个参与者，这些业务不仅要有严格的端到端时延限制，还要使用大量的网络资源。从路由的角度来说，这些需求可以转化为决定一棵组播树的问题，而从全局观点优化网络资源可看作是优化组播树的总体代价，因此，最小化组播树的时延和代价成为有效支持这些新兴业务的两个最重要的目标。寻找满足时延约束的最小代价组播路由问

7、题可以形式化为约束的Steiner树问题，它作为一个NP完全问题，一直是路由问题中的研究难点。在Internet上广泛使用的基于链路状态的OSPF协议中⋯，每个收稿日期：2007一04-25作者简介：黄林(1979·)，男．博士研究生，研究方向是网络优化。158运筹与管理2010年第19卷OSPF路由器都维护一个描述自治系统拓扑结构的数据库，根据这个数据库利用SPF算法通过构建最短路径树(SPT)来计算出路由表．但是sPF算法只能构造连接源节点和每个目的节点的最小时延树，因此，它只能找到一棵满足时延约束的生

8、成树，而无法对树的代价进行优化。第一个满足端到端时延约束的组播路由启发式算法由V．P．Kompella等提出KPP算法心1。其做法扩展了用于求解无约束Steiner树问题的KMB算法阳】，首先求出任意两网络节点间满足时延约束的最小代价路径，并以此构建封闭图，然然后以基于最小生成树的启发式算法产生路由树。Q．zhu等人提出的BsMA算法H1则采用一个切实可行的搜索优化方法，它首先使用Dijkstm最短路算法"o求出