一种保护隐私的LBS近邻兴趣点低通信查询方法

针对利用传统匿名框查询兴趣点返回无用结果过多带来的通信量增大问题,提出结合兴趣点分布的匿名框构造方法.首先,LBS服务器构造以所有兴趣点位置为生成元的Voronoi图,该图将全局地图划分成能够表示用户与兴趣点距离远近的划分单元;然后,利用四叉树将整个Voronoi图组织成层次式树型结构,树型结构的叶子节点代表最小的网格单元,每个网格包含覆盖若干个兴趣点;最后,根据用户提供的假位置信息,返回包含用户位置的子树网格单元信息,用户根据网格单元内的兴趣点Voronoi图划分单元可以获取周围兴趣点分布情况,从而构造包含目标兴趣点在内的查询匿名框,达到保护用户位置隐私、查询内容隐私的目标,同时,有目的的兴趣点查询避免了过多无用兴趣点查询信息带来的通信量增大问题.性能分析及实验表明,提出的方法能够增大攻击者对用户隐私信息的不确定性,并具有较低的通信量.

A Privacy-preserving Research of Reducing Communication Cost for Nearest Neighbor PoI Query in LBS

Querying with traditional cloaking region brought too much communication cost due to the returned useless points of interest (PoI), a new cloaking region constructing method was proposed. Firstly, LBS server divided the whole map into cells according to PoIs' locations with Voronoi partition, then the Voronoi partition was organized with quadtree into a hierarchical structure, the leaf nodes of the quadtree represented minimum grid cells, each grid cell contained several PoIs; Finally, LBS server sent the subtree to a user according to the user's fake location, the user got the PoIs distribution around him and constructed the cloaking region according to the distribution. The method protected the user's location and query privacy, and the hormic PoI query decreased the communication cost of the useless PoIs. Performance analysis and experiments show that this method increases the uncertainty of users' private information to attackers, and its communication cost is lower.