Competition-based participant recruitment for delay-sensitive crowdsourcing applications in D2D networks

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.