张志成[1]2013年在《群智能优化算法在QoS组播路由中的应用研究》文中认为随着网络技术的飞速发展,尤其是多媒体技术(如视频会议、网络电视、网络游戏、IP电话等)的广泛应用,对网络的传输能力提出了更高的要求。此类应用往往需要网络具备多点通信的能力,而组播通信就是针对多点传输和多方协作设计的通信方式。此通信方式在主链路上只有一个数据的拷贝,在分支链路上由路由器进行数据包的复制传输,极大的降低了网络资源的消耗,具有高效的数据传输效率。组播通信必将成为下一代网络数据传输中重要的支撑技术。组播路由是组播通信的关键和核心技术,要实现组播通信必须确定组播路径,组播路径是用组播分布树来描述的,而构建组播分布树就是组播路由的任务。QOS即服务质量,它能确保网络业务量的高效传输,针对各种网络业务的不同需求提供不同的服务质量,达到区分业务提高服务质量的目的。QoS组播路由的重要任务是构建一棵能够满足各种业务对服务质量需求的组播树,学者Kompella首先证明了具有两个或多个不相关可加性约束的QOS组播路由是NP-Complete问题,并提出了KPP算法来构造满足时延约束的Steiner树。随着多媒体技术的深入发展,多媒体业务对网络资源的要求愈来愈高,多约束条件下的QoS组播路由技术成为当前研究的热点。现代群智能优化都是基于自然界生物群体所表现出的群体智能现象所提出的,这些算法设计简单、易于理解,对所应用的领域没有特殊要求。因此,群智能优化算法得到广泛的研究与应用。传统QOS组播路由算法(最短路径树算法、最小Steiner树算法)有自己特殊的数学模型并有严格的论证,但是现实中的网络结构往往很复杂并且具有不确定性,并不是一种模型所能描述的,而群智能算法是启发式算法,可以避免建立严格模型的困难,对有两个或两个以上目标和约束的复杂可变网络一般都能求出有效解。近几年,将遗传算法、蚁群算法、粒子群算法等群智能优化算法应用到QoS组播路由中的文章相继发表,这些文章大多是对某一种算法的收敛时间、运行效率和搜索能力进行探索,因为每一篇文章所采用的仿真模型各不相同,所以不便对这些群智能优化算法进行统一的比较,不能形成一个全面的认识。本文采用Salama网络拓扑随机生成算法生成一个随机网络拓扑模型,定义相同的源节点和组播组节点,相同的QOS约束条件,在相同的网络拓扑模型基础上应用遗传算法、蚁群算法、粒子群算法、萤火虫算法求解QOS组播树,并对QOS的相关参数进行分析。本文使用Matlab仿真平台进行算法仿真,并使用该软件绘制相关的图表,对仿真结果进行分析研究。
张洁[2]2003年在《遗传算法在QoS组播路由算法中的应用》文中认为在计算机网络中，随着大量新兴多媒体实时业务的应用，以及Internet上商业化应用的飞速发展，网络对QoS需求增长，高效的QoS支持变得越来越重要。而路由机制是实现QoS保证的关键之一，应将路由选择和QoS相关联。 目前组播路由算法的研究大多都针对无约束组播路由问题和时延受限组播路由问题，多采用启发式等方法。本论文研究如何将遗传算法这一新型优化算法应用到QoS组播路由算法问题中，利用该算法的并行搜索、群体优化的特点，为解决QoS组播路由问题寻找新的途径。本文主要研究四类典型的QoS组播路由问题求解。主要研究工作共分四个部分： 第一部分是绪论，对计算机网络的组播通信进行了综述。主要介绍组播引入的背景、特点、组播技术，还叙述了QoS的相关内容、研究现状、组播路由协议和应用。 第二部分是研究的基础部分，主要介绍了QoS的描述参数、数学模型、存在问题以及组播路由算法研究现状。 第叁部分介绍了遗传算法的历史、特点、优缺点和应用，还介绍遗传算法的基本步骤，混合遗传算法，还包括在遗传算法中用于解决约束优化问题的常用方法。 遗传算法在QoS组播路由算法中的应用 第四部分是本文研究的重点，着重介绍目前的研究热点一基于遗传算法的组播路由算法。主要研究四个方面的问题:时延约束组播路由问题;时延和时延抖动约束组播路由问题;带度约束的组播路由问题;多个QoS约束的组播路由问题。根据QoS组播路由的特点，结合遗传算法的寻优特性，提出来一种新的混合遗传算法解决时延约束组播路由算法和一种新的混合遗传算法解决多个QoS约束的组播路由问题的组播路由算法。
王宇[3]2003年在《基于遗传算法的QoS组播路由》文中进行了进一步梳理随着宽带IP技术的发展，像视频会议这样的多媒体业务得到了越来越多的应用。一方面在这些业务中，很适合用组播的方式一次性地将报文传送到多个接收者，以节省网络资源；另一方面这些业务都是一些实时性很强的业务，需要提供QoS保障。在满足QoS的条件下，寻找将分组发送到一个组播组中所有成员的路径的过程称为QoS组播路由。QoS组播路由算法是宽带IP的一项核心技术。求解高效的QoS组播路由是开展宽带IP服务的关键所在。然而研究表明，由于QoS组播路由带有多个QoS约束参数，因此QoS组播路由问题是一个NP完全问题，这使得它与传统的路由过程不同，难以用经典的最短路径优先算法求解。以前，许多研究都集中在采用启发式算法来求解该问题。然而由于这些算法都具有较高的时间复杂度而不能满足实际应用的需要。本文采用了基于遗传算法的QoS组播路由算法来求解该问题。遗传算法是近年来提出的一种新型优化算法。它基于自然选择的原理，通过循环执行相同的、简单的选择、杂交和变异叁种遗传操作，并在适应度函数值的引导下对复杂的解空间进行有效地搜索，直到获得最优的解。选择、杂交和变异是遗传操作的叁个基本遗传算子，选择和杂交完成遗传算法的大部分搜索功能，而变异增加了遗传算法找到最优解的能力。本算法利用树型结构的编码来表示组播树的染色体。在杂交算子的设计上，通过对两个父代个体结合，然后再生成组播树的方法，使算法具有较好的杂交性能。通过对该算法的仿真分析可以看出整个算法能以较快的速度求解。在本文的最后，对该算法进行了分析，阐述了遗传算法在求解QoS组播路由问题上的广阔前景。
卢婷[4]2013年在《基于遗传算法的无线Ad Hoc网络QoS组播路由研究》文中认为服务质量(Quality of Service, QoS)组播(multicast)路由是网络优化的难题之一。用启发式算法解决QoS组播路由问题，计算时间和代价会随着网络规模的扩大而急剧增大。遗传算法(GeneticAlgorithm, GA)由于具有较强的适应性、强壮性和灵活性，是求解QoS组播路由问题的重要手段。由于WANET(Wireless Ad Hoc Network, WANET)节点能量有限，与有线网络不同，无线Ad Hoc网络QoS组播路由问题需要考虑能量消耗。随着多媒体应用的飞速发展，QoS组播路由也需要考虑传输延迟和代价。本论文主要围绕华为技术有限公司研究项目“BGP路由协议硬件加速”和“IP流量探测技术”在无线Ad Hoc网络中的研究任务，从无线Ad Hoc网络的特点出发，对Ad Hoc网络QoS组播路由问题展开了深入研究，在QoS组播路由中考虑了传输延迟、路由代价、能量消耗、网络生存期和组播生存期。本文的主要创新性研究成果如下：(1)在无线Ad Hoc网络中提出了叁个QoS组播路由问题，分别是：延迟抑制最小能耗组播路由(Delay-Constrained Minimum-Energy Multicast Routing, DCMEMR)问题，目的是为了保证多媒体应用的延迟约束，并同时减小组播的能量消耗；最大网络生存期最小代价组播路由(Maximum-Network-Lifetime Minimum-Cost MulticastRouting, MaxNLMCMR)问题，目的是为了减小组播传输代价的同时延长网络的生存期；延迟抑制最大组播生存期组播路由(Delay-Constrained Maximum-LifetimeMulticast Routing, DCMaxLMR)问题，目的是为了保证多媒体应用的延迟约束，并同时延长组播的工作时间。(2)提出了树结构编码法。树结构编码法用组播树本身来描述染色体，省略了遗传算法执行过程中的编码/解码操作，可以简化遗传算法，加速算法的收敛。(3)针对DCMEMR问题，提出基于遗传算法的延迟抑制最小能耗组播路由算法(GA-based Delay-Constrained Minimum-Energy Multicast Routing Algorithm,DCMEGA)。该算法的遗传算子能减小组播树的延迟和能量消耗，加速算法的收敛。实验结果证明该算法构造的组播树不仅满足延迟抑制条件，而且能量消耗最小，并且该算法能快速收敛。(4)针对MaxNLMCMR问题，提出基于遗传算法的最大网络生存期最小代价组播路由算法(GA-based Maximum-Network-Lifetime Minimum-Cost Multicast RoutingAlgorithm, MaxNLMCGA)。该算法的遗传算子能减小组播树的传输代价和能量消耗，变异算子能延长网络生存期，加速算法的收敛。实验结果证明该算法构造的组播树不仅传输代价最小，而且网络生存期最长，并且该算法能快速收敛。(5)针对DCMaxLMR问题，提出基于遗传算法的延迟抑制最大组播生存期组播路由算法(GA-based Delay-Constrained Maximum-Lifetime Multicast Routing Algorithm,DCMaxLGA)。该算法的遗传算子能减小组播树的延迟和能量消耗，变异算子能延长组播生存期，加速算法的收敛。实验结果证明该算法构造的组播树不仅满足延迟抑制条件，而且组播生存期最长，并且该算法能快速收敛。
徐佳[5]2006年在《IP QoS中主动队列管理和组播路由算法研究》文中研究指明信息时代的来临已经使Internet已成为一个重要的和无处不在的基础设施,与此同时,随着分布式多媒体应用需求的不断增长,以及Internet上商业化应用的飞速发展,对网络性能和服务质量提出了更高的要求。但是“尽力而为”服务仍是日前Internet中主要的一种服务类别,所有分组在网络中被同等对待,缺少有效的管理,局部的拥塞经常发生,导致网络性能下降、应用的分组丢失和数据抖动。如何提高IP网络的服务质量(QoS),已经成为众多国际组织、网络设备制造商和业务提供者研究和应用开发焦点问题。而主动队列管理机制是实现服务质量的基础,QoS组播路由是实现服务质量的重要手段,目前这两方面的研究己成为IP网络研究领域的一个热点。本文的研究工作主要集中在主动队列管理(AQM)算法和基于QoS组播算法的研究上。提出了几个改进的主动队列管理算法和有效、实用的QoS组播路由算法。取得的主要成果如下:(1)提出了一种能动态调整参数的随机早期检测算法DRED,一方面,通过主动丢包率来调整Maxp的值,调整对拥塞的控制力度,使算法更能适应网络状态的变化,保持较高的效率;另一方面,使丢包率以相对队列长度的二次方进行调整,使丢包率对队列的长度更加敏感,使队列更加稳定,尽量减少强制丢包。实验表明DRED算法降低了丢包率,提高了传统RED算法的网络适应性和链路利用率。(2)提出了一种精确度加强的主动队列管理算法BLUE+,该算法根据平均队列长度,对BLUE算法的步长参数detin、detde进行动态调整,并且依据TCP友好公式中丢包率与连接数之间的关系,调整Pmark值。此外在队列长度减少时候提高算法的刷新速度,避免了大量丢包。在此基础上,研究了在区分服务环境下基于BLUE+的TCP拥塞控制方法。仿真表明:在TCP连接数突变的情况下,BLUE+精确度加强算法的性能明显要好于BLUE算法,并且能提高吞吐率,降低丢包率。在区分服务环境下能有效地工作。仿真实验表明,BLUE+是一种稳定、有效的队列管理算法。(3)针对多维QoS约束的组播路由问题,提出了一种基于遗传算法的解决方案QCMRA-GA。该算法对经典遗传算法的叁大算子进行了重新设计,有效地克服了遗传算法的早熟现象。对染色体进行Prufer树型编码,可以避免回路的产生,并根据编码特性,进行基于叶子节点和Steiner节点的解空间压缩,提高了算法的收敛速度。实验表明QCMRA-GA的正确性和效率性。(4)针对多QoS约束的组播路由问题,借鉴改进的蚁群系统,提出了一种新
陈艳, 李志远, 马莉[6]2016年在《基于遗传算法的优化QoS组播路由算法》文中指出随着网络宽带技术的快速发展,多媒体业务对服务质量(QoS)的要求越来越高,QoS组播路由也成为制约宽带技术发展的关键问题。为了提高通信网络的利用率和解决网络传输中QoS组播路由问题,提出了一种基于遗传算法的优化QoS组播路由算法。首先介绍了QoS组播路由的网络模型,然后详细阐述了优化QoS组播路由算法的设计,并通过仿真实验证明了该算法具有加快算法收敛速度,提高网络带宽利用率,降低网络拥塞等优点。
姜圳[7]2004年在《基于QoS的组播路由关键技术研究》文中认为QoS 组播路由就是给定一个源节点s,一组目的节点集D,一系列QoS 限制条件C,以及可能的优化目标,寻找满足C 的覆盖s 和D 中所有节点的最好的有效树,这是一个NP 完全问题。当前多数QoS 组播路由研究集中在下面的几个问题:带宽受限组播路由;延迟受限组播路由;延迟受限最小代价组播路由;时延—时延抖动受限组播路由。求解该类问题是一个NP 完全问题,不存在确定型多项式复杂性解法。目前都采用启发式算法来解决,当前提出的启发式算法十分复杂而难以求解,该类问题是学术界的研究热点。由于在测控网络中对于数据传输的实时性要求很高,同时要求非常小的延迟抖动和信息的安全性,因此本文的研究工作主要集中在探讨网络QoS 组播路由算法如何支持实时通信,及寻求相对简单且易于求解的保证QoS 组播路由的算法,以及保障组播通信安全。本文根据国内外大量的研究文献资料,将智能优化算法应用到QoS 组播路由进行详细的分析论证。在此基础上利用遗传算法来求解QoS 组播路由问题,并且提出改进的二进制编码方法,该运算简单且可以快速的收敛到最优解,在理论研究的基础上进行仿真和实验研究。本文提出将模拟退火引入组播路由求解问题中,通过不断的“产生新解,判断,接受/舍弃”的迭代来寻求到全局最优解,即找到符合要求的组播树。模拟退火算法是一种随机搜索算法,可以很快的收敛到最优解或近似解。在做理论研究的基础上进行仿真和实验研究。本文同时提出一种基于QoS 要求的混合遗传组播路由算法,以保证QoS 路由对组播实时通信的支持,并进行模拟仿真实验,与遗传算法和模拟退火算法比较,证明所提算法的有效性。
刘宇浩[8]2011年在《动态克隆选择算法在QoS组播路由中的应用研究》文中研究指明网络服务质量(Quality of Service, QoS)属于一种网络安全机制,它具备疏通网络交通、保证网络传输效率、防止网络阻塞等优势。目前的网络技术,在提高网络传输速度、保证网络安全的同时,QoS的重要性也逐渐显现出来,网络服务质量的提升,可以更好的利用网络资源,减少由于网络阻塞、资源独享而产生的开销。QoS组播路由问题是一种满足网络约束的组播策略,可以提高网络资源利用率。该问题的主要任务是在网络环境中寻找一条满足约束条件的路径,其中的约束条件包括带宽、时延、时延抖动和费用等。QoS组播路由可以对不同的用户提供不同的服务,满足网络环境的动态性、异构性。实验证明,超过两个约束的QoS组播路由问题是一个多项式复杂程度的非确定性完全问题(Non-deterministic Polynomial Time Complete, NP-C),即无法在任何一个多项式时间内寻找到问题的解。解决NP-C问题的方法有很多,目前针对QoS路由优化,较为成熟的算法是蚁群算法,由于蚁群算法是分布式的智能算法,具有鲁棒性、一定概率的全局性,高效的空间搜索能力,故成为了解决优化问题的有效的启发式算法之一。但蚁群算法具有盲目性,无针对性,对路径搜索时间较长,易出现停滞现象。该算法最重要的不足是缺乏对动态网络环境的适应性。因此,本文对人工免疫系统进行了研究,并针对QoS组播路由选择问题,尝试在免疫系统中寻找解决NP-C问题的途径,并提出了将动态克隆选择算法(Dynamic Clonal Selection Algorithm, DCSA)应用在QoS路由选择问题中。DCSA算法是一种具有动态特性的克隆选择算法,该算法多数被应用于网络故障诊断,可以解决自体集多变的环境问题。本文以解决当前QOS组播路由算法前期收敛慢、缺乏动态性为目的,通过研究DCSA算法的特性,寻求该算法在QoS组播路由问题中的衔接点,发现人工免疫系统普遍存在局部最优、新种群元素生成效率低等缺点。因此,课题从智能仿生算法入手,分析研究目前多种流行的仿生算法理论。由于人工鱼群算法具有前期收敛速度快,全局性好及适用于组合优化问题等特点,所以课题选取人工鱼群算法作为DCSA算法改进的理论依据,并提出了新算法对应的模型,详细介绍了各模块的结构。最终将改进后的DCSA算法应用于QoS组播路由问题,在实验阶段,根据实际网络环境,建立更符合实际的随机网络结构进行模拟实验,实现QoS组播路由算法。
赵雄蛟[9]2013年在《智能算法在多约束QoS组播路由问题中的应用研究》文中研究指明多约束QoS组播路由问题是下一代网络发展亟须解决的一个关键问题。对其展开研究具有重要的应用价值和学术价值。多约束QoS组播路由问题被证明是一个NP难问题，所以传统的图论方法对其无能为力，研究启发式算法是一个较好的选择。近十几年来流行的智能算法由于其优秀的优化性能得到了广泛的应用。迄今为止，几乎所有的智能算法都已被应用于解决多约束QoS组播路由问题。尽管如此，现有的智能路由选择算法仍然有不足之处，如未成熟收敛，容易出现停滞现象，时间耗费过大，过于复杂等。本文针对现有智能算法在解决该问题上的不足展开研究，取得了一些成果，主要包括：①针对现有遗传算法应用于多约束QoS组播路由问题时存在收敛速度慢、容易陷入局部最优等不足，从种群初始化、交叉、变异操作叁个方面对遗传算法进行改进，提出一种改进的遗传算法求解多约束QoS组播路由问题，并采用8个节点的网络实例实验仿真，通过实验表明改进遗传算法的有效性。②为了克服现有萤火虫群算法应用于多约束QoS组播路由问题时存在时间耗费多、自适应性和鲁棒性不强等不足，从荧光素更新方式、动态决策域更新方式和邻居集合更新方式叁个方面改进，提出一种改进的萤火虫群优化算法求解该问题，并在8个节点的网络实例中进行测试，通过实验表明改进的萤火虫群算法的有效性。③采用一种改进的Salama算法生成规模较大的模拟测试网络，对本文提出的两种改进算法进行仿真测试，并与其它的智能算法进行比较，通过实验仿真表明本文提出的两种改进算法的优越性。
王军[10]2008年在《基于遗传算法的QoS组播路由算法优化研究》文中研究说明视频广播、IPTV等应用的出现,使得传统的Internet所提供的“尽力而为”的服务已经无法满足新应用在QoS方面的要求,因此,近年来业界广泛地将研究的关注点放在了组播应用环境下如何确保用户的服务质量(QoS)这个难题上。QoS组播路由算法已经被证明是一个NPC问题,从而使得其成为组播进一步应用的症结。基于启发式算法的路由方法随着网络节点以及链路数量的增加,计算时间代价会急剧增加而且在处理多约束的条件下显得无能为力。遗传算法的诸多特点为QoS组播路由计算带来了新的动力,然而由于“早熟收敛”现象以及适应度函数设定等方面的原因造成收敛到最优解概率较低以及速度较慢的问题。针对上述传统遗传算法的不足,本文的主要研究工作如下:1.预防“早熟收敛”现象改进算法,主要是针对造成“早熟收敛”现象的“超级个体”和固定交叉、变异概率两方面原因进行改进,选择机制优化在出现“超级个体”时通过对种群进行对数化处理来提高低适应度个体被选择的几率,从而预防“超级个体”对种群进化的消极影响。自适应交叉、变异操作改进则通过侦测种群进化的情况来动态调整交叉、变异概率,从而在机制上预防了种群过早收敛。此改进算法提高了整体进化收敛到最优组播路由的概率。2.适应度函数改进方面,原适应度函数公式f(P)=(Afb+Bfd+Cfdj+Dfpl)/Efc虽明确了适应度值与四大QoS约束参数以及网络代价之间的关系,但并不能保证满足QoS约束是搜索最优组播路由的前提。改进后的适应度函数表达式f(P)=(Afb*Bfd*Cfdj*Dfpl)-Efc,不但明确了满足QoS约束是前提的地位,避免了产生不合理解的情况,更是提高了选择压,从而加快了种群进化的速度。3.初始群体生成预处理方面,通过对传统遗传算法的分析,初始群体中是否包含有符合QoS约束的组播路径个体直接影响到最优路径算法的收敛性。预处理改进算法就能够通过对初始群体进行侦测,若包含有有效路径则进入选择、交叉和变异操作,反之,则需重新进行初始群体生成操作。此改进能够有效降低收敛到最优解所需的平均代数。4.在上述叁方面改进的基础上,本文提出了一种新的基于优化遗传算法的QoS组播路由算法,并从遗传算法设计基本步骤、编码表示、适应度函数设定、初始群体生成、选择算子设计、交叉算子设计、变异算子设计、遗传参数自适应优化以及终止条件设计等九个环节详细阐述了算法的实现方法。本文提出的优化算法均经过仿真验证。本文通过在预防“早熟收敛”现象改进算法、适应度函数改进以及初始群体生成预处理叁方面的改进切实地提高了进化过程的动态性,促使算法能够收敛到质量更高的解,提升了算法的性能。
参考文献：
[1]. 群智能优化算法在QoS组播路由中的应用研究[D]. 张志成. 兰州大学. 2013
[2]. 遗传算法在QoS组播路由算法中的应用[D]. 张洁. 浙江工业大学. 2003
[3]. 基于遗传算法的QoS组播路由[D]. 王宇. 四川大学. 2003
[4]. 基于遗传算法的无线Ad Hoc网络QoS组播路由研究[D]. 卢婷. 上海交通大学. 2013
[5]. IP QoS中主动队列管理和组播路由算法研究[D]. 徐佳. 扬州大学. 2006
[6]. 基于遗传算法的优化QoS组播路由算法[J]. 陈艳, 李志远, 马莉. 桂林航天工业学院学报. 2016
[7]. 基于QoS的组播路由关键技术研究[D]. 姜圳. 哈尔滨理工大学. 2004
[8]. 动态克隆选择算法在QoS组播路由中的应用研究[D]. 刘宇浩. 太原理工大学. 2011
[9]. 智能算法在多约束QoS组播路由问题中的应用研究[D]. 赵雄蛟. 重庆大学. 2013
[10]. 基于遗传算法的QoS组播路由算法优化研究[D]. 王军. 上海交通大学. 2008
标签：自动化技术论文; 遗传算法论文; 路由算法论文; qos论文; 网络优化论文; 路由论文; 仿真软件论文; 组播论文; 算法论文; ip组播论文; qos参数论文;