面向5G 网络云原生应用资源调度的博弈优化策略

赵文君，周金和，王 晶

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

0 概述

随着5G 网络和云原生技术的发展，2018 年中国数字经济的规模已达4.73 万亿元，其中70%以上的企业已经使用容器技术或正在测试相关的应用环境，2020 年将有约50%的老旧应用以云原生化的方式被改进，云原生应用将成为新常态［1］。云原生被证明是建设和连续运行世界上最大云的有效加速技术。在当前复杂的云计算环境中，传统应用需要快速响应用户需求，从而提高了应用的复杂性，同时，5G 网络产生的新需求也对应用提出了更高的挑战。微服务体系结构的出现成为解决该问题最有效的方案之一，其将应用划分为多个小服务，其中，单个服务专注于特定的功能，并且独立运行在隔离的环境中，然后使用轻量级通信机制进行集成从而形成高内聚低耦合的服务结构［2］。云原生技术使应用具有更强的可靠性、更短的交付时间、更简化的运维操作以及更高的运营效率。

5G 云原生技术的发展使得云原生应用引起研究人员的广泛关注。在大规模应用系统中，微服务数量较多，微服务之间存在复杂的交互关系，导致云原生应用在运行时的资源调度面临新的挑战。微服务之间存在对网络资源的竞争关系，5G 云原生服务提供商缺乏充足的资源来满足所有应用程序的需求［3］，因此，将可用的服务资源合理地分配给不同的应用程序具有重要意义。文献［4］研究云分布虚拟资源上的最佳虚拟功能放置问题，使用分支定界和模拟退火2 种启发式算法来实现最佳布局，其降低了执行复杂性并缩短了服务迁移的延迟。文献［5］考虑系统调整的延迟性，提出一种基于控制理论前馈和反馈的虚拟资源动态分配方法。文献［6］针对5G 云无线电接入网络提出一种动态资源管理策略，设计2 种贪婪启发式算法，从而有效降低网络中的服务器总数并提高终端用户的体验质量。文献［7］从计算资源成本的角度出发，以最小化所有背包成本之和为目标研究动态背包问题，实现了服务部署成本的最优化。

虽然上述研究均针对资源利用率和网络延迟2 个方面进行了优化，但是都未充分考虑网络收益问题。在资源调度的过程中，能耗是5G 网络中亟待解决的问题之一。文献［8］充分考虑网络中的能耗问题，通过提供按需内容交付服务解决了部署成本与服务可用性之间的权衡问题，然后进一步提出多项式时间启发式方法，以对计算资源进行合理分配。

目前，博弈论已经广泛应用于资源分配与优化任务，如互联网定价和5G 网络切片资源分配等。文献［9］针对云原生应用运行时计算资源有限的问题，采用拥塞博弈理论对运行时的微服务资源进行调度管理，其有效提高了云原生应用的整体性能。文献［10］提出支持卸载和迁移的智能网关方法，该方法采用非合作博弈重新调度云环境中的计算任务，降低了能耗和网络延迟，但是其未考虑用户的需求，如用户对应用程序的偏好性等。文献［11］通过对多个用户构建非合作博弈模型，考虑传输时间和网络成本的影响从而确定用户的利润，其提高了用户的体验质量，但未充分考虑资源有限和云提供商的利润问题。由于云环境下应用程序之间的资源竞争行为与经济学中的自由竞争市场类似，因此基于博弈论的方法能够构建资源管理中的竞争关系［12］。考虑微服务之间的协作与竞争关系，可以将博弈论引入微服务中，通过对有限的网络资源进行竞争以获取更多的网络效益。

云原生应用资源调度的目的包括优化应用时间、保证服务质量、优化费用以及实现高效节能等。本文提出一种面向5G 网络云原生应用的资源调度博弈优化策略。将云原生应用程序划分为多个微服务，微服务资源由云原生服务提供商所有，云原生应用为云原生应用商所有。云原生应用商通过租用云原生服务提供商的微服务来构建应用，从而提高收益，而云原生服务提供商通过收取对应的费用作为收益。为了使云原生应用商与云原生服务提供商的收益最大化并最大限度地降低能耗，本文将云原生应用资源调度问题建模为多主多从的Stackelberg 博弈模型，构建收益函数对传统收益进行具体化描述，并引入用户偏好性指标以提高两者的传统收益。为解决能耗问题，本文对能耗和传统收益进行联合建模，并证明纳什均衡解的存在。在此基础上，引入柯西分布提高策略的收敛性，使用分布式迭代方法确定云原生应用商的最佳租用比例和云原生服务提供商的最佳定价，最后通过Stackelberg 博弈实现效用的最大化。

1 系统模型

根据5G 网络架构［13］，本文将云原生服务提供商和数据网络中的云原生应用商构建为图1 所示的系统模型。

图1 系统模型Fig.1 System model

由图1 可知，本文系统模型主要由X个云原生应用商NCNAi（i=1，2，…，X）和Y个云原生服务提供商NCSPj（j=1，2，…，Y）构成。云原生应用商拥有有限的微服务资源，可以将微服务资源租给云原生应用商，以便对云原生应用进行开发。其中，微服务资源服从密度为φ的异构齐次泊松点分布。应用开发的资源调度过程为：

1）云原生服务提供商给定微服务资源的定价，并告知云原生应用商。

2）云原生应用商根据应用的性能和微服务的定价等多种因素确定自身租用微服务资源的比例，并将自身应用开发为云原生应用。

3）用户依据自身偏好和满意度对应用进行访问。

1.1 云原生应用流行度

在现实中，用户对不同的应用具有不同的偏好，因此，应用之间的流行度存在一定差别，应用流行度越高，用户的访问频率越高，相应的收益越大。因此，引入应用流行度这一指标可以更合理地确定微服务的租用比例，从而提高云原生应用的收益。假设存在N个应用，用集合表示为A=｛A1，A2，…，AN｝，第n个应用的流行度为Dn，n=｛1，2，…，N｝。不同的应用有不同的流行度，假设云原生应用商的应用集依据应用流行度由高到低降序排列，则用户向应用请求服务的概率为Dn，其服从Zipf 分布［14］。

随着移动终端的普及，一些流行的应用开始为人们所熟知，如抖音、快手等。本文引入调节因子θ，以调整应用的流行程度，从而提高云原生应用的流行度与云原生应用商的收益。Dn的计算公式如下：

其中，α为云原生应用的流行度指数，流行度随着α的增大而提高，即云原生应用1 最受用户欢迎，云原生应用N最不受用户欢迎。

1.2 用户偏好性

用户偏好性直接影响云原生网络的收益，一般而言，如果用户偏好性低，云原生应用的收益就会降低，反之亦然。因此，本文引入用户偏好性指标来衡量应用的服务质量，通过用户反馈来调整云原生应用商的收益。用户偏好性表示用户使用云原生应用的体验水平，偏好性直接受到应用时延、能耗大小等多方面因素的影响。文献［15］建立用户偏好性和网络服务质量之间的多维函数关系，以此为参考，本文对用户偏好性进行定义。假设每个应用有M个评价指标，每个评价指标都有R个离散的取值，则每个应用对应一个应用偏好矩阵G：

其中，gmr表示用户对应用的第m个特性的偏好程度，gmr∈[0，1]，0 代表用户反感，1 代表用户喜欢，m∈{1，2，…，M}，r∈{1，2，…，R}。W=[W1W2…WM]为M个评价指标的权重值矩阵，用户对第n个应用的偏好性如式（2）所示：

其中，ε为用户偏好性的影响因子，λ为云原生应用商给出的微服务的租用比例。评价指标的取值数量R可以自行设定，依据大数定律，R趋于无穷大时，Bn收敛到常数值，具体如下：

1.3 云原生应用商能耗

云原生应用商提供云原生应用的过程主要包括：1）云原生应用的开发，其中主要为微服务的开发；2）维持云原生应用的运行。因此，云原生应用商能耗被定义为微服务开发能耗Ed和应用运行能耗Er之和，单位为瓦特。应用运行能耗Er包括微服务运行能耗Emr和传统应用运行能耗Etr。微服务开发能耗是开发时间的函数，表示为tdevedev，其中，edev为单位时间内微服务开发所需能耗。综上，云原生应用商的总能耗计算公式如式（4）所示：

其中，emr、etr分别为单位时间内微服务运行和传统应用运行的能耗，tdev、trun分别为微服务开发和应用运行的时间，eidle为空闲时应用所消耗的能耗，Ttotal为应用开发和运行的总时间。

2 博弈创建

面向5G 网络的云原生应用资源调度策略采用Stackelberg 博弈进行优化。Stackelberg 博弈模型至少包括博弈方、博弈的策略空间和博弈的效用函数［16］3 个元素。Stackelberg 博弈是一种符合主从关系的博弈，博弈方一般由主导者和追随者构成，博弈双方都存在各自的效用函数和策略空间［17］。本文的博弈过程可描述为：

1）主导者根据效用函数做出决策。

2）追随者根据主导者的效用函数和决策给出自己的决策。

3）主导者根据追随者的决策和自己的效用函数调整自己的决策。

4）博弈双方通过调整各自的决策从而达到纳什均衡，最终使双方的效用达到最优。

2.1 博弈构成

Stackelberg 博弈模型的3 个元素具体如下：

1）博弈方：主导者是X个云原生应用商，追随者是Y个云原生服务提供商。

2）博弈的策略空间：主导者的策略空间是云原生应用商给出的微服务的租用比例λxy，追随者的策略空间是云原生服务提供商制定的微服务价格P={P1，P2，…，PY}。

3）博弈的效用函数：主导者的效用函数是云原生应用商的效用Ux，追随者的效用函数是云原生服务提供商的效用Uy。云原生应用商的效用函数Ux由云原生应用商所得收益Uprofx（如式（5）所示）与用户租用微服务的租金Urentx和运行能耗Ex之差构成，如式（6）所示。

其中，T为单位时间内应用的被访问次数，S为每次服务的单价。

云原生服务提供商的效用函数Uy由租用微服务收取的费用Pyφyλxy和微服务管理成本Cyφyλxy之差构成，如式（8）所示：

2.2 问题创建

在微服务分配的过程中，云原生应用商通过租用云原生服务提供商的微服务来开发自身应用，以降低应用的时延和能耗，从而为用户提供优质的服务并提高自己的收益。云原生服务提供商可以通过租用微服务来获取一定的收益，最终通过博弈使云原生应用商与云原生服务提供商的收益最大化。

云原生服务提供商的优化问题可以视为使其效用函数最大化的问题，表达式为：

云原生应用商的优化问题也可以创建为其效用函数最大化问题，即：

效用函数最大化意味着云原生应用商收益最大化且能耗达到最优。通过对式（7）进行推导，可以得到云原生应用商的效用函数，即：

通过博弈构建过程可知，云原生服务提供商的博弈目的是最优化自己的效用函数值。云原生应用商依据收益和能耗租用一定比例λ的微服务，λxy的大小取决于云原生服务提供商的微服务定价Py，如果微服务的定价过高，云原生应用商将不会租用微服务；反之，如果微服务定价过低，云原生服务提供商难以获得利润。因此，云原生服务提供商只有进行合理地定价，云原生应用商才能选择合适的租用比例，使双方效用函数最优化，从而提高用户体验质量并使能耗达到最优。

2.3 纳什均衡

Stackelberg 博弈由多个云原生应用商和多个云原生服务提供商构成，由于云原生服务提供商资源有限，因此多个云原生应用商之间存在竞争关系。同时，每个云原生应用商的租用策略会影响云原生服务提供商的微服务定价，从而影响其他云原生服务提供商的租用策略，因此，云原生应用商之间存在非合作博弈关系。

纳什均衡是非合作博弈的最优解，是博弈参与者之间策略空间的稳定状态，即不存在一个博弈参与者能够通过改变对应的策略空间来取得更多的收益［18］。对于非合作博弈而言，如果博弈满足如下条件：

1）博弈方的集合有限。

2）博弈参与者的策略空间集合为欧氏空间中的封闭、有界以及非空的凸集。

3）博弈的效用函数在博弈参与者的策略空间中满足连续的性质且为凹函数。

则可以证明该博弈过程存在纳什均衡解，每一个博弈方的效用函数都可以达到最优化，且任何博弈的参与者不能通过改变自己的策略来获得更高的收益［19］。

纳什均衡的证明过程如下：

1）设主导者（云原生应用商）为X个，追随者（云原生服务提供商）为Y个，则对应的集合有限。

2）博弈参与者的策略空间显然是欧氏空间中的有界非空闭集，且效用函数在策略空间上连续。

3）对效用函数Ux求一阶和二阶偏导数分别可得：

显然，存在一阶偏导数（如式（12）所示）和二阶偏导数（如式（13）所示），且二阶偏导数小于0，可得效用函数在策略空间上满足严格凹函数特性。

综上，云原生应用商之间的非合作博弈存在纳什均衡解，证毕。

3 策略优化

云原生服务提供商的微服务资源有限，因此，云原生应用商的租用比例应该符合实际情况。本文考虑租用比例的合理性，通过求最值来确定租用比例的边界条件，然后通过拉格朗日乘数法对博弈进行优化求解，最后利用迭代方法给出云原生应用商的最佳租用比例以及云原生服务提供商的最佳定价。策略优化过程具体如下：

假设微服务资源足够所有云原生应用商使用，云原生服务提供商给出一组微服务租用价格P={P1，P2，…，PY}，通过求导可得云原生应用商的最佳租用比例，如下：

由式（14）可知，当λ=0，即云原生应用商的租用比例为0 时，云原生应用商将不会租用微服务，此时云原生服务提供商和云原生应用商都不会在云原生网络中受益，而且用户体验质量不能得到改善。因此，存在微服务定价的最大值，由λ=0 可以求得微服务定价的最大值为：

当λ=1，即云原生应用商的租用比例为1 时，云原生应用商将租用所有微服务，由于云原生服务提供商资源有限，而且租用所有微服务会导致云原生服务提供商效用减少，因此存在微服务定价的最小值。由λ=1 可以求得微服务定价的最小值为：

综上，存在微服务定价的最大值和最小值，当定价小于最小值时，云原生服务提供商应该上调当前的租用价格；当定价大于最大值时，云原生服务提供商应该下调当前的租用价格。通过多次调整来达到最佳微服务定价，最终使两者利润最大化，同时提高用户的体验质量。

在实际情况中，云原生服务提供商的微服务资源情况不可忽略，其需满足式（17），而且云原生应用商的租用比例应该满足0 ≤λ≤1。

其中，Fmax是微服务资源数量的最大值。

本文利用拉格朗日乘数法对博弈进行优化求解，首先构建拉格朗日函数如下：

其中，ω、ξ、υ为拉格朗日函数中的拉格朗日乘数。拉格朗日函数的充分必要约束条件为：

经过推导可得微服务的最佳租用比例如式（20）所示：

其中，γ的表达式如式（21）所示，其为云原生服务提供商微服务资源的约束条件。

对云原生服务提供商的效用函数求最大值可得到微服务资源的最优定价Py，将微服务的资源租用比例最佳取值代入式（8）进行求导，求导结果如式（22）所示，令导数为0 可反解出Py，每次更新的微服务资源定价如式（23）所示。

由式（23）可知，单个微服务资源的最优定价是动态变化的，它与其他云原生服务提供商的微服务定价密切相关。因此，本文采用迭代法对微服务的最优定价进行求解，迭代公式如下：

其中，t为迭代次数，为第t次迭代时微服务资源的定价，为第t次迭代时微服务资源管理的成本价，ρ为迭代步长，其为一个递减参数，取值随着迭代次数的变大而逐渐变小。在实际情况中，递减参数值过小或过大都不利于纳什均衡点逼近，因此，本文引入柯西分布［20］对该系数进行优化，柯西分布较高的两翼概率特性使其可以产生远离原点并具有较宽分布范围的随机数，使策略可以在更宽的范围内寻找纳什均衡点，从而提高策略的收敛性能。优化后的迭代步长ρ*表达式如下：

当迭代次数为t+1 时，若云原生服务提供商和云原生应用商的效用值达到最大，则终止迭代过程；反之，进入下一个周期，直到两者效用值最大后停止迭代过程。

4 仿真分析

本文通过MATLAB R2016b 对所提策略进行仿真验证，网络模型由2 个云原生服务提供商和6 个云原生应用商构成，云原生应用商竞争微服务资源以开发应用。具体的仿真参数设置如下：单个云原生服务提供商拥有500 个微服务资源，λ=0.6，ε=0.2，R=50，T=100，S=2。在仿真中，将本文策略与蚁群（ACA）算法［21］、全局最优（GOS）策略［22］、QOS 优先（QOS PA）算法［23］，分别在云原生应用商效用、用户满意度和能耗减少率3 个方面进行对比分析。

图2 所示为云原生服务提供商1 和云原生服务提供商2 之间微服务定价的关系，曲线上的点表示当前云原生服务提供商相对于另一个云原生服务提供商的最优定价策略。从图2 可以看出，（0.49，0.4）为2 条曲线的交点，即纳什均衡点，此处代表双方定价和效用达到最优。虽然云原生服务提供商之间的最优定价互相影响，但是总存在一组最优定价使双方效用最大化。

图2 2 个云原生服务提供商之间的微服务定价关系Fig.2 Microservices pricing relationship between two cloud native service providers

图3 所示为不同应用流行指数下云原生应用商的收益变化情况。从图3 可以看出，在相同迭代次数情况下，α值越大，云原生应用商越受欢迎，对应的云原生应用商收益越大。在α一定的情况下，随着迭代次数的增大，云原生应用商收益逐渐提高，当迭代次数约为50 时，云原生应用商收益值收敛到当前情况下的最大值。

图3 云原生应用商收益与迭代次数之间的关系Fig.3 The relationship between the benefits of cloud native application business and the number of iterations

图4 所示为不同策略和算法下云原生应用商的效用变化情况。从图4 可以看出，本文策略的效用函数明显优于其他策略和算法，且在4 种不同的策略和算法中，GOS 策略的收敛性能最好，在迭代次数约为45 时其收敛到最大值。

图4 云原生应用商效用和迭代次数之间的关系Fig.4 The relationship between the utility of cloud native application business and the number of iterations

图5 所示为不同策略和算法下用户平均偏好度和用户对应用的使用次数之间的关系，从图5 可以看出，随着用户对应用使用次数的增加，用户的平均偏好度逐渐增加，且本文优化策略的用户平均偏好度明显优于其他3 种策略和算法。

图5 应用使用次数与用户平均偏好度的关系Fig.5 The relationship between the number of applications used and the average user preference

图6 所示为不同策略和算法下应用使用次数与能耗减少率的关系，本次实验中假定不同策略和算法下用户产生的请求一致。从图6 可以看出，随着应用使用次数的增加，能耗减少率逐渐提高，且本文优化策略的能耗减少率性能优于其他3 种策略和算法。

图6 应用使用次数与能耗减少率的关系Fig.6 The relationship between the number of applications used and energy consumption reduction rate

5 结束语

本文针对5G 网络中云原生应用的微服务资源调度问题进行研究，提出一种面向云原生应用资源调度的博弈优化策略，以提高云原生应用商和云原生服务提供商的收益，降低网络能耗，提高用户的体验质量。将云原生应用资源调度问题建模为多主多从的Stackelberg 博弈模型，对传统收益进行具体描述，引入用户偏好性指标，以提高云原生应用商和云原生服务提供商的传统收益。针对资源调度过程中的能耗问题，对能耗和传统收益进行联合建模，证明纳什均衡解的存在，并使用分布式迭代方法确定云原生应用商的最佳租用比例和云原生服务提供商的最佳定价，在此基础上，通过Stackelberg 博弈实现效用的最大化。仿真结果表明，该策略能够有效提高网络收益并降低网络能耗。本文工作对构建未来的绿色网络有一定参考意义，下一步将在5G 网络和信息中心网络中联合部署云原生应用，以提高内容分发率并降低网络能耗。