TL;DR
This paper provides a comprehensive survey of the state-of-the-art in task allocation for Mobile Crowd Sensing (MCS). It highlights the unique challenges of MCS compared to general crowdsourcing, categorizes existing problem formulations and algorithms, and outlines promising future research directions.
What Problem Does This Paper Address?
Urban sensing, the process of collecting data about city environments (e.g., air quality, traffic), is increasingly relying on Mobile Crowd Sensing (MCS). MCS leverages the sensors and mobility of everyday smartphones to gather this data. A critical component for the success of MCS applications is task allocation: efficiently assigning sensing tasks to mobile users (workers). Traditional crowdsourcing task allocation methods are often insufficient for MCS due to its unique characteristics, such as the need for workers to be in specific locations, privacy concerns, and the impact of mobility and energy consumption on participation. This paper aims to bridge this gap by systematically reviewing the existing research on MCS task allocation, identifying its unique features, and proposing future research avenues.
Methods
The paper categorizes MCS task allocation research based on several dimensions:
- Problem Formulation:
- Benefit and Cost: Balancing sensing quality (benefit) against factors like incentive cost, location privacy, and energy consumption (cost).
- Single-Objective vs. Multi-Objective: Optimizing for a single goal (e.g., maximizing coverage) versus multiple goals simultaneously.
- Single-Task vs. Multi-Task: Allocating tasks independently versus considering the interdependencies between multiple tasks.
- Offline vs. Online Allocation: Determining task assignments before execution versus dynamically during execution.
- Allocation Algorithms:
- Greedy-Based Algorithms: Iteratively selecting the "best" worker or task-worker pair until a stopping criterion is met. These are common due to their empirical effectiveness, especially for submodular utility functions.
- Non-Greedy Algorithms: Employing more sophisticated techniques like genetic algorithms, minimum cost maximum flow, and bipartite graph partitioning to find near-optimal solutions, particularly when utility functions are non-submodular or problems are complex.
The paper also discusses the importance of utility estimation, which involves profiling and predicting worker mobility, and the searching process for finding optimal solutions.
Datasets
The paper notes that a significant challenge for evaluating MCS task allocation algorithms is the lack of public, real-world datasets. Existing work often relies on:
- Real-world mobility datasets: Such as the D4D dataset (containing cell tower information and phone call records) and Gowalla.
- Synthetic datasets: Generated using tools like the one proposed in [61] to create realistic scenarios for experimentation and ensure reproducibility.
Key Insights and Ideas
- MCS is fundamentally different from generic crowdsourcing: The core distinction lies in the interplay of mobility and sensing. Workers must be physically present at specific locations, and their movement patterns are crucial.
- Location privacy is a paramount concern: Unlike traditional crowdsourcing, MCS inherently involves location data, making privacy-preserving mechanisms a unique and critical aspect of task allocation.
- Energy consumption is a major barrier to participation: High energy demands from sensing and data transmission can significantly deter users from participating in MCS, necessitating energy-aware allocation strategies.
- The "participatory" vs. "opportunistic" mode distinction is key: Workers can either actively travel to complete tasks (participatory) or complete them incidentally during their daily routines (opportunistic). Hybrid approaches that leverage both are promising.
- Task allocation is often an NP-hard problem: This necessitates the development of approximation algorithms rather than exact solutions, especially for large-scale MCS systems.
Key Results
The paper doesn't present new experimental results but rather synthesizes findings from existing literature. It highlights that:
- Greedy-based algorithms have demonstrated good empirical performance and can achieve theoretical approximation bounds (e.g., 1-1/e) for submodular utility functions.
- Various algorithms (genetic algorithms, MCMF, bipartite partitioning) have been proposed to tackle more complex MCS task allocation problems.
- The effectiveness of algorithms is typically evaluated by comparing their performance against baselines using a combination of real-world mobility data and synthetic task parameters.
Limitations and Future Work
The authors identify several limitations and propose future research directions:
- Sustainable MCS Task Allocation: Moving beyond short-term task allocation to address long-term sensing needs, requiring continuous investment models, better participant experience considerations, and gradual MCS penetration strategies.
- Behavioral Models: Incorporating more sophisticated models of user behavior, including predicting task acceptance likelihood and leveraging contextual factors like participant motion and boredom.
- Hybrid MCS Task Allocation: Developing effective strategies to jointly optimize opportunistic and participatory modes, especially when they share resources like budgets.
- Data Sharing Among Multiple Tasks: Exploring scenarios where sensing results from one task can be reused for others, particularly when sensors are limited.
- Social-Network-Assisted MCS Task Allocation: Leveraging social networks for worker recruitment and task dissemination, adapting existing propagation models to include MCS-specific factors.
- Composite MCS Task Allocation: Addressing the complexity of tasks requiring multiple sensors or subtasks, where collaboration among participants is essential.
- Location-Privacy-Concerned MCS Task Allocation: Bridging the gap between theoretical privacy mechanisms and practical user understanding and adoption, and establishing guidelines for MCS business entities.
- Task Allocation for Sparse MCS: Developing methods to infer missing data in un-sensed regions and designing allocation schemes that optimize for data inference quality rather than just coverage.
- Task Allocation for Indoor MCS: Adapting existing approaches for indoor environments, which have unique sensing and navigation applications.
Summary updated