Task Assignment And User Scheduling Algorithms In Crowdsensing

Crowdsensing is a new computing and sensing model, utilizing the functionalities of sensing, computation, storage, and communication of mobile smart devices. It treats the smart devices carried by mobile users as powerful and intelligent wireless sensors, and coordinates them together, so as to accomplish sensing tasks. Crowdsensing can accomplish various large complex sensing tasks with a low cost, which traditional sensor networks cannot easily deal with. Therefore, it is significant to study crowdsensing.Task allocation and user scheduling is the key problem in crowdsensing. It takes charge of not only completing sensing tasks, but also achieving some specific optimization objective, such as minimizing the completion time, maximizing the number of completed tasks, maximizing the total gain, etc. Currently, the research achievements on task assigning and user scheduling algorithms in crowdsensing are few. This dissertation mainly studies the task assignment and user scheduling problems of crowdsensing in two different scenarios. First, we introduce the crowdsensing scenarios; then, we build the models for the two problems; finally, we propose an online task allocation algorithm and an offline algorithm based on the greedy strategies, and also conduct an analysis to demonstrate their significant performances.The contribution and innovation in this dissertation are:●In the model of crowdsensing built on mobile social network, we start from analyzing the characteristics of the MSN and the completion procedure of each task. An online algorithm is proposed to solve the-problem of minimizing tasks’ latest completion time. Tasks sorted in the descending order of workload are assigned one by one to the user with the minimum processing time. The feasibility and efficiency of the algorithm will be proved by the competitive ratio analysis and experiment results of real trace and synthetic experiments.● For a crowdsensing system which has position relevancy between users and tasks, the goal is to maximize the total gain of tasks. We first show how this scenario is popular in reality. Then we mathematically model the original problem to the form of minimum weighted set covering. We propose a greedy algorithm to maximize the total gain. In the algorithm, task producing more gain is preferentially assigned to users costing less. Compared to other assigning algorithms, ours performs better, which will be proved by synthetic experiments.The research of task assignment and user scheduling in this dissertation has universal relevance. It is also applicable to other similar scenarios and problems. It has deep meaning for the popularization of crowdsensing.