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

摘要：

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

关键词：位置隐私、网络Voronoi图、道路网络、基于位置服务、移动计算

分类号：TP311.13(计算技术、计算机技术)

资助基金：国家自然科学基金项目61303017；河北省自然科学基金项目 F2014210068；国家级大学生创新创业训练计划项目201410107003；国家留学基金资助出国留学项目201408130042

在线出版日期：2016-03-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共14页

页码：2750-2763