基于查询概率的假位置选择算法

摘要

位置服务(Location-based Service,LBS)已经成为日常生活的重要组成部分.用户在享受位置服务带来的巨大便利的同时,也面临着巨大的隐私泄露风险.针对传统的位置隐私保护中K-匿名机制没有考虑到攻击者具有背景知识或者边信息的问题,提出了一种改进的假位置选择算法来保护位置隐私.该方法首先对样本空间进行网格划分,并基于历史查询数据计算出每个位置单元的查询概率;再结合历史查询概率为用户寻找(K—1)个假位置,使得这(K-1)个假位置的历史查询概率与用户所在位置的历史查询概率尽量相同,并且使这K个位置尽量分散.实验结果证明了该算法在位置隐私保护方面的有效性.%Location-based service(LBS) has become a vital part in daily life.While enjoying the convenience provided by LBS,users may have high risk of losing privacy.Traditional K-anonymity for location privacy does not consider that adversaries have some problems of background knowledge and side information.Therefore,this paper proposed an improved dummy locations selection algorithm to protect location privacy.Firstly,the space is divided into grids,and historical statistics are utilized to obtain the probability of queries of each grid of space.Then,the dummy locations are selected for users in order that the (K-1) grids has the same query probability as far as possible corresponding with the grid where the real user exists and the K locations are spread as far as possible.A series of experiments on synthetic datasets show that this algorithm is feasible and effective.