一种基于遗传算法的组播路由选择方法.pdf

《一种基于遗传算法的组播路由选择方法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2001年10月东北大学学报（自然科学版）Oct.2001第22卷第5期JournalofNortheasternuniversity（NaturalScience）Vol.22，No.5一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一文章编号：1005-3026（2001）05-0513-04一种基于遗传算法的组播路由选择方法王新红，杜荔，王光兴（东北大学信息科学与工程学院，辽宁沈阳110004）摘要：提出了一种基于遗传算法的组播路由选择方法·该方法首先寻找所有满足时延限制条件的路径，组成备选路径集，然后以代价

2、最小为优化准则，在备选路径集中采用遗传算法求解最优解·为保证算法的收敛速度快，遗传算法的交叉操作使用了相同链路保留的方法·最后，进行了仿真实验，并与其他算法做了比较·实验表明，该算法收敛速度快，可靠性高，能够满足多媒体网络对实时性的要求·尤其是在网络规模较大时，本算法可大大减小路由计算时间·关键词：组播；路由；遗传算法；时延限制；最小代价；GoS（服务质量）中图分类号：TP391文献标识码：A组播（multicast）是一种由源节点可以同时向本文考虑一个源节点到多个目的节点的组播多个目的节点发送信息的通信方式·大量多媒体问题·假设信息由源节点S6V传送到一组目的节应用如电视会议、远程教

3、学等，需要网络支持组播点集DgV-｛S｝·组播树T=（V，E），其中VTTT功能·目前已经提出了多种组播算法，其中最常见gV，ETgE，T中存在由源节点S到每个目的节的是求解斯坦利最小树（MST）的方法［1，2］·这一点d6D的通路PT（S，d）·组播树T的代价定义问题被证明是NP完全问题，提出了很多启发式为C（T）=nC（e）·组播树T的时延为由［1］［2］［3］e6E）算法，如KMB算法、MPH算法、SPH算法T源节点S到各目的节点路径时延的最大值，即等·在斯坦利问题中增加GoS限制条件，提出了受限斯坦利最小树的方法·文献［4，5］给出了引入D（T）=max（ne6P（S，d）D（

4、e），d6D）·T时延限制的斯坦利树的启发式算法·除了启发式假定组播树的最大时延限制为!，则构建的算法外，文献［6］提出采用遗传算法解决时延受限组播树应满足如下条件：的组播路由问题·然而，文献［6］中的算法在父代·VTgV&ETgE交叉操作后生成的斯坦利树不连续，需要进行修·S6VT&DgVT补，实现起来有一定的难度·文献［7］也提出了一·D（T）＜!种遗传算法的解决方案，然而他们采用单点交叉如果S为所有满足以上条件的组播树的集算法，收敛速度不尽人意·好的路由算法应该具有合，则要寻找的组播树T为C（T）=min（C（TS），简单和快速的特点·为此，本文将提出一种采用遗TS6S）·本文的

5、目的也就是在满足时延限制条件传算法的实现简单、收敛速度快的组播路由算法·下寻找代价最小的组播树，即在D（T）＜!的情况下，构建使得C（T）最小的组播树·1组播路由问题的描述2基于遗传算法的组播路由选择计算机网络可以表示为有向赋权图G（V，方法E），其中V=｛O1，O2，⋯，ON｝是图G中节点的集合；E=｛e1，e2，⋯，eL｝是边的集合·E上每条遗传算法是一种公认的解决优化问题的有效从i到j的边都定义了两个正实数加权值（C，工具［8］i，j·它模拟自然界的生物进化过程，通过“优Di，j），Ci，j为由节点i到节点j传送信息的代价；胜劣汰”法则保留优秀后代·作为一种并行算法，Di，j为由

6、i到j传送信息的时延·它具有快捷、简便、容错性强等特点，在解决优化收稿日期：2000-10-31基金项目：国家自然科学基金资助项目（69973011）·作者简介：王新红（1974-），女，河北保定人，东北大学博士研究生；王光兴（1937-），男，辽宁沈阳人，东北大学教授，博士生导师·516东北大学学报（自然科学版）第22卷Communications，1998，21（2）：126-132.［8］陈国良，王煦法，庄镇泉，等·遗传算法及其应用［M］·北［7］石坚，邹玲，董天临，等·遗传算法在组播路由选择中的应用京：人民邮电出版社，1996.75-87·［J］·电子学报，2000，28（5）

7、：88-89·（ChengL，WangXF，ZhuangZ，etal.geneticalgorithm（ShiJ，ZouL，DongTL，etal.Theapplicationofgeneticanditsapplication［M］.Beijing：People’sPostsandalgorithminmulticastrouting［J］.ACTAElectronicSinica，TelecommunicationsPress，1996.7