Abstract: Privacy protection and task allocation are two core issues in spatial crowdsourcing. Based on Euclidean space, most of existing researches use geo-indistinguishability (GeoI) to protect location privacy, while ignoring the underlying road network information, which leads to privacy leakage and utility loss of crowdsourcing workers. In order to protect the location privacy of workers and produce small utility loss, a privacy-preserving batch task allocation algorithm framework for road network is proposed. Firstly, the graph-exponential mechanism optimization problem is proposed, and a greedy algorithm is designed to find the approximate optimal solution. At the same time, the edge server is introduced as the privacy protection agent of workers. Then, the task allocation problem is transformed into a bipartite graph maximum flow problem with the weight of workers travel distance, and the optimal solution is obtained by using Kuhn Munkras (KM) algorithm. Finally, the experiment results show that the proposed algorithms significantly improves both privacy protection and utility.

Key words: spatial crowdsourcing, road network, graph-exponential mechanism, task allocation, Kuhn Munkras (KM) algorithm