Online Organizing Large-Scale Heterogeneous Tasks and Multi-Skilled Participants in Mobile Crowdsensing

Online gathering large-scale heterogeneous tasks and multi-skilled participant can make the tasks and participants to be shared in real time. However, their online gathering will bring many intractable objective requirements, which makes task-participant matching become extremely complex. To cope well with the gathering, we design a hierarchy tree and time-series queue to organize tasks and participants. The data structures we designed can effectively meet all requirements that are brought due to tasks and participants gathering online. In addition, based on the designed data structures, we study online large-scale heterogeneous task allocation problem from three aspects: the computing pattern, the tree creation method, and the extension of matching strategy. Our best method (TsPY) is based on parallel computing in the computing pattern, adopts time first and then space in the tree creation method, and increases the short-distance first strategy in the matching strategy. Finally, we conducted detailed experiments under the conditions of different participant geographical distributions (i.e., uniform distribution, Gaussian distribution, and check-in empirical distribution), different sensing methods (i.e., participatory sensing and opportunistic sensing), and different recommendation methods (i.e., point recommendation and trajectory recommendation). The experimental results show that TsPY has a good performance in multiple indicators such as algorithm running time, task-participant matching rate, participant travel distance, and redundant tasks removed. Compared with serial computing, parallel computing can reduce the algorithm running time by more than 66% on average in our experimental environment. Compared with space first and then time, creating a tree based on time first and then space can increase task-participant matching rate by more than 13% on average. Increasing the short-distance first strategy can reduce the participant travel distance by more than 4% on average.