基于蚁群算法的邻域分区优化QoS单播路由算法研

基于蚁群算法的邻域分区优化QoS单播路由算法研随着网络技术的高速发展，网络的应用越来越广泛，全新的多媒体业务应运而生，对网络服务质量(QoS)的要求也更高，而传统网络所提供的服务方式已无法满足新业务的需求，设计满足新业务要求的网络控制机制和路由算法是当前的一个急待解决的问题。而现有的很多算法只对QoS一个或两个约束条件进行研究，在多种QoS约束下，这些算法具有一定的局限性。如何解决多个约束QoS路由问题，如何在满足业务要求的同时，尽量减少资源消耗，合理分配网络的流量负荷，减少阻塞率，成为新关注的热点。在解决这一问题时，路由算法的选择又是其中的一个核心问题，并且带宽、延时、访问花费是决定选择该路径的关键因素。论文针对这一状况和蚁群算法在大规模问题求解过程中存在的时间性能和算法复杂度的优化问题，提出了用基于蚁群算法的邻域分区优化算法对大规模的网络进行路由选择，也就是把大规模的网络按其区域位置分解成小规模的子系统，然后应用蚁群算法进行路由选择的仿真，该方法不但改善了蚁群算法在求解大规模问题的时间性能和算法复杂度，同时也解决了传统的路径选择不使用次优路径的弊端。论文在做路径选择时，主要用了带宽、延时、访问花费来作为路径选择的参数，用蚁群算法作为路径选择算法。论文的主要工作如下：一、对论文的选题背景、国内外QoS单播路由的研究现状、蚁群算法应用及研究和论文结构作概述；二、对路由原理、路由协议、路由算法、QoS路由等基本概念和原理作了系统的阐述三、对蚁群算法的原理和发展作了概述，并针对普通蚁群算法在求解大规模优化问题时面临着时间和性能的问题，把大规模优化问题进行分解为子规模优化问题，用蚁群算法进行仿真实验和结果分析。四、把改进的蚁群算法思想应用于OoS单播路由算法中，进行网络模型的构建，同时用服务质量的带宽、延时、访问花费三个参数，进行路由算法的模拟运算，寻找最佳路径，并对实验结果进分析。五、总结，对未来的研究工作做出展望。作者：杨丽华学科专业：通信与信息系统授予学位：硕士学位授予单位：云南大学导师姓名：施心陵学位年度：2005语种：chi分类号：TP393关键词：路由算法QoS单播路由蚁群算法邻域分区蚁群算法及其在路由优化中的应用路由算法是网络的重要组成部分，它直接影响着网络性能，而含有多约束条件的QoS路由是一个NP-C问题，传统的路由算法很难解决，因此，一些学者尝试采用不同的算法相结合或者针对问题对某些算法进行改进来解决路由优化问题。其中蚁群算法是一个行之有效的方法，针对不同的网络，它在保证服务质量的前提下能够搜索到网络中的最优链路，提高了网络的传输效率。而这些研究缺乏通用的标准，如何把不同的问题归结到一个统一的框架下解决路由优化问题，如何提高寻优速度，缩短运行时间是当前的一个研究热点。1蚁群算法的定义1.1蚁群算法基本定义定义1(蚁群算法)蚁群算法(antcolonyoptimization，ACO)，又称蚂蚁算法，是一种用来在图中寻找最优路径的技术。它最早出现在1992年Dorigo[1]的博士论文里，该方法具有正反馈、分布式计算和富于建设性的贪婪启发式搜索的特点，主要用于求解组合优化问题。定义2(启发式算法)对于那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方法，人们常常称之为启发式算法。现在的启发式算法也不是全部来自然的规律，也有来自人类积累的工作经验。收定义3(信息素)蚂蚁释放一种化学物质，根据环境中的这种物质蚂蚁可以找到食物和窝之间的最短路径，我们称这种物质为信息素。定义4(信息素更新)信息素更新是指路径上信息素量与蚂蚁数量的变化和时间的推移之间存在增加和消失的变化关系。每只蚂蚁走完一步或对所有n个节点的遍历完成后，要对链路上的信息进行更新。因此，定义t+n时刻在节点i到节点j的路径(i,j)上的信息量计算公式为+=1+(1)==1(2)式中：——信息素挥发系数，——本次循环中节点i到节点j的路径上信息素的增量。——第k只蚂蚁在本次循环中在节点i到节点j的路径上留下的信息量。定义5(链路选择概率)信息素踪迹越浓的路径，被选中的概率越大，即路径概率选择机制。设网络G=(V,E)，这里V表示图中顶点的集合，设=|V|，E表示边的集合。蚁群优化的目的是寻找图G中起始节点Vi到目的节点Vj的最短路径，每条边e(i,j)∈E都有一个信息素变量Tij，Tij会随着迭代次数的增加而变化。Pij表示在节点i选择到节点j的概率。表示节点i处可选择的下一跳邻居节点j的集合。则蚂蚁在选择路径时会根据可选每条链路上的选择概率进行选择，并在该节点根据概率分配蚂蚁。概率公式为=*(3)式中：——节点i可选的下一跳节点集合。=1(4)式中：——能见度因数，它由某种启发式算法决定。，，——3个参数，分别反映了蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性。1.2收敛性定义6(收敛性)设Pi(t)=P(i∈Y)表示第i条路径在t次迭代时得到最优路径时的概率，如果lim+=1则称该条路径具有收敛性(Y是路径上所有链路集合)。1.2.1蚁群算法收敛性证明蚂蚁通过环境中的信息素与其它蚂蚁进行交互，不断的迭代循环，最终找到最优路径，但是，由于迭代的次数会受到具体链路环境的影响，虽然能够得到最优路径但有可能会迭代好多次.这就影响了算法的效率，一些专家学者对算法的收敛性进行了研究。关于蚁群算法的收敛性，很多研究者都进行了分析证明。早期的有GutjarhWJ最先从有向图论的角度对特定的改进蚁群算法BGAS的收敛性进行了证明[2]，GutjarhWJ提出了两种新的GBAS，即GBAS/tdev和GBAS/tdlb，通过选择合理的参数来保证蚁群算法的收敛性并收敛到全局最优解；StuezleT和DorigoM提出了一类改进蚁群算法——ACOgb算法[3]并在理论上分析了它的收敛性，得出当迭代次数无限增大时，算法收敛到全局最优解。YooJH等对一类分布式蚂蚁路由算法的收敛性进行了深入的理论研究[4]。1.2.2对蚁群算法的改进蚁群系统由Dorigo和Gambardella于96年提出，能够在一个合适的时间找出好的解决方案。但只限小规模的问题。由于此限制，专家学者们针对不同的问题对蚁群算法进行了改进，典型的蚁群算法的改进有：带精英策略的蚁群系统；基于优化排序蚂蚁系统；蚁群系统；最大－最小蚂蚁系统；最优－最差蚂蚁系统。带精英策略的蚁群系统类似于遗传算法的精英策略。在此系统中，为了使得当前找到的最有解对下一次迭代循环中更能增加蚂蚁选择的概率，在每次循环迭代完以后对最有解增加额外的信息素量。缺点：虽然使用精英策略可以使蚂蚁系统可以较早的找出最优的解，但是，由于使用的精英蚂蚁过多，搜索容易集中在最优值周围，从而不能找出更好的解来。基于优化排序的蚂蚁系统借助遗传算法中排序的概念，根据每只蚂蚁走过的路径的长短进行大小排序，并根据大小顺序进行加权，在这里只考虑几只最好的蚂蚁，从而避免局部极优路径被很多蚂蚁过分重视的情况发生。最大－最小蚂蚁系统[5]是把集中到最优解的附近与避免早熟收敛行为结合在一起。该方法主要做了3方面改进：①在每次循环迭代以后，只允许一只蚂蚁进行信息素更新，这只蚂蚁既有可能是找出此次循环中最优解的蚂蚁也可能是从一开始以来最优解的蚂蚁。②为了避免搜索的停滞，把路径上信息素轨迹量的值域范围限制在[Tmin,Tmax]区间内。③为使蚂蚁在开始阶段就能够搜索到新的解决方案，设信息素轨迹初始值为Tmax。另外，宋雪梅等也提出了一种改进的ACO算法即PMACO算法[6]，PMACO算法主要是基于动态信息素升级和变化策略等以提高计算质量。根据蚁群算法，有的链路有蚂蚁通过，而有的链路没有蚂蚁通过，那么当短链路上的信息素增长比其它链路上的信息素增长快时，更多的蚂蚁会以更高的概率选择此链路。这样就容易出现蚂蚁在开始时刻容易选择局部最优链路，提出了变化概率规则，在刚开始采取大概率，其它时刻采取小概率。1.3收敛速度定义7(收敛速度)链路上信息素随迭代次数增加而聚集到最优连路上的快慢称为收敛速度。1.3.1蚁群算法收敛速度的分析关于蚁群算法的收敛性问题有很多学者都进行了一定的研究，并且得出了结论，蚁群算法是寻找最优路径可行的方法，通过不断的迭代最终找到最优路径，但是由于实际网络中的情况非常复杂，所以有时要经过大量的迭代最终找到最优路径，虽然能找到但效率也受到了一定的影响，由于蚁群算法在国内外研究的比较晚，而对如何提高收敛速度的研究更是成为该领域一个公开的问题。段海滨等[7]在对基本蚁群算法的Markov链分析过程中，运用离散鞅作为研究工具，把最优解集序列转变为下鞅序列来考察信息素轨迹向量的收敛性。并对蚁群算法几乎处处收敛问题和停时间问题进行了研究，提出了首达时间的定义，并对首次到达时间的期望值进行了分析蚁群算法信息素在路由协议中的实现目前蚁群算法主要用在组合优化方面，基本蚁群算法的思路是这样的：1.在初始状态下，一群蚂蚁外出，此时没有信息素，那么各自会随机的选择一条路径。2.在下一个状态，每只蚂蚁到达了不同的点，从初始点到这些点之间留下了信息素，蚂蚁继续走，已经到达目标的蚂蚁开始返回，与此同时，下一批蚂蚁出动，它们都会按照各条路径上信息素的多少选择路线(selection)，更倾向于选择信息素多的路径走（当然也有随机性）。3.又到了再下一个状态，刚刚没有蚂蚁经过的路线上的信息素不同程度的挥发掉了(evaporation)，而刚刚经过了蚂蚁的路线信息素增强(reinforcement)。然后又出动一批蚂蚁，重复第2个步骤。每个状态到下一个状态的变化称为一次迭代，在迭代多次过后，就会有某一条路径上的信息素明显多于其它路径，这通常就是一条最优路径。关键的部分在于步骤2和3：步骤2中，每只蚂蚁都要作出选择，怎样选择呢？selection过程用一个简单的函数实现：蚂蚁选择某条路线的概率＝该路线上的信息素÷所有可选择路线的信息素之和假设蚂蚁在i点，p(i,j)表示下一次到达j点的概率，而τ(i,j)表示ij两点间的信息素，则：p(i,j)＝τ(i,j)/∑τ(i)（如果所有可选路线的信息素之和∑τ(i)＝0，即前面还没有蚂蚁来过，概率就是一个[0,1]上的随机值，即随机选择一条路线）步骤3中，挥发和增强是算法的关键所在（也就是如何数学定义信息素的）evaporation过程和reinforcement过程定义了一个挥发因子，是迭代次数k的一个函数ρ(k)＝1－lnk/ln(k+1)最初设定每条路径的信息素τ(i,j,0)为相同的值然后，第k+1次迭代时，信息素的多少对于没有蚂蚁经过的路线：τ(i,j,k+1)＝(1－ρ(k))τ(i,j,k)，显然信息素减少了有蚂蚁经过的路线：τ(i,j,k+1)＝(1－ρ(k))τ(i,j,k)＋ρ(k)/|W|，W为所有点的集合为什么各个函数要如此定义，这个问题很难解释清楚，这也是算法的精妙所在。如此定义信息素的挥发和增强，以及路径选择，根据马尔可夫过程（随机过程之一）能够推导出，在迭代了足够多次以后，算法能够收敛到最佳路径。组合优化很有意思的，像禁忌搜索、模拟退火、蚁群算法、遗传算法、神经网络这些算法能够解决很多生活中的实际问题。