空间众包环境下的3类对象在线任务分配

发布时间：2018-04-16 05:35

本文选题：空间众包 + 任务分配　；参考：《软件学报》2017年03期

【摘要】：随着移动互联网技术与O2O(offline-to-online)商业模式的发展,各类空间众包平台变得日益流行,如滴滴出行、百度外卖等空间众包平台更与人们日常生活密不可分.在空间众包研究中,任务分配问题更是其核心问题之一,该问题旨在研究如何将实时出现的空间众包任务分配给适宜的众包工人.但大部分现有研究所基于的假设过强,存在两类不足:(1)现有工作通常假设基于静态场景,即,全部众包任务和众包工人的时空信息在任务分配前已完整获知,但众包任务与众包工人在实际应用中动态出现,且需实时地对其进行任务分配,因此,现存研究结果在实际应用中缺乏可行性;(2)现有研究均假设仅有两类众包参与对象,即众包任务与众包工人,而忽略了第三方众包工作地点对任务分配的影响.综上所述,为弥补上述不足,提出了一类新型动态任务分配问题,即,空间众包环境下的3类对象在线任务分配.该问题不但囊括了任务分配中的3类研究对象,即众包任务、众包工人和众包工作地点,而且关注动态环境.进而设计了随机阈值算法,给出了该算法在最差情况下的竞争比分析.采用在线学习方法进一步优化了随机阈值算法,提出自适应随机阈值算法,并证明该优化策略可逼近随机阈值算法使用不同阈值所能达到的最佳效果.最终通过在真实数据集和具有不同分布人造数据集上进行的大量实验,验证了算法的效果与性能.
[Abstract]:With the development of mobile Internet technology and the business model of O _ 2O off line-to-online), various kinds of spatial crowdsourcing platforms have become increasingly popular, such as DiDi, Baidu takeout and other spatial crowdsourcing platforms are closely related to people's daily life.In the research of space crowdsourcing, the task assignment problem is one of its core problems, which aims to study how to assign real-time space crowdsourcing tasks to suitable crowdsourcing workers.However, most of the existing research institutes are based on too strong assumptions, and there are two types of deficiency: 1) existing work is usually based on static scenarios, that is, all crowdsourcing tasks and space-time information of crowdsourcing workers are fully known before the assignment of tasks.However, crowdsourcing tasks and crowdsourcing workers appear dynamically in practical applications and need to be assigned in real time. Therefore, the existing research results lack of feasibility in practical applications.) the existing studies assume that there are only two types of crowdsourcing participants.That is, crowdsourcing and crowdsourcing workers, ignoring the impact of third-party crowdsourcing locations on task allocation.In conclusion, in order to make up for the above deficiencies, a new dynamic task assignment problem is proposed, that is, online task assignment for three classes of objects in the environment of crowdsourcing.This problem not only includes three kinds of research objects in task assignment, that is, crowdsourcing task, crowdsourcing worker and crowdsourcing work place, but also pays attention to dynamic environment.Furthermore, the stochastic threshold algorithm is designed, and the competitive ratio analysis of the algorithm in the worst case is given.The random threshold algorithm is further optimized by online learning, and an adaptive random threshold algorithm is proposed. It is proved that the optimization strategy can approach the optimal effect of the random threshold algorithm using different thresholds.Finally, through a large number of experiments on real data sets and artificial data sets with different distributions, the effectiveness and performance of the algorithm are verified.
【作者单位】：软件开发环境国家重点实验室(北京航空航天大学);
【基金】：国家重点基础研究发展计划(973)(2014CB340300) 国家自然科学基金(61502021,71531001) 软件开发环境国家重点实验室(北京航空航天大学)开放课题(SKLSDE-2016ZX-13)~~
【分类号】：TP301.6

【相似文献】