林荟荟,黄 杰,李 玉,万 健

(1.浙江科技学院 信息与电子工程学院,杭州 310023;2.杭州电子科技大学 计算机学院,杭州 310018)

随着移动网络的发展和移动设备的普及,空间众包越来越受到人们的关注[1],任务分配问题是空间众包的核心问题[2-4]。目前学术界主要讨论如何将任务高效地分配给任务执行者,同时对其分配的优化目标主要为最大化整体任务分配数量[5-6]。Hien等[7]扩展了分配模型,为每个任务执行者-任务对设置权重,并以最大化总任务分配权重为目标。但是现实中任务执行者和任务是动态变化的,该模型仍然无法实现在整个时间线上最大化任务分配数量的目标。Chen等[8]提出一种基于预测的任务分配算法,然后用贪心算法最大化当前与未来的任务分配数量。但通过采样的方式进行预测,在时间和空间上预测准确度不高。

以上研究都是基于平台分配任务,任务执行者保证执行空间众包任务。但现实中每个任务执行者对任务的选择具有主观性,任务执行者都希望能执行符合他们意愿的任务,比如在自己所处位置附近[9]、任务报酬高[10]的任务,或是与自己的知识、技能相匹配的任务[11]。Zheng等[12]首次定义有拒绝的空间众包问题,提出4种近似分配算法来提高分配的效率,但采用的是静态分配的方法得到最优分配。本研究基于平台分配任务的方式(server assigned tasks,SAT)[13-14]探讨空间众包中任务执行者可拒绝情况下的在线任务分配问题[15],实现提出动态可拒绝的空间众包处理方法:首先最大化任务分配数量,即实现最大匹配;然后,针对任务执行者的主观性,为减少任务执行者拒绝的概率,寻找全局最大匹配下最高兴趣度分配方案。……