基于遗传算法的多约束QoS单播路由算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于遗传算法的多约束QoS单播路由算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

【摘 要】针对QoS路由问题，设计了一种基于改进遗传算法的多约束qos单播路由算法。本算法的编码方法是节点路径序号编码，缩小编码空间的同时避免了编码空间与解空间的转换，提高了算法执行效率；计算适值函数时根据延时、丢包率和延时抖动约束引入一种新的惩罚机制，加快了淘汰速度，更好地保证了“优胜劣淘”的思想；在变异操作中采用“最佳路径替换”的思想，消除了不存在链路或避免产生循环链路，提高了收敛性。通过与传统遗传算法对比，实验结果证明本算法可行且具有更好的有效性和收敛性。

【关键词】单播 路由算法 服务质量 遗传算法 收敛性 惩罚机制

[Abstract] According to QoS routing problem， a multi-constraint QoS unicast routing algorithm based on an improved genetic algorithm was proposed in this paper. In the proposed algorithm， path number coding is used to improve algorithm efficiency， which reduces coding space and avoids the switch between decoding space and coding space. A new punishment mechanism is introduced to compute fitness function according to delay， packet loss ratio and delay jitter constraints， which speeds up the elimination rate and guarantees“survival of the fittest”. In addition， “best path substitution”is adopted in mutation process， which eliminates the blank path or cycle path to enhance convergence. Simulation results demonstrate that， compared with traditional generic algorithm， the proposed algorithm is feasible with better effectiveness and convergence.

[Key words]unicast routing algorithm quality of service （QoS） genetic algorithm （GA） convergence punishment mechanism

1 引言

目前，互联网的本质是一种无连接的网络[1-2]，传统的网络只提供一种尽力而为的服务。然而，一方面随着网络的急剧发展，人们对网络传输容量、质量、实时性的要求越来越高，传统的网络已经不能满足用户的需求；另一方面，网络带宽资源日益趋紧，目前的网络很难同时满足多种应用要求，尤其是数据传输容量与实时性的要求。如此有限的网络带宽资源如何适当地被网络系统使用，确保得到最大数据传输量的同时不以丢失传输速率为代价成了一项重要的任务。

为了解决上述问题，QoS机制[3-4]应运而生。它旨在保证服务质量，在网络多媒体等方面有着广泛的应用。该机制主要涉及多约束路由选择问题，而该问题为NP-完备问题[5]，这种问题难以用传统的算法解决。GA（Genetic Algorithm，遗传算法）[6]是一种模仿自然选择的过程（优胜劣淘、适者生存）和遗传的机理（交叉和变异）来寻找最优解的启发式搜索，它具有收敛性好、鲁棒性强、潜在并行性等特点，使得节点QoS路由选择问题简单、有效。

对于QoS路由问题，文献[7]针对多点投递和单点投递情况提出一种基于遗传算法的QoS路由选择策略，但是该算法采用一种二进制编码方案，需要对解空间和编码空间进行转换，增加了算法的复杂度，而且伴随着网络节点增多，解空间迅速增大，这也增加了搜索空间，使得算法效率急剧降低。文献[8]提出一种基于带宽时延约束的QoS单播路由算法，但是只考虑一种单一的QoS参数即时延。文献[9]提出一种带约束的多目标服务质量路由算法，通过对QoS参数的限制条件进行阐述，找到了一条满足QoS的路由，但是该算法通过适应度函数计算适值，同时约束了带宽和丢包率，把时延和代价同时作为目标函数，且没有经过预处理，这不仅使得计算过程过于复杂，而且还增加了算法运行时间。文献[10]提出一种单播多约束的遗传算法，但是算法的交叉和变异操作由于没有经过修复，容易产生无效路径即不存在解。

针对以上问题，本文提出一种基于改进遗传算法满足多约束QoS单播路由的算法，在满足带宽、时延、丢包率和延时抖动的约束条件下，寻找出一条花费最小的路径。该算法具有较好的收敛速度，并且通过实验证明得到的解（最优路径）是全局最优的，较好地提高了QoS满意率。

2 网络模型与问题描述

网络模型定义为图G（N，E）。用N={n1，n2，...，nn}表示节点集合，用E表示链路集合，每条链路记作（u，v）∈E，包含参数：网络链路带宽B（u，v）、链路时延d（u，v）、链路费用c（u，v）、丢包率l（u，v）、延时抖动j（u，v），给定源节点s和目的节点d，网络带宽约束Band、时延约束Delay、丢包率约束Loss、延时抖动约束Jitter。多约束QoS单播路由就是寻找满足给定约束的从源节点到目的节点代价最小的路径。对于从源节点s到目的节点d的路径记作P（s，d）（由多条链路（u，v）组成），则问题可转化为以下优化问题：

3 基于改进遗传算法的QoS路由算法

3.1 编码

本算法采用一种可以直接被用于遗传操作的编码方案，即路径序号编码，它对于网络节点以数字顺序编号，按照路径中节点出现的顺序，依次记录节点编号作为群体中的一条染色体。该算法直接用解空间作为编码空间，无需进行编码空间转换，简化了算法操作步骤，节省了运行时间，提高了运行效率。

3.2 初始种群

在种群初始化时，加入一个预处理环节，对给定网络拓扑结构进行遍历，把链路带宽与给定限制带宽对比，将小于给定约束的链路作为不可达链路，同时从拓扑结构中去除这段链路，获得一个新的拓扑结构图，经过筛选的拓扑图可能不是连通的。如果得到的拓扑图是非连通的，且源节点和目的节点不在同一连通子图里，则无法提供服务。假设筛选后得到的满足带宽约束的网络拓扑结构是连通的，那么以下研究将不再考虑带宽约束条件。带宽约束筛选的过程，通过保留符合带宽限制的路径，不仅减少QoS参数中带宽这一限制条件，大大方便了算法设计，而且对原有的网络空间进行缩减，减少编码空间，使算法性能得到了进一步优化。

采用随机深度优先搜索算法进行种群初始化，该算法的基本思想是：以源节点为起始节点，随机选择1个邻接节点作为下一节点，连接这2个节点，判断下一节点是否为目的节点，如果不是则把下一节点作为起始节点重复上述操作，直至下一节点是目的节点，在重复上述操作的过程中要确保网络中的每个节点最多在路径中出现一次，这样才能保证得到的路径是无环且有效的[11-12]。通过完成上述操作将得到所有可能解集即初始种群，但是该种群是不满足约束条件的。

3.3 适应度函数计算

遗传算法通过对每一代个体评估来决定该个体是被抛弃还是遗传到下一代种群，而这个评估过程的实现是通过使用适值函数计算一个适应值来确定的。这样适应度函数的设计将直接影响到该遗传算法的收敛速度及是否会陷入局部最优解，设计的函数应能体现个体性能，满足多QoS约束且花费较小的个体性能好，则其对应的适应值应该大；反之，不满足约束或者花费较大的个体则适应值应该尽可能小。在自然选择过程中，适应度指的是生物对当前环境适应能力的大小，一般适应度高的其生存能力强，反之则容易被自然选择所淘汰，这就是常说的优胜劣淘机制。而遗传算法是对自然机制的模拟，同理适应度高的个体被选中的概率就大，反之则容易被淘汰。

Φ（Z）是定义的一个惩罚函数，用来度量QoS参数的满足程度。当在约束范围之内时，r值为1，否则值为r∈（0，1）。r是定义的一个惩罚因子，如果r选取太小，则会造成过重惩罚，使得那些适值小的个体直接被淘汰，永久不会被选择，这样将导致算法解陷入局部最优；如果选取太大，则惩罚太轻，起不到加快收敛的作用。因此，考虑到实际情况，根据违反的程度进行惩罚，即违反程度越大则惩罚力度就越大。r取值公式如下：

其中，constraint表示给定约束值，reality表示实际值（每条路径时延、延时抖动、丢包率的值）。

这是本文提出的一种新惩罚制度，通过加强对不满足约束条件个体的惩罚力度，加快优胜劣淘的速度，快速寻到最优解。

3.4 选择

选择算子的优劣是影响算法收敛性的直接因素，本遗传算法采用结合最佳个体保存法和赌轮法的选择算法，即首先选出N个精英（适应度最高）个体作为最佳个体（本算法中N取1），选中的个体将无需直接参与形成下代群体的交叉和变异操作，这就使得每代的最优解在进化的过程中不会被破坏。种群中余下的其他个体则使用赌轮法执行选择。

赌轮法是目前较常用的基本选择方法，该方法依据适值大小对种群个体进行排序，计算所有种群的适值总和，累计对当前种群以及排在前面种群进行求和，得到的结果作为当前种群的选择概率，概率由小变大，最后一个为1，随机产生[0，1]区间上的数，根据判断在上述哪个种群对应的适值区间则选择哪个种群，重复上述操作直至新种群规模达到初始规模。直观表示即：个体i的适应度为fi，则其被选中的概率为。其中，popsize表示当前参与选择的种群中规模，概率pi反映总个体适应度之和中个体i所占比例。根据文献[6]中的定理2.7（如果交叉概率和变异概率分别为[0，1]、（0，1），并保证当前最优解不被交叉和变异操作所破坏，则该算法必收敛于全局最优）可知，该遗传算法具有收敛到全局最优的性能。

3.5 交叉

现在常用的交叉方法之一就是单点交叉，本算法将其进行改进之后再使用，主要过程是：对于完成选择得到的染色体（种群个体），首先分别在其上面选择2个点，并判断这2个点是否是起始或者目的节点序号，如果是则重新选择，直到选中的节点非源和目的节点；然后确定交换位置（交叉点前或者交叉点后），本文选取交叉点之后；最后将2个染色体以1的概率互相替换交叉点之后的链路，得到2个新的染色体，即下一代个体（新源到目的节点的路径）。

3.6 变异

依据优胜劣淘的思想，通过上述适值计算、选择、交叉过程得到最优个体即最优解可能是局部最优而不是全局最优，这将导致“早熟”现象的产生。使用变异操作通过随机改变染色体中点（路径中节点序号）可以避免这种现象的产生，确保了种群的多样性。对于交叉完成得到的新子女个体以概率进行变异，若变异概率太大则会影响种群的真实性，若太小则不能达到目的，因此变异概率通常是0.1或者更小，这样可以使算法很快跳出局部最优解靠向全局最优解。变异方式如下：

（1）判断当前路径是否是无效路径（不存在链路或者循环链路）。

（2）如果是无效链路，则使用上述选择出直接进行遗传的“最佳路径”来替换这条无效路径。

本变异算法通过替换不仅避免了“早熟”现象，而且通过路径替换确保了路径的有效性，使得种群变得有效，提高了种群质量，从而加快了算法的收敛速度。