文档介绍：华中科技大学
硕士学位论文
基于遗传算法的Qos路由选择策略研究
姓名:朱冠宇
申请学位级别:硕士
专业:系统分析与集成
指导教师:王乘
20040401
摘要
随着的迅速普及发展传统的所能提供的尽力而为的服务已
经不能满足不断涌现的新应用对 Qos 服务质量的要求虽然已提出一些为这些应
用提供 Qos 保障的模型和机制但它们的运行基础是已知满足 Qos 约束的分组转发路
径传统的基于单一度量的路由算法对求解满足 Qos 约束的路径的问题无能为力
必须提出新的考虑网络 Qos 特性的路由选择策略即 Qos 路由
已经证明 Qos 路由是 NP 完全问题遗传算法对求解该类问题比较有效本文采
用遗传算法对 Qos 单播路由 Qos 多播路由两个问题作了一些探索性研究文中针
对这两个问题分别提出了有效的编码方案并以编码方案为基础完成了求解 Qos
路由的遗传算法的构建工作本文在以下方面有所创新
1 为求解 Qos 单播路由问题的遗传算法提出一种一维二进制编码方案并针
对该编码方案提出了两种可行的个体解码思想采用该编码方案编码的个体
可有效避免路由环遗传算法的交叉变异算子实现简单
2 在求解 Qos 多播路由问题时考虑了路由器转发能力的限制文中为求解
Qos 多播路由的遗传算法提出了二维矩阵编码方案采用该编码方案的个体
在包含连接信息的同时还直观显示了组播树中结点度的信息非常便于判
断路由器是否满足转发能力限制
3 求解多播路由的遗传算法采用了保持父代个体相同链路的交叉策略在交叉
运算过程中本文提出的编码方案便于寻找相同链路
在研究过程中以 VC6 为开发工具实现了网络拓扑生成算法和求解两类 Qos
路由问题的遗传算法经试算比较算法性能良好收敛速度较快最后对全文进
行总结提出了研究中的不足和对将来进一步研究的若干建议

关键字 Qos 路由遗传算法单播多播度约束二维编码

I
Abstract
As the rapid development of the , there are more and more new appplications
based on the . The traditional “Best Effort” service that afforded by the can’t
satisfy those applications’ demands of QoS. Although some models and mechanisms have
been proposed to guarantee the QoS, the foundation of their implement is the QoS constraint
satisified packet transmit path. So new, QoS characteristic considered routing algorithm is
discussed here.
Qos routing has been proven to be a plete algorithm is good
for solve plete this paper,the algorithm of Qos routing with
multiconstraint using ic algorithm for unicast and multicast is discussed. In this paper,
we innovate in the following points:
(1) An effective coding method is adopted,and two operators of decoding are put
forward for solving encoding and decoding mechanism can avoid
operator of cross and mutation can be implement easily.
(2) The paper considers the router’s ability of transmitting when design the QoS
multicast strategy. It issues the 2-dimensional coding method for solving the QoS
mu