Hybrid User-Based Task Assignment for Mobile Crowdsensing: Problem and Algorithm
Kun Liu, Shuo Peng, Wei Gong, Baoxian Zhang, Cheng Li
Abstract
With the rapid growth of Internet of Things and proliferation of handheld smart devices, mobile crowdsensing has been regarded as an effective sensing paradigm due to its high scalability, low cost, and wide coverage. In this paper, we study hybrid task assignment where semi-opportunistic and participatory users co-exist for task executions while tasks are delay sensitive and have heterogeneous qualities. The design objective is to maximize the total quality of completed tasks subject to a total budget shared by both types of users. We formulate this problem as an integer programming problem. We propose an efficient hybrid users based task assignment algorithm (referred to as HU-TSA), which works in an iterative way as follows. It first selects the top n (initially, n = 1) semi-opportunistic users in terms of quality-cost ratio for task assignment. It then clusters the remaining tasks into different regions based on their closeness and then performs utility based optimized user-region binding and standardized task density based path planning for the participatory users. It repeats the above process over all possible values of n to seek an optimal budget splitting between the two types of users for improved performance. We present the detailed design description of HU-TSA and deduce its computational complexity. Extensive simulations are carried out and the results show the effectiveness of HU-TSA by comparing with existing algorithms.