Protecting user anonymity in location-based services with fragmented cloaking region

We address user privacy protection in a two-dimensional location-based service (LBS), where a trusted anonymity server called the anonymizer cloaks the queries to the LBS provider from distributed mobile users so that their anonymity can be preserved to a certain extent. Current solutions are mainly designed with k-anonymity in mind, and a major problem of them is the performance degradation in the sparse user scenario. In this paper, to alleviate the problem we propose a novel framework, where the traditional single cloaking region (CR) is split into multiple sub CRs. The framework can be easily applied to existent schemes designed with k-anonymity. To the best of our knowledge, this is the first work to replace a continuous CR with a fragmented one. Experimental results show that our approach increases the quality of service in both normal and sparse user scenarios while retaining the same anonymity level. Particularly, the area of the CR is decreased, resulting in improved accuracy of the candidate results returned from the LBS provider as well as reduced transmission overhead between the LBS provider and the anonymizer.