面向时空群智感知任务的众包机制设计

发布时间：2020-05-30 12:58

【摘要】：在移动众包系统中,工人可以利用智能手机,在限定时间内收集地理位置相关的感知数据,以完成面向时空的群智感知任务,譬如收集下班高峰期时间段内不同道路的拥堵信息。考虑到任务执行的开销,系统可以将存在时段重叠的群智感知任务分配给同一个工人来降低任务开销。为了激励工人积极地完成群智感知任务,系统需要给完成任务的工人支付相应的报酬。在现实场景中,工人为了最大化自身的收益,往往策略性地提供私有信息,譬如提供虚假的工作成本信息或者工作时间信息来获得更多的报酬。这使得在群智感知任务存在时段重叠的非可信环境下,已有的研究无法产生良好的分配策略。因此,本文研究如何激励工人真实地提供私有信息,优化任务分配,并最大化社会效益,即工人和众包平台的总收益。本文首先考虑面向地点同质任务的离线机制设计。在此场景中,群智感知任务和工人的信息是提前报告给系统的。本文设计了一个基于动态规划思想的VCG激励机制,并且用理论证明了该机制可达到真实性、个体理性和计算有效性三个性质。实验数据表明本文提出的离线分配机制可达到最大的社会效益和保证工人的真实性。其次,本文考虑了面向地点同质任务的在线机制设计。在此场景中,群智感知任务和工人实时到达系统,系统需要立刻决定如何分配群智感知任务。针对该场景,本文设计了基于二价拍卖的在线分配机制,并用理论证明了该机制能防止工人高报单位耗费。实验结果表明该机制优于基于直观贪心思想的分配机制并能实现更好的社会效益。最后,本文进一步考虑了面向地点异质任务的在线机制设计。在此场景中,群智感知任务和工人具有异质的位置地点信息。对地点信息进行建模后,本文设计了考虑地点异质性的二价拍卖在线分配机制,实验结果表明该机制能达到较好的社会效益,并优于两个对比的分配机制。
【图文】：

工人,平台,分配任务,上注

动众包系统的构架如图 2-1 所示，系统由用户、工人和众包平台三部分组成。存在于云端，用户在众包平台上发布任务，工人在众包平台上注册，希望可以。接下来本文描述整个流程，用户向众包平台发出任务请求；在接到任务请求后台分配任务给工人；工人完成任务后，得到执行任务所产生的任务结果，然后务结果给众包平台；最后，众包平台把任务结果返回给用户，任务便算完成。

时间重叠,系统接收,任务分配,示例

图 2-2：时间重叠任务分配的例子再比如图 2-2 所示例子：系统接收到 3 个群智感知任务：task1，task2 和 task3测同一地区的 wifi 信号强度，task1 是 1 点到 2 点，task2 是 2 点到 4 点，task3 5 点。有两个工人：Worker a 和 Worker b。Worker a 的工作时间是 0.5 点到 4.5耗费是 1，Worker b 的工作时间是 1.5 点到 5.5 点，单位耗费是 1.5。这样就会配策略：（1）是把 task1 和 task2 分配给 Worker a，把 task3 分配给 Worker b，算出来是 6；（2）是把 task1 分配给 Worker a，把 task2 和 task3 分配给 Worke耗费算出来是 5.5。本来因为 Worker a 的单位耗费比 Worker b 少，所以照道理task2 分配给 Worker a 会比较节省开销，但是本文发现，把 task2 分配给 Worker他的 task2 和 task3 之间存在重叠，而重叠部分只需要完成一次，所以把 task2位耗费高的 Worker b，总的耗费开销反而减少了。接下来本文形式化地描述系统中符号。时间被分割成相等时间长度的*1,2, , +。假设存在一群群智感知任务， *1,2, , +，对于每个群智感知任务 ∈ ，个感知时间段 , , -，，其中 ∈ *1,2, , +是群智感知任务的开始时
【学位授予单位】：东南大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP393.09

【相似文献】