学士学位论文--基于蚁群优化的zigbee路由算法研究(编辑修改稿)

学士学位论文--基于蚁群优化的zigbee路由算法研究(编辑修改稿)内容摘要：

器网络路由设计研究领域的热点。 随着 各种智能算法的相继出现。 越来越多的学者将它们应用于无线传感器网络路由协议的研究中，而蚂蚁寻找食物的行为与网络中节点寻找路由的过程十分相似，因此基于蚁群算法的传感器网路由协议得到了大量的关注。 课题国内外研究的意义 蚁群算法是一种仿生智能算法，它从现实生活中蚂蚁寻食的过程得到启发，采用概率选择机制控制路径的走向，同时也加入了随着时间的延长，信息素挥发的因子。 众多的研究证明，蚁群算法具有很强的发现较好解的能力，该算法不仅利用了正反馈原理，在一定程度上加快了进化过程，而且在本质上也可并行实现，不同个体之间 通过不断的信息交流和传递，能够相互协作，有利于发现较好解。 蚁群算法可以理解为一种特殊的强化学习算法。 国内蚁群算法应用现状 随着群智能理论和应用算法研究的不断发展，蚁群算法在离散求解空间问题中表现出良好的搜索效果。 蚁群优化算法并不是旅行商问题的最佳解决方法，但是它却为解决组合优化问题提供了新思路，并很快被应用到其它组合优化问题中。 比较典型的应用研究包括： 网络路由优化、数据挖掘以及一些经典的组合优化问题。 蚁群算法在电信路哈尔滨远东理工学院学士学位论文 2 由优化中已取得了一定的应用成果。 HP 公司和英国电信公司设计了蚁群路由算法。 在该算法中，每只蚂蚁就像蚁群优化算法中一样 ,根据它在网络上的经验与性能，动态更新路由表项。 如果一只蚂蚁因为经过了网络中堵塞的路由而导致了比较大的延迟，那么就对该表项做较大的增强。 同时根据信息素挥发机制实现系统的信息更新，从而抛弃过期的路由信息。 这样，在当前最优路由出现拥堵现象时， ACR 算法就能迅速的搜寻另一条可替代的最优路径，从而提高网络的均衡性、负荷量和利用率。 目前这方面的应用研究仍在升温，因为通信网络的分布式信息结构、非稳定随机动态特性以及网络状态的异步演化与 ACO 的算法本质和特性非常相似。 ACO 还在许 多经典组合优化问题中获得了成功的应用 , 如二次规划问题 (QAP) 、机器人路径规划、作业流程规划、图着色 (Graph Coloring) 等问题。 部分研究者将 ACO 用于了武器攻击目标分配和优化问题、车辆运行路径规划、区域性无线电频率自动分配Bayesian works 的训练和集合覆盖等应用优化问题。 Costa 和 Herz 还提出了一种 AS 在规划问题方面的扩展应用图着色问题，并取得了可与其他启发式算法相比的效果。 最近几年来，随着人类在无线通信技术、微传感器技术、微机电技术等方面取得的进步，一种集成了 感知、通信能力的传感器节点被发明出来。 这种节点具有低成本、低功耗、多功能、体积小和短距离无线通信的特点，由这种节点构成的网络引起了人们越来越多的关注。 这种传感器节点集成了无线通信技术、传感器技术、分布式信息处理技术和嵌入式计算机技术等功能。 目前来说，无线传感器网络路由算法已经成为国内外学者的一个研究热点。 文耀锋等针对传感网络中簇头采用单跳通信时距离转化为线性规划问题，提出了一种基于粒子群优化的有效能量空洞避免的无线传感器路由算法。 这些改进的路由算法在节省结点能源方面取得了很多进展，但缺少对路径全局寻优方面的 考虑，降低了 WSN 的整体吞吐量。 目前，在将蚁群算法应用于无线传感器网络路由方面，提出了许多新的算法。 有的文献中提出了一种针对斯坦纳树的蚁群算法，该算法可被移植到 WSN 路由中。 然而，并没有针对 WSN 的特定需求做出相应改变，而且没有考虑对于 WSN 性能至关重要的能耗问题。 Zhang 等人在研究了三种不同的基于蚂蚁的 WSN 算法，然而，作者仅仅关注信息素初始分布的建立，在系统启动效率方面具有一定的优势。 有的文献通过在蚂蚁算法的下一跳选择公式中引入偏转角的概念来优化路径并利用蚂蚁算法的正反馈效应来完成数据汇聚从而达到节 省能量的目的。 但是，该算法要求每个节点都必须配备有定位设备如 GPS 系统，很大程度上限制了它的适用范围。 国外蚁群算法研究现状 20 世纪 40 年代到 50 年代期间，法国昆虫学家 Grasse 在研究白蚁的生物群体行为时，首次提出了媒介质网 (stigmergy)的概念，来描述白蚁个体之间间接交流信息的特殊方式。 媒介质与其他的交流方式主要有两点不同：首先，它是昆虫间接感受周围物质世界的改变而释放出来的物理的 (physical)、非符号化 (nonsymbolic)、非语言层次上的沟通媒介；其次，它只能被接触到媒 介质的昆虫感知，也就是它具有局部被感知的特性。 媒介质的这种特性在著名的双桥实验中有详细的研究，并成为激发计算机科学家提出蚂蚁系统阳 (第一个 ACO 算法 )的直接源泉。 蚁群算法是有意大利学者 ， ， 等人在 20 世纪 90 年代初首先提出来的它是继模拟退火算法、遗传算法、禁忌搜索算法，人工神经网络算法后的有一种应用于组合优化问题的启发式搜索算法。 生物界的昆虫和其他群居动物的群体智能 (swarm intelligence) 行为一直是科学家进行科学研究的灵感源泉。 1979 年，R． Hofstadter 首次提出了人工蚂蚁的概念，探讨了具有较低智能的简单个体间能否通过相互作用而产生较高的群体智能行为 .从此，蚁群的链式反应行为 (autocatalytic behavior)哈尔滨远东理工学院学士学位论文 3 或正反馈 (positive feedback)特性受到越来越多的关注。 ACO的思想是由在意大利米学者 等人于 1991 年提出的。 从 1991 年到 1996年， M Dorigo 等人就蚁群搜索食物的过程与旅行商问题 (TSP) 之间的相似性 , 通过人工蚂蚁搜索食物的过程做了一定的研究，先后提出了三种模型： antquantity, antdensity和 antcycle。 这三种模型的主要差别是在于对信息素浓度的变化采取不同的数学公式。 直到 1996 年， M Dorigo 在发表了系统的关于蚂蚁系统 (AS)的全面论述，总结了这三种模型。 在这篇论文中 M Dorigo 引入了 antcode 模型，并针对 TSP 问题做了一系列实验，和其他只能算法做了比较，阐明了 AS 的强壮性 (robust)，多适应性 (versatile)和基于群体性 (populationbased)。 2020 年， P． Deepalakshmill 提出了 ARMAN 算法，在原有蚁群算法数学模型上，加入了路径选择偏好概率，通过偏好概率选择移动网络中从源节点到目的节点的多重路径，最终得到的路径时延更小、带宽更高、抖动更少。 蚁群优化 (ACO)是由意大利学者 M． Dorigo 等人作为求解著名旅行商问题 (TSP)的启发式算法而提出的，它是模拟自然界中蚂蚁搜索食物行为而提出的一种启发式智能进化算法。 由于蚁群优化算法具有正反馈性、分布式并行计算机制、较强的鲁棒性等特点 ，可用于求解基于分布式网络的最优路径计算，如路由、负载平衡和计算机网络中的多路传输等方面。 Laura Rosati 等人在 2020 年提出 DAR(Distributed Ant Routing)协议，它是一种按需的路由协议，相对于主动式路由，它可以减少路由时的网络负载。 前向蚂蚁只负责收集关于交叉节点的 ID 信息，它在使用概率公式计算选择下一跳节点的概率时只使用信息素值作为参数。 而后向蚂蚁在返回过程途中只释放常量值的信息素值。 在 DAR中。 每个路由节点中路由表都是随机的：下一跳节点是依据概率值的大小进行选择的。 这个概率值是通过以前蚂蚁走过时留下的信息素进行计算的。 但是 DAR 算法要让蚂蚁记录经过的节点，不适用于大型网络，同时 也容易陷入局部最优解，网络的收敛速度也不快。 课题研究内容 无线传感器网络 (Wireless Sensor Network． WSN)是继 Inter 之后随着无线通信技术、传感器技术、微电子技术和分布信息处理技术发展起来的一种新兴信息获取技术。 WSN 综合了嵌入式技术、传感器技术、通信技术和分布式信息处理技术，能够协作实时感知、监测、采集网络分布区域内的各种环境的信息，并对数据进行适当的处理以获得精简准确的信息，并传送给最终的用户。 在 WSN 中，每个传感器结点的路由选择过程和蚂蚁的觅食寻优行为具有极 大的相似性，因此，利用蚁群优化来设计 WSN 的路由算法具有理论上的可行性。 基于此，我们把传感器结点模拟成蚂蚁，把传感器的路径选择模拟成蚂蚁的觅食路径选择路径的启发式信息模拟成蚂蚁在路径上释放的信息素，提出了一种基于蚁群优化的路由算法。 蚁群算法是一种来自大自然的随机搜索寻优方法，是生物界的群体启发式行为，现己陆续应用到组合优化、人工智能、通讯等多个领域。 蚁群算法的正反馈性和协同性使其可用于分布式系统，隐含的并行性更使之具有极强的发展潜力。 从数值仿真结果来看，它比目前风行一时的遗传算法、模拟退火算法等有更好的适 应性。 但是蚁群算法毕竟是一种新兴的模拟进化算法，还缺乏坚实的数学理论基础，算法的参数选择、收敛性等还有待进一步研究，算法的最优停止条件也是值得研究的地方。 目前，关于算法的参数选择大都与具体问题的应用结合，通过实验进行确定，而算法的停止条件则采用固定循环次数或当进化不明显时停止迭代作为条件。 本文探讨了蚁群算法的原理、特点及功能；对基本蚁群算法的有关参数的合理选择进行实验分析；提出了相应的改进策略，并通过仿真实验，验证了改进算法的有效性，提高了寻求最优路哈尔滨远东理工学院学士学位论文 4 径能力；分析了基于蚁群算法的网络路由优化。 采用该算法并 把该算法应用于 zigbee 无线网络中，平衡了 zigbee 网络的缺点可以提高网络的确定性服务质量，提高网络路由节点的平均寿命，寻求网络中任一俩个节点的最优路径，提高数据包成功发送速度，同时平衡网络带宽、时延节省费用，并对他们进行限制，保证在网络出现过载拥堵情况时，重要数据不受延迟或丢弃。 蚁群算法显示出它在无线传感器网络路由方面的优势。 所以利用蚁群优化的特点和优势提出了一种基于蚁群优化的 zigbee 路由算法，根据 zigbee 路由策略和蚁群优化的特点，构造了人工蚂蚁使算法具有较好的节能性和全局寻优能力，并改善网络 的性能。 提出自己的思路和做法，达到网络优化的目的。 本章小结 采用在无线传感网络路由方面显示出独特优势的蚁群优化 zigbee 路由算法，可以提高网络服务质量，延长寿命，节省费用。 因此基于蚁群算法的传感器网路由协议得到了国内外学者的大量的关注。 由于利用了正反馈原理，协同性以及隐含的并行性更使之具有极强的发展潜力，并且可以理解为一种特殊的强化学习算法。 根据 zigbee 路由策略和蚁群优化的特点，构造了传感器结点使算法具有较好的节能性和全局寻优能力，并改善网络的性能，达到网络优化的目的。 哈尔滨远东理工学院学士学位论文 5 第 2 章 无线网络蚁群 算法路由技术 生物界的昆虫和其他群居动物的群体智能，行为一直是科学家进行科学研究的灵感源泉，随着各学科门类的交叉综合，群体智能已经成为解决计算问题的新兴的方法。 1979年， Dougls R． Hofstadter 首次提出了人工蚂蚁的概念，探讨了具有较低智能的简单个体间能否通过相互作用而产生较高的群体智能行为。 从此，正反馈特性受到越来越多的关注。 蚁群算法简介 蚁群算法基本概念 蚁群算法是一种基于蚁群系统原理的、具有自组织能力的、新型的启发式优化算法。 蚁群系统基本原理，人工蚁群系统 (通常简称 蚁群系统 )用于通过信息素痕迹和启发信息的指引来构造解。 人工蚁群是受到真实蚂蚁觅食行为的启示而提出的，这个行为使蚂蚁可以在食物源和蚁巢之间找到最短路径。 最初，蚂蚁以随机的方式探索蚁巢周围的区域，一旦一只蚂蚁找到食物源，它会评估食物的数量和质量，并搬运一些食物回到蚁巢。 在回程中，蚂蚁在地面上留下一种被成为信息素的挥发性分泌物，留下的信息素数量取决于食物的数量和质量。 图 21 蚁群觅食源点到结点的路径选择 对于一条路径，选择它的蚂蚁越多，则在该路径上蚂蚁所留下的信息素的强度就越大，而强度大的信息素会吸引更 多的蚂蚁，从而形成一种正反馈。 通过这种正反馈，蚂蚁最终可以发现最短路径。 在 ACO 算法中，信息素轨迹通过一个被称为信息素模型的参数化概率模型模拟。 信息素模型由一系列模型参数组成，这里的模型参数值被称为信息素值。 如图所示 , 蚂蚁从 A 点 (蚁巢 ) 出发 , 速度相同 , 目的地在 D 点 (食物 ) , 可能随机选择路线 ABD 或 ACD。 假设初始时每条分配路线一只蚂蚁 , 每个时间单位行走一步 , 图中上图为经过 9 个时间单位时的情形：走 ABD 的蚂蚁到达终点，而走 ACD 的蚂蚁刚好走到 C 点，为一半路程。 图中下图为经过 18 个时间单 位时的情形：走 ABD 的蚂蚁到达终点后得到食物又返回了起点 A，而走 ACD 的蚂蚁刚好走到 D 点。 假设蚂蚁每经过一处所留下的信息素为一个单位，则经过 36 个时间单位后 , 所有开始一起出发的蚂蚁都经过不同路径从 D 点取得了食物，此时 ABD 的路线往返了 2 趟，每一处的信息素为4 个单位，而 ACD 的路线往返了一趟 , 每一处的信息素为 2 个单位，其比值为 2:1。 寻找食物的过程继续进行，则按信息素的指导，蚁群在 ABD 路线上增派一只蚂蚁 (共 2只 )，而 ACD 路线上仍然为一只蚂蚁 . 再经过 36 个时间单位后 , 两条线路上的信息素单位 积累为 12 和 4，比值为 3B1。 若按以上规则继续，蚁群在 ABD 路线上再。