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

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

论文摘要

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

论文目录

  • 1引言
  • 2动机案例
  •   2.1动机案例1
  •   2.2动机案例2
  • 3基于约束空间众包的定义
  •   3.1基于约束空间众包的概念
  •   3.2基于约束空间众包的流程
  •   3.3基于约束空间众包的组成要素
  • 4多阶段任务分配算法
  • 5实验与讨论
  •   5.1 模拟实验
  •     5.1.1 实验设计
  •     5.1.2实验结果与评估
  •   5.2 真实场景实验
  •     5.2.1 实验设计
  •     5.2.2 实验结果与评估
  •   5.3 讨论
  • 6相关工作
  • 7结论
  • Background
  • 文章来源

    类型: 期刊论文

    作者: 范泽军,沈立炜,彭鑫,赵文耘

    关键词: 空间众包,任务分配,多阶段,时空约束,空间拓扑

    来源: 计算机学报 2019年12期

    年度: 2019

    分类: 信息科技,基础科学

    专业: 数学

    单位: 复旦大学计算机科学技术学院,复旦大学上海市数据科学重点实验室

    基金: 国家重点研发计划“人机物融合的云计算架构与平台”(2018YFB1004800)资助~~

    分类号: O224

    页码: 2722-2741

    总页数: 20

    文件大小: 4799K

    下载量: 402

    相关论文文献

    标签:;  ;  ;  ;  ;  

    基于约束的空间众包多阶段任务分配
    下载Doc文档

    猜你喜欢