Optimized Large-Scale Road Sensing Through Crowdsourced Vehicles

Abstract

Modern vehicles are gradually becoming powerful mobile sensing, communication, computing and storage platforms, which bring about the concept of vehicular urban sensing that leverages sensor nodes as an effective and affordable solution for large-scale and fine-grained sensing. And there is a trend to combine the vehicular sensing and outsourcing technologies to solve the large-scale urban road sensing problem. However, how to select appropriate participated vehicles, how to least interrupt the original routes of vehicles, and how to actively maximize the benefit of the sensing remain challenging problems. In this paper, we introduce a Crowdsourced Vehicular Sensing (CVS) framework based on more realistic assumptions of the vehicular sensing, which consists of three steps: vehicle recruitment, candidate path calculation, and path computing. We define a <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">maximal weighted sensing paths</i> (MWSP) problem, which is NP-Complete, in vehicular crowdsensing scenario and use heuristic methods to speed up the solving process for large-scale crowdsensing in urban road networks. The MWSP problem is formulated as a maximal satisfiability (MaxSAT) problem, and a <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">least-interrupted</i> urban sensing strategy is adopted. So trips are least disrupted when conducting the sensing tasks, which would increase the drivers’ willingness to participate in urban sensing. Experiments based on real-world road-network and historical origin-destination datasets verify the effectiveness of the proposed method. The results show that the proposed algorithm outperforms other solutions and it can solve the vehicular crowdsensing problem effectively and efficiently.