A Near-Optimal Heterogeneous Task Allocation Scheme for Mobile Crowdsensing

Abstract

We study the problem of heterogeneous task assignment in mobile crowdsensing (MCS) scenarios where the opportunistic mode and participatory mode coexist. Workers in opportunistic mode complete tasks during their daily routines while workers in participatory mode complete tasks by moving to designated locations. This problem can be simplified into a Knapsack problem which is NP-hard. Then, to solve this problem, we propose a two-phase task assignment algorithm MSHTA based on the workers’ mobility and historical information which leverage the advantages of two sensing modes in sensing quality and sensing cost of tasks. Specifically, a task is optimally assigned to workers who meet their sensing requirements (e.g., sensing time, sensing sensor) at each phase. Extensive simulation results show the effectiveness of our proposed algorithm in terms of tasks’ sensing quality and tasks’ sensing cost.

1 Introduction

The popularity of 4G/5G networks and the explosive growth of mobile devices with numerous sensors have enabled a novel sensing paradigm, namely mobile crowdsourcing (MCS) [1]. MCS uses mobile devices held by pedestrians (called workers) as basic sensing units to monitor environments (e.g., traffic congestion [2], air quality [3], noise level [4], etc.) of urban area in real-time. In MCS, workers collect data according to the requirements of tasks assigned to them by MCS platform, and then return the data to MCS platform. By analyzing the data submitted by workers, MCS platform can obtain environmental information of urban areas. Due to the differences of workers, they may submit different data for the same task where the data could significantly impact the analysis results of MCS platform. Hence, task assignment becomes a major issue in current MCS research works.

Recently, there have been many studies on MCS task assignment [5,6,7,8,9,10,11,12], which can be divided into two categories based on worker’s mobility patterns: (i) Some existing research works for MCS task assignment only consider opportunistic mode where workers will complete tasks assigned to them by MCS platform without changing their scheduled movement route in their daily life. In [5,6,7,8], the authors studied the assignment of single task in MCS. They proposed different task assignment schemes, which can maximize the sensing quality of tasks or assigned tasks to a minimum number of workers to ensure a certain level of tasks’ sensing quality. In contrast, some authors studied task assignment of multi-task coexistence in MCS, where tasks share limited resources such as budget and workers. For example, both [9] and [10] proposed multi-task assignment schemes to maximize overall system utility when the tasks share a limited incentive budget. (ii) The other category considers the task assignment under the participatory mode in MCS, where workers don’t have a fixed movement route and they will go to the designated location to perform the task. For instance, Kazemi et al. [11] aimed to maximize the number of completed tasks, while ensuring constraints on worker’s maximum number of accepted tasks. Similarly, Hu et al. [12] considered minimize the sensing cost for completing a given tasks set under the constraint on worker’s maximum movement distance. Most existing task assignment schemes adopt either the opportunistic mode or participatory mode while they did not consider task assignments in which two sensing modes coexisted.

As a matter of fact, both sensing modes have their own advantages and disadvantages, which we will explain as follow. The opportunistic mode does not require to change the worker’s scheduled movement route, so the interference to the worker is relatively small, and the cost of the task organizer is low. But the sensing quality of task largely depends on the worker’s movement route. For tasks occur in locations where are few workers pass through, the sensing quality may be very low. In participatory mode, workers can move according to sensing requirements of task, which can guarantee task completion. But there will be additional sensing cost to compensate the workers’ mobile overhead. Moreover, sensing tasks become complicated with the increase in demands of mobile crowdsensing, a task should be assigned to the workers who meet sensing requirements of tasks.

Motivated by the complementary nature of two sensing modes, we study the problem of the heterogeneous task assignment with the coexistence of two sensing modes. Compared to the task assignment problems in opportunistic or participatory mode alone, there are two research challenges in our problem. First, since the workers of two types (i.e., opportunistic workers and participatory workers) share a total budget, we need a more complex method for task assignment which considers the workers of two sensing modes simultaneously. Second, due to the heterogeneity, tasks should be assigned to workers who meet their sensing requirements. In an effort to address the problem and challenges mentioned above, our work makes the following contributions:

• We formulate the problem of heterogeneous task assignment with the coexistence of two sensing modes, in which tasks have different requirements on sensing time, location and sensor.

• We propose a two-phase greedy algorithm MSHTA to address our problem. MSHTA aggregates the respective advantages of the two sensing modes and assign the task based on the respective requirements of task.

• We evaluate the performance of the MSHTA through extensive simulations. The experimental results demonstrate the effectiveness of our proposed algorithm in terms of tasks’ sensing quality and tasks’ sensing cost.

2 System Model and Problem Statement

In this section, we first introduce the system model of our MCS scenario, and then formulate the problem of the heterogeneous task assignment with the coexistence of two sensing modes.

2.1 System Model

We consider a heterogeneous task assignment problem in an MCS scenario where two sensing modes coexist. Specifically, the entire sensing region is divided into l sub-regions where the data collection mission in one sub-region is defined as a “sensing task”. Suppose that there are m sensing tasks during a certain time period where each task has its own sensing requirements (e.g., sensing time, sensing sensor), denoted by $\mathcal {T} = \{t_{1},t_{2},...,t_{m}\}$. For simplicity, we divide the certain time period into g equal slots. The task $t_{j}$ ($j\in \mathcal {T}$) can be characterized by a parameter tuple $(s_{j},e_{j},l_{j},d_{j})$, where $s_{j}$ is the start slot of the task $t_{j}, e_{j}$ is the end slot of the task $t_j, l_{j}$ represents the sensing region of the task $t_j, d_{j}$ indicates the required sensor type of the task $t_j$. We assume that the union of sensors is denoted as $\mathcal {S} = \{d_{1},d_{2},...,d_{q}\}$. The energy consumed of task $t_j$ is determined by the type of sensor and the sensing slots. Suppose that the energy consumed by all sensors each slot is known, represented by the set $\mathcal {R}$, where $\mathcal {R} = \{r_{d_{1}},r_{d_{2}},\ldots r_{d_{q}}$}.

On the other hand, we assume there are n workers who have registered in the MCS plarform and they are willing to collect the data which sensing tasks need. The workers can be divided into the opportunistic workers and participatory workers according to the willingness of workers. Denote $W_{O} = \{w_{1},w_{2},...,w_{o}\}$ the opportunistic worker set and $W_{P} = {w_{1},w_{2},...,w_{p}}$ the participatory worker set, respectively. We adopt a parameter tuple ($l_{i},s_{i},k_{i},b_{i}$) to characterize the worker $w_i$ ($w_i \in W_o\cup W_p$). Specifically, $s_i$ is the set of sensors held by worker $w_i$, $k_i$ is the operational proficiency set of the sensor that the worker $w_i$ holds, it can be derived from the worker history execution task record, $l_i$ is the current location of the worker $w_i$, and $b_i$ is the current remaining battery of the mobile device held by the worker $w_i$. Suppose that the location of the worker does not change during the slot but changes between slots.

We adopt a centralized task allocation model, in which MCS platform collects the worker’s historical data and then selects the appropriate workers from the worker pool to perform the task [13, 14]. Since the sensing quality of task depends on the opportunistic worker’s movement route, it is necessary to accurately predict the location of opportunistic workers. A common method is that MCS platform uses the historical movement trajectories of the opportunistic worker to characterize the opportunistic worker’s mobility. Considering the difference in tasks sensing time, we directly use a statistical-based model to derive the probability that an opportunistic worker will pass a particular region at a given period.

Denote $\mathcal {D}$ the historical trajectory data set of the opportunistic worker, wherein each record consists of a worker ID, current location, and time period. Based on the learning of existing location records, the probability that the worker $w_i$ will access the specific region r during time period t can be calculated as follow:

$$\begin{aligned} P(w_i,t,r) = \frac{|\mathcal {D}_{(w_i,t,r)}|}{|\mathcal {D}|}, \end{aligned}$$

(1)

where $|\mathcal {D}_{(w_i,t,r)}|$ represents the number of days in which the worker $w_i$ pass the region r during time period t throughout $\mathcal {D}$, and $|\mathcal {D}|$ is the number of days included in the data set $\mathcal {D}$.

According to the mobility of the participatory worker, the probability that a participatory worker appears in the task sensing region within the task sensing time is 1.

In addition, in order to ensure the sensing quality of task, each task should be executed by multiple workers and then MCS platform aggregates the returned data by workers to obtain a more realistic value. In this paper, $\gamma$ is specified as the number of workers performing tasks. We use the binary variable $a_{ij}$ to indicate whether or not the task $t_j$ is assigned to the worker $w_i$. $a_{ij} = 1$ means that $w_i$ is selected to perform task $t_{j}$, otherwise 0. Therefore, the task assignment solution can be formalized as follow:

$$\begin{aligned} a_{ij} = {\left\{ \begin{array}{ll} 1 &{} \text {task }t_{j} \text { is assigned to worker }w_{i},\\ 0 &{} \text {otherwise}. \end{array}\right. } \end{aligned}$$

(2)

Furthermore, to ensure the sensing quality of the task, a worker can only perform one task at a slot.

When a worker goes to perform a task, it will lead to a cost, which is composed of three parts. The first part is basic reward paid to each worker recruited to the MCS platform. The second part is the sensing cost of workers using their mobile devices to perform sensing task. The third part is the cost of workers moving to the location of tasks. To compensate for the cost, the worker will receive a reward from the MCS platform. Specifically, if a worker $w_{i}$ is assigned multiple tasks, $w_{i}$ will receives more reward. Therefore, the reward for $w_{i}$ can be expressed as:

$$\begin{aligned} R(w_{i}) = R_{0}+R_1*\sum _{j=1}^ma_{ij}*|e_j-s_j+1|+R_2*\sum _{j=1}^ma_{ij}*d(w_i,t_j), \end{aligned}$$

(3)

where $R_{0}$ is basic reward paid to each worker who is recruited to the MCS platform; $R_{1}$ represents the reward that the worker performs the sensing task at each slot; $R_{2}$ represents the unit distance movement reward for the workers’ movement. The distance between the worker and the task is defined as the number of sub-regions that the worker passes through when he arrives at the task sensing regions. Moreover, all tasks share a total budget B, that is, the reward paid to all workers cannot exceed B.

2.2 Problem Statement

We use the task’s coverage ratio and workers’ sensor operation proficiency to measure the task’s sensing quality, where the coverage ratio of task is the probability that the worker passes the task’s sensing location during the task’s sensing time. Given an MCS task $t_j$, its sensing quality is calculated as follow:

$$\begin{aligned} Q_{t_{j}} = \frac{1}{\gamma }*\sum _{i=1}^na_{ij}*P(w_i,l_j,t_{s_{j}\sim e_{j}})*k_i, \end{aligned}$$

(4)

where

$$\begin{aligned} P(w_i,l_j,t_{s_{j}\sim e_{j}}) = \frac{\sum _{t=s_{j}}^{e_{j}}P(w_i,l_j,t)}{|e_j-s_j+1|}. \end{aligned}$$

(5)

Then, we define the utility value formula to calculate the utility value that the worker $w_i$ performs the task $t_j$ as follow:

$$\begin{aligned} u_{w_{i}} = P(w_i,l_j,t_{s_{j}\sim e_{j}})*k_i. \end{aligned}$$

(6)

Based on the above description and assumption, the system objective is to maximize the overall sensing quality of tasks under the budget constraint:

$$\begin{aligned} \max _{\varvec{a}}&\sum _{j=1}^mQ_{t_{j}}\end{aligned}$$

(7)

$$\begin{aligned} \text {s.t.}&\nonumber \\&{C_1:} \sum _{j=1}^ma_{ij}*|t_j|*b_{d_{j}} \le b_i,\forall {i} \in {W_o\cup W_p} \end{aligned}$$

(8)

$$\begin{aligned}&{C_2:}\ \sum _{i=1}^na_{ij} = \gamma , {\forall }{j} \in {T}\end{aligned}$$

(9)

$$\begin{aligned}&{C_3:}\ \sum _{i=1}^nR(w_i)\le B\end{aligned}$$

(10)

$$\begin{aligned}&{C_4:}\ s_j \subset s_i, {\forall }j \in {T},{\exists }i \in {W_o\cup W_p}\end{aligned}$$

(11)

$$\begin{aligned}&{C_5:}\ \sum _{j=1}^ma_{ij} \le 1, {\forall }i \in {W_o\cup W_p} \end{aligned}$$

(12)

Constraint $C_1$ means that each worker is assigned a task set whose consumed energy cannot exceed the worker’s available battery. Constraint $C_2$ represents all tasks share the total budget B. Constraint $C_3$ represents each task needs to be performed by $\gamma$ workers. Constraint $C_4$ represents if a worker is assigned a task, he must have the sensor required of the task. Constraint $C_5$ represents at most one task is assigned to a worker in a slot.

When we do not consider the heterogeneity of tasks, budget constraint and workers’ battery constraint, this problem could be simplified into a Knapsack problem, which is NP-hard.

3 Problem-Solving Algorithms

Considering the time complexity and optimality of the algorithm, we design a two-phase greedy algorithm to solve our problem, namely MSHTA.

Note that the final achieved assignment may not be real optimal solution, but rather close to the real optimal solution. The underlying reason is that we do not optimize the search space globally but decompose the original search space into multiple subspaces and probe the local optimization solutions one by one. However, by this method, the computational overhead can be significantly reduced.

3.1 Task Optimization Allocation: Greedy-Based Search

In this section, we will explain the task assignment process. The task assignment process is mainly composed of two phases. In the first phase, the task is assigned to the opportunistic worker, and in the second phase, the tasks with lower sensing quality are reassigned to the participatory worker execution to improve the sensing quality of task. In the following, the workflow of the algorithm will be described.

In the first phase, for each task, we first remove the invalid opportunistic worker who does not pass the task sensing region (i.e., P = 0) during the task execution time or does not have the sensor required for the task or with insufficient remaining battery to perform the task. Then, for each qualified opportunistic worker, the worker’s utility value for the task is obtained based on the utility value formula, and the incentive increment generated by assigning the task to the worker will be calculated by reward formula. Finally, a sorting operation is performed on all qualified workers based on the utility value of the worker. And select top-$\gamma$ qualified workers as the performer of the task. The corresponding binary variable $a_{ij}$ is set to 1. The selected worker list SeleList and the available budget will be update accordingly. The process continues until all tasks are associated with $\gamma$ workers or the budget is exhausted or there are no available opportunistic workers. Related pseudocode is presented in Algorithm 1.

In the second phase, all tasks are sorted based on the current sensing quality. In each iteration, we choose the lowest-sensing-quality task as the target. Participatory workers without the required sensor or with insufficient remaining battery are first removed, which can identify the qualified workers for the target task. Then for each qualified participatory worker, we obtain its utility based on the utility function, and the incentive increment generated by assigning the task to the worker will be calculated by reward function. Finally, a sorting process is conducted on all qualified participatory workers based on the utility value. The participatory worker with largest utility value is compared with the original $\gamma$ executive workers in the utility value. If the utility value of this participatory worker is greater than the utility value of one worker in the original $\gamma$ executive workers, select the participatory worker who with the largest utility value and lowest incentive increment as the performer of the task and then delete an original execution worker who have the smallest utility value of the task. And thus, sort all tasks based on current sensing quality, update the selected worker list SeleList and the available budget. The process continues until the budget is exhausted or there are no available participatory workers. The relevant pseudocode is presented in Algorithm 2.

After the above two-phase task assignment process, each task is assigned to the worker

4 Experimental Purposes and Baselines

The purpose of our simulation is to compare the performance of the MSHTA and other benchmark schemes in different situations (e.g., different task number, different budget). The performance indicators are the average task sensing quality, the number of tasks completed, total task sensing cost and total movement distance of the worker. Specifically, we have provide the following two benchmark schemes for comparative research.

OPP (Opportunity Mode Based Approach): This algorithm only uses opportunistic workers to maximize the sensing quality of all tasks while maintaining budget constraint. It spends all budget to choose opportunistic workers to perform task. Similar to [7], the OPP iteration selects the worker until the total budget is exhausted or the sensing quality of task no longer increases, and the selected workers will complete the task in their daily life. This benchmark scheme is used to test whether the MSHTA scheme is more efficient than the pure opportunity scheme in terms of tasks’ sensing quality, tasks’ sensing cost and task completed number.

PAR (Participation Mode Based Approach): This algorithm only uses participatory workers to maximize the sensing quality of all tasks while maintaining budget constraint. PAR spends all budget to choose the participatory workers and workers move to the specified location to perform tasks. Specifically, it uses a greedy-based algorithm to select workers to perform tasks. This benchmark approach is used to test whether the MSHTA scheme is more efficient than the pure participation scheme in terms of tasks’ sensing quality, tasks’ sensing cost, movement distance of the worker and task completed number.

4.1 Experimental Setups

In our simulation, we assume that tasks and workers are uniform distributed in the 5 KM * 5 KM region which is divided into 25 sub-regions, and all tasks will occur between 10 O’clock and 12 O’clock where this time period is divided into 8 slots. The available sensors of the worker are random and the worker’s sensor operation proficiency follows the normal distribution with a parameter of (0.8, 0.2). The remaining battery of the mobile device held by the worker follows a normal distribution with the parameter (70, 20). The cost of each worker recruited to the MCS platform is set to 2, the cost of performing the task is set to 0.5 each slot, and the cost per unit of movement distance of the participatory worker is set to 2.

4.2 Evaluation Results

In this section we will present the results of the simulation experiment. We can observe the impact of various parameters on the sensing quality of task, the number of tasks completed, the total sensing cost and the total movement distance of the worker. If the task’s sensing quality is not less than 0.6, we say that the task is completed.

Impact of Total Budget. We first investigate the impact of the budget on the performance. We set the number of tasks to 30, the number of workers to 80 and the $\gamma$ value to 3. The budget is change from 300 to 900. The results are shown in Figs. 1 and 2.

Fig. 1.

Task sensing quality under different total budget.

Fig. 2.

Task completed number under different total budget.

Fig. 3.

Task sensing quality under different task number.

Fig. 4.

Task sensing cost under different task number.

In Fig. 1, we can observe that, as the budget increases, the average task sensing quality also increases for three schemes. This is because a higher budget allows more workers recruited to perform tasks. Since our MSHTA scheme considers the advantages of the two sensing modes simultaneously, the average sensing quality of our MSHTA scheme is more than other schemes. Moreover, our MSHTA scheme can complete more tasks than other two schemes, which is demonstrated by Fig. 2. Because the participatory workers in PAR need more incentives to perform tasks, it only can complete fewer tasks when the budget is 300, and the average task sensing quality in PAR is smallest.

Impact of Task Number. To study the impact of task number, we keep the number of workers, budget and $\gamma$ value fixed, i.e., n = 80, $B=600$ and $\gamma = 3$, and task number in the range of 10, 20, 30, 40, 50. Then, we observe the changes in the task average sensing quality and sensing cost, as shown in Figs. 3 and 4.

It is obvious that in Fig. 3 the average task sensing quality decreases as the task number increasing, that is because with the number of task increases, more tasks require more workers and budget to perform tasks. Since MSHTA scheme aggregates the advantages of two sensing modes in terms of sensing cost and sensing quality, it has a higher average task sensing quality than other schemes.

Figure 4 shows the performance of three schemes in the sensing cost under different task number. Although the MSHTA scheme cannot achieve the lowest sensing cost due to the workers’ mobile cost, but its task sensing quality is the highest among the three schemes.

Impact of $\gamma$ Value. Then, we evaluate the impact of the $\gamma$ value. The value of $\gamma$ is varied from 1 to 5 with the increment of 1. We set the number of workers to 80, the budget to 600 and the number of tasks to 30. The results are shown in Figs. 5 and 6.

Figure 5 shows that as the value of $\gamma$ increases, the average task sensing quality is decreasing, this is because as the $\gamma$ increases, more worker and more budget are required to perform the task. Combined with Fig. 6, we can see that MSHTA scheme achieves the highest sensing quality of task when need a lower sensing cost. That is because MSHTA scheme assign tasks to workers with higher sensing quality and lower sensing cost.

Fig. 5.

Task sensing quality under different sensor reading threshold.

Fig. 6.

Task sensing cost under different sensor reading threshold.

Fig. 7.

Task sensing quality under different worker number.

Fig. 8.

Moving distance of worker under different worker number.

Impact of Worker Number. Finally, we study the impact of the worker’s number on the performance. We set the number of tasks to 30, the $\gamma$ value to 3 and the budget to 600. The results are shown in Figs. 7 and 8.

From Fig. 7, we can see that the average task sensing quality increase as the number of workers increases for three task allocation schemes. This is because as the number of workers increases, there will be workers who are more responsive for tasks’ sensing requirements. And the performance of MSHTA scheme is better than other schemes under different number of workers.

As shown in Fig. 8, because the moving distance of the workers in our scheme is shorter than that in PAR scheme, our scheme can achieve a lower sensing cost. Compared with OPP scheme, although our scheme has a higher sensing cost, it is much higher than the OPP scheme in terms of tasks’ sensing quality.

5 Conclusion

In this paper, we studied a novel heterogeneous task allocation problem in the MCS scenario where two sensing modes coexist. First, we introduced the system model of our MCS scenario and formalized the problem of the heterogeneous task assignment problem with the coexistence of two sensing modes. Then, we proposed a two-phase task assignment algorithm MSHTA to solve this problem, which aggregates the advantages of two sensing modes. In the first phase, MSHTA selects a set of opportunistic workers to perform tasks during their daily life; in the second phase, MSHTA reassigns the tasks with lower sensing quality to participatory workers and requires them move to the specified region to perform the task. Finally, simulation experiments show that the performance of our task assignment scheme is better than other two benchmark schemes.