Abstract

Task allocation is a fundamental research issue in mobile crowd sensing. While earlier research focused mainly on single tasks, recent studies have started to investigate multi-task allocation, which considers the interdependency among multiple tasks. A common drawback shared by existing multi-task allocation approaches is that, although the overall utility of multiple tasks is optimized, the sensing quality of individual tasks may become poor as the number of tasks increases. To overcome this drawback, we re-define the multi-task allocation problem by introducing task-specific minimal sensing quality thresholds, with the objective of assigning an appropriate set of tasks to each worker such that the overall system utility is maximized. Our new problem also takes into account the maximum number of tasks allowed for each worker and the sensor availability of each mobile device. To solve this newly defined problem, this paper proposes a novel multi-task allocation framework named MTasker. Different from previous approaches which start with an empty set and iteratively select task-worker pairs, MTasker adopts a descent greedy approach, where a quasi-optimal allocation plan has evolved by removing a set of task-worker pairs from the full set. Extensive evaluations based on real-world mobility traces show that MTasker outperforms the baseline methods under various settings, and our theoretical analysis proves that MTasker has a good approximation bound.

Department(s)

Computer Science

Comments

National Natural Science Foundation of China, Grant 2017YFB1002000

Keywords and Phrases

Mobile crowd sensing; multi-task allocation; sensing quality; submodular optimization

International Standard Serial Number (ISSN)

1536-1233

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2024 Institute of Electrical and Electronics Engineers, All rights reserved.

Publication Date

01 Sep 2018

Download

Full Text Link

Share

 
COinS