面向多租户网络资源分配的博弈优化策略

郑振康，周金和

（北京信息科技大学 信息与通信工程学院，北京 100101）

0 概述

5G 网络设计的目的是为了能够支持来自不同垂直行业和用户间差异化的服务需求。在传统网络中，针对特定服务和需求来设计专用网络的方式虽然部署简单、隔离性强，但是存在资源利用率低、服务响应时延大等问题。为了在不牺牲服务质量的前提下，合理有效地利用基础设施并更加高效地提供定制化服务，网络切片技术成为5G 网络应对上述问题的关键［1］。5G 网络切片通过集中控制和云计算技术，将公共的基础设施资源集中云化，并基于资源池划分出不同的网络切片。每个切片都由多种网络功能构成，不同类型的切片应用于特定服务场景下的具体用例［2-3］。5G 网络切片从本质上改变了传统的服务方式，通过对物理网络的资源分层切片，为不同的请求提供专用网络，能够进一步优化由于请求差异化与服务多样化引发的资源浪费和网络部署成本过高的问题［4］。

灵活的网络切片部署依赖于高效的切片资源分配和编排管理，合理的资源分配方案能够有效降低网络部署成本、提高资源利用率和用户满意度。网络资源分配优化作为5G 网络切片中尚未有效处理的难点，如何制定高效可行的资源分配方案引起了学术界的广泛关注。相关学者充分考虑了网络切片中资源的分配优化和方案部署，多数方案都从提高资源利用率和降低网络能耗两方面进行研究。文献［5］研究无线虚拟化环境中的带宽资源分配，通过贪婪搜索实现高效的资源编排，可以为用户动态地分配带宽资源，优化系统性能。文献［6］研究切片即服务，开发了一种基于多云域的内容分发网络即服务平台，能够改善内容分发网络切片的部署成本和服务质量。文献［7］研究多服务无线网络中的资源分配，联合考虑了切片间的资源分配以及切片内的资源调度问题，该方案可以在保证切片隔离的同时，平衡分配效率和服务时延。文献［8］研究蜂窝异构网络中的频谱资源分配问题，联合优化了网络中的频谱分配和用户接入，可以提高网络终端速率。上述研究工作主要对网络切片的成本以及服务时延进行了优化，但没有考虑网络能耗。

博弈论是研究理性个体在利益冲突的情况下制定对策，最终达到平衡态的数学工具。博弈模型为分析和预测群体的策略交互行为提供了一个系统的理论工具，被广泛用于解决网络切片资源分配和优化问题。文献［9］研究无线接入网切片的动态资源分配问题，提出一种基于博弈论的自动化机制协助租户决策，该机制能够明显提高租户收益。文献［10］将端到端网络切片的资源分配问题建模为系统收益最大化的问题，并通过拍卖机制求解，该机制能保证资源分配的公平性，但切片间的竞争性不足。文献［11］提出一种面向5G 网络缓存资源分配的博弈优化策略，联合优化了网络提供商的收益和网络能耗，有效地改善了缓存命中率和系统能耗，但未考虑缓存资源的高效利用。文献［12］研究无线频谱资源、无线网络基础设施和移动用户间的三方匹配问题，通过匹配博弈解决资源分配问题，降低了资源分配的响应时延和系统成本并提高了用户满意度，但该文献未考虑服务切片在实际网络部署的网络能耗和资源利用率等关键指标。

通过博弈来实现多租户网络中频谱资源的合理分配，能够提高频谱资源的利用率、降低切片部署成本、增加网络收益并提升用户满意度。为此，本文提出一种面向多租户网络资源分配的博弈优化策略。网络中基础设施提供商为网络切片租户（Network Slice Tenants，NSTs）分配构建接入服务切片所需的基站频谱资源，NSTs 和用户的关系建模为多主多从的Stackelberg 博弈。通过引入切片流行度和服务命中率等指标，构建博弈双方的收益函数。在此基础上，应用逆向归纳法，通过拉格朗日乘数法求解出用户的最优吞吐量需求，并根据分布式迭代算法求解NSTs 的最优接入服务切片定价，最终经过多次迭代后收敛到唯一的纳什均衡点。

1 系统模型

多租户网络中无线接入网切片结构如1 所示，其中包括物理基础设施层、虚拟网络资源层、网络切片实例层和网络服务实例层4 个模块［13］。本文提出的面向多租户网络资源分配的博弈优化策略用于解决接入服务切片通信资源中频谱资源的合理分配，部署在网络切片管理和编排模块，以实现接入服务切片实例资源的合理分配，并为用户提供接入服务实例。

图1 无线接入网切片结构Fig.1 Structure of radio access network slice

在本文模型中，各模块的具体功能如下：

1）物理网络基础设施层包括基站等接入设施、计算服务器和存储单元，分别由不同的提供商管理。

2）虚拟网络资源层包括三大网络资源，为物理网络基础设施通过虚拟化技术整合而成的资源块，并提供给NSTs。

3）NSTs 解析服务需求映射，租用虚拟网络资源，构建网络切片实例层。

4）网络服务实例层提供用户和业务服务，每种服务包括不同用例，每个用例都由一个服务切片实例表示。

1.1 系统模型

本文系统模型如图2 所示，由1 个基础设施提供商、M个NSTs{1,2,…,M}以及N个用户组成。其中用户包括K个内部接入用户{1,2,…,K}和L个外部接入用户{1,2,…,L}，所有用户均可访问所有NSTs，切片间的频谱共享借助于多址接入技术。

图2 本文系统模型Fig.2 System model in this paper

在本文系统模型中，服务请求和切片构建的具体过程如下：

1）基础设施提供商拥有基站频谱资源，为合理高效地利用物理设施并增加自身收益，将虚拟网络资源出租给NSTs。

2）NSTs 根据用户的需求和切片流行度构建接入服务切片，为用户提供网络接入服务。

3）用户购买接入服务切片，接入网络获取所需内容。

由于网络中的物理资源有限，NSTs 会根据用户的需求和自身的服务能力来动态地调整切片定价，以最大化自身收益，进而最大化网络收益。

1.2 资源模型

基础设施提供商基站的频谱资源抽象为：最大带宽频谱资源为B，下行传输功率为p，假设B和p为常数。对于NSTsm，m∈{1,2,…,M}，从基础设施提供商处租用虚拟频谱资源，以分配得到一定比例的频谱带宽。本文假设接入服务切片之间是物理隔离的，NSTs 之间不存在干扰。

对于内部用户而言，能够直接获得的网络接入吞吐量Ri与订购的切片类型有关，即与NSTsm在接入服务切片中再分配的频谱资源有关。Ri计算如下：

1.3 切片流行度

由于用户对于不同接入服务的偏好不同，因此NSTs 需要提供不同的切片类型。通过分析用户的请求分布，提前构建用户下一次可能请求的切片实例，能够提高用户满意度，降低切片请求时延和网络能耗。

假设用户总共请求C种接入服务切片，C={S1,S2,…,SC}。Zipf 分布［14］描述了接入服务切片排名与其访问概率之间的关系，假设{S1,S2,…,SC}是接入服务切片排名，访问概率Dc计算如下：

其中：ω为平坦因子，当ω=0 时满足一般的幂律分布；υ＞0 为偏态因子，也称为流行度指数，υ越大，切片被访问的概率越高，即切片流行度越高，S1越受欢迎，并且少量切片类型占有更高的请求概率。

1.4 服务命中率

假设用户对网络接入服务的请求满足泊松分布，平均请求率为λ，根据文献［15］，本文考虑生存时间（TTL）切片管理模型，则NSTsm接入服务切片c的命中率可表示为：

其中：λn,c=λ·Dc表示用户对切片c的请求率；Tm表示NSTsm的接入服务切片特征时间，即从切片实例构建到终止服务的持续时间。

由于切片的类型数量很大，因此到达每个NSTsm的请求率相对很小，根据等价无穷小定理，e-x～x(x→0)，可以近似得到：

2 问题构建

一个博弈模型通常由3 个基本元素组成：决策个体集合，每个决策者所能采取的策略集合以及每个决策者的收益函数［16］。

本文考虑的Stackelberg 博弈模型的决策个体地位不对等，决策个体集合分为领导者和从属者，其中领导者处于决策的主导地位，每个决策个体都有自身的策略集合和对应的收益函数［17］。Stackelberg 博弈可以概括为以下3 个阶段：

1）领导者首先做出当前收益函数下的最优决策。

2）从属者考虑领导者和其他从属者的策略，结合自身收益跟随决策。

3）领导者再考虑从属者的策略和自身收益函数调整其决策。整个博弈过程是动态的，当双方收益不再增加，即没有决策个体愿意改变策略时，博弈过程结束。

2.1 博弈构成

本文通过多主多从的Stackelberg 博弈来建模多租户网络接入服务切片的频谱资源分配问题，基本元素构成具体包括：

1）决策个体集合。领导者是M个NSTs{1,2,…,M}。在多租户网络中，NSTs 租用基础设施提供商的基站资源，它具有先手优势，首先决定接入服务切片定价并影响从属者的决策。从属者包括内部用户{1,2,…,K}和外部用户{1,2,…,L}，用户 考虑NSTs 的切片定价和自身吞吐量需求，调整切片订购策略，最大化自身收益。

2）策略集合。用户的策略是其在每个NSTs 处订购的服务切片比例xi,m、xj,m，其需求可由多个NSTs满足。NSTs 进行资源的切片实例化和重售，它的策略是制定切片的价格P={P1,P2,…,Pm}。

3）收益函数。用户的收益函数用Un表示，NSTsm的收益函数用Um表示，其中，n∈{1,2,…,K；1,2,…,L}，m∈{1,2,…,M}。

假设多租户网络中包括两类用户，即内部用户和外部用户。这种假设是合理的，例如在通过接入服务切片接入学校网络时，内部用户包括学生、教职工等，可通过校园网直接接入，而外部人员需要借助虚拟专用网间接接入。

用户的收益Un包括两部分：一部分是获得接入服务切片的收益，表示为接入吞吐量Rn的对数形式［18］；另一部分是购买服务切片的支出。

对于内部接入用户i，i∈{1,2,…,K}，式（5）表示与接入吞吐量Ri相关的收益：

用户获得接入服务切片时的最终收益为：

其中：δi为收益系数；λ为平均请求率。

切片的价格应该结合市场规律，即NSTsm的访问人数越多，切片价格应该更高，这个关系用nm/Nm表示，为NSTsm中当前存在的用户数除以其最大服务能力。用户购买接入服务切片的成本如式（7）所示，内部接入用户的净收益如式（8）所示：

其中：ηm为成本系数表示受市场规律影响下的切片价格。

对于外部接入用户j，j∈{1,2,…,L}，与内部接入用户不同，其成本与切片价格是二次函数关系，即对外部接入用户收费更高，并且没有保证基础吞吐量式（9）和式（10）为外部接入用户与接入吞吐量相关的收益和购买接入服务切片的成本，外部接入用户与NSTs 的博弈建模及求解与内部接入用户类似，故后续博弈求解中只考虑内部用户接入。

其中：τ为调整系数，控制外部接入用户成本函数的变化。

NSTs 的收益包括接入服务切片定价Pm带来的收益以及构建切片实例的成本Εm，则NSTsm的收益函数为：

2.2 问题建模

在本文资源分配系统中，用户通过订购接入切片来接入网络，在支付切片价格后获得所需服务。同时，NSTs 通过制定资源的重售价格，创建网络切片来获取收益。两者在考虑服务能力和体验质量的前提下，都试图最大化自身收益。

对于每个NSTs 而言，资源分配优化问题可映射为其收益最大化问题，即：

其中：切片定价为非负值。

对于两类用户而言，优化问题同样被映射为其收益最大化问题，将式（6）、式（7）代入式（8），得到内部接入用户的净收益解析式为：

则对应的收益最大化问题为：

其中：0 ≤x≤1 为用户订购切片比例取值。

从上述博弈模型问题构建可以看出，NSTs 的目标是最大化其在式（11）中的收益。而用户作为从属者，其目标为式（14），在NSTs 做出决策后跟随决策。

本文考虑的接入服务切片频谱资源分配模型中存在两种博弈，NSTs 和用户之间是符合主从关系的Stackelberg 博弈，在NSTs 切片定价决策后，用户之间是非合作博弈关系。NSTs 之间通过价格博弈，来吸引更多的用户购买接入服务切片，尽可能增加自身收益；同样，用户可以根据NSTs 的定价调整自己的购买策略。博弈建模的结果是得到纯策略纳什均衡点，该点处博弈双方选择最佳策略，并得到最佳策略下的最大收益。

2.3 纯策略纳什均衡

Stackelberg 博弈的纳什均衡定义为子博弈完美纳什均衡：一个接入频谱资源的分配和定价策略，其中没有任何一个决策个体有兴趣偏离该策略，否则自身收益会减少［19］。

定义1（最佳响应）一个决策个体i对于策略组合s-i的最佳响应为纯策略使得对于所有的策略

具体地，在本文的模型中，NSTs 之间共享用户的接入服务请求，每个NSTs 决定频谱资源的重售价格以最大化自身收益。显然，当服务两类用户的收益更大时，该NSTs 的最佳响应超过只服务单一用户。

定义2（纳什均衡）如果对于所有的决策个体i，si均是对策略组合s-i的一个最佳响应，则策略集s=(s1,s2,…,sn)是一个纳什均衡。

下文将给出本文资源分配博弈优化模型纯策略纳什均衡解的证明。

假定领导者已做出决策，即公布资源重售（服务切片）价格p，在该定价下用户之间是非合作博弈关系，收益函数为Ui(p,xi,m,x-i,m)，其 中i∈{1,2,…,K}，则用户的切片订购策略间存在唯一的纳什均衡点。

证明：根据文献［16］中布劳威尔不动点定理可知，若满足博弈的决策个体有限，每个用户的策略空间x是欧氏空间上的有界闭集，并且其收益函数Ui在x上是连续的，且存在一个不动点，则该博弈具有一个纯策略纳什均衡解。

下文证明用户收益函数Ui在其策略空间x上是凹函数。首先将用户收益函数Ui对策略空间xi,m求一阶偏导数：

然后将用户收益函数对策略空间xi,m求二阶偏导数：

由式（16）可知，一阶偏导数存在，二阶偏导数为负，即收益函数在整个策略空间上为凹函数，再结合收益函数的单调性和凹函数图像性质可知，用户的切片订购策略间存在唯一的纳什均衡点，证毕。

3 博弈求解

第2 节已经证明了本文提出的Stackelberg 博弈模型存在子博弈完美纳什均衡，本节用一种逆推解法——逆向归纳法来求解博弈模型。首先，求解Stackelberg 博弈的第二阶段，得到用户最优的吞吐量需求，即用户订购的服务切片比例x*。然后，将x*用于求解博弈的第一阶段，得到NSTs 切片的最优定价p*。

3.1 用户的最优吞吐量需求

由于在多租户网络中，基础设施提供商基站的频谱资源有限，并且用户存在预算约束，因此在实际求解中，必须考虑用户的最大成本约束。用户的最优吞吐量x*求解问题表示为：

本文选择拉格朗日乘数法来求解约束优化问题式（17）。构造拉格朗日函数如下：

其中：α、β、γ是拉格朗日乘子。

通过KKT（Karush-Kuhn-Tucher）条件［20］得到用户的最优吞吐量需求，条件如下：

其中：条件②和条件③分别为原始和对偶可行条件；条件④和条件⑤为互补松弛条件。

求解式（19）得到用户的最优吞吐量需求，如式（20）所示：

3.2 NST 的最优切片定价

得到用户的最优吞吐量需求x*后，本文提出一种复杂度较低的迭代算法，用于求解NST 的最优接入服务切片定价p*，具体步骤如下：

1）输入x*及其他初始化参数。

2）初始化P={P1,P2,…,Pm}，令P1=P2=…=Pm=0。

3）求解式（11）关于Pm的偏导数：

4）式（21）不是解析解，NSTs 最优的切片定价需要通过迭代求解，迭代公式如下：

其中：t为迭代次 数为 第t次迭代 时NSTsm的切片定价；λk为迭代步长，与总迭代次数成反比。

4 仿真结果与分析

4.1 仿真设置

为验证本文所提策略，对提出的资源分配优化策略性能进行仿真分析，使用NS2 和GT-ITM 工具构建多租户网络环境和接入服务切片实例，利用Python 进行结果分析。对比算法包括最大最小公平策略［21］、基于优先级的动态资源分配策略［22］和时延最小化资源分配策略［23］，在资源利用率、网络收益和能耗减少率3 个方面进行对比验证。其中，文献［19］提出的最大最小公平算法首先满足所有用户的最低需求，再将剩余资源平均分配；文献［20］提出的基于优先级的动态资源分配算法考虑用户的需求和优先级，动态地进行资源分配；文献［21］提出的时延最小化资源分配算法考虑切片的优先级并最小化切片时延。

仿真中模拟的网络环境中包括2 个NSTs 和100 个内部接入用户，网络中最大的带宽频谱资源B=500，每个NSTs 租用的最大频谱带宽Wm=250。其他的仿真参数如表1 所示。

表1 仿真参数与参数值Table 1 Simulation parameters and parameter values

4.2 仿真结果

图3 给出了网络切片提供商NSTs 1 与NSTs 2 的切片定价的关系，两条曲线上的点分别表示当前NSTs 对另一NSTs 的最佳响应定价策略。由图3 可知，（1.4，1.8）是双方定价的交点，也是博弈均衡点，在该点处NSTs 1 与NSTs 2 都没有兴趣改变定价策略使自己的收益降低，为双方收益最大化的最佳定价组合。

图3 NSTs 1 与NSTs 2 的切片定价关系Fig.3 Slice pricing relationship of NSTs 1 and NSTs 2

图4 给出NSTs 的收益同其切片流行度之间的关系。由式（2）可知，切片流行度与流行度指数υ和平坦因子ω有关。从图4 可以看出：当ω一定时，υ越大，切片越受欢迎，访问概率越大，相应的NSTs 的收益越高；而当υ一定时，ω越小，流行切片的访问概率越大，相应的NSTs 的收益越高；当υ、ω一定时，随着迭代次数增加，NSTs 的收益值逐渐增加；当迭代次数为70 左右时，NSTs 的收益收敛到最大值，并且υ越大，ω越小，收敛越快。

图4 NST 收益与迭代次数的关系Fig.4 The relationship of NSTs revenue and iterations numbers

图5 给出不同策略下接入服务用户的收益与迭代次数的关系。由图5 可知，当迭代次数相同时，本文提出的基于博弈的资源分配策略中接入服务用户收益值最大，随着迭代次数的增加，接入服务用户的收益值逐渐增大。基于优先级的动态分配策略仅考虑最大化切片的服务质量，未能有效保证用户收益，而时延最小化资源分配策略考虑了切片服务时延并设置了切片偏好度，用户收益相对更高。基于博弈的资源分配策略通过博弈加快了收敛，迭代次数为70 左右时收敛，收敛速度仅次于最大最小公平策略。

图5 用户收益与迭代次数的关系Fig.5 The relationship of user revenue and iteration numbers

图6 给出不同策略下网络中频谱带宽利用率与用户接入服务切片请求到达率的关系，初始条件用户接入相同，4 种策略资源利用率相同。由图6 可知，随着用户切片请求到达率的增加，利用率逐渐增大，本文提出的基于博弈的资源分配策略能收敛到最大的资源利用率。基于优先级的动态资源分配策略通过维护切片的优先级和需求量，动态地为切片分配资源，比起时延最小化资源分配策略仅考虑计算和通信资源的按需分配策略，能到达更大的资源利用率。

图6 资源利用率与请求到达率的关系Fig.6 The relationship of resource utilization and request arrival rate

基于博弈的资源分配策略的接入服务用户收益值迭代70 次左右达到收敛，最大最小公平算法收敛最快，但资源利用率最低。

图7 给出不同策略下系统的网络能耗减少率与用户请求率的关系。为对比需要，假设不同策略下用户的请求模式相同，都为泊松分布，以此反映不同策略下的能耗情况。由图7 可知，随着请求到达率的增加，网络的能耗减少率持续增加，本文提出的基于博弈的资源分配策略能达到最高的网络能耗减少率。基于博弈的资源分配策略通过用户和NSTs 间的博弈，实现了多租户网络中频谱资源的更加合理的分配，相比于其他3 种策略，切片部署成本更低，并且资源利用率更高，实现了更高的网络能耗减少率，能更好地响应绿色通信。

图7 网络能耗减少率与请求到达率的关系Fig.7 The relationship of network energy consumption reduction rate and request arrival rate

5 结束语

高效网络切片的部署实现是推进5G 网络发展的关键因素，其中网络资源的分配优化是网络切片的关键问题之一。针对多租户网络中NSTs 的接入服务切片频谱资源分配问题，本文提出一种面向多租户网络资源分配的博弈优化策略。将NSTs 和用户构建为多主多从的Stackelberg 博弈模型，引入切片流行度和服务命中率指标，将博弈方的传统收益具体建模，并证明该博弈模型存在唯一的纳什均衡。在此基础上，提出一种分布式迭代策略求解NSTs 的最优切片定价以及用户的最优吞吐量需求。仿真结果表明，本文策略能够提高资源利用率和用户满意度，并降低切片部署能耗。本文对于5G 网络切片的部署实现有重要意义，下一步将考虑端到端网络切片的资源分配优化方案，利用强化学习实现方案的主动部署。