java基于蚁群算法路由选择可视化动态模拟-开题报告

开题报告课题: 基于蚁群算法路由可视化动态模拟1. 选题依据（1） 课题研究意义DWDM全光通信网在我国已进入了高速发展期，正向着 ASON（Automatically Switched Optical Network 自动交换光网络）为代表的新一代智能化光网络的方向发展。而智能化的动态光路由和波长分配（Routing and Wavelength Assignment, RWA）算法则是构建ASON、实现对全光网的智能化控制和管理的关键技术之一。蚁群算法是受真实蚁群觅食行为的启发而产生的一种模拟进化算法，是由有限个蚂蚁的个体行为组成的多 agent系统1、2，已被成功应用于解决 TSP（Traveling Salesman Problem 旅行家问题）1、JSP（Job-shop Scheduling Problem生产排程问题） 、QAP（Quadratic Assignment Problem二次指派问题）等组合优化问题。近来已有的大量研究表明，蚁群算法具有并行性、鲁棒性、可重构性、分布性等特质。这些特性使得蚁群算法在解决动态 RWA问题中表现出优异的性能。在网络带宽的有效利用、波长资源的合理分配、以及网络路由的重构与恢复，基于蚁群思想都能找到对应的解决方法。相关研究工作如达到预期目标将处于国际先进水平,也必然会加快我国构建智能光网络的步伐,因此具有良好的经济效益和社会效益.（2） 国内外研究现状、水平和发展趋势至今为止，国内外比较成熟的动态 RWA算法都把 RWA问题强行拆分成路由和波长分配两个子问题分别加以解决,如 First-Fit（最先适用）算法、LLR（least-loaded routing最小负载路由）算法、LI（Least Influence最小影响）算法 3等，并且都为集中式算法，需要利用全网信息，没有考虑波长变换，无法完成在算法层面上的网络的自动恢复，路由和波长分配独立解决也导致这些算法难以得到全局最优解。而由于蚁群算法具有并行性、鲁棒性、可重构性、分布性等特质，并且运用蚁群算法的思想结合分层图模型可以把路由和波长分配联系起来同时解决。这使得基于蚁群算法的动态 RWA解决方案具有传统方法不可比拟的优点：同时考虑路由和波长分配易于得到全局最优解；可以并行执行、分布计算，在算法层面上就可以实现网络的智能恢复而不需要添加其他设备。同时，原始的蚁群算法也存在算法收敛慢、容易早熟、停滞、求解时间过长、在特定条件下难以得到全局最优解等不足。要想把蚁群算法真正运用于实际，则必须进一步研究以克服原始蚁群算法的不足之处。蚁群算法在构建智能光网络中巨大的潜在价值已引起国内外广泛的注意，相关的研究开发大多处于理论探讨阶段。我们的目标就是进一步优化蚁群算法的性能,使其达到实用水平.主要参考文献：1Marco Dorigo, Vittorio Maniezzo, Alberto colorni, “Ant System:Optimizaition by a Colony of Cooperating Agents”, IEEE Transctions on Systems, Man and Cybernetics-part, Vol.26.NO.1.February 1996.2E.Bonabeau et al. “Routinfin telecommunications networks with “smart” ant-like agents”. In Proceedings of the Second International Workshop on Tntelligent Agents for Telecommunication Applications, 1998. Lecture Notes in Artificial Intelligence, Springer Verlag.3Hui,Z.,Jue,J., and Mukherjee, B. “A Review of Routing and Wavelength Assignment Approaches for Wavelength-Routed Optical WDM Networks,” Optical Networks,January 2000.2. 研究内容（1）研究目标经过深入的调研，本课题制订的研究目标是.设计一套基于蚁群算法思想的动态 RWA 解决方案,基于 NS2 或者 OPNET 建立一套 WDM 全光网动态 RWA 问题的模拟仿真平台.在仿真平台上进行算法测试,根据测试结果改进算法,使算法性能达到或超过传统的基本算法.(2)研究的具体内容1蚁群算法在动态 RWA问题中的实现。参照蚁群算法的基本思想和动态 RWA问题的特点，2，设计仿生蚁群的计算方法和算法，3.设计全光网络动态路由仿真平台,4.编写仿真程序对算法性能进行评估。5.对各种进化算法的改进进行比较研究,6.分析比较各参数对算法性能的影响。针对算法仿真测试中暴露的不足之处 7.针对性地改进算法,提高算法性能。其次 8.降低成本。9.减少人力消耗。（3）需解决的关键问题1设计出仿生蚁群的计算公式，计算方法和有效的算法。2.建立 WDM全光网动态波长路由仿真平台。3.确定各相关参数。4.确定改进方法对各种网络拓扑的综合性能最优.5.算法性能达到实用水平。6.算法支持分布计算和并行执行。7.算法支持光网自愈和区分服务。8.算法支持波长变换。3. 研究方法（1） 研究方案的论证和可行性分析动态 RWA的解决方案主要有两种,一是路由和波长分配分为两个子问题独立解决, 这类算法大多年是建立在传统电路交换网络无向多图（undirected multigraph）模型上, 路由策略常用最短路径路由或是链路最小负荷路由；波长分配策略则有首次命中、随即搜索、最少使用、最常使用、相对性能损失、最小负荷（适合多光纤网络） 、保护阈值（有利于多跳业务） 。另一类算法就是把路由和波长分配结合起来考虑,这种算法建立的基础是另一种新的模型分层图模型.需要指出的是,无论采用哪种模型,运用蚁群算法的思想都能找到对应的解决方案.由于 RWA问题本身是一个不可分割的整体，所以运用的无向多图模型即使分别得到了路由和波长分配的最优解，也难以得到全局的最优解.因此,本课题我们选择在分层图模型的基础上设计基于蚁群算法的解决方案,把路由和波长分配作为一个整体同时解决,以期找出全局最优解.由于引入分层图模型后,路由和波长分配问题就转化为等同的纯路由问题,网络中波长资源、链路长度等信息都可以加权转化为等效路径代价，因此，传统的路由算法都可应用到分层图模型中。但是传统的路由算法如最短路由，最小负载路由等都仅仅集中优化了某一方面的性能，而没有考虑全网的综合性能，并且求解过程中需要预先知道全网的信息。蚁群算法的优点在于，把各种需要考虑的因素加权转化为等效的路径代价后，应用蚁群策略可以找出综合了各方面因素后的全局最优解。并且算法执行过程中仅仅只需利用局部网络的信息，因此蚁群算法可以分布执行，在全局优化网络性能方面也大大优于现有算法。建立算法模型后,性能的验证是必不可少的.因此我们得出算法后要建立动态 RWA问题的仿真平台,验证算法性能.网络仿真软件主要有两个:NS2 和 OPNET.两者都是现今最流行网络仿真软件.但由于 NS-2只有在 linux下才能使用其全部功能. 而 OPNET网络仿真软件是目前世界上最先进的网络仿真开发和应用平台,由于其强大的建模与性能分析功能,使其非常适合本课题的研究需求.还因为本课题的所有研究工作均需在 windows平台上完成,而OPNET正适合运行在 windows平台上,因此本课题我们选择 OPNET来搭建仿真平台.技术可行性：近年来，国内外已有大量研究把蚁群算法成功应用于传统电网路由，以及TSP等寻路问题。动态 RWA问题的研究也已有了一定的成果。NS2、OPNET 等光网仿真技术已比较成熟。把蚁群算法运用于波长路由只要针对全光网的特性进一步发展原始算法，在技术上是可行的。经济效益分析：目前，ASON 已成为下一代光网络的发展趋势，但国际上还没有一种完全成熟的智能化的波长选路方法。蚁群算法在完美解决动态 RWA问题的同时，还具有分布计算、并行执行、智能恢复和重构等优点，完全符合 ASON智能化控制和管理的要求。如果能开发出有自主知识产权的核心选路算法，则不仅可以推动国家信息产业的发展，还能节约大量引进专利的资金，并具出口创汇潜力。（2）采用的技术路线1.学习蚁群算法和进化计算的算法思想，2.调研各种动态 RWA问题的解决方案，3.着重分析比较电网或光网络的选路算法,以期找出各种算法的优缺点,并能借鉴各种有利于算法性能的因素.4.基于蚁群算法的思想,设计计算公式、计算方法和算法。5.进行初步测试确保算法正确.6.基于 OPNET网络仿真软件设计可变波长全光网络动态波长路由仿真平台。7.编写算法仿真程序测试算法,8.调整各参数取值以优化算法性能(阻塞率、执行时间、收敛路径是否最优).9.调研比较各种进化算法的改进方法.10.改进算法 11.用仿真平台模拟各种实际网络拓扑,对算法进行测试. 12.比较各改进算法的综合性能 .以期 13.确定最