This Is AuburnElectronic Theses and Dissertations

Privacy Protected Location Based Services




Bao, Jie

Type of Degree



Computer Science


An increasing number of the mobile devices nowadays embedded with the GPS module (e.g., smart phones, PDAs and RFIDs), which makes the user can facilitated from the location based services. They can ask for the nearby points of interest (POIs) which can be gas stations, restaurants and track the trace of the buses. Example of such services likes "show me the nearest gas station". In order to access location-based services, mobile users have to disclose their exact location information to service providers. However, adversaries could collect the location information for purposes against mobile users' privacy, such as tracking and stalking. The most popular solutions for privacy protection are utilizing the K-anonymity model to blur user's exact location information. By using this principle, the client will not send its exact location information to the service provider, but a blurred region with at least k-1 other peers. As the result, the services provider will not be able to find out the identity of the query issuer, even if they know the exact user distribution in that area. There are two very popular system architectures applying the K-anonymity principle to construct the cloaking region for the privacy preserving spatial queries: the centralized spatial cloaking and the peer to peer spatial cloaking. However, there are some drawbacks and defects for these existing solutions. For example the central server for the first solution will become a single point of failure and performance bottleneck. And for the Peer to Peer solution, there are several other privacy issues such as the distinguishability for the peers. This research work proposes a cache management mechanism for the centralized solution to further improve user privacy protection, saving computational power, and decreasing communication costs. And for the decentralized solution, we propose a CAN (Content Addressable Network) based road network partition and an incremental query processing mechanism to extend the location privacy protection over the road networks and improve the indistinguishability for K-anonymity principle. And a corresponding k nearest neighbors searching algorithm is also proposed to optimize the existing solution.