1、第 1 页 共 33 页 1 1 绪论绪论 通信网络的迅速发展，新业务的不断出现，使多点通信成为网络必须支持的 功能。传统网络中使用一对一的通信协议支持多点协议，数据需要做多个拷贝， 分别传送，极大的浪费了网络资源。未来的多媒体通信，将带来大量的多点通信， 使用点对点协议将造成网络效率的低下；另外，多媒体通信的业务通常需要达成 一定的同步关系，使用点对点协议完成多点通信不再有效；而复用技术的发展使 组播在共同的链路上共享带宽成为可能。由于上述原因必须考虑多点路由问题。 由于网络是动态变化的，网络拓扑结构的变化的不可预测性和变化的频繁性 和不确定性是网络多点路由问题与其他常见的组合优化问题的根本
2、不同之处，网 络流量的随机性和偶然性也是网络动态变化的主要因素。有效快捷的网络路由算 法是网路发展的重要问题。 而蚁群算法的出现和广泛应用，提供了多点路由优化设计的新的思想。蚁群 算法是一种模拟进化算法，它是在对自然界中真实蚁群的集体行为研究的基础上， 由意大利学者 M.Dorigo 等人首先提出的。M.Dorigo 等人充分利用了蚁群搜索食物 的过程与著名的旅行商问题（TSP）之间的相似性，通过人工模拟蚂蚁搜索食物的 过程（即通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路 径）来求解 TSP 问题。仿生学家通过大量细致观察研究发现，蚂蚁个体之间是通过 一种被称为外激素的物质进
3、行信息传送，从而能相互协作，完成复杂的任务。蚂蚁 在运动过程中，能在它所经过的路径上留下该物质，而且蚂蚁在运动过程中能够感 知这种物质的存在及其强度，并以此指导自己的运动方向，蚂蚁倾向于朝着这种物 质强度高的方向移动。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息 正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂 蚁个体之间就是通过这种信息的交流达到搜索食物的目的。 蚁群算法是一种随机搜 索算法，与其它模拟进化算法一样，通过候选解组成的群体的进化过程来寻求最优 解，该过程包含两个基本阶段：适应阶段和协作阶段。在适应阶段，各候选解根据 所积累的信息不断调整自身结构；
4、在协作阶段，候选解间通过信息交流，以期产生 性能更好的解。 蚁群算法之所以能引起相关领域研究者的注意， 是因为这种求解模式能将问题 第 2 页 共 33 页 求解的快速性、全局优化特征以及有限时间内答案的合理性结合起来。其中，寻优 的快速性是通过正反馈式的信息传递和积累来保证的。 而算法的早熟性收敛又可以 通过其分布式计算特征加以避免，同时，具有贪婪启发式搜索特征的蚁群系统又能 在搜索过程的早期找到可以接受的问题解答。 这种优越的问题分布式求解模式经过 相关领域研究者的关注和努力， 已经在最初的算法模型基础上得到了很大的改进和 拓展。基于蚁群算法的以上特点，将蚁群算法用于 OSPF 协议的网络中，根据不同 网络的需要寻找最优路径（可以是时延、中间路由器个数或者费用等参数最优化） ， 将是一个非常值得我们去研究的课题。 1.1 1.1 本设计研究的目的意义本设计研究的目的意义 人们生活的现代社会是一个由计算机信息网络、 电话通信网络、 运输服务网络、 能源和物流分配网络等各种网络组成的复杂的网络系统。 网络优化的目的就是研究 如何有效地计划、 控制和管理这个网络系统， 使之发挥最大的
