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

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

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

[Abstract] According to QoS routing problem， a multi-constraint QoS unicast routing a✡lgorithm 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 f ☹ittest”. 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 algori✍thm is feasible with better effectiveness and convergence.

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

1 引言

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

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

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

2 网络模型与问题描述

3.1 编码

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

3.2 初始种群

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

3.3 适应度函数计算

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

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

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

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

3.4 选择

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

3.5 交叉

3.6 变异

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

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

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

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