0 引言

互联网以其通用性和方便性等特征吸引越来越多用户的同时，使得用户呈现出爆炸式增长的趋势，最终互联网的僵化现象日趋严重^[1]。为使用户方便快捷地使用网络信息资源，网络虚拟化^[2]技术应运而生，网络虚拟化技术主动适应新型网络架构，其方便性体现在将多个虚拟网络请求映射到有限的共享物理网络之上，从而满足用户的多样化需求。其中虚拟网络映射问题(Virtual Network Mapping Problem, VNMP) ^[3-6]是实现网络虚拟化的一个重要环节。

虚拟网络映射问题是一个NP-hard问题^[5]。在网络虚拟化中，不同的角色承担不同的任务，基础设施提供商(Infrastructure Provider, InP)和服务提供商(Service Provider, SP)分别承担不同的任务：InP主要的任务是管理物理基础设施资源；而SP主要的任务是从InP那里获得可用的物理网络资源创造虚拟网络并提供端到端的服务^[7]。所以虚拟网络映射问题的解决方案，应该从各个方面反映利益需求。

在虚拟网络映射问题中，大多数的研究围绕在单个目标的优化求解问题上，但实际上平衡多个目标的优化问题在现实世界中普遍存在，在虚拟网络映射的背景下也不例外，对一个目标最优的解无法保证对另一个目标也是最优的，这就需要寻找一个折中的解决方案，使每个目标函数同时得到优化，最终得到综合优化的解集，像这样的解集本文称为Pareto最优解集(Pareto-optimal Set)^[8]。在多目标优化问题中，随着目标个数的增加，占优阻力(Dominance Resistance)^[9-11]将逐渐增大，抗占优解(Dominance Resistant Solution, DRS)^[9-12]的数量也随之增加，从而使得Pareto熵逼近最优解的难度也逐渐增加。

多目标优化问题通常通过加权值的方法转化为单目标问题进行求解^[13-14]，但是权值的数值分配并不明确，得出的效果不是很好。目标约束化处理也是一种常用的解决方法^[15]，这些传统的数学规划方法往往效率较低，对于权值确定和目标顺序较敏感，因此，传统的优化算法对于解决实际问题中的多目标问题并没有起到较好的效果。进化算法作为一类成功应用于多目标优化领域的启发式搜索算法，受到越来越多的关注。

2002年，Deb等^[16]提出非常经典的多目标算法：NSGA-Ⅱ，采用新型的解集选择策略，保留精英集以使父代中的优良个体直接进入下一代，提高解集质量。本文在此基础上改进算法，结合粒子群优化算法，提出了一种多目标粒子群优化的虚拟网络映射算法(Virtual Network Embedding algorithm based on Multi-objective Particle Swarm Optimization, VNE-MOPSO)：融入遗传算法中的交叉算子思想，利用非支配排序、拥挤距离排序对解集划分各个等级，精英保留机制选择每代的优良个体进入子代直至得到需要的解集。本文确立了两个目标函数：成本和节点负载均衡度，采用基于VNE-MOPSO方法求解。与其他方法相比，本文方法主要有三个特点：

1) 以最小化成本和最小化节点负载均衡度为目标函数，既保证了较小的映射成本，又为虚拟网络映射提供了一个更为均衡的底层物理网络。

2) 采用基于非支配排序、拥挤距离排序的多目标优化算法求解。精英保留机制有效提高解集的质量，促进了Pareto解集的快速收敛。

3) 改进基本的粒子群优化算法。在寻优过程中融入了交叉算子的思想，并应用在虚拟网络映射中。在迭代过程中，以一定的概率将全局最优解和自身最优解交叉互换，从而扩大了解的搜索空间，在保证快速收敛的前提下有效避免了种群优化陷入局部最优。

1 多目标虚拟网络映射问题描述 1.1 网络模型

底层网络 底层物理网络可以标记为带权无向图G_s=(N_s，L_s，A_sⁿ，A_s^l)，其中，N_s代表底层节点集合，L_s代表底层链路集合，A_sⁿ代表底层节点对应的属性集(计算能力中央处理器(Central Processing Unit, CPU)，物理位置)，A_s^l代表底层链路对应的属性集(可用带宽)。在链路映射的过程中，令P_s表示底层网络所有节点之间无环路径的集合。

虚拟网络 虚拟网络也可以标记为带权无向图G_v=(N_v，L_v，R_vⁿ，R_v^l)，其中，N_v表示虚拟节点集，L_v表示虚拟链路集，R_vⁿ和R_v^l分别表示虚拟网络请求中的虚拟节点和虚拟链路约束集。

虚拟网络映射 虚拟网络的映射过程是将虚拟请求G_v部署到底层物理网络G_s的子集上，并且符合G_v对节点CPU、位置和链路带宽约束的过程。通常，虚拟网络映射可分为节点映射阶段f_N和链路映射阶段f_E。

1.2 目标函数定义

多目标的虚拟网络映射问题定义如下：

$\min \left\{ \begin{array}{*{35}{l}} {{f}_{1}}=\sum\limits_{u.v\in {{L}_{v}}}{\sum\limits_{j.k\in {{L}_{s}}}{f_{jk}^{uv}\cdot BW({{l}_{uv}})}} \\ {{f}_{2}}=\sqrt{\sum\limits_{u\in M}{{{(CPU(u)-\frac{\sum\limits_{u\in M}{CPU(u)}}{\left| M \right|})}^{2}}}} \\ \end{array} \right.$

(1)

其中： f₁代表虚拟网络映射方案的带宽开销； f₂代表节点的负载均衡度，|M|代表剩余物理节点资源。

资源容量约束：

$\left( \forall u\in {{N}_{v}} \right)\left( \forall j\in {{N}_{s}} \right):\left\{ \begin{matrix} x_{j}^{u}\cdot CPU\left( u \right)\le CPU\left( j \right) \\ x_{j}^{u}\cdot Dis\left( {{D}_{j}}{{D}_{u}} \right)\le {{W}_{u}} \\ \end{matrix} \right.$

(2)

$\left( \forall {{l}_{jk}}\in {{L}_{s}} \right)\left( \forall {{l}_{uv}}\in {{L}_{v}} \right):f_{jk}^{uv}\cdot BW\left( {{l}_{uv}} \right)\le BW\left( {{l}_{jk}} \right)$

(3)

连通性约束：

(∀j∈N_s)(∀l_uv∈L_v):

$\sum\limits_{{{l}_{jk}}\in {{L}_{s}}}{f_{jk}^{uv}}-\sum\limits_{{{l}_{kj}}\in {{L}_{s}}}{f_{kj}^{uv}}\left\{ \begin{matrix} \text{ }1, & \text{ }x_{j}^{u}=1 \\ -1, & \text{ }x_{j}^{u}=1 \\ \text{ }0, & 其他 \\ \end{matrix} \right.$

(4)

变量值范围约束：

$\left\{ \begin{align} & \left( \forall j\in {{N}_{s}} \right):\sum\limits_{u\in {{N}_{v}}}{x_{j}^{u}\le 1} \\ & \left( \forall u\in {{N}_{v}} \right):\sum\limits_{j\in {{N}_{s}}}{x_{j}^{u}=1} \\ \end{align} \right.$

(5)

$\left\{ \begin{align} & \left( \forall j\in {{N}_{s}} \right)\left( \forall u\in {{N}_{v}} \right):x_{j}^{u}\in \left\{ 01 \right\} \\ & \left( \forall {{l}_{jk}}\in {{L}_{s}} \right)\left( \forall {{l}_{uv}}\in {{L}_{v}} \right):f_{jk}^{uv}\in \left\{ 01 \right\} \\ \end{align} \right.$

(6)

2 VNE-MOPSO 2.1 PSO算法

粒子群优化算法(Particle Swarm Optimization, PSO)^[17]是计算智能领域，除了蚁群算法、鱼群算法之外的一种群体智能优化算法。由Eberhart和Kennedy在1995年提出，源于对鸟群捕食行为的研究。PSO算法是从这种生物种群行为特征中得到启发并用于求解优化问题的，每个粒子都有自己的位置和速度，粒子的速度决定了粒子移动的方向和距离，速度随自身及其他粒子的移动经验进行动态调整，逐渐向全局历史最优位置X^gb和自身历史最优位置X^pb移动，从而实现个体在可解空间中的寻优。

PSO的速度和位置更新计算式如下：

${{V}_{i+1}}=\omega {{V}_{i}}+{{c}_{1}}{{r}_{1}}({{X}^{pb}}-{{X}_{i}})+{{c}_{2}}{{r}_{2}}({{X}^{gb}}-{{X}_{i}})$

(7)

${{X}_{i+1}}={{X}_{i}}+{{V}_{i+1}}$

(8)

其中:X_i为粒子当前的位置向量，V_i为粒子当前的速度向量。ω表示粒子的惯性权重，表示粒子保持现有速度的惯性，r₁和r₂为0～1的随机数，c₁和c₂为学习因子，代表粒子分别向局部最优位置和全局最优位置移动的趋势。

2.2 PSO算子重定义

原始粒子群算法具有执行速度快、效率高的优点，主要用于解决连续域内的优化问题，其实现过程是粒子以一定的速度向自身历史最佳位置X^pb和全局粒子最佳位置X^gb聚集，从而不断优化得到最优解。

但是，虚拟网络映射问题是一个离散域问题，算法中每个粒子都代表问题的一个潜在解，每个粒子对应一个由适应度函数决定的适应度值，需要根据具体问题对算法的参数和相关操作进行重新定义。

定义1 粒子的位置。粒子的位置向量X_i=为第i个可能的映射方案，M表示虚拟网络中节点的个数，x_i^k取正整数，其值表示第k个虚拟节点从底层网络候选节点列表中选择的底层网络节点编号。

定义2 粒子的速度。粒子的速度向量V_i=为映射方案的调整决策，用于指导当前的映射方案向更优的映射方案调整。其中v_i^k是一个二进制变量。

定义3 减法$\Theta $。X_i$\Theta $X_j用于计算两种映射方案的差异性。如果映射方案在同一维上有相同的值，则差值的结果为1;否则为0。

定义4 加法$\oplus $。P_iV_i$\oplus $P_jV_j用于获得映射方案的调整决策，其中P_iV_i和P_jV_j分别以P_i的概率V_i维持各维的值和以P_j的概率V_j维持各维的值，P_i+P_j=1(0≤P≤1) 。

定义5乘法$\otimes $。X_i$\otimes $X_j用于获得新的映射方案，映射方案X_i按照调整决策X_j对其虚拟节点方案进行调整。

因此将式(7) 和(8) 重定义后的粒子群优化算法的位置和速度更新基本公式如下：

${{\mathit{\boldsymbol{V}}}_{i+1}}={{P}_{1}}{{\mathit{\boldsymbol{V}}}_{i}}\oplus {{P}_{2}}({{\mathit{\boldsymbol{X}}}^{pb}}\Theta {{\mathit{\boldsymbol{X}}}_{i}})\oplus {{P}_{3}}({{\mathit{\boldsymbol{X}}}^{gb}}\Theta {{\mathit{\boldsymbol{X}}}_{i}})$

(9)

${{\mathit{\boldsymbol{X}}}_{i+1}}={{\mathit{\boldsymbol{X}}}_{i}}\otimes {{\mathit{\boldsymbol{V}}}_{i+1}}$

(10)

其中:P₁、P₂和P₃随机产生，P₁+P₂+P₃=1。

2.3 VNE-MOPSO描述

第1.2节对多目标虚拟网络映射问题建立了模型。针对求解该问题，本文提出了一种基于多目标粒子群优化的虚拟网络映射算法，即VNE-MOPSO。将每次经过PSO算法产生的种群和自身最优种群合并后，进行非支配和拥挤距离排序，由此得到种群的全局最优解。PSO算法应用到虚拟网络映射中时，融入了交叉算子的思想，具体实现就是将全局最优解与个体最优解以一定的概率(本文中设置概率为0.9) 进行交换，然后进行迭代求解，因此该算法有效提高所求解的多样性并提高收敛速度。

VNE-MOPSO步骤如下。

1) 虚拟网络请求到达；

2) 初始化解集，用最短路径方法生成映射方案，计算每种映射方案的目标函数值f₁、 f₂；

3) 每种映射方案自身作为个体最优解，对解集进行非支配排序，得到等级为k₁, k₂，…，k_p，p个等级的解，将等级为k₁的非支配解集进行拥挤距离排序，取拥挤距离最大的映射方案作为当前的全局最优解；

4) WHILE(t未达到最大迭代次数T)

① 根据种群的个体最优解和全局最优解按照式(9) 、(10) 得到一个映射方案集oldpop(t)；

② 将这个映射方案集oldpop(t)与上一次迭代更新后的个体最优映射方案集pbpop(t-1) 的每个解进行支配对比，并将pbpop(t-1) 中的被支配解更新为oldpop(t)的对应解，最终得到当前迭代的个体最优映射方案集pbpop(t)；

③ 将②中提到的oldpop(t)与pbpop(t)合并，进行非支配排序、拥挤距离排序，得到gbpop(t)，进而得到全局最优解；

④ 随机产生一个概率r，设定如果r>0.9, 将全局最优解与任意一个个体最优解交换；

⑤ t=t+1；

END WHILE

5) 根据用户需求输出映射方案。

根据本节提到的算法对多目标虚拟网络映射问题进行求解，本文采用基于非支配排序、拥挤距离排序的多目标优化算法求解，提高解集的质量，促进了Pareto解集的快速收敛；改进的基本粒子群优化算法，融入交叉算子，在虚拟网络映射中得以应用，扩大了解的搜索空间，增加解集的多样性。在多目标虚拟网络映射寻优过程中，不是输出一个映射方案，而是以解集的形式输出结果，即得到一个Pareto解集，解集中的各个解都是互相非支配的。

3 仿真实验结果及分析 3.1 实验设置

在ViNE-Yard平台下对算法进行测试。在实验中，通过GT-ITM工具产生基础设施网络(Substrate Network, SN)及虚拟网络(Virtual Network, VN)的拓扑。其中底层网络拓扑包含100个物理节点，各节点的链接概率为0.5，底层节点的CPU资源和链路的带宽资源均服从[0,100]均匀分布。对于每个虚拟网络请求，节点数为均匀分布在[2,10]的随机数，其CPU需求为分布在[0,20]的随机整数。虚拟链路请求的带宽要求为均匀分布在[0,25]的随机数。所有算法通过C++语言在Linux系统下实现。在实验中，将会产生100个虚拟网络请求, 各虚拟请求按照泊松过程到达, 同时，设置算法的种群大小为20，进行30次迭代后产生映射方案。

3.2 评价指标

为了有效评估算法的性能，本文主要采用以下指标对算法进行评价。

1) 接受率。定义为在t时间段内，被成功接收的虚拟网络请求数目与虚拟网络请求的总数目的比值：

$R\left( t \right)=\frac{acCount}{total\_ac}$

(11)

其中：acCount表示一段时间内接收的虚拟网络请求数目；total_ac表示该时间段内总的需要处理的虚拟网络请求数目。

2) 平均收益。收益可以定义为接收一个虚拟请求的节点CPU资源和链路带宽资源的总和；平均收益就是指在t时间内的请求资源总和的平均值：

$\frac{t\_tr}{T}=\frac{1}{T}(\sum\limits_{{{n}_{v}}\in {{N}_{v}}}{CPU\left( {{n}_{v}} \right)}+\sum\limits_{{{l}_{v}}\in {{L}_{v}}}{BW\left( {{l}_{v}} \right)})$

(12)

3) 平均成本。成本可以定义为接收一个虚拟请求时分得的物理资源的总和。平均成本就是指平均一个虚拟请求的成本：

$\frac{t\_tc}{acCount}=\frac{\sum\limits_{{{n}_{v}}\in {{N}_{v}}}{CPU}+\sum\limits_{{{l}_{v}}\in {{L}_{v}}}{\sum\limits_{{{l}_{s}}\in {{L}_{s}}}{BW\left( f_{{{l}_{s}}}^{{{l}_{v}}},{{l}_{v}} \right)}}}{acCount}$

(13)

4) 节点负载均衡度：

$N=\sqrt{\sum\limits_{u\in M}{{{(CPU(u)-\frac{\sum\limits_{u\in M}{CPU(u)}}{\left| M \right|})}^{2}}}}$

(14)

3.3 实验结果及分析

在初始化的节点映射阶段，本文采用一种在满足虚拟节点请求的距离约束范围内的情况下，虚拟节点对应的满足条件的候选物理节点少的优先选择映射的映射策略。链路映射则采用了R-Vine映射算法^[18]中的虚拟网络映射方案。然后结合本文提到的算法，将多目标粒子群映射算法VNE-MOPSO分别与以成本为目标函数的单目标粒子群映射算法PSO(cost)-VNE，以节点负载均衡度为目标函数的单目标粒子群映射算法PSO(load)-VNE进行比较分析。

图 1比较的是VNE-MOPSO与以成本为目标函数的粒子群优化算法PSO(cost)-VNE和以节点负载均衡度为目标函数的粒子群优化算法PSO(load)-VNE的虚拟网络的接受率对比。由图 1可知，代表PSO(cost)-VNE算法和PSO(load)-VNE算法的两条曲线表明两种算法的接受率效果基本一致，而均低于经过改进的VNE-MOPSO的接受率。PSO(cost)-VNE算法和PSO(load)-VNE算法都是单目标粒子群算法，即使选择不同的目标函数，接受率结果也并未有明显差别，VNE-MOPSO均衡考虑两种目标函数，在同一时间段内接收的虚拟网络的个数相对多一些。

通过图 2可以发现，最初随着虚拟请求的到来，虚拟网络随之开始接收符合条件的虚拟请求，物理资源的使用相应增加，这样就会在初始短时间内迅速产生成本消耗。PSO(load)-VNE算法重点考虑网络均衡度，在资源充足的初始映射阶段产生的成本消耗相对很少，随着虚拟请求的不断到来，成本消耗趋于稳定。由于VNE-MOPSO需要平衡成本和节点负载均衡度这两方面的目标函数，而PSO(cost)-VNE算法仅仅考虑成本这一目标函数，相比VNE-MOPSO消耗了更多的底层资源。VNE-MOPSO在成本方面的优势随后得以体现，当虚拟请求的到来与离开平衡时，平均成本虽有波动但整体趋于平稳。且VNE-MOPSO的平均成本低于PSO(cost)-VNE算法的平均成本。VNE-MOPSO和PSO(load)-VNE算法的平均成本消耗虽然有高有低，但总体上是趋于一致的，在VNE-MOPSO兼顾考虑成本和节点负载均衡度的情况下，与只考虑节点负载均衡度来进行映射的PSO(load)-VNE算法相比，虽然平均成本没有优化，但在其他方面产生了优化。

如图 3所示，在节点负载均衡度方面，VNE-MOPSO均优于PSO(cost)-VNE算法和PSO(load)-VNE算法。

通过图 4可以看出，VNE-MOPSO的平均收益整体较优于PSO(cost)-VNE算法和PSO(load)-VNE算法。因为接受率测试结果很相近，所以它们的平均收益也有基本一致的结果。

将算法VNE-MOPSO与加权值的粒子群映射算法PSO(weight)-VNE进行比较分析。设置五条曲线“weight=1/9”，“weight=3/7”，“weight=1/1”，“weight=7/3”，“weight=9/1”，图 5~8分别为相应的接受率、成本、节点负载均衡度和收益对比。

图 5~8中比如“weight=1/9”表示目标函数中成本和节点负载均衡度以1:9的比例构成，以此类推其他设置权值。由图 5可知，虽然VNE-MOPSO在开始阶段的短时间内与其他测试结果有一致的接受率，但是时间约为4500后明显高于其他曲线。此图表明VNE-MOPSO与加权值的粒子群映射算法PSO(weight)-VNE相比接受率有一定的优越性。如图 6所示，VNE-MOPSO的平均成本均高于加权值的粒子群映射算法PSO(weight)-VNE的几个结果，因为更高的接受率意味着需要进行更多的虚拟网络映射，也会导致总映射成本的增加，但仍在可接受范围内。通过图 7和图 8可知，VNE-MOPSO相比其他结果有较好的节点负载均衡度和收益。

当weight=7/3时，PSO(weight)-VNE算法的接受率测试结果与VNE-MOPSO的最接近，但是还是低于该算法的接受率。此时由图 7可知节点负载均衡度是最高的，平均收益略低于VNE-MOPSO的，所以总体看来当weight=7/3时, PSO(weight)-VNE算法运行出的解决方案质量略差。当weight=3/7时，PSO(weight)-VNE算法的节点负载均衡度与VNE-MOPSO的最接近，但接受率和收益并没有很好的效果。加权值的算法首要难点就是权值确定，有时还需要有高的精确度，取值比例分配情况多样，在实际应用中，最终取值不一定是一种优秀的方案。

4 结语

针对虚拟网络映射问题，本文提出了一种多目标粒子群优化算法，并在虚拟网络映射中成功应用。该算法引入遗传算法中的交叉算子思想，以0.9的概率完成解集间的交换工作，同时有效结合非支配排序和拥挤距离排序方法。采用成本和节点负载均衡度作为需要处理的两个目标函数，同时考虑这两种因素对虚拟网络映射的影响。通过实验表明，该算法具备一定的有效性，仿真结果达到较好的平衡。

一个好的虚拟网络映射方案，需要考虑的因素是多方面的。在虚拟网络映射中，本文提出的算法考虑平衡两个目标函数对虚拟映射的影响，因此，下一步的工作是尝试平衡三个目标函数的作用，将有利于得到更好的虚拟网络映射处理方案。