Maximum Profit Routing for Mobile Crowdsensing
Zhiyao Li, Jiale Zhang, Xiaofeng Gao, Guihai Chen · 2022
Wireless sensor networks and mobile crowdsensing are two important paradigms in urban dynamic sensing. In both sensing paradigms, task allocation is a significant problem that may affect the completion quality of sensing tasks. In this paper, we focus on allocating sensing tasks for mobile crowdsensing. We propose a system model to illustrate how the allocation mechanism works in crowdsensing and define the task allocation problem as maximum profit routing for mobile crowdsensing (MPRMC). The NP-hardness of MPRMC is proved based on a special case analysis. To solve MPRMC, we consider the problem in two special cases: Temporal-MPRMC and Spatial-MPRMC. Correspondingly, we propose a fully polynomial-time approximation scheme for Temporal-MPRMC and a 2Ɣ-approximation for Spatial-MPRMC, respectively. Then, we generalize the special cases and give a 2Ɣ lg2n-approximation for MPRMC. To the best of our knowledge, our algorithms have the best approximation ratios for MPRMC. Finally, we conduct various experiments to validate the effectiveness of our designs.