基于克隆选择的QoS组播路由优化

王 莘

（西安航空学院 电气学院，陕西 西安 710077）

基于克隆选择的QoS组播路由优化

王 莘

（西安航空学院 电气学院，陕西 西安 710077）

衡量QoS组播路由主要性能指标有延时，代价，带宽等，本文所提出的基于遗传算法的多约束QoS组播路由优化算法。引入了一个综合性能指标Q适应度函数，对延时、带宽、代价这3个性能指标进行权衡。以减小组播树的代价和延时，增大带宽，提高组播的服务质量。并对解决传统算法对于存在两组及以上的组播树，他们的代价都是最优的，延时和带宽都满足受限条件时无法选择的问题十分有效的。

组播路由；遗传算法；克隆选择；适应度函数

随着网络的发展和应用，催生了很多新的业务类型。这些新型业务中很多基于组播技术，要求网络能够提供相应的服务质量（Quality of Service, QoS）控制，以满足业务本身的特点和用户的不同需求，而传统的点对点技术无法提供服务质量的保证。QoS组播路由技术依据当前的网络状态和拓扑结构进行路由选择[1]，其目的是选择从源节点到各个接收数据的目的节点并满足QoS要求的路径，同时使得由各个路径组成的组播树开销最小。而求解具有多个约束条件时直接使用这种方法，就会更为困难。

遗传算法（Genetic Algorithm, GA）是一种可有效地解决组合优化等复杂问题的智能算法[2]，文中所使用的遗传算法引入了一个综合性能指标Q适应度函数，对延时、带宽、代价这3个性能指标进行权衡。减小组播树的延时和代价，增大带宽，提高服务质量[3]。并有效的解决了传统的算法对于存在两组及以上的组播树，他们的代价都是最优的，延时和带宽都满足受限条件时无法选择的问题。从而实现了更精确的求解和参数的自动化设置。

1 克隆选择

克隆选择是生物免疫系统的重要学说。其基本原理是通过细胞对抗原的识别，来选择并保留下来那些能过识别抗原的细胞，同时对这些细胞进行扩增，而那些不能识别抗原的细胞则不选择也不扩增。在成长的克隆中，免疫系统是自适应的，同时也呈现出一种变异机制，在对抗体特意编码的基因中产生极高频率的点变异[4]。这种机制与改进抗原一起所进行的选择具有极高的亲和力匹配。同时要能够识别所有的抗原，受控群体和指令系统要具有多样性。

2 优化QoS组播路由的克隆算法

2.1 算法概述

对QoS组播路由影响较大的是延时、带宽、代价是这3个性能指标，传统克隆算法在使组播树的代价最小时，总通过满足延时、约束带宽的方法实现的。可是在这种方式的算法下，导致组播树延时增大，带宽减小。以延时和带宽的性能下降为代价的网络优化就与现今网络的发展相矛盾，而整个树的整体性能往往不是最优的，并且往往会导致局部最优和不稳定，算法过于早熟。当网络中存在了两组或以上的组播树，它们的代价都是最优的，延时和带宽都满足受限条件，但是组播树的延时或带宽不同。这时传统算法只是满足延时、带宽约束的前提下是组播树的代价最小，而无法随机的选择一组组播树得到最优组播树。

这对这种情况，本文提出了基于改进克隆策略的整体优化主播路由算法。该算法在原克隆算法满足延时约束的条件基础上，引入了一个综合性能指标Q适应度函数，Q=B/(D×C)取代原克隆算法只以代价C作为适应度函数，对延时、带宽、代价这3个性能指标进行权衡。以减小组播树的代价和延时，增大带宽，提高组播的服务质量。并对解决传统算法对于存在两组及以上的组播树，他们的代价都是最优的[5]，延时和带宽都满足受限条件时无法选择的问题十分有效的。

同时该算法引进了基因优化操作，对二代抗体群p[t+1]基因优化操作。即对个体内部的所有源节点到目的节点所选择的的路径进行亲和度计算，每组源节点和目的节点只保留一个最有路径，这样大大提高了收敛速度。

2.2 算法步骤

S1：备选路径集的选择：确定源节点a和目的节点bj(bj∈N)，利用深度优化搜索找出满足约束条件的路径，将搜索的所有路径组成多播组端接点bj的备选路径集PT（a，bj）。

S2：初始抗体群的产生：对备选路径集PT（a，bj），如其中有nbj（bj∈N）备选路径，共选N次，按选取的自然顺序将取得的这N组数据组成向量，记作Ab[r] ，则此向量就是初始抗体。把上述操作进行M次，就可得到一初始抗体群p[1]。

S3：亲和度计算：在优先满足延时条件下，定义亲和度函数f = Q 、Q=B/(D×C)其中

整体考虑组播路由综合性能，因为带宽越大、延时和代价越小，则Q值越大、组播综合性能越优。保留Q值最大的前5项的组播树，组成抗体群p[t]。

S4：克隆：设原抗体群p[t]为一X×Y维矩阵，那么对其进行的克隆操作可表示为：

其中In=X，这样所组成的就是二代的抗体群p[t+1]。

S5：基因优化：对二代抗体群p[t+1]基因优化操作。即对个体内部的所有源节点到目的节点所选择的的路径进行亲和度计算，每组源节点和目的节点只保留一个最有路径。

S6：克隆交叉：采用随机按位交叉，对二代抗体群p[t+1]进行交叉换位，随机产生L组组播树，并在其随机位上按照交叉概率进行交换。

S7：遗传变异：同样采用随机按位交叉，对二代抗体群p[t+1]进行变异操作，随机选取一整数值R∈[0，ni-1]，按照变异概率取代pi×j[t]=Ab[r]，(i＜X，j＜Y，r[1，M])上的原有值。

S8：判断最优个体：若新一代群体中存在最优个体，则终止运算；否则，t = t+1转到S4。

2.3 仿真结果及分析

本文算法采用MWaxman提出的方法[6]，所使用的网络拓扑图如图1所示，延时、带宽、代价由（D,B,C）表示，源节点为1，目的节点为2、3、5、8。

图1 节点网络拓扑Fig. 1 Node network topology

当带宽约束的B=70，延时D≤45，时。首先进行预处理，去掉不满足要求的3-7、5-6两条链路。则生成的路径集如表1所示。

使用matlab编写该算法程序并运行，结果如图2所示，算法在第一代就收敛了，大大提高了其收敛速度。得出的最优组播树为[{1,2},{1,2,5},{1,4,3},{1,2,5,7,8}]，Q=0.108 6。

图2 Q值随代数变化曲线Fig. 2 Curve of Q value change with algebra

表1 备选路径集Tab.1 Alternative path set

3 结 论

仿真结果表明算法通过设计适应度函数Q，并结合交叉、变异的克隆原理对组播路由进行优化，可使程序运行更为简洁，提高了效率，其收敛度明显有较大提高，运行可靠，大大改善了QoS组播路由[7]的服务质量。

[1] 胡虹雨,毕军,陆慧梅.大规模组播路由中组播相关信息聚集问题研究[J].清华大学学报,2011(12):1800-1807.

HU Hong-yu,BI Jun,LU Hui-mei.Aggregation of multicastrelated information in large scale multicast routing[J].Journal of Tsinghua University,2011(12):1800-1807.

[2] 张银浦.遗传算法在组播路由优化中的应用[J].河北科技大学学报,2011(3):261-264.

ZHANG Yin-pu.Application of gencetic algorithm to of multicast routing[J].Journal of Hebei University Of Science and Technology,2011(3):261-264.

[3] 刘维群，李元臣.一种满足时延和时延差约束的组播路由算法[J].计算机工程 ,2012(14):102-105.

LIU Wei-qun，LI Yuan-chen.Multicast routing algorithm satisfying delay and delay defference constraint[J].Computer Engineering,2014(14):102-105.

[4] 刘国联,何炼.一种用于优化QoS组播路由的克隆算法[J].科技信息,2012(32):55-56.

LIU Guo-lian,HE Lian.A clone of optimization algorithm for QoS multicast routing[J]. Science & Technology Information,2012(32):55-56.

[5] 黄小凤,王炼红.基于改进克隆策略的整体优化组播路由算法[J].电子技术应用,2009(9):119-121,125.

HUANG Xiao-feng,WANG Lian-hong.Whole optimization multicast routing algorithm based on improved clonal strategy[J].Application of Electronic Technique,2009(9):119-121,125.

[6] 丁文. 基于免疫多目标优化的网络组播路由选择[J].计算机应用研究,2012(4):1477-1479.

DING Wen. Multicast routing selection based on multi-object immune alogrithm[J].Application Research of Computers,2012(4):1477-1479.

[7] 张启明.无线网络中一种高QoS保证的路由协议研究[J].现代电子技术,2012(21):78-82.

ZHANG Qi-ming. Research of a high QoS guarantee of routing protocol in the wireless network[J].Modern Electronics Technique,2012(21):78-82.

QoS multicast routing optimization based on clonal selection

WANG Xin
（College of Electrical Engineering, Xi'an Aeronautical University, Xi'an 710077, China）

Influence of QoS multicast routing is the larger delay, bandwidth, at the expense of performance indicators,this paper presents an optimization algorithm for multiple constrained QoS multicast routing based on genetic algorithm.Introduce a comprehensive performance index of Q fitness function, to weigh in on time delay, bandwidth, at the expense of the three performance indicators. The cost of delay is small, the multicast tree bandwidth, improve the multicast service quality. And effective solution to the traditional algorithm for the existence of two group and multicast tree above, their price is the best, do not choose to delay and bandwidth can satisfy the constrained conditions of the problem.

multicast routing; genetic algorithm; colonal selection; fitness function

TN919

A

1674-6236(2014)03-0083-02

2013–06–28 稿件编号：201306198

王 莘(1983—)，男，陕西西安人，硕士研究生，助教。研究方向：电力电子控制。