基于斯塔克伯格博弈的边缘协同计算研究

黎作鹏 王浩翔

摘  要： 小型基站（Small?cell base stations，SBSs）被认为是边缘计算环境中重要的组成部分。但由于自身计算资源有限，当计算工作负载过大时，为用户提供的服务质量将面临重大的挑战。因此，针对小型基站间协同计算展开研究。首先，以最优化小型基站的个人效用为目标，结合多主多从斯塔克伯格（stackelberg）博弈模型，提出一种可实现小型基站间协同计算的算法。然后，通过循环迭代的方式求解小型基站之间非合作博弈的纳什均衡解。最后，通过Matlab进行实验，验证了该算法的可行性和有效性。

关键词： 小型基站; 边缘计算; 协同计算; Stackelberg博弈; 纳什均衡; 仿真分析

中图分类号： TN929?34                             文献标识码： A                      文章编号： 1004?373X（2020）14?0079?04

Research on edge cooperative computing based on Stackelberg game

LI Zuopeng1，2， WANG Haoxiang1，2

（1. School of Information and Electrical Engineering， Hebei University of Engineering， Handan 056038， China;

2. Hebei Key Laboratory of Security Information Perception and Processing， Hebei University of Engineering， Handan 056038， China）

Abstract：The small?cell base stations （SBSs） are considered as an important part of the edge computing environment. Since SBSs′ own computing resources are limited， the service quality provided to users will be faced with major challenges when the computing workload is too large. Therefore， the collaborative computing between SBSs is studied. With the goal of optimizing the personal utility of SBSs， an algorithm to realize the collaborative computing between SBSs is proposed in combination with the Stackelberg game model with multi?master and multi?slave. The Nash equilibrium solution of non?cooperative game between SBSs is solved by means of the loop iteration. The feasibility and effectiveness of the algorithm are verified by the experiments with Matlab.

Keywords： small base station; edge computing; collaborative computing; Stackelberg game; nash equilibrium; simulation analysis

0  引  言

随着万物互联时代[1]的到来，数据呈现出爆炸性的增长，这使得传统的集中式云计算模型在应用服务实时性、用户隐私保护和数据传输能耗等方面都出现了问题。在此背景下，一种新的在网络边缘执行计算的模型，即边缘计算随之诞生。

小型基站（SBSs）被认为是边缘计算中关键的支撑设备，具有计算和存储能力，可以作为云的替代品，为终端用户提供任务卸载计算。但与云数据中心相比，SBS计算资源是有限的，依赖单个SBS会极大地限制边缘计算的性能[2]。幸运的是，下一代（5G）移动网络中SBSs的部署非常密集[3]，这为邻近的SBSs间实现协同计算提供了可能。

本文中的SBSs是由个人部署的，因此每个SBS无法获得全局信息。本文结合Stackelberg博弈模型，提出一种以最优化SBSs个人效用函数为目标的SBSs间协同计算算法。在该算法中考虑了SBSs间的通信和计算的过程[4]，将其产生的时延和能耗分别建模并归一化为运行开销[5]，同时为了SBS能够更好地参与到边缘计算协同当中，引入了激励机制。针对上述两种开销，过载的SBSs对任务进行本地计算或协同计算的选择[6]。最后通过循环迭代的方法求解非合作博弈的纳什均衡。

1  模型分析与算法实现

1.1  网络模型

本文对网络场景做了如下假設：在一定范围内密集部署了x个SBSs（[SBSi∈{SBS1，SBS2，…，SBSx}]），由于设备都只具有有限的计算能力，所以本文假设[SBSi]在时隙t最大的卸载任务接收量（下辖终端用户卸载的任务）为[wmaxi]，同时在时隙t终端用户向[SBSi]卸载的总任务量为[λi]。根据公式[αi?wmaxi-λi]对[SBSi]在时隙t的情况进行分类。如果[αi<0]，表示[SBSi]有空闲计算资源，可帮助其他有需求的SBSs进行协同计算，本文称其为资源供应点（后简称为供应点），将符合这种情况的SBSs设为集合[SBSS={SBSS1，SBSS2，…，SBSSm}]。如果[αi>0]，表示[SBSi]需要其他SBSs来协助完成计算，本文称其为资源请求点（简称为请求点），将符合的SBSs设为集合[SBSB={SBSB1，SBSB2，…SBSBn}]。每个SBS的状态是呈现时空变化性的，但本文基于当前时隙t内各个SBS的负载状态进行分析。由于SBSs间是纯分布式的，无集中式管理的，结合文献[7]中多主多从Stackelberg博弈模型，本文假设“资源供应点”为领导者，“资源请求点”为跟随者。其中[SBSSj]的出价为[pj]，所有供应点的策略向量定义为[p=（p1，p2，…，pm）]。一个请求点可通过向多个不同的供应点订购一定量的计算资源，来弥补自身的不足。假定[dij]表示[SBSBi]当前请求[SBSSj]协同处理的任务量，定义[di=（dij，d-ij）]为[SBSBi]向[SBSS]请求的协同计算总任务量，其中[d-ij]表示[SBSBi]向[SBSSj]以外的其他供应点请求协同计算的任务量。[d=（d1，d2，…，dn）]表示网络中所有[SBSB]的请求协同计算的策略。为了便于计算，假设每个任务的数据为单位大小，所需计算周期为一个CPU周期。同时定义[αSj]为[SBSSj]的剩余可接收任务量，对于[SBSSj]帮助[SBSBi]协同完成的任务量[dij]，则需要满足[0≤dij≤αSj]，同时对于[SBSSj]上所有请求协同计算的任务量，也需要满足[i=1ndij≤αSj]。为了能够更好地反映博弈中一个参与者对选择策略的满意程度，本文在上述研究背景下，建立了[SBSBi]和[SBSSj]的效用函数并进行了分析。

1.2  资源请求点效用函数

对于请求点而言，它们之间构成了非合作博弈关系。同时由于隐私的原因，请求点之间相互独立且不会互相告知彼此的信息。在此背景下，本文针对请求点中过载任务量的效用函数进行了分析。该效用函数主要由三部分组成：协同计算开销、本地计算开销和激励机制开销。下面对这三部分进行建模分析。

1.2.1  协同计算

协同计算过程的开销主要分为两部分，一部分是将数据[dij]从[SBSBi]传输至[SBSSj]的传输时延和传输能耗，其公式分别为：

[tB，trij=1rij]           （1）

[eB，trij=pij1rij]          （2）

式中：[rij]为[SBSBi]与[SBSSj]之间的传输速率;[pij]为[SBSBi]向[SBSSj]传输时的功率。

另一部分是在[SBSSj]上的计算时延，本文根据M/M/1排队系统对计算时延进行建模，每个任务的平均计算延迟（包括任务等待时间和处理时间）公式如下：

[tS，lij=1fSj-ωSj]          （3）

式中，[ωSj]为[SBSSj]上的总任务量，[ωSj=λSj+i=1ndij]，[i=1ndij]为[SBSSj]终端卸载任务量与协同任务量之和。

因此，[SBSBi]请求协同计算时的开销为：

[CB，tri=i=1n[dijeB，trij+υ（tB，trijdij+tS，lijωSj）]] （4）

式中，[υ]为延迟成本和能量成本的归一化系数。

1.2.2  激励机制

SBSs通常由个人用户（例如家庭/企业所有者）拥有和部署，因此如果没有适当的激励机制，SBSs将不愿意参与边缘的协同计算过程。结合网络模型中供应点的出价，可得当[SBSBi]向[SBSSj]请求协同计算的任务量为[dij]时，需要向[SBSSj]支付的价格为[sij=qijpj]。

因此，[SBSBi]向[SBSS]支付的总费用为：

[SBi=j=1mdijpj]        （5）

1.2.3  本地计算

在时隙t时，可能会出现协同计算成本高于本地计算成本的情况，所以可能部分过载任务会选择在本地进行计算。针对[SBSBi]本地计算任务时的开销进行建模。首先利用M/M/1排队系统对计算时延进行建模，每个任务的平均计算延迟（包括任务等待时间和处理时间）为：

[tB，li=1fBi-ωBi]          （6）

式中，[ωBi]表示在[SBSBi]处理的工作负载大小，[ωBi=λBi-j=1mdij]。同时根据文献[8]可知[SBSBi]处理每个任务的计算能耗与CPU速度的平方成正比，可以表示为：

[eB，li=κ（fBi）2]          （7）

式中，[κ]表示常量，取决于CPU架构。

因此，在[SBSBi]上完成任务的计算开销为：

[CB，li=βBi（eB，li+υtB，li）]     （8）

式中，[βBi]是过载任务量，[βBi=αBi-j=1mdij]。

1.2.4  效用函数

根据上述三个模型，本节给出了请求点的效用函数，假定存在请求点[SBSBi]，其效用函数定义为[FBi（p，di，d-i）]，可以表示为：

[FBi（p，di，d-i）=-（CB，tri+CB，li+SBi）] （9）

每个请求点根据当前的价格策略[p]，调整自身策略，最终实现效用函数[FBi]的最优化，即[max{FBi（p*，di，d*-i）}]，其中[p*]和[d*-i]表示博弈中的其他參与者都各自选择了最优的价格策略和协同计算策略。

1.3  资源供应点效用函数

本文中的供应点效用函数只考虑了出售计算资源得到的收益，所以供应点效用函数可以利用收益函数[Gj（pj，q）]来表示。定义[SBSSj]的收益函数为[Gj（pj，d）=Qjpj]，其中[Qj=i=1ndij]表示请求点向[SBSSj]请求的协同计算任务总量。因为请求点的选择会根据供应点价格不同而产生变化，所以提供点的价格并不是越高越好，而是选择使自身收益最大化的价格策略。假设[SBSSj]的最优价格策略是[p*j]，则其最大收益为[max{Gj（pj，p*-j，d）}]，其中[p*-j]和[d*]表示博弈中其他参与者都选择了使自身效用最优的价格策略和协同计算策略。

1.4  资源请求点非合作博弈的纳什均衡点

纳什均衡是非合作博弈问题的关键，同时也是非合作博弈的解。当达到纳什均衡后，非合作博弈中的每个参与者的效用函数都达到最大值，且参与者单方面改变自身的策略不会增加自身的收益。本节对纳什均衡解的存在性进行了证明。

定理1 职对于供应点价格策略[p=（p1，p2，???，pm）]给定的情况下，请求点之间存在非合作博弈，并存在纳什均衡点[d*-i]，使所有请求点的效用函数最优化，即[max{FBi（p*，di，d*-i）}]。

证明  显然，任意请求点[SBSBi]的任务协同计算策略[di]是欧几里得空间中的有界闭集。此外，用户的效用函数[FBi]在其策略空间上是连续的。对任意请求点[SBSBi]的效用函数求一阶偏导得：

[fi（dij）=?FBi（p，di，d-i）?dij      =-（eB，trij-eB，trij+υtB，trij+pj）+υfSj（fSJ-ωSj）2-      1（fBi-ωBi）2-βBi1（fBi-ωBi）2] （10）

对[SBSBi]的效用函数求二阶偏导得：[?F2i（p，di，d-i）?d2ij=-2υfSj（fSj-ωSj）3+                           1（fBi-ωBi）2+βBi（fBi-ωBi）3<0] （11）

式中，[βBi>0，fSj>0，υ>0]，可见请求点的效用函数是凹函数，确保了纳什均衡的存在性[9]。

1.5  Stackelberg博弈问题的求解

由于SBS无法获取全局信息，因此，本文采用了一种循环迭代的方法来求解Stackelberg博弈的纳什均衡。假设在t 时供应点的价格策略为p（t），请求点根据当前价格调节协同计算策略，达到纳什均衡。其中，协同计算任务量的变化率与请求点效用函数的梯度成正比。

[ddijdτ=dij～=?Fi（p，di，d-i）?dij]      （12）

式中，[τ]是时间变量。效用函数凹函数的特性保证了迭代算法能够收敛到博弈的纳什均衡点[7]，因此，[SBSBi]协同计算任务量迭代方程可表示为：

[dij（τ+1）=dij（τ）+ξidij～]    （13）

式中，[ξi>0]表示请求点卸载任务调节步长。

在请求点之间达到纳什均衡后，供应点根据各请求点的任务协同计算策略来调整自己的出价。供应点的价格变化率可通过其边际效用来表示，因此对任意资源供应点[SBSsj]的价格迭代方程为：

[pj（t+1）=pj（t）+ψj?Gj（p（t），d（t））?pj（t）] （14）

式中，[ψj>0]表示供应点价格策略调节步长。

资源供应点的边际效用可以通过一个小的变化量[ε]（例如[ε=10-4]）来计算其对效用产生的影响[8]。因此，边际收益可以粗略的计算为：

[?Gj（p（t），d（t））?pj（t）≈[Gj（…，pj（t）+ε，…）-                            Gj（…，pj（t）-ε，…）]（2ε）-1] （15）

在请求点达到纳什均衡过程中，供应点保持价格不变，观察并等候请求点的任务协同计算策略达到稳定。这一等候时间即是供应点一次迭代的间隔时间[Δt]，[Δt]也是所有请求点迭代并达到纳什均衡的时间间隔。所以供应点根据式（14）和式（15）在多个[Δt]内进行价格迭代。每个[Δt]中多个请求点根据式（12）和式（13）在时间间隔[Δτ]中进行迭代。对整个网络而言，迭代的最终结果是请求点和供应点得到了各自最优的协同计算策略[d*]和价格策略[p*]，算法的时间序列如图1所示。在上述的迭代过程分析的基础上，给出实现协同计算的算法流程图，如图2所示。

2  实验仿真与分析

本文选择了Matlab 2014a仿真平台进行实验，辅助以Origin 9.0和Office 2010绘图。

2.1  参数设定

本节对仿真系统的参数进行了设置[9?10]，具体情况如表1所示。假设整个无线网络环境为100 m×100 m×100 m，仿真环境中部署了10个同构的小型基站，每个小型基站接收到的终端用户卸载任务到达速率（单位：个/s）为[λi∈（0，300）]。

2.2  结果分析

本次实验从资源供应点和资源请求点两个集合中分别选取一个小型基站进行分析，并将其迭代运行情况进行绘图，如图3、图4所示。首先由图3可知，在迭代的过程中，资源请求点的效用函数整体呈现增长的趋势，在趋向收敛的过程中略微有所减小，但达到纳什均衡点后，收益最终趋于稳定。随着本地计算开销的减少，协同计算开销和激励机制的开销都在增长，但在达到纳什均衡之后趋于平稳。这是由于在达到纳什均衡后，更改任何策略都无法使效用函数的值更优，因此不再改变任务协同计算策略。图4中，从曲线上可以看出资源供应点的效用函数是基于价格的凹函数。在价格从0.1逐渐增大的过程中，资源供应点的效用函数随之先增大后减小，在0.37左右达到最大值。这是由于在竞争的过程中，提高价格可以提升自身的效用函数，但是如果价格过高，就会失去竞争力，资源请求点就会选择其他的资源提供点来进行协同计算。

3  结  语

本文针对边缘环境中的小型基站间的协同计算进行研究，在同时考虑了请求点和供应点的效用函数最优的情况下，通过Stackelberg博弈分析了两者的交互关系，提出了一种边缘协同计算的方法。并通过仿真实验证明循环迭代的方法可使其达到纳什均衡，可以使每个小型基站的效用函数最大化，同时也提供了网络的资源利用率。本文下一步的工作是对复杂任务的情况进行分析，另外在计算资源供应点效用时还需对其运行开销进行考虑。

参考文献

[1] 施巍松，孙辉，曹杰，等.边缘计算：万物互联时代新型计算模型[J].计算机研究与发展，2017，54（5）：907?924.

[2] 周悦芝，张迪.近端云计算：后云计算时代的机遇与挑战[J].计算机学报，2018，41（25）：1?24.

[3] ANDREWS J G， BUZZI S， CHOI W， et al. What will 5g be？ [J]. IEEE journal on selected areas in communications， 2014， 32（6）： 1065?1082.

[4] ZHANG H Q， XIAO Y， BU S R， et al. Computing resource allocation in three?tier IoT fog networks： a joint optimization approach combining Stackelberg game and matching [J]. IEEE Internet of Things journal， 2017， 4（5）： 1204?1215.

[5] 孟陈融.面向边缘计算的数据中心服务资源调度机制研究[D].北京：北京邮电大学，2018.

[6] 李波，黄鑫，牛力，等.车载边缘计算环境中的任务卸载决策和优化[J].微电子学与计算机，2019，36（2）：78?82.

[7] 田厚平，郭亚军，王学军.一类基于进化博弈的多主多从Stackelberg对策算法[J].系统工程学报，2005（3）：303?307.

[8] CHEN L X， XU J. Socially trusted collaborative edge computing in ultra dense networks [C]// Proceedings of the Second ACM/IEEE Symposium on Edge Computing. San Jose： ACM， 2017： 9.

[9] 姜永，陈山枝，胡博.异构无线网络中基于Stackelberg博弈的分布式定价和资源分配算法[J].通信学报，2013，34（1）：61?68.

[10] CHEN L X， ZHOU S， XU J X. Computation peer offloading for energy?constrained mobile edge computing in small?cell networks [J]. IEEE/ACM transactions on networking， 2018， 26（4）： 1619?1632.