Research On User Recruitment Under Budget Constraint In Mobile Crowdsensing

With the wide application of smartphones and other mobile electric devices,mobile crowdsensing(MCS)also develops rapidly,and shows its broad prospect of application.In mobile crowdsensing,lots of mobile users are recruited by a mobile crowdsensing platform,to cooperatively perform a complex job including many sensing tasks.How to recruit well-suited mobile users properly and efficiently,is one of the most important and hottest issues.This dissertation mainly focuses on the user recruitment problem under budget constraint in mobile crowdsensing.Unlike previous works,each sensing task in this dissertation is indivisible,and can be performed by more than one user,but its single profit for platform is invariable,making our problem different from trivial 0-1 knapsack problem.Moreover,most of existing works mainly study the user recruitment without budget constraint,and single user’s cost is invariable,their optimization objectives are usually minimizing the total cost.In this dissertation,users’cost depend on the tasks they can deal with,and the MCS platform wants to maximize the total profit,while total cost of user recruitment can not exceed a given budget.To this end,this dissertation studies two kinds of different user recruitment models,and proposes corresponding solutions and algorithms:1.Centralized and deterministic user recruitment problem.In this problem,mobile users decide which tasks to perform according to their own situation,and the cost depends on the number of performing tasks.The MCS platform knows all users’sets of sensing tasks they can perform and their charges.Firstly,the profit-maximizing problem under budget constraint is formalized by a mathematical model,and proved to be NP-hard,then a modified greedy algorithm called gPUR is adopted to solve this problem.Moreover,after analyze the performance guarantee of gPUR,its approximation ratio is given.2.Opportunistic and probabilistic user recruitment problem.Due to the large amount of tasks’ messages and unavailable of cellular networks,the centralized solution can’t work here.To this end,an opportunistic tasks dissemination and user recruitment scheme(OTDURS)is proposed.In OTDURS,the MCS platform disseminates tasks via opportunistic networks,and recruits users based on users’historical probabilistic information of performing tasks.Mathematical model of this problem is constructed and its NP-hardness is proved,then two opportunistic and probabilistic algorithms for user recruitment are proposed,and their computational complexity are acceptable.The offline algorithm FUR recruits users based on the historical probabilistic information of all users,it gets an offline user recruitment strategy after a series of greedy iterations.NUR is an online algorithm,with the opportunistic networks,the MCS platform disseminates tasks’ messages and recruits users at the same time.Based on deterministic set of performing tasks of current user and historical probabilistic information of other users,the MCS platform executes offline algorithm and outputs a temporary user recruitment strategy every time meets a new user.The MCS platform will make decisions immediately and recruit current user if he is in temporary strategy.After extensive simulations and experiments,the performances of proposed algorithms are evaluated,experimental results are analyzed and compared in detail.The results show that they can achieve better performances than other compared algorithms.