道路网络上基于网络Voronoi图的隐私保护算法

基于位置服务(location-based services, LBSs)中的不可信服务提供商不断收集用户个人数据，为用户隐私带来威胁.因此，LBSs中的位置隐私保护研究已在学术界和工业界受到广泛关注.现有道路网络中的位置隐私保护方法大多是基于深度或广度图遍历的算法，需重复扫描道路网络的全局拓扑信息，匿名效率较低.针对这一问题，利用网络Voronoi图(network Voronoi diagram, NVD)将道路网络事先划分为独立的网络Voronoi单元，将传统方法中的多次遍历全局道路网络转化为了访问网络Voronoi单元中的局部路网信息.根据网络Voronoi单元覆盖的移动用户数和路段数，将网络Voronoi单元分为了不安全单元、安全-中单元和安全-大单元3类，提出了适应不同类型网络Voronoi单元特点的高效位置匿名算法.最后，通过在真实数据集上进行大量实验，验证了提出算法在仅比传统算法多牺牲0.01%的查询代价的前提下，保证了100%的匿名成功率和0.34ms的高效匿名时间，在隐私保护强度和算法性能方面取得了较好的平衡.

A Privacy Protection Algorithm Based on Network Voronoi Graph over Road Networks

With advances in wireless communication and mobile positioning technologies, location-based services (LBSs) have seen wide-spread adoption. The academia and industry have pay attention to location privacy preserving in LBSs for about ten years. Most existing location cloaking algorithms over road networks are based on DFS-based or BFS-based graph traversal algorithms. However, the main drawback of these approaches is the repetitive global road network traversal, which results in the low efficiency and high communication cost. In order to resolve the problem, we propose a network Voronoi-based location anonymization algorithm NVLA on road networks. Under the help of network Voronoi diagram (NVD), the road network is divided into several network Voronoi cells offline. Then, we reduce the problem of anonymization over the global road network into finding cloaking sets in local network Voronoi cells (NVC). Next, according to the number of road segments and the number of users in a cell, network Voronoi cells are classified to unsafe, safe-medium and safe-large cells. Finally, according to the features of the different network Voronoi cells, different cloaking algorithms are proposed. We design and conduct a series of experiments, and the experimental results validate the efficiency and effectiveness of the proposed algorithm. The average cloaking time is only 0.4 ms and the cloaking success rate is about 100%. On the other hand, only 0.01% of the query cost is sacrificed.