基于遗传算法的QoS组播路由优化研究-计算机应用技术专业论文.docx

A Thesis Submitted to Ningbo University for the Master’s Degree QoS Multicast Routing Optimization Research based on Genetic Algorithm Candidate：Peng Lu Supervisors：Professor He Jiaming Faculty of Electrical Engineering and Computer Science Ningbo University Ningbo 315211, Zhejiang P.R.CHINA June 15, 2015 独 创 性 声 明 本人郑重声明： 所呈交的论文是我个人在导 师指导下进行的研究 工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为 获得宁波大学或其他教育机构的学位或证书所使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明 并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 签名：___________ 日期：____________ 关于论文使用授权的声明 本人完全了解宁 波大学有关保留、使用学位 论文的规定，即：学 校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公 布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存 论文。 （保密的论文在解密后应遵循此规定） 签名： 导师签名： 日期： - - I - 宁波大学硕士学位论文 基于遗传算法的 QoS 组播路由优化研究 摘 要 随着 Internet 的出 现以 及迅猛 的发 展，越来 越多 的多媒 体应 用大量 涌现 而出， 例如 视频会 议、远 程视频 教学和 视频点 播等。 这些应 用虽然 都有着 不同的 形式， 但是 却都有 着一个 共性：对信 息传输 的高效 性都有 较高的 要求。为了 更好的 保证 这些 业务的 传输质 量，信息 在传输 过程中 需要满 足一些 特定的 要求，这就 是所谓 的 QoS(Quality of Service)问 题。多 约束 的 QoS 问 题已 经被 证明 是一 个 NP 难 问题 ， 而传 统的路 由协 议提供 的是一 种“尽力 而为 ”的服 务，无法 有效的 提供 QoS 保障。 为了 有效 满足 QoS 约束 条件 ，智能 算法 被用来 解决多 QoS 约束 的 NP 难问 题 ，而 在众 多智能 算法中，遗传 算法因 具有较 好的并 行性、全局 性和自 适应性 ，故在 解 决 NP 难问 题方面 拥有 较大的 优势。现在 已有很 多基 于遗传 算法的 多 QoS 约束 组 播路 由的研 究，但是 要将组 播路由 问题很 好的和 遗传算 法结合 在一起，有两 个难 点，第一 个就是 如何设 定种群 个体完 成编码 ，第二 个就是 如何设 置好的 适应度 函 数。好的 编码可 以无需 解码，并且 可以有 效地完 成交叉 和变异 操作；而遗 传算法 求 解 的 过 程 中 基 本 上 不 需 要 使 用 搜 索 解 空 间 的 任 何 知 识 和 其 他 辅 助 信 息 只 需 要 根据 适应度 函数值 来对个 体性能 进行评 价，并在 评价基 础上进 行遗传 操作直 到求 得解 。 关键词： 组播路由， 服务质量(QoS)， 遗传算法， 路由算法， 编码针对 以上问 题，本文 基于遗 传算 法循序 渐进的 分别研 究多 QoS 单播 路由、满 足时 延和带 宽约束 的组播 路由以 及多 QoS 组播 路由。最后 针对每 个问题 各提出 了 一个 改进的 遗传 算法，分别 解决了 满足 多 QoS 约束 的单播 路由 问题 、满足 时延和 带宽 约束的 组播路 由问题 以及满 足多 QoS 约束 的组播 路由问 题。其中 第一个 算法 主要 在设定 适应值 函数的 时候提 出了一 种创新 的惩罚 机制，第二 个算法 主要提 出 一种 创新的 编码方 式，而最 后一个 算法是 对前两 个算法 的一个 整合。对于 文章提 出的 算法分 别进行 仿真实 验，最 后可以 得出结 论：文 章提出 的算法 都是可 行的， 并且 通过与 现有提 出的遗 传算法 结果进 行比较，文章 算法在 收敛 关键词： 组播路由， 服务质量(QoS)， 遗传算法， 路由算法， 编码 关键词： 组播路由， 服务质量(QoS)， 遗传算法， 路由算法， 编码 基于遗传算法的 QoS 组播路由优化研究 QoS Multicast Routing Optimization Research based on Gene