TL;DR
This paper provides a comprehensive survey of the state-of-the-art in task allocation for Mobile Crowd Sensing (MCS), a burgeoning field that leverages mobile devices for urban sensing. It highlights the unique challenges of MCS task allocation compared to general crowdsourcing and categorizes existing research, offering insights into future research directions.
What Problem Does This Paper Address?
Urban sensing is crucial for understanding city dynamics, and Mobile Crowd Sensing (MCS) has emerged as a cost-effective approach using mobile devices. A fundamental challenge in MCS is task allocation: efficiently assigning sensing tasks to mobile users (workers) to maximize sensing quality, coverage, and application effectiveness while considering various constraints. Traditional crowdsourcing allocation methods are often insufficient due to MCS's unique characteristics, such as the inherent mobility of participants, the need for specific locations, privacy concerns, and the energy constraints of mobile devices. This paper aims to bridge this gap by systematically reviewing and categorizing the existing research on MCS task allocation, identifying its unique features, and outlining future research opportunities.
Methods
The paper categorizes MCS task allocation research based on several dimensions:
- Problem Formulation: This includes classifying tasks by their objectives (single vs. multi-objective), the scope of allocation (single-task vs. multi-task), and the timing of allocation (offline vs. online).
- Cost Factors: Research is analyzed based on the primary cost considered, such as incentive cost, energy consumption, and location privacy.
- Allocation Algorithms: The paper distinguishes between greedy-based algorithms (iteratively selecting the "best" option) and non-greedy algorithms (e.g., genetic algorithms, minimum cost maximum flow, bipartite graph partitioning).
The authors also discuss the unique factors in MCS task allocation, differentiating them from general crowdsourcing. These include:
- Mobility-Relevant Features: Participatory vs. opportunistic modes of participation and the critical need for location privacy.
- Sensing-Relevant Features: Increased energy consumption due to sensor usage and localization, and the varying "sensor type requirements" across different mobile devices.
Datasets
The paper notes that a significant challenge for evaluating MCS task allocation algorithms is the absence of public real-world datasets. Consequently, existing work often evaluates algorithms using a combination of:
- Real-world datasets: Primarily for worker mobility information, such as the D4D dataset (containing cell tower and phone call records) and Gowalla.
- Synthetic datasets: For task characteristics like spatial-temporal distribution, budget, and required quality.
The paper also mentions a toolbox for generating synthetic data to enable reproducible research.
Key Insights and Ideas
- MCS is not just crowdsourcing on wheels: The inherent mobility, location dependency, and sensor diversity of mobile devices introduce unique challenges and opportunities in task allocation that are distinct from traditional crowdsourcing.
- The "pull" vs. "push" dilemma: Simple "pull" models where workers choose tasks can lead to suboptimal global performance, while "push" models where the server assigns tasks require sophisticated allocation algorithms.
- Trade-offs are central: MCS task allocation is fundamentally about balancing competing factors like sensing quality, incentive cost, energy consumption, and location privacy.
- Location privacy is a major hurdle: While theoretical solutions exist, bridging the gap between academia and industry in implementing user-friendly and effective privacy mechanisms remains a significant challenge.
- The need for realistic evaluation: The lack of standardized, large-scale real-world datasets hinders the robust evaluation and comparison of different MCS task allocation approaches.
Key Results
The paper does not present new experimental results but rather synthesizes findings from existing literature. It categorizes numerous studies based on their problem formulation, cost considerations, and algorithmic approaches. For instance, it highlights that greedy algorithms can achieve good empirical performance and theoretical approximation bounds (e.g., 1-1/e for submodular functions) in many scenarios, but non-greedy approaches are necessary for more complex or non-submodular problems. The paper also summarizes the characteristics of these studies in a table, providing a valuable resource for researchers.
Limitations and Future Work
The authors acknowledge several limitations and propose promising future research directions:
- Sustainable MCS Task Allocation: Moving beyond short-term task allocation to address long-term sensing needs, requiring continuous investment models, improved participant experience, and gradual MCS penetration strategies.
- Behavioral Models: Incorporating more sophisticated models of user behavior, including predicting task acceptance likelihood and leveraging contextual factors for better task assignment.
- Hybrid MCS Task Allocation: Developing strategies that effectively combine participatory and opportunistic participation modes to balance sensing quality and cost.
- Considering Data Sharing Among Multiple Tasks: Exploring scenarios where sensing results from one task can be leveraged for another, especially given the limited sensor types on mobile devices.
- Social-Network-Assisted MCS Task Allocation: Investigating how to leverage social networks for worker recruitment and task allocation, adapting existing propagation models to MCS-specific factors.
- Composite MCS Task Allocation: Addressing the complexity of tasks that require collaboration among multiple participants due to varying sensor capabilities or privacy preferences.
- Location-Privacy-Concerned MCS Task Allocation: Bridging the gap between theoretical privacy solutions and practical implementation, focusing on user-friendly mechanisms and public education.
- Task Allocation for Sparse MCS: Developing methods to infer missing data in un-sensed regions and designing task allocation strategies that optimize data inference quality, rather than just coverage.
- Task Allocation for Indoor MCS: Extending existing approaches, primarily designed for outdoor scenarios, to address the growing importance of indoor MCS applications for management, security, and surveillance.
Summary updated