Task Assignment for Semi-opportunistic Mobile Crowdsensing

In this paper, we propose a novel crowdsensing paradigm called semi-opportunistic sensing, which is aimed to achieve high task quality with low human involvement. In this paradigm, each mobile user can provide multiple path choices to reach her destination, which largely broadens the task assignment space. We formulate the task assignment problem in this paradigm of maximizing total task quality under incentive budget constraint and user travel time constraints. We prove this problem is NP-hard and then propose two efficient heuristic algorithms. First, we propose a Best Path/Task first algorithm (BPT) which always chooses current best path and current best task into the assignment list. Second, we propose an LP-relaxation based algorithm (LPR), which greedily assigns paths and tasks with the largest values in LP relaxation solution. We deduce the computational complexities of the proposed algorithms. We evaluate the performance of our algorithms using real-world traces. Simulation results show that our proposed crowdsensing paradigm can largely increase overall task quality compared with the opportunistic sensing paradigm where each user has only one fixed path. Simulation results also show that our proposed algorithms are efficient and their performance is close to the optimal solution.