Time-Based Quality-Aware Incentive Mechanism for Mobile Crowd Sensing

Abstract

Recent years have witnessed the advance of mobile crowd sensing (MCS) system. How to meet the demands of task time requirements and obtain high-quality data with little expense has become a critical problem. We focus on exploring incentive mechanisms for a practical scenario, where the tasks are time window dependent. An important indicator, “quality of user’s data (QOD)” is also considered. First, we design a prediction model based on user history data (p-QOD), to calculate the next time of the user’s QOD. Second, we design a dynamic programming algorithm based on time windows and p-QOD, to ensure all of the task time windows are covered, as well as minimizing the platform’s cost. Finally, we determine the payment for each user through a Vickrey–Clarke–Groves auction (VCG) considering the user’s true data quality (t-QOD), which is based on their submission time. Through both rigorous theoretical analysis and extensive simulations, we demonstrate that the proposed mechanisms achieve high computation efficiency, fairness, and individual rationality.

1 Introduction

Recently mobile crowd sensing systems (MCS) have emerged as a novel networking model (e.g., smartphones and smart watches), giving rise to extensive concerns for solving the complex sensing applications from the significant demands of people’s lives, including Haze Watch for pollution monitoring, NoiseTube and Ear-Phone for creating noise maps, which leverage the ubiquity of sensor-equipped mobile devices to collect data at low costs. These provide a new compelling paradigm for solving the problem of large-scale sensing data collection.

The key challenge for the MCS system is how to design an effective incentive mechanism. The incentive mechanism can motivate more participation in MCS with minimum cost, to ensure the reliability of the data quality. For the participants, incentive mechanisms ensure individual rationality and make the payment fair. However, most of MCS applications are based on voluntary user participation or lack effective incentive mechanisms, especially for the time-sensitive crowd sensing system.

Recent studies have focused on time-sensitive systems. These studies include the continuous time interval coverage tasks that require completing sensing data in the entire time interval publicized by the platform [1]. However, most of the existing mechanisms fail to incorporate users’ quality of data (QOD) and the impact of user submission time on the platform. The meaning of QOD varies for different applications. For example, in the Med Watcher system QOD refers to the quality of up-loaded photos (e.g., resolution, contrast, sharpness, etc.). In air quality monitoring MCS systems, QOD means a user’s estimation accuracy of air quality.

In order to solve these problems, we propose a time-sensitive incentive mechanism for a practical scenario. Unlike most of the previous work, we use an important indicator known as “quality of user’s data” (QOD). First, we design a prediction model based on the user history data (p-QOD). We use the time attenuation factor (TAF) to denote the affect weight of QOD, to calculate user’s p-QOD. Next, considering users’ strategic behaviors, our system uses p-QOD to calculate user bids. We design a dynamic programming algorithm based on the time window and user’s bid to ensure the continuous time-interval coverage while satisfying the minimum social cost. Finally,considering the impact of users’ submit time on QOD, we weight the true quality of the data (t-QOD) based on the submission time and determine the payment for each user through VCG auction while considering the t-QOD. Similar to traditional VCG mechanisms, ours maximizes the social welfare.

• Apart from other reverse combinatorial auctions, our mechanism also satisfies fairness between users while approximately maximizing the social efficiency and reducing the platform costs in time window case. The key contributions of our work are the following: A simple yet representative formulation based on the social optimization user selection (SOUS) problem to address the strong requirement of continuous time-interval coverage. Using the time attenuation factor (TAF) to denote the affect weight of history QOD. Next, we integrate p-QOD into the time-window selection phase, and select winners that meet the needs of the platform.

• We design a payment incentive mechanism t-QOD VCG considering the influence of the user submit times. Apart from other reverse combinatorial auctions, our mechanism also satisfies fairness between users while approximately maximizing the social welfare and reducing the platform costs in the time window case.

• We perform extensive simulations to evaluate the effectiveness of our incentive mechanism.

The rest of the paper is organized as follows. Section 2 reviews related work. The system model of our mechanism is introduced in Sect. 3. We evaluate the performance of the user selection and user payment mechanism via simulations in Sect. 4. Finally, we conclude our paper in Sect. 5.

2 Related Work

At present, a number of mobile crowd sensing applications have been designed and implemented. For example, Ahnn [2] designed a system named GeoServ as a distributed sensing platform, where millions of participants can take part in urban sensing and share information using always-on cellular data connections. Lee et al. proposed a reverse auction by use of mechanisms such as virtual participation credit (VPC) and recruitment credit (RC) [3] for collecting users’ sensing data. They designed a novel reverse auction-based dynamic price (RADP) incentive mechanism, in which the service provider publicized time tasks in each round and users sold their sensing data to the provider with users’ claimed bid prices. However, the data collected did not meet the task time requirements. The Vickrey Clark Groves (VCG) reverse auction [4] is a payment model where each bidder’s compensation is the damage caused by the bidder’s accession to all other bidders. In [5], the VCG auction updated rules to adjust user distribution based on the online mechanisms. Koutsopoulos [6] introduced the VCG auction. Each time the service provider receives a request, it publishes the sensing task and a reverse auction is opened to complete the task. A Bayesian game is used on the participants once the auction is open. The mechanism maximizes the revenue of each user and proves that the game achieves a Bayesian Nash equilibrium. Yang et al. considered two system models [7]: the platform-centric model design and incentive mechanism using a Stackelberg game; and the user-centric model design and auction-based incentive mechanism that allows users to control their payment more.

Guo in [8] introduced a formal concept model to characterize group activities and classify them into four organizational stages. This paper presents a group-aware, mobile, crowd-sensing system called MobiGroup, which supports group activity organization in real-world settings. In [9], the consideration of data quality is included into the design of incentive mechanisms for crowd sensing, and participants are paid for how well they perform, to motivate the rational participants to perform data sensing efficiently. This mechanism estimates the quality of sensing data, and offers each participant a reward based on effective contribution. Pouryazdan [10] adopt vote-based approaches, and presented a thorough performance study of vote-based trustworthiness with trusted entities that are a subset of the participating smartphone users. The reputations of regular users are determined based on vote-based (distributed) reputations.

Liu et al. [11] introduced four key design elements. The QoI is quantified in relation to the level they require. The credits are quantified based on the degree of satisfaction. The Gur Game used the two above indexes in the mathematical framework of the Gur Game for distributed decision-making, and the dynamic pricing scheme allocated credits to participants while minimizing the necessary adaptation of the pricing scheme from the network operator. A common feature of the existing work is that they do not consider the QOD may change over time. This is the major difference with our mechanisms.

3 Problem Formulation and Proposed Solution

3.1 System Overview

The MCS in this paper consists of a cloud platform and a set of N users ${\text{U}}\, = \,\left\{ { 1, \ldots ,{\text{n}}} \right\}$. In real scenarios of MCS, there are many applications based on the time window, such as monitoring of real-time vehicle flow, continuous measurement of air quality, and the long-term observation of specific regional noises. The MCS platform must collect continuous data at a specific time window. In this paper, we assume the MCS is designed for these practical and universal time-window scenarios. For the platform, these time-sensitive tasks can’t be done by a single user. The sensing data that all users must submit must meet the full coverage of the task time, to ensure the data integrity of the system.

Our platform first publishes the time-sensing tasks. Let G represent the length of task time requirements, ${\text{G}} = \left[ {{\text{T}}_{\text{S}} ,{\text{T}}_{\text{E}} } \right]$, ${\text{T}}_{\text{S}}$ denote the task start time, and ${\text{T}}_{\text{E}}$ denote the task end time. The platform requests participants executing sensing tasks from $T_{S}$ to $T_{E}$ to submit their sensing data. Thus, participants should submit their sensing data in the required time window. In addition, the sensing data is invalid if users submit data that is not in the valid time G. Assume that a crowd of smartphone users ${\text{U}} = \left\{ {1, \ldots ,{\text{n}}} \right\}$ are the participants interested in our sensing tasks. Each participant uploaded their own free time windows set $\Phi _{\text{i}} = \left\{ {\left[ {{\text{s}}_{\text{i}} \left( 1 \right),{\text{e}}_{\text{i}} \left( 1 \right)} \right], \ldots ,\left[ {{\text{s}}_{\text{i}} \left( {\text{k}} \right),{\text{e}}_{\text{i}} \left( {\text{k}} \right)} \right]} \right\}, {\text{s}}_{\text{i}} \left( {\text{k}} \right)$ and ${\text{e}}_{\text{i}} \left( {\text{k}} \right)$ are the start time and end time, respectively. Any ${\text{s}}_{\text{i}} \left( {\text{k}} \right) < {\text{T}}_{\text{S}}$ or ${\text{e}}_{\text{i}} \left( {\text{k}} \right) > {\text{T}}_{\text{E}}$ is invalid data and can’t bring extra revenue for any user i. The problem of winner determination and payment can be decoupled into two separate problems. We formulate the winner determination phase as Social Optimization User Selection (SOUS) problem. Considering each user’s bid and time window, our MCS system maximizes the social efficiency of the platform as given in Definition 1.

Definition 1.

(SOUS Model) The expected social efficiency maximization problem

$$ Y\left( H \right) = \hbox{max} \left[ {y\left( G \right) - \sum B_{i} } \right] $$

(1)

$$ {\text{s}}.{\text{t}}. {\text{G}}{ \sqsubseteq } \cup_{{i \in U,\theta \in \left\{ {1, \ldots ,k} \right\}}} \left[ {s_{i} \left( \theta \right),e_{i} \left( \theta \right)} \right] $$

(2)

where ${\text{y}}\left( {\text{G}} \right)$ is the utility function of the platform when the entire time window tasks were performed, which are computed as follows. Each user’s bid $B_{i}$ is calculated by the platform based on the user’s history quality of data. H is the set of winners, ${\text{H}} \in {\text{U}}$.

Definition 2.

(Platform Utility) The utility of the platform is

$$ y\left( G \right) = v\left( G \right) - \sum\nolimits_{i \in H} {P_{i} } $$

(3)

which denotes if all of the data obtained by the platform meets the coverage of time window G. The data value obtained by the platform is ${\text{v}}\left( {\text{G}} \right)$. Each user’s paid is ${\text{P}}_{\text{i}}$, which is computed by the platform.

The workflow of the system is described as follows

• 1. First, the platform publishes the sensing time window, ${\text{G}} = \left[ {{\text{T}}_{\text{S}} ,{\text{T}}_{\text{E}} } \right]$, to users.

• 2. Each user i submits its set of tasks $\Phi _{\text{i}}$, consisting of the set of tasks that user i wants to execute.

• 3. Based on the user’s p-QOD and time windows $\Phi _{\text{i}}$, the platform determines the set of winners ${\text{H}}\, ( {\text{H}} \in {\text{U)}}$.

• 4. Based on user’s true data quality (t-QOD) and the submission time, the platform pays the winners. Specifically, a loser does not execute any task and receives zero payment.

3.2 The Predict Quality of Data (p-QOD)

In general, the definition of QOD is as a metric to measures the quality of sensed data from participants. QOD determines user bids and the choice of the platform. In our user selection phase, we use historical records to predict the next time of quality that the user can achieve, p-QOD. First, we use the time attenuation factor (TAF) to denote the affect weight of p-QOD. Second, the DNC algorithm [12, 13] is used to calculate users’ p-QOD. Assuming that each historical data’s quality is arranged in a queue Q, and each history execution time ${\text{t}}\left( {\text{Q}} \right)$ satisfies:

• (1) ${\text{t}}\left( {\text{Q}} \right) \ge {\text{t}} - {\text{T}}$, where ${\text{t}}$ represents the current time and T represents the span of time (e.g. a week or a mouth).

• (2) The header of the queue was the QOD for the last time, and the tail of the queue was the QOD for the earliest time, as shown in Fig. 1:

  Fig. 1.

  

  Historical data’s quality.

Different colors represent different users’ QOD. The blue one in Fig. 1 was the QOD for the last time and the tail of the queue with the dotted line was the QOD for the earliest time. As shown in Fig. 1, we only consider the historical quality of data in t-T (e.g. the data for the last month) when calculating the quality of the next time. Thus, the TAF $\uplambda_{\text{i}}$ of the first h data of user i is

$$ \lambda_{i} = \left\{ {\begin{array}{*{20}c} 0 & {t\left( Q \right) < t - T} \\ {1 - \frac{t - t\left( Q \right)}{T}} & {t\left( Q \right) \ge t - T} \\ \end{array} } \right. $$

(4)

According to the TAF, the p-QOD ${\text{p}}\_{\text{q}}_{\text{i}}$ of this time is

$$ p\_q_{i} = \frac{{\sum \lambda_{i} Q_{h} }}{{\sum \lambda_{h} }} $$

(5)

${\text{Q}}_{\text{h}}$ indicates the first h data’s quality for user i, and $\uplambda_{\text{h}}$ is the first h data’s TAF, calculated by (4). The TAF indicates the current task time had a higher impact on user’s p-QOD, while the earlier task time had a lower influence on user’s p-QOD.

3.3 Incentive Mechanism in SOUS Model

3.3.1 Mechanism Design

In our SOUS model, the platform first publicizes the sensing time window ${\text{G}} = \left[ {{\text{T}}_{\text{S}} ,{\text{T}}_{\text{E}} } \right]$. Next, it determines the winners based on their $\widehat{\text{c}}_{\text{i}} \left( {{\text{p}}\_{\text{q}}_{\text{i}} } \right)$, which represents the user’s cost function in this round that is calculated by the platform. The users’ time windows are independent of each other, which means there is no contact between different users’ time windows $\Phi _{\text{i}}$ and $\Phi _{\text{j}}$. According this, we propose an algorithm based on dynamic programming to solve the SOUS problem illustrated in Algorithm 1.

The SOUS problem is equivalent to the problem of maximizing social efficiency, as shown in Definition 1: ${\text{Y}}\left( {\text{H}} \right) = { \hbox{max} }\left[ {{\text{y}}\left( {\text{G}} \right) - \sum {\text{B}}_{\text{i}} } \right]$, the value of ${\text{y}}\left( {\text{G}} \right)$ is continuous, since the platform publishes the sensing time window G until all time window tasks are performed. Therefore, the problem can be treated as a minimizing social cost problem.

$$ min_{i \in U} \{ C\left( i \right)| T_{E} \in \left[ {s_{i} \left( k \right),e_{i} \left( {\text{k}} \right)} \right]\} $$

(6)

$$ s.t. G \subseteq {\bigcup }_{{i \in \left\{ {1, \ldots .,n} \right\}\left[ {s_{i} \left( k \right),e_{i} \left( k \right)} \right]}} $$

(7)

The constraint in formula (7) means summing all users’ time windows should cover the platform requirements from ${\text{T}}_{\text{S}}$ to ${\text{T}}_{\text{E}}$. We assume that there are enough users satisfying the constraint involved in the sensing tasks. Users are sorted according to the end time of the time windows, such as ${\text{e}}_{1} \left( 1 \right) \le {\text{e}}_{2} \left( 2 \right) \le \ldots \le {\text{e}}_{\text{n}} \left( {\text{n}} \right)$. ${\text{C}}\left( {\text{i}} \right)$ is the minimum social cost covering $[{\text{T}}_{\text{s}} , {\text{e}}_{\text{i}} \left( {\text{k}} \right)]$. Considering all ${\text{C}}\left( {\text{i}} \right)$ in the above order have been computed, the state transition is

$$ C\left( i \right) = \left\{ {\begin{array}{*{20}l} {\arg min_{{e_{j} \left( k \right) > s_{i} \left( k \right)_{j < i} }} C\left( j \right) + \widehat{c}_{i} \left( {p\_q_{i} } \right), } \hfill & {T_{S} \notin \left[ {s_{i} \left( k \right),e_{i} \left( k \right)} \right]} \hfill \\ {\widehat{c}_{i} \left( {p\_q_{i} } \right) ,} \hfill & {T_{S} \in \left[ {s_{i} \left( k \right),e_{i} \left( k \right)} \right]} \hfill \\ \end{array} } \right. $$

(8)

${\text{C}}\left( {\text{i}} \right)$ is the minimum value of the sum of ${\text{C}}\left( {\text{j}} \right)$ which satisfies ${\text{e}}_{\text{j}} \left( {\text{k}} \right) > {\text{s}}_{\text{i}} \left( {\text{k}} \right)\left( {\forall {\text{j}} < i} \right)$ and the bid ${\text{B}}_{\text{i}} = \widehat{\text{c}}_{\text{i}} \left( {{\text{p}}\_{\text{q}}_{\text{i}} } \right)$. We obtain the winners H that satisfy the minimum social cost.

3.4 QOD-VCG Auction in User Payment

3.4.1 Weight the True Quality of Data (t-QOD)

After the winners submit their data, our platform obtains users’ true data quality. The users’ submission times affect the performance of the task execution (e.g. the user submits its data after the end of the task, and can’t collect sufficient data). Therefore, in order to ensure the fairness of the payment mechanism, we design an incentive mechanism based on QOD-VCG auction, using user’s true quality of data (called t-QOD) ${\text{t}}\_{\text{q}}_{\text{i}}$. We weight the true quality of the data (t-QOD) based on the submission time and determine the payment for each user through VCG auction while considering the t-QOD.

In this paper, we reasonably assume that the platform uses weighted aggregation to calculate Q (the sum of the QODs of the winners that execute these tasks) as ${\text{Q}} = \sum\nolimits_{{{\text{i}}:{\text{i}} \in {\text{H}}}} {\upalpha_{\text{i}} * {\text{t}}\_{\text{q}}_{\text{i}} }$, where $\upalpha_{\text{i}}$ is the weight of ${\text{i}}$ submits its quality ${\text{t}}\_{\text{q}}_{\text{i}}$. The value of $\upalpha_{\text{i}}$ changes over time. Thus, $\upalpha_{\text{i}}$ is considered as a time factor [9]. Suppose that the user’s data submits the time as t. Let ${\text{T}}_{\text{S}} = {\text{s}}$ and ${\text{T}}_{\text{E}} = {\text{e}}$ for convenience. If ${\text{i}}$ submits his data in $\Phi _{\text{i}} ({\text{s}} \le {\text{t}} \le {\text{e}})$, then the time factor $\upalpha_{\text{i}} = 1$. However, with the delay of ${\text{i}}$ submits it’s data $({\text{t}} > e)$, the negative effect of $\upalpha_{\text{i}}$ on ${\text{q}}_{\text{i}}$ is greater. Formula (10) is the function of $\upalpha_{\text{i}}$, $\upalpha_{\text{i}} = {\text{g}}\left( {{\text{t}} - {\text{e}}} \right)$ (9). In addition, ${\text{f}}\left( {\text{x}} \right)$ is a sigmoid function (10) and ${\text{sgn}}\left( {\text{x}} \right)$ is a sign function (11).

$$ g\left( {t - e} \right) = 2 \times sgn\left( {t - e} \right) \times f\left( {e - t} \right) + sgn\left( {e - t} \right) $$

(9)

The expression of sigmoid function ${\text{f}}\left( {\text{x}} \right)$:

$$ f\left( x \right) = \frac{1}{{1 + e^{ - x} }} $$

(10)

The expression of sign function ${\text{sgn}}\left( {\text{x}} \right)$:

$$ sgn\left( x \right) = \left\{ {\begin{array}{*{20}l} {1,} \hfill & {x > 0} \hfill \\ {\frac{1}{2},} \hfill & {x = 0} \hfill \\ {0,} \hfill & {x < 0} \hfill \\ \end{array} } \right. $$

(11)

The functional model of $\upalpha_{\text{i}}$ is shown in Fig. 2, where x = t − e, $\upalpha_{\text{i}} = {\text{g}}\left( {{\text{t}} - {\text{e}}} \right)$.

Fig. 2.

Time factor function model.

The MCS system accounts for the dynamic changes of users’ behavior patterns when they submit their data. The aggregation error [14] of the sum of the QODs (Q) submitted by the winners and the task demand QODs $(\overline{\text{Q}} )$ is upper bounded by a predefined threshold $\vartheta$, $\overline{\text{Q}} - {\text{Q}} \le \vartheta$. Intuitively, the larger $\vartheta$ is, the more QOD will be available to the platform.

3.4.2 Mechanism Design

In this paper, we introduce QOD-VCG extended from the payment mechanism proposed in [15]. The QA-VCG payment mechanism relied on data quality to pay for users. However, the time that winners submit their sensing data in our time window system can’t be predicted accurately. Since the QOD varies with time, we propose a time-based QOD-VCG payment mechanism based on the QA-VCG. We formulate the payment problem in (12), and set $t\_q_{i}$ to be controlled by time factor $\upalpha_{\text{i}}$, to eliminate the unfairness caused by time delay.

$$ P_{i} \left( {\widehat{c}_{i} |\overline{c}_{i} } \right) = Y\left( H \right) + \widehat{c}_{i} \left( {t\_q_{i} } \right) - Y\left( {H_{ - i} ,\overline{c}_{i} } \right) $$

(12)

${\text{P}}_{\text{i}} \left( {\widehat{\text{c}}_{\text{i}} |\overline{\text{c}}_{\text{i}} } \right)$ in (12) represents the platform’s payment to user ${\text{i}}$ when the bid of ${\text{i}}$ is $\overline{\text{c}}_{\text{i}} .$ The cost function of ${\text{i}}$ is $\widehat{\text{c}}_{\text{i}} \left( \cdot \right)$. Thus, under the limitation of the aggregation error, the objective of QOD-VCG can be formulated as

$$ \begin{array}{*{20}l} {Y\left( H \right) = \mathop {\hbox{max} }\limits_{{q_{i} \in Q}} \mathop \sum \limits_{i = 1}^{n} \left[ {y_{i} \left( {\alpha_{i} *t\_q_{i} } \right) - \widehat{c}_{i} \left( {{\text{t}}\_q_{i} } \right)} \right] ,} \hfill \\ {s.t. Q - \overline{Q} \le \vartheta } \hfill \\ \end{array} $$

(13)

We use ${\text{Y}}\left( {{\text{H}}_{{ - {\text{i}}}} ,\overline{\text{c}}_{\text{i}} } \right)$ (${\text{H}}_{{ - {\text{i}}}}$ denotes all the winners except user i) to denote the social surplus, in case of the bid of ${\text{i}}$ is $\overline{\text{c}}_{\text{i}}$ and the cost function of ${\text{i}}$ is $\widehat{\text{c}}_{\text{i}} \left( \cdot \right)$ while other users’ k (except user i) bid is $\widehat{\text{c}}_{\text{k}}$.

$$ Y\left( {H_{ - i} ,\overline{c}_{i} } \right) = \sum\nolimits_{k \ne i}^{n} {\left[ {y_{k} \left( {\alpha_{k} *t\_q_{k} } \right) - \widehat{c}_{k} \left( {t\_q_{k} } \right)} \right] + \left[ {y_{i} \left( {\alpha_{i} *t\_q_{i} } \right) - \overline{c}_{i} \left( {t\_q_{i} } \right)} \right]} $$

(14)

Both $t\_q_{i} \,{\text{and}}\, t\_q_{k}$ in Eq. (14) are the different QODs of user i and k, respectively.

If user ${\text{i}}$ reports it’s true cost function ${\text{c}}_{\text{i}} \left( \cdot \right)$, the profit of ${\text{i}}$ can be expressed as

$$ \begin{aligned} u_{i} \left( {c_{i} |\overline{c}_{i} } \right) & = P_{i} \left( {\widehat{c}_{i} |\overline{c}_{i} } \right) - c_{i} \left( {t\_q_{i} } \right) \\ & = \sum\nolimits_{k \ne i}^{n} {\left[ {y_{k} \left( {\alpha_{k} *t\_q_{k} } \right) - c_{k} t\_\left( {q_{k} } \right)} \right] + \left[ {y_{i} \left( {\alpha_{i} * t\_q_{i} } \right) - c_{i} \left( {t\_q_{i} } \right)} \right] - Y\left( {H_{ - i} ,\overline{c}_{i} } \right)} \\ \end{aligned} $$

(15)

Based on the above definitions, (15) is maximized when the bid of ${\text{i}}$ is the true cost ${\text{c}}_{\text{i}} \left( \cdot \right)$. As a result, only users reporting their real cost function would maximize their profit ${\text{u}}_{\text{i}} \left( {{\text{c}}_{\text{i}} |\overline{\text{c}}_{\text{i}} } \right)$.

4 Performance Evaluation

4.1 Data Description

The experiment in this paper is based on a noise model, where the intensity of the noise is varies at different times in the same place. The noise model provides help with travel and purchases. A number of college students were selected as experimental participants. The participants in this experiment were equipped with a timer, accelerometer, and the audio signal sampling microphone device that supports 16 bits 44.1 Hz. The mobile devices of the participants are not restricted. First, we publicize different tasks with different sensing time windows in many different locations. Next, participants collect sensing data with different devices in different ways (i.e., walking, taxi, or bus). Finally, the platform measures the performance of the participants according to the time and QOD submitted by the user and pays the participant.

4.2 Baseline Method

We first compare the platform’s total payment of the QOD-VCG auction with the traditional VCG auction. We integrate the concept of t-QOD defined in Sect. 3 into the VCG payment problem. Next, we use a baseline method MSG-greed to select N users as winners, according to the descending order of the value ${\text{q}}_{\text{i}} ,$ until the error-bound constraints of all tasks are satisfied. Like our QOD-VCG mechanism, the baseline auction also satisfies individual rationality.

4.3 Experiment Settings

In order to measure the performance of the system, we set different time windows in different areas. We chose three different locations and four different time periods. The start times and end times are different for each. Because the noise collection experiment is conducted in colleges, it accounts for the class times and rest times of the users. The participation may be different, so the time window settings are shown as Table 1.

Table 1. Settings for areas and sensing time windows

In our QOD-VCG auction, we consider the two settings described in Table 2. In setting I, we fix the number of tasks as K = 30, and vary the number of users from 50 to 150. In setting II, we fix the number of users as N = 130 and vary the number of tasks from 30 to 60. We assume that participants in the SOUS model calculated the same QOD through their historical data. The values of $\vartheta$ and $\alpha_{i}$ for any user $i \in N$ are based on their true behavior.

Table 2. Settings for QOD-VCG auction

4.4 Performance Evaluation

A: Time Window

Since the platform needs to collect data from different areas and time windows, the following figures plot the number of users and number of winners in different time windows. We determine the different end times, which means the different time windows G are an index to measure the system.

For our simulation of the SOUS mechanism, which is illustrated in Fig. 3 shows that, when the length of |G| increases, not only do the number of users increase, but the number of winners also increase. Because of the increase of the sensing time, there are more participants in each area to perform tasks. Therefore, the platform needs to collect more participants to perform the sensing task. As the time increases, the winners of the auction will also grow. The unsmoothed curves in Fig. 3 are due to the experiment that was conducted at the school and affected by the class time, resulting in the fluctuation of Fig. 3.

Fig. 3.

Performance of SOUS with various end time of the sensing time window

B: Platform’s Total Payment

We compare the platform’s total payment generated under setting I (a) and II (b) using the QOD-VCG auction and the baseline auction MSG-greed mechanism, in both setting I and II as shown in Fig. 4. The platform’s total payment of the QOD-VCG auction is far less than that of the baseline and VCG auction. The unsmoothed curves in Fig. 4 as well as in the forthcoming Fig. 5 are due to the parameter $\upalpha_{\text{i}} ,$ which varies with time, as shown in Fig. 2. We conclude that the platform’s total payment of the QOD-VCG auction is close to optimal and far better than that of the baseline auction. Compared with the traditional VCG auction, the data of QOD-VCG is varied, due to the introduction of the time factor. Hence, the payment to the winner will be more reasonable than other payment mechanisms.

Fig. 4.

Performance of QOD-VCG in platform’s payment comparison with other mechanisms under setting I and II

Fig. 5.

Performance of QOD-VCG in social efficiency compare with other mechanisms under setting I and II.

C. Social Efficiency

In Fig. 5, we show the comparison of the social efficiency under setting I (c) and II (d) between the QOD-VCG auction, VCG auction, and the baseline auction mechanism in both settings I and II. It is obvious from these two figures that the social efficiency of the baseline auction is significantly less than the QOD-VCG auction. By increasing the number of users and tasks, the social efficiency is also increased. Hence, our social efficiency is closely related to the social cost; the cost will increase with the increase of time window. The bid price may decline with the increase of the number of bidders over time, and the social cost unexpectedly decreased. From the two figures above, we also know that the QOD-VCG auction obtains close-to-optimal social welfare, which is closer to the optimal social welfare.

5 Conclusion

In this paper, we design QOD-aware incentive mechanisms for MCS systems based on the SOUS problem and VCG auction. We design an individual rationally and computationally efficient mechanism for selecting optimal users. For the payment stage, we design a QOD-VCG mechanism that achieves close-to-optimal social efficiency while satisfying individual rationality and fairness. Moreover, our theoretical analysis is validated through extensive simulations.

The system designed in this paper has certain advantages from the experimental results. However, there are still some shortcomings. The next steps focus on the following aspects: (1) The computational efficiency of the model being further optimized; (2) Designing online incentive model to meet the participants in real-time dynamics to join; and (3) Using the long-term user participation incentive in our mechanism.