Social-Aware Task Allocation in Mobile Crowd Sensing

Task allocation is a significant issue in crowd sensing, which trades off the data quality and sensing cost. Existing task allocation works are based on the assumption that there is plenty of users available in the candidate pool. However, for some specific applications, there may be only a few candidate users, resulting in the poor completion of tasks. To tackle this problem, in this paper, we investigate the task allocation problem with the assistance of social networks. We select a subset of users; if a user can not complete the task, he can propagate the task information to his friends. The object of this problem is to maximize the expected number of completed tasks. We prove that the task allocation problem is an NP-hard and submodular problem and then propose a native greedy selection (NGS) algorithm, which selects the user with maximum margin gain in each round. To improve the efficiency of the NGS algorithm, we further propose a fast greedy selection algorithm (FGS), which selects the user who can actually complete the maximum number of tasks. Experimental results show that although FGS gets slightly worse results in terms of the expected number of completed tasks, it can greatly reduce the running time of seed selection