基于工人信誉度和距离的任务分配算法

王从文

摘要：时空众包任务分配问题大多涉及到工人和任务的位置信息，针对工人的信誉度的研究较少。本文首先对工人信誉度进行定义，针对现有相关研究存在的问题，提出基于信誉度的任务分配算法，目标为最大化任务完成质量。实验中将本文提出的算法与随机算法进行对比，结果表明本文提出的算法性能优于随机算法。

关键词：时空众包;任务分配;信誉度

Abstract： The problem of space-time crowdsourcing task assignment mostly involves the location information of workers and tasks， and there is little research on the credibility of workers. This paper firstly defines the credibility of the workers， and proposes a task assignment algorithm based on credibility in view of the existing research problems. The goal is to maximize the quality of task completion. In the experiment， the algorithm proposed in this paper is compared with the random algorithm. The results show that the performance of the algorithm proposed in this paper is superior to the random algorithm.

Key words： space-time crowdsourcing;task allocation;credibility

1  研究背景

众包会产生大量的数据，目标是利用移动设备来收集和共享数据，可以给移动用户分配特定的任务。数据经由各种通讯设备获取，自行车上的传感器也可以收集数据，如图1和图2所示。

在众包市场中需求者可在众包网站上发布短期任务，工人通过完成此类任务进而获得相应的奖励。需求者利用众包工人多样性的特点，将任务分配给具备任务所需技能的工人。在技能未知的情况下，将任务随机分配给可用的工人，通过重复的任务分配来提高任务完成的质量，极大浪费人力、物力和财力。

时空众包领域中，工人大体可分为诚实和不诚实两类（按信誉度高低来确定）。不诚实的工人通过快速给出看似合理的答案，最大化自身利益。然而一些算法并没有考虑不诚实的工人的问题，这样会导致低质量的任务完成结果。其次工人的动态性，不能保证可用工人一定是信誉度高的工人，低技能等级工人会被分配他们无法完成的任务，导致低质量的任务完成结果。由于低技能工人和恶意工人的存在，会严重地影响任务完成质量，所以合理的任务分配算法对于众包系统的发展起到了关键的作用。本文针对工人信誉度的问题，展开相关研究。

2  研究框架

众包实现的完整过程为：任务请求者（发包商）首先在众包平台上发布任务，需要给出任务的详细描述以及要求和工人完成任务后可获得的奖金。工人注册或登录平台，即可决定是否参与到此任务中。如图3所示。

已知任务和工人的經纬度以及工人的信誉度（dlust），这时就需要我们跟据这些已知条件算出每个工人所对应该任务的V值，V值越大也就意味着该工人越适合该任务。算法将根据V值为任务分配最合适的工人，为任务根据V值分配合适的一个工人或多个工人。

众包平台将根据V值对任务推荐工人，我们认为V>0为推荐对象，当前一个推荐对象被占用可依此降低V值。当工人接收到平台的推荐时参与到此任务中。参与者为了完成此任务将付出努力，并在任务截止时间前在平台上提交一个质量为q的方案，最后发包商在时间截止后，评审所参与者提交的方案并将奖金通过众包平台发放给提交了质量最高的方案的参与者。

我们假定所有工人的信誉参数为R（根据每个工人的信誉度dlust用归一化方法为其算出一个0-1之间的R值）。同理我们假定所有参与者的距离参数为K（根据当前工人与当前任务计算出之间的距离（dist）、每个工人与每个任务之间的距离最大值max与最小值min，用归一化方法为其算出一个0-1之间的K值），我们称R越大其参与者的可信度越强，反之可信度越弱;同理K越小其最佳距离则越近。而α、β则是其信誉参数与距离参数在空间众包中的占比，多次实验与结果分析最终确定了α值为0.43、β值为0.57。

首先，当dist与min都为0时，则不去判断距离仅仅单方面判断符合要求的工人的可信度。其次，当可信度R达到可以忽略地理位置的高度时，那么推荐方案仅仅依靠工人的可信度。

3  实验分析

数据集采用大学生数学建模竞赛中公开的数据集，工人1-20信誉度从高至低且地理位置相对集中。根据图4的数据，我们可以清晰地看到任务16-20与20个工人计算的V值的最大波动有所体现，但总体来说波动在可接受范围之内。

图5为20个任务中所推荐的工人（系列）V值均大于0，虽然会有其他元素影响V值，但是在每个系列中其V值的波动同时也在可接受范围内。这体现出算法的稳定性较好。

图6和图7中在与随机算法进行对比时，不难发现，在信誉度方面随机值选取相对波动较大，本文的算法计算值较平稳。在距离方面本文算法距离控制在27-81这个稳定的区间内，而随机匹配的工人任务间的距离值较大，综上所述本文提出的算法较好。

4  结论

本文提出基于工人信誉度和距离的任务分配算法，能够有效地对问题进行求解。对工人进行选择时，需要对工人综合得分进行计算，根据工人的得分排序来选择工人。实验表明，使用Kevin算法可以更好地处理带工人信誉度的空间众包任务分配问题。

虽然Kevin算法综合表现良好，但是也存在一定的不足之处，仍需要进一步研究并改进。比如每个系列与任务所对应的位置波动的限制数还是不够明确，比如在距离的计算中，我们采用了经纬度算法，而实际上应该更为复杂，还要根据地理条件、时间以及交通状况来定。本文在分配不成功的任务处理上不够完善，还应该具备反馈功能，通过反馈的方式动态调整工人，将任务的等级包含进来是下一步研究重点。

参考文献：

[1]http：//www.crowdcloud.com/.

[2]http：//blog.csdn.net/yuanxing14/article/details/41948485.

[3]于德安.众包任务分配算法的改进与应用[D].大连海事大学，2016.