Algorithms for Time Window-Based Online Task Assignment in Mobile Crowdsensing

Mobile crowdsensing (MCS) has been an effective sensing paradigm by exploiting the pervasive sensor-rich mobile devices for sensor data collection. Online task assignment is an important issue for mobile crowdsensing since tasks typically arrive dynamically and need to be handled in an online manner.  In this paper, we study online task assignment for maximizing the total profit of the MCS platform while satisfying the time window requirement of each task. We first describe the crowdsensing model and then study the online task assignment in the following two different scenarios: (1) user-offline-arriving scenario, where all users are fully available throughout the whole sensing period and their movements are fully planned by the platform;  (2) user-online-arriving scenario, where users arrive and depart dynamically and each user has a specific participatory time window for task executions. For the former scenario, we propose a benchmark algorithm and also an online heuristic algorithm.  The benchmark algorithm tries to provide a best-case performance by assuming all future task arrival information is known in advance. The online algorithm adopts bipartite-matching-based strategy for task assignment and further performs minimal detour based data offloading for reducing the data upload cost, whenever possible. For the latter scenario, we propose an effective online algorithm, which adopts a maximum-profit-first strategy for task assignment and also minimal detour based data offloading for reduction of data upload cost whenever applicable. For all the proposed algorithms, we present their detailed design and deduce their time complexities. Extensive simulations are conducted and the results demonstrate that our proposed algorithms can largely increase the total profit of the platform as compared with existing work.