时空众包环境下时效均衡的在线任务分配算法

摘要

针对时空众包任务分配研究中单一考虑任务分配总效用或任务等待时间,导致总体分配效果不佳的问题,提出一种基于分配时间因子的动态阈值算法.首先,基于预估等待分配时间和已等待分配时间计算任务的分配时间因子;其次,综合考虑任务的回报值和分配时间因子进行任务分配排序;然后,在初始值的基础上增加动态调整项为每一项任务设置阈值;最后,根据阈值条件为每一项任务设置候选匹配集,并从候选匹配集中选择匹配系数最大的候选匹配对加入结果集,完成任务分配.通过实验证明,该算法在任务分配率达到95.8％的情况下,与贪心算法相比,在分配总效用方面提升20.4％;与随机阈值算法相比,在分配总效用方面提升17.8％,在任务平均等待时间方面缩短13.2％;与基于两阶段框架模型的在线微任务分配改进(TGOA-Greedy)算法相比,在分配总效用方面提升13.9％.实验结果表明,该算法能够在提升任务分配总效用的同时缩短任务的平均等待时间,实现分配总效用与任务等待时间两者间的均衡.