文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 互联网 > 基于遗传模拟退火的QoS单播路由算法
侵权投诉

基于遗传模拟退火的QoS单播路由算法

基于遗传模拟退火的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-),女,硕士研究生.

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email