QoS约束路由问题的求解算法的设计与实现

QoS约束路由问题的求解算法的设计与实现

计算机科学与技术专业 2010级 xxx

指导教师 xxx

摘要

随着网络的快速增长以及新型实时业务的不断涌出，用户需要更好水平的网络服务质量 (QoS，Quality Of Service)。QoS路由作为解决网络服务质量问题的一项关键技术，决定着网络传输质量的好坏，并且具有重要的地位。

蚁群算法，是一种在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年提出，其灵感来源于蚂蚁在觅食过程中寻找觅食路径的行为。在蚁群算法中，采用了分布式正反馈并行机制，通过候选解组成的群体进化来寻求最优解，其易于较好的结合性以及较强的鲁棒性，使其成为国内外学者研究的热点。

本文主要研究了蚁群算法在Qos路由的应用，即求解多约束Qos路由问题的解决方案。在本文中，通过结合禁忌搜索技术，给出了适合求解多约束单播QoS路由问题以及多约束多播QoS路由问题的蚁群算法。此外，本文还给出了一个构造随机无向加权连通图的算法，用于模拟QoS路由问题。在此基础上，本文还给出了该算法在matlab平台上的实验结果。通过实验结果，可以发现，应用蚁群算法求解QoS路由问题能后获得不错的解决方案。最后，我们总结了该论文的主要成果以及优缺点，并给出了以后的研究方向。

关键词：Qos路由；蚁群算法；多约束；禁忌搜索