质量和预算感知的移动众包任务分配方法研究

发布时间：2018-12-12 02:40

【摘要】：随着无线网络通信技术(如4G网络)的快速发展和移动设备(如智能手机、平板电脑、PDA)的迅速普及,多种多样的移动众包平台出现在人们的日常生活中并得以广泛应用,如Uber、滴滴出行、CrowdFlower、Gigwalk、Gimission、Foursquare等。与此同时,移动众包也引起了各领域研究人员的广泛关注,成为学术界一个新的研究热点,并在理论和工程方面提出了许多具有挑战性的问题。任务发布者和移动工人是移动众包中的主要参与者,每个移动工人有各自的位置、轨迹,每个时空任务也都关联着时间和位置属性,每个众包任务的完成总是需要多个工人的参与,但是在众包模式下,任务的接受和执行完全遵循自愿的原则,由工人根据自身兴趣、意愿等自行决定而非强制。任务发布者关注的往往是完成任务的工人数量、工人提交结果的质量、支付给工人的奖励等方面;而影响工人决定的因素更为复杂,如交通路线及成本(时间、精力、金钱等)、奖励、兴趣等。因此,无论对于任务发布者,还是移动工人,任务分配是移动众包应用和研究中的一个核心问题。但是,任务的时效性和位置分布、工人的移动性和行程路线等各种复杂多变的时空因素都为移动众包任务分配问题的解决提出了挑战。现有的研究工作大多只针对工人数量、质量、预算等单一约束条件下的任务分配问题,对多约束条件下的任务分配方法研究还比较少。本文从任务发布者和工人的不同需求出发,针对现有工作的不足,对移动众包中的任务分配问题建模,并基于此分别研究基于任务发布者的多约束任务分配问题和基于工人兴趣的任务分配问题。具体工作和贡献如下:1.提出了移动众包中的任务分配问题模型。在此基础上,本文分别提出了基于任务发布者的多约束任务分配问题和基于工人兴趣的任务分配问题。2.针对基于任务发布者的多约束任务分配问题,本文分别以任务分配质量(时空任务被一定数量的工人完成的概率)最大化和预算最小化为优化目标提出了两个不同的众包任务分配算法。通过这两个算法计算得出的任务分配方案在满足任务发布者对完成任务的工人数量、任务分配质量、奖励预算等约束条件的同时,前者可以保证任务发布者获得尽可能高的任务分配质量,后者则可以保证任务发布者以尽可能少的预算获得任务结果。3.针对基于工人兴趣的任务分配问题,本文提出了以奖励最大化为优化目标的分支定界算法和两个近似算法,旨在根据移动工人的当前位置为工人分配一条执行任务的行程路线。工人按照算法计算得出的行程路线执行任务,不仅可以在规定的时间内完成路线中的任务,而且可以使工人获得尽可能多的任务奖励。4.本文采用从一个基于地理位置的签到网站Gowalla上收集到的真实数据作为实验数据集,通过在真实数据集上的对比实验比较各种算法的运行效率和效果。实验表明,本文提出的算法均取得了较好的运行效率和实验效果。
[Abstract]:With the rapid development of wireless network communication technologies (such as 4G networks) and the rapid spread of mobile devices (such as smart phones, tablet computers, and PDAs), a wide variety of mobile package platforms have been widely used in people's daily lives, such as Uber, Didi, CrowdFower, Giwalk, Gimission,Foursquare绛，

本文编号：2373743