论文部分内容阅读
随着以智能手机为代表的具有强大的计算、感知、存储和无线通信能力的便携式移动终端的普及和应用,一种召集便携式移动终端携带者执行具有空间特性的任务的新兴众包模式逐渐兴起,称之为空间众包。空间众包利用群体智慧和智能设备,可以高效完成空间任务。由于其灵活的工作方式、低成本和普适性等诸多优势,因而具有广泛的应用前景。目前,已有大量基于空间众包的应用程序投入到实际生活中使用。一个典型的空间众包系统主要由基于云端的系统平台和众包用户构成。其中,众包用户是在线注册的网络用户,根据其角色分为任务请求者和工作者。众包平台接受请求者上传的任务,然后招募工作者来完成任务。由于众包任务复杂且多样、需求各异,众包工作者具有不同的特征、目的,因此系统平台需要结合任务和工作者各自的需求和特征进行合适的任务匹配。任务分配的结果能在多大程度上满足众包用户的期望,作为一个重要的因素,影响着用户继续选择众包应用的潜在可能,继而影响众包应用的发展。因此,任务分配问题成为空间众包亟待解决的关键问题之一。空间众包要求工作者移动到任务所在位置完成任务,工作者选择的路线不同,完成任务获得的报酬和付出的时间成本是不同的。应当在考虑报酬和成本的权衡下进行合理的路线规划,设计出让工作着满意的路线。因此,路线规划问题成为空间众包中另一重要的研究问题。本文针对空间众包中的任务分配问题和路线规划问题展开研究。首先,针对具有属性偏好的空间众包如何进行高效的任务分配。现有的工作虽然考虑了不同属性对任务分配目标的影响,然而在适用于多目标优化时缺乏灵活性,且其性能和效率有待进一步提高。为此,本文假设:(1)具有更高预算的任务可以在更大的范围内选择工作者;(2)任务支付给工作者的报酬与其出行的距离成正比。根据距离设计了一种报酬计算方式,激励更多的高质量工作者参与任务。然后引入了多属性决策模型,将空间众包中的任务分配问题定义为一个多属性决策问题(MultiAttribute Decision Making,MADM),并提出了一种新的求解算法。目标是在预算约束下,最大化任务响应的质量、最小化任务出行的距离。在真实数据集和合成数据集上测试了所提出算法的优秀性能。其次,任务分配如何在满足任务工作者期望的同时,尽量满足任务请求者的期望。现有的任务分配方法或者从工作者的角度出发,或者仅考虑任务请求者的利益,很少同时关注双方的期望。而实际上,工作者通常希望在付出成本尽可能小的情况下获得尽可能多的回报。同样,任务请求者在发出服务请求后,希望任务能尽快得到响应。因此,设计合理的任务分配模型和算法,满足空间众包工作者的期望并最小化任务等待时间,对众包应用的发展具有积极的意义。为此,本文基于贪婪思想设计了具有延迟敏感的空间众包任务分配算法DSTA-G。并用大量的仿真实验证明了DSTA-G的优越性能。另一方面,现有的空间众包任务分配研究主要基于小型数据集。然而在实际应用中,数据规模往往是非常庞大的(如,美团众包平台)。因此,如何将众包任务分配方法扩展到大型数据集上,并维持其性能,具有重要的现实意义。为此,将空间索引技术Geohash引入空间众包任务分配中,对DSTA-G进行改进,提出了算法DSTAGH。大量仿真实验证明了DSTA-GH能够显著改进任务分配效率。最后,对于具有固定的起点和终点的工作者来说,在可选的任务中,如何进行合理的路线规划,使得:(1)工作者在时间预算内到达终点;(2)经过路线所花的代价最少;(3)完成路线上的任务所获得的报酬最多。现有工作的局限在与限定经历每个地点最多一次,且现有方法或者采用精确算法,或者采用基于贪婪思想的传统启发式方法。精确算法复杂度高,而传统启发式算法的精确度有待提高。为此,本文分析了路线规划的特点,不限定经历每个地点的次数,结合遗传算法和模拟退后算法的优缺点,提出了一种近似算法GA-SA。以精确算法EA、基于朴素遗传算法的解决方案PLGA和基于朴素模拟退火算法的解决方案PL-SA作为基线对算法GA-SA的精确度、综合寻优能力、收敛速度等进行了评估。