基于团队影响力感知的空间众包任务分配算法研究.pdf

摘要

摘要

随着带有GPS功能的智能设备的普及和无线网络技术的发展，空间众包作为

一种将包含位置信息的任务分配给移动工人的框架，在近年来受到了广泛关注。

在现实世界场景中，面对多样化和复杂性的增加，存在一些任务的执行可能不由

单一工人独立完成。相反，这些任务通常需要多个工人的协作和共同努力，这种

工作模式被称为团队任务分配。然而，以公平的方式满足所有工人团队的任务分

配仍然是一个挑战。目前主流的团队任务分配方法主要是通过挖掘工人团队之间

的相互信息来计算出团队的任务偏好，从而基于偏好来进行团队任务分配。然而

这些团队任务分配方法并没有充分的考虑到团队工人的历史时空信息，导致最终

的团队任务分配效果不够理想。和以往的方法相比，本文充分的挖掘工人团队的

历史时空信息，并将社会影响力分析的思想运用到团队任务分配之中。在社交网

络中，团队里的工人能够通过社交媒体来获取和传播信息，社交影响力高的团队

自然有更高的概率被分配到任务，因此将团队的社交影响力纳入到任务分配环节

是可行有效的。根据这种思想，本文提出了一个新颖的基于团队影响力感知的任

务分配框架，包括两个部分：团队任务影响力建模和基于影响力的团队任务分配。

具体而言，团队任务影响力建模部分旨在计算出当前时刻的团队任务影响力，用

于解决团队任务影响力的计算问题，其计算过程由三部分组成：分别是根据团队

的执行任务历史记录得到的团队任务偏好、根据团队的历史位置信息得到的团队

任务意愿以及通过社交网络影响力分析得到的团队传播任务信息能力。基于团队

影响力感知的任务分配部分具体采用了树分解的最优任务分配算法来解决团队任

务分配的问题，在计算出团队任务影响力的基础上，将任务分配给适当的团队。在

这一部分中本文将团队影响力与团队工人的位置以及团队工人到任务位置距离相

结合，在基于团队影响力的任务分配算法上又提出了两种算法，并将根据这些算

法来设置对比实验。最后，通过大量实验验证，较之于没有考虑团队任务影响力

的任务分配算法，将团队任务影响力纳入到团队任务分配的过程后，算法在CPU

时间、任务分配数量和平均影响力这三个指标上均有大幅提升。

关键词：空间众包，团队任务分配，团队任务影响力，树分解

I

ABSTRACT

ABSTRACT

WiththewidespreadavailabilityofGPS-enabledsmartdevicesandtheadvancement

ofwirelessnetworktechnology,SpatialCrowdsourcing,asaframeworkforassigning

location-basedtaskstomobileworkers,hasgarneredsignificantattentioninrecentyears.

Inreal-worldscenarios,withincreasingdiversityandcomplexity,sometasksmaynot

becompletedbyasingleworkeralone.Instead,thesetasksoftenrequirethecollabora-

tionandjointeffortofmultipleworkers,aworkmodeknownasgrouptaskassignment.

However,fairlysatisfyingallworkergroupswithtaskassignmentsremainsachallenge.

Currentmainstreammethodsofgrouptaskassignmentprimarilycalculategroupprefer-

encesbyminingmutualinformationamongworkergroups,andthenassigntasksbasedon

thesepreferences.However,thesegrouptaskassignmentmethodsd