本站动态
联系我们
QQ：3949358033
工作时间：9:00-24:00
| 基于约束的空间众包多阶段任务分配 |
| 来源：一起赢论文网 日期：2020-04-22 浏览数：1613 【 字体： 大 中 小 大 中 小 大 中 小 】 |
|
2 multi-tasking scenario, each simple task is basically independent. A single worker may undertake one or more
tasks, and the execution of a single simple task does not have to be split and assigned to multiple workers.
However, in constrained spatial crowdsourcing, a single worker may not be able to complete the entire task.
Constrained spatial crowdsourcing involves location and service authorization, worker available time and worker
movement range. Instead, a task in constrained spatial crowdsourcing requires a group of workers to complete the
task collaboratively. In response to this demand, we propose a multi-stage task allocation method on constrained
spatial crowdsourcing in this paper. The core algorithm of the method will first obtain the path set corresponding
to the task according to two different optimization objectives including the minimum execution time and the
minimum movement range, and then sort them according to the priority. For each path in the set, the algorithm
will recursively select the workers to undertake the phased tasks by means of adopting a method from which the
local optimal results are obtained in both directions from the starting point and from the ending point. Once the
tasks on the path can be collaboratively completed by one or a group of workers, an allocation decision for the
phased task is obtained. Through the above steps, the method efficiently breaks down the task into a set of
sub-tasks that can be undertaken by different workers when the constraints are met, thereby increasing the
probability of completion of the task. Finally, a simulation experiment and a field experiment were carried out
based on the above algorithm. In the simulation experiment, we compare our algorithm with a dynamic
programming algorithm which can obtain the global optimal solution based on the same randomly generated data
set. The data set includes the workers’ restricted location and service authorization status, movement range and
current position coordinate. The experimental results show that our algorithm has better computational efficiency
than the comparison algorithm. The field experiment is performed utilizing a self-developed campus spatial
crowdsourcing task platform. The experimental results show that our algorithm can derive sub-task allocation
decisions that the workers can accept in real spatial crowdsourcing environment.
Key words spatial crowdsourcing; task allocation; multi stage; spatial-temporal constraint; spatial topology
1 引言
人机物融合的智能技术是发展新经济的关键
技术之一[1]。在此背景下，人类社会中个体或群体
的智慧与劳动力能够参与人机物系统的运行，而众
包（Crowdsourcing）[2]则是将这些不同个体或群体
的能力进行组合的一种软件服务[3]。在概念方面，
众包指以公开召集的方式将传统上由指定人员执
行的任务外包给未预先指定的且通常具有庞大人
员基数的群组的行为。利用众包机制，任务的执行
能够充分依赖群体智慧[4]，获得更为广泛的知识来
源，从而提高任务完成的效率与质量，并为人机物
系统提供了融合人类社会群体协作的途径。此外，
互联网的发展催生出了一系列基于 Web 的在线众
包平台，例如 Amazon Mechanical Turk，o Desk 等。
任务请求者（requester）可在众包平台上发布众包
任务，已注册于平台的参与者（worker）能够选择
并承担选定的任务。从 2009 年开始，众包得到了
各个领域的关注[5]，在诸如自然语言理解[6]、图片
标注[7]、软件测试[8]等领域得到广泛应用。
除此以外，还有许多众包任务与物理世界的地
理位置与时间要素相关，例如获取道路的实时路况
信息，拍摄建筑物的各角度照片等。针对这些类型
任务的众包被称为空间众包（Spatial Crowdsourcing）
[9]，它要求参与者真实地移动至指定的位置执行相
应的操作，承担数据收集与感知等任务，并通过移
动终端反馈操作结果。空间众包可被视为人机物融
合场景下的一种新型软件服务。与传统众包相同，
空间众包也面临着任务分配、质量管理、用户激励、
隐私保护等一系列挑战[10]。其中，任务分配的目
的是在满足特定限制条件的前提下从候选参与者
中选择合适的一个或一组参与者来承担任务的执
行[11]。在此背景下，许多研究者提出了各种方法
来计算空间众包任务的最优的参与者分配方案[12]。
这些方法基于不同的策略解决分配的最优化问题。
计算机学报———
本课题得到国家重点研发计划“人机物融合的云计算架构与平台”(2018YFB1004800)资助.范泽军，男，1994年生，硕士研究生，主要研究领域为人
机物融合、移动云计算软件系统、边缘计算，Email:16212010007@fudan.edu.cn. 沈立炜（通信作者），男，1982年生，博士，副教授，CCF会员（66586M），
主要研究领域为人机物融合、移动应用开发与分析.Email:shenliwei@fudan.edu.cn. 彭鑫，男，1979年生，博士，教授，CCF会员，主要研究领域为移
动计算与云计算、代码大数据、智能化软件开发.Email:pengxin@fudan.edu.cn. 赵文耘，男，1964年生，硕士，教授，CCF会员，主要研究领域为软
件工程、软件开发工具及其环境、企业应用集成.Email:wyzhao@fudan.edu.cn.
基于约束的空间众包多阶段任务分配
范泽军1
) ,2)
沈立炜1
),2)
彭鑫1
),2)
赵文耘1
),2)
1)
(复旦大学 计算机科学技术学院, 上海 200433)
2)
(复旦大学 上海市数据科学重点实验室, 上海 200433)
摘 要 在人机物融合的背景下，空间众包可被视为一种新型的软件服务。空间众包针对于物理世界中与地理位置和时间
要素相关的众包任务，通常要求参与者真实地移动到指定位置执行相应操作，承担数据收集与感知等任务，并通过移动终端
反馈操作结果。任务分配是空间众包中的关键技术，其目的是在满足时空约束条件的前提下选取一个或一组合适的参与者承
担任务的执行。在具有空间位置访问权限、线下服务使用权限并考虑参与者可用时间与移动范围约束的空间众包场景中，单
个参与者可能无法完成整个任务的执行，转而需要一组参与者进行协同合作后才能完成。针对该需求，本文提出了一种基于
约束的空间众包多阶段任务分配方法。该方法的核心算法将首先根据两种不同的优化目标获取对应的任务路径集合，然后针
对每一条路径采用从起点和终点双向选取局部最优的方法递归地选择承担阶段性任务的参与者。通过上述步骤，可高效地将
任务分解为一组由不同参与者在符合约束条件时能够承担的阶段性子任务，以此提高任务完成的概率。最后，使用上述算法
分别进行了模拟实验和真实实验。模拟实验面向随机生成的参与者数据集，并与基于动态规划取得全局最优解的算法进行对
比。实验结果表明本文所提算法相比于对比算法具有更好的计算效率。真实实验依赖自主开发的校园空间众包任务平台开展。
实验结果表明本文算法能够在真实任务环境下推导得到参与者可接受的子任务分配决策。
关键词 空间众包；任务分配；多阶段；时空约束；空间拓扑
中图法分类号 TP311
Multi Stage Task Allocation on Constrained Spatial Crowdsourcing
FAN Ze-Jun1
)2)
SHEN Li-Wei1
)2)
PENG Xin1
)2)
ZHAO Wen-Yun1
)2)
1)
(School of Computer Science, Fudan University, Shanghai 200433)
2)
(Shanghai Key Laboratory of Data Science, Fudan University, Shanghai 200433)
Abstract In the context of the fusion of the ternary human-machine-thing, spatial crowdsourcing is regarded as
a new type of software service. Spatial crowdsourcing works for crowdsourcing tasks which are related to the
geographic and temporal elements in the physical world. The involved workers are usually required to move to
the specified location to perform the corresponding operations, to undertake tasks such as data collection and
perception, and to feedback the operation results through the mobile terminal. Task allocation has been a key
technique in the field of spatial crowdsourcing. It aims to select one or a group of suitable workers to undertake
the execution of the task while satisfying the constraints of time and space. The existing spatial crowdsourcing
research work mostly works for simple tasks, which can usually be undertaken by one worker alone. Even in a
计算机学报 4
的影响。在物品速递业务中，众包参与者可浏览当
前任务，报名参与任务，同时提交自己在该城市中
的活动意愿与可用时间范围。通过计算，参与者可
被指派承担不同路线阶段的任务，相比传统的方式，
在以下几个方面提高众包任务的完成效率与质量。
（1）针对参与者由于权限问题无法进入某单
位完成众包任务的情况，平台可以邀请该单位内的
相关人员承接该任务的最后一段，通过在单位门口
进行交接的方式完成整体任务。
（2）平台按照参与者在任务报名时提交的活
动意愿，给参与者分配相应任务阶段，而并不要求
参与者完成整个任务。如对于平时在东城区活动的
参与者，只需要执行任务在东城区的部分，将物品
传递至两区交界处，再由另一个负责西城区的参与
者接力完成剩余的部分。
（3）平台按照参与者在任务报名时提交的可
用时间范围，给参与者分配最合适的任务。如某参
与者白天正常上班，晚上 8 点到 11 点是他的可用
时间范围，那么平台只会给他分配涉及时间段在晚
上 8 点到 11 点之间的任务。
2.2 动机案例二
假设众包任务发生在某单位中。图 1(a)表示了
该单位的涵盖位置与服务信息的拓扑结构。其中矩
形节点表示空间位置，代表空间内的房间等建筑单
元，其解释见图 1(b)。结点之间的连线表示位置之
间的通道，连线上的标记表示从一个位置到另一个
位置的距离以及估算的移动时间。圆角矩形表示单
位提供的线下服务，其解释见图 1(b)。这些服务位
于特定的位置（位于矩形框内），括号内的分钟数
表示该服务的预估执行时间。另一方面，某些空间
位置与线下服务具有访问权限与使用权限，我们使
用矩形与圆角矩形左上方的锁图标表示这类权限。
图 1 示例场景
Bob、Charlie 与 David 是愿意接受众包任务的
三位参与者。他们在众包平台上指定了当天的可用
时间（图中人形图标下方的时间区间，例如 Bob 在
13:00 至 14:30 内愿意承担任务），以及当天愿意移
动的范围（图 1(b)表格中灰色底色标记的位置范围，
例如 Bob 可接受前往 A、B、C、D 的任务）。另
外，图 1(b)表格中的钥匙图标表示参与者能够访问
相应的位置或者使用相应的服务。例如，Charlie 具
有进入位置 C（会议室）、D（打印室），以及使
用 SD（文件打印）等权限或能力。
Alice 是该单位某项目负责人，由于出差原因无
法亲自执行某工作流程，因此她在众包平台上发布
任务：“我需要找人代替我从收发室领取一个装有
合同文档的 U 盘，并前往文件打印室进行打印，然
后在财务处进行文件盖章后送至我的办公室”。
当任务发布时，Bob、Charlie 与 David 分别处
于位置 A、D、E 附近。由于位置与服务存在着各
类权限要求，三位参与者针对这些权限的授权情况
各不相同，同时参与者自身具有可用时间与移动范
围的约束，因此无法找到一个单独的参与者完成所
有的任务操作。
本文所提出的任务分配方法面对上述问题，基
于位置服务拓扑，在考虑参与者的授权情况以及个
人约束的前提下按照特定的优化目标将任务分解
为多个阶段的子任务，并将其分派给指定的参与者。
在该过程中，申请者发布的任务描述首先被映
射成一组操作序列：（1）前往 A 使用 SA；（2）
前往 D 使用 SD；（3）前往 G 使用 SG；（4）前
往 I。
随后众包平台的任务分配算法可按照两类分
配优化目标中的一个推导子任务分配方案。第一类
优化目标是“用时最少”，即尽量减少参与者整体完
成任务的总体耗时。该类优化目标适用于时间敏感
类型任务的分配，即众包任务对总体执行时间有要
求。典型场景包括：（1）发布者在任务描述中规
定了任务的完成时间；（2）任务涉及的空间位置
或线下服务在任务发布后可能变为不可达或关闭
状态（此类场景要求在尽量短的时间内进行服务调
用）。第二类优化目标是“移动距离最短”，即尽量
缩短参与者协作完成任务的移动总距离。该类优化
目标适用于非时间敏感，但希望降低总体空间移动
距离的任务。典型场景包括：任务涉及的物品具有
特殊性，例如易碎、易融化、具有较大体积或重量
等。图 2 展示了基于两类优化目标得到的子任务分
配方案。
计算机学报 5
图 2 示例任务的多阶段分配方案
基于用时最少的优化目标，众包平台尝试将
Alice 提交的任务进行分解，得到图 2(a)所示方案。
第一阶段由处于 A 处附近的 Bob 承担，建议其于
14:10 之前达到 A（收发室），在领取物品后通过 B
（休息室）送往 D（打印室）。由于 Bob 不具备文
件打印相关的权限，因此平台将第二阶段的子任务
委托给处于 D 处附近的 Charlie，并要求 Charlie 在
14:28 之前到达打印室交接物品并进行 SD 服务（文
件打印）的操作。由于 Charlie 不愿意前往 F（归档
处），因此平台将安排 Charlie 将打印好的文件及 U
盘通过 B 送至 E（公共办公区）并将物品移交给处
于 E 处附近的 David。David 承担第三阶段的子任
务，他被指示在 15:10 前到达 E 进行交接，随后通
过 F（归档处）前往 G（财务处），并使用 SG 服
务（文件盖章），最后将物品送至最终的目的地 I
（办公室）。在该方案中，算法选取了耗时最短的
路径，同时考虑了三位参与者的权限、可用时间与
移动范围。计算得到的子任务向参与者指派了移动
路径，以及开始承担任务的建议时间。
类似地，以移动距离最短为优化目标，得到图
2(b)的子任务分配方案。与(a)方案相比，在进行任
务分配时选取距离最短的路径，随后根据权限与参
与者约束得到三阶段的子任务。其中，对于 Bob 而
言，要求他通过 C（会议室）前往 D（打印室）；
对于 Charlie 而言，不要求他通过 F（归档处）。
3 基于约束空间众包的定义
本章首先给出了基于约束空间众包的概念及
其基本流程，随后对流程中涉及的要素进行定义。
3.1 基于约束空间众包的概念
文献[14]对空间众包的关键技术，尤其是任务
分配进行了综述，其中提出了一个空间众包的概念
模型，通过任务、参与者与服务器这三类要素来描
绘众包的体系。基于该模型，图 3 展示了本文所提
出的空间众包的概念及其定位。
图 3 多阶段空间众包的属性
我们将基于约束空间众包的任务类型定义为
紧急任务、定点任务与静态任务。紧急表示任务需
要由参与者在受限的时间期限内尽快完成；定点表
示任务的执行与特定的位置点相关，即使用线下服
务或递送物品均需精确到一个具体的位置；静态表
示与任务相关的位置信息不会随着时间发生变化。
其次，任务的时空特性描述了发布任务在时间与空
间维度的约束，我们将其定义为固定的空间位置与
指定的时间约束。前者表示与任务相关的位置以及
服务信息由空间拓扑预先决定；后者则表示任务的
完成时间期限。最后，基于约束的空间众包需要由
一组参与者通过群体协作的方式实现最终的目标。
参与者的时空特性是任务分配必须考虑的因
素。对于一个参与者而言，他可指定可用的时间，
即在该时间范围内可被分派任务。另外，参与者的
实时位置也能通过各种手段获取。其次，参与者的
技能对任务分配也产生影响。在基于约束的空间众
包中，我们将参与者的技能等价于访问特定位置的
权限，以及使用特定线下服务的权限。最后，参与
者可指定其移动范围的约束，即不能接受前往超过
该范围位置点的任务。参与者的可用时间与移动范
围被认为是影响任务分配的重要约束。
在空间众包中，服务器负责数据的存储、处理
与任务的分配。我们重点定义其中的任务分配。本
文定义了两类优化目标来推理最优的参与者任务
分配方案，分别是完成时间最少和移动距离最短。
本文方法主要针对单任务的分配，并未考虑多任务
存在时的分配策略。在分配过程中，我们（1）采
用离线分配的方式，即在任务真实执行前决定分配
方案；（2）使用服务器分配任务[11]的方式，即在
知晓所有参与者当前位置的情况下由服务器自动
推理分配方案；（3）假设用户在接受任务之后能
够主动地向目标位置移动，而不是借由其他的原因
移动到目标位置时顺带着完成任务。
当前，本文所述的空间众包暂未考虑参与者激
励、信任、隐私保护等方面的因素。
计算机学报 3
典型的策略包括最大化完成任务的质量[13]，以及
最小化系统成本与开销[14][15]。从任务分配的结果
来看，已有的空间众包研究工作大多针对包括单个
操作目标的简单任务，例如道路实时路况的获取。
这些简单任务一般都能够由一位参与者单独承担。
即使在多任务的场景下，每一项任务也基本独立，
一个参与者可能承担其中的一项或者多项任务[16]，
但对于单项任务而言，其执行过程无须拆分并分配
给多个参与者。
现实场景中存在另一类任务。相比于简单任务，
这类任务包括一组与位置和线下服务相关的有序
操作。其中，（1）位置是能够被人访问的现实世
界中的地点，例如图书馆、体育馆等。各个位置间
的通道形成了一张网络。在空间众包中，对位置的
访问要求参与者真实移动到指定地点执行指定的
操作，例如将物品递送到目标地点或者前往目标地
点获取某些服务。（2）线下服务位于特定的位置，
参与者需到达该位置才能使用服务，且服务的执行
需要花费一定的时间。例如，图书馆的借阅服务或
设备的登记服务。
另外，这类空间众包任务在分配过程中需要考
虑两个方面的约束。（1）位置的访问权限与服务
的使用权限。空间中某些位置具有访问权限，即只
有经过授权的人员才能进入该位置所代表的空间。
某些服务具有使用权限，即具备使用授权或能力的
人员才被允许使用。例如，扫描仪仅能被具有权限
的人员使用。（2）参与者的可用时间与移动范围
的约束。这两个约束是参与者所指定的愿意执行任
务的时间区间与空间活动范围。在分配过程中，时
间区间之外的，或超过移动范围的任务不应分配给
该参与者。
我们将具有以上所述特点的空间众包称为基
于约束的空间众包。这种类型的众包任务可能无法
由单个参与者单独承担，因此有些情况下需要将其
拆分为多个具有依赖关联的阶段子任务并由一组
参与者协同完成。
传统的空间众包分配方法无法有效应对这种
新类型的众包任务。针对该挑战，本文对基于约束
的空间众包的任务分配展开研究，提出了一种多阶
段任务分配方法。该方法可高效地将任务分解为一
组由不同参与者在符合约束条件时能够承担的阶
段性子任务，以此提高任务完成的概率。在分配过
程中，本方法的核心算法根据任务执行的总用时最
少与移动距离最短这两个优化目标推导分配方案。
我们使用该算法进行了实验，实验结果表明本方法
具有较高的计算效率，并且在真实任务环境下能推
导得到参与者可接受的子任务分配决策。
本文的剩余章节结构如下：第二章通过两个动
机案例展现本文所提方法的使用场景及效果；第三
章定义了基于约束的空间众包任务分配的概念、流
程与组成要素；第四章具体描述考虑时空约束的空
间众包多阶段任务分配算法；第五章介绍实验设计
并对实验结果与方法进行讨论；第六章列举了相关
工作；最后是本文的总结与对未来工作的展望。
2 动机案例
本章通过两个动机案例对基于约束的空间众
包多阶段任务分配进行解释。动机案例一面向真实
应用场景，探讨多阶段任务分配的应用价值与效果；
动机案例二针对在模拟空间内的任务执行需求，解
释多阶段任务分配的工作方式与执行结果。
2.1 动机案例一
同城配送（如达达、蜂鸟众包、人人快递、飞
毛腿等）提高了同一城市内物品递送的效率。它采
用众包的方式，主要流程包括：任务发布者在平台
发布需求，通常为物品派送类任务；任务参与者在
平台上接受任务；任务参与者到达指定起点获取物
品，送至指定终点。同城配送是一种典型的众包模
式，其任务参与者不一定是专业的快递员，普通民
众也可参与寄送任务的执行。
在众包任务的执行过程中，众包参与者由于特
定的约束条件，无法按照平台既定的路线完成端到
端的派送任务。影响参与者执行任务的主要限制条
件包括：（1）参与者未拥有某些特定地点的准入
权限，如学校、企业、政府机构等大部分单位的大
门需要相应的权限才能进入。若参与者不能进入某
个单位，则必须花费额外工作量与时间等待客户提
取。如果客户不在，则可能当天无法寄送。（2）
参与者需要前往远离自己平时活动范围的地方执
行任务，如参与者平时在东城区活动，若承接的众
包任务需要前往西城区执行，会出现路线不熟悉等
情况，影响众包任务的完成效率。（3）若众包任
务分配不得当，参与者在执行任务的时间段可能有
其他重要事项，则会出现参与者工作积极性与工作
效率降低的情况，影响众包任务的完成质量。
针对这种场景，若采用多阶段任务分配，允许
多名参与者协作完成任务，则可降低上述约束带来
计算机学报 6
3.2 基于约束空间众包的流程
图 4 展示了基于约束的空间众包的基本流程。
图 4 多阶段空间众包的流程
流程中的任务分配建立在两个预先定义的知
识集之上，分别是参与者的位置与服务授权以及位
置服务拓扑。参与者的授权信息指明了参与者具有
访问指定位置和使用指定线下服务的能力；位置服
务拓扑则表示了一组位置与服务在物理空间维度
上的结构与关联。
参与者可在任意时刻决定是否开始接受任务
的指派。在该准备时刻，参与者需要指定其能够承
担任务的时间区间以及移动范围。每一次众包任务
的分配都是从已准备好并空闲的参与者中选取一
个最优集合，相互协作完成整体的任务目标。在此
过程中，任务的请求者首先在众包平台上发布其任
务，描述任务的操作序列与约束，如第二章中给出
的例子：（1）前往 A 使用 SA；（2）前往 D 使用
SD；（3）前往 G 使用 SG；（4）前往 I。随后，
服务器针对该任务需求，基于候选参与者的信息和
位置服务信息，计算多阶段的子任务分配方案（具
体的分配算法见第四章）。最后，子任务的分配方
案被指派给选中的参与者。
3.3 基于约束空间众包的组成要素
本文所述的空间众包有一系列要素构成，包括
位置服务拓扑结构、参与者、任务、子任务分配方
案等。
（1）位置服务拓扑结构
𝑇𝑜𝑝𝑜 = 𝐿, 𝑆, 𝐸, 𝐿𝑆
𝐿 = 𝑙 | 𝑙 = 𝜃�
�, 𝜑
𝑙
𝜑�
� 𝜖 𝑟𝑒𝑠𝑡𝑟𝑖𝑐𝑡𝑒𝑑, 𝑢𝑛𝑟𝑒𝑠𝑡𝑟𝑖𝑐𝑡𝑒𝑑
𝑆 = 𝑠 | 𝑠 = 𝑑𝑒𝑠𝑝�
�, 𝛿
𝑠, 𝜓
𝑠
𝜓�
� 𝜖 𝑟𝑒𝑠𝑡𝑟𝑖𝑐𝑡𝑒𝑑, 𝑢𝑛𝑟𝑒𝑠𝑡𝑟𝑖𝑐𝑡𝑒𝑑
𝐸 = 𝑒 | 𝑒 = 𝑖, 𝑙�
� , 𝑑
𝑙𝑖,𝑙𝑗, 𝑡𝑙
𝑖,𝑙𝑗 , 𝑙𝑖, 𝑙𝑗𝜖𝐿
LS = L × S，且size 𝐿𝑆�
�
−1 = 1
𝑅𝑜𝑢𝑡𝑒 = 𝑛0, … , 𝑛
𝑘 , 且(𝑛
𝑖, 𝑛
𝑖+1) ∈ 𝐸 𝑜𝑟
(𝑛�
�, 𝑛
𝑖+1) ∈ 𝐿𝑆 𝑜𝑟 𝐿𝑆
𝑛𝑖
−1= 𝐿𝑆�
�𝑛+1
−1 𝑜𝑟 (𝐿𝑆�
�𝑖
−1, 𝑟�
�+1) ∈ 𝐸
位置服务拓扑是表达空间范围内物理位置、线
下服务及相互之间关联关系的网状结构。使用 Topo
表示该拓扑结构，主要由四个部分组成，分别是位
置的集合 L，线下服务的集合 S，位置间的连接 E
及位置与服务的包含关系 LS。
其中，位置 l 由二元组描述。θl是该位置的具
体坐标点，φl则描述该位置是否附加有访问权限。
若位置仅供授权人员访问，则 φl取值 restricted，反
之则取值 unrestricted。线下服务 s 定义为一个三元
组。desps是服务的简要描述信息。δ
s
表示该服务预
估的执行时长。ψs指示了该服务是否具有使用权限。
当任何人都能使用该服务时（有专人提供服务或者
任何人都能够使用特定的服务设备），ψs取值
unrestricted。反之，当该服务仅允许受限人员使用
或者该提供该服务的设备仅能具有使用权限的人
员操作时，ψs取值 restricted。
E 代表了实际物理空间中位置间的通道，即拓
扑网络中连接两个 l（li与 l
j
）的边。每一个通道 e
定义为一个三元组，除了连接的两个位置之外，𝑑�
�𝑖,𝑙𝑗,
𝑡�
�𝑖,𝑙𝑗，分别表示从 li前往 lj的路线距离与预估的移动
时间。值得注意的是，距离与移动时间不一定成正
比，即距离短可能用时会更长，在真实的上下坡现
实场景中可能存在这种情况。位置与服务的映射 LS
表示了特定的线下服务所处的位置，这类服务需要
参与者真实移动到服务所对应的位置才能使用。在
拓扑结构中，假设每一个服务只能对应于一个位置。
拓扑结果中相连的位置或服务构成了路径
Route。每一条路径有序地排序了位置结点与服务结
点，且相邻的结点必须存在位置的邻接关系或位置
与服务的包含关系。为了便于对路径的操作，进一
步定义如下的属性与操作：
Route.startNode 与 Route.endNode 表示路径的
起点与终点；Route.T 与 Route.D 分别表示沿路径移
动的整体用时与距离。Route.subRoute(li,l
j)表示从原
始路上截取由 li至 l
j
的子路径的操作。
（2）参与者
𝑤 = 𝐿𝑃�
�, 𝑆𝑃
𝑤, 𝑙
𝑤, 𝑀𝑅
𝑤, 𝐴𝑇
𝑤
𝐿𝑃�
�= 𝑙 | 𝑙 𝜖 𝐿, 𝑙. 𝜑
𝑙= 𝑟𝑒𝑠𝑡𝑟𝑖𝑐𝑡𝑒𝑑
𝑆𝑃�
�= 𝑠 | 𝑠 𝜖 𝑆, 𝑠. 𝜓
𝑠= 𝑟𝑒𝑠𝑡𝑟𝑖𝑐𝑡𝑒𝑑
𝑀𝑅�
�= 𝑙 | 𝑙 𝜖 𝐿, 𝑙包含于移动范围内
𝐴𝑇�
�= 𝑠𝑡𝑎𝑟𝑡𝑇𝑖𝑚𝑒, 𝑒𝑛𝑑𝑇𝑖𝑚𝑒
计算机学报 9
19. lj←交叠位置中 w2额外开销最小的位置;
20. M ← M + deriveStage (r, s, lj, w1, st) +
deriveStage (r, lj, d, w2, st); RETURN M;
21. ELSE
22. M ← M + deriveStage (r, s, l1, w
1, st) +
deriveStage (r, l2, d, w
2, st);
23. r’ ← r.subRoute(l1, l
2);
24. RouteAllocation(r’,W,st+r.subRoute(s,l1).T,M);
25. END IF
值得注意的是，如果此时出现两个或多个特征
（𝑤 = 𝐿𝑃�
�, 𝑆𝑃
𝑤, 𝑙
𝑤, 𝑀𝑅
𝑤, 𝐴𝑇
𝑤 ）完全一致的参与者，
算法将会引入参与者的信誉度（credit）指标来协助
选择。信誉度是由众包平台提供的用户数据，由用
户的任务完成率、任务转包率、历史承接任务数量
等数据综合推算得出，当出现两个或多个特征完全
一致的参与者时，算法将会选择信誉度最高的参与
者进行任务分配。
针对用时最短的优化目标，从 SR 中选择沿路
径前进耗时最长（即能沿路径前进最远），且离开
路径起点具有最短移动时间（通过 mt 方法计算）
的参与者 w1（第 6 行）。类似地，针对距离最短的
优化目标，选择能够沿路径前进距离最长且离开路
径起点最近（通过 md 方法计算）的参与者 w1（第
6 行）。算法使用 l1表示选中的参与者 w
1
能够达到
的最远位置点。
下一步采用从终点反向递推的方式选择协作
的参与者。类似地，从 W 中查找所有具有终点位置
权限、服务权限，且可用时间与移动范围符合终点
操作要求的参与者集合 DR（第 12 行）。在执行这
步骤之前，为了得到更贴近实际场景的结果，在第
一次调用 RouteAllocation 时需要考虑第一阶段参与
者移动至起点的耗时，更新路径执行的起始时间
（第 8-10 行）。另外，还需要更新第一阶段参与者
在执行其阶段子任务后的位置（第 11 行）。当 DR
为空时，直接返回空的分配方案。反之，通过
backward(r,d,w)方法计算 w 在 r 路径中从 d 位置倒
推到他最远能够到达的位置点的子路径，并使用
l.bw 表示这条子路径的起点。针对不同的优化目标，
计算在子路径中移动的总体耗时/总体距离与 w 前
往 l.bw 的耗时与距离差值，将具有最大差值的 w 选
定为承担后续阶段的参与者 w2（第 16 行）。
在推导出前后两阶段的子路径后，若两条路径
具有交叠，则选择位置交集中对 w2而言额外开销最
小的位置 lj（针对用时最少的优化目标，从交集中
选择离 w2的当前位置移动时间最短的位置。类似地，
针对距离最短的优化目标，选择离 w2的当前位置移
动距离最短的位置）作为交接点，分别创建并返回
由 w1承担的从 s 到 l
j
，以及由 w2承担的从 l
j
到 d
的阶段性子任务。（第 19-20 行）。若两条路径不
存在交集，则生成分别由 w1和 w
2
承担的从 s 到 l1
以及 l2到 d 的子任务，同时将路径上的剩余部分（从
l1到 l
2
）视为新的待分析路径 r’，递归调用
RouteAllocation 进行子任务分配（第 22-24 行）。
其中，r’路径的执行起始时间为 r 的实际起始执行
时间加上 l1之前路径的耗时。
以 动 机 案 例 二 中 的 任 务 为 例 , 针 对 路 径
A-SA-B-D-SD-B-E-F-G-SG-I，RouteAllocation 算法
经历了两次调用。在第一次调用中，基于从起点递
推的方式推导得到应由 Bob 承担从 A 至 D 的子路
径（A-SA-B-D），基于从终点反向递推的方式得到
应由 David 承担从 E 至 I 的子路径（E-F-G-SG-I）。
第二次调用针对剩余的从 SD 至 E 的路径（SD-B），
可直接推导得到由 Charile 单独承担。将这些结果
合并后的得到三阶段的子任务分配方案。类似地，
在以距离最短为优化目标的情况下，也通过调用两
次 RouteAllocation 过程得到针对距离最短的路径的
三阶段任务分配方案。
多阶段任务分配算法的最佳时间复杂度为
O(n*logn*l2),最坏时间复杂度为 O(r*n*logn*l
2
)，其
中 n 为报名参加某任务的参与者的平均数量，l 为
任务涉及的位置或服务的平均数量，r 为任务路径
集合 Routes 的平均长度。
算法 4. RouteAllocationFromStart
输入: r //当前任务执行路径
W //参与者集合
st //路径执行的起始时间
M //初始分配结果
输出: M //单路径任务分配结果
1. s←r.startNode; d←r.endNode;
2. SR←{sr1,…, srn}, sri∈W 且 sri具有起点访问权
限、符合 sri移动范围与可用时间约束;
3. IF SR = ∅ THEN
4. M ←{}; RETURN M;
5. END IF
6. w1←w ∈ SR, 根 据 优 化 目 标 ， 使
forward(r,s,w).D-md(w, s)取得最大值;
7. l1 ← forward(r,s,w
1).getEnd();
8. IF r = 完整任务路径 THEN
计算机学报 7
每一个参与者 w 定义为一个五元组。其中，LPw
与 SPw分别表示一个参与者针对受限的位置与服务
的授权情况，即 LPw是该人员除了公共位置外能够
访问的受限位置的集合，SPw是他能够使用的受限
服务的集合。
lw表示参与者的实时位置。另外，根据参与者
在准备接受任务时指定的移动范围与可用时间，
MRw是移动范围内的位置集合。AT
w
是愿意承担任
务的时间区间，由起始时间与结束时间的二元组描
述。
（3）任务
𝑡𝑎𝑠𝑘 = 𝑂𝑃, 𝑡�
�𝑢𝑏
𝑂𝑃 = 𝑜𝑝1, … , 𝑜𝑝
𝑛 , 𝑜𝑝
𝑖 𝜖 𝑚𝑜𝑣𝑒 𝑙
𝑖, 𝑙
𝑗 , 𝑢𝑡𝑖𝑙𝑖𝑧𝑒 𝑙, 𝑠 ,
𝑙�
�, 𝑙
𝑗, 𝑙𝜖𝐿, 𝑠𝜖𝑆
任务请求者在众包平台上发布任务。通过将任
务描述映射到位置服务拓扑，将任务 task 定义为一
个由操作序列 OP 和发布时间 tp
ub
构成的二元组。
每一项操作 op 具有明确的目标，需要委托参与者
从位置 li前往指定的位置 l
j
（move）或使用处于位
置 l 的特定的服务 s（utilize）。
（4）子任务分配方案
𝑇𝐴 = 𝑠𝑡𝑎𝑔𝑒 | 𝑠𝑡𝑎𝑔𝑒 = 𝑤, 𝐼𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛, 𝑡�
�𝑑𝑣𝑖𝑐𝑒
𝐼𝑛𝑠 = 𝑖1, … , 𝑖
𝑛 , 𝑖
𝑘 𝜖 𝑚𝑜𝑣𝑒 𝑙
𝑖, 𝑙
𝑗 , 𝑢𝑡𝑖𝑙𝑖𝑧𝑒 𝑙, 𝑠 ,
𝑙�
�, 𝑙
𝑗, 𝑙𝜖𝐿, 𝑠𝜖𝑆, 𝑙
𝑖, 𝑙
𝑗 𝜖𝐸, (𝑙, 𝑠)𝜖𝐿𝑆
众包平台根据申请者提交的任务计算得到一
组子任务分配方案 TA。TA 由多个阶段组成，每一
个阶段指派给一个特定参与者 w，表现为基于位置
服务拓扑的有序执行指令 Ins。指令包括位置移动
与服务使用，其中位置移动指令详细地指示了从一
个位置移动到另一个位置应该经过的位置点。邻接
阶段的连接点表示了参与者的交接位置，一般表现
为由前一阶段的参与者将物品交由后一阶段的参
与者从而继续后续的任务流程。另外，为了尽量缩
短任务的完成时间以及减少参与者在交接时的等
待时间，每一个阶段还指明了参与者应到达任务起
始位置的建议时间 ta
dvice
。
除此之外，定义名为 deriveStage(r, s, d, w, st)
的操作，将指派给参与者 w 的、在路径 r 中从 s 结
点到 d 结点的操作序列转换成子任务分配方案。同
时，根据路径 r 的起始执行时间 st，计算在 s 处的
建议开始时间，即阶段方案中的 ta
dvice
。
（5）优化目标
𝑂𝑝𝑡𝑖𝑚𝑎𝑙�
�𝑖𝑠𝑡= min 𝑚𝑑(
𝑤1, 𝑙0 ) + min(𝑠𝑢𝑚(𝑑𝑙
1,𝑙2)) ，
l1,l
2
是 Ins 中涉及的位置
𝑂𝑝𝑡𝑖𝑚𝑎𝑙�
�𝑖𝑚𝑒=
min (𝑚𝑑(
𝑤1 , 𝑙0)) + min(𝑠𝑢𝑚 𝑡𝑙
1,𝑙2 + 𝑠𝑢𝑚(𝛿𝑠)),
l1,l
2,s 是 Ins 中
涉及的位置和服务
optimald
ist
表示移动距离最短的优化目标。该目
标要求分配方案中沿路径的移动距离最短，同时承
担第一阶段子任务的参与者到达任务起点的移动
距离最短。optimalt
ime
则表示用时最少的优化目标。
它要求分配方案中沿路径具有最短的移动用时，同
时要求第一个参与者到达任务起点的用时最少。
4 多阶段任务分配算法
本文提出 MultiStageAllocation 算法根据指定的
优化目标对基于约束的空间众包任务推导得到子
任务分配方案。算法的基本思路是：首先根据优化
目标获取与任务对应的路径集合并根据优先级进
行排序，随后依次针对每一条路径，递归地采用从
起点和终点双向选取局部最优结果的方法选择承
担阶段性任务的参与者。一旦路径上的任务能够被
一个或一组参与者协作完成，则得到阶段任务的分
配方案。
算法 1. MultiStageAllocation
输入: Topo //位置-服务拓扑结构
W = (w1,…,w
n) //候选参与者
OptimalGoal //优化目标
task //任务
输出: TA //子任务分配方案
1. Routes ←GetRoutes(Topo, task, OptimalGoal) ;
2. TA ←{};
3. FOREACH r in Routes DO
4. TA ← RouteAllocation(r,W, task.tp
ub, TA);
5. IF TA != {} THEN
6. RETURN TA;
7. END IF
8. END FOR
9. RETURN {};
MultiStageAllocation 依赖四项输入，分别是位
置服务拓扑结构 Topo、参与者集合 W、任务 task
和优化目标 OptimalGoal。MultiStageAllocation 的执
行分过程为两个阶段。首先，根据优化目标获取与
任务对应的且经过优先级排序的路径集合 Routes
（第 1 行）。随后，依次针对每一条路径，根据参
与者的信息计算在该路径上的子任务分配方案（第
计算机学报 8
3-9 行）。一旦得到方案即将方案返回，否则迭代
计算优先级次低的路径。若针对所有路径都无法计
算出分配方案，则该次众包任务分配被视为失败。
以 动 机 案 例 二 中 所 描 述 的 任 务 为 例 ，
MultiStageAllocation 将针对经过排序的路径集合
Routes 计算方案。在以用时最少为优化目标的情况
下，将首先对路径 A-SA-B-D-SD-B-E-F-G-SG-I 进
行计算（该路径是 Routes 中优先级最高的，即路径
总用时最短的）。若对该路径计算失败，则继续对
优先级较低的路径进行计算。MultiStageAllocation
依赖 GetRoutes 算法获取与任务对应的路径并对其
进行排序。该算法接受位置服务拓扑结构 Topo、优
化目标 OptimalGoal 与任务 task 作为输入。根据 task
操作列表 OP 中的每项操作 op，通过 findPath 方法
在 Topo 中获取覆盖 op 起点和终点位置的局部路径
集合 op_routes（第 1-3 行）。随后，将各条局部路
径集合按照前后顺序进行组合，生成总体任务的路
径集合 Routes（第 4 行）。最后，根据不同的优化
目标，计算每条路径的总额外开销（总额外移动距
离或总额外移动时间），由低到高将路径进行排序
（第 5 行）。
算法 2. GetRoutes
输入: Topo //位置服务拓扑结构
OptimalGoal //优化目标
task //任务
输出: Routes //任务执行路径集合
1. FOREACH op in task.OP DO
2. op_routes[op] ← findPath(Topo, op);
3. END FOR
4. Routes ← combine(op_routes[]);
5. Routes ←根据不同的优化目标，按照额外开销由低
到高排序;
6. RETURN Routes;
以动机案例二中的任务为例, 当前任务操作列
表为（1）前往 A 使用 SA；（2）前往 D 使用 SD；
（3）前往 G 使用 SG；（4）前往 I。findPath 方法
将计算出所有上述任务操作列表的可能的局部路
径，如符合操作（2）的局部路径：B-D-SD 或
B-C-D-SD。然后对所有操作对应的局部路径进行组
合以生成路径集合 Routes。
针对每一条路径，MultiStageAllocation 算法依
赖 RouteAllocation 算法计算潜在的子任务分配集合。
算法输入是路径 r、参与者集合 W 与路径执行的起
始时间 startTime。RouteAllocation 的基本过程如算
法 3 所示：
首先采用从起点递推的方式选择参与者。找出
具有起点位置访问权限、且参与者的移动范围与可
用时间覆盖该起点的位置与执行时间的参与者集
合 SR（第 2 行）。若没有参与者满足条件，则算法
返回空集合（第 3-5 行）。反之，根据不同的任务
优化目标，找出最合适的参与者（第 6-7 行）。在
该步骤中，forward(r,s,w)方法用于计算 w 在 r 路径
中从 s 位置处出发到他最远能够访问到的位置点或
服务的子路径。计算得到的子路径需要满足以下条
件：（1）w 具有对子路径中所有位置和所有服务的
访问授权；（2）子路径中的所有位置点都在 w 的
移动范围内；（3）子路径的执行时间在 w 的可用
时间范围之内。
算法 3. RouteAllocation
输入: r //当前任务执行路径
W //参与者集合
M //初始分配结果
输出: M //单路径任务分配结果
1. s←r.startNode; d←r.endNode;
2. SR←{sr1,…, srn}, sri∈W 且 sri具有起点访问权
限、符合 sri移动范围与可用时间约束;
3. IF SR = ∅ THEN
4. M ←{}; RETURN M;
5. END IF
6. w1←w ∈ SR, 根 据 优 化 目 标 ， 使
forward(r,s,w).D-md(w, s) 或
forward(r,s,w).T-mt(w, s)取得最大值;
7. l1 ← forward(r,s,w
1).getEnd();
8. IF r=完整任务路径 THEN
9. st ← st+movingTime(w1,s);
10. END IF
11. updateCoordinate(w1,l
1);
12. DR←{dr1,…, drn}, dri∈W 且 dri具有终点访问权
限、符合 dri移动范围与可用时间约束;
13. IF DR = ∅ THEN
14. M ←{}; RETURN M;
15. END IF
16. w2←w ∈ DR, 根 据 目 标 ， 使
backward(r,d,w).D-md(w,d.bw) 或
backward(r,d,w).T-mt(w,d.bw)取得最大值;
17. l2
← backward(r,d,w2).getStart();
18. IF r.subRoute(s,l1) ∩ r.subRoute(l
2,d) ≠ ∅ THEN
计算机学报 11
在此基础上，模拟实验的目标设置为，在相同
的位置服务拓扑与参与者约束情况下：
（1）验证多阶段任务分配算法相比基于动态规
划的 OptimumAllocation 具有更高的计算效率。
（2）验证如下结论：从起点和终点双向选取局
部最优结果的设计方式，和从起点开始单向选取局
部最优结果的设计方式相比，具有一定的优越性。
在给定的位置服务拓扑结构的前提下，实验所
用的模拟数据是随机生成的参与者的受限位置与
服务的授权情况、活动范围和当前位置坐标等数据。
这组数据的随机生成方式遵照以下规则：
（1）针对参与者在受限位置与服务上的授权，
对每个受限位置和服务，随机生成所有参与者的受
限位置与服务的授权情况的数据。
（2）针对参与者的当前位置，首先根据位置服
务拓扑结构得出所有位置的具体坐标数据和整体
空间范围的横纵坐标区间，然后在该区间内随机生
成每个参与者的当前位置的横纵坐标。
（3）针对参与者的移动范围，在一定区间内
随机生成每个参与者的活动半径，根据参与者的当
前位置和活动半径，计算得出参与者能够访问的位
置集合。
在本次实验中，生成多组参与者的模拟数据。
具体生成方式如下:（1）根据图 1 所示的位置服务
拓扑生成对应的模拟平面图。图 1 所示拓扑参考了
某公司办公地点的实际拓扑结构，因此具有其合理
性。模拟的平面拓扑为长 1200 米、宽 850 米的空
间范围，并标注出每个位置或服务在该空间内的坐
标。同时生成每个位置或服务的权限概率值，该值
表示对于某个参与者，有多大的概率拥有该位置或
服务的访问权限。一般而言，公开程度越高的空间
或服务，其权限概率值越高，如茶水间、休息室的
权限概率值均较高。权限概率值的生成过程参考了
该公司管理平台公开的人员分布真实数据：将所有
人员分为高层管理人员、基层管理人员、技术类普
通员工、非技术类普通员工、保洁安保人员和外部
访客等不同分类，并从企业管理平台获得每个分类
的数量信息。其中外部访客分类采取 1 个月内的日
平均访客数量。上述数据均来源于某真实公司。根
据每个位置或服务对不同分类人员的开放程度，计
算其权限概率值。例如，文件盖章服务仅对高层管
理人员、基层管理人员和非技术人员开放，这三类
人员占总人员数量的 55%，则文件盖章服务的权限
概率值为 55%。
（2）定义活跃参与者为接受任务指派的参与
者。根据不同的活跃参与者数量分别使用两种算法
记录算法的执行时间（ExecutionTime）与分配结果。
例如，活跃参与者数量为 20000 代表有 20000 名参
与者报名参与了该众包任务，可以作为任务分配对
象。活跃参与者数量选取方式为：从 20000 开始，
以 20000 为增长梯度，依次递增至 160000。
（3）针对某个具体的活跃参与者数量，依据
上述的三类随机数据生成规则，生成对应数量的随
机模拟数据。现在考虑每个生成的模拟参与者，针
对每个位置或服务均生成一个 0 至 1 范围内的随机
数，根据该位置或服务的权限概率值，决定这个模
拟参与者是否拥有对应权限。模拟参与者的当前位
置为在平面拓扑范围内随机生成的坐标点。模拟参
与者的活动半径为 100m 到 600m 内的随机值，根
据随机活动半径计算出其意愿活动范围内的位置
或服务集合。
下面定义三个任务，分别评价多阶段任务分配
算法与基于动态规划算法的分配结果。这三个任务
都基于图 1 所示的位置服务拓扑。
task1 的操作序列描述：前往会议室领取某文件
（C）；前往图书馆（F）使用数据归档服务（SF）；
将归档凭证递送至计算机楼（I）。
task2 的操作序列描述（即动机案例中的任务）：
前往收发室（A）使用物品领取服务（SA）；前往
打印室（D）使用文件打印服务（SD）；前往财务
处（G）使用文件盖章服务（SG）；前往办公室（I）。
task3 的操作序列描述：前往收发室（A）使用
物品领取服务（SA）；前往打印室（D）使用文件
打印服务（SD）；前往财务处（G）使用文件盖章
服务（SG）；前往归档处（F）使用数据归档服务
（SF）；前往办公室（I）；前往打印室使用文件
打印服务（SD）；前往会议室（C）。
任务设计遵循了任务规模递增的原则，从 task1
到 task3，任务涉及的空间位置和服务的数量增加，
任务描述的复杂程度增加，平均任务路径长度增加。
对于上述三类定义任务，根据不同的优化目标
分 别 执 行 分 配 Multi StageAllocation 算 法 和
OptimumAllocation 算法，得出任务分配结果。其中
Multi StageAllocation 为 本 文 提 出 的 主 算 法 ， 而
OptimumAllocation 为对比算法。记录任务分配方案
结果的总额外移动距离（TEDist）和总额外移动时
间（TETime），分别表示所有参与者为了完成任务
而从当前位置移动到阶段任务起点所花费的额外
计算机学报 10
9. st ← st+movingTime(w1,s);
10. END IF
11. updateCoordinate(w1,l
1);
12. M ← M + deriveStage (r, s, l1, w
1, st);
13. IF l1
= d THEN
14. RETURN M;
15. ELSE
16. r’ ← r.subRoute(l1, d);
17. RouteAllocation(r’,W,st+r.subRoute(s,l1).T,M);
18. END IF
RouteAllocation 采用了从起点和终点双向选取
局部最优结果的设计方式。和从起点开始单向选取
局部最优结果的设计方式（如算法 4 所示）相比，
两者算法耗时相近的情况下，双向算法能取得一定
的性能优势，即在总额外移动时间或总额外移动距
离方面略优于单向算法；此外，双向算法在从起点
递推和从终点反向递推出现交叠部分的时候进行
选择交叠部分中造成最小额外开销的位置或服务。
同时，双向算法能兼顾某些特殊情况，如某个参与
者满足路径中除了起点以外大部分位置或服务的
限制条件。在第 5 章实验与讨论中，将结合实验数
据对双向算法和单向算法的性能优劣问题作进一
步讨论。
5 实验与讨论
本章展示实验的过程与结果。实验分为模拟实
验和真实实验两部分。模拟实验的目的是验证算法
的有效性与可拓展性，真实实验的目的是验证算法
的可用性。首先介绍实验设计方案，包括模拟数据
的生成方式、真实实验的设置等细节。其次列举实
验结果并进行评价。最后讨论本方法的特点与局限
性。
5.1 模拟实验
5.1.1 实验设计
为了比对并验证多阶段任务分配算法的可拓
展性与有效性，我们另外设计了一个基于动态规划
的算法作为对比对象。该算法与本文的多阶段任务
分配算法共享 MultiStageAllocation 与 Get Routes 部
分（即算法 1、2），在计算子任务分配集合方面（即
算法 3），采用一种基于动态规划的全局最优算法，
如算法 5 所示。
OptimumAllocation 的基本原理是：利用一个数
组保存前 n 个位置或服务组成的局部路径的最佳分
配方案（第 2 行）。对于其中某个局部路径，假设
其为前 i 个位置或服务组成的局部路径，其中 0<i<k
（第 3 行），考虑其每一个可能的子局部路径（前
j 个位置或服务组成的局部路径，0<j<i）与活跃参
与者中在满足权限授权情况、活动范围和可用时间
等约束条件的限制下，能够单独完成路径缺失部分
（第 j+1 个到第 i 个位置或服务）的参与者。类似
地 ， 若 此 时 出 现 两 个 或 多 个 特 征
（𝑤 = 𝐿𝑃�
�, 𝑆𝑃
𝑤, 𝑙
𝑤, 𝑀𝑅
𝑤, 𝐴𝑇
𝑤 ）完全一致的参与者，
算法将会参考参与者的信誉度指标来完成选择。找
出所有的子局部路径与缺失部分单参与者填补的
总额外开销（根据不同的优化目标决定）最小的组
合，作为前 i 个位置或服务组成的局部路径的新方
案（第 6-13 行）。最后，输出前 n 个位置或服务组
成的局部路径的分配方案。OptimumAllocation 的最
佳复杂度为 O(n2*l
2
),最坏时间复杂度为 O(r*n2*l
2
)，
其中 n 为报名参加某任务的参与者的平均数量，l
为任务涉及的位置或服务的平均数量，r 为任务路
径集合 Routes 的平均长度。
算法 5 . OptimumAllocation
输入: r //任务执行路径
W //参与者集合
st //路径执行的起始时间
输出: M //任务分配结果
1. len←r 中位置和服务的总数;
2. allocation[]← 长 度 为 len+1 的 数 组 ， 其 中
allocation[k]表示 r 中前 k 个位置或服务组成的局
部路径的最佳分配方案(k>0);
3. FOR i ←1 TO len
4. extraCost←根据优化目标得到的总额外开销;
5. winner←0;
6. FOR j ←1 TO i
7. currCost←allocation.cost()+minCost(w,j,i);
8. IF currCost < extraCost THEN
9. winner←j;
10. extraCost←currCost;
11. END IF
12. END FOR
13. allocation[i] ← 在 allocation[winner]的基础之
上，将 winner~i 段分配给最低开销的参与者;
14. END FOR
15. RETURN allocation[len]
计算机学报 |
| [返回] |
下一篇：深度学习FPGA加速器的进展与趋势