Destination-Aware Time-Constrained Task Allocation in Mobile Crowdsensing for Orienteering Application

Orienteering, a sport that combines navigation with running, requires efficient route planning and real-time decision-making, which can benefit significantly from mobile crowdsensing (MCS) technologies. MCS enables the platform to provide data-based service by incentivizing mobile users to perform sensing tasks and gathering sensing data from them. An extremely important problem in MCS is how to achieve effective task allocation in the context of participatory sensing, where mobile users are selectively recruited to perform tasks. However, most current work in this aspect does not consider the condition where multiple time constraints coexist, but models the problem from a single time constraint. Moreover, only a very small number of studies have paid attention to the characteristics of user destinations. Therefore, according to the shortcomings of the above research, we propose a multi-time-constrained task allocation based on origin-destination users (TAOD) problem in MCS for orienteering application, which is proved to be NP-hard. In order to solve the TAOD problem, we firstly design a path reconnection algorithm based on double-ended priority queue (PR-DEPQ) for the single-user scenario. Then, we extend the PR-DEPQ to multi-user task allocation scenario and present a multi-user path reconnection algorithm based on sensing value priority (MUPR). Extensive simulation results show the higher performance of our proposed MUPR as compared with the existing baseline algorithms.