时间连续型空间众包任务的效率与质量问题研究

• 作 者: 王婷
• 出 处: 中国科学技术大学
• 发表日期: 2004年期
• 关键词: 空间众包 时间连续型众包 任务质量

随着智能移动设备的广泛使用,一种新的众包形式-空间众包应运而生。空间众包要求工作者到达指定任务位置才能执行任务。本文提出了一种新的空间众包形式,称为时间连续型空间众包。时间连续型空间众包与以往空间众包的不同在于,时间连续型空间众包任务需要长时间的任务周期才能完成任务。时间连续型空间众包在实际生活中存在广泛应用,包括环境监测、交通检测等。由于任务预算和可分配工作者数量有限,时间连续型空间众包任务无法在任务周期内被全部执行,使得所获得的结果数据往往不完整,出现数据缺失的问题。为了解决数据缺失问题,本文采用插值技术对缺失值进行估计,但同样会影响数据的准确性。因此对于时间连续型空间众包任务来说,任务质量是非常重要的衡量指标。基于此,本文提出一种基于熵的任务质量函数。在此基础上,本文分别研究了单任务场景和多任务场景下的时间连续型空间众包任务分配问题,具体研究内容如下:(1)本文提出时间连续型空间众包模式及相关定义,提出时间连续型空间众包任务质量函数,并研究以任务质量为优化目标的任务分配算法。(2)在单任务分配场景下,本文提出最大化单任务质量问题,并分析该问题的时间复杂度。接着,本文证明最大化单任务质量问题是NP-hard问题,并给出了带有近似比的近似算法来完成任务分配。同时为了提高算法运行效率,本文还提出一系列优化策略。(3)在多任务分配场景下,本文提出最大化多任务总质量问题和最大化最小单任务质量问题。在最大化多任务总质量问题中,本文发现了多任务之间的关联冲突,并提出并行化框架来加快优化过程。在最大化最小单任务质量问题中,本文采用启发式近似算法来完成任务分配。(4)本文采用模拟数据集和真实数据集,通过实验分析不同参数对算法的影响。对于单任务分配场景下的最大化单任务质量问题,通过对比实验显示优化策略对算法效率的提升。在多任务分配场景下,针对最大化多任务总质量问题,本文对比无并行化算法、独立任务组级并行化算法和任务级并行化算法的实验结果,表现任务级并行化算法的高效性;针对最大化最小单任务问题,通过设置对比试验显示本文所提算法的有效性。