基于Voronoi图预划分的LBS位置隐私保护方法

doi:10.11959/j.issn.1000-436x.2015109

摘要/Abstract

摘要：

为了解决服务器面临大量用户请求时匿名效率下降的问题，分别提出适用于静态用户和动态用户的协作匿名方法。首先基于Voronoi图划分全局区域，再由中心服务器组织本区域内用户实现协作匿名，由于服务器无需为每个用户单独构造匿名区，降低了服务端的负担；针对查询过程中用户提供真实位置信息带来位置隐私泄露的问题，提出了逆向增量近邻查询算法。用户以固定锚点代替真实位置，向位置服务器逐步获取兴趣点候选集并计算出想要的结果，避免位置隐私直接泄漏的同时获取精准查询结果。该算法同时解决了锚点与用户过近而带来的位置隐私被推断问题。实验表明本方法在有效保护用户位置隐私的同时，具有良好的工作效率。

关键词: 位置隐私, 协作匿名, 锚点, 逆向增量查询

Abstract:

In view of low efficiency when the anonymous server faces a large number of users,a cooperative anonymous method is proposed for static and dynamic users respectively.Based on the Voronoi division of the global area,a central server organizes the users in its region to achieve cooperative anonymity,the server needn't construct anonymous region alone for each user,and the burden of the server is reduced.In view of providing actual location when users query from a LBS server,a decrease nearest neighbor query algorithm is proposed.A user's actual location is replaced with a stationary anchor location and gets the points of interest candidate set from the LBS server gradually.By running the algorithm,pre-cise results can be got and avoiding exposure to a user's location privacy.The algorithm can also help to reduce the possi-bility of location inference when the anchor chooses closely to the user.Experiments show that our method can guarantee the user's location privacy,and provide a good working efficiency.

Key words: location privacy, cooperative anonymity, anchor, decrease nearest neighbor query

马春光,周长利,杨松涛,赵蕴龙. 基于Voronoi图预划分的LBS位置隐私保护方法[J]. 通信学报, 2015, 36(5): 1-12.

AChun-guang M,HOUChang-li Z,ANGSong-tao Y,HAOYun-long Z. Location privacy-preserving method in LBS based on Voronoi division[J]. Journal on Communications, 2015, 36(5): 1-12.

图/表 16

图1

图2

图3

图4

图5

图6

图7

表1

图8

图9

图10

图11

图12

图13

图14

图15

参考文献 21

[1]	CHEEMA M A , ZHANG W , LIN X , et al. Efficiently processing snapshot and continuous reverse k nearest neighbors queries[J]. The VLDB Journal, 2012,21(5): 703-728.
[2]	WU D , WANG X , SUN L , et al. Identity privacy-based reliable routing method in VANETs[J]. Peer-to-Peer Networking and Applications, 2014,7(3): 285-294.
[3]	薛姣，刘向宇，杨晓春，王斌等．一种面向公路网络的位置隐私保护方法[J]．计算机学报， 2011,34(5):865-878. XUE J , LIU X Y , YANG X C , et al. A location privacy preserving ap-proach on road network[J]. Chinese Journal of Computers, 2011,34(5):865-878.
[4]	潘晓，郝兴，孟小峰．基于位置服务中的连续查询隐私保护研究[J]．计算机研究与发展， 2010,47(1):121-129. PAN X , HAO X , MENG X F . Privacy preserving towards continuous query in location-based services[J]. Journal of Computer Research and Development, 2010,47(1):121-129.
[5]	GEDIK B , LIU L . Location privacy in mobile systems:a personalized anonymization model[A]. Distributed Computing Systems,ICDCS 2005,Proceedings of 25th IEEE International Conference[C]. 2005. 620-629.
[6]	MOKBEL M F , CHOW C Y , AREF W G . The new Casper:query processing for location services without compromising privacy[A]. Proceedings of the 32nd International Conference on Very Large Data Bases[C].VLDB Endowment, 2006. 763-774.
[7]	KALNIS P , GHINITA G , MOURATIDIS K , et al. Preventing loca-tion-based identity inference in anonymous spatial queries[J]. Knowl-edge and Data Engineering,IEEE Transactions, 2007,19(12): 1719-1733.
[8]	GHINITA G , KALNIS P , SKIADOPOULOS S . PRIVE:anonymous location-based queries in distributed mobile systems[A]. Proceedings of the 16th International Conference on World Wide Web[C]. ACM, 2007. 371-380.
[9]	CHOW C Y , MOKBEL M F , LIU X . A peer-to-peer spatial cloaking algorithm for anonymous location-based service[A]. Proceedings of the 14th Annual ACM International Symposium on Advances in Geo-graphic Information Systems[C]. 2006. 171-178.
[10]	HONG J I , LANDAY J A . An architecture for privacy-sensitive ubiqui-tous computing[A]. Proceedings of the 2nd International Conference on Mobile Systems,Applications,and Services[C]. 2004. 177-189.
[11]	KIDO H , YANAGISAWA Y , SATOH T . An architecture for privacy-sensitive ubiqui-tous computing[A]. Perva-sive Services,Proceedings of International Conference[C]. 2005. 88-97.
[12]	YIU M L , JENSEN C S , HUANG X G , LU H . SpaceTwist:managing the trade-offs among location privacy,query performance,and query accuracy in mobile services[A]. IEEE 24th International Conference on Data Engineering[C]. 2008. 366-375.
[13]	GONG Z , SUN G Z , XIE X . Protecting privacy in location-based services using k-anonymity without cloaked region[A]. Mobile Data Management (MDM),2010 Eleventh International Conference[C]. 2010. 366-371.
[14]	黄毅，霍峥，孟小峰． CoPrivacy：一种用户协作无匿名区域的位置隐私保护方法[J]．计算机学报， 2011,34(10):1976-1985. HANG Y , HUO Z , MENG X F . CoPrivacy:a collaborative location privacy-preserving method without cloaking region[J]. Chinese Journal of Computers, 2011,34(10):1976-1985.
[15]	GRUSTER M , GRUNWALD D . Anonymous usage of location-based services through spatial and temporal cloaking[A]. Proceedings of the 1st International Conference on Mobile Systems,Applications and Services[C]. 2003. 31-42.
[16]	MOKBEL M F . Towards privacy-aware location-based database serv-ers[A]. Data Engineering Workshops,Proceedings of 22nd Interna-tional Conference[C]. 2006. 93.
[17]	CHOW C Y , MOKBEL M F , AREF W G . Casper*:query processing for location services without compromising privacy[J]. ACM Transac-tions on Database Systems (TODS), 2009,34(4): 24.
[18]	LI T C , ZHU W T . Protecting user anonymity in location-based services with fragmented cloaking region[A]. Computer Science and Automation Engineering (CSAE),2012 IEEE International Conference[C]. 2012. 227-231.
[19]	杨松涛，马春光，周长利．面向LBS的隐私保护模型及方案[J]．通信学报， 2014,35(8):116-124. YANG S T , MA C G , ZHOU C L . Privacy preserving towards continuous query in location-based services[J]. Journal on Communications, 2014,35(8):116-124.
[20]	SAYE R I , SETHIAN J A . Analysis and applications of the Voronoi implicit interface method[J]. Journal of Computational Physics, 2012, 231(18): 6051-6085.
[21]	LIN X , LU R , LIANG X , et al. STAP:A social-tier-assisted packet forwarding protocol for achieving receiver-location privacy preserva-tion in vanets[A]. INFOCOM,2011 Proceedings IEEE, 2011. 2147-2155.

参数名	取值范围	默认值
用户匿名需求k	5≤k≤30	10
全局移动用户总数U	25 000≤U≤200 000	100 000
用户定义查找范围γ	500≤γ≤2 500	2 000 m
LBS单次PoI最大负载β	1≤β 11≤	6
用户查询PoI个数\|P_i\|	5≤\|P_i\|≤30	10
区域内PoI总数m	—	160 000