Cumulative Participant Selection with Switch Costs in Large-Scale Mobile Crowd Sensing

With the rapid increasing of the number of mobile devices and their embedded sensing technologies, mobile crowd sensing (MCS) has become an emerging modern sensing paradigm for performing large-scale urban sensing. One of the key challenges of large-scale mobile crowd sensing systems is how to effectively select the minimum set of appropriate participants from the huge user pool to perform the sensing tasks. The capability of a particular user for certain task depends on many factors, such as her moving pattern/behavior, device capability, sensor quality, or even uploading bandwidth. Many of these information of participants are unknown by the selection mechanism. Therefore, self-learning based approaches have been proposed to learn the users' capability for certain tasks via multiple trials and their online performances. In this paper, we first model the cumulative participant selection problem as a combinational multi-armed bandit problem and present an online selection algorithm which leverages the historical performing records of participants to learn the different capabilities (both sensing probability and time delay) of participants. Further, to consider the cost of switching participant for particular tasks, we then introduce the cumulative participant selection problem with switch costs and propose a corresponding online learning method. For both proposed learning algorithms, we provide regret analysis. In addition, extensive simulations with real- world mobile datasets are conducted for the evaluations of the proposed methods. Our simulation results confirm the effeteness of them.