Fast participant recruitment algorithm for large-scale Vehicle-based Mobile Crowd Sensing

Mobile crowd sensing has become an emerging computing and sensing paradigm that recruits ordinary participants to perform sensing tasks. With the highly dynamic mobility pattern and the abundance of on-board resources, vehicles have been increasingly recruited to participate large-scale crowd sensing applications such as urban sensing. However, existing participant recruitment algorithms take a long time in recruitment decision for large number of vehicular participants. In this paper, a fast algorithm for vehicle participant recruitment problem is proposed, which achieves linear-time complexity at the sacrifice of a slightly lower sensing quality. The participant recruitment problem is modeled as a unconstrained maximization problem without explicitly cost constraint and a trade-off parameter is introduced to control the recruiter cost. Trace-driven simulations on both real-world and synthetic data-sets are conducted to evaluate the performance of the proposed algorithm. Simulation results show that the proposed algorithm is 50 times faster than the state-of-art algorithm at the sacrifice of 5% lower sensing quality when the number of participants is over 1000.