基于帕累托效率的高效免疫克隆算法

付凡成

(南昌理工学院 计算机信息工程学院，江西 南昌 330044)

0 引 言

虚链路如何被采用一直是构建覆盖网络的关键难题之一。为了提高物理网络中相关特征能力，同时也为了满足上层应用需求，从物理网络中择取一部分关键节点，基于虚链路关联成一个虚拟的逻辑网络，这种网络称之为覆盖网络。覆盖网络的形式种类多样，针对不同类别的覆盖网络，其虚链路在采用过程中需要关注的因子、网络拓扑的构造特点以及实现的算法等均不一样。

在各种点对点网络中，为了满足网络节点的动态添加与删除，文献[1]提出分布式算法实现的选取策略，用来建立动态变化的覆盖网络拓扑。当对网络节点进行添加与删除之后，余下网络节点会依据分布式算法实现路由指标项的动态调节，即虚链路的动态添加或者移除。文献[2]基于覆盖网络服务体系，采取集中式算法，以网络带宽大小作为约束条件，在虚链路采用问题上实现了基于多数据流的线性框架的构建，其用处是为了在成本最优化情况下符合全部终端节点的流量要求。此框架是针对一组固定网络节点建立的覆盖网络，适合于大规模覆盖网络应用场景。在虚拟计算应用环境下，文献[3]提出一种覆盖网络拓扑构建算法，该算法基于Kautz图理论基础，将流量拥塞情况、网络节点度数、负载均衡等考虑到虚链路采用问题中，选取分布式算法实现，从而实现覆盖网络拓扑的动态调整与变化。

基于覆盖网络技术，移动化网格的设计与构建得以实现，然而考虑到特定场景的网络性质，其虚链路的采用受到特定因子影响。移动化网格的设计原理是将网络节点智能划分成一般节点与特殊节点，通过在特殊节点之间采用虚链路构建覆盖网络进行分布式资源协调。针对由n个特殊节点组成的覆盖网络，虚链路存在条数理论上等于n(n-1)/2。若覆盖网络拓扑选用全部连通模式，其任何一个特殊节点均需对余下所有特殊节点的状态信息进行维护，从而带给特殊节点较高的负载压力，影响覆盖网络扩展性；除此之外，相对一部分覆盖网络节点之间的直接连通路由成本比间接连通路由成本要高。所以，如何采取符合条件的虚链路将对覆盖网络负载能力与成本费用产生较大影响。

1 虚链路采用问题模型构建

在移动化网格中，覆盖网络需要承担任务配置、资源搜索以及路由转换等作用[4]，所以特殊网络节点之间尽可能采用带宽流量较高的链路。除此之外，覆盖网络中的虚链路与实链路是一对多的关系，一条虚链路可能对应一条或者多条物理网络真实路径，一条真实路径又对应多条实链路，所以实链路很大程度上直接影响虚链路的路由维护成本以及带宽流量大小。

网络中所需维护的虚链路条数与网络性能成正比关系，虚链路条数越多，其覆盖网络性能越好，然而对应的维护成本越大，所以在覆盖网络作为一个全连通网络的前提下，虚链路如何采用就需要深入考虑网络性能与维护成本两个变化因素[5]。虚链路采用问题抽象形式化描述如下：

覆盖网络的实模型使用三元图GON=(S,L,L’)描述，其中特殊网络节点集合使用S表示，实链路集合由L描述，覆盖网络链路使用L’描述。

定义2l’(i,j)→path(i,j)={l1,l2,…,lk}用以描述某一条虚链路对应的最优化实路径，其最优化即网络带宽最大、延迟最小或者实链路网络节点跳数最少等多种因子的总体最好状态。此最优化实路径是k条实链路的有序队列，其中某一条实链路使用li∈L描述。

定义3b(i,j)用于描述覆盖网络虚链路l’(i,j)的带宽，其大小数值由l’(i,j)对应的实路径path(i,j)决定。

覆盖网络必须是一个全连通网络，这是虚链路采用的一个关键前提，也就是说在覆盖网络中对于任意两个网络节点si, sj∈S,至少拥有一条网络路径(si, si1, si2,…, sik, sj), si, si1, si2,…, sik, sj∈S且互不相同，使得

在覆盖网络的全连通性得到保证的情况下，其虚链路采用问题则是尽量采用高带宽虚链路，并让网络链路总体维护成本最小，即如下

(1)

(2)

(3)

x(i,j)={0,1}

(4)

2 多目标免疫克隆算法P-IC

虚链路采用问题是一个多目标约束优化问题[6]，其问题时间复杂度与覆盖网络规模大小成正比关系。此处使用免疫克隆算法，引入人工免疫系统中克隆、变异以及选择等处理机制解决虚链路采用问题[7]。

2.1 约束处理机制

(5)

其中，x=[x(i,j)]n×n∈X∈[0,1]n×n，X表示一个n×n维决策空间，x(i,j)用以描述覆盖网络核心网络节点si与sj之间的虚链路是否被采用。

2.2 抗体编码分析

2.3 抗体群操作处理

(6)

(7)

(8)

通过克隆、基因重组处理之后，抗体种群转换成

(9)

(10)

基因变异处理采取自适应方式[10]，也就是在单一抗体外围生成一个变异的解群体，采用局部搜索使得抗体与抗原的亲和度尽可能得到提高。自适应方式的基因变异将解质量的好坏与查找区域互相关联，从而让自适应数值较大的抗体在较小区域内查找，反之自适应数值较小的抗体在较大区域内查找。

(11)

(12)

其中，rnd(2)表示随机发生器生成的整数模2所获取的结果，T是基因变异温度，另外Δ(x,y)描述如下

Δ(x,y)=y(1-rxλ)

(13)

(14)

多目标免疫克隆P-IC算法描述如下：

Algorithm P-IC( )

Input: Physical network topology and bandwidth parameters of super nodes

Output: Virtual links between super nodes and bandwidth

Step1: Set algorithm ternination condition;

Set the size of antibody population;

Initialize evolution algebra k=1;

Max iterations is Kmax=100;

Randornly generate initial antibody popution

Step2: Use clone perator on antibody population Bk

Step5: Let k=k+1, if k=Kmax, stop iteration, output Bk+1;

else return Step2

End

2.4 算法复杂度分析

考虑到N、Nnon与m是同阶，因此P-IC算法的时间复杂度下限最差是O(m2)。

3 仿真测试与结果分析

本文验证实验在Waxmax算法基础上，使用Brite工具构造一个覆盖网络拓扑图，模拟实际覆盖网络特性。假定特殊网络节点有10个，任意一个网络节点平均度数d=4,α=0.15，β=0.2。网络链路带宽使用边权值eb∈[5,100]表示；网络链路的维护成本使用ec∈[10,50]表示；对于10个特殊网络节点搭建的全连通图的每条边(虚链路)依次从1到45按序编号。

依据多目标免疫克隆P-IC算法，抗体群规模大小原始值是10；抗体编码长度是45；假定正常的nc数值，让克隆处理之后的抗体群规模大小N保持在30上下；单个抗体基因变异概率是一半，即1/2；P-IC算法的最大进化代数是100，不同处理类别实验模拟20次为一个周期，选取平均值作为最终结果。

虚链路最小带宽的优化情况如图1所示。其中横坐标代表进化代数，纵坐标表示虚链路最小带宽，每个黑圆点的分布位置表示某一代进化过程中某一个粒子所采用的虚链路中最小带宽。可知，在最原始生成的粒子中，最小带宽大小在5到20范围内，在进化过程中，P-IC算法会采用越来越高带宽的网络链路，在60到70代之间大概能趋于优化目标，其虚链路最小带宽无限趋向于35。

图1 虚链路最小带宽的优化情况

图2 虚链路总体维护成本的优化情况

虚链路维护成本的优化情况如图2所示。尽管部分粒子在原始阶段有较低的维护成本，然而结合图1可知，对应当时的虚链路带宽也不高，并且采用的虚链路并不能保证覆盖网络的全连通性。随着进化过程，全部粒子对应解的维护成本将趋向正常化。

虚链路采用问题获取的帕累托最优解集如图3所示。在获取的3个最优解中，依据对约束条件的转换，其中连通性是1的解说明是不连通的，所以定义为不可行解。剩下两个解则是可行解，覆盖网络虚链路可从中采用一个即可。

图3 虚链路采用问题获取的帕累托最优解集

4 结束语

虚链路采用问题是构建覆盖网络的重点问题之一，由于覆盖网络类型的多样性，虚链路采用过程中需要考虑的实现算法、参数因子以及网络拓扑特征各不相同。对于移动化网格覆盖网络的构建而言，是在一组固定的覆盖网络节点之间采用部分虚链路，并综合考虑了虚链路的带宽大小、网络连通性、实际链路带宽大小以及维护成本等因子。此处将虚链路采用问题抽象表述成约束条件下的多目标优化问题，在求解中，通过对约束条件进行转换，变成优化目标，并提出一种P-IC算法，以此进行求解。考虑到优化问题的求解手段不一，最优求解方法有待于进一步研究分析[10]。

参考文献：

[1]Yin Xunrui,Wang Yan.Min-cost multicast networks in Euclidean space[C]//Proceedings of the IEEE International Symposium on Information Theory-ISIT,2012:1316-1320.

[2]ZHANG Xiangrong,HOU Limin,LI Yangyang,et al.SAR feature extraction and recognition based on immune clone Gaussian process hidden variables model[J].Journal of Infrared and Millimeter Wave,2013,32(3):110-116(in Chinese).[张向荣,缑丽敏,李阳阳,等.基于免疫克隆高斯过程隐变量模型的SAR目标特征提取与识别[J].红外与毫米波学报,2013,32(3):110-116.]

[3]NI Zhiping,YU Ling,QIN Xi.Solution model of TSP problem based on chaotic immune clonal selection algorithm[J].Science and Technology Bulletin, 2016,32(10):93-97(in Chinese).[倪志平,余玲,覃溪.基于混沌免疫克隆选择算法的TSP问题求解模型[J].科技通报,2016,32(10):93-97.]

[4]Mishra M,Tripathy S,Peri S.SEPastry:Security enhanced pastry[C]//Proceedings of the Second International Confe-rence on Advances in Computing and Information Technology,2012:789-795.

[5]LIU Xiaosheng,LIU Jianping,LIU Bo.Implementation of AFDX virtual link layer based on FPGA[J].Computer Engineering,2012,38(19):233-237(in Chinese).[刘晓胜,刘建平,刘博.基于FPGA的AFDX虚拟链路层实现方法[J].计算机工程,2012,38(19):233-237.]

[6]Rong-hua S,Li-cheng J.A novel immune clonal algorithm for MO problems[J].IEEE Transactions on Evolutionary Computation,2012,16(1):35-50.

[7]SHENG Wanxing,ZHANG Bo,DI Hongyu,et al.Application of immune optimization algorithm based on dynamic antibody memory in automatic demand response[J].Journal of China Electromechanical Engineering,2014,34(25):4199-4206(in Chinese).[盛万兴,张波,邸宏宇,等.一种基于动态抗体记忆库的免疫优化算法在自动需求响应中的应用[J].中国电机工程学报,2014,34(25):4199-4206.]

[8]LIU Cheng,HE Feng,WANG Tong,et al.A routing algorithm for virtual link of AFDX network[J].Electro-Optical and Control,2014,17(12):211-215(in Chinese).[刘成,何锋,王彤,等.一种AFDX网络虚拟链路的路由配置算法[J].电光与控制,2014,17(12):211-215.]

[9]QI Yutao,LIU Fang,CHANG Weiyuan,et al.Memetic immune optimization algorithm for solving multi-objective problems[J].Journal of Software,2013,12(7):322-327(in Chinese).[戚玉涛,刘芳,常伟远,等.求解多目标问题的Memetic免疫优化算法[J].软件学报,2013,12(7):322-327.]

[10]Pallis G.Improving content delivery by exploiting the utility of CDN servers[C]//Proceedings of the 5th International Conference Data Management in Cloud,Grid and P2P Systems,2012:88-99.