基于遗传模拟退火的QoS单播路由算法
第29卷第12期2012年12月计算机应用研究
ApplicationResearchofComputersVol.29No.12Dec.2012
基于遗传模拟退火的QoS单播路由算法
陈晓娟,陈
摘
婧
(东北电力大学信息工程学院,吉林吉林132012)
要:针对QoS的问题,设计了一种融合遗传算法和模拟退火算法的QoS路由算法,在遗传算法选择算子上
借鉴了小生境的思想,避免了遗传初期有效基因的丢失;在遗传算法交叉算子和变异算子方面使用了自适应算子,使之能更好地适应网络的变化。通过与传统遗传算法进行比较,进一步说明了本算法的有效性。关键词:服务质量;单播;模拟退火遗传算法中图分类号:TP393.0
文献标志码:A
文章编号:1001-3695(2012)12-4680-03
doi:10.3969/j.issn.1001-3695.2012.12.072
QoSroutingalgorithmbasedongeneticsimulatedannealingalgorithm
CHENXiao-juan,CHENJing
(CollegeofInformationEngineering,NortheastDianliUniversity,JilinJilin132012,China)
Abstract:ThispaperputforwardakindofQoSroutingalgorithmswhichfusedthegeneticalalgorithmandsimulatedannealingalgorithm.Intheselectionoperatorsofgeneticalgorithm,itusedthethoughtofnichewhichavoidedtheearlylossofeffective
itusedadaptiveoperatorswhichcouldbetteradapttogene.Inthecrossoveroperatorandmutationoperatorofgeneticalgorithm,
thechangeofthenetwork.Thecomparisonwithtraditionalgeneticalgorithmfurthershowstheefficiencyofthealgorithm.Keywords:QoS(qualityofservice);unicast;geneticsimulatedannealingalgorithm
0引言
动函数delay_jitter(e)。本文将节点参数归并到该路径下游边的参数上。根据以上定义,数据包在网络上某特定路由路径的传输性能表示如下:
delay(e')=delay_jitter(e')=packet_loss(e')=1-
e∈p(s,d)e∈p(s,d)
近年来,随着视频会议、视频电话的普及和服务数量的增
加,越来越多的人开始加入互联网的使用团队之中,互联网的业务也呈现多样化的发展趋势。人们发现传统的尽力而为(besteffort)型服务越来越无法满足用户的需求,于是QoS成
[1]
为研究的热点。目前常用的QoS路由算法主要有Dijkstra、蚁群及其改进算法、遗传及其改进算法、粒子群方法等。但这些方法都是基于单一度量的路由算法,不能很好地满足QoS多种度量的要求,因此须提出一种考虑多种QoS特性的新的路由选择策略,即多约束QoS问题。研究证明,多个不相关可
[2]
加度量的QoS路由选择问题隶属于NP完全问题。遗传算法(GA)具有良好的全局搜索能力,而模拟退火算法具有良好的局部搜索能力,故将GA与模拟退火算法结合,加入小生境的思想以保持种群的多样化,并设计了自适应遗传算子和变异算子,以使其能够更好地适应网络的变化。本文根据单播多约提出了相应的束QoS要求建立了单播QoS路由的网络模型,单播QoS路由优化目标函数,最后进行仿真实验并分析了评价算法的性能。
∑delay(e)∑delay_jitter(e)
(1)(2)(3)(4)
e∈p(s,d)
∏(1-packet_loss(e))∑cost(e)
cost(e')=
e∈p(s,d)
2
2.1
遗传模拟退火算法的实现过程
遗传模拟退火算法流程
算法包含两个阶段,首先通过遗传算法搜索得到近优解,
然后再进行模拟退火操作。此过程反复迭代,直到满足终止条件为止,如图1所示。2.22.2.1
遗传算法参数的设计遗传编码
本算法的编码方法采用自然数序列编码法,即对于一条路由路径,以该路径经过的节点号序列作为该路径的编码值。例“S,N1,…,Nk,D”,如一条路由路径经过则可以表示为图2。2.2.2
适应值函数
适应值函数是反映遗传算法优越性的重要指标,其大小是判定算法收敛速度的重要依据。QoS单播路由计算的目的是在尽可能满足单播多约束要求的条件下,寻找费用最小的路径。本文的适应值函数就反映了路由算法的性能,设计了四个性能问题:带宽、延迟、丢包率以及费用。因此构造适应值函数采用罚函数的形式。
F(e)=cost(e)×(A1fd+A2fdj+A3fpl)
(5)
1网络模型和问题描述
[3]
E)表示网络。其中V表示所有节点设无向图graph(V,
一个节点代表一个路由器;E表示所有边的集合,每条的集合,
边代表两个相邻路由器之间的链路。为每个节点和边都设置一些度量权值,用来描述网络特性。s∈V为路由起点(即源节d∈{V-{s}}为路由终点(目的节点),点),对每条链路e∈E,定义三种度量:时延函数delay(d)、费用函数cost(e)、延时抖
收稿日期:2012-04-03;修回日期:2012-05-18
作者简介:陈晓娟(1973-),女,教授,博士,主要研究方向为电力线通信(919149563@qq.com);陈婧(1987-),女,硕士研究生.
基于遗传模拟退火算法的QoS组播路由算法_专业资料。提出了一种基于遗传模拟退火算法的带宽、时延和时延抖动约束费用最小的组播路由选择方法,该方法针对遗传算法的局限...
基于混合蚁群与遗传模拟退火的QoS组播路由算法_专业资料。对于网络业务,服务质量(QoS)包括传输的带宽、传送的时延、数据的丢包率等。通过使用蚁群算法的自组织能力...
基于遗传模拟退火算法的多约束QOS组播路由优化算法_专业资料。组播路由问题在计算机网络中是著名的Steiner树问题,是NP完全问题。通过考虑组播通信服务质量需求与网络...
基于遗传模拟退火算法的QoS组播路由问题求解_专业资料。提出了一种基于遗传模拟退火算法的带宽时延约束费用最小组播路由选择方法,该方法针对遗传算法的局限性,采用基于...
遗传模拟退火算法在组播路由选择中的应用_专业资料。本文研究基于带宽、时延及时延抖动约束最小代价的QoS组播路由优化算法。针对遗传算法在求解多目标优化问题时局部...
基于蚁群系统的QoS单播路由算法_互联网_IT/计算机_专业资料。。 J 二u 平昂 卺昂 期 Electronic Sci.&Tech./Jan.15.2014 基于蚁...
一种基于蚁群算法的QoS多播... 3页 10财富值 基于遗传模拟退火的QoS单播.....陈萍 等:一种基于概率的 QoS 单播路由算法 精确的程度. 583 如何表达和捕捉...
本文基于模糊数学、微观经济学和群体智能相关知识,引入服务质量QoS满意度和效用,设计了一种柔性QoS单播路由机制,应用量子遗传算法,寻找使网络提供方效用和用户效用达到...
考虑到选播的QoS路由问题,提出了一种基于模拟退火遗传算法的时延控制选播路由算法。该算法利用模拟退火的思想弥补了遗传算法局部收敛较弱和较慢的缺陷,并根据给定的...
来求解多QoS约束路由.在文献 〔18—20〕中,把遗传、蚁群和模拟退火这3个智能...数单播路由算法.在文献〔22〕中,提出了一种基于概 率的不精确链路信息下QoS...
热门文档