Background
In recent years, with the rapid development of information technology, mobile smart devices are becoming more popular. Mobile devices such as smartphones, watches, etc. have various types of sensors such as global positioning systems, thermometers, distance sensors, light sensors, cameras, etc., and have powerful computing capabilities. Users carrying the devices move in urban areas, and the idle resources of the devices are fully utilized, so that the birth of intelligent perception of the mobile group is promoted. Because a large number of fixed sensor nodes do not need to be deployed, the mobile crowd sensing system has higher space-time coverage, and has wide application in the aspects of environment monitoring, traffic management and smart cities. However, in a mobile crowd-sourced system, the total task load of different task requesters often has a large difference, and there are situations where users compete for use with each other, and the objective of the present invention is to minimize the maximum expected completion time of all tasks of all task requesters.
Disclosure of Invention
The invention relates to an opportunistic crowd sensing on-line task distribution method based on user pre-grouping, which is characterized in that the opportunistic crowd sensing system is provided with a plurality of task requesters and a plurality of users capable of executing sensing tasks, each task requester is provided with one or more tasks, each task is not divided and needs one user to finish, the task requesters and the users randomly move in a target environment, the distribution of the sensing tasks and the return of sensing results can only be carried out when the task requesters and the users meet directly in space, the interaction of the sensing tasks and the results is carried out through short-distance wireless communication modes such as DSRC/802.11 p/Bluetooth/WiFi, and the like.
The application environment of the invention is as follows:
Each task requester i has stored locally its expected encounter time interval EMTij with each user j;
The expected completion time of task k assigned to user j by task requester i, denoted Tik, is:
Wherein Sij is the task set that task requester i assigns to user j, Sp is the p-th task in task set Sij, τp is the processing time required by task Sp, user j first needs to complete those tasks that task requester i has assigned to that user prior to task k before task k is completed, Sp≤sk indicates that user j completes task p prior to task k when task k is completed, deltaij is the expected encounter time required by task requester i to assign task to user j and user j to return the perceived result to task requester i, deltaij＝EMTij if task requester i happens to meet directly in space when task requester i assigns task to user j, otherwise deltaij＝2EMTij;
User j completes the task submitted to it by task requester i, the desired processing time required, denoted EPTij:
Where τik is the processing time required for task sik, whose value is proportional to the load of the task;
The first free user of task requester i is the user with the smallest EPTiq value of all users assigned to the task requester, where user q is one user of the task requester user group;
The desired task completion time Mi for task requester i is the maximum of the desired processing times for all users in the task requester user group, namely:
Wherein the method comprises the steps ofIs a collection of users assigned to task requester i after user pre-groupingRepresenting the desired encounter time of task requester i with user uix.
The user pre-grouping method combining task load and meeting rule comprises the following steps:
The method comprises the steps of 1, assigning a user to each task requester, wherein the user with the shortest expected meeting interval time is assigned to the task requester with the largest total task load each time, and then the user is deleted from the optional user set, and the process is continuously carried out until the user group of each task requester has one user;
stage 2:
on the basis of phase 1, the following steps are continued:
1) When there is a user not yet grouped, performing the following steps;
2) Then, performing intra-group virtual allocation on all tasks of the task requester, wherein the principle is that the tasks are allocated in a first idle mode, and the tasks are allocated to the first idle user continuously, and the virtual allocation process is continuously performed until all the tasks are virtually allocated, and on the basis, the task expected completion time of the task requester is updated;
3) And (3) ending if no ungrouped users exist, otherwise, turning to the step (2).
The method for distributing the online tasks in the group based on the first idle user priority distribution and the maximum load task priority distribution comprises the following steps:
a) Starting to perform virtual task allocation whenever a task requester encounters a user belonging to its own user group and has not previously allocated a task to the user;
b) The task requester virtually distributes the rest tasks to all users which are not distributed to any task in the group, wherein the principle is that the tasks with the maximum load are preferentially distributed and distributed to the users which are idle first, and the process is continuously carried out until all the tasks are virtually distributed;
c) For the currently encountered user, the task requester allocates all the tasks virtually allocated to the user in the previous step to the user in practice, and the rest tasks are still held by the user and wait for the reassignment when encountering other users which are not allocated to the tasks in the user group in the future.