基于双边拍卖的群智感知数据复用机制设计

doi:10.11959/j.issn.2096-3750.2019.00109

物联网学报 ›› 2019, Vol. 3 ›› Issue (3): 26-33.doi: 10.11959/j.issn.2096-3750.2019.00109

基于双边拍卖的群智感知数据复用机制设计

江常坤¹,高林²

¹ 深圳大学计算机与软件学院，广东深圳 518060
² 哈尔滨工业大学（深圳）电子与信息工程学院，广东深圳 518055

修回日期:2019-03-12 出版日期:2019-09-30 发布日期:2019-10-14
作者简介:江常坤（1988- ），男，河南信阳人，深圳大学计算机与软件学院助理教授，主要研究方向为移动计算、智能物联网和网络经济学。|高林（1980- ），男，浙江金华人，哈尔滨工业大学（深圳）电子与信息工程学院副教授，主要研究方向为无线通信与网络、博弈论和网络经济学。

Mechanism design for crowd sensing with data reuse based on two-sided auction

Changkun JIANG¹,Lin GAO²

¹ College of Computer Science and Software Engineering,Shenzhen University,Shenzhen 518060,China
² School of Electronic and Information Engineering,Harbin Institute of Technology (Shenzhen),Shenzhen 518055,China

Revised:2019-03-12 Online:2019-09-30 Published:2019-10-14

摘要/Abstract

摘要：

群智感知是一种有前景的感知范式，其主要借助大量移动设备中的多样嵌入式传感器来完成数据感知任务。群智感知中的一个关键问题是如何有效地协调移动设备用户同时执行多项感知任务。通过在感知任务和用户之间引入一个新的数据层，从而有效地利用感知任务的相似性和用户的异质性，在数据层之上建立联合任务选择和用户调度问题，旨在最大化整个系统的社会福利。这个问题因其组合特性以及存在感知任务和用户两方面的私有信息而很难解决。为了处理上述问题，提出了一种双边随机拍卖机制，并证明其能够满足计算高效性、个体理性和期望意义下的激励相容性。仿真结果表明，所提的随机拍卖机制可以接近最优的社会福利，并且数据复用带来的社会福利收益会随着任务相似性的增强而显著增加。

关键词: 群智感知, 数据复用, 激励机制, 拍卖机制

Abstract:

Crowd sensing is a promising sensing paradigm,which mainly uses a variety of embedded sensors in a large number of mobile devices to accomplish data sensing tasks.One of the key issues in crowd sensing is how to effectively coordinate mobile device users to perform multiple sensory tasks simultaneously.By introducing a new data layer between the sensing task and the user,the similarity of the sensing task and the heterogeneity of the user were effectively utilized,and the joint task selection and user scheduling problems were established on the data layer,aiming at maximizing the social welfare of the whole system.This problem was difficult to solve due to its combinatorial nature and the presence of private information on both the sensing tasks and the users.In order to deal with these problems,a two-sided randomized auction mechanism was proposed,and it was proved that it can satisfy the desirable properties of the computational efficiency,the individual rationality,and the incentive compatibility in expectation.The simulation results show that the proposed stochastic auction mechanism can achieve nearly optimal social welfare,and the social welfare benefits brought by data reuse will increase significantly with the enhancement of task similarity.

Key words: crowd sensing, data reuse, incentive mechanism, auction mechanism

中图分类号:

TN915

江常坤,高林. 基于双边拍卖的群智感知数据复用机制设计[J]. 物联网学报, 2019, 3(3): 26-33.

Changkun JIANG,Lin GAO. Mechanism design for crowd sensing with data reuse based on two-sided auction[J]. Chinese Journal on Internet of Things, 2019, 3(3): 26-33.

图/表 3

参考文献 20

[1]	GANTI R K , YE F , LEI H . Mobile crowd sensing:current state and future challenges[J]. IEEE Communications Magazine, 2011,49(11): 32-39.
[2]	DAS T , MOHAN P , PADMANABHAN V N ,et al. PRISM:platform for remote sensing using smart phones[C]// The 8th International Conference on Mobile Systems,Applications,and Services, 2010.
[3]	RA M R , LIU B , LA PORTA T F ,et al. Medusa:a programming framework for crowd-sensing applications[C]// ACM MobiSys. ACM, 2012.
[4]	DUAN L J , KUBO T , SUGIYAMA K ,et al. Incentive mechanisms for smart phone collaboration in data acquisition and distributed computing[C]// IEEE INFOCOM. IEEE, 2012.
[5]	YANG D J , XUE G L , FANG X ,et al. Incentive mechanisms forcrowdsensing:crowd sourcing with smart phones[J]. IEEE/ACM Transactions on Networking, 2016,24(3): 1732-1744.
[6]	LUO T , THAM C K . Fairness and social welfare in incentivizing participatory sensing[C]// 2012 9th Annual IEEE Communications Society Conference on Sensor,Mesh and Ad Hoc Communications and Networks (SECON). IEEE, 2012.
[7]	FENG Z N , ZHU Y M , ZHANG Q ,et al. TRAC:truthful auction for location-aware collaborative sensing in mobile crowdsourcing[C]// IEEE INFOCOM. IEEE, 2014.
[8]	ZHANG X , XUE G L , YU R Z ,et al. Truthful incentive mechanisms for crowd sourcing[C]// IEEE Conference on Computer Communications. IEEE, 2015: 2830-2838.
[9]	GAO L , HOU F , HUANG J W . Providing long-term participation incentive in participatory sensing[C]// IEEE INFOCOM. IEEE, 2015.
[10]	CHEUNG M H , SOUTHWELL R , HOU F ,et al. Distributed time-sensitive task selection in mobile crowdsensing[C]// The 16th ACM International Symposium on Mobile Ad Hoc Networking and Computing. ACM, 2015: 157-166.
[11]	JIN H M , SU L , CHEN D Y ,et al. Quality of information aware incentive mechanisms for mobile crowd sensing systems[C]// The 16th ACM International Symposium on Mobile Ad Hoc Networking and Computing. ACM, 2015: 167-176.
[12]	LI Y P , COURCOUBETIS C , DUAN L J . Dynamic routing for social information sharing[J]. IEEE Journal on Selected Areas in Communications, 2017,35(3): 571-585.
[13]	JIN H M , SU L , NAHRSTEDT K . Centurion:incentivizing multi-requester mobile crowd sensing[C]// IEEE Conference on Computer Communications. IEEE, 2017: 1-9.
[14]	NISAN N , RONEN A . Computationally feasible VCG mechanisms[J]. Journal of Artificial Intelligence Research, 2007(29): 19-47.
[15]	YANG S , HAJEK B . VCG-Kelly mechanisms for allocation of divisible goods:adapting VCG mechanisms to one-dimensional signals[J]. IEEE Journal on Selected Areas in Communications, 2007,25(6): 1237-1243.
[16]	DOBZINSKI S , DUGHMI S . On the power of randomization in algorithmic mechanism design[C]// 2009 50th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 2009.
[17]	LAVI R , SWAMY C . Truthful and near-optimal mechanism designvia linear programming[J]. Journal of the ACM, 2011,58(6).
[18]	ZHANG L Q , LI Z P , WU C . Dynamic resource provisioning in cloud computing:a randomized auction approach[C]// IEEE INFOCOM. IEEE, 2014.
[19]	SMITH D K . Theory of linear and integer programming[J]. Journal of the Operational Research Society, 1987,38(6).
[20]	BRESLAU L , CAO P , FAN L ,et al. Web caching and Zipf-like distributions:evidence and implications[C]// IEEE INFOCOM. IEEE, 1999.

基于双边拍卖的群智感知数据复用机制设计

Mechanism design for crowd sensing with data reuse based on two-sided auction

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 3

参考文献 20

相关文章 7

Metrics

推荐阅读 0

[1]	郭英芸, 高博, 张志飞, 张煜, 熊轲. 一种基于带宽分配的联邦学习激励机制[J]. 物联网学报, 2022, 6(4): 82-92.
[2]	冯心欣, 郭丹颖, 柳泽烽, 郑海峰. 结合聚类与CMAB的群智感知车联网任务分配方法[J]. 物联网学报, 2021, 5(3): 86-96.
[3]	沈晓东, 刘俊勇, 胡帅, 饶萍, 何迈. 泛在电力物联网形势下考虑多主体投资的配电网运行优化策略[J]. 物联网学报, 2021, 5(1): 117-122.
[4]	王朝炜,刘婷,王天宇,王卫东. 面向智慧矿山的移动群智感知覆盖及能效优化[J]. 物联网学报, 2020, 4(4): 17-25.
[5]	张伟,李卓,陈昕. 感知质量优化的移动群智感知任务在线分发算法[J]. 物联网学报, 2020, 4(4): 91-97.
[6]	骆淑云,温雨舟,徐伟强,朱升宏. 移动智能边缘计算激励机制研究[J]. 物联网学报, 2019, 3(2): 80-88.
[7]	刘怀哲,高林. 基于移动热点共享的物联网激励机制研究[J]. 物联网学报, 2019, 3(1): 20-29.