一种结合任务参与者匹配偏好的多任务分配方法在移动众包中的应用

《Computer Networks》：A Multi-Task Allocation Method Incorporating Task-Participant Matching Preferences in Mobile Crowdsensing

多任务分配方法PAMTA在移动众包中考虑任务-参与者匹配偏好，通过双向建模量化执行成本，结合遗传算法与免疫自适应策略解决NP难问题，实验表明其显著提升平台利润、任务分配比及人均任务数，同时增强偏好匹配度确保执行稳定。

　　

杨凯成|周朝然|张欣|刘玉婷|马克·佐尔加德里

长春科技大学计算机科学与技术学院，中国吉林省长春市130022

摘要

任务分配（TA）是移动众包（MCS）中的一个基本挑战，其目标是以最大化平台利润的方式为参与者分配任务。然而，忽视参与者的能力和任务的时间限制要求往往会导致不匹配，从而导致任务失败、资源浪费和利润减少。因此，一些研究将参与者和任务的偏好作为软优化目标纳入效用函数中，以确保任务执行的稳定性。然而，算法在追求全局最优性的过程中往往会牺牲平台利润。为了解决这些问题，我们提出了一种考虑任务-参与者匹配偏好的多任务分配方法（PAMTA），通过这种方法优化任务分配。鉴于该问题的NP完全性，我们首先在任务-参与者匹配偏好规则约束下对多任务分配问题进行了形式化定义。然后，我们开发了一种基于偏好的评估方案，并构建了一个用于评估平台任务执行成本的模型。为了高效解决问题，我们设计了一种名为PAMTA-ASIGA的定制启发式算法，该算法结合了遗传算法和免疫及自适应策略。在多种MCS场景下的广泛实验表明，所提出的PAMTA在平台利润、任务分配比例以及每个参与者分配的任务数量方面显著优于基线方法。此外，PAMTA还提高了任务和参与者的平均偏好值，从而确保了任务分配的稳定性。

引言

近年来，随着物联网（IoT）和移动互联网技术的进步，智能移动设备（如智能手机和可穿戴设备）在日常生活中变得越来越普遍[1]、[2]、[3]。这些设备配备了各种强大的嵌入式传感器，包括摄像头和陀螺仪，提供了丰富的感知能力。因此，移动用户可以收集有关人类活动和环境条件的多样化信息，有效补充甚至替代传统无线传感器网络中的静态传感器。在这种背景下，以人为中心的移动众包（MCS）作为一种获取大规模多模态数据的主要范式出现，引起了研究人员的广泛关注[4]、[5]。MCS因其低成本、普及性和灵活性而受到重视，并已成功应用于交通监控[6]、环境监测[7]、医疗保健服务[8]等多个领域。

MCS系统通常涉及三个主要角色：任务请求者、MCS平台和移动参与者[9]。任务请求者向平台提交任务需求并提供相应的奖励。MCS平台将这些任务分配给移动参与者，并管理收集的数据。参与者执行分配的任务并将结果上传到平台以获得奖励。随着MCS应用的不断扩展，任务和参与者的数量都在增加。因此，设计一种有效的任务分配（TA）机制以最大化平台利润、满足任务请求者和参与者的需求，并确保任务分配的稳定性，已成为MCS中的一个基本挑战[10]、[11]、[12]。

已经对MCS中的TA问题进行了大量研究，重点关注参与者可以执行的任务数量以及分配策略的优化目标。根据分配给每个参与者的任务数量，TA问题可以分为单任务分配和多任务分配。许多研究关注单任务分配，其中参与者在完成每个任务后等待新任务[13]、[14]、[15]、[16]、[17]。然而，在实践中，参与者通常更愿意在空闲时间（如通勤或休闲时间）完成多个任务，这使得单任务分配效率低下。为了克服这一限制，近期文献探索了多任务分配策略，旨在在追求各种优化目标的同时提高分配效率[18]、[19]、[20]、[21]、[22]、[23]、[24]。然而，现有的方法仅关注最小化任务成本[25]、最大化平台效用[18]或提高参与者福利[26]，往往无法平衡所有相关方的利益，也没有考虑平台的长期运营策略。

考虑到现实世界场景中任务和参与者的可用性有限，一些研究提出了在时间限制下优化平台利润和完成任务数量的TA策略[19]、[27]、[28]、[29]。然而，这些研究经常忽略了平台和参与者的理性行为。在实践中，平台不太可能招募没有必要技能的参与者，而参与者可能会拒绝不符合他们兴趣的任务或提供的奖励不足以覆盖执行成本[30]、[31]。如果MCS平台在分配任务时不考虑任务和参与者的偏好，参与者可能会拒绝执行任务，从而无法确保任务分配的稳定性，导致平台资源浪费和平台利润下降[32]、[33]、[34]。在现有的MCS任务分配方案中，参与者和任务的多维偏好（包括旅行距离、电池焦虑、声誉和社会能力）通常作为软优化目标纳入效用函数中。通过加权求和或排名操作来促进整体社会福利和满意度[35]、[36]、[37]。然而，这些非强制性的约束使得难以定义平台可接受的最低任务-参与者偏好匹配程度。由于匹配程度相对较低的组合也可能产生高利润，平台在追求最佳整体效用时可能会忽略这些组合，从而导致平台利润下降。

通过分析实际案例和上述文献，我们确定了在设计有效TA策略以优化平台利润时必须解决的三个关键方面：（1）时间限制，包括旅行时间和执行时间，以确保任务在截止日期前完成；（2）任务-参与者匹配偏好，这决定了任务-参与者的兼容性。当这些偏好被量化为硬性准入规则时，平台可以设置一个最低匹配偏好阈值，以接受高于该阈值的高利润任务-参与者组合，从而优化平台利润；（3）执行成本，这直接影响平台利润和参与者对任务的接受度。然而，这些考虑因素带来了几个挑战。首先，任务和参与者的可用性变化，加上每个任务的合适参与者数量不同，导致任务类型和参与者收益的异质性，从而影响平台利润。其次，任务-参与者匹配偏好具有多维特性，平台上为每个维度单独设置准入阈值会忽略它们之间的相互关系。同时，设计准确的指标来量化匹配程度及其对执行成本的影响也具有挑战性。第三，在强制性约束下，最大化平台利润的TA问题是NP完全的。现有算法可以有效解决此类问题，但它们缺乏针对所研究问题的目标约束处理机制，容易导致大量无效分配。

为了解决这些挑战，我们提出了一种考虑匹配偏好的多任务分配方法（PAMTA），该方法可以在保证任务分配稳定性的同时最大化平台利润。本研究的主要贡献如下：

1) 我们在MCS平台中引入了强制性匹配偏好规则，通过专门的匹配偏好阈值定义了最低任务-参与者偏好匹配阈值，并设计了一个双向偏好建模模块，通过加权评估方法量化任务执行成本。

2) 鉴于启发式算法适用于解决具有类似结构的问题，我们开发了一种算法PAMTA-ASIGA，该算法结合了遗传算法和免疫及自适应策略，在匹配偏好规则下生成最优的多任务分配策略。

3) 我们进行了广泛的模拟实验，结果表明PAMTA在平台利润、任务分配比例和每个参与者分配的任务数量方面优于基线方法。同时，我们确认强制性规则有助于提高任务和参与者的平均偏好值，并提升平台利润。

本文的其余部分组织如下。第2节回顾了MCS中任务分配的相关工作。第3节描述了匹配偏好规则下的TA场景并定义了TA问题。第4节介绍了PAMTA方法。第5节报告了实验结果。第6节讨论了PAMTA的局限性。第7节总结了本文。

相关研究

相关工作

随着MCS应用和平台的不断发展，对MCS任务的需求预计也将相应增加。任务完成效率是影响MCS平台整体性能的关键因素，研究人员非常关注如何提高系统效率。根据MCS平台每次分配的任务数量，TA问题可以分为单任务分配问题和多任务分配问题。

考虑任务-参与者匹配偏好的任务分配建模

在本节中，我们使用任务-参与者匹配偏好对TA问题进行了建模，并证明了它是一个NP完全问题。

PAMTA的多任务分配详细方法

在本节中，我们提出了一种新的考虑任务-参与者匹配偏好的多任务分配（PAMTA）方法。在图2中，PAMTA包括三个核心模块：（1）一个双向偏好建模模块，用于定量捕捉任务和参与者之间的相互偏好，以确保个性化和兼容的匹配；（2）一个奖励评估机制，该机制结合了设备资源消耗和手动执行因素来评估实际执行成本

实验

在本节中，我们通过模拟实验评估了PAMTA的性能。首先，我们介绍了实验设置；然后讨论了实验结果。

讨论

在本节中，我们讨论了本文提出的PAMTA方法的局限性。

1) 本文开发的PAMTA-ASIGA算法适用于在算法执行之前所有参与者和任务的信息都已知的任务分配问题。然而，在现实世界的MCS场景中，任务的到达和参与者的流动性都表现出高度的动态性和随机性。尽管算法中的免疫操作符具有传统启发式方法的优势

结论

为了解决在时间限制下MCS任务分配中平台资源利用不足以及将参与者或任务的偏好视为软优化目标导致的平台利润不足的问题，本文提出了一种考虑任务-参与者匹配偏好的多任务分配方法（PAMTA），以最大化平台利润并保证任务分配的稳定性。在PAMTA中：首先，为了全面满足任务和参与者的需求，采用了双向偏好

CRediT作者贡献声明

杨凯成：撰写——原始草案、方法论、调查、形式分析、数据整理、概念化。周朝然：撰写——审阅与编辑、验证、项目管理、资金获取。张欣：撰写——审阅与编辑、验证、监督、资金获取。刘玉婷：撰写——审阅与编辑、验证。马克·佐尔加德里：监督、资源管理、项目管理。

利益冲突声明

作者声明他们没有已知的可能会影响本文报告工作的财务利益或个人关系。

杨凯成目前正在长春科技大学计算机科学与技术学院攻读博士学位。他的研究兴趣包括城市计算、移动众包和人工智能。