一种基于兴趣点分布的匿名框KNN查询方法

doi:10.3969/j.issn.0372-2112.2016.10.021

电子学报 ›› 2016, Vol. 44 ›› Issue (10): 2423-2431.DOI: 10.3969/j.issn.0372-2112.2016.10.021

一种基于兴趣点分布的匿名框KNN查询方法

朱顺痣¹, 黄亮², 周长利³, 马樱¹

1. 厦门理工学院计算机与信息工程学院, 福建厦门 361024;
2. 国家计算机网络应急技术处理协调中心, 北京 100029;
3. 华侨大学计算机科学与技术学院, 福建厦门 361021

收稿日期:2015-04-14 修回日期:2015-11-28 出版日期:2016-10-25 发布日期:2016-10-25
作者简介:朱顺痣,男,1973年7月出生,福建东山人,厦门大学博士,厦门理工学院计算机与信息工程学院教授、院长.主要研究领域为数据挖掘、信息推荐、隐私保护和系统工程.E-mail:szzhu@xmut.edu.cn;黄亮,男,1982年6月出生,湖南隆回人,中国科学院计算技术研究所博士.目前工作于国家计算机网络应急技术处理协调中心,主要研究领域为无线资源管理、异构网络、集中式无线接入网络、移动互联网;周长利,男,1985年3月出生,黑龙江省哈尔滨人,哈尔滨工程大学博士,华侨大学计算机科学与技术学院讲师.主要研究领域为位置隐私保护、网络与信息安全.E-mail:zhouchangli666@163.com;马樱,男,1982年1月出生,湖南邵阳人,电子科技大学计算机系统结构专业博士,厦门理工学院计算机与信息工程学院讲师.主要研究方向为基于挖掘的软件工程、大数据、云计算.
基金资助:
国家自然科学基金（No.61373147，No.61502404）；福建省自然科学基金（No.2016Y0079，No.2015J05132）；福建省教育厅A类项目（No.JA14234）

A Privacy-Preserving Method Based on PoIs Distribution Using Cloaking Region for K Nearest Neighbor Query

ZHU Shun-zhi¹, HUANG Liang², ZHOU Chang-li³, MA Ying¹

1. School of Computer and Information Engineering, Xiamen University of Technology, Xiamen, Fujian 361024, China;
2. National Computer Network Emergency Response Technical Team Coordination Center of China, Beijing 100029, China;
3. School of Computer Science and Technology, Huaqiao University, Xiamen, Fujian 361021, China

Received:2015-04-14 Revised:2015-11-28 Online:2016-10-25 Published:2016-10-25

摘要/Abstract

摘要：

针对利用匿名框实现的兴趣点K近邻KNN）查询带来的通信开销大、时延长等问题，提出了基于单一兴趣点Voronoi图划分和四叉树层次化组织的KNN查询方法.该方法根据兴趣点层次信息有针对性的构造查询匿名框用来获取详细查询信息，在保护位置隐私的同时，降低了查询通信开销，同时注入虚假查询保护了用户的真实查询内容隐私.最后分别采用模拟地理数据和真实地理数据进行理论分析和有效性验证.

关键词: 位置隐私, 基于位置的服务, 匿名框, K近邻查询

Abstract:

Achieving KNN query with traditional cloaking region brings higher communication cost and delay caused by useless points of interest (PoI) returned,a new KNN query method is proposed.Based on Voronoi diagram division of PoIs and hierarchical index quadtree structure,cloaking region can be constructed purposefully.Due to the targeted query request,the communication cost is decreasing compared with traditional cloaking region methods.And injecting fake query requests makes the query content privacy preserving work.We have verified the effectiveness of our proposal by analysis and experiments.

Key words: location privacy, location based service, cloaking region, K nearest neighbor query

中图分类号:

TP311

朱顺痣, 黄亮, 周长利, 马樱. 一种基于兴趣点分布的匿名框KNN查询方法[J]. 电子学报, 2016, 44(10): 2423-2431.

ZHU Shun-zhi, HUANG Liang, ZHOU Chang-li, MA Ying. A Privacy-Preserving Method Based on PoIs Distribution Using Cloaking Region for K Nearest Neighbor Query[J]. Acta Electronica Sinica, 2016, 44(10): 2423-2431.

参考文献

[1] Palanisamy B,Liu L,Lee K,et al.Anonymizing continuous queries with delay-tolerant mix-zones over road networks[J].Distributed and Parallel Databases,2014,32(1):91-118.
[2] 周傲英,杨彬,金澈清,等.基于位置的服务:架构与进展[J].计算机学报,2011,34(7):1155-1171. Zhou Aoying,Yang Bin,Jin Cheqing,et al.Location-based services:Architecture and progress[J].Chinese Journal of Computers,2011,34(7):1155-1171.(in Chinese)
[3] Ghinita G.Privacy for location-based services[J].Synthesis Lectures on Information Security,Privacy,& Trust,2013,4(1):1-85.
[4] 叶阿勇,林少聪,马建峰,等.一种主动扩散式的位置隐私保护方法[J].电子学报,2015,43(7):1362-1368. Ye Ayong,Lin Shaocong,Ma Jianfeng,et al.An active diffusion based location privacy protection method[J].Acta Electronica Sinica,2015,43(7):1362-1368.(in Chinese)
[5] 潘晓,郝兴,孟小峰.基于位置服务中的连续查询隐私保护研究[J].计算机研究与发展,2010,47(1):121-129. Pan Xiao,Hao Xing,Meng Xiaofeng.Privacy preserving towards continuous query in location-based services[J].Journal of Computer Research and Development,2010,47(1):121-129.(in Chinese)
[6] 刘华玲,郑建国,孙辞海.基于贪心扰动的社交网络隐私保护研究[J].电子学报,2013,41(8):1586-1591. Liu Hualing,Zheng Jianguo,Sun Cihai.Privacy preserving in social networks based on greedy perturbation[J].Acta Electronica Sinica,2013,41(8):1586-1591.(in Chinese)
[7] 唐科萍,许方恒,沈才樑,等.基于位置服务的研究综述[J].计算机应用研究,2012,29(12):4432-4436. Tang Keping,Xu Fangheng,Shen Caiheng,et al.Survey on location based service[J].Application Research on Computer,2012,29(12):4432-4436.(in Chinese)
[8] 陈丹伟,邵菊,樊晓唯,等.基于MAH-ABE的云计算隐私保护访问控制[J].电子学报,2014,42(4):821-827. Chen Danwei,Shao Ju,Fan Xiaowei,et al.MAH-ABE based privacy access control in cloud computing[J].Acta Electronica Sinica,2014,42(4):821-827.(in Chinese)
[9] Hashem T,Kulik L,Zhang R.Countering overlapping rectangle privacy attack for moving kNN queries[J].Information Systems,2013,38(3):430-453.
[10] Ngo C N,Dang T K.On efficient processing of complicated cloaked region for location privacy aware nearest-neighbor queries[A].Proceedings of Information and Communication Technology[C].Berlin Heidelberg:Springer,2013.101-110.
[11] Chow C Y,Mokbel M F,Liu X.Spatial cloaking for anonymous location-based services in mobile peer-to-peer environments[J].GeoInformatica,2011,15(2):351-380.
[12] 王丽娜,彭瑞卿,赵雨辰,等.个人移动数据收集中的多维轨迹匿名方法[J].电子学报,2013,41(8):1653-1659. Wang Lina,Peng Ruiqing,Zhao Yuchen,et al.Multi-dimensional trajectory anonymity in collecting personal mobility data[J].Acta Electronica Sinica,2013,41(8):1653-1659.(in Chinese)
[13] 徐建,徐明,林欣,等.路网限制环境中基于匿名蜂窝的位置隐私保护[J].浙江大学学报(工学版),2011,45(3):429-439. Xu Jian,Xu Ming,Lin Xin,et al.Location privacy protection through anonymous cells in road network[J].Journal of Zhejiang University (Engineering Science),2011,34(5):865-878.(in Chinese)
[14] Pingley A,Zhang N,Fu X,et al.Protection of query privacy for continuous location based services[A].Proceedings of IEEE INFOCOM[C].USA:IEEE PRESS,2011.1710-1718.
[15] 朱良,孙未未,荆一楠,等.基于Voronoi图的路网k聚集最近邻居节点查询方法[J].计算机研究与发展,2011,48(z2):533-540. Zhu Liang,Jing Yinan,Sun Weiwei,et al.Voronoi-based aggregate nearest neighbor query processing in road networks[J].Journal of Computer Research and Development,2011,48(z2):533-540.(in Chinese)
[16] Hu H,Xu J.2PASS:Bandwidth-optimized location cloaking for anonymous location-based services[J].IEEE Transactions on Parallel and Distributed Systems,2010,21(10):1458-1472.
[17] 史敏仪,李玲娟.移动用户位置隐私保护方案研究[J].计算机技术与发展,2014,51(10):151-154. Shi Minyi,Li Lingjuan.Study on location privacy protection scheme for moving objects[J].Computer Technology and Development,2014,51(10):151-154.(in Chinese)
[18] Huang Leping,Yamane L,Mastsuura K,et al.Silent cascade:enhancing location privacy without communication QoS degradation[A].Proceedings of the 3rd International Conference on Security in Pervasive Computing[C].Berlin Heidelberg:Springer,2006.165-180.
[19] Palanisamy B,Liu L.Mobimix:Protecting location privacy with mix-zones over road networks[A].Proceeding of IEEE 27th International Conference on Data Engineering(ICDE)[C].Hannover:IEEE PRESS,2011.494-505.
[20] Freudiger J,Shokri R,Hubaux J P.On the optimal placement of mix zones[A].Privacy Enhancing Technologies[C].Berlin Heidelberg:Springer,2009.216-234.
[21] Mano K,Minami K,Maruyama H.Privacy-preserving publishing of pseudonym-based trajectory location data set[A].The Eighth International Conference on Availability,Reliability and Security (ARES)[C].USA:IEEE PRESS,2013.615-624.
[22] Yu R,Kang J,Huang X,et al.MixGroup:Accumulative pseudonym exchanging for location privacy preservation in vehicular social networks[J].IEEE Transactions on Dependable and Secure Computing,2015,PP(99):1-12.
[23] Xiaodong L,Rongxing L.Vehicular Ad Hoc Network Security and Privacy[M].Wiley:IEEE Press,2015.71-89.
[24] 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].USA:VLDB Endowment,2006.763-774.
[25] 郝忠孝.时空数据库新理论[M].北京:科学出版社,2011.
[26] Chow C Y,Mokbel M F,Liu X.Spatial cloaking for anonymous location-based services in mobile peer-to-peer environments[J].GeoInformatica,2011,15(2):351-380.
[27] Gong Z,Sun G Z,Xie X.Protecting privacy in location-based services using k-anonymity without cloaked region[A].The Eleventh International Conference on Mobile Data Management (MDM)[C].USA:IEEE Press,2010.366-371.
[28] Ma C,Zhou C,Yang S.A voronoi-based location privacy-preserving method for continuous query in LBS[J/OL].International Journal of Distributed Sensor Networks,2015,(2015):Article ID 326953.http://dx.doi.org/10.1155/2015/326953.

一种基于兴趣点分布的匿名框KNN查询方法

A Privacy-Preserving Method Based on PoIs Distribution Using Cloaking Region for K Nearest Neighbor Query

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

[1]	周志刚, 张宏莉, 叶麟, 余翔湛. F-Seeker:基于重匿名的粒度化好友搜索架构[J]. 电子学报, 2016, 44(10): 2477-2484.
[2]	叶阿勇, 林少聪, 马建峰, 许力. 一种主动扩散式的位置隐私保护方法[J]. 电子学报, 2015, 43(7): 1362-1368.
[3]	王丽娜, 彭瑞卿, 赵雨辰, 陈栋. 个人移动数据收集中的多维轨迹匿名方法[J]. 电子学报, 2013, 41(8): 1653-1659.
[4]	徐建, 郭鸣, 徐 Chong, 徐明, 郑宁. 一种分布式环境中的近邻检测方法[J]. 电子学报, 2013, 41(5): 1001-1006.