With the rapid development of smartphones, spatial crowdsourcing platforms are getting popular. A foundational research of spatial crowdsourcing is to allocate micro-tasks to suitable crowd workers. Most existing studies focus on offline scenarios, where all the spatiotemporal information of micro-tasks and crowd workers is given. However, they are impractical since micro-tasks and crowd workers in real applications appear dynamically and their spatiotemporal information cannot be known in advance. In this paper, to address the shortcomings of existing offline approaches, we first identify a more practical micro-task allocation problem, called the Global Online Micro-task Allocation in spatial crowdsourcing (GOMA) problem. We first extend the state-of-art algorithm for the online maximum weighted bipartite matching problem to the GOMA problem as the baseline algorithm. Although the baseline algorithm provides theoretical guarantee for the worst case, its average performance in practice is not good enough since the worst case happens with a very low probability in real world. Thus, we consider the average performance of online algorithms, a.k.a online random order model.We propose a two-phase-based framework, based on which we present the TGOA algorithm with 1 over 4 -competitive ratio under the online random order model. To improve its efficiency, we further design the TGOA-Greedy algorithm following the framework, which runs faster than the TGOA algorithm but has lower competitive ratio of 1 over 8. Finally, we verify the effectiveness and efficiency of the proposed methods through extensive experiments on real and synthetic datasets.

Bike-sharing systems are widely deployed in many major cities, providing a convenient transportation mode for citizens' commutes. As the rents/returns of bikes at different stations in different periods are unbalanced, the bikes in a system need to be rebalanced frequently. Real-time monitoring cannot tackle this problem well as it takes too much time to reallocate the bikes after an imbalance has occurred. In this paper, we propose a hierarchical prediction model to predict the number of bikes that will be rent from/returned to each station cluster in a future period so that reallocation can be executed in advance. We first propose a bipartite clustering algorithm to cluster bike stations into groups, formulating a two-level hierarchy of stations. The total number of bikes that will be rent in a city is predicted by a Gradient Boosting Regression Tree (GBRT). Then a multi-similarity-based inference model is proposed to predict the rent proportion across clusters and the inter-cluster transition, based on which the number of bikes rent from/ returned to each cluster can be easily inferred. We evaluate our model on two bike-sharing systems in New York City (NYC) and Washington D.C. (D.C.) respectively, confirming our model's advantage beyond baseline approaches (0.03 reduction of error rate), especially for anomalous periods (0.18/0.23 reduction of error rate).

Off-the-shelf smartphones have boosted large scale participatory sensing applications as they are equipped with various functional sensors, possess powerful computation and communication capabilities, and proliferate at a breathtaking pace. Yet the low participation level of smartphone users due to various resource consumptions, such as time and power, remains a hurdle that prevents the enjoyment brought by sensing applications. Recently, some researchers have done pioneer works in motivating users to contribute their resources by designing incentive mechanisms, which are able to provide certain rewards for participation. However, none of these works considered smartphone users' nature of opportunistically occurring in the area of interest. Specifically, for a general smartphone sensing application, the platform would distribute tasks to each user on her arrival and has to make an immediate decision according to the user's reply. To accommodate this general setting, we design three online incentive mechanisms, named TBA, TOIM and TOIMAD, based on online reverse auction. TBA is designed to pursue platform utility maximization, while TOIM and TOIM-AD achieve the crucial property of truthfulness. All mechanisms possess the desired properties of computational efficiency, individual rationality, and profitability. Besides, they are highly competitive compared to the optimal offline solution. The extensive simulation results reveal the impact of the key parameters and show good approximation to the state-of-the-art offline mechanism.