学士学位论文基于蚁群优化的zigbee路由算法研究.doc

《学士学位论文基于蚁群优化的zigbee路由算法研究.doc》由会员分享，可在线阅读，更多相关《学士学位论文基于蚁群优化的zigbee路由算法研究.doc（43页珍藏版）》请在三一办公上搜索。

1、哈尔滨远东理工学院学士学位论文 题 目： 基于蚁群优化的zigbee路由算法研究 姓 名： 崔继鹏 分院： 工学院 专业： 电子信息工程 学 号： 09030201 指导教师： 郑灿香 二0 年 月 日毕业设计（论文）评语及成绩 一、指导教师评语：是否同意参加答辩：指导教师签字： 20 年 月 日 二、评阅人评语：是否同意参加答辩： 评阅教师签字： 20 年 月 日 三、答辩委员会评语：是否建议授予学士学位：答辩委员会成员签字：1、 2、 3、 4、 5、 6、7、 8、 9、 20 年 月 日 四、答辩委员会主任单位 答辩委员会主任职称 答辩委员会主任签字 20 年 月 日 五、毕业设计（论

2、文）成绩： 学生所在分院盖章： 20 年 月 日哈尔滨远东理工学院毕业设计（论文）任务书学生姓名崔继鹏学 号 09030201分 院工学院专 业 电子信息工程任务起止时间： 2012 年 12 月 10 日 至 2013 年 5 月 31 日毕业设计（论文）题目： 基于蚁群优化的zigbee路由算法研究毕业设计（论文）工作内容： 本文提出了一种基于蚁群优化的ZigBee路由算法，该算法很好地利用了蚁群算法的自适应性，结合蚁群算法和无线传感网络中ZigBee技术的结构和特点，并根据蚂蚁寻径与路由传输数据节点的相似性，采用该算法提高网络的确定性服务质量，提高网络路由节点的平均寿命，寻求网络中任一俩

3、个节点的最优路径，提高数据包成功发送速度，同时平衡网络带宽、时延节省费用，并对他们进行限制以保证在网络出现过载拥堵情况时，重要数据不受延迟或丢弃。蚁群算法显示出它在无线传感器网络路由方面的优势。毕业设计（论文）进度安排：1、查阅中外文文献资料，写出文献综述阶段：2012年12月10日2013年1月10日2、调查、设计、实验、研究阶段：2013月1 月11日2013年3月31日3、设计（论文）撰写与整理阶段： 2013年4 月1 日2013年5月31日指导教师意见与要求： 签字： 年 月 日主任意见： 签字： 年 月 日摘 要无线传感器网络（Wireless Sensor Network, WS

4、N）是由大量具有通信与计算能力的微小传感器路由节点以多跳通信、自组织的方式形成的分布式无线网络。传感器节点只能和其邻居节点通信，其计算能力、存储能力和通信能力都十分有限。无线传感器网络广泛应用于军事领域、环境监测、医疗健康等领域，具有重要的实用价值。由于无线传感器网络中的传感器节点能量受限，因此，有效节约并且均衡网络的能量消耗就成了研究传感器网络路由算法的关键因素。本文提出了一种基于蚁群优化的ZigBee路由算法，该算法很好地利用了蚁群算法的自适应性，结合蚁群算法和无线传感网络中ZigBee技术的结构和特点，并根据蚂蚁寻径与路由传输数据节点的相似性，采用该算法提高网络的确定性服务质量，提高网络

5、路由节点的平均寿命，寻求网络中任一俩个节点的最优路径，提高数据包成功发送速度，同时平衡网络带宽、时延节省费用，并对他们进行限制以保证在网络出现过载拥堵情况时，重要数据不受延迟或丢弃。蚁群算法显示出它在无线传感器网络路由方面的优势。关键词：蚁群优化(ACO)；ZigBee技术；路由；网络寿命AbstractWireless Sensor Network is a wireless Ad hoc network consisting of numerous tiny sensor nodes by multi-hop communication and self-organization, whi

6、ch have communication and computing capability. The sensor node can only communication with neighbor nodes, and its computing capability, storage capacity and communication ability are limited. WSN is widely used in military, environment monitoring, medical and health services and so on, and it has

7、great practical and scientific values. Because of the limited energy of sensor nodes in the WSN, therefore, the key factor of routing algorithm in the WSN will be to save efficiently and balance the energy consumption in the network.This paper proposes a kind of Zigbee routing algorithm of based on

8、ant colony optimization, the algorithm makes good use of the ant colony algorithm for adaptive, combination of ant colony algorithm and wireless sensor network Zigbee technology structure and characteristics，according to ant routing and routing data transmission node similarity, using this algorithm

9、 to improve network deterministic service quality, to improve network routing node average life, for any two nodes in a network optimal path, improve the successfully sent speed of data transmission, at the same time to balance network bandwidth, save delay cost ，and they were restricted, to ensure

10、that the network overload congestion, important data without delay or discarded. Ant colony algorithm shows it in the wireless sensor network routing advantages.Keywords：Ant colony optimization; Zigbee technology; Routing; Network lifetime目 录摘 要IAbstractII目 录III第1章 绪 论11.1 课题研究的目的和意义11.2 课题国内外研究的意义1

11、1.2.1 国内蚁群算法应用现状11.2.2 国外蚁群算法研究现状21.3 课题研究内容31.4 本章小结4第2章 无线网络蚁群算法路由技术52.1 蚁群算法简介52.1.1 蚁群算法基本概念52.1.2 蚁群算法特点62.1.3 蚁群算法基本数学模型62.2 蚁群算法的实现82.3 蚁群算法迭代过程102.4 无线网络蚁群算法路由技术分析112.4.1 简单相关路径Zigbee路由算法概述112.4.2 路由维护与信息素更改112.4.3 基于蚁群算法的Zigbee路由研究与改进122.5 蚁群算法中信息素的更新原则122.6 本章小结12第3章 无线网络蚁群优化算法路由技术133.1 蚁群

12、优化算法基本原理133.1.1 蚁群优化算法基本概念133.1.2 蚁群优化算法数学模型133.1.3 蚁群优化算法的值与点的收敛143.2 蚁群优化算法在路由中的应用143.3 蚁群算法中参数的最优选择153.3.1 蚁群信息素挥发度的选择153.3.2 蚁群数量的选择163.3.3 启发因子的选择183.3.4 总信息量的选择183.4 本章小结19第4章 实验分析与结果仿真204.1 蚁群路由定义204.1.1 蚁群优化网络算法流程204.1.2 路由发现204.1.3 路由选择214.1.4 路由维护224.2 蚁群路由实现与结果仿真224.3 本章小结26第5章 课题研究中的难点及解

13、决方法275.1 有关蚂蚁构建过程与难点分析275.2 基于遗传算法的Zigbee路由研究与改进285.3 课题的可行性评估295.4 本章小结30结 论31致 谢32参考文献33附 录 A34附 录 B35附 录 C36第1章 绪 论无线通信技术的迅速发展，使得人们对移动通信的需求越来越强烈，人们通过配有无线接口的便携式计算机或个人数字助理(PDA)来实现移动中的通信，目前的移动通信往往需要有固定基础设施的支持才能实现，例如全球通信系统(GSM)。但是当遇到医疗抢险、抗洪救灾以及军事战场等特殊紧急环境的时候，传统的无线网络就不可用了。为了能够在没有固定基础设施的地方进行通信，一种被称作Ad

14、hoc(Mobile Ad Hoc Networks)网络的技术应运而生。移动Ad Hoc网络是一种新的移动无线网络系统，它不需任何固定基站设施，节点之间的通信可借助于其他的移动节点形成多跳通信完成。由于该网络组网快速、灵活，抗毁性强，使用方便而且应用范围广泛，因此是当前网络和通信技术领域的研究热点之一。从研究内容看，Ad Hoc的网络层协议是研究的难点和重点，而Zigbee路由算法又是网络层协议的核心技术问题。1.1 课题研究的目的和意义 随着网络的普及，人们对网络的需求越来越丰富，对网络技术的要求也越来越高。开始只是简单的文字传输，而现在人们对视频、音频等多样化实时传输有了更多的需求。本课

15、题研究基于蚁群优化zigbee路由算法，采用该算法提高网络的确定性服务质量，提高网络路由节点的平均寿命，寻求网络中任一俩个节点的最优路径，提高数据包成功发送速度，同时平衡网络带宽、时延节省费用，并对他们进行限制，保证在网络出现过载拥堵情况时，重要数据不受延迟或丢弃。蚁群算法显示出它在无线传感网络路由方面的优势。无线传感器网络路由设计的指标之一就是尽可能的节省能量，延长网络寿命。这给传感器网络路由协议的设计提出了巨大挑战。将蚁群算法应用于路由协议的设计中，利用蚁群算法的网络分布式、个体简单而群体智能表现出优化等特点很好的均衡了网络负载，延长了网络寿命。近年来引起了中外研究人员的广泛关注，并且已逐

16、渐成为当前无线传感器网络路由设计研究领域的热点。随着各种智能算法的相继出现。越来越多的学者将它们应用于无线传感器网络路由协议的研究中，而蚂蚁寻找食物的行为与网络中节点寻找路由的过程十分相似，因此基于蚁群算法的传感器网路由协议得到了大量的关注。1.2 课题国内外研究的意义蚁群算法是一种仿生智能算法，它从现实生活中蚂蚁寻食的过程得到启发，采用概率选择机制控制路径的走向，同时也加入了随着时间的延长，信息素挥发的因子。众多的研究证明，蚁群算法具有很强的发现较好解的能力，该算法不仅利用了正反馈原理，在一定程度上加快了进化过程，而且在本质上也可并行实现，不同个体之间通过不断的信息交流和传递，能够相互协作，

17、有利于发现较好解。蚁群算法可以理解为一种特殊的强化学习算法。1.2.1 国内蚁群算法应用现状随着群智能理论和应用算法研究的不断发展，蚁群算法在离散求解空间问题中表现出良好的搜索效果。蚁群优化算法并不是旅行商问题的最佳解决方法，但是它却为解决组合优化问题提供了新思路，并很快被应用到其它组合优化问题中。比较典型的应用研究包括： 网络路由优化、数据挖掘以及一些经典的组合优化问题。蚁群算法在电信路由优化中已取得了一定的应用成果。HP公司和英国电信公司设计了蚁群路由算法。在该算法中，每只蚂蚁就像蚁群优化算法中一样,根据它在网络上的经验与性能，动态更新路由表项。如果一只蚂蚁因为经过了网络中堵塞的路由而导致

18、了比较大的延迟，那么就对该表项做较大的增强。同时根据信息素挥发机制实现系统的信息更新，从而抛弃过期的路由信息。这样，在当前最优路由出现拥堵现象时，ACR算法就能迅速的搜寻另一条可替代的最优路径，从而提高网络的均衡性、负荷量和利用率。目前这方面的应用研究仍在升温，因为通信网络的分布式信息结构、非稳定随机动态特性以及网络状态的异步演化与ACO的算法本质和特性非常相似。ACO还在许多经典组合优化问题中获得了成功的应用, 如二次规划问题(QAP) 、机器人路径规划、作业流程规划、图着色(Graph Coloring) 等问题。部分研究者将ACO 用于了武器攻击目标分配和优化问题、车辆运行路径规划、区域

19、性无线电频率自动分配Bayesian networks 的训练和集合覆盖等应用优化问题。Costa和Herz还提出了一种AS 在规划问题方面的扩展应用图着色问题，并取得了可与其他启发式算法相比的效果。最近几年来，随着人类在无线通信技术、微传感器技术、微机电技术等方面取得的进步，一种集成了感知、通信能力的传感器节点被发明出来。这种节点具有低成本、低功耗、多功能、体积小和短距离无线通信的特点，由这种节点构成的网络引起了人们越来越多的关注。这种传感器节点集成了无线通信技术、传感器技术、分布式信息处理技术和嵌入式计算机技术等功能。目前来说，无线传感器网络路由算法已经成为国内外学者的一个研究热点。文耀锋

20、等针对传感网络中簇头采用单跳通信时距离转化为线性规划问题，提出了一种基于粒子群优化的有效能量空洞避免的无线传感器路由算法。这些改进的路由算法在节省结点能源方面取得了很多进展，但缺少对路径全局寻优方面的考虑，降低了WSN的整体吞吐量。目前，在将蚁群算法应用于无线传感器网络路由方面，提出了许多新的算法。有的文献中提出了一种针对斯坦纳树的蚁群算法，该算法可被移植到WSN路由中。然而，并没有针对WSN的特定需求做出相应改变，而且没有考虑对于WSN性能至关重要的能耗问题。Zhang等人在研究了三种不同的基于蚂蚁的WSN算法，然而，作者仅仅关注信息素初始分布的建立，在系统启动效率方面具有一定的优势。有的文

21、献通过在蚂蚁算法的下一跳选择公式中引入偏转角的概念来优化路径并利用蚂蚁算法的正反馈效应来完成数据汇聚从而达到节省能量的目的。但是，该算法要求每个节点都必须配备有定位设备如GPS系统，很大程度上限制了它的适用范围。1.2.2 国外蚁群算法研究现状20世纪40年代到50年代期间，法国昆虫学家Grasse在研究白蚁的生物群体行为时，首次提出了媒介质网(stigmergy)的概念，来描述白蚁个体之间间接交流信息的特殊方式。媒介质与其他的交流方式主要有两点不同：首先，它是昆虫间接感受周围物质世界的改变而释放出来的物理的(physical)、非符号化(nonsymbolic)、非语言层次上的沟通媒介；其次

22、，它只能被接触到媒介质的昆虫感知，也就是它具有局部被感知的特性。媒介质的这种特性在著名的双桥实验中有详细的研究，并成为激发计算机科学家提出蚂蚁系统阳(第一个ACO算法)的直接源泉。蚁群算法是有意大利学者M.Dorigo，M.aniezzo，A.Cobrni 等人在20世纪90年代初首先提出来的它是继模拟退火算法、遗传算法、禁忌搜索算法，人工神经网络算法后的有一种应用于组合优化问题的启发式搜索算法。生物界的昆虫和其他群居动物的群体智能(swarm intelligence)行为一直是科学家进行科学研究的灵感源泉。1979年，RHofstadter首次提出了人工蚂蚁的概念，探讨了具有较低智能的简单

23、个体间能否通过相互作用而产生较高的群体智能行为.从此，蚁群的链式反应行为(autocatalytic behavior)或正反馈(positive feedback)特性受到越来越多的关注。ACO的思想是由在意大利米学者M.Dorigo等人于1991年提出的。从1991年到1996年，M Dorigo等人就蚁群搜索食物的过程与旅行商问题(TSP) 之间的相似性, 通过人工蚂蚁搜索食物的过程做了一定的研究，先后提出了三种模型：ant-quantity, ant-density和ant-cycle。这三种模型的主要差别是在于对信息素浓度的变化采取不同的数学公式。直到1996年，M Dorigo在发

24、表了系统的关于蚂蚁系统(AS)的全面论述，总结了这三种模型。在这篇论文中M Dorigo引入了ant-code模型，并针对TSP问题做了一系列实验，和其他只能算法做了比较，阐明了AS的强壮性(robust)，多适应性(versatile)和基于群体性(population-based)。2009年，PDeepalakshmill 提出了ARMAN算法，在原有蚁群算法数学模型上，加入了路径选择偏好概率，通过偏好概率选择移动网络中从源节点到目的节点的多重路径，最终得到的路径时延更小、带宽更高、抖动更少。蚁群优化(ACO)是由意大利学者MDorigo等人作为求解著名旅行商问题(TSP)的启发式算法而

25、提出的，它是模拟自然界中蚂蚁搜索食物行为而提出的一种启发式智能进化算法。由于蚁群优化算法具有正反馈性、分布式并行计算机制、较强的鲁棒性等特点 ，可用于求解基于分布式网络的最优路径计算，如路由、负载平衡和计算机网络中的多路传输等方面。Laura Rosati 等人在2008年提出DAR(Distributed Ant Routing)协议，它是一种按需的路由协议，相对于主动式路由，它可以减少路由时的网络负载。前向蚂蚁只负责收集关于交叉节点的ID信息，它在使用概率公式计算选择下一跳节点的概率时只使用信息素值作为参数。而后向蚂蚁在返回过程途中只释放常量值的信息素值。在DAR中。每个路由节点中路由表都

26、是随机的：下一跳节点是依据概率值的大小进行选择的。这个概率值是通过以前蚂蚁走过时留下的信息素进行计算的。但是DAR算法要让蚂蚁记录经过的节点，不适用于大型网络，同时也容易陷入局部最优解，网络的收敛速度也不快。1.3 课题研究内容无线传感器网络(Wireless Sensor NetworkWSN)是继Internet之后随着无线通信技术、传感器技术、微电子技术和分布信息处理技术发展起来的一种新兴信息获取技术。WSN综合了嵌入式技术、传感器技术、通信技术和分布式信息处理技术，能够协作实时感知、监测、采集网络分布区域内的各种环境的信息，并对数据进行适当的处理以获得精简准确的信息，并传送给最终的用户

27、。在WSN中，每个传感器结点的路由选择过程和蚂蚁的觅食寻优行为具有极大的相似性，因此，利用蚁群优化来设计WSN的路由算法具有理论上的可行性。基于此，我们把传感器结点模拟成蚂蚁，把传感器的路径选择模拟成蚂蚁的觅食路径选择路径的启发式信息模拟成蚂蚁在路径上释放的信息素，提出了一种基于蚁群优化的路由算法。蚁群算法是一种来自大自然的随机搜索寻优方法，是生物界的群体启发式行为，现己陆续应用到组合优化、人工智能、通讯等多个领域。蚁群算法的正反馈性和协同性使其可用于分布式系统，隐含的并行性更使之具有极强的发展潜力。从数值仿真结果来看，它比目前风行一时的遗传算法、模拟退火算法等有更好的适应性。但是蚁群算法毕竟

28、是一种新兴的模拟进化算法，还缺乏坚实的数学理论基础，算法的参数选择、收敛性等还有待进一步研究，算法的最优停止条件也是值得研究的地方。目前，关于算法的参数选择大都与具体问题的应用结合，通过实验进行确定，而算法的停止条件则采用固定循环次数或当进化不明显时停止迭代作为条件。本文探讨了蚁群算法的原理、特点及功能；对基本蚁群算法的有关参数的合理选择进行实验分析；提出了相应的改进策略，并通过仿真实验，验证了改进算法的有效性，提高了寻求最优路径能力；分析了基于蚁群算法的网络路由优化。采用该算法并把该算法应用于zigbee无线网络中，平衡了zigbee网络的缺点可以提高网络的确定性服务质量，提高网络路由节点的

29、平均寿命，寻求网络中任一俩个节点的最优路径，提高数据包成功发送速度，同时平衡网络带宽、时延节省费用，并对他们进行限制，保证在网络出现过载拥堵情况时，重要数据不受延迟或丢弃。蚁群算法显示出它在无线传感器网络路由方面的优势。所以利用蚁群优化的特点和优势提出了一种基于蚁群优化的zigbee路由算法，根据zigbee路由策略和蚁群优化的特点，构造了人工蚂蚁使算法具有较好的节能性和全局寻优能力，并改善网络的性能。提出自己的思路和做法，达到网络优化的目的。1.4 本章小结采用在无线传感网络路由方面显示出独特优势的蚁群优化zigbee路由算法，可以提高网络服务质量，延长寿命，节省费用。因此基于蚁群算法的传感

30、器网路由协议得到了国内外学者的大量的关注。由于利用了正反馈原理，协同性以及隐含的并行性更使之具有极强的发展潜力，并且可以理解为一种特殊的强化学习算法。根据zigbee路由策略和蚁群优化的特点，构造了传感器结点使算法具有较好的节能性和全局寻优能力，并改善网络的性能，达到网络优化的目的。第2章 无线网络蚁群算法路由技术生物界的昆虫和其他群居动物的群体智能，行为一直是科学家进行科学研究的灵感源泉，随着各学科门类的交叉综合，群体智能已经成为解决计算问题的新兴的方法。1979年，Dougls RHofstadter首次提出了人工蚂蚁的概念，探讨了具有较低智能的简单个体间能否通过相互作用而产生较高的群体智

31、能行为。从此，正反馈特性受到越来越多的关注。2.1 蚁群算法简介2.1.1 蚁群算法基本概念蚁群算法是一种基于蚁群系统原理的、具有自组织能力的、新型的启发式优化算法。蚁群系统基本原理，人工蚁群系统(通常简称蚁群系统)用于通过信息素痕迹和启发信息的指引来构造解。人工蚁群是受到真实蚂蚁觅食行为的启示而提出的，这个行为使蚂蚁可以在食物源和蚁巢之间找到最短路径。最初，蚂蚁以随机的方式探索蚁巢周围的区域，一旦一只蚂蚁找到食物源，它会评估食物的数量和质量，并搬运一些食物回到蚁巢。在回程中，蚂蚁在地面上留下一种被成为信息素的挥发性分泌物，留下的信息素数量取决于食物的数量和质量。图2-1 蚁群觅食源点到结点的

32、路径选择对于一条路径，选择它的蚂蚁越多，则在该路径上蚂蚁所留下的信息素的强度就越大，而强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈。通过这种正反馈，蚂蚁最终可以发现最短路径。在ACO算法中，信息素轨迹通过一个被称为信息素模型的参数化概率模型模拟。信息素模型由一系列模型参数组成，这里的模型参数值被称为信息素值。如图所示, 蚂蚁从A 点(蚁巢) 出发, 速度相同, 目的地在D点(食物) , 可能随机选择路线ABD 或ACD。假设初始时每条分配路线一只蚂蚁, 每个时间单位行走一步, 图中上图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。图中下图为

33、经过18 个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36 个时间单位后, 所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2 趟，每一处的信息素为4个单位，而ACD的路线往返了一趟, 每一处的信息素为2 个单位，其比值为2:1。 寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD 路线上增派一只蚂蚁(共2只)，而ACD路线上仍然为一只蚂蚁. 再经过36个时间单位后, 两条线路上的信息素单位积累为12 和4，比值为3B1。若按以上规则继续，蚁群在ABD 路线上

34、再增派一只蚂蚁(共3只)，而ACD 路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24 和6，比值为4B1。若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD 路线。这就是蚁群的自催化效应。图 2-2 蚁群原理图2.1.2 蚁群算法特点本文提出的算法具有以下特点：(1)路由代价低。采用分布式路由决策，避免了在网络中传输路由表，路径维护在数据传输过程中自动进行，不需要使用额外的数据包和数据传输的传输过程来进行路径维护；(2)自适应性好。蚁群算法的自组织特性使该算法能自动适应网络状态和节点能量的动态变化，算法鲁棒性强；(3)支持多路径。每个节点

35、有多个通向目标的路径，路经的选择取决于路径的质量，多路径提高路由的可靠性；(4)支持休眠模式。可以使信息素浓度低、能量低的节点进入休眠模式，进一步降低能耗。2.1.3 蚁群算法基本数学模型蚂蚁具有找到蚁巢与食物之间最短路径的能力。这种能力是靠其在所经过的路径上留下一种挥发性分泌物来实现的。蚂蚁在一条路径上前进时，会留下挥发性分泌物，后来的蚂蚁选择该路径的概率与当时这条路径上挥发性物质强度成正比对于一条路径，选择它的蚂蚁越多，则在该路径上蚂蚁所留下的分泌物的强度就越大。而强度大的分泌物会吸引更多的蚂蚁，从而形成一种正反馈通过这种正反馈，蚂蚁最终可以发现最短路径。我们通过释放人工蚂蚁群来创建基于蚂

36、蚁算法的网络模型，为了把通信网络和蚂蚁算法理论联系起来，我们利用信息素表，如表2-1来取代网络节点中的路由选择表。表2-1 信息素路由选择表信息素路由选择表 邻节点目的节点 a b k d1 p11 p12 p1m d2 p21 p22 p2m d3 dm pn1 pn2 pnm表1中的n为某个节点可以选择的目的节点数，m为该节点的相邻节点数。“信包素表”给出了以某个节点为目的节点时选择下一节点的概率，同时表1中的概率值按照某种规则周期性地刷新：下面的公式给出了在节点u中的蚂蚁k选择到相邻节点v的概率： (2-1)其中为链路上的“信息素”；为与节点 直接相连的所有节点的集合； = ，其中为链路

37、的传输代价可能是链路的距离或链路的传输成本等；为链路上的剩余带宽；和是决定时延和剩余带宽相对重要的参数。从公式我们看出，蚂蚁更有可能选择时延小、可利用带宽大、信息素强度较强的链路。蚂蚁开始搜索的初始时刻，各条路径上分布的信息量相等，即(C为常数)。蚂蚁在运动过程中，根据各条路径上的信息量决定转移方向，时刻位于某一城市的蚂蚁一次只能选择其中一个目标城市，次后回到起点，完成一次循环。那么，时刻位于城市的蚂蚁选择城市为目标城市的概率是： (2-2)其中，表示蚂蚁下一步允许选择的城市。与实际蚁群不同，人工蚁群系统具有记忆功能，用以记录蚂蚁当前所走过的城市，集合随着进化过程作动态调整。随着时间的推移，以

38、前留下的信息渐渐消失，经过个时刻，蚂蚁完成一个循环，各路径上的信息量要根据如下做调整: (2-3) (2-4)公式(2-3)和(2-4)中表示在时刻和之间第k只蚂蚁在路径上留下的信息素量，表示在时刻和之间路径上信息素增量，其中是一个参数，表示残留信息的持久程度 ，1-表示在时刻和+之间信息素消逝程度。当所有蚂蚁完成各自路径的选择过程，必须对各边上的信息素按公式(2-3)作一次全局更新，此时根据具体算法的不同，表达形式可以不同，要根据具体问题而定。M.Dorigo提出的三种模式为ant-cycle system(蚁周)；ant-quantity system（蚁量）和ant-density sy

39、stem（蚁密度）在ant-cycle system模型中： (2-5)公式(2-5)中是常数，为蚂蚁循环一周时释放在所经过路径上的信息素总量，即总信息量；表示第只蚂蚁在本次循环中所走路径的长度。初始时刻，。在ant-quantity system模型中： (2-6)在ant-density system模型中： (2-7)由公式(2-5)、(2-6)、(2-7)可知，它们的差别在于的不同。M.Dorigo通过对三种旅行商问题的实验做了比较，可见ant-cycle system模型性能较好。2.2 蚁群算法的实现从以上蚁群算法的模型可知，算法的寻优过程是一个递推迭代过程，Ant-cycle s

40、ystem程序的伪代码其实现步骤如下(设NCMAX是定义好的循环次数)： (1) 初始化:Set ， NC=0，每条边上的并且随机放置个蚂蚁到个城市上；(2) 令 (s是tabu list的下标)：For k=1 to m do把第k个蚂蚁的初始城市号码放置；(3) 重复本步骤直到tabu list被填满(这个步骤重复n-1次)：Set s=s+1 For k=1 to m do，根据概率式(2-2)来选择下一步应该到达的城j在时刻，蚂蚁k在城市，将第k个蚂蚁移到城市j，并将j插入到中；(4) For k=1 to m do，将第k个蚂蚁从城市移到，计算第k只蚂蚁的总路径长度，更新找到的最短路

41、径。For to m do根据式(2-4)、(2-5)，更新边上的信息素浓度；(5) 根据式(2-3)，对每一条边计算Set Set set (6) 如果并且(不是所有的蚂蚁选择同一条路径)那么；清空所有的tabu list；转到第(2)步；否则；初始化，设置时间计数器，循环计数器，每条边信息素浓度初值，将m只蚂蚁随机放到n个城市初始化tabu列表，将所有蚂蚁的初始城市放置到tabu列表中Tab列表满？Y计算机转移概率p，按概率将每只蚂蚁从第i个城市移到第j个，宁见j插入tabu列表中N封闭回路，分别计算每只蚂蚁走过的总长度，记录最短路径，计算信息素浓度该变量达到最大环次数求解度N Y 显示并

42、打印最短路径图 2-3 蚁群算法流程图打印出最短路径，终止整个程序。由于算法的第一步的复杂度为，第二步的复杂度为，第三步的复杂度为，第四步的复杂度为，第五步的复杂度为，第六步的复杂度为，所以如果程序终止于次循环后，算法的复杂度就为。当城市个数n和蚂蚁个数m成线性关系时，这个算法的复杂度为。蚁群算法的流程图如图2-3所示。2.3 蚁群算法迭代过程以下图为例说明蚁群算法的迭代运算过程。AO、Al代表两只蚂蚁，VO、Vl为两个节点，它们之间存在两条路径Upper和Down，且Upper的距离为2，Down的距离为1。假设初始时刻每条路径均有相同的概率(各为0.5)被选择，信息素初值，。两只蚂蚁从V0开始寻找最短路径。 UpperUpper障碍物A0A0V1V1V0V0障碍物 A1A1DownDown 图 2-4 蚁群算法迭代图初始时，A0走Upper路径，Al走Down路径，各自释放在路径上的信息素为:,。当A0、Al到达V1后，各条路径上实际有的信息素为:当蚂蚁重回起点V0进行路径选择时，根据概率选择公式有: 由于，因此，两只蚂蚁都将选择路径Down。此