在5G、物联网与产业互联网发展的推动下, 物联网设备的类别越来越细化^{[1, 2]}. 目前, 物联网技术已经发展出许多计算密集型的应用类别, 例如虚拟现实、在线交互游戏、无人驾驶等^[3]. 然而, 大部分应用设备受限于自身的计算资源和能量等问题, 在设备上执行这类任务会产生大量的能耗. 为解决这个问题, 用户会购买云计算(cloud computing, CC)服务或移动边缘计算(mobile edge computing, MEC)服务, 并将任务卸载到云服务器或边缘服务器上计算^[4-7].

作为传统的用户任务卸载方式, CC拥有许多集中式服务器并可以提供大量的计算资源^{[8, 9]}. 然而, 通过广域网将任务卸载到云端所需要的时延将会抵消掉在云端计算节省的时间. 与传统CC范式不同, MEC范式可以将CC服务从集中式的远程服务器扩展到距离用户更近的分布式服务器^{[10, 11]}. 用户通过将任务整体^[12]或部分^{[13, 14]}卸载至MEC服务器并请求提供计算资源, 可以降低传输时延. 同时, 相比于CC, MEC服务提供商收取的计算资源费用对用户更友好, 用户可以请求更多的计算资源来满足自己的QoS.

在实际生活场景中, 用户希望减小自己购买计算资源时付出的成本, 同时服务提供商希望最大化自己的利益, 因此博弈论成为解决MEC系统中效益问题的重要方法^[15-17]. 通过将用户与服务器提供商之间的交互进行建模, 可以分析并计算出双方的最优策略. 随着边缘服务提供商的增加以及边缘基站的部署, 在市场竞争中, 用户更需要根据不同的定价以及算力来制定自己的卸载策略, 以最优化自身效益.

现有的大部分研究都只是简单考虑了“云-边-端”三层架构, 认为MEC服务器是一个计算资源有限但距离用户更近的CC服务器; 并且部分研究为了最大化单方效益, 会舍弃掉另一方的部分利益, 陷入局部最优. 在本文中, 考虑了边缘服务器随机分布情况. 用户为了减少卸载和计算成本, 可以选择不同的边缘服务器. 其次, 与部分研究相似, 为了验证最优效益存在, 证明了移动设备与边缘服务器之间存在纳什均衡. 最后设计了一种基于贪心思想的改进双重拍卖算法来获得最优解. 与已有算法相比, 该算法会记录系统中的所有拍卖可能, 并选择最优组合进行拍卖, 实现边缘服务器分布式场景中用户效益的最优卸载; 同时, 算法中加入了资源整合机制, 可以最大化边缘服务器资源利用率, 实现资源受限情况下的最优效益. 本文的主要贡献如下.

1) 构建了一个用户与MEC服务器随机分布的场景, 用户可以将任务卸载至任意一个边缘服务器上进行计算, 并将MEC服务器与移动设备之间的交互建模为Stackelberg博弈.

2) 证明了MEC服务器与用户、用户之间存在唯一的纳什均衡点, 并提出了一种基于贪心思想的改进双重拍卖算法来求得系统最优整体效益.

3) 仿真实验的结果验证了所提算法的有效性. 在MEC服务器随机分布的场景下, 本文所提算法可以显著提高系统中用户效益和边缘服务器效益.

1 相关工作

现有关于MEC的研究主要关注移动设备任务卸载和边缘服务器计算资源分配. 文献[18]将非正交多址(NOMA)技术引入MEC系统中, 并为了进一步提高频谱的利用效率, 提出了一种用于子信道分配的低复杂度次优匹配算法, 该算法可以最大程度地提高卸载效率. 文献[19]考虑时延敏感型任务的卸载问题, 将该问题建模为传输功率、子载波和计算资源分配联合优化, 并将原始问题拆解为3个子问题, 通过一个迭代算法顺序处理. 通过等价参数凸规划获得最优解. 文献[20]研究MEC中协同计算任务卸载和资源分配联合问题, 通过对计算卸载决策、协同选择、功率分配进行分别建模从而最小化系统时延. 作者提出了一种基于拉格朗日对偶分解、生津公式法和单调优化法的联合迭代算法来解决提出的问题. 文献[21]考虑超密集网络下的任务卸载问题, 使用博弈论寻找到各用户的最优卸载服务器后, 再通过启发式萤火虫算法来优化用户任务卸载比例带来的时延和能耗问题, 在多次迭代中不断逼近最优值. 文献[22]注重优先级任务的卸载问题, 根据用户任务的平均处理价值分配优先级, 并根据优先级分配其相应的计算资源, 从而减少系统总时延和能耗.

上述工作主要优化时延和能耗的加权问题, 没有考虑经济效益情况. 在考虑MEC社会效益的研究中, 大部分工作主要使用拍卖算法或其他激励机制来实现效益最优. 文献[23]提出了一种新的分层结构, 通过将请求计算卸载的移动设备与边缘服务器之间建立一种投标与要价的双边交互, 并将计算资源和通信资源以利润最大化的方式进行拍卖, 从而满足用户QoS标准. 文献[24]从博弈论出发, 构建了CC服务器与MEC服务器之间一种全新的协作关系, 从顶层向下层进行任务卸载, 并对卸载的任务进行出价奖励. 通过验证两者之间的纳什均衡关系来证明最优任务卸载量和出价存在, 并进行多次迭代找到该最优解. 这套关系同样可以适用于边缘服务器与移动设备之间. 文献[25]研究了工业物联网中如何提升社会效益, 对MEC服务器与移动设备之间的双向交互进行建模, 构建了一个通用的双重拍卖框架来解决交互问题并最大化社会效益. 在满足各项经济属性的前提下, 通过真实的双重拍卖算法将MEC服务器的计算资源出售, 从而最优化效益. 文献[26]将MEC服务器与用户之间的竞争性交易以3层拍卖模型表示, 并把整个拍卖过程拆分为3个独立且有顺序的子问题. 作者提出了一种真实的组合拍卖算法来联合优化服务成本和无线信道资源. 文献[27]在不考虑信道资源的情况下, 基于市场定价利润最优化问题设置了一个激励机制, 同时针对用户随机性, 设计了一种在线多轮拍卖算法. 文献[28]提出了一种基于双重拍卖的多对多计算资源分配算法, 以最大限度提高效益. 作者从网络经济学的角度研究MEC中的跨服务器资源分配方案, 并将MEC服务器与用户之间的双边交互建模为双重动作, 从而解决多种用户任务跨服务器交互问题.

现有使用拍卖理论来优化MEC社会效益的研究没有考虑边缘服务器随机分布场景下, 用户对服务器的选择产生的效益影响. 例如文献[18-23]侧重于能耗最优化, 并没有考虑服务收费问题; 文献[24-28]虽然考虑了计算服务成本, 但并没有考虑不同边缘服务器之间的位置差异对用户的卸载影响, 且没有考虑边缘服务器计算资源受限情况. 用户选择不同位置的边缘服务器会产生不同的传输时延和能耗, 进而影响用户请求计算资源量, 最终影响用户效益. 在这篇文章中, 考虑MEC服务器随机分布且计算资源受限情况下对于用户卸载选择的影响, 使用Stackelberg博弈对MEC服务器与移动设备之间进行建模, 并且在该场景下提出了基于贪心思想的改进双重拍卖算法来最优化MEC服务器资源受限情况下的移动设备效益. 与传统双重拍卖的价高者得和其他文章为简化时间而忽略部分交易的双重拍卖不同, 本文提出的双重拍卖算法可以在首轮拍卖中满足价高者得的用户局部效益最优, 进而在第2轮拍卖中实现系统整体效益最优.

2 系统架构和问题建模 2.1 系统架构

如图1所示, MEC系统网络架构由M个用户、N个边缘服务器组成, 用户与边缘服务器之间通过无线信道连接. 假设每个用户拥有一个不可分割的待卸载任务, 即共有M个任务, 用U={U₁, U₂, …, U_M}表示. 用户的属性可以表示为U_i ={C_i, $ T_i^D $ , $ P_i^T $ )}, 其中C_i表示用户的卸载任务量, $ T_i^D $ 表示用户任务的截止时间, $ P_i^T $ 表示用户设备的传输功率. 边缘服务器分布在用户周围, 用S={S₁, S₂, …, S_n}表示. 边缘服务器属性可以表示为S_j ={D_j, P_j, p_j}, 其中D_j边缘服务器j的计算资源总量, P_j表示边缘服务器j的计算功率, p_j表示边缘服务器的资源定价. 假定边缘服务器可以给每一个用户提供卸载和计算服务, 即边缘服务器的服务范围可以覆盖所有用户, 并且一个边缘服务器可以同时处理多个用户任务. 用户的边缘服务器卸载选择策略可以表示为矩阵 $ {\eta ^{M \times N}} $ , 且用户i的卸载策略可以表示为η_i ={η_i,1, η_i,2, …, η_i,j, …, η_i,N} , η_i,j =1表示用户i选择边缘服务器j卸载任务.

双重拍卖模型如图2所示, 由买方(用户)、卖方(边缘服务器)以及第三方拍卖者组成. 其中交易双方分别向拍卖方提供需求资源量、出价以及出售资源量、要价. 在拍卖进行时, 拍卖方会将每次交易倾向条目储存在交易记录表中, 并在拍卖结束后统一达成交易.

2.2 传输模型

多服务器多用户随机分布的边缘计算模型常应用于大型商场或商业区场景中, 因此采用自由空间路径损耗模型来描述用户任务卸载至边缘服务器过程. 对于不同用户传输, 采用正交频分多址方式, 并假设每个用户拥有的信道带宽为B_i . 由香农公式知, 忽略用户之间的信道干扰, 用户i将任务卸载到边缘服务器j的上行链路传输速率为:

$ {v_{i, j}} = {B_i}{\log _2}\left(1 + \frac{{P_i^T{H_{i, j}}}}{{{\sigma ^2}}}\right) $

(1)

其中, H_i,j表示用户i与边缘服务器j之间的信道增益, 与文献[29]相似, H_i,j= $ d_{i, j}^{ - 3} $ , d_i,j表示用户i与边缘服务器j之间的距离; 由于采用自由空间路径损耗模型, 因此信道增益与距离成反比. $ {\sigma ^2} $ 表示高斯白噪声的方差.

在得知用户与边缘服务器的传输速率后, 可以求得用户将任务卸载至边缘服务器的时延. 不考虑传输过程中的速度损耗, 用户i卸载任务至边缘服务器j的传输时延可以表示为:

$ T_{i, j}^C = \frac{{{C_i}}}{{{v_{i, j}}}} $

(2)

与文献[30]的计算方法相似, 系统中用户i将任务卸载至边缘服务器j的传输能耗可以表示为:

$ E_{i, j}^C = P_i^T \times \frac{{{C_i}}}{{{v_{i, j}}}} $

(3)

2.3 Stackelberg博弈模型

在本节中, 对用户的计算资源请求量与边缘服务器的资源定价之间进行博弈建模. 由于Stackelberg博弈是两阶段完全信息动态博弈, MEC服务提供商作为领导者首先在第1阶段制定自己的定价策略, 用户作为追随者在得知定价策略后确定自己的资源请求策略. 为了建立博弈模型, 首先对用户卸载策略进行描述, 之后定义MEC服务提供商与用户的效用函数, 它们的目标都是最大化自己的效用函数值.

在多用户多服务器的边缘计算场景中, 各服务器的定价会对用户的卸载倾向以及系统整体性能产生较大的影响. 由于每个用户都在所有边缘服务器的覆盖范围内, 因此用户可以选择不同的边缘服务器来卸载它们的任务, 以达到自身成本最小化的目的. 同时, 希望更多的用户将任务卸载到边缘服务器上, 这样传输时延以及成本会更低. 用户对各边缘服务器的喜好程度可以表示为:

$ {o_{i, j}} = {\beta _1}\frac{{{S_j}}}{{{R_{i, j}}}} + {\beta _2}\frac{1}{{{d_{i, j}}}} + {\beta _3}{\textit{Cost}}{{}_{i, j}} $

(4)

其中, $\; {\beta _1} + {\beta _2} + {\beta _3} = 1 $ , 为权重参数; S_j表示边缘服务器j拥有的总计算资源量. $ {o_{i, j}} $ 的值越大, 说明用户i在拍卖时优先与边缘服务器j达成交易. 用户i对于j个边缘服务器的优先级可以表示为: O_U =(o_i,1, o_i,2, …, o_i,N), 并将o_i,1对应的边缘服务器j的η_i,j置为1.

基于式(4), 每个用户可以选择一个合适的边缘服务器卸载任务并购买计算资源. 进一步需要研究用户与边缘服务器之间的博弈交互. 用户与边缘服务器之间不断改变自己的策略以适应对方的策略, 并最终达到两者最优效用. 用户与边缘服务器的效用函数建模如下.

2.3.1 用户效益

用户成本由两部分组成: 1)用户购买计算资源的出价; 2)用户任务的卸载能耗. 为了最优化系统中用户效益, 在拍卖时需要优先考虑每个用户对应成本最小的边缘服务器. 对于卸载至边缘服务器上计算的用户, 他们需要支付任务通过无线信道传输所产生的能耗以及购买计算资源的出价. 用户i在将任务卸载至边缘服务器j上计算的成本可以表示为:

$ {\textit{Cost}}{_{i, j}} = {\alpha _i}{R_{i, j}}{p_j} + (1 - {\alpha _i})P_i^T \times \frac{{{C_i}}}{{{v_{i, j}}}} $

(5)

其中, R_i,j表示用户i向边缘服务器j请求的计算资源量. $ {\alpha _i} $ 表示用户i两部分成本之间的权重系数.

如果用户购买了大量的计算资源, 那么这些任务的执行时间会减少, 因此用户可以从完成这些任务中获得的报酬就会增加. 然而, 当用户拥有足够的计算资源以后, 计算能力的提升以及从任务中获得的报酬的增加都会减缓. 因此, 用户卸载至边缘服务器上完成任务获得的收益可以用自然对数函数建模^[27], 表示随着 $ {R_{i, j}} $ 的增加, 用户收益的增加不断变缓. 用户i的效益可以表示为:

$ U_i^P = {\lambda _i}\ln (1 + \mu _j^{ - 1}{R_{i, j}}) - {\textit{Cost}}{{{}}_{i, j}} $

(6)

其中, $ {\lambda _i} $ 表示用户i的收益系数, $\; {\mu _j} $ 表示边缘服务器j的计算能力.

2.3.2 边缘服务器效益

边缘服务提供商通过出售边缘服务器中的计算资源来获得效益, 并且该效益与单位计算资源的收费有关. 边缘服务器的效益可以用边缘服务器出售计算资源获得的收益减去计算用户任务的能耗求得. 由于边缘服务器需要提供计算服务, 因此边缘服务提供商需要付出额外的成本来维护边缘服务器的使用. 边缘服务器的计算能耗与用户卸载的任务大小以及用户请求的计算资源量有关. 边缘服务器j的计算能耗可以表示为:

$ E_j^C = \sum\limits_{i = 1}^M {{\eta _{i, j}}\frac{{{P_j}R{ _{i, j}}}}{{{f_j}}}} $

(7)

相应的, 边缘服务器j的效益可以表示为:

$ U_j^P = \sum\limits_{i = 1}^M {{\eta _{i, j}}{R_{i, j}}{p_j}} - E_j^C $

(8)

2.4 问题建模

本文的首要目标是通过优化用户任务卸载决策以及请求资源量来最大化系统中用户的总收益. 优化问题P1建模如下:

$\left\{ { \begin{array}{l}\text{P}1:\text{max }{U}_{{\rm{user}}}=\left\{{\displaystyle \sum _{i=1}^{M}{U}_{i}^{P}}\right\} \\ 约束条件: \\ \text{C1}:{\displaystyle \sum _{j=1}^{N}{\eta }_{i, j}}=1, \forall i\in M \\ \text{C2}:{T}_{i, j}^{C}+{T}_{i, j}^{E}\leqslant {T}_{i}^{D}, \forall i\in [1, M] \end{array} } \right.$

(9)

其中, 约束条件C1限制每个用户只能卸载至一个边缘服务器上; 约束条件C2说明用户在边缘服务器上的计算时延与传输时延之和要小于用户任务的截止时间. 由于用户到不同边缘服务器的传输时延是不同的, 因此其计算时延也是不同的, 可得知用户在每个边缘服务器上的请求资源有最小值.

本文的次要目标是通过优化单位计算资源收费来最大化边缘服务提供商的效益. 优化问题P2建模为:

$ \left\{ {\begin{array}{*{20}{l}} {{\rm{P2}}:{\rm{max }}\;{U_{{\rm{ES}}}}{\rm{ = }}\left\{ {\displaystyle\sum\limits_{j = 1}^N {U_j^P} } \right\}}\\ {约束条件:}\\ {{\rm{C}}3:0 \leqslant {R_{i,j}} \leqslant {D_j},\forall i \in [1,M],j \in [1,N]}\\ {{\rm{C4}}:\displaystyle\sum\limits_{j = 1}^N {\displaystyle\sum\limits_{i = 1}^M {{\eta _{i,j}}{R_{i,j}}\leqslant {D_j}} } }\\ {{\rm{C5}}:{p_j} > 0,j \in [1,N]} \end{array}} \right. $

(10)

其中, 约束条件C3限制每个用户对任意一个边缘服务器请求的计算资源, 表示请求的计算资源量要小于等于边缘服务器所拥有的计算资源量; 约束条件C4表示每个边缘服务器上各卸载任务请求的资源量之和要小于等于该边缘服务器所拥有的计算资源量; 约束条件C5表示必须要收费大于0, 如果边缘服务提供商收益小于它维护服务付出的成本, 那么它将不会继续提供服务.

不难看出, 用户效益最大化与边缘服务器效益最大化之间纯在冲突, 因为若希望用户效益提高, 则需要减少用户向边缘服务器支付的计算资源成本, 然而这样会减少边缘服务器的效益. 因此, 需要找到一个用户最优卸载策略和最优计算资源请求策略, 在对边缘服务器效益产生较小影响的情况下, 最大化系统中用户整体效益.

3 问题分析与拍卖算法描述 3.1 Stackelberg博弈问题分析

该博弈问题中, 边缘服务器作为领导者, 且每个边缘服务器拥有一个最优定价策略, 可以表示为P^*=( $ {p}_{1}^{*}, {p}_{2}^{*}, \cdots , {p}_{N}^{*} $ ); 移动用户作为跟随者, 且每一个用户对每一个边缘服务器拥有一个最优计算资源请求策略, 可以表示为R^*=( $ {R}_{1}^{*}, {R}_{2}^{*}, \cdots , {R}_{M}^{*} $ ), 其中 $ R_i^* $ =( $ {R}_{i, 1}^{*}, {R}_{i, 2}^{*}, \cdots , {R}_{i, N}^{*} $ ). 当达到纳什均衡时, 存在不等式:

$\left\{ { \begin{split} & {U_i^P(R_{i, j}^*, R_{ - i, j}^*, p_j^*) \geqslant U_i^P({R_{i, j}}, R_{ - i, j}^*, p_j^*)} \\ & {U_j^P(R_{i, j}^*, p_j^*) \geqslant U_j^P(R_{i, j}^*, {p_j})} \end{split} } \right.$

(11)

其中, $ R_{ - i, j}^* $ 表示除了用户i的其他用户最优卸载策略. 在纳什均衡中, 每一个用户都不能通过单独改变自己的计算资源请求策略以更大化效益.

定理1. 在用户选择边缘服务器博弈中存在纳什均衡.

证明: 如式(6)所示, 用户的效益函数它是一个关于请求资源R_i,j的连续函数. 它对于请求资源R_i,j的一阶偏导数为:

$ \frac{{\partial U_i^p}}{{\partial {R_{i, j}}}} = \frac{{{\lambda _i}}}{{{\mu _j} + {R_{i, j}}}} - {\alpha _i}{p_j} $

(12)

相应的, 该函数对于请求资源R_i,j的二阶偏导数为:

$ \frac{{{\partial ^2}U_i^P}}{{\partial {{({R_{i, j}})}^2}}} = - \frac{{{\lambda _i}(1 + {\mu _j})}}{{{{({\mu _j} + {R_{i, j}})}^2}}} $

(13)

因为 $\; {\mu _j} $ >0,R_i,j>0, $ {\lambda _i} $ >0, 所以式(15)是负的. 因此, 式(6)中定义的用户效益函数是关于请求计算资源R_i,j的凸函数, 说明当边缘服务器收费确定时, 用户效益与请求计算资源量正相关, 但增长速度逐渐变慢. 根据纳什均衡存在定理, 不难发现在此博弈关系中存在纳什均衡, 该定理证得.

定理2. 对于给定边缘服务器收费p_j, 用户i对于边缘服务器j的最优计算资源请求量可以表示为:

$ R_{i, j}^* = \max \left(\frac{{{\lambda _i}}}{{{\alpha _i}{p_j}}} - {\mu _j}, \frac{{{C_i}}}{{T_i^D - T_i^C}}\right) $

(14)

证明: 由定理1知, 用户效益是关于请求资源的凸函数. 根据凸函数的性质, 函数的极值点就是函数的最大值点. 令式(12)=0, 可以求得用户效益取得最大值时的计算资源为:

$ R'_{i, j} = \frac{{{\lambda _i}}}{{{\alpha _i}{p_j}}} - {\mu _j} $

(15)

其中, $R'_{i, j}$ 可能会小于0, 然而用户对于每个边缘服务器的计算资源请求量应该满足 $ R_{i, j}^* $ >0. 当 $R'_{i, j}$ >0时, $ R_{i, j}^* $ = $R'_{i, j}$ ; 当 $R'_{i, j}$ <0时, 说明在当前价格下请求该数量计算资源会使效益减小, 此时应该在满足用户任务截止时间的前提下, 最小化用户请求的计算资源. 计算资源量由用户任务量和用户期望时间与传输时间差的比值求得. 因此, 该定理证得.

定理3. 每一个用户有且仅有一个最优的计算资源请求策略.

证明: 如果边缘服务器的收费为0, 那么用户在请求计算资源时便不会考虑不同边缘服务器的收费差异, 只考虑距离带来的传输能耗问题; 如果边缘服务器的收费非常高, 那么用户无论选择哪个边缘服务器所带来的效益都不高. 因此本文只考虑每个边缘服务器都是合理收费情况, 此时分别让最优请求计算资源量对收费求一阶偏导数和二阶偏导数有:

$ \frac{{\partial R_{i, j}^*}}{{\partial {p_j}}} = - \frac{{{\lambda _i}}}{{{\alpha _i}p_j^2}} $

(16)

$ \frac{{{\partial ^2}R_{i, j}^*}}{{\partial {{({p_j})}^2}}} = \frac{{2{\lambda _i}}}{{{\alpha _i}p_j^3}} $

(17)

由于p_j >0, $ {\lambda _i} $ >0, 因此请求计算资源量对收费的一阶偏导数是小于0的, 说明随着边缘服务器收费的提高, 用户对边缘服务器请求的计算资源量会逐渐减小, 这样才能使自己的效益最优; 同时, 请求计算资源量对收费的二阶偏导数是大于0的, 说明随着边缘服务器收费的增高, 用户对于收费变得越来越不敏感.

综上, 易知用户的计算资源请求量是关于收费p_j的一个递减的下凹函数. 因此, 对于一个给定范围的收费, 该函数是一个严格的凹函数. 所以用户计算资源请求策略是最优且唯一的, 该定理证得.

定理4. 用户与边缘服务器之间存在纳什均衡.

证明: 根据定理1和定理2可知, 当边缘服务器的收费p_j确定时, 用户总是可以达到纳什均衡. 下一步, 通过分析边缘服务器的效益来证明用户与边缘服务器之间的纳什均衡. 分别让边缘服务器的效益函数对收费求一阶偏导数和二阶偏导数有:

$ \frac{{\partial U_j^P}}{{\partial {p_j}}} = \sum\limits_{i = 1}^M {\eta _{i, j}}\left(\frac{{{P_j}{\lambda _i}}}{{{\alpha _i}{f_j}p_j^2}} - {\mu _j}\right) $

(18)

$ \frac{{{\partial ^2}U_j^P}}{{\partial {{({p_j})}^2}}} = \sum\limits_{i = 1}^M { - {\eta _{i, j}}\frac{{{P_j}{\lambda _i}}}{{{\alpha _i}{f_j}p_j^3}}} $

(19)

不难看出, 式(18)>0、式(19)<0. 这说明对于给定范围的收费p_j, 随着它的增大, 边缘服务器的效益会逐渐增加, 这是因为用户购买计算资源的单价上升, 所以边缘服务器的效益逐渐增加; 同时, 这种增加的趋势在逐渐变慢, 这是因为用户购买计算资源的单价上升, 所以用户购买计算资源量会减少, 边缘服务器效益增加速度会有缓和. 因此, 用户与边缘服务器之间存在纳什均衡, 定理证得.

3.2 双重拍卖算法描述

在第3.1节中, 证明了用户与边缘服务器之间存在纳什均衡, 且各服务器对于计算资源的收费会直接影响各用户对于该服务器请求的计算资源, 而用户请求计算资源量与自身以及边缘服务器的效益相关. 在博弈中, 各个用户通过计算出最优的计算资源请求量来最大化自己的效益, 同时需要尽可能将边缘服务器的计算资源与用户进行匹配, 从而最大化系统内用户整体效益.

传统双重拍卖算法中, 交易双方向第三方拍卖者提供自己出售(需求)的物品量和对应要价(出价)后, 遵循价高者得原则, 即将出价最高的用户优先拍卖. 在计算资源不受限的情况下, 这种拍卖策略可以实现效益最优化. 但在资源受限场景中, 传统双重拍卖算法容易陷入局部最优, 因为可能会出现部分交易占用大量资源, 从而导致较多用户无法完成拍卖的情况.

为了解决上述问题, 在本节中, 提出了一种基于贪心思想的改进双重拍卖算法(improved double auction algorithm based on greed, IDAG)来解决用户与边缘服务器之间的效益最大化问题. 在IDAG算法中, 首先从用户的角度出发, 将各用户与其对应成本最小的边缘服务器进行拍卖匹配, 使得各用户自身的效益最大化, 这样会占用边缘服务器的大部分计算资源, 拍卖失败的用户会加入失败队列; 其次从系统的角度出发, 通过改变交易策略, 从而省下额外的计算资源, 并将这些计算资源拍卖给失败用户, 从而实现整个系统的效益最大化. 该算法的具体步骤如算法1.

算法1. 基于贪心思想的改进双重拍卖算法

输入: 用户集合U, 边缘服务器集合E

输出: 成功拍卖用户W_U , 用户效益U_user, 边缘服务器效益U_ES

1) 通过式(4)和式(14)计算用户喜好矩阵和用户请求资源矩阵, 初始化各边缘服务器匹配用户队列 $\scriptstyle {E^U} $ =( $\scriptstyle E_1^U, \cdots , E_N^U $ )= $\scriptstyle \varnothing$ , 成功拍卖用户队列W_U = $\scriptstyle \varnothing$ , 失败用户队列W_L = $\scriptstyle \varnothing$ ;

For each user in U//遍历用户集合中的所有用户

2) 从用户喜好矩阵中选择用户i最喜爱的边缘服务器j. 若R_i,j ≤S_j, 则将用户i拍卖给该边缘服务器, 并将该用户加入 $\scriptstyle E_j^U $ 中, 并且D_j $\scriptstyle \leftarrow $ D_j–R_i,j , W_U $\scriptstyle \leftarrow $ W_U $\scriptstyle \cup $ u_i否则从用户喜好矩阵中选择下一个边缘服务器继续判断. 若遍历完所有边缘服务器后, 用户i仍没有拍卖成功, 则将该用户加入失败队列W_L $\scriptstyle \leftarrow $ W_L $\scriptstyle \cup $ u_i ;

End for

3) 对各边缘服务器按计算资源收费升序排列, 此时边缘服务器匹配用户队列可表示为 $\scriptstyle {E^U} $ =( $\scriptstyle E_1^U, \cdots , E_j^U, \cdots , E_N^U $ ), 其中p₁≤…≤p_j≤…≤p_N. 对边缘服务器匹配用户队列 $\scriptstyle E_1^U, \cdots , E_j^U, \cdots , E_{N - 1}^U $ 中的各用户按照请求计算资源升序排列, 对 $\scriptstyle E_N^U $ 中的各用户按照请求计算资源降序排列;

For each user in $\scriptstyle E_N^U $ //遍历第n个边缘服务器匹配用户队列

4) 从 $\scriptstyle E_N^U $ 选择第1个用户u_i, 如果第j个边缘服务器还有计算资源, 则从该服务器选择第1个用户 $\scriptstyle u'_1$ . 如果 $\scriptstyle {R_{{u_i}, j}} $ ≤D_j, 则将u_i交换至边缘服务器j. 如果 D_j < $\scriptstyle {R_{{u_i}, j}} $ 并且 $\scriptstyle {R_{{u_i}, N}} $ < $\scriptstyle {R_{u'_1, N}}$ , 则说明该边缘服务器无法交换, 判断下一个边缘服务器. 如果两个边缘服务器的计算资源足够交换且交换后用户效益和边缘服务器效益没有下降, 则将u_i与 $\scriptstyle u'_1$ 交换, 直到u_i交换完全;

End for

For each user in W_L//循环失败匹配队列, 重新拍卖

5) 判断用户u_i是否有可以重新拍卖的边缘服务器, 如果 $\scriptstyle {R_{{u_i}, j}} $ ≤D_j, 则将u_i拍卖给边缘服务器j, 并将该用户加入成功匹配队列W_U $\scriptstyle \leftarrow $ W_U $\scriptstyle \cup $ u_i;

End for

for each $\scriptstyle E_j^U $ in $\scriptstyle E_N^U $ , j=1, 2, …, N//遍历每个边缘服务器匹配用户队列, 计算效益

6) 分别用式(6)和式(8)计算用户效益U_user和边缘服务器效益U_ES ;

End for

If ║U_ES(t)–U_ES(t–1)║>ε

7) 改变各边缘服务器资源定价p_j $\scriptstyle \leftarrow $ p_j+δ $\scriptstyle \frac{{\partial U_j^P}}{{\partial {p_j}}} $ ; 重复步骤1)–6)

End if

在算法1中, 步骤2)为第一轮拍卖, 目的是各用户贪婪资源分配. 在首轮计算资源拍卖结束后, 对于各拍卖成功的用户, 他们的效益是最优的, 因为他们在成本最低的边缘服务器上获得了计算资源. 但此时仍可能存在资源浪费现象, 因为部分用户会在一些成本较低的边缘服务器上占用过多计算资源, 从而导致部分用户拍卖失败, 用户整体效益不是最优的. 因此需要进行第2轮计算资源拍卖, 将失败用户与边缘服务器进行重新匹配.

在第2轮拍卖开始前, 需要先在边缘服务器之间进行用户交换, 即步骤4), 目的是节省出部分计算资源给失败用户. 在边缘服务器之间的任务交换过程中会出现如下3种情况.

① 如果用户任务i在E_j上的请求计算资源小于等于E_j的剩余资源, 则将该用户从 $ E_N^U $ 中移除, 并加入E_j中.

② 如果用户任务i在E_j上的请求计算资源大于该边缘服务器的剩余计算资源, 且任务i在E_N上的计算资源小于 $ E_j^U $ 上第一个任务在E_j上的计算资源, 则边缘服务器j不能进行任务交换.

③ 如果不满足②中的两个条件, 说明E_j可以进行交换. 如果 $ \forall $ ${R_{u'_j, N}}$ < $ {R_{{u_i}, N}} $ , $\displaystyle\sum\limits_{j = 1}^k {{R_{u'_j, j}} \lt {R_{{u_i}, j}}}$ , 则E_j不能进行交换, 因为E_j可以交换用户的计算资源无法满足条件. 如果上述条件满足, 但交换后用户整体效益降低, 那么E_j仍无法进行任务交换, 判断下一个边缘服务器. 当找到一个可以交换的任务队列后, 则将两个队列上的任务进行交换, 从而增加E_N的剩余计算资源.

之后, 失败用户开始重新进行拍卖. 通过判断每一个失败任务对不同边缘服务器的请求资源是否满足 $ {R_{{u_i}, j}} $ ≤D_j来匹配它们. 在完成第2轮拍卖后, 系统中的计算资源被更高效地利用, 且成功拍卖用户增多, 用户效益与边缘服务器效益进一步增加. 最后, 步骤7)通过不断修改边缘服务器资源定价, 从而使得系统中用户和边缘服务器效益整体达到最佳.

与传统双重拍卖算法相比, 本文提出算法的不同在于: 1)我们将 $ {o_{i, j}} $ 作为首轮拍卖的重要指标, 不仅仅考虑价格; 2)用户将有更多机会参与拍卖, 因为每个用户会有不同的选择和出价, 而传统算法中出价低的用户基本没有机会; 3)拍卖完成后, 对资源进行重新整合, 使更多失败用户可以重新拍卖. 在首轮拍卖中, 各用户基于贪心思想优化自身利益, 会不顾其他用户的拍卖情况, 选择最优于自己的边缘服务器完成拍卖, 因此部分用户会占用较多的资源, 陷入局部最优; 第2轮拍卖前, 将计算资源进行重新整合, 放弃掉部分第一轮拍卖中的局部最优解, 使失败用户可以重新参与拍卖, 实现系统整体效益最优.

算法的步骤2)需要遍历整个用户集合, 共有M个用户, 因此需要的时间为O(M); 步骤4)要进行资源整合, 会对收费最高服务器队列的用户进行遍历, 该队列最大数量为用户总数M, 因此需要的时间为O(M). 遍历每一个用户时, 需要访问剩余N–1个边缘服务器, 以判断是否有剩余计算资源供整合, 每个用户所需时间为O(N–1), 因此步骤4)的总时间为O(MN); 步骤5)对失败用户重拍卖, 最大数量为用户总数, 因此需要的时间为O(M). 遍历每一个用户时, 需要访问N个边缘服务器, 以判断是否有剩余计算资源供失败用户重新拍卖, 每个用户所需时间为O(N), 因此步骤5)的总时间为O(MN). 综上, 算法1的时间复杂度为O(MN).

需要注意的是, 贪心策略在大多数问题上容易陷入局部最优. 比如0-1背包问题中, 使用贪心策略不能保证背包可以装满, 部分闲置空间会使背包价值下降. 但本文假设用户任务无法拆分情况, 并且为了保证用户QoS标准, 每个用户都有硬时延要求, 因此各用户请求资源有最小值, 无法将边缘服务器计算资源完全拍卖. 且在实际生活场景, 很难做到资源的完美消耗. 所以本文提出的算法可以实现完全卸载情况下的整体最优.

4 仿真结果与分析 4.1 实验设置

本文的仿真实验设置的应用场景为多用户需要计算卸载的大型小区, 假设系统中共有5个边缘服务器, 用户数量从80个到130个递增. 不同服务器之间具有定价、算力以及物理位置的差异, 同时服务器的初始定价与其算力成正比. 用户和边缘服务器随机分布在半径为1000 m的区域, 如图3所示. 式(4)中的参数设置为β₁=0.1, β₂=0.1, β₃=0.8. 其他参数及具体数据范围如表1所示. 取20次实验结果的平均值, 并且同以下4种基准算法进行对比:

随机匹配算法 (random matching algorithm, RMA): 用户随机与边缘服务器进行拍卖.

顺序匹配算法 (sequential matching algorithm, SMA): 类似于传统双重拍卖算法, 用户按照边缘服务器价格由低到高拍卖.

文献[25]提出的(breakeven based double auction, BDA): 将边缘服务器出价的中间值作为breakeven点, 并以此过滤掉部分不符合拍卖的用户.

文献[31]提出的(double action of multi-type multi-resource based on dynamic pricing, DAMMDP): 成功交易的价格是由边缘服务器决定的, 并且该价格是用收费更高的边缘服务器来代替. 收费最高的边缘服务器参与拍卖时价格不变.

4.2 仿真结果分析

图4–图6展示了不同的用户数量对于成功匹配用户总体效益、边缘服务器效益、成功匹配用户数量的影响. 可以发现, 当用户数量较少时, 各算法在效益和成功匹配数量上的表现是接近的, 因为此时边缘服务器中所拥有的计算资源还没有被完全占用, 每个用户都可以匹配给相应的边缘服务器. 当用户数量继续上升时, 边缘服务器的计算资源几乎被分配完, 此时各算法之间的差异增大.

图4可以看出, 随着用户数量的增加, IDAG算法的成功匹配用户效益在不断增加, 与其他算法的差距增大. 这是因为当边缘服务器计算资源消耗殆尽时, 通过二次拍卖将部分计算资源结余出来留给匹配失败的用户, 因此成功匹配的用户更多, 且效益增加. 其他算法随着用户增加后, 失败匹配用户逐渐增加, 并且没有边缘服务器之间的任务交换, 因此成功匹配用户效益增长程度逐渐趋平. 随着用户数量的增加, 随机匹配、顺序匹配和DAMMDP算法都出现了波动. 这是因为在随机匹配和顺序匹配中, 用户任务数据量的改变会产生较大的影响. 但当用户数量到达110以后, 这两种方法的用户效益趋于稳定. 因为用户已经将系统内边缘服务器的计算资源全部占用. 对于DAMMDP算法, 由于其为了增加成功匹配用户数量, 在定价阶段将所有用户的出价提高, 从而导致随着用户的增多, 成功匹配用户的整体效益出现下降. 而BDA算法为了提高系统用户总效益, 会删除掉成本较高的边缘服务器和用户任务, 因此随着用户数量的增加, 其用户效益仍在增加. 但由于没有资源重分配过程, 因此当系统内计算资源完全占用后, 用户效益难以增加.

图5中, 用户数量从80到90时, 边缘服务器的效益出现的急剧提高. 这是因为边缘服务器的计算资源被大量占用, 且边缘服务器的效益与分配的计算资源正相关, 因此效益提升. 当用户数量继续增加, 边缘服务器的计算资源已经被用户任务占用完全, 效益难以提升, 趋于稳定. 可以看出, BDA策略和DAMMDP策略的效果较差, 这是因为BDA会删去成本较高边缘服务器的, 因此边缘服务器的效益会降低; 而DAMMDP会提高用户成本, 从而使得这类用户的拍卖优先级降低, 使得边缘服务器效益降低.

从图6中可以看出, BDA算法和DAMMDP算法的成功匹配用户数相比于随机匹配和顺序匹配效果更优, 但代价就是效益的降低. 在一些需要增加成功匹配用户数量且对算法运行时间较为敏感的场景中, BDA算法和DAMMDP算法更具有优势. 由于IDAG算法有资源重分配过程, 因此即使当用户数量到达100以后系统内计算资源占用完毕, 本文提出的算法仍然可以使更多用户与边缘服务器匹配.

IDAG算法相对于基准算法在成功匹配用户效益、边缘服务器效益的提升分别为: 33.4%、8.2%.

图7和图8展示了当用户数量为100、用户效益系数为5时( $ {\lambda _i} $ =5), 边缘服务器的计算能力 $\; {\mu _j} $ 对于用户效益和计算资源请求量的影响.

从图7中可以看出, 随着计算能力的提高, 系统中成功匹配用户的效益在不断提高, 这是因为单位计算资源的数据处理能力在同步提高. 用户的任务数据量不变, 从而用户请求的计算资源量就会减少, 因此成功匹配用户的成本会减少, 效益会提高. 同时, 从图8中可以发现, 正如前面提到的, 用户对于计算资源的请求量在不断减少.

图9和图10展示了当用户数量为100、边缘服务器计算能力 $ \;{\mu _j} $ 为[6, 10]时, 用户效益参数对于成功匹配用户效益和请求计算资源量的影响. 当效益参数提高, 单位计算资源就可以带来更高的效益. 因此, 随着效益参数的提高, 用户的收益会增加, 可以购买更多的计算资源来减少计算时延, 提高用户的QoS. 可以看出, 用户效益参数与用户请求的计算资源呈正相关, 式(15)也可以看出这种变化; 同时, 用户效益在不断提升. 因为用户收益的提高会超过其额外申请计算资源带来的成本增加.

总的来说, IDAG算法无论在用户效益、边缘服务器效益还是系统总体效益都相较于4种基准算法有较为明显的提升. 同时, 在成功匹配用户数量上也表现不俗, 并且也达到了理想的平衡. 因此, 在边缘服务器与用户随机分布的场景中, 本文提出的IDAG算法有着优异的性能.

5 结论

本文研究了边缘服务器随机分布的MEC场景中用户和边缘服务器效益问题. 首先通过将用户与边缘服务器之间的交互过程建模为Stackelberg博弈, 并验证了该博弈存在唯一的纳什均衡点. 为找到最优任务卸载和计算资源请求策略, 提出了一种基于贪心思想的改进双重拍卖算法. 实验结果表明, 与其他基准算法相比, 提出的IDAG算法可以有效提高系统内成功拍卖的用户效益和边缘服务器效益, 并且能使更多用户将任务卸载至边缘服务器计算. 在未来, 这项工作将加强云服务器对于整体策略的影响, 并将用户QoS标准作为计算用户效益的一个重要指标.