高丽萍,张祥磊,高 丽
1(上海理工大学 光电信息与计算机工程学院,上海 200093)
2(复旦大学 上海数据科学重点实验室,上海 200093)
3(上海理工大学 图书馆,上海 200093)
近年来,移动设备的普遍性和用户的移动性推动共享经济的发展,在这种经济中,工作者接受平台上发布的且感兴趣的任务,以换取一定的报酬.这也促成一种新的分布式问题的解决模式——空间众包.空间众包在现实世界中有很多应用,比如报告超市特定产品的价格,在固定地点拍照或现场验证数据[1].它的显著特点是要求工人在特定的时间前往某个地点或某个区域完成任务.
以往的多数研究是基于点任务研究任务分配的,比如外卖配送,固定地点拍照等.大多数的点任务只需要一人就可以完成,但是区域任务[2]的特点一般为面积大,执行过程复杂且困难,如公园空气污染检测,检测某条道路的交通动态以及收集某地区的噪声等,而像这种任务还需要大量的响应来确保最终结果的准确性,所以区域任务需要多个工人去执行.由于人力资源有限,这就需要为一个工人分配多个任务或一个任务由多个工人来完成高质量,低响应的区域任务.此外,区域任务还会涉及到跨区域的问题,为了鼓励用户接受跨区域的众包任务,可以通过相应的激励策略来鼓励用户接受跨区域任务.
在当前的云计算和大数据的背景下,不同功能的边缘设备可以通过自身携带的传感器与任务分配中心的服务器进行协作[3].由于边缘设备和远程的主服务器之间的距离较远,这会增加边缘设备的延迟.在这种情况下,众包任务的参与者在不同时间不同地区参与众包过程,使得众包的范围不断扩大,从而大量的数据涌入到主服务器,当中心服务器发生宕机时,会造成短时间内服务不可用.由于会产生低时延和服务不可用的问题,提出一种利用从服务器来解决这一问题的方案,从服务器具有灵活性和可扩展性,可以帮助众包平台通过不同的节点协调不同区域的任务.这样既能解决边缘设备与服务器的低时延问题,还可以避免主服务器造成单点故障时服务不可用的问题.
空间众包的任务分配可以分为离线分配和在线分配模型[4],离线分配是指在分配前已经获取到工人和任务的所有信息(如到达顺序,地点等),但是这种离线模型没有考虑到动态工人和任务的移动性,而且在一些实际场景中并不可用.在在线任务分配过程中,工人或任务的数量是高度波动的,而任务请求必须在特定的时间内提供响应,由于本文研究对区域任务进行任务分配,区域任务和工人的信息是未知的,所以本文研究的是一个在线分配问题.
与先前的空间众包研究不同,跨区域在线多任务分配(Cross Regional Online Multi-task Allocation,CROMA)问题需要设计一种在预算和时间约束下,能够保证质量得分的区域任务在线分配方法,该方法需要将未来时间到达的工人或任务考虑其中进行任务分配,并且如果同一区域内存在剩余任务,将会进行一个跨区域分配,保证每个任务能够完成.具体来说,本文贡献如下:
·本文提出在预算和时间约束下,通过工人移动来跨区域接受任务的问题,并设计了一个基于边缘服务器的在线任务分配框架来将空间众包活动分成多个阶段.该框架通过最大化工人完成任务所产生的质量分数来选择合适的工人任务分配对.
·针对CROMA问题,对系统框架的多个阶段提出对应的算法.首先,通过历史的离线数据对任务和工人进行预分配,提出一种预分配算法用于后续的在线算法.然后,根据预分配结果和工人的可移动性,进行同一区域内分配和全局分配,提出一种基于移动工人预分配的在线多任务分配,该算法中通过激励机制鼓励工人接受跨区域的任务.由于本文的研究重点是区域任务的任务分配,所以提出一种任务分解算法将区域任务分解为多个子区域,最终通过粒子群优化算法来完成最终分配.
·最后,在不同的预算,不同最大可接受任务数,不同工人数量,不同任务数量以及激励机制的权重参数不同的情况下,通过真实数据集对提出的算法在总质量得分和运行时间方面与4种其他算法进行了评估,从而验证了本文算法的有效性和效率.
Boutsis等人[5]提出了一种离线任务分配方法,该方法满足最大化众包任务中正确响应的概率和在任务期限内接收响应的概率,但这对于执行需要实时信息的空间任务是不现实的.Xia等人[6]为了使供应链平台寻找利润最大化的任务分配,提出了利润驱动任务分配问题,并建立了一个带有任务时间约束的任务定价模型,通过一种基于树分解位置的优化算法来实现最优分配.在平台的预算约束下,为了最大化工人任务分配对的数量,Liu等人[7]提出了一种基于阈值的贪婪算法,该算法利用随机生成的阈值来剪枝具有较大预算成本的匹配对,随后对该算法进行了改进,使其从历史数据中学习最优阈值来剪枝高成本的匹配对.Menatalla等人[8]讨论了移动众包系统中多工人多任务分配问题,提出了一个基于组的多任务工人选择的模型,通过遗传算法将一组工人分配给任务集群,再使用禁忌搜索算法将工人分配给集群内的单个任务来最大化任务完成质量和最小化任务完成时间.
上述的算法是基于离线数据进行的全局任务分配,虽然依据离线数据会产生好的效果,但是实际上,空间众包中的大多数任务分配都是使用在线任务分配模型.
在线任务分配是指预先未知工人和任务的信息,来进行工人和众包任务的分配.为了保证任务分配的全局最优,本文目标是通过考虑当前和未来工人/任务来进行全局分配.Cheng等人[9]定义一个最大质量任务分配(MQA)问题,设计了一种基于网格的预测方法来预测未来工人/任务的空间分布,将在线场景转换为离线场景,从而达到已知工人或任务的信息,并提出了MQA贪婪算法和MQA分治算法去解决该问题.为了保证任务分配的总体质量,Miao等人[10]研究了移动众包中的质量感知在线任务分配(QAOTA)问题,提出了一个测量任务质量的概率模型和描述工人行为的搭便车模型.Qian等人[11]过将在线场景转换为离线场景,提出了一种自适应批处理机制,使用合适的时间戳,将分配过程划分为多个时间间隔,每个时间间隔的工人和任务的信息是已知的.Chen等人[12]在动态场景下研究了最小化最大延迟空间众包(MMD-SC)问题,其中考虑到了工人的旅行成本和任务的缓冲时间,提出了一种基于空间嵌入的双边在线随机算法.在Boutsis等人[5]的研究中,提出了一种多目标在线任务分配机制,该机制利用遗传算法来识别任务和工人之间的最佳匹配,从而使平台和工人的效用最大化.
边缘服务器是建立在边缘计算器上的服务器.基于云计算技术和边缘计算能力,边缘服务器可以作为主服务器的延展,将计算,存储等服务扩展到边缘服务器上.边缘服务器可以实现多种功能,包括存储,通信等.Li等人[13]通过提出一种在超密集网络中部署边缘服务器的优化部署和分配策略,以最小化服务提供商的成本并保证服务完成时间.Wang 等人[14]关注如何在城市中通过边缘服务器来优化移动边缘计算网络性能,文章将该问题描述为一个多目标约束优化问题,目标是平衡边缘服务器的负载并最小化移动用户与边缘服务器之间的访问延迟.Zhang等人[15]提出了一种基于预测的在线任务分配算法,该算法是一种双阶段图形驱动的双边分配策略,通过边缘服务器和二部图来完成任务分配.
在本节中,本文将介绍使用的相关定义和系统框架,并且定义了本文所解决的问题.
定义1.动态工人
空间众包系统中包括一组众包工人,表示为w∈W,他们在平台注册后接收和完成v任务请求者发布的任务,每个工人都与一组属性相关联,这些属性表示为w=〈lw,rw,nw,vw,bw〉,其中lw表示工人当前的位置,rw表示工人可接受的任务范围的半径,nw表示工人可以接受的最大任务数,vw表示工人的移动速度,bw表示工人在bw时进入平台.在本文中,假设工人在任意时刻可以自由的加入或离开众包系统.
定义2.区域任务
请求者发布在空间众包系统中的每个区域任务t∈T都与一组属性关联,这些属性为t=〈idt,lt,areat,σt,bt,et〉,其中idt表示任务的唯一标识符,lt表示任务进入平台所指的位置,areat表示该区域任务的面积,σt表示完成该任务所需的时间,bt和et分别表示任务在bt时刻进入平台,需要在截止时间et之前完成.
定义3.工人任务分配集
在本文中假设每个工人可以接受多个任务,一个区域任务也可以被多个工人接受.工人任务分配集Cp是由一组工人集W和一组区域任务集T中选择合适的工人和任务形成匹配对产生的,形式为〈wi,tj〉,其中每个分配对都与一个质量分数q(wi,tj)(见定义3)和一个旅行成本bij所关联,如下:
bij=C×dis(lw,lt)
(1)
其中C为每英里的单位成本,dis(lw,lt)为工人和任务位置之间的距离.
定义4.整体质量得分
通过每个工人对任务的距离和时间的不同权重来计算完成任务的质量分数:
(2)
Q(w,t)=∑∀〈wi,tj〉∈Cpq(wi,tj)
(3)
定义5.激励机制
为了鼓励工人可以接受跨区域的区域任务,本文提出了一种激励工人的机制:
E=ε×disw+θ×timew
(4)
其中,E为每个跨区域接受任务的工人能得到的额外原始质量的百分比,ε为工人与跨区域任务的距离权重,θ为工人与跨区域任务的时间权重,disw为工人跨区域接受任务时移动的距离,timew为工人跨区域完成任务时花费的时间.
定义6.跨区域在线多任务分配问题(CROMA)
给定一组区域任务T和一组工人W,所有的工人都是动态地到达空间众包平台,并在不同的区域完成任务.图2显示了本文的任务分配框架.CROMA问题是在给定的区域任务T和工人W之间找到最优的工人任务匹配对,使其满足任务质量得分Q(w,t)最大化,即:
maxQ(w,t)
(5)
约束条件为:
(6)
∑∀〈wi,tj〉∈Cpbij≤B
(7)
约束1为每个工人接受任务的数量不能超过他们可接受的最大任务数nw,约束2为在每一时刻,所分配工人的总体旅行成本不超过预算B,本文的区域任务分配框架如图1所示.
图1 区域任务分配框架Fig.1 Regional task allocation framework
本节将通过一系列的算法来解决区域任务分配过程.
本节首先通过历史的离线数据对任务和工人进行预分配,即对当前时刻的工人和任务的信息是已知的,在它们之间进行预分配,将产生的分配对用于后续的在线算法.
首先匹配在同一区域的工人和任务,在所有已知的工人集W和任务集T之间进行一个预分配,并且删除不满足约束的预分配.此时需要去计算每个工人所接受的任务数是否超过nw,如果工人所接受的任务数超过最大的任务数,则删除分配对中质量分数较低的对,以确保任务的质量(1~12行).对没有超过最大的任务数的工人进行如下操作,对所有区域的工人和未分配的任务进行分配,将不再同一个区域的工人和任务的分配删掉,保留满足约束的分配对.在这次匹配中,工人是可以自由移动的,所有这次匹配可以将同一区域内没有分配成功的任务与工人进行匹配,在匹配过程中也要保证约束条件(13~29行).至此,该算法得到工人和所有任务的预分配对.算法1描述具体的分配过程.
算法1. Pre-allocation Algorithm(PA)
输入:工人集W,任务集T
输出:预分配结果集N
初始化:L=Ø,Tunassign=Ø
1.for eachwa∈Wdo
2. for eachtb∈Tdo
3. get a match pair 〈wa,tb〉
4. if(∑∀〈wi,tj〉∈Cpbij)+bab≤Bandnwa 5. add 〈wa,tb〉 toL 6. continue 社区学习共同体作为社会资本是社区治理的基础性力量,其能力大小关乎社区治理水平和效能。要通过提炼社区学习共同体社区治理的核心要素,作为衡量和评价其社区治理能力的指标要素。 7. else 8. delete the match pair 9. end if 10. end for 11.Tunassign← unassigned tasks 12.end for 13.for eachw∈Wdo 14. for eacht∈Tunassigndo 15. line 3-line 11 16. end for 17.Tunassign←unassigned tasks 18.end for 19.for eachw∈Wdo 20. for eacht∈Tunassigndo 21. if w and t don′t belong to the same area then 22. delete the match pair 23. end if 25. get a match pair 〈w,t〉 26. add 〈w,t〉 toL 27. end if 28. end for 29.end for 30.N←L 31.returnN 由于每个工人都有自己的活动范围,并且工人不能接受超出该范围的任务,但工人是可以自由移动的,因此设计一种基于移动工人的跨区域在线算法,使工人可以跨区域的去接受任务.针对算法1形成的预分配对,本文提出一种在满足预算的情况下,实现整体质量得分最大的算法,见算法2,该算法首先会对同一区域的工人和任务进行分配,如果无法生成匹配,则将未分配的任务添加到每个区域未完成的任务顺序中,然后在所有区域之间进行全局分配.如果在全局分配后存在剩余任务,那么从算法1得到的预分配结果中选择工人,即从预分配的分配对中选择工人来完成该任务. 算法2. Cross-regional Allocation Algorithm based on Mobile Workers(CRMW) 输入:工人集W,任务集T,预分配结果集N 输出:分配结果集S 初始化:Tunassign=Ø 1.for eachregioni(i=1,2,3…) do 2. for newly arrived worker(task)i do 3. Get all candidate sets for worker(task)i 4. if ∑∀〈wi,tj〉∈Cpbij+bwt≤Bandni 5.S←〈i,j〉 6. end if 7.Tunassign← unassigned tasks 8. if i cannot form a match then 9. line 13 10. end if 11. end for 12.end for 13.for each workerwin different regions do 14. for eacht∈Tunassigndo 15. get a match pair 〈w,t〉 16. if ∑∀〈wi,tj〉∈Cpbij+(bwt+bwtE)≤Bandn 17.S←〈w,t〉 18. else 19. continue 20. end if 21.Tunassign← unassigned tasks 22. end for 23.end for 24.for each workerwin different regions do 25. select workers from N to complete the task 26. get a match pair 〈w′,t′〉 27. if ∑∀〈wi,tj〉∈Cpbij+bw′t′≤Bandnw′ 28.S←〈w′,t′〉 29. end if 30.Tunassign← unassigned tasks 31.end for 32.returnSandTunassign 33.jump to line 2 在算法2中,为了能使工人更好的接受跨区域的任务,本文利用定义5的激励模型来为工人支付额外的奖励,在算法2中的第16行,即:bwt+Ebwt,其中bwt为工人接受该任务所得到的报酬,Ebwt为工人接受跨区域任务所得到的额外奖励.只要保证不超过预算约束,就可以将其作为一个分配对.如果超出预算约束,则将该任务在下一轮分配中,去选择后续到达的工人去完成. 由于区域任务的特点一般为面积大,执行过程复杂且困难,所以本文将区域任务分解为多个子区域,然后将每个子区域分配给工人执行,这样可以在人力资源有限的情况下,保证响应结果的速度.算法3对分解算法进行了具体描述. 算法3. Regional Task Decomposition Algorithm(RTDA) 输入:区域任务T 输出:按优先级排列的任务集合C 1. for regional tasktarrives do 2. initializationC=Ø 3. caculate the center position of the task 4. take the shape of the task as a regular shape 5. divide the area into multiple subregions 6. for each subregion do 7. caculate the center position of each subregion 8. caculate the distance between the center position of task and the center position of subregion 9. end for 10. take the distance as the priority and sort from small to large 11. add to the setC 12. end for 13. returnC 该算法是将任务请求者提交的区域任务分解为一个按优先级排列的子区域任务的集合,然后将子区域单独分配给每个工人,算法会从地图运营商收集区域任务的形状,大小等指标来对区域任务进行分解.该算法的输入为区域任务,输出为按优先级排列的任务集合C.首先初始化集合为空,对区域任务计算其中心的位置,然后将其转化为规则图形,按照数学方法将区域划分为大小相近的多个子区域,每个区域作为一个任务,计算每个子区域的中心位置与整个区域中心位置的距离(3~8行).然后将该距离作为优先级对任务进行排序,将排序结果加入到集合C中.其中,距离越小优先级越高,表示会为该区域优先分配工人. 由于算法2为每个区域任务都分配了一定数量的工人,并且在算法3中将区域任务进行分解,所以本小节的目的是从给定数量的工人中为子区域任务进行匹配,通过粒子群优化算法来实现工人和子任务的分配.在PSO算法中,使用两个公式更新第k次迭代时粒子的位置和速度,公式如下: (8) (9) 其中δt为单位的时间步长值,r1和r2表示[0,1]间的随机数,c1,c2表示自我认知因子和社会经验因子,w为惯性因子.粒子的速度更新主要由3部分组成,第1项与惯性因子w有关,较大的惯性因子会使算法可以进行全局探索,较小的惯性因子会使得粒子速度集中在搜索空间的局部区域;第2项和第3项分别为粒子的自我认知部分和社会经验部分. 由于本文在算法2中,按照约束对工人和任务形成的分配对,所以在该部分无需任何约束,只需按照质量分数为子任务分配更合适的工人即可,所以适用于标准的粒子群优化算法.根据前文,适应度函数为: f(x)=α×dis(w,t)+β×σ(w,t) (10) α和β分别为权重参数,将在后续实验中介绍.算法4描述了对每个区域任务进行分解后,通过标准粒子群优化算法为生成的子区域分配工人的具体过程. 算法4. Particle Swarm Optimization Algorithm(PSO) 输入:按优先级排列的任务集合C,工人集合W 输出:分配结果M′ 1. generate initial swarm with the particle positionXkand velocities randomlyvk 2. caculate the value of fitness function 3. determine first global best of the swarm 4. whilek≤ maxiteration do 5. update position usingeq.(8) 6. update velocity usingeq.(9) 7. caculate the value of fitness function usingeq.(10) 8. determine best local for each particle 9. determine best global in the swarm 10. update the best global 11. end while 12. returnM′ 由于该算法的适应度函数是根据定义4中每个工人对任务的质量分数公式而来,所以在算法迭代的过程中,对适应度函数的全局最优相当于对质量分数的全局最优选择. 本节使用真实数据集测试本文提出的一系列算法.对于真实数据集,本文采用的是Foursquare签到数据集[16].在Foursquare数据集中,可以通过API获取到该数据集的相关信息:2153471个用户,1143092个场所,1021970个签到记录.本文从中选取6231个工人和19284个任务,首先初始化一部分的工人和任务到众包平台中,随后为每个工人和任务随机设置到达时间,以及离开平台的时间.在实验过程中,从总质量得分和运行时间两个方面作为算法的评估结果进行比较分析. 本文的实验是在配备 Intel(R)Core(TM)i7-7820X CPU @ 3.60 GHz 和 64GB 的机器上进行的,采用的编程语言为Python3.7.在实验中,假设区域任务只会出现在活动范围内或不在活动范围内两种情况.本文会通过改变每个阶段的算法来与本文提出的算法进行比较,基于此可以提出四种对比算法:1)通过贪婪算法进行分配,对区域任务进行分解,最后对子区域任务使用粒子群优化算法再次分配,记为G-D-P;2)通过基于移动工人预分配的在线分配算法进行分配,对区域任务进行分解,最后对子区域任务使用贪婪算法进行再次分配,记为P-D-G;3)通过贪婪算法进行分配,对区域任务进行分解,对子区域任务使用贪婪算法进行再次分配,记为G-D-G;4)通过基于移动工人预分配的在线分配算法进行分配,对区域任务进行分解,最后对子区域任务使用随机算法进行再次分配,记为P-D-R.本文根据总质量得分和运行时间来评估所有算法,并研究了不同参数对其性能的影响,在后续实验中,距离权重α,时间权重β经多次实验的最优值设置为0.8和0.7,具体参数的设置如表1所示. 表1 实验参数设置Table 1 Experimental parameter setting 本节将对提出的算法和其他4种算法在总体质量得分和运行时间方面进行比较,通过每次改变一个参数,同时将其他参数设置为默认值来进行对比实验.下面将从工人数量,任务数量,预算和工人可接受的最大任务数4个方面的变化情况对总体质量得分和时间进行评估. 5.2.1 不同的工人数量 在图2中,给出了5种算法在不同的工人数量时的总体质量得分和运行时间的变化情况,其他参数的默认值设置为表1中的加粗值.图2(a)表明了随着工人数量的增长,总体质量得分的变化情况,可以得到5种算法的总体趋势都是在增加.这是随着工人数量增加,工人任务分配对的数量同时也在增加,从而总体质量得分增加.由于工人数量增加,且P-D-G和P-D-P都包含工人跨区域接受任务,所以总体质量得分要比其他算法高.图2(b)表明5种算法的运行时间都随着工人数量的增加而增加.由于P-D-P和G-D-P使用了PSO算法,该算法的时间复杂度和迭代次数有关,迭代次数和工人或者任务的数量有关,所以运行时间会随着规模的增加而增加,但运行时间是可控的,而且PSO的优化效果会随着迭代次数的增加不断变化,考虑到这种情况,需要尽可能的增加其迭代次数来保证得到全局最优的结果. 图2 不同工人数量下算法的比较Fig.2 Comparison of algorithms with different numbers of workers 5.2.2 不同的任务数量 图3给出了5种算法在不同的任务数量时的总体质量得分和运行时间的变化情况,其他参数的默认值设置为表1中的加粗值.图3(a)表明了随着任务数量的增长,总体质量得分的变化情况,可以看出随着任务数量增加,得到的分配对数量也会增加,故总体质量分数也在增加,其中P-D-P的效果最显著.图3(b)表明了算法的运行时间随着任务数量的增加的变化情况,由于任务数量增加,工人任务分配对数量在增加,系统进行分配的时间也在增加,故5种算法的运行时间也不断增加.由于P-D-R使用了随机算法,所以运行时间是最快的,P-D-P和G-D-P使用了PSO算法,故运行时间要比其他算法长,具体原因同上. 图3 不同任务数量下算法的比较Fig.3 Comparison of algorithms with different number of tasks 5.2.3 不同的预算 该部分给出了算法在不同预算下的总体质量得分和运行时间的变化趋势,其他参数的默认值设置为表1中的加粗值.图4(a)表明了随着预算的增加,总体质量分数的变化情况.可以得到5种算法的质量得分都随着预算的增加而增加,由于预算的增加,产生的工人任务分配对的数量也会增加,所以总体质量分数会变大.还可以看出本文提出的算法产生的总体质量分数要比其他4种算法高,其次是P-D-G,这是因为本文的算法激励工人跨区域接受了未分配的任务,从而质量分数要比其他算法高.图4(b)表明了随着预算的增加,运行时间的变化情况.因为预算的增加,未分配成功的任务可以更好的找到工人进行跨区域完成,所以P-D-P和P-D-G的运行时间要比其他算法的运行时间长. 图4 不同预算下算法的比较Fig.4 Comparison of algorithms under different budgets 5.2.4 不同的工人最大可接受任务数量 图5给出5种算法在不同的工人最大可接受任务数量时的总体质量得分和运行时间的变化情况,其他参数的默认值设置为表1中的加粗值.图5(a)可以得到5种算法都随着工人接受的最大任务数量的增加而增加,由于每个工人可接受的任务变多,完成的任务数量是增加的,所以总体质量分数是增加的.还可以看出使用跨区域在线分配的算法效果要比其他算法好,这是因为工人跨区域接受任务,任务得以完成,从而得到相应的质量分数.图5(b)表示的是5种算法运行时间的变化情况,由于每个工人可接受的任务数量变多,即为工人分配的时间也会变长,算法的运行时间也会增加. 图5 不同工人最大接受任务数下算法的比较Fig.5 Comparison of algorithms under the maximum number of tasks accepted by different workers 本文考虑在预算和时间约束下,最大化总体质量的区域任务在线分配问题,基于此提出一个多阶段的区域任务在线任务分配框架,框架中在不同阶段提出不同的算法为其选择合适的工人,首先通过跨区域在线分配算法为每个区域任务分配一定数量的工人,且该过程中设置了激励模型来鼓励工人跨区域接受任务,然后通过任务分解算法将区域任务分解为多个子区域任务,最后使用粒子群算法来对子区域任务进行分配工人.本文通过真实数据集进行实验,与其他4种算法进行对比,证明本文算法的有效性. 在未来的工作中,本文将考虑在工人提交任务后,如何准确地评估工人的响应结果的质量,并对提供质量较差的工人的能力进行一次重新评估,以便用于以后的任务分配,从而保证任务的质量.4.2 区域任务分解算法
4.3 子区域任务分配算法
5 实 验
5.1 实验设置
5.2 实验结果
6 总结与展望