To solve the problem of privacy leakage in crowdsourced location data collection, a locally differentially private location data collection method with crowdsourcing was proposed. Firstly, a Voronoi diagram constructed by point-by-point insertion method was used to partition the road network space. Secondly, a random disturbance satisfying local differential privacy was used to disturb the original location data in each Voronoi grid. Thirdly, a designed spatial range query method was applied to noisy datasets to get the unbiased estimation of the actual result. Finally, experiments were carried out on spatial range queries to compare the proposed algorithm with PTDC (Privacy-preserving Trajectory Data Collection) algorithm. The results show that the query error rate is no more than 40%, and less than 20%in the best situation, and the running time is less than 8 seconds, which are better than those of PTDC algorithm while the proposed method has a higher degree of privacy preserving.

Since the data utility would be sharply reduced after privacy-preserving process and several attack models could not be resisted by traditional algorithms, such as, semantic location attacks and maximum moving speed attacks, a trajectory privacy-preserving algorithm based on semantic location preservation under road network constraints, called k-CS ( k-Connected Sub-graph) algorithm, was proposed. Firstly, two attack models in road network space were proposed. Secondly, the privacy problem of semantic trajectory was defined as the k-CS anonymity problem, which was then proven NP-hard. Finally, an approximation algorithm was proposed to cluster nodes in the road network to construct anonymity zones, and semantic locations were replaced with the corresponding anonymity zones. Experiments were implemented to compare the proposed algorithm with the classical algorithm, called ( k,δ)-anonymity. The experimental results show that, the k-CS algorithm performs better than ( k,δ)-anonymity algorithm in data utility, query error and runtime. Specifically, k-CS algorithm reduces about 20% in information loss than ( k,δ)-anonymity, and k-CS algorithm deceased about 10% in runtime than ( k,δ)-anonymity algorithm.