文档介绍：基于斯塔克伯格博弈的边缘协同计算研究
摘 要: 小型基站(Small?cell base stations,SBSs)被认为是边缘计算环境中重要的组成部分。但由于自身计算资源有限,当计算工作负载过大时,为用户提供的服务质量将个人部署的,因此每个SBS无法获得全局信息。本文结合Stackelberg博弈模型,提出一种以最优化SBSs个人效用函数为目标的SBSs间协同计算算法。在该算法中考虑了SBSs间的通信和计算的过程[4],将其产生的时延和能耗分别建模并归一化为运行开销[5],同时为了SBS能够更好地参与到边缘计算协同当中,引入了激励机制。针对上述两种开销,过载的SBSs对任务进行本地计算或协同计算的选择[6]。最后通过循环迭代的方法求解非合作博弈的纳什均衡。
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]的效用函数并进行了分析。 资源请求点效用函数
对于请求点而言,它们之间构成了非合作博弈关系。同时由于隐私的原因,请求点之间相互独立且不会互相告知彼此的信息。在此背景下,本文针对请求点中过载任务量的效用函数进行了分析。该效用函数主要由三部分组成:协同计算开销、本地计算开销和激励机制开销。下面对这三部分进行建模分析。
协同计算
协同计算过程的开销主要分为两部分,一部分是将数据[dij]从[SBSBi]传输至[SBSSj]的傳输时延和传输能耗,其公式分别为:
式中:[rij]为[SBSBi]与[SBSSj]之间的传输速率;[pij]为[SBSBi]向[SBSSj]传输时的功率。
另一部分是在[SBSSj]上的计算时延,本文根据M/M/1排队系统对计算时延进行建模,每个任务的平均计算延迟(包括任务等待时间和处理时间)公式如下:
式中,[ωSj]为[SBSSj]上的总任务量,[ωSj=λSj+i=1ndij],[i=1ndij]为[SBSSj]终端卸载任务量与协同任务量之和。
因此,[SBSBi]请求协同计算时的开销为:
式中,[υ]为延迟成本和能量成本的归一化系数。
激励机制
SBSs通常由个人用户(例如家庭/企业所有者)拥有和部署,因此如果没有适当的激励机制,SBSs将不愿意参与边缘的协同计算过程。结合网络模型中供应点的出价,可得当[SBSBi]向[