Research On The Location Privacy Protection Algorithm Based On Grid-divided Space

With the popularity of smart mobile devices, location-based services have applied to all walks of life in depth and changed people's production and life style. The premise of the services application is that users must submit their precise locations. Because of the sensitive characteristics of position information itself, the leakage of location information will cause serious privacy issues. Now,location privacy problem has attracted more and more people's attention.Currently, there are many methods to protect location information privacy, such as false location anonymity, anonymous area and space encryption technology. Among them,the approach of anonymous area was widely used because of its high-performance,in which location k-anonymity is used to protect the users' privacy. The anonymous area method has two kinds of types. One type is data dependent Cloak algorithm, such as Centre Cloaking, Nearest Neighbor Cloaking, Hilbert Cloak algorithm and Clique Cloak algorithm; another is space dependent Cloak algorithm such as Four grid algorithm,Interval Cloak algorithm, Casper algorithm and Extended adjacency grid algorithm.Grid-divide Cloak algorithm is one of the extended adjacency grid algorithm. In this method, regional space is divided into lots of grids in the same layer according to certain rules, then user expand space with some strategy, until the generated areas can satisfy user's anonymity requirements. But this algorithm is not suitable in the case that the distribution of users is sparse or users require a higher anonymity.An improved grid location algorithm based on Grid-divide for privacy protection is proposed in this paper, in which grid-divide method is also used and all girds is also in the same layer. The difference between the improved method and the traditional is that the way of the space expansion is from center to around, which can ensure the effectiveness and extension of smaller size expansion. In addition, Amax, the max value of area number, is introduced to limit the final size of the anonymous region; Time delay is used, which can make more users enter the candidate anonymous area and then improve the success rate of the algorithm; The parameter Tmax is introduced to limit the service delay time, so smaller candidate anonymous area can be generated faster.The improved Grid-divide algorithm was realized using C language and was simulated on the data sets which generated by mobile object generator based on network.Experiment results express that the improved algorithm is more effective and faster than the traditional.