基于负载均衡的无线虚拟网络映射算法

高旗，吕娜，缪竞成

（空军工程大学 信息与导航学院，西安 710077）

0 引言

为了满足无线网络用户多样化的业务需求，具有紧密耦合架构的无线网络只能基于已有的设备和服务进行更新，而堆叠式的更新部署使得无线网络出现结构冗余、发展困难的僵化问题［1］。

无线网络虚拟化（Wireless Network Virtualization，WNV）是解决无线网络僵化问题的有效方式［2］，基本思想是解耦，通过统一的资源调度和网络管理为用户提供差异化网络服务。无线网络虚拟化将无线网络抽象为基础设施提供商（Infrastructure Provider，InP）和服务提供商（Service Provider，SP）。其中InP 负责底层物理网络的管理和资源分配，SP 负责租赁使用资源为用户提供服务，所有的SP 均向一个InP 请求网络资源，实现资源共享。

在无线网络虚拟化过程中，虚拟网络映射（Virtual Network Embedding，VNE）是其中的重要手段［3］，解决如何将InP 的网络资源分配给不同的SP 进而提供服务的问题。映射过程主要包括节点映射和链路映射，因此将虚拟网络映射问题抽象为如何在满足约束条件的情况下，为虚拟网络选择合适的物理节点和链路。

相较于有线网络，无线网络链路资源有限且存在干扰，映射时需考虑干扰对资源分配以及服务质量（Quality of Service，QoS）的影响，因此无线虚拟网络映射算法主要针对优化资源分配［4-10］、提高链路可靠性［11-12］以及保证服务质量［13-17］等方面进行研究。文献［5］中将资源空间以卡诺图的形式进行划分，通过动态调整资源块的位置提高资源利用率。文献［6］中将拓扑势引入节点资源排序当中，在节点映射阶段综合考虑当前节点资源以及相邻链路资源，保证映射成功率。文献［18］中基于网络虚拟化中不同功能对资源的需求不同，设计了资源分级管理系统，有效减少总体映射时间。上述文献从资源优化的角度出发，通过改变资源排序方式或将资源分级映射来提高资源利用率，但并未考虑到无线网络中功率和带宽资源之间的互补性。

在无线虚拟网络映射中，功率和带宽资源具有互补性和替代性，为了实现负载均衡提高资源利用率，文献［19］中提出一种联合功率和带宽的映射算法WVNE-JBP（Wireless Virtual Network Embedding-Joint Bandwidth and Power），但所求映射方案较为单一，没有给出如何在功率、带宽资源富余度不同情况下的映射方案。

为了解决映射过程中功率和带宽资源使用不均衡的问题，合理调配富足资源进行映射，减少因其他资源短缺造成的映射失败，本文基于负载均衡原理提出一种联合资源分级的无线虚拟网络映射（Joint Hierarchical Resource Virtual Network Embedding，JHR-VNE）算法，在映射虚拟网络请求（Virtual Network Request，VNR）时综合考虑功率资源和带宽资源，通过修正系数将资源进行分级，使得物理网络在分配时侧重不同资源，提高资源利用率。本文主要工作为：

1）提出新的节点资源排序方式，综合考虑节点功率资源和相连链路平均带宽资源，利用权值系数对资源进行分级，在节点映射阶段预先选择具有不同资源侧重的节点；

2）改进成本函数，通过修正系数调整功率和带宽资源单位成本，在链路映射阶段进一步选择具有不同侧重的资源分配方案，提高虚拟网络请求接受率和资源利用率。

1 映射模型和问题分析

无线虚拟网络映射模型由物理网络和虚拟网络构成，分别表示基础设施提供商和服务提供商。

1.1 物理网络模型

1.2 虚拟网络模型

在映射时，物理网络分配根据虚拟网络请求分配一定的功率资源和带宽资源，满足虚拟网络对传输速率的需求。

其中：σ2是信道高斯白噪声；I(lS)是其他链路对当前映射链路造成的干扰；g(lV)是信道增益；dis()表示节点间距离；k为增益系数。

无线虚拟网络映射模型如图1 所示，虚拟网络中数字代表链路传输速率r(lV)，单位为Mb/s。物理网络中物理节点上方数字代表具有的功率资源p(nS)，单位为W；物理链路旁的数字代表具有的带宽资源b(lS)，单位为MHz。当物理节点和链路满足位置、资源约束条件后，即可映射相应的虚拟网络并提供服务。

1.3 约束条件

在映射过程中，同一个虚拟网络请求的不同虚拟节点不能映射到同一个物理节点上，且物理节点需在虚拟节点映射范围内，被映射的物理节点和链路需具有足够的资源，即满足式（3）～（6）。

式（5）～（6）表示物理网络在分配功率和带宽资源以满足虚拟网络对传输速率需求时，即式（1），分配给虚拟节点m的功率资源不能超过被映射物理节点n能提供的资源，分配给虚拟链路lV的带宽资源不能超过被映射物理链路lS能提供的带宽资源。

1.4 干扰模型

考虑到无线网络环境中，相邻链路间存在干扰，本文采用文献［19］中的链路干扰系数：

其中：dl为影响当前映射链路lS的干扰链路数目，γ为常数。链路干扰系数dI(lS) 在进行链路映射时作为权值用于选择最短路径。

式（1）中的干扰I(lS)，与链路间距离dis(lS，li)、链路两端节点功率p(nS)以及链路增益g(lS)相关，具体计算过程见文献［20］，公式如下：

1.5 评价指标

VNR 接受率为已映射的VNR 数量与所有VNR 数量的比值，反映算法的全局优化能力。

成本cost为反映底层网络为虚拟网络提供功率资源和带宽资源所付出的代价。

其中：α(nS)和β(lS)为权值系数。

资源利用率η反映算法在分配功率资源和带宽资源时的效率，其值为已分配的资源与总资源的比值。

2 JHR-VNE算法分析

2.1 节点资源排序及映射

在有线虚拟网络映射过程中，虚拟节点对资源的需求是相对固定的，如计算资源、内存等，而在无线虚拟网络映射中，由于虚拟网络的请求是针对传输速率，因此物理网络在分配资源时的原则如式（1）所示，物理节点所具有的功率资源和物理链路所具有的带宽资源均会影响映射成功率。

目前无线虚拟网络映射相关研究采用扩展节点资源的方式，将节点功率资源和与该节点相连的全部链路带宽资源综合计算进行排序，以寻找同时满足功率和带宽要求的节点，提高映射成功率。

该排序方式将节点相连的全部链路资源计算在内，但没有考虑到链路的实际映射能力。本文基于此提出一种新的节点资源排序方式，如式（12）所示：

其中：ε为权值系数；Num() 表示与节点nS相连的链路数量；加号右边表示与节点nS相连链路的平均带宽。相较于全部带宽，平均带宽更能表示链路资源的可用性。

不同于有线虚拟网络映射过程中物理网络为虚拟网络分配固定的计算资源或带宽资源，无线虚拟网络映射中，为满足虚拟网络不同的传输速率需求，受式（1）约束，在传输速率确定的条件下，物理网络可以动态选择分配虚拟网络的功率资源和带宽资源，由此导致可用的资源分配方案数量激增。

为实现资源的高效利用，采用式（12）节点资源排序方式，在节点映射过程中同时考虑可用链路资源，通过调整ε值预先将虚拟网络关于节点和链路资源的需求进行分类。在满足最低传输速率时，高ε值的虚拟网络会选择具有较多带宽资源的物理节点，低ε值的虚拟网络会选择具有较多功率资源的物理节点。映射时采用2.3 节的目标函数，前者求得的最优资源分配方案中消耗链路带宽资源较多而消耗节点功率资源较少，后者则相反。通过该分级策略使得节点和链路资源负载均衡，避免直接求解最优目标函数时所有虚拟网络对功率和带宽资源的需求比例相似，导致功率资源使用接近上限而带宽资源利用率低的情况。

2.2 链路映射

根据2.1 的节点资源排序方式选择可用节点，由于VNR对资源需求的侧重不同，在选择链路时同样综合考虑带宽资源和链路相连节点的功率资源。进行链路映射时，采用路径分离方法［21］，将传输速率r(lV) 分为i个相等的Δr，映射每个Δr均满足式（1）。为提高VNR 的映射数量和映射成功率，物理网络分配功率Δp(nV)和带宽资源Δb(lV) 仅满足最低传输速率要求，如式（13）所示，在考虑链路干扰的条件下采用最短路径进行链路映射。

2.3 目标函数

无线虚拟网络映射过程中，当满足虚拟网络所需的传输速率要求时，物理网络有多种方案分配功率和带宽资源，为提高资源利用率和映射数量，以最小化成本为目标函数，选择合适的功率和带宽资源进行映射。目标函数如式（14）所示，且满足约束条件式（1）、式（3）～（6）。

其中：α(nS)和β(lS)为权值系数，分别表示使用功率和带宽所需付出的代价，大小为单位资源成本，一般为可用资源的倒数。

为实现资源分级部署并提高利用率，将权值系数进行修正，改进后的成本如式（16）：

其中：λ为修正系数。δ代表VNR 的不同级别，δ小的VNR 所消耗的功率资源成本小，更倾向于使用大功率小带宽；δ大的VNR 所消耗的带宽资源成本小，更倾向于使用小功率大带宽。

结合式（13）和式（16），成本化简如下：

在满足约束条件（1）、式（3）～（6）的情况下，选择使得成本最小的功率Δp(nV)，即求解目标函数式（17）的极小值，使得Δp(nV)满足cost函数的导数为零。为减少解的搜索时间，设置功率定义域的最小值Δpmin为当Δb(lV)=b(lS)时（带宽为链路最大可用带宽）满足式（13）的功率值。若功率的极小值点不在定义域范围内，令Δp(nV)=ηp(nS)为最终映射功率，η为修正系数，再根据式（13）求得此时的带宽Δb(lV)，为当前VNR 的映射资源方案。

2.4 算法流程

JHR-VNE 算法为最大化利用功率和带宽，对映射资源进行分级，采用新的节点资源排序方式，使用改进的成本函数为目标函数，通过最小化成本寻找合适的功率和带宽分配方案，具体流程如下所示。

算法1 JHR-VNE。

JHR-VNE 算法主要包括节点映射和链路映射两个部分。在一次映射中，节点映射计算主要集中在资源排序和节点选择上，其时间复杂度为O(|NV│||NS|)，链路映射中计算最短路径的时间复杂度为O(i|LS│|lb(|NS|))，计算极小值点的时间复杂度为O（n2）。综上得出，在映射过程中JHR-VNE 算法的时间复杂度为O(|NV│||NS|+i|LS│|lb(|NS|)+n2)。

3 仿真实验与结果分析

通过仿真实验验证本文算法的有效性，在VNR 总体接受率、各级别VNR 接受率、资源利用率、成本等方面与WVNE-JBP 算法［19］进行对比，分析算法优劣性。

3.1 网络参数设置

实验仿真平台为Matlab，使用改进SalamNet 生成物理网络和虚拟网络拓扑。物理网络共设置50 个节点，其位置随机分布在200 km×200 km 的范围内，2 个物理节点间随机生成一条物理链路。其中节点的功率资源服从均匀分布U（50，100），链路的带宽资源服从均匀分布U（20，50），运行总时间为5 000 时间窗。虚拟网络生成节点个数服从均匀分布U（3，10），2 个虚拟节点间以0.5 概率形成虚拟链路。其中，虚拟网络到达率服从0.05 的泊松分布，即100 个时间窗内到达5 个虚拟网络，传输速率服从均匀分布U（3，8），生存时间为100 时间窗。其他参数设置为λ=0.25，δ=0，1，2，ɛ=（2*δ+3）/10，φ=100，η=0.618，信道增益中，k=4，σ2=10-8。

3.2 仿真结果分析

本文将所提JHR-VNE 算法与WVNE-JBP 算法［19］进行对比，WVNE-JBP 算法的节点资源排序依据为当前节点所具有的功率资源和与之相连链路的总带宽资源，通过路径分离选择最短路径进行链路映射，其目标函数为原始成本函数。

图2 展示了JHR-VNE 算法与WVNE-JBP 算法［19］的VNR总体接受率，可以看出本文算法的接受率有较大提升，WVNE-JBP 算法总体接受率为58.5%，本文算法为70.2%，提高了11.7 个百分点。接受率曲线波动原因为部分VNR 生存时间到期，释放相应资源给新到达的VNR。

图3 为两种算法各级别VNR 接受率比较，δ变化时，JHR-VNE 算法映射VNR 消耗的资源存在变化，而对WVNEJBP 算法消耗资源没有影响。

图3（a）中，当δ=0时，本文算法映射VNR 倾向于消耗较大功率资源和较小带宽资源，接受率相较于WVNE-JBP算法提高了11.8 个百分点。图3（b）中，当δ=1时，两种算法映射VNR 消耗功率资源和带宽资源比例类似，接受率没有明显差距，最终本文算法相较于WVNE-JBP 算法提高了5.5个百分点。图3（c）中，当δ=2时，本文算法映射VNR 倾向于消耗较多带宽资源和较少功率资源，此时接受率提高了17.8 个百分点。对比图3，本文算法调整消耗功率资源和带宽资源的占比后，VNR 接受率有明显提高，其中带宽资源为主要占用资源时接受率提升最大。

图4 和图5 分别表示功率和带宽的资源利用率情况，JHR-VNE 算法在约44%的时间内具有80%以上的功率利用率，约49%的时间内具有50%以上的带宽利用率，约15%的时间内具有60%以上的带宽利用率，平均功率利用率为76.6%，平均带宽利用率为49.8%。WVNE-JBP 算法在约23%的时间内具有80%以上的功率利用率，约51%的时间内具有50%以上的带宽利用率，约18%的时间内具有60%以上的带宽利用率，平均功率利用率为72.2%，平均带宽利用率为48.2%。可以看出本文算法在平均功率利用率上提升了4.4 个百分点，而在平均带宽利用率方面提升了1.6 个百分点。这是因为两种算法均采用路径分离方式，将带宽资源的需求压力分摊至子链路上，此时映射受制于节点的功率资源大小。

将图3（c）、图4～5 结合可以看出，节点的功率资源利用率较高而链路的带宽资源利用率较低，即使增大了映射过程占用带宽资源的比例，该级别VNR 接受率仍小于其他级别，即功率资源是影响VNR 接受率的主要因素。

图6 为两种算法的成本对比，可以看出相较于WVNEJBP 算法，JHR-VNE 算法具有较稳定的成本开销，原因是本文算法根据修正后的成本函数分配资源，不同级别VNR 消耗功率和带宽资源的单位成本有所差异，通过调整资源分配方案使得总体成本消耗处在相对稳定的水平，且与修正前成本相差不大，但VNR 接受率和资源利用率有所提升。

4 结语

本文提出的JHR-VNE 算法采用新的节点资源排序方式，将节点功率资源和与之相连的平均链路带宽作为节点映射选择依据，利用权重系数对功率和带宽资源进行分级，平衡节点和链路负载；修正成本函数，物理网络为不同级别VNR 分配资源时消耗功率和带宽资源的单位成本不同，以达到提高资源利用率的目的。经过仿真实验验证，本文算法能够解决功率、带宽资源使用不均衡的问题，在总体VNR 接受率、各级别VNR 接受率以及资源利用率方面有明显提升。下一步将结合强化学习算法，在与网络交互过程中获取资源的实时状态，进一步提高功率和资源的利用率。