基于服务质量的动态资源分配算法

向碧群，杨钱英，吴广富，李静毅

(1.重庆邮电大学 移通学院，重庆 401520；2.重庆邮电大学 移动通信技术重庆市重点实验室，重庆 400065)

0 引 言

随着移动数据需求的快速增长和智能终端功能的日益强大，无线通信网络容量以爆炸式的速度增长。网络虚拟化作为处理当前互联网“僵化”问题的重要措施，已经成为未来网络研究热点[1-2]。由于无线通信信道固有的随机波动，因此，网络虚拟化不能直接对传统无线网络资源进行抽象和隔离。无线网络虚拟化的一个重要挑战就是物理资源分配，如何为多个异构虚拟网络分配共享的物理资源，以最大化地利用物理资源，是无线网络虚拟化中资源分配的研究重点[3]。

当前大部分参考文献对虚拟资源分配的问题是如何为不同网络拓扑的虚拟节点和虚拟链路分配满足其资源需求约束的物理节点和物理链路[4]。然而，在无线通信网络中，无线资源包括时域、频域、空域和功率资源[5]。因此，无线虚拟资源分配问题可以转换为异构的多维装箱问题，其目的是尽可能减少资源空洞。文献[6]在无线网络虚拟化环境下提出了一种类似卡诺图的资源分配算法，主要解决在线虚拟网络请求。文献[7]考虑了部分可用频谱带宽和频谱聚合，提出一种以最大化频谱资源利用率为目的，基于最低最左原则(bottom-left, BL)的启发式算法。文献[8]提出了一种基于多用户机会频谱共享的无线虚拟网络频谱资源分配算法，改善了无线频谱资源利用率。文献[9]提出了一种无线虚拟网络的动态资源分配算法，在一定程度上改善了虚拟网络请求的接受率和物理资源利用率。

然而以上方法都存在2个缺陷：①为了获得更高的物理网络收益，优先为请求资源量大的虚拟网络分配资源，而过度地拒绝请求资源量小的虚拟网络，从而忽略了网络公平性，不利于市场的公平竞争；②不同的分配顺序会导致不同的物理资源分配方式，产生不同的虚拟网络请求接受率、物理资源利用率和物理网络收益。

为了解决上述问题，本文提出一种基于服务质量的动态资源分配算法(dynamic resource allocation algorithm based on quality of service, DRA-QoS)。首先，该算法定义公平率，通过控制物理网络接受不同规模的虚拟网络请求 (virtual network request, VNRs)的比例，来保证VNRs的公平性；其次，综合考虑VNRs的生命周期和时延要求，定义优先级，在保证时延约束满意度的前提下尽可能多的接受VNRs；最后，设计了一种改进的重分配策略。仿真结果表明，DRA-QoS算法不仅提高了物理网络收益，而且有效地改善了虚拟网络请求的服务质量。

1 问题描述与分析

1.1 网络模型

主要考虑频域和时域的物理资源，用一个二维向量(F，T)表示。F表示频谱资源集合，包括了|F|个正交子载波数；T表示时域资源，包括了|T|个时隙数。时频物理资源如图1所示，水平方向表示子载波，垂直方向表示时隙，每个小方格代表1个资源块，作为时频资源调度的最小单位。

图1 时频物理资源Fig.1 Time and frequency physical resource

定义虚拟网络请求s为一个五元组Rs=(ws,fs,ts,ds,δs)。其中，ws表示收益因子，代表物理网络单位时频资源被分配给虚拟网络请求s后所产生的收益，与该虚拟网络请求的业务类型有关，即分配相同资源量到不同的业务带来不同收益；fs表示虚拟网络请求s所需的频率子载波资源量；ts表示虚拟网络请求s所需的时隙资源量；ds表示虚拟网络请求s被服务的时间，即生命周期。如果虚拟网络请求s的服务时间终止了，则分配给虚拟网络请求s的物理资源将被释放，并且可以允许分配给其他的VNRs。δs表示虚拟网络请求s的容忍时间，即虚拟网络请求s等待被分配的时间超过δs，缓存区则拒绝分配该虚拟网络请求s。为了有效地利用时频资源块，分配给每个虚拟网络请求的资源块必须是连续的。虚拟网络请求VNR1和VNR2的基本参数如括号所示，其可能的分配结果如图2所示。

1.2 问题分析

如果一个时间片内同时到达多个VNRs，而物理资源有限，随着时间推移，物理资源逐渐被占用，剩余的可用资源将越来越少，因此，物理网络不可能在每个时间片内都能接受所有到达的VNRs。考虑到不同业务类型对应的虚拟网络请求QoS不同，资源分配过程中需要考虑以下3个问题。

图2 虚拟网络请求的分配Fig.2 Distribution of two special VNRs

1)在虚拟网络请求分配资源之前，需要对物理网络已经分配的VNRs进行公平性衡量。也就是说，每个时间片分配资源之前，先统计已分配资源不同规模VNRs的数量。如果频繁地为大规模VNRs分配资源，而过度地拒绝小规模VNRs，会降低虚拟网络请求的QoS。

2)同一时间片内会同时到达多个VNRs，而在规定时间范围内，分配VNRs数量有限，因此，必然会导致一些VNRs产生额外的时延(本文只考虑VNRs的等待时延)。为了保证不同业务对应虚拟网络请求的QoS，需要进一步优化资源分配顺序。

3)考虑虚拟网络请求的动态性，需要设计一种更加合理的重分配策略，以充分利用物理资源。

1.2.1 公平性分析

分配大规模的VNRs更容易使有限的物理资源消耗殆尽，而导致小规模VNRs被过度拒绝，从而降低了用户的服务质量，并且分配资源量大的VNRs更容易产生物理资源碎片，造成时频资源分配瓶颈。为了解决上述问题，本文引入了公平率概念，即第t个时间片内，物理网络中已分配大规模的VNRs数量与小规模VNRs数量的比例表示为

(1)

(1)式中：NUMl(t)表示第t个时间片内被成功分配的大规模VNRs的个数；nums(t)表示第t个时间片内被成功分配的小规模VNRs的个数。

当所需时频资源量大于平均时频资源的虚拟网络请求为大规模虚拟网络请求，否则，为小规模虚拟网络请求。从(1)式可知，Fr(r)>1表示该时间片已分配的大规模VNRs数大于小规模VNRs数。为了保证大、小规模的VNRs能得到公平分配，此时应该选择规模较小的VNRs进行资源分配。同理，Fr(r)≤1表示该时间片已分配的小规模VNRs数大于大规模VNRs数，说明物理网络剩余的可用资源较多，接受大规模的VNRs的可能性较大。因此，该时间片可选择大规模VNRs进行资源分配。

1.2.2 平均时延分析

根据不同类型业务对不同时延的敏感度，设置相应的容忍时间，用δ表示。例如，一个虚拟网络请求s被设置的容忍时间为δs，则该VNR在进行资源分配时，除了满足基本的时频资源请求量外，还应该考虑该虚拟网络请求的QoS。具体来说，假如该虚拟网络请求s在第t1个时间片到达而在第t2个时间片被分配资源，分别用tsar和tsal表示。虚拟网络请求s在占用物理资源之前的等待时间，用τs表示，即τs=tsal-tsar。该虚拟网络请求的等待时延应满足其最大容忍时间δs要求，即

0≤τs≤δs

(2)

为了表示加入QoS后的资源分配模型对不同类型业务的时延影响，定义了平均时延表示每个时间片内被成功分配资源的虚拟网络请求的平均时延为

(3)

1.2.3 时延约束满意度

保证虚拟网络请求的时延服务质量，要求尽可能地减少VNR等待分配资源的时间。当剩余的容忍时间较多时，对应VNR等待的时间就较短，因此，保证虚拟网络请求的时延约束满意度可以等价为最大化剩余容忍时间所占比例。对虚拟网络请求资源分配的时延约束满意度(satisfaction of delay constraint, SoC)定义为

(4)

SoCs值越大，表示虚拟网络请求s的时延约束满意度越高。特别地，如果虚拟网络请求s到达，立即被分配资源，即τs=0，则SoCs=1表示虚拟网络请求s的时延约束满意度最高。反之，若虚拟网络请求s在给定的最大容忍时间内未得到分配，即τs=δs，则SoCs=0表示虚拟网络请求s的时延约束满意度最低。

1.2.4 目标函数

从物理网络角度出发，资源分配的目的为最大化物理网络收益，而从用户角度出发，更关注其服务质量。为了保证请求的QoS，又考虑虚拟网络请求生命周期，定义优先级p为收益因子与生命周期的比值。也就是说，虚拟网络请求的p值越大，其优先级越高，则被分配资源的可能性越大。分配虚拟网络请求s，使物理网络获得的收益用revs表示，计算式为

×As

(5)

第t个时间片所获物理网络收益为

(6)

(6)式中，S*(t)表示第t个时间片缓存区内成功分配时频资源的VNRs集合。

在保证虚拟网络请求的QoS前提下，以最大化物理网络收益为目标函数

(7)

限制条件为

(8)

(8)式中：S(t)表示第t个时间片缓存区内需要分配的VNRs集合；csij表示为虚拟网络请求s分配时频资源的起始位置，csij=1表示第i个子载第j个时隙对应的时频资源块的开始位置。

2 DRA-QoS算法设计

2.1 区域密度指数

首先，通过卡诺图画圈原理将物理网络的可用时频资源划分为多个不完全重叠的矩形资源块。然后，根据VNR的时频资源量，选取物理网络能满足该VNR资源的矩形资源块，作为候选的目标资源。如果有多个矩形资源块能满足条件，选择时频资源量最少的矩形资源块，若所选择的矩形资源块所包含的时频资源量仍大于该VNR需求的时频资源量，需要为该VNR预分配时频资源，并计算每个可能分配该VNR的子区域后的区域密度指数(area density index, ADI)，选择使ADI最小的子区域作为最终的目标资源。反之，如果该时间片没有足够的时频资源满足该VNR的资源量，则该VNR被放入缓存区等待下个时间片再次尝试被分配，直到其等待时间到达最大容忍时间，被拒绝，并从缓存区内被删除。

ADI定义为已占用资源块与空闲资源块之间边界的条数，表示为

(9)

(9)式中：ai,j表示第i个子载波第j个时隙对应的时频资源块；a表示某个VNR占用的矩形资源区域；A表示所有被占用的时频资源块集合。

2.2 重分配影响因子

重分配影响因子ξ，定义为某个VNR所占矩形资源块的区域密度指数与周长的比例，用其表示该VNR对时频资源连续性的影响。ξ值越大，表示该VNR占用的矩形资源块与其他VNRs占用的矩形资源块越分散，空闲的时频资源越碎片化。其中，ξ∈[0,1]，ξ=0表示所选VNR所占用的矩形资源块与其他VNRs所占用的矩形资源块完全聚集。简单而言，所选VNR占用的矩形资源块周围没有空闲时频资源；反之，ξ=1表示所选VNR所占用的矩形资源块与其他VNRs所占用的矩形资源块完全分散。

因此，给定一个虚拟网络请求s，重分配影响因子表示为

(10)

(10)式中：ADIs表示虚拟网络请求s占用矩形资源块的区域密度指数；ls表示虚拟网络请求s所占用矩形资源块的周长。

2.3 基于QoS的动态资源分配算法

因为VNRs的到达和离开是动态变化的，必定会导致物理资源碎片化。为了更有效地调度物理资源，本文考虑了重分配策略。然而，重分配不仅会增加算法的复杂度，还会产生额外的成本开销，甚至导致虚拟网络请求服务中断。因此，不恰当的重分配策略不仅不会给物理网络带来更多的收益，还会影响虚拟网络请求的服务质量。基于此，本文在重分配过程考虑以下3点。

1)在虚拟网络请求的生命周期快结束时，不进行重分配。因为该虚拟网络请求占用的物理资源即将被释放。因此，设定一个门限值Δd，当其生命周期的剩余时间小于Δd的虚拟网络请求不考虑重分配。

2)因为资源请求量大的VNRs，更不容易找到合适的物理资源来满足其资源需求，并且对它们执行重分配开销更大，所以优先选择请求资源量小的VNRs。

3)计算所选VNRs的重分配影响因子ξ，并根据设定的门限值ξth，选择ξ>ξth的VNRs执行资源重分配。

本文以最大化物理网络收益为目标函数，提出基于QoS的动态资源分配算法，具体流程如图3所示。该算法在虚拟网络请求被分配时频资源之前，先探测物理网络空闲时频资源的连续性，再执行重分配或资源分配过程。

3 仿真结果及分析

为验证所提DRA-QoS算法的有效性，本文利用MATLAB仿真工具进行仿真，并与基于生命周期的动态资源分配算法(dynamic resource allocation algorithm based on lifetime priority，DRA-LP)、贪婪动态分配(greedy dynamic allocation，GDA)算法[9]进行性能对比。其中，DRA-LP算法是基于生命周期的动态资源算法，即在动态资源分配的时候，优先考虑虚拟网络的生命周期，导致优先级低的请求时延更长。GDA算法为每个虚拟网络分配了优先级，在资源分配阶段，分配新到达的虚拟网络请求之前必须优先保证已分配的虚拟网络请求有足够可用的资源。

3.1 性能参数

1)物理资源利用率UR。定义为VNRs所占用的物理资源与总物理资源的比例。

(11)

(11)中：Rs(i)表示第i个时间片物理资源被占用的总量；R为总的物理资源；N为仿真时间片总数。

图3 DRA-QoS算法流程Fig.3 DRA-QoS algorithm flow diagram

2)虚拟网络请求接受率AR。定义为成功分配虚拟网络请求数与总到达虚拟网络请求数的比值。

(12)

3)物理网络收益RE。

(13)

(13)式中，rev(i)为第i个时间片的物理网络收益。

3.2 仿真场景设置

本文利用MATLAB对DRA-QoS算法进行仿真分析，物理资源包括20个子载波和20个时隙，构成一个20×20的二维时频资源块。虚拟网络请求的到达过程建模为一个服从参数λ=5的泊松分布过程，每个VNR的生命周期服从参数u=10的指数分布，虚拟网络请求所需的子载波数和时隙数均服从U(2,5)均匀分布。虚拟网络请求分配了三类业务：实时性业务(例如，网络电话)、高速率业务(例如，视频流)和尽力而为业务(例如，文件下载)，并根据每种业务对时延的敏感度，分别为它们分配了不同的收益因子和容忍时间，分别是0.5，0.3，0.2和1，2，4个时间片。这三类业务对应的VNRs的收益因子和容忍时间被列入表1。在重分配过程中，设定了门限值Δd=10。

表1 不同类型的VNRs的分配参数

3.3 仿真结果及性能分析

下面分别从平均时延、时延满意度、公平率、重分配率和算法时间复杂度等方面进行仿真分析。

图4和图5仿真了阈值ξth对虚拟网络请求接受率和物理网络收益的影响。由图4，图5可以看出，随着ξth增大，虚拟网络请求接受率和物理网络收益都有所降低。原因在于ξth越大，表示需要重分配的虚拟网络请求越少，资源分配过程中产生的资源碎片就不能得到充分利用，从而导致虚拟网络请求接受率更低，能获得的物理网络收益也就更少。同理，ξth越小，表示进行重分配的虚拟网络请求个数越多，则更有可能使空闲时频资源连续，从而接受更多的虚拟网络请求，增加物理网络收益。特别地，ξth=1表示已分配的虚拟网络请求不需要进行重分配，故虚拟网络请求接受率最低。随着时间变化，虚拟网络请求接受率降低到55%并趋于稳定。ξth=0表示需要对已分配的虚拟网络请求全部进行重分配，从而虚拟网络请求接受率最高，最终达到79%。值得注意的是，当ξth值从0.8降为0.5时，VNRs接受率提高了14%，而ξth值从0.5降为0.2，虚拟网络请求接受率仅提高了3%左右。但是ξth值越小，需要重分配的虚拟网络请求数就越多，DRA-LP算法的复杂度和重分配的计算成本就越高，而其性能改善并不明显，因此并不是ξth越小越好。其中，DRA-LP算法中的ξth值被设置为0.5。

图6和图7分别表示采用DRA-QoS，DRA-LP和GDA算法求解虚拟网络资源分配模型后，3种不同业务的平均时延和时延约束满意度的对比图。因为业务的时延约束满意度和平均时延有关，因此，需要将平均时延和时延约束满意度的仿真结果综合分析。由图6可以看出，相比DRA-QoS和DRA-LP算法，采用GDA算法的实时业务和高速率业务的平均时延更低，而尽力而为业务的平均时延更高。不考虑时延要求的DRA-LP算法，其实时业务和高速率业务的SoC分别为0.1和0.4，DRA-QoS和GDA算法中实时业务的SoC均稳定在0.48，如图7a所示，高速率业务的SoC分别为0.45和0.54，如图7b所示。DRA-QoS算法为了保证不同类型业务对应的虚拟网络请求能有效得到分配，不仅仅考虑时延，还考虑了生命周期，因此，实时业务和高速率业务的平均时延比GDA算法略高。DRA-LP算法没有考虑时延，故实时业务和高速率业务的平均时延均较高。考虑时延要求，虽然增加了尽力而为业务的等待时延，但因为该业务对时延不敏感，故不同算法对尽力而为业务的SoC影响不大，仅相差0.01左右，如图7c所示。

图4 虚拟网络请求接受率随时间的变化(λ=5,u=10,U(2,5))Fig.4 VNRs acceptance rate vs the simulation time

图6 不同业务的平均时延对比Fig.6 Average delay comparison of different services

图7 不同业务的时延约束满意度对比Fig.7 Satisfaction comparison of different business delay constraint

图8给出了公平率对比图。每个时间片到达的虚拟网络请求数量不同，且请求资源量大小也不一定，为了有效呈现仿真结果，该仿真每隔25个时间片对数据进行一次统计。可以看出，采用DRA-LP算法和GDA算法，得到的公平率大致相同。然而，DRA-QoS算法考虑了网络公平性，因此，其公平率均在1上下波动。因为每个时间片到达的大、小规模的VNRs比例不一致，所以存在一定的波动。

因为GDA算法在每个时间片均对物理网络已经分配的所有VNRs进行重分配，故其重分配率为1。图9给出了DRA-QoS和DRA-LP算法重分配率的对比图。随着时间推移，物理网络中存在的VNRs越来越多，虚拟网络请求的动态变化会导致物理资源碎片化，为了充分利用物理时频资源，重分配的VNRs随之增多。然而，当物理网络接受的VNRs到达一定限度时，剩余物理时频资源越来越少，满足新到达的VNRs资源需求的可能性就小，接受的VNRs数量就少。同时，物理网络中存在的VNRs越来越聚集，因此，重分配率会随之降低。因为DRA-QoS算法在DRA-LP算法的基础上对重分配策略进行了改进，限制了重分配VNRs的个数，故DRA-QoS算法在重分配VNRs数达到一定程度后，趋于稳定。

图8 不同算法公平率对比Fig.8 Fairness comparison of different algorithms

图9 重分配率对比Fig.9 Redistribution rate comparison of different algorithms

物理资源利用率的对比图如图10所示，可以看出，DRA-QoS，DRA-LP和GDA算法均考虑了重分配策略，可以动态有效地调度物理资源以充分利用物理资源，因此，能获得较高的资源利用率。而DRA-QoS算法在重分配过程中，对剩余生命周期小于Δd(仿真中，分配为10个单位时间)的VNRs和请求资源量大的VNRs不执行重分配策略，故较另外2种分配算法的利用率略低，保持在80%左右。

图10 资源利用率对比Fig.10 Resource utilization comparison

图11给出了虚拟网络请求接受率对比图。开始阶段，物理资源充足，虚拟网络请求接受率均较高，随着时间变化，最终趋于稳定。因为可用的物理资源越来越少，接受新到达VNRs的可能性就减小，最终物理网络中的VNRs数只在小范围内波动。DRA-LP算法将虚拟网络请求生命周期倒数作为优先级，优先分配生命周期短的VNRs，使得物理网络能接受更多的VNRs，故虚拟网络请求接受率较高。而DRA-QoS算法考虑了虚拟网络请求的公平性和时延要求，因此，较DRA-LP算法的虚拟网络请求接受率降低了3%。

图11 虚拟网络请求接受率对比Fig.11 VNRs acceptance rate comparison

图12描述了物理网络收益的变化规律。结合图9和图10的仿真结果，可以看出，DRA-QoS算法较DRA-LP算法有略低的资源利用率和虚拟网络请求接受率，而获得的物理网络收益较平稳。其原因在于DRA-QoS算法考虑了请求的公平性，物理网络接受的大、小规模的VNRs所占比例相当，同时考虑了不同业务对时延要求和虚拟网络请求生命周期的重要性和优先级p，确保对时延有一定要求且生命周期较短的VNRs能优先被分配资源，保证了请求的服务质量，获得较稳定的物理网络收益。

图12 物理网络收益对比Fig.12 Physical network revenue comparison

图13给出了3种算法的运行时间复杂度的对比图。可以看出，GDA算法的运行时间最长，且波动幅度最大，原因在于GDA算法在每个时间片对已分配的虚拟网络请求都要进行资源重分配，而每个时间片物理网络中已存在的虚拟网络请求数不同。而DRA-QoS算法和DRA-LP算法都只选择部分虚拟网络请求进行资源重分配，故其运行时间较低。由于DRA-QoS算法进一步优化了重分配策略，故该算法的运行时间更低。

4 结束语

本文针对虚拟网络请求的服务质量，考虑了网络虚拟请求的公平性和时延要求，提出了基于服务质量的动态资源分配算法DRA-QoS。该算法构建QoS约束控制参数的虚拟网络资源分配模型；通过控制物理网络中不同规模的虚拟网络请求的比例，保证虚拟网络请求的公平性；综合考虑虚拟网络请求的生命周期和时延，保障服务质量的同时尽可能多地接受虚拟网络请求。同时，该算法还提出改进的重分配策略，根据已分配的虚拟网络请求的剩余生命周期和空闲物理资源的聚合度，选择需要进行重分配的VNRs以降低重分配率。仿真结果表明，所提DRA-QoS算法在满足服务质量的同时，可以有效利用物理资源。

图13 算法时间复杂度对比Fig.13 Algorithm time complexity comparison