Time Window-based Online Task Assignment for Mobile Crowdsensing

Mobile crowdsensing is a new paradigm for data collection by utilizing the mobility of sensor-rich hand-held smart devices. One of the key challenges in mobile crowdsensing is how to effectively assign tasks to mobile users in an online manner. In this paper, we study the online task assignment problem in mobile crowdsensing where each task has specific time window for its sensor data collection. The objective is to maximize the total profit of the platform in whole sensing period. We first model the crowdsensing system and formulate the profit maximization problem under study. To address this problem, we propose two heuristic algorithms, one is bipartite-match-based algorithm (BMA) using Kuhn-Munkres algorithm and the other improves the first by using data offloading for data upload cost reduction, if applicable. We present detailed algorithm design for both algorithms and deduce their computational complexities. Finally, simulation results validate the effectiveness of our proposed algorithms.