计算机科学 ›› 2019, Vol. 46 ›› Issue (3): 202-208.doi: 10.11896/j.issn.1002-137X.2019.03.030

• 信息安全 • 上一篇    下一篇

基于双向拍卖的k-匿名激励机制

童海1,2,白光伟1,沈航1,3   

  1. (南京工业大学计算机科学与技术学院 南京 211816)1
    (南京大学计算机软件新技术国家重点实验室 南京 210093)2
    (南京邮电大学通信与网络技术国家工程研究中心 南京 210003)3
  • 收稿日期:2018-02-11 修回日期:2018-05-14 出版日期:2019-03-15 发布日期:2019-03-22
  • 通讯作者: 沈航(1984-),男,博士,讲师,硕士生导师,CCF会员,主要研究方向为无线网络编码、移动互联网、无线多媒体通信协议等,E-mail:hsen@njtech.edu.cn(通信作者)。
  • 作者简介:童海(1993-),男,硕士生,主要研究方向为移动群智感知、激励机制、隐私保护,E-mail:tonghaiwork@163.com;白光伟(1961-),男,博士,教授,博士生导师,CCF杰出会员,主要研究方向为无线传感器网络、移动互联网、网络体系结构和协议、网络系统性能分析和评价、多媒体网络服务质量等
  • 基金资助:
    国家自然科学基金项目(61502230,61073197),江苏省自然科学基金项目(BK20150960),江苏省普通高校自然科学研究项目(15KJB520015),南京市科技计划项目(201608009),南京大学计算机软件新技术国家重点实验室资助项目(KFKT2017B21),南京邮电大学通信与网络技术国家工程研究中心资助项目,江苏省六大高峰人才基金资助项目(第八批)资助

Double-auction-based Incentive Mechanism for k-anonymity

TONG Hai1,2,BAI Guang-wei1,SHEN Hang1,3   

  1. (College of Computer Science and Technology,Nanjing Tech University,Nanjing 211816,China)1
    (State Key Laboratory for Novel Software Technology (Nanjing University),Nanjing 210093,China)2
    (National Engineering Research Center for Communication and Network Technology (Nanjing University of Posts and Telecommunications),Nanjing 210003,China)3
  • Received:2018-02-11 Revised:2018-05-14 Online:2019-03-15 Published:2019-03-22

摘要: 在基于位置的服务(LBS)中,kk-匿名是重要的位置隐私保护技术之一。kk-匿名要求至少k名用户参与匿名集的构建,使得集合中任何用户都不能从其他k-1名用户中区分开来。然而,很多参与者希望得到回报或顾忌个人隐私泄漏,导致匿名集人数不足。为了提高用户参与匿名集构建的积极性,提出了一种基于双向拍卖的kk-匿名激励机制(Double-Acution-based Incentive,DAI),以保证交易公平的同时最大化买卖双方的效用。首先,利用多阶段采样来筛选候选用户集;然后,根据预算平衡性选择获胜用户集和合理的报酬;最后,从个体理性、计算效率、预算平衡和真诚可信等方面,通过理论证明了机制的合理性。仿真结果表明,DAI能够抑制用户恶意竞价情况的发生,同时提高买方的满意度和效用。

关键词: k-匿名, 激励机制, 双向拍卖, 位置隐私

Abstract: kk-anonymity has become one of the most important location privacy technologies in LBS (Location Based Service).At least k users should be required to build an anonymous set,in which any user cannot be distinguished from other k-1 users.However,many users are not interested in their location privacy,so they have little interest in participating in the construction of anonymous sets.In order to improve the enthusiasm of users to participate in building anonymous sets,this paper proposed a double-auction-based incentive(DAI) mechanism for k-anonymity,which maximizes both the utility of buyers and sellers while guaranteeing fair transaction.To this end,multi-stage sample is used to filter the candidate user sets,then a reasonable remuneration and the winning set of users are determined according to budget balance.Finally,the rationality of the mechanism is provided in consideration of individual rationality,computation efficiency,budget balance and truthfulness,and so on.Simulation results demonstrate that DAI can solve the problem of malicious competition in the existing methods,and improve satisfaction and utility of buyers effectively.

Key words: k-anonymity, Double auction, Incentive mechanism, Location privacy

中图分类号: 

  • TP393
[1]SWEENEY L.k-anonymity:A model for protecting privacy[J].International Journal of Uncertainty,Fuzziness and Knowledge-Based Systems,2002,10(5):557-570.
[2]YANG D,XUE G,FANG X,et al.Crowdsourcing to smartphones:incentive mechanism design for mobile phone sensing[C]∥International Conference on Mobile Computing and Networking.ACM,2012:173-184.
[3]YANG D,FANG X,XUE G.Truthful incentive mechanisms for k-anonymity location privacy[C]∥IEEE INFOCOM.IEEE,2013:2994-3002.
[4]YUAN Z,WEI T,SHENG Z.On Designing Satisfaction-Ratio-Aware Truthful Incentive Mechanisms for k-Anonymity Location Privacy[J].IEEE Transactions on Information Forensics & Security,2016,11(11):2528-2541.
[5]WU Y,PENG H,PENG H,et al.MagiCrowd:A crowd based incentive for location-aware crowd sensing[C]∥Wireless Communications and NETWORKING Conference.IEEE,2016.
[6]WANG X,LIU Z,TIAN X,et al.Incentivizing Crowdsensing with Location-Privacy Preserving[J].IEEE Transactions on Wireless Communications,2017,PP(99):1.
[7]SHI W S,SUN H,CAO J,et al.Edge Computing:An Emerging Computing Model for Internet of Everything Era[J].Journal of Computing Research and Development,2017,54(5):907-924.(in Chinese)
施巍松,孙辉,曹杰,等.边缘计算:万物互联时代新型计算模型[J].计算机研究与发展,2017,54(5):907-924.
[8]KAWAJIRI R,SHIMOSAKA M,KASHIMA H.Steered crowd-
sensing:incentive design towards quality-oriented place-centric crowdsensing[C]∥ACM International Joint Conference on Pervasive and Ubiquitous Computing.ACM,2014:691-701.
[9]LI X,MIAO M,LIU H,et al.An incentive mechanism for K -anonymity in LBS privacy protection based on credit mechanism[J].Soft Computing,2017,21(14):3907-3917.
[10]REDDY S,ESTRIN D,HANSEN M,et al.Examining micro-payments for participatory sensing data collections∥Proceedings of the 12th ACM International Conference on Ubiquitous Computing.ACM,2010:33-36.
[11]DANEZIS G,LEWIS S,ANDERSON R.How much is location privacy worth[C]∥Proceedings of the Workshop on the Economics of Information Security Series (WEIS).ACM,2005.
[12] LEE J S,HOH B.Sell your experiences:a market mechanism based incentive for participatory sensing[C]∥IEEE InternationalConference on Pervasive Computing and Communications.IEEE,2010:60-68.
[13] LUO T,TAN H P,XIA L.Profit-maximizing incentive for participatory sensing[C]∥ Proceedings-IEEE INFOCOM.IEEE,2014:127-135.
[14]FENG Z,ZHU Y,ZHANG Q,et al.TRAC:Truthful auction for location-aware collaborative sensing in mobile crowdsourcing[C]∥Proceedings-IEEE INFOCOM.IEEE〈2014:1231-1239.
[15]ZHANG H,LIU B,SUSANTO H,et al.Incentive mechanism for proximity-based Mobile Crowd Service systems[C]∥IEEE INFOCOM 2016-IEEE International Conference on Computer Communications.IEEE,2016:1-9.
[16]ZHANG X,YANG Z,ZHOU Z,et al.Free Market of Crowd-
sourcing:Incentive Mechanism Design for Mobile Sensing[J].IEEE Transactions on Parallel & Distributed Systems,2014,25(12):3190-3200.
[17]ZHAO D,LI X Y,MA H.Budget-Feasible Online Incentive
Mechanisms for Crowdsourcing Tasks Truthfully[J].IEEE/ACM Transactions on Networking,2016,24(2):647-661.
[1] 傅彦铭, 朱杰夫, 蒋侃, 黄保华, 孟庆文, 周兴.
移动众包中基于多约束工人择优的激励机制研究
Incentive Mechanism Based on Multi-constrained Worker Selection in Mobile Crowdsourcing
计算机科学, 2022, 49(9): 275-282. https://doi.org/10.11896/jsjkx.210700129
[2] 王磊, 李晓宇.
基于随机洋葱路由的LBS移动隐私保护方案
LBS Mobile Privacy Protection Scheme Based on Random Onion Routing
计算机科学, 2022, 49(9): 347-354. https://doi.org/10.11896/jsjkx.210800077
[3] 王思明, 谭北海, 余荣.
面向6G可信可靠智能的区块链分片与激励机制
Blockchain Sharding and Incentive Mechanism for 6G Dependable Intelligence
计算机科学, 2022, 49(6): 32-38. https://doi.org/10.11896/jsjkx.220400004
[4] 杜辉, 李卓, 陈昕.
基于在线双边拍卖的分层联邦学习激励机制
Incentive Mechanism for Hierarchical Federated Learning Based on Online Double Auction
计算机科学, 2022, 49(3): 23-30. https://doi.org/10.11896/jsjkx.210800051
[5] 王鑫, 周泽宝, 余芸, 陈禹旭, 任昊文, 蒋一波, 孙凌云.
一种面向电能量数据的联邦学习可靠性激励机制
Reliable Incentive Mechanism for Federated Learning of Electric Metering Data
计算机科学, 2022, 49(3): 31-38. https://doi.org/10.11896/jsjkx.210700195
[6] 杨昕宇, 彭长根, 杨辉, 丁红发.
基于演化博弈的理性拜占庭容错共识算法
Rational PBFT Consensus Algorithm with Evolutionary Game
计算机科学, 2022, 49(3): 360-370. https://doi.org/10.11896/jsjkx.210900110
[7] 张学军, 杨昊英, 李桢, 何福存, 盖继扬, 鲍俊达.
融合语义位置的差分私有位置隐私保护方法
Differentially Private Location Privacy-preserving Scheme withSemantic Location
计算机科学, 2021, 48(8): 300-308. https://doi.org/10.11896/jsjkx.200900198
[8] 王辉, 朱国宇, 申自浩, 刘琨, 刘沛骞.
基于用户偏好和位置分布的假位置生成方法
Dummy Location Generation Method Based on User Preference and Location Distribution
计算机科学, 2021, 48(7): 164-171. https://doi.org/10.11896/jsjkx.200800069
[9] 王乐业.
群智感知中的地理位置本地化差分隐私机制:现状与机遇
Geographic Local Differential Privacy in Crowdsensing:Current States and Future Opportunities
计算机科学, 2021, 48(6): 301-305. https://doi.org/10.11896/jsjkx.201200223
[10] 张王策, 范菁, 王渤茹, 倪旻.
面向缺损数据的(α,k)-匿名模型
(α,k)-anonymized Model for Missing Data
计算机科学, 2020, 47(6A): 395-399. https://doi.org/10.11896/JsJkx.190500131
[11] 周艺华, 李广辉, 杨宇光, 侍伟敏.
基于GeoHash的近邻查询位置隐私保护方法
Location Privacy Preserving Nearest Neighbor Querying Based on GeoHash
计算机科学, 2019, 46(8): 212-216. https://doi.org/10.11896/j.issn.1002-137X.2019.08.035
[12] 吴丹丹, 吕鑫.
分布式结构下基于用户协作的匿名区域构建算法
Location Anonymous Algorithm Based on User Collaboration under Distributed Structure
计算机科学, 2019, 46(4): 158-163. https://doi.org/10.11896/j.issn.1002-137X.2019.04.025
[13] 曹敏姿, 张琳琳, 毕雪华, 赵楷.
个性化(α,l)-多样性k-匿名隐私保护模型
Personalized (α,l)-diversity k-anonymity Model for Privacy Preservation
计算机科学, 2018, 45(11): 180-186. https://doi.org/10.11896/j.issn.1002-137X.2018.11.028
[14] 熊婉竹, 李晓宇.
基于匿名路由的移动位置隐私保护
Mobile Location Privacy Protection Based on Anonymous Routing
计算机科学, 2018, 45(10): 142-149. https://doi.org/10.11896/j.issn.1002-137X.2018.10.027
[15] 戴佳筑,华亮.
路网环境下敏感位置匿名区域的生成方法
Method of Anonymous Area Generation for Sensitive Location Protection under Road Networks
计算机科学, 2016, 43(3): 137-144. https://doi.org/10.11896/j.issn.1002-137X.2016.03.027
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!