基于任务间优先关系约束的众包任务分配机制研究

1、目 录第1章 绪论1第2章 准备工作6第2.1节 系统模型6第2.2节 问题描述7第2.3节 NP难特性分析9第3章 算法设计11第3.1节 解决STAP的近似算法11第3.1.1节 确定各任务层次的部分12第3.1.2节 构造最终任务集合的部分14第3.1.3节 构造任务的优先分配序列的部分15第3.1.4节 任务分配的部分18第3.2节 解决PTAP的近似算法19第3.2.1节 对任务执行时间的预估部分19第3.2.2节 构造优先分配序列的部分20第3.2.3节 任务分配的部分20第4章 仿真模拟22第4.1节 仿真环境参数设置22第4.2节 仿真模拟结果23第5章 结论28参考文献29致

2、 谢31III摘 要众包作为一个新兴的研究领域，通过极大地利用外部的、非确定的参与人群，旨在寻求一个更快捷且低成本的途径完成系统面临的各项任务。在众包的实际应用中，一个任务通常能够被划分成许多个步骤。不同步骤对任务执行者的技能存在不同的需求，同时，步骤间会有先后顺序的约束。根据每个步骤各自的需求，任务发布者将任务划分，再将划分后的多个子任务发布到众包系统中，由系统将这些子任务分配给参与其中的任务执行者。在经过大量的文献阅读后，我们发现对于被划分的子任务间存在先后顺序约束的众包机制研究，现阶段是不足的。另外，如果一个公司将一项完整的任务交由众包平台分配完成，那么该任务往往是公司的一个项目，因此，

3、发布任务的公司通常会要求众包系统能够尽快地完成发布的任务。然而，现有的机制研究中并不存在与我们所提及的相关的设计，即一个针对任务之间的先后顺序约束，以完成所有任务花费的时间最小为优化目标的众包任务分配机制的设计。为弥补这方面存在的不足，我们对任务间存在的先后顺序约束加以考虑，并针对提出的众包系统设计了一个有性能保证的任务分配机制。由于证明了我们所提出的问题是一个NP难问题，为提高问题求解的效率，这需要我们对应地提出一个近似最优的算法。在仿真模拟阶段最终的结果表明，我们提出的算法在不同参数设置情形下算法结果始终能够获得很好的近似最优比。关键词：众包；任务分配；执行时间最小化；先后顺序约束。Abs

4、tractCrowdsourcing can be used to leverage external crowds to perform specialized tasks quickly and inexpensively. In the application of crowdsourcing, one task may often include many steps. Different steps may require different skills and have precedence constraints among them. Based on the differe

5、nt requirements of steps, the task requester may divide the task into many sub-tasks, and publish the sub-tasks in the crowdsourcing system. However, only few existing studies consider the precedence constraints among the divided sub-tasks. Moreover, one complete task from a company may be a project

6、, and companies usually want to finish their projects as fast as they can. Unfortunately, there have been no allocation mechanism with consideration of crowdsourcing tasks with precedence constraints and minimization of the total execution time simultaneously. To tackle this challenge, we consider t

7、he precedence constraints among tasks and design an efficient task allocation mechanism for the crowdsourcing system. We prove that the studied problem is NP-hard, and propose an approximation algorithm. The simulation results show that the proposed algorithm has good approximate optimal ratios unde

8、r different parameter settings.Keywords: crowdsourcing; task allocation; execution time minimization; precedence constraint. 第1章 绪论伴随着信息技术和网络技术日新月异的发展，众包技术能够通过极大地利用外部的、非确定的参与人群，找到一个更快捷且低成本的途径完成系统面临的各项任务4。图1.1 众包系统模型图因其自身的特性，近年来，众包成为了一个前景广阔的研究热点。许多以众包技术为背景的商业网站(如Amazon Mechanical Turk13、CrowdFlower1、

9、microWorkers2、Yahoo! Answers3等)会将任务发布者们给出的任务发布在平台上，吸引世界各地的大量的网络用户参与其中帮助平台完成各项任务15。图1.2 Amazon Mechanical Turk平台示意图图1.3 microWorkers网页示意图因此，众包也可以被看作是一个通过特定平台将任务外包给一群未知的网络个体用户的过程。众包技术存在的巨大潜力吸引了许多公司和学者，他们以此为研究背景提出了大量的以实现任务发布者利益最大化为目标的应用。在以众包技术为依托的众多应用中，移动感知技术尤为显眼，它通过最大限度地利用附着在参与众包的人群身上的智能手机或是其它的移动设备，以一

10、个相对低廉的成本完成一些复杂的感知任务8。例如，Kumar Rana等人开发了一个端到端的城市噪音绘制系统Ear-Phone，通过以众包为基础的数据采集方式实现了城市噪音污染的实时监测11。图1.4 Ear-Phone的系统构架示意图因此，对于通过利用众包的思想能够解决许多实际应用中面临的问题这一点是毋庸置疑的。除了在城市计算研究领域中的数据采集部分，众包的思想也被广泛应用于科学探索10、文本转录、商标设计等各个方面12。一般地，一个众包平台中的用户被分成两种类型，分别被称为“任务发布者”和“任务执行者”。任务发布者参与其中的目的是通过众包网站将一些计算复杂度很大的任务交由基数庞大的、通常是一

11、些网络个体用户的任务执行者完成，而任务执行者则是为了通过为网站完成一些简单细小的任务来获取一些报酬。在现实应用场景下，任务发布者的角色通常是由大型的商业公司或是一些非营利的组织来扮演的。他们会将一些计算量极大复杂、程度极高的任务交由平台分配完成，同时，每一个任务都会对拥有某些特定技能的任务执行者会有所要求。因此，如何进行有效的任务分配是机制设计过程中极其重要的部分。现阶段，绝大部分的众包平台会考虑将某个特定的任务交由对该任务有所了解甚至熟悉的任务执行者完成，以保障结果的有效性，因此，研究设计一个考虑先将任务划分，再将子任务分配的众包机制显得尤为必要5,7-9,14。当平台要把得到子任务分配给大

12、批量的参与其中的任务执行者时，它将面临诸多不可避免的问题。第一，任务执行者拥有不同的技能，他们在被平台安排任务的过程中受自身能力的限制，平台能够对其分配的任务会有所差异。例如，任务执行者可能来自不同的国家，因为语言障碍，涉及到与任务执行者不熟悉的语言相关的任务时，平台不会予以分配。第二，在上述的许多对任务执行者拥有的技能存在需求的众包平台中，一些特定的任务通常存在多个步骤6。例如，在对城市噪声分析的任务中，我们先会通过分布在城市各个街道的手机用户完成环境噪声数据的采集，再通过数据挖掘的相关机制对手机采集到的噪声数据处理分析，最后对分析结果的正确性进行证实。因此，实际场景下的绝大多数任务是能够被

13、划分为若干个步骤再依次被完成的，同时，这些步骤间通常存在着先后顺序特性的约束。这样的先后顺序约束可以被描述为，当且仅当优先于某个步骤的若干个步骤都被完成时，该步骤才能够被平台分配给某个任务执行者完成。通常，任务发布者会将存在若干个步骤的任务划分为多个子任务，再将这些子任务发布在众包平台上。6 对一些特定的任务之间的先后顺序关系进行的考虑，并对问题模型设计了一个众包任务分配机制。更进一步地说，公司提交的一个伴随多个步骤的任务，通常会是一个项目，而发布任务的公司通常会要求众包系统尽可能快速地完成它发布的任务。然而，现阶段并没有与我们描述的对应的、能够解决这样的问题的机制，即一个针对任务之间的先后顺

14、序约束，以完成所有任务花费的时间最小为优化目标的众包任务分配机制。在这篇论文中，我们对任务之间存在先后顺序约束的众包任务分配问题进行研究，并想要设计一个有性能保证的、以完成所有任务花费的时间最小为优化目标的任务分配算法。对于研究的问题，很容易证明它是一个NP难问题。因此，需要相应地为这个问题设计一个近似算法，使得问题求解的答案在可接受的范围内，同时也能够保证问题求解的效率。一个任务执行者对于某个任务的执行时间可能与众包系统中的其他任务执行者存在差异，这种情形会使平台面临的任务分配问题变得更复杂。对此，我们的解决思路是先通过化简最初提出的问题，得到一个简化的任务分配问题。在解决了简化的问题后，再

15、将被省去了的约束条件重新纳入问题考虑的范围，同时基于简化问题的解决方案对最开始被提出的问题进行算法设计。在简化的任务分配问题中，与之对应的任务分配算法由四个部分构成：确定该任务层次的部分、构造最终任务集合的部分、构造任务的优先分配序列的部分和任务分配的部分。首先，对于任务集合中的每一个任务，根据该任务的条件任务集合，确定该任务的层次。显然，最后一个任务集合中的任务被完成时，该任务经历的时间与完成任务集合中全部任务的整体时间是一致的。我们对最终任务定义，这类任务不存在于任务集合中任何一个任务的条件任务集合中。可以很容易明白完成任务集合中全部任务的整体时间是由任务集合中的那些最终任务预期被完成所经

16、历的时间来决定的。正因为这样的特性，才有了我们在第二部分里构造最终任务集合的相关操作。接着，通过每一个任务预期被完成所需要经历的时间，能够确定任务集合中各个任务之间的优先分配级别，并组成分配序列。当在第四部分将任务分配给任务执行者时，那些在分配序列中靠前的任务会比那些靠后的任务有更高的优先权，它们将先被平台分配出去交给任务执行者完成。在最开始被提出的任务分配问题中，与之对应的任务分配算法由三个部分构成：对任务实际被执行需要的时间的预估部分、构造任务的优先分配序列的部分和任务分配的部分。为了得到任务的优先分配序列，需要先确定平台发布的任务集合中各个任务的预估执行时间，因此在算法的第一部分，我们会

17、对任务的执行时间找到一个合理的预估方式。接着，在算法的第二部分中完成了任务的层次划分以及最终任务集合构建之后，基于任务被完成需要经历的预期的时间对任务作增序排序，得到一个任务优先分配序列。最后，根据这个构建的优先分配序列，平台将任务分配给任务执行者。论文相关工作做出的主要贡献如下：我们设计了一个针对众包系统中任务间存在先后关系约束情况的，同时有性能保证的任务分配算法。据我们所了解到的，论文所设计的机制是目前唯一的考虑了众包众包系统中任务间存在先后关系约束，同时以完成所有任务花费的时间最小为优化目标的众包任务分配机制。算法得到的分配方案对应的完成所有任务花费的时间与相同分配场景下最优的分配方式所

18、得的结果，我们将两者之比定义为近似最优比率。我们进行了大量的仿真模拟实验对所提算法的性能评估，实验结果反映论文提出的算法在不同的参数设置下始终能够维持很好的近似最优比率。论文剩余部分的安排如下。我们首先在第2节对系统模型描述。其次，对提出的近似算法的具体描述会在第3节陈述。接着，第4节的部分是通过一系列的仿真模拟实验对所提机制进行评价。最后，在第5节对论文整体的工作做出了总结。33第2章 准备工作在这一章节，我们首先介绍众包系统模型。之后详尽地描述众包模型下的任务分配问题。接着在本章节的结尾处，我们会证明提出的任务分配问题是一个NP难问题。第2.1节 系统模型在我们所研究的众包系统中存在三类角

19、色：一个任务发布者，一个众包平台和许多参与众包的任务执行者。为了让任务足够的简单，使得尽可能多的任务执行者都有能力去完成，任务发布者往往会将那些完整的任务划分为许多单一的任务。之后，任务发布者将这些被划分的任务递交给众包平台。平台将收到的所有任务一次性发布给系统中的任务执行者。那些为平台提供服务的任务执行者从平台发布的任务里选出自己感兴趣的任务，然后将各自的选择提交给平台。在进行任务分配之前的过程里，平台不得不面临各种各样的问题，如被划分好的任务之间存在着先后顺序约束，以及任务执行者在选择各自的任务时存在着的差异性。在考虑了由任务的特性而产生的各个约束后，平台遵循着这些约束对任务分配。每一个任

20、务只由一个任务执行者一次完成。最后，任务执行者会在截止期限内完成平台要求的各自需要完成的任务，再将任务的结果回复给众包平台。平台将任务执行者提交的答案汇总，反馈给任务发布者，而任务执行者提交的答案是否满足对应任务提出的要求，任务发布者会对它做出评估。在任务执行者的答案满足对应任务提出的需求后，任务执行者将会获取相应的报酬。同时众包平台也会因为受任务发布者雇佣而得到一笔报酬。图2.1 众包系统的构架我们用符号表示平台发布的任务集合。假设任务集合中存在个任务，并用表示。每一个任务执行者用符号表示。符号表示所有参与众包的任务参与者组成的集合，。发布在众包平台上的任务具体描述为，其中表示为任务的条件任

21、务集合，是对完成任务需要的实际执行时间的预估值，是任务执行者在针对任务给出符合条件的答案后得到的报酬。由于任务间存在着先后关系约束，当且仅当条件任务集合中的所有任务被完成时，任务才能够被分配给任务执行者完成。反之，如果条件任务集合（即任务不存在条件任务），任务能够在任意时刻被平台分配出去。为了降低问题的复杂程度，我们暂时假设每个任务执行者完成同一任务所用的时间是相同的，而是对任务的执行时间的预先估算。符号是由任务执行者提交的感兴趣完成的任务集合。如果平台最终决定将任务分配给任务执行者来完成，则任务必须存在于任务执行者提交的任务集合中。同时，每一个任务执行者在提交各自相关的任务时，对提交的任务会

22、附上个人的执行时间。如果任务执行者提出愿意完成任务，则该任务执行者对完成任务的个人执行时间是他最快完成需要的时间。任务执行者提交的所有任务的个人执行时间是对应在集合中的。第2.2节 问题描述我们将对众包模型下的任务分配问题作详尽的描述。在任务执行者提交了他们各自愿意完成的任务集合后，众包平台决定如何合理地将任务集合中的任务分配给任务执行者群体中的每一个。平台的任务分配工作以完成所有任务所需要经历的时间最小化为目标。由于任务间存在先后关系约束，同时任务执行者感兴趣的任务彼此互不相同，众包平台在进行任务分配时需要将这些限制纳入考虑，并对任务的分配情况做出一个合理的决定。用表示任务是否已经被完成。如

23、果任务是一个被完成了的任务，有；否则。我们用表示任务是否能够被分配，同时很容易得到一个关于的等式。如果任务满足约束公式，此时任务能够被分配给一个任务执行者。我们进一步用表示平台是否将任务分配给任务执行者。如果任务被分配给了任务执行者，则；否则。用于表示任务是否优先于任务被分配给一个任务执行者完成。如果，这意味着任务应当优先于任务被分配出去。如果是任务预期开始被完成的时刻（即平台最早能够将任务分配给一个任务执行者的时刻）。显然，满足如下约束公式。当所有的任务执行者提交了他们各自愿意完成的任务集合后，众包平台将决定一个合理的任务分配结果。众包系统内所有的用户完成所有的任务所经历的完整的时间，将其定

24、义为任务集合的执行时间。接着，平台以完成发布的任务集合所需要经历的时间最小化为目标进行任务分配。定义1 （提出的任务分配问题（PTAP） 我们最开始提出的、以完成发布的任务集合所需要经历的时间最小化为目标的任务分配问题，该问题的定义如下。在对提出的任务分配问题（PTAP）的符号定义中，公式的优化目标说明了这个任务分配的问题的目的在于完成发布的任务集合所需要经历的时间最小化。第一个约束公式说明了任务间存在着先后关系。如果任务优先于任务被分配出去，则有且该约束公式被转换为，这意味着当且仅当任务被完成时，任务才能够被分配出去。取最大值的目的在于确保任务的条件任务集合中的所有任务都已经被完成了。任务执

25、行者对于完成任务的个人执行时间可能与系统中的其他任务执行者存在差异，鉴于这种情形，对于符号的设定会使提出的任务分配问题更加的复杂。为了降低问题的复杂程度，我们暂时假设每个任务执行者完成同一任务所用的时间是相同的，而是完成任务需要花费的执行时间。也就是说，我们通过化简最初提出的问题，得到一个简化的任务分配问题。在解决了简化的问题后，再将被简化了的约束条件纳入问题考虑，并基于简化问题的解决方案对最初突出的问题进行算法设计。在简化的任务分配问题中，对于任意的，如果，有。接着，在简化问题的定义中，任务执行者个人完成任务需要的执行时间可以被转换为。定义2 （简化的任务分配问题（STAP） 鉴于最初被提出

26、的任务分配问题的复杂性，我们假设每个任务执行者完成同一任务所用的执行时间是相同的，同时简化的任务分配问题如下：简化的任务分配问题（STAP）的目标依旧是为了完成发布的任务集合所需要经历的时间最小化。显然，除了任务执行者各自的任务执行时间，简化的问题和最开始被提出的问题之间不存在任何变化。假设每个任务执行者完成同一任务所用的时间是相同的，则与相等，且任务分配问题的定义发生了变化。尽管STAP中的第一个约束公式的内容发生了变化，但它的目的始终是为了维持任务间先后顺序的约束条件。第2.3节 NP难特性分析接下来，我们将证明两个被提出的众包任务分配问题都是NP难问题：定理1 以完成所有发布的任务所需要

27、经历的时间最小化为优化目标的简化的任务分配问题（STAP）是一个NP难问题。证明 将STAP进一步简化，再简化的问题里任务间不存在先后关系越是，且每一个任务执行者愿意执行平台发布的所有任务（即任务的条件任务集合，同时任务执行者提交的愿意完成的任务集合）。对于这个再简化的问题，可以将其规约为一个多机调度问题。在这个再简化的问题里，平台发布的任务就相当于多机调度问题里的作业，而参与众包的任务执行者可以被看作是多机调度问题里的加工机器。在多机调度问题里，我们需要寻求一种作业调度方案，使所有的作业在尽可能短的时间内由给定的若干台机器加工处理完成，且作业不可再拆分成更小的子作业，这样的优化目标与再简化的

28、问题是一致的。众所周知，多机调度问题是一个经典的NP完全问题。由于再简化的任务分配问题能够被规约为多机调度问题，则简化的任务分配问题（STAP）也是一个NP难问题。定理1在此得以证明。定理2 以完成所有发布的任务所需要经历的时间最小化为优化目标的最开始被提出的任务分配问题（PTAP）是一个NP难问题。证明 正如在定理1中呈现的，已证明STAP是一个NP难问题，同时它能够被规约为多机调度问题。另外，由于能够在多项式时间内将PTAP规约为STAP。则PTAP能够被规约为多机调度问题，因此它是一个NP难问题。定理2得以证明。第3章 算法设计在这一章节，我们将解决之前两个模型提出的问题，并对设计的算法

29、做详尽的描述，该算法能够达成问题模型提出的目标，即完成发布的任务所需要经历的时间最小化。接下来，我们会介绍设计的任务分配算法的结构。随后对提出的算法的细节部分展开陈述。已经证明了以执行时间最小化为目标的最初提出的任务分配问题（PTAP）和简化的任务分配问题，两者都是NP难问题，且目前没有高效的算法能够用来得到这些问题的最优解。因此，我们会先针对简化的任务分配问题（STAP）设计一个能够在多项式时间内解决问题的近似算法。接着，以简化问题的解决方案为基础，解决最初提出的问题（PTAP）。第3.1节 解决STAP的近似算法论文设计的用于解决STAP的算法有如下四个部分：确定该任务层次的部分、构造最终

30、任务集合的部分、构造任务的优先分配序列的部分和任务分配的部分。在算法的第一个部分，根据该任务的条件任务集合，我可以确定该任务的层次。最终任务存在明显的特征与其它任务有所区别，这类任务不存在于任务集合中任何一个任务的条件任务集合中。我们很容易明白完成任务集合中全部任务的整体时间是由任务集合中的那些最终任务预期被完成所经历的时间来决定的。因为这样的特点，我们在算法的第二部分里构造了最终任务集合。接着，根据每一个任务预期被完成所需要经历的时间，能够确定各个任务之间的优先分配级别，将任务按增序排列可以得到分配序列。最后，依照所得的任务分配序列将任务分配给任务执行者。第3.1.1节 确定各任务层次的部分

31、我们想要通过任务层次的概念来具体反映平台发布的任务之间的优先关系。在已知的两个模型里，当且仅当条件任务集合中的所有任务被完成时，对应于条件任务集合的任务才能够被分配给任务执行者完成。因此有约定，如果任务的层次为，则 它的条件任务集合里的所有任务的层次都应当小于。用符号来表示任务的层次。显然，每一个条件任务集合的任务必然是最低层次()的任务。对于如何划分任务层次的算法，可见算法1处的算法详细过程。首先，如果将任务之间的优先关系抽象成图，很容易得到一个有向无环图。原因在于如果抽象的图是有环图，可能会遇到与下面的例子类似的情况。有三个任务，任务存在于任务的条件任务集合中，任务存在于任务的条件任务集合

32、中，而任务存在于任务的条件任务集合中。我们发现，在这样类似于“死锁”状态的例子里，这三个任务永远不可能不完成，而这样的情况与实际应用是不相符的。根据表1提供的例子，可得到任务之间的具体关系，其中任务为任务的条件任务。则在将关系抽象成图的过程中，可通过一个从任务指向任务的箭头表示它们之间的关系。通过这种方式，最终能够得到一张反映例子中各任务之间关系的有向无环图。在算法1中，我们首先将每一个任务的条件任务集合复制，对应存放于变量中。用于表示算法当前正在确认的层次的变量，在算法的初始化中有。第一部分关于区分任务层次的算法是以迭代的方式运行的。在每一次迭代中，对存放在临时的任务集合中的、还没有被区分层

33、次的所有任务，依次查看，判断任务的临时条件任务集合是否为空。如果有，则我们确定任务的层次为（有）。当中所有的任务都被查看过后，将删除存在于其它条件任务集合中的、层次为的任务，并将临时的条件任务集合中所有层次为的任务删除。在本次迭代结尾处，对变量赋值。接着开始下一轮的迭代，在临时的任务集合时，迭代停止，算法结束。算法1 区分任务层次输入： 发布的任务集合输出： 1：设置变量；2：for 任务集合中的每一个任务 do3： 设置变量；4：设置变量；5：while do6： for 中的每一个任务 do7： if then8： 变量赋值；9： for 中的每一个任务 do10： for 中的每一个任务

34、 do11： if then12： 将任务从集合中删除；13： if then14： 将任务从集合中删除；15： ；16：return ；为了更清晰的展示提出的算法，我们将在本章节给出一个例子。例子中有一个任务发布者发布的任务集合。同时能够知道表1中反映的任务间的先后关系。表0.1 任务集合中关于任务的细节任务条件任务集合任务执行时间342572根据算法1，我们可以计算得到表1中每一个任务的层次。表0.2 由算法1计算得到的任务集合中各个任务的层次任务任务层次111223确定任务层次的过程能够使我们对任务之间具体的关系有更为清晰的了解。同时在设计构造任务的优先分配序列的部分中，我们将会发现这一

35、部分的作用和必要性。第3.1.2节 构造最终任务集合的部分定义3 我们给出定义，不存在于任何其它一个任务的条件任务集合的任务为最终任务。发布的任务集合中至少存在一个最终任务。如果是一个最终任务，则他满足条件，对于任意的，有。完成所有发布的任务经历的时间是由那些最终任务预期被完成所经历的时间来决定的，因此在对任务的优先级别进行排序之前，需要构建一个最终任务集合。根据最终任务具备的特征，先假设任务集合中的每一个任务都是最终任务。接着在对每一个任务就针对假设作验证。如果当前被验证的任务存在于其它的某个任务的条件任务集合，那么需要修正之前的假设。如果该任务不存在于任何其它任务的条件任务集合，这表明假设

36、是正确的，且该任务是一个最终任务。算法1的具体过程如下。算法2 构建最终任务集合输入： 任务集合输出： 最终任务集合1：变量赋值；2：for 中的每一个任务 do3： for 中的每一个任务 do4： for 中的每一个任务 do5： if then6： 将任务从最终任务集合中删去；7：return 最终任务集合；我们继续使用3.2.1中给出的例子，按照算法2给出的计算过程，可以算出构建成的最终任务集合。因为例子中没有条件任务集合存在任务和。最终任务具备的特点让我们知道，如果任务集合中的最终任务都被完成了，那么任务集合中所有的那些不是最终任务的任务也都已经被完成了。换句话说，如果任务集合中所有

37、的最终任务都已经被完成，那么这个任务集合里的所有任务就都被完成了。第3.1.3节 构造任务的优先分配序列的部分算法的优化目标与被完成需要经历的预期时间最大的最终任务相关联。因此需要先得到所有最终任务各自能够被分配给任务执行者需要经历的预期的时间。为了达成问题的目标，我们将根据任务预期的被分配出去的时间对任务进行优先顺序排序，并生成一个任务分配的优先序列。接下来，我们会先给出一些与算法相关的必要定义。定义4 任务序列：一个任务序列是由一组任务构成的，序列中第个任务必须存在于第个任务的条件任务集合中，同时这个任务序列的最后一个任务必然是一个最终任务。在一个任务序列中任务只能一个接着一个地被执行，因

38、此完成这个任务序列里所有任务需要经历的预期的时间与这个序列里的最终任务被完成需要经历的预期的时间是相等的。定义5 关键任务序列：任务关键序列是发布的任务集合中，完成这个任务序列里所有任务需要经历的预期的时间最大的任务序列。论文提出的关于构造优先分配序列的算法是以迭代的方式运行的。在每一次迭代过程中，首先找到任务集合的关键任务序列，接着将处在任务关键序列中的层次最低的任务取出并放入目标任务优先分配序列。算法3的具体过程如下。用符号表示任务在算法运行得到的任务分配序列中的次序。在每一次迭代的过程中，需要找到一个任务序列，该序列的值比任何其它的任务序列的值都大。其中，一个任务序列的值与在该序列中的最

39、终任务被完成需要经历的预期的时间是一致的。为了得到所有最终任务被完成各自需要经历的预期的时间，先计算存在于最终任务的条件任务集合中的任务，得到它们被完成各自所需要经历的预期的时间。因此，在算法3中，最开始的步骤就是计算任务集合中每一个任务被完成所需要经历的预期的时间。用符号表示任务被完成所需要经历的预期的时间。显然，当时，有；而当时，有。注意到，算法是按低层次往高层次的顺序依次计算各个任务被完成所需要经历的预期的时间的，同时条件任务集合中任务的层次必然都小于任务。因此,在计算时,中的值都已经被计算得到了。为辅助构造关键任务序列的过程，用符号任务集合中被完成需要经历的预期时间最大的任务。在计算完

40、所有最终任务被完成各自需要经历的预期的时间后，能够找到其中被完成需要经历的预期时间最大的最终任务，并根据被记录的构造关于任务的关键任务序列。用符号来表示关于任务的关键任务序列中层次最低的任务。接着，将任务放入目标的任务优先分配序列中，有。之后，将任务从任务集合以及所有其它任务的条件任务集合中删除。如果任务是一个最终任务，还需要将它从最终任务集合中删除。最后，算法进入下一轮的迭代，直到任务集合为空时算法才会结束。算法3 构造任务的优先分配序列输入： 任务集合，最终任务集合输出： 任务的优先分配序列 1：变量赋值； 2：while do 3： for 从1至 do 4： for 中的每一个任务 d

41、o 5： if then 6： 计算任务被完成需要经历的预期时间，并用符号表示； 7： 任务集合中被完成需要经历的预期时间最大的任务用符号表示； 8： 找到最终任务集合中被完成需要经历的预期时间最大的最终任务； 9： 构造关于最终任务的关键任务序列；10： 找到在关于任务的关键序列中层次最低的任务；11： 变量赋值；12： 将任务从任务集合以及所有其它任务的条件任务集合中删除；13： if then14： 将任务从最终任务集合中删去；15： 变量赋值；在给出的例子中可以看到任务执行者在对应的任务上标注了时间，任务执行者在接到任务后需要花费相应地时间去完成该任务。根据算法3的计算流程，当任务还没

42、有分配出去时，我们能够看到每一个任务集合中的任务对应的值。表0.3 任务集合中各任务被完成所需要经历的预期的时间任务任务被完成预期的时间34281110接着，会找到由任务，组成的关键任务序列。任务是得到的关键任务序列中层次最低的任务。于是，将任务从任务集合中移出，将其加入到目标的优先分配序列中，并更新发生了改变的任务集合中各个任务被完成所需要经历的预期的时间。接着，重复这样的过程直到任务集合中没有需要确认优先级别的任务。最后能够得到一个按照优先级别排序的分配序列。例子的运行结果如下，优先分配序列为。第3.1.4节 任务分配的部分在构造了任务优先分配序列后，平台将任务分配给任务执行者。依照算法3

43、的描述，平台在每一次迭代中都会选择一个任务，使剩余所有的任务被完成所需要经历的时间较选择前有最大幅度的减少，并将这个任务加入到目标的优先分配序列。因此，如果平台根据构建的优先分配序列将任务依次分配各任务执行者，任务集合被完成需要经历的预期的时间将会最小化。我们设计的任务分配部分的算法包括了四个步骤，具体描述如下：步骤1：根据优先分配序列对任务集合中的任务排序。步骤2：根据每个任务执行者提交的任务集合的大小，按递增顺序对任务执行者集合中的任务执行者排序。步骤3：依次查看排好序的任务集合中的任务。当任务被查看时，平台依次查看排好序的任务执行者集合中的任务执行者直到找到愿意执行任务的那一个。当查看任

44、务执行者时，平台检查他是否满足条件。如果，那么平台将任务分配给任务执行者，同时将任务和任务执行者从对应的集合和中删去。对于有任务不能被分配或者任务执行者接不到任务的情况，那些分别留在了集合和的所有任务和任务执行者都需要等待新的任务执行者参与其中或者那些被分配出去了的任务被完成了，这些变化能使平台中任务和任务执行者的状态发生新的改变。步骤4：当一个被分配出去了的任务被完成时（以任务执行者完成了任务为例），平台首先会将任务执行者放回到有序的任务执行者集合中，接着重复步骤3的流程，检查是否有能够开始被分配的任务并继续将任务分配给任务执行者，这样的重复直到时才会结束。根据在这一章节给出的例子，我们继续

45、给出问题相关的设定，参与众包的任务执行者有三位，他们各自申请的任务如下。表0.4 任务执行者集合中的细节任务执行者提交的任务集合342依照上述各步骤的过程，我们能够得到一个分配任务给任务执行者的序列。表0.5 提出的算法在给出的例子下生成的结果任务任务执行者被完成经历的时间4329911第3.2节 解决PTAP的近似算法用来解决PPTP的算法分为三个部分：对任务实际被执行需要的时间的预估部分、构造任务的优先分配序列的部分和任务分配的部分。在每一个任务执行者提交的任务集合里，能够知道每一个任务执行者对所有他提交的任务给出的执行时间。为了得到任务集合中各个任务的预估执行时间，在算法的第一部分，我们

46、需要对任务的执行时间找到一个合理的预估方式。在算法的第二部分中完成了任务的层次划分以及最终任务集合构建之后，基于任务被完成需要经历的预期的时间能够对任务按增序完成排序。最后，根据在第三部分中构建的优先分配序列将任务分配给任务执行者。第3.2.1节 对任务执行时间的预估部分事实上，任务执行者对于任务需要的执行时间很可能与其他任务执行者对任务需要的执行时间是不同的，但由于最初提出的问题的复杂性，我们的想法是先解决一个简化了的问题，再基于简化的问题的解决方案对原问题进行求解。问题的基本解决思路就是对发布的任务排序构成一个优先分配的序列，接着将任务分配给任务执行者。在构造优先分配序列的阶段，确定每一个

47、任务执行时间的预估值既会对目标的优先分配序列产生很大的影响，也会影响算法最终的运行结果的误差。因此，为任务的执行时间找到一个合理预估方法对解决整个问题来说极为重要。用符号表示对任务的执行时间的预估，的值为所有愿意完成任务的任务执行者各自提交的执行时间中的最小值。即第3.2.2节 构造优先分配序列的部分在得到各个任务的预估执行时间后，首先根据每个任务的条件任务集合利用算法1确定每个任务的层次。由于完成任务集合中全部任务的整体时间是任务集合中的那些最终任务被完成所经历的时间决定的，利用算法2能够构建最终任务集合。之后，利用算法3根据任务被完成需要经历的预期时间对任务进行排序，构建一个优先分配序列。

48、第3.2.3节 任务分配的部分在构造了任务优先分配序列后，平台依旧根据构成的优先分配序列将任务分配给任务执行者。另外，任务应该被分配给所有愿意完成该任务的任务执行者中需要的任务执行时间最小的那个。我们设计的任务分配部分的算法包括了四个步骤，具体描述如下：步骤1：根据优先分配序列对任务集合中的任务排序。步骤2：根据每个任务执行者提交的任务集合的大小，按递增顺序对任务执行者集合中的任务执行者进行排序。步骤3：依次查看排好序的任务集合中的任务。当任务被查看时，平台依次查看排好序的任务执行者集合中找到那些愿意执行任务的任务执行者。找到任务执行者中需要的任务执行时间最小的那个，并判断是否满足条件。如果，

49、那么平台将任务分配给任务执行者，同时将任务和任务执行者从对应的集合和中删去。对于有任务不能被分配或者任务执行者接不到任务的情况，那些分别留在了和的所有任务和任务执行者都需要等待新的任务执行者参与其中或者那些被分配出去了的任务被完成了的情况，这些变化能使平台中任务和任务执行者的状态发生新的改变。步骤4：当一个被分配出去了的任务被完成时（以任务执行者完成了任务为例），平台首先会将任务执行者 放回到有序的任务执行者集合中，接着重复步骤3的流程，检查是否有能够开始被分配的任务并继续将任务分配给任务执行者，这样的重复直到时才会结束。第4章 仿真模拟在本章节，我们将先介绍仿真模拟过程中所有参数的设置，接着

50、进行大量相关的实验对提出的算法的性能作评价。第4.1节 仿真环境参数设置定义6 变量表示在一个任务分配算法运行下完成任务集合中所有任务所需要经历的时间，而表示对于任务集合中的所有任务完成它们所需要经历的理论上最优的时间。接着，有近似最优比率：仿真模拟的环境设定如下。为了反映提出算法的性能，尤其是与近似最优比相关的算法的性能。我们通过变化发布的任务数目、参与众包的任务执行者的数目以及任务集合的层次对应的符号的值进行评估。更确切地说，以及。各个层次的任务总数均匀地在范围内随机分布。对于任务集合中的每一个任务，存在属性：任务实际被执行需要的预估时间、任务的条件任务集合，同时条件任务集合的大小在范围内

51、随机分布。在图4.1、4.2、4.4中，用于表示每个任务被执行的预估时间的变量在内均匀地随机。而在图4.3的仿真模拟中，变量在呈的正态分布环境下随机产生。每个任务执行者会提交一个任务集合，由所有他（她）感兴趣执行的任务组成，不同实验中，该任务集合的大小在或范围内的均匀分布环境下随机产生。在确定了后的每一个实验中，我们会生成2000个样例运算，并对这些样例的算法结果求均值。最终，求得的均值是在确定了后实验的最终结果。第4.2节 仿真模拟结果(1) 系统中任务参与者的数目对近似最优比率的影响图4.1 , 近似最优比与不同的作比较首先将平台发布的任务数目确定为200，在此情形下，通过在范围内变化参与

52、其中的任务执行者的数目对算法性能作评价。任务集合的层数被设定为6。算法对这些设定构成的实验样例进行计算，在得这些实验的结果后我们将结果反映在了折线图4.1上。显然，在参与中报的任务执行者数目增多的情形下，评价算法性能的指标-最优近似比率的值会有所降低。由于对于任务集合中的所有任务，完成它们所需要经历的理论上最优的时间与且仅与任务集合 的大小和结构相关，因此无论参与其中的任务执行者如何变化，理论最优时间都不会发生变化。但对于任务分配算法运行下完成任务集合中所有任务所需要经历的时间来说，当参与众包的任务执行者数目增大时，任务一旦能够被分配，他们会有更大的可能性被马上分配出去，这使得算法得到的完成任

53、务集合中所有任务所需要经历的时间有所减少，接着有评价算法性能的指标-最优近似比率的值有所降低。因此，最优近似比率的值会随着参与众包的任务执行者数目的增大而减少。我们还将任务集合的大小设置为了300，对该设定进行仿真实验并将结果反映在了折线图4.1上。情形下的算法结果与情形下一致。(2) 系统中被发布的任务集合的层数对近似最优比率的影响图4.2 , 近似最优比与不同的作比较我们又通过变化任务集合的层数，以仿真实验下的算法结果来反映两者之间的关系。将平台发布的任务数目依次确定为200和300，同时将参与众包的任务执行者的数目设定为80，在此情形下，通过在范围内变化任务集合的层数对算法性能将作评价。

54、对这样的设定产生的样例进行算法求解，并将结果反映在了折线图4.2上。显然，最优近似比率的值会随着任务集合层数的增大而减少。这是因为平台发布的任务固定了，而任务集合的层数有所增加会使得每一层里的任务数目相对减少，同一层次的任务之间的竞争关系缓和，每个任务在能够开始被分配时都存在更大的几率立刻被分配给任务执行者，这使得任务分配算法运行下完成任务集合中所有任务所需要经历的时间更加接近于任务集合中的所有任务完成它们所需要经历的理论上最优的时间。总之，最优近似比率的值确实会随着任务集合层数的增大而减少。(3) 任务的预估执行时间的随机分布方式对近似最优比率的影响图4.3 , , 近似最优比与不同的作比较

55、图4.3中，我们通过在范围内变化参与其中的任务执行者的数目对算法性能将作评价，每一个样例中平台发布的任务数目始终维持在200。任务集合的层数被设定为6。各个任务执行者提交的任务集合的大小在范围内均匀地随机生成。每一个任务的条件任务集合的大小以两种不同的随机方式生成，算法运行两种环境下的样例，我们对得到的近似最优比率进行观察比较。由于当任务被执行的预估时间的变量在内均匀地随机时，任务集合中的所有任务完成它们所需要经历的理论上最优的时间往往大于另一种随机方式下的结果。又因为无论任务被执行的预估时间以什么样的方式随机生成，算法计算的时间与理论最优的时间之间的差距是有限的。所以能够发现任务被执行的预估

56、时间在内均匀地随机时，样例对应的近似最优比率会相对小一些。这与图4.3中的结果是一致的。(4) 任务执行者提交的任务集合的大小对近似最优比率的影响图4.4 , , 近似最优比与不同的作比较图4.4的仿真实验中，将平台发布的任务数目确定为200，在此情形下，我们通过在范围内变化参与其中的任务执行者的数目对算法性能将进行评价。任务集合的层数被设为6。每个任务的条件任务集合的大小在一个呈高斯分布的环境下随机生成。在每一个任务执行者提交的任务集合的大小在或范围内均匀地随机生成的情形下，将对应的近似最优比率进行比较。在对图4.1(a)进行过分析后，我们很容易得到这样的结论，在任务执行者提交的任务集合的大小在范围内均匀地随机生成的情形下，对应的近似最优比率会比的随机环境小一些。最终，实验的结果与设想的确是一致的。(5) 相同参数设置的环境下，STAP与PTAP结果的比较将实验结果画进折线图的过程中，在同样的参数设置生成的环境下，我们将STAP和PTAP的结果用同色的实现和虚线进行区分。由于STAP中并未考虑任务执行者对同一任务需要执行的时间可能会不同这样的条件限制，因此任意任务执行者完成任务的时间始终为，而在PTA