Keywords

1 Introduction

Recently, mobile crowdsensing [2] has become a cost-effective way to collect massive sensing data and thus enabled tremendous real-world applications such as environment monitoring, traffic condition monitoring, and smart city [3, 7, 8, 12]. In a mobile crowdsensing system, the service platform recruits mobile users to perform tasks by exploiting the sensing and computing ability of smart devices at the users.

Based on whether tasks are performed consciously by users, existing work for mobile crowdsensing can be categorized into two types: opportunistic sensing and participatory sensing. In opportunistic sensing, users move following their daily routines and complete sensing tasks with minimum disturbance. Sensing data along their moving paths can be collected automatically without human involvement and thus leads to low employment expenses of opportunistic sensing users. However, since the paths taken by opportunistic sensing users are predetermined based on users’ moving patterns, tasks not on any mobile user’s path will not be performed. This often results in limited task coverage. In contrast, the moving paths of participatory sensing users are scheduled by the service platform. Service platform can ask such users to move to any task location within their travel capability to perform tasks at the cost of high employment expenses.

Task assignment [4] is one of the most important problems for mobile crowdsensing. In participatory sensing, [9] aims to minimize the task expiration penalty by user selection and path planning, while [5] studied the problem of user selection and path planning in an online manner to maximize total task quality under given travel budget. In opportunistic crowdsensing, [10] studied the multi-objective optimization problem of maximizing total task quality under energy consumption constraints of users’ smart devices. [11] studied the problem of maximizing total task quality under incentive budget constraint and proposed an approximation algorithm exploiting the submodular property of the used utility function. High task quality and low employment expenses are two crucial goals in the design of effective task assignment mechanisms for mobile crowdsensing. However, the above two crowdsensing paradigms cannot meet these two goals simultaneously. In this paper, we propose a new mobile crowdsensing paradigm called semi-opportunistic mobile crowdsensing. The motivation behind our work in this paper is as follows. For traditional opportunistic mobile crowdsensing, each user moves to predetermined destination along a fixed path. However, in reality, a user may take one path from multiple choices (e.g., most frequently taken paths or most economical paths) to reach the same destination without much disturbance of her daily routine. For a mobile user, each such path is a reasonably good choice for her to make the trip. For the platform, the task assignment performance can be significantly improved since tasks are typically randomly distributed at different locations and in this case the platform has much more choices for task assignment due to the increased path set from the user side. In this way, task coverage probability can be greatly improved with slightly increased human involvement.

In this paper, we first propose the semi-opportunistic mobile crowdsensing paradigm. In this paradigm, each user provides multiple candidate paths for the service platform to choose from. We describe in details how this new paradigm works. We then formulate the optimal task assignment problem, which jointly chooses mobile users and their taken paths and also tasks for them to perform with an objective to maximize the total task quality subject to given incentive budget constraint and user travel time constraints. We prove this problem is NP-hard and then propose two efficient heuristic algorithms to address this problem. First, we propose a Best Path/Task first algorithm (BPT) which always chooses current best path and current best task into the assignment list. Second, we propose an LP-relaxation based algorithm (LPR), which greedily assigns paths and tasks with the largest values in LP relaxation solution. We deduce the computational complexities of the proposed algorithms. We evaluate the performance of our algorithms on real-world traces. Simulation results show our proposed algorithms are very close to the optimal solution and significantly outperform the case when pre-determined single path is used for each user.

The rest of this paper is organized as follows. We describe the system model and formulate the problem under study in Sect. 2. We propose our algorithms in Sect. 3. We present the simulation results in Sect. 4. We conclude the paper in Sect. 5.

2 Problem Statement

In this section, we describe the semi-opportunistic sensing system, formulate the problem under study, and prove its NP hardness.

2.1 Crowdsensing Paradigm

In this subsection, we introduce the semi-opportunistic sensing system, which consists of a crowdsensing service platform and a set of mobile users.

Mobile User. A mobile user is going to some place in a future time interval (e.g., 7:00–9:00 tomorrow morning). She has a travel time budget (e.g., two hours of commuting time), and fortunately, the actual travel time is less than that. She can use the remaining time to perform some sensing tasks on her travel path to make some money. To reach her destination, she may have multiple candidate paths for the trip. Due to different traffic conditions, each path has distinct travel time and thus distinct remaining time for task performing. She can ask the service platform for compensation of her task performing behavior. She then submits her application form containing her suggested paths to the service platform along with corresponding estimated available task performing time and also demanded compensation for each path. Without causing confusion, hereafter, we shall use the terms “user” and“worker” interchangeably unless otherwise stated.

Service Platform. The crowdsensing service platform receives a set of task performing requests which need to be done in a specific future time interval with a total incentive budget to support the task performing. Each task is submitted with detailed task attributes including task location, task performing time, and task quality requirement. We will discuss the task model in Subsect. 2.2. The platform also receives a list of task performing applications with detailed path information from mobile users who are willing to perform tasks in this time interval. The platform jointly chooses mobile users and their taken paths and also tasks for them to perform. The objective is to maximize the sum of task quality subject to total incentive budget and user’s path travel time budget.

Semi-opportunistic Crowdsensing Paradigm. Our crowdsensing paradigm is composed of the following steps:

  • First, the crowdsensing service platform announces a specific future time interval and recruits mobile user to perform tasks in this time interval.

  • Second, each mobile user who is willing to undertake tasks in that future time interval submits to the service platform her suggested moving paths in that time interval, with corresponding task performing time and demanded compensation for each path.

  • Third, the platform selects mobile users to perform tasks and informs each selected user which path to take and also which task(s) to perform.

  • Fourth, each mobile user travels along the designated path, performs assigned task(s), and finally receives demanded compensation.

2.2 System Model

The three layer task assignment process is illustrated in Fig. 1. The platform selects a set of mobile users to perform tasks on their paths. For each user, one path in her given path set is selected by the platform, if the user is chosen for performing task(s). Some task(s) on this path are then assigned to the user as long as her travel time budget is not violated.

Fig. 1.
figure 1

Three layer task assignment process. The red ones are selected. (Color figure online)

Full size image

Worker Model. We denote the users by user set \(\mathcal {I} = \left\{ 1, 2, \cdots , I \right\} \). Each user has a starting point and a destination point. Each user has several path choices for her to reach her destination. We define decision variable \(x_i = 1\) if the user \({i \in \mathcal {I}}\) is selected to perform task, or otherwise \(x_i = 0\).

Path Model. Each user has multiple path choices to reach her destination. We denote the path set of user \({i \in \mathcal {I}}\) as path set \(\mathcal {K}_i = \left\{ 1, 2, \cdots , K_i \right\} \). Each path is a simple path from a departure place to a destination passing through a few streets or blocks. Each path \(k_i \in \mathcal {K}_i\) has a fixed incentive reward \(r_{i{k_i}}\) and a time budget \(T_{i{k_i}}\) for performing tasks on this path. Different workers demand different incentive rewards for different paths which depend on time budgets of the paths and labor costs per unit time for recruiting the users. We define decision variable \(y_{ik_i} = 1\) if user i is selected to travel along path \(k_i\), or otherwise \(y_{ik_i} = 0\). Each user can only take one of her provided path choices, and thus we have:

$$\begin{aligned} x_i = \sum _{k_i}{y_{ik_i}}, \quad \forall i \in \mathcal {I} \end{aligned}$$
(1)

The total incentive cannot exceed the platform given incentive budget B, thus we have:

$$\begin{aligned} \sum _i\sum _{k_i}{r_{i{k_i}}\cdot {y_{ik_i}}} \le B \end{aligned}$$
(2)

Task Model. We denote the task set as \(\mathcal {J} = \left\{ 1, 2, \cdots , J \right\} \). Each task \(j \in \mathcal {J}\) is associated with a specific location, task performing time \(t_j\), and task quality \(q_j\). Due to different task types and performing difficulties, tasks have different performing times. Task quality can be indicated by the information value of the task location [11] or the probability of giving a correct answer for an event by majority voting [5]. We define \(w_{i{k_i}j} = 1\) if task \(j \in \mathcal {J}\) is along the path \(k_i\) of user i, or otherwise \(w_{i{k_i}j} = 0\). We define decision variable \(z_{i{k_i}j} = 1\) if task \(j \in \mathcal {J}\) is assigned to user i on her path \(k_i \in \mathcal {K}_i\), or otherwise 0. We have

$$\begin{aligned} z_{i{k_i}j} \le w_{i{k_i}j},\quad \forall j \in \mathcal {J}, i \in \mathcal {I}, {k_i} \in \mathcal {K}_i \end{aligned}$$
(3)

Each path is associated with zero, one, or several tasks to perform and the total task performing time cannot exceed the path-related task performing time budget. Therefore, we have:

$$\begin{aligned} \sum _{j}{{t_j}\cdot {z_{i{k_i}j}}} \le T_{i{k_i}} \cdot {y_{ik_i}},\quad \forall i \in \mathcal {I}, {k_i} \in \mathcal {K}_i \end{aligned}$$
(4)

Task j can only be performed by user i taking path \(k_i\) if path \(k_i\) of user i is selected by the platform, thus we have:

$$\begin{aligned} z_{i{k_i}j} \le {y_{ik_i}} ,\quad \forall j \in \mathcal {J}, i \in \mathcal {I}, {k_i} \in \mathcal {K}_i \end{aligned}$$
(5)

We assume each task needs to be done no more than once. Thus, we have

$$\begin{aligned} \sum _{i}\sum _{k_i}{z_{i{k_i}j}} \le 1,\quad \forall j \in \mathcal {J} \end{aligned}$$
(6)

2.3 Problem Formulation

The task assignment problem of maximizing the sum of quality of all the tasks subject to the incentive budget constraint and travel time constraints is formulated as follows:

$$\begin{aligned} max \quad \sum _{i,k_i,j} {q_j} \cdot {z_{i{k_i}j}}\quad \quad \quad \quad \quad \quad \quad \end{aligned}$$
(7)

The hardness of the above problem is given as follows. We consider a simplified case where there is only one user who has exactly one path to take and the platform can afford her incentive reward. Then the problem is to maximize the total task quality under the user’s task performing time budget. This is a 0-1 knapsack problem. Here, the item weight is task performing time and the sum of item weights cannot exceed the weight capacity (i.e., the user’s task performing time budget). Moreover, here, the value of an item is the quality of a task and the objective is to maximize the sum of values of chosen items. The 0-1 knapsack problem is known to be NP-hard. Therefore, the problem under study in this paper is also an NP-hard problem.

3 Proposed Task Assignment Algorithms

There are two resource constraints (i.e., incentive reward and per-path-related task performing time) in the task assignment problem under study. Incentive reward constraint is a high-layer constraint from the service platform and path-related task performing time constraint is a low-layer constraint from the user side. In this section, we propose two efficient heuristic algorithms to address the NP-hard task assignment problem formulated in Subsect. 2.3. First, we propose Best Path/Task First Algorithm (BPT) which always chooses current best path and current best task into the assignment list. Second, we propose an LP-relaxation based algorithm, which greedily assigns paths and tasks with largest values into the LP relaxation solution.

3.1 Best Path/Task First Algorithm (BPT)

In this subsection, we propose BPT algorithm. The algorithm is composed of two major components: Task Selection and Path Selection.

Task Selection. For each of the candidate paths provided by users, the Task Selection process selects a set of still available tasks leading to the maximum task quality while meeting the path-related task performing time constraint. This is a 0-1 knapsack problem and is known to be NP-hard. Here, an approximate algorithm is presented for the Task Selection, which works as follows.

  1. 1.

    Sort all still available tasks on this path in the descending order according to the ratio of task quality and performing time.

  2. 2.

    If the sum of task performing time of all still available tasks is no larger than task performing time budget, then all tasks are selected.

  3. 3.

    Otherwise, find the maximum number m such that the first m tasks in the task list meet the following condition: These m tasks’ total task performing time is smaller than or equal to the task performing time budget while the first \((m+1)\) tasks’ total task performing time is larger than the task performing time budget. If the sum of task quality of the first m tasks are smaller than the task quality of the \((m+1) ^{th}\) task and the task performing time of the \((m+1) ^{th}\) task is not larger than the task performing time budget, then the \((m+1) ^{th}\) task is selected, otherwise the first m tasks are selected.

The above steps for Task Selection work in spirit similar to the 2-approximate algorithm in [1] and thus also has an approximate ratio of two.

Path Selection. This process aims to select a set of users and designate a specific path to each of them with an objective of maximizing the total task quality under incentive budget. For this purpose, we propose a greedy algorithm which works as follows.

  1. 1.

    Compute the sum of task quality of tasks available to be performed on each candidate path using the above Task Selection algorithm.

  2. 2.

    Compute the quality/incentive ratio (i.e., the ratio of sum of quality of all tasks (temporarily) assigned to a path to the path-related incentive reward) of each path.

  3. 3.

    Select the path with the largest ratio and go to step 1 if the incentive budget constraint is not violated after the selection.

  4. 4.

    If the incentive budget constraint is violated after adding the path in the above step, and if the total task quality of this path is larger than the sum of total task quality of all previously selected paths, then abandon all the previously-selected paths and take this path.

The detailed procedure for BPT is given in Algorithm 1. Lines 1–2 are for initialization. Lines 3–40 iteratively choose the path leading to the largest quality/incentive ratio while Lines 10–26 give detailed procedure for selecting tasks for each candidate path. More specifically, line 3 ensures that the incentive budget constraint is not violated. In line 4, \(i^*\), \(k^*\), and \(Q^*\) record the user, path, and path-specific total task quality for the so far best path, respectively. P records the ratio of total task quality and incentive for the so far best path, whose initial value is zero. Lines 6–8 ensure that at most one path is selected for each user. Line 10 ensures to choose tasks which are on the current path and further have not been selected by any other path. Lines 12–13 consider the case when the task performing time budget is large enough to cover all the tasks on the path. Lines 14–22 determine whether to take the first m tasks or the \((m+1)^{th}\) task. Lines 24–26 select the path with the largest ratio of overall task quality to the incentive for taking the path. Lines 30–32 add paths into the assignment list if the incentive budget constraint is not violated. Lines 34–38 take the last path and abandon all previously-selected paths if the task quality of the last path is larger than the sum of all the previously-selected paths.

The computational complexity for the Task Selection in lines 10–26 is O(Jlog(J)) due to the task sorting operation. Thus, the computational complexity of BPT is \(O({I^2}KJlog(J))\), where I, K, J denote the number of users, number of path choices of a user, and number of tasks, respectively.

figure a

3.2 LP-Relaxation Based Algorithm(LPR)

We propose an LP-relaxation based algorithm, which greedily assigns paths and tasks with largest values in Linear Programming(LP) relaxation solution. The algorithm is composed of LP-relaxation based initialization and greedy task assignment.

LP-Relaxation Based Initialization. The 0–1 integer constraints of \(x_i\), \(y_{i{k_i}}\), and \(z_{i{k_i}j}\) are relaxed as follows:

$$\begin{aligned} 0 \le x_i \le 1, 0 \le y_{i{k_i}} \le 1, 0 \le z_{i{k_i}j} \le 1,\quad \forall j \in \mathcal {J}, i \in \mathcal {I}, {k_i} \in \mathcal {K}_i \end{aligned}$$
(8)
figure b

After the relaxation, the new problem can be solved by a linear programming solver in polynomial time. And we use \(x_i^*\), \(y_{ik_i}^*\), \(z_{i{k_i}j}^*\) to denote the optimal solution of this linear programming problem.

Greedy Task Assignment. The greedy task assignment is composed of path selection and task selection. The algorithm iteratively selects the path with the highest value of \(y_{ik_i}^*\) if the user of this path has not yet been selected and the total incentive budget is not violated after selecting this path. For each selected path, the algorithm iteratively selects the task with the highest value of \(z_{i{k_i}j}^*\) if the task j has not yet been selected and the total task performing time budget of this path is not violated after selecting this task. This algorithm is feasible since the incentive budget constraint and task performing time constraint are not violated.

LPR is described in Algorithm 2. Line 2 runs the linear programming algorithm to obtain the relaxed solution. Lines 5–9 select the path with the maximum value of \(y_{ik_i}^*\) into the assignment list. Lines 11–18 iteratively select the task with the maximum value of \(z_{i^*k^*j}^*\) into the assignment list.

The computational complexity of solving linear programming problem is polynomial. The computational complexity of Greedy Task Assignment is O(IKJ). Therefore the computational complexity of LPR is polynomial.

4 Performance Evaluation

In this section, we conduct extensive simulations to evaluate the performance of our proposed algorithms. We shall describe detailed simulation settings, the traces that we use, and finally present the simulation results.

We compare our algorithms with optimal solution on real-world traces. The optimal solution is obtained by using branch and cut algorithm which is a time-consuming algorithm. We denote the optimal solution as \(Semi\_opt\). We also compare our algorithms with the traditional opportunistic sensing paradigm where each mobile user only takes one pre-determined path which is her most frequently taken path. The optimal solution for this traditional opportunistic sensing paradigm is referred to as \(Oppt\_opt\). In addition, in our simulations, average task quality equals to total task quality divided by total task number. The default parameter settings are shown in Table 1.

Table 1. Default parameter settings.
Full size table

We use two real-world traces Geolife dataset [13] and NCCU dataset [6] to evaluate the performance of our proposed algorithms. Geolife dataset [13] was collected by 182 users and contains 17,621 trajectories. The majority of the data was created in Beijing, China. We use trajectories in main urban zone of Beijing city which is of 17 km \(\times \) 18 km. The transportation mode of these users includes driving, taking a bus, riding a bike, and walking. NCCU dataset [6] was collected by 115 college students for 15 days in a campus environment of 3764 m \(\times \) 3420 m. Similar to [10], we divide the areas into square subareas. Mobile users move among different subareas and user paths are sequences of subarea indexes. We divide the area of Geolife dataset into \(20 \times 20\) subareas and divide the area of NCCU dataset into \(10 \times 10\) subareas. In these two datasets, paths were chosen based on frequencies that they were taken in the datasets.

We evaluate the average performance of different algorithms on real-world traces. In Figs. 2(a) and 2(b), as the number of paths K increases, average task quality of \(Semi\_opt\), LPR, and BPT increases as well. The performance of LPR and BPT is close to \(Semi\_opt\). The performance of \(Semi\_opt\) and that of \(Oppt\_opt\) are the same when \(K=1\) since they both choose the most frequently taken path for each user and use optimal algorithm for task assignment. When \(K>1\), \(Semi\_opt\), LPR, and BPT have better performance than \(Oppt\_opt\) which again validates the effectiveness of our proposed crowdsensing paradigm.

Fig. 2.
figure 2

Performance comparison of different algorithms on real-world traces.

Full size image

5 Conclusion

In this paper, we proposed a new mobile crowdsensing paradigm called semi-opportunistic sensing where each mobile user has multiple path choices to take to reach her destination. We formulated the optimal task assignment problem, which aims to select proper mobile users taking proper paths and assign tasks to maximize the total task quality while meeting given incentive budget constraint and travel time constraints. We proved the problem is NP-hard and proposed two efficient algorithms. We presented detailed algorithm design and deduced their computational complexities. We conducted extensive simulations on real-world traces. Simulation results validate the effectiveness of our proposed crowdsensing paradigm and further the results show that the performance of our proposed algorithms is close to the optimal solution.