首页 | 本学科首页   官方微博 | 高级检索  
     

基于启发式遗传算法的QoS组播路由问题求解
引用本文:王征应,石冰心.基于启发式遗传算法的QoS组播路由问题求解[J].计算机学报,2001,24(1):55-61.
作者姓名:王征应  石冰心
作者单位:华中理工大学电子与信息工程系,
摘    要:研究了带宽、延时抖动和包丢失率约束以及费用最小的QoS组播路由问题,并提出一种启发式遗传算法。该算法有以下特点:(1)预处理机制;(2)树结构编码;(3)启发式交叉策略;(4)指导性变异过程,最后通过仿真实验证明该算法快速有效。

关 键 词:服务质量  组播路由  启发式遗传算法  计算机网络  问题求解  QoS
修稿时间:2000年3月17日

Solving QoS Multicast Routing Problem Based on Heuristic Genetic Algorithm
WANG Zheng,Ying,SHI Bing,Xin.Solving QoS Multicast Routing Problem Based on Heuristic Genetic Algorithm[J].Chinese Journal of Computers,2001,24(1):55-61.
Authors:WANG Zheng  Ying  SHI Bing  Xin
Abstract:In this paper, we study the bandwidth, delay, delay jitter, and packet loss constrained least cost multicast routing problem which is known to be NP complete, and present a heuristic genetic algorithm to solve the problem. Firstly, the links with a bandwidth less than the bandwidth requirement are removed, thus the remained links in the refined graph must satisfy the bandwidth constraint. Then the heuristic genetic algorithm is adopted to solve the minimal multicast tree with delay constraint. The proposed genetic algorithm has the following characteristics: (1) Tree structure coding scheme, by which we can use any data structure of the tree to describe the chromosome structure, and omits the coding and decoding process. (2) Elitist selection model, by which we first select the optimal individuals and directly copy them to the next generation and then select the rest individuals by the proportional model. (3) Heuristic crossover operation, which first selects links with same parent and copy them to the children directly, and then connects the separate sub trees to form a multicast tree using the least delay paths if neither parent satisfies the delay constraint, or the least cost ones if either parent satisfies the delay constraint. (4) Instructional mutation operations, by which the mutation procedure first randomly selects a subset of nodes according to the mutation probability, and then breaks the multicast tree into some separate sub trees by removing all the links that are incident to the selected nodes. Finally it re connects those separate sub trees into a new multicast tree by randomly selecting the least delay or the least cost paths between them. Simulations have verified that this algorithm is efficient and effective.
Keywords:quality of service  multicast routing  heuristic  genetic algorithm
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号