论文总字数：25272字

摘 要

移动群集感知（Mobile Crowd Sensing， MCS）是一种新兴的众包模式，它充分地利用强大的移动设备来收集数据以达到任务发布者的目的。为了吸引更多用户参与到移动群集感知系统中，诸如报酬奖励的激励机制是非常必要的。另一方面，由于预算有限，任务发布者同时需要决定支付多少报酬给用户。基于此，本文从任务发布者的角度出发，研究面向移动群集感知的激励相容机制：任务发布者发布了一些种类不同的任务,然后通过给定参与用户一定的报酬来吸引用户完成任务。任务发布者的目标是在完成所有任务的情况下尽可能地减少预算成本。本文考虑了两种实际应用场景，一种是离线场景，即所有用户信息是已知的。在这种场景下，我们设计了一种基于贪心算法的离线场景机制。另一种是动态在线场景，即系统只知道当前时刻之前到达用户的信息，未来到达用户的信息是未知的。在这种场景下，我们设计了动态在线机制。我们首先通过理论证明在上面两种场景下的机制都满足计算有效性、个体理性、激励相容性、参与公平性四个目标。此外，通过仿真实验,我们验证了我们设计的机制具有很高的系统效益。

关键词：移动群集感知，机制设计，计算有效性，激励相容，个体理性，参与公平性

Towards Incentive-Compatible Mechanism Design for Mobile Crowd Sensing

Abstract

Mobile crowd sensing (MCS) is a new crowdsourcing paradigm which sufficiently makes use of powerful mobile devices to collect data to achieve crowdsourcer’s goal. To attract more users to participate in MCS system, incentive mechanisms are necessary. On the other hand, crowdsourcer should determine the payment for the users due to the budget constraint. From the crowdsourcer’s point of view, we investigate the incentive-compatible mechanism towards mobile crowd sensing that crowdsourcer wants to find a subset of users to complete a set of different tasks, and the payment he pays should be as small as possible. We consider two realistic scenarios, one is the offline scenario where the information of the users is known a priori, and we design Greedy-Based Offline Mechanism. The other one is the dynamic online scenario where the system only knows the information of the users before the current time, without knowing the future information, and we design a dynamic online mechanism. We prove that both the two mechanisms satisfy the computational efficiency, individual rationality, incentive compatible and consumer sovereignty. Through simulation, we evaluate the theoretical properties of our mechanisms and determine that the designed mechanism achieves high system efficiency.

Keywords — mobile crowd sensing, mechanism design, computational efficiency, incentive compatible, individual rationality, consumer sovereignty

目 录

摘要 I

Abstract II

第一章 绪论 1

1.1 引言 1

1.2 论文结构及创新点 2

第二章 相关工作 3

2.1 集合覆盖问题 3

2.2 移动群集感知机制设计 3

第三章 系统模型和问题描述 4

3.1 系统模型 4

3.2 问题描述 5

3.3 设计目标 6

第四章 离线场景机制设计 7

4.1离线场景机制设计 7

4.2 机制分析 9

第五章 在线场景算法 11

5.1 在线场景机制设计 11

5.2 机制分析 13

第六章 实验设计与验证分析 15

6.1 仿真设置 15

6.2 实验结果 16

总结 18

致谢 19

参考文献 20

第一章 绪 论

1.1 引言

随着互联网技术的快速发展，一种新的商业形式最近越来越受到人们的青睐，政府部门、企业公司和个人可以把他们想要完成的任务发布到网络中，雇佣感兴趣的临时工人来完成这些任务，然后给予他们相应的报酬。这种商业模式也可以称为众包：通过成熟的众包平台，任务发布者不仅可以方便迅速地和工作者联系在一起，同时省去了繁杂的招聘程序，进而为这些任务发布者节省了额外的招聘开销^[1]。

在过去的几年里，智能手机以迅猛的速度进入了人们的生活，影响了人们的生活方式。随着4G网络的普及和处理器的高速发展，笔记本电脑慢慢地淡出了人们的生活。在2010年，智能手机的销量第一次超过了个人电脑^[2]。这比预期的2012年要快了2年^[3]。根据国际数据公司（IDC）全球手机季度跟踪报告，预计在2015年全球会售出有982,000,000部智能手机^[4]。现在，智能手机是可编程的，并且装有一系列便宜且功能强大的嵌入式传感器，例如加速度计、数字式罗盘、陀螺仪、GPS、麦克风和相机。这些传感器能够非常有效地记录人们的活动和感知人们周围的环境。因此，智能手机在方方面面影响了人们的生活，例如社会网络、环境监测、贸易、医疗保健和交通^[5]。

如果所有的智能手机组成一个移动传感网络，这将会成为历史上最大的移动传感网络。我们可以利用这些智能手机和到处所在的无线网络来收集和分析大规模的数据，这样大规模的数据在以前是无法想象的。以前要想收集这些数据，就得在各个地方分布大量的传感器，这将花费大量的资金和精力。由于智能手机上的传感器有拥有巨大的应用潜力，很多研究者开发了基于移动群集感知（Mobile Crowd Sensing， MCS）的实际应用系统，例如构造流量/WiFi网络覆盖地图的Sensorly^[6]，提供交通信息的Nericell^[7]和VTrack^[8]等等。充足的用户参与度是衡量一个移动群集感知系统是否能提供良好服务质量的标准。现在大多数的MCS系统是基于自主参与原则的。当参与到移动群集感知系统中时，智能手机用户消耗他们的资源，如电池和计算资源等，或者提供他们的位置信息，而这有可能对他们的隐私造成威胁。为了提供优质的服务质量，众包系统希望更多地吸引用户参与到群智感知系统中来。因此，激励机制是十分重要的，给予参与用户的一定的物质奖励是一种很简单并且很有效的手段。

大多数现有的移动群集感知系统是基于离线场景的^[9]。在离线场景下，任务发布知道到达系统中所有参与用户的信息（诸如资源，成本等），收集到这些信息之后，任务发布者根据这些参与用户的信息选择一部分优质的用户来完成任务。然而，实际生活中的很多问题都是动态在线的场景，即任务发布者只能够收集到当前时刻参与用户的信息，对于未来潜在的用户是未知的。因此，一种在线的激励机制需要在不知道系统未来信息的情况下，当某些用户到达系统的时候，决定是否选择该用户。

从参与用户的角度来看，在移动群集感知系统中，用户都是理性的，他们参与到众包系统中完成任务目的都是最大化自己的利益。在实际的离线场景中，用户能够虚报自己能够胜任的任务和他完成这些任务需要的成本，来增加自身收益。但是由于用户虚报自己能完成的任务是很容易被发现的。比如某个用户夸大自己，声称能够完成自己不能胜任的任务，而当用户在指定时间内未能完成系统分配给他虚报的任务时，系统是不给他相应的报酬，这对于一个理性的用户来说是不合算的，所以我们只假设用户只能虚报自己完成这些任务需要消耗的资源。在线场景下，由于用户的到来时间是不固定的，我们假设他在虚报自己完成这些任务需要消耗的资源的同时还能虚报自己的时间，如来到系统的时间和离开系统的时间。

于是我们考虑下面这个问题，任务提供者有一系列不同的任务，用户是按随机顺序到达系统的，他提供他到达系统的时间、他能完成的任务集和完成这些任务需要的花费，在这里我们用花费来表示他的消耗的资源。用户为了最大化自己的利益会虚报自己的信息。任务提供者在规定的时间内找到用户来完成这些任务并给这些用户一些报酬，最终使得任务提供者的支出最少。为了解决该问题，我们希望我们设计出的机制能够满足如下5个目标：计算有效性、个体理性、激励相容、参与公平性和高近似性。具体来说，计算有效性是指系统能在多项式时间内分配任务，个体理性是指用户的效益不能为负，激励相容是指用户能真实地报出他的报价和他的到来/离开时间，参与公平性是指机制不能武断地拒绝一个用户，每个用户都应该有赢得任务的机会，高近似性是指我们的设计的机制产生的效益非常接近最优解的效益。

1.2 论文结构及创新点

前人的研究一般分为两类，一类研究是不区分任务种类的；另一类研究虽然区分任务种类，但是系统的目标是最大化自己的效益（用户只要完成任务就能给系统带来效益），并未考虑要覆盖所有的任务。本文研究的问题和前人的不同之处在于系统要在覆盖所有任务的条件下最小化自己的预算成本，在现实中，本文考虑的情况是存在的，所以本文的研究是有意义的。

由于直接考虑在线场景难度较大，所以本文一开始先考虑离线场景中的情况，即用户没有到来时间和离开时间，他提供他能完成的任务集和完成这些任务需要的花费，用户为了最大化自己的利益会虚报自己完成任务的成本，任务提供者在规定的时间内找到用户来完成这些任务并给这些用户一些报酬，他的目标是使得自己的支出最少。为了解决该问题本文利用了贪心算法的良好特性和借助了二阶拍卖的思想（即在拍卖中，提出最高价格的用户获胜，但是他仅需要支付提出第二高拍卖价格的金额），提出了贪心离线机制。在在线场景中，由于我们只有历史信息，并不知道未来的用户的情况，对于这种情况，本文提出了一种动态在线机制。我们把用户的子任务集和剩下任务集合的交集的模除以他的报价称作增长密度，在每一个阶段中，系统规定一个最多完成的任务量。在当前阶段中，只有当用户增长密度没超过阶段密度，且该阶段的任务量没有消耗完，系统就把任务分配给这个用户并给他一定的报酬。阶段密度是通过历史到来的用户的信息得出的。

本文的结构如下：第二章我们先介绍相关研究概况；第三章我们介绍系统模型并详细地描述问题；第四章我们提出在离线场景中设计的机制；第五章我们提出在在线场景中设计的机制；第六章我们提供了实验结果并对实验结果进行适当的分析；第七章我们对整篇文章的内容与结论进行适当的总结并对接下来的工作进行了展望。

第二章 相关工作

2.1 集合覆盖问题

我们简要地描述一下集合覆盖（set cover）问题，给定一些有限集合S₁，S₂，···，S_n，每一个集合S_t都有一个非负权重w_t。我们让。我们的目标是找到一个特殊的子集合，使得满足时，最小^[13]。这是一个NP难问题。

Chvatal^[14]提出的启发式的贪心算法能在内执行完，其中，所得到的权重和W满足，其中W_opt是最优方案的权重，。Lund和Yannakakis^[19]证明了集合覆盖问题在多项式时间内的解与最优解的近似比不可能低于，除非NP问题有拟多项式时间，其中n是被覆盖的集合的大小。Feige^[20]在相同的假设下提出了一个更低的界。

2.2 移动群集感知机制设计

Archer^[22]提出了一种在组合问题中只有一个隐含参数的激励相容机制设计的方法，他推导了满足激励相容机制的一般形式，然后根据这个形式设计了多项式时间内的只有一个隐含参数的激励相容机制。

Singer^[12]在离线场景中研究了一个传统的机制设计问题：拍卖商把任务拍卖给用户并给他们一定的报酬，用户完成任务能给拍卖商带来收益，在有预算限制时，拍卖商如何在保证激励相容的情况下最大化自己的效益？Singer提出了预算可行机制，并且证明当目标函数为子模性函数时，这个机制也同样适用。

Yang^[9]研究了移动感知中的激励相容机制。他的场景同样是离线的。他考虑了两种系统模型，一种是系统中心模型，在这种模型中，系统能提供的报酬是一个定值，并且希望能最大化系统的效益，Yang利用斯塔克尔伯格博弈来解决这个问题；第二种是用户中心模型，在这种模型中，系统没有一个固定的预算，系统的效益等于用户给他创造的效益减去支付给用户的报酬，系统希望自己的效益不要小于0，Yang提出了基于拍卖的激励机制，同样也满足激励相容。以上工作都是在离线场景中的，现在也有学者做了在线场景中的一些工作。

剩余内容已隐藏，请支付后下载全文，论文总字数：25272字

相关图片展示：