Competition-Based Participant Recruitment for Delay-Sensitive Crowdsourcing Applications in D2D Networks
Abstract
Device-to-Device (D2D) networks impose a significant challenge on delay-sensitive crowdsourcing due to the highly nondeterministic and intermittent network connectivity. Under this setting, the paper investigates a participant recruitment problem in which an initial set of recruited nodes, which we call seeds, need to make an optimal decision on what other nodes to recruit to perform the crowdsourcing task. These seeds face the dilemma that recruiting more nodes increases their own payment but on the other hand also increases the risk of being excluded from the crowdsourcing task. As a first attack to this problem, we propose a dynamic programming algorithm. However, it is a centralized solution and hence the practicality is compromised. Therefore, we introduce two distributed alternatives. One is based on the divide-and-conquer paradigm by first partitioning a network into a set of opportunistic Voronoi cells and then running an optimization algorithm in each cell. The other is a task-splitting scheme which recursively delegates the recruitment task to newly joined nodes. We implemented our proposed solutions on an Android-based prototype and built a testbed using 25 Dell Streak tablets. Our experiments which lasted for 24 days demonstrate that the distributed schemes approximate the theoretical optimum with affordable complexity. Moreover, we conducted simulations with a much larger scale and more diverse settings. The simulation results corroborate the experimental data and confirm that our proposed distributed solutions closely approach the performance of the centralized solution while satisfying the optimization goal under different network configurations.
Recommended Citation
Y. Han et al., "Competition-Based Participant Recruitment for Delay-Sensitive Crowdsourcing Applications in D2D Networks," IEEE Transactions on Mobile Computing, vol. 15, no. 12, pp. 2987 - 2999, Institute of Electrical and Electronics Engineers (IEEE), Dec 2016.
The definitive version is available at https://doi.org/10.1109/TMC.2016.2524590
Department(s)
Computer Science
Keywords and Phrases
Delay-constrained; Opportunistic network; Optimization; Prototype; Single-copy multi-path
International Standard Serial Number (ISSN)
1536-1233
Document Type
Article - Journal
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2016 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.
Publication Date
01 Dec 2016
