空间众包任务分配算法的研究

发布时间：2023-10-29 10:35

　　空间众包由工人、任务请求者和平台组成,有效的任务分配算法能够兼顾三方利益,实现分配效果全局最优。任务分配问题最大的难点在于动态性,任务是随机出现且有时效性,工人自由地加入或离开,导致平台无法及时获取工人和任务相关信息,增加任务分配的难度。如何在动态情况下实现更好的任务分配效果,仍然是一个尚未完全解决的问题。本文针对该问题开展了以下工作:首先,针对空间众包模型理想化问题,本文结合应用背景,提出合理的工人和任务模型。为工人增加技能属性,任务增加类型属性,根据二者匹配程度赋予不同的分数,在此基础上将其建模为一个以最大化任务分配总分数为目标,受工人和任务时间和空间约束的优化问题。采用批处理模式进行任务分配,在每个时间片,将最大分数问题转化为二分图匹配问题。其次,针对批处理模式下任务分配局部最优的问题,本文提出基于预测的任务分配算法,即在任务分配中,通过历史数据对未来时间片的任务分布情况进行预测,使工人不断地出现在任务较多的区域,提升任务分配的效果。再次,由于工人会有欺骗行为,导致任务完成存在失败的概率,本文提出可靠性来衡量任务完成概率。可靠性定义包含工人可信度、任务类型和工人技能匹配程度。工人...

【文章页数】：58 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
1 绪论
    1.1 研究背景和意义
    1.2 国内外研究现状
    1.3 主要研究内容
    1.4 论文组织结构
2 空间众包介绍
    2.1 空间众包的概念
    2.2 空间众包的研究方向分类
    2.3 空间众包任务分配算法
    2.4 本章小结
3 空间众包模型及相关定义
    3.1 空间众包任务
    3.2 空间众包工人
    3.3 最大分数任务分配(MSA)问题
    3.4 任务分配可靠性
    3.5 本章小结
4 任务分配算法研究
    4.1 算法框架
    4.2 基础算法(BASIC)
    4.3 最短距离优先算法(CDP)
    4.4 最小位置熵优先算法(LLEP)
    4.5 基于预测的任务分配算法(MNTP)
    4.6 基于可靠性的任务分配算法(HRP)
    4.7 本章小结
5 实验与结果分析
    5.1 实验设置
        5.1.1 实验环境
        5.1.2 实验数据
        5.1.3 评价标准
    5.2 任务分布预测实验
        5.2.1 实验设计
        5.2.2 实验结果与分析
        5.2.3 实验结论
    5.3 基于预测的任务分配实验
        5.3.1 实验设计
        5.3.2 实验结果与分析
        5.3.3 实验结论
    5.4 基于可靠性的任务分配实验
        5.4.1 实验设计
        5.4.2 实验结果与分析
        5.4.3 实验结论
    5.5 本章小结
结论
参考文献
致谢
作者简历及攻读硕士学位期间的科研成果



本文编号：3857909