Page 408 - 《软件学报》2025年第10期

汪建洲 等: 基于双边拍卖的多基站移动边缘计算资源分配方法 4805

不难看出, 在任何一种情况下, 用户、边缘服务器提供商、通信基站和平台的效用均非负. 因此, DACRA 机
制是个体理性的.
性质 4. DACRA 为多项式时间算法.
证明: 根据第 3.2–3.4 节, 知道算法 2 时间复杂度为 O(LN), 算法 3 时间复杂度为 O(NM), 算法 4 时间复杂度
为 O(LNM). DACRA 算法执行资源分配过程, 需要调用 T 次算法 2, 调用 TL 次算法 3, 调用 T 次算法 4. 此外, 根
2
据 T 的定义得到 T ⩽ L. 因此, DACRA 机制的时间复杂度为 O(L NM), DACRA 是多项式时间算法.
3.6 DACRA 算法举例
本节通过一个简单的多基站多边缘服务器 MEC 例子 (如图 2 所示) 说明 DACRA 机制执行的过程. 其中, 用
户 1–3 同时被两个基站覆盖, 用户 4 只被一个基站覆盖, 边缘服务器提供商 1 依赖通信基站 1 进行通信, 提供商 2
依赖基站 2 通信. 等待分配的有提供商的计算资源 (CPU 和内存) 和基站的无线带宽资源. 用户 1–4 的需求分别是
(5, 8, 8)、(3, 5, 6)、(5, 8, 8) 和 (3, 5, 6), 对应出价为 (11, 8, 6)、(11, 8, 6)、(10, 8, 7) 和 (9, 7, 5), 边缘服务器提供商
1 和 2 的计算资源容量分别是 (9, 14) 和 (10, 16), 对应要价为 (7, 6) 和 (7, 7), 通信基站 1 和 2 的无线带宽容量为
16 和 15.

...
通信
基站 1 边缘服务器
提供商 1
...
用户 3
...
用户 2 ...
用户 4
...
... 边缘服务器
提供商 2
用户 1
通信基站 2
图 2 多基站多边缘服务器 MEC 例子

算法收集用户、边缘服务器提供商和通信基站信息后执行双边拍卖. 算法 1 调用算法 2 进行用户分组, 为得
到用户 1–4 均存在潜在交易. 再调用算法 4 计算得到用户计算资源和无线带宽资源支付单价分别为 f p =7.75 和
f w =5.00, 对应边缘服务器计算资源接收单价 f e =7.38, 该价格由用户 4 和提供商 2 的潜在交易产生, 取消该笔交易.
用户 3 由于基站 1 无线带宽不足也无法达成交易, 最后用户 1 和 2 与边缘服务器 1 交易, 它们使用通信基站 1 通
信. 因为最大拍卖次数 T=2, 对剩余用户再进行 1 次双边拍卖, 得到 f p =7.75、f w =5 和 f e =7.37. 用户 3 与边缘服务器
2 达成交易, 并使用通信基站 2 通信, 双边拍卖结束.
用户 1–4 的效用分别为 26.25、23、29.25 和 0, 用户 4 可以通过提高出价来达成交易, 但这会使得它的效用
低于 0, 而用户 1–3 降低出价则可能使得他失去交易机会从而效用降为 0. 边缘服务器提供商 1 和 2 的效用分别
为 20.88 和 4.88, 也同样无法通过修改要价而提高它的效用. 因此, 用户和边缘服务器的占优策略是诚实报价.
4 仿真与分析

本节通过开放数据集的仿真实验, 将 DACRA 与现有方法在社会福利、请求成功率和资源利用率上的性能进
行比较. 最后通过一组特定的仿真实验验证第 3.5 节中的性质, 实验中包括以下对比算法.
(1) 经典的迈克菲双边拍卖 McAfee’s DA (McAfee’s double auction) [31] . 其核心思想是一种基于占优策略的双
边拍卖.
(2) 动态组合双边拍卖算法 DCDA (dynamic combinatorial double auction) [30] . 该算法通过定义计算资源稀缺度