空间众包中可拒绝情况下的在线任务分配-《浙江科技学院学报》

文章信息/Info

Title:: Online task assignment under rejectable conditions in spatial crowdsourcing

Author(s):: LIN Huihui; HUANG Jie; LI Yu; WAN Jian; School of Information and Electronic Engineering, Zhejiang University of Science and Technology,Hangzhou 310023, Zhejiang, China; School of Computer and Software,Hangzhou Dianzi University, Hangzhou 310018, Zhejiang, China

摘要:: 现实中空间众包任务可能会遭到任务执行者的拒绝,为解决该问题提出动态可拒绝的空间众包处理方法。首先,为降低被拒绝的概率,运用主成分分析法(principal components analysis,PCA)计算任务执行者对任务的兴趣度;然后针对任务动态分配问题采用批处理模式解决,提出基于MaxFlow的排序算法(sequence algorithm base on MaxFlow,SMF)和基于KM算法(KuhnMunkres,KM)的不重复构造交替树算法(nonrepetitive construction of alternating tree algorithm based on KM,NRKM)寻找全局最大匹配下最高兴趣度分配方案;最后将贪心算法(greedy algroithm)、KM算法和SMF算法作为对照算法,与NRKM算法在CPU时间成本、任务分配数量和任务分配兴趣度3个方面进行比较。结果表明NRKM算法相对于KM算法、SMF算法在分配效率上分别提高11%和9%。可见,NRKM算法能高效解决可拒绝情况下空间众包任务的分配,对解决空间众包任务涉及执行者意愿的分配问题具有参考价值。