群智感知中基于反拍卖模型的众包激励方法

朱旋 杨麦顺 安健 向乐乐 杨蔷薇

摘要：激励是实现群智感知（CS）众包服务的主要方法，针对现有方法在服务过程中没有充分考虑节点参与数量和恶意竞争对群智感知带来的影响，提出一种基于反拍卖模型的激励（RVAIM）方法。首先，研究众包的激励机制，结合反拍卖与Vickrey拍卖思想，构建面向任务覆盖的反拍卖模型；其次，对模型中涉及的任务覆盖、反拍卖选择和奖励实施等关键技术问题进行深入分析与研究；最后，从计算有效、个人理性、预算平衡、真实性和诚实性五个方面分析RVAIM激励方法的有效性。实验结果表明，与IMCSS和MSensing激励方法相比，RVAIM在有效性和可行性方面均有较好的表现，能够解决现有方法中的恶意竞争问题，并能够平均提升众包服务完成率约21%。

关键词：

群智感知；众包；激励机制；反拍卖；Vickrey拍卖

中图分类号： TP181 文献标志码：A

0引言

手机和Pad等移动智能终端除了基础信息通信功能外，在搭载摄像头、麦克风、GPS（Global Position System）、加速器、陀螺仪、温湿计等嵌入式传感器设备后还具备强大的数据感知能力。群智感知（Crowd Sensing， CS）[1]即是借助携带此类智能终端的移动用户，实现对用户或其周边环境多维数据的快速收集，包括温度、湿度、地理位置和噪声水平等信息，并基于这些海量感知信息进行统计和分析，进而挖掘出群体的行为模式和服务关联属性等信息。

众包[2]是实现CS的主要方法，它通过调动大众的智慧和计算能力来实现感知任务的合理分配和有效覆盖。然而，用户在提供众包服务的过程中会消耗自身资源，如电量、网络流量和时间等；同时因共享位置信息还会带来潜在的隐私威胁，致使用户参与积极性降低。激励[3-7]作为实现CS众包服务的主要方式之一，它通过设计适当的奖酬措施，来激发用户参与众包服务的积极性。进一步分析国内外相关研究[2，8-11]可以看出：1）现有的众包激励模型多数以用户数量满足任务完成要求为前提，并没有充分考虑众包中任务的参与用户数量，在实际应用中可能出现某些任务的用户数量达不到要求的情况，致使此类任务无法得到有效完成；2）现有基于拍卖模型的激励机制并没有深入分析竞争中的恶意行为给众包实现带来的影响，容易出现通过虚报任务竞标值（低于任务开销）增大用户自身效用等问题，任务竞拍过程中公平性的缺失，致使用户参与众包服务的积极性降低。

针对上述激励研究中存在的问题，本文提出一种基于反Vickrey拍卖的激励机制（Reverse Vickrey Auction Incentive Mechanism，RVAIM），以此解决众包中服务完成率低和激励机制中恶意竞争的问题。

1相关研究

激励机制是CS系统的重要组成部分。Doan等[12]对激励机制的设计提出两大挑战：一是如何招募和保持参与用户；二是怎样评估和计算参与用户的贡献。前者是从用户角度，要求参与用户的损耗、兴趣等得到满足；后者是从服务平台角度，要求对感知数据的质量和奖励预算进行权衡。Yang等[2]分别从参与用户和服务平台角度构建了PlatformCentric和UserCentric两种激励模型，前者通过计算唯一Stackelberg Equilibrium，实现服务平台效用的最大化，但用户效用仅依据时间因子进行计算，模型应用范围具有局限性；后者则基于反拍卖模型，通过真实性等四个经济特性保证了模型的有效性，但该模型并未考虑用户可能采用竞标值低于任务开销的恶意竞标方式。Tham等[13]为提高用户参与的公平性和最大化社会效用，分别提出IDF（Incentive with Demand Fairness）和TIF（Iterative Tank Filling）激励机制。Wu等[4]根据用户的历史服务可信度提出一种信誉激励机制。Li等[5]则针对用户隐私保护问题提出两种关于加强隐私安全方面的激励机制。

反拍卖模型是经济可行的，可解决用户退出和预算平衡两个典型激励问题[14]。为此，基于反拍卖模型的激励机制得到深入研究与广泛应用。Zhang等[8]考虑用户之间存在合作关系，依据服务平台数量及用户竞标数量的不同，分别提出SSModel（Singlerequester Singlebid）、SMModel（Singlerequester Multiplebid）和MMModel（Multiplerequester Multiplebid）三种激励模型，其中SSModel是UserCentric模型[2]的一个特例，SMModel是SSModel的一般形式，MMModel综合了服务平台与用户两种竞争方式，但三个激励模型均没有考虑任务竞拍过程中的恶意竞争问题。Zhao等[6]根据用户参与任务的时机，结合非负子模函数特性，提出两种在线激励机制。Gao等[7]则针对如何依据位置条件选择参与用户的问题，提出一种可实现用户长期参与的激励机制。

通过以上分析，目前激励机制主要从数据质量、区域覆盖和奖励预算等角度进行设计，即依据激励条件直接对用户进行筛选，而没有充分考虑任务的实际参与用户数量及用户竞争中的恶意行为，容易出现因任务没有适宜用户参与而导致任务没有完成的问题和因任务竞标中的恶意竞争行为而导致用户参与积极性降低的问题。

2面向任务覆盖的反拍卖激励模型

2.1构建激励模型

如图1所示，面向任务覆盖的反拍卖激励模型主要由三个组件构成：服务请求者、服务平台和服务提供者。其中，服务请求者是感知任务（简称任务）的发布者；服务提供者是任务的执行者，即众包用户；而服务平台是众包实现的核心组件，负责任务与用户的细粒度匹配，其包括任务覆盖、反拍卖选择和奖励实施三个模块。通过任务覆盖模块和反拍卖选择模块依次对参选的服务请求者进行选择，以选出参与任务的优胜者集；在任务结束后，通过奖励实施模块对优胜者集中的用户实施奖励。其中，在反拍卖过程中，服务平台被视为任务的拍卖者，而服务提供者被视为任务的竞拍者。首先，服务请求者向服务平台请求执行任务集Γ ={τ1，τ2，…，τm}（m≥2，m∈N+）；同时给出奖励集V={v1，v2，…，vm}。其中，vi为任务τi的奖励设置值，τi之间相互独立且τi不可再分。其次，服务平台向可能对Γ感兴趣的服务提供者候选集W={w1，w2，…，wn}（n≥2，n∈N+）发布任务，服务提供者wj根据自身偏好及能力选择任务子集TjΓ，并向服务平台递交任务竞标二元组Bj=（Tj，bj），其中bj为Tj的竞标值总和。假设wj独立完成Tj，任务开销为cj≥0（bj≥cj），且cj和Bj为私有信息，即对其他服务提供者是透明的。最后，服务平台通过任务覆盖模块和反拍卖选择模块选出优胜者集WsW，并将竞标结果反馈给每个参选用户；同时决定每个优胜者wj的奖励值pj≥bj。在wj完成Tj且向服务平台提交感知数据后，服务平台向其支付pj，并在Γ 结束后，将任务集的执行结果反馈给服务请求者。假设每个优胜者wj（wj∈Ws）会执行Tj，并会完成Tj中所有任务τi（τi∈Tj）；同时感知数据的质量满足服务平台要求。

2.2激励机制的特性

定义1服务提供者效用。服务提供者wj的效用uj表示为：

uj=xj（pj-cj）（1）

其中：uj为wj的奖励值与开销的差值，xj代表wj是否为优胜者。假设当xj=1时，表示wj为优胜者（wj∈Ws）；当xj=0时，表示wj未赢得任务竞拍。

定义2服务平台效用。服务平台的效用U表示为：

U=∑τk∈Tj（Ws）vk-∑wj∈Wspj（2）

其中：U为已完成任务的奖励设置值总和与支付给优胜者的奖励值总和的差值，Tj（Ws）表示所有优胜者任务子集的并集。假设服务平台在接受服务请求者的任务集Γ之后，并不会更改任务τi对应的奖励设置值vi。

理想激励机制应具备一些经济特性，包括计算有效、个人理性、预算平衡和真实性[2，8]。然而，服务请求者可以通过恶意竞争方式打破真实性且实现个人理性，即采用竞标值不大于任务开销的竞标方式。例如，在MSensing[2]的演算举例中，用户w1以b1=8赢得T1={τ1，τ3，τ4，τ5}的竞标，且p1=9。不妨假设c1=7，可得u1=2。若w1以b1≤7参与竞标，同样可得p1=9，且u1=2。虽然w1效用没有直接增加，但是此类竞标方式有效提升了赢得竞标的概率，即间接实现了效用的增加。恶意竞争行为会严重影响拍卖的公平性，进而降低服务请求者的参与积极性。鉴于此，本文设计的激励机制需满足以下5个期望特性。

1）计算有效。一个机制是计算有效的是指该机制的运行可以在一个多项式时间内完成。

2）个人理性。如果服务提供者效用是非负的，那么该服务提供者是个人理性的。

3）预算平衡。如果服务平台效用是非负的，那么该服务平台是预算平衡的。

4）真实性。一个机制是真实的是指在不管他人竞标值的情况下，没有一个服务提供者可以通过偏离任务真实估计值（任务开销）的竞标值增大自身的效用。

5）诚实性。如果服务提供者的竞标值为自身的真实预判值（不小于任务开销），那么该服务提供者是诚实的。

在5个期望特性中，计算有效、个人理性和预算平衡为3个基础特性，用于确保激励机制是可行的；真实性和诚实性为两个关键特性，用于增强机制的激励效果。真实性可减轻服务提供者在竞拍输赢等方面的担忧，Myerson[15]证明了一个拍卖是真实的必须满足选择规则是单调的和优胜者的奖励值是关键值两个条件：如果服务提供者以竞标值bj赢得拍卖，那么以竞标值bj′

3激励机制

拍卖理论[2]对于激励机制设计是一种非常好的理论工具。其中，反拍卖是一种逐级向下竞价，以最低价成交的拍卖方式；Vickrey拍卖[16]是一种密封且以次高价成交的拍卖方式。本文采用反拍卖与Vickrey拍卖相结合方式，进而提出RVAIM激励机制，即竞标值次低者将赢得拍卖。

3.1激励机制的设计

RVAIM的实现过程包括3个步骤：任务覆盖、反拍卖选择和奖励实施。首先，从竞标者数量ni=1的任务集中选出优胜者集Ws′；其次，从ni≥2的任务集中选出优胜者集Ws″及每个任务的竞标胜利者（定义6）；最后，对优胜者集Ws=Ws′∪Ws″中的每个服务提供者计算奖励值。

3.1.1任务覆盖

定义3任务完成。若任务τi的优胜者数量ni′≥1，则表示该任务完成。

优胜者是被服务平台选定的众包用户。若ni′=0，则表示任务为“无人执行”，服务平台只需统计此类任务情况并反馈给服务请求者；若ni′=1，则表示任务为“一人执行”，是任务完成的最低条件；若ni′≥2，则表示任务为“多人执行”，是任务完成的理想条件。

定义4任务覆盖条件。在竞标者数量ni=1的任务τi中，服务提供者wj成为该任务的优胜者需满足任务覆盖条件，该条件表示为：

bj≤∑Lk=1vk（3）

其中：L表示在任务子集Tj中的任务数量，∑Lk=1vk=Vj表示Tj的总奖励设置值。

任务τi有两种可能为“一人执行”情况：1）该任务只有一个竞标者wj，且wj满足任务覆盖条件；2）该任务有多个参与竞标者，但只有一个竞标者wj满足优胜者条件（定义5）。为提高任务完成率，需最大限度保留此类竞标者，下面给出任务覆盖算法的简要实现过程。

算法1任务覆盖算法（Task Covering Algorithm， TCA）。

程序前

步骤1输入：Γ，V，Bj，Ws′=；/*输入任务集、奖励集及竞标二元组，“”表示空集*/

步骤2根据Bj=（Tj，bj）统计用户参与竞标的任务集Γ′及每个任务τi的竞标者数量ni；

步骤3FOR （所有τi∈Γ′） DO

IF （ni=1） THEN

IF （满足式（3）） THEN

Ws′ ← Ws′∪{wj}；

IF （ni≥2） THEN

转到算法2；

ENDFOR

步骤4输出Ws′；

步骤5结束。

程序后

此时，Ws′是从只有一人竞标的任务集中选出的优胜者集。若wj∈Ws′，考虑wj可能竞标多个任务，如果在wj的竞标任务中包括多人竞标的任务，则wj仍需要通过反拍卖选择模块作进一步筛选。

3.1.2反拍卖选择

在基于反拍卖的激励机制中，服务平台为使自身效用最大化，会选择竞标值高而支付奖励值低的服务提供者，由于此类选择是典型NPhard（Nondeterministic Polynomial）问题[3]，因此不可能在多项式时间内找到最优服务提供者集。假设服务平台根据Vj/bj计算竞标值，即选择在单位竞标值上奖励设置值高的服务提供者（表示任务贡献量大）。同理，服务平台在预算平衡条件下从候选集W中选出Vj/bj值大且数量多的服务提供者是NPhard问题。该问题主要是由于从候选集中直接选择竞标胜利者集而产生的，为避免此类问题，本文采用一种间接实现方式，即先利用优胜者条件得到每个任务的优胜者集，再利用竞标胜利者条件对其进行筛选，进而得到任务集的竞标胜利者集。

定义5优胜者条件。在竞标者数量ni≥2的任务τi中，竞标者wj成为该任务的优胜者需满足条件为：

∑nik=1bkVk≤1（4）

其中：∑nik=1bkVk表示在任务τi中每个竞标者的bj/Vj总和。在反拍卖模块中，竞标者wj的竞标值通过bj/Vj进行计算，且由小到大进行选择。为最大限度保留“一人执行”任务中的优胜者wj，若在该条件的计算中涉及wj，则wj优先进行计算；若此时任务τi的优胜者数量ni′=1，由优胜者条件可得bj≤Vj，即wj同样满足任务覆盖条件。

定义6竞标胜利者条件。竞标者wj参选的任务子集TjΓ，假设初始Tj内的任务数为numj，满足优胜者条件的总任务数为numj′。若numj=numj′，则wj赢得Tj内所有任务的竞标，即wj为竞标胜利者。

在竞标者数量ni≥2的任务集中，考虑每个任务τi中可能有多个优胜者且只有一个竞标胜利者，为计算τi的优胜者集Si′，依据bj/Vj对τi中每个竞标者wj进行排序；为得到此类任务集的优胜者集Ws″，需依据胜利者条件对Si′作进一步判断，以选出τi的最终优胜者集Si″，下面给出反拍卖选择算法的简要实现过程。

算法2反拍卖选择算法（Reverse Auction Selection Algorithm， RASA）。

程序前

步骤1输入：Ws″=，Si′=，Si″=；

步骤2IF （ni≥2） THEN/*承接算法1中的步骤3*/

1）Sort（bj/Vj）；/*函数Sort（bj/Vj）用于对参数bj/Vj升序排序*/

2）根据式（4）计算Si′ ← Si′∪{wj}；

/*若wj∈Ws′，则wj优先进行计算*/

3）FOR （所有wj∈Si′） DO

IF （wj满足（numj=numj′）） THEN/*优胜者条件*/

Si″ ← Si″∪{wj}；

Ws″ ← Ws″∪Si″；

ENDFOR

步骤3计算每个任务Si″中的ji′、 ji″和j*i

1）j′ ← arg min{j|bj/Vj}；

2）j″ ← second_arg min{j|bj/Vj}；

3）j* ← arg max{j|bj/Vj}；

/*函数second_arg min用于计算参数bj/Vj的次低者*/

步骤4输出Ws″，（ji′， ji″， j*i）；

步骤5结束。

程序后

3.1.3奖励实施

依据Myerson理论[15]，任务集中的每个竞标胜利者都应得到奖励。目前奖励实施多数采用对任务集内的所有竞标胜利者统一计算方法，所获得的奖励值并不能较好反映其任务中的工作量，影响用户参与积极性。本文采用依据任务逐一计算奖励值的方法，并区分优胜者类型分别进行实施，其中优胜者根据任务竞标结果划分为两种类型：竞标胜利者wj（j=j″）和竞标非胜利者wj（j≠j″）。

定义7额外奖励。在“多人执行”任务中，每个任务τi为其竞标胜利者wj=j″设置额外奖励，额外奖励值Aτi表示为：

Ati=Vj″·（（bj*/Vj*）-（bj′/Vj′））（5）

其中：bj′/Vj′和bj*/Vj*分别为bj/Vj最低者wj′和最高者wj*的值。Ati可以累加，若wj在Τi中成为竞标胜利者的次数为j，则wj作为竞标胜利者而得到的总额外奖励值为Aj″=∑jk=1此处也缺少变量名称，是k=1吗？请明确。Aτi（τi∈Tj， k∈N+），其中k为Tj中任务的个数。

定义8奖励。服务平台在任务结束后对优胜者实施奖励，优胜者wj的奖励值pj表示为：

pj=max{bj，bj+Aj=j″}（6）

由于服务提供者wj在每个任务中的竞标结果不同，其奖励值也不同：若wj在任务子集Tj的竞标中全为竞标非胜利者，则pj=bj；反之，若在某些任务τi（τi∈Tj）中为竞标胜利者，则pj=bj+Aj″。在所有优胜者的奖励值计算结束后，需要对服务平台的预算平衡性进行检验，下面给出奖励实施算法的简要实现过程。

算法3奖励实施算法（Reward Implementation Algorithm， RIA）。

程序前

步骤1计算额外奖励值及总奖励设置值

FOR （所有τi∈Γ′） DO

/*Γ′表示被参与竞标的任务集，Γ′Γ*/

1）根据式（5）及（ji′， ji″， j*i）计算Aτi；/*额外奖励值*/

2）计算VΓ=∑τi∈Γ′vi；/*VΓ表示任务集Γ′的总奖励设置值*/

ENDFOR

步骤2计算优胜者的奖励值

Ws=Ws′∪Ws″；

/*Ws表示任务集Γ′的优胜者集*/

FOR （所有wj∈Ws） DO

1）根据j″统计wj为竞标胜利者的次数j；

2）Aj″=∑jk=1Aτi（τi∈Tj， k公式中并未见含有k的变量？如何理解，书写正确吗？请明确。∈N+）；/*总额外奖励值*/

3）根据式（6）计算奖励值pj；

4）P=∑wj∈Wspj；/*支付总奖励值*/

ENDFOR

步骤3预算平衡判断

IF （P>VΓ） THEN

Ws ← ，P ← 0；

ELSE 服务平台启动任务；

步骤4输出pj；/*任务结束后支付给优胜者*/

步骤5结束。

程序后

3.2演算实例

3.3有效性分析

为说明RVAIM满足第2章中设置的期望特性，分别从计算有效、个人理性、预算平衡、真实性和诚实性5个方面给予证明。

引理1RVAIM是计算有效的。

4实验结果与分析

实验从两个方面对RVAIM的性能进行评估：

1）有效性分析。对比RVAIM与其他激励机制在期望特性方面的性能，作为参照，与IMCSS（Incentive Mechanism for Crowdsourcing in the SSmodel）[8]和MSensing（Myerson Sensing）[2]激励机制进行比较。

2）可行性分析。考察RVAIM激励作用、抑制恶意竞争和任务覆盖方面的性能。

4.1实验环境及参数设置

通过Matlab设计模拟实验，实现了本文中的激励模型。为便于比较，使用和文献[2]和[8]基本相同的实验环境和参数设置。实验环境为Windows 10 PC、Intel Core i7 3.1GHz处理器、8GB内存。

模拟实验中的参数设置如表1所示。奖励设置值、任务竞标值和竞标任务数分别为各自参数值范围内的随机数。

为验证n的变化情况，假设m=100；为验证m变化的情况，假设n=100；为计算服务提供者wj的效用，假设任务开销cj=bj/2。实验运行总次数不低于100次，数据结果取其平均值。

4.2激励机制有效性分析

1）运行时间。首先通过运行时间对激励机制的计算有效性进行评估。如图3（a）所示，随着m增长，RVAIM的运行时间近似于O（m2）增长，而IMCSS和MSensing为线性增长；如图3（b）所示，随着n增长，3种激励机制的运行时间都近似于O（n2）增长。总体上，3种激励机制的运行时间比较接近，RVAIM略低于IMCSS是因为其解算过程依据任务进行，需要对任务及竞标者进行双重循环。

2）服务提供者平均效用。服务提供者平均效用通过优胜者总效用与优胜者数量之比进行计算，用于评估激励机制的个人理性。如图4所示，RVAIM在服务提供者平均效用方面优于IMCSS和MSensing，这主要是因为RVAIM中竞标胜利者的额外奖励Ati是可以累加的，促使优胜者的总效用较大。在图4（a）中，随着m增长，服务提供者的任务选择会更广泛，竞争性降低导致优胜者数量的不断增长，当m>n时，总效用达到最大。随着m进一步增长，优胜者数量会逐渐趋近于n（图6（a）），且服务提供者为赢得竞标会选择bj/Vj偏小的任务，这样优胜者总效用会减少，进而出现服务提供者平均效用降低现象。在图4（b）中，随着n增长，3种激励机制中服务提供者平均效用都出现下降现象，主要原因是由于优胜者数量保持增长，而优胜者总效用基本保持不变所引起的。

3）服务平台效用。服务平台效用依据优胜者选择的任务集进行计算，用于评估激励机制的预算平衡特性。在图5（a）中，3种激励机制中的服务平台效用都随着m增长而增长，这主要是由于服务提供者选择任务范围的扩大，更多任务会得到完成。同时，服务提供者为增大自身效用，会选择奖励设置值高的任务，也会促进服务平台效用的增加。在图5（b）中，3种激励机制中的服务平台效用曲线总体为增长态势，是由于随着n增长，优胜者数量会增加，任务集完成率会不断提升。当任务集饱和后，由于竞争性增强，服务提供者为赢得竞标，会倾向于选择奖励设置值低的任务，这将导致RVAIM和IMCSS在初始阶段出现缓慢降低现象。同时，IMCSS持续偏低是因为其在任务的选择上以用户之间的合作为基础，导致诸多任务得不到有效的完成。

4.3激励机制可行性分析

1）激励作用。如图6（a）所示，随着m增长，由于服务提供者选择任务竞争性的降低，导致优胜者数量增长并逐渐趋近于n；当竞争性降低时，服务提供者会选择奖励设置值高的任务，而竞标值会随之提高，这将增加竞标失败的概率，因此出现竞标胜利者数量逐渐减少现象。在图6（b）中，随着n增长，竞争性不断加强，在任务集Γ趋向于饱和的过程中，只有少数竞标条件更低的服务提供者才能赢得竞标，以致优胜者数量出现缓慢增长；虽然优胜者数量的增长会带动竞标胜利者数量的增长，但是当竞标者所能承受的竞标值已降至最低时，竞标胜利者数量会进入一个相对稳定状态。

2）抑制恶意竞争。RVAIM通过真实性和诚实性抑制恶意竞争行为，考虑IMCSS和MSensing在真实性的实现方法是一致的，RVAIM仅与MSensing进行对比，如图7所示。实验中允许服务提供者的竞标值偏离任务开销，且其效用包括直接效用与间接效用。假设Τj共有20个竞标者，其中b1=5，c1=4，p1=10， j″=1，bj′=4，bj*=6，竞标值变化±1将影响赢得竞标的概率为±20%。在图7（a）中，MSensing的竞标者w1可以通过降低竞标值的恶意竞争方式增加间接效用，进而增加自身效用，而w1在IMCSS中使用相同恶意竞争方式只能实现效用负增长，且无法通过提升竞标值增加自身效用，即IMCSS是真实的。由图7（b）可以看出，IMCSS中竞标值的稳定性优于MSensing，且相对于最大效用时的竞标值b=5变化幅度相小，这是因为IMCSS根据每个任务仅选择一个竞标胜利者，且该任务的优胜者无法通过改变竞标值增大自身效用，导致任务竞争中的竞标值相对集中，即竞标者仅会选择近似于真实预判值的竞标值，因此，IMCSS可以有效抑制恶意竞争行为。

3）任务覆盖。为说明任务覆盖模块的处理效果，仅假设m=100。在图8中，初始数量是指初始任务集Γ中竞标者数量ni=1的任务数量；任务覆盖后数量是指初始数量的任务通过任务覆盖模块后成为“一人执行”的任务数量；仅符合竞标条件的数量是指初始数量的任务直接通过反拍卖模块后成为“一人执行”的任务数量。随着n增长，三条曲线均呈现快速下降状态，表明竞标者数量ni=1的任务随着竞标者数量的增长在迅速减少；当n≤200时，即在任务集接近于饱和前，任务覆盖后数量持续保持并近似于初始数量；同时明显高于仅符合竞标条件的数量，表明任务覆盖模块的作用发挥是显著的，即任务覆盖模块在任务集Γ未饱和前能够有效提升任务集的完成率，平均提升约为21%。

通过与IMCSS和MSensing相比，本文方法在计算有效、个人理性和预算平衡方面的性能与IMCSS和MSensing相近，但具有任务覆盖范围广、激励特性全面和抑制恶意竞争明显的优点，提高了激励机制的适用性及可靠性。

5结语

本文针对现有的众包激励机制中因任务没有适量用户参与而使任务无法完成和因任务竞争中缺乏公平性而导致用户参与积极性低的问题，构建了面向任务覆盖的反拍卖激励模型，并在该模型的基础上，将反拍卖与Vickrey拍卖进行结合，提出一种基于反拍卖众包激励机制RVAIM。实验结果表明，该机制不仅能够有效解决现有激励方法中缺乏公平性问题，而且能够有利于提升众包服务完成率，平均可提升约为21%。本文提出的RVAIM为众包激励机制的设计提出了新的设计思路，即在服务平台预算平衡的条件下，综合考虑服务平台的任务完成率和服务提供者的参与积极性，进而获得较好的众包应用效果。

参考文献：

[1]

JAIMES L G， VERGARALAURENS I J， RAIJ A. A survey on incentive techniques for mobile crowd sensing [J]. IEEE Internet of Things Journal， 2015， 2（5）： 370-380.

[2]

YANG D， XUE G， FANG X， et al. Crowdsourcing to smartphones： incentive mechanism design for mobile phone sensing [C]// Proceedings of the 18th Annual International Conference on Mobile Computing and Networking. New York： ACM， 2012： 173-184.

[3]

PHAM H N， SIM B S， YOUN H Y. A novel approach for selecting the participants to collect data in participatory sensing [C]// Proceedings of the IEEE/IPSJ 11th International Symposium on Applications and the Internet. Piscataway， NJ： IEEE， 2011： 50-55.

[4]

WU C， LUO T， WU F， et al. An endorsementbased reputation system for trustworthy crowdsourcing [C]// Proceedings of the 2015 IEEE Conference on Computer Communications Workshops. Piscataway， NJ： IEEE， 2015： 89-90.

[5]

LI Q， CAO G. Providing privacyaware incentives for mobile sensing [C]// Proceedings of the 2013 IEEE International Conference on Pervasive Computing and Communications. Piscataway， NJ： IEEE， 2013： 76-84.

[6]

ZHAO D， LI XY， MA H. How to crowdsource tasks truthfully without sacrificing utility： online incentive mechanisms with budget constraint [C]// Proceedings of the 2014 IEEE Conference on Computer Communications. Piscataway， NJ： IEEE， 2014： 1213-1221.

[7]

GAO L， HOU F， HUANG J. Providing longterm participation incentive in participatory sensing [C]// Proceedings of the 2015 IEEE Conference on Computer Communications. Piscataway， NJ： IEEE， 2015： 2803-2811.

[8]

ZHANG X， XUE G， YU R， et al. Truthful incentive mechanisms for crowdsourcing [C]// Proceedings of the 2015 IEEE Conference on Computer Communications. Piscataway， NJ： IEEE， 2015： 2830-2838.

[9]

WEN Y， SHI J， ZHANG Q， et al. Qualitydriven auction based incentive mechanism for mobile crowd sensing [J]. IEEE Transactions on Vehicular Technology， 2014， 64（9）： 4203-4214.

[10]

LUO T， TAN HP， XIA L. Profitmaximizing incentive for participatory sensing [C]// Proceedings of the 2014 IEEE Conference on Computer Communications. Piscataway， NJ： IEEE， 2014：127-135.

[11]

LEE JS， HOH B. Dynamic pricing incentive for participatory sensing [J]. Pervasive and Mobile Computing， 2010， 6（6）： 693-708.

[12]

DOAN A， RAMAKRISHNAN R， HALEVY A Y. Crowdsourcing systems on the worldwide Web [J]. Communications of the ACM， 2011， 54（4）： 86-96.

[13]

LUO T， THAM CK. Fairness and social welfare in incentivizing participatory sensing [C]// Proceedings of the 9th Annual IEEE Communications Society Conference on Sensor， Mesh and Ad Hoc Communications and Networks. Piscataway， NJ： IEEE， 2012： 425-433.

[14]

GAO H， LIU C， WANG W， et al. A survey of incentive mechanisms for participatory sensing [J]. IEEE Communications Surveys & Tutorials， 2015， 17（2）： 918-943.

[15]

MYERSON R B. Optimal auction design： mathematics of operations research [J]. Mathematics of Operations Research， 1981， 6（1）： 58-73.

[16]

WIKIPEDIA. Vickrey auction [EB/OL]. [20160102]. [20160111]. https：//en.wikipedia.org/wiki/Vickrey_auction.