key: cord-0047476-ib189vow
authors: Li, Jianjun; Fu, Jia; Yang, Yu; Wang, Xiaoling; Rong, Xin
title: Research on Crowd-Sensing Task Assignment Based on Fuzzy Inference PSO Algorithm
date: 2020-06-22
journal: Advances in Swarm Intelligence
DOI: 10.1007/978-3-030-53956-6_17
sha: aaa99e633b3118286158d62cf2e92aa21c03d3b1
doc_id: 47476
cord_uid: ib189vow

To solve the problem of load unbalance in the case of few users and multi-task, a fuzzy inference PSO algorithm (FPSO) crowd sensing single objective task assignment method is proposed. With task completion time, user load balancing and perceived cost as the optimization goals, the fuzzy learning algorithm dynamically adjusts the learning factor in the PSO algorithm, so that the PSO algorithm can perform global search in the scope of the task space, thus obtaining the optimal task assignment solution set. Finally, the FPSO algorithm is compared with the PSO, GA and ABC algorithms on the optimization objectives, such as the algorithm convergence, task completion time, perceived cost and load balance. The experimental results show that the FPSO algorithm not only has faster convergence rate than the other algorithms, and shorten the task completion time, reduce the platform’s perceived cost, improve the user’s load balance, and have a good application effect in the crowd sensing task assignment.

With the widespread use of mobile users, smartphones have become an important bridge between the physical world and the online world. These advances have driven a new paradigm for collecting data and sharing data, namely group intelligence perception [1, 2] . At present, the application of group intelligence perception mainly includes: air quality monitoring [3] , traffic information management [4] , public information sharing [5] and so on. As the task assignment of the key problem of the crowd-sensing system, it is necessary to meet the optimization objectives under the constraints while completing the specified tasks, such as the shortest time to complete the task, the least perceived cost required to complete the task, the maximum benefit from completing the task, etc. Therefore, the main problem solved by the fuzzy inference PSO algorithm crowd sensing task assignment method is: how to perform task assignment for the multi-task of less user participants, which can ensure that the given number of tasks is completed in the shortest time, the perceived cost is the lowest, and user load balancing is optimal. For the problem of poor user load balance in mobile commerce, a fuzzy inference particle swarm crowd sensing task assignment method is proposed to improve the global search ability of the algorithm and avoid falling into local optimum. The main contributions of this paper include:

(1) A single objective task assignment optimization model is constructed, with task completion time, perceived cost and user load balance as the objective function. (2) Based on the task assignment optimization model, a fuzzy inference particle swarm intelligence discernment task assignment method is proposed to solve the task assignment problem in discrete space. (3) Through the simulation experiment, the proposed fuzzy inference particle swarm task assignment method (FPSO) is compared with PSO, GA and ABC algorithms.

The experimental results show that fuzzy inference particle swarm optimization algorithm can minimize the task completion time, the lowest perceived cost and the maximum user load balance.

The paper mainly reviews the literature on single target assignment and dual objective assignment. For single-objective task assignment: Xiao et al. [6] considered the independent perceptual task scheme to minimize the task average completion time as the optimization goal, proposed the AOTA algorithm (average time-sensitive online task assignment algorithm); and considered the cooperative perception. In the task assignment scheme, the LOTA algorithm (the maximum completion time sensitive online task assignment algorithm) is proposed to minimize the maximum completion time of the task, and the important performance of the two algorithms is proved by simulation experiments. Yang et al. [7] considered the biggest problem of budget information in crowd-sensing, modeled by Gaussian process and proposed an algorithm BIM for quantifying the amount of information based on common standards based on information. The algorithm is suitable for the inability to obtain user cost. Xiao et al. [8] focused on the recruitment of users who are sensitive to deadlines for probabilistic collaboration. Mobile users perform crowd-sensing tasks within a certain probability range, and can recruit multiple user systems to perform common tasks to ensure expected the completion time does not exceed the deadline, and ag DUR (Criteria for Time-sensitive Greedy User Recruitment Algorithm) is proposed to maximize utility for recruiting users and to minimize perceived cost expenditures during the deadline. Azzam et al. [9] proposed a user group recruitment model based on genetic algorithm in order to recruit more participants to perform tasks, considering user interest points, related device perception capabilities and user basic information. By comparing with the personal recruitment model, the user group recruitment model based on genetic algorithm can improve the quality of collecting perceived data and ensure the reliability of perceived results. Yang et al. [10] designed the problem of heterogeneous sensor task assignment, and designed the heuristic algorithm to combine the genetic algorithm and the greedy algorithm to achieve the optimization goal of minimizing the total penalty caused by delay.

For dual-target assignments: Liu et al. [11] mainly studied the multi-task assignment of dual-objective optimization. For FPMT (less participants multitasking), to maximize the total number of tasks and minimize the moving distance as the optimization goal, use the MCMF (minimum cost maximum flow) theory to convert the FPMT problem, and consider the FPMT problem to build a new MCMF model. Xiong et al. [12] proposed a task assignment search algorithm based on maximizing space-time coverage and minimizing perceived cost in task assignment. Considering the perceived time and the quality of task completion. Wang et al. [13] only studied the perceptual task assignment problem to minimize the overall perceived cost and maximize the total utility of group intelligence perception, while meeting various quality of service (QoS) requirements, and proposed a new hybrid method combines the greedy algorithm with the bee colony algorithm. Messaoud et al. [14] mainly studied the participatory crowd-sensing user, and under the condition of satisfying information quality and energy constraints, to optimize the data perceptual quality and minimize the perceptual time of all participants, the appropriate task participants designed a crowd-sensing task assignment mechanism based on the tabu search algorithm combined with information quality and energy perception. Dindar Oz [15] proposed a solution to the problem of multi-objective task assignment, and designed a neighboring function that successfully solved the quadratic assignment problem for the metaheuristic algorithm, namely the maximum release of greedy allocation. Ziwen Sun et al. [16] proposed an attack location assignment (ALTA) algorithm based on multi-objective binary PSO optimization algorithm, which models the task as a multi-objective optimization model. The objective function is total task execution time, total energy consumption and load balancing. The method of nonlinearly adjusting inertia weight overcomes the shortcomings of binary particle swarm optimization (BPSO) which is easy to fall into local optimum.

In summary, for the crowd-sensing task assignment problem, most researchers only consider one or two optimization goals such as perceived cost, task completion time, and task completion quality, and there are few studies that satisfy both optimization goals. This paper considers the problem of poor user load balance encountered in the process of task problems, combines task completion time and perceived cost, establishes single objective task assignment optimization model, and proposes fuzzy inference particle swarm task assignment method to solve task assignment problem in discrete space.

There are two main types of task assignments: multi-participant less tasks and fewer participants multitasking. This topic mainly studies the task assignment of multi-tasks with fewer participants. How to perform reasonable task assignment makes the user load balance more, and the user participation enthusiasm can reduce the task completion time and reduce the perceived cost. In a specific environment, after the cognitive platform publishes the task, the mobile terminal users who are interested in these tasks will confirm the tasks to indicate their intentions, and finally confirm the set of end users U = {u 1 , u 2 , . . . , u n }, and the set of the published task R = {r 1 , r 2 , . . . , r m } (n < m). At the same time, an end user can complete one or more tasks. Reasonable task assignment enables each task target to be assigned to the appropriate user or user community to perform. Each user is also assigned to a task target that matches its own performance, using each user's maximum energy to complete the task, saving costs, improve task completion rates.

In order to satisfy the establishment of the crowd-sensing task assignment model under defined conditions, the following assumptions are made:

(1) The task assignment studied in this paper is in a specific time range, and only the participating users and tasks are allocated during this time.

(2) The matching of the published tasks and the participating users within the coverage of the specified task area is not a task for all coverage areas. This narrows the scope of the task space and improves the quality of the task completion. (3) For the tasks released by the crowd-sensing platform, users who are suitable for performing the task will be found. There is no case that the appropriate users cannot be found after the task is released. (4) All users move from the current position to the task position at the same speed, regardless of the user's moving speed.

(See Table 1 ). 

(1) Task completion time The total time taken by n users to complete m tasks is T:

Which t ij represents the time taken by the i user to perform the j task. (2) Load balance Load balancing is measured using the ratio of task completion times. The expression is the ratio of each user's completion time to the total task completion time.

Which t ij represents the completion time of each user on behalf of each user, and T represents the total task completion time. The closer the task completion time to the total task completion time, the more balanced the load is. Therefore, the larger the β, the higher the load balance.

The perceived cost is related to the distance the user moves to the location of the task and is proportional to the distance traveled by the perceived user to the task location. If the position coordinate of the user 1 is (x u 1 , y u 1 ), and the position coordinate of the task 1 is (x r 1 , y r 1 ), the distance between the user and the task is

if the ratio coefficient of the perceived cost and the moving distance is constant α, the perceived cost of the user to the task is c 1 = αd 11 . Therefore, the single objective task assignment optimization model is:

The constraints are: (1) m tasks are completely assigned to n users;

(2) Each sensing task can only be executed once by a certain perceived user;

(3) The task and the task can only be executed once by a certain user;

The number of tasks assigned by each perceptual user is not more than γ ; 1 ≤ A i ≤ γ

Particle Swarm Optimization (PSO) is proposed to be influenced by bird predation behavior [17, 18] . The PSO algorithm is modeled as follows:

Which v i (t) represents the velocity of the particle i at the iteration time t, i represents the number of particles, i ∈ {1, 2, . . . , N }. w is the weight function, and c 1 , c 2 are the weight acceleration coefficient; random is a uniformly distributed random variable in the interval (0,1); x i (t) represents the current position of the particle i at the iteration time t; x 

In order to improve the overall performance of the swarm intelligence algorithm, fuzzy inference technology is added to the particle swarm optimization algorithm, and the learning factor in the PSO algorithm is dynamically adjusted by the fuzzy inference technology, so that the PSO algorithm can perform global search in the task space to avoid the algorithm falling into the local optimal area, so as to get the optimal task assignment solution set. In order to verify that the fuzzy inference PSO algorithm improves the performance of the original algorithm, several typical algorithms are selected for comparison. As shown in Fig. 1 , the FPSO algorithm has a faster convergence rate than other algorithms.

In this paper, a fuzzy system with two inputs, two outputs and nine rules is designed. The input is the current optimal performance index (VB), the current iteration number iter; the output is c 1 and c 2 ; the Mamdani type [19] is blurred. The system adjusts c 1 and c 2 .

(1) Fuzzy set: For the input variables V and iter, three fuzzy sets are defined: Low, Medium, High. For the output variables c 1 and c 2 , five fuzzy sets are defined: Low, Medium Low, Medium, Medium High, and High, using a triangular membership function. (2) Variable range. In order to apply to various optimization problems, the input variables need to be converted to a normalized form, that is:

Where VB is the current optimal estimate of the population; VB min is the optimal estimate of the population; VB max is the worst estimate of the population; iter is the current number of iterations; iter max is the maximum number of iterations of the algorithm. After normalization, the range of NV and Niter is [0, 1].

(3) Fuzzy rules: The overall idea of fuzzy rule setting is that in the early stage of algorithm iteration, when the evaluation value is poor, it needs strong global search ability, large shrinkage factor value, and the particle is the most Excellent learning ability is stronger than the ability of particles to learn from the society, that is c 1 > c 2 ; in the later stage of algorithm iteration, when the evaluation value is good, it needs less global search ability and shrinkage factor value, and the ability of particles to learn from society is stronger. The ability of a particle to learn optimally from itself, that is c 1 < c 2 . Therefore, the following nine fuzzy rules are designed:

If NB is Low and Niter is Low, then c 1 is Medium Low and c 2 is Low. If NB is Low and Niter is Medium, then c 1 is Medium High and c 2 is Medium. If NB is Low and Niter is High, then c 1 is Medium High and c 2 is High. If NB is Medium and Niter is Low, then c 1 is Medium Low and c 2 is Low. If NB is Medium and Niter is Medium, then c 1 is Medium and c 2 is Medium. If NB is Medium and Niter is High, then c 1 is Medium High and c 2 is High. If NB is High and Niter is Low, then c 1 is Medium Low and c 2 is Low. If NB is High and Niter is Medium, then c 1 is Medium Low and c 2 is Medium High. If NB is High and Niter is High, then c 1 is Medium High and c 2 is High.

Therefore, the FPSO algorithm flow chart is shown in Fig. 2:   Fig. 2 . FPSO algorithm flow chart

The particle swarm optimization algorithm in the swarm intelligence algorithm is used to map the optimal objective function and constraint conditions of the crowd-sensing task assignment problem to each element of the fuzzy inference particle swarm optimization algorithm to complete the task solving.

Task assignment process:

(1) Analyze the task assignment problem of mobile commerce group in a specific environment; (2) Establishing a crowd-sensing single objective task assignment optimization model, and determining the task assignment constraints and optimization objective function, and transforming into the evaluation index function of the fuzzy inference particle swarm optimization algorithm; (3) Using the FPSO algorithm to optimize the search for decision variables; (4) Optimized search of decision variables by FPSO algorithm, and evaluate the optimization results according to the objective function; (5) When the result satisfies the task assignment requirement, the output result ends with the FPSO algorithm.

In the set environment of mobile commerce crowd-sensing, taking the Drip taxi as an example, the time spent by the passenger to release the taxi task to the vehicle owner to start executing the task within the specified time is recorded as the task completion time; The owner of the vehicle arrives at the distance that the passenger user releases the position of the ride, and the fuel cost, the loss fee, etc. consumed during the period are recorded as task-aware costs; the load balance is reflected in the number of tasks received by each vehicle owner. Therefore, the number of simulation tasks is 200, 400, 600, 800, 1000, and the maximum number of iterations of the algorithm is 200. Experiments are performed on the Matlab R2016b simulation platform. The FPSO algorithm parameter settings are shown in Table 2 . Learning factor c 1 2

Learning factor c 2 2

Maximum inertia factor w max 0.9

Minimum inertia factor w min 0.4

Maximum particle speed V max 4

The experiment uses three optimization objectives to compare the advantages and disadvantages of several algorithms, namely task completion time, task-aware cost and load balancing. The experimental results and analysis are as follows:

(1) Analysis of task completion time The task completion time comparison chart is shown in Fig. 3 and Fig. 4 . It can be seen from Fig. 3 that PSO, ABC and GA algorithms have good convergence in the early iteration compared with the FPSO algorithm. However, with the increase of the number of iterations, PSO, ABC and GA are easy to fall into local optimum, and FPSO algorithm can achieve global optimization and enhance global search ability. Therefore, from Fig. 3 to complete the task total time and Fig. 4 to complete the task average time can be seen the superiority of the FPSO algorithm, while the task completion time is minimum. (2) Perceived cost analysis In the task assignment model, task completion time, perceived cost, and load balance are used as task optimization goals. In the experiment, we mainly consider the perceived cost of applying different algorithms to complete the comparison of the same number of tasks. The number of tasks is 200, 400, 600, 800 and 1000 respectively in FPSO, PSO, ABC and GA algorithms. It can be seen from Fig. 5 , as the number of tasks increases (600, 800, 1000, respectively), the perceived cost of the FPSO algorithm is significantly lower than the PSO, ABC and GA algorithms. (3) Load balance analysis Load balancing is one of the important optimization goals in the paper. The greater the load balancing degree, the more reasonable the task assignment is, It can be seen from Fig. 6 that as the number of iterations increases, the curve of the FPSO algorithm is always above the PSO, ABC and GA algorithm curves, and finally tends to 0.92, so the FPSO algorithm is better implemented than the PSO, ABC and GA algorithms. Load balancing optimization goals make task assignments more reasonable. Through the above experiments, we know that the FPSO algorithm can shorten the task completion time, reduce the perceived cost of the task, and balance the user's task load. Therefore, in the actual task allocation, it is possible to improve the timeliness of the task, reduce the operating cost of the platform, and improve the task completion amount of the user.

This paper proposes a crowd-sensing task assignment method based on fuzzy inference particle swarm optimization to solve the problem of load unbalance in task assignment. In the proposed method, the fuzzy inference technology can dynamically adjust the learning factor in the PSO algorithm, so that the PSO algorithm can perform global search in the task space to obtain the optimal task assignment solution set. Compared with PSO, ABC and GA algorithms, it has higher precision and better stability in solving performance. At the same time, applying FPSO algorithm for task assignment can greatly shorten task completion time, reduce platform perceived cost and improve user load balance. In the future research, not only the load balancing problem of task allocation should be considered, but also the user interest preference problem in the allocation process is also an important factor to determine whether the user performs the task. The user must not only consider the cost of executing the task, but also Considering the degree of interest in the task, a combination of various factors motivates the user to perform the task. Therefore, in the next study, the user's interest in the task can be listed as an important factor in the user's work, and the task assignment can be further studied.

A survey of mobile phone sensing

Mobile crowd sensing: current state and future challenges

U-Air: when urban air quality inference meets big data

Crowd sensing maps of on-street parking spaces

Flier Meet: a mobile crowd sensing system for cross-space public information reposting, tagging and sharing

Online task assignment for crowd sensing in predictable mobile social networks

Selecting most informative contributors with unknown costs for budgeted crowd sensing

Deadline-sensitive user recruitment for probabilistically collaborative mobile crowd sensing

GRS: a group-based recruitment system for mobile crowd sensing

Heterogeneous task assignment in participatory sensing

Task me: multi-task assignment in mobile crowd sensing

Near-optimal task assignment for piggyback crowd sensing

Qos-constrained sensing task assignment for mobile crowd sensing

Fair QoI and energy-aware task assignment in participatory sensing

An improvement on the migrating birds optimization with a problem-specific neighboring function for the multi-objective task allocation problem

Attack localization task allocation in wireless sensor networks based on multi-objective binary particle swarm optimization

Particle swarm optimization: an overview

Multi-species cooperative particle swarm optimization algorithm

Prediction of biochar yield using adaptive neuro-fuzzy inference system with particle swarm optimization