Two-Sided Online Task Assignment Based on Worker Portraits in Mobile CrowdSensing
Zhenyang Mao, Peng Li, Guangzhong Liao, Lei Nie, Haizhou Bao, Qin Liu · 2024
Task assignment is a challenging problem in mobile crowdsensing (MCS), especially since workers and tasks are online. Existing work does not consider the portrait of the workers when assigning tasks, which may result in workers being assigned to fields they are not familiar with, thus affecting the quality of task completion. In this paper, we focus on online scenarios and identify a more practical task assignment problem, a two-sided (workers and tasks) online task assignment problem based on worker portrait in MCS. We decompose this problem into two subproblems: the worker portrait analysis problem (WPA) and the two-sided online personalized assignment problem (TOPA). To solve the WPA problem, we propose a worker portrait analysis algorithm that uses the semi-supervised model to describe the worker portrait at a fine-grained level. Then, based on the worker portrait, we propose a two-sided online personalized assignment algorithm to solve the TOPA problem. The proposed algorithm guarantees a lower bound on the assignment results by analyzing the worker portrait data. Moreover, we prove the TOPA problem is NP-hard and demonstrate the competitive ratio can achieve ln(max(ui,j)+1). Finally, we conduct extensive experiments on two datasets, and the experimental results show that our method outperforms baseline algorithms.