PaperlayerView exact revision on arXiv

Source-linked AI summary

Task Allocation in Mobile Crowd Sensing: State of the Art and Future Opportunities

Jiangtao Wang, Leye Wang, Yasha Wang, Daqing Zhang, Linghe Kong

arXiv:1805.08418v2cs.HC

TL;DR

MCS task allocation matters because worker-selected tasks can leave sensing uneven, while server assignment can pursue system goals such as sensing quality under budget constraints. This article reviews MCS-specific allocation features, problem formulations, and algorithms, and identifies future research directions. It concludes that MCS allocation requires consideration of distinct costs and benefits and discusses emerging approaches such as hybrid and social-network-assisted allocation.

Abstract

from arXiv · show

Mobile Crowd Sensing (MCS) is the special case of crowdsourcing, which leverages the smartphones with various embedded sensors and user's mobility to sense diverse phenomenon in a city. Task allocation is a fundamental research issue in MCS, which is crucial for the efficiency and effectiveness of MCS applications. In this article, we specifically focus on the task allocation in MCS systems. We first present the unique features of MCS allocation compared to generic crowdsourcing, and then provide a comprehensive review for diversifying problem formulation and allocation algorithms together with future research opportunities.

I. INTRODUCTION

Mobile crowd sensing uses mobile devices, embedded sensors, and user mobility to collect urban data, but task assignments can leave sensing unevenly distributed. This article reviews MCS task allocation because existing broad MCS surveys do not systematically cover it.

  • MCS combines mobile users, phone sensors, and communication infrastructure to collect urban sensing data across diverse applications.Source: §I · p. 1
  • Pull-mode workers choose tasks by their own preferences, which can leave some tasks undersampled and others redundantly sensed.Source: §I · p. 1
  • Prior MCS surveys provide broad field overviews but do not systematically review sensing task allocation, motivating this focused review.Source: §I · p. 1
  • The article examines MCS-specific features, summarizes task-allocation formulations and algorithms, and identifies future research directions.Source: §I · pp. 1–2

II. PRELIMINARY FOR MOBILE CROWD SENSING

Mobile crowd sensing is a crowdsourcing paradigm in which users collect and contribute data through sensor-rich mobile devices. The article places task allocation within the MCS life-cycle and focuses on its distinctive features, formulations, algorithms, and research opportunities.

A. Crowdsourcing and Mobile Crowd Sensing

B. Life-Cycle of MCS and Research Issues

III. SPECIFIC FACTORS IN MCS TASK ALLOCATION

MCS task allocation shares concerns such as incentives and budgets with general crowdsourcing, but mobility and sensing introduce additional constraints. These include location-dependent participation, location privacy, spatial-temporal quality measures, energy use, and device-specific sensor requirements.

A. Overview

  • MCS shares incentive and budget concerns with general crowdsourcing, while its mobility and sensing requirements create distinct allocation factors.Source: A. Overview · p. 2
  • Because sensing results depend on location, MCS allocation accounts for participation modes, location privacy, and spatial-temporal quality measures.Source: A. Overview · pp. 2–3
  • Phone sensing and localization consume energy, and differing device sensor sets make sensor-type requirements relevant to task assignment.Source: A. Overview · p. 3

B. Worker-Side Factors.

Worker-side allocation choices trade off task completion, cost, intrusiveness, privacy, and energy consumption. The section describes participatory and opportunistic modes, location privacy, and energy-aware allocation.

Workers’ Participation Mode

  • Participatory workers travel to assigned locations, supporting task completion but adding travel and incentive costs; opportunistic workers use routine routes, with sensing quality dependent on those trajectories.Source: B. Worker-Side Factors · p. 3

Location Privacy

  • Location obfuscation can make uploaded positions uncertain and distances to tasks imprecise, creating an allocation-efficiency trade-off for privacy protection.Source: B. Worker-Side Factors · p. 3

Energy Consumption

  • Task allocation can account for workers’ energy consumption in addition to methods that reduce energy during sensing and data uploading.Source: B. Worker-Side Factors · p. 3

C. Organizer-Side Factors

The review organizes MCS task allocation around sensing quality, costs, and other optimization goals and constraints. It describes how spatial and temporal structure shapes sensing quality and the formulation of allocation problems.

C. Organizer-Side Factors

  • MCS quality models capture spatial-temporal structure by dividing an area and period into cells or by modeling points of interest with a specified range.The cited examples use equal-size subareas and time slots, or POIs with a range [55,56,57,58].Source: C. Organizer-Side Factors · pp. 3–4
  • MCS sensing quality is measured either by spatial-temporal coverage or by error when inferring data for areas without sensor readings.Coverage may require a minimum sample threshold; inference metrics include average inference error for continuous values and average classification error for categorical values.Source: C. Organizer-Side Factors · p. 4

IV. PROBLEM FORMULATION IN MCS TASK ALLOCATION

  • MCS allocation is formulated as mathematical optimization with varied goals and constraints, and the review classifies research from several perspectives.Fig. 3 presents the classification of problem formulations.Source: §IV · p. 4, Figure 3 · p. 4

A. Benefit and Cost

  • Benefit is sensing quality, while cost includes overheads such as incentives, location-privacy risk, and energy consumption.The review classifies existing work by the cost types included in its optimization problems.Source: A. Benefit and Cost · p. 4
  • Maximizing sensing quality by assigning more workers can raise incentive costs, so studies either maximize quality under a budget or minimize cost while meeting a quality threshold.The cited examples include for quality maximization under budget constraints and for cost minimization with a minimum quality guarantee.Source: A. Benefit and Cost · p. 4
  • Task allocation can optimize system energy use alongside coverage, sensing quality, worker reputation, or budget constraints.Prior formulations include minimizing energy while maintaining required spatial-temporal coverage, and maximizing quality under an overall energy limit.Source: A. Benefit and Cost · pp. 4–5

B. Single-Objective Allocation VS Multi-Objective Allocation

MCS allocation studies vary in whether they optimize one objective or several, and whether they allocate for isolated tasks or coordinate interdependent tasks. Shared worker pools and budgets make coordination across tasks relevant as task numbers grow.

B. Single-Objective Allocation VS Multi-Objective Allocation

  • Single-objective formulations optimize one goal while treating others as constraints; multi-objective formulations optimize several goals but may require organizers to choose weights when converted to a single objective.Examples of multi-objective goals include maximizing sensing quality while minimizing energy, or minimizing travel cost while maximizing completed tasks.Source: B. Single-Objective Allocation VS… · p. 5

C. Single-Task-Oriented Allocation VS Multi-Task-Oriented Allocation

  • Multi-task allocation coordinates tasks competing for shared workers or budgets, commonly maximizing their overall utility as a weighted sum of task sensing quality.Studies consider worker sensing-capability constraints or total incentive-budget constraints.Source: C. Single-Task-Oriented Allocation VS… · p. 5

D. Offline Allocation VS Online Allocation

MCS allocation may be decided before task execution or while tasks are running, with different information available in each mode. The review also describes allocation as a combinatorial search supported by utility estimation and near-optimal solution algorithms.

D. Offline Allocation VS Online Allocation

  • Offline allocation is decided before execution and avoids real-time worker locations, but depends on accurate mobility prediction; online allocation uses available real-time locations alongside mobility history.Online methods can target fewer redundant assignments while meeting participation requirements, or minimize assigned tasks while covering the target area.Source: D. Offline Allocation VS Online… · p. 5

A. General Framework

  • MCS allocation searches combinations of workers or worker-task pairs, but these problems are usually NP-hard, making brute force unsuitable for large worker or task sets.Existing work commonly uses approximation algorithms to seek near-optimal solutions.Source: A. General Framework · p. 5
  • The framework estimates a candidate set’s utility using worker mobility profiling and prediction, then searches for a near-optimal solution with greedy or non-greedy algorithms.Fig. 4 depicts these two components: utility estimation and the searching process.Source: A. General Framework · p. 5, Figure 4 · p. 5

B. Greedy Based Algorithms

Greedy allocation is common, but its theoretical guarantees depend on the utility function and constraints. Because greedy choices can be suboptimal in some settings, the review also describes alternative search strategies.

B. Greedy Based Algorithms

  • Most reviewed MCS studies use greedy algorithms that iteratively add the best worker or worker-task pair until a stopping condition is met [34,35,43,44,50,51, 52].Stopping conditions include exhausting the budget, reaching required coverage, or having no further assignable workers.Source: B. Greedy Based Algorithms · p. 6
  • For submodular utility functions with cardinality constraints, greedy methods have a 1-1/e (≈0.63) approximation bound; non-submodular formulations in lack a declared strict bound.The review identifies theoretical guarantees for greedy optimization of non-submodular functions as a future research question.Source: B. Greedy Based Algorithms · p. 6

C. Non-Greedy Algorithms

  • Because greedy algorithms can be suboptimal when selecting the local best at each step, reviewed alternatives include genetic algorithms, flow and graph methods, dynamic programming, branch-and-bound, and bisection.The examples include GA for time-sensitive and time-tolerant allocation, MCMF-based algorithms [33], and divide-and-conquer graph partitioning and.Source: C. Non-Greedy Algorithms · p. 6

D. Algorithm Evaluation

Evaluation commonly compares algorithms with baselines across varying settings, but public real-world datasets are lacking. The paper identifies sustainable allocation as an open direction, with long-term spending, participation, uptake, and environmental costs among the issues to address.

D. Algorithm Evaluation

  • Public real-world datasets are absent, so evaluations use real mobility traces alongside commonly synthetic task information.D4D includes cell-tower information and 50,000 users’ phone-call records in Ivory Coast; a synthetic-data toolbox is cited as supporting reproducible experiments.Source: D. Algorithm Evaluation · p. 6
  • Table 1 summarizes each analyzed study’s problem formulation and allocation algorithm to help readers identify relevant papers.Source: D. Algorithm Evaluation · p. 6, Table 1 · p. 7

VI. FUTURE RESEARCH OPPORTUNITIES AND PROPOSALS

  • The gap between ideal problem settings and real-world applications is identified as a barrier to wider MCS deployment.Source: §VI · p. 6

A. Sustainable MCS Task Allocation.

  • Long-term sensing calls for continuous spending models, attention to participant experience, and modeling MCS penetration as gradual.The paper also identifies green allocation, including green energy, less redundant information, and reduced human cost.Source: A. Sustainable MCS Task Allocation · pp. 7–8

B. Behavioral Models for Improving Task Allocation.

The section proposes richer behavioral prediction to guide MCS task allocation and a hybrid approach combining opportunistic and participatory workers. The hybrid may balance workers’ participation preferences with sensing quality and cost, but jointly optimizing the two worker types remains challenging.

B. Behavioral Models for Improving Task Allocation.

  • Predicting task acceptance and context-linked sensing quality can guide assignment, while boredom detection may reveal workers’ contextual cognitive surplus.The proposed quality classifier relates context such as participant motion to sensing-data quality.Source: B. Behavioral Models for Improving… · p. 8

C. Hybrid MCS Task Allocation

  • Hybrid allocation pairs opportunistic workers on routine trajectories with participatory workers sent to uncovered locations, balancing participation preferences, sensing quality, and incentive cost.Opportunistic workers can reduce incentive costs, while participatory workers can improve sensing quality in locations they do not cover.Source: C. Hybrid MCS Task Allocation · p. 8
  • Jointly optimizing opportunistic and participatory workers remains an open challenge when their allocations are correlated, such as through a shared incentive budget.Source: C. Hybrid MCS Task Allocation · p. 8

D. Considering Data Sharing Among Multiple Tasks.

The section identifies opportunities to extend MCS allocation beyond competing tasks and specialized platforms, addressing inter-task data sharing, social-network recruitment, composite sensing tasks, and location privacy.

D. Considering Data Sharing Among Multiple Tasks.

  • MCS allocation can account for sensing data shared across tasks, rather than treating workers as resources that one task’s assignment makes unavailable to others.For example, GPS and accelerometers used for queue-time estimation can be shared with noise monitoring, which also uses GPS.Source: D. Considering Data Sharing Among… · p. 8

E. Social-Network-Assisted MCS Task Allocation

  • Social networks could recruit MCS workers where large specialized-platform user pools are unavailable, but propagation models need MCS-specific factors such as incentive appeal and task-topic interest.Source: E. Social-Network-Assisted MCS Task… · p. 8

F. Composite MCS Task Allocation

  • Composite tasks such as air-quality monitoring require collaboration because participants may each provide only a subset of the sensors needed for a complete sample.The paper identifies collaborative allocation for such tasks as an important future research direction.Source: F. Composite MCS Task Allocation · pp. 8–9

G. Location-Privacy-Concerned MCS Task Allocation

  • A gap remains between proposed privacy protection and its use in MCS applications; suggested directions include understandable mechanisms, public education, and business guidelines or regulations.Source: G. Location-Privacy-Concerned MCS Task… · p. 9

H. Task Allocation for Sparse MCS

The section outlines future allocation research for sparse and indoor MCS, within a survey of MCS task-allocation formulations, algorithms, and open directions.

H. Task Allocation for Sparse MCS

  • Sparse MCS allocation must account for how sensing choices affect missing-data inference, but evaluating inference quality without ground truth and incorporating incentives remain challenges.Matrix completion and compressive sensing are used to infer missing data in the described paradigm.Source: H. Task Allocation for Sparse MCS · p. 9

I. Task Allocation for Indoor MCS.

  • Indoor MCS applications such as floor-plan reconstruction and indoor navigation motivate allocation that jointly considers incentive cost and inference accuracy.Source: §I · p. 9

VII. CONCLUSION

  • The article surveys MCS task allocation’s distinctive characteristics, classifies research by problem formulation or allocation algorithm, and identifies future research directions.Source: §VII · p. 9
Loading 1805.08418v2…