Introduction
Participatory sensing leverages the ubiquity of mobile devices to collect environmental data, such as air quality or noise levels, across urban landscapes. While cost-effective, these campaigns often suffer from uncoordinated data collection. Without guidance, participants naturally cluster in high-traffic areas, leading to significant data redundancy in some regions and critical gaps in others. Furthermore, coordinating thousands of individuals is computationally daunting, especially when accounting for the stochastic nature of human mobility and the limited "measurement budgets" of volunteers.
This paper introduces Best-match, a coordination algorithm designed to optimize large-scale sensing tasks. By combining Gaussian Processes (GPs) with stochastic mobility models and efficient clustering, the framework provides real-time measurement suggestions that maximize information gain while respecting user constraints.
The Best-match Framework
The proposed system operates in two distinct phases to balance computational complexity with real-time responsiveness:
1. Offline Phase: SiScaS (Simulations for Scalable Searching)
To manage the "curse of dimensionality" inherent in multi-agent coordination, the system first employs DBSCAN to cluster participants based on spatial proximity. It then utilizes Gaussian Processes to model the environmental phenomenon, using Mutual Information as a metric to identify locations where new data would most effectively reduce predictive uncertainty. During this offline stage, the algorithm runs a Stochastic Local Greedy Search (SLGS) across numerous simulated mobility scenarios, generating a library of "ideal" measurement patterns for various potential participant distributions.
2. Online Phase: Best-match
In the live environment, the system observes the actual locations of participants. It performs real-time clustering and identifies the pre-calculated offline simulation that most closely matches the current state using Euclidean distance. This "best match" allows the system to issue high-quality measurement requests in seconds, even when dealing with thousands of users.
Experimental Evaluation
The researchers evaluated the framework using real-world datasets from Beijing, including PM2.5 air quality readings from static stations and GPS trajectories from the Geolife dataset (182 users over five years). To test scalability, the population was synthetically expanded to 1,000 participants by sampling different temporal windows from the mobility pool.
Performance and Utility
The primary metric for success is "Utility," defined by the reduction in uncertainty (Mutual Information) across the monitored area. As shown in the figure below, the Best-match algorithm consistently outperforms standard benchmarks, including Random sampling, Proximity-based (pull) methods, and Naive Greedy approaches.
In highly dynamic environments where conditions change rapidly, Best-match demonstrated a 75.34% improvement in utility over the Naive Greedy approach for 250 participants. Notably, as the number of participants increases, Best-match maintains a significant lead over uncoordinated methods, approaching the theoretical upper bound of information gain.
Computational Efficiency
Scalability is a critical requirement for urban-scale sensing. While a Naive Greedy algorithm provides high utility, its computational cost grows exponentially with the number of participants. As illustrated in the following figure, the time required for the Naive Greedy approach (shown in the inset) skyrockets beyond practical limits as the population reaches 750 participants.
In contrast, the Best-match algorithm maintains a manageable runtime. For a full 24-hour coordination cycle involving 1,000 users, Best-match completed its calculations in approximately two hours, whereas the Naive Greedy approach became computationally infeasible.
Conclusion
The Best-match algorithm effectively bridges the gap between theoretical optimization and practical, large-scale deployment. By embracing the stochasticity of human movement and utilizing offline simulations, the system provides a robust solution for urban participatory sensing. Future work will focus on integrating more sophisticated real-time mobility predictions and addressing potential issues related to sensor heterogeneity and adversarial user behavior.
Summary updated