基于改进蚁群算法的qos组播路由问题研究

来源：互联网   发布日期：2011-09-18 20:07:01   浏览：9503次  

蚁群算法是基于蚂蚁群体觅食过程中，具有找到蚁穴与食物源之间最短路径的能力，这一生物学行为发展起来的一种群智能优化方法。它最初用于解决旅行商(tsp)问题，具有自适应性、鲁棒性及本质上的并行性等许多特点。该算法的出现引起了学者们的巨大关注，在过去的短短十余年时间内，蚁群算法已经在组合优化、函数优化、系统辨识、网络路由、机器人路径规划、数据挖掘以及大规模集成电路的综合布线设计等领域获得了广泛的应用，并取得了较好的效果。 组播路由问题是随着互联网的迅猛发展衍生出的系列问题之一，随着群组通信特别是网络视频会议、网络视频点播、股市行情发布、远程教育等应用大量兴起，组播技术已成为支持这些应用的重要基础。由于这些实时业务对网络传输中的时延、带宽、代价等较为敏感，当突发性较高的多媒体业务数据在网络上传输时，其传输质量将会受到影响，这样就需要服务质量技术的支持，以确保实时业务的通信质量。传统“尽力而为”服务，不能满足网络用户的需求。组播qos路由就是寻找满足特定qos约束的一棵组播树，这已被证明是一个np完全问题。虽然针对该问题，学术界已提出了不少算法，但普遍存在着算法复杂、实现困难、算法适应性差、难以满足组播应用的需求等特点。因而需要运用到启发式算法。 本文首先总结了现有的组播路由协议及算法分类，分析qos度量以及qos组播路由问题的模型和分类。列举了蚁群算法的研究进展、思想起源和优缺点，给出了基于蚁群算法的qos组播路由算法的描述和步骤并进行分析。随后，在此基础上结合模拟退火算法的特点：在搜索最优解的过程中，以一定的概率接受劣解。将模拟退火算法思想与蚁群算法相结合，生成基于模拟退火思想的逆向蚂蚁。逆向蚂蚁在选择路径时，按照信息素浓度高的路径被选中的概率小的规则。因此在探讨基于模拟退火思想的逆向蚁群算法解决qos组播路由问题时，通过在算法初期引入逆向蚂蚁以增强搜索的随机性，增加搜索的遍历性，避免算法过早收敛进入停滞状态，陷入局部最优。随着迭代的进行，逐渐减少逆向蚂蚁数量，从而加快算法的收敛速度。 通过应用改进的waxman随机网络生成方法，生成了仿真随机网络，并对基于模拟退火思想的逆向蚁群算法和基于常规蚁群算法的qos组播路由问题进行仿真实验，将两种算法产生的结果进行对比，分析得出：逆向蚁群算法在收敛性、稳定性、鲁棒性和网络性能代价等方面都有较好的效果。最后，对qos组播路由算法的研究提出了一些建议。

赞助本站