考虑工人培养的移动群智感知任务分配机制_吕翊_.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 卷需要的高能力值。而经验不足的工人指缺乏平台发布类型的任务所需能力值的工人。由于要最大化自身长期效用，平台需要对工人进行选择和培养，培养工人指经验不足的工人提高其较低或缺失的能力值的过程，令其执行缺乏优质工人的任务，提高这些工