Selecting Optimal Mobile Users: Balancing Budget and Accuracy in Long-term Crowdsensing

TL;DR

Researchers from Shanghai Jiao Tong University and Temple University have developed a sophisticated online selection mechanism for crowdsourced environmental monitoring. By leveraging Lyapunov Optimization and Gaussian Processes, they've created a system that manages long-term budgets while maximizing the accuracy of urban air pollution and noise maps.

The Challenge: The Dynamic City Problem

Urban environmental monitoring is shifting from expensive, fixed sensor networks to ubiquitous mobile crowdsourcing. However, a crowdsourcer faces a daunting optimization hurdle: How do you decide which user to pay right now, without knowing who will show up later or how much they will charge?

The difficulty is three-fold:

1. Temporal Coupling: Spending too much budget today leaves the map "blind" tomorrow.
2. Complex Utility: Every new data point has "diminishing returns" (submodularity), but if the cost to get it is too high, the overall "utility-minus-cost" might actually decrease (non-monotonicity).
3. Online Uncertainty: Decisions must be made instantly as users move through the city.

Methodology: Decoupling the Future

The authors' approach, published in IWQoS '19, breaks the problem into two distinct layers.

1. The Long-term Controller (Lyapunov Optimization)

Instead of predicting the future, the system maintains a virtual queue representing the "over-spent budget." If the queue is high, the system becomes "conservative," prioritizing budget saving. If the queue is low, it prioritizes data utility. This effectively converts a long-term average constraint into a series of real-time decisions.

2. The Short-term Executor (Recursive Online Algorithm)

Within a single hour (time slot), the system must solve a non-monotone submodular maximization problem. Since exhaustive search is impossible, they use a multi-stage thresholding strategy.

Figure: The multi-stage online selection process within a single time slot.

The algorithm observes users in the first half of a slot to set a "quality-per-dollar" threshold, then applies this threshold to recruit users in the second half. This process is applied recursively to optimize performance even when the budget is tight.

Modeling Utility via Gaussian Processes

To measure "utility," the authors don't just count data points. They use a Noise-aware Gaussian Process (GP).

• Inference: GP allows the system to predict pollution levels in grids where no users are present.
• Entropy: The utility is defined by the reduction in Conditional Entropy. Essentially, a user is valuable if their data significantly reduces the uncertainty of the entire city map.

Experimental Results

The framework was tested using real-world datasets:

• Air Quality: Beijing's real air pollution indices.
• Mobility: The Microsoft GeoLife dataset (trajectories of 182 users over 3 years).

The results confirmed that the Lyapunov parameter $V$ allows operators to tune the trade-off between map accuracy and cost.

Figure: Average data utility vs. budget upper bound. As the budget increases, the system captures more significant environmental changes.

The proposed algorithm achieved nearly 70% of the theoretical optimal performance (which requires perfect future knowledge) while operating entirely in real-time.

Conclusion and Insights

This research provides a mathematically rigorous way to handle the "budget vs. quality" trade-off that plagues crowdsensing startups. By treating budget management as a queue stability problem and using Gaussian Processes for spatial inference, the authors have moved environmental monitoring closer to a sustainable, self-organizing future.

Key Limitation: The current model assumes one user per grid. Future extensions to handle "sensor fusion" from multiple users in the same location could further improve noise reduction in high-traffic areas.