基于约束的空间众包多阶段任务分配

• 作者: 彭鑫 沈立炜 范泽军 赵文耘
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 空间众包 任务分配 多阶段 时空约束 空间拓扑
• 年，卷（期）: 2019,（12）
• 所属期刊栏目: 数据科学与工程
• 页码范围: 2722-2741
• 页数: 20页
• 分类号: TP311
• 字数: 21878字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2019.02722

摘要

在人机物融合的背景下,空间众包可被视为一种新型的软件服务.空间众包是针对于物理世界中与地理位置和时间要素相关的众包任务,通常要求参与者真实地移动到指定位置执行相应操作,承担数据收集与感知等任务,并通过移动终端反馈操作结果.任务分配是空间众包中的关键技术,其目的是在满足时空约束条件的前提下选取一个或一组合适的参与者承担任务的执行.在具有空间位置访问权限、线下服务使用权限并考虑参与者可用时间与移动范围约束的空间众包场景中,单个参与者可能无法完成整个任务的执行,转而需要一组参与者进行协同合作后才能完成.针对该需求,本文提出了一种基于约束的空间众包多阶段任务分配方法.该方法的核心算法将首先根据两种不同的优化目标获取对应的任务路径集合,然后针对每一条路径采用从起点和终点双向选取局部最优的方法递归地选择承担阶段性任务的参与者.通过上述步骤,可高效地将任务分解为一组由不同参与者在符合约束条件时能够承担的阶段性子任务,以此提高任务完成的概率.最后,我们使用上述算法分别进行了模拟实验和真实场景实验.模拟实验面向随机生成的参与者数据集,并与基于动态规划取得全局最优解的算法进行对比.实验结果表明本文所提算法相比于对比算法具有更好的计算效率.真实场景实验依赖自主开发的校园空间众包任务平台开展.实验结果表明本文算法能够在真实任务环境下推导得到参与者可接受的子任务分配决策.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	沈立炜	复旦大学上海市数据科学重点实验室	22	43	4.0	4.0
2	范泽军	复旦大学计算机科学技术学院	1	2	1.0	1.0
3	彭鑫		1	2	1.0	1.0
4	赵文耘		1	2	1.0	1.0