计算机科学 ›› 2019, Vol. 46 ›› Issue (1): 190-195.doi: 10.11896/j.issn.1002-137X.2019.01.029

• 信息安全 • 上一篇    下一篇

基于轨迹多特性的隐私保护算法

许华杰1,2, 吴青华1, 胡小明3   

  1. (广西大学计算机与电子信息学院 南宁530004)1
    (广西多媒体通信与网络技术重点实验室(广西大学) 南宁530004)2
    (上海第二工业大学计算机与信息工程学院 上海201209)3
  • 收稿日期:2017-12-28 出版日期:2019-01-15 发布日期:2019-02-25
  • 作者简介:许华杰(1974-),男,博士,副教授,CCF高级会员,主要研究方向为无线网络、网络安全、智能算法,E-mail:hjxu2009@163.com(通信作者);吴青华(1992-),女,硕士生,主要研究方向为信息安全;胡小明(1978-),女,博士,副教授,主要研究方向为密码学、信息安全。
  • 基金资助:
    广西自然科学基金项目(2014GXNSFAA118382),崇左市科技计划项目(崇科FB2018001),广西科技计划项目(2017AB15008),上海市教育委员会科研创新项目(14ZZ167),国家自然科学基金项目(71463003)资助

Privacy Protection Algorithm Based on Multi-characteristics of Trajectory

XU Hua-jie1,2, WU Qing-hua1, HU Xiao-ming3   

  1. (School of Computer and Electronic Information,Guangxi University,Nanning 530004,China)1
    (Guangxi Key Laboratory of Multimedia Communications and Network Technology,Guangxi University,Nanning 530004,China)2
    (School of Computer and Information Engineering,Shanghai Second Polytechnic University,Shanghai 201209,China)3
  • Received:2017-12-28 Online:2019-01-15 Published:2019-02-25

摘要: 现有基于聚类的轨迹隐私保护算法在衡量轨迹间的相似性时大多以空间特征为标准,忽略了轨迹蕴含的其他方面的特性对轨迹相似性的影响。针对这一情况可能导致的匿名后数据可用性较低的问题,提出了一种基于轨迹多特性的隐私保护算法。该算法考虑了轨迹数据的不确定性,综合方向、速度、时间和空间4个特性的差异作为轨迹相似性度量的依据,以提高轨迹聚类过程中同一聚类集合中轨迹之间的相似度;在此基础上,通过空间平移的方式实现同一聚类集合中轨迹的k-匿名。实验结果表明,与经典隐私保护算法相比,在满足一定隐私保护需求的前提下,采用所提算法实施隐私保护之后的轨迹数据整体具有较高的数据可用性。

关键词: 轨迹隐私保护, 隐私保护度, 轨迹聚类, 不确定性

Abstract: Most of existing trajectory privacy protection algorithms based on trajectory clustering use spatial features as the standard when measuring the similarity between trajectories,ignoring the influence of other temporal and spatial characteristics of trajectories on trajectory similarity.In view of the fact that this situation may lead to the problem oflow availability of anonymous data,a protection algorithm based on integrated spatiotemporal characteristics of trajectory was proposed.The proposed algorithm combines the uncertainty of trajectory data,and uses the difference of 4 aspects of direction,speed,time and space to measure similarity between trajectories,in order to improve the similarity between the trajectories in the same cluster set.And then the trajectories of the same clustering set are spatially shifted to achieve the k-anonymization of the trajectories in the same clustering set.The experimental results show that compared with the classical privacy protection algorithm,the trajectory data protected by proposed algorithm as a whole has higherdata availability under certain privacy protection requirements.

Key words: Trajectory privacy protection, Degree of privacy protection, Trajectory clustering, Uncertainty

中图分类号: 

  • TP391
[1]HUO Z,MENG X F.A Survey of Trajectory Privacy Preserving Techniques [J].Chinese Journal of Computers,2011,34(10):1820-1830.(in Chinese)<br /> 霍峥,孟小峰.轨迹隐私保护技术研究[J].计算机学报,2011,34(10):1820-1830.<br /> [2]LEI K Y,LI X H,LIU H,et al.Dummy Trajectory Privacy Protection Scheme for Trajectory Publishing based on the Spatiotemporal Correlation [J].Journal on Communications,2016,37(12):156-164.(in Chinese)<br /> 雷凯跃,李兴华,刘海,等.轨迹发布中基于时空关联性的假轨迹隐私保护方案[J].通信学报,2016,37(12):156-164.<br /> [3] XU T,CAI Y.Exploring Historical Location Data for Anonymity Preservation in Location-Based Services[C]//Proceedings of IEEE Conference on Computer Communications.New York:IEEE Press,2008:547-555.<br /> [4]HWANG R H,HSUEH Y L,CHUNG H W.A Novel Time-Obfuscated Algorithm for Trajectory Privacy Protection [J].IEEE Transactions on Services Computing,2014,7(2):126-139.<br /> [5]ZHAO J,ZHANG Y,LI X H,et al.A Trajectory Privacy Protection Approach via Trajectory Frequency Suppression [J].Chinese Journal of Computers,2014,37(10):2096-2106.(in Chinese)<br /> 赵婧,张渊,李兴华,等.基于轨迹频率抑制的轨迹隐私保护方法[J].计算机学报,2014,37(10):2096-2106.<br /> [6]NERGIZ M E,ATZORI M,SAYGIN Y,et al.Towards Trajectory Anonymization:A Generalization-based Approach [J].Transactions on Data Privacy,2009,2(1):47-75.<br /> [7]YANG J,ZHANG B,ZHANG J P,et al.Personalized Trajectory Privacy Preserving Method based on Graph Partition[J].Journal on Communications,2015,36(3):1-11.(in Chinese)<br /> 杨静,张冰,张健沛,等.基于图划分的个性化轨迹隐私保护方法[J].通信学报,2015,36(3):1-11.<br /> [8] NERGIZ M E,ATZORI M,SAYGIN Y.Towards Trajectory Anonymization:A Generalization-based Approach[C]//Proceedings of ACM SIGSPATIAL International Workshop on Security and Privacy in GIS and LBS.California:ACM,2008:52-61.<br /> [9]DOMINGO F J,SRAMKA M,TRUJILLO-RASUA R.Privacy-preserving Publication of Trajectories Using Microaggregation[C]//Proceedings of ACM SIGSPATIAL International Workshop on Security and Privacy in GIS and LBS.San Jose:ACM,2010:26-33.<br /> [10]DOMINGO F J,SRAMKA M,TRUJILLO-RASUA R.Microaggregation and Permutation-based Anonymization of Movement Data[J].Information Sciences,2012,208(21):55-80.<br /> [11]ABUL O,BONCHI F,NANNI M.Never Walk Alone:Uncertainty for Anonymity in Moving Objects Databases[C]//Proceedings of the 24th IEEE International Conference on Data Engineering.Cancun:IEEE,2008:376-385.<br /> [12]ABUL O,BONCHI F,NANNI M.Anonymization of Moving Objects Databases by Clustering and Perturbation [J].Information Systems,2010,35(8):884-910.<br /> [13]WANG C,YANG J,ZHANG J P.Privacy Preserving Algorithm based on Trajectory Location and Shape Similarity [J].Journal on Communications,2015,36(2):144-157.(in Chinese)<br /> 王超,杨静,张健沛.基于轨迹位置形状相似性的隐私保护算法[J].通信学报,2015,36(2):144-157.<br /> [14]GUO X D,WU Y J,YANG W J,et al.L-diversity Algorithm for Privacy Preserving Trajectory Data Publishing [J].Computer Engineering and Applications,2015,51(2):125-130.(in Chinese)<br /> 郭旭东,吴英杰,杨文进,等.隐私保护轨迹数据发布的l-差异性算法[J].计算机工程与应用,2015,51(2):125-130.<br /> [15]SHI L K,ZHANG Y R,ZHANG X.Trajectory Data Clustering Algorithm based on Spatio-temporal Pattern[J].Journal of Computer Applications,2017,37(3):854-859.(in Chinese)<br /> 石陆魁,张延茹,张欣.基于时空模式的轨迹数据聚类算法[J].计算机应用,2017,37(3):854-859.
[1] 杨洁, 王国胤, 张清华, 冯林. 层次粒结构下粗糙模糊集的不确定性度量[J]. 计算机科学, 2019, 46(1): 45-50.
[2] 郑宏亮, 侯雪辉, 宋笑迎, 庞阔, 邹丽. 基于犹豫模糊可信度的知识推理[J]. 计算机科学, 2019, 46(1): 131-137.
[3] 汪琳娜, 杨新, 杨习贝. 监督邻域粗糙集[J]. 计算机科学, 2018, 45(8): 186-190.
[4] 夏扬波, 杨文忠, 张振宇, 王庆鹏, 石研. 一种移动无线传感器网络的节点位置预测方法[J]. 计算机科学, 2018, 45(8): 113-118.
[5] 毛莺池,陈杨. 不确定性车辆路口的轨迹预测[J]. 计算机科学, 2018, 45(3): 235-240.
[6] 魏方圆,黄德才. 基于区间数的多维不确定性数据UID-DBSCAN聚类算法[J]. 计算机科学, 2017, 44(Z11): 442-447.
[7] 赵凡,魏玲. D型概率决策形式背景下的规则获取[J]. 计算机科学, 2017, 44(8): 274-279.
[8] 徐俊洁,陈荣. 基于故障关联的多故障概率诊断方法[J]. 计算机科学, 2017, 44(4): 124-130.
[9] 刘德浩,王倩. 一种具有相依关系的二维云推理方法及其在预测中的应用[J]. 计算机科学, 2016, 43(Z6): 99-102.
[10] 刘云恒,刘耀宗,张宏. 一种不确定RFID数据流清洗策略[J]. 计算机科学, 2016, 43(Z11): 482-485.
[11] 王骏,黄德才. 基于联系数的位置不确定性数据UCNK-Means聚类算法[J]. 计算机科学, 2016, 43(Z11): 436-442.
[12] 陈晖,马亚平. 面向不确定性知识表示的描述逻辑SROIQ(D)不确定性扩展[J]. 计算机科学, 2016, 43(Z11): 88-92, 107.
[13] 张晓君,林颖,周昌乐. 智能主体的等级BDI(信念、愿望和意图)模型[J]. 计算机科学, 2016, 43(7): 35-40.
[14] 范菁,阮体洪,吴佳敏,董天阳. 基于二次谱聚类和HMM-RF混合模型的车辆行为识别方法研究[J]. 计算机科学, 2016, 43(5): 288-293.
[15] 程恺,陈刚,张品,尹成祥. 作战计划生成方法研究现状与展望[J]. 计算机科学, 2016, 43(12): 8-12, 23.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 编辑部. 新网站开通,欢迎大家订阅![J]. 计算机科学, 2018, 1(1): 1 .
[2] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75, 88 .
[3] 夏庆勋,庄毅. 一种基于局部性原理的远程验证机制[J]. 计算机科学, 2018, 45(4): 148 -151, 162 .
[4] 厉柏伸,李领治,孙涌,朱艳琴. 基于伪梯度提升决策树的内网防御算法[J]. 计算机科学, 2018, 45(4): 157 -162 .
[5] 王欢,张云峰,张艳. 一种基于CFDs规则的修复序列快速判定方法[J]. 计算机科学, 2018, 45(3): 311 -316 .
[6] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[7] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[8] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[9] 刘琴. 计算机取证过程中基于约束的数据质量问题研究[J]. 计算机科学, 2018, 45(4): 169 -172 .
[10] 钟菲,杨斌. 基于主成分分析网络的车牌检测方法[J]. 计算机科学, 2018, 45(3): 268 -273 .