基于改进蚁群算法的有线网络路由QoS研究

摘要

随着计算机网络应用多元化的发展，传统的尽力而为服务模型已不能满足网络中大量多媒体传输的需求，追求计算机网络服务质量(QoS)已成为网络发展的趋势。QoS路由选择问题是在网络中搜索路径，该路径各属性满足各种约束条件。已有学者证明，满足多约束条件下的路由选择是NPC问题，传统算法无法在有效的多项式时间内求解最优。
　　蚁群算法作为一种群智能搜索算法，能够有效的解决NPC问题。蚁群算法具有并行性、鲁棒性、易与其他算法相融合的优点，但同时也有收敛慢，易停滞的缺点。本论文第二，三章分别介绍计算机网络服务质量(QoS)的基本概念，蚁群算法原理及一些改进方式。第四章介绍了基于新鲜度的分工蚁群算法，即将蚁群按照搜索状况自动分成两个不同分工的种群，其中一种分工的蚁群以一定的概率按照边的新鲜度进行状态转移，以减弱过强的正反馈性，降低算法陷入停滞状态的概率；另一种分工的蚁群则按照边上的信息素进行状态转移，加强蚁群中搜索经验的交流。各边上信息素更新时，对组成较优解的边上信息素进行强化，使蚂蚁在接下来的搜索循环中趋向于优质解。
　　第五章介绍了基于自主行为的蚁群算法，每只蚂蚁将保存自己搜索到的最优解与最差解。蚂蚁在进行状态转移时，将按上次循环搜索的结果与自身搜索的最优解与最差解相比较，自主地决定本次搜索循环蚂蚁转移的策略。上次循环搜索得到的解优于最优解的蚂蚁将在本次及接下来一定次数的搜索循环内在该最优解附近搜索，力图获取更优质的解；上次循环搜索的解差于最差解的蚂蚁在本次循环搜索进行状态转移时，将避免选择组成最差解的边，以改善解的质量；处于最优解与最差解之间的蚂蚁在本次搜索循环时按照基本蚁群算法的方式进行状态转移，即依概率的方式进行选择。按照最大-最小蚂蚁系统的方式，将各边的信息素量置于上下限之内，并且该上下限能够随着搜索状况动态改变，以防止算法陷入停滞状态。
　　以上两种改进的蚁群算法均已应用于有线网络QoS路由计算之中。采用Salam网络随机生成算法产生随机网络作为数据进行仿真实验。仿真实验表明，解决QoS路由选择问题时，基于新鲜度的分工蚁群算法与基于自主行为的蚁群算法的搜索性能均优于基本蚁群算法以及最大-最小蚂蚁系统。