Time-Efficient Allocation Mechanisms for Crowdsensing Tasks with Precedence Constraints †

Crowdsensing has emerged as an efficient and inexpensive way to perform specialized tasks by leveraging external crowds. In some crowdsensing systems, different tasks may have different requirements, and there may be precedence constraints among them, such as the Unmanned Aerial Vehicle (UAV) crowdsensing systems. Moreover, minimizing the total execution time is a regular target for finishing the crowdsensing tasks with precedence constraints. As far as we know, only a few existing studies consider the precedence constraints among crowdsensing tasks, and none of them can minimize the total execution time simultaneously. To tackle this challenge, an efficient allocation mechanism for tasks with precedence constraints is first proposed, which can minimize the total execution time. Then, a case study is given to show how to fit our mechanism in the UAV crowdsensing system. Finally, the simulation results show that the proposed mechanisms have good approximate optimal ratios under different parameter settings and are efficient for the UAV crowdsensing system as well.