Please wait a minute...
J4  2011, Vol. 45 Issue (7): 1154-1160    DOI: 10.3785/j.issn.1008-973X.2011.07.003
    
Anonymity level adaptation algorithm to meet resource constraint
of K-anonymity service in LBS
YANG Zhao-hui1, LI Shan-ping1, LIN Xin1,2
1. College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China;
2. Department of Computer Science and Technology, East China Normal University, Shanghai 200241, China
Download:   PDF(0KB) HTML
Export: BibTeX | EndNote (RIS)      

Abstract  

A limitation in current design of K-anonymity services for location based services (LBS) is that they only provide a given minimum level of anonymity as QoS guarantee and can’t improve the anonymity level for users when service resources are capable. The anonymous query result size was proposed as a new QoS target in order to measure and constrain resource consumption on the K-anonymity service and LBS per user query. Then appropriate anonymity level can be selected under such constraint. Theoretical analysis was performed to find mathematical relation between anonymous query result size and anonymity level, leading to the construction of anonymity level adaptation algorithm. The simulation results accorded well with the theoretical relation. The anonymity level adaptation algorithm can control anonymous query result size to stay around the specified QoS target.



Published: 01 July 2011
CLC:  TP 393  
Cite this article:

YANG Zhao-hui, LI Shan-ping, LIN Xin. Anonymity level adaptation algorithm to meet resource constraint
of K-anonymity service in LBS. J4, 2011, 45(7): 1154-1160.

URL:

https://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2011.07.003     OR     https://www.zjujournals.com/eng/Y2011/V45/I7/1154


LBS中面向K-匿名服务资源约束的匿名度调节算法

针对基于位置的服务(LBS)中的K-匿名机制以固定的最小匿名度为服务质量(QoS)指标,不能在计算资源允许的条件下为用户提供更高匿名度的问题,提出定义新的QoS指标——匿名结果集势指标R*,用于度量和约束匿名服务和LBS为用户的每次查询所平均消耗的计算资源,在此约束下选择可接受的匿名度. 从理论上分析匿名结果集势与匿名度的估算函数关系,据此构造相应的匿名度调节算法. 模拟实验的结果与上述理论函数关系吻合很好,证明本文的匿名度调节算法能够将匿名结果集势约束在给定值附近,实现了定义的QoS指标.

[1] GEDIK B, LIU L. Location privacy in mobile systems: a personalized anonymization model [C] ∥ Proceedings of the 25th International Conference on Distributed Computing Systems. Columbus: IEEE, 2005: 620-629.
[2] MOKBEL M, CHOW C, AREF W. The new Casper: query processing for location services without compromising privacy [C] ∥ Proceedings of the 32nd International Conference on Very Large Data Bases. Seoul, Korea: VLDB Endowment, 2006: 763-774.
[3] 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.
[4] CHOW C, MOKBEL M, LIU X. A peertopeer spatial cloaking algorithm for anonymous locationbased service [C] ∥ Proceedings of the 14th Annual ACM International Symposium on Advances in Geographic Information Systems: Arlington: ACM, 2006: 171-178.
[5] GHINITA G, KALNIS P, SKIADOPOULOS S. PRIVE: anonymous locationbased queries in distributed mobile systems [C] ∥ Proceedings of the 16th International Conference on World Wide Web. Banff: ACM, 2007: 371-380.
[6] 林欣,李善平,杨朝晖. LBS中连续查询攻击算法及匿名性度量 [J]. 软件学报, 2009, 20(4): 1058-1068.
LIN Xin, LI Shanping, YANG Zhaohui. Attacking algorithms against continuous queries in LBS and anonymity measurement [J]. Journal of Software, 2009, 20(4): 1058-1068.
[7] XU J, TANG X, HU H, et al. Privacyconscious locationbased queries in mobile environments [J]. IEEE Transactions on Parallel and Distributed Systems, 2010, 21(3): 313-326.
[8] HU H, LEE D. Range nearestneighbor query [J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(1): 78-91.
[9] CHEN J, CHENG R. Efficient evaluation of imprecise locationdependent queries[C] ∥ Proceedings of IEEE 23rd International Conference on Data Engineering. Istanbul: IEEE, 2007: 586-595.
[10] TAO Y, PAPADIAS D, SHEN Q. Continuous nearest neighbor search. [C] ∥ Proceedings of the 28th International Conference on Very Large Data Bases. Hong Kong, China: VLDB Endowment, 2002: 287-298.
[11] BRINKHOFF T. A framework for generating networkbased moving objects [J]. Geoinformatica, 2002, 6(2): 153-180.

[1] I De-jun,WANG Gang,YANG Can-jun,JIN Bo,CHEN Yan-hu. NTP/IEEE1588-based time synchronization system in seafloor observatory network[J]. J4, 2014, 48(1): 1-7.
[2] GUO Tong,LIN Feng. Bayesian network structure learning based on hybrid genetic
and fish swarm algorithm
[J]. J4, 2014, 48(1): 130-135.
[3] DU Rui-zhong, TIAN Jun-feng, ZHANG Huan-guo. Cloud service selection model based on trust and personality preferences[J]. J4, 2013, 47(1): 53-61.
[4] ZHANG Shuai, SUN Jian-ling, XU Bin, HUANG Chao, KAVS Aleksander J.. RBAC based access control model for services compositions
cross multiple enterprises
[J]. J4, 2012, 46(11): 2035-2043.
[5] Chen Sui-sheng,Lu Jian-gang,Lou Xiao-chun. Localization algorithm for wireless sensor networks
based on MDS-MAP and nonlinear filtering
[J]. J4, 2012, 46(5): 866-872.
[6] PAN Ju-long, LI Shan-ping, ZHANG Dao-yuan. Detecting suspicious node within one cluster in wireless sensor network
using game theoretic approach
[J]. J4, 2012, 46(1): 72-78.
[7] YANG Zhao-hui, LI Shan-ping, LIN Xin. Quality optimizing real-time scheduling for incremental context services[J]. J4, 2012, 46(1): 90-97.
[8] GAO Qing,LI Shan-ping,YANG Zhao-hui. Virtual force-field based energy efficient geo-routing in
wireless sensor network
[J]. J4, 2012, 46(1): 98-104.
[9] QIAN Jian-feng, YIN Jian-wei, DONG Jin-xiang. Load balancing algorithms of semantic publish/subscribe system
over structured P2P networks
[J]. J4, 2011, 45(10): 1710-1719.
[10] PAN Gang, LI Shi-jian, CHEN Yun-xing. ScudContext: large-scale environmental context services infrastructure
towards cyber-physical space integration
[J]. J4, 2011, 45(6): 991-998.
[11] CHE Jian-hua, HE Qin-ming, CHEN Jian-hai, WANG Bei. Software simulation-based fault injection tool of
virtual machine system
[J]. J4, 2011, 45(4): 614-620.
[12] ZHANG Li-ping, PAN Gang, ZHENG Neng-gan, YANG Guo-qing, LI Hong, ZHAO Min-de. Consistent bidirectional generation method and development
platform based on SmartC models and codes
[J]. J4, 2011, 45(1): 20-29.
[13] LI Jian-ting, JIN Xin-yu, TANG Jun, ZHANG Yu. Target localization method based on wireless multimedia sensor network[J]. J4, 2011, 45(1): 45-49.
[14] SHU Ting, SUN Shou-qian, WANG Hai-ning, XU Wei-qiang. Adaptive generation algorithm for executable state identification
sequences in EFSM model
[J]. J4, 2010, 44(11): 2183-2187.
[15] CHEN You-Rong, SHU Li, DONG Ji-Fen, HONG Zhen. Power control in wireless sensor network based on
nearestneighbor algorithm
[J]. J4, 2010, 44(7): 1321-1326.