移动边缘计算中基于Stackelberg博弈的算力交易与定价

吴雨芯，蔡 婷，张大斌

（1.广东白云学院大数据与计算机学院，广州 510450；2.重庆邮电大学移通学院大数据与软件学院，重庆 401520）

0 引言

随着物联网技术在诸多领域的不断应用与发展，位于网络边缘的移动智能设备数量正呈指数型增长。庞大的设备群每天都在产生海量的高速数据流，在爆炸式的增长速度下，传统集中式的物联网体系结构对设备安全、数据隐私、低延时传输提出了严峻的挑战［1］。区块链作为一种去中心化、防篡改、安全可跟踪的分布式账本技术［2］，可为物联网提供可行的高信任、低成本解决方案。引入区块链技术，可在缺乏信任的环境中建立一个可伸缩、基础设施成本降低、自治、用户隐私驱动的访问控制、数据完整性和防止网络攻击的全新物联网生态系统——物链网（Blockchain of Things，BoT）。

然而，BoT 中执行计算密集的区块链挖矿过程需要消耗大量的算力资源，这对计算和存储能力有限的轻量级移动智能设备而言是一项巨大的挑战［3-4］。为了解决资源约束问题，基于移动边缘计算的物联网云架构提供了计算卸载解决方案，允许轻量级设备将计算密集型任务卸载到边缘服务器［5-7］，从而使更多的移动智能设备节点可以直接参与区块链协商一致过程，有利于提高BoT 整体鲁棒性。与此同时，它将云计算资源带到BoT 的边缘，有效解决移动智能设备和远程云之间存在的高延迟与低能效问题。

为了在BoT 中实现计算卸载，算力交易不可避免地发生在矿工与边缘计算服务提供商（Edge computing Service Provider，ESP）之间。根据区块链中的工作量证明（Proof of Work，PoW）机制［8］，矿工需要购买更多的算力才能提高挖矿成功率，获取更多的奖励，这也意味着需要付出更高的成本代价。因此，ESP 与矿工之间出现了一个算力需求与定价博弈问题。ESP 以最大化自己的利润为目标设定算力资源价格，而矿工为了最大化自己的挖矿奖励从供应商那里购买算力。为了解决这个问题，本文以博弈者的行为序列为基础，将ESP与矿工之间的算力交易建模为一个两阶段Stackelberg 博弈过程：第一阶段，ESP 作为领导者设定算力资源价格，并向矿工收取计算卸载费用；第二阶段，矿工根据价格决定从ESP购买的算力服务需求。此外，考虑到矿工之间的非合作关系，本文对比了两种定价策略，即统一定价和歧视性定价。

1 相关工作

近几年，基于区块链和边缘计算的物联网框架得到广泛研究。由于区块链技术的自身特点，它能有效解决物联网中数据的安全传输和隐私问题。其中：Huh 等［9］提出一种基于Ethereum的区块链计算平台来管理物联网设备，利用智能合约存储来自智能设备的数据，以实现物联网设备之间的安全通信和同步；Kang等［10］提出一种基于信誉的数据共享方案，使用联盟链和智能合约有效地保证了车联网中数据的存储和共享；Liu等［11］利用基于区块链的数据硬币和能源硬币技术，以应对电动车辆云和边缘计算中信息和能源交易问题；Novo［12］基于区块链技术，提出一个完全分布式的可扩展访问控制体系结构，用于在物联网中仲裁角色和权限；Li等［13］使用区块链和无证书密码技术设计了一个安全可靠的大型物联网存储和保护系统。

区块链技术的加入，给资源受限的轻量级移动智能设备完成计算密集的挖矿任务带来不小的挑战，因此，基于移动边缘计算的计算卸载策略成为了研究热点。Liu 等［14］提出一种支持移动边缘计算的无线区块链框架，将计算密集型挖掘任务卸载到附近的边缘计算节点，并在边缘服务器中缓存区块的加密散列。Du等［15］研究了具有最小-最大公平性保证的混合雾/云计算系统中的计算卸载问题。Chen 等［16］在移动边缘计算中，提出一种基于Lyapunov 优化的多用户多任务计算卸载方法。Chatzopoulos 等［17］提出一种多层计算卸载框架FlopCoin，用于集成移动设备的分布式激励方案和分布式信誉机制。Sun 等［18］通过综合考虑资源的不稳定性、车辆计算能力的异质性和计算任务的相互依赖性，提出一种有效的车载云任务调度方案。Zhang 等［19］开发了一个多队列模型，以探讨卸载策略对物联网设备性能的影响，其中算力资源由边缘服务器提供。张海波等［20］结合免授权频谱技术，研究了车辆异构网络中任务卸载模式决策和资源分配问题。

此外，部分文献从博弈论的角度对移动边缘计算中算力交易进行了一系列的研究。Shah-Mansouri等［21］将物联网设备之间的竞争建模为一种计算卸载博弈，其目的是在分层的雾/云计算中最大化自己的体验质量。Li等［22］基于联盟链技术构建了一个安全的P2P能源交易系统，并利用Stackelberg博弈提出一种基于信用的支付方案，以保证高频率交易。Xiong等［23］建立了ESP与矿工之间的Stackelberg博弈关系，并应用逆向归纳法搜索纳什均衡。Wang 等［24］提出了设备通信网络中数据交易的两种定价模型，即基于Stackelberg 博弈的单买方/多卖方定价模型和基于单卖方/多买方定价模型的上升时钟拍卖模型。Jiao等［25］提出一种基于拍卖算法的算力资源定价机制，用于ESP 支持移动区块链挖掘任务。Guo 等［26］研究了移动边缘计算框架中的计算卸载问题，提出一种双层贪婪博弈卸载方案。Chen 等［27］提出一种基于智能体的强化学习系统，以模拟专业交易机制、监控交易者制定的不合理策略。

不同于上述工作，本文针对移动智能设备计算和存储能力受限的问题，结合移动边缘计算与区块链技术，在云挖掘机制的辅助下提出一种算力交易CPTP-BSG（Computing Power Trading and Pricing with Blockchain and Stackelberg Game）模型。利用Stackelberg 博弈对算力交易过程进行建模，并使用低梯度迭代算法计算统一定价与歧视性定价策略下的纳什均衡解。基于所提模型的实验验证了算法的有效性。

2 算力交易模型

本文模型CPTP-BSG的整体框架如图1所示。

图1 CPTP-BSG模型框架Fig.1 CPTP-BSG model framework

模型由云层、边缘层、设备层组成。设备层的每个节点通过部署在云服务器上的可信授权代理完成注册，以获取合法身份标识（IDentification，ID）和安全证书（Certificate，Cert），并使用椭圆曲线加密算法获取私钥（Private Key，PK）［28］，以生成账户地址（Wallet Address，WA）加入区块链。映射列表｛ID，Cert，PK，WA｝由授权代理生成并存储在帐户池中。

边缘服务器为移动智能设备提供算力服务，以实现计算卸载，提高区块链共识效率。云服务器为整个系统提供广域监视和控制，进一步提高系统的安全性。在云挖掘机制的辅助下，每个移动设备节点都可以从ESP处购买算力，并将密集的计算任务卸载到边缘服务器。由于各矿工之间存在相互竞争关系，计算能力越强意味着赢得记账奖励的可能性越大。

2.1 问题定义

CPTP-BSG模型中ESP与矿工之间的算力交易过程如图2所示。

假设矿工集合M={1，2，…，N}，每个矿工i∈M决定各自的算力服务需求。其中,表示矿工参与区块链数据同步的最小算力表示ESP能够提供的最大算力。由于成本负担，每个矿工不能无节制地增加其算力服务需求。根据区块链协商一致协议，矿工优先算出PoW 难题并获得奖励的概率与其算力直接相关。因此，本文定义αi表示矿工i在获得算力服务需求xi后具备的相应算力，如式（1）所示：

第一个挖矿成功并达成区块共识的矿工将获得奖励，包括固定奖励R和可变奖励rti两部分。其中r表示给定的可变奖励因子，ti表示矿工i挖掘的区块中包含的交易事务数量。另外，解决PoW 难题的过程会产生相关的计算成本，即矿工i支付给ESP的算力资源服务费。矿工的目标是最大化自己的预期利润Ui，其计算如式（2）所示：

其中：Qi(αi(xi)，ti)表示矿工i挖矿成功的概率，pi表示ESP 针对矿工i给出的算力资源价格。然而，矿工挖出的新区块在达成共识过程中会由于网络延迟太长而被丢弃，成为孤儿区块［29］。因此，挖矿成功的概率与区块成为孤儿块的概率Qorphan（ti）关系如式（3）所示：

根据文献［30］和文献［31］，区块挖掘在时间上遵循泊松分布，区块成为孤儿块的概率可近似表示如下：

其中：泊松分布参数λ表示单位时间内随机事件发生的平均次数，T（ti）表示区块传播时间。根据文献［29］，假设时间函数是线性的，T(ti)=z×ti，其中z＞0 表示给定的延迟因子。因此，式（3）可进一步表示如下：

2.2 Stackelberg博弈建模

两阶段Stackelberg 博弈如图3所示。在阶段Ⅰ，ESP作为领导者首先制定算力资源价格；在阶段Ⅱ，根据ESP制定的价格，矿工作为跟随者决定自己的算力服务需求。领导者和追随者在博弈过程中可以不断地调整策略，以实现利润最大化。通过逆向归纳方法，本文给出了领导者和跟随者的最优化问题。

图3 两阶段Stackelberg博弈模型Fig.3 Two-stage Stackelberg game model

2.2.1 ESP价格策略

ESP 的预期利润是矿工支付的算力服务费减去服务成本后获得的收入，服务成本c主要包括ESP提供算力服务期间所产生的耗电量、硬件磨损、操作和维护费用等。在阶段Ⅰ，ESP 设置价格策略{[pi]i∈M：0 ≤pi≤}以追求最大利润，其中表示最高价格。由此可得出ESP 的预期利润表示如式（6）所示：

2.2.2 矿工挖掘策略

根据ESP给出的价格策略以及与其他矿工之间的竞争关系，矿工i决定它的算力服务需求以实现预期利润最大化。据式（1）～（5）可得出，矿工i的预期利润Ui如式（8）所示：

2.3 纳什均衡分析

Stackelberg博弈的最终目标是寻找纳什均衡解［32］，即ESP和矿工通过博弈过程实时调整自己的策略，以实现双方利润的最大化。在本文所提CPTP-BSG 模型中，纳什均衡可定义如下。

定义1设p*是ESP 设定的算力资源最优价格，x*是矿工的最优算力服务需求，则（p*，x*）是纳什均衡点需满足的条件如下：

对于ESP 而言，当算力资源价格设定为p*时，预期利润高于任何其他的价格。对于矿工而言，当算力服务需求设定为x*时，预期利润高于任何其他的算力需求。值得注意的是，ESP 在制定价格时，可以采取两种不同的策略，即统一定价和歧视性定价。统一定价表示对所有矿工采用相同的算力资源价格，而歧视性定价表示ESP 针对不同矿工的不同算力服务需求，制定不同的算力资源价格。本文根据两种不同的定价策略，分析各自的纳什均衡。

2.3.1 统一定价

1）阶段Ⅱ：矿工最优算力需求。

在统一定价策略下，假设ESP给定一个价格pi=p，∀i。矿工根据价格p决定自己的计算服务需求xi，通过竞争以获取最大利润。根据式（8）可知，矿工预期利润Ui(xi，pi)在[,]区间显然是连续的，其关于xi的一阶和二阶导数如下所示：

其中，根据式（14）和式（16）可知，对每个矿工i有如下表达式成立：

因此，可知Π(p)是严格的凸函数，存在唯一的最优价格使得ESP预期利润最大化。

2.3.2 歧视性定价

在歧视性定价策略下，ESP 针对不同的矿工制定不同的算力资源价格。在Stackelberg 博弈过程中，ESP 与每个矿工i达到纳什均衡，从而实现整体利润最大化。同样的，利用逆向归纳方法对矿工的最优算力服务需求和ESP利润最大化进行分析。

1）阶段II：矿工最优算力需求。

在歧视性定价下，矿工的纳什均衡计算与统一定价策略类似。假设ESP 的价格策略为。根据统一定价下矿工的最优算力需求式（23）所示，可得出歧视性定价策略下矿工i的最优算力需求如式（28）所示：

3 均衡求解算法

为了求解Stackelberg 博弈均衡解，本文使用低梯度迭代算法实现ESP 和矿工利润的最大化。对于ESP 制定的算力资源价格，首先计算多矿工（追随者）非合作子博弈最优解，再将矿工的最优算力服务需求代入ESP 的子博弈过程，通过梯度迭代算法得到最优价格。算法步骤描述如下：

根据算法1，矿工i在第一次迭代时根据输入的初始价格pi确定其算力服务需求。ESP 在接收到矿工提交的算力服务需求后完成算力分配，并将更新后的价格广播给所有矿工，矿工再各自计算自身的预期利润函数最优解以获取下次迭代的最优算力需求。算法1 终止的条件是最新的价格策略小于阈值β，β决定了算法的执行时间和最终结果的准确性。阈值越小，最终结果越接近最优解，但同时会增加算法的迭代次数和执行时间。

4 实验结果与分析

为了验证所提算法的有效性，仿真实验将对比统一定价和歧视性定价策略下矿工算力服务需求和ESP最优价格的收敛性能。与此同时，为了进一步分析挖矿奖励和矿工数量对算力需求和最优价格的影响，本文对两种不同价格策略进行仿真实验，利用算法1 获得唯一的纳什均衡并解决最优定价问题。利用梯度迭代算法，可以得到领导者的最优定价策略，跟随者也可以获得其最优的算力需求购买策略。

4.1 安全性分析

本文算法基于区块链技术，允许矿工与ESP 在云挖掘机制和智能合约的辅助下完成算力交易。因此，CPTP-BSG模型可通过标准的加密算法防御许多传统的安全攻击。同时，由于算力交易信息中附加了实体的数字签名，攻击者无法模拟交易实体或伪造交易实体的信息。此外，CPTP-BSG模型还具备以下安全性。

1）不依赖唯一可信的第三方：ESP 与矿工之间的算力交易不需要第三方来保证交易系统的健壮性和可扩展性。

2）隐私保护：区块链的去中心化共识和公共账本为交易提供了可信环境。在智能合约的辅助下，ESP 与矿工之间的算力交易全程使用账户地址WA，不提供私人信息，有助于保护矿工和ESP的身份隐私。

3）账户安全：在没有相应私钥和安全证书的情况下，攻击者无法打开ESP或矿工账户。

4）交易认证：在PoW 机制的帮助下，所有交易数据都由获得记账权的节点进行公开审计和认证，降低了交易实体的认证成本和安全风险。

5）防止双花攻击：算力交易所使用的加密货币依靠数字签名来保证所有权，且存储于分布式账本中的历史交易数据是不可篡改的，可以有效防止双花攻击。

4.2 结果分析

4.2.1 参数设置

为了对比分析不同参数对价格策略和矿工算力需求的影响，本文设置初始实验参数如表1 所示。其中初始矿工数量N=100，矿工i挖掘的区块大小满足正态分布(μt，σ2)。

表1 实验参数Tab.1 Experimental parameters

4.2.2 性能分析

为了验证所提梯度迭代算法的收敛性能，本文利用算法1 分别在不同的算力资源价格最大值-p下求解多矿工非合作Stackelberg博弈的纳什均衡点，实验结果如图4所示。在实验迭代次数达到20 左右时，标准化平均最优价格和算力需求总量达到均衡点，证明了所提算法的有效性。结果还表明，随着算力服务需求总量的持续增长，平均最优价格会有所下降，但多个矿工之间的竞争会使得算力资源价格最终趋于稳定。

图4 所提算法收敛性能Fig.4 Convergence performance of the proposed algorithm

为了分析矿工数量对最优价格的影响，本文对比了统一定价和歧视性定价两种策略下最优价格的变化。从图5 可知，在统一定价策略下，平均最优价格基本与最高价格相同。这是因为价格与算力需求之间存在负相关关系，随着矿工数量的增加，矿工的算力需求总量也随之增加。因此，价格需要略有增加以满足新的纳什均衡点。然而，由于本文默认最大价格的限制，最优价格总是接近于最大价格。另外，从式（26）可知，函数Π(p)关于p的一阶导数总是大于0，意味着ESP 的利润会随着价格的增长而增长。因此，统一定价下的最大价格便成为ESP利润最大化的预期最优价格。

从图5 还可以看出，歧视性定价策略下平均最优价格略低于统一定价。为了刺激矿工购买更多的算力，在歧视性定价策略下，ESP 为不同算力需求量的矿工制定不同的资源价格。从图6 可知，随着矿工数量的不断增加，新加入的矿工会带来新的算力服务需求，因此需求总量也会不断增加。由于价格的优势，歧视性定价策略下矿工算力服务需求总量高于统一定价，在这种情况下，ESP 可以在歧视性定价策略下获得更高的利润。另外，随着矿工数量的不断增加，矿工之间的竞争使得每个矿工挖矿成功的概率不断降低。由于获得奖励的概率降低，促使矿工对算力的购入动机不断减弱，从而算力服务需求总量增长率降低，但算力需求总量仍增加。

图5 最优价格与矿工数量的关系Fig.5 Optimal price versus the number of miners

图6 算力服务需求总量与矿工数量的关系Fig.6 Total computing power service demand versus the number of miners

从图7 可以看出，在矿工数量较少时，由于统一定价策略下的平均价格高于歧视性定价，因此ESP 可在统一定价策略下获得更高的利润。然而随着矿工数量的持续增加，歧视性定价策略的价格优势促使其算力服务需求总量增速高于统一定价，因此，ESP 在歧视性定价策略下所获得的利润会超过统一定价策略。

图7 ESP利润与矿工数量的关系Fig.7 ESP profit versus the number of miners

为了进一步分析歧视性定价对单个矿工个性化算力需求的影响，本文针对矿工挖掘的不同区块大小，对比了统一定价和歧视性定价策略下可变奖励因子与矿工算力需求的关系。从图8 可知，在奖励因子较小时，由于矿工挖矿成功的奖励偏低，因此单个矿工没有动机为较低的奖励去支付更高的算力需求。在这种情况下，ESP 需要制定更低的价格来吸引矿工购入更多的算力。随着奖励因子的不断增大，挖矿成功的奖励提高，这促使矿工增加其算力需求量，从而提高挖矿成功的概率。因此，与统一定价相比，歧视性定价策略针对不同矿工的个性化算力需求进行智能调价，使得所有矿工的算力需求总量不断增加，从而帮助ESP获得更高的利润。

5 结语

针对移动边缘计算中智能设备实现计算卸载的问题，本文结合区块链技术提出了一种基于Stackelberg 博弈的算力交易模型CPTP-BSG，并将矿工与ESP之间的算力交易建模为一个两阶段的博弈过程。在统一定价和歧视性定价策略下对比分析了矿工的算力需求和ESP 利润最大化，并提出一种低梯度迭代算法计算纳什均衡。实验结果证明了所提算法的有效性，歧视性定价策略下资源价格更符合个体矿工的个性化算力需求，所有矿工的算力需求总量和ESP 利润均优于统一定价策略。在未来的工作中，将进一步引入多主多从Stackelberg 博弈，研究多个ESP 之间的竞争对算力交易与智能定价的影响。此外，在算力交易过程中还将考虑引入多跳计算卸载以应对真实、复杂的网络环境。