Competitive analysis

Algorithm

Engineering

Mathematical analysis

World Wide Web

Philosophy

Economics

Microeconomics

Mobile device

Online algorithm

Theology

Patience

Crowdsensing

Mathematics

Computer security

Computer science

Operations research

Upper and lower bounds

Budget constraint

Mobile CrowdSensing (MCS) is a promising paradigm that recruits users to cooperatively perform various sensing tasks. In most realistic scenarios, users dynamically participate in MCS, and hence, we should recruit them in an online manner. In general, we prefer to recruit a user who can make the maximum contribution at the least cost, especially when the recruitment budget is limited. The existing strategies usually formulate the user recruitment as the budgeted optimal stopping problem, while we argue that not only the budget but also the time constraints can greatly influence the recruitment performance. For example, if we have less remaining budget but plenty of time, we should recruit users with more patience. In this paper, we propose a dynamic user recruitment strategy with truthful pricing to address the online recruitment problem under the budget and time constraints. To deal with the two constraints, we first estimate the number of users to be recruited and then recruit them in segments. Furthermore, to correct estimation errors and utilize newly obtained information, we dynamically re-adjust the recruiting strategy and also prove that the proposed strategy achieves a competitive ratio of (1 - 1/e) <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> /7. Finally, a reverse auction-based online pricing mechanism is lightly built into the proposed user recruitment strategy, which achieves truthfulness and individual rationality. Extensive experiments on three real-world data sets validate the proposed online user recruitment strategy, which can effectively improve the number of completed tasks under the budget and time constraints.

Dynamic User Recruitment with Truthful Pricing for Mobile CrowdSensing