P2P模式下基于网格扩增的位置匿名算法

计算机科学 ›› 2014, Vol. 41 ›› Issue (4): 90-94.

P2P模式下基于网格扩增的位置匿名算法

王嘉慧,程久军

同济大学电子与信息工程学院上海201804;同济大学嵌入式系统与服务计算教育部重点实验室上海201804

出版日期:2018-11-14 发布日期:2018-11-14
基金资助:
本文受国家科技支撑计划项目(2012BAH15F03),上海市自然科学基金项目(13ZR1443100),科技部国际合作项目(2013DFM10100),上海市科委计划项目(11JC1412800)资助

Spatial Cloaking Algorithm Based on Grid Expansion in P2P Mode

WANG Jia-hui and CHENG Jiu-jun

Online:2018-11-14 Published:2018-11-14

摘要/Abstract

摘要： 位置k-匿名方法是当前基于位置的服务中隐私保护领域的研究热点。典型的位置匿名算法多采用单一可信的中心匿名服务器对用户位置进行匿名,但中心服务器容易成为性能瓶颈和集中攻击点,而已有P2P模式下的位置匿名算法在安全性上较弱。针对上述问题,提出了一种P2P模式下基于网格扩增的位置匿名算法,其利用网格划分平面,通过不断翻倍扩增网格宽度寻找满足用户隐私需求的匿名区,最终完成对用户位置的匿名。同时算法在运行中能够与邻近节点分享计算所得中间结果,并对其进行缓存。实验表明,与已有算法相比,本算法可显著降低网络带宽的消耗,减少位置匿名耗时,同时能够避免匿名区中心攻击,且抗查询采样攻击的能力得到较大提升。

关键词: 基于位置的服务,位置隐私,k-匿名,P2P

Abstract: Location k-anonymity becomes a research focus in the privacy-preserving field of location-based service recently．Typical spatial cloaking algorithms require a centralized trusted anonymity server which could be the system bottleneck and single point of attacks,while the existing spatial cloaking algorithms in P2P (Peer to Peer) mode suffer from several attack models．A spatial cloaking algorithm based on grid expansion in P2P mode was proposed to solve this problem．It divides the space into grids and computes cloaking region by keeping trying to double the grid’s width until user’s privacy requirement is satisfied．Meanwhile the intermediate result is shared and cached with other peers during the running process of the algorithm．The experimental results show that the proposed algorithm reduces the consumption of network bandwidth and time cost of spatial cloaking．Moreover,it is free from center-of-cloak attack and more resistant to sample query attack in comparison with the existing algorithms.

Key words: Location-based service,Location privacy,k-Anonymity,P2P

王嘉慧,程久军. P2P模式下基于网格扩增的位置匿名算法[J]. 计算机科学, 2014, 41(4): 90-94. https://doi.org/

WANG Jia-hui and CHENG Jiu-jun. Spatial Cloaking Algorithm Based on Grid Expansion in P2P Mode[J]. Computer Science, 2014, 41(4): 90-94. https://doi.org/

参考文献

[1] Hong J I,Landay J A．An architecture for privacy-sensitiveubiquitous computing[C]∥Proceedings of the 2nd international conference on Mobile systems,applications,and services．New York:ACM,2004:177-189
[2] Yiu M L,Jensen C S,Huang X,et al．SpaceTwist Managing the Trade-Offs Among Location Privacy,Query Performance,and Query Accuracy in Mobile Services[C]∥IEEE 24th International Conference on Data Engineering．Cancun:ICDE,2008:366-375
[3] 胡磊,王佳俊,倪巍伟．一种基于坐标和的保护位置隐私近邻查询方法[J]．计算机科学,2012,39(8):173-177
[4] Gruteser M,Grunwald D．Anonymous Usage of Location-based Services through Spatial and Temporal Cloaking[C]∥Procee-dings of the 1st international conference on Mobile systems,applications and services．New York:ACM,2003:31-42
[5] Chow C Y,Mokbel M F,Aref W G．Casper*:Query processing for location services without compromising privacy[J]．ACM Transactions on Database Systems,2009,34(4):24-48
[6] Chow C Y,Mokbel M F．Enabling private continuous queries for revealed user locations[C]∥Proceedings of the 10th international conference on Advances in spatial and temporal databa-ses． Berlin Heidelberg:Springer-Verlag,2007:258-273
[7] Kalnis P,Ghinita G,Mouratidis K,et al．Preventing Location-Based Identity Inference in Anonymous Spatial Queries[J]．IEEE Transactions on Knowledge and Data Engineering,2007,19(12):1719-1733
[8] Gedik B,Liu L．Location Privacy in Mobile Systems:A Personalized Anonymization Model[C]∥Proceedings of the 25th IEEE International Conference on Distributed Computing Systems．Washington:IEEE,2005:620-629
[9] Chow C Y,Mokbel M F,Liu X．A Peer-to-Peer Spatial Cloaking Algorithm for Anonymous Location-based Services[C]∥Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems．New York:ACM,2006:171-178
[10] 黄毅,霍峥,孟小峰．CoPrivacy:一种用户协作无匿名区域的位置隐私保护方法[J]．计算机学报,2011,34(10):1976-1985
[11] 徐建,黄孝喜,郭鸣,等．动态P2P网络中基于匿名链的位置隐私保护[J]．浙江大学学报:工学版,2012,46(4):712-718
[12] Chow C Y,Mokbel M F,Liu X．Spatial Cloaking for Anonymous Location-based Services in Mobile Peer-to-Peer Environment[J]．Geoinformatica,2011,15(2):351-380
[13] Xue M,Kalnis P,Pung H K．Location Diversity:Enhanced Privacy Protection in Location Based Services[C]∥Proceedings of the 4th International Symposium on Location and Context Awareness．Berlin Heidelberg:Springer-Verlag,2009:70-87
[14] Brinkhoff T．A framework for generating network based moving objects[J]．Geoinformatica,2000,6(2):153-180
[15] Ghinita G,Kalnis P,Skiadopoulos S．MobiHide:A Mobilea Peer-to-Peer System for Anonymous Location-Based Queries[C]∥Location Diversity:Enhanced Privacy Protection in Location Based Services．Berlin Heidelberg:Springer-Verlag,2007:221-238

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed