iLOCuS: Incentivizing Vehicle Mobility to Optimize Sensing Distribution in Crowd Sensing

Vehicular crowd sensing systems are designed to achieve large spatio-temporal sensing coverage with low-cost in deployment and maintenance. For example, taxi platforms can be utilized for sensing city-wide air quality. However, the goals of vehicle agents are often inconsistent with the goal of the crowdsourcer. Vehicle agents like taxis prioritize searching for passenger ride requests (defined as task requests), which leads them to gather in busy regions. In contrast, sensing systems often need to sample data over the entire city with a desired distribution (e.g., Uniform distribution, Gaussian Mixture distribution, etc.) to ensure sufficient spatio-temporal information for further analysis. This inconsistency decreases the sensing coverage quality and thus impairs the quality of the collected information. A simple approach to reduce the inconsistency is to greedily incentivize the vehicle agents to different regions. However, incentivization brings challenges, including the heterogeneity of desired target distributions, limited budget to incentivize more vehicle agents, and the high computational complexity of optimizing incentivizing strategies. To this end, we present a vehicular crowd sensing system to efficiently incentivize the vehicle agents to match the sensing distribution of the sampled data to the desired target distribution with a limited budget. To make the system flexible to various desired target distributions, we formulate the incentivizing problem as a new type of non-linear multiple-choice knapsack problem, with the dissimilarity between the collected data distribution and the desired distribution as the objective function. To utilize the budget efficiently, we design a customized incentive by combining monetary incentives and potential task (ride) requests at the destination. Meanwhile, an efficient optimization algorithm, iLOCuS, is presented to plan the incentivizing policy for vehicle agents to decompose the sensing distribution into two distinct levels: time-location level and vehicle level, to approximate the optimal solution iteratively and reduce the dissimilarity objective. Our experimental results based on real-world data show that our system can reduce up to 26.99 percent of the dissimilarity between the sensed and target distributions compared to benchmark methods.