Budget-feasible User Recruitment in Mobile Crowdsensing with User Mobility Prediction

摘要

Mobile crowdsensing (MCS) is a new and promising tool in urban sensing. It exploits a crowd of smartphone-carried mobile users and transfers their sensory data to requesters who usually publish spatio-temporal tasks of sensing city area. In reality, mobile users can probabilistically move in the sensing region in their daily mobility and stay there for a period of time; and then these probabilistic users can be recruited to collaboratively perform MCS sensing tasks. Such an MCS depending on the probabilistic collaboration of mobile users is usually called non-deterministic MCS. In this paper, we focus on the budget-feasible user recruitment (BFUR) problem in non-deterministic MCS, which is the first work to maximize the requester's utility under a given budget constraint. Because of the NP-hardness of BFUR, we reformulate it as a monotone submodular maximization problem and propose a greedy algorithm (called uMax) with provable constant-factor competitiveness. Unlike previous works for non-deterministic MCS, however, this paper specially puts effort on predicting the mobility patterns of users, especially their stay time in requester's sensing region, and then designs an effective predictor based on bi-directional long short-term memory neural network. Such a prediction of user's stay time not only connects the BFUR problem modeling defined in this paper and the actual mobility uncertainty of users, but also can apply to any non-deterministic MCS campaign that depends on the knowledge of user's stay patterns. We finally validate the performance of the proposed predictor under a real-world dataset of wireless mobile networks, and evaluate algorithm uMax by comparing it with two other baseline algorithms.