基于超模博弈的移动边缘计算边缘服务定价研究

杨桂松， 程 浩， 李 俊， 何杏宇

（1 上海理工大学 光电信息与计算机工程学院， 上海 200093； 2 国家工业信息安全发展研究中心， 北京 100040；3 上海理工大学 出版印刷与艺术设计学院， 上海 200093）

0 引言

随着物联网和移动设备的发展，移动边缘计算［1－2］成为一种流行的计算范式。 在此范式中，计算和存储资源被下放到网络边缘，为移动用户提供高性能、低延迟的边缘服务。 现有关于移动边缘计算的研究主要集中在计算卸载和资源分配方面，很少有研究关注移动边缘计算中交易方面的问题，目前还不存在一个通用的边缘服务定价方法。

在移动边缘计算中，边缘服务提供商向移动用户出售边缘服务以支持其完成计算密集型任务［3－5］（如自动驾驶、大型交互式游戏等）。 这是因为移动用户受自身移动设备限制，计算和存储能力有限，不能独立完成这些任务。 边缘服务提供商将边缘服务（包括计算服务、存储服务等）封装到一起出售给移动用户来赚取收益。 而移动用户购买边缘服务来满足自己相应的需求。

合适的边缘服务定价方法不仅能提高边缘服务提供商的收益水平［6］，也能改善移动用户的体验，这对促进移动边缘计算范式的发展和应用有重大意义。 定价问题在移动边缘计算相关领域已经有许多相关研究工作出现，包括网络服务定价、动态定价和车联网服务定价等。 文献［7］根据网络条件不断调整网络服务价格，将定价问题表述为成本最小化问题。 文献［8］通过放宽多个约束条件，将具有挑战性的定价问题转化为线性规划问题，提出一种动态定价策略。 文献［9］提出了一种新的多用户车辆辅助移动边缘计算网络动态定价策略。 也有一些研究工作考虑在不同价格和质量的网络服务中进行选择。 为了解决这一问题，文献［10］和文献［11］提出了一种拍卖机制，通过这种机制，网站服务代理可以自动选择边缘计算方案来支持其最终用户。 在文献［12］中，提出了一个利用边缘服务的资源分配拍卖模型，允许代理根据其能量贡献参与拍卖过程。

现有关于定价的研究没有针对边缘服务的特性设计一个适合边缘服务的定价方法。 在移动边缘计算中，如何根据移动用户需求变化和边缘服务提供商同行价格竞争制定最优边缘服务价格是一个关键挑战。 一方面，移动用户需求与边缘服务单价密切相关，边缘服务提供商的边缘服务市场需求受自身边缘服务单价影响。 对于一个边缘服务提供商而言，其他边缘服务提供商定价一定时，其定价越高，边缘服务市场需求越低；自身定价一定时，其他边缘服务提供商定价越高，自身边缘服务市场需求越高［13］。 除此之外，还需要考虑移动用户的主观因素，即部分移动用户考虑其他因素而不改变原来的需求。 例如由于边缘服务提供商的距离或信誉等因素，移动用户不会因为价格变化而改变自身需求。另一方面， 边缘服务提供商之间的同行价格竞争直接影响边缘服务定价。 对手的边缘服务定价越高，对自身越有利。 因此，每个边缘服务提供商要充分考虑同行的报价来制定自身边缘服务价格。 对于边缘服务定价问题，边缘服务具有可替代性和相异性，因此边缘服务提供商之间存在价格竞争关系。 博弈论可以很好解决竞争关系下的定价问题［14－18］。

基于上述讨论，为解决移动边缘计算中的边缘服务定价问题，提出一种基于超模博弈［19－20］的边缘服务定价方法。 该方法主要从边缘服务提供商的角度出发，在满足移动用户需求的前提下最大化边缘服务提供商的收益。 首先，将边缘服务定价过程建模成一个博弈模型，博弈的参与者是边缘服务交易市场中的所有边缘服务提供商。 参与者可以根据对手的边缘服务定价策略制定对自己最有利的定价策略［21］。 然后，通过理论分析，证明了该博弈是超模博弈，从而论证纳什均衡的存在性。 超模博弈表现为战略互补性，这意味着当一个参与者采取更好的行动时，其他参与者也会效仿其行动。 超模博弈以格点理论和比较静力学的数学理论为基础，具有快速收敛的性质。 最后，为求解超模博弈的纳什均衡，通过迭代近似的方法不断逼近纳什均衡，得到最优边缘服务定价。 本文的主要贡献总结如下：

（1）研究并提出移动边缘计算中的边缘服务定价问题，为边缘服务交易市场繁荣提供支持。

（2）将边缘服务提供商之间的边缘服务定价过程建模成博弈模型，准确描述了边缘服务提供商同行价格竞争关系和移动用户需求对边缘服务定价的影响。

（3）设计一种梯度迭代算法，求解超模博弈的纳什均衡，解决了边缘服务定价问题，在满足移动用户需求的前提下提高了边缘服务提供商的收益。

1 系统描述

在移动边缘计算中，边缘服务交易过程是：边缘服务提供商将边缘服务打包出售给移动用户，支持其完成计算密集型任务，以此赚取收益、即移动用户支付的报酬，如图1 所示。

图1 边缘服务交易过程Fig. 1 The process of edge services transaction

假定边缘服务交易市场中有n家边缘服务提供商，用E ＝｛e1，e2，...，en｝ 表示，其中，ei表示第i家边缘服务提供商。 在边缘服务交易中，边缘服务提供商代表卖家，移动用户代表买家。 边缘服务以固定份额进行出售，其属性包含单位成本和单位价格。 由于地理位置、计算和存储能力大小等因素，不同卖家提供的边缘服务单位价格和单位成本是不同的，用pi表示第i家边缘服务提供商ei的边缘服务单位价格，ci表示其边缘服务单位成本，qi表示边缘服务交易市场中所有移动用户对ei的边缘服务需求。 假定边缘服务单价对市场需求的影响是线性的，即：

其中，αi为边缘服务提供商ei能满足边缘服务交易市场的最大边缘服务需求量；θi为ei自身需求价格系数，表示边缘服务提供商ei的市场需求受自身边缘服务单价影响程度；σij为边缘服务提供商ei关于另一家边缘服务提供商ej的需求价格系数，表示边缘服务提供商ej的边缘服务单价对边缘服务提供商ei市场需求的影响。 明显可知，αi，θi，σij＞0，i，j ＝1，2，…，n。 因此，边缘服务提供商ei的收益yi可以计算为：

2 边缘服务定价

2.1 博弈模型

在边缘服务定价过程中，每家边缘服务提供商在制定边缘服务单价时不知道其他边缘服务提供商的边缘服务单价，只能在一次出价完成后，才能根据其他边缘服务提供商的边缘服务单价调整自身边缘服务单价。 假定所有边缘服务提供商不存在恶意竞争情况，也没有部分边缘提供商联合出价以谋取更多收益的情况，每家边缘服务提供商都处于公平竞价地位。

根据上述特征，该边缘服务定价过程可以被描述为非合作静态博弈，即每个博弈参与者都是自主进行决策，与这个策略环境中其他参与者无关。 在博弈定价过程中每个边缘服务提供商首先给出初始边缘服务定价，然后根据对手定价调整自身定价，相互博弈直到定价达到纳什均衡，得到最优边缘服务定价。 此博弈过程充分考虑了边缘服务提供商同行价格竞争和移动用户需求，具体过程如图2 所示。

图2 博弈定价Fig. 2 Game pricing

一个通用的博弈模型包含3 个重要元素：参与者、策略和效用函数。 其中，参与者是指边缘服务交易市场中的所有边缘服务提供商ei（i∈n），策略指的是每个参与者的边缘服务定价pi（i∈n）。 考虑到边缘服务交易市场规律和移动用户承受能力，所有边缘服务提供商的边缘服务定价只能在一定范围内调整，即∀i，i∈n，pi∈［pmin，pmax］。 效用函数指的是边缘服务提供商的期望收益函数，可表示为Ui（P） （见后文公式（5）），P ＝｛p1，p2，…，pn｝，即参与者ei的效用Ui（P） 等同于参与者ei在所有参与者出价为P时的期望收益。 每个参与者调整自己的边缘服务定价，使得自身效用最大化，最终得到最优定价，即定价的纳什均衡，用P∗＝｛，…，｝表示，其中pi∗表示参与者ei的最优定价。

在边缘服务交易市场中，大部分移动用户主要考虑价格因素会随着边缘服务提供商调整价格而改变之前所选择购买的边缘服务提供商，同时其余移动用户不会随着边缘服务提供商调整价格而改变之前所选择的购买对象。 为了计算方便，假定前者占比为α（0＜α ＜1），后者占比为1－α。 因此，边缘服务提供商ei的边缘服务市场需求受市场上所有边缘服务提供商的价格向量P和α的共同影响，可表示为：

公式（3）表达的含义是边缘服务提供商ei的市场需求是由自身需求价格函数和剩余所有边缘服务提供商的需求价格函数共同决定。α越大表示边缘服务交易市场中受价格因素影响的移动用户越多，边缘服务提供商的市场需求受自身需求价格函数的影响越大，受其他边缘服务提供商的需求价格函数影响越小。

此外，边缘服务市场是动态且复杂的，存在一些突发状况，比如某些社会事件（一款火热的大型交互式游戏出现），使得移动用户的边缘服务需求增加或减少。 考虑市场需求的不确定性和不稳定性，对边缘服务提供商的需求加上一个随机扰动，可表示为：

其中，ξ为随机扰动因子。 每家边缘服务提供商会根据竞争对手当前定价策略，调整边缘服务定价，以实现自身收益最大化。 将边缘服务提供商ei的期望收益看作其效用，根据式（1）～式（4）可得：

2.2 博弈模型的超模性分析

为分析上述非合作静态博弈的性质，对边缘服务提供商（参与者）的效用函数进行分析，发现参与者之间的定价策略具有互补性，即参与者的最优反应对应关于对手的定价策略递增。 而超模博弈为具有互补策略的博弈提供了一个一般解决方法，下面给出超模博弈的定义。

定义1 超模博弈对于一个集合S， 若其中任意2 个元素a和b的上确界都在S中，其中上确界记为a∨b，下确界记为a∧b， 则称S为格子。从格子S到实数R的函数F， 即F：S→R， 若对于∀a，b∈S，都有F（a）＋F（b）≤F（a∨b）＋F（a∧b），则称F（a） 为S上的超模函数。

根据定义1 可知，超模博弈具有2 个明显的特征：策略集S是R的子格，效用函数F关于自身和竞争对手的策略均是递增差分的，即效用函数是策略集上的超模函数。 由2.1 节内容可知，每家边缘服务提供商的定价范围在实数范围内是闭集，即pi∈［pmin，pmax］， 这表明其策略集是实数R的子格。 因此，只需证明其效用函数是策略集上的超模函数即可说明该博弈是超模博弈。 为了简化边缘服务提供商效用的表达形式，设计一个函数如下：

边缘服务提供商ei的效用函数可简化为如下：

对于边缘服务提供商ei定价集合中的任意2 个定价pi和有：

由式（8）和式（9）可得：

此效用函数满足定义1 的条件，因此该博弈为超模博弈，可表示为G ＝｛E，{pi}i∈n，{Ui}i∈n｝。 根据超模博弈的性质［13］可知，该博弈模型一定存在纳什均衡，且纳什均衡点唯一，也就是每个边缘服务提供商都有唯一的最优定价。 求解最优定价可表示如下：

根据公式（11）可以求得每个边缘服务提供商的最优定价，即定价的纳什均衡P∗。 由于每家边缘服务提供商的定价彼此相互影响，很难根据联立的n个方程（类似于式（11）的形式）直接求解纳什均衡。 因此，本文考虑使用梯度迭代更新的方法，不断迭代更新来逼近所有边缘服务提供商定价的纳什均衡。 具体求解过程见2.3 节。

2.3 梯度迭代更新算法设计

根据超模博弈的性质可知，超模博弈可以从任意初始值收敛到纳什均衡。 由于边缘服务提供商拥有的边缘服务数量、提供边缘服务的效率等均各不相同，每家边缘服务提供商的初始定价也是不同的。所有边缘服务提供商同时出价，不分先后。 为了实现定价快速收敛和充分考虑定价相互影响之间的均衡，每家边缘提供商都按效用函数梯度的方向更新自身边缘服务定价，可表示为：

其中，ε表示学习率，即调整定价的速率。 这里▽Ui（P） 可计算为：

根据边缘服务定价的更新公式可以设计梯度迭代更新算法，所有边缘服务提供商依次更新自身边缘服务定价，直到边缘服务定价达到稳定状态，即定价的纳什均衡。 由于本文的超模博弈考虑了移动用户需求的影响，此博弈可能在某些特殊情况下（如边缘服务交易市场中受边缘服务价格因素影响的移动用户占比过少）不能达到纳什均衡。 这并不是违背超模博弈必定存在纳什均衡的性质，因为在特殊情况下，边缘服务提供商之间的定价过程可能不适用于建模成超模博弈，需要考虑更多的因素，建模成其它的博弈，如不完全信息博弈等。 梯度迭代更新算法的伪代码如下。

算法1 梯度迭代更新算法

输入初始定价向量P

输出最优定价向量P∗

1.参数初始化：最大边缘服务满足量ai，定价范围pmin，pmax，自身需求价格系数θi，对手影响价格系数σij，边缘服务单位成本ci，随机扰动因子ξ，学习率ε等

2. while （change ofpi＞ 1e － 5 or iteration numbers ＜＝max）

／／价格变化幅度大于一个精度或迭代次数小于最大迭代次数

3.forifrom 1 ton／／所有边缘服务提供商

4.根据式（13）计算梯度▽Ui（P）

5.ei根据式（12）调整自身边缘服务单价

6.更新价格向量P

7.end for

8.end while

9.returnP∗／／定价的纳什均衡，即最优定价

3 实验结果和分析

为评估所提边缘服务定价方法的有效性，针对算法收敛性和边缘服务提供商的收益等指标进行仿真。 仿真环境是Python 3.8。 在仿真实验中，设置相关参数见表1。 参数设置的依据是边缘交易市场的一般规律，比如边缘服务提供商的市场需求受自身边缘服务单价的影响比受其他边缘服务提供商边缘服务单价影响大，因此自身需求价格系数大于对手影响需求价格系数。

表1 仿真参数表Tab. 1 Simulation parameters

3.1 边缘服务定价收敛性分析

首先分析仅受价格因素影响需求的移动用户占边缘服务交易市场不同比例时，所提算法是否能收敛，为每个边缘服务提供商找到最优定价。 为了使仿真实验具有一般性和普适性，本次仿真实验采用控制变量法，通过一组对比实验（6 次定价）来展示每家边缘服务提供商的边缘服务定价情况。 其中n ＝3，此仿真实验中共有3 家边缘服务提供商，所提供的边缘服务是相互可替代的。

图3 显示不同受价格因素影响的移动用户占比对梯度迭代算法收敛效果的影响。 其中，图3（a）、图3（b）和图3（c）分别显示α ＝0.9，α ＝0.7，α ＝0.5对算法收敛效果的影响。 可以看出当仅受价格因素影响的移动用户占比大于等于市场一半时，该算法有很好的收敛效果，能找到定价的纳什均衡点。 通过这3 张图的对比可以发现，当α ＝0.9 时，3 家边缘服务提供商的边缘服务定价收敛是最快的，曲线也是最平滑的。 这表明所提算法在仅受价格因素影响的移动用户占边缘服务交易市场主体时有很好的收敛效果，可以实现快速定价。

而图3（d）、图3（e）和图3（f）分别显示α ＝0.4，α ＝0.3，α ＝0.2 对算法收敛效果的影响。 可以看出仅受价格因素影响的移动用户占比小于市场一半时，算法越来越难收敛，最后呈现发散趋势。 这表明本文设计的算法主要是针对边缘服务单价对移动用户需求和边缘服务提供商的收益的影响，当价格不是影响移动用户购买边缘服务的主要因素时，不再适用。 通过这3 张图的对比可以发现，图3（d）和图3（e）可以收敛，而图3（f）直接呈发散趋势，迭代次数到达限制的最大迭代次数。 这表明所提算法的普适性有限，不能针对受价格以外的因素来解决边缘服务定价问题。 但这也从另一角度证明，当价格是影响移动用户是否购买边缘服务的主要因素时，所提算法可以很好解决边缘服务定价问题。

图3 算法收敛效果Fig. 3 Simulation of algorithm convergence effect

为直观表示算法收敛情况，算法迭代次数见表2。 由表2 可以看出，当受价格因素影响的移动用户占比越来越小，算法的迭代次数在增加，最后达到算法所设定的最大迭代次数。 这表明所提算法针对边缘服务定价问题的有效性，当移动用户主要根据价格而选择是否购买边缘服务时，所有边缘服务提供商的边缘服务定价均能达到稳定状态。

表2 迭代次数表Tab. 2 Number of iterations

3.2 边缘服务定价影响因素分析

为进一步研究影响边缘服务提供商定价高低的因素，在α ＝0.8 的边缘服务交易市场仿真环境中做了一组对比实验。 在此边缘服务交易仿真中，受价格因素影响的移动用户占比为大多数。 由第1 节系统模型部分的分析可知，边缘服务提供商受自身需求价格系数影响较大，因此考虑其最终的边缘服务定价高低是受自身需求价格系数影响。 为了验证这个猜想，在其他条件相同的情况下（除自身需求价格系数外使用表1 的参数），采用2 组不同的自身需求价格系数进行仿真实验，结果如图4 所示。

图4（a）显示3 家边缘服务提供商的自身需求价格影响系数分别为θ1＝0.6，θ2＝0.5，θ3＝0.8 的边缘服务定价情况。 可以发现边缘服务提供商e2的自身需求价格影响系数最小，其最终边缘服务定价最高，而边缘服务提供商e3的自身需求价格影响系数最大，其最终边缘服务定价最低。 图4（b）显示3家边缘服务提供商的自身需求价格影响系数分别为θ1＝0.8，θ2＝0.6，θ3＝0.5 的边缘服务定价情况。 可以发现与图3（a）相似的结果，即边缘服务提供商e3的自身需求价格影响系数最小，其最终边缘服务定价最高，而边缘服务提供商e1的自身需求价格影响系数最大，其最终边缘服务定价最低。

通过图4（a）和图4（b）的对比可以得出以下结论，在相同的边缘服务交易市场环境中，边缘服务提供商自身需求价格影响系数越低，其最终边缘服务单价越高，即边缘服务定价高低与自身需求价格影响系数负相关。 在实际交易中，如果边缘服务提供商所能出售的边缘服务量受其自身价格影响较小，说明其边缘服务相较于其他边缘服务提供商的边缘服务有优势，比如边缘服务质量高。 因此该边缘服务提供商在博弈定价过程中具有优势地位，其边缘服务定价也就最高。 另一结论是边缘服务提供商最终定价高低与其初始定价高低无关。 因为在图4（b）中边缘服务提供商e3的初始定价最低，最终定价却最高，而边缘服务提供商e2的初始定价最高，其最终定价却不是最高。 这表明在实际定价过程中，边缘服务提供商的初始定价方案是不合理的，仅根据自身情况给出初始定价，没有考虑移动用户的需求变化和同行的价格竞争。

图4 自身需求价格影响系数图Fig. 4 Self－demand price influence coefficient

3.3 边缘服务提供商的收益分析

从边缘服务提供商的角度分析所提出的定价方案对边缘服务提供商的收益的影响，即在每家边缘服务提供商调整边缘服务单价时，其收益是如何变化的。 在3.1 节实验的基础上，本节实验在α ＝0.8，θ1＝0.6，θ2＝0.5，θ3＝0.8 的边缘服务交易市场仿真环境中观察各家边缘服务提供商的收益和所有边缘服务提供商的总收益。

图5 显示3 家边缘服务提供商的效用U1、U2和U3变化情况，即期望收益随着边缘服务定价的不断调整而增加，最终趋于稳定。 这表明在博弈定价过程中，边缘服务提供商之间在综合考虑移动用户需求和同行价格竞争影响，可以给出“最优反应”，最终制定出使自身收益最大化的边缘服务单价。 值得注意的是，尽管每家边缘服务提供商的定价都是呈上升趋势，但这并不意味着其收益百分百呈上升趋势，因为当边缘服务提供商定价过高时，移动用户可能会选择购买其他边缘服务提供商的边缘服务。 每家边缘服务提供商的收益随着边缘服务定价的调整都得到了一定程度的提升，这证明所提定价方法的有效性。

图5 边缘服务提供商收益Fig. 5 Profits of edge services providers

为进一步分析所提定价算法的优越性，将所提梯度迭代更新算法与随机算法和贪婪算法相对比。随机算法指的是各边缘服务提供商根据各自边缘服务的情况进行随机定价，而不是通过博弈来进行定价。 贪婪算法指的是边缘服务提供商在定价过程中没有考虑移动用户的需求，贪婪地选择跟随所有边缘服务提供商中的最高价格作为自己的边缘服务单价。 边缘服务提供商收益对比如图6 所示。 图6 显示，在3 家边缘服务提供商e1、e2、e3的单独收益方面，所提算法的收益更高；在3 家边缘服务提供商的总收益方面，所提算法明显高于另外2 种算法，这体现了所提算法的优越性。

图6 边缘服务提供商收益对比Fig. 6 The comparison of the profits of edge services providers

4 结束语

本文研究了移动边缘计算中的边缘服务定价问题，提出一种基于超模博弈的边缘服务定价方法。该方法首先考虑边缘服务提供商之间的定价影响、不同移动用户对价格的敏感程度和边缘服务交易市场中的不确定因素，设计合适的效用函数，计算边缘服务提供商的效用。 然后，通过证明效用函数的超模性，论证该博弈定价纳什均衡的存在性。 最后，设计一种梯度迭代更新算法，求解超模博弈的纳什均衡找到最优边缘服务定价。 结果表明所提算法在收敛速度和提升边缘服务提供商收益的有效性。 在未来工作中，将考虑更复杂、更繁琐的边缘服务交易场景，探索更多针对不同类型边缘服务的定价方法。