1.   引言

网络虚拟化^[1—4]是一种可以在底层物理网络上创建多种异构虚拟网络的技术。虚拟网映射是指：通过映射算法将虚拟网络部署在能满足其约束条件的底层网络上。其中，请求接受率和节能是映射过程中两个重要的指标。前者代表了虚拟请求的接受情况，如何将有限资源高效分配，以映射更多的虚拟请求是虚拟网映射过程中要重点考虑的问题。后者代表系统的能耗量，由于高功耗不仅导致运行维护成本增加，而且带来大量碳排放，加剧温室效应。因此如何有效地租用资源，降低开销，提高收益，已成为亟待解决的问题。但两者之间存在资源竞争关系，仅考虑节能会影响虚拟网构建成功率，一味追求请求接受率又会影响网络资源利用率。

国内外研究主要集中于优化单一目标以获得最优解。例如通过设置反馈系统，找到稳定的处于活跃状态的底层资源子集，然后将虚拟网映射到该区域中，以增加休眠节点和链路数量，从而降低能耗^[5]。又如利用启发式算法为底层资源设置优先级，已有的被激活的底层节点和链路拥有更高的优先权，通过优先权的设置将虚拟资源映射在较小的子集中^[6]。在内容分发网络CDN中^[7]，为了解决能源成本问题，提出一种成本感知容量配置算法，动态规划多个ISP中CDN服务器集群的服务容量，并优化其在能量消耗和跨ISP流量方面的总体运营成本。在解决云计算网络的虚拟网节能映射问题中^[8]，通过建立混合整数线性规划模型，整合网络和数据中心的资源来实现节能。通过建立整数线性规划公式^[9]，以最小化每个虚拟请求的电力成本，解决灵活栅格光网络中的虚拟网映射节能问题。在无线网络虚拟化中的节能问题中^[10]，通过使用随机优化和Lyapunov优化方法来解决跨层优化问题，进而到达节能效果。

此类方法虽能降低能耗，但其主导思想是通过关闭尽可能多的底层设备达到节能的目的，这将会使业务载荷过于集中在某些节点和链路上，导致“热点”和“瓶颈”出现，进而影响请求接受率。同样地，在以提高请求接受率为目标的算法中，主要关注底层网络的效用问题，忽略底层网络能耗，从而造成不必要的能量消耗。因此，如何对节能和请求接受率进行权衡是虚拟网映射过程中的重大挑战。

现有的解决多目标问题的方法主要集中在两个方面：数学规划法和智能优化算法。数学规划法通常将多目标问题转化为单目标问题^[11]，其中各个目标间的权重往往无法明确给出，因此这类方法应用起来有一定局限。智能优化算法多集中于粒子群多目标优化算法^[12]，此类算法容易陷入局部最优且存在映射时间过长的问题。基于此，本文使用纳什议价理论来权衡节能和请求接受率间的关系，避免目标间权重的选择，找到全局最优。提出一种基于纳什议价博弈的虚拟网多目标映射算法(Multi-Objective Virtual Network Embedding algorithm based on Nash Bargaining, MOVNE-NB), 将虚拟网映射问题建模成一个纳什议价过程，把请求接受率和节能看作两个参与人，通过求解纳什议价解，得到一个兼顾全局最优及公平的虚拟网映射方案，在确保两指标公平性的同时提高虚拟网映射的整体性能。

2.   相关知识

在网络虚拟化环境中，考虑到要解决对抗冲突中最优解的问题，选取纳什议价理论对请求接受率和节能进行优化。纳什议价是一个经典的合作博弈框架^[13,14]，主要研究具有资源冲突的参与人间的策略选择及均衡问题。通过具有约束力的谈判规则使博弈各方的利益都有所增加，达到共赢。在保证谈判过程中公正性的同时获得一个帕累托有效解，保证全局最优。对于此类问题，有纳什公理：帕累托有效性、对称性、等价收益不变性、无关选择独立性。纳什证实了在满足以上4条公理的条件下，此问题拥有唯一合作解${x_0} = \arg\mathop {\max}\nolimits_x \left[ {{f_1}\left( x \right) - {d_1}} \right]$·$\left[ {{f_2}\left( x \right) - {d_2}} \right]$，该解落在帕累托前沿上，且可实现博弈结果的全局利益最大化及公平性。其中，f₁, f₂是博弈双方的收益函数，(d₁, d₂)表示博弈双方可能得到的最差收益，称为“谈判协议的最佳替代”(Best Alternative To a Negotiated Agreement, BATNA)^[15]。

3.   基于纳什议价的多目标映射算法

3.1   模型构建

3.1.1   网络模型构建

(1)虚拟网映射请求接受率模型：最大化请求接受率需最大化成功映射的虚拟节点和虚拟链路。因此，将该问题建模成

其中，${f_n} = f_j^u \cdot \left( {\displaystyle\sum\nolimits_{\forall u \in {N^{_{^V}}}} {{\rm{ReqCPU}}\left( u \right)} } \right)$, ${f_l} = f_{{{jk}}}^{{{uw}}}$$\cdot \left( {\displaystyle\sum\nolimits_{\forall {l_{jk}} \in {L^S}} {{\rm{ReqBWL}}\left( {{l_{{{uw}}} }} \right)} } \right)$。式(2)，式(3)为容量约束，ReqCPU(u)表示虚拟节点u的CPU资源请求量，CPU(j)表示物理节点j的CPU资源总量；ReqBWL(l_uw)表示虚拟链路l_uw的带宽资源请求量，BWL(l_jk)表示物理链路l_jk的带宽资源总量。式(4)限制一个虚拟节点只能映射到一个底层节点，若虚拟节点u成功部署在底层节点j上，则f_j^u=1；否则f_j^u=0。式(5)表示相同虚拟节点不能映射到同一底层节点，NNo为虚拟网络节点数量。式(6)为变量约束，若虚拟链路l_uw成功部署在底层链路l_jk上，则$\mathop {{f}}\nolimits_{{{jk}}}^{{{uw}}}$=1否则$\mathop {{f}}\nolimits_{{{jk}}}^{{{uw}}}$=0。

(2)虚拟网映射节能模型：虚拟网节能映射的目标是最小化能耗。其能耗由节点及链路共同组成。因此，将节能问题建模成

其中，${g_n} = f_j^u \cdot \left( {{p_b} + {p_l} \cdot u} \right)$。p_b为服务器空载时的基本功耗，p_m为服务器的满载功耗，${p_l} = {p_m} - {p_b} \cdot u$为处理器利用率。${g_l} = f_{{{jk}}}^{{{uw}}} \cdot {p_n}$, p_n为基本能耗。约束条件同请求接受率模型。

3.1.2   纳什议价模型构建

根据纳什公理以及请求接受率和节能模型^[16]可以建立基于纳什议价的虚拟网映射模型，设a_AAR和a_EER分别为请求接受率和节能的BATNA，则将纳什议价优化问题建模成

其中，两个参与人都可以通过改变自己的BATNA来改进自身利益。参与人操纵BATNA的过程如图1所示。其中P为BATNA，坐标为(a, b)。$(y - b)/(x - a) = k/h$为纳什方程，表示将剩余(即总价值减去参与人最后底线后所得到的剩余价值)v–a–b以h/k的比例分配给谈判者。所有将剩余分配完的点(x, y)都落在由点(v, 0)和(0, v)确定的直线x+y=v上。此时，点Q就是纳什均衡解。若参与人A为了提高利益将BATNA移至P₁，则从此时的纳什解为Q′，意味着有利于A，而不利于B。因此，当参与人操纵其BATNA向右下方移动时将会提高自身利益而损害对方利益。从而导致最终解的不公平甚至议价失败。

图 1  参与人操纵BATNA的过程

下载: 全尺寸图片 幻灯片

3.2   公平议价机制

根据3.1节分析，为了避免解的不公平或者议价失败，本节设置公平议价机制保证议价公平进行。首先根据定理1找到可以达到帕累托有效解的初始BATNA，由式(9)计算出目标，每个参与人由定理2改变自身的BATNA，在纳什议价的框架下经过多次迭代得到到达帕累托前沿的最优BATNA。进而得到请求接受率和节能的最优目标。则有以下定义。

定义 1　最优最差目标：若$\left( {{x_{{\rm{AAR}}_n}}, {x_{{\rm{AAR}}_l}}} \right)$和$\left( {{x_{{\rm{EER}}_n}}, {x_{{\rm{EER}}_l}}} \right)$分别是请求接受率和节能的最优解，那么请求接受率最优目标和最差目标分别定义为${\rm{AAR}}_b = \displaystyle\sum\nolimits_n {{f_n}\left( {{x_{{\rm{AAR}}_n}}} \right)} + \displaystyle\sum\nolimits_l {{f_l}\left( {{x_{{\rm{AAR}}_l}}} \right)}$, ${\rm{AAR}}_w =$$\displaystyle\sum\nolimits_n {{f_n}\left( {{x_{{\rm{EER}}_n}}} \right)} + \displaystyle\sum\nolimits_l {{f_l}\left( {{x_{{\rm{EER}}_l}}} \right)}$。

同样地，节能最优目标和最差目标分别为${\rm{EER}}_b =\displaystyle \sum\nolimits_n {{g_n}\left( {{x_{{\rm{EER}}_n}}} \right)} + \displaystyle\sum\nolimits_l {{g_l}\left( {{x_{{\rm{EER}}_l}}} \right)}$, ${\rm{EER}}_w =$$\displaystyle\sum\nolimits_n {{g_n}\left( {{x_{{\rm{AAR}}_n}}} \right)} + \displaystyle\sum\nolimits_l {{g_l}\left( {{x_{{\rm{AAR}}_l}}} \right)}$。

在迭代开始时，需要设置初始BATNA，初始值的好坏将决定议价是否成功。因此，初始BATNA的设置十分重要，则有定理1。

定理 1　假设请求接受率和节能的代价方程是连续的，那么BATNA$\left( {{\rm{AAR}}_w, {\rm{EER}}_w} \right)$将会产生一个公平的议价结果。

证明　令${x^*} = \left( {x_n^{*},x_l{^*}} \right)$是式(10)中BATNA为$\left( {{\rm{AA}}{{\rm{R}}_w},{\rm{EE}}{{\rm{R}}_w}} \right)$的情况下的最优化方法。在此情况下的请求接受率和节能的目标分别为sAAR和sEER。假设存在纳什议价问题$\left( {s',d{\, '}} \right)$，令：$s{{\rm{'}}\!\!_{{\rm{AAR}}}} \!=\! \alpha \!\cdot \!{s_{{\rm{AAR}}}} \!\!+\! \!\beta$, $d{{\, '}\!\!_{{\rm{AAR}}}}{\rm{ }} = \alpha \cdot {d_{{\rm{AAR}}}} + \beta$，其中，$\alpha = \displaystyle\frac{{{\rm{EE}}{{\rm{R}}_w} - {\rm{EE}}{{\rm{R}}_b}}}{{{\rm{AA}}{{\rm{R}}_w} - {\rm{AA}}{{\rm{R}}_b}}}$, $\beta = \displaystyle\frac{{{\rm{EE}}{{\rm{R}}_b} \cdot {\rm{AA}}{{\rm{R}}_w} - {\rm{EE}}{{\rm{R}}_w} \cdot {\rm{AA}}{{\rm{R}}_b}}}{{{\rm{AA}}{{\rm{R}}_w} - {\rm{AA}}{{\rm{R}}_b}}}$。$s{'\!_{{\rm{AAR }}}}$和$s{'\!_{{\rm{EER}}} }$分别表示问题$\left( {s', d{\, '}} \right)$中请求接受率和节能的目标，因此，${\rm{AAR}}{'\!_w} = {\rm{EER}}'\!_w$, ${\rm{AAR}}{'\!_b} = {\rm{EER}}{'\!_b}$。令$\left( {y_{{\rm{AAR}}} },\right.$$\left.{y_{{\rm{EER}}} } \right)$为$\left( {s', d'} \right)$的一个可行集，则有$\displaystyle\sum \left[ \alpha \cdot \left( \displaystyle\sum\nolimits_n \!\!\!{g_n} +\right.\right.$$\left.\left.{\displaystyle\sum\nolimits_l \!\!{{g_l}} } \right) \!+\! \beta \right] \!=\! {y_{{\rm{EER}}} }$和$\displaystyle\sum\! {\left[ {\alpha \!\cdot\!\left( {\displaystyle\sum\nolimits_n \!\!{{f_n} \!+\! \displaystyle\sum\nolimits_l \!\!{{f_l}} } } \right) + \beta } \right] }$$= {y_{{\rm{AAR}}} }$，由于$\displaystyle\sum\nolimits_n \!\!{{g_n} + \displaystyle\sum\nolimits_l \!\!{{g_l}} }$和$\displaystyle\sum\nolimits_n \!\!{{f_n} + \displaystyle\sum\nolimits_l \!\!{{f_l}} }$是连续函数，该方程一定有解。意味着$\left( {{y_{{\rm{AAR}}} }, {y_{{\rm{EER}}} }} \right)$是$\left( {s', d'} \right)$的一个可行结果。因此，一定有$s{'\!_{{\rm{EER}}} }$=$s{'\!_{{\rm{AAR}}} }$。根据纳什议价模型的等价收益的不变性可知

由式(11)和式(12)可得

同理，由式(10)和式(12)，可得

由式(13)和式(14)可得

综上所述，定理1给出了一个初始BATNA可以在请求接受率和节能模型之间产生一个公平的交易。 证毕

初始BATNA设置成功后，在迭代过程中，对于BATNA的更新有定理2。

定理 2　令$\left( {a_{{\rm{AAR}}}^{\left( k \right)},a_{{\rm{EER}}}^{\left( k \right)}} \right)$为第k次迭代的BATNA，初始化BATNA为$\left( {{\rm{AAR}}_w, {\rm{EER}}_w} \right)$，则每个参与人的BATNA更新应遵守以下BATNA改变方程

证明　在本博弈中，请求接受率第1个回合的BATNA为w₁=AAR_w。如果节能的利益${{π}}$超过2AAR_w，则节能接受AAR_w，否则拒绝AAR_w。若是首次谈判的BATNA无法通过，则请求接受率对节能的利益预测为均匀分布[0, ${π}$]，此时第2个回合要求的BATNA为w₂=1/2${{π}}$。如果节能的利益${{π}}$超过w₂，则接受BATNA，否则继续拒绝。利用逆向归纳法，如果在第1个回合中，节能已经拒绝了请求接受率的BATNA，拒绝的收益为0，则第2个回合的谈判是节能最后的机会。因此当且仅当${{π}}$>w₂时，节能的选择策略为接受，而无论第1个回合的w₁值为多少，此时节能的利益总是大于零。而在第2个回合中，节能推断请求接受率的利润是标准分布于[0, ${{π}}$]。因此，节能选择的w₂要使自己的利益最大化，即：$\max\left( {{w_2} \cdot {p_{2a}} + 0 \cdot {p_{2r}}} \right)$，其中p_2a和p_2r分别是节能接受和拒绝w₂的概率。于是上述最大值问题变为：$\max\left[ {{w_2}\left( {{{\left({p_1} - {p_2}\right)}}/{{{p_1}}}} \right)} \right]$，节能第2个回合的最优BATNA为${w_2} = {{{p_1}}}/{2}$，此时双方的最大收益为：请求接受率$\delta {{{\pi _1}}}/{2}$，节能$\delta {{\left(\pi -{\pi _1}\right)}}/{2}$。因此，对于节能来说，已知谈判进行到第2回合时所能得到的最大利益。所以首次谈判节能如果选择接受${w_1}$，则必须满足$\pi -{w_1} \ge \delta{{\left(\pi - {\pi _1}\right)}}/{2}$，整理得${w_2} \!\ge\! {w_1} \!+\! \left( {\left({{\delta - 2}}\right)/{2}} \right)\pi$。综上所述，在初始BATNA为(EER_w, AAR_w)时，可推出定理2的BATNA改变方程。 证毕

在多次迭代后，根据纳什公理，此博弈将达到一个趋于帕累托前沿^[13]的有效解。

3.3   基于纳什议价的虚拟网映射算法

基于以上求得的纳什议价解，虚拟网映射算法如下：

算法 1　MOVNE-NB

(1)对于每个虚拟节点，找出满足其资源请求的物理节点集合；对于每条虚拟链路，找出满足其资源请求的物理链路集合；

(2)对于CPU_i, BWL_i, cpu_i, bwl_i，由式(1)和式(8)计算请求接受率和节能的最优目标；

(3)根据更新方程依次更新a_k及b_k的值；

(4)由目标式(9)计算博弈结果；

(5)返回AAR, EER, |V_i|, |V_l|, |S_i|, |S_l|的值；

(6)按资源请求量大小降序排列虚拟节点：$n_i^v$, i=1, 2, ···, V_i，得到虚拟节点$n_i^v$的可映射物理节点集合；

(7)遍历候选集合：如果未找到满足条件的物理节点，则返回节点映射失败标志；否则挑选S中消耗资源$A({n^v})$最大的虚拟节点$n_{\max}^v$，若满足$C_N^V \le C_N^S$，则将$n_{\max}^v$映射到$n_{\max}^s$上，即${F_N}(n_{\max}^v) =$$n_{\max}^s$，更新$n_{\max}^s$的剩余资源。//按资源从大到小排序进行节点映射；

(8)按资源请求量大小降序排列虚拟链路：$l_i^v$, i=1, 2, ···, V_l；

(9)对于每条虚拟链路：如果最短路径不存在，返回链路映射失败标志；否则获取虚拟链路$l_i^v$两端的虚拟节点$n_b^vi$和$n_e^vi$，得到虚拟链路$l_i^v$的可映射链路集合。选择H中带宽资源最大的虚拟链路$l_{\max}^v(n_b^vi, n_e^vi)$。使用k-最短路径算法连接$l_{\max}^v(n_b^vi,$$n_e^vi)$，若路径$l_{\max}^s(n_b^si, n_e^si)$满足带宽约束$C_L^V \le C_L^S$，则将$l_{\max}^v(n_b^vi, n_e^vi)$映射到$l_{\max}^s(n_b^si, n_e^si)$上，即${F_L}(l_{\max}^v) = l_{\max}^s$；

(10)返回MAP_SUCCESS标志。

由上述流程可知，该算法第(1)步时间复杂度与物理节点和物理链路的个数有关，为O($\left\|S_i\right\|$+$\left\|S_l\right\|$)。第(3)步迭代过程的时间复杂度与a_k和b_k有关，即O($\left\|a_k\right\|$+$\left\|b_k\right\|$)，第(6)步及第(7)步的时间复杂度为O($\left\|S_i\right\|$$\left\|V_i\right\|$$\left\|V_i\right\|$${\rm log}\left\|V_i\right\|$)，第(8)步排序算法，第(9)步链路映射过程中，k-最短路径算法时间复杂度为O($\left\|S_i\right\|{\rm log}$$\left\|S_i\right\|+k$$\left\|S_i\right\|$$\left\|S_l\right\|$)，因此链路映射过程的时间复杂度为O($\left\|V_l\right\|{\rm log}\left\|V_l\right\| + \left\|V_l\right\|$$\left\|S_i\right\|{\rm log}\left\|S_i\right\|+\left\|V_l\right\|k\left\|S_i\right\|+\left\|V_l\right\|\left\|S_l\right\|$)。其中，$\left\|V_i\right\|$和$\left\|V_l\right\|$分别为虚拟网请求的节点个数和链路个数。$\left\|S_i\right\|$和$\left\|S_l\right\|$分别为底层网络映射集合节点个数和链路个数。

4.   实验

4.1   实验环境

实验所用PC参数如下，CPU: 3.4 GHz，内存：4 G。用GT-ITM^[17]模型和NS2软件生成底层物理网络和虚拟请求的拓扑结构。实验设计同文献[16]，底层网络节点数为100，节点相互之间连接的概率为0.5，底层物理网络和虚拟网资源分布情况为：(1)底层物理节点CPU资源量的值分布区间为[50, 100]，且服从均匀分布。(2)底层物理链路带宽资源量的值分布区间为[50, 100]，且服从均匀分布。(3)虚拟节点CPU资源请求量的值分布区间为[0, 14]，且服从均匀分布。(4)虚拟链路带宽资源需求量的值分布区间为[0, 34]，且服从均匀分布。平均100个时间单元可到达20个虚拟网请求，且服从泊松分布。虚拟网请求总个数为2000个，运行时间单元个数约为14000个。节点和链路能量消耗中常量值设置同文献[18]: P_l = 150, P_b = 150, P_n = 15。

4.2   结果分析

(1)公平性分析：首先判定公平性，如果S_AAR和S_EER是本方案得到的解所对应的请求接受率和节能目标，当且仅当满足式(18)时

此时，所得到的解是公平的。即请求接受率和节能的优化率相同，在博弈过程中的让步率相同。记为PIWOS(Performance Improvement in the Whole Optimization Space)，代表此目标的性能优化率。

为了验证公平性，设计实验与传统的解决多目标优化方法：聚合目标函数(Aggregate Object Function, AOF)^[19]和$\varepsilon$约束法($\varepsilon$-Constraint Methed, $\varepsilon$-CM)^[20]作对比。

在AOF方法中，建造聚合函数：$\alpha \cdot {\rm{AAR}}_b \cdot {s_{{\rm{EER}}} } +$$\beta \cdot {\rm{EER}}_b \cdot {s_{{\rm{AAR}}} }$。其中，$\alpha$代表请求接受率的权值，$\beta$代表节能的权值，$\alpha$+$\beta$=1。在AOF中为($\alpha$, $\beta$)选取不同的值：AOF(0.2, 0.8), AOF(0.5, 0.5), AOF(0.8, 0.2)。

在$\varepsilon$-CM方法中，(1)令请求接受率为优化目标，节能为约束条件，记为$\varepsilon$-CM(AAR)，即${\rm{EER}} < 0.95 \cdot {\rm{EER}}_w$。(2)令节能为优化目标，请求接受率为约束条件，记为$\varepsilon$-CM(EER)，即${\rm{AAR}} < 0.95 \cdot {\rm{AAR}}_w$。

图2表明不同的方法对于节能和请求接受率的优化程度不同，MOVNE-NB在权衡两目标的公平性上有较为明显的优势。MOVNE-NB的PIWOS值为(0.7355, 0.7355)，表明请求接受率和节能在各自的优化空间上得到了相同程度的优化。而AOF(0.2, 0.8)的PIWOS值为(0.5587, 0.8353)，表示在节能和请求接受率的系数设为0.2和0.8时更倾向于优化请求接受率。当其系数设为0.5和0.5时，即AOF(0.5, 0.5)时，PIWOS值为(0.9068, 0.3687)，此时的结果表明优化结果偏向于节能。AOF(0.8 0.2)的PIWOS值为(0.9983, 0.0129), $\varepsilon$-CM(AAR)的PIWOS值为(0.4311, 0.8827)，都存在优化程度不公平的问题。在优化过程中优化其中一个目标后忽略了另一个目标的性能，导致最终的优化结果相差过大。其中$\varepsilon$-CM(EER)没有得到可行方法。因此，运用本文算法可以避免权值的选择，得到的映射方案既保证了公平性，又在最大程度上保证了两者的优化程度。

图 2  公平性对比

下载: 全尺寸图片 幻灯片

(2)映射结果分析：本文选取文献[5]的EA-FB, PR-FB算法及文献[6]的EH_Alg算法进行对比实验。图3图4表明与EA-FB, PR-FB和EH_Alg算法相比，MOVNE-NB算法的平均节点开启量分别降低5.1%, 7.3%和9.6%。平均链路开启量分别降低2.4%, 2.6%和4.6%，这是由于MOVNE-NB算法经过纳什议价的处理后，在保证请求接受率的情况下节能，尽可能使处于激活状态的节点和链路数降低。图5表明与EA-FB, PR-FB和EH_Alg算法相比系统能耗分别降低10.8%, 10.2%和12.5%。这是由于开启的节点和链路数量越少，底层网络能耗越低。图6表明MOVNE-NB算法的收益成本比有所提高。这是由于收益成本比受链路映射影响，其值与承载虚拟链路的物理路径长度成反比。而EA-FB, PR-FB和EH_Alg算法以节能为目标，力求将虚拟请求映射在相对较小的底层网络集合中，这样必定会导致其中部分链路资源利用率过高，使承载虚拟链路的底层链路过长，进而使收益成本比的下降幅度加大。图7表明EA-FB, PR-FB和EH_Alg算法的请求接受率均呈下降趋势，MOVNE-NB算法在运行10000个时间单位后有回升的趋势。这是由于EA-FB, PR-FB和EH_Alg算法以节能为目标，在不考虑请求接受率的情况下，将业务量过于集中在较小拓扑中，从而导致底层网络“瓶颈”的出现，影响请求接受率。而MOVNE-NB算法综合考虑节能和请求接受率，在两者间寻找较好的平衡。图8表明运行22000个时间单位后，EA-FB, PR-FB, EH_Alg和MOVNE-NB算法的映射时间分别为123 s, 120 s, 94 s, 120 s。与EH_Alg算法相比，MOVNE-NB算法的运行时间有所增加，EH_Alg算法在对节点优先级进行排序时，选取节点CPU资源、剩余CPU资源以及是否为开启状态为考量标准，其时间复杂度仅与节点总数，邻居节点数和链路总数有关。而EA-FB, PR-FB和MOVNE-NB算法在选取节点时，都利用迭代算法寻找映射集合后再对节点排序，因此映射时长有所增加。

图 3  平均节点开启量

下载: 全尺寸图片 幻灯片

图 4  平均链路开启量

下载: 全尺寸图片 幻灯片

图 5  系统能耗量

下载: 全尺寸图片 幻灯片

图 6  平均收益成本比

下载: 全尺寸图片 幻灯片

图 7  请求接受率

下载: 全尺寸图片 幻灯片

图 8  算法运行时间

下载: 全尺寸图片 幻灯片

5.   结束语

本文综合考虑请求接受率和节能的性能，首次将纳什议价模型运用到虚拟网映射问题上，提出一种基于博弈论纳什议价模型的虚拟网映射算法(MOVNE-NB)，利用谈判技术权衡虚拟网映射过程中请求接受率和节能两个指标的性能。实验表明本文算法不仅能产生一个帕累托有效解，同时保证了全局最优及公平性，进而提高了映射综合质量。虽然将博弈论引入虚拟网中，在保证请求接受率的情况下达到了节能的效果，但在节能方向上，还有深入研究的空间。因此，下一步将继续在节能方向上展开工作，深入挖掘其他更加契合的映射算法。