Toward Optimum Crowdsensing Coverage with Guaranteed Performance

Mobile crowdsensing networks have emerged to show elegant data collection capability in loosely cooperative network. However, in the sense of coverage quality, marginal works have considered the efficient (less participants) and effective (more coverage) designs for mobile crowdsensing network. We investigate the optimal coverage problem in distributed crowdsensing networks. In that, the sensing quality and the information delivery are jointly considered. Different from the conventional coverage problem, ours only select a subset of mobile users, so as to maximize the crowdsensing coverage with limited budget. We formulate our concerns as an optimal crowdsensing coverage problem, and prove its NP-completeness. In tackling this difficulty, we also prove the submodular property in our problem. Leveraging the favorable property in submodular optimization, we present the greedy algorithm with approximation ratio O(√ k), where k is the number of selected users. Such that the information delivery and sensing coverage ratio could be guaranteed. Finally, we make extensive evaluations for the proposed scheme, with trace-driven tests. Evaluation results show that the proposed scheme could outperform the random selection by 2 × with a random walk model, and over 3 × with real trace data, in terms of crowdsensing coverage. Besides, the proposed scheme achieves near optimal solution comparing with the brute-force search results.