Multi-Task Allocation in Mobile Crowd Sensing with Individual Task Quality Assurance

Jiangtao Wang, Yasha Wang, Daqing Zhang, Feng Wang, Haoyi Xiong, Chao Chen, Qin Lv, Zhaopeng Qiu

Research output: Contribution to journalArticlepeer-review

126 Citations (Scopus)


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 is 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.
Original languageEnglish
Pages (from-to)17
Number of pages9
JournalIEEE Transactions on Mobile Computing
Issue number9
Early online date15 Jan 2018
Publication statusPublished - 1 Sept 2018
Externally publishedYes


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


Dive into the research topics of 'Multi-Task Allocation in Mobile Crowd Sensing with Individual Task Quality Assurance'. Together they form a unique fingerprint.

Cite this