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

3848 Journal of Software 软件学报 Vol.31, No.12, December 2020

时间槽长度变化对算法的影响如图 8 所示.算法的默认设置是区域大小是 0.5km×0.5km,工人、用户和工作
点的数量是 20k,用户等待时间 15 分钟,时间槽长度从 5 分钟变化到 30 分钟.由于 OPT 算法和 DM 算法的效果
与时间槽的长度无关,所以两种算法的曲线都保持直线,时间槽的长度影响预测结果,从而影响 POM 算法,所以
POM 算法的曲线根据参数变化而变化.
• POM 算法的匹配结果如图 8(a)所示:匹配数量随着时间槽的增长呈先上升后下降的趋势.原因是当时
间槽过短时,预测的准确性降低,离线匹配结果对在线匹配的指导性不强,在线匹配过程中无法在离线
结果中找到合适的匹配结果,算法效果类似于 DM;当时间槽长度超过最长等待时间时,用提前失效现
象会发生,即离线匹配中的结果会由于用户超过等待时间而失效,在线匹配只能从当前空闲的资源中
查找匹配,导致匹配的数量开始下降;
• 算法运行时间如图 8(b)所示:当时间槽长度和用户等待时间相近时, POM 算法的运行时间最短,其他时
间由于多次调用 DM 算法导致时间上升;
• 算法的内存占用如图 8(c)所示:由于时间槽长度增加,离线匹配结果增加,导致算法存储空间增大.

(a) 匹配数量 (b) 运行时间 (c) 内存占用
Fig.8 Results on varying length of slots
图 8 时间槽长度变化的实验结果
区域大小变化对算法的影响如图 9 所示.3 种角色的数量是 20k,用户等待时间 15 分钟,时间槽长度 15 分钟,
划分区域大小从 0.1km×0.1km 变化到 1.0km×1.0km.如时间槽长度变化的实验分析中所提到的,OPT 算法和 DM
算法与区域大小划分无关,所以两种算法的曲线都保持直线,划分区域大小影响预测结果,从而影响 POM 算法,
所以 POM 算法的曲线根据参数变化而变化.

(a) 匹配数量 (b) 运行时间 (c) 内存占用
Fig.9 Results on varying grid size
图 9 区域大小变化的实验结果

• POM 算法的匹配结果如图 9(a)所示:随着划分区域面积的不断增大,POM 算法的匹配结果呈先上升后
下降的趋势.这个趋势和时间槽的划分有相似之处,但是原因不同.当区域过小时,预测准确性降低,此
时无法起到指导作用,离线匹配中查找不到合适的结果,所以需要对当前闲置资源调用 DM 算法进行
匹配.当区域过大时,预测算法将产生大量预测结果,但是由于区域划分过大,导致在线分配时这些结果
不一定都是稳定的,找不到稳定匹配的用户要调用 DM 算法进行处理,此时和用户提前失效的结果
相似;