Recently, mobile crowdsensing has become a promising paradigm to collect rich spatial sensing data, by taking advantage of widely distributed sensing devices like smartphones. Based on sensing data, event detection can be conducted in urban areas, to monitor abnormal incidents like traffic jam. However, how to guarantee the detection accuracy is still an open issue, especially when unreliable users who may report wrong observations are considered. In this work, we focus on the problem of user recruitment in collaborative mobile crowdsensing, aiming to optimize the fine-grained detection accuracy in a large urban area. Unfortunately, the problem is proved to be NP-hard, which means there is no polynomial-time algorithm to achieve the optimal solution unless P $=$ NP. To meet the challenge, we first employ a probabilistic model to characterize the unreliability of users, and measure the uncertainty of inferring event occurrences given collected observations by Shannon entropy. Then, by leveraging the properties of adaptive monotonicity and adaptive submodularity, we propose an adaptive greedy algorithm for user recruitment, which is theoretically proved to achieve a constant approximation ratio guarantee. Extensive simulations are conducted, which show our proposed algorithm outperforms baselines under different settings.
Authors: Tong Liu (Shanghai University), Wenbin Wu (Shanghai University), Yanmin Zhu (Shanghai Jiao Tong University), Weiqin Tong (Shanghai University),
Hide Authors & Abstract