SRA: Secure Reverse Auction for Task Assignment in Spatial Crowdsourcing

摘要

In this paper, we study a new type of spatial crowdsourcing, namely competitive detour tasking, where workers can make detours from their original travel paths to perform multiple tasks, and each worker is allowed to compete for preferred tasks by strategically claiming his/her detour costs. The objective is to make suitable task assignment by maximizing the social welfare of crowdsourcing systems and protecting workers' private sensitive information. We first model the task assignment problem as a reverse auction process. We formalize the winning bid selection of reverse auction as an $n$n-to-one weighted bipartite graph matching problem with multiple 0-1 knapsack constraints. Since this problem is NP-hard, we design an approximation algorithm to select winning bids and determine corresponding payments. Based on this, a Secure Reverse Auction (SRA) protocol is proposed for this novel spatial crowdsourcing. We analyze the approximation performance of the proposed protocol and prove that it has some desired properties, including truthfulness, individual rationality, computational efficiency, and security. To the best of our knowledge, this is the first theoretically provable secure auction protocol for spatial crowdsourcing systems. In addition, we also conduct extensive simulations on a real trace to verify the performance of the proposed protocol.