# Quality-Aware Incentive Mechanism for Mobile Crowd Sensing

Authors: Ling-Yun Jiang; Fan He; Yu Wang; Li-Juan Sun; Hai-ping Huang
Journal: Journal of Sensors
 (2017)

---

## Abstract

Mobile crowd sensing (MCS) is a novel sensing paradigm which can sense human-centered daily activities and the surrounding environment. The impact of mobility and selfishness of participants on the data reliability cannot be ignored in most mobile crowd sensing systems. To address this issue, we present a universal system model based on the reverse auction framework and formulate the problem as theMultiple Quality Multiple User Selection (MQMUS) problem. Thequality-aware incentive mechanism(QAIM) is proposed to meet the quality requirement of data reliability. We demonstrate that the proposed incentive mechanism achieves the properties of computational efficiency, individual rationality, and truthfulness. And meanwhile, we evaluate the performance and validate the theoretical properties of our incentive mechanism through extensive simulation experiments.


---

## Body

## 1. Introduction

A new paradigm of sensing with smartphones has emerged which is usually called people-centric mobile sensing or mobile crowd sensing [1]. Compared with the traditional sensor networks, MCS is an effective way for large-scale data sensing, processing, and gathering without deploying a large number of sensor nodes. MCS has enabled numerous large-scale applications such as urban environment monitoring [2–4], traffic flow surveillance [5–7], healthcare [8], behavior and relationship discovery [9, 10], indoor localization [11], 3G/Wi-Fi discovering [12–14], activity monitoring [15, 16], and bus arrival time prediction [17].The effect of the aforementioned mobile crowd sensing applications relies heavily on the quantities of participants. However, the ordinary individuals are not willing to share their sensing capabilities unless there are sufficient incentives. Research on incentive mechanism has been widely concerned by investigators, and considerable designed schemes about the incentive mechanism design have been put forward which can be classified into nonmonetary incentives [18–20] and monetary incentives [21–29].The key of any crowd sensing system is not only the quantities of participants but also the sensing quality offered by participants. However, most of the existing solutions usually assume that each sensing task (e.g., air quality in a certain region) in a sensing cycle could be performed by a single participant. It is intuitive that the quality of sensing project would be higher if each sensing task was performed by multiple participants. One of the main reasons is that the sensed data cannot always be trusted because participants maybe intentionally (e.g., malicious participants) or unintentionally (e.g., making mistakes) offer the data contrary to the truth. Another reason may come from the recruitment system model itself. A typical MCS consists of two roles: the recruiter who publicizes the sensing tasks and the participants who constitute potential sensing capability selected by the recruiter from many candidates. The interaction between the recruiter and the candidates is modeled as a reverse auction in many existing solutions which can be illustrated by Figure1. The recruiter always selects participants according to the sensing plans of the candidates. However, changes always go beyond plans. The participants may not be able to complete the task according to their schedule for unexpected incidents (e.g., a selected participant cannot go to the specific locations claimed in his sensing plan). These participants may offer some forged data or do nothing. As a result, the tasks could not be completed in time.Figure 1
A typical mobile crowd sensing system as a reverse auction framework.In this paper, we address the issue of quality-aware monetary incentive mechanism design. We design a truthful incentive mechanism satisfying the properties of computational efficiency, individual rationality, and truthfulness with low approximation ratio.The remainder of this paper is organized as follows. In Section2, we review the related work. In Section 3, we describe the system model and formulate the MQMUS problem. Thereafter, in Section 4 we propose the incentive mechanism, named QAIM, which consists of two phases, winner selection and payment determination, and analyze the properties of QAIM. Section 5 presents the experimental results. Finally, we draw the conclusion and discuss some possible future directions in Section 6.


## 2. Related Work

There are lots of incentive mechanisms which can be classified into nonmonetary incentives [18–29] and monetary incentives [30–45]. Paying for sensed data in crowd sensing tasks is the most intuitive incentive. Monetary incentive mechanisms are mainly based on two kinds of schemes: Stackelberg game and auction.Stackelberg game is a game where one leader player has the dominant influence over the other players [46]. Duan et al. [30] make use of the Stackelberg game to design a threshold revenue model for service providers. The system and the users interact through a two-stage process similar to that of Stackelberg game. The system announces the total reward and the threshold number of required participants. Each participant decides whether to accept the task or not. Yang et al. [31] also model the proposed platform-centric incentive mechanism as a Stackelberg game, prove that this Stackelberg game has a unique equilibrium, and design an efficient mechanism for computing it. The above two Stackelberg game solutions have theoretical guarantees. However, the premise of this kind of method is that the costs of all users or their probability distributions are assumed to be known, which limits the applicability of Stackelberg game-based mechanisms because participants may keep their costs private in the real world.An auction-based mechanism is originally the process of buying and selling goods by negotiating the monetary prices [47]. A kind of auction, called reverse auction, is adopted to model the negotiation process in crowd sensing, which is shown in Figure 1. Lee and Hoh [32] firstly design a reverse auction-based dynamic price incentive mechanism with virtual participation credit with the objective of minimizing and stabilizing the platform cost while maintaining the participation level. Yang et al. [31] consider two system models for smartphone crowd sensing system: the platform-centric model with the solution based on the Stackelberg game and user-centric model with the solution based on the reverse auction. Feng et al. [33] formulate the winning bids determination problem and present a truthful auction for location-aware collaborative sensing. Zhang et al. [34] focus on the user-centric model and study three methods which involve cooperation and competition among the services. Xu et al. [35, 36] investigate truthful incentive mechanisms for time window dependent tasks with the strong requirement of data integrity and propose two incentive mechanisms for the single time window case and the multiple window case, respectively. Subramanian et al. [37] consider offline and online incentive mechanisms using the same bidding framework with MSensing Auction proposed in [31]. Zhao et al. [38] investigate the incentive mechanisms in the online setting based on an offline budget feasible mechanism [39], which provides a starting point for the online mechanism. Jin et al. [40] pay attention to the quality of the mobile crowd sensing systems and incorporate a metric named QoI (Quality of Information) into the incentive mechanisms. SRC and MRC mechanisms with the criterion of the combinatorial QoI and price are proposed. However, the authors fail to consider the truthfulness of the MRC mechanism. The aforementioned solutions assume that each measurement of sensing task can be represented by a single sensor reading.Several solutions are proposed to ensure the quality of crowd sensing data. Tanas and Herrera-Joancomartí [48] achieve the first work, which focuses on how to validate sensing data, but the premise of their work is that there are multiple users to submit multiple sensing readings on each task. Kazemi et al. [49] assume each worker has a reputation score, and assign enough number of workers to each spatial task such that workers’ aggregate reputation can satisfy the confidence of the task. However, they focus on self-incentivized spatial crowdsourcing, in which people perform the tasks voluntarily without any reward. Zhang et al. [41] propose a task management framework to match workers to the merged query and sensing tasks efficiently. In their model, each task can be assigned to multiple workers, and each worker can be assigned to at most one task, although each worker may have the preference for multiple tasks. Xu et al. [42] design the incentive mechanism, which considers the issue of stimulating the biased requesters in the competing crowdsourcing market. Xiong et al. [43] consider thek-depth coverage as an MCS data collection constraint, but every subtask is assigned to the same value of k. Wang et al. [44] present a detailed quality-aware mobile crowdsourced sensing framework, composed of three MCS components: crowd, crowdsourcer, and crowdsourcing platform. The crowdsourcer is a new role who assesses the posted contributions’ quality. He et al. [45] propose a recruitment strategy in vehicle-based crowdsourcing through taking full advantage of predictable mobility patterns of vehicles, which bring a new insight to improve the quality of crowd sensing system. However, the behaviors of human are affected by many factors. It is far more difficult to predict the mobility patterns of human beings than those of vehicles.In this paper, we try to enhance the quality-aware incentive mechanism from two main dimensions: the reputation of participants and the design of task.


## 3. Problem Statement

Different from most crowd sensing systems, the objective of this paper is designing the truthful incentive mechanism with maximum social efficiency and high sensing quality. To achieve this objective, the recruiter needs to select participants who can match the diverse requirements of the crowd sensing application with minimum social cost. Before demonstrating the rigorous problem definition, we would like to present a motivating example to make the problem better understood.


### 3.1. A Participant Recruitment Example in Air Quality Monitoring

We take the urban air quality monitoring MCS task as an example. As shown in Figure2, the MCS recruiter wants to collect the state of the air in three regions (denoted as G={A,B,C}). Nine candidates ({v1,v2,…,v9}) are interested in performing the task and reporting their sensing plans, which include what they can do with the corresponding bid price. The industrial structures vary greatly in different regions. The regions with more plants, which can discharge waste gas, need more participants to monitor. For example, the recruiter wants 5 participants to monitor region C and only 3 to monitor region A because there are more chemical plants in region C. We use squares to represent the regions, and the number above each square denotes its requirement. To the perspective of the candidates, people may not just stay in a certain region in one sensing cycle and can fulfill multiple sensing tasks in different regions. We use disks to represent the candidates, and the number above each disk denotes its corresponding bid price, and the set of regions below each disk denotes the regions that he can monitor.Figure 2
A motivating example with diversity requirements.In this example, the mobile crowd sensing system has some requirements: (1) Every subtask should be assigned to enough participants so that their aggregate sensing results can ensure the sensing quality. (2) Every subtask has different sensing requirement. The different number of participants should be recruited to satisfy different sensing requirements with minimum costs. (3) Every participant has different ability in terms of the task completion and should be assigned to the different number of subtasks based on his particular ability.


### 3.2. System Model and Problem Formulation

We present the rigorous definition and formulation of the MQMUS problem. In this problem, the recruiter can divide the task into multiple subtasks with different quality factors and the participants can be assigned to multiple subtasks in one sensing cycle.Suppose that a crowd sensing taskG can be divided into e disjoint subtasks according to the sensing geographic areas, and each subtask gk has its sensing quality factor h(gk) (to simplify, we use the number of participants to represent h(gk) as shown in the above motivating example). The recruiter publicizes the sensing task G={g1,g2,…,gk,…,ge} and the quality factor h(G)={h(g1),h(g2),…,h(gk),…,h(ge)} as a quality constraint for participants selecting.Consideringn candidates, U={v1,v2,…,vi,…,vn} are interested in performing the sensing task. Each candidate vi∈U submits a sensing plan Bvi=(ψvi,bvi) to the recruiter, in which ψvi={g1vi,g2vi,…,gkvi} is the set of subtasks that candidate vi can perform (the superscript vi of gkvi is only used to represent that vi can fulfill the subtask gk) and bvi is bid price that candidate vi wants to charge for performing ψvi.We assume that the candidatevi has a reputation score rvi, which states the probability that the candidate performs a task correctly. The recruiter is responsible for maintaining and updating the reputation score of every candidate. The value of rvi is set to 1 initially and updated by(1)rvi=rvi+∑gm∈ψvihgm-1ηmaxgk∈G⁡hgk.We utilize a voting mechanism to set the value ofη. This intuition is based on the idea of the wisdom of crowds [50] that the majority of the participants are trusted. The recruiter aggregates the different sensing results to get the reliable result at the end of the sensing cycle. The setting way of η is inspired by [44]. η is set to “−1” in two cases: (1) the candidate cannot perform the subtask as the claimed sensing plan; (2) the sensing result of the same subtask is contrary to more than half of participants’ results; otherwise, η is “0.” If rvi<0, vi will not be selected until the recruiter resets rvi to 1 after a period of time (e.g., 10 sensing cycles).Assume that the number of candidates is sufficient to fulfill the sensing taskG with its quality constraints h(G). This assumption is reasonable for mobile crowd sensing systems as made in [31, 33, 35]. The selected participant sj is placed into the list S={s1,s2,…,sj-1} according to the order. sj is the ID of the candidate and its subscript j denotes that sj is the jth selected participant. The recruiter has to calculate the payment psj for each participant as the incentive. The utility of participant can be calculated by (2), in which csj is the real cost of the participant sj and only known by itself. bsj is not less than csj due to the selfishness and rationality of participants (if the reputation score of sj is set to a value less than 0 in this sensing cycle, the utility of sj will be 0 in the next sensing cycle because he will not be selected). (2)usj=psj-csj.The utility of the recruiter is calculated by (3). V(h(G)) is the value to the recruiter when it has collected enough data to satisfy the quality constraints h(G) of the sensing task G.(3)u0=VhG-∑sj∈Spsj.The social efficiency of the sensing taskG (with the quality constraints h(G)) is calculated by (4). Although the real cost csj is only known by participant sj, we will prove that claiming a different cost bsj cannot help to increase the utility of participant sj in our designed mechanisms. So we use bsj when we attempt to maximize social efficiency in the mechanisms designed below. The objective of maximizing the social efficiency is equivalent to the objective of minimizing the social cost.(4)uhG=VhG-∑sj∈Sbsj.Given the list of selected participantsS={s1,s2,…,si,…,sm},Gsi is the set of the remaining subtasks excluding those subtasks of participants {s1,s2,…,si} according to their sensing plans. The goal of achieving high quality crowd sensing with minimum social cost can be formulated as (5) and constrained by (6).(5)min∑sj∈Sbsj(6)s.t.ψs1∩G+ψs2∩Gs1+⋯+ψsm∩Gsm-1≥∑gk∈Ghgk.We design a truthful incentive mechanism,QAIM, to select appropriate participants to satisfy the objective of this paper, and to eliminate the fear of market manipulation (the participants cannot improve their utility by submitting a bid price different from its real cost).Q
A
I
M consists of two phases: winner selection algorithm QAIM(S) and payment determination algorithm QAIM(P). For a given h(G) and a set of bids B={Bv1,Bv2,…,Bvi,…,Bvn}, the algorithm QAIM(S) selects a subset of participants S⊆U and the algorithm QAIM(P) returns the vector (p1,p2,…,pm) for those selected participants.We cannot find the optimal solution in polynomial time for theMQMUS problem presented in (5) and (6) because this problem is NP-hard. The proof is in Appendix.Our objective is to design the incentive mechanisms satisfying the following four desirable properties to solveMQMUS problem:(i)
Computational Efficiency. A mechanism is computationally efficient if both the winner selection function and payment decision function can be computed in polynomial time.(ii)
Individual Rationality. Each participant will have a nonnegative utility upon performing the sensing task.(iii)
Truthfulness. A mechanism is truthful if no participant can improve its utility by submitting a bid price different from its real cost, no matter what others submit. In other words, reporting the real cost is a dominant strategy for all participants.(iv)
Social Optimization. The objective function is maximizing the social efficiency. We attempt to find optimal solution or approximation algorithm with low approximation ratio when there is no optimal solution computed in polynomial time.


## 3.1. A Participant Recruitment Example in Air Quality Monitoring

We take the urban air quality monitoring MCS task as an example. As shown in Figure2, the MCS recruiter wants to collect the state of the air in three regions (denoted as G={A,B,C}). Nine candidates ({v1,v2,…,v9}) are interested in performing the task and reporting their sensing plans, which include what they can do with the corresponding bid price. The industrial structures vary greatly in different regions. The regions with more plants, which can discharge waste gas, need more participants to monitor. For example, the recruiter wants 5 participants to monitor region C and only 3 to monitor region A because there are more chemical plants in region C. We use squares to represent the regions, and the number above each square denotes its requirement. To the perspective of the candidates, people may not just stay in a certain region in one sensing cycle and can fulfill multiple sensing tasks in different regions. We use disks to represent the candidates, and the number above each disk denotes its corresponding bid price, and the set of regions below each disk denotes the regions that he can monitor.Figure 2
A motivating example with diversity requirements.In this example, the mobile crowd sensing system has some requirements: (1) Every subtask should be assigned to enough participants so that their aggregate sensing results can ensure the sensing quality. (2) Every subtask has different sensing requirement. The different number of participants should be recruited to satisfy different sensing requirements with minimum costs. (3) Every participant has different ability in terms of the task completion and should be assigned to the different number of subtasks based on his particular ability.


## 3.2. System Model and Problem Formulation

We present the rigorous definition and formulation of the MQMUS problem. In this problem, the recruiter can divide the task into multiple subtasks with different quality factors and the participants can be assigned to multiple subtasks in one sensing cycle.Suppose that a crowd sensing taskG can be divided into e disjoint subtasks according to the sensing geographic areas, and each subtask gk has its sensing quality factor h(gk) (to simplify, we use the number of participants to represent h(gk) as shown in the above motivating example). The recruiter publicizes the sensing task G={g1,g2,…,gk,…,ge} and the quality factor h(G)={h(g1),h(g2),…,h(gk),…,h(ge)} as a quality constraint for participants selecting.Consideringn candidates, U={v1,v2,…,vi,…,vn} are interested in performing the sensing task. Each candidate vi∈U submits a sensing plan Bvi=(ψvi,bvi) to the recruiter, in which ψvi={g1vi,g2vi,…,gkvi} is the set of subtasks that candidate vi can perform (the superscript vi of gkvi is only used to represent that vi can fulfill the subtask gk) and bvi is bid price that candidate vi wants to charge for performing ψvi.We assume that the candidatevi has a reputation score rvi, which states the probability that the candidate performs a task correctly. The recruiter is responsible for maintaining and updating the reputation score of every candidate. The value of rvi is set to 1 initially and updated by(1)rvi=rvi+∑gm∈ψvihgm-1ηmaxgk∈G⁡hgk.We utilize a voting mechanism to set the value ofη. This intuition is based on the idea of the wisdom of crowds [50] that the majority of the participants are trusted. The recruiter aggregates the different sensing results to get the reliable result at the end of the sensing cycle. The setting way of η is inspired by [44]. η is set to “−1” in two cases: (1) the candidate cannot perform the subtask as the claimed sensing plan; (2) the sensing result of the same subtask is contrary to more than half of participants’ results; otherwise, η is “0.” If rvi<0, vi will not be selected until the recruiter resets rvi to 1 after a period of time (e.g., 10 sensing cycles).Assume that the number of candidates is sufficient to fulfill the sensing taskG with its quality constraints h(G). This assumption is reasonable for mobile crowd sensing systems as made in [31, 33, 35]. The selected participant sj is placed into the list S={s1,s2,…,sj-1} according to the order. sj is the ID of the candidate and its subscript j denotes that sj is the jth selected participant. The recruiter has to calculate the payment psj for each participant as the incentive. The utility of participant can be calculated by (2), in which csj is the real cost of the participant sj and only known by itself. bsj is not less than csj due to the selfishness and rationality of participants (if the reputation score of sj is set to a value less than 0 in this sensing cycle, the utility of sj will be 0 in the next sensing cycle because he will not be selected). (2)usj=psj-csj.The utility of the recruiter is calculated by (3). V(h(G)) is the value to the recruiter when it has collected enough data to satisfy the quality constraints h(G) of the sensing task G.(3)u0=VhG-∑sj∈Spsj.The social efficiency of the sensing taskG (with the quality constraints h(G)) is calculated by (4). Although the real cost csj is only known by participant sj, we will prove that claiming a different cost bsj cannot help to increase the utility of participant sj in our designed mechanisms. So we use bsj when we attempt to maximize social efficiency in the mechanisms designed below. The objective of maximizing the social efficiency is equivalent to the objective of minimizing the social cost.(4)uhG=VhG-∑sj∈Sbsj.Given the list of selected participantsS={s1,s2,…,si,…,sm},Gsi is the set of the remaining subtasks excluding those subtasks of participants {s1,s2,…,si} according to their sensing plans. The goal of achieving high quality crowd sensing with minimum social cost can be formulated as (5) and constrained by (6).(5)min∑sj∈Sbsj(6)s.t.ψs1∩G+ψs2∩Gs1+⋯+ψsm∩Gsm-1≥∑gk∈Ghgk.We design a truthful incentive mechanism,QAIM, to select appropriate participants to satisfy the objective of this paper, and to eliminate the fear of market manipulation (the participants cannot improve their utility by submitting a bid price different from its real cost).Q
A
I
M consists of two phases: winner selection algorithm QAIM(S) and payment determination algorithm QAIM(P). For a given h(G) and a set of bids B={Bv1,Bv2,…,Bvi,…,Bvn}, the algorithm QAIM(S) selects a subset of participants S⊆U and the algorithm QAIM(P) returns the vector (p1,p2,…,pm) for those selected participants.We cannot find the optimal solution in polynomial time for theMQMUS problem presented in (5) and (6) because this problem is NP-hard. The proof is in Appendix.Our objective is to design the incentive mechanisms satisfying the following four desirable properties to solveMQMUS problem:(i)
Computational Efficiency. A mechanism is computationally efficient if both the winner selection function and payment decision function can be computed in polynomial time.(ii)
Individual Rationality. Each participant will have a nonnegative utility upon performing the sensing task.(iii)
Truthfulness. A mechanism is truthful if no participant can improve its utility by submitting a bid price different from its real cost, no matter what others submit. In other words, reporting the real cost is a dominant strategy for all participants.(iv)
Social Optimization. The objective function is maximizing the social efficiency. We attempt to find optimal solution or approximation algorithm with low approximation ratio when there is no optimal solution computed in polynomial time.


## 4. Mechanism Design and Analysis

### 4.1. Mechanism Design

We attempt to find an approximation algorithm following a greedy approach which can be solved in polynomial time because theMQMUS problem is NP-hard problem. The winner selection algorithm QAIM(S) is illustrated in Algorithm 1 and the payment algorithm QAIM(P) is illustrated in Algorithm 2.Algorithm 1
Q
A
I
M
(
S
).
Input:h(G), set of bids B
(1) λ=1; Gλ=G; S=Φ; for l∈U if (rl<0)U=U-{l};
(2) while (Gλ≠Φ){
(3)   for each l∈(U-S) if (ϖl(Gλ)≠0)Tl(λ)=blϖl(Gλ) else Tl(λ)=MAX;
(4)   for each l∈(U-S) Sort Tl(λ) in non-decreasing order;
(5)   q=1; y=1; min⁡hλ=mingk∈Gλ{h(gk)};
(6)    while (y≤min⁡hλ){
(7)      i=arg(Tq(λ)); S=S∪{i}; y=y+1; q=q+1;
(8)      for each (gki∈ψi){
if(gki∈Gλ){
(9)         h(gk)=h(gk)-1;
(10)         if h(gk)=0Gλ+1=Gλ-{gk};}}}
(11)   λ=λ+1;}
(12) return SAlgorithm 2:
Q
A
I
M
(
P
).
input:h(G), set of bids B, list of selected participants S
(1) for all u∈U do {pu=0;} for l∈U if (rl<0)U=U-{l};
(2) for all si∈S do {
(3)    U′=U-{si};χ=Φ; υ=1; Gυ=G;
(4)    while (Gυ≠Φ){
(5)      for l∈(U′-χ){if (ϖl′(Gυ)≠0)Γl(υ)=blϖl′(Gυ) else Γl(υ)=MAX;}
(6)       for l∈(U′-χ){SortΓl(υ)innon-decreasingorder;}
(7)       q=1; y=1; min⁡h=mingk∈Gυ{h(gk)};
(8)      while (y≤min⁡h){
(9)         r=arg(Γq(υ)); psi=max⁡{psi,ϖsi′(Gυ)ϖr′(Gυ)br};
χ=χ∪{r}; y=y+1; q=q+1;
(10)          for (gkr∈ψr){
(11)          if (gkr∈Gυ){
(12)            h(gk)=h(gk)-1;
(13)            if h(gk)=0{Gυ+1=Gυ-{gk};}}}}
(14)    υ=υ+1;}}
(15) return PIn Algorithm1, l is the ID of candidates, λ is the number of selection round, and Gλ is the set of remaining subtasks excluding those in the sensing plans of the selected participants before the previous λ-1 rounds. Theeffective sensing units of l in the λth round are denoted by ϖl(Gλ) which can be calculated by (7), theeffective average sensing weight of candidate l in the λth round is denoted by Tl(λ) which is calculated in Line (3) of Algorithm 1.(7)ϖlGλ=Gλ∩ψl.The main idea of greedy approach is to select candidate with least effective average sensing weight, soTl(λ) of all remaining candidates are sorted in nondecreasing order in Line (4) of Algorithm 1, and arg(Tq(λ)) is the ID of the qth selected participant in the λth selection round.The trick ofQAIM(S) lies in the use of min⁡hλ which denotes the number of participants that can be selected in the λth round. The nondecreasing sorting of Tl(λ) implies that (8) is true.(8)bargT1λϖarg⁡T1λGλ≤bargT2λϖarg⁡T2λGλ≤⋯≤bargTmin⁡hλλϖarg⁡Tmin⁡hλλGλ.Equation (9) is true; otherwise the first selected participant in the (λ+1)th round will be selected in the λth round.(9)bargTmin⁡hλλϖarg⁡Tmin⁡hλλGλ≤bargT1λ+1ϖarg⁡T1λ+1Gλ.The calculation method ofGλ+1 in Line (10) of Algorithm 1 implies that Gλ+1 cannot be bigger than Gλ, so (10) is true which implies the participant is selected in the nondecreasing order of theeffective average sensing weight:(10)bargTmin⁡hλλϖarg⁡Tmin⁡hλλGλ≤bargT1λ+1ϖarg⁡T1λ+1Gλ≤bargT1λ+1ϖarg⁡T1λ+1Gλ+1.Letsp,sp+1,…,sp+min⁡hλ-1 denote the IDs of the selected participants in the λth selection round; the set of remaining subtasks would possibly be changed only at the end of the λth selection round, so (11) is true. (11)Gsp=Gsp+1=⋯=Gsp+min⁡hλ-2=Gλ,Gsp+min⁡hλ-1=Gλ+1.Equation (12) is true by derivation from (10) and (11).(12)bs1ϖs1G≤bs2ϖs2Gs1≤⋯≤bsiϖsiGsi-1≤⋯≤bsmϖsmGsm-1.In Algorithm2, u is the ID of candidates with the same role as l in QAIM(S), υ is the number of payment determination round, and Gυ is the set of remaining subtasks excluding those in the sensing plans of the selected participants before the previous υ-1 rounds. Theeffective sensing units of l in the υth round are denoted by ϖl′(Gυ) with the same calculation method used in (7). Theeffective average sensing weight of candidate l in the υth round is denoted by Γl(υ) which is calculated in Line (5) of Algorithm 2.To compute the payment for eachsi in the winner list S, we consider the set of candidates U-{si} and reselect appropriate participants into the list χsi with the same method used in QAIM(S) (the superscript si of χsi is used to identify that si is not considered as a candidate). Let χsi={x1si,x2si,…,xksi,…,xasi} and xksi denote the kth selected participant, Gxksi is the set of remaining subtasks excluding those effective subtasks of participants {x1si,x2si,…,xksi} according to their sensing plans, and (13) is true for the same reason of (12).(13)bx1siϖx1si′G≤bx2siϖx2si′Gx1si≤⋯≤bxksiϖxksi′Gxk-1si≤⋯≤bxasiϖxasi′Gxa-1si.


### 4.2. A Walk-Through Example

To better understand the algorithm, we use the example in Figure2 to illustrate how the QAIM works.With regard to the aforementioned example, the crowd sensing taskG={A,B,C} is divided into 3 subtasks: h(A) is set to 3, h(B) is set to 4, and h(C) is set to 5. There are 9 candidates U={v1,v2,…,v9} who want to participate in the task and report their sensing plan: the bid price of vi is shown above it, and the subtask that vi can fulfill is given below it in Figure 2. Take v3, for example, ψv3={A,B}, which can also be represented as ψv3={Av3,Bv3}, and bv3=1. Theeffective sensing units of v3 in the first round are denoted by ϖv3(G1) which is calculated by (7) (i.e., A,B,C∩A,B=2), and theeffective average sensing weight of v3 in the first round is denoted by Tv3(1) which is calculated in Line (3) of Algorithm 1 (i.e., bv3/ϖv3(G1)=1/2).We first assume that all participants are trustworthy and can fulfill the sensing units as they had claimed in their sensing plan.In the first selection round,Gλ={A,B,C},h(A)=3,h(B)=4,h(C)=5,min⁡hλ=3. Tl(λ) of each candidate in the first round is listed in Table 1. According to QAIM(S), v3 is the first winner and then v4, and v1 is the third one in the first round. The selected list S={v3,v4,v1}, Gv3={A,B,C}, Gv4={A,B,C}, and Gv1={B,C}.Table 1
T
l
(
λ
) in the first selection round.
T
v
1
(
λ
)
T
v
2
(
λ
)
T
v
3
(
λ
)
T
v
4
(
λ
)
T
v
5
(
λ
)
T
v
6
(
λ
)
T
v
7
(
λ
)
T
v
8
(
λ
)
T
v
9
(
λ
)
λ
=
1
4/3
3/2
1/2
2/3
3.5/2
3.6/2
3.7/2
2/1
6/3In the second selection round,Gλ={B,C}, h(A)=0, h(B)=1, h(C)=3, and min⁡hλ=1. Tl(λ) of each candidate in the second round is listed in Table 2. According to QAIM(S), v5 is the first and only winner. The selected list S={v3,v4,v1,v5} and Gv5={C}.Table 2
T
l
(
λ
) in the second selection round.
T
v
2
(
λ
)
T
v
5
(
λ
)
T
v
6
(
λ
)
T
v
7
(
λ
)
T
v
8
(
λ
)
T
v
9
(
λ
)
λ
=
2
3/1
3.5/2
3.6/2
3.7/2
2/1
6/2In the third selection round,Gλ={C}, h(A)=0, h(B)=0, h(C)=2, and min⁡hλ=2. Tl(λ) of each candidate in the third round is listed in Table 3. According to QAIM(S), v2 is the first winner and v6 is the second one. The selected list S={v3,v4,v1,v5,v2,v6}, Gv2={C}, and Gv6=⌀.Table 3
T
l
(
λ
) in the third selection round.
T
v
2
(
λ
)
T
v
6
(
λ
)
T
v
7
(
λ
)
T
v
8
(
λ
)
T
v
9
(
λ
)
λ
=
3
3/1
3.6/1
3.7/1
MAX
6/1In the fourth selection round,Gλ=⌀, which implies the selected participants (v3,v4,v1,v5,v2,v6) can satisfy the sensing requirements.Ifv3 is a malicious participant, he lies in the results of all sensing units; the reputation of v3 is 0 calculated by (1) which means he will not be selected in the next sensing recruitment cycle.Owning to the limitation of the space and the similarity of the algorithm process, we only give the payment example of the first selected winnerv3 which is similar to the payment determination of other participants. pv3 is initialized to 0.In the first payment determination round,Gυ={A,B,C}, h(A)=3, h(B)=4, h(C)=5, and min⁡hυ=3. Γl(υ) of each candidate in the first round is listed in Table 4. According to QAIM(P), v4 is the first winner; then pv3=max⁡pv3,(ϖv3′Gυ/ϖv4′Gυ)bv4=max⁡0,(2/3)∗2=4/3. v1 is the second winner; then pv3=max⁡pv3,(ϖv3′Gυ/ϖv1′Gυ)bv1=max⁡{4/3,(2/3)∗4}=8/3. v2 is the third winner; then pv3=max⁡{pv3,ϖv3′Gυ/ϖv2′Gυbv2}=max⁡{8/3,(2/2)∗3}=3.Table 4
Γ
l
(
υ
) in the first payment determination round considering v3.
Γ
v
1
(
υ
)
Γ
v
2
(
υ
)
Γ
v
4
(
υ
)
Γ
v
5
(
υ
)
Γ
v
6
(
υ
)
Γ
v
7
(
υ
)
Γ
v
8
(
υ
)
Γ
v
9
(
υ
)
υ
=
1
4/3
3/2
2/3
3.5/2
3.6/2
3.7/2
2/1
6/3In the second payment determination round,Gυ={B,C}, h(A)=0, h(B)=1, h(C)=2, and min⁡hυ=1. Γl(υ) of each candidate in the second round is listed in Table 5. According to QAIM(P), v5 is the first and only winner; then pv3=max⁡{pv3,(ϖv3′(Gυ)/ϖv5′(Gυ))bv5}=max⁡{3,(1/2)∗3.5}=3.Table 5
Γ
l
(
υ
) in the second payment determination round considering v3.
Γ
v
5
(
υ
)
Γ
v
6
(
υ
)
Γ
v
7
(
υ
)
Γ
v
8
(
υ
)
Γ
v
9
(
υ
)
υ
=
2
3.5/2
3.6/2
3.7/2
2/1
6/2In the third payment determination round,Gυ={C}, h(A)=0, h(B)=0, h(C)=1, and min⁡hυ=1. Γl(υ) of each candidate in the second round is listed in Table 6. According to QAIM(P), v6 is the first and only winner; then pv3=max⁡pv3,ϖv3′Gυ/ϖv6′Gυbv6=max⁡{3,(0/1)∗3.5}=3.Table 6
Γ
l
(
υ
) in the third payment determination round considering v3.
Γ
v
6
(
υ
)
Γ
v
7
(
υ
)
Γ
v
8
(
υ
)
Γ
v
9
(
υ
)
υ
=
3
3.6/1
3.7/1
MAX
6/1In the fourth payment round,Gυ=⌀, so the payment to v3 is 3.


### 4.3. Properties of QAIM

In this section, we analyze the properties ofQAIM theoretically to show that QAIM is computationally efficient, individually rational, and truthful. The approximation is also discussed in the end. We use n to denote the number of candidates, e to denote the number of subtasks, Ω(G) to denote all the sensing units, and Ω(Gsi′) to denote the effective sensing units of the selected participants S={s1,s2,…,si}, and for ease of analysis they can be calculated by(14)ΩG=∑k=1ehgk,(15)ΩGsi′=ψs1∩G+ψs2∩Gs1+⋯+ψsi∩Gsi-1.(1)
Q
A
I
M
Is Computationally Efficient. We analyze QAIM(S) and QAIM(P), respectively, where QAIM takes O(n3∗e) in the worst case.The nested for-loop (Lines (8)–(11)) of QAIM(S) will be executed λ∗ψsi∗min⁡hλ times. The maximal value of λ is Ω(G) which is less than n obviously in the worst case when theeffective sensing unit of every candidate has only one subtask. ψsi is less than e and min⁡hλ is far less than n obviously, so QAIM(S) takes O(n2∗e) in the worst case.Q
A
I
M
(
P
) takes O(n3∗e) in the worst case because there are similar processes in both QAIM(S) (Lines (2)–(11)) and QAIM(P) (Lines (4)–(14)), which will be executed S times less than n.(2)
Q
A
I
M
Is Individually Rational. When considering the set of candidates U-{si}, let xksi be the replacement of participant si which appears in the kth place in the selected list χsi={x1si,x2si,…,xksi,…,xasi}. Equation (16) is true according to the main idea of winner selection.(16)s1=x1si,s2=x2si,…,si-1=xi-1si,That  isGsi-1=Gxi-1si.xksi will not be selected in the kth place if si is considered, so (17) is true.(17)bsiϖsiGsi-1≤bxisiϖxisiGsi-1,That  isbsiGsi-1∩ψsi≤bxisiGsi-1∩ψxisi.Equation (18) is true based on the derivation from (16) and (17).(18)bsiGxi-1si∩ψsi=bsiGsi-1∩ψsi≤bxisiGsi-1∩ψxisi=bxisiGxi-1si∩ψxisi,That  isbsi≤Gxi-1si∩ψsiGxi-1si∩ψxisibxisi.Equation (19) is true according to the main idea of payment calculation in Line (9) of QAIM(P).(19)psi=maxxrsi∈χsi⁡ϖsi′Gxr-1siϖxrsi′Gxr-1sibxrsi.From the analysis of (18) and (19), we know bsi≤psi.(3)
Q
A
I
M
Is Truthful. According to Myerson’s Theorem [51], an auction is truthful if and only if the selection rule is monotone and each winner is paid the critical value pi; if a participant wins the auction by bidding bi, he also wins by bidding bi′<bi but loses by bidding bi′>pi.The monotonicity of the selection rule is obvious: ifsi bids a smaller bsi′ that means bsi′/ϖsi(Gs(i-1))≤bsi/ϖsi(Gs(i-1)),si will also be selected according to (12).Supposepsi=maxxrsi∈χsi{(ϖsi′Gxr-1si/ϖxrsi′Gxr-1si)bxrsi}=(ϖsi′(Gxf-1si)/ϖxfsi′(Gxf-1si))bxfsi; (20) is true if bsi is greater than psi.(20)bsi≥ϖsi′Gxf-1siϖxfsi′Gxf-1sibxfsi,That  isbsiϖsi′Gxf-1si≥bxfsiϖxfsi′Gxf-1si.Equation (20) shows the fact that si will not be selected before the previous f participants (x1si,x2si,…,xfsi) are selected. But if the previous f participants are selected, there is no reason to select si because the previous selected participants can satisfy different sensing requirements.(4) The Approximation Factor to Optimal Solution Is
l
n
(
Ω
(
G
)
)
+
1. Let OPT denote the minimal social cost computed by optimal solution, Ω(Gsi′) denote the effective sensing units of the selected participants S={s1,s2,…,si} calculated by (15), and cost(si+1) denote the social cost of the (i+1)th selected participant si+1.Because the participant is selected in the nondecreasing order of theeffective average sensing weight according to QAIM(S) and the average cost of the rest uncovered sensing units is not greater than OPT/(Ω(G)-Ω(Gsi′)), (21) is true.(21)costsi+1≤OPTΩG-ΩGsi′.Hence the total cost ofQAIM can be calculated by(22)∑r=1mcostsr≤∑r=1mOPTΩG-ΩGsr-1′≤OPTΩG+OPTΩG-1+OPTΩG-2+⋯+OPTΩG-ΩG-2+OPTΩG-ΩG-1≤ln⁡ΩG+1OPT.


## 4.1. Mechanism Design

We attempt to find an approximation algorithm following a greedy approach which can be solved in polynomial time because theMQMUS problem is NP-hard problem. The winner selection algorithm QAIM(S) is illustrated in Algorithm 1 and the payment algorithm QAIM(P) is illustrated in Algorithm 2.Algorithm 1
Q
A
I
M
(
S
).
Input:h(G), set of bids B
(1) λ=1; Gλ=G; S=Φ; for l∈U if (rl<0)U=U-{l};
(2) while (Gλ≠Φ){
(3)   for each l∈(U-S) if (ϖl(Gλ)≠0)Tl(λ)=blϖl(Gλ) else Tl(λ)=MAX;
(4)   for each l∈(U-S) Sort Tl(λ) in non-decreasing order;
(5)   q=1; y=1; min⁡hλ=mingk∈Gλ{h(gk)};
(6)    while (y≤min⁡hλ){
(7)      i=arg(Tq(λ)); S=S∪{i}; y=y+1; q=q+1;
(8)      for each (gki∈ψi){
if(gki∈Gλ){
(9)         h(gk)=h(gk)-1;
(10)         if h(gk)=0Gλ+1=Gλ-{gk};}}}
(11)   λ=λ+1;}
(12) return SAlgorithm 2:
Q
A
I
M
(
P
).
input:h(G), set of bids B, list of selected participants S
(1) for all u∈U do {pu=0;} for l∈U if (rl<0)U=U-{l};
(2) for all si∈S do {
(3)    U′=U-{si};χ=Φ; υ=1; Gυ=G;
(4)    while (Gυ≠Φ){
(5)      for l∈(U′-χ){if (ϖl′(Gυ)≠0)Γl(υ)=blϖl′(Gυ) else Γl(υ)=MAX;}
(6)       for l∈(U′-χ){SortΓl(υ)innon-decreasingorder;}
(7)       q=1; y=1; min⁡h=mingk∈Gυ{h(gk)};
(8)      while (y≤min⁡h){
(9)         r=arg(Γq(υ)); psi=max⁡{psi,ϖsi′(Gυ)ϖr′(Gυ)br};
χ=χ∪{r}; y=y+1; q=q+1;
(10)          for (gkr∈ψr){
(11)          if (gkr∈Gυ){
(12)            h(gk)=h(gk)-1;
(13)            if h(gk)=0{Gυ+1=Gυ-{gk};}}}}
(14)    υ=υ+1;}}
(15) return PIn Algorithm1, l is the ID of candidates, λ is the number of selection round, and Gλ is the set of remaining subtasks excluding those in the sensing plans of the selected participants before the previous λ-1 rounds. Theeffective sensing units of l in the λth round are denoted by ϖl(Gλ) which can be calculated by (7), theeffective average sensing weight of candidate l in the λth round is denoted by Tl(λ) which is calculated in Line (3) of Algorithm 1.(7)ϖlGλ=Gλ∩ψl.The main idea of greedy approach is to select candidate with least effective average sensing weight, soTl(λ) of all remaining candidates are sorted in nondecreasing order in Line (4) of Algorithm 1, and arg(Tq(λ)) is the ID of the qth selected participant in the λth selection round.The trick ofQAIM(S) lies in the use of min⁡hλ which denotes the number of participants that can be selected in the λth round. The nondecreasing sorting of Tl(λ) implies that (8) is true.(8)bargT1λϖarg⁡T1λGλ≤bargT2λϖarg⁡T2λGλ≤⋯≤bargTmin⁡hλλϖarg⁡Tmin⁡hλλGλ.Equation (9) is true; otherwise the first selected participant in the (λ+1)th round will be selected in the λth round.(9)bargTmin⁡hλλϖarg⁡Tmin⁡hλλGλ≤bargT1λ+1ϖarg⁡T1λ+1Gλ.The calculation method ofGλ+1 in Line (10) of Algorithm 1 implies that Gλ+1 cannot be bigger than Gλ, so (10) is true which implies the participant is selected in the nondecreasing order of theeffective average sensing weight:(10)bargTmin⁡hλλϖarg⁡Tmin⁡hλλGλ≤bargT1λ+1ϖarg⁡T1λ+1Gλ≤bargT1λ+1ϖarg⁡T1λ+1Gλ+1.Letsp,sp+1,…,sp+min⁡hλ-1 denote the IDs of the selected participants in the λth selection round; the set of remaining subtasks would possibly be changed only at the end of the λth selection round, so (11) is true. (11)Gsp=Gsp+1=⋯=Gsp+min⁡hλ-2=Gλ,Gsp+min⁡hλ-1=Gλ+1.Equation (12) is true by derivation from (10) and (11).(12)bs1ϖs1G≤bs2ϖs2Gs1≤⋯≤bsiϖsiGsi-1≤⋯≤bsmϖsmGsm-1.In Algorithm2, u is the ID of candidates with the same role as l in QAIM(S), υ is the number of payment determination round, and Gυ is the set of remaining subtasks excluding those in the sensing plans of the selected participants before the previous υ-1 rounds. Theeffective sensing units of l in the υth round are denoted by ϖl′(Gυ) with the same calculation method used in (7). Theeffective average sensing weight of candidate l in the υth round is denoted by Γl(υ) which is calculated in Line (5) of Algorithm 2.To compute the payment for eachsi in the winner list S, we consider the set of candidates U-{si} and reselect appropriate participants into the list χsi with the same method used in QAIM(S) (the superscript si of χsi is used to identify that si is not considered as a candidate). Let χsi={x1si,x2si,…,xksi,…,xasi} and xksi denote the kth selected participant, Gxksi is the set of remaining subtasks excluding those effective subtasks of participants {x1si,x2si,…,xksi} according to their sensing plans, and (13) is true for the same reason of (12).(13)bx1siϖx1si′G≤bx2siϖx2si′Gx1si≤⋯≤bxksiϖxksi′Gxk-1si≤⋯≤bxasiϖxasi′Gxa-1si.


## 4.2. A Walk-Through Example

To better understand the algorithm, we use the example in Figure2 to illustrate how the QAIM works.With regard to the aforementioned example, the crowd sensing taskG={A,B,C} is divided into 3 subtasks: h(A) is set to 3, h(B) is set to 4, and h(C) is set to 5. There are 9 candidates U={v1,v2,…,v9} who want to participate in the task and report their sensing plan: the bid price of vi is shown above it, and the subtask that vi can fulfill is given below it in Figure 2. Take v3, for example, ψv3={A,B}, which can also be represented as ψv3={Av3,Bv3}, and bv3=1. Theeffective sensing units of v3 in the first round are denoted by ϖv3(G1) which is calculated by (7) (i.e., A,B,C∩A,B=2), and theeffective average sensing weight of v3 in the first round is denoted by Tv3(1) which is calculated in Line (3) of Algorithm 1 (i.e., bv3/ϖv3(G1)=1/2).We first assume that all participants are trustworthy and can fulfill the sensing units as they had claimed in their sensing plan.In the first selection round,Gλ={A,B,C},h(A)=3,h(B)=4,h(C)=5,min⁡hλ=3. Tl(λ) of each candidate in the first round is listed in Table 1. According to QAIM(S), v3 is the first winner and then v4, and v1 is the third one in the first round. The selected list S={v3,v4,v1}, Gv3={A,B,C}, Gv4={A,B,C}, and Gv1={B,C}.Table 1
T
l
(
λ
) in the first selection round.
T
v
1
(
λ
)
T
v
2
(
λ
)
T
v
3
(
λ
)
T
v
4
(
λ
)
T
v
5
(
λ
)
T
v
6
(
λ
)
T
v
7
(
λ
)
T
v
8
(
λ
)
T
v
9
(
λ
)
λ
=
1
4/3
3/2
1/2
2/3
3.5/2
3.6/2
3.7/2
2/1
6/3In the second selection round,Gλ={B,C}, h(A)=0, h(B)=1, h(C)=3, and min⁡hλ=1. Tl(λ) of each candidate in the second round is listed in Table 2. According to QAIM(S), v5 is the first and only winner. The selected list S={v3,v4,v1,v5} and Gv5={C}.Table 2
T
l
(
λ
) in the second selection round.
T
v
2
(
λ
)
T
v
5
(
λ
)
T
v
6
(
λ
)
T
v
7
(
λ
)
T
v
8
(
λ
)
T
v
9
(
λ
)
λ
=
2
3/1
3.5/2
3.6/2
3.7/2
2/1
6/2In the third selection round,Gλ={C}, h(A)=0, h(B)=0, h(C)=2, and min⁡hλ=2. Tl(λ) of each candidate in the third round is listed in Table 3. According to QAIM(S), v2 is the first winner and v6 is the second one. The selected list S={v3,v4,v1,v5,v2,v6}, Gv2={C}, and Gv6=⌀.Table 3
T
l
(
λ
) in the third selection round.
T
v
2
(
λ
)
T
v
6
(
λ
)
T
v
7
(
λ
)
T
v
8
(
λ
)
T
v
9
(
λ
)
λ
=
3
3/1
3.6/1
3.7/1
MAX
6/1In the fourth selection round,Gλ=⌀, which implies the selected participants (v3,v4,v1,v5,v2,v6) can satisfy the sensing requirements.Ifv3 is a malicious participant, he lies in the results of all sensing units; the reputation of v3 is 0 calculated by (1) which means he will not be selected in the next sensing recruitment cycle.Owning to the limitation of the space and the similarity of the algorithm process, we only give the payment example of the first selected winnerv3 which is similar to the payment determination of other participants. pv3 is initialized to 0.In the first payment determination round,Gυ={A,B,C}, h(A)=3, h(B)=4, h(C)=5, and min⁡hυ=3. Γl(υ) of each candidate in the first round is listed in Table 4. According to QAIM(P), v4 is the first winner; then pv3=max⁡pv3,(ϖv3′Gυ/ϖv4′Gυ)bv4=max⁡0,(2/3)∗2=4/3. v1 is the second winner; then pv3=max⁡pv3,(ϖv3′Gυ/ϖv1′Gυ)bv1=max⁡{4/3,(2/3)∗4}=8/3. v2 is the third winner; then pv3=max⁡{pv3,ϖv3′Gυ/ϖv2′Gυbv2}=max⁡{8/3,(2/2)∗3}=3.Table 4
Γ
l
(
υ
) in the first payment determination round considering v3.
Γ
v
1
(
υ
)
Γ
v
2
(
υ
)
Γ
v
4
(
υ
)
Γ
v
5
(
υ
)
Γ
v
6
(
υ
)
Γ
v
7
(
υ
)
Γ
v
8
(
υ
)
Γ
v
9
(
υ
)
υ
=
1
4/3
3/2
2/3
3.5/2
3.6/2
3.7/2
2/1
6/3In the second payment determination round,Gυ={B,C}, h(A)=0, h(B)=1, h(C)=2, and min⁡hυ=1. Γl(υ) of each candidate in the second round is listed in Table 5. According to QAIM(P), v5 is the first and only winner; then pv3=max⁡{pv3,(ϖv3′(Gυ)/ϖv5′(Gυ))bv5}=max⁡{3,(1/2)∗3.5}=3.Table 5
Γ
l
(
υ
) in the second payment determination round considering v3.
Γ
v
5
(
υ
)
Γ
v
6
(
υ
)
Γ
v
7
(
υ
)
Γ
v
8
(
υ
)
Γ
v
9
(
υ
)
υ
=
2
3.5/2
3.6/2
3.7/2
2/1
6/2In the third payment determination round,Gυ={C}, h(A)=0, h(B)=0, h(C)=1, and min⁡hυ=1. Γl(υ) of each candidate in the second round is listed in Table 6. According to QAIM(P), v6 is the first and only winner; then pv3=max⁡pv3,ϖv3′Gυ/ϖv6′Gυbv6=max⁡{3,(0/1)∗3.5}=3.Table 6
Γ
l
(
υ
) in the third payment determination round considering v3.
Γ
v
6
(
υ
)
Γ
v
7
(
υ
)
Γ
v
8
(
υ
)
Γ
v
9
(
υ
)
υ
=
3
3.6/1
3.7/1
MAX
6/1In the fourth payment round,Gυ=⌀, so the payment to v3 is 3.


## 4.3. Properties of QAIM

In this section, we analyze the properties ofQAIM theoretically to show that QAIM is computationally efficient, individually rational, and truthful. The approximation is also discussed in the end. We use n to denote the number of candidates, e to denote the number of subtasks, Ω(G) to denote all the sensing units, and Ω(Gsi′) to denote the effective sensing units of the selected participants S={s1,s2,…,si}, and for ease of analysis they can be calculated by(14)ΩG=∑k=1ehgk,(15)ΩGsi′=ψs1∩G+ψs2∩Gs1+⋯+ψsi∩Gsi-1.(1)
Q
A
I
M
Is Computationally Efficient. We analyze QAIM(S) and QAIM(P), respectively, where QAIM takes O(n3∗e) in the worst case.The nested for-loop (Lines (8)–(11)) of QAIM(S) will be executed λ∗ψsi∗min⁡hλ times. The maximal value of λ is Ω(G) which is less than n obviously in the worst case when theeffective sensing unit of every candidate has only one subtask. ψsi is less than e and min⁡hλ is far less than n obviously, so QAIM(S) takes O(n2∗e) in the worst case.Q
A
I
M
(
P
) takes O(n3∗e) in the worst case because there are similar processes in both QAIM(S) (Lines (2)–(11)) and QAIM(P) (Lines (4)–(14)), which will be executed S times less than n.(2)
Q
A
I
M
Is Individually Rational. When considering the set of candidates U-{si}, let xksi be the replacement of participant si which appears in the kth place in the selected list χsi={x1si,x2si,…,xksi,…,xasi}. Equation (16) is true according to the main idea of winner selection.(16)s1=x1si,s2=x2si,…,si-1=xi-1si,That  isGsi-1=Gxi-1si.xksi will not be selected in the kth place if si is considered, so (17) is true.(17)bsiϖsiGsi-1≤bxisiϖxisiGsi-1,That  isbsiGsi-1∩ψsi≤bxisiGsi-1∩ψxisi.Equation (18) is true based on the derivation from (16) and (17).(18)bsiGxi-1si∩ψsi=bsiGsi-1∩ψsi≤bxisiGsi-1∩ψxisi=bxisiGxi-1si∩ψxisi,That  isbsi≤Gxi-1si∩ψsiGxi-1si∩ψxisibxisi.Equation (19) is true according to the main idea of payment calculation in Line (9) of QAIM(P).(19)psi=maxxrsi∈χsi⁡ϖsi′Gxr-1siϖxrsi′Gxr-1sibxrsi.From the analysis of (18) and (19), we know bsi≤psi.(3)
Q
A
I
M
Is Truthful. According to Myerson’s Theorem [51], an auction is truthful if and only if the selection rule is monotone and each winner is paid the critical value pi; if a participant wins the auction by bidding bi, he also wins by bidding bi′<bi but loses by bidding bi′>pi.The monotonicity of the selection rule is obvious: ifsi bids a smaller bsi′ that means bsi′/ϖsi(Gs(i-1))≤bsi/ϖsi(Gs(i-1)),si will also be selected according to (12).Supposepsi=maxxrsi∈χsi{(ϖsi′Gxr-1si/ϖxrsi′Gxr-1si)bxrsi}=(ϖsi′(Gxf-1si)/ϖxfsi′(Gxf-1si))bxfsi; (20) is true if bsi is greater than psi.(20)bsi≥ϖsi′Gxf-1siϖxfsi′Gxf-1sibxfsi,That  isbsiϖsi′Gxf-1si≥bxfsiϖxfsi′Gxf-1si.Equation (20) shows the fact that si will not be selected before the previous f participants (x1si,x2si,…,xfsi) are selected. But if the previous f participants are selected, there is no reason to select si because the previous selected participants can satisfy different sensing requirements.(4) The Approximation Factor to Optimal Solution Is
l
n
(
Ω
(
G
)
)
+
1. Let OPT denote the minimal social cost computed by optimal solution, Ω(Gsi′) denote the effective sensing units of the selected participants S={s1,s2,…,si} calculated by (15), and cost(si+1) denote the social cost of the (i+1)th selected participant si+1.Because the participant is selected in the nondecreasing order of theeffective average sensing weight according to QAIM(S) and the average cost of the rest uncovered sensing units is not greater than OPT/(Ω(G)-Ω(Gsi′)), (21) is true.(21)costsi+1≤OPTΩG-ΩGsi′.Hence the total cost ofQAIM can be calculated by(22)∑r=1mcostsr≤∑r=1mOPTΩG-ΩGsr-1′≤OPTΩG+OPTΩG-1+OPTΩG-2+⋯+OPTΩG-ΩG-2+OPTΩG-ΩG-1≤ln⁡ΩG+1OPT.


## 5. Performance Evaluation

### 5.1. Before the Simulation Setup

Because there is no real data set which is consistent with the proposed system model, we have to mine the ways of human mobility from Gowalla [52] and Brightkite [53], which come from the location-based social networking website where users share their locations by checking-in. The details of the data sets are listed in Table 7.Table 7
Facts about studied traces.
Trace source
Brightkite
Gowalla
Time/duration of trace
2008/4–2010/10
2009/2–2010/10
The number of users
58228
196591
The number of check-ins
4491143
6442890We consider the variation law of user’s mobile preferences because the sensing task is dependent on location in most crowd sensing systems. Observing a user’s visiting history can help discover the user’s abilities to fulfill the subtasks in different locations.We divide the regionQ into k∗k square blocks and let q(x,y)∈Q denote the block in which x,y∈1,2…,k represents horizontal and vertical locations, respectively. Let fi(t,q(x,y)) denote the number of checking-ins of user i during the time period t∈[t1,t2] in block q(x,y). If fi(t,q(x,y)) is greater than zero, q(x,y) is called the reachable region of user i during the time period t.The reachable regions of useri can be viewed as the subtasks in different locations that the user can fulfill. Let h(i,t) denote the number of reachable regions which can be viewed as the number of subtasks that the user can fulfill, which is calculated by(23)hi,t=∑x=1k∑y=1kηit,qx,y,ηit,qx,y=0,fit,qx,y=0,1,fit,qx,y>0.With different partition granularity in different data set, more than 95% of the users’ number of reachable regions is smaller than 1.25% of the number of region blocks; the complementary cumulative distribution ofh(i,t) follows the same power-law distribution formulated by (24), which can be seen in Figures 3 and 4, respectively.(24)pX>x=xxmin-k.Figure 3
The complementary cumulative distribution ofh(i,t) in Gowalla.Figure 4
The complementary cumulative distribution ofh(i,t) in Brightkite.The phenomenon of power-law distribution is consistent with our life experience: the activity scope of most people has a limited range in several specific regions in their daily life. The above-mentioned result tells us how to set the number of subtasks that the user can fulfill.


### 5.2. Performance Evaluation

In order to evaluateQAIM, we first introduce two baseline algorithms with the similar ideas of using redundancy.(i)
max(K) is derived from theK-depth coverage objective solution proposed in [43]. No matter how different the sensing quality factor of each subtask is, K is set to the maximal value of these quality factors.(ii)
Greedy(1) is derived from the idea proposed in [41]. No matter how many subtasks one participant can do, he is only assigned with one subtask at a time. So, the participant is selected in the nondecreasing order of the bid price.The performance metrics include the social cost, the number of winners, the running time, and the truthfulness, and the importance of reputation score is also checked up.Simulation parameters are shown in Table8. Each measurement is averaged over 100 instances.Table 8
Simulation settings.
Simulation parameters
Settings
h
(
g
k
)
Uniformly distributed over[3,7]
b
v
i
Uniformly distributed over[5,7]
ψ
v
i
=
{
g
1
v
i
,
g
2
v
i
,
…
,
g
k
v
i
}
g
k
v
i is random in G but |ψvi| is between 3 and 10 which abides to Pareto distribution with xmin = 1 and k = 1.75.(1) Impact of
U. Figures 5–7 show the performance of QAIM(S) with different candidates when the number of sensing subtasks is set to 100. As shown in Figures 5 and 6, the social cost and the number of winners of QAIM(S) are both less than those of Greedy(1) or max(K). The variation does not follow the rule of decreasing with increment of the number of candidates but is within a certain range. The reason is h(gk) and bvi which are generated randomly. QAIM(S) has superiority in achieving high quality crowd sensing with minimum social cost. The running time of QAIM(S) is larger than Greedy(1) but less than max(K) as shown in Figure 7. The variation trend of the running time is consistent with the property of theoretical analysis which increases with the increasing number of candidates.Figure 5
The social cost with different candidates.Figure 6
The number of winners with different candidates.Figure 7
The running time with different candidates.(2) Impact of
G. Figures 8–10 show the performance with a fixed number of 1400 candidates when the number of sensing subtasks varies from 100 to 140 with increment of 10. As shown in Figures 8 and 9, both the social cost and the number of winners of QAIM(S) increase with the increment of G and are less than other algorithms. The running time of QAIM(S) is larger than Greedy(1) but less than max(K) and increases with G as shown in Figure 10, which is consistent with the property of theoretical analysis.Figure 8
The social cost with different number of sensing subtasks.Figure 9
The number of winners with different number of sensing subtasks.Figure 10
The running time with different number of sensing subtasks.(3) Truthfulness. We verified the truthfulness of QAIM with different candidates when the number of subtasks is set to 100. We randomly selected the 78th participant and changed the bid price b78 of the 78th participant. When b78>p78, the 78th participant would not be selected. The running time of QAIM(P) is recorded in Figure 11 which shows the time cost of the truthfulness. The running time of QAIM(P) is bounded by 80 and increases with the increment of the number of candidates except when the number of candidates is 1300, which is a reasonable phenomenon since the running time of QAIM(P) is related to not only the number of candidates but also the number of winners.Figure 11
The running time ofQAIM(P) with different candidates.(4) The Effect of Reputation Value. Finally, we verified the importance of the calculation of reputation value. We first set the 78th participant as the malicious user and offer the contrary sensing result to correct ones of all subtasks intentionally; we find that it would not be selected after the second test. Then we reset the reputation score to 1 and let the 78th participant be selected but the 78th participant does not fulfill one of the subtasks; we find that it would be selected after the second test and would not be selected after the third test.


## 5.1. Before the Simulation Setup

Because there is no real data set which is consistent with the proposed system model, we have to mine the ways of human mobility from Gowalla [52] and Brightkite [53], which come from the location-based social networking website where users share their locations by checking-in. The details of the data sets are listed in Table 7.Table 7
Facts about studied traces.
Trace source
Brightkite
Gowalla
Time/duration of trace
2008/4–2010/10
2009/2–2010/10
The number of users
58228
196591
The number of check-ins
4491143
6442890We consider the variation law of user’s mobile preferences because the sensing task is dependent on location in most crowd sensing systems. Observing a user’s visiting history can help discover the user’s abilities to fulfill the subtasks in different locations.We divide the regionQ into k∗k square blocks and let q(x,y)∈Q denote the block in which x,y∈1,2…,k represents horizontal and vertical locations, respectively. Let fi(t,q(x,y)) denote the number of checking-ins of user i during the time period t∈[t1,t2] in block q(x,y). If fi(t,q(x,y)) is greater than zero, q(x,y) is called the reachable region of user i during the time period t.The reachable regions of useri can be viewed as the subtasks in different locations that the user can fulfill. Let h(i,t) denote the number of reachable regions which can be viewed as the number of subtasks that the user can fulfill, which is calculated by(23)hi,t=∑x=1k∑y=1kηit,qx,y,ηit,qx,y=0,fit,qx,y=0,1,fit,qx,y>0.With different partition granularity in different data set, more than 95% of the users’ number of reachable regions is smaller than 1.25% of the number of region blocks; the complementary cumulative distribution ofh(i,t) follows the same power-law distribution formulated by (24), which can be seen in Figures 3 and 4, respectively.(24)pX>x=xxmin-k.Figure 3
The complementary cumulative distribution ofh(i,t) in Gowalla.Figure 4
The complementary cumulative distribution ofh(i,t) in Brightkite.The phenomenon of power-law distribution is consistent with our life experience: the activity scope of most people has a limited range in several specific regions in their daily life. The above-mentioned result tells us how to set the number of subtasks that the user can fulfill.


## 5.2. Performance Evaluation

In order to evaluateQAIM, we first introduce two baseline algorithms with the similar ideas of using redundancy.(i)
max(K) is derived from theK-depth coverage objective solution proposed in [43]. No matter how different the sensing quality factor of each subtask is, K is set to the maximal value of these quality factors.(ii)
Greedy(1) is derived from the idea proposed in [41]. No matter how many subtasks one participant can do, he is only assigned with one subtask at a time. So, the participant is selected in the nondecreasing order of the bid price.The performance metrics include the social cost, the number of winners, the running time, and the truthfulness, and the importance of reputation score is also checked up.Simulation parameters are shown in Table8. Each measurement is averaged over 100 instances.Table 8
Simulation settings.
Simulation parameters
Settings
h
(
g
k
)
Uniformly distributed over[3,7]
b
v
i
Uniformly distributed over[5,7]
ψ
v
i
=
{
g
1
v
i
,
g
2
v
i
,
…
,
g
k
v
i
}
g
k
v
i is random in G but |ψvi| is between 3 and 10 which abides to Pareto distribution with xmin = 1 and k = 1.75.(1) Impact of
U. Figures 5–7 show the performance of QAIM(S) with different candidates when the number of sensing subtasks is set to 100. As shown in Figures 5 and 6, the social cost and the number of winners of QAIM(S) are both less than those of Greedy(1) or max(K). The variation does not follow the rule of decreasing with increment of the number of candidates but is within a certain range. The reason is h(gk) and bvi which are generated randomly. QAIM(S) has superiority in achieving high quality crowd sensing with minimum social cost. The running time of QAIM(S) is larger than Greedy(1) but less than max(K) as shown in Figure 7. The variation trend of the running time is consistent with the property of theoretical analysis which increases with the increasing number of candidates.Figure 5
The social cost with different candidates.Figure 6
The number of winners with different candidates.Figure 7
The running time with different candidates.(2) Impact of
G. Figures 8–10 show the performance with a fixed number of 1400 candidates when the number of sensing subtasks varies from 100 to 140 with increment of 10. As shown in Figures 8 and 9, both the social cost and the number of winners of QAIM(S) increase with the increment of G and are less than other algorithms. The running time of QAIM(S) is larger than Greedy(1) but less than max(K) and increases with G as shown in Figure 10, which is consistent with the property of theoretical analysis.Figure 8
The social cost with different number of sensing subtasks.Figure 9
The number of winners with different number of sensing subtasks.Figure 10
The running time with different number of sensing subtasks.(3) Truthfulness. We verified the truthfulness of QAIM with different candidates when the number of subtasks is set to 100. We randomly selected the 78th participant and changed the bid price b78 of the 78th participant. When b78>p78, the 78th participant would not be selected. The running time of QAIM(P) is recorded in Figure 11 which shows the time cost of the truthfulness. The running time of QAIM(P) is bounded by 80 and increases with the increment of the number of candidates except when the number of candidates is 1300, which is a reasonable phenomenon since the running time of QAIM(P) is related to not only the number of candidates but also the number of winners.Figure 11
The running time ofQAIM(P) with different candidates.(4) The Effect of Reputation Value. Finally, we verified the importance of the calculation of reputation value. We first set the 78th participant as the malicious user and offer the contrary sensing result to correct ones of all subtasks intentionally; we find that it would not be selected after the second test. Then we reset the reputation score to 1 and let the 78th participant be selected but the 78th participant does not fulfill one of the subtasks; we find that it would be selected after the second test and would not be selected after the third test.


## 6. Conclusion

In this paper, we address the fundamental research issue: how can we achieve high quality crowd sensing with the minimum social cost? To answer this question, we study different conditions of recruiter and candidates in crowd sensing system. Based on the findings, we formulate the sensing quality assurance problem as an optimization problem (MQMUS) and prove it to be NP-hard. We design a polynomial-time greedy approximation algorithm QAIM which consists of two phases: QAIM(S) selects appropriate participants to satisfy the objective of this research which approximates the optimal solution with the times of ln⁡(Ω(G))+1 and QAIM(P) eliminates the fear of market manipulation. Through rigorous theoretical analysis, we demonstrate the proposed mechanisms with the properties of high computation efficiency, individual rationality, and truthfulness and then evaluate our algorithm using synthetic data with the features of real data sets. Evaluations show that our algorithms outperform existing approaches. In the future work, we will explore the quality-aware incentive mechanisms in more complex scenarios, for example, how to prevent cocheating using the history of mobility traces and the completed tasks list of participants.



---

*Source: 5757125-2017-09-28.xml*