Minimum-Cost Crowdsourcing with Coverage Guarantee in Mobile Opportunistic D2D Networks

摘要

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.