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

4802 软件学报 2025 年第 36 卷第 10 期

6. else
7. C i ⇐ C i ∪ {通信基站 j};
8. end if
9. end for
10. for 1 ⩽ i ⩽ N do
11. if T ⩽ len(C i ) then
12. T ⇐ len(C i );
13. end if
C i = ∅ then
14. if
15. continue;
16. end if
17. M i ⇐ min(C i );
18. j ⇐ random(M i );
19. A j ⇐ A j ∪ {用户 i};
20. 设置用户 i 不可再加入第 j 组;
21. end for
T
输出: A: 用户分组的列表; : 最大可执行拍卖次数.
3.3 潜在交易匹配算法
算法 3 输入包括第 j ∈ Γ 组的用户集合 A j 和边缘服务器提供商集合 . 首先, 计算无线带宽和计算资源的稀
Z j
缺度以及用户和边缘服务器的竞价密度. 然后, 按照无线带宽资源竞价密度降序排序用户集合, 并在此基础上再按
照计算资源竞价密度降序排序. 边缘服务器提供商则根据竞价密度升序排序. 最后, 根据用户出价、边缘服务器提
供商要价、计算资源和无线带宽资源约束得到潜在交易列表, 并将结果进行排序后返回算法 1. 潜在交易匹配算
法的时间复杂度受两层循环影响, 根据 A j 和 Z j 的定义得到 len(A j )len(Z j ) ⩽ NM, 因此该算法时间复杂度为 O(NM).
算法 3. 潜在交易匹配算法.

输入: A j : 第 j 组用户的集合; Z j : 第 j 组边缘服务器提供商的集合.
e
e
1. 初始化: U ⇐ ∅: 第 j 组存在交易的用户集合; S ⇐ ∅: 第 j 组存在交易的边缘服务器提供商集合; ρ ⇐ 0: 已经
j j
分配的无线带宽之和.
2. for 1 ⩽ m ⩽ len(Z j ) do
/ √
)
(∑ ∑
R R
3. SD m = s m,r ·c m,r f r ·c m,r ;
r=1 r=1
4. end for
5. for 1 ⩽ i ⩽ len(A j ) do
/ √
R R
(∑ ) ∑
6. UD i ⇐ b i,r ·d i,r f r ·d i,r ;
r=1 r=1
/ √
7. UD i,BW ⇐ (b i,BW ·d i,BW ) f BW ·d i,BW ;
8. end for
9. A j ⇐ descend_sort(UD i,BW );
10. A j ⇐ descend_sort(UD i );
11. Z j ⇐ ascend_sort(SD m );