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

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

被 2 个通信基站覆盖, 则此时 T=3. 若在第 1 轮双边拍卖中用户 1 达成交易, 那么第 2 轮拍卖时, T=2.

算法 1. DACRA 算法框架.
输入: U: 所有用户信息的集合; S: 边缘服务器提供商信息的集合; B: 通信基站信息的集合.
1. 初始化: t ⇐ 1: 当前拍卖次数; T ⇐ 1: 最大可执行拍卖次数; A ⇐ 0: 用户分组列表, 第 j 项表示第 j 组的用户集
e
;
e
e
合 A j U ⇐ 0: 存在交易用户列表, 第 j 项表示第 j 组存在交易的用户集合 U ; S ⇐ 0: 存在交易边缘服务器提供商
j
s
列表, 第 j 项表示第 j 组存在交易边缘服务器提供商集合 S ; U ⇐ ∅: 成功交易的用户集合.
e
j
2. while t ⩽ T and U , ∅ do
3. A,T ⇐ 算法 2 (U,B);
4. for 1 ⩽ j ⩽ L do
U ,S ⇐ 算法 3
e
e
5. j j (A j ,Z j );
6. end for
e
e
7. X, P,Y,W ⇐ 算法 4 (U ,S );
,
8. for 1 ⩽ i ⩽ N 1 ⩽ m ⩽ M do
x i,m = 1 then
9. if
s
s
10. U ⇐ U ∪ {用户 i};
11. end if
12. end for
s
13. U ⇐ U/U ;
s
14. U ⇐ ∅;
15. t ⇐ t +1;
16. end while
17. 向所有用户发送 X, P,Y,W;
18. 向所有边缘服务器提供商发送 X, P;
19. 向所有通信基站发送 Y,W;
输出: X: 计算资源分配关系矩阵; P: 计算资源的成交费用矩阵; : 通信关系矩阵; W: 通信费用矩阵.
Y
3.2 距离分组算法
算法 2 以用户、通信基站提供的信息 U、B 作为输入. 首先, 根据用户与通信基站之间的欧氏距离确定覆盖
该用户的通信基站. 然后, 计算最大可执行拍卖次数 T 并将用户加入距其最近的通信基站所在分组中. 如果用户与
多个通信基站距离最近, 则随机加入其中一个通信基站所在分组. 最后, 返回计算得到的 T 以及形成的分组 A 至
算法 1 中. 距离分组算法的时间复杂度为 O(LN).

算法 2. 距离分组算法.
输入: U: 所有用户信息的集合; B: 通信基站信息的集合.
1. 初始化: C ⇐ 0: 每个用户被通信基站覆盖集合的列表; M ⇐ 0: 每个用户距离最短通信基站集合的列表; A ⇐ 0:
每个用户分组的列表; T ⇐ 1: 最大可执行拍卖次数.
,
2. for 1 ⩽ i ⩽ N 1 ⩽ j ⩽ L do
√
2
2
3. τ i,j ⇐ (µ j −γ i ) +(ξ j −β i ) ;
4. if τ i,j > λ j then
5. τ i,j ⇐ ∞;