CN-121504106-B - Mobile crowd sensing task allocation method and system based on fuzzy clustering and dynamic scheduling

CN121504106BCN 121504106 BCN121504106 BCN 121504106BCN-121504106-B

Abstract

The invention provides a mobile crowd sensing task allocation method and a system based on fuzzy clustering and dynamic scheduling; the method comprises the steps of mining a potential space structure of a task by utilizing fuzzy clustering, classifying the task into fuzzy clustering with membership attribute through soft division, constructing a benefit matrix comprising space-time feasibility and time cost after acquiring space-time distribution characteristics of the task, and realizing global optimal matching between workers and task clustering by adopting a Hungary algorithm. Aiming at the online execution stage, a dynamic scheduling mechanism comprising a primary task pool and a cooperative task pool is designed, and workers screen tasks according to mixed priority indexes combined with time urgency, spatial proximity and clustering membership. The invention solves the problem that the overall efficiency and the local flexibility are difficult to be compatible in large-scale task allocation by a layering mechanism of macroscopic division, mesoscopic matching and microscopic scheduling, and effectively reduces the time resource cost of the system while obviously improving the overall task completion rate.

Inventors

ZHANG YUANYUAN
HUANG YUQING
HUANG RUIHONG
XIONG JINBO
Bi Renwan
WANG XIAODING
LIN LI
JIN BIAO

Assignees

福建师范大学

Dates

Publication Date: 20260505
Application Date: 20260114

Claims (6)

1. A mobile crowd sensing task distribution method based on fuzzy clustering and dynamic scheduling is characterized in that the method is used for distributing tasks to a given task set and a worker set according to the optimization objective of maximizing the overall task completion rate and minimizing the overall task time resource cost, and comprises the following three stages: The first stage is a fuzzy task dividing stage, wherein tasks with geographical position attributes are divided into different clustering areas by adopting a fuzzy clustering algorithm, and a membership matrix and a clustering center of each task for each cluster are obtained; the second stage is an optimal worker-cluster allocation stage, a benefit matrix between workers and clusters is constructed based on the membership matrix, a one-to-one mapping relation between workers and task clusters is determined by using a maximum weight matching algorithm, and a responsible cluster area is designated for each worker; the third stage is a mixed priority scheduling stage, and enters an online execution process, and workers construct a task pool according to the responsible clustering area and dynamically select and execute tasks according to mixed priority indexes including time, space and membership; the benefit matrix between workers and the clusters is constructed based on the membership matrix, and the one-to-one mapping relation between the workers and the task clusters is determined by using a maximum weight matching algorithm, specifically as follows: First, constructing benefit matrix Benefit matrix Elements of (a) Representing workers Assigning clusters The calculation formula is as follows: Wherein, the Is a membership matrix In the presence of an element of the group, In order for the coefficient of ambiguity to be a factor, Is a worker Executing tasks Is used for the time-estimated cost of (a), Is a value that prevents the introduction of a denominator of 0, The space-time feasibility judging function is as follows: Wherein, the The current time is indicated as such, Representing tasks Is used to determine the expiration time of (1), Representing workers The deadline for returning to the original location is required, Representing workers Is used for controlling the speed of movement of the vehicle, Representing tasks Location and worker A distance between the initial positions; then, the benefit matrix Conversion into a cost matrix Cost matrix Elements of (a) The calculation formula of (2) is as follows: And solving the cost matrix by using a Hungary algorithm to obtain an optimal matching scheme for maximizing the total benefit.
2. The mobile crowd sensing task allocation method based on fuzzy clustering and dynamic scheduling according to claim 1, wherein the step of dividing the tasks with geographical location attribute into different clustering areas by adopting a fuzzy clustering algorithm to obtain membership degree matrix and clustering center of each task to each cluster comprises the following specific steps: initializing a membership matrix Updating the cluster center set by iteratively minimizing an objective function of the weighted distance sum of squares And membership matrix Until convergence; updating membership matrix Elements of (a) The calculation formula of (2) is as follows: Wherein, the In order to be the location of the task, And All are the cluster centers of the two groups, As the total number of clusters, Index variables for traversing the cluster center; updating cluster centers The calculation formula of (2) is as follows: Wherein, the As a total number of tasks, Index variables for traversing tasks; Stopping iteration when the change of the membership matrix is smaller than the convergence threshold epsilon or the maximum iteration number is reached, and outputting the final membership matrix And clustering center set 。
3. The mobile crowd-aware task allocation method based on fuzzy clustering and dynamic scheduling of claim 1, wherein each worker in the mixed priority scheduling phase Maintaining a primary task pool Collaborative task pool : The primary task pool Including clusters of all unassigned tasks that are responsible for workers Tasks with highest membership; The collaborative task pool Including pairs of clusters among all unassigned tasks Is not highest but exceeds a preset collaboration threshold Is a task of (1); when a worker selects a task from a candidate list consisting of a primary task pool and a cooperative task pool, the worker selects the task according to the mixed priority index Sequencing and mixing priority index By time priority Spatial priority And membership priority Weighted summation results in: Wherein the method comprises the steps of Based on the calculation of the remaining effective time of the task, For the task Is used for the remaining active time of the (c), And Representing the maximum and minimum values respectively of the remaining active time of all tasks in the task pool, Is a value that prevents the denominator from being introduced as 0; Based on the distance calculation of the task from the worker, Representing the linear distance between the two positions, Representing workers Is provided in the position of (a), In order to be the location of the task, And Respectively all tasks and workers in the task pool Distance between Maximum and minimum values of (a); task-based Clustering pairs Membership degree of (C) Calculating; is a weight coefficient.
4. The mobile crowd sensing task allocation method based on fuzzy clustering and dynamic scheduling according to claim 3, wherein the hybrid priority scheduling stage adopts a dynamic scheduling strategy, and specifically comprises the following steps: step A1 when workers Updating workers according to the current unassigned task set while in an idle state Is the primary task pool of (1) Collaborative task pool Merging the two into a candidate list; Step A2, calculating the mixed priority of each task in the candidate list And press The tasks are arranged in ascending order; step A3, checking the ordered task list in turn, and passing through a feasibility function Judgment task Whether space-time constraints are satisfied; Step A4, selecting the first task meeting the constraint in the list as the next execution target, atomically updating the state of the selected task to be 'allocated', and removing the selected task from the unassigned task set.
5. The mobile crowd sensing task allocation method based on fuzzy clustering and dynamic scheduling according to claim 1, wherein the overall task time resource cost in the optimization objective introduces a time penalty term for unallocated tasks; the overall task time resource cost is the time cost average that includes all tasks that are allocated and unallocated: for tasks that have been successfully allocated, the actual completion time cost of the allocated tasks is calculated ; For the final unallocated tasks, calculating penalty time costs for all unallocated tasks The penalty time cost The definition is as follows: Wherein the method comprises the steps of The maximum linear distance between any two task positions in all unassigned tasks for a task area, For the minimum moving speed of the worker, Minimum processing speed for workers.
6. A mobile crowd-sourced task allocation system based on fuzzy clustering and dynamic scheduling, comprising a processor, a memory and a computer program stored on the memory, wherein the processor, when executing the computer program, performs the steps of the mobile crowd-sourced task allocation method according to any one of claims 1-5.

Description

Mobile crowd sensing task allocation method and system based on fuzzy clustering and dynamic scheduling Technical Field The invention belongs to the technical field of mobile crowd sensing and resource scheduling, and particularly relates to a mobile crowd sensing task allocation method and system based on fuzzy clustering and dynamic scheduling. Background Mobile crowd sensing is an emerging paradigm for data collection, utilizing the average user carrying intelligent mobile devices as "workers" to sense and collect environmental data. The core challenge of mobile crowd-sourced platform operation is how to effectively distribute massive tasks with space-time constraints to workers with diverse capabilities and dynamically changing movement trajectories. Existing research is focused mainly on local optimization strategies such as path planning for individual workers or greedy heuristic based on instant task matching. Although these methods are computationally efficient, there is often no ideal balance between global task completion rate and overall time efficiency. In particular, the spatial distribution of tasks often presents natural clustering features, while the decision-making behavior of workers is diverse and dynamic, which makes it very complex to design a framework that enables globally optimal resource allocation. If the overall optimal solution is simply pursued, the calculation complexity rises exponentially along with the increase of the number of tasks and workers, and the real-time requirement is difficult to meet, and if the overall optimal solution is simply depended on local greedy, uneven task distribution is easily caused, and tasks in partial areas are backlogged in a large amount, so that the overall time resource cost of the system is increased. Therefore, a task allocation scheme capable of combining macro global planning and micro dynamic scheduling is needed. Disclosure of Invention The invention aims to provide a mobile crowd sensing task allocation method and a system based on fuzzy clustering and dynamic scheduling, which are characterized in that the method and the system are realized through a layering mechanism, and the task space structure is excavated and optimally matched by utilizing fuzzy clustering at the macroscopic level, and dynamic scheduling is carried out by mixing priority levels at the microscopic level, so that the time resource cost of the overall task is obviously reduced while the high task completion rate is ensured. In order to achieve the above purpose, the technical scheme of the invention is that a mobile crowd sensing task allocation method based on fuzzy clustering and dynamic scheduling is used for allocating tasks to given task sets and worker sets by taking maximization of overall task completion rate and minimization of overall task time resource cost as optimization targets, and comprises the following three stages: The first stage is a fuzzy task dividing stage, wherein tasks with geographical position attributes are divided into different clustering areas by adopting a fuzzy clustering algorithm, and a membership matrix and a clustering center of each task for each cluster are obtained; the second stage is an optimal worker-cluster allocation stage, a benefit matrix between workers and clusters is constructed based on the membership matrix, a one-to-one mapping relation between workers and task clusters is determined by using a maximum weight matching algorithm, and a responsible cluster area is designated for each worker; the third stage is a mixed priority scheduling stage, and enters an online execution process, and workers construct a task pool according to the responsible clustering area and dynamically select and execute tasks according to mixed priority indexes including time, space and membership. Preferably, the step of dividing the tasks with the geographic position attribute into different clustering areas by adopting a fuzzy clustering algorithm to obtain a membership matrix and a clustering center of each task to each cluster comprises the following specific steps: initializing a membership matrix Updating cluster center set through iterationAnd membership matrixUntil convergence; updating membership matrix Elements of (a)The calculation formula of (2) is as follows: Wherein, the In order to be the location of the task,AndAll are the cluster centers of the two groups,In order for the coefficient of ambiguity to be a factor,As the total number of clusters,Index variables for traversing the cluster center; updating cluster centers The calculation formula of (2) is as follows: Wherein, the As a total number of tasks,Index variables for traversing tasks; when the change of the membership matrix is smaller than the convergence threshold Or stopping iteration when the maximum iteration number is reached, and outputting a final membership matrixAnd clustering center set。 Preferably, the benefit matrix between the worker and the cluster