博弈论组合赋权的虚拟网络映射算法

徐 江，孟相如，韩晓阳，史朝卫

1(空军工程大学 研究生院，西安 710051) 2(空军工程大学 信息与导航学院，西安 710077)

1 引 言

网络虚拟化[1]为解决网络“僵化”问题提供了有效手段，它可以实现多个异构的虚拟网络(Virtual Network，VN)共享底层网络(Substrate Network，SN)资源，不仅提高了网络资源利用率，也带来了更加灵活多样的服务，虚拟网络映射作为网络虚拟化的关键技术之一，受到广泛关注[2-4].

虚拟网络映射已被证明是NP-hard问题，相关的解决方法已经成为研究热点[5-8].虚拟网络映射按步骤可分一阶段和两阶段映射，一阶段映射算法由于复杂度较高，适应性较低，目前两阶段映射算法是研究的主流[3]，即首先将网络所有节点进行映射，然后再进行链路映射，因此节点映射策略对于虚拟网络映射成功与否起到非常关键的作用.节点映射方法主要有启发式算法[4]、线性规划求解[5]和智能优化算法[6]等，节点排序也已经从简单的节点资源排序[7]，发展到拓扑资源联合排序[8]，逐渐形成了节点多指标排序[9]的问题.文献[10]提出一种基于TOPSIS(Technique for Order Preference by Similarity to Ideal Solution，TOPSIS)的节点重要性评估方法，并且在考虑节点资源属性的基础上，引入了社会网络分析法中的度中心性和接近度中心性，但TOPSIS方法的欧式距离无法区分与正负理想方案距离相等的点，并且节点指标权重人为设置，主观性较强.文献[11]提出一种加权相对熵的节点排序方法，能实现虚拟拓扑与物理拓扑联合感知，但是其指标权重需要根据环境变化进行人为调整，因此对经验依赖较大.文献[12]介绍了底层网络特征的提取过程、节点排序方法，并利用粒子群优化方法训练指标权重向量，它可以针对不同的优化目标，自动确定算法中的参数，但是算法复杂度较高.

从目前的研究来看，虚拟网络映射中节点多指标排序的问题，归根到底是指标选择与权重确定的问题.节点指标选择主要是将节点资源属性与拓扑属性相结合从而更为综合的反映节点的重要性，但是各指标之间相互关系复杂，对于具体指标的选择是一个挑战；指标权重的获取主要有主观赋权法[13]和客观赋权法[14]，主观赋权法结合了专家的经验，能够根据实际情况进行针对性的调整，但是对经验依赖性较强，客观赋权法基于相应的科学理论，方法众多、应用广泛，但与实际问题结合中存在一定的片面性.

针对上述问题，本文提出一种博弈论组合赋权的虚拟网络映射算法(Virtual Network Embedding Algorithm Based on Game Theory Combination Weighting，GTCW-VNE)，首先综合考虑节点资源属性与拓扑属性提取特征指标，进行归一化处理后组成节点特征指标向量并构建决策矩阵，其次利用层次分析法(Analytic Hierarchy Process，AHP)和熵值法分别获取节点指标权重向量，然后利用博弈论组合赋权法对其进行平衡，进而将具有互补作用的主客观赋权法结合，兼顾两者优点，得到最优的权重向量，最后按节点特征指标向量与指标权重向量的内积值对节点排序.仿真结果表明该算法提高了虚拟网络映射成功率和收益开销比.

本文的主要贡献如下：

a.将虚拟网络映射建模为一个节点多指标排序的优化问题，指出影响节点排序优劣的主要因素为能否根据映射目标选取合适的节点指标和权重.

b.提出了博弈论组合赋权的虚拟网络映射算法，首次将主观赋权方法与客观赋权方法结合运用于虚拟网络映射，提升了算法性能.

c.为了提高映射算法应对环境变化的能力，将熵值赋权法与AHP应用于节点指标赋权，使得节点指标权重可以随网络环境的变化进行相应的调整，增强了节点指标赋权的灵活性.

2 虚拟网络映射模型与评价指标

2.1 网络映射模型

2.1.1 底层物理网络

底层物理节点与链路分别用与表示，底层物理网络用带权无向图表示.可用CPU资源、地理位置约束为物理节点的属性；物理链路的属性为可用带宽资源.

2.1.2 虚拟网络

虚拟节点与链路分别用Nv与Ev表示，虚拟网络用带权无向图Gv=(Nv，Ev)表示，CPU资源需求cpu(nv)和地理位置需求loc(nv)为虚拟节点nv的属性；虚拟链路ev的属性为带宽资源需求bw(ev).

2.1.3 虚拟网络映射

虚拟网络映射是在满足底层物理网络承载能力的基础上，将VN的节点和链路映射到SN中节点和链路的过程，主要分节点映射和链路映射两个阶段.图1所示为一个映射可行方案，a，b，c为虚拟节点，A，B，C，D为物理节点，节点的CPU资源需求和可用CPU资源分别用方框内的数字表示，带宽需求和可用带宽资源分别用实线上的数字表示，虚拟网络请求的节点映射方案为{a→A，b→D，c→C}，链路映射方{(a，b)→(A，D)，(a，c)→(A，C)，(b，c)→(D，C)}.

图1 虚拟网络映射示例

2.2 评价指标

2.2.1 映射成功率

虚拟网络的映射成功率可表示为：

(1)

其中，NUMvacpt与NUMvall分别表示T时间内已经映射成功的虚拟网络数和虚拟网络映射请求总数，δ为无限小的常数.

2.2.2 收益开销比

虚拟网络请求Gv=(Nv，Ev)在t时刻的收益R(Gv，t)与开销C(Gv，t)分别定义为：

(2)

(3)

其中，参数α、β分别表示节点与链路资源的权重参数，对于网络运营商来说收益和开销的计算是复杂的，因此可根据实际情况设置不同的值，本文在仿真环境中为了便于比较计算将参数都设置为1.hops(ev)为虚拟链路在物理链路上经过的跳数.

长期平均收益开销比可以反映物理网络资源的利用程度，定义为：

(4)

3 算法设计

3.1 节点特征指标提取

网络中每个节点都有着各自的特征，这些特征决定了节点在网络中的重要程度，在节点多指标排序的虚拟网络映射算法中，为了更加科学的对节点进行排序，提高映射效率，需要对网络节点提取相应的特征指标，从而更加全面的对节点资源进行描述.本文提取了以下4个节点特征指标.

3.1.1 节点计算资源

节点计算资源NCR(ni)用CPU资源表示，如式(5)所示.

NCR(ni)=cpu(ni)

(5)

具有较大计算资源的物理节点将更有可能承载资源需求较多的虚拟节点.随着虚拟节点的映射，此项资源也将随之更新.

3.1.2 节点邻接带宽资源

节点的邻接带宽资源即与节点相连的所有邻接链路带宽之和，反映了此节点可用的带宽资源，如式(6)所示.

(6)

式中，E(ni)为节点ni的邻接链路集合.

3.1.3 节点的度

节点的度指的是与该节点直接相连的节点数量，用DEG(ni)表示，对于一个有较多链路连接的节点，该节点可以拥有更多连通性，更有可能找到与其它节点之间较短的通路，如式(7)所示.

(7)

式中，Gn为网络中所有节点的集合，Aij表示节点ni和nj的关系，如果两个节点相邻则值为1，不相邻则值为0.

3.1.4 节点就近度

节点就近度能够反映节点在网络拓扑中的重要性，如式(8)所示.

(8)

(9)

在获得了节点的特征指标向量之后，为特征指标向量中的每一个元素赋予一个权重wNCR，wDC，wDEG，wCC，构造出节点的权重向量w(n)，如式(10)所示.

w(n)=[wNCR，wDC，wDEG，wCC]

(10)

将特征指标向量与权重向量的内积作为节点排序的依据，如式(11)所示.

W(ni)=a(ni)·w(n)

(11)

3.2 博弈论组合赋权模型

在虚拟网络映射中，节点权重向量的选取对映射结果有决定性的影响，然而使用单一方法确定权重向量难以避免片面性、独断性，为了提高权重向量赋值的科学性，本文采用博弈论组合赋权方法确定节点权重向量.

3.2.1 基本权重集

为了提高节点权重向量选择的科学性，可以使用L种方法获取权重向量，如此构造出一个基本权重向量集{ω1，ω2…，ωk}，k=1，2…L，本文采用熵值法和层次分析法2种方法获取基本权重向量集.

熵值法：熵值法通过指标的相对差异判断其对系统的影响程度，是一种客观赋权方法.

首先，根据节点特征指标向量，构建决策矩阵A，如式(12)所示.

A=[a(n1)，a(n2)…，a(nm)]T

(12)

其中，m是网络中节点的数目，a(ni)为节点的特征指标向量.

计算节点第j个指标的熵值为Ej，如式(13)所示.

j=1，2…，N

(13)

其中，aij为代表矩阵A中第i个节点，第j个指标的值，N为节点指标数量.

最终，确定指标权重wj，如式(14)所示.

(14)

层次分析法赋权：层次分析法能够将复杂的多目标问题分解成为层次结构来解决，本文将节点计算资源、邻接带宽资源、度和就近度指标作为一层分析，层次分析法的具体过程参考文献[13].

3.2.2 可能权重向量集

可能权重向量集是优化权重的基础，它由基本权重向量集构建而成，为优化权重提供了多样的选择，可能权重向量集里包含了我们需要的理想权重向量.记k个权重向量ωk(本文采用熵值法和层次分析法分别获取指标权重向量)的任意线性组合为：

(15)

3.2.3 博弈论组合赋权法

博弈论组合赋权的思想在于“协调冲突，利益最大化”，即尽量找到与各个基本指标权重向量之间偏差最小的向量，可以归结为对公式(15)中的线性组合系数∂k进行优化，从而使w和各个ωk的离差最小，有对策模型如式(16)所示.

(16)

求解该模型即可得到一个与基本赋权方法相协调、均衡的综合权重向量.

由矩阵的微分性质可得到式(16)最优化的导数为：

(17)

对应的线性方程组公式为：

(18)

式(18)求得的(∂1，∂2，…∂L)，有时并不能满足作为指标权重向量的系数，因此要进行归一化处理，如式(19)所示.

(19)

4 GTCW-VNE算法实现

本节设计了GTCW-VNE启发式算法求解节点多指标排序的虚拟网络映射问题.GTCW-VNE算法在节点映射阶段，对虚拟节点和物理节点分别计算节点特征指标向量与权重向量的内积，并作为节点排序的依据，链路映射采用k-最短路径算法.GTCW-VNE算法节点映射步骤如下：

输入：Gs，Gv

输出：NodeEmbeddingList

1. 根据网络环境运用层次分析法获取节点指标权重向量

2. for虚拟网络中每一个虚拟节点nv∈Nv

4. 采用熵值法，运用公式(12)-公式(14)计算节点指标权重向量

5. 根据第1步和第4步得出的节点指标权重向量，运用公式(15)构造可能权重向量集合w

9. end for

11. 把虚拟节点映射次序存入链表VNodeList

13. do

15. 删除已经映射的候选节点

17. returnNODE_EMBEDDING_FAILED

18. else

21. end for

23. 更新已映射物理节点集合OSNode

24. end if

25. end for

26. return NODE_EMBEDDING_SUCCESS

5 性能评估与分析

5.1 仿真环境

仿真实验中的底层物理网络和虚拟网络请求采用改进Salam网络拓扑随机生成算法生成.底层物理网络在1000×1000范围内生成均匀分布的100个节点，节点间的链路连接概率为0.5.物理节点的CPU资源和物理链路的带宽资源均服从[50，100]的均匀分布，虚拟网络请求服从泊松分布，每100个时间单元的到达个数期望为5.虚拟网络的生存时间服从指数分布，期望为1000个时间单元，节点的数目服从[2，10]的均匀分布，CPU资源需求服从[10，50]的均匀分布，虚拟链路带宽资源需求服从[10，30]的均匀分布，将虚拟节点的位置约束设置为500.依照文献[11]的节点指标权重赋值思想，结合本实验环境，设置层次分析法赋权的判断矩阵如表1所示.

表1 判断矩阵及指标权值

仿真实验运行50000个时间单元，进行10次，将平均值作为最终结果以降低随机因素的影响.

5.2 算法的对比评价

本节在相同的实验条件下，设置不同的场景，从映射成功率、长期平均收益开销比两方面对比分析GTCW-VNE算法与其它3种算法(见表2)的性能.

表2 算法对比表

图2是4种不同虚拟网络映射算法映射成功率随时间变化的曲线，可以看出，TA-SVNE算法的映射成功率最低，保持在0.62左右，主要是因为其指标权重的选择过于主观片面，PSODD-VNE算法采用粒子群优化算法，针对特定的评价指标(长期平均收益开销比)进行多轮训练，不断更新各个粒子对应的权重向量参数，实现排序结果优化，但是其指标选择较为片面，并且没有考虑虚拟节点拓扑属性，因此映射成功率较低，保持在0.70附近，EAJTA-VNE算法不仅综合考虑了节点CPU资源、邻接链路带宽以及就近度3个指标，还采用加权相对熵的方法对具有多个指标的节点进行量化处理，并且能够根据环境的变化，赋予节点指标不同权值，其映射成功率保持在0.72附近，本文提出的GTCW-VNE算法，综合考虑了节点CPU资源，邻接链路带宽，节点的度和就近度4个指标，利用博弈论组合赋权法对熵值法和层次分析法产生的指标权重进行平衡，综合了主观赋权法和客观赋权法的优点，因此获得了更好的效果，其映射成功率最高，保持在0.74左右.

图3比较了4种算法的长期平均收益开销比.TA-SVNE算法因为映射成功率最低，收益开销比明显低于其它三种算法，稳定后为0.4左右，PSODD-VNE算法以平均收益开销比作为优化目标来计算指标权值，但是对虚拟节点进行排序时仅考虑了资源属性，并且提取的底层节点部分指标代表性不强，导致资源开销较大，所以长期平均收益开销比较低，稳定后维持在0.48附近，EAJTA-VNE算法考虑了节点CPU资源、邻接带宽资源和就近度等属性，针对网络环境变化对指标权重适当进行了调整，并且采用加权相对熵的节点排序方法实现了拓扑联合感知，其收益开销比较高，稳定后为0.5左右，而本文提出的GTCW-VNE算法全面考虑了节点的资源与拓扑属性，综合了主观与客观因素对指标权重的影响，获得了最优的权重向量，提高了收益开销比，稳定后为0.51左右.

图2 映射成功率

Fig.2 Acceptance ratio

图3 长期平均收益开销比

Fig.3 Long-term average revenue to cost ratio

本节在特定网络环境下比较分析了4种映射算法的性能，但现实中虚拟网络请求是多样化的，并且对节点资源的需求各异，本节设置了两种不同的虚拟网络请求场景以比较4种算法在不同场景之下的性能.

场景1.本组实验模拟4种虚拟网络映射算法在不同CPU需求情况下的性能差异.虚拟网络CPU需求服从[0，q]的均匀分布，其中，q为虚拟网络CPU需求上限，带宽需求服从[10，30]的均匀分布.当CPU需求上限q在[30，50]之间时，层次分析法的判断矩阵设置如表3所示.

表3 判断矩阵及指标权值

当CPU需求上限q在[50，70]之间时，层次分析法的判断矩阵如表4所示.

表4 判断矩阵及指标权值

从图4和图5可以看出，随着CPU需求的增大4种映射算法的映射成功率均有所下降，GTCW-VNE算法的映射成功率最高且收益开销比也优于其它算法.前期由于虚拟网络CPU资源需求较少，带宽需求对于映射成功率影响较大，因此利用层次分析法适当增大带宽资源的指标权重，优先映射链路带宽资源丰富的区域，后期随着CPU资源需求的增大，因此对映射成功率影响也越来越大，利用层次分析法适当增大CPU资源的权重，可以提高映射效率.从表3、表4可以看出随着节点资源属性权重的调整，拓扑属性权重也随之增加，这有利于减少链路映射跳数，节约资源开销，提高了收益开销比.GTCW-VNE算法因为可以根据网络环境的变化利用博弈论组合赋权法综合主客观赋权方法的优点，对权重向量进行自适应的调整，因此性能始终最优.

图4 不同CPU需求时映射成功率

Fig.4 Acceptance ratio for different CPU requirements

图5 不同CPU需求时长期平均收益开销比

Fig.5 Long-term average revenue to cost ratio for different CPU requirements

场景2.本组实验模拟虚拟网络映射算法在不同带宽需求下的性能.虚拟链路带宽需求服从[10，p]的均匀分布，p为链路带宽需求分布的上限，节点CPU需求服从[0，50]的均匀分布.当带宽需求上限p在[20，30]之间时，层次分析法的判断矩阵如表4所示，当带宽需求上限p在[30，40]之间时，层次分析法的判断矩阵如表3所示.

图6 不同带宽需求时映射成功率

Fig.6 Acceptance ratio for different bandwidth requirements

图7 不同带宽需求时长期平均收益开销比

Fig.7 Long-term average revenue to cost ratio for differ-ent bandwidth requirements

从图6和图7可以看出，随着虚拟链路带宽需求的增加，4种映射算法的映射成功率和收益开销比均有一定的下降，主要是因为随着带宽需求的增加而底层网络带宽资源的承载能力有限，导致部分链路映射开销过大或者映射失败.而本文提出的GTCW-VNE算法，因为考虑了更多的节点拓扑属性，并且根据带宽需求的变化对带宽资源的权重进行了相应的调整，因此映射效率优优于其它算法.通过2组实验可以发现，虚拟网络资源需求的改变对算法映射性能有着较大的影响.GTCW-VNE算法因为结合了主观赋权法和客观赋权法的优势，避免了其它三种算法的局限性、片面性，因此相比其它算法效果更好.

6 结束语

本文针对节点多指标排序的虚拟网络映射算法在指标权重确定中存在的片面性和局限性问题，提出一种博弈论组合赋权的虚拟网络映射算法.首先提取网络节点的各项特征指标，并进行归一化处理，组成特征指标向量，建立对节点资源情况的全面掌握，其次引入指标权重向量，利用熵值法和层次分析法构建基本权重向量集，然后利用博弈论组合赋权法，对基本权重向量进行均衡处理，以获取最优权重向量并对节点进行排序，最后依据排序结果进行节点映射，采用k-最短路径算法进行链路映射.仿真结果表明GTCW-VNE算法能够灵活适应网络环境变化，优化节点排序，相比于其他算法提高了虚拟网络映射成功率和收益开销比.下一步将结合安全虚拟网络映射进行研究.