基于k-means++的抗相似性攻击轨迹匿名算法
Trajectory Anonymous Algorithm Based on k-Means++ against Similarity Attack

DOI: 10.12677/CSA.2020.104063, PP. 610-618

Keywords: 轨迹隐私保护，l-多样性，轨迹(k？l？δ) -匿名算法，k-means++
Trajectory Privacy Preservation, l-Diversity, Trajectory (k？l？δ) -Anonymous Algorithm, k-Means++

Full-Text   Cite this paper   Add to My Lib

Abstract:

针对聚类中心的选择问题以及轨迹匿名集中轨迹间的相似性过高而泄露轨迹隐私的问题，提出基于k-means++的抗轨迹相似性攻击的轨迹(k,l,δ)-匿名算法。轨迹预处理的过程中，通过构造同步轨迹来减少信息损失；构建匿名集和时，本文采用k-means++算法来构建匿名集合，并且用(l,δ)-约束来限制轨迹匿名集合间的相似性构建包含k条轨迹的匿名集合。实验结果表明，该算法能够较好地构建匿名集合，能够有效抵制轨迹相似性攻击，相比其它算法减少了轨迹信息的损失，同时增强了轨迹数据可利用性，更好地实现了轨迹隐私保护。
Aiming at the problems of how to choose the center of cluster and trajectory privacy leakage caused by the high similarity between the anonymous centralized trajectories, we propose a trajectory anonymous algorithm to resist trajectory similarity attacks. In the preprocessing process, the algorithm adopts trajectory synchronization to reduce information loss. In clustering process, we use k-means++ algorithm to construct the anonymous collection; to prevent the privacy leakage caused by the high slope similarity of trajectories in the set, at least l trajectories with different slopes are required to satisfy trajectory k-anonymity, and the difference value of trajectory slope in each class is required to be at least σ. Experimental results show that the proposal can effectively resist trajectory similarity attacks, reduce information loss comparing to other trajectory anonymous algorithms, enhance the data of availability, and achieve better trajectory privacy protection.

References

[1]	哈吉德玛. 基于位置服务(LBS)的应用研究[J]. 现代信息科技, 2019, 3(4): 61-62.
[2]	Xiao, Z., Yang, J.J., Huang, M., et al. (2017) QLDS: A Novel Design Scheme for Trajectory Privacy Protection with Utility Guarantee in Partici-patory Sensing. IEEE Transactions on Mobile Computing, 17, 1397-1410. https://doi.org/10.1109/TMC.2017.2768360
[3]	He, X., Jin, R. and Dai, H. (2018) Leveraging Spatial Diversity for Privacy-Aware Location Based Services in Mobile Networks. IEEE Transactions on Information Forensics & Se-curity, 13, 1524-1534. https://doi.org/10.1109/TIFS.2018.2797023
[4]	Xiao, P., Chen, W., Sun, Y., et al. (2017) Continuous Queries Privacy Protection Algorithm Based on Spatial-Temporal Similarity Over Road Networks. Journal of Computer Re-search & Development, 54, 2092-2101.
[5]	张学军, 桂小林, 伍忠东. 位置服务隐私保护研究综述[J]. 软件学报, 2015, 26(9): 2373-2395.
[6]	魏兴民, 杜鹏懿. 基于位置服务的隐私保护综述[J]. 现代信息科技, 2019(8): 154-157.
[7]	Machanavajjhala, A., Kifer, D., Gehrke, J., et al. (2006) L-Diversity: Privacy beyond Kanonymity. ACM Transactions on Knowledge Discovery from Data, 1, 3. https://doi.org/10.1145/1217299.1217302
[8]	Gao, S., Ma, J.F., Sun, C., et al. (2014) Balancing Trajectory Privacy and Data Utility Using a Personalized Anonymization Model. Journal of Network and Computer Applications, 38, 125-134. https://doi.org/10.1016/j.jnca.2013.03.010
[9]	杨静, 张冰, 张健沛, 等. 基于图划分的个性化轨迹隐私保护方法[J]. 通信学报, 2015(3): 1-11.
[10]	Abul, O., Bonchi, F. and Nanni, M. (2008) Never Walk alone: Uncertainty for Anonymity in Moving Objects Databases. In: Proceedings of the International Conference on Data Engineering, 376-385. https://doi.org/10.1109/ICDE.2008.4497446
[11]	Cai, H.-F., Yang, H.-X. and Wang, S. (2014) A Cluster-ing-Based Privacy-Pre-Serving Method for Uncertain Trajectory Data. 2014 IEEE 13th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom), Beijing, China, 49-62. https://doi.org/10.1109/TrustCom.2014.5
[12]	Dai, J. and Liang, H. (2015) A Method for the Trajectory Privacy Protection Based on the Segmented Fake Trajectory under Road Networks.
[13]	吴英杰, 唐庆明, 倪巍伟. 基于聚类杂交的隐私保护轨迹数据发布算法[J]. 计算机研究与发展, 2013, 50(3): 578-593.
[14]	Huo, Z., Huang, Y. and Meng, X.F. (2011) History Trajectory Privacy-Preserving through Graph Partition. In: Proceedings of the 1st Interna-tional Workshop on Mobile Location-Based Service, ACM Press, New York, 71-78. https://doi.org/10.1145/2025876.2025891
[15]	Agarwal, P.K., Avraham, R.B., Kaplan, H., et al. (2014) Compu-ting the Discrete Fréchet Distance in Subquadratic Time. SIAM Journal on Computing, 43, 429-449. https://doi.org/10.1137/130920526
[16]	Brinkhoff, T. (2003) Generating Traffic Data. IEEE Data Engineering Bulletin, 26, 19-25.

Full-Text