Abstract:

The use of location-based service brings convenience to people’s daily lives, but it also raises concerns about users’ location privacy.In the k-nearest neighbor query problem, constructing K-anonymizing spatial regions is a method used to protects users’ location privacy, but it results in a large waste of communication overhead.The SpaceTwist scheme is an alternative method that uses an anchor point instead of the real location to complete the k-nearest neighbor query,which is simple to implement and has less waste of communication overhead.However,it cannot guarantee K-anonymous security, and the specific selection method of the anchor point is not provided.To address these shortcomings in SpaceTwist, some schemes calculate the user’s K-anonymity group by introducing a trusted anonymous server or using the way of user collaboration, and then enhance the end condition of the query algorithm to achieve K-anonymity security.Other schemes propose the anchor point optimization method based on the approximate distribution of interest points, which can further reduce the average communication overhead.A lightweight K-anonymity incremental nearest neighbor (LKINN) location privacy protection algorithm was proposed to improve SpaceTwist.LKINN used convex hull mathematical tool to calculate the key points of K-anonymity group, and proposed an anchor selection method based on it, achieving K-anonymity security with low computational and communication costs.LKINN was based on a hybrid location privacy protection architecture, making only semi-trusted security assumptions for all members of the system, which had lax security assumptions compared to some existing research schemes.Simulation results show that LKINN can prevent semi-trusted users from stealing the location privacy of normal users and has smaller query response time and communication overhead compare to some existing schemes.

Key words: location-based service, location privacy preservation, K-anonymity, convex hull, anchor