Budgeted Unknown Worker Recruitment for Heterogeneous Crowdsensing Using CMAB

Abstract

Mobile crowdsensing, through which a requester can coordinate a crowd of workers to complete some sensing tasks, has attracted significant attention recently. In this paper, we focus on the unknown worker recruitment problem in mobile crowdsensing, where workers’ sensing qualities are unknown a priori. We consider the scenario of recruiting workers to complete some continuous sensing tasks. The whole process is divided into multiple rounds. In each round, every task may be covered by more than one recruited workers, but its completion quality only depends on these workers’ maximum sensing quality. Each recruited worker will incur a cost and each task is attached a weight to indicate its importance. Our objective is to determine a recruiting strategy to maximize the total weighted completion quality under a limited budget. We model such unknown worker recruitment process as a <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">novel combinatorial multi-armed bandit</i> (CMAB) problem, and propose an unknown worker recruitment algorithm based on the modified upper confidence bound (UCB). Moreover, we extend the problem to the case where the workers’ costs are also unknown and design the corresponding algorithm. We analyze the regret bounds of the two proposed algorithms through rigorous proofs. In addition, we also study the unknown worker recruitment problem with fairness constraints. Here, the term “fairness” means that the platform must guarantee a minimum selection fraction for each registered worker, so that the platform can avoid the scenario where some workers are over-recruited but some others might be under-recruited. For this problem, we devise a fairness-aware unknown worker recruitment algorithm. Finally, we demonstrate the performance of the proposed algorithms through extensive simulations on real-world traces

Topics & Concepts