基于多目标遗传算法的多播服务质量路由优化.pdfVIP

第41卷 第7期 计算机研 究与发展 Vo1．41．No．7 2004年7月 JOURNAL oF 0DM[PUTER RESEARCH AND DEVELoPM匮NT July 2004 基于多目标遗传算法的多播服务质量路由优化 崔逊学 林 闯 (南京大学计算机软件新技术国家重点实验室 南京 210093) (清华大学计算机科学与技术系 北京 100084) (cuixunxue@163．net) 摘 要 互联网不断增长的多媒体应用引发人们研究如何满足这些应用的服务质量(QoS)约束，并导致提出了一些基 于服务质量的体系结构．目前网络中多主机之间的多播通信一般需要严格的多个QoS保证．首先将满足不同约束的多 播路由选择过程转化为一个多目标优化问题，然后使用一种基于多目标遗传算法的新型多播树计算方法，同时优化时 延、丢包率和带宽利用率等不同的参数．实验结果表明，该方法能在有限进化代数内产生一组有效的非劣多播路由解，结 合多目标优化的遗传算法克服了单目标路由优化的缺陷． 关键词 多目标优化；遗传算法；多播路由；服务质量 中图法分类号 TP393 Multicast QoS Routing Optimization Based on Multiobj ective Genetic Algorithm CUI Xun—Xue ， and LIN Chuang2 (State Key Laboratoryfor Novel Softzoare Technology，Nanjing University，Nanjing 210093) (Department ofComputer Science and Technology，Tsinghu；a University，Beijing 100084) Abstract The continuous demand for using multimedia applications over the Internet has triggered a spur of research on how to satisfy the quality of service(QoS)requirements of these applications．These efforts resulted in the proposals of several QoS-based frameworks．At present，multicast communications among multiple hosts in networks usually require multiple strict quality of service guarantees．In this paper，a selection process of determining multicast routes satisfying the different QoS constraints is converted into a multiobjective optimization problem．Then a novel multicast tree computation algorithm is provided，which optimizes several QoS parameters on delay，loss ratio and bandwidth utilization simultaneously．Simulation results show that this algorithm is effectively capable of obtaining a set of non—dominated multicast mutes within a finite evolutionary generation，which takes advantage of multiobjective optimization and overcomes the weakness of multieast routing with a single objective． Key words multiobjective optimization；genetic algorithm ；multi