Minimum-Cost Crowdsourcing with Coverage Guarantee in Mobile Opportunistic D2D Networks
Authors:
Open Access
- 2 March 2017
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Mobile Computing
- Vol. 16 (10) , 2806-2818
Abstract
With the remarkable proliferation of intelligent wireless devices and active mobile users, we have witnessed a rapid increasing trend of mobile crowdsourcing applications. While crowdsourcing does not depend on any specific underlying network, the device-to-device (D2D)-based crowdsourcing is highly desired when the originator of a crowdsourcing task cannot directly reach out to the participants or the conventional approaches for data transportation are costly. The marriage of crowdsourcing and D2D creates new, interesting research problems, mainly due to the unique non-deterministic setting in D2D. In this work, we focus on the problem of how to efficiently distribute a crowdsourcing task and recruit participants based on D2D communications. We formally formulate the minimum-cost crowdsourcing (MCC) problem in D2D networks, which explores a multi-dimensional design space to seek an optimal solution that minimizes the total crowdsourcing cost while satisfying the coverage probability over the field of interest. We introduce an approximation algorithm based on a reduced solution space and formally prove that its cost is bounded by a desired approximation ratio in comparison with the optimal solution. We further propose a lightweight online heuristic that inherits the same design philosophy but implements it in a distributed manner. We prototype the proposed online scheme in Android and carry out experiments in a campus environment, involving 21 Dell Streak tablets carried by students for a period of 15 days. We also extract the algorithm codes from our prototype and perform extensive simulations based on Haggle trace. The results demonstrate the efficiency of the proposed heuristics and reveal empirical insights into the design tradeoffs and practical considerations in D2D-based crowdsourcing.Keywords
Funding Information
- US National Science Foundation (CNS-1528004)
This publication has 35 references indexed in Scilit:
- Pay as How Well You Do2015
- Distributed Time-Sensitive Task Selection in Mobile Crowdsensing2015
- Quality of Information Aware Incentive Mechanisms for Mobile Crowd Sensing Systems2015
- Truthful incentive mechanisms for crowdsourcing2015
- Game-theoretic resource allocation methods for device-to-device communicationIEEE Wireless Communications, 2014
- On minimizing budget and time in influence propagation over social networksSocial Network Analysis and Mining, 2012
- Maximizing Submodular Set Functions Subject to Multiple Linear Constraints2009
- Probabilistic routing in intermittently connected networksACM SIGMOBILE Mobile Computing and Communications Review, 2003
- Delay-tolerant networking: an approach to interplanetary InternetIEEE Communications Magazine, 2003
- Submodular functions and convexity1983