论文部分内容阅读
QoS(服务质量)多播路由问题已经成为网络领域中研究的重要课题。它是寻找带有约束条件的可行多播树解的NP-Complete问题。QoS约束可以分为连接约束(如带宽),路径约束(如点到点的延迟)以及树的约束(如延迟抖动)。总的来说,启发式算法常用于解决此类NP-Complete问题。许多遗传算法被用来解决这类问题。根据文献[2,3],Sun等人提出量子行为微粒群优化算法(QPSO)。在许多全局优化问题上该算法被证明是一种有效地解决方案,并且它不会遭遇到遗传算法所遭遇的一些问题。QPSO算法最初用于解决连续函数的优化问题。到目前为止,也很少用于解决离散的组合优化问题(COP)。本文的目的就是在于使用QPSO算法解决QoS多播路由问题。首先,研究QoS理念尤其是QoS路由算法问题。分析几种常用的QoS多播路由优化算法的原理和应用策略。并且,将这几种算法的特点进行比较。针对QoS约束特征,进一步研究了有约束的多目标优化问题。其次,构建QoS多播路由网络模型,采用罚函数处理约束条件。分别描述了遗传算法和遗传算法与禁忌搜索的混合算法(GA-TS)应用到QoS多播路由优化问题的实现过程。也描述了PSO算法求解QoS多播路由问题的实现过程,并且详细阐述了QPSO算法的实现方案。为了将PSO和QPSO算法应用于QoS多播路由优化问题,本文设计一种新的整数编码方案,将QoS多播路由优化问题转化为整数计算问题。最后,利用网络模型,本文测试了基于QPSO算法的路由优化算法。用于比较,在相同条件下使用PSO算法、GA算法以及GA-TS混合算法作了测试。计算机仿真结果表明QPSO算法在解决QoS多播路由问题方面要优于PSO算法、GA算法以及GA-TS混合算法,这主要表现在它的有效性和效率上。QPSO算法可以更有效地求得QoS多播路由问题的优化解,可靠性更高。