Abstract
Mobile Crowd Sensing (MCS) relies on a large pool of participants to collect environmental or urban data. However, new MCS applications often suffer from a "cold-start" problem due to a lack of initial awareness. This paper explores using social networks to recruit workers via word-of-mouth influence. We propose a framework that extends social influence models to account for topical interest and incentive attraction. To address the computational complexity of traditional selection methods, we introduce Fast-Selector, a two-phase algorithm that prioritizes trajectory diversity. Experimental results on real-world datasets show that Fast-Selector provides a 100x speedup over greedy approaches with minimal loss in coverage.
Introduction
Mobile Crowd Sensing (MCS) has emerged as a powerful paradigm for large-scale data collection. Despite its potential, the success of MCS is predicated on the availability of a significant worker pool. Most existing literature assumes this pool is pre-established. In practice, new applications face a "cold-start" hurdle. Social networks offer a promising recruitment channel, but traditional influence maximization focuses on the quantity of reached users rather than their geographic utility. For MCS, spatial-temporal coverage is the primary metric of success.
The Recruitment Framework
The authors propose a recruitment framework that integrates social network dynamics with MCS requirements. By extending classic models like Independent Cascade (IC) and Linear Threshold (LT), the framework incorporates user-specific factors such as topical interest and incentive sensitivity.
Algorithm Design
Two main algorithms are developed to solve the seed selection problem:
- Basic-Selector: A greedy approach using Monte-Carlo simulations. While it provides a high-quality baseline, its computational cost is prohibitive for large-scale networks, often taking hours or days to process.
- Fast-Selector: A novel two-phase heuristic. The first phase uses a "budget-insensitive" utility function focusing on social degree and trajectory diversity (using Cosine Similarity of movement matrices). The second phase switches to a "budget-sensitive" mode to refine the final selection as the incentive limit is approached.
Experimental Evaluation
The study utilizes the Brightkite and Gowalla datasets, focusing on a 240km × 200km region in the Northeastern United States. These datasets provide both social links and historical check-in data, allowing for realistic simulations of movement and influence spread.
Results
The evaluation highlights a critical trade-off between accuracy and efficiency. While the Basic-Selector is accurate, its running time scales poorly with the number of nodes, as shown in the following figure.
Fast-Selector addresses this bottleneck by achieving a 100x speedup, processing large datasets in under 1,000 seconds. Crucially, it outperforms standard baselines (like high-degree selection) by an average of 12.9% in coverage while only sacrificing 6–9% compared to the exhaustive Basic-Selector.
Conclusion
By incorporating trajectory diversity into social recruitment, Fast-Selector effectively solves the cold-start problem for MCS. This approach ensures that recruited workers are not just numerous, but geographically diverse. Future work will address privacy concerns regarding location data and explore dynamic incentive mechanisms.
Summary updated