PaperlayerView exact revision on arXiv

Source-linked AI summary

ActiveCrowd: A Framework for Optimized Multi-Task Allocation in Mobile Crowdsensing Systems

Bin Guo, Yan Liu, Wenle Wu, Zhiwen Yu, Qi Han

arXiv:1608.02661v1cs.HC

TL;DR

Large-scale MCS platforms need worker selection for concurrent heterogeneous tasks, beyond the predominantly single-task focus of prior approaches. ActiveCrowd formulates intentional- and unintentional-movement allocation and solves them with GGA-I and GGA-U. Experiments on D4D show that the algorithms outperform baselines in effectiveness and efficiency.

  • Problem

    Existing worker-selection approaches are mostly single-task oriented, leaving multi-task allocation for concurrent heterogeneous tasks on large-scale MCS platforms insufficiently addressed.

  • Method

    ActiveCrowd formulates worker selection for intentional movement in time-sensitive tasks and unintentional movement in delay-tolerant tasks using GGA-I and GGA-U.

  • Results

    Experiments on the D4D dataset with 50,000 users report that the algorithms outperform baselines in effectiveness and efficiency.

  • Takeaways & Limitations

    The framework supports multi-task worker allocation across two common movement situations in MCS environments.

Abstract

from arXiv · show

Worker selection is a key issue in Mobile Crowd Sensing (MCS). While previous worker selection approaches mainly focus on selecting a proper subset of workers for a single MCS task, multi-task-oriented worker selection is essential and useful for the efficiency of large-scale MCS platforms. This paper proposes ActiveCrowd, a worker selection framework for multi-task MCS environments.

I. INTRODUCTION

ActiveCrowd addresses multi-task worker selection in large-scale MCS platforms, where concurrent heterogeneous tasks require system-level allocation beyond predominantly single-task approaches. It distinguishes intentional movement for time-sensitive tasks from routine movement for delay-tolerant tasks and proposes greedy-enhanced genetic algorithms, which outperform baselines in experiments.

  • Research gap: Existing worker-selection studies are mostly single-task oriented and do not address concurrent heterogeneous tasks on large-scale MCS platforms.The paper identifies platform-oriented allocation as requiring additional system-level parameters.
  • Motivation: Multi-task allocation can improve resource efficiency by assigning several location-dependent tasks to one worker along a travel route.Workers may also undertake multiple tasks to gain associated rewards.
  • Task scenarios: Time-sensitive tasks require intentional movement to designated venues, whereas delay-tolerant tasks can be assigned to workers visiting venues during daily routines.The scenarios include emergency information collection and longer-term sensing during ordinary mobility.
  • Proposed framework: ActiveCrowd is a framework for multi-task allocation that studies intentional-movement and unintentional-movement worker selection.These correspond respectively to time-sensitive and delay-tolerant tasks.
  • Methods: Two greedy-enhanced genetic algorithms, GGA-I and GGA-U, are proposed for optimal allocation in the two multi-task settings.The algorithms target intentional and unintentional worker movement, respectively.
  • Evaluation: Experiments on the D4D mobile-phone usage dataset with 50,000 users show that the algorithms outperform baselines in effectiveness and efficiency.The result is reported for both allocation settings.

II. RELATED WORK

Prior MCS platforms support task publishing and data collection, while optimized multi-task allocation has received limited attention. ActiveCrowd targets multi-task worker selection by incorporating temporal factors and workers’ spatial movement constraints for two task-movement situations.

  • MCS platforms: General-purpose MCS platforms publish and manage sensing tasks, but workers typically decide which tasks to complete rather than being matched and selected.The paper contrasts this with optimized multi-task allocation, which has not received attention on those platforms.
  • Existing selection research: Earlier worker-selection studies consider factors including sensor availability, privacy, social relations, geography, time, incentives, and quality-of-information requirements.These approaches address individual selection or related allocation objectives.
  • Multi-task research: Very few studies address multi-task worker selection for concurrent tasks under constraints such as total budget, platform rewards, sensing cost, or probabilistic coverage.The cited studies pursue different optimization objectives for multiple tasks.
  • ActiveCrowd: ActiveCrowd allocates location-based tasks while considering temporal factors and workers’ spatial movement constraints.It studies intentional movement for time-sensitive tasks and unintentional movement for delay-tolerant tasks.
  • Approach: The framework formulates the two worker-selection problems and addresses them with two greedy-enhanced genetic algorithms.The algorithms correspond to the two movement situations.

B. The ActiveCrowd Framework

ActiveCrowd classifies MCS tasks by urgency, clusters adjacent tasks within each category, and applies separate greedy-enhanced genetic algorithms to select workers. For time-sensitive tasks, the formulation uses worker and venue locations, Manhattan travel distance, assignment limits, and task coverage constraints.

  • Framework workflow: Tasks are classified as time-sensitive or delay-tolerant, then adjacent tasks are clustered by publishing time and venue.Separate worker-selection algorithms are applied to the two task categories.
  • Framework workflow: The framework uses GGA-I for time-sensitive tasks and GGA-U for delay-tolerant tasks.The two algorithms correspond to intentional and unintentional worker movement, respectively.
  • Time-sensitive formulation: WSTS models task locations, required worker counts, worker locations, and a maximum q on the number of tasks assigned to one worker.Selected workers are required to travel specifically to designated task venues.
  • Time-sensitive formulation: Manhattan distance between worker or task locations measures travel through city blocks.Locations are represented by latitude and longitude, and the distance uses coordinate-wise absolute differences.
  • Time-sensitive formulation: The formulation assigns task sets to workers, limits each worker to at most q tasks, and enforces required worker counts for tasks.These constraints define the combinatorial allocation problem.
  • Optimization complexity: Because the WSTS solution space grows with the numbers of workers, task capacity, and tasks, heuristic solutions are used.The paper states that the problem is NP-complete and has a large solution space.

B. The NearestFirst algorithm

NearestFirst greedily assigns tasks to nearby workers, while GGA-I improves this baseline through heuristic genetic search over feasible assignment matrices.

  • B. The NearestFirst algorithm: NearestFirst repeatedly assigns the task-worker tuple with the smallest Manhattan distance, updating remaining task demand, worker loads, and distances.Tasks are removed when sufficiently staffed, and workers are removed after reaching the task limit q.
  • B. The NearestFirst algorithm: Because NearestFirst makes locally best choices, it is usually sub-optimal for the large combinatorial worker-selection space.Genetic algorithms are introduced to seek better solutions at relatively low computation cost.
  • C. The GGA-I Algorithm: GGA-I initializes its genetic population from the NearestFirst result rather than random solutions because the search space is huge and the greedy result is closer to optimal.Individuals are then evolved through selection, crossover, and mutation.
  • C. The GGA-I Algorithm: GGA-I represents assignments as an m×n worker-task matrix with binary entries, enforcing task feasibility by columns and worker feasibility by rows.Each column must provide the required workers, while each row cannot exceed q assignments.
  • C. The GGA-I Algorithm: GGA-I minimizes total worker travel distance, using each assignment scheme’s total distance to evaluate and rank individuals.Lower-unfitness individuals have greater chances of forming later generations.
  • C. The GGA-I Algorithm: GGA-I exchanges same-index columns during crossover to preserve task feasibility and changes binary assignments during mutation while validating both feasibility constraints.Crossover additionally reselects rows when needed to maintain worker feasibility; mutation replaces a selected assignment and adds another in the same task column.

V. WORKER SELECTION FOR DELAY-TOLERANT TASKS

For delay-tolerant tasks, ActiveCrowd profiles worker mobility and selects workers whose usual routes are likely to cover task locations, reducing worker burden.

  • V. WORKER SELECTION FOR DELAY-TOLERANT TASKS: WSDT allocates delay-tolerant tasks to workers whose routes are likely to pass the task locations.Its two phases are worker mobility profiling and optimal worker selection.
  • V. WORKER SELECTION FOR DELAY-TOLERANT TASKS: Worker mobility profiling uses historical location records and statistical movement patterns to estimate whether a worker will pass a task location within 24 hours.The approach uses location-record statistics rather than a more complex mobility prediction method.
  • V. WORKER SELECTION FOR DELAY-TOLERANT TASKS: A task can be assigned to worker w only when the estimated passing probability p(w, t) exceeds the threshold Rthld.The threshold filters assignments according to predicted route coverage.

B. Problem Formulation

WSDT selects a small worker set that covers all tasks under worker-capacity and mobility-probability constraints, then uses greedy and genetic methods for its NP-complete optimization.

  • B. Problem Formulation: WSDT models tasks, required worker counts, candidate workers, selected workers, and each worker’s assigned task set.The formulation uses Eqs. (7)–(9) to express the optimization problem.
  • B. Problem Formulation: The objective minimizes the selected worker set while assigning enough workers to every task.The supplied objective expression is incomplete, but the surrounding formulation identifies minimum worker selection as the goal.
  • B. Problem Formulation: Constraint (8) requires each task to receive its needed number of workers.This is the task-coverage requirement in the formulation.
  • B. Problem Formulation: Constraint (9) requires assigned workers to have task-passing probability at least Rthld.The constraint links feasible assignments to predicted worker mobility.
  • B. Problem Formulation: WSDT is NP-complete by reduction from Set Cover, and its large solution space motivates greedy and enhanced genetic algorithms.The paper explicitly connects computational complexity with the choice of solution methods.
  • B. Problem Formulation: The utility function f(WS) is the union of tasks completed by workers in WS and is non-negative, monotone, and submodular.The formulation parallels minimum-cost coverage while targeting a small worker set and reduced incentive cost.
  • C. The MostFirst Algorithm: MostFirst greedily selects the worker who can accomplish the most currently coverable tasks, removing tasks once they have enough workers.It computes p(w, t), counts qualifying tasks per worker, and iterates until no tasks remain.
  • C. The MostFirst Algorithm: MostFirst is sub-optimal, although its result can serve as a basis for other methods.The paper presents it as a heuristic rather than an exact optimizer.

D. The GGA-U Algorithm

GGA-U applies a genetic algorithm to delay-tolerant worker selection, using binary worker-selection vectors, MostFirst initialization, and evolutionary operators.

  • D. The GGA-U Algorithm: GGA-U addresses WSDT’s combinatorial search by applying a genetic algorithm whose workflow follows GGA-I.The algorithm is designed to improve on the MostFirst heuristic.
  • D. The GGA-U Algorithm: A WSDT solution is represented as a binary vector, where each element indicates whether a candidate worker is selected.The vector dimension equals the number of selectable workers.
  • D. The GGA-U Algorithm: GGA-U initializes every individual from MostFirst and perturbs vector elements to create the initial population.This uses the greedy solution as the population starting point.
  • D. The GGA-U Algorithm: The minimized objective is the total number of selected workers, and individuals with more selected workers receive greater unfitness.Large-unfitness individuals are more likely to be eliminated during selection.
  • D. The GGA-U Algorithm: GGA-U creates children by swapping pieces of two parent vectors during crossover.The crossover operation is illustrated in Fig. 5.
  • D. The GGA-U Algorithm: Mutation randomly changes selected vector elements to their opposite values.Together with selection and crossover, mutation supplies variation during evolution.

VI. EVALUATION AND DISCUSSION

The evaluation uses the D4D mobility dataset and examines ActiveCrowd algorithms under varying task, worker, and spatial-distribution settings. It compares effectiveness, efficiency, completion time, mobility prediction, and selected-worker counts against baselines.

  • Experimental settings: The evaluation studies how task and worker counts, task distributions, and algorithmic baselines affect worker selection.The three task distributions are compact, scattered, and hybrid; baselines include GA, EA, and GYPSO.
  • Experimental settings: Experiments use D4D, a real-world dataset containing over 50,000 Orange Group customers’ call records from two weeks in Ivory Coast.The study mainly uses records from Abidjan, where 347 of 1,231 cell towers are located.
  • Experimental settings: WSTS experiments assign each task 2–4 workers, cap each worker at 3 tasks, and assume a worker speed of 70 meters per minute.Task locations are randomly distributed among cell towers within a target area.
  • Evaluation metrics: WSDT predicts whether workers pass task locations within the next 24 hours using their latest 10-day call records.A worker is considered able to accomplish a task when the next day’s call records place her under the task’s cell tower.
  • Evaluation metrics: For WSTS, evaluation emphasizes total movement distance, computation complexity, and average task completion time.For WSDT, it examines mobility-prediction accuracy, task completion ratio, and the number of selected workers.

C. Evaluation of GGA-I

GGA-I is evaluated for multi-task worker selection by comparing movement distance, computation complexity, scalability, and completion time with baseline and optimal methods. It achieves near-optimal distance with better efficiency than exhaustive enumeration and shorter completion times than the heuristic baselines.

  • Effectiveness: GGA-I’s total selected-worker distance is close to EA’s optimal solution and outperforms NearestFirst and GYPSO.It also performs much better than GA, which supports the usefulness of heuristic inputs.
  • Efficiency: EA minimizes total distance but its computation complexity grows rapidly with candidate-worker count, whereas GGA-I offers better solutions than the other efficient baselines.The evaluation concludes that GGA-I balances effectiveness and efficiency.
  • Scalability: GGA-I’s computation complexity does not increase dramatically as task and worker counts grow, despite an exponentially growing solution space.This supports efficient worker selection when many tasks execute concurrently.
  • Candidate-worker scaling: As candidate-worker count increases, total distance decreases slowly while the average number of tasks assigned per worker falls.The results indicate that a reasonable candidate-worker scale is sufficient for a given task set.
  • Completion time: GGA-I achieves shorter average task completion times than NearestFirst, GA, and GYPSO under different task counts.The paper attributes this result mainly to GGA-I’s least total movement distance.

D. Evaluation of GGA-U

GGA-U is evaluated through mobility-probability accuracy and selected-worker counts across compact, scattered, and hybrid task distributions. It selects fewer workers than MostFirst, especially with a lower passing threshold, without significant impact on predicted and practical probabilities.

  • Evaluation design: The evaluation first validates mobility profiling and then tests worker selection under different task distributions and passing thresholds.It also compares GGA-U with MostFirst on selected-worker counts.
  • Selected-worker evaluation: GGA-U outperforms MostFirst in the number of selected workers across compact, scattered, and hybrid task distributions.The experiments use 20 tasks, two Rthld values, and three task sets for each distribution.
  • Threshold effects: Lowering Rthld decreases the number of selected workers because more worker options become available.This establishes the threshold’s direct effect on worker-pool flexibility and selection size.
  • Threshold effects: Increasing Rthld does not substantially improve predicted or practical probability.A relatively low threshold can therefore reduce selected-worker counts without significantly affecting task completion ratio.
  • Task distributions: Compact task distributions require the fewest selected workers, while scattered distributions require more because tasks are less likely to co-occur along workers’ routes.Hybrid distributions fall between these spatial patterns in the reported comparison.

VII. DISCUSSIONS

The discussion identifies scope boundaries and future extensions for ActiveCrowd, including unsupported task types, optimization factors, alternative methods, worker expertise, and larger-scale evaluation.

  • Heterogeneous tasks: ActiveCrowd currently addresses one-shot tasks, while recurrent sampling tasks remain outside its intentional worker-selection framework.The authors plan to extend ActiveCrowd to recurrent tasks in future work.
  • Optimization goals: The current optimization goals minimize either total worker distance or worker-set size, excluding incentives and budget.The authors identify incentives and budget as important factors for future work.
  • Methods for worker selection: The proposed greedy-enhanced genetic algorithms are effective and efficient, but other advanced and theoretically founded optimization methods remain future work.Submodularity is identified as a possible direction for combinatorial optimization.
  • Worker profiling: Worker profiling could incorporate expertise and experience, but obtaining these attributes introduces additional constraints and may require time-consuming social-media mining.Profiles may come from worker-provided information or inferred user-generated data.
  • Large-scale user study: The evaluation uses a real-world human mobility dataset, while city-level deployment and large-scale user studies remain planned.The planned platform would support reports on municipal problems and urban dynamics.
  • Conclusion: ActiveCrowd studies intentional- and unintentional-movement worker selection for time-sensitive and delay-tolerant tasks using GGA-I and GGA-U.The conclusion frames these as two common multi-task MCS situations.
  • Conclusion: Compared with GA, EA, and GYPSO, the proposed algorithms better meet optimization needs efficiently and outperform basic greedy and GA methods across circumstances.The conclusion reports consistent superiority over the basic greedy algorithm and GA under various circumstances.

APPENDIX

The appendix defines the selected-worker utility function and provides a proof of its structural properties, followed by author biographies.

  • Utility function: The utility function f(WS) represents the union of tasks completed by the selected worker set and is non-negative, monotone, and submodular.These properties are stated as assumptions or characteristics of the worker-set utility.
  • Proof: The proof establishes monotonicity from worker-set inclusion and submodularity from diminishing task gains when adding a worker to a larger set.It compares marginal task increases for nested worker sets.
  • Author biographies: The appendix includes biographies identifying the authors’ affiliations, academic backgrounds, and research interests in mobile crowd sensing, ubiquitous computing, and HCI.The biographies cover Bin Guo, Yan Liu, Wenle Wu, Zhiwen Yu, and Qi Han.
Loading 1608.02661v1…