空间众包中可拒绝情况下的在线任务分配

Online task assignment under rejectable conditionsin spatial crowdsourcing

现实中空间众包任务可能会遭到任务执行者的拒绝,为解决该问题提出动态可拒绝的空间众包处理方法。首先,为降低被拒绝的概率,运用主成分分析法(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算法能高效解决可拒绝情况下空间众包任务的分配,对解决空间众包任务涉及执行者意愿的分配问题具有参考价值。

In reality,spatial crowdsourcing tasks may be rejected by task executors.To solve this problem,a dynamic and rejectable spatial crowdsourcing method was proposed.First,in order to lower the probability of rejection,the principal components analysis(PCA)was used to calculate the interest of the executor in the task;then,the batch processing mode was adopted to solve the problem of task dynamic allocation,and sequence algorithm based on MaxFlow(SMF)and non-repetitive construction of alternating tree algorithm based on KM(NR-KM)were proposed to find the highest interest allocation scheme under the global maximum matching;finally,greedy algorithm,KM algorithm(Kuhn-Munkres)and SMF algorithm were used as the control algorithm to compare the CPU time cost,task assignment quantity and task assignment interest with the NR-KM algorithm.The results show that the NR-KM algorithm improves the allocation efficiency by 11%and 9%,respectively,compared with KM algorithm and SMF algorithm.It can be seen that the NR-KM algorithm efficiently solves the assignment of spatial crowdsourcing tasks under rejectable conditions,and has reference value for solving the assignment problem of spatial crowdsourcing tasks involving the executor s will.