Spatial Task Assignment Based on Information Gain in Crowdsourcing

Abstract

Spatial crowdsourcing provides workers for performing cooperative tasks considering their locations, and is drawing much attention with the rapid development of mobile Internet. The key techniques in spatial crowdsourcing include worker-mobitlity-based task matching for more information gain and efficient cooperation among coworkers. In this paper, we first propose information gain based maximum task matching problem, where each spatial task needs to be performed before its expiration time and workers are moving dynamically. We then prove it is a NP-hard problem. Next, we propose two approximation algorithms: greedy and extremum algorithms. In order to improve the time efficiency and the task assignment accuracy, we further propose an optimization approach. Subsequently, for complex spatial tasks, we propose a feedback-based cooperation mechanism, model the worker affinity and the matching degree between a task and a group of coworkers, and design a feedback-based assignment algorithm with group affinity. We conducted extensive experiments on both real-world and synthetic datasets. The results demonstrate that our approach outperforms related schemes.