Page 181 - 《软件学报》2020年第12期

李博扬 等:新型时空众包平台中的在线三维稳定匹配问题 3847

间、时间槽长度和区域大小.
首先报告工人数量、用户数量和工作点数量变化对算法结果的影响.实验的设置是用户等待时间 15 分钟,
时间槽长度 15 分钟,区域大小是 0.5km×0.5km,工人、用户和工作点数量从 10k 扩展到 100k.
• 3 种算法匹配数量的结果如图 6(a)所示:随着工人数量、用户数量和工作点数量的不断增加,3 种算法
的匹配数量不断上升,POM 算法的匹配效果一直高于 DM 算法,低于 OPT 算法;
• 算法的运行时间如图 6(b)所示:OPT 算法的运行时间远远高于其他算法,POM 算法的运行时间略低于
DM 算法,且两种算法的运行时间增幅较缓;
• 算法的内存占用如图 6(c)所示:OPT 算法由于索引的使用内存占用迅速增加,POM 算法和 DM 算法的
内存占用都有增加,且 POM 算法的内存占用高于 DM 算法.

(a) 匹配数量 (b) 运行时间 (c) 内存占用
Fig.6 Results on varying |W|, |U| and |P|
图 6 工人数量、用户数量和工作点数量变化的实验结果
用户等待时间变化对算法的影响如图 7 所示.算法的默认设置是时间槽长度 15 分钟,区域大小是 0.5km×
0.5km,工人、用户和工作点的数量是 20k,用户等待时间从 5 分钟变化到 30 分钟.
• 3 种算法的匹配数量都随着等待之间的延长而多变,如图 7(a)所示:OPT 算法的匹配数量一直最多,
POM 算法在等待时间短时的结果差于 DM 算法.随着等待时间边长,POM 效果高于 DM 算法.原因是
当等待时间小于时间槽长度时,离线匹配结果可能提前失效,要调用 DM 算法来为这些用户进行在线
分配,但是很多角色还在离线匹配结果中,导致可用的工人和工作点很少,匹配结果不理想.随着等待时
间逐渐边长,这种提前失效的情况消失,匹配结果变好;
• 算法的运行时间如图 7(b)所示:OPT 算法时间消耗上升较快;在等待时间远低于时间槽长度时,POM 算
法的运行时间和 DM 算法差不多,原因和匹配结果一致.随着等待时间变长,POM 算法的运行时间低于
DM 算法;
• 算法的内存占用如图 7(c)所示:由于索引开销加大,OPT 算法的内存消耗持续上涨,POM 算法和 DM 算
法的内存消耗小幅上涨,这是在线分配结果和可选工人数量变多的缘故.等待时间的变长不影响离线
匹配的结果,所以 POM 算法的内存增长和 DM 算法趋势一致.

(a) 匹配数量 (b) 运行时间 (c) 内存占用
Fig.7 Results on varying T u
图 7 用户等待时间变化的实验结果