基于动态阈值的时空众包在线分配算法  

Spatiotemporal crowdsourcing online task allocation algorithm based on dynamic threshold

作　　者：余敦辉 袁旭 张万山 王晨旭 YU Dunhui;YUAN Xu;ZHANG Wanshan;WANG Chenxu(College of Computer and Information Engineering,Hubei University,Wuhan Hubei 430062,China;Hubei Provincial Education Informationization Engineering and Technology Center,Wuhan Hubei 430062,China)

机构地区：[1]湖北大学计算机与信息工程学院,武汉430062 [2]湖北省教育信息化工程技术中心,武汉430062

出　　处：《计算机应用》2020年第3期658-664,共7页journal of Computer Applications

基　　金：国家自然科学基金资助项目(61572371,61832014);湖北省技术创新重大专项(2018ACA13)~~

摘　　要：为提升时空众包动态现实场景中任务分配总效用,提出一种基于在线随机森林的动态阈值算法(DTRF)。首先,根据众包平台中工人和任务的历史匹配数据初始化在线随机森林;然后,通过在线随机森林预测每位工人期望的任务回报率作为阈值,按阈值为每个工人选取候选匹配集;最后,从候选匹配集中选取当前效用总和最高的匹配,同时用分配结果更新在线随机森林。实验结果表明,所提算法在提升总效用的同时有效地提高了工人的平均收益。与贪心算法相比,所提算法的任务分配率提升了4.1%,总效用提升了18.2%,工人平均收益提升了11.2%。与随机阈值算法相比,所提算法在任务分配率、总效用、工人平均收益等方面都有较好的提升,且稳定性更好。In order to improve the total utility of task allocation in spatiotemporal crowdsourcing dynamic reality,a Dynamic Threshold algorithm based on online Random Forest(DTRF)was proposed.Firstly,the online random forest was initialized based on the historical matching data of workers and tasks on the crowdsourcing platform.Then,the online random forest was used to predict the expected task return rate of each worker as the threshold,and the candidate matching set was selected for each worker according to the threshold.Finally,the matching with the highest sum of current utility was selected from the candidate match set,and the online random forest was updated based on the allocation result.The experiments show that the algorithm can improve the average income of workers while increasing the total utility.Compared with the greedy algorithm,the proposed algorithm has the task assignment rate increased by 4.1%,the total utility increased by 18.2%,and the average worker income increased by 11.2%.Compared with the random threshold algorithm,this algorithm has a better improvement in task allocation rate,total utility,average income of workers with better stability.

关 键 词：时空众包 在线任务分配 分配总效用 在线随机森林 动态阈值算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]