Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (8): 2318-2325.DOI: 10.11772/j.issn.1001-9081.2018122585

• Cyber security • Previous Articles     Next Articles

Virtual trajectory filling algorithm for location privacy protection

FU Yu, WANG Hong   

  1. College of Computer Science and Technology, Civil Aviation University of China, Tianjin 300300, China
  • Received:2019-01-02 Revised:2019-04-02 Online:2019-04-11 Published:2019-08-10
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (U1433116, U1633110).


付宇, 王红   

  1. 中国民航大学 计算机科学与技术学院, 天津 300300
  • 通讯作者: 付宇
  • 作者简介:付宇(1973-),男,浙江义乌人,副教授,博士,主要研究方向:网络与信息安全、智能信息处理;王红(1963-),女,重庆人,教授,CCF会员,主要研究方向:大数据挖掘、智能信息处理。
  • 基金资助:

Abstract: In view of the different constraints on the moving objects between road network environment and Euclidean space environment, a virtual trajectory filling algorithm was proposed, which was applicable to both constraints. The interaction between the user and the provider of Location-Based Services (LBS) was taken over by the algorithm, and virtual user trajectory was constructed to confuse and fill the real trajectory, realizing the hiding and protection of the real trajectory. Firstly, the target region was partitioned and the points of convergence were extracted. Then, the trajectory segmentation and virtual trajectory were generated based on the convergence points. Finally, the reasonable distribution of the virtual trajectory was achieved by constructing the timing preset algorithm and the trajectory confusion filling algorithm, which increased the difficulty of associating the trajectory information with a specific target object. Experimental results show that after less than 15 virtual trajectories per user being filled, the probability of the location privacy disclosure of the target object is dropped from 60% to and stabilizes at around 10%, and the trajectory privacy disclosure probability is decreased from 50% to and stabilizes at about 6%, achieving good effect of location privacy protection.

Key words: Location-Based Service (LBS), road network environment, location privacy protection, virtual trajectory, convergence point

摘要: 针对位置隐私保护中路网环境和欧氏空间环境对移动对象不同的约束限制,提出一种适用于这两类不同空间约束特点的虚拟轨迹填充算法。该算法接管了用户与位置服务提供者之间的交互,并构建了虚拟用户轨迹对真实轨迹进行混淆填充,从而实现了真实轨迹的隐藏和保护。首先,对目标区域进行分区和汇聚点提取;随后,以汇聚点为基础进行轨迹分段和虚拟轨迹的生成;最后,通过构建时序预置算法和轨迹混淆填充算法实现了虚拟轨迹的合理分布,增加了将轨迹信息关联到特定目标对象的难度。实验结果表明,所提算法能够在每用户15次以内的填充后将位置隐私披露风险概率从60%下降并稳定在10%左右,轨迹隐私披露概率从50%下降并稳定在6%左右,能达到较好的位置隐私保护的效果。

关键词: 基于位置的服务, 路网环境, 位置隐私保护, 虚拟轨迹, 汇聚点

CLC Number: