蚁群路由算法（共8篇）
蚁群路由算法 篇1
摘要：通过研究蚂蚁寻食的轨迹,分析推理出一种得到最优路径的并行算法,由于其灵感来源于蚂蚁,所以起名为蚁群算法。蚁群算法是近年才发展起来的,成功应用于很多领域,如车辆调度问题、分布式人工智能研究、负载平衡、大规模集成电路设计、工厂生产计划制定方面、图像着色和路由算法方面等等。本文主要是运用蚁群算法,寻找Ad Hoc网络中最优路由路径,使整个Ad Hoc网络成为一个稳定可靠的网络系统。
关键词：蚁群算法,网络路由
1 引言
蚁群算法最初是由M.Dorigo等人于1991年提出的。后来蚁群算法引起了很多领域研究者的注意与关注。蚁群算法是通过分布式求解模式来解决优越问题,经过很多学者的改进,目前已发展成相对成熟的算法体系。它能够将全局优化特征与问题求解的快速性、有限时间内答案的合理性相结合,快速找到最优解。而Ad Hoc网络环境中路由的选择类似于蚁群寻找食物的场景,所以将蚁群算法应用到Ad Hoc移动网络的网络路由选择是比较合适的一种算法。
2 蚁群算法概念
2.1 蚁群觅食过程
所有蚂蚁在不知道哪里有食物的情况下,在周围寻找食物。当有一只蚂蚁找到食物后,会释放一种挥发性物质———信息素扩散到周围,该信息素的扩散范围由近及远渐渐减少,它能吸引周围蚂蚁过来,这样越来越多的蚂蚁找到了该食物。有些发现信息素的蚂蚁会另辟捷径找到这个食物,如果这些蚂蚁新开辟的路径比其他路径短,则逐渐地更多的蚂蚁会吸引到这条路上来。最后,随着越来越多的蚂蚁往该食物的目的地移动,并且大多数蚂蚁会按照最短路径去找到该食物。
2.2 蚁群算法的特点
蚁群算法是通过个体间相对简单的信息传递,得出从源点到目的地之间的最短路径,它是一种集体寻优的算法。根据分析,我们得出蚁群算法有很多特点,主要有几点,如图1所示。
并行性:蚁群算法具有并行性。在蚁群搜索算法中,每只蚂蚁都是同时进行搜索的,彼此独立,它在空间多点同时开始独立解搜素,一方面使得算法具有较强的全局并行搜索能力,另一方面使得算法的可靠性增加。
较强的鲁棒性:蚁群算法不需要知道初始路线,不依赖于初始路线的选择,在搜索过程中可自发完成不需要人工干预。
正反馈性:在2.1一节中蚁群觅食过程中,我们发现最优路径的搜索直接依赖与最短路径上信息素的多少,信息素的积累是一个正反馈的过程。在不限定初始路径的情况下,给予微小的触动,就会使得正反馈不断累积找到最优解,所以正反馈是蚁群算法得以演化成最优解的一个重要的特点。
自组织性:系统论中有自组织和它组织两类,而蚁群算法属于一种自组织的算法。该算法不需要外界的特定干预就可自己搜寻出最优解,所以说它是一种自组织算法。当蚁群算法开始时,每个蚂蚁无序的随机的寻找路径,经过一段时间,信息素积累,自发的越来越多的蚂蚁找到了最优路径的过程,从无序到有序的过程。
3 Ad hoc网络路由
3.1 概述
Ad hoc网络又称为自组织网,无基础设施网或多跳网,它是一种无中心的移动自组织网络。在Ad Hoc的整个网络中,很多个终端节点都是可移动的,没有固定的基础设施,每个节点都可以任意方式地动态地与其它节点进行关联。这样使得两个无法直接进行通讯的节点可以借助网络中的其他节点进行转发通讯。而在网络中的每个节点都有路由功能,它能够发现并维持与其他节点的关联。
目前,由于无线通信和终端技术的不断发展,Ad Hoc网络在民用环境下也得到了发展,如需要在没有有线基础设施的地区进行临时通信时,可以很方便地通过搭建Ad Hoc网络实现。在Ad Hoc网络中,当两个移动主机在彼此的通信覆盖范围内时,它们可以直接通信。但是由于移动主机的通信覆盖范围有限,如果两个相距较远的主机要进行通信,则需要通过它们之间的移动主机B的转发才能实现。因此在Ad Hoc网络中,主机同时还是路由器,担负着寻找路由和转发报文的工作。在Ad Hoc网络中,每个主机的通信范围有限,因此路由一般都由多跳组成,数据通过多个主机的转发才能到达目的地。故Ad Hoc网络也被称为多跳无线网络。
3.2 Ad Hoc网络的特点
Ad Hoc网络作为一种新的组网方式具有很多特点。
带宽有限:由于Ad Hoc网络中没有有线基础设施的支持,主机节点之间的通讯都是通过无线网络传输的,所以在Ad Hoc网络中的无线通讯带宽有限。
动态变化:由于Ad Hoc网络中所有的主机节点是可以移动的,主机之间的关系会不断发生变化,所以网络的主机节点是动态变化的。
独立性:Ad Hoc网络最大的特点就是不依赖现有的网络通信设施,具有一定的独立性,适合灾难救助、偏远地区通信等应用。
主机能源有限:由于在网络中的主机都是移动式的,如便携计算机、pad等,这些主机的能源主要由电池提供,因此Ad Hoc网络有能源有限的特点。
分布式特性:在Ad Hoc网络中没有中心控制节点,主机通过分布式协议互联。一旦网络的某个或某些节点发生故障,其余的节点仍然能够正常工作。
物理安全有限:Ad Hoc网络的分布式特性相对于集中式的网络具有一定的抗毁性。
生存周期短:Ad Hoc网络主要用于临时的通信需求,相对与有线网络,它的生存时间一般比较短。
4 蚁群算法应用到网络路由算法
在网络路由处理中,网络的流量分布不断变化,网络链路或结点也会随机地失效或重新加入。蚁群的自身催化与正向反馈机制正好符合了这类问题的求解特点,因而,蚁群算法在网络领域得到一定应用。蚁群觅食行为所呈现出的并行与分布特性使得算法特别适合于并行化处理。因而,实现算法的并行化执行对于大量复杂的实际应用问题的求解来说是极具潜力的。
设网络中有四个节点1,2,3,4。要实现1和4之间的通信,由于无线网络通讯距离有限或者延迟方面的限制,1和4之间无法直接进行通信,但是它们可以借助2和3进行通讯转发,但是借助2和3通讯会有2条通信支路:1-2-4和1-3-4,这两条通讯支路的长度是不同的,如图2所示。
我们应用蚁群算法的思路,假设在节点1有两只蚂蚁,蚂蚁A和B由节点1向节点4爬行,而与此同时,在节点4处也有两只蚂蚁,正在向节点1爬行。由于最开始,在2和3两条路上的信息素是不存在的,所以蚂蚁选择两条路的概率是相同的。我们假设蚂蚁A和蚂蚁C按照1-2-4和4-2-1的路线爬行,蚂蚁B和D按照1-3-4和4-3-1的路线爬行。假设蚂蚁行进的速度近似相同,一段时间之后蚂蚁B和蚂蚁D经过支路1-3-4和4-3-1的路线分别到达节点1和节点2,而蚂蚁A和蚂蚁C依然还在1-2-4和4-2-1的路线中,如图3所示。
在蚂蚁行进的过程中,每个蚂蚁均留下了同样数量信息素的痕迹。这时路线1-3-4上留下的信息素明显要高于路线1-2-4上的信息素浓度,如果之后还有其他蚂蚁需要从1到达4节点时,受信息素的诱导,选择1-3-4的概率很大。一段时间后,选择走路线1-3-4的蚂蚁会越来越多,而选择走1-2-4的蚂蚁会越来越少,最后呈现较强信息素痕迹的那些支路会变成形成一条从节点1到节点4的最短路径。
5 结束语
由于蚁群算法的各种特点与Ad hoc网络中的场景非常类似,使其在这方面的应用非常成功。随着蚁群算法的不断改进和各种技术领域的不断发展,蚁群算法的应用进展以蚁群算法为代表的蚁群智能已成为当今分布式人工智能研究的一个热点,许多源于蜂群和蚁群模型设计的算法己越来越多地被应用于企业的运转模式的研究,该算法还被用于求解Job-Shop调度问题、二次指派问题以及多维背包问题等。
参考文献
[1]詹士昌,徐婕,吴俊.蚁群算法中有关算法参数的最优选择[J].科技通报,2003年05期.
[2]胡小兵,黄席樾.对一类带聚类特征TSP问题的蚁群算法求解[J].系统仿真学报,2004年12期.
[3]周四望等.无线传感器网络中基于数据融合的移动代理曲线动态路由算法研究[J].计算机学报,2007.30(6):894-904.
[4]王开义,赵春江,胥桂仙,宋晓宇.GIS领域最短路径搜索问题的一种高效实现[J].中国图象图形学报.
[5]冀俊忠,黄振,刘椿年.基于聚类和分段优化的蚁群算法[J].北京工业大学学报,2008年04期.
[6]徐京,张彦,辛阳等.高速网络内容监控系统的关键技术分析.信息网络安全,2012(10)29-35.
[7]徐国天.基于OSPF路由欺骗的网络监听技术研究.信息网络安全,2012,10,10-12.
基于蚁群算法的水果图像分割技术 篇2
关键词：水果图像；蚁群算法；图像分割；四维向量
中图分类号： TP391.41；S126文献标志码： A文章编号：1002-1302（2014）09-0380-02
收稿日期：2014-06-22
基金项目：江苏省自然科学基金（编号：BK2012128）。
作者简介：杨业娟 （1981—），女，江苏盐城人，硕士，讲师，研究方向为图形图像处理、数据挖掘、管理信息系统。E-mail：yangyejuanvip@126.com。随着计算机技术的发展，尤其是手机等移动数字成像设备的广泛应用，利用移动数字成像设备进行各领域的图像识别和处理已经成为未来发展趋势，其应用的关键在于根据应用需求解决图像中关注目标的检测和识别。首先需要通过图像分割技术从采集的图片中把目标对象与其所在环境互不重叠地划分成多个区域。再针对确定的目标对象所在区域，对被识别对象进行特征的提取与识别，从而帮助用户进一步完成其所需要的图像识别和处理应用。由于目标对象在采样成像过程中存在自然光源不稳定、目标对象移动、目标对象与环境中附属物之间以及多个目标对象之间的遮挡等问题，造成移动数字成像设备在图像识别与目标对象定位的工作中效率低，很难找到一种适合各类采摘目标的通用图像分割方法。郭艾侠等提出一种基于探索性分析的荔枝果实与枝叶的识别方法，通过在YCbCr严肃空间内，合理设定Cr分量阈值实现对荔枝果实的准确分割[1]；张善文等采用Ostu算法实现对植物病害图像中叶片的有效分割[2]；周洪刚等采用Ostu分割算法与面积阈值法相结合实现对成熟柑橘的自动识别[3]；郭艾侠等将二次阈值分割方法应用于分割荔枝果实图像，取得了较好的分割效果[4]；谢忠红等结合图像颜色模型，通过采用Ostu算法自动实现了对彩色水果图像的精确分割[5]；王开义等结合分水岭与改进的马尔科夫随机场模型对马铃薯丁粘连图像进行分割[6]。受到以上研究成果的启发，本研究尝试将蚁群算法（ant colony algorithm，ACA）[7-8]这一来源于生物种群仿真的启发式寻优算法对具有复杂背景的水果图像进行分割。
1水果图像分割算法
要实现对图像中目标信息的准确识别，就必须考虑识别图像的内容区域构成。通过移动数字成像设备对自然环境下水果的采样图像一般都是复合图像内容，在整个图像中主要包括：水果实体、部分细小果枝和叶片、背景环境和其他一些细缝或者阴影所产生的浅黑色等多种图像的区域。要实现对图像中水果目标的识别提取，有必要对图像进行区域分割，从而便于后续找出对应的水果图像。
为了解决水果图像中各部位的分类识别问题，文献[1-2]通过对强光、普通光和逆光3种光线照射条件下获取的水果图像进行探索性数据分析，发现该研究对象的果实体与叶片等主体内容的颜色为偏红、偏绿和偏褐等，建立了水果图像YCbCr色彩空间中最佳色彩模型为Cr单通道图，并以此为基础设定出合理的阈值分割水果图像的YCbCr色彩图，通过去除图像中的叶片、侧枝以及环境等背景信息，取得了较好的识别效果。但是在实际生活中不同水果具有不同的颜色特点；水果目标与其背景之间有的存在较大的颜色差别，导致水果识别时用单通道分量图进行分割处理虽然可以缩短图像处理时间，但是会影响目标识别效率。若采用K-Means、C-Means等模糊聚类的图像分割方法对水果图像进行处理时，对于背景颜色与水果颜色差异较小的情况，该方法会把与水果颜色相近的背景区域和水果同类化，导致水果与背景的误分类。考虑移动数字成像设备对自然环境下水果的图像采集一般都是RGB彩色图像，并且水果自身的颜色具有多样性，本研究尝试将蚁群算法应用于水果图像分割处理。
实地拍摄的水果图像一般为RGB彩色图像，人们肉眼识别水果也多是通过水果的颜色特征，单通道分量图的图像分割方法不能充分利用图像中丰富的颜色信息，因此识别效率和实用性不佳。本研究基于蚁群算法进行图像分割，则要充分利用图像中的颜色特征来构建模糊聚类处理方法。以原始图像的R、G、B 3 色直方圖为基础，选择3色直方图的k个峰值点作为水果图像的颜色聚类中心特征，将大量的像素聚类分析循环计算简化为仅在少数几个聚类中心峰值点之间的分析比较，通过引导蚁群算子在聚类中心附近进行迭代计算，从而提高计算效率。
由于水果表皮上通常都含有一定量的蜡质层，很多水果在成像时会有明显的反光现象，这种反光在水果图像中通常以亮斑或亮度增强区域的形式表现出来，亮斑从颜色角度可看作R、G、B 3色的综合影响，因此会对图像的划分造成干扰。为了削弱亮斑对图像分割的干扰，需要对亮度进行处理，对亮度较大的区域需要进行3色的综合弱化，通过一群算子迭代将其与相邻像素同化。
在水果图像中，水果目标果体和背景的区域划分通常还需要考虑图像在像素梯度方面的特征，一般果体、枝、叶和背景物的内部像素梯度变化较小，而边界和噪声的像素梯度变化较大，而且内部梯度变化较小的像素占多数，边界像素数又大于噪声像素数，因此可以在水果图像的R、G、B 3色直方图及图像梯度基础上进行如下处理：以k个聚类中心为计算核心逐一检验，聚类中心的3色直方特征对应的像素个数较多的，则该聚类中心一般情况在果体、枝、叶和背景物的内部，令其梯度特征为零；而对聚类中心的3色直方特征对应的像素个数较少的，令其梯度值为最大梯度列的均值。
对于二维的水果图像，根据上面的像素梯度划分和图像中不同类别像素的相邻像素梯度特征表现，定义邻域特征：（1）
梯度为零的聚类中心，令其邻域特征为8，则该聚类中心为像素区块内部；（2）
对于梯度值较高的聚类中心，若3色特征对应的像素数目较多，则可令其邻域特征点数目为6，则该聚类中心为边界；（3）
梯度值较高的聚类中心，如果灰度特征对应的像素个数较少，令其邻域特征为3，则该聚类中心为噪声。
综合上述3原色、亮度、梯度和邻域的影响，本研究构建的蚁群图像分割处理算法如下：
所选定初始聚类中心表示为：Ci（P，B，G，N），i=1，…，k。对于给定水果图像P，定义每个像素Pj 可作为1只蚂蚁，每只蚂蚁则将3原色、亮度、梯度和邻域作为特征的四维向量，图像分割求解实质上是这些蚂蚁搜索食物源的聚类问题求解过程。任意图像像素点Pi 到Pj 的欧氏距离为lij：
基于蚁群算法的可信网络路由 篇3
关键词：路由,重组,蚁群算法,可信计算
网络应用的日趋广泛增加了对信息传输的实时性和稳定性的要求。作为一种比较完善的网络管理制度,网络重组能很好地保证网络运行的可靠性和安全性。当传输链路或网络节点出现故障时,具有重组机制的网络就能及时地处理由链路故障或节点故障所造成的问题,恢复正常的通信,保证网络的可靠和安全。作为网络重组中的重要内容,在路由重组的有效性和可操作性(即可信机制)的研究中引入可信计算,提高网络路由重组结果的可信度,以增强动态网络的可靠性。
可信计算技术最早于1999年由TCPA(TCG的前身以可信概念为基础提出[1]。可信计算组织TCG用实体行为的预期性来定义可信:如果它的行为总是以预期的方式,朝着预期的目标,则一个实体是可信的。可信计算技术的本质就是通过信任度技术来对计算环境的可信度进行度量,只有当前计算环境可信时,才认为当前的计算是值得信赖的。在TCPA制定的规范所定义的可信计算的属性中,信息的完整性就是用户确保信息能被正确传输。因此在路由重组算法的研究中,以可信因子来描述重组时路由环境的真实情况,从而提高路由重组结果的有效性。
本文使用的路由算法是一种由M.Dorigo[2]等提出的解决组合优化问题的多Agent方法———蚁群算法。这种算法可以应用于许多最优化的问题,在旅行商问题(TSP)、二次分配(QAP)、车间调度问题(JSP)以及作业排队等问题[3]上均有出色的表现。蚁群算法的最优化是一种许多蚂蚁寻找较优路径的渐进过程。每只蚂蚁通过一系列的抉择一步步地各自建立一种解决方法。找到较优方法的蚂蚁在其经过的路径上标识一些信息素,随后而来的下一代蚂蚁会受到信息素的影响而趋向于选择较优的方法。
本文将蚁群算法用于网络路由中,在综合考虑了路由耗费和延时两个因素的影响后[4],研究这些蚂蚁的搜索行为如何对在多个节点和路径之间找寻最短路由进行控制和管理。通过在信息素更新公式和路由选择上的改进,将网络路径的带宽限制作为路由重组成功与否的一个因素加入到路由重组算法中,以此作为描述路由环境的可信因子,在提高了算法的搜索效率的同时,使组播路由的带宽耗费较均匀地分配于链路中,来降低由于多个路由耗费超过链路带宽限制所造成的传输失败的概率。从而提高这种网络路由的可信度。
1改进的蚁群算法数学模型
蚁群算法是受真实的蚂蚁群体路径寻优方式的启发而提出的。如果有一只蚂蚁随机选择了一条较短的路径,那么它就能在较短的时间来回,并在该条路上留下信息素。而这些信息素又会吸引其他蚂蚁也选择这条路径,导致最短路径上遗留的信息素越来越多,从而形成一种正反馈。其本质上是一种以信息素为媒介,通过群体智能来散布最优解信息,采用逐步收敛的方式来求解最优解的方法。而网络中的路由选择就是这种选择最优路径的问题。并可以通过路由选择不同的策略,使组播路由对各条链路带宽的耗费均匀化,以降低传输失败的概率,从而提高路由选择结果的可信度。应用于重组网络中的蚁群算法可以用移动智能体间的交互来实现[5]。对应于不同的应用,这些交互可以是直接、间接或者本地的。最终达到及时进行可信网络重组的目的。
用G(N,L)来表示所构建的网络。N是网络中的节点集,L是连接节点的链路集,用V来表示网络中链路的数量。L(i,j)表示节点i和j之间的链路,C和D分别代表链路耗费和延时集,Tk为第k只蚂蚁已经经过的节点集。W为每条链路的最大带宽Wl的集合。
假设在网络G中有P个路由请求,不同的路由请求可能经过相同的链路,而每个路由r所耗费的链路带宽为Br。在获得最少链路延时和耗费的前提下,可能有多条不同的路由请求经过同一条链路。由于每个路由请求均会耗费链路的带宽,就可能造成同一条链路上各条路由请求所耗费的带宽总和要高于这条链路的最大带宽限制。这在实际的环境中是很容易出现的状况,当链路带宽无法满足传输的需要时,就会造成信息传输的成功率下降,进而影响路由重组策略的性能。因此,为了让不同的路由请求经过同一条链路时所耗费的总带宽不超过链路的最大带宽限制,就需要在路由选择上进行变动,以使不同的路由请求较均匀地分布于网络中,达到负载平衡。不但减小了由于多条路由请求始终集中于少数几条较优路径所带来的网络不稳定性,而且降低了由于链路带宽不足而引起的传输问题,实现了可信的网络路由重组。
首先定义每条链路的带宽利用率ηl来衡量网络中的负载平衡:
总的带宽利用率:
其中,若第i次路由请求经过链路l,则ρi l的值取1,其他则取0。
基于式(1)和式(2),可以使用带宽利用率的方差δ2来衡量网络负载平衡的情况:
从式(3)中可以看到,δ2的值越小,则不同路由请求的负载分布得越均匀。即不同的多条路由请求同时经过同一条链路的概率越小,则由于链路带宽不足而造成的信息通信问题的数量将显著减小。从而降低传输失败的概率,提高了路由选择结果的可信度,即提高了路由重组结果在实际信息传输时的成功率,进而实现了可信的网络重组。
将蚁群算法用于可信网络重组时需要用到下列公式(4)～(7):
(1)信息素更新公式:
τi j(t)表示在t时刻边L(i,j)上的信息素浓度,ρ为信息素的迹的保持度,则1-ρ为信息素在t和t+1之间的挥发程度。式(4)便是一只蚂蚁在完成一次对n个节点的路由之后,信息素的更新公式。对于多播路由,不同路由请求间的信息素即使在同一条链路上也互不干扰,即不同蚂蚁分泌的信息素各不相同,蚂蚁的种类代表了路由请求的数量。
(t,t+n)为第k只蚂蚁在时间段t和t+n之间遗留在路径L(i,j)上的信息素,m为每一轮的蚂蚁的个数,(t,t+n)由式(6)决定:
其中Q是一个常数,将Lk的定义为Lk=Q/((β·Ck+γ·Dk)/(β+γ)+σ·δ2),Ck和Dk分别为第k只蚂蚁完成一次从起始点到结束点的路由所经过链路的总耗费和总时延,δ2如式(3)所示,通过考虑δ2的因素将不同路由对带宽利用的影响作用于每次路由请求中。β、γ和σ分别用来表示路由耗费、路由延时和带宽利用率方差对信息素更新的影响因子。在此项中增加了这些内容,由于在信息素更新公式中考虑了带宽利用率的影响,使得整个算法都受到了式中这几个因素的影响,因而使算法的收敛性得到了有效的提高。从带宽利用率方差的定义结合蚁群算法的迭代过程可以看出,在式(6)的作用下,网络中不同路由的负荷将更加均匀化,从而如前所述提高了路由重组结果的可信度,即有效提高了路由重组结果用于实际信息传输的成功率。
(2)节点选择概率:
其中ηij=1/Cij为考虑路径耗费因素的项,νij=1/Dij为考虑路径延时因素的项。式(7)中综合考虑了耗费和延时对选择概率的影响,模拟实际的网络环境因素的影响,从而对路由的最优选择给出了评价标准,即寻找使耗费和延时达到最小的路由。α、β和γ分别用来表示信息素的迹、路由耗费和路由延时对选择概率的影响因子,α,β,γ≥0。Tk(t)为在t时刻蚂蚁k已经经过的节点的集合。
2改进后的路由重组策略
本文中所构建的用于实现重组策略的网络具有在扩展网络规模时增加节点,以及在某些节点出现问题时将其从网络中删除的功能。在随后的路由中会根据网络的变化来更新路由的路径,使得动态网络具有更好的鲁棒性。
每轮均用到M只蚂蚁需要完成两个任务,即依据信息素浓度来选择移动到下一个节点,以及更新每条路由上的信息素浓度。对于第一个任务,在考虑了路由耗费和延时的情况下给出了式(7),依据式(7)给出的概率大小通过轮盘赌选择法来选择路由,即节点被选中的概率与节点选择概率的大小成正比。对于第二个任务,使用式(4)来更新每条链路上的信息素浓度,并通过式(6)中的因子来控制信息素,从而在获得相对最优路由的同时,使不同路由的选择在网络中的分布更加均衡。对多播路由来说,在网络中可能同时有多个路由请求,因此结合蚁群算法,就需要有和路由请求个数相同的蚂蚁种类,且不同蚂蚁所分泌的信息素互不干扰。为了降低多个路由请求同时经过同一条链路的概率,并满足最大时延的约束,当某只蚂蚁所选择的路由无法到达目的节点时,会将此蚂蚁所经过的路由标示为忽略状态,随后进行下一轮寻优。
假设有K轮的蚂蚁群在网络中寻找最优路径,每一轮有M只蚂蚁。则路由重组策略的具体实施步骤如下:
(1)为所有的蚂蚁初始化数据结构,设定所有链路上的信息素初始值,并定义每条链路的最大带宽。
(2)启动到P个目的节点的K轮蚂蚁觅食活动,每轮派出M只蚂蚁。到不同目的节点觅食的蚂蚁种类各不相同,因此在相同链路上所分泌的信息素也互不影响。且不同路由请求会各自占用所经过链路的相应带宽。
(3)对每只蚂蚁来说,判断所连接的节点链路是否是已经过的路径,然后依照式(7)的选择概率来选择要移动到的下一节点。如果所在的节点为起始点,则随机选择移动的下一节点。记下每一代每一只蚂蚁的觅食路线和路线长度。将选择的节点加入记录所经过节点的表格。用式(4)更新所经过的链路上的信息素浓度。
(4)下一轮的蚂蚁重复步骤(3),直到所有蚂蚁都完成这些步骤。如果其中有蚂蚁没有到达目的节点,则将此蚂蚁所走过的路由标示为忽略状态,然后再重复步骤(3)。
(5)结束K轮寻优过程,得出最终结果。
3仿真结果
图1所示为仿真实验所构建的具有8个节点的网络拓扑图,在每条链路上都有路由耗费和延时数值,用以模拟真实网络环境。对于这种网络结构,可以通过增加或删除节点间的链路来改变网络拓扑结构,从而模拟真实网络的路由重组。假设每个节点自身的耗费和延时均为1个单位,每条边的耗费和延时情况用元组
假设有两个路由请求,分别是从节点1到节点6,以及从节点1到节点8。分别用(1,6)和(1,8)来表示。仿真的参数设置为:N=8,K=30,M=100,α=4,β=6,γ=6,ρ=0.8,Q=10。其中α和β的值设为一样,就是将链路耗费和延时对信息素的影响视为同等大小。假设每条链路的最大带宽均为9,2个路由请求在所经过的链路上分别占用的带宽为5。因此若2个路由同时经过同一条链路,则共同占用的带宽达到了10,已经超过了链路所提供的最大带宽9,容易造成此次路由的失败,降低了寻优结果的可信度。为了提高路由的可信度,应在保证路由耗费和延时较小的同时,减少2条路由经过同一条链路的情况。
仿真结果如表1所示。对于常规的蚁群路由算法,(1,6)和(1,8)这两个路由请求经过了多条相同的链路,这是由于节点6和8在所构建的网络中是相邻的节点,在单纯只是寻找最低耗费和延时总数值的路由中,分别到达这两个节点所经过的路径必定会有多条重复。为了提高路由结果的可信度,改进的算法减少了不同路由请求经过相同链路的数量。基于可信路由算法的结果让(1,6)和(1,8)这两个路由请求经过不同的链路到达目的节点,但也在一定程度上增加了总耗费和延时数值,这是受各个因子相对路由结果的重要性以及网络的拓扑结构等因素影响的。在本次仿真所构建的网络中,正是由于兼顾了耗费、延时和可信度的影响,因此所选链路单独对于耗费或延时来说并非是最优路径,是综合三者所得出的选择结果。
为了使可信路由对于路由结果可信度的作用更加直观,将仿真网络的节点数扩充到100个,节点间链路的延时值和耗费值简化为两者在同一链路上取相同值,均在1～200以及无穷之间随机产生,当链路延时耗费数值取无穷时则表示两节点间没有连通。以(1,35)和(1,85)这两个路由请求为例,在此次构建的网络中,每条链路的最大带宽也设为9,每个路由请求在所经过的链路上分别占用的带宽为5。若不同的路由请求经过同一条链路,即超过了链路最大带宽9,则经过这条链路的路由成功率设为0.6,只有一个路由请求经过的链路上的成功率设为0.9,则通过分别计算路由结果的平均成功率,可以有效度量路由结果的可信度。为消除随机性对算法结果的影响,将可信蚁群路由算法运行50次后,分别与常规蚁群路由算法的成功率进行比较,仿真结果如图2和图3所示。
从图中可以看出,加入了可信的路由算法比常规的蚁群算法在成功率上有了明显的提高。尤其当路由请求增多,多条路由同时经过同一条链路的情况增加时,这条链路上传输成功率的下降将会更加明显。此时应用可信的路由算法将会获得更大的网络性能提升。
本文提出了一种基于蚁群算法来寻找网络中节点间可信路由的方法。在综合考虑了链路耗费和延时这两种因素的情况下,同时将多个路由请求对同一条链路的带宽利用情况作为影响传输成功率的因素,通过对算法中的概率选择和更新公式以及节点选择策略的改进,此算法显示出较好的收敛性。通过仿真实验证实,在所构建的网络环境中,该算法能在找到较优路由的同时,有效地提高路由结果的可信度,从而实现网络的可信路由。
参考文献
[1]Trusted Computing Group.TCG Specification Architecture Overview[EB/OL].[2005-03-01].https://www.trusted computing group.org/groups/TCG_1_0_Architecture Overview.pdf.
[2]DORIGO M,GAMBARDELLA L M.Ant colony system:A cooperative learning approach to the traveling salesman problem[C].IEEE Trans.On Evolutionary Computation,1(1)(1997):53-66.
[3]乐群星,魏法杰.蚂蚁算法的基本原理及其研究发展现状[J].北京航空航天大学学报,2005,18(4).
[4]LU Guo Ying,LIU Ze Min.Multicast routing based on ant-algorithm with delay and delay variation constraints[C].Circuits and Systems,2000.IEEE APCCAS2000.The2000IEEE Asia-Pacific Conference on4-6Dec.2000:243-246.
蚁群路由算法 篇4
由于社会发展的需要,传统有线网络无法满足用户更多类型的应用需求,公众对无线通信领域的应用标准不断提高,面向无线通信网络的应用加剧了提升通信效率方面的开发幅度和性能要求,受限的无线媒介与实际应用的需求矛盾逐渐凸显[1,2]。路由协议是运行于网络层的信息转发策略,性能优越的路由协议能够使消息的传递过程更加顺畅,使通信客户端可以通过最优的路径将信息传递给其它客户端,有效提升了网络的整体性能。无线通信协议的路径选择示意如图1所示,目前针对路由协议的开发仅仅局限在网络层本身,并没有将其与实际的数据应用相结合,通过信息手段将当前网络状况与实际协议开发相结合是目前行业发展的新趋势[3,4]。
目前,很多专家学者针对无线环境下的路由协议进行了研究。为了解决分布式编码感知路由协议中可能出现的吞吐量降低的问题,王春雨等[5]设计了一个能够进行网络编码的无线通信路由协议,达到了提升系统吞吐量的目的。IP数据包广泛应用于分布式通信网络,迫切需要网络具有自组织能力。由于单通道单一接口模型不满足复杂系统的需求,Jin等[6]建立了一个面向军事应用的分布式网络拓扑结构,并实现了基于ZRP的多渠道M-ZRP路由协议。仿真结果表明,M-ZRP具有更好的性能。
蚁群算法(Ant Colony Optimization,ACO)是根据蚂蚁群落采集食物的原理被提出和模拟而来,已被应用于诸多领域。与基于梯度的性能优化算法原理不同,蚁群算法通过概率搜索算法来完成[7,8]。虽然概率搜索算法一般需要采用价函数,但是与传统的梯度演化算法相比,其有诸多比较显著的性能,集中表现在以下方面[9,10,11]:1无集中控制约束,不会因个别个体的故障影响整个系统问题的求解,确保了系统更强更稳定的鲁棒性;2以非直接通信形式保证系统的可扩展性;3采用并行分布算法模型和多处理器运行模式;4定义问题的连续性没有限制;5算法实现相对比较简单。
OPNET Modeler中的WLAN、MANET等无线通信节点模型提供了多种成熟的路由协议,包括按需距离向量路由(Ad hoc On Demand Distance Vector,AODV)、动态源路由(Dynamic Source Routing,DSR)、地理路由(Geographic Routing Protocol,GRP)等[12,13]。
针对无线网络中存在的问题,本文提出了基于TSP蚁群算法的无线通信路由协议优化设计方法,此优化设计将TSP基本蚁群算法的基本原理和通信路由选择相结合,通过建立系统模型,依靠蚂蚁信息素含量及距离竞争机制为节点选择最优通信路径。同时,本文通过在OP-NET Modeler通信仿真软件中建立仿真场景及完成模型构建,对基于TSP蚁群算法的无线通信路由协议进行测试验证,并与其它典型无线路由协议进行对比分析,主要分析指标是传输延时及吞吐量。
1 基于TSP蚁群算法的路由协议优化设计
1.1 TSP蚁群算法模型
定义类似TSP,设C={c1,c2,…,cn}是一个节点的集合,是集合C中元素两两连接的集合,dij(i,j=1,2,…,n)是lij的Euclidean距离,如式(1),其中,xi、xj、yi、yj分别表为元素节点的坐标。
G=(C,L)表示某个有向图,TSP主要负责从有向图G中找出距离最小的Hamilton圈,此即一条对C={c1,c2,…,cn}中n个元素通过且仅通过一次的最短封闭曲线。
为模拟蚂蚁的实际行为,首先引进如下记号:设bi(t)表示t时刻位于元素i的蚂蚁的数目;n表示TSP规模,m为蚁群中蚂蚁的数目,d为节点i、j间的距离,则有:
Lk为蚂蚁k走过的路程,用一张禁忌表tabuk(k=1,2,…,m)记录蚂蚁k当前所走过的节点元素,集合随着tabuk的进化过程作动态调整。是t时刻集合C中元素两两连接lij上残留信息素的集合;τij(t)为t时刻路径(i,j)上残留信息素数量,在初始时刻各条路径上信息素浓度相等,并设τij(0)=C(C为某个正常数),基本蚁群算法的寻优是通过有向图g=(C,L,Γ)实现的,主要集中表现为路径选择策略以及信息素调节策略。
1.2 路径选择机制
蚁群算法中放置的人工蚂蚁处于离散状态中,蚂蚁根据不同节点信息素浓度选择下一个需要访问的节点。蚂蚁通过随机策略完成整个游程,整个游程的过程意味着所求问题的某个可行答案。
将m只蚂蚁随机放在n个节点上,然后在每个节点上循环利用某个特定的状态转移规则。蚂蚁在节点i与另一个没有经过的节点j间的运动运行随机转移策略,该策略以节点i、j之间路径上存在的信息素含量τij(t)以及节点间的距离为依据。Pkij(t)表示t时刻蚂蚁k由节点i转移到节点j的状态转移概率:
式中,allowedk={{1,2,…,n}-tabuk},为蚂蚁k下一步可以选择的节点;ηβij(t)是启发函数,对蚂蚁k而言,dij越小,k则越大,Pkij(t)亦越大。
显然,该启发函数描述了蚂蚁从节点i运动到节点j的期望程度,即路径(i,j)的期望程度;α,β分别描述τ、η的作用程度。α表示信息启发式因子,描述轨迹的相对重要性,其值大小表明各路径上的信息素含量的重要程度,值越大,蚂蚁越选择其它蚂蚁走过的路径的可能性就越大,但α值过大会使搜索过程陷于局部最优僵局;β为期望启发式因子,表示能见度的相对重要性,它的大小表明启发式信息的重要程度,其值越大,则该概率选择越接近于贪婪规则。当α=0时,算法即相当于传统的贪婪算法。当β=0时,此算法变为了纯粹的正反馈启发式算法。因此,蚂蚁倾向于选择通过信息素浓度大、路程短的路径。
1.3 信息素调节机制
为了避免残留信息素过多引起残留信息淹没启发信息,在每只蚂蚁走完一步或者完成对所有n个节点的遍历,即一个循环结束后,要对残留信息进行更新处理。这种更新策略模仿了人类大脑记忆的特点,在新信息不断存入大脑的同时,存储在大脑中的旧信息随着时间的推移逐渐淡化,甚至被忘记[14]。当m只蚂蚁全部完成一次节点后,形成了回路集合H(t),此集合是问题的一个可行解集合,其中第k只蚂蚁的路径长度设置为L(k,t)。当第t个搜索时刻结束后,蚂蚁会在各自的路径回路上释放信息素,其增量反比于此解的质量,每条路径上信息素总量和m只蚂蚁留在边(i,j)上总的信息素增量根据式(5)、式(6)调整。
式(5)中,参数ρ代表信息素挥发系数,则1-ρ代表信息素残留系数,为了避免信息含量的无限积累,设置ρ的范围为ρ∈[0,1);Δτij(t)描述本次循环中路径(i,j)上的信息素增量,初始时刻Δτij(0)=0,Δτkij(t)代表本次循环中第k只蚂蚁在路径(i,j)上释放的信息素量。
本文首先根据特定策略淡化路径上的信息素含量,模拟现实蚁群的信息素蒸发原理,避免了过多的残留信息造成的无用信息掩盖启发信息的弊端,蚂蚁再将自身的信息素叠加到上面。此更新规则可以使较短路径或者是其它走过蚂蚁比较多的路径积累更多的信息素,在算法的循环运行过程中,此类路径被选择的概率就越高,因此较优路径容易得到加强。
针对信息素不同更新规则,Dorigo M.设计了3种基本蚁群算法模型,分别为AntCycle模型、AntQuantity模型以及AntDensity模型。
在AntCycle模型中:
在AntQuantity模型中:
在AntDensity模型中:
式中,Q为常数,表示蚂蚁寻找路径过程中所释放信息素总量,它在一定程度上影响算法的收敛速度,本文中的Q值通过仿真获得。
本文采用的AntCycle模型,其利用的是系统全局信息,此信息更新策略能够使较短路径上对应的信息素逐步增大,保证了算法中整体范围下较短路径的生存能力,提升了信息正反馈性能,加快了系统搜索路径的效率。同时,AntCycle模型的更新规则能够保证残留信息不造成无限积累,如果某条路径没有被选中,则对应节点的信息素含量会随着时间的推移渐渐消失,使节点具备逐步淘汰劣质路径的能力,即使某条路径经常被访问也不至于因为τij(t)的积累,而出现τij≥ηij的情况,使得期望值的作用无法体现。因而,本文的蚁群算法采用AntCycle模型。
1.4 路由协议设计与实现
针对求解TSP问题的蚁群算法模型,对此模型进行修改,同时结合无线自组织网络信息传输的特点,完成基于蚁群算法的路由协议设计,简称ACAB(Ant Colony Algorithm Based)路由协议,具体实现步骤如下:
Step1:初始化各通信节点间的距离。此操作通过节点广播信息完成,每个节点被分配不同的ID,作为其在此过程中的唯一标识,广播的数据帧格式如图2所示,包括节点ID属性,当前位置坐标(x,y),是否为源节点或目的节点,如果有数据发送需求,源节点属性值赋值为1,同时将目的节点的ID进行赋值,并对发送序列进行编号,如果没有数据发送需求,则置为0。
Step2:将若干蚂蚁放在不同的通信节点中,每个通信节点维护自身的信息素列表,表中描述了当前节点的信息素含量和此刻与其它节点间的距离。信息列表的具体信息如图4所示。当节点位置移动后,此表中的数据也进行更新。
Step3:每只蚂蚁根据各节点至目的节点的距离d和信息素水平τij(t),选择下一通信节点,同时修改禁忌表。
Step4:所有蚂蚁完成周游后,更新信息列表中的信息素水平和节点位置信息。
Step5:返回Step2,迭代次数d=d+1,直至寻找到源节点与目的节点间的最优路径或者满足结束条件,最优路径的判定标准是路程最短min(Road),摒弃不必要的路径信息。
2 仿真实现及分析
通过在OPNET Modeler中建立仿真对比场景,对提出的基于TSP蚁群算法的无线通信路由协议与典型的AODV、DSR路由协议进行对比验证,分析其在传输延时及吞吐量方面的性能表现。
2.1 仿真场景建立及模型实现
OPNET Modeler采用离散事件驱动的模拟机理,通过事件驱动器以先进先出的机制对事件列表和事件时间列表进行维护管理[15]。本文设计的仿真场景中包含的通信节点由WLAN节点组成,可以通过设置其属性对其进行控制。仿真范围为1 000m2,仿真时间为30min。仿真过程中通信节点可以随机移动,物理层与数据链路层均采用基本IEEE 802.11协议,通信节点总数初步设为100,数据发送间隔为100ms,基本数据帧大小为100字节,仿真场景如图3所示。
同时,WLAN节点包含完整的OSI协议模型,本文的路由协议设计在IP层自定义完成。通信信息从WLAN收信机进入,依次经过MAC层、数据链路层、IP层、UDP层、路由层、应用层,完成整个消息的通信流程[16]。对消息的处理过程由traf_src进程模型完成,负责应用层相关事务。
2.2 基于TSP蚁群算法的路由协议测试验证
为了验证优化后路由协议的通信性能,本文将基于TSP蚁群算法的路由协议优化设计方法与传统的AODV及DSR路由协议进行了对比仿真。在仿真的20分钟内,节点的信息素逐步累积,不同的数据请求序列针对不同的信息素标识,完成数据传输后,对应此路径的信息素被清除,以节省系统容量。由于节点均为随机移动,各节点的平均信息素水平基本相同,体现了本协议优化方法的公平性。
为了更直观地体现通信性能的变化,本文通过传输延时和吞吐量对网络性能进行描述分析。
为了体现系统整体性能,本文统计平均传输延时珦D,假设成功发送N组数据,则计算如下:
式(10)中,D(i)表示第i个分组的传输延时。
网络的吞吐量TH是指在正常情况下系统在单位时间内所有节点正确接收的信息量,单位是bit/s或是M/s。吞吐量描述了网络可以完成通信任务的程度,是衡量自组织网络通信质量的重要指标。
ΔRp(i,m)是指数据分组i到数据分组m被目的节点接收时系统已传输的信息总量,ΔT(i,m)是数据分组i到数据分组m被接收时两者的时间差。若i>m,表示计算从第m个分组到第i个分组的吞吐量,若m=1,则结果是平均吞吐量。
图4的仿真结果表明,在传输延时方面,提出的优化路由协议较AODV协议、DSR协议分别减少了7.5%和9.8%;在吞吐量方面,提出的优化路由协议较AODV协议、DSR协议分别提高了8.4%和7.8%。信息素含量如图5所示,仿真过程中信息素含量基本维持在110单位左右,较稳定。这表明本文设计的基于TSP蚁群算法的无线通信路由协议较经典的协议效果有所改进。优化协议性能突出的原因是通过蚂蚁信息素对路径进行规划和最优化选择,使得劣质路径在选择的过程中被淘汰,但是需要指出的是,前期为了蚂蚁寻找路径而广播的信息也加大了系统负担,隐含在一部分吞吐量数据中,对仿真结果也产生了一定的影响。但总体而言,本文设计的ACAB路由协议效果较为突出。
3 结语
通过分析无线网络传输的基本原理及蚁群算法的运算过程,本文提出了基于TSP蚁群算法的无线通信路由协议优化设计方法。此优化设计将TSP基本蚁群算法的基本原理和通信路由选择相结合,通过建立系统模型,依靠蚂蚁信息素含量及距离竞争机制为通信节点选择最优的通信路径。同时,本文在OPNET Modeler通信仿真软件中建立仿真场景并完成模型构建,对基于TSP蚁群算法的无线通信路由协议进行测试验证,并与其它典型无线路由协议进行对比分析。仿真结果表明,在传输延时方面,提出的优化路由协议较AODV协议、DSR协议分别减少了7.5%和9.8%;在吞吐量方面,提出的优化路由协议较AODV协议、DSR协议分别提高了8.4%和7.8%。总之,本文设计的基于TSP蚁群算法的无线通信路由协议优化设计方法效果突出。
蚁群路由算法 篇5
现代多媒体通信对网络的带宽、延时、延时抖动、丢包率等参数提出了严格要求。而网络服务质量路由 (Qo SR) 算法的目的是在网络中搜索最佳路由, 该路由须满足带宽、延时、丢包率等条件。由于包含两个或两个以上不相关可加或可乘性参数的路由选择是一个NPC问题[1], 传统路由算法无法在有效时间内找到最优解, 因而启发式搜索算法已成为解决多约束Qo S路由问题的有效途径[2,3,4]。
蚁群算法 (ant colony optimization, ACO) 是通过蚂蚁个体在候选解的空间中独立地搜索解, 并在搜寻的解上留下一定量的信息素;蚂蚁间以信息素为媒介进行间接、异步的信息传递。随着算法的推进, 较优解路径上的信息素浓度会不断增加, 同时其他路径上信息素浓度随着时间逐渐变弱;当算法趋于收敛时, 在最优解路径上的信息素浓度最大。整个蚁群算法的最优解路径在蚂蚁个体的共同协作下求得。近年来一些学者对该算法提出了若干优化方案[5,6,7,8], 在不同的应用领域进行了有益探索。
1、蚁群算法中蚁王概念的引入
蚁群算法在构造解的过程中因为采用随机选择策略使得算法的进化速度变慢, 而正反馈原理旨在强化性能较好的解, 因此失去了随机性, 大量蚂蚁会选择同一条路径使搜索到的路径失去了多样性, 此时算法容易出现停滞现象并陷入局部最优解。
为了对传统蚁群算法进行改进, 我们在蚁群中引入了“蚁王”概念, 假设蚁王能够保存搜索到的所有候选解, 并对路径进行比较排序, 进而迅速发现全局最优解。其目的是对群体搜索过程有整体观念, 进而加以宏观指导, 以提高全局搜索的工作效率。
1.1 新算法思想
引入蚁王的蚁群算法要实现的目标是假设不同的蚂蚁从相同起点出发, 分别经过若干条不同路径最后到达终点, 尽量让蚂蚁在初始阶段选择较多的不同路径, 以获得最终的多样化解。每一只蚂蚁完成了自己的行程后就将信息素传递给蚁王 (全局信息) 。每次迭代完成后, 蚁王将收集到的路径按从小到大的顺序排列, 并将较大路径舍弃, 保存较小路径, 以供蚁群在下一次的寻优时加以利用。每次迭代完成后, 对前一轮全局最优解进一步优化, 动态更新路径信息。如此反复比较找到最短路径, 然后使用信息素全局更新规则对蚂蚁所选各路径上的信息素进行更新。即蚂蚁完成一个循环后更新所有路径上的信息素, 只有那些属于最短路径的边信息素才被得到增强, 最终形成一个新的最短路径。
蚁群算法的任务就是引导问题的解向着全局最优的方向不断进化。蚁王的引进能够对最优解进行快速增强, 同时对最差解进行削弱, 使得属于最优路径的边与属于最差路径的边之间的信息量差异进一步增大, 逼使蚂蚁的搜索行为更集中于最优解附近。
假设蚁王能够保存搜索到的最优值。蚂蚁将在接下来的路径选择中, 根据蚁王的指导决定路径的选择, 从而缓解蚁群算法的停滞现象及局部最优问题。算法流程见图1。
2、改进的蚁群算法
2.1 蚁群的路径选择规则
蚁王可以存储到当前为止前g个较优解。改进的蚁群算法将设置一个精英解信息素矩阵。设蚁群中有m (t) 个蚂蚁按照精英信息素矩阵选择转移节点, n (t) 个蚂蚁按照基本蚁群算法中边上的信息素进行选择转移节点, w (t) 个蚂蚁将随机选取蚁群存储的g个较优解中的一个解, 进行变异操作。
2.2 信息素的奖励促进机制
蚂蚁每完成一次搜索会找到一条最优路径, 蚁王将最优路径与之前搜索到的全局最优路径作比较, 如果新搜索到的全局最优解最优, 则以其取代前的全局最优路径。
本文采用最大最小蚂蚁系统将路径上的信息素设置在一定的范围内。蚂蚁每完成一次迭代循环搜索之后, 就将路径存储到蚁王中, 蚁王将此次搜索到的路径值与之前搜索到的存储路径值作比较, 如果新搜索到的路径解优于之前搜索到的最优解, 则以这条代替以前的全局最优路径。蚂蚁在进行循环状态转移时, 为了使其它蚂蚁在寻路的时候更好的选择此路径, 需要将这条路径上的信息素浓度增大, 以进一步增强了蚁王搜索过程的指导性, 使得蚂蚁的搜索更集中于当前所找出的全局最优路径上来, 加快收敛速度。
设当所有蚂蚁进行搜索巡游后, 只对当前搜索到的前e (t) 个较优解路径进行精英信息素矩阵对应边上进行更新。当所有蚂蚁完成一次搜索后, 进行信息素的更新。信息素的更新采用较优路径更新策略。较优路径包括两部分: (1) 当前迭代最优解的路径; (2) 蚂蚁在当前迭代搜索到解的路径比自己最优解更优的路径。路径 (1) 信息素的更新能够使局部最优路径信息素保留住, 使以后蚂蚁的搜索方向集中于较优方向
该算法关键在于蚁王对蚂蚁的调配。当一次迭代搜索完成后, 判断当前迭代得到的迭代最优解与全局最优解之间的关系。若迭代最优解优于全局最优解, 则加大e (t) 的数量, 即加大精英信息素矩阵中优质解路径更新的数量, 那么精英信息素矩阵中信息素的分布表示当前较优质解的分布。同时加大m (t) 的数量, 表示下一次搜索将加大在精英信息素矩阵进行搜索蚂蚁的数量, 有利于蚂蚁能够在此表示较优解的矩阵发现更好的解。
若迭代最优解优于全局最优解, 即全局最优解不变时, 则减少e (t) , m (t) , w (t) 的数量, 防止劣质解对算法搜索造成的干扰。
蚁群中有一部分蚂蚁按照路径上的信息素进行搜索, 并且该路径上的信息素量置于一定的范围之内, 防止由于在精英信息素蚂蚁进行搜索而造成的停滞现象。
3、应用于网络单播路由的仿真实验结果
本文仿真实验环境采用matlab7.8, 应用Salam拓扑算法随机生成网络拓扑图2所示。
其中网络各边参数如表1所示。分别采用传统蚁群算法ACO和本文改进的蚁群算法IACO对以上网络单播过程求最佳路由, 每个路由请求实验共进行100次, 所得结果总结在表2中。
4、总结
本文在基本蚁群算法的基础上, 提出了一种新的改进思路———引进蚁王概念的蚁群算法, 借鉴自然蚂蚁无法感知距离之行为, 让“蚁王”对蚁群路径的选择策略和过程加以指导和改善。在蚁群中引入蚁王概念, 可使群体搜索过程更加协调有序, 从而提高全局搜索效率。应用于网络单播路由优化的实验结果表明, 引入蚁王概念的蚁群算法能够获得比基本蚁群算法更加优越的性能。
摘要：本文在传统蚁群算法中引入了“蚁王”概念, 使之能对路径寻优过程进行存储、调整和指导, 从而使群体搜索过程更加协调有序。相关仿真实验证明, 这种改进的蚁群算法在解决网络单播路由优化问题时, 能够获得比传统蚁群算法明显优越的收敛性能。
关键词：蚁群算法,QoS,网络路由优化,蚁王
参考文献
[1]DORIGO M, MANIEZZO V, COLORNI A.Ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Systems, Man, and Cybernetics:Part B, 1996, 26 (1) :29-41.
[2]Wang Z, Crowcroft J.Quality-of-Service for Routing Supporting Multimedia Applications[J].IEEE Journal of Selected Areas in Communications, 1996;14 (7) :1228-1234.
[3]刘洋, 王文国.差异化密集蚁群算法与网络Qo S路由选择[J].通信技术, 2015, 48 (8) :949-953
[4]杨原.基于群智能优化算法的Qo S组播路由算法研究[D].西安:西安科技大学, 2014.
[5]陈峻, 沈洁, 秦玲, 陈宏建.基于分布均匀度的自适应蚁群算法[J].软件学报, 2003, 14 (8) :1379-1387.
[6]邓可, 林杰, 张鹏.基于信息熵的异类多种群蚁群算法[J].计算机工程与应用, 2008, 44 (36) :16-19.
[7]张鹏, 林杰, 邓可.一种基于路径相似度的蚁群算法[J].计算机工程与应用, 2007, 43 (32) :28-33.
蚁群路由算法 篇6
随着Internet和多媒体技术的发展, 网络多媒体业务迅速增长, 对网络服务质量 (QoS) 提出了更高的要求, 如何充分利用网络资源来满足日益多样化的QoS要求已成为人们关注和研究的热点。QoS网络路由的目的就是在分布的网络中寻找一条最佳路径, 从源节点出发, 历经所有目的节点, 同时满足所有QoS约束以保证网络服务质量, 并且费用最小。目前, QoS路由的研究主要分为:单播路由 (Unicast Routing) 、组播路由 (Multicast Routing) 和选播路由 (Anycast Routing) 。文献[1]已经证明具有两个及以上约束条件的QoS路由问题是一个NP-完全问题。近几年来, 国内外许多研究人员相继提出了许多QoS路由算法, 如蚁群算法[2,3,4,5,6]、遗传算法[7,8,9,10]和模拟退火算法[11]等, 并取得了一定的成果。
蚁群算法是文献[12]提出的一种优化方法, 它以蚂蚁觅食行为为基础, 用蚂蚁的行走路线表示待求解问题的可行解, 不依赖于具体问题的数学描述, 具有很强的全局优化能力, 已广泛应用于组合优化中的NP-完全问题。但蚁群算法本身也存在一些缺点, 如收敛速度慢、易陷入局部最优。许多学者提出了一些改进策略, 并应用于QoS路由优化上, 取得了一定的成果[2,3,4,5,6]。本文针对基本蚁群算法的缺陷, 给出了一种改进的可选节点集优化的变异蚁群算法对QoS单播路由问题进行求解, 采用混合蚂蚁行为, 根据QoS约束条件以及当前的最优路径对可选节点集进行优化, 引入二次变异策略, 借助节点使用计数器, 进行二次蚁群搜索机制, 提高了收敛速度, 减少了陷入局部极值的可能性, 增强了寻优能力。
1 QoS单播路由问题模型
本文只讨论包含带宽、延时和费用三个QoS约束条件的网络模型, 如图1所示。
用一个无向赋权图G<V, E>表示网络, 其中V={V1, V2, …, VN}表示网络节点集, N表示网络节点数, E={e1, e2, …, eM}表示双向链路集, M表示网络链路数, 每条链路ei∈E上包含三个属性, 用三元组表示 (bandwidth, delay, cost) , 分别表示链路的带宽、延时和费用。对于任一链路ei∈E, 定义三种度量, 延时函数delay (e) :E→R+, 费用函数cost (e) :E→R+, 带宽函数bandwidth (e) :E→R+。对于给定的源节点s∈V, 目的节点t∈{V-{s}}, s和t组成的路径p (s, t) 存在下列关系:
(1)
(2)
(3) bandwidth (p (s, t) ) =min{bandwidth (e) , e∈p (s, t) }
QoS单播路由就是要寻找一条从源节点s到目的节点t∈{V-{s}}的一条路径p (s, t) , 满足:
(1) 延时约束 delay (p (s, t) ) ≤D
(2) 带宽约束 bandwidth (p (s, t) ) ≥B
(3) 费用约束 在所有满足 (1) 和 (2) 条件的路径中, cost (p (s, t) ) 最小。
其中, D和B分别是路径p (s, t) 规定的延时和带宽约束值, 即QoS约束条件。
2 基本蚁群算法
蚁群算法的基本思想是:蚂蚁在觅食过程中会在路径上释放出信息素, 后面蚂蚁根据遗留的信息素选择下步走要走的路径, 路径上的信息素值越高, 蚂蚁选择这条路径的概率越大, 从而构成一个正反馈过程[12]。
(1) 蚂蚁状态转移规则
在t时刻蚂蚁由当前节点i选择下一节点j的规则是:
其中sk表示蚂蚁k所选择的下一节点;τij (t) 表示t时刻链路 (i, j) 上的信息素强度;参数α表示信息素的重要程度;参数β表示启发信息的重要程度;allowedk表示t时刻蚂蚁可以选择的节点集;ηij (t) 表示启发函数;q为[0, 1]上的随机数;q0为参数 (0≤q0≤1) ;S是根据式 (2) 计算出的下一选择节点。
(2) 信息素局部更新规则
对于第k只蚂蚁, 如果节点r和s是其所选择路径上的两个相邻节点, 信息素τ (r, s) 按下式进行更新:
τ (r, s) = (1-a0) τ (r, s) +Δτ (3)
式中:
其中:0<a0<1, Q0为常数, Lk为蚂蚁k本一次循环中所走过的长度。
(3) 信息素全局更新规则
在每次循环结束后, 仅对全局最优的路径上的信息素进行更新。如果节点r和s是两个相邻节点, 信息素τ (r, s) 按下式进行更新:
τ (r, s) = (1-ρ) τ (r, s) +ρΔτ (r, s) (4)
式中,
其中0<ρ<1;Q为常数;表示节点之间信息素强度;Lbest表示所有蚂蚁在一次循环中的全局最优路径。
3 可选节点集优化的变异蚁群算法
针对基本蚁群算法在求解QoS单播路由问题时容易陷入局部最优和收敛速度慢的缺点, 本文提出了可选节点集优化的变异蚁群算法, 其改进策略如下:
(1) 使用节点计数器策略 增加一个节点使用计数器NodeSum (1, N) , 计数器中每个节点的使用次数初始化值都为0, 即NodeSum (1, j) =0, ∀j∈N, 蚂蚁爬行时每经过一个节点j一次, 该节点的计数值就增加1, 即:
NodeSum (1, j) =NodeSum (1, j) +1
(2) 可选节点集优化策略 在蚂蚁由当前节点选择下一节点前, 先对下一初始可选节点集进行判断和筛选, 把那些不符合QoS约束条件以及比当前最优路径差的初始可选节点从可选节点集中删除, 得到优化后可选节点集。这样做的目的是避免太多无效搜索, 使当前最优路径对后面蚂蚁产生除信息素更新外的又一个搜索方向指示信息, 使得后面搜索方向更明确, 以提高搜索效率。
例如, 有1个蚂蚁爬行到当前路径为Path, 当前搜索到的最优路径为Pathbest, 由当前节点选择下一节点的初始节点集为allowed= (V1, V2, V3, V4) , 根据上面的策略, 如果Path+Vi (i=1, 2, 3, 4) 不符合QoS约束条件或者目标函数Path+Vi劣于Pathbest, 则将Vi删除, 假如 (V1, V2) 不符合, 则由当前节点选择下一节点的可选节点集就变为allowed= (V3, V4) 。
(3) 变异前蚂蚁爬行策略 为了使变异前的蚂蚁爬行路径多样化, 受混合行为的蚁群算法[13]的启发, 定义了8种不同行为蚂蚁爬行策略, 保持了初始路径的多样化, 有利于后面的变异能在较宽的领域进行搜索。这8种蚂蚁行为分别定义为:
行为1 蚂蚁以随机方式选择下一节点;
行为2 蚂蚁以目标启发函数贪心方式选择下一节点;
行为3 蚂蚁以目标启发函数轮盘选择方式选择下一节点;
行为4 蚂蚁以信息素与目标启发函数结合的函数贪心方式选择下一节点;
行为5 蚂蚁以信息素与目标启发函数结合的函数轮盘选择方式选择下一节点;
行为6 蚂蚁以信息素贪心方式选择下一节点;
行为7 蚂蚁以信息素轮盘选择方式选择下一节点;
行为8 利用前面定义的节点使用计数器, 蚂蚁以爬行节点次数最少的方式选择下一节点。
(4) 变异时蚂蚁爬行策略 在t时刻蚂蚁由当前节点i选择下一节点s时, 并且不仅仅根据上式 (2) 来决定, 同时把上面所定义的节点使用计数器考虑进去, 在一定的概率下, 让蚂蚁选择节点计数值最小的节点, 即蚂蚁走过次数最小的节点, 使未被访问的节点有被访问的可能性。这样, 即保证蚂蚁往比较优的路径上爬行, 也在一定程度上有利于跳出局部极值。具体选择按下式进行:
其中, q1为参数 (0<q1<1) , 其余定义与式 (1) 和 (2) 相同。本文仿真中,
(5) 第一次变异 在设定的M只蚂蚁执行完一次搜索后, 对当前搜索到的符合QoS约束条件的从源点到目的节点的路径进行变异和二次蚁群算法搜索。具体策略如下:假设某条合格路径为Path= (1, 17, 3, 12, 20) , 该路径长度为length (Path) =5, 则其变异长度定义为L=round (length (Path) /3) , 即变异长度为接近总长度的1/3的整数, 这样使得变异前和变异后的路径差异不太大, 而且使得变异后的路径是在变异前的路径的基础上发生局部变化而进化得来的, 符合进化算法的思想。在本例中L (Path) =2, 即变异长度为2。Mutated为变异的次数, 固定为一常数, 每次根据变异长度L (Path) 随机产生两个变异点R1和R2, R2=R1+L, 然后按照上述蚂蚁爬行规则, 执行二次蚁群算法搜索R1和R2之间的路径。如果变异后搜索到的路径优于当前的最优路径, 则将变异后的路径替换当前的最优路径, 例如, 变异后的路径变为Pathmutated= (1, 17, 12, 20) , 然后比较Pathbest和Pathmutated, 若后者优于前者, 则用后者替换前者;如果变异后搜索到的路径优于变异前的路径, 则将变异后的路径替换变异前的路径;然后进行下一次变异, 如此重复, 直到执行完Mutated次变异。
(6) 第二次变异 在第一次变异执行完后, 对当前搜索到的最优路径按照第一次变异时的策略进行变异。
经过二次变异和二次蚁群搜索, 能够很大程度上跳出局部最优, 快速地向全局最优进化。
(7) 信息素局部更新 这里仅对符合约束条件的路径的链路的信息素进行局部更新, 对于那些死亡或者不符合约束条件的链路, 虽然蚂蚁也走过, 但不进行信息素局部更新。
(8) 如果在设定的k次迭代内找到的最优路径没有发生过改变, 则对所有的链路信息素进行重新设置, 具体为:
τ
式中τ
上述的改进策略即保证了在下一周期搜索时倾向于部分较优解附近, 提高算法的收敛速度, 又保证了使蚂蚁倾向于未搜索过的链路, 减少算法陷入局部极值的可能性, 增强了算法的全局寻优能力。
另外, 根据最大—最小蚂蚁系统[14]策略, 将每条链路信息素限制在[τmin, τmax]区间内, 具体策略如下:
利用本文算法求解QoS单播路由的详细步骤如下:
Step1 设置请求单播路由源节点Vs, 目的节点Vd, 带宽约束B, 延时约束D, 删除不满足QoS约束的链路, 得到新的网络拓扑图。
Step2 设置蚂蚁种群数量m, 最大迭代次数DiedaiNum, 设定的迭代次数shedingDiedai, 变异次数Mutated, 初始化各链路信息素强度τ, 节点使用计数器NodeSum, 参数α, β, q0, q1, a0, Q0, ρ, Q, 迭代次数l=0, 最优路径记录Pathbest。
Step3 迭代次数l=l+1, 在源点创建m只蚂蚁分组, 初始化禁忌表, 并将源点加入禁忌表, t=0, 节点使用计算器:
NodeSum (1, Vs) =NodeSum (1, Vs) +m
Step4t=t+1, i=1;对每只蚂蚁分组k, 由当前节点Vi选择下一节点Vj前, 先根据QoS约束条件和当前最优路径对可选节点集进行优化, 把不符合要求的可选节点从可选节点集中删除, 得到新的可选节点集。
Step5 变异前节点选择按上述改进策略 (3) 的方式进行, 变异时节点选择按上述改进策略 (4) 的方式进行, 由当前节点Vi选择下一节点Vj, 然后, 根据下面三种情况再进行判断 :
(1) 如果Vj∈ϕ, 且Vi≠Vd, 则蚂蚁死亡;
(2) 如果Vj∉ϕ, 且Vi≠Vd, 则继续搜索, 下一搜索Vi≡Vj;
(3) 如果Vi≡Vd, 则蚂蚁完成搜索。
然后, 把节点Vj加入禁忌表, 更新节点使用计数器:
NodeSum (1, Vj) =NodeSum (1, Vj) +1
Step6 重复执行Step 4直到蚂蚁死亡或者蚂蚁完成搜索。
Step7 记录完成从Vs到Vd搜索的路径p (Vs, Vd) 。
Step8 计算路径p (Vs, Vd) 的目标函数值, 对p (Vs, Vd) 的链路按式 (3) 进行信息素局部更新, 更新后按式 (7) 进行判断, 并与当前的最优路径进行比较, 如果优于当前的最优路径, 则更新当前的最优路径Pathbest=p (Vs, Vd) 。
Step9 对m只蚂蚁爬行找到的符合约束条件的路径p (Vs, Vd) 进行第一次变异和二次蚁群搜索, 变异次数为MutatedNum。具体方法, 如上改进策略 (5) 所述, 如果变异后的路径优于当前的最优路径, 则更新当前的最优路径。
Step10 对进行第一次变异后的当前最优路径进行第二次变异和二次蚁群搜索, 变异次数为MutatedNum。具体方法, 如上改进策略 (6) 所述, 如果变异后的路径优于当前的最优路径, 则更新当前的最优路径。
Step11 根据式 (4) 对执行二次变异后的当代最优路径Pathbest的链路进行全局信息素更新, 更新后按式 (7) 进行判断。
Step12 判断在设定的shedingDiedai次迭代内最优路径有无变化, 如果没有变化, 则根据式 (6) 对更新后的链路信息素进行重新设置。
Step13 转Step3, 进入迭代循环。
Step14DiedaiNum次迭代结束后, 输出当前的最优路径Pathbest, 算法结束。
4 仿真实验
本文算法用图1所示的网络模型进行仿真, 只考虑链路的带宽、延时和费用约束, 链路属性用三元组表示 (带宽, 延时, 费用) 。
有1个QoS单播路由请求, 源节点为“1”, 目的节点为“20”, 约束条件值分别为B=8, D=12。
本文算法和基本蚁群算法参数设置为:VS=1, Vd=20, M=8, DiedaiNum=20, shedingDiedai=3, Mutated=5, τ0=1, NodeSum0=0, α=1, β=1, q0=0.4, q1=0.7, a0=0.1, Q0=3, ρ=0.3, Q=10。仿真结果如表1和图2所示。
由仿真示例可见, 本文算法在10次迭代内就能收敛到全局最优解 (1, 17, 12, 20) , 收敛速度快;而基本蚁群算法在20次迭代内只收敛到局部最优解 (1, 17, 3, 16, 20) , 收敛速度慢, 陷入局部最优。仿真结果验证了本文算法是可行和有效的, 并且能够跳出局部最优, 快速收敛到全局最优解。
5 结束语
针对QoS单播路由问题, 本文提出了一种改进的可选节点集优化的变异蚁群算法。该算法采取混合蚂蚁行为, 优化可选节点集, 通过二次变异, 借助节点使用计数器, 引入二次蚁群搜索机制, 减少了算法陷入局部极值的可能性, 提高了算法的寻优能力和收敛速度。实验结果证明了上述结论。
蚁群路由算法 篇7
随着高速网络技术的发展, 与多媒体相关的实时业务应用大量兴起[1], 而有效的组播路由[2]是实现多媒体通信的关键技术。传统的组播通信大多采用“尽力而为”, 没有很好地考虑服务质量QoS (Quality of Service) [3]。随着网络的发展, 多媒体通信对网络的服务质量QoS提出了越来越高的要求, QoS组播路由问题应运而生。QoS组播路由问题是指在分布的网络中寻找最优路径[4], 要求从源节点出发, 历经所有的目的节点, 找到一条满足网络路由中延时、带宽、丢包率等约束条件且花费最小的网络路径。Wang Z 等学者已经证明了包含两个及以上约束条件的QoS网络路由是一个NP完全问题[5]。
蚁群算法 (Ant Colony Algorithm, ACA) 是上世纪90年代意大利学者 M.Dorigo和V.Maniezzo等人通过模拟自然界蚂蚁寻径的行为提出的一种全新启发式算法, 它被广泛用于解决各种NP完全问题[6]。现利用一种基于自适应蚁群优化算法, 提出考虑网络链路利用率的QoS多约束条件下组播路由解决方法。
1 基本蚁群算法
蚁群算法是一种新近发展起来的、模拟蚂蚁群体觅食行为的仿生优化算法。蚂蚁在寻找食物的运动过程中, 能在其经过的路径上分泌一定数量具有气味的称为信息素的物质进行信息传递, 并指导自己的运动方向。某一路径上走过的蚂蚁越多, 此路径上蚂蚁留下的信息素轨迹也越多, 则后来蚂蚁选择该路径的概率也越大, 从而更增加了该路径被选择的可能性。同时, 路径上的信息素也会随着时间的流逝而不断地挥发, 这种机制所得蚂蚁不完全受过去经验的约束, 有利于蚂蚁向新的路径搜索。随着时间的推移, 蚂蚁就会找到由蚁巢到食物源的最优路径。该算法采用了正反馈并行自催化机制, 具有较强的鲁棒性、优良的分布式计算机制、易于与其他方面结合等优点。
蚁群算法利用随机策略, 使得进化速度较慢, 收敛速度不理想;利用正反馈强化性能较好的解, 但导致当前不被选用的路径, 往后被选用的概率越来越小, 使算法在某些局部最优解附近徘徊, 出现停滞现象, 而且挥发系数ρ的存在会使那些从未搜索到的路径上的信息素量逐渐减少到0, 从而降低算法的全局搜索能力。若ρ过大, 会使以前搜索过的路径被再次选择的可能性过大, 影响算法的全局搜索能力, 易于陷入局部最优解;若ρ过小, 虽然可以提高算法的全局搜索能力, 但会使算法的收敛速度降低。1996年Gambardella和Dorigo提出了一种修正的蚁群算法 (ACS) [7], 该算法对信息素的更新策略作了相应的改进, 即使用:
(1) 局部信息更新, 蚂蚁从城市i转移到城市j后, 路径上的信息素按式 (1) 进行更新:
undefined
式中:ξ∈ (0, 1) , τo为常数。
采用局部信息更新策略减小了已选择过的路径再次被选择的概率, 提高了算法的全局搜索能力。
(2) 全局信息更新, 针对全局最优解所属边按式 (2) 进行信息素更新:
τij (t+n) = (1-ρ) τij (t) +ρΔτundefined (t) , ρ∈ (0, 1) (2)
式中:Δτundefined (t) =1/Lgb;Lgb为当前全局最优解的路径长度。采用全局信息更新策略, 增强了全局最优解路径上的信息素, 加强了算法的正反馈作用, 从而加快算法的收敛速度。
2 QoS网络路由模型
2.1 QoS组播路由问题的基本概念和网络模型定义
就组播路由而言, 网络通常表示成一个带权图G= (V, E) , 其中V代表节点集合;E代表网络中双向链路集合, 关联每条链路的参数就是该链路的QoS度量。在此, E表示网络中双向链路的集合[8];S为源节点, S∈V;M∈{V-{S}}为目的节点集, S, M组成组播树T (s, M) 。对于任一链路e∈E, 可定义某些属性:延时函数:delay (e) :E∈R+;费用函数cost (e) :E∈R+;带宽函数bandwidth (e) :E∈R+。对于任一网络节点n∈V, 定义某些属性:延迟函数delay (n) :V∈R+;费用函数cost (n) :V∈R+, 由此存在如下关系:
undefined
式中:pT (s, t) 为组播树T (s, M) 上源点s到终点t的路径。
QoS组播路由问题是要寻找一颗组播树T (s, M) 满足:
延时约束:
undefined
带宽约束:
undefined
式中:B表示带宽约束;Dt表示延时约束。
费用函数 (目标函数) 可描述为在所有满足条件的组播树中, cost (T (s, M) ) 最小。
2.2 网络负载和链路利用率
为考虑链路利用率的情况, 将链路代价定义为[9]:
undefined
E中的每条边对应网络中的一条链路ei, j, 其中i表示上游路由器;j表示下游路由器。ei, j具有三个属性:Maximum Bandwidth (MB) , Reserved Bandwidth (RB) , Unreserved Bandwidth (UB) 。因此有对任意e∈E, ∃MB (i, j) , RB (i, j) 和UB (i, j) , 并且MB (i, j) =RB (i, j) +UB (i, j) 。在式 (8) 的基础上, 定义式 (9) , 用来计算图G中每条链路的代价。
undefined
由式 (9) 可知, 剩余带宽越大, 链路代价越小;反之, 链路代价越大。
3 自适应蚁群算法的QoS组播问题实现
3.1 适应度函数
适应度函数是蚁群进行路径选择的依据, 也就是蚂蚁从初始路径集Ωi中选择第j条路径的概率:
undefined
式中: phepj (s, Di) 是路径pj (s, Di) 上的分泌物强度, 它表明某条路径上的分泌物强度越大, 该路径被选中的概率也就越大。初始状态时各条路径上的分泌物强度相同。
3.2 蚂蚁的信息素调整
蚂蚁寻找路径时, 按以下规则进行信息素调整:
(1) 对蚂蚁所经过的路径进行分泌物强度调整。其中a是常量参数;cost (e) 为该路径的代价;phepi (s, Di) 为源节点S到目的节点Di的路径上的分泌物强度。调整后, 有:
undefined
上述公式与文献[10]不同, 信息素的调整不是固定值, 而是根据所选择路径的代价来调整的, 并且路径代价受带宽影响, 是根据链路利用率来确定的。增加信息调整的自适应性, 同时也加快了收敛速度。
(2) 当蚂蚁都走完一条路径时, 对所有路径进行分泌物挥发调整。其中ρ是挥发度;Δ为各条路径上的初始信息强度。
undefined
(3) 当蚂蚁都找到所有目的节点, 组成一颗组播树时, 再按式 (13) 进行信息素调整, 即:
undefined
式中:B为常量参数;cost (T) 为该组播树的代价;pi (s, Di) 是被选路径。
3.3 算法步骤
Step 1:生成初始路径集。找出从源节点S到每个目的节点Di∈D (i=1, 2, …, m) 满足延时约束的有效路径, 并组成初始路径集Ωi。
Step 2:初始化α, β, B, ANTn和初始集中各条路径上的信息强度Δ。
Step 3:从源节点发出ANTn只蚂蚁, 按式 (10) 计算路径集Ωi中每条路径的适应度, 每只蚂蚁再按赌轮旋转规则从中选择一条路径, 再按式 (11) 进行分泌物强度调整。
Step 4:当每只蚂蚁都完成一条路径选择后, 按式 (12) 进行分泌物挥发性调整。
Step 5:重复执行Step 3和Step 4, 直到蚂蚁找到所有目的节点的路径, 每只蚂蚁寻找到的路径各组成一颗组播树。计算各组播树的代价 (相同链路的代价只计算一次) , 判断是否大多数蚂蚁收敛于同一组播树, 如果是, 则该组播树为最优路径, 退出程序;否则, 用代价最小的组播树替代代价最大的组播树, 转执行Step 6。
Step 6:蚂蚁按原路返回, 并按式 (13) 调整返回路径上的分泌物强度, 再转Step 3执行。
4 实验仿真和算法分析
本文采用改进的Waxman网络拓扑仿真模型[11], 利用Matlab 7.0进行仿真, 其特点是每对节点之间按概率p (u, v) =βexp (-d (u, v) /2an) 相连, 其中d (u, v) 为u, v两节点之间的距离, 并且按照Salama和Reeves在Waxman基础上的网络生成算法使平均节点度达到指定值。参数α, β分别控制网络中长边和短边的比例以及边的密度, n为网络节点个数。参数的选取如表1所示。表2列出了30个节点的网络仿真试验中, 两种不同算法在不同延时约束条件下的组播树代价。每次试验分别进行20次, 其中代价值分别是20次试验得到的平均值。从表2容易看出, 算法IAAC比算法AAC在相同延时条件下生成组播树的代价要小。图1描述了两种算法在30个网络节点的网络仿真中, 组播树的代价随迭代次数的变化情况。从图中可以看出, IAAC算法在收敛速度上要优于AAC算法, 并且在最优组播树的代价上也要优于AAC算法。图2显示了两种算法在随着网络节点数变化时, 组播树代价的变化情况。随着网络节点数的增加, IAAC算法所得最优组播树的代价低于AAC算法所得最优组播树的代价, 并且最优组播树的代价增加比AAC算法得到最优组播树代价的增加速度要慢。通过仿真试验, 本文改进的自适应蚁群算法能以更快的收敛速度得到最优组播树, 并且最优组播树的代价相对原有自适应蚁群算法要更优。
5 结 语
本文提出了一种应用自适应蚁群算法并结合实际网络的链路利用率的多约束QoS组播路由算法。将链路利用和网络负载考虑到组播路由中, 使得网络路由问题的研究更符合实际网络的需求。在运用自适应蚁群时, 结合信息素更新的特点, 将链路代价考虑到其中, 使得信息调整的自适应性加强, 同时收敛速度得到改善。
摘要：结合多约束QoS组播路由的特点, 应用一种自适应蚁群优化算法解决组播路由问题。考虑到实际通信中链路利用率对网络的影响, 将网络中链路的带宽转化为链路的代价问题, 并在蚁群算法中根据蚂蚁所选路径的代价进行信息素更新, 增加了信息素调整的自适应性, 同时加快了算法的收敛速度, 使得组播路由算法在考虑网络QoS约束的基础上进一步贴合实际网络的需求。
关键词：QoS,蚁群算法,自适应,链路利用率
参考文献
[1]Chockler G V, et al.Group Communication Specifications:AComprehensive Study[J].ACM Computing Surveys, 2001, 33 (4) :1-43.
[2]Wang B, Hou C J.A Survey on Multicast Routing and ItsQoS Extensions:Problems, Algorithms and Protocols[J].IEEE Network Magazine, 2000, 14 (1) :22-36.
[3]Xiao X P, Ni L M.Internet QoS:the Big Picture[J].IEEENetwork Magazine, 1999, 13 (2) :1-13.
[4]邹德莉, 郝应光.基于非精确状态信息的QoS组播路由算法[J].微电子学与计算机, 2006, 23 (9) :66-72.
[5]Wang Zheng, Crowcroft J.Quality of Service Routing for-Supporting Multimedia Applications[J].IEEE Journal onSelected Areas in Communications, 1996, 14 (7) :1 228-1 234.
[6]Dorigo M, Maniezzo V, Colorni A.Ant System:Optimizationby a Colony Cooperating Agents[J].IEEE Trans.on Sys-tems, Man, and Cybernetics-bart B:Cybernetics, 1996, 26 (1) :29-41.
[7]李昌兵.基于计算智能的多播QoS路由技术研究[D].重庆:重庆大学, 2007.
[8]王应征, 石冰心.基于遗传算法的时延受限代价最小组播路由选择方法[J].通信学报, 2002, 23 (3) :112-117.
[9]Cisco.OSPF Design Guide[EB/OL].http://www.cisco.com/warp/public/104/1.html, 2004-02.
[10]李生红, 刘泽民.基于蚁群算法的组播路由调度方法[J].计算机工程, 2001, 27 (4) :63-65.
[11]Waxman B M.Routing of Multiple Connections[J].IEEEJournal on Selected Area in Communications, 1986, 6 (9) :1622-1 671.
蚁群路由算法 篇8
Ad Hoc网络[1]是一种特殊的无线移动网络构架技术,在进行网络通信时不需要依靠现有固定有线基础设施,能够迅速展开使用的无中心、自组织和自愈的通信网络体系。与传统有线网络和蜂窝网络相比,Ad Hoc网络无固定基础设施,网络中各个节点都可以随时进入或离开网络,并且彼此之间的地位是相互平等和相互协作,通过无线链路进行通信、交换信息,实现信息和服务的共享。由于网络拓扑结构的动态变化以及带宽和能源受限等特点,路由问题成为了Ad Hoc网络研究与应用的关键和难点,设计出高效的自适应的Ad Hoc网络路由协议成为了当前研究的热点问题。
近年来,大量的关于Ad Hoc网络的研究都是基于路由算法展开的,利用智能优化算法改进的路由算法协议在通信网络领域的应用已越来越受到研究者的关注。蚁群算法是由意大利学者Dorigo于1991年提出,并用该方法解决了一系列的组合优化问题。它是一种性能优良的启发式随机优化算法,具有自组织及自动学习的能力,能够形成可靠的并具有生存力的路由算法。本文结合Ad Hoc网络结构提出一种改进的蚁群算法作为自组织网的网络层路由协议,在网络拓扑结构复杂、动态变化较大的情况下,能有效地提高网络传输性能和通信效率。
1 蚁群算法
1.1 蚁群算法原理
蚁群算法[2]是一种新的仿生类进化算法,蚂蚁有能力在没有任何提示下找到从其巢穴到食物源的最短路径,并且能随环境的变化适应性地搜索新的路径。根本原因是蚂蚁在寻找食物源时,能在其走过的路上释放一种特殊的分泌物——信息素,随着时间的推移该物质会逐渐挥发,后来的蚂蚁选择该路径的概率与当时这条路径上该物质的强度成正比。当通过的蚂蚁越来越多时,其留下的信息素轨迹也越来越多,后来蚂蚁选择该路径的概率也越高,从而更增加了该路径的信息素强度,形成一种正反馈机制,最终可以发现并收敛到最短路径上。蚁群算法则是模拟了这样的优化机制,个体间的信息交流与相互协作最终找到最优解。通过最优路径上蚂蚁数量的增加→信息素强度增加→后来蚂蚁选择概率增大→最优路径上蚂蚁数量更大达到最终收敛于最优路径上。
1.2 用蚁群算法求解的数学模型
首先引入如下符号:m表示算法中蚂蚁的数量,dij(i,j=1,2,…,n)表示边(i,j)之间的距离,n为城市个数,τij(t)表示t时刻在(i,j)上残留的信息素量,初始时刻各边信息素量相等。蚂蚁k在t时刻由城市i转移到城市j的概率为:
式(1)中:ηij为先验知识或能见度,针对具体问题根据启发式规则而定,α为边(i,j)上残留信息的重要程度,β为启发信息的重要程度,tabuk为蚂蚁k的禁忌表即蚂蚁所走过的城市集。
随着时间的推移,以前蚂蚁留下的信息逐渐消逝,用参数ρ(ρ∈(0,1))表示信息素挥发率。当蚂蚁完成一次循环后,各路径上的信息量根据下式做调整:
式(2)中:τij(t)new表示更新后边(i,j)上的信息素量,τij(t)old表示更新前边(i,j)上的信息素量,△τkij表示第k只蚂蚁本次循环中留在边(i,j)上的信息素量,△τij表示本次循环中边(i,j)上信息量增量,Q为常数,Lk表示第k只蚂蚁在本次循环中所走过的路径长度。当所有蚂蚁都完成一次周游后,因每只蚂蚁本次周游的禁忌表已满,此时应及时清空,准备下一次周游,当周游次数达到设定值时算法结束。
蚁群算法有诸多改进算法,但启发式因子α、期望值启发式因子β、信息素挥发因子ρ、蚂蚁数量m和信息素量Q都是始终影响算法性能的重要参数。其中的α大小反映了信息素因素的作用强度,β反映了先验性、确定性因素的作用,ρ的大小直接关系到蚁群算法的全局搜索能力及其收敛速度。此外m和Q也是影响算法效率的重要参数。研究表明,参数的不同取值对算法性能影响较大,本文首先确定算法性能较佳的最佳组合参数的解决方案。
2 蚁群算法的参数最优化
考虑到蚁群算法的局限性,关于蚁群算法的参数最优化组合,本文利用遗传算法的优化组合能力来确定蚁群算法的最优参数组合。遗传算法是一种求解组合优化问题的自适应全局优化概率搜索算法,大量减少了为寻找最优参数组合而进行的盲目实验次数。将主要影响蚁群算法性能的5个参数作为遗传算法中的染色体进行编码,设计评价的函数即适应度函数,进行遗传算法的选择、交叉、变异算子计算,通过多次迭代找出最优的参数组合。
(1)染色体选择、编码及初始种群生成染色体中蚁群算法的参数α、β、ρ、Q、m,利用遗传算法确定蚁群算法的最优参数组合。由于实数编码的遗传算法具有精度高、搜索空间大的启发信息等优点,采用十进制实数编码,初始种群根据预设数量采用随机方式生成。
(2)适应度函数
适应度函数的选取要与解决的问题相结合,由目标函数决定。本文中适应度函数F()定义为评估参数,用目标函数的形式给出。在网路路由路径问题中,所求得结果为路径长度,其值越小越好,而遗传算法的适应度值是越大越好。因此,对于某个体将其解码得到巡回路线的总距离为T(i),个体的适应度值为F=1/T(i)。评价函数值越大,适应度就越高。
(3)选择算子
根据适应度函数选取进行交叉的个体,随机从种群中挑选预定数目的个体,然后从这些个体中选择具有最好适应度的个体做父个体,重复进行整过程直到完成所有的父个体选择,主要按照轮盘赌选择机制执行选择功能。
(4)交叉算子
采用均匀交叉方法,均匀交叉法运用较广义化,其中将每个点都作为潜在的交叉点,其破坏性可以促进对解空间的搜索,可以搜索到其他交叉方法无法搜索到的模式。其过程是先随机产生与父辈个体编码等长的二进制交叉模板串,然后按照此模板串对两个父个体基因串进行交叉,得到两个新的后代个体。
(5)变异算子
采用高斯变异方法,这种方法起源于进化策略。一般在进化策略中的个体包含两个元素(x,σ),其中第一个向量x表示搜索空间中的一个点,第二个向量σ表示标准差。后代(x',σ')产生为σ'=σeN(0△σ),x'=x+N(0,△σ'),其中N(0,△σ)是均值为0,标准差为σ的独立高斯随机数向量。
3 基于邻域分区的蚁群算法
动态邻域分区[3,4]蚁群算法的核心是解决复杂大规模问题时采用“分而治之”的思想。设有n个节点的优化问题,分别为N1,N2,…Nn,先选择一个距离阈值D,然后按以下步骤划分子区域:
(1)从中随机选取一节点N作为第一子区域的中心并令K1=Ni,计算下一节点Nj到K1的距离d1i。如果dji≤D,则Nj属于第一子区域节点;如果d1i>D,则Nj作为第二子区域中心K2。
(2)如有区域中心K1、K2对于未被处理的节点Nk,则分别计算Nk到K1、K2的距离d1k、d2k。若d1k、d2k都大于D,则Nk作为一个新的子区域中心,否则若d1k>d2k,则Nk属于第二子区域节点,若d1k
(3)如有区域中心K1、K2、…Km,对于未被处理的节点Nk,则分别计算Nk到K1、K2、…Km的距离d1k、d2k、…dmk。若d1k、d2k、…dmk都大于D,则Nk作为一个新的子区域中心,否则Nk属于与它距离最小的子区域的节点。
(4)续第(3)步,直到所有节点被处理完,得到M个子区域。
邻域分区方法把大规模节点分成若干个分区子集后,对这些分区利用网络互连群计算机或多处理器计算机进行并行计算,然后把每个子区域中心全局连接起来用蚁群算法进行计算。步骤如下:
4 基于改进分区蚁群算法的路由协议设计
通过将遗传算法作为优化工具,通过迭代找出最优的参数组合,然后将最优的参数组合返回蚁群算法中。将蚂蚁觅食的行为当作网络中的数据通信,蚁群算法中有一个蚂蚁决策表,它包括所有结点选择下一路径的转移概率和结点的本地信息,蚂蚁使用这个表来指导其搜索朝着搜索空间中最有吸引力的区域移动,这正是网络通信中路由表的形成过程。改进蚁群算法路由协议的设计[5,6,7]步骤如下:
(1)首先精简网络使之成为一个新的简单网路,基于此拓扑图进行搜索,从源节点开始,随机地选择一个与之相关联的节点,将两点相连,然后从选择的节点继续随机地选择与其关联的下一个节点,在连接时要判断是否有回路,如有回路则重新进行节点的选择。
(2)根据基本蚁群算法已有研究成果,确定各参数较优范围,得到各参数的经验值初始化参数值;设置遗传算法中初始参数包括迭代次数、染色体数、交叉概率和变异概率。
(3)将遗传算法抽象为一个函数F,参数α、β、ρ、Q,m抽象为函数的自变量,将参数组合种群初始化为染色体,根据设计的适应度函数进行选择、交叉、变异算子多次迭代。
(4)根据交叉概率,选择若干组解,然后分组进行交叉的解。若新的目标函数变好,接受新值,否则就拒绝;根据变异概率,判断是否变异,变异后的目标函数变好,接受新值,否则就拒绝;找出函数F(α,β,ρ,m,Q)最优的参数组合,然后返回蚁群算法中。
(5)将网络中节点数据,用横、纵坐标表示,用距离阈值的邻域分区法如上所述,得到每个子区域的节点数据。
(6)对网络中每个子区域节点用蚁群优化算法求当前最优的解,初始化网络拓扑中各边的信息素值τij(0),初始化循环次数和控制参数,设置最大循环次数。将m只蚂蚁放到源节点,重复应用公式(1)来选择各自路径,当该蚂蚁成功完成从源节点到目的节点的路由选择后,则对所选路由的各路径上的信息素根据信息更新规则公式(2)进行更新。
(7)对所有蚂蚁重复第(6)步,直到m只蚂蚁都完成。若循环次数大于设置最大循环次数,则循环结束,输出子区域求解结果;否则循环次数加1,跳转至上一步继续执行。
(8)最后将每个子区域中心连接输出问题的最优解。
为验证本文提出策略及算法的实用性,下节将结合实际例子对策略及算法进行仿真。
5 算法仿真
本文提出改进算法应用属于网络层控制,通过MAT-LAB仿真平台下的模拟实验,考察节点均匀分布在仿真区域矩形的空间中,遗传算法的染色体个数、交叉概率和变异概率分别为30、0.2、0.5,随机选取性能相对最佳的40、70、100、200、400个节点作为问题的求解;速度/方向5、10、15、20、25、30、35,40(m/s);停留时间15、30、60、120、240、480(s);仿真时间500(s);数据包发送率1Packet/s;路由协议是基本蚁群算法协议和改进蚁群算法路由协议;每隔1s发送一次数据报,数据源在0到180s之间随机选取一个数开始发送数据直到仿真结束。
图一是用10只蚂蚁对40个节点迭代100次进行优化求解路径示意图,最后得到的花费是1759.4569(m)。图二是40个节点分为2个子分区后所进行优化求解的示意图,各子分区中心坐标为K1(162,126),K2(183,124),第一子区23个节点,第二子区17个节点,得到的最佳解为1689.0497(m),两个中心点之间的连接路径为黑色虚线。
图三是用10只蚂蚁对100个节点迭代1000次进行优化求解路径示意图,最后得到的花费是2718.2468(m)。图四是对100个节点分为三个子分区后所进行优化求解的示意图,各子分区中心坐标为K1(139,118),K2(174,101),K3(163,124),第一子区23个节点,第二子区31个节点,第三子区46个节点,最后得到的最佳解为2525.3416(m),三个中心点之间的连接路径为黑色虚线。
6 结果分析
在实验中,蚁群算法程序所采用的参数是求解迭代次数100次,根据最优参数组合,我们把信息素的初值为100,α取2,β取1,ρ取0.7,蚂蚁数取为10只,区域阀值Q的值随机选取,但对区域优化路径的结果有一定影响。每一个实验先用蚁群算法对全部结点进行运算,并且做多次搜索实验选出最佳路径。然后再对这些结点进行分区,对每个分区求解最佳路径后,再进行全部结点整合求解出最佳路径。实验结果如表一所示:
图五中可以看出,不同停留时间下改进蚁群路由算法的传输延时比基本蚁群路由算法的要小,改进蚁群路由算法能够提供较为稳定的连接,并能保证提供最优的路径(跳数最少或延时最短)。随着停留时间的增加,两者的传输延时都呈现减小的趋势,而改进算法的趋势相对缓慢,在动态情况下,显然改进蚁群算法的路由协议相对基本算法具有更加优良的性能。
图六是在逐渐增加结点移动速度的情况下,基本算法和改进算法在端对端传输延时指标上的比较曲线,结点移动速度的增加意味着网络拓扑结构变化率加快,整个网络不稳定。从图六中可以看出,改进算法路由曲线比基本算法的平坦,说明它受结点移动速度的影响较小,两种路由都出现了传输延时的增加,但在相同速度下改进算法比基本算法的性能好。例如,在速度达到40m/s时,基本算法和改进算法的端对端传输延时分别为0.37s和0.16s,改进算法是基本算法的两倍多。
7 结束语
从实验结果来看,改进蚁群算法应用于无线Ad Hoc网络路由大规模寻优问题中,优化性能较基本算法有明显改善。由于蚁群算法的参数进行优化,在使用改进分区蚁群优化算法应用求解时,搜索最佳路径的时间有所缩短,搜索程序的运算复杂度有所降低,提高了优化效率和优化质量,而且可快速得到大规模问题的满意解本文方法无论是优化性能还是时间性能都取得了较满意的结果,具有实际工程应用价值。
从实验中也可看出,虽然分区所用的运行时间和运算复杂度降低,但在选取结点分区中,算法程序在所采用的参数设置及可扩展性等方面仍存在着不足。本文不论在协议还是在仿真方面都是采用网络层协议的优化,关于跨层协议的算法策略及性能的研究是否可以在此基础上延伸和实现,所以需进一步地研究和完善。
摘要：本文针对当前AdHoc网络路由的特点,在AdHoc路由优化算法基础上提出一种改进的蚁群算法。该算法首先将影响蚁群算法性能的参数作为遗传算法中的染色体,通过迭代找出最优的参数组合,然后对区域节点采用动态邻域分解的同时进行并行优化计算,最后将各子区域进行邻域全局连接得到最优解,该算法体现“分而治之”的思想。实验仿真结果表明,改进算法有效地提高了网络传输性能和通信效率,在性能上较基本蚁群算法有更大的优势。
关键词：Ad Hoc网络,路由协议,蚁群算法,邻域分区
参考文献
[1]左国明,于万钧,胡兆玮.基于改进蚁群算法的Ad hoc路由算法[J].计算机应用研究,2008,(25):59-61.
[2]李士勇.蚁群算法及其应用[M].哈尔滨:哈尔滨工业大学出版社,2004.
[3]丁建立,陈增强,袁著祉.基于动态聚类邻域分区的并行蚁群优化算法[J].系统工程理论与实践,2003,(9):105-110.
[4]张学敏,张航.基于改进蚁群算法的最短路径问题研究[J].自动化技术与应用,2009,28(6):4-7.
[5]王新生,贾冬艳,李学.基于蚂蚁算法的Ad hoc网络QoS多播路由[J].计算机工程,2009,35(11):218-220.
[6]T.Camp,J.Boleng,V.Davies.A survey of mobility mod-els for Ad Hoc networks research.Wireless Communica-tion&Mobile Computing(WCMC),2008,2(5):483-502.