Online Stable Task Assignment in Opportunistic Mobile Crowdsensing With Uncertain Trajectories

In opportunistic mobile crowdsensing, participants (workers) accept to carry out the requested sensing tasks only if they are already close to or within the regions of interest. Thus, the existence of an assignment opportunity between a worker-task pair strictly depends on whether or not the worker will visit the task region. However, when worker trajectories are uncertain and hence not known in advance, existing solutions fail to produce an effective task assignment. Besides, a satisfactory task assignment should respect the preferences and capacity constraints of workers and task requesters, which are generally neglected in the literature. In this study, we address all of these issues together and propose novel task assignment algorithms for different settings, which we prove to be optimal in terms of preference awareness (or stability). Extensive simulations performed on both synthetic and real data sets validate our theoretical results, and demonstrate that the proposed algorithms significantly outperform the existing solutions in terms of preference awareness and average quality of sensing attained in the final task assignment in almost all scenarios.