基于轨迹形状多样性的隐私保护算法

doi:10.11772/j.issn.1001-9081.2016.06.1544

计算机应用 ›› 2016, Vol. 36 ›› Issue (6): 1544-1551.DOI: 10.11772/j.issn.1001-9081.2016.06.1544

基于轨迹形状多样性的隐私保护算法

孙丹丹^1,2, 罗永龙^1,2, 范国婷^1,2, 郭良敏^1,2, 郑孝遥^1,2

1. 安徽师范大学计算机科学与技术系, 安徽芜湖 241003;
2. 安徽师范大学网络与信息安全工程技术研究中心, 安徽芜湖 241003

收稿日期:2015-11-16 修回日期:2016-01-13 出版日期:2016-06-10 发布日期:2016-06-08
通讯作者: 罗永龙
作者简介:孙丹丹(1990-),女,安徽淮南人,硕士研究生,主要研究方向:信息安全、隐私保护;罗永龙(1972-),男,安徽太湖人,教授,博士生导师,博士,CCF会员,主要研究方向:信息安全、隐私保护;范国婷(1989-),女,安徽阜阳人,硕士研究生,主要研究方向:信息安全、隐私保护;郭良敏(1980-),女,安徽肥东人,副教授,博士,CCF会员,主要研究方向:信息安全、分布式计算;郑孝遥(1981-),男,安徽芜湖人,讲师,博士研究生,CCF会员,主要研究方向:个性化推荐、信息安全。
基金资助:
国家自然科学基金资助项目(61370050);安徽省自然科学基金资助项目(1508085QF133);安徽省高校省级自然科学研究重点项目(KJ2014A084)。

Privacy protection algorithm based on trajectory shape diversity

SUN Dandan^1,2, LUO Yonglong^1,2, FAN Guoting^1,2, GUO Liangmin^1,2, ZHENG Xiaoyao^1,2

1. Department of Computer Science and Technology, Anhui Normal University, Wuhu Anhui 241003, China;
2. Engineering Technology Research Center of Network and Information Security, Anhui Normal University, Wuhu Anhui 241003, China

Received:2015-11-16 Revised:2016-01-13 Online:2016-06-10 Published:2016-06-08
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61370050), the Natural Science Foundation of Anhui Province (1508085QF133), the Research Program of Anhui Province Education Department (KJ2014A084).

摘要/Abstract

摘要： 针对匿名集内轨迹间的高度相似性而导致的轨迹隐私泄露问题,提出基于轨迹形状多样性的隐私保护算法。该算法通过轨迹同步化处理的方式改进轨迹数据的预处理过程,以减少信息损失;并借鉴l-多样性思想,在贪婪聚类时选择l条具有形状多样性的轨迹作为匿名集成员,以防止集合内成员轨迹的形状相似性过高而导致轨迹形状相似性攻击。理论分析及实验结果均表明,该算法能够在保证轨迹k-匿名的同时满足l-多样性,算法运行时间较小,且减少了轨迹信息损失,增强了轨迹数据的可用性,更好地实现了轨迹隐私保护,可有效应用到隐私保护轨迹数据发布中。

关键词: 轨迹数据发布, 隐私保护, 轨迹匿名, k-匿名, l-多样性

Abstract: The high similarity between trajectories in anonymity set may lead to the trajectory privacy leak. In order to solve the problem, a trajectory privacy preserving algorithm based on trajectory shape diversity was proposed. The exiting pre-processing method was improved to reduce the loss of information through trajectory synchronization processing. And by l-diversity, the trajectories with shape diversity were chosen as the members of the anonymity set when greedy clustering. Too high shape similarity between member trajectories of the set was prevented to avoid the attack of trajectory shape similarity. The theoretical analysis and experimental results show that, the proposed algorithm can realize k-anonymity of trajectory and l-diversity concurrently, reduce the running time and trajectory information loss, increase the trajectory data availability and realize better privacy protection. The proposed algorithm can be effectively applied to the privacy-preserving trajectory data publishing.

Key words: trajectory data publishing, privacy protection, trajectory anonymity, k-anonymity, l-diversity

中图分类号:

TP309.2

孙丹丹, 罗永龙, 范国婷, 郭良敏, 郑孝遥. 基于轨迹形状多样性的隐私保护算法[J]. 计算机应用, 2016, 36(6): 1544-1551.

SUN Dandan, LUO Yonglong, FAN Guoting, GUO Liangmin, ZHENG Xiaoyao. Privacy protection algorithm based on trajectory shape diversity[J]. Journal of Computer Applications, 2016, 36(6): 1544-1551.

参考文献

[1] KRUMM J. Inference attacks on location tracks[C]//Proceedings of the 5th International Conference on Pervasive Computing, LNCS 4480. Berlin: Springer, 2007: 127-143.
[2] SWEENEY L. k-anonymity: a model for protecting privacy[J]. International Journal of Uncertainty Fuzziness and Knowledge-Based Systems, 2012, 10(5): 557-570.
[3] GRUTESER M, GRUNWALD D. Anonymous usage of location-based services through spatial and temporal cloaking[C]//Proceedings of the 1st International Conference on Mobile Systems, Applications and Services. New York: ACM, 2003: 31-42.
[4] 霍峥,孟小峰.轨迹隐私保护技术研究[J].计算机学报,2011,34(10):1820-1830. (HUO Z, MENG X F. A survey of trajectory privacy-preserving techniques[J]. Chinese Journal of Computers, 2011, 34(10): 1820-1830.)
[5] MACHANAVAJJHALA A, KIFER D, GEHRKE J, et al. l-diversity: privacy beyond k-anonymity[J]. ACM Transactions on Knowledge Discovery from Data, 2007, 1(1): Article No. 3.
[6] LUPER D, CAMERON D, MILLER J, et al. Spatial and temporal target association through semantic analysis and GPS data mining[C]//IKE 2007: Proceedings of the 2007 International Conference on Information & Knowledge Engineering. Las Vegas:[s.n.]. 2007: 251-257.
[7] TERROVITIS M, MAMOULIS N. Privacy preservation in the publication of trajectories[C]//MDM'08: Proceedings of the 2008 IEEE 9th International Conference on Mobile Data Management. Washington, DC: IEEE Computer Society, 2008: 65-72.
[8] GRUTESER M, LIU X. Protecting privacy, in continuous location-tracking applications[J]. IEEE Security & Privacy Magazine, 2004, 2(2): 28-34.
[9] NERGIZ M E, ATZORI M, SAYGIN Y. Towards trajectory anonymization: a generalization-based approach[C]//Proceedings of the SIGSPATIAL ACM GIS 2008 International Workshop on Security and Privacy in GIS and LBS. New York: ACM, 2008: 52-61.
[10] NERGIZ M E, ATZORI M, SAYGIN Y. Towards trajectory anonymization: a generalization-based approach[C]//SPRINGL 2008: Proceedings of the 2008 SIGSPATIAL ACM GIS 2008 International Workshop on Security and Privacy in GIS and LBS. New York: ACM, 2008: 52-61.
[11] ABUL O, BONCHI F, NANNI M. Never walk alone: uncertainty for anonymity in moving objects databases[C]//ICDE 2008: Proceedings of the 2008 IEEE 24th International Conference on Data Engineering. Piscataway, NJ: IEEE, 2008: 376-385.
[12] ABUL O, BONCHI F, NANNI M. Anonymization of moving objects databases by clustering and perturbation[J]. Information Systems, 2010, 35(8): 884-910.
[13] CHEN L, ÖZSU M T, ORIA V. Robust and fast similarity search for moving object trajectories[C]//Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2005: 491-502.
[14] YAROVOY R, BONCHI F, LAKSHMANAN L V S, et al. Anonymizing moving objects: how to hide a MOB in a crowd?[C]//Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology. New York: ACM, 2009: 72-83.
[15] ANDRIENKO G, ANDRIENKO N, GIANNOTTI F, et al. Movement data anonymity through generalization[C]//Proceedings of the 2nd SIGSPATIAL ACM GIS 2009 International Workshop on Security and Privacy in GIS and LBS. New York: ACM, 2009: 27-31.
[16] 王超,杨静,张健沛.基于轨迹位置形状相似性的隐私保护算法[J].通信学报,2015,36(2):144-157. (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.)
[17] HUO Z, HUANG Y, MENG X F. History trajectory privacy-preserving through graph partition[C]//Proceedings of the 1st International Workshop on Mobile Location-Based Service. New York: ACM, 2011: 71-78.
[18] GAO S, MA J, SUN C, et al. Balancing trajectory privacy and data utility using a personalized anonymization model[J]. Journal of Network & Computer Applications, 2014, 38(1): 125-134.
[19] 杨静,张冰,张健沛,等.基于图划分的个性化轨迹隐私保护方法[J].通信学报,2015,36(3):1-11.(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.)
[20] HUO Z, Meng X F, HU H B, et al. You can walk alone: trajectory privacy-preserving through significant stays protection[C]//Proceedings of the 17th International Conference on Database Systems for Advanced Applications, LNCS 7238. Berlin: Springer, 2012:351-366.
[21] DOMINGO-FERRER J, TRUJILLO-RASUA R. Microaggregation- and permutation-based anonymization of movement data[J]. Information Sciences, 2012, 208: 55-80.
[22] 吴英杰,唐庆明,倪巍伟,等.基于聚类杂交的隐私保护轨迹数据发布算法[J].计算机研究与发展,2013,50(3):578-593.(WU Y J, TANG Q M, NI W W, et al. A clustering hybrid based algorithm for privacy preserving trajectory data publishing[J]. Journal of Computer Research and Development, 2013, 50(3): 578-593.)
[23] 王波,杨静.一种基于逆聚类的个性化隐私匿名方法[J].电子学报,2012,40(5):883-890.(WANG B, YANG J. A personalized privacy anonymous method based on inverse clustering[J]. Acta Electronica Sinica, 2012, 40(5): 883-890.)
[24] 郭旭东,吴英杰,杨文进,等.隐私保护轨迹数据发布的l-差异性算法[J].计算机工程与应用,2015,51(2):125-130.(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.)
[25] 袁冠,夏士雄,张磊,等.基于结构相似度的轨迹聚类算法[J].通信学报,2011,32(9):103-110.(YUAN G, XIA S X, ZHANG L, et al. Trajectory clustering algorithm based on structural similarity[J]. Journal on Communications, 2011, 32(9): 103-110.)
[26] CHOW C Y, MOKBEL M F. Trajectory privacy in location-based services and data publication[J]. ACM SIGKDD Explorations Newsletter, 2011, 13(1): 19-29.
[27] XIAO X, YI K, TAO Y. The hardness and approximation algorithms for l-diversity[C]//Proceedings of the 13th International Conference on Extending Database Technology. New York: ACM, 2010: 135-146.
[28] BRINKHOFF T. A framework for generating network-based moving objects[J]. GeoInformatica, 2002, 6(2): 153-180.

基于轨迹形状多样性的隐私保护算法

Privacy protection algorithm based on trajectory shape diversity

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	李卓, 宋子晖, 沈鑫, 陈昕. 边缘计算支持下的移动群智感知本地差分隐私保护机制[J]. 计算机应用, 2021, 41(9): 2678-2686.
[2]	吴恺凡, 殷新春. 基于随机运算符的轻量级匿名射频识别系统双向认证协议[J]. 计算机应用, 2021, 41(6): 1621-1630.
[3]	秦静, 安雯, 季长清, 汪祖民. 无线体域网隐私保护机制研究综述[J]. 计算机应用, 2021, 41(4): 970-975.
[4]	刘向宇, 夏国平, 夏秀峰, 宗传玉, 朱睿, 李佳佳. 个性化时空数据隐私保护[J]. 计算机应用, 2021, 41(3): 643-650.
[5]	张恩, 李会敏, 常键. 可验证的隐私保护k-means聚类方案[J]. 计算机应用, 2021, 41(2): 413-421.
[6]	陈锦宇, 刘兆伟. 基于改进投票证明共识协议的车联网系统[J]. 计算机应用, 2021, 41(1): 170-176.
[7]	马敏耀, 刘卓, 徐艺, 吴恋. 隐私保护整数区间位置关系判定问题[J]. 计算机应用, 2020, 40(9): 2657-2664.
[8]	吕佳玉, 竺智荣, 姚志强. 云计算环境下的双通道数据动态加密策略[J]. 计算机应用, 2020, 40(8): 2268-2273.
[9]	马敏耀, 吴恋, 刘卓, 徐艺. 隐私保护整数点和区间关系判定问题[J]. 计算机应用, 2020, 40(7): 1983-1988.
[10]	龙洋洋, 陈玉玲, 辛阳, 豆慧. 基于联盟区块链的安全能源交易方案[J]. 计算机应用, 2020, 40(6): 1668-1673.
[11]	杨洋, 王汝传. 增强现实中基于位置安全性的LBS位置隐私保护方法[J]. 计算机应用, 2020, 40(5): 1364-1368.
[12]	拜亚萌, 满君丰, 张宏. 基于区块链的电子健康记录安全存储模型[J]. 计算机应用, 2020, 40(4): 961-965.
[13]	罗惠雯, 龙士工. 基于用户感兴趣区域的地理不可区分性的位置扰动算法[J]. 计算机应用, 2020, 40(3): 760-764.
[14]	张梅舒, 徐雅斌. 多维数值型敏感属性数据的个性化隐私保护方法[J]. 计算机应用, 2020, 40(2): 491-496.
[15]	刘向宇, 陈金梅, 夏秀峰, Manish Singh, 宗传玉, 朱睿. 防止暴露位置攻击的轨迹隐私保护[J]. 计算机应用, 2020, 40(2): 479-485.