Combinatorial Multi-Armed Bandit Based Unknown Worker Recruitment in Heterogeneous Crowdsensing

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 an unknown worker recruitment process as a novel combinatorial multi-armed bandit problem, and propose an extended UCB based worker recruitment algorithm. Moreover, we extend the problem to the case where the workers' costs are also unknown and design the corresponding algorithm. We analyze the regrets of the two proposed algorithms and demonstrate their performance through extensive simulations on real-world traces.