基于遗传模拟退火算法的多约束QoS组播路由算法①

刘金明， 仲光苹

(1.黑龙江八一农垦大学信息技术学院，黑龙江 大庆 163319;2.东北石油大学数学科学与技术学院，黑龙江 大庆 163318)

0 引言

多约束QoS组播路由问题实际上就是带多个QoS约束的Steiner树问题，是典型的NP完全问题[1]，存在大量基于蚁群算法、遗传算法等智能搜索算法的求解方法，其中应用最多的就是遗传算法及其改进算法.文献[2]中Xiang等提出了基于遗传算法来求解QoS路由问题，其算法采用的二进制编码方法，导致其搜索空间会随着网络规模的增大而急剧增大.文献[3]中Wang等提出基于遗传算法求解带宽和时延约束费用最小组播路由问题，其算法采用树型结构编码策略，算法的性能较好，但树形编码却带来了非常复杂的交叉和变异操作.文献[4]中Hamdan等针对时延和时延抖动约束的费用最小组播路由问题，提出了基于整数队列编码策略的遗传算法求解方法，算法的编码方式非常简单，且效率较高.文献[5]中刘金明等提出了基于遗传模拟退火算法求解组播路由问题的相关方法，但是只涉及了带宽和时延两个QoS约束条件.文献[6]中，张琨等提出了基于模拟退火方法的多约束QoS组播路由算法，算法求得的组播路由树的费用性能较好，但由于模拟退火算法自身的不足，导致算法的效率比较低.本文在前人研究基础上，提出基于遗传模拟退火算法的多约束QoS组播路由算法，该组播路由算法采用基于备选路径集策略的整数队列编码方法，结合模拟退火算法温度参数设计适应度函数，并引入启发式交叉操作策略和自适应的交叉变异概率思想，即解决了遗传算法容易陷入过早的收敛和进化后期搜索效率低的问题，又克服了模拟退火算法自身进化速度慢的缺陷.实验仿真表明，本文提出的算法求得的组播路由树具有良好的费用性能，且收敛速度很快.

1 QoS组播路由问题描述

组播网络可用无向带权连通图G=(V，E)来表示，其中V为节点集，E为链路集，R+和R+分别表示正实数集和非负实数集.对于任意链路e∈E，可定义3种度量，分别为:费用函数C(e):E→R+，带宽函数B(e):E→R+和时延函数D(e):E→R+;对于任意网络节点n∈V，可定义3种度量，分别为费用函数C(n):E→R+，时延函数D(n):E→R+和包丢失率函数PL(n):V→R+.在组播网络中，给定源节点s∈V，目的节点集合M⊆{V－{s}}，∀di，dj∈M，则s和M组成的组播路由树T(s，M)将存在下列关系:

式中，PT(s，di)为组播路由树T(s，M)上从给定源节点s到任意目的节点di的一条路由路径，DJ(s，M)为组播路由树T(s，M)中的最大时延抖动值.

在组播网络G=(V，E)中，给定源节点s∈V，目的节点集合M⊆{V－{S}}，∀di∈M，设定带宽函数B(·)∈R+，时延函数D(·)∈R+，时延抖动函数DJ(·)∈R+，包丢失率函数PL(·)∈ R+，费用函数C(·)∈R+，则多约束QoS组播路由算法求得的组播路由树T(s，M)必须满足如下条件:

(1)带宽约束:B(PT(s，di))≥Bi;

(2)时延约束:D(PT(s，di))≤Di;

(3)时延抖动约束:DJ(s，M)＜DJ;

(4)包丢失率约束:PL(PT(s，di))≤PLi;

(5)费用约束:在所有满足上述(1)～(4)条件的组播路由树中，使C(T(s，M))最小.

其中，Bi，Di和PLi分别对应着目的节点 di的带宽、时延和包丢失率约束，而DJ是整个组播路由树的时延抖动约束.

2 多约束QoS组播路由算法

2.1 编码及种群初始化

在组播网络中，给定源节点s和目的节点集合M，基于备选路径集的整数队列编码方法就是将染色体编码成长度为m=|M|的整数队列，每一个队列就是染色体的一个基因，也就是从源节点到特定目的节点满足一定约束条件的路由路径.本文采用的具体编码方案如下:

首先，对所有的目的节点di∈M，计算其备选路径集.目的节点di备选路径集的生成方法为:先对网络使用带宽约束Bi进行简化，再使用Dijkstra第k最短路径算法找到从给定源节点s到特定目的节点di所有满足时延约束Di和包丢失率约束PLi的路由路径.设Qi为特定目的节点di的备选路径集，则

然后，从所有的目的节点对应的路径集中都任选一条路由路径作为染色体的基因，组成一棵基因个数为m的组播路由树，作为初始种群的一个染色体.

按照上述方法生成一定数量的染色体构成初始种群，完成种群初始化.

2.2 适应度函数设计

适应度函数决定了遗传算法的搜索方向，直接影响遗传算法的执行时间和求解效率.多约束QoS组播路由问题实际上是带多个约束的费用最小化问题.由于遗传算法的编码过程中已经去除了带宽、时延和包丢失率约束，因此目标函数可以直接表示为

其中，Φ(Z)为惩罚函数，r为惩罚因子，当组播路由树满足时延抖动约束时，其值为0;否则等于r(r为比较大的正实数).

结合模拟退火算法的温度参数，可以将遗传算法的适应度函数定义为

式中:fmin为当前代种群中最小目标函数值，t为当前代温度值.

此适应度函数可以使算法在进行赌轮选择时具有两点好处:一是在温度高时(组播路由算法运行早期)，可有效避免个别适应度高的染色体充斥整个种群造成早熟;二是在温度低时(组播路由算法运行后期)，优良染色体具有相对更大的适应度函数值，使其能够更容易遗传给下一代，加快算法的搜索速度.

结合了温度参数的新型适应度函数的使用，可以有效解决传统遗传算法自身存在的容易陷入过早收敛和进化后期搜索效率低的问题.

2.3 遗传参数设计

2.3.1 选择操作

选择操作采用最常用的赌轮选择的方法，同时为保证算法能够收敛到全局最优解，在进行选择操作前先使用最优保留策略将当前种群中的最优解直接复制给下一代种群.

2.3.2 交叉和变异操作

交叉概率Pc和变异概率Pm是遗传算法设计过程中影响其搜索行为和求解性能的关键，直接决定了算法的收敛性能.本文采用自适应的交叉和变异概率计算方法，其计算公式如下:

式中，k1，k2，k3，k4，k5，k6都是常数，且 k3=k1+k2，k6=k4+k5;fitmax是当前代种群中的最大适应度函数值，fitavg是当前代种群的平均适应度函数值;fiti'是两个要进行交叉操作的染色体中较大的适应度函数值，fiti是要进行变异操作的染色体的适应度函数值.

采用此交叉和变异概率计算方法，适应度函数值较小的染色体计算出的交叉和变异概率都比较大，能够加快遗传算法的搜索速度.当前代最优染色体的交叉和变异概率是一个较小值，能够使最优染色体参与到生成下一代个体的交叉和变异操作中，进一步加快算法的搜索速度.当fitavg→fitmax使算法陷入问题求解的局部最优时，适应度函数值较大的染色体计算出的交叉和变异概率也将增大，能够有效提高算法跳出局部最优的能力，有效避免“早熟”.但为了防止原有解空间被完全破坏，当|fitmax－fitavg＜ ε时，就固定Pc，Pm值.

算法的交叉操作采用相同链路保留的策略.其交叉策略为:按赌轮方法选择出两个父代染色体TM和TN，计算其交叉概率Pc，按概率Pc进行交叉操作生成新的染色体Tc.两个父代染色体中相同的路由路径(优良基因)将直接遗传给后代染色体，对于路由路径不同的目的节点，以di为例，计算两个父代染色体中目的节点di对应的路由路径PM(s，di)和PN(s，di)的路径费用，将路径费用小的路由路径(优良基因)作为组成子代染色体从源节点s到目的节点di的基因.对两个父代染色体TM和TN中所有具有不同路由路径的目的节点，按上述操作生成子代染色体的基因，完成交叉操作生成一个子代染色体.

算法的变异操作采用位变异的方法.位变异的方法是:任意选取染色体中某个目的节点di对应的路由路径(基因)，从其对应的备选路径集Qi中随机选择一条路由路径作为基因进行替换.

2.4 模拟退火参数设计

2.4.1 初温确定和退温操作

初始温度的设定采用t0=Kδ的形式，其中K是一个足够大的数，且δ=是初始种群的最大和最小目标函数值.退温操作采用tn+1=αt的形式，其中0＜α＜1.

2.4.2 构造邻域解

邻域解的构造方法采用与变异操作类似的“路径交换策略”.

图1 算法收敛性能的分析

图2 算法费用性能的分析

2.4.3 设置状态接受函数

模拟退火算法的初始种群由遗传算法提供，组播路由算法运行一轮次后生成的种群，再经过一系列的遗传操作后，将生成新的种群，这个新的种群就是组播路由算法运行每一轮次中模拟退火算法的初始种群.对该初始种群进行基于Metropolis判别准则的选择复制后，将生成下一代种群，这个种群就组播路由算法运行一轮次后生成的新一代种群.假设为染色体i构造了一个邻域染色体j，i和j将基于Metropolis判别准则竞争进入下一代种群.Metropolis判别准则为:令Δf=fit(Ti)－fit(Tj)，若Δf≤0，则新染色体j将被复制到下一代种群中;若Δf＞0，则生成一个随机数 r∈[0，1]，当 r＜exp(－Δf/tn)时，新染色体j仍将被复制到下一代种群中;否则，把染色体i复制到下一代种群中.

通过在Metropolis判别准则中引入温度参数，使算法在高温时接受劣质解的能力比较强，保证了种群的多样性，避免“早熟”.而当温度下降时，使优良染色体更容易遗传给下一代，加快算法的收敛速度.

2.5 算法的终止准则

2.5.1 内部循环终止准则

内部循环终止准则是算法由模拟退火部分向遗传算法部分切换的条件，也称为Metropolis抽样稳定准则.本文采用基于不改变规则的控制法，在算法的模拟退火部分求解过程中，若求得的最优解连续若干代进化过程中保持不变，则认为满足了内部循环终止条件，进行退温操作，并切换到遗传算法部分进行遗传操作.

2.5.2 外部循环终止准则

外部循环终止准则是整个组播路由算法的终止准则.本文采用循环总数控制法和基于不改变规则的控制法相结合的方法.即当算法达到外部循环总次数时，认为达到了外部循环终止条件;或者算法还没有达到设定的循环总次数，但在一定迭代次数内没有改变当前最优解时，也认为达到了外部循环终止条件.

3 仿真实验

本文在VC++6.0编程环境下对提出的算法进行了仿真.在仿真实验中，为了仿真方便，将QoS组播路由问题进行简化，只考虑链路的时延和费用两个度量属性，链路的带宽，节点的费用、时延、包丢失率度量属性都被忽略掉了，相应的QoS约束条件也进行了简化，只保留时延和时延抖动两个约束条件.由本文的编码方案可知，采用简化后的度量属性和约束条件不会影响算法仿真的准确性.

通过仿真实验，主要对提出的多约束QoS组播路由算法的两点性能进行分析:一是对算法的收敛性能进行分析;二是对算法求得的组播路由树的费用性能进行分析.

在仿真实验中，将文献[4]中提出的基于遗传算法的时延及时延抖动约束组播路由算法，文献[6]中提出的基于模拟退火算法的多约束QoS组播路由算法与本文提出的算法在性能和效率上进行了比较.因为上述三个算法所采用的策略不同，所以本文使用CPU执行时间来对算法的收敛性能进行分析测试.

图1展示了本文算法与文献[4]算法、文献[6]算法在执行时间上的比较结果.而图2则展示了在不同网络节点数情况下，本文算法与文献[4]算法、文献[6]算法在计算出的组播路由树费用性能上的比较结果.从图1和图2不难看出，本文提出的基于遗传模拟退火算法的多约束QoS路由算法在计算性能和求解效率上具有明显的优势.

4 结论

本文针对多约束QoS组播路由问题求解的复杂性，提出了一种新型全局智能优化算法——遗传模拟退火算法，并提出了基于遗传模拟退火算法的多约束QoS组播路由算法.该算法通过采用基于备选路径集的整数队列路径编码方案来简化编解码操作，结合温度参数来设计适应度函数，即避免了早熟，又加快了进化后期的搜索能力，引入启发式交叉操作和自适应的交叉变异概率思想提高算法的计算效率，通过Metropolis判别准则来保证算法的全局收敛性.通过仿真实验证明，该算法具有收敛速度快，稳定性强，费用性能良好的特点，能够满足当前多媒体网络在QoS方面的各种需求.

[1]Stefan Vob.Steiner’s Problem in Graphs:Heuristic Methods[J].Discrete Applied Mathematics，1992，40(1):45 －72.

[2]F.Xiang，L.Junzhou，W.Jieyi，et al.QoS Routing Based on Genetic Algorithm[J].Computer Communications，1999，22(15):1394－1399.

[3]Wang Zhengying，Shi Bingxin，Zhao Erdun.Bandwidth－ delay－constrained Least Cost Multicast Routing Based on Heuristic Genetic Algorithm[J].Computer Communications，2001，24(7):685－692.

[4]M.Hamdan，M.E.El－ Hawary.Multicast Routing with Delay and Delay Variation Constraints Using Genetic Algorithm[J].Proceedings of the Canadian Conference on Electrical and Computer Engineering，2004，4:2363 －2366.

[5]刘金明，王娜，刘勇.基于遗传模拟退火算法的QoS组播路由问题求解[J].佳木斯大学学报(自然科学版)，2008，26(4):535－538.

[6]张琨，王珩，刘玉风.一种基于模拟退火方法的多约束QoS组播路由算法[J].计算机科学，2005，32(5):41 －45.