0 引言

近年来，为了满足不断增长的用户需求，云计算行业部署了可容纳100多万台服务器的巨大数据中心，规模呈指数级增长。虚拟化技术是云计算范式中使用的主要技术之一^[1]，可以使同一台物理机托管和运行多台虚拟服务器，提高资源利用率并降低总功耗^[2]。在网络虚拟化范式中，传统互联网服务提供商包括基础设施提供商和服务提供商^[3]，前者管理物理网络资源，后者负责按需租赁硬件资源，创建虚拟网络，为用户提供IT服务。虚拟化技术为这种云计算多租赁市场运营机制提供了重要的技术支持，对企业提高收益和资源利用率有较大的意义。

虚拟网络映射技术是网络虚拟化研究的热点问题之一。文献[4]证明了虚拟网络映射问题是NP难的；文献[5]选用构造性粒子群算法优化虚拟网络映射问题，将节点映射和链路映射融合到同一阶段完成；文献[6]提出一种基于滑动区域的粒子群节能映射算法；文献[7]通过蚁群随机游走的预计算算法识别虚拟网络拓扑结构；文献[8]提出一种基于霍普菲尔德神经网络的节能映射算法；文献[9]提出一种节能、并发和拓扑感知的虚拟网络映射方法，采用非支配排序遗传算法优化映射方案；文献[10]提出一种环境自适应的拓扑联合感知虚拟网络映射算法；文献[11]提出一种基于消除和选择表达实现的虚拟网络映射方法，使用多准则决策分析物理节点的综合评估。

上述方案虽然在一定程度上解决了虚拟网络映射问题，但以文献[5-6]为例，部分研究将节点映射和链路映射融合在一个阶段完成，使得每次的链路选择虽然是局部最优，但最终的虚拟网络映射解的物理链路并不是整体的最短路径，从而导致链路资源消耗过多。文献[7-11]没有考虑节点在网络拓扑中所处的相对位置对节点选择的影响，可能得到与全局最优解相差较大的局部最优解。针对上述问题，本文提出一种两阶段的基于含权k-壳分解的分组教学虚拟网络映射算法。该算法首先使用含权k-壳分解法^[12]，为物理节点计算出一个基于网络位置核心与否的重要性排序，在以往的度中心性的基础上，添加了对节点位置、链路权值等拓扑属性的考量，把节点所处的周围环境量化为节点重要度，避免节点疏散导致链路映射开销过大。然后，使用最短路径算法映射链路，结合分组教学优化模型的分组、教学、自学与互学的优化策略，实现节点和链路的协调映射，弥补了一阶段算法的不足且避免搜索陷入局部最优解，提升了虚拟网络请求接受率及长期收益成本比。

1 网络模型和评价指标

参考文献[5, 6, 8, 11]对虚拟网络映射问题的研究，设计了网络模型和评价指标。

1.1 网络模型 1.1.1 物理网络

物理网络表示为带权无向图G^s=(N^s, L^s, C_N^s, B_L^s)，其中：N^s和L^s分别表示物理节点和链路的集合；C_N^s表示物理节点n^s(n^s∈N^s)所能提供的CPU资源；B_L^s表示物理链路l^s(l^s∈L^s)所能提供的带宽资源。虚拟网络映射示例如图 1所示。图中SN是物理网络示例；A~F为物理节点，方框内数字表示其剩余CPU和总CPU资源；节点间连线为物理链路，线上数字表示其剩余带宽和总带宽。

1.1.2 虚拟网络

虚拟网络模型也用带权无向图G^v=(N^v, L^v, C_N^v, B_L^v)表示，其中，N^v和L^v分别表示虚拟节点和链路的集合；C_N^v表示虚拟节点n^v(n^v∈N^v)所需的CPU容量；B_L^v表示虚拟链路l^v(l^v∈L^v)所需的带宽资源。当虚拟网络请求到达后，物理网络为其分配满足C_N^v、B_L^v约束的网络资源。虚拟网络运行结束后，其所占的资源将被物理网络收回。在图 1中，VN是一个虚拟网络请求；a~c为虚拟节点，方框内数字表示其CPU需求；节点间连线为虚拟链路，线上数字为其带宽需求。

1.1.3 映射

虚拟网络的映射问题可以描述为G^v到G^s的一个映射M: G^v(N^v, L^v)→G^s(N^s, L^s)，包括节点映射M_node和链路映射M_link两个阶段。

M_node: N^v→N^s ∀ n^v, m^v∈N^v, M_node(n^v)=n^s∈N^s，当且仅当m^v=n^v时，服从

$ M_{\text {node }}\left(n^v\right)=M_{\text {node }}\left(m^v\right), $

(1)

$ C_N^v\left(n^v\right) \leqslant C_N^s\left(M_{\text {node }}\left(n^v\right)\right)_{\circ} $

(2)

M_link: L^v→P^s ∀ l^v=(n^v, m^v)∈L^v, M_link(n^v, m^v)=P^s(n^v, m^v)∈P^s(M_node(n^v), M_node(m^v))，服从

$ B_L^v\left(l^v\right) \leqslant \min \limits_{l^s \in P^s\left(l^v\right)} B_L^s , $

(3)

其中：P^s表示物理节点之间所有可用无环路径的集合。式(1)说明同一个虚拟网络请求的不同虚拟节点需分配给不同的物理节点；式(2)旨在确保物理节点必须满足虚拟节点的CPU资源请求；式(3)旨在确保每一个虚拟链路(n^v, m^v)所映射的物理链路的带宽资源满足该虚拟链路的带宽需求。在图 1中，VN的节点映射结果为{a→A, b→F, c→B}，链路映射结果为{(a, b)→(A, F), (a, c)→(A, B), (b, c)→(F, E), (E, B)}。

1.2 评价指标

在t时刻，物理网络接受虚拟网络请求，为基础设施提供商带来收益的计算公式为

$ \mathit{Rev}\left(G^v, t\right)=\alpha \sum\limits_{n^v \in N^v} C\left(n^v\right)+\beta \sum\limits_{l^v \in L^v} B\left(l^v\right), $

(4)

其中：C(n^v)表示虚拟节点n^v所需的CPU资源；B(l^v)表示虚拟链路l^v所需的带宽资源；参数α和β用于调节CPU和带宽资源的权重。

在t时刻，物理网络接受虚拟网络的成本定义为节点和链路资源的成本之和，

$ \mathit{Cos}\left(G^v, t\right)=\gamma \sum\limits_{n^v \in N^v} C\left(n^v\right)+\delta \sum\limits_{l^v \in L^v} \sum\limits_{l^s \in L^s} B\left(l^v\right) \mathit{len}\left(l^s\right), $

(5)

其中：len(l^s)表示用于映射链路l^v的物理链路数；参数γ和δ用于调节CPU和带宽资源的权重。

利用虚拟网络映射长期收益成本比可以判断出虚拟网络映射算法是否高效，其计算公式为

$ R / C=\lim _\limits{T \rightarrow \infty} \frac{\sum\limits_\limits{t=0}^T \operatorname{Rev}\left(G^v, t\right)}{\sum\limits_\limits{t=0}^T \operatorname{Cos}\left(G^v, t\right)} 。$

(6)

利用虚拟网络请求接受率可以判断出虚拟网络映射算法是否合理，其计算公式为

$ R A T_{\mathrm{accept}}=\lim _\limits{T \rightarrow \infty} \frac{\sum\limits_\limits{t=0}^T V N R_{\mathrm{acc}}}{\sum\limits_\limits{t=0}^T V N R_{\mathrm{tot}}} 。$

(7)

在T足够大的情况下，从t=0到T时刻，式(7)的分子表示基础设施提供商成功接受的虚拟网络请求数目，分母表示向基础设施提供商发送的虚拟网络请求总数。

2 算法设计 2.1 算法框架

受分组教学机制的启发，文献[13]提出一种新的全局优化算法——分组教学优化算法(group teaching optimization algorithm, GTOA)。在此基础上，本文提出一种两阶段的基于含权k-壳分解的分组教学虚拟网络映射算法KGTOA-VNE。该算法基于GTOA构造了一个两阶段分组教学模型：由学生能力分组和教师选取组成角色分配阶段；由教师教学和学生自学互学组成学习更新阶段。该模型中每一个学生和教师都是虚拟网络映射问题潜在的解。KGTOA-VNE结合网络拓扑信息，使用含权k-壳分解法对物理网络进行预处理，计算出物理节点重要度，以协调两阶段映射过程。预处理结果作为虚拟网络映射寻优过程的决策变量，为学习更新指定教学方向。在学习阶段学生进行学习，迭代更新解的知识内容，当满足停止准则时，返回群体找到的最优解。KGTOA-VNE算法框架如图 2所示。

2.2 底层网络预处理

底层网络预处理定义了物理节点的重要性。一些算法在计算节点之间联系时，认为无边为0、有边为1，但这种方式往往不能准确地观察网络复杂性图景。KGTOA-VNE算法基于含权k-壳分解法提出一种物理网络节点重要度计算方法，该方法用链路带宽作为权值衡量节点之间联系的强弱，并将物理网络层层剥壳，为每个节点分配一个表示网络位置层级的整数索引k_s。小的k_s表示网络的边缘位置，最内层的网络核心节点对应大的k_s^[14]。通过物理节点在网络中的位置计算该节点的重要度，是度中心性的一种扩展，削弱了边缘位置节点的影响力，提高核心位置节点的重要性。k-壳分解后的物理网络如图 3所示。

图 3中节点的最小度数从1开始，去掉网络中度为1的物理节点及所连链路(去掉节点1~6及链路)，继续去掉剩余网络中出现的一些新的度为1的节点(去掉节点7、8及链路)，直到不再存在度小于等于1的节点。被去掉的节点组成1-壳物理节点，记为k_s=1。按上述方法继续剥壳，网络中2-壳节点为9~11，3-壳节点为12~15，当网络为空时结束。该方法根据k_s将节点进行了位置层级划分，而不是简单地认为具有相同度的节点同等重要，可以为学生找到更值得学习的节点。例如节点7和12、14、15具有相同的度，但若承载相邻的虚拟节点会占用较多的链路。物理网络节点度量计算公式为

$ \mathit{Val}(n)=\left[k(n)^{\omega_1}\left(\sum\limits_{m \in N(n)} B(n, m)\right)^{\omega_2}\right]^{\frac{1}{\omega_1+\omega_2}} C(n), $

(8)

其中：k(n)为节点n的壳数；N(n)为节点n的一阶邻居节点集合；B(n, m)为节点n和m之间的剩余链路带宽；C(n)为节点n的剩余CPU容量；ω₁、ω₂为调节比重的参数。根据式(8)，具有较大Val值的节点优先考虑被映射。底层网络预处理过程(节点排序算法)的具体步骤如下。

算法1 节点排序算法

输入：底层网络G^s=(N^s, L^s, C_N^s, B_L^s)

输出：按照重要度排序的节点

1.k_s←1//初始化壳数

2.while(G^s! =null)//判断是否所有节点计算完毕

3. temp←0

4. for n in G^s.node

5.   p ← sum(G^s.neighbors(n))//计算节点n的邻居节点个数之和赋值给p

6.   if p < =k_s

7.     q←∑ m∈N(n) B(n, m)//计算节点n和邻居节点的带宽之和

8.     根据式(8)计算出节点排序度量

9.     remove(n)//将节点从网络中移除

10.     temp++

11.   if temp==0//网络中不存在k_s壳节点

12.   k_s++

13. 将节点按照排序度量从大到小排序

2.3 算法流程 2.3.1 初始化

初始化参数和种群，针对虚拟网络映射问题，KGTOA-VNE算法重新定义学生矩阵，其元素为每个虚拟节点所映射物理节点的度量，

$ \boldsymbol{X}^t=\left[X_1^t, X_2^t, \cdots, X_N^t\right]^{\mathrm{T}}=\left[\begin{array}{ccc} x_{1, 1}^t & \cdots & x_{1, D}^t \\ \vdots & & \vdots \\ x_{N, 1}^t & \cdots & x_{N, D}^t \end{array}\right], $

(9)

其中：N为初始化虚拟网络映射解的个数；维度D为虚拟网络请求的节点个数；t为当前评估次数，最大评估次数为T_max。

2.3.2 角色分配阶段

1) 学生能力分组

为了不失一般性，假设整个班级的学生成绩服从正态分布，密度函数公式为

$ f(x)=\frac{1}{\sigma \sqrt{2 \pi}} \mathrm{e}^{\frac{-(x-\mu)^2}{2 \sigma^2}} \circ $

(10)

提高平均成绩μ和减少标准差σ是提升班级成绩的两种途径。根据成绩的高低，将学生分成人数相同且服从正态分布的两组。成绩高的学生为出色组，拥有更好的学习能力，剩余的学生为一般组。学生能力分组在寻优过程中是动态的，每一轮过后，所有学生根据新的成绩重新分组。

2) 教师选取

学生取得的成绩为虚拟网络映射解的收益成本比，用适应度函数F(x)表示。首次选取F(x)值最大的学生担任教师角色，在之后的迭代过程中按照式(11)选取教师，

$ T e a^t= \begin{cases}x_{F 1}^t, & F\left(x_{F 1}^t\right) \geqslant F\left(\frac{x_{F 1}^t+x_{F 2}^t+x_{F 3}^t}{3}\right), \\ \frac{x_{F 1}^t+x_{F 2}^t+x_{F 3}^t}{3}, & F\left(x_{F 1}^t\right)<F\left(\frac{x_{F 1}^t+x_{F 2}^t+x_{F 3}^t}{3}\right), \end{cases} $

(11)

其中：x_F1^t、x_F2^t、x_F3^t 为成绩最优的三个学生。如果第一优学生适应度值高于前三优学生均值，则选取第一优学生作为教师，反之，则选取前三优学生的均值作为教师。为了加快算法的收敛速度，学生共用相同的教师。

2.3.3 学习更新阶段

1) 教师教学

教师为不同组的学生制订不同的教学计划。

① 面对接受知识能力较强的出色组，教师在考虑学生接受知识方面能力差异的同时，着重对其平均成绩μ的提高。该组通过式(12)~(15)更新课程，

$ \begin{aligned} & x(i, n)_{\text {tea }}^{t+1}=x(i, n)^t+a \times\left(\mathit { Tea }(n)^t\right)- \\ & a \times\left(F \times\left(b \times M(n)^t+c \times x(i, n)^t\right)\right), \end{aligned} $

(12)

$ M(n)^t=\frac{1}{N} \sum\limits_{i=1}^N x(i, n)^t, $

(13)

$ b+c=1, $

(14)

$ x(i, n)_{\text {tea }}^{t+1}= \begin{cases}x(i, n)_{\text {tea }}^{t+1}, & F\left(x(i)_{\text {tea }}^{t+1}\right)>F\left(x(i)^t\right), \\ x(i, n)^t, & F\left(x(i)_{\text {tea }}^{t+1}\right) \leqslant F\left(x(i)^t\right), \end{cases} $

(15)

其中：x(i, n)^t为第i个虚拟网络映射解在t时刻第n个虚拟节点所映射物理节点的重要度；Tea(n)^t为教师在t时刻第n个虚拟节点所映射物理节点的重要度；M(n)^t为出色组在t时刻第n个虚拟节点所映射物理节点的重要度均值；x(i, n)_tea^t+1为第i个虚拟网络映射解更新后，在t+1时刻第n个虚拟节点所映射物理节点的重要度；F为教学因子，取1或2；调节参数a、b、c为[0, 1]内的随机数，避免算法搜索陷入局部最优。

② 面对接受知识能力较弱的一般组，教师倾向从个体的角度提高学生的成绩。该组通过式(15)和(16)更新课程，

$ x(i, n)_{\text {tea }}^{t+1}=x(i, n)^t+2 \times d \times\left(\mathit { Tea }(n)^t-x(i, n)^t\right), $

(16)

其中：d为[0, 1]内的随机数。

虚拟网络映射解只有当适应度函数值提高时，更新选择映射的物理节点，否则不更新。

2) 学生自学互学

在课余时间，学生通过式(17)和(18)更新自己的知识。式(17)的第2、3项分别表示学生向其他同学学习交流和自学的两种学习过程。

$ x(i, n)_{\text {stu }}^{t+1}=\left\{\begin{array}{l} x(i, n)_{\text {tea }}^{t+1}+e \times\left(x(i, n)_{\text {tea }}^{t+1}-x(j, n)_{\text {tea }}^{t+1}\right)+ \\ g \times\left(x(i, n)_{\text {tea }}^{t+1}-x(i, n)^t\right), \\ \;\;\;F\left(x(i, n)_{\text {tea }}^{t+1}\right)>F\left(x(j, n)_{\text {tea }}^{t+1}\right), \\ x(i, n)_{\text {tea }}^{t+1}-e \times\left(x(i, n)_{\text {tea }}^{t+1}-x(j, n)_{\text {tea }}^{t+1}\right)+ \\ g \times\left(x(i, n)_{\text {tea }}^{t+1}-x(i, n)^t\right), \\ \;\;\;F\left(x(i, n)_{\text {tea }}^{t+1}\right) \leqslant F\left(x(j, n)_{\text {tea }}^{t+1}\right), \end{array}\right. $

(17)

其中：x(i, n)_stu^t+1是第i个虚拟网络映射解在自学互学完成后，在t+1时刻关于节点n的信息；x(j, n)_tea^t+1是虚拟网络映射解j在t时刻向教师学到的关于节点n的信息，j∈{1, 2, …, i-1, i+1, …, N}是随机选择的；e和g为[0, 1]内的随机数，避免算法搜索陷入局部最优。

$ x(i, n)_{\text {stu }}^{t+1}=\left\{\begin{array}{l} x(i, n)_{\text {tea }}^{t+1}, F\left(x(i, n)_{\text {tea }}^{t+1}\right)>F\left(x(i, n)_{\text {stu }}^{t+1}\right), \\ x(i, n)_{\text {stu }}^{t+1}, F\left(x(i, n)_{\text {tea }}^{t+1}\right) \leqslant F\left(x(i, n)_{\text {stu }}^{t+1}\right) 。\end{array}\right. $

(18)

同样地，虚拟网络映射解只有当适应度函数值提高时，更换选择映射的物理节点，否则不更新。

KGTOA-VNE算法通过角色分配和学习阶段迭代更新，链路映射使用最短路径算法。当满足停止准则时，进行种群评估，选取总成绩最好的学生为最优解。KGTOA-VNE算法的执行过程如下。

算法2 KGTOA-VNE算法

输入：底层网络G^s，G^v。

输出：最优解x(i)。

1.初始化参数：最大评估次数T_max，当前评估次数T_current，种群大小N，决策变量上下界u、l，维度D，适应度函数F(x)；

2.初始化种群，根据参数随机生成种群X^t；

3.计算个体适应度，按降序排列，选择最优解x(i)；

4.更新计算次数T_current=T_current+N；

5.while(T_current < T_max)

6. 根据式(11)，分配教师Tea(n)；

7. if学生解的适应度值索引>N/2

8.   //将学生分为出色组x_good

9.   根据式(12)~(15)实现教师教学阶段；

10.   根据式(17)和(18)执行学生学习阶段；

11. else

12.   //将学生分为一般组x_common

13.   根据式(15)和(16)实现教师教学阶段；

14.   根据式(17)和(18)执行学生学习阶段；

15. 将x_good和x_common组成一个新的种群；

16. 计算种群适应度值，并按降序排列，选择最优解x(i)；

17. T_current=T_current+2N+1。

KGTOA-VNE算法的时间复杂度为O((|N^v|+|N^s|²+|L^v||N^s|²)×|P|×|iter|)，包括物理网络初始化的复杂度O(|N^s|²)，虚拟节点映射的复杂度O(|N^v|)，链路映射的复杂度O(|L^v||N^s|²)。其中，|P|表示学生的总人数，|iter|表示迭代次数。

3 实验仿真与分析 3.1 实验仿真

参考文献[6, 11]的实验环境，采用GT-ITM工具生成物理网络和虚拟网络请求拓扑图。在物理网络中，初始化物理节点数为100，且物理节点的CPU容量和链路的带宽资源为均匀分布在[50, 100]的实数。虚拟网络请求以泊松过程持续到达，每100个时间单位内到达5个虚拟网络请求，每个虚拟网络的生命周期服从均值为1 000个时间单位的指数分布，映射收集时间窗口为2 000个时间单位，模拟环境总时长为40 000个时间单位，共2 000个虚拟网络请求。每个虚拟网络请求中，节点CPU和链路带宽资源需求为[0, 30]的均匀分布。每个虚拟网络请求的节点个数取值范围为[0, 20]之间的整数。任意两个物理节点或虚拟节点之间连通的概率为50%，种群规模设置为15，ω₁、ω₂为1。

3.2 实验分析

为了验证本文所提算法的性能，选取基于构造性粒子群实现的一阶段(CPSO-VNE)算法^[5]、基于非支配遗传算法的多目标节能(EE-CTA)算法^[9]、基于环境自适应的拓扑联合感知二阶段(EAJTA-VNE)算法^[10]和基于消除和选择表达实现的二阶段(ELECTRE-VNE)算法^[11]作为对比算法，对虚拟网络请求接受率和长期收益成本比等进行综合评价。

图 4显示了不同虚拟网络映射算法的物理节点开启量随时间的变化趋势。EE-CTA算法以节能为目标，采用非支配排序遗传算法寻找最优解，减少了节点开启数目，但同时也存在由于映射失败导致节点开启量低的情况。其余四种算法的节点开启量非常接近，反映了它们在利用具有足够资源的物理节点来承载虚拟节点方面有一定的相似性。

图 5显示了不同虚拟网络映射算法的物理链路开启量随时间的变化趋势。KGTOA-VNE算法通过底层网络的预处理，加入对物理节点位置信息的考量，减少了所映射物理节点间距离。ELECTRE-VNE算法在对节点重要性排序时考虑了多个属性，但多属性间的不均衡性可能导致节点映射较为分散，从而链路开启量较高。EAJTA-VNE算法在节点选取过程中，利用相对熵思想结合CPU、链路带宽等因素，对节点的重要度进行排序，优先映射重要度较高的节点，但是由于没有考虑位置集中性，重要度较高的物理节点存在相距较远的情况，导致需要经过多条链路连接虚拟节点。

图 6显示了不同虚拟网络映射算法的请求接受率随时间的变化趋势。KGTOA-VNE算法的请求接受率接近100%，比其他算法高出约0.58%~6.70%。其中ELECTRE-VNE算法和KGTOA-VNE算法的请求接受率非常相似，但是其在映射虚拟节点时考虑了过多的属性，这在一定程度上会对算法的接受率产生负面影响。CPSO-VNE算法选用粒子群的逐步更新，将节点映射和链路映射融合到一阶段完成，但一阶段映射在算法平衡性方面没有两阶段的效果好，从而导致了该算法的请求接受率不足。KGTOA-VNE算法利用含权k-壳分解法和分组教学模型对解进行优化，确保了虚拟节点和链路能够映射在地理位置集中且具有足够资源的物理网络上。因此，当请求服务时间结束后，释放出的物理网络资源足够集中，便于后续虚拟网络请求的映射，避免了资源碎片化，提高并维持了算法的请求接受率。

图 7显示了不同虚拟网络映射算法的长期收益成本比随时间的变化趋势。KGTOA-VNE算法的收益成本比相较其他算法高出约12.15%~20.25%。在虚拟网络请求被接受的情况下，随着时间的增加，由于节点CPU请求资源大小固定且被映射到单个物理节点上，节点开销可以认为是固定不变的。因此，链路开启量成为影响基础设施供应商花费的重要因素。EAJTA-VNE算法开启了大量的节点和链路来保障虚拟网络请求被接受，耗费了较多成本，使得收益成本比较低。EE-CTA算法的节点和链路开启量虽然都比较低，但是部分请求映射失败，基本收益没有得到保障，收益成本比也相对降低。CPSO-VNE算法和ELECTRE-VNE算法的整体协调性不如KGTOA-VNE算法。KGTOA-VNE算法结合分组教学优化模型的分组、教学、自学与互学的优化策略，实现节点和链路的协调映射，在保证了请求接受率的情况下使链路映射达到最优，提高了收益成本比。

4 结束语

本文提出一种基于含权k-壳分解的分组教学虚拟网络映射算法，利用含权k-壳分解法制定物理节点的排序指标，结合分组教学模型的寻优思想来优化映射结果。结果表明，本文算法可以减少链路映射的消耗，在确保虚拟网络映射请求接受率的情况下提高了收益成本比。但是，所提算法需要消耗一定量的时间，还需要进一步的改进。