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

摘要

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