Towards Sensing Task Allocation In Mobile Crowdsourcing

Mobile crowd sensing system is a technology of collecting data as the era of big data coming.As the promotion of smartphones and the universalization of smartphones,the smartphone users can collaborate with each other.There are different kinds of sensors integrated in the smartphones such as acceleration transducer,GPS and gyroscope,which can collect sensing data around the environment.It's the best way to collect and share large numbers of data among different people.However,the calculating resources such as CPU and storage may affect the ability of the smartphones.Therefore,it's essential to allocate sensing tasks to the smartphones with considering the limit resource and constraints.As a result of different kinds of constraints in the real world,this thesis is focusing on the critical sensing workloads allocation in mobile crowd sensing systems.This thesis is divided into two sections.For the first section,we focus on the sensing workloads allocation with constraints of budget of platform,fairness among sensing tasks and the traffic limit of each smartphone.Our objective is to maximize the aggregate data utility of all the sensing tasks.We also consider the redundancy of the sensing data received from the smartphones.There are some challenges with considering the intractability of this problem.The challenges are the intrinsic tradeoff between the aggregate data utility maximization and the fairness among the sensing tasks and the large numbers of smartphones in the real world.We put forward an efficiently distributed algorithm to solve this problem.First,we decompose the primal problem into two subproblems.For the first subproblem,we design a greedy algorithm with approximation ratio of 2.For the second subproblem,we design a distributed algorithm based on the dual-based decomposition.The large scale simulations and a small scale prototype can demonstrate that our algorithm can be efficient and accurate.Based on the first section,the second section is focusing on how to allocate the sensing tasks in a real-time crowd sensing system.Our problem's objective is to maximize the reward of the platform.First,the system users who publish their sensing tasks on the platform,and then the platform will allocate these sensing tasks to the smartphone users to perform.After these smartphone users finish these sensing tasks,they will transmit the sensing data to the platform.The platform should maximize the rewards,which are defined as the difference between the money the platform received from the system users and the money the platform should pay for the smartphone users.There is a great challenge in this crowd sensing system.The system users and the smartphone users are arriving at the platform dynamically.This paper will first demonstrate that this problem is NP-hard,and then formulate an offline model and the online model.For an offline model,an efficient approximation algorithm is designed.For an online model,an efficient greedy algorithm is designed.The large-scale simulations and mathematical analysis demonstrate that our algorithm is efficient and accurate.This thesis is focusing on the most important area of mobile crowdsourcing.This is essential because a real mobile crowdsourcing system should be optimized so that it can operate well without any mistakes.Also,this thesis solve two critical problems in the area of tasks allocation in mobile crowdcourcing.