多种群遗传蚁群融合的多Qos约束组播路由算法

刘宏英，高太平

（1.山西大同大学数学与计算机科学学院，山西大同 037009；2.山西大学计算机科学与信息技术学院，山西太原 030006；3.山西大学省部共建教育部重点实验室，山西太原 030006）

多种群遗传蚁群融合的多Qos约束组播路由算法

刘宏英1，高太平2，3

（1.山西大同大学数学与计算机科学学院，山西大同 037009；2.山西大学计算机科学与信息技术学院，山西太原 030006；3.山西大学省部共建教育部重点实验室，山西太原 030006）

具有多约束的Qos（quality of service）路由问题是一个NP完备问题，传统方法很难求得全局最优解。针对多约束Qos组播路由问题，选择带宽、时延和时延抖动为Qos参数，由多种群遗传算法产生初始状态，利用蚁群算法的全局寻优能力提出一种将多种群遗传算法和蚁群算法融合的新算法。分析表明，该算法是可行、有效的。

蚁群算法；多种群遗传算法；服务质量；路由算法

近年来，随着网络技术的飞速发展，网络用户对网络的服务质量提出了许多新的要求。传统Internet路由协议只提供尽力服务，不提供服务质量（Qos）保证。为了支持更大范围的Qos需求，路由协议需要一个更复杂的模型，该模型将采用多个特征值（如带宽、延迟、延迟抖动、包丢失率等）来描述。Qos多播路由的基本问题是指在分布的网络中寻找最优路径，要求在源和目的节点之间，找到一条能同时满足多个约束条件且具有最小代价的路径。这是一个NP-完全问题。学者们已经提出一些启发式算法，如遗传算法、神经网络和蚂蚁算法等来寻找最优或近似解。这些算法都有各自的优缺点。本文综合基本蚁群算法和多种群遗传算法的优点，先采用多种群遗传算法生成从源节点到目的节点的较优路径，然后根据这些较优路径生成各路径上的信息素分布，最后在此基础上利用蚁群算法求出全局最优解［1-4］。

1 网络模型

在研究路由问题时，一个网络可表示成一个加权图G（N，E），其中N表示节点集，E表示连接节点的通信链路集。分别表示该网络中的节点数和链路数。为不失一般性，只考虑网络中一对节点之间最多只有一条链路的情况。

为了描述方便，引入以下记号，设Φd（Z）是延迟度量的惩罚函数，当该路由满足延迟约束时（delay（PT（s，t）≤Dt），值为l；否则等于rd（0＜rd＜1）。同理，Φdj（Z）是延迟抖动度量和包丢失率度量的惩罚函数，当路由满足延迟抖动约束（delay_jitter（PT（s，Mt）≤DJt），值为l，否则为rdj（0＜rdj＜1）；Φpl（Z）是包丢失率度量的惩罚函数，当路由满足包丢失率约束时，值为l，否则等于rpl（0＜rpl＜1）。rd，rdj，rpl的值大小决定惩罚的程度。

其中，A，B，C分别为fd，fdj，fpl的加权系数，分别表示延迟、延迟抖动和包丢失率在目标函数中所占的比重，其值取决于客户的需求，由系统根据具体应用设定。

Qos限制在多种群遗传-蚁群融合的多Qos约束路由算法中的多种群遗传部分中是在计算个体适应值时引入的，而在蚁群算法部分中是在全局信息素更新的时候引入，即用搜索所得路径是否满足限制条件来确定惩罚因子的数值来调整目标函数值。在m只蚂蚁完成一次寻径后，计算它们的目标函数，该函数如式（1）。

2 多种群遗传-蚁群融合的多Qos约束路由算法

2.1 多种遗传算法在本算法中的关键部分［5-6］

1）编码方式 采用基于路径的编码方式进行构造，它由一系列的自然数组成。该方式使遗传算法的交叉与变异操作只需对节点序列进行简单的编码与解码过程。染色体的第一个位置是源节点，中间是这条可行路径经过的节点序列，最后位置是目的节点。染色体的长度是变化的，但不能超过总的节点数目，否则说明在链路中有环路。

2）初始种群生成 本文按随机深度优先搜索方法，搜索到一定数量的路径，作为初始群体。随机深度优先搜索方法的具体实现：一般的深度优先搜索方法是，根据邻接表按深度优先搜索，找出一条从源节点到目的节点的路径。显然，只要邻接表不变，则每次搜索的路径是相同的。因此，当每搜索完一条路径后，随机地打乱同一节点下多个邻接点之间的顺序后，再按一般的深度优先搜索方法就能搜索到随机路径。对于上述方法得到的某些个体中的链路并非实际存在，这并无大碍。因为图中实际不存在的链路也可认为是一个四元组（D，J，B，C）只不过D，J和C被置为一个足够大的值，而B的值为0。因此，包含有这种链路的个体其适应度很小，很快就会被淘汰，不会影响最后的结果。

3）适应度函数 在遗传算法中，适应度函数是用来判断个体好坏的标准，它将直接反映个体的性能，本算法中个体是一棵覆盖源节点和目的节点的子树，在综合考虑费用、带宽、时延、时延抖动和包丢失率的基础上得到如式（1）的适应度函数。

4）选择操作，交叉操作，变异操作 采用轮盘赌选择方法从初始群体中选择Pop_num*Pop_size个个体构成新种群。首先从群体中随机选择两个个体，找出两个父代个体中相同的基因位，即两者的相同节点；然后从这些相同节点中随机选取其中的一个基因位作为交叉点进行两个父代的交叉。（1）从群体中随机选择一个个体Pi，然后从个体的所有基因位中随机选择两个基因节点a和b（a的位置在前，b的位置在后）；（2）以a为起始节点，b为目的节点，利用建立初始种群时的随机深度优先搜索方法找到一条新的从a到b随机路径link；（3）用link替换a和b之间的部分路径。

多种群遗传算法的描述：

输入：图G=（V，E），R=（B，Dt，DJt，PLt），源节点为s，目的节点集M∈｛V-｛s｝｝，种群个数Pop_num，交叉概率Pc，变异概率Pm，最大进化代数maxgen，适应度函数的参数A，B，C，rd，rdj，rpl。

输出：满足约束条件的最优路径

随机产生Pop_num个初始种群；

for（i=1；i＜=Pop_num；i++）

//对每个初始种群进行操作

计算种群中个体的适应值；

for（ge_cnt=0；gen_cnt＜maxgen；ge_cnt++）

//maxgen为一个进行周期内的最大进化代数

SelectionOperation //对个体进行选择操作

Crossover Operation //对个体进行交叉操作

Mutation Operation //对个体进行变异操作

计算种群中染色体的适应值；

保留种群中的最优个体；

end for

end for

2.2 蚁群算法在本算法中的关键部分

在蚁群算法中，每个蚂蚁根据状态转移规则来选择下一跳节点，而信息素值依据全局更新和局部更新两种规则来进行更新。下面介绍这三种规则：

2.2.1 状态选择规则

第i只蚂蚁在节点r，依据下述规则来选择下一节点s：

否则，t时刻蚂蚁i由节点r转移到节点s的转移概率：

2.2.2 信息素的局部更新规则

当蚂蚁i经过路径（r，s）且r，s是该蚂蚁所选路径上的两个相邻节点时，则路径上的信息素按如下公式进行调整，否则不调整。

其中ρ表示信息素的挥发程度，在（0，1）范围内取值，cons为常数。

2.2.3 信息素的全局更新规则

当蚂蚁i成功完成一次寻径后，即由起点到达终点后返回时，按如下公式对所有经过的路径进行全局信息素更新：

并对其它链路上的信息素强度按如下公式更新：

其中，ρ是信息素的消逝因子ρ0＜ρ＜1，Lk是目标函数。

2.2.4 信息素的初始化

各个种群最优个体对应的路径可以为实施蚁群搜索提供非常有指导价值的信息，据此设置初始信息素将会大大缩短蚁群开始时完全随机的等概率搜寻过程，初始信息素的设置如下：

其中，LKB为第k个种群的最优个体所对应路径的总费用，Q为常数。

蚁群算法的描述：

Initialize_Phermone_Trail；//设置初始信息素for（s_cnt=0；s_cnt＜s_NUM；s_cnt++）//s_NUM为蚁群搜索周期的循环数目

for（k=l；k＜=m；k++）//为蚂蚁数目

初始化蚂蚁搜索禁忌表；

While（存在不属于搜索禁忌表的节点）

第k只蚂蚁依式（2）选择下一节点；否则，依据式（3）随机选择下一节点，修改搜索禁忌表并根据式（4）进行局部信息素的更新；

end while

当蚂蚁k完成一次路径的搜索后，应用全局更新规则式（5）和式（6）修改当前最优路径和其它路径中各个支路上的信息素；

end for

end for

输出最小代价路径；

2.3 多种群遗传蚁群融合的多Qos约束组播路由算法

多种群遗传蚁群融合的多Qos约束组播路由算法的描述如下：

步骤1 初始化参数设定遗传参数种群数目pop_NUM、各种群规模pop_SIZE、交叉概率pc、变异概率pm；假定网络中有m只蚂蚁，一个蚁群搜索周期内的循环数目N1；给出网络节点数n，各个节点的（d，dj，pl，c）取值，以及每条存在边的（d，dj，b，c）取值；给出约束条件的（D，DJ，B，PL）的值；

步骤2 精简网络精简网络拓扑结构中不符合Qos约束要求的链路或节点（除去不满足带宽约束的链路），把网络滤成一个新的简单网络，如果源点和终点位于同一连通分支，就将此连通分支作为算法研究的基图；

步骤3 随机产生pop_NUM个种群，每个种群包含pop_SIZE个个体；

步骤4 各个种群完成各自的遗传操作，生成若干优化解；

步骤5 根据多种群遗传算法中生成的若干优化解生成蚂蚁算法中的信息初始分布，放出m只蚂蚁从源节点s出发；

步骤6 每只蚂蚁根据已有信息素分布和状态转移规则来选择各自的路径。当某只蚂蚁成功的完成路由选择后，该蚂蚁所选路由各路径上的信息素根据局部更新规则进行更新；

步骤7 对所有蚂蚁重复步骤6，直到所有蚂蚁完成步骤6；

步骤8 选择建立了最小费用并满足Qos限制的路由的蚂蚁，然后使用全局更新规则对该蚂蚁所选的路由的各路径上的信息素进行更新；

步骤9 重复步骤6到步骤8，直到获得满意的结果；

步骤10 输出最好解。

2.4 算法复杂度分析

设n为网络的规模，m为多种群遗传-蚁群融合的多Qos约束路由算法所采用的蚂蚁数目，最大循环次数为N1，s为多种群遗传算法中种群规模，为种群个数，p为染色体编码长度，l最大循环次数为N2，则针对前面给出的多种群遗传-蚁群融合的多Qos约束路由算法的描述，可逐步分析时间复杂度，如表1所示。

多种群遗传-蚁群算法中m只蚂蚁要遍历n个结点，经过N1次循环，p个规模为s的种群经过N2次循环，则整个计算过程的时间复杂度为：T（n）=ο（N1·n·2m+N2·ps2）。由于当网络规模很大，网结点要远大于其它参数，如取常数的循环次数N1和N2以及种群个数和种群规模；取蚂蚁个数为网络节点数时，本算法的时间复杂度可以近似为O（n3）。

3 结束语

本文描述了适应于研究Qos组播路由的网络模型，提出了一种基于多种群遗传蚁群融合的多Qos约束组播路由算法。该算法结合了遗传算法和蚁群算法的优点，避免了这两种算法单独使用时的弊端。通过分析可知该算法是有效、可行的。

表1 多种群遗传-蚁群融合的多Qos约束组播路由算法时间复杂度分析

［1］王征应，石冰心.基于启发式遗传算法的Qos组播路由问题求解［J］.计算机学报.2001，24（1）：55-61.

［2］杨云，徐佳，高飞，等.基于蚁群系统的Qos约束组播路由算法［J］.小型微型计算机系统，2006，27（11）：2030-2035.

［3］孙宝林，李腊元.一种基于遗传算法的多约束Qos多播路由优化算法［J］.计算机工程与应用，2003，39（30）：1-3.

［4］Rouskas G N，Baldine I.Multicast routing with end-to-end delay and delay variation constraints［J］.IEEE Journal on Selected Areas in Communication，1997，15（3）：346-356.

［5］李腊元，李春林.多Qos约束的多播路由协议［J］.软件学报，2004，15（2）：286-291.

［6］张素兵，刘泽民.基于蚂蚁算法的时延受限分布式多播路由研究［J］.通信学报，2001，22（3）：70-74.

〔编辑 高海〕

Qos Routing based on Multi-num Colony-Genetic Algorithm

LIU Hong-ying1，GAO Tai-ping2，3
（1.School of Mathematics and Computer Science，Shanxi Datong University，Datong Shanxi，037009；2.School of Computer and Information Technology，Shanxi University，Taiyuan Shanxi，030006；3.Key Laboratory of Ministry of Education for Computation Intelligence＆Chinese Information Processing，Taiyuan Shanxi，030006）

The Qos routing problem with multi-constrains belongs to NP-complete problem.It's hard to get the global solution using the traditional algorithm.This paper proposes a new algorithm based on the ant colony algorithm and multi-swarm Genetic algorithm.Algorithm analysis shows that the algorithm is feasible and effective.

ant colony algorithm；multi-swarm genetic algorithm；quality of service；routing algorithm

TP309

A

1674-0874（2011）02-0001-04

2010-12-28

国家自然科学基金资助项目［60803034］

刘宏英（1977-），女，山西大同人，硕士，讲师，研究方向：网络优化。