基于两阶段机会型参与式协作的车载众包感知高效公平任务分配

《Computer Networks》：Efficient and fair task allocation via two-stage opportunistic-participatory collaboration in vehicular crowd sensing

　　

摘要

车辆众包感知（VCS）已成为智慧城市中大规模城市感知的有前景范式。然而，现有的任务分配方案面临若干关键挑战，包括过度依赖单一类型的感知工作者、对时空公平性考虑不足，以及在感知成本与覆盖需求之间难以取得平衡。为解决这些问题，本文提出了分层车辆众包感知（HiVCS），这是一种分层两阶段任务分配框架，通过战略性地利用机会型工作者与参与型工作者的互补优势。在第一阶段，采用带有技能与距离约束的稀疏二分图匹配算法，以最低成本实现大规模基础覆盖。在第二阶段，我们构建了一个约束多目标优化问题，并使用CMOEA-EG（一种带有精英引导策略的约束多目标进化算法）进行求解，同时优化平均成本、任务覆盖率和时空公平性。在多个主要城市的真实出租车轨迹数据集上进行的广泛实验表明，HiVCS在成本效率、覆盖性能和时空公平性方面相较于现有代表性基线方法均取得了显著提升。所提框架还展现出优异的扩展性和鲁棒性，验证了其在真实VCS部署中的实用性。

引言

车辆众包感知（VCS）是一种有前景的大规模城市感知范式。它利用出租车、网约车和物流车队等商用车辆的广泛移动性和车载传感器，以低成本方式进行智慧城市数据采集，如空气污染监测、交通优化和环境感知[1]、[2]。作为移动众包感知（MCS）的重要分支，VCS通过商用车辆的持续移动性扩展了城市感知覆盖范围[3]、[4]。任务分配是连接感知需求与执行者的关键环节，它决定了系统效率、成本控制和资源公平性，已被广泛研究[5]、[6]。

尽管VCS研究取得了显著进展，现有任务分配方案仍面临关键的实际局限性。大多数方案仅关注单一类型工作者，忽略了轨迹固定的机会型工作者与灵活路由的参与型工作者之间的互补优势，导致资源利用次优且城市感知覆盖有限[7]、[8]、[9]、[10]、[11]。优化目标局限于单一维度，如最小化成本或最大化覆盖。对时空公平性考虑不足导致任务分布不均，在人流量较少的区域持续存在任务饥饿问题[12]、[13]、[14]、[15]。此外，现有方法在处理多样化任务和异构工作者时，仍面临技能匹配和动态调度的挑战[16]、[17]。此外，在多目标优化方法中，采用分层决策结构以平衡实时响应与优化深度的应用仍然有限[18]、[19]。

为解决上述问题，本文提出了分层车辆众包感知，记为HiVCS，这是一种利用机会型工作者与参与型工作者互补性的两阶段任务分配框架。遵循粗粒度覆盖后细粒度优化的原则，机会型工作者在第一阶段通过带有技能和距离约束的稀疏二分图匹配实现广泛任务覆盖。参与型工作者在第二阶段通过约束多目标优化解决剩余任务，联合优化成本效率、覆盖率和时空公平性。采用包含24小时内48个半小时时间片的时间片调度机制、技能匹配约束和动态位置更新，确保框架的时效性和适应性。

本文的主要贡献总结如下：

• (1)
  一种分层两阶段分配范式，利用机会型工作者的轨迹稳定性在第一阶段通过带有技能和距离约束的稀疏二分图匹配以最小成本最大化初始覆盖，然后使用参与型工作者对剩余任务应用约束多目标优化，联合最小化成本、最大化任务覆盖率和最大化时空公平性。
• (2)
  针对参与型工作者阶段的约束多目标优化问题，开发了CMOEA-EG的增强版本。该算法通过精英父代引导策略和约束松弛策略进行了增强，这些策略共同增强了其在实验场景中的搜索能力和解质量，从而有效优化任务成本、任务覆盖率和时空公平性。
• (3)
  我们在三个真实出租车轨迹数据集上进行对比实验，评估所提HiVCS框架的性能。评估指标包括平均任务成本、任务覆盖率和时空公平性指数，并与四种代表性基线方法进行比较。

本文其余部分组织如下。第2节回顾相关工作。第3节建立系统模型和问题定义。第4节详细说明HiVCS框架及其算法。第5节展示实验结果和分析。最后，第6节总结全文并展望未来研究方向。

章节摘要

相关工作

车辆众包感知（VCS）已从简单的激励机制设计发展为复杂的任务分配框架。尽管取得了显著进展，现有文献仍面临三个核心挑战：单工作者范式的低效性、对时空公平性作为主要约束的忽视，以及动态多目标优化的计算负担。本节从这些维度回顾文献，以定位我们所提的HiVCS框架。

系统模型与问题建模

本节介绍了HiVCS框架，包括系统架构、数学模型及相应算法。该框架整合机会型工作者和参与型工作者，以实现高效覆盖、成本优化和时空公平性。

任务分配与优化

本节提出了面向机会型MCS的HiVCS任务分配框架。该框架旨在通过利用工作者的移动性并应对多目标优化挑战来最大化社会福利。它包含两个渐进阶段：第一阶段专注于机会型工作者的稀疏二分图匹配，第二阶段采用改进的双种群约束多目标进化算法处理参与型工作者。

实验评估

本节展示了模拟实验结果，证明了所提HiVCS任务分配算法在所有性能指标上的优越性。我们与四种代表性基线算法进行了全面比较，以验证其在成本效率、覆盖增强和时空公平性方面的优势。此外，消融实验和敏感性分析验证了HiVCS协同机制的必要性以及算法的适应性。

结论

本文解决了车辆众包感知任务分配中成本效率、覆盖性能和时空公平性的联合优化这一紧迫挑战。我们提出了HiVCS，一种分层两阶段框架，战略性地整合了具有固定轨迹的机会型工作者与具有灵活重路由能力的参与型工作者的互补优势。第一阶段采用带技能和距离约束的稀疏二分图匹配以实现

CRediT作者贡献声明

马庆典：论文撰写 – 审阅与编辑，论文撰写 – 初稿撰写。王英杰：监督指导。侯文涵：监督指导，资源提供。滕浩军：监督指导，软件开发。李映馨：数据整理，概念设计。

利益冲突声明

作者声明不存在已知的竞争性经济利益或个人关系，这些利益或关系可能会影响本文所报道的工作。

致谢

本工作部分得到了中国国家自然科学基金（基金编号92582115和62272405）、山东省青年创新科技支持计划（基金编号2021KJ080）、山东省自然科学基金（基金编号ZR2024YQ002和ZR2022MF238）、烟台市科技创新发展规划（基金编号2024ZLYJ121）以及山东省重点研发计划（基金编号2025CXPT077）的支持。

马庆典于2024年获得鲁东大学智能科学与技术学士学位。目前就读于烟台大学计算机与控制工程学院，攻读硕士学位。其研究方向包括车辆众包感知和任务分配。

马庆典|王英杰|侯文涵|滕浩军|李映馨