Research On Task Allocation Based On Minimum Cost Flow Algorithm In Mobile Crowd Sensing

Moblie crowdsensing(MCS)is a new computing mode in the Internet of things environment.It relies on large-scale ordinary users to collect sensing data through intelligent mobile portable devices and return it to the service platform.The service platform finally completes the process of large-scale and complex social tasks by processing the sensing data.Different from traditional sensor networks,mobile swarm intelligence sensing has many advantages,such as large coverage,high sensing accuracy,strong flexibility and so on.This paper focuses on the key problem of mobile group intelligence sensing-task allocation.Task allocation aims at how to identify mobile sensing users for currently unfinished MCS tasks that can achieve the maximum overall task quality under given cost/budget constraints,or the lowest cost under given task quality requirements.At present,there is little research on the diversity and reusability of tasks and sensing ability,as well as the establishment of appropriate incentive mechanism.To solve the above problems,after studying the existing crowd-sensing system,this paper establishes a three-layer model based on the traditional tasks-users model,which adds a data item layer in the middle of the two-layer model.The main function of data item layer is to standardly split tasks' requirements and users' sensing abilities,and transform the original complex task assignment problem into a binary matching problem.Using this model,the time parameters are further fused with it,and finally the core problem is transformed into a time-varying minimum cost flow problem.For the different rules of first come first service allocation,centralized instantaneous allocation and centralized waiting allocation,the greedy algorithm and the shortest dynamic f-augmented path algorithm are proposed respectively,and the bidding mechanism is added,so that the sensing users can freely buy and sell their matching priorities through bidding.Considering the stability of the task coalition and the large amount of surplus generated by the reusability of data,the Shapley value method is selected as the rule for fair distribution of the surplus generated by the algorithm.Finally,real data are used to test the performance of the proposed algorithm.Finally,by comparing greedy algorithm,zero wait algorithm,unrestricted wait algorithm and bidding wait algorithm through real data set experiments and different reference variables,it is found that unrestricted wait allocation algorithm is the most effective of the four algorithms,and bidding wait algorithm and zero wait algorithm will reach 105% and 109% of the lowest cost of the best algorithm on average,These three algorithms are much higher than the traditional first come first allocation algorithm.The waiting time of the algorithm is 20% and the longest waiting time of the algorithm is 80%.