基于Stackelberg 博弈的边缘云资源定价机制研究

刘荆欣，王 妍,2+，韩 笑，夏长清，宋宝燕

1.辽宁大学 信息学院，沈阳110036

2.中国科学院 沈阳自动化研究所 机器人学国家重点实验室，沈阳110016

3.中国科学院 沈阳自动化研究所 网络化控制系统重点实验室，沈阳110016

4.中国科学院 机器人与智能制造创新研究院，沈阳110169

随着移动计算和物联网时代的发展，传统的云-端集中处理方式逐渐显现出诸多弊端。相比于云计算的不足，移动边缘计算（mobile edge computing，MEC）解决了网络负载大、高时延、带宽不足等问题。MEC 可以将计算资源丰富的边缘设备转化为边缘云，资源受限的终端设备可以通过无线网络将任务卸载到边缘云服务器，实现云-边-端的分布式管理模式。

在MEC 系统中，计算资源的管理对于提高系统资源利用率和优化系统资源效益起着关键作用。边缘云服务器处理外来任务会消耗本地计算资源，因此，终端设备需要依据边缘云的资源定价机制支付一定的服务费用，旨在激励边缘云提供充足的计算资源。

现有定价机制如拍卖机制依赖于中间商的静态定价，不足之处一方面表现为拍卖双方需要向中间商支付额外的服务费用，总成本增加使得资源交易双方无法实现最优效益；另一方面静态定价不能很好地满足终端设备资源需求的动态变化，终端设备对资源的总需求量减少，边缘云服务器难以实现本地资源的有效利用。为解决上述问题，本文构建基于Stackelberg 博弈的边缘云资源定价机制，在最大化资源供需双方效益的同时实现计算资源的有效利用。主要研究贡献如下：

（1）针对资源定价时终端设备存在因资金不足而导致的本地任务搁置问题，本文提出包含贷款和激励的辅助机制，用以增加终端设备的参与积极性与资源需求量，实现终端设备任务的及时处理。

（2）针对博弈时间过长与价格制定不准确带来的问题，提出影响资源定价的四种价格导向因素，根据价格导向因素制定了一致性与弹性两种定价方案，为后续的动态定价做准备。

（3）针对传统静态定价策略成本高且无法满足终端设备的动态性需求问题，构建基于Stackelberg 博弈的资源定价机制，为终端设备提供不同资源需求下的价格差异化服务。该模型将资源需求与定价问题转化为边缘云收益最大与终端设备支付成本最小问题。

（4）移动边缘计算对资源定价的实时性要求高，本文设计出一种改进的强化学习SARSA 算法，可以较快获得边缘云资源定价的最优解。实验表明，改进的SARSA 算法的性能较优于其他算法。

1 相关工作

近年来，很多学者对边缘系统效益的最优资源定价问题进行了相关研究，主流的研究分为定价导向因素与最优定价求解两个方向。

在资源定价导向因素的研究中，文献[9]提出一种云计算资源定价算法，该算法通过分析资源的历史利用率，不断迭代得到当前的资源价格。但是该定价算法仅考虑资源利用率的使用情况，未分析影响定价的其他导向因素。在文献[10]中提出基于价格的分布式算法。该文献仅以任务调度作为资源定价的研究点。文献[11]为云中心设定了静态的资源定价方案，虽然定价操作简单但不能满足终端设备的动态性需求，但是难以实现资源的有效利用。文献[10-11]都没有考虑用户需求与资源价格的实时关系，无法依据用户需求动态调整资源价格。

在资源定价机制中另一主要研究点为资源价格的最优求解方法。现有最优求解大多采用拍卖思想与博弈理论。在文献[12]中，作者通过拍卖算法实现系统效益和多维资源的联合优化，定价方式为系统性能的提升与单位效益的乘积。但该算法以每轮拍卖结果为优化目标，导致结果难以趋近全局最优且系统的执行成本高。在云计算或MEC 的资源定价与分配问题中，文献[4,11,13]均采用Stackelberg 博弈理论。在文献[4]中，作者将提供商和需求者的相互作用建模为Stackelberg 游戏，并通过Wolf-PHC 算法搜索最优定价策略。但由于Wolf-PHC 为确定性策略，易受外部环境的影响，同时需要遍历整个Q 表，导致时间复杂度高。在文献[11,13]中，均通过博弈理论的逆向归纳方法求得纳什均衡解。但逆向归纳方法是从博弈的最后阶段对每种可能路径进行比较，若出现不同路径却有相同利益时，该方法无法确定唯一的最优路径，适用性失效。

通过分析可以得出，目前的研究未深入分析影响资源定价的导向因素，而资源定价时定价导向因素的变动将直接影响定价准确性。在资源定价的最优求解方法上还存在求解结果难以趋近全局最优、资源利用率低、执行时间复杂度及费用高等问题亟待解决。

2 边缘云资源定价系统模型

针对资源定价场景中存在的终端设备任务处理不及时与边缘云资源定价不准确等问题，本文构建了边缘云资源定价系统模型，旨在最大化边缘云效益的同时为终端设备提供计算资源服务。如图1 所示，资源需求辅助机制包括贷款机制和激励机制。贷款机制可以促使终端设备尽可能多地使用边缘服务器并实现本地任务的实时处理。设计激励机制的目的一方面在于减轻终端设备的支付成本，另一方面可以增加终端设备对计算资源的需求，进而提升系统的计算资源利用率。为了缩短边缘云资源定价时间并提高定价的准确性，设计了包含价格导向因素与定价方案的资源定价机制，实现边缘云的最优效益。本文将终端设备资源需求行为与边缘云资源定价行为设计成两阶段的Stackelberg 边缘云博弈模型，该博弈模型摒弃了第三方的参与，打破了静态定价无法满足资源动态性需求的局面，实现资源供需双方直接交互。为满足移动边缘计算的实时性需求，本文设计出一种改进的强化学习SARSA 算法，可以较快获得边缘云资源定价与终端设备资源需求的最优解。

图1 边缘云资源定价系统模型Fig.1 Edge cloud resource pricing system model

2.1 资源需求辅助机制

在资源定价场景中，当终端设备的剩余资金难以负担资源的支付费用时，本地任务将无法得到及时的处理，因此，提出包含贷款机制与激励机制的资源需求辅助机制，以缓解终端设备的任务执行压力，实现任务的及时处理。

针对终端设备在资源定价场景下存在因资金不足导致任务被搁置问题，提出基于信用度的贷款机制，以保证终端设备参与任务卸载的积极性。令a∈{0,1}表示终端设备的资金状况，a=1 表明资金充足，等待资源提供者定价；a=0 表明没有足够的资金购买边缘云资源，致使本地任务无法及时处理。为解决此问题，提出基于信用度的贷款机制，允许终端设备向临近的边缘云服务器发送贷款请求。

当边缘云服务器接收到贷款请求后，会立即对贷款者G的信用度进行多方位的审核，审核内容包括：（1）贷款者需持有一些本地资源，可以服务外来小额任务；（2）贷款者是否成功偿还系统规定的押金数额；（3）根据终端设备以往贷款纪录计算的信用度为非负值。终端设备的信用度计算公式为：

其中，()为当前计算的信用度，设定()的初值()=10。()为上轮信用度，()为本轮贷款金额，为常量。

边缘云服务器会给审核通过的终端设备发放贷款金额()，并为其设定贷款利率和未按时还款的惩罚因子。若贷款者在规定时间内偿还()与贷款利息，则=0 且()值加1。未按时还款时=1，信用度减1，并产生额外的惩罚金额。惩罚金额()的计算公式为：

其中，代表逾期利率，t是规定的还款时间，t是逾期时间，是贷款利率，是未按时还款的惩罚因子。若G拒绝还款或未在系统可容忍的最大时间内还款，边缘云服务器将没收终端设备的押金，并向全网广播G的个人信息，所有设备都将拒绝为G提供资源服务。

终端设备进行任务卸载时，除了存在因资金不足导致任务无法执行问题外，还将面临由支付资源费用所引发的资金压力，而这会在一定程度上削弱终端设备增加资源需求的动机。为此，提出基于诱导因素的激励机制，该激励机制鼓励终端设备向云中心共享数据以获得相应的奖励，旨在通过终端设备、边缘云服务器、云计算中心三者间的协同合作增加终端设备的总资源需求并提高资源利用率。首先，边缘云服务器作为任务处理商，会将任务处理结果相继反馈给终端设备及云数据中心。而后，云中心充当数据收集站，将给予作为原始数据提供者的终端设备相应的奖励。激励机制计算公式如下：

其中，表示云中心设定的固定奖励，(G)表示G的资源需求e相对于系统总资源需求的占比，表示终端设备基于激励机制所得奖励，其值与资源需求量e成正比。基于诱导因素的激励机制一方面可以减少终端设备的支付成本，增加终端设备的任务卸载积极性；另一方面，激励机制与终端设备的资源需求量相关，一定程度上促进终端设备增强资源需求的动机。

2.2 边缘云资源定价机制

在移动边缘计算网络中，边缘云服务器持有有限的计算资源，为激励其提供资源服务，需要为边缘云制定合理的资源价格。本文提出影响资源定价的四种导向因素，并根据导向因素为边缘云制定一致性与弹性两种定价方案，以提高定价的准确性并为后续的动态定价做准备。

价格导向因素的分析是实现边缘云资源准确定价的基石。同样，价格的准确性将进一步影响交易双方的利益，本研究提出如下四种价格导向因素。

（1）资源总需求导向定价。边缘云服务器可根据本地资源剩余量与各终端设备资源总需求量间的实时关系，动态设置资源价格。当边缘云资源剩余量较少且终端设备的总需求较大时，可适当提高资源价格以赚取更多奖励。而当资源剩余量多且终端设备总需求较小时，可以适当降低资源价格刺激资源消费。总需求导向定价的价格调整因子α如式（4）所示，其中为当前边缘云服务器的资源剩余量，为各终端设备本轮的总资源需求。

（2）竞争环境导向定价。由于终端设备会优先选择可以提供相同服务且资源价格低廉的边缘云服务器，边缘云服务器必须考虑其他竞争者的定价策略。边缘云服务器本轮资源价格将以竞争者上轮的平均定价为依据，定义价格调整因子α如式（5）所示，其中′代表服务器设定的初始资源价格，代表上轮竞争者的平均资源定价。

（3）对象属性导向定价。边缘云服务器作为一种位置比较固定的基础设施，其身份信任度是可靠的。而终端设备因具有较强的移动性，其身份信任度很难确认。为此，本文将终端设备的行为可信度作为定价导向因素之一，边缘云通过对比各终端设备的当前可信度属性值，有选择性地为各终端设备设定资源价格，保证资源管理的安全性。定义价格调整因子α如式（6）所示，其中为常数，()表示终端设备的信用度。

（4）对象需求导向定价。各边缘云服务器可根据终端设备资源需求量的不同，调整售卖给各终端设备的资源价格，旨在激励终端设备的增加资源需求量。当终端设备资源需求量增多导致资源竞争加剧时，可适当调高资源价格获取收益；对于资源需求量少的终端设备，可通过降低资源价格来提升系统的总资源需求。定义价格调整因子α如式（7）所示，其中，为终端设备的本轮资源需求，上轮资源需求为，为上轮资源价格。

合理的定价策略不仅能够激励供需双方进行有序的资源交易，而且将促进双方利益的优化和资源的有效利用。依据不同导向因素的价格调整因子为边缘云服务器制定了一致性与弹性两种定价方案。

一致性定价下，边缘云服务器对本地资源的需求者设定相同的资源价格p，该定价方案对终端设备而言是公平的，没有价格差别，更容易实施。由于在单位时间内，每个边缘云的总需求导向定价和竞争环境导向定价的各价格调整因子α、α都是固定的，因此可以为接入网络的各终端设备设定一致的资源价格。一致性定价方案p的计算如式（8）所示。

弹性定价方案下，由于每个终端设备的属性值与资源需求量不同，边缘云服务器可根据对象属性与对象资源需求导向定价的价格调整因子α、α的差别性为终端设备制定不同的资源价格。弹性定价方案p的计算如式（9）所示。

3 最优资源需求与定价决策

为获得终端设备资源需求及边缘云定价的最优策略，首先，根据用户需求量与系统资源定价之间的实时关系，引入斯坦克伯格（Stackelberg）动态博弈模型，并分别为资源供需双方设置效用函数。其次，验证了非合作博弈中终端设备与边缘云服务器各纳什均衡点的存在性。最后，采用强化学习算法求解最优策略问题，旨在实现边缘云收益最大与终端设备支付成本最小。

3.1 基于Stackelberg 的边缘云博弈模型

由于边缘云服务器的资源定价策略是一个动态优化过程，现有的静态定价策略可能无法满足终端设备的动态性资源需求。因此，有必要设计一种合理的动态资源定价策略，以联合优化边缘云服务器的资源效益和终端设备的支付成本。本文构建了基于Stackelberg 博弈的资源定价模型，以实现资源需求与资源价格的动态调整。

图2 资源供需双方的Stackelberg 博弈过程Fig.2 Stackelberg game between resource supply and demand

阶段I、II 共同构成Stackelberg 动态博弈，博弈的目标旨在证明纳什均衡点(,)的存在性与唯一性。判定Stackelberg 博弈成立的条件为：

为了验证Stackelberg 博弈纳什均衡点的存在性，本文分析了边缘云服务器效用函数U和终端设备的效用函数U 的一阶、二阶导数。

3.2 基于改进的SARSA 算法纳什均衡求解

通过凹凸函数证明了终端设备与边缘云纳什均衡解的存在性，本节提出改进的强化学习算法得到博弈双方最优需求与定价决策。强化学习中很多场景涉及多智能体系统的交互，比如多玩家的博弈游戏。本节将终端设备与边缘云服务器的行为建模为多智能体交互，旨在实现所有设备的效益最大化。

针对现有最优求解方案存在适用性低、实现全局最优难度大及时间复杂度高的问题，提出改进的SARSA（state action reward state action）算法解决上述问题，算法思想如算法1 所示。

改进的SARSA 算法

输入：state space,action space,discount rate γ,learning rate,instant reward。

强化学习的目标是通过训练得到最优策略(,)，并通过状态值V()、状态动作值Q(,)评估期望回报。若满足Q(,)>V()，则可以调整p,p增加策略(,)的概率。终端设备及边缘云服务器值的更新策略分别为：

对于策略(s,a，根据状态转移概率、动作转移概率产生新的随机性策略(s,a)=(s,a。若新的随机策略满足()=arg minQ(,)，则()为最优需求策略。若满足()=arg maxQ(,)，则()为最优定价策略。

4 仿真实验

本章首先评估改进的多智能体强化学习算法的性能。然后根据实验结果证明，所提定价机制在最大化资源供需双方利益方面优于现有的其他算法。最后，通过广泛的数值模拟两种定价方案对最优资源需求及定价的影响，旨在得到最优定价策略。

4.1 实验对比

仿真实验基于Python 语言环境进行，在仿真模拟中，通过强化学习算法不断训练得到资源供需双方的最优策略。简单地将终端设备的资源需求动作空间定义为A={20,21,…,90}，边缘云服务器的定价动作空间定义为A={50,51,…,90}。一些默认参数值设置如下：设定=0.000 5，=2，边缘云的资源成本=2，贷款利率=2%，惩罚因子=5%，折扣率=0.6，学习率∈(0,1]。为保证多agent 能够收敛到最优解，将最大集数设定为6 000。首先通过仿真实验将现有最优策略的求解方法与所提强化学习方法对比，仿真实图像如图3 所示。

图3 展示了四种算法的收敛性能与环境适应性能。由图可知逆向回归算法未在有限迭代次数内收敛，其余三种算法均收敛于一个稳定值，且本文所提算法的迭代次数最少。这是因为逆向回归算法无法根据环境的改变及时调整路径，需进行全局搜索，导致收敛性能差。而改进的SARSA 算法通过状态、动作转移概率，增加可能取得最大值的策略概率。在环境适应性能方面，WOLF-PHC 与改进的SARSA算法优于另外两种算法，这是由于两种算法为尽快地训练出最优策略，引入学习因子，并依据值的变化实时调整。SARSA 与改进的SARSA 学习算法收敛性能好，但由于SARSA 算法为确定性策略，易受环境影响，学习效果欠佳。通过与各种算法对比可知，改进的SARSA 算法的性能优于其他算法。

图3 四种求解最优策略的算法比较Fig.3 Comparison of four algorithms for solving optimal strategies

图4 是将本研究所提的两种定价方案与文献[9]、文献[11]中的定价方案进行的比较，旨在探究各定价方案对边缘云效益的影响。可以看出，随着迭代过程的推进，效用值曲线整体呈现上升规律。当迭代次数达到21 次，除了动态拍卖算法外，其余三种定价下服务器的效用值不再增加，收敛于最大效益值。这是因为动态拍卖算法将每轮的拍卖结果作为优化目标，导致结果难以趋近全局最优，收敛性能差。除此之外，弹性定价方案下边缘云效益值高于其他三种定价方案，效用值优于一致性方案24%。这是因为本文通过价格导向因子制定资源价格，价格制定的准确性对博弈过程中边缘云实现最大化自身效益至关重要。

图4 边缘云效用函数的收敛情况比较Fig.4 Comparison of convergence of edge cloud utility functions

4.2 实验分析

本节通过实验数据比较一致性定价与弹性定价对最优资源需求与定价策略的影响，旨在为终端设备及边缘云选择最大化自身利益的定价方案。

首先评估两种定价方案下终端设备数量对最优资源定价的影响，如图5 所示。在最高资源定价分别为80 和60 的情况下，一致性定价的最优价格均近似于最大价格，这是因为边缘云服务器的效益随价格的增加而增加，并有意将一致性定价下的最优价格设置为临近最大价格。而弹性定价下，最优价格略低于一致性定价，且最优价格随终端设备数目的增加而缓慢下降。这是由于弹性定价下，边缘云服务器可以有选择地为终端设备设定不同的资源价格，旨在鼓励终端设备购买更多的资源。

图5 终端设备数量对最优资源定价的影响Fig.5 Impact of number of terminal devices on optimal resource pricing

图6 评估了终端设备数量对最优资源需求的影响。可以看出，随着终端设备的增加，单个设备的最优资源需求下降。这是因为终端设备增多会加剧设备间的资源竞争，导致自身获得资源量减少。但弹性定价下的最优资源需求高于一致性定价，这是因为弹性定价可以基于定价导向因素为终端设备设置不同的资源价格，使得终端设备有动力申请更多的资源服务。且=6 000 时的资源需求低于=8 000，这是由于奖励增加可以降低终端设备的支付成本，从而激励终端设备增加资源需求量。

图6 终端设备数目对最优资源需求的影响Fig.6 Impact of number of terminal devices on optimal resource demand

图7 展示了两种定价方案下终端设备效用函数的收敛情况，即支付成本的收敛情况。可以看出，当迭代次数为18 时，两种方案下终端设备的效用值达到最小且不再变化，并且弹性定价下的支付成本略低于一致性定价7%。这是因为弹性定价会促使终端设备增加资源需求量，获得更多的云中心奖励，并且弹性定价下最优资源定价低于一致性定价。因此，终端设备在弹性定价方案下实现最小化支付成本，获得资源需求的纳什均衡解。

图7 两种定价方案下终端设备效用函数的收敛情况Fig.7 Convergence of utility functions of terminal devices under two pricing schemes

5 结束语

针对现有定价机制在定价导向因素与最优定价求解方面存在价格制定不准确，最优解难以趋近全局最优，依赖中间商的静态定价费用高，资源利用率低，执行时间复杂度高等上述问题，本文构建了一种基于Stackelberg 博弈的边缘云资源定价机制模型。首先，提出了包含贷款和激励的辅助机制以促使终端设备任务的及时处理；其次，提出了影响资源定价的四种价格导向因素，并据此制定一致性与弹性两种定价方案，提高了定价的准确性和效率；然后，构建了基于Stackelberg 博弈的资源定价机制模型，实现了资源需求与资源价格的动态调整，联合优化了边缘云服务器的资源效益与终端设备的支付成本；最后，通过改进的强化学习SARSA 算法得到了资源需求及定价的最优策略。实验表明，改进的SARSA 算法在收敛性能、学习效果、边缘云效益等方面优于其他最优求解算法，同时终端设备和边缘云服务器的效用函数均在弹性定价方案下实现最优。本文所提定价方法在多终端设备同时与同一边缘云服务器博弈的情况下，博弈进程的时间可能略有增加，后续工作将针对现有方案存在的不足之处加以完善。