PaperlayerView exact revision on arXiv

Source-linked AI summary

TaskMe: Multi-Task Allocation in Mobile Crowd Sensing

Yan Liu, Bin Guo, Yang Wang, Wenle Wu, Zhiwen Yu, Daqing Zhang

arXiv:1608.02657v1cs.HC

TL;DR

Existing MCS participant-selection work is largely single-task oriented, despite large-scale platforms facing concurrent tasks, multiple objectives, and privacy concerns. TaskMe addresses these settings with bi-objective allocation methods for FPMT and MPFT, and its algorithms outperform greedy baselines on a large real-world dataset.

  • Problem

    Existing participant-selection studies mainly address single tasks and often use one objective without sufficiently considering participant-task ratios or location privacy in large-scale MCS.

  • Method

    TaskMe models FPMT with Minimum Cost Maximum Flow algorithms and MPFT with multi-objective optimization algorithms, balancing task completion or incentive payments against movement distance.

  • Results

    The proposed FPMT and MPFT algorithms outperform greedy baseline approaches in experiments using the D4D dataset of 50,000 mobile users.

  • Takeaways & Limitations

    TaskMe provides allocation mechanisms for multi-task MCS platforms with differing participant resources, bi-objective goals, and privacy-aware working areas.

  • Takeaways & Limitations

    FPMT requires calculating all possible task combinations for each participant, limiting task scale and increasing computation cost; complex constraints such as completed-task quality may also be unsupported.

Abstract

from arXiv · show

Task allocation or participant selection is a key issue in Mobile Crowd Sensing (MCS). While previous participant selection approaches mainly focus on selecting a proper subset of users for a single MCS task, multi-task-oriented participant selection is essential and useful for the efficiency of large-scale MCS platforms. This paper proposes TaskMe, a participant selection framework for multi-task MCS environments. In particular, two typical multi-task allocation situations with bi-objective optimization goals are studied: (1) For FPMT (few participants, more tasks), each participant is required to complete multiple tasks and the optimization goal is to maximize the total number of accomplished tasks while minimizing the total movement distance. (2) For MPFT (more participants, few tasks), each participant is selected to perform one task based on pre-registered working areas in view of privacy, and the optimization objective is to minimize total incentive payments while minimizing the total traveling distance. Two optimal algorithms based on the Minimum Cost Maximum Flow theory are proposed for FPMT, and two algorithms based on the multi-objective optimization theory are proposed for MPFT. Experiments verify that the proposed algorithms outperform baselines based on a large-scale real-word dataset under different experiment settings (the number of tasks, various task distributions, etc.).

INTRODUCTION

TaskMe addresses multi-task participant allocation in MCS, where concurrent tasks and varying participant availability require multiple objectives, including completion, distance, incentives, and privacy.

  • Motivation: Existing MCS platforms mainly publish tasks and collect data, leaving large-scale multi-task allocation insufficiently addressed.The paper identifies concurrent tasks from different requesters as a platform-oriented challenge.
  • Two allocation situations: TaskMe studies FPMT and MPFT according to whether tasks exceed available participants or participants exceed tasks.FPMT has few participants and many tasks; MPFT has rich participant resources and fewer tasks.
  • Bi-objective objectives: FPMT maximizes accomplished tasks while minimizing movement distance, whereas MPFT minimizes incentive payments and movement distance.FPMT assigns multiple tasks per participant, while MPFT assigns one task per participant using registered working areas for privacy.
  • Approach: The proposed FPMT algorithms use Minimum Cost Maximum Flow, while MPFT algorithms transform bi-objective optimization into single-objective optimization.The FPMT methods are MT-MCMF and MTP-MCMF; the MPFT methods are W-ILP and C-ILP.
  • Evaluation: Experiments on D4D call records from 50,000 mobile users report better performance than greedy baseline approaches.The evaluation varies settings such as task number and task distributions.

RELATED WORK

Prior MCS participant-selection research largely addresses single-task selection or different task-assignment settings, motivating TaskMe’s focus on multi-task allocation under two participant-resource situations.

  • MCS platforms: MCS platforms support location-based tasks, but participants commonly choose tasks themselves rather than being selected by the platform.This contrasts with platform-directed participant selection based on sensing purposes.
  • Single-task selection: Prior participant-selection studies select users for one task using criteria such as availability, incentive cost, or spatial coverage.These approaches do not fully utilize mobile-user resources when participants are insufficient and generally do not address privacy.
  • Multi-task allocation: Few studies address multi-task allocation, including work on makespan and quality-of-information requirements under budget constraints.The cited studies do not establish the task–participant relationship targeted in this paper.
  • Paper focus: TaskMe focuses on multi-task allocation in MCS under two typical situations and formulates two bi-objective participant-selection problems.The situations differ in the relative numbers of active participants and tasks.

TASK ALLOCATION OF FPMT PROBLEM

The FPMT problem assigns multiple location-based tasks to resource-constrained participants while balancing accomplished-task count against movement distance through an MCMF formulation.

  • Problem formulation: FPMT requires each participant to complete multiple tasks while maximizing accomplished tasks and minimizing total movement distance.Tasks may require several participants, with upper bounds to avoid redundant sensing data.
  • Problem formulation: The formulation represents participants, tasks, assigned task sets, and each participant’s total movement distance.Each participant is assigned q tasks, and task tj can be assigned to at most pj users.
  • Challenges: FPMT combines task–participant combinatorial optimization with a shortest-path problem for each participant, creating a tradeoff between its objectives.The paper proposes enumerating task combinations before solving the allocation problem.
  • MCMF transformation: The MCMF model encodes total movement distance as cost and total accomplished tasks as flow.The model requires additional nodes and constraints to represent participant task sets and task completion limits.
  • MT-MCMF: MT-MCMF enumerates task sets, computes minimum-distance routes, constructs a flow network, and repeatedly augments minimum-cost paths.Christofides is used to compute the path for each participant–task-set combination.
  • MTP-MCMF: MTP-MCMF prunes participant-to-task-set edges by selecting only some task-set nodes to reduce the flow network’s scale.The paper identifies the number of task-set nodes as a major contributor to MT-MCMF’s time complexity.

TASK ALLOCATION OF MPFT PROBLEM

MPFT allocates participants from pre-specified working areas so every task is completed by one-task-per-participant assignments while minimizing incentive payments and movement distance. The paper converts its bi-objective formulation into single-objective integer programs using linear-weight and constraint methods.

  • MPFT objectives and setting: MPFT selects participants to complete all tasks while minimizing total incentive payments and movement distance.Each participant performs one task, and participants are represented by their registered working areas rather than precise locations for privacy.
  • MPFT objectives and setting: Each task is assigned a required number of participants, with assignment variables linking working areas, participants, tasks, distances, and incentives.The formulation defines D_ij as distance between area A_i and task t_j, C_i as area-participant incentive, and x_ij as the number assigned.
  • Linear-weight formulation: The linear-weight method scales incentive and distance objectives before combining them with weights k1 and k2.Scaling is needed because incentive and distance have different dimensions; the resulting problem is solved as integer linear programming with branch-and-bound in W-ILP.
  • Algorithms: W-ILP and C-ILP solve MPFT after transforming its bi-objective formulation into single-objective optimization problems.W-ILP uses linear weights, while C-ILP uses the constraint method and branch-and-bound to obtain an optimal ILP solution.
  • Constraint formulation: The constraint method avoids directly combining differently dimensioned objectives but does not guarantee the same optimal degree as the linear-weight formulation.The paper presents it as an alternative transformation for handling MPFT’s contradictory incentive and distance objectives.

Dataset and Experiment Setups

Evaluation uses the D4D dataset to place participants and location-based tasks, with separate setups for FPMT and privacy-preserving MPFT. FPMT varies task distributions, while MPFT models six areas, randomly generated participants, incentives, and tasks.

  • Dataset: The D4D dataset contains cell-tower information and phone-call records from 50,000 users in Ivory Coast.Experiments use cell-tower locations for tasks and participant locations.
  • FPMT setup: FPMT experiments set the maximum participants per task to 6 and allow each participant to perform randomly 2–7 tasks at one time.These settings support evaluation of multi-task completion under movement-based completion-time assumptions.
  • FPMT setup: The experiments use compact, scattered, and hybrid task distributions.Compact tasks cluster within part of the user area; scattered tasks span a wider target area; hybrid tasks are randomly distributed in the user area.
  • MPFT setup: MPFT divides the city evenly into six areas and randomly assigns each area 10–100 participants with incentives between 1 and 10, inversely proportional to area population.Participant locations are represented by areas rather than precise locations to preserve privacy.
  • MPFT setup: MPFT uses 20 randomly distributed tasks, each requiring five participants to support sensing quality.The setup reflects the few-task, more-participant situation.

Baseline Methods and Evaluation Metrics

The evaluation compares TaskMe algorithms with greedy baselines for FPMT and MPFT using task completion, movement, incentive, completion-time, and runtime measures. In the reported FPMT setup, all methods reach the maximum task count, so distance becomes the comparison focus.

  • Baseline methods: MT-GrdPT is the FPMT baseline, greedily assigning each participant nearby tasks until reaching the participant’s task quota.It minimizes movement distance after maximizing the number of accomplished tasks.
  • Baseline methods: W-Grd and C-Grd are MPFT baselines based respectively on linear weighting and constraint-based greedy selection.C-Grd first selects a minimum-distance set and then adjusts assignments when the incentive budget is exceeded.
  • Evaluation metrics: FPMT evaluation measures accomplished tasks, total movement distance, average completion time for urgent tasks, and algorithm runtime.The task-count and distance indicators are the chief comparison measures.
  • Evaluation metrics: MPFT evaluation measures total participant incentive payments and total movement distance.Both metrics reflect publisher cost and travel involved in accomplishing tasks.
  • Evaluation results: In the reported FPMT experiments, all three methods reach the maximum number of accomplished tasks, making total distance the remaining comparison focus.The maximum is m×q when each of m participants performs q tasks.

Different number of tasks

The experiments evaluate FPMT allocation as task counts and participant workloads vary, and compare MPFT methods across weighted and constrained incentive–distance trade-offs. MTP-MCMF remains close to MT-MCMF with lower runtime, while ILP-based MPFT methods outperform or closely track greedy baselines under the reported settings.

  • Different number of tasks: MTP-MCMF achieves results close to MT-MCMF as the number of tasks changes, while MT-MCMF runtime increases sharply because it forms task sets from all tasks.MTP-MCMF limits task-set construction to 10 selected tasks, which keeps its runtime nearly unchanged but may lose the optimal solution.
  • Different value of k: At k=12, MTP-MCMF matches MT-MCMF in distance while taking about one-third of its runtime.MTP-MCMF can approximate MT-MCMF with an appropriate k, although restricting task sets may lose the optimal solution.
  • Different value of q: Increasing q raises total distance, and MTP-MCMF and MT-MCMF remain similar while MT-GrdPT performs worse; adjusting q can reduce completion time for urgent tasks.MT-MCMF requires more runtime than MTP-MCMF under the tested settings.
  • Different task distributions: MTP-MCMF and MT-MCMF outperform MT-GrdPT across different task distributions, while scattered tasks increase movement distance and completion time.The scattered distribution has longer inter-task distances than compact and hybrid distributions.
  • MPFT evaluation: For MPFT, increasing the incentive weight lowers incentive but raises distance, and neither objective can be minimized simultaneously.W-Grd is close to W-ILP, while C-ILP outperforms C-Grd across incentive budgets and provides uniformly distributed, controllable non-inferior solutions.

DISCUSSIONS

The discussion identifies limitations in participant diversity, constraint coverage, incentive modeling, allocation scalability, and evaluation scope. The authors outline future work to address these boundaries and test the framework in a city-level platform.

  • Diversity of participants: Participants receive equal task counts in FPMT, while MPFT participants choose tasks independently, limiting consideration of participant diversity and potentially creating contradictions.Future work will select unique participants for tasks according to individual characteristics.
  • Various constraints: The framework models two general constraints but omits other factors such as participant interests and platform budgets.The authors plan to incorporate additional constraints to improve practicality.
  • Incentive models: MPFT incentives are modeled as inversely proportional to the number of users in an area and exclude factors such as movement distance.The authors note that this may diminish participant enthusiasm for long-term participation and plan situation-specific incentive models.
  • Methods for task allocation: FPMT allocation requires calculating all possible task combinations for each participant, limiting task scale and increasing computation cost.The algorithms may also be unsuitable for complicated constraints such as completed-task quality.
  • Large-scale user study: Evaluation uses a real-world human mobility dataset with tasks distributed under different schemes and assumptions, rather than a large-scale city-level user study.The authors intend to deploy the framework in a municipal platform and conduct broader user studies.

CONCLUSION

The paper formulates two bi-objective participant-selection problems for settings with deficient or rich participant resources. It solves them with MCMF and multi-objective optimization algorithms, whose evaluations outperform baseline approaches.

  • CONCLUSION: The paper defines FPMT for deficient participant resources and MPFT for rich participant resources as two bi-objective participant-selection problems.FPMT targets accomplished tasks and travel distance, while MPFT targets incentive payments and movement distance.
  • CONCLUSION: MT-MCMF and MTP-MCMF use an MCMF model to select FPMT participants by maximizing accomplished tasks and minimizing total traveling distance.The algorithms address the deficient-participant setting.
  • CONCLUSION: W-ILP and C-ILP use a multi-objective optimization model to select MPFT participants by minimizing total incentive payments and total movement distance.The algorithms address the rich-participant setting.
  • CONCLUSION: Evaluations on a large-scale real-world dataset show that the proposed algorithms outperform baseline approaches for both problems.The conclusion reports this outcome without specifying a numerical margin.
Loading 1608.02657v1…