Sage Journals: Discover world-class research

Abstract

The development of modern vehicles equipped with various sensors and wireless communication has been the impetus for vehicular crowdsensing applications, which can be used to complete large-scale and complex social sensing tasks such as monitoring road surfaces condition. However, most of the sensing tasks are closely related with specific location and required to be performed in certain area, and in this article, we have proved these kind of location-based optimal task assignment to be an NP-hard (non-deterministic polynomial-time hard) problem. To solve this challenge, we first establish mathematical model of multi-vehicle collaborative task assignment problem, considering vehicle’s time budget constraint, location, and multiple requirements of sensing tasks. And we propose an approximation location-based task assignment mechanism for it, which is composed of two parts: the first part is to determine the allocating order among engaged vehicles and the second part is to schedule optimal sensing path for single vehicle, which in this article we propose an optimal sensing path scheduling algorithm to finish this task. Using Lingo software, we prove the efficiency of the proposed optimal sensing path scheduling algorithm. Extensive simulation results also demonstrate correctness and effectiveness of our approach.

Keywords

Location-dependent task assignment NP-hard approximate assignment mechanism vehicular crowdsensing

Introduction

By leveraging mobile vehicles as basic sensing units which cope through wireless network, vehicular crowdsensing is a new tool for pervasive information collection, sharing, and exploration,¹ which can be used to complete large-scale sensing application at a lower cost. Many large-scale sensing tasks, such as traffic network monitoring, need to collect large number of sensing data in order to get reliable result. Unfortunately, measuring traffic network from a limited number of observation points is not sufficient to capture all the details, especially at the fringes of network.² Thus, by outsourcing sensing task to the crowd of vehicles, such large-scale sensing activity can be performed at a societal scale, using numerous vehicles scattered over a wide geographic area, which can not only guarantee the quality of data collected but also reduce sensing cost.

Vehicular crowdsensing is a research branch of mobile crowdsensing, which not only utilizes vehicles but also mobile smart devices such as smartphones to perform sensing tasks. At present, research about mobile crowdsensing mainly focuses on the following aspects. (1) Crowdsensing systems built up to enable specific large-scale sensing task, such as network monitoring, cooperative localization, and environment monitoring.^3,4 (2) Incentive mechanism. Since contributing sensing data consumes energy and bandwidth, mobile device often do not want to participate, thus it is essential to incentive mobile devices to provide sensing services.^5,6 (3) Task assignment mechanism. Since mobile devices differ greatly in sensing and processing capabilities, it is important to assign appropriate tasks to individuals who can solve the problem properly according to the characteristics of the task.⁷ Using an efficient task assignment mechanism, we can make full use of the capability of the masses. Moreover, to increase the quality of the results obtained through crowdsourcing, an accurate evaluation of the results of each task is required.^8–12 (4) Reliable and privacy-preserving crowdsensing method. Due to the anonymity and low pay of mobile devices in crowdsourcing platforms, there may be concerns regarding reliability and privacy-preservation when using such platforms to deliver services.¹³

In terms of sensing task assignment, since most sensing tasks are location dependent, it is important to consider both vehicles’ location and tasks’ required performing area. What’s more, since owners of vehicle have a limited time budget each day, he or she has limited capacity in performing the sensing task. Yang et al.⁸ introduced the shifting method for unit disk model into task assignment problem, aiming at maximizing the utility of crowdsensing platform. In the above method, each sensing task was strictly allocated to one vehicle, which can reduce the cost of the platform. However, since there is no redundancy, the data collected may be unreliable. What’s more, the method only considered vehicles’ location as allocation factor, which is one-sided. He et al.^9,10 took into account vehicles’ time budget and deployed redundancy to ensure reliability. However, they did not consider the characteristics of task, for example, quality demands of task, which is essential during allocation process.

In this article, we establish a location-based task assignment (LBTA) mechanism according to the characteristics of the location-dependent tasks and vehicles, aiming at maximizing the utility of crowdsensing platform. We consider the following three factors for allocation.

First, total traveling time of performing a set of sensing tasks which depends on both the location of vehicles and the required performing areas of a set of sensing tasks. Since each owner of vehicle has a time budget constraint, it is essential to consider both owner’s time budget constraint and total traveling time of a set of sensing tasks.

Second, the type of sensing task may also influence task allocation. In this article, we propose two types of tasks: compulsory tasks and original tasks, which will be described in detail later.

Finally, in order to ensure the completion quality of tasks, it is desirable to introduce redundancy by giving each task to several vehicles and aggregating the individual results by some fusion rules, that is, multiple vehicles may need to coordinate to perform the same sensing task.

Our contributions are three-folds:

We study the problem of location-based task allocation by taking into account the geographical characteristics of both sensing tasks and vehicles, quality requirements of tasks, and time budget constraint of owners of vehicles. We formulate the mathematical model of multi-vehicle collaborative task assignment problem considering the above allocation factors and prove that this task assignment problem is NP-hard (non-deterministic polynomial-time hard).

We propose an approximation mechanism called LBTA to solve the above problem, a heuristic algorithm composed of two parts: the first part is to determine the allocating order among engaged vehicles and the second part is to schedule optimal sensing path for single vehicle, which in this article we propose an optimal sensing path scheduling (OPS) algorithm to finish this task. In order to show the effectiveness of OPS algorithm, we compare the solution obtained by OPS with the solution obtained by exact algorithm, which in this article we use Lingo software.¹⁴ The comparison shows that the solution obtained by OPS process is very close to the exact optimal solution.

We conduct extensive simulations, and the results demonstrate correctness and effectiveness of our approach.

The remaining of the article is organized as follows. We introduce the model in section “Modeling and problem formulation,” where we formulate the multi-vehicle collaborative task assignment problem. Then, we present an approximation algorithm LBTA in section “LBTA algorithm.” We report the results of our extensive simulations in section “Simulation evaluation” and conclude our work in section “Conclusion.”

Modeling and problem formulation

We consider a vehicular crowdsensing system, which consists of crowdsensing platform and several vehicles. Due to economical or geographical reasons, individuals with sensing tasks can publish their tasks in the platform and offer some incentives for those who complete these tasks. If the task needs to be completed in a certain geographical position, it is referred as a location-dependent task. In this article, we only discuss allocation scheme for location-dependent task.

Problem formulation

Individuals first publish their tasks in the platform. Then, available vehicles can register and claim for a list of interested tasks to perform. We denote the registered vehicle list as $Vehicle = {vehicl e_{1}, vehicl e_{2}, \dots, vehicl e_{m}}$ and the set of sensing tasks which have been published in the platform as $Task = {tas k_{1}, tas k_{2}, \dots, tas k_{n}}$ . At the same time, a vehicle $vehicl e_{u} \in Vehicle$ can complete more than one sensing tasks.

Since we consider the geographical characteristics of sensing tasks, vehicles which are allocated sensing tasks need to travel to locations associated with these tasks. We refer to the series of tasks allocated to a certain $vehicl e_{u}$ as the sensing path of $vehicl e_{u}$ . In this article, our proposed allocation algorithm will plan the sensing path for each vehicle, aiming at maximizing the utility of platform.

When planning optimal sensing path for each vehicle, we need to consider the following factors:

To guarantee the quality of each sensing $tas k_{j}$ , sensing redundancy is necessary in many applications. Assume each $tas k_{j}$ needs $N_{j}$ independent duplicates to guarantee quality.

The type of sensing task may also influence sensing path planning. In this article, we propose two types of tasks: compulsory tasks and ordinary tasks.

We assume that the reward of the task publisher is ex-ante, that is, he or she has to submit the reward once the mobile vehicle starts to work on the task. Assume $tas k_{j}$ has a reward of $p_{j}$ , which is shared by vehicles and the platform. Particularly, the mobile vehicle receives $λ p_{j} (λ < 1)$ as its reward and the platform charges an amount $(1 - λ) p_{j}$ , which can be regarded as the maintenance cost or the usage fee of the platform. The reward sharing ratio $λ$ is explicitly determined by the protocol designer.

Since vehicles have to travel to locations associated with assigned tasks, it is reasonable to assume that owner of $vehicl e_{u}$ has a time budget constraint $T_{umax}$ .

An illustrative example of this is given in Figure 1. In Figure 1, there are three sensing paths in different colors, and each one of them is assigned to a certain vehicle. The main purpose of this article is to plan sensing path for every mobile vehicle, aiming at maximizing the sum of utilities on these sensing paths.

Figure 1.

An illustration of sensing path planning for three mobile users.

Modeling

According to the problem description in section “Problem formulation,” we formulate the location-dependent task assignment problem as follows.

Given an undirected weighted graph $G = (V, E)$ , $V = {v_{1}, v_{2}, \dots, v_{n}}$ , and a compulsory node set $S \subset V$ . Each node $v_{i}$ represents a sensing $tas k_{i}$ in set $Task = {tas k_{1}, tas k_{2}, \dots, tas k_{n}}$ , which has a score and a time window. Score means the reward a vehicle can gain after performing this task, and time window means this task has to be performed during this time period. Each edge has a weight indicating time used to travel along the edge.

Node in set S represents compulsory task, which means this task must be performed during its time window. Ordinary task is not that important as compulsory one, when vehicles do not have enough time to go through and perform all tasks, some ordinary tasks may be ignored, but the chosen ordinary tasks also need to be performed in their time windows.

$[\begin{matrix} t_{11} & \dots & t_{1 n} \\ ⋮ & ⋱ & ⋮ \\ t_{n 1} & \dots & t_{nn} \end{matrix}]$ represents the time matrix of graph G, and $t_{ij}$ represents the time used to travel from $v_{i}$ to $v_{j}$ ; $(p_{1}, p_{2}, \dots, p_{n})$ represents the reward matrix, and $p_{i}$ represents the reward of performing $v_{i}$ . The time window for node $v_{i}$ is $[e_{i}, l_{i}]$ , which means if the node is selected to be performed, the earliest time to perform is $e_{i}$ and the latest is $l_{i}$ .

For $vehicl e_{u}$ , we define a binary variable $x_{ij}^{u}$ , and its definition is as follows

x_{ij}^{u} = {\begin{matrix} 1 \\ 0, otherwise \end{matrix}, i, j = 1, 2, \dots, n

where $x_{ij}^{u} = 1$ represents that the edge $e_{ij}$ is selected in the sensing path planned for $vehicl e_{u}$ ; $t_{i}$ denotes the time when mobile vehicle arrives at node $v_{i}$ , and if node $v_{i}$ is not selected in the optimal sensing path, then $t_{i} = 0$ .

For $vehicl e_{u}$ , we define $f_{u} : u \in U$ to measure the utility on its sensing path, which can be defined as follows

f_{u} = \sum_{i = 1}^{n - 1} \sum_{j = 2}^{n} (1 - λ) p_{i} x_{ij}^{u}

(1)

Since $vehicl e_{u}$ has a time upper limit $T_{umax}$ , to find the sensing path of $vehicl e_{u}$ is to find a visited route including all compulsory nodes in S, and each selected node needs to be performed in its time window, such that the total time to visit all nodes in sensing path is not more than the time upper limit. We have the following constraints on $x_{ij}^{u}$

\sum_{j = 1, j \neq s}^{n} x_{sj}^{u} = 1

(2)

\sum_{i = 1, i \neq s}^{n} x_{is}^{u} = 1

(3)

\sum_{i = 1}^{n - 1} x_{ik}^{u} = \sum_{j = 2}^{n} x_{kj}^{u} \leq 1 2 \leq k \leq n - 1

(4)

\sum_{i = 1}^{n - 1} x_{ik}^{u} = \sum_{j = 2}^{n} x_{kj}^{u} = 1 k \in S

(5)

e_{i} \leq t_{i} \leq l_{i}

(6)

t_{s} = 0, t'_{s} \leq T_{umax}

(7)

x_{ij}^{u} = {0, 1}

(8)

Suppose the starting node of $vehicl e_{u}$ is $v_{s}$ , and the vehicle will always go back to the starting node. Constraint (2) and (3) means node $v_{s}$ is the starting and ending node of the sensing path. Constraint (4) means that for every node $v_{k}$ , if there is an edge entering into it, there must be another edge leaving it. Constraint (5) means that every node in the compulsory node set S must be selected in the optimal sensing path. Constraint (6) means that time for visiting nodes in sensing path must satisfy time window constraint. Constraint (7) means that the total time used for passing through sensing path cannot be more than $T_{umax}$ . Constraint (8) indicates that $x_{ij}^{u}$ is a binary variable.

Based on the above definitions, we can define the overall utility of mobile sensing as follows

f (U) = \sum_{u \in U} f_{u} = \sum_{u \in U} \sum_{i = 1}^{n - 1} \sum_{j = 2}^{n} (1 - λ) p_{i} x_{ij}^{u}

What’s more, since each $tas k_{j}$ has $N_{j}$ independent duplicates, we have the following constraint

\sum_{u \in U} \sum_{i = 1, i \neq j}^{n} x_{ij}^{u} \leq N_{j}

(9)

We cast the optimal sensing task assignment problem as the following integer program

maximize f (U)

(10)

subject to equations (2) - (9)

(11)

We refer to this problem as the mobile vehicle-sensing utility maximization (MVSUM) problem.

The hardness of MVSUM

In this section, we will show that MVSUM is an NP-hard problem.

Theorem 1

MVSUM is NP-hard. Furthermore, for any $ϵ > 0$ , it is NP-hard to find a polynomial-time solution that achieves at least $1 - (1 / e) + ϵ$ of the maximum utility of spectrum sensing for any instance of MVSUM.

Proof

The hardness follows directly since the maximum coverage problem,¹⁵ an NP-hard problem, is a special case of MVSUM. In other words, it means MVSUM can be degenerated to the maximum coverage problem. If MVSUM can be solved in polynomial time, then so does maximum coverage problem, which is a contradiction.

Since MVSUM is NP-hard, we need to focus on approximation algorithm based on greedy algorithm.

LBTA algorithm

Main algorithm flow of LBTA

Figure 2 presents the workflow of LBTA.

Figure 2.

Dynamic target assignment workflow.

Before starting task allocation process, the platform needs to initialize system parameters including geographical locations of vehicles and sensing tasks, number of duplicates for each sensing task, and its corresponding score. After initialization, the platform generates order allocation among various vehicles and starts a round of task assignment. When it is vehicle_u’s turn, the platform will plan a sensing path for that vehicle using OPS algorithm described in section “OPS based on single vehicle” and update the number of duplicates for each sensing task. If time and resources permit, the platform will generate a new order allocation for vehicles and starts a new round of assignment. If the present scheme is superior to older one,¹⁶ the older one will be replaced. Repeat the above process until time and resources are out of limit, thus establishing a best assignment scheme at present.

OPS based on single vehicle

The algorithm can be described as follows.

1. Sort the order of compulsory nodes.

When sorting the order of compulsory nodes, we are trying to find a shortest possible route that visits each compulsory node exactly once and returns to the original node, which is a classical traveling salesman problem (TSP) and has been proved to be non-deterministic polynomial complete (NPC) problem. Thus, in this article, based on greedy criterion, we sort the order as follows.

Based on the current compulsory node, the platform traverses all non-visited compulsory nodes that are reachable from the current one and selects the nearest one as next node. The platform marks the current node as visited, moves on to the next node, and repeats the greedy strategy until all compulsory nodes have been marked as visited. According to that order, we also need to adjust time window constraint.

After the above process, we get a path $p = {v_{s}, v_{com 1}, v_{com 2}, \dots, v_{comk}, v_{s}}$ , where $v_{com 1}, v_{com 2}, \dots, v_{comk} \in S . v_{s}$ is the starting node of the current vehicle. Every node $v_{comk}$ on path p is a compulsory node except the starting node $v_{s}$ , and these nodes come together as set S. Assume there are k nodes in S, thus compulsory nodes will divide path p into k + 1 sub-paths: $p_{1}, p_{2}, \dots, p_{k + 1}$ , where $p_{1} = {v_{s}, v_{com 1}}$ , $p_{2} = {v_{c o m 1}, v_{c o m 2}}$ ,…, $p_{k + 1} = {v_{comk}, v_{s}}$ .

2. Insert other nodes into the path created in step 1.

First, we try to find a sensing plan for sub-path $p_{1}$ , which is mentioned in step 1 and contains nodes ${v_{s}, v_{com 1}}$ .

In order to do node insertion into sub-path $p_{1}$ , we first introduce a concept called time adjacent neighborhood. Assume there are two task nodes $v_{m}$ and $v_{n}$ , and $t_{m}$ , $t_{mn}$ , and $l_{n}$ represent vehicle’s arrival time at $v_{m}$ , time used for traveling from $v_{m}$ to $v_{n}$ , and latest time to visit $v_{n}$ , respectively. We can define node $v_{m}$ as the time adjacent neighborhood of node $v_{n}$ if $t_{m} + t_{mn} \in [0, l_{n}]$ .

Based on the above definition, we start insertion in backward order, that is, we first deal with node $v_{com 1}$ and find a previous node $v_{i}$ of $v_{com 1}$ to insert into sub-path $p_{1}$ . Then, we treat $v_{i}$ as current node and repeat the above process until we finally reach node $v_{s}$ . Specific steps are as follows.

According to the time window and time distance between nodes, we can get all the time adjacent neighborhood nodes of $v_{com 1}$ , and then select the largest score node as the previous node of $v_{com 1}$ . Mark the current node $v_{com 1}$ as visited, choose the previous node as current node, and repeat greedy strategy until returning back to $v_{s}$ . For other sub-paths in p, repeat the above process, and we can finally get a complete route as a solution. The algorithm is described in Table 1.

Table 1.

Algorithm of OPS based on single vehicle.

Input:

Edge-weighted graph

G = (V, E)

: each node

v_{i}

has an associated non-negative score

w_{i}

, each edge

e_{ij} \in E

has a weight

d_{ij}

, representing time taken to travel from node

v_{i}

to node

v_{j}

Compulsory node set S.

Output: a route of sensing tasks from starting node

v_{0}

to ending node

v_{0}

Algorithm steps:

Step 1. Sort the order of compulsory nodes.

Current node =

v_{comi} \in S

;

Distance = Max;

//Select node

v_{comj}

which is closest to node

v_{comi}

While (S is not empty) {

Fetch a node

v_{comj}

from S.

(d_{ij} < Distance)

{Distance =

d_{ij}

; Next node =

v_{comj}

;}

}

//Treat

v_{comj}

as current node and repeat the process

Remove

v_{comi}

from S and set current node as

v_{comj}

Continue the above process, until compulsory set is empty.

Step 2. Insert other nodes into sub-path created in Step 1.

Current sub-path

p_{1} = {v_{s}, v_{com 1}}

Current node

v_{com 1}

While (

v_{s}

has not been visited) {

Select the largest score node

v_{i}

in time adjacent neighborhood of

v_{com 1}

Mark

v_{i}

as visited and insert

v_{i}

into sub-path

p_{1}

Set current node as

v_{i}

, continue the above process.

}

Continue the above process, until all sub-paths

p_{2}, \dots, p_{k + 1}

have been visited.

Step 3. End of the algorithm.

An illustrative example

In this section, we give a simple example to illustrate how OPS works on a single vehicle. Eight sensing tasks correspond to eight nodes in Figure 3, and tasks 2 and 4 are compulsory nodes. Current vehicle’s time budget is set to be 40 min. Figure 3 represents the situation and related parameters of each node, and Table 2 represents the time distance between every pair of nodes.

Figure 3.

Situation and related parameters of each node.

Table 2.

Time distance between every pair of nodes (minutes).

	0	1	2	3	4	5	6	7	8
0	0	8	10	6	10	8	11	9	14
1	8	0	3	3	14	5	13	10	13
2	10	3	0	5	15	6	12	11	11
3	6	3	5	0	12	3	11	9	10
4	10	14	15	12	0	11	5	4	9
5	8	5	6	3	11	0	9	8	8
6	11	13	12	11	5	9	0	3	5
7	9	10	11	9	4	8	3	0	7
8	14	13	11	10	9	8	5	7	0

The exact solution

In this section, we select node 0 as the starting node. Since the computation scale in this case is not large, we can obtain the exact result by solving the integer linear programming using Lingo software. The exact optimal route is 0-3-1-2-5-7-4-0 with total income 840.

The OPS solution

First, we need to sort the compulsory nodes, which are nodes $v_{2}$ and $v_{4}$ . According to the distance between compulsory node and starting position $v_{0}$ , we get a path $p = {v_{0}, v_{2}, v_{4}, v_{0}}$ .

The compulsory nodes divide path p into 3 sub-paths $p_{1} = {v_{0}, v_{2}}$ , $p_{2} = {v_{2}, v_{4}}$ , and $p_{3} = {v_{4}, v_{0}}$ . We then update time window for compulsory nodes based on user’s time expectation.

The latest arrival time of $v_{4}$ is 40–10 = 30 min, and then the time window of $v_{4}$ is updated as [0, 30]. The latest arrival time of $v_{2}$ is 30–15 = 15 min, and then the time window of $v_{2}$ is updated as [0, 15]. We then need to plan a sensing path for sub-path $p_{1} = {v_{0}, v_{2}}$ .

According to Table 1, the set of time adjacent neighborhoods of $v_{2}$ is ${v_{1}, v_{3}, v_{5}}$ . Since $p_{1} > p_{5} > p_{3}$ , we choose $v_{1}$ as the previous node of $v_{2}$ and update the time window of $v_{1}$ as [0, 12]. Then, calculate the time adjacent neighborhood of $v_{1}$ , which is $v_{3}$ , and update the time window of $v_{3}$ as [0, 9]. We find that no other node can be inserted between $v_{0}$ and $v_{3}$ ; thus, the sensing path planning process for sub-path $p_{1}$ can be terminated. The complete route of $p_{1}$ is ${v_{0}, v_{3}, v_{1}, v_{2}}$ , and the arrival time of $v_{2}$ is updated as 12 min.

By repeating the above process, we can get the complete route of $p_{2}$ as ${v_{2}, v_{5}, v_{7}, v_{4}}$ and the route of $p_{3}$ as ${v_{4}, v_{0}}$ . Then, the complete route of p is ${v_{0}, v_{3}, v_{1}, v_{2}, v_{5}, v_{7}, v_{4}, v_{0}}$ , and we get a total reward 840.

Comparison of above solutions

In this case, solutions obtained by OPS algorithm and Lingo software are the same, but the efficiency of the former algorithm is higher than the later one. This shows that the precise algorithm is suitable for small-scale, high-accuracy demand problem, while heuristic algorithm is suitable for large-scale, time-sensitive problem and can efficiently obtain suboptimal solution.

Simulation evaluation

In this section, we present performance evaluation studies to evaluate the performance of our approach (LBTA algorithm). The goal of the simulation study is to verify the effectiveness of our proposed LBTA algorithm. The simulation is based on MyEclipse development environment.

Simulation setup

In MyEclipse development environment, we set m vehicles and n sensing tasks distributed in a 15 km × 15 km region randomly. To simulate actual sensing task allocation process, first we set each vehicle’s time budget T_max to be a random variable $T + σ$ , where T is a constant and $σ$ subjects to uniform distribution in range [−10, 10]. Second, the rewards for different tasks may differ due to diversity of sensing tasks, thus we define random variable $P + α$ as reward p when completes a task, where P is a constant and $α$ subjects to uniform distribution in range [−3, 3]. Finally, to simplify the problem, we assume that tasks only have requirement in latest time, which means time window of tasks would be simplified into $[0, l_{i}]$ , and $l_{i}$ is also set as $L + δ$ , where L is a constant and $δ$ is uniformly distributed in range [−10, 10]. The settings of important simulation parameters are presented in Table 3.

Table 3.

Simulation parameters.

Environment parameters	Settings
Number of sensing tasks, n (default)	25
Number of mobile vehicles, m (default)	20
Proportion of compulsory task: ordinary task	1:3
Redundancy rate of task	[1, 3] uniformly distributed
Vehicle’s speed	36 km/h
Time budget constant, T	40 min
Task reward constant, P	16
Time window constant, L	30
Proportion of vehicle’s utility, $λ$	0.8

During the process of simulation, we conduct each class of experiment for 10 times and we select the average value of these results as final result. Since we make our target of allocation as maximizing the utility of platform, in next steps, we mainly focus on some factors affecting platform utility, which include vehicle’s time budget, number of vehicles, total amount of tasks, and proportion of tasks in different types. We define platform utility as $\max \sum_{i = 1}^{n - 1} \sum_{j = 2}^{n} (1 - λ) p_{i} x_{ij}$ .

Results analysis

1. While the vehicle’s time budget constraint and the proportion of different types of tasks are fixed, we vary the number of sensing tasks n from 25 to 55, while the number of mobile vehicles m are fixed from 10 to 30, respectively. The platform utility obtained by LBTA for each scenario is recorded and the result is plotted in Figure 4.

Figure 4.

Impact of number of sensing tasks and number of vehicles on platform utility.

Figure 4 shows that as the number of mobile vehicles increases, the corresponding platform utility also increases, given that the number of sensing tasks is 25. The reason is that mobile vehicles only conduct sensing tasks within their time budget constraint, so when the number of vehicles is relatively low, part of sensing tasks could not be executed. As the number of vehicles grows, the number of executed sensing tasks will also increase, which leads to overall promotion of platform utility.

When the number of vehicles remains unchanged, platform utility increases as the amount of sensing tasks gets larger. The reason is that, although the number of vehicles and the number of sensing tasks these vehicles are capable of executing remain unchanged, vehicles are more capable of choosing sensing task with higher reward, thus achieving higher platform utility.

2. While the vehicle’s time budget constraint and the number of vehicles are fixed, we vary the number of sensing tasks from 25 to 55, while the proportion of different types of sensing tasks are fixed to 1:3, 1:2, and 1:1, respectively. The platform utility obtained by LBTA for each scenario is recorded and the result is plotted in Figure 5.

Figure 5.

Impact of proportion of different tasks on platform utility.

Compulsory task has to be completed, but its price may be lower than some ordinary tasks. Thus, more compulsory tasks result in lower platform utility.

3. When the number of vehicles and the proportion of different class of tasks are fixed, we vary the number of sensing tasks from 25 to 55, while time budget constraint of vehicles is fixed from 30 to 50, respectively. The platform utility obtained by LBTA for each scenario is recorded and the results are plotted in Figure 6.

Figure 6.

Impact of time budget constraint on platform utility.

Clearly, as the vehicle’s time budget constraint increases, the total utility of the platform increases. This is because when the time budget is lower, the number of sensing tasks performed by the vehicles is lower as well. As the time budget grows, the number of performed sensing tasks will increase, and the corresponding platform utility grows too. Once the vehicle’s time budget is big enough, vehicles will be able to finish all sensing tasks, which achieves maximum of platform utility.

4. Platform utility obtained by LBTA versus utility obtained by greedy algorithm

Finally, we show the advantage of LBTA. Our proposed LBTA can deal with sensing task assignment problem with compulsory nodes, for which there is no such existing algorithm. Thus, we choose greedy algorithm for comparison. Greedy algorithm solves the task allocation problem for single vehicle greedily, which uses existing orienteering algorithm to allocate sensing tasks, and sensing task is strictly allocated to one vehicle.

We vary the number of sensing tasks n from 25 to 55, while the number of vehicles is fixed to 15, 20, and 25. We plot the result in Figure 7(a). And we vary the number of sensing tasks n from 50 to 100, while the number of vehicles is fixed to 20, and the proportion of compulsory tasks versus ordinary tasks is fixed to 1:3. The result is plotted in Figure 7(b).

Figure 7.

(a) Platform utility obtained ratio from LBTA and greedy algorithm. (b) Compulsory task completion achieved by LBTA and greedy algorithm.

From Figure 7(a), it is clear that the platform utility obtained from LBTA is approximately the same as greedy algorithm. However, from Figure 7(b), as for the compulsory task completion ratio, greedy algorithm only accomplishes an average of 68.3%, while LBTA achieved 95.5% on average. This shows the significant advantage of LBTA over greedy algorithm.

Conclusion

In this article, we studied the problem of allocating location-dependent tasks in vehicular crowdsensing applications. We first introduce several allocation factors, which have not been considered in previous work. Then, we focus on the task allocation problem and show that the problem is NP-hard and propose an efficient algorithm, LBTA. Moreover, we provide an illustrative case to help explain the LBTA. Extensive simulation results prove the effectiveness of our proposed LBTA algorithm.

Footnotes

Academic Editor: Sangheon Pack

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Natural Science Foundation of China (nos 61302078 and 61372108) and Funds for Creative Research Groups of China (no. 61121061).

References

Han

Zhang

Luo

. Truthful scheduling mechanisms for powering mobile crowdsensing. IEEE T Comput 2016; 65(1): 294–307.

Faggiani

Gregori

Lenzini

. Smartphone-based crowdsourcing for network monitoring: opportunities, challenges, and a case study. IEEE Commun Mag 2014; 52(1): 106–113.

Gregori

Lenzini

Luconi

. Sensing the internet through crowdsourcing. In: Proceedings of the IEEE international conference on pervasive computing and communications workshops (PERCOM workshops), San Diego, CA, 18–22 March 2013. New York: IEEE.

Huang

Tomasic

. Energy efficient and accuracy aware (E2A2) location services via crowdsourcing. In: Proceedings of the IEEE 9th international conference on wireless and mobile computing, networking and communications (WiMob), Lyon, 7–9 October 2013. New York: IEEE.

Yang

Xue

Fang

. Incentive mechanisms for crowdsensing: crowdsourcing with smartphones. IEEE/ACM T Network 2016; 24(3): 1732–1744.

Zhang

Van der Schaar

Reputation-based incentive protocols in crowdsourcing applications. In: Proceedings of the IEEE INFOCOM, Orlando, FL, 25–30 March 2012. New York: IEEE.

Lee

Park

. A quality enhancement of crowdsourcing based on quality evaluation and vehicle-level task assignment framework. In: Proceedings of the international conference on big data and smart computing (BIGCOMP), Bangkok, 15–17 January 2014. New York: IEEE.

Yang

Yu’e

A location-based task assignment mechanism for mobile phone sensing. J Comput Res Dev 2014; 51(11): 2374–2381.

Shin

D-H

Zhang

. Toward optimal allocation of location dependent tasks in crowdsensing. In: Proceedings of the IEEE INFOCOM, Toronto, ON, Canada, 27 April–2 May 2014. New York: IEEE.

10.

Shin

D-H

Zhang

. Near-optimal allocation algorithms for location-dependent tasks in crowdsensing. IEEE T Veh Technol 2016; 99: 1–1.

11.

Yang

Shi

Leveraging crowdsourcing for efficient malicious users detection in large-scale social networks. IEEE Internet Things J 2016; 99: 1–1.

12.

Shin

D-H

Zhang

. Joint sensing task and subband allocation for large-scale spectrum profiling. In: Proceedings of the IEEE INFOCOM, Kowloon, Hong Kong, 26 April–1 May 2015. New York: IEEE.

13.

Varshney

LR.

Privacy and reliability in crowdsourcing service delivery. In: Proceedings of the annual SRII global conference (SRII), San Jose, CA, 24–27 July 2012, pp.55–60. New York: IEEE.

14.

https://en.wikipedia.org/wiki/Lingo_(programming_language)

15.

Hochbaum

DS.

Approximation algorithm for NP-hard problems. Boston, MA: PWS Publishing Company, 1997.

16.

Zong Ji

. Dynamic target assignment method based on multi-agent decentralized cooperative auction. J Beijing Univ Aeronaut Astronaut 2007; 33(2): 180–183.

	0	1	2	3	4	5	6	7	8
0	0	8	10	6	10	8	11	9	14
1	8	0	3	3	14	5	13	10	13
2	10	3	0	5	15	6	12	11	11
3	6	3	5	0	12	3	11	9	10
4	10	14	15	12	0	11	5	4	9
5	8	5	6	3	11	0	9	8	8
6	11	13	12	11	5	9	0	3	5
7	9	10	11	9	4	8	3	0	7
8	14	13	11	10	9	8	5	7	0

	0	1	2	3	4	5	6	7	8
0	0	8	10	6	10	8	11	9	14
1	8	0	3	3	14	5	13	10	13
2	10	3	0	5	15	6	12	11	11
3	6	3	5	0	12	3	11	9	10
4	10	14	15	12	0	11	5	4	9
5	8	5	6	3	11	0	9	8	8
6	11	13	12	11	5	9	0	3	5
7	9	10	11	9	4	8	3	0	7
8	14	13	11	10	9	8	5	7	0

A location-dependent task assignment mechanism in vehicular crowdsensing

Abstract

Keywords

Introduction

Modeling and problem formulation

Problem formulation

Modeling

The hardness of MVSUM

Theorem 1

Proof

LBTA algorithm

Main algorithm flow of LBTA

OPS based on single vehicle

An illustrative example

The exact solution

The OPS solution

Comparison of above solutions

Simulation evaluation

Simulation setup

Results analysis

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References

	0	1	2	3	4	5	6	7	8
0	0	8	10	6	10	8	11	9	14
1	8	0	3	3	14	5	13	10	13
2	10	3	0	5	15	6	12	11	11
3	6	3	5	0	12	3	11	9	10
4	10	14	15	12	0	11	5	4	9
5	8	5	6	3	11	0	9	8	8
6	11	13	12	11	5	9	0	3	5
7	9	10	11	9	4	8	3	0	7
8	14	13	11	10	9	8	5	7	0