基于免疫蚂蚁算法的多约束QoS路由选择算法

1、基于免疫蚂蚁算法的多约束QoS路由选择算法陈荣元（长沙交通学院计算机系，湖南 长沙 410076）摘要：本文针对多约束路由选择问题，提出了一种新颖的免疫蚂蚁算法。不失一般性，选择费用、带宽、延时、丢失率和时延抖动为QoS参数，专门设计了该算法的实现步骤和流程图。最后，实例表明所提出的算法是有效的。关键词：QoS路由选择；免疫蚂蚁算法；费用；时延；带宽；丢失率A Multiple Constrained QoS Routing Based on Immune and ant AlgorithmCHEN Rongyuan（Dept.of Computer,Changsha Communicatio

2、n University,Changsha 410076 China）Abstract:The paper aims at the problem of QoS routing with multiple Constraint, presents a novel immune and ant algorithm .Without losing generality, cost, bandwidth, delay and loss rate are chosen as QoS parameters ,the concrete realization steps and steam chart w

3、ere designed. Finally, an example demonstrates that the algorithm is effective and efficient.Key words: QoS routing;immune-ant algorithm;cost;delay;bandwidth;loss rate1 引言QoS路由的主要目标是为接入的业务选择满足服务质量要求的传输路径，同时保证整个网络资源的有效利用。度量参数选择问题、寻径问题和路由信息不准确问题是QoS路由中的几个主要研究内容。本文着重研究多约束QoS路由选择问题。多约束QoS路由选择是指在网络中寻找一条满

4、足传输带宽、链路时延、时延抖动和信息丢失率等约束条件，并使通信费用最小的路径。多约束QoS路由选择是一个NP完全问题11。遗传算法5、Hopfield 神经网络方法689 、蚂蚁算法1015、点火耦合神经网络方法12等都有人用来求解多约束QoS路由选择问题。遗传算法是一种启发式随机搜索算法，求解组合优化问题时存在的主要问题是遗传进化的性能与遗传算子以及适应度函数的设计密切相关，遗传进化容易收敛到局部最优。Hopfield网络求解组合优化问题近年来十分活跃，但其网络能量函数的设计和网络局部极小点的逃离等仍未得到很好解决；网络的负梯度下降本质上使得网络收敛到局部最优解。目前这方面的研究包括引入参数

5、Hopfield网络和Hopfield网络能量函数的改进8 9。点火耦合神经网络方法12利用耦合神经网络方法的自动波生成和传播特性求解QoS路由选择问题收到了较好的效果。蚂蚁算法1015是目前QoS路由中研究比较多的一种方法，由Dorigo等提出1314 ，该算法是一种分布式探测寻路方法，具有全局寻优能力。缺点是算法中参数较多，选择尚无理论指导，不能保证收敛于全局最优。免疫网络理论最初由Jerne提出16，在此基础上提出了许多人工免疫工程方法，包括基于免疫系统而特别设计的解决约束、多模式和组合优化问题的免疫计算方法17181920 。基于免疫学的计算方法结合先验知识和免疫系统适应能力，提供了新

6、颖的解决复杂优化问题的方法和能力。本文针对QoS路由选择问题，提出了一种新的融合算法即免疫蚂蚁算法。算法的基本思想是把待求解的问题对应为抗原，问题的解对应为抗体，利用蚂蚁算法的全局寻优能力和免疫算法的适应能力求解组合优化问题，实验结果表明免疫蚂蚁算法表现出了超越免疫算法和疫蚂蚁算法的优点，在考虑了五个路由限制的情况下，算法的效率得到了大幅度的提高。2 免疫算法原理1,2, 20免疫算法的一般框架流程如图1所示。其中算法中的抗原通常是指目标函数。算法中的抗体通常是指目标函数的优化解。算法步骤：1） 免疫细胞产生产生初始抗体：随机产生N个个体或从记忆库中提取N个个体构成初始群体；2） 抗原与抗体相

7、遇分析问题：对问题及其解的特性进行分析和了解，并设计解的合适表达形式；3） 抗体识别抗原对上述群体中各抗体进行评价：通常采用基于个体浓度的适应度评价策略；在自然免疫系统中，为保持抗体的多样性，通常在鼓励与抗原有高匹配度的抗体的同时，对浓度过高的抗体予以抑制。并且抗原与抗体的匹配不是完全匹配，而是部分匹配，从而保证任一种抗原都有至少一种抗体与之匹配。4） 抗体繁殖：基于上一步的计算结果对抗体群体进行选择、交叉、变异操作得到新群体。5） 判断是否满足结束条件。是，则结束；否，则继续下一步操作。6） 转去执行第3）步。3 基于免疫蚂蚁算法的QoS路由算法31问题描述网络模型可以表示为赋权图G=(V,

8、E)，其中V是图中所有节点组成的集合，E是图中所有边的集合，每一条边表示相邻两节点间的直达通信路径 ，假定相邻两节点间最多仅有一条边。 bandwidth(i)代表相邻节点间的直通链路i的可用带宽。对于一个路由请求R，路由算法如果能够找到一条具有最小费用的路径L，同时满足以下四个条件，L就被路由请求R就可接受。1 带宽可用限制：, j 为L上的任意一条链路；2 端到端时延限制：，其中i为L上不包括起始节点的其他所有的节点，j为L上的任意一条链路； 3 端到端丢失率限制： , 其中i为L上不包括起始节点的其他所有的节点；4 端到端时延抖动限制：NDV(aim)jitter, NDV(aim)是在

9、目的节点的延时变化。其中bandwidth、delay、loss、和jitter分别代表QoS要求的带宽、时延、丢失率和时延抖动限制。32采用免疫蚂蚁算法的QoS路由从第二部分地区免疫算法的一般步骤的描述可以看出，免疫算法中有几个关键点在具体实现时是要认真考虑的，一是抗体和抗原的编码形式；二是抗原与抗体的匹配规则；三是抗体的评价方法；四是新抗体的产生和新群体的形成规则；五是记忆库的设计和使用。L(f、n1,n2,nk、a) cost delay loss jitter1、 抗体的编码形式如下： 记为A(L(f、n1,n2nk、a)、cost、delay、loss、jitter)，其中L(f、n

10、1,n2nk、a)、cost、delay、loss、jitter分别表示路径、抗体的实际费用、时延、丢失率和时延抖动。from aim bandwidth delay loss jitter2、 抗原的编码形式如下：记为R(from 、aim、bandwidth、delay、loss、jitter)表示，其中from 、aim，bandwidth、delay、loss、jitter分别表示路由请求的源节点、目的节点，所需带宽和允许的最大延时、丢失率、时延抖动。3、 抗原与抗体的匹配规则：如抗体的L(f、n1,n2nk、a)是以抗原的from为起点aim为终点的不间断的路径，且满足四个约束条件，

11、抗原与抗体就匹配规;否则不匹配。4、 抗体的评价方法： 对于多个抗体（候选解），通常根据抗体和抗原间的亲和力(applicability)的大小来判断哪一个是最优抗体（最优解），本文中的亲和力定义为： 其中：maxconst是一个比较大的常数， c、d、l、j是常数，在算法中，根据cost、delay、loss和jitter的相对重要性来选定它们的值。5、 新抗体的产生和新群体的形成规则：利用蚂蚁算法产生一批新抗体，再把它们和局部记忆库中的现有抗体一起进行配对、交叉产生一批新抗体；最后从新产生和局部记忆库中的抗体中选取applicability值大的一批作为新抗体群。6、 忆库的设计和使用：算

12、法中采用两个记忆库（局部和全局记忆库），局部记忆库是存储求解某个抗原过程中局部最优抗体，规模为10；全局记忆库是用来存储针对某个抗原最终求得的最优抗体，规模为5。7、抗体交叉规则：多个抗体随机配对后,在一对抗体中寻找相同节点(源节点和目节点除外)，若有多个相同节点就随机选一个作为交叉点。例：A（2、4、5、8）和B（2、3、4、8）是配对后的一个对抗体，我们选择节点4为交叉点，交叉后得到两个新抗体C（2、4、8）和D（2、3、4、5、8）。蚂蚁算法3,4,10涉及到三种主要规则（状态转移，全局和局部信息素更新），文献13已证明了同时采用全局和局部两种更新规则可以取得更快的全局优化结果，本文采用

13、两种更新规则。三种规则定义如下：1状态转移规则：蚂蚁在节点f处选择节点t的概率 (2) 其中：i为所有与f存在直接边的节点。 2局部信息更新规则： 其中a0,b0,const是常数3全局信息更新规则：其中：a1,b1是常数，price是最优抗体和抗原的亲和力算法中把网络两节点间直接存在的通路作为自我，也作为一个基因，为了提高效率，在程序开始前拒绝那些时延抖动不能满足的请求；并过滤掉那些带宽小于需求带宽的边，具体实现中是令这些边的信息素为零；在针对某个抗原寻找抗体的过程中先不考虑延时、丢失率的限制，而是等找到抗体后再判断新求得的抗体是否满足要求。根据上述分析得到算法如下（算法流程见图2）：1)

14、输入请求：输入请求R(from 、aim、bandwidth、delay、loss、jitter)；2) 否定选择：判断路由请求是不是自我（即检查源目节点间是否存在直接通路），如是就作为一个初始抗体；3) 查询记忆库：检查全局记忆库中有无该请求，如有就作为一个初始抗体；4) 产生初始抗体：采用蚂蚁算法结合路由请求（抗原），遵循状态转移规则产生一批初始抗体；按公式（3）进行信息素更新；5) 抗体更新：利用蚂蚁算法产生新抗体，并把它们和局部记忆库中的现有抗体一起进行配对、交叉产生新抗体；6) 计算亲和力applicability和抗体选择：按公式（1）计算各个抗体的亲和力applicability

15、，选取一批较优的存入局部记忆库中；根据新入记忆库的那些抗体按公式（4）进行信息素更新；7) 如果满足结束条件就输出结果，最优抗体取代全局记忆库中最少被选为初始抗体的那个记忆细胞，结束循环；否则转第5）步。4 实例仿真图3是本文所采用的网络拓扑，图中每个顶点用表示，其中的元素分别代表节点时延、节点丢失率和节点时延变化。每条边用表示，其中的元素分别代表边的费用、带宽和链路时延。假定有五个路由请求,它们QoS的参数见表1。为了使在保证满足带宽、时延、丢失率和丢失率的前提下，优先使费用达到最小，再尽量使时延、丢失率和时延变化最小，多次试算后，我们最终选取仿真参数为：a0=0.069, const=0.

16、3210, a1=2.210-7,b0=b1=0.05,maxconst=100000，c=1000,d=100,l=10,j=1。每条边初始pheromone取为100，每一次迭代放出个蚂蚁，获得全局优化结果如表1所示。此仿真的平均迭代10次就能得到最优解，小于基于蚂蚁算法的QoS路由调度方法迭代次数（134次）3和基于遗传算法（GA）的QoS迭代次数（152次）5，更远远小于基于Hopfield神经网络的QoS路由选择迭代次数（10941次）6。5 结论与分析本文提出了免疫蚂蚁算法来解决QoS路由受限问题，在蚂蚁算法处理QoS问题效率较高的基础上，免疫算法把目标函数和约束条件作为抗原，这就

17、能保证所生成的抗体直接与问题相联系，收敛方向能得以控制，生成的抗体能有效排除抗原，也就相当于求得了问题的最优解。对与抗原亲和力高的抗体进行记忆，能促进快速求解，即当遇到同类抗原时，可以快速生成与之对应的抗体。算法中的交差、变异操作增强了抗原识别、记忆功能和调节功能。本算法解决QoS问题达到了很高的效率，仿真也验证了此算法的有效性。参考文献：1 Watkins A, Boggess L. A New Classifier Based on Resource Limited Artificial Immune Systems. Proceedings of the 2002 Congress on

18、 Evolutionary Computation CEC2002 EC,1546-15512 Luo Wenjian and Cao Xianbin and Wang Xufa . An Immune Genetic Algorithm Based on Immune Regulation. Proceedings of the 2002 Congress on Evolutionary Computation CEC2002.801-8063 S. Zhang, Z. Liu. A QoS Routing Algorithm Based on Ant Algorithm. IEEE ICC

19、 2001, l(5):1581-15854 Isaacs J, Watkins R, Foo S. Evolving Ant Colony Systems in Hardware for Random Number Generation. Proceedings of the 2002 Congress on Evolutionary Computation CEC2002 EC,1450-14555 FENG X,LI J Z, WANG J V,et al. QoS routing based on genetic algorithmJ.Computer Communications,1

20、999,22 (15- 16):1392-1399.6 Chotpat P,Goutam C,Norio S. Neural network approach to multicast routing in real- time communication networksA. Proc International Conference on Network ProtocolsC,1995:332 3397 Kuntimad G,Rangnath H S. Perfect image segmentation using pulse coupled neural networksJ.IEEE

21、Trans Neural Networks,1999,10（3）:591-598.8 Hopfield J J.Tank D W. “Neural” computation of decisions in optimization problemsJ.Biological Cybernetics,1985,54（3）:141-152.9 Alexei N S. Parallel image processing with autowaves; segmentation and edge exaction EN/OL. 10 张素兵,吕国英,刘泽民,周正基于蚂蚁算法的QoS路由调度方法电路与系统

22、学报，2000,5：1-511 XIAO XI-PENG,Lionel M Ni. Internet QoS : A Big PictureJ. IEEE Network, 1999,13(2):8-1812 张军英,王德峰,石美红.基于点火耦合神经网络的多约束QoS路由选择算法.通信学报,2002,7：40-4713 Dorigo M,Gam bardella L M. Ant colony system:A Cooperative Learning Approach to the Traveling Salesman Problem.IEEE Trans.on Evplutionary Computation,1997,1(1):53-6614 Gianni Dicaro, Mario Dorigo. Ant-Net:Distributed Stigmergetic Control for Communications Networks. Journal of Artificial Intelligence Research,1998,9:317-36515 R Schoonderwoerd,O Holland, J Bruten,L Rothkrant