考虑工人培养的移动群智感知任务分配机制_吕翊_.pdf

考虑工人培养的移动群智感知任务分配机制吕 翊 王 燕 崔亚平*何 鹏 吴大鹏 王汝言(重庆邮电大学通信与信息工程学院 重庆 400065)(先进网络与智能互联技术重庆市高校重点实验室 重庆 400065)(泛在感知与互联重庆市重点实验室 重庆 400065)摘 要：移动群智感知(MCS)通过大量感知工人的移动性和工人随身携带的感知设备来收集数据，是一种新的大规模数据感知范式。现有大量研究致力于解决移动群智感知中的任务分配问题，使感知数据质量得以提高，但忽略了缺乏优质工人的感知任务，导致任务完成质量降低。为了解决上述问题，对于缺乏优质工人的感知任务，该文关注将经验不足的工人培养为优质工人，并令其执行这些感知任务，实现工人的长期复用，提高感知数据质量和长期平台效用。具体来说，该文考虑了缺乏优质工人的感知任务所需的能力和工人的能力类型，并据此应用稳定匹配算法选择待培养工人，提出一种基于能力聚合和半马尔可夫预测的多阶段工人选择培养(MWSD)算法。结果表明，相比基于区块链的非确定团队协作(BNTC)算法，该文所提算法能够有效将缺乏优质工人的感知任务的数据质量提高24%，长期平台效用提高17%。关键词：移动群智感知；任务分配；工人培养；工人选择中图分类号：TN929.5文献标识码：A文章编号：1009-5896(2023)04-1505-09DOI:10.11999/JEIT220249Worker Development-Aware Task Allocation Strategyin Mobile Crowd SensingL Yi WANG Yan CUI Yaping HE Peng WU Dapeng WANG Ruyan(School of Communication and Information Engineering,Chongqing University of Posts andTelecommunications,Chongqing 400065,China)(Advanced Network and Intelligent Connection Technology Key Laboratory of Chongqing EducationCommission,Chongqing 400065,China)(Chongqing Key Laboratory of Ubiquitous Sensing and Networking,Chongqing 400065,China)Abstract:Mobile Crowd Sensing(MCS)is a new paradigm that collects sensing data via the mobility ofmassive workers and carried sensing devices.Current works focus on the task allocation issue and improvingsensing data quality.However,they ignore the sensing tasks lacking qualified workers and decrease the taskcompletion quality.To tackle the above problem,for sensing tasks that lack qualified workers,inexperiencedworkers are developed to qualified workers and execute these tasks.As a result,the qualified workers can long-term execute these tasks,and the sensing data quality and long-term platform utility are improved.Furthermore,both the capacities that sensing tasks need and the capacities that workers own are considered.According the above capacities,first,a stable matching algorithm is applied to select workers to be developed.And then a Multi-stage Worker Selection and Development(MWSD)algorithm is proposed based on capacityfusion and Semi-Markov prediction.The results show that compared to Blockchain-based Nondeterministic 收稿日期：2022-02-15；改回日期：2022-07-30；网络出版：2022-08-04*通信作者：崔亚平基金项目：国家自然科学基金(61771082,61801065,61871062,61901070,62061007,U20A20157)，重庆市教委科学技术研究项目(KJQN201900611,KJQN202000603)，重庆市高校创新研究群体(CXQT20017)，重庆市自然科学基金(cstc2020jcyj-zdxmX0024,cstc2021jcyj-msxmX0892)Foundation Items:The National Natural Science Foundation of China(61771082,61801065,61871062,61901070,62061007,U20A20157),The Science and Technology Research Program of Chongqing Municipal Education Commission(KJQN201900611,KJQN202000603),TheUniversity Innovation Research Group of Chongqing(CXQT20017),The Natural Science Foundation of Chongqing(cstc2020jcyj-zdxmX0024,cstc2021jcyj-msxmX0892)第45卷第4期电 子 与 信 息 学 报Vol.45No.42023年4月Journal of Electronics&Information TechnologyApr.2023Teamwork Cooperation(BNTC)algorithm,the mechanism can improve the data quality of sensing taskslacking qualified workers by 24%and long-term platform utility by 17%.Key words:Mobile Crowd Sensing(MCS);Task allocation;Worker development;Worker selection 1 引言近年来，移动群智感知(Mobile Crowd Sens-ing,MCS)成为一种有吸引力的感知和收集数据范式，鼓励普通市民通过自身携带的智能设备感知或生成数据，然后将数据在云端聚合1。MCS的目的是完成对数据的群体智能提取和以人为中心的服务交付2。如今，MCS的应用更加广泛，在路况检测3、室内定位4等方面发挥了重要作用。典型的MCS由3部分组成：任务请求者、平台和工人1。MCS的运行需要大量携带感知设备的人群。当需要某些感知数据时，任务请求者向平台外包感知任务，或者平台生成一系列感知任务，此时平台需要招募大量工人来完成，工人利用随身携带的智能设备中内嵌的传感设备感知周围环境，获取并上传感知数据至平台，然后平台将感知数据进行处理，回传至任务请求者。任务请求者将数据质量反馈给平台，并向平台支付一定的报酬，平台根据数据质量给予工人对应的回报。支付过程结束，表示完成了1次感知任务的外包，以达到提高平台效用和感知数据质量等目标。MCS过程离不开有效的任务分配机制。任务分配在MCS中所起到的作用是将感知任务合理地分配给对应工人。现有研究提出了大量机制来解决任务分配问题510。文献5旨在解决多任务分配问题中任务完成质量低的问题，综合考虑了工人的空间覆盖率和感知准确度，提出了一种带有特定修复策略和新的遗传算子的大规模遗传算法。该工作未考虑执行感知任务的工人的充足性，导致任务完成质量降低。因此，文献6考虑了感知任务缺乏足够工人的情况，提出了一种分区域学习模型来为更合理的任务分配机制提供指导，根据感知任务的历史数据和时空联系来为任务提供工人，并且利用贝叶斯压缩感知来推测丢失的数据，最终保证了数据质量。然而，该工作忽视了任务的类型和工人对应的能力值。如果工人的能力值对于特定类型的任务较低，则工人提交的数据质量偏低。为解决上述问题，文献7考虑到工人的位置和经验值，同时考虑任务的种类，基于概率提高和熵减将任务分配问题转化成在线选择工人与任务对的问题，以提高感知数据质量。文献8对同一工人完成不同任务的能力进行区分，提出了一种动态任务分配模型，二次招募能够高质量完成某类任务的工人，提高感知任务的感知质量。上述文献未考虑不同任务种类的相似性，若同一工人拥有多种任务所需的能力类型，则此工人可完成多个任务。所以文献9考虑了任务之间的关联，即一个工人可以完成两个相似的任务。同时令多个工人进行协作来收集大量的感知数据副本，以获取高质量感知数据。然而上述研究忽略了工人的可培养性。文献10考虑了工人的社交关系，利用社交关系中其他工人的影响值来培养工人对于感知任务的参与度，提出了一个考虑工人社会影响值的两阶段博弈收益模型，以提高工人的整体参与度和回报。但这项工作没有考虑不同工人之间能力类型的差异。上述文献旨在提高感知数据质量，然而在真实场景中，并非所有的任务都能由充足的优质工人来完成，导致任务完成质量降低。此外，未考虑工人拥有多种能力类型，也未考虑一个感知任务需要多种类型的能力值才能高质量完成，忽略了工人能力的可培养性，导致所提机制的感知数据质量和长期平台福利降低。为了解决上述问题，本文考虑了优质工人不足的情况下如何将平台发布的感知任务高质量完成的问题，对于优质工人不足的感知任务，平台为其招募大量经验不足的工人并对他们进行培养，培养结束后，这些工人会拥有完成平台发布的所有类型感知任务的能力。此外，设计了一个工人选择培养机制并提出相应算法，具体划分为两步：选择工人和培养工人。平台首先对经验不足的工人进行选择，以获得可培养的工人集合。然后令可培养的工人执行平台发布的不同类型的任务，平台在每一阶段都会根据工人在本阶段的名誉值和下一阶段的预测名誉值来选择能够进入下一阶段培养的工人，并在每个阶段都对任务请求者和工人定价。仿真结果显示，与现有的MCBS算法相比，本文机制能够将工人名誉值提高26%，将平台效用提高57%，以及将工人培养结束后的长期平台效用提高17%。2 系统模型为了高质量完成感知任务，平台按照任务的类型和工人的名誉值来选择工人。当完成某些类型任务的优质工人数量不足时，平台为这些任务选择擅长这几类任务的全部优质工人和大量经验不足的工人。优质工人是指在平台发布的所有类型的任务中表现良好的工人，他们拥有平台发布类型的任务所1506电 子 与 信 息 学 报第 45 卷需要的高能力值。而经验不足的工人指缺乏平台发布类型的任务所需能力值的工人。由于要最大化自身长期效用，平台需要对工人进行选择和培养，培养工人指经验不足的工人提高其较低或缺失的能力值的过程，令其执行缺乏优质工人的任务，提高这些工人对缺乏优质工人的任务的能力值。W=w1,w2,.,wi1,wi,.,wnR=r1,r2,.,ri1,ri,.,rkT=t1,t2,.,ti1,ti,.,tk设工人集合为，任务请求者集合为，对应的任务集合为，且每个任务对应不同的任务类型。假设每个任务请求者有一个任务，一个工人可执行多个任务。具体实现分为两个步骤：选择工人和培养工人。mmWe系统模型如图1所示。平台在发布任务后，工人首先根据自身偏好向任务发出申请。然后平台在选择全部优质工人后，根据完成任务需要的能力类型的初始匹配度和更新匹配度，应用GS(Gale-Shapley)算法11来根据任务对工人的偏好选择经验不足的工人，将选择的这部分工人定义为待培养工人集合。lG=g1,g2,.,gr1,gr,.,glD=T1,T2,.,TlK=k1,k2,.,kr1,kr,.,klt1(c1,c2,c3)w1选择工人结束后，本文将待培养工人的培养过程分为个阶段，表示为，对应每个阶段的持续时间为，且每个阶段都有一个名誉阈值，表示为。令所有待培养工人在每个阶段都执行平台发布的任务，并在每个阶段结束时，平台根据工人不同类型的能力值计算工人对于所执行类型任务的名誉值，同时预测下一阶段达到此类型任务名誉阈值的概率，最后利用本阶段工人质量是否达到阈值，以及达到下一阶段质量阈值的概率选择进入下一阶段培养的工人，直到培养结束。例如，假设任务 的内容为在特定商场识别化妆品和护肤品品牌12，此任务需要的能力类型分别为对商场的熟悉能力、对化妆品品牌、护肤品品牌的熟悉能力，用表示；工人拥有的能力为对商场的熟悉能力、对护肤品品牌、剃须刀品牌以及运动品牌(c1,c3,c4,c5)w1t1c2c1c3(c1,c2,c3)w1t1的熟悉能力，用表示。执行 结束后，会了解部分化妆品品牌，其 值会提高，同时和 值也会提高。在多个培养阶段执行此类型任务，培养结束后，若其值达到较高水平，则会成为对于 的优质工人。定价贯穿于工人培养过程。在每个培养阶段，平台都根据对任务请求者的初始定价以及工人的可培养性来对二者进行最终定价。每个培养阶段结束后，平台根据向任务请求者收取的费用与支付给工人的费用之差来确定自身收益，即平台效用。U=maxlr=1rjRqrjwiWpwis.t.lr=1Br B(1)llllBrrB本文旨在通过提高工人提交的数据质量来最大化长期平台效用，长期平台效用指在 个培养阶段结束后获得的平台效用之和，故长期平台效用式(1)表示。其中第1项是工人执行 个阶段的任务后平台向任务请求者收取的总费用，第2项是工人执行 个阶段的任务后平台支付给工人的总费用。括号内表示平台在某一阶段的净收益，即平台效用。长期平台效用指多阶段平台效用之和，故上式中长期平台效用表示为 个阶段的平台效用之和。表示平台在第 阶段的预算，表示平台总预算。3 解决方案 3.1 选择工人由于多个工人向同一任务发出执行申请，且任务请求者对收到申请的工人有不同的偏好。因此涉及如何进行多个工人的执行申请与任务请求者对工人的不同偏好之间的匹配。此外，在选择待培养工人时，若匹配完成后部分工人舍弃之前匹配的任务而与更满意的任务匹配，导致舍弃的任务得不到完成。因此，为解决上述问题，在选择经验不足的工 图 1 系统模型图第4期吕 翊等：考虑工人培养的移动群智感知任务分配机制1507人作为待培养工人时，本文应用Gale-Shapley算法为任务匹配工人。首先，在未匹配的任务和工人中，为这些任务分别暂时匹配其最偏好的工人，而拒绝其他提出申请的工人。所有在上一步未被匹配的工人再向其最偏好的任务提出匹配申请，任务必须是此工人未申请过的。然后，任务在上一步暂时匹配的工人和新申请的工人之间做出比较，并且暂时接受其最偏好的工人。最后，当没有工人再提出匹配申请时结束，此时的匹配为最终的匹配结果。mmCt=c1,c2,.,cv1,cv,.Cw=c1,c2,.,cu1,cu,.witjm作为任务请求者对工人的偏好，由计算得到。假设每个任务所需的能力类型与工人实际所拥有的能力类型分别为和。工人与任务 的可由式(2)确定mwitj=cuCw,cvCtI(cu,cv)(2)uvwitjI(cu,cv)=1其中，和 分别表示工人能力类型和任务所需能力类型的索引。若与 的能力类型匹配，则，mmwitj否则为0。然后平台对每个任务对应的最高的工人进行匹配度更新，得到更新匹配度13mwitj=1max|Ctj|,|Cwi|u=1,v=1(cu cv)2(3)|Ctj|tj|Cwi|wiWe其中，表示任务 所需能力类型的数量，表示工人所拥有的能力类型的数量。为每个任务选择其最合适的工人，最终得到待培养工人集合。t2 t1 t3w1t1w3w4t2w1w2t3w5t1t1w3w4mw3t1mw4t1mw3t1mw4t1mw3t1 w4t2w1 w2t3w5对工人的匹配过程进行举例说明。如图2(a)所示，表示工人对感知任务的由大到小的偏好，第1轮，所有工人向其最偏好的任务发出执行请求，任务 收到和的请求，任务 收到和的请求，任务收到的请求。对于任务，平台根据式(2)分别计算 与工人,的初始匹配度和，然后根据式(3)计算任务与工人之间的更新匹配度和。由计算结果得知，即任务对工人的偏好为。根据同样的计算方法，任务对工人的偏好排序为。而任务只收到的请求。图 2 选择工人1508电 子 与 信 息 学 报第 45 卷t1w3t2w1t3w5因此，任务 暂时接受，暂时接受，暂时接受，如图2(b)中蓝色箭头所示。w2t3w4t2t2w1w4t3w2w5mw1t2mw4t2mw2t3mw5t3mw1t2 mw4t2mw2t3 mw5t3t2w1t3w5w2由于工人继续寻求与其他任务进行匹配，即此时匹配过程还未结束，故在第2轮继续进行匹配过程。工人根据对任务的偏好向 发出请求，向发出请求，如图2(b)中黑色箭头所示。此时需计算任务对和的偏好，以及任务 对和的偏好，即,和,。与第1轮中的计算过程相同，得到，故任务仍然与暂时匹配，此时放弃，而与暂时匹配，如图2(c)中蓝色箭头所示。w1,w2,w3如此继续匹配过程，直到没有工人发出申请。匹配结果如图2(d)所示，为待培养工人集合。3.2 培养工人lr工人的培养过程分为 个阶段。由于工人名誉值与多种能力类型的值有关，故在第 阶段工人名誉值 与能力值之间的关系表示为14rwi(c1,c2,.,cn)=1c1+2c2+.+ncn+b(4)u(0,1)其中，表示不同类型能力值所占的权重。然后，使用逻辑函数将工人名誉值转化为取值内的值wi(c1,c2,.,cn)=11+exp(wi(c1,c2,.,cn)(5)A=(1,2,.,u1,u,.,n)TC=(c1,c2,.,cu1,cu,.,cn)T令，则上式可写为hA(C)=11+exp(ATC+b)(6)回归模型的代价函数为Cost(yi,yi)=ln(hA(C),yi=1ln(1 hA(C),yi=0(7)yiwihA(C)yirkr其中，表示工人名誉值的估值，即，表示工人在第 阶段的名誉值阈值的映射，并有yi=1,hA(C)kr0,hA(C)kr(8)wi因此，工人的代价函数可以写为Ji(A)=Cost(yi,hA(C)=yilnhA(C)+(1 yi)lnhA(1 C)(9)A本文使用梯度下降法对进行求解。由于要使代价函数最小，故使得Ji(A)A=0(10)Arrwi(c1,c2,.,cn)kr此时求得，能够使式(4)中第 阶段的工人名誉值与名誉值阈值 之间的代价最小。wir+1r+1wikr+1rS=1wi,2wi,.,r1wi,rwi,.,lwirwi=krwirLwir本文使用半马尔可夫模型15,16来预测工人第阶段的名誉值高于名誉阈值的概率。工人的状态为第 阶段求得的工人名誉值，状态空间为名誉阈值空间，且有，工人的第 个状态表示为。wiLwirLwir+1Lwir1wi由于工人从状态转移到状态是独立于状态的，故本文将工人的名誉值变化建模为离散时间下的时间齐次的半马尔可夫模型14。所以，时间齐次的半马尔可夫核心部分如式(11)所示TPwirx(t)P(Lwir+1=x,Swir|Lwi0,Lwi1,.,Lwir,Twi0,Twi1,.,Twir)=P(Lwir+1=x,Swir|Lwir=r)(11)TPwirx(t)wirxTwirwiLwirLwir+1Swir=Twir+1 TwirPwiwirx其中，表示工人在时间 之内从状态转移到的概率，表示工人从状态转移到的时刻，表示工人的状态停留时间。为简单起见，这里只考虑工人到达下一轮名誉阈值的概率17。然后，令表示为工人的转移概率矩阵，且工人从状态转移到状态的概率为Pwirx(t)=P(Lwir+1=x|Lwir=r)=numwirx/numwir(12)numwirwirnumwirxrxwirx其中，表示工人从状态转移的数量，表示从状态转移到状态的数量。工人在时间 之前由状态转移到状态的概率记为Gwirx=P(Swir|Lwir=r,Lwir+1=x)=1P(Swir=|Lwir=r,Lwir+1=x)(13)rGwir也可以得到工人在时间 之前或者在时间 离开状态的概率Gwir=P(Swir|Lwir=r)=lx=1,x/=rTPwirx()(14)TPwirx通过公式(11)(13)可得到相关齐次马尔可夫核心部分，表示为TPwirx()=P(Lwir+1=x,Swir|Lwi0,Lwi1,.,Lwir,Twi0,Twi1,.,Twir)=P(Swir|Lwir=r,Lwir+1=x)P(Lwir+1=x|Lwir=r)=Gwirx()Pwirx(15)因此，得到了工人在任务截止时间之前到达下一状态的概率，即到达下一状态中名誉阈值的概率，故工人在本状态的预测效用为式(16)15，其第4期吕 翊等：考虑工人培养的移动群智感知任务分配机制1509Tr中，表示任务截止时间，工人在本状态的预测效用由工人在本阶段任务截止时间之内到达下一状态的概率来表示。WUr(wi)=1 Tr=0(1 TPwirx()(16)rr+1r然后，为了计算平台在第 阶段的效用，本文根据工人第阶段的预测效用与第 阶段名誉值的代价为工人和任务请求者定价，如式(17)所示pwi=WUrCostr(yi,hA(C)pwiqrj=WUrCostr(yi,hA(C)qrj|(17)pwiqrjpwiqrjpwiqrj其中，和是对工人和任务请求者的初始定价，和是对二者的最终定价。由工人名誉值决定，由任务对应的优质工人占比决定。本文设计了一个基于贪婪的多阶段工人选择培养算法(Multi-stage Worker Selection and Devel-opment,MWSD)以选择工人，令其进入下一阶段的培养。如算法1所示，行(2)行(17)表示平台在rWer+1rWsl|We|NO(lN)=O(N)NO(N)阶段 选择进入下一阶段培养的工人并为其定价的过程。具体来说，行(4)行(13)表示当不为空时，平台根据第阶段工人的名誉值到达此阶段名誉阈值的概率和第 阶段工人名誉值代价函数的比值来选择可培养的工人，如行(5)所示。行(6)行(8)表示对于已选择的工人，计算平台所需成本，若成本之和小于平台在此阶段的预算，则将此可培养的工人加入；否则说明此阶段的优质工人已选择结束，并将本阶段的优质工人集合作为下一阶段的待培养工人集合，如行(9)行(12)所示。然后，平台为本阶段的工人与任务请求者定价，如行(14)行(16)所示。由算法可得，算法执行 个阶段，且每个阶段需要遍历的工人数目最大为初始待培养工人数目，记为，故算法的时间复杂度为。由于列表需要的临时存储空间为，故算法的空间复杂度为。4 仿真分析本文评估了所提机制的工人名誉值、平台效用以及长期平台效用，并通过仿真结果来比较所提机制与对比算法的差异，仿真参数见表118,19。对比算法1为考虑工人培养的随机选择培养算法(Random with Worker Development,RWD)。与本机制基于工人的代价和预测效用来选择工人不同，对比算法1表示每个培养阶段随机选择进入下一培养阶段的工人，以在考虑工人培养的前提下检验本机制的性能。对比算法2和对比算法3为不考虑工人培养的工人选择算法，以突出工人培养的有效性。对比算法2为最小社会成本赢标选择算法(Min-imum-social-Cost winning-Bid Selection,MCBS)20，此算法在每个阶段都贪婪选择成本最小的工人来执行任务，直到平台在此阶段的预算耗尽。对比算法3为基于区块链的非确定团队协作算法(Blockchain-based Nondeterministic TeamworkCooperation,BNTC)21，此算法以工人名誉值为价值，以工人成本为重量，在每个阶段使用基于动态规划的背包算法选择工人，直到平台在此阶段的预算耗尽。算法1多阶段工人选择培养算法(MWSD)WeK输入：待培养工人集合，工人名誉阈值集合；Ws输出：优质工人集合Ws(1)gr g1,g2,.,gl(2)while doWs(3)/*当待培养工人集合不为空时*/We/=(4)while dowb argmaxwiWe(WUr/Costr(yi,hA(C)(5)/*若待培养工人的成本小于本阶段预算*/c(Ws)+c(wb)Br(6)if thenWs Ws wb(7)We Wewb(8)/*否则进入下一培养阶段的工人选择结束*/(9)else thenWe Ws(10)(11)break(12)end if(13)end while/*为任务请求者和工人定价*/gr(14)for 中所有工人和任务请求者 do(15)根据式(17)为任务请求者和工人定价(16)end for(17)end whileWs(18)return 表 1 仿真参数设置参数名称参数值任务数50工人数100名誉阈值01平台每阶段最大预算250工人最高成本101510电 子 与 信 息 学 报第 45 卷4.1 名誉值与平台效用由于工人名誉值由工人不同的能力类型值聚合而成，所以本文通过工人的名誉值来衡量工人提交感知数据的质量，通过平台效用来衡量本文所提机制在每个培养阶段的性能。图3表示工人名誉值随培养阶段的变化图。在MWSD算法和RWD算法中，工人的平均名誉值随着培养阶段的增加而增大，第12阶段后工人平均名誉值趋于平稳，且趋于平稳后MSWD算法的工人名誉值最高。这是因为MWSD和RWD算法中都考虑了工人培养，且MWSD根据工人本阶段的代价函数以及到达下一阶段名誉阈值的概率来选择进入下一阶段培养的工人，第12阶段之后，工人的培养过程结束，其平均名誉值均大于0.9。MCBS和BNTC算法的工人平均名誉值先高于MWSD算法，后低于此算法，这是因为MCBS算法和BNTC算法未考虑工人培养。以第20阶段为例，MWSD算法中工人的平均名誉值较于RWD,MCBS和BNTC算法分别提升了12%,26%和24%。图4是平台效用随培养阶段的变化图。平台效用随培养阶段的增加而增加，MWSD算法和RWD算法的平台效用都先增加后趋于平缓，且MWSD算法的平台效用在第12阶段后趋于平稳。并获得的平台效用最高。原因是MWSD算法考虑了工人培养。工人培养结束后得到的工人为优质工人，故平台效用趋于平稳。在无培养过程的MCBS和BNTC算法中，平台效用也先缓慢增加后趋于平稳。这是因为在每个阶段，平台根据本阶段预算选择工人作为优质工人，故优质工人占比增加，平台效用也缓慢增加，直到优质工人占比不变，平台效用也趋于稳定。以第20阶段为例，相对于RWD算法、MCBS算法和BNTC算法，MWSD算法产生的平台效用分别提升了47%,57%和85%。图5表示MWSD算法中平台效用随任务数量和培养阶段变化的关系图。由图中可以看出，当任务数量分别为50,70,90,110时，在同一培养阶段的平台效用是逐渐增加的。这种趋势的原因是任务数量增加，需要培养的优质工人数也增加，此时平台效用也会提高。图6是平台成本随培养阶段的变化曲线。MWSD算法和RWD算法中平台成本随培养阶段的增加而增加，然后趋于平稳，且MWSD算法所需平台成本最高。这是因为二者都考虑了工人培养。MCBS和BNTC算法的平台成本先缓慢增加后趋于平稳，总体趋势相对于MWSD算法更平缓。原因是MCBS和BNTC算法未考虑工人培养，且每个阶段都在平台预算内选择使平台效用最高的部分工人进入下一阶段，直到工人数量不再变化。第20阶段的MWSD所需的平台成本分别比RWD,MCBS和BNTC高23%,185%和180%。图 3 不同培养阶段的工人平均名誉值 图 4 不同培养阶段的平台效用 图 5 不同任务数量和培养阶段的平台效用 图 6 不同培养阶段的平台成本第4期吕 翊等：考虑工人培养的移动群智感知任务分配机制15114.2 长期平台效用本文用长期平台效用来衡量所提机制的性能。图7是长期平台效用随培养阶段的变化曲线。随着阶段数目的增加，4种对比算法的长期平台效用均增加，且最终MWSD算法的长期平台效用最高。这是因为4种算法在每个阶段的平台效用都为正值，且MWSD算法考虑了工人培养，综合考虑了工人在本阶段的代价函数以及到达下一阶段名誉阈值的概率。另外，MWSD算法的长期平台效用先低于后高于MCBS和BNTC。原因是MCBS和BNTC未考虑工人培养，且每个阶段都选择平台预算之内的使得平台效用最大的工人，而MWSD算法将经验不足的工人逐渐培养，使得平台效用逐渐增加，最终获得较高的长期平台效用。仿真结果显示，培养结束后，MWSD算法的长期平台效用分别比RWD,MCBS和BNTC高了59%,17%和17%。图8是长期平台效用随着任务数量和培养阶段变化的关系图。如图所示，在同一阶段，当任务数量分别为50,70,90,110时，长期平台效用也呈增加趋势。这是因为当任务数量增加时，完成所有感知任务所需的优质工人数目也增加，此时产生的平台效用也呈增加趋势。5 结束语本文所提出的任务分配机制考虑了缺乏优质工人的任务，并对经验不足的工人进行培养，使这些任务能够高质量完成，对工人进行长期复用，从而提高长期平台效用。首先，对于经验不足的工人，平台对其进行匹配，得到待培养工人。其次，在工人培养过程分为多个阶段。对于每个阶段，一方面，应用逻辑回归模型将工人的多种能力值进行聚合为名誉值，计算工人名誉值与本阶段名誉阈值之间的代价；另一方面，使用半马尔可夫方法预测工人在下一阶段到达名誉阈值的概率，得到工人的预测效用。最后，结合工人在本阶段的代价与下一阶段的预测效用选择进入下一培养阶段的工人。仿真结果表明，培养结束后，所提机制中的工人名誉值、平台效用和长期平台效用得以提高。未来工作将考虑任务请求者的反馈，考虑优质工人占比较高但存在感知数据质量较低的偶然性问题，提出更能保证数据质量的方法。参 考 文 献CAPPONI A,FIANDRINO C,KANTARCI B,et al.Asurvey on mobile crowdsensing systems:Challenges,solutions,and opportunitiesJ.IEEE CommunicationsSurveys&Tutorials,2019,21(3):24192465.doi:10.1109/COMST.2019.2914030.1LIU Yutong,KONG Linghe,and CHEN Guihai.Data-oriented mobile crowdsensing:A comprehensive surveyJ.IEEE Communications Surveys&Tutorials,2019,21(3):28492885.doi:10.1109/COMST.2019.2910855.2ARCAS-TUNEZ F and TERROSO-SAENZ F.Forest pathcondition monitoring based on crowd-based trajectory dataanalysisJ.Journal of Ambient Intelligence and SmartEnvironments,2021,13(1):3754.doi:10.3233/AIS-200586.3AN Jian,WANG Zhenxing,HE Xin,et al.Know where youare:A practical privacy-preserving semi-supervised indoorpositioning via edge-crowdsensingJ.IEEE Transactions onNetwork and Service Management,2021,18(4):48754887.doi:10.1109/TNSM.2021.3107718.4JI Jianjiao,GUO Yinan,GONG Dunwei,et al.Evolutionary multi-task allocation for mobile crowdsensingwith limited resourceJ.Swarm and EvolutionaryComputation,2021,63:100872.doi:10.1016/j.swevo.2021.100872.5WEI Xiaohui,LI Zijian,LIU Yuanyuan,et al.SDLSC-TA:Subarea division learning based task allocation in sparsemobile crowdsensingJ.IEEE Transactions on EmergingTopics in Computing,2021,9(3):13441358.doi:10.1109/TETC.2020.3045463.6WANG Xiong,JIA Riheng,FU Luoyi,et al.Online spatialcrowdsensing with expertise-aware truth inference and taskallocationJ.IEEE Journal on Selected Areas in7 图 7 不同培养阶段的长期平台效用 图 8 不同任务数量和培养阶段的长期平台效用1512电 子 与 信 息 学 报第 45 卷Communications,2022,40(1):412427.doi:10.1109/JSAC.2021.3126045.JI Jianjiao,GUO Yinan,GAO Xiaozhi,et al.Q-learning-based hyperheuristic evolutionary algorithm for dynamictask allocation of crowdsensingJ.IEEE Transactions onCybernetics,2023,53(4):22112224.doi:10.1109/TCYB.2021.3112675.8ZHANG Lichen,DING Yu,WANG Xiaoming,et al.Conflict-aware participant recruitment for mobilecrowdsensingJ.IEEE Transactions on ComputationalSocial Systems,2020,7(1):192204.doi:10.1109/TCSS.2019.2948957.9NIE Jiangtian,LUO Jun,XIONG Zehui,et al.A multi-leader multi-follower game-based analysis for incentivemechanisms in socially-aware mobile crowdsensingJ.IEE