💻 computer science

CFCO: A Social-Welfare-Maximizing Collaborative Coalition Formation Method for Task Offloading in Vehicular Edge Computing

本文提出了 CFCO，一种旨在最大化社会福利的协作联盟形成方法，该方法统一了本地、D2D 和 MEC 计算模式，以优化车载边缘计算中的任务卸载，并在真实轨迹数据上证明了其相比现有基准方案在延迟、公平性和效率方面具有更优越的性能。

原作者： Kangli Zhao, Huaming Gong, Wenpei Xiao, Chunyan Zhou, Qiyue Zhang

发布于 2026-08-25

📖 1 分钟阅读☕ 轻松阅读

原作者： Kangli Zhao, Huaming Gong, Wenpei Xiao, Chunyan Zhou, Qiyue Zhang

原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一个这样的城市：这里的每一辆汽车都不仅仅是交通工具，而是一个移动的计算机，不断地生成并需要处理海量数据，以支持自动驾驶功能、实时导航和安全警报。这些汽车拥有自己的处理器，但受限于电池寿命和发热问题。它们可以将沉重的计算任务发送给路边服务器，但该服务器的工作人员数量有限，且无线连接可能会不稳定或拥挤。当过多的汽车同时尝试使用服务器时，队列会变得过长，导致数据到达时已失去实用价值。这就是“车载边缘计算”面临的日常困境——该领域正致力于研究如何快速、高效地完成这些数字任务，而不至于耗尽汽车的电池或错过关键期限。

在这个复杂的环境中，来自阿巴教师大学（Aba Teachers University）的一个研究小组提出了一种名为 CFCO 的新策略。CFCO 并非强迫每辆车在“自行处理”或“发送给路边服务器”之间做出选择，而是鼓励车辆通过组成小型临时小组来进行协作。研究人员将这个问题建模为一个社交谜题，其目标是实现整个驾驶员群体的整体“幸福感”或收益最大化，而非仅仅针对单辆车的速度或能量进行优化。他们通过权衡任务完成的及时性、消耗的能量以及延迟惩罚来定义这种收益。如果一辆车恰好在规定时间内完成任务，它会获得奖励；如果延迟或耗电过多，则会扣分。系统的任务就是将车辆安排成最有利的配置方案。

为了测试这一想法，研究人员并没有依赖虚构的场景或简单的计算机模型。相反，他们使用了来自“下一代模拟”（Next Generation Simulation）数据集的真实世界数据，该数据集包含了实际车辆在高速公路上移动、加速和聚集的详细记录。他们模拟了 60 辆汽车沿道路行驶的一个快照，并为每辆车分配了一个带有严格时间限制的具体计算任务。有些任务较轻，有些则较重；有些车行驶速度快，有些则较慢。研究人员运行了他们的 CFCO 算法，该算法就像一个智能交通控制器。它不断检查：将一辆车从独立工作转为加入小组，或者从小组转为向路边服务器请求任务，是否会提高整个群体的总分。如果某种改变有助于群体，则执行该改变；如果会对群体造成损害，则予以拒绝。这个过程不断重复，直到系统找到一个稳定的、高分的排列组合。

模拟结果令人瞩目。在一个典型的 60 辆汽车场景中，CFCO 方法实现的系统总收益分数为 481.28，高于所有测试过的其他方法，包括一种非常彻底但缓慢的搜索方法，以及一种车辆直接将所有任务卸载给服务器的简单方法。任务的平均完成时间仅为 0.225 秒，相比于完全依赖路边服务器时 0.455 秒的完成时间，有了显著提升。或许更重要的是，该系统极其可靠，成功完成了 99.8% 的任务。研究人员还发现，该方法具有公平性；它并没有让少数车辆苦苦挣扎而让其他车辆获益，而是通过分配工作负载，使大多数驾驶员都能体验到相似的性能水平。

这种方法之所以如此有效，是因为它利用了道路的物理现实。算法发现，在许多情况下，最佳解决方案并不是将数据发送给服务器或独自处理，而是让汽车与附近的邻车共享工作。在最终的安排中，约 57% 的汽车形成了这些协作小组，22.5% 的汽车向路边服务器发送数据，其余 20.5% 的汽车则自行处理任务。这种混合模式使得系统能够绕过经常阻塞服务器连接的拥堵。当与服务器的连接不可靠或服务器过于繁忙时，汽车只需转向彼此，利用短程无线链路将繁重的计算任务传递给处理器性能更强的邻车。

研究人员还测试了该系统在不同条件下的表现。他们发现，即使在路边服务器连接非常差的情况下，系统也会通过增加对“车对车”小组的依赖来适应环境，从而保持较高的成功率。反之，当服务器可用时，系统能高效利用它，而不会让其成为瓶颈。他们将该方法与几种其他策略进行了对比，包括随机分组法和仅关注眼前步骤的贪婪算法。CFCO 方法始终优于这些替代方案，不仅提供了更好的结果，而且耗时更短。虽然一种非常缓慢的穷举搜索法可以找到几乎相同的解，但其耗时是 CFCO 方法的十二倍以上，这使得 CFCO 在需要秒级决策的实时应用中更具实用性。

一个最令人欣慰的发现是，该算法的结果与理论上的最优解非常接近。通过在规模较小的环境下进行测试（此时可以计算出精确的最优解），研究人员发现其方法与最优解的差距仅为 0.03%。这一微小的差距表明，该算法并非在盲目猜测，而是在解决复杂问题时找到了近乎完美的数学解。研究还证实了该方法的鲁棒性，这意味着即使车辆数量发生变化、处理器速度发生波动或无线带宽发生变化，它依然能表现出色。

最终，这项研究表明，智能交通的未来并不要求每辆车都成为超级计算机，也不需要一个完美且始终在线的服务器网络。相反，它指向了一种灵活的、协作的模型，即车辆作为一个整体资源进行运作。通过根据附近车辆的情况及其实力动态地组建和解散小组，系统可以处理现代驾驶中的沉重计算负荷而游刃有余。研究结论指出，这种追求社会福利最大化的路径，在速度、能量和公平性之间取得了平衡，这是单纯的卸载或孤立计算无法实现的。随着自动驾驶变得越来越普遍，此类方法可能成为确保汽车“数字大脑”永不超载、保障每个人旅途顺畅与安全的关键。

技术摘要：CFCO —— 一种用于车载边缘计算中任务卸载的社会福利最大化协作联盟形成方法

1. 问题陈述

车载边缘计算（VEC）旨在通过在数据源附近提供资源，来支持延迟敏感型和计算密集型应用（如自动驾驶、协同感知）。然而，现有方法面临显著局限性：

本地计算： 受限于车载 CPU 频率、能量预算和热限制。
MEC 卸载： 受限于不稳定的车路协同（V2I）链路、道路阻挡、切换失败以及当多辆车同时进行卸载时产生的资源竞争（带宽和计算核心）。
D2D 协作： 虽然利用相邻车辆的空闲资源具有前景，但引入了联盟形成、首领选择和稳定性方面的挑战。

现有文献通常将这些模式分开处理，或依赖于缺乏可解释性的复杂训练（如深度强化学习）。因此，需要一个可解释的框架，能够联合优化本地计算、设备到设备（D2D）协作和 MEC 卸载，以实现社会福利的最大化——这是一个平衡了异构车辆任务的早期完成收益、能量成本和延迟惩罚的综合指标。

2. 方法论：CFCO 算法

本文提出了 CFCO（协作联盟形成卸载），这是一种旨在通过迭代联盟结构优化来最大化系统社会福利的启发式算法。

2.1 系统模型

网络拓扑： 使用来自 NGSIM 数据集的真实轨迹构建的一维道路拓扑。
任务模型： 每辆车 $i$ 的任务由输入大小 ( $L_i$ )、计算密度 ( $\rho_i$ )、截止时间 ( $\tau^{\max}_i$ )、延迟收益权重 ( $w_i$ ) 和延迟惩罚系数 ( $\lambda_i$ ) 定义。截止时间与车辆速度耦合，反映了高速移动车辆具有更高的敏感性。
执行模式：
1. 本地计算： 在车辆自身的 CPU 上执行。
2. MEC 卸载： 通过 V2I 链路将任务卸载至路侧单元（RSU），受带宽共享和有限核心拥塞的影响。
3. D2D 协作： 非 MEC 车辆组成联盟。具有最高 CPU 频率的车辆担任联盟首领。首领以并行/批处理模式处理任务；执行延迟由联盟中的最大工作量决定，而首领的能量消耗则累积总工作量。

2.2 优化目标

目标是最大化个体净福利 ( $W$ ) 之和：
$W = \sum_{i \in V} \left( w_i \max(0, \tau^{\max}_i - T_i) - E_i - \lambda_i T_i \right)$
其中 $T_i$ 是任务延迟， $E_i$ 是能量消耗。该问题涉及集合划分、离散模式选择和链路可行性约束。

2.3 算法设计

CFCO 在有限状态空间上执行单调改进算法：

初始化： 将车辆初始化为单体。通过比较本地福利与拥塞 MEC 场景（假设所有车辆都尝试卸载）下的福利，进行保守检查以确定初始 MEC 用户。
合并与拆分：
- 合并： 如果两个非 MEC 联盟的社会福利增益严格大于零，则迭代合并这对联盟。
- 拆分： 如果多个成员组成的联盟的福利低于各成员个体本地福利之和，则将该联盟拆分为单体。
模式细化： 如果改变车辆在 MEC 与非 MEC 状态之间（或在本地与 D2D 之间）的切换能严格增加总社会福利，则进行切换。
局部搜索： 执行确定性的局部移动（MEC 切换或车辆在不同联盟间的迁移）以跳出局部最优。
终止： 当不再能找到进一步提升福利的移动或达到最大迭代次数时，算法终止。

3. 核心贡献

统一模型： 实现了一个集成本地、D2D 和 MEC 模式的一致实现模型。它显式地基于 CPU 频率对 D2D 联盟首领进行建模，并通过带宽共享和核心限制对 MEC 拥塞进行建模。
社会福利驱动的启发式算法： 不同于仅优化延迟或能量的方法，CFCO 联合优化了一个复合福利函数。它保证了在有限状态空间内的单调改进和收敛，且无需离线训练。
轨迹驱动评估： 研究利用真实的 NGSIM 车辆轨迹（位置、速度、类别）来映射现实的 CPU 频率和随速度变化的截止时间，从而超越了纯合成拓扑的局限。
统计严谨性： 结果在十个独立的随机种子下取平均值，并配以 95% 置信区间、Wilcoxon 符号秩检验以及针对整数线性规划（ILP）解的小规模精确最优性差距研究。

4. 实验结果

实验在 $N=60$ 辆车和 V2I 可用性概率为 0.7 的条件下进行。CFCO 与八种基准方案进行了对比，包括仅 MEC、单体（仅本地）、随机、贪婪策略、匹配算法、模拟退火（SA）以及最优响应局部搜索（BR-LS）。

4.1 性能指标（平均值）

社会福利： CFCO 达到了 481.28，超过了第二优的基准方案（BR-LS 为 480.24）0.2%，并比仅 MEC 模式高出 71.0%。
平均延迟： CFCO 为 0.225 s，比 BR-LS 降低了 1.9%，比仅 MEC 模式降低了 50.4%。
任务成功率： 0.998，接近完美。
Jain 公平指数： 0.716，表明车辆间的福利分布较为均衡。
执行模式分布： CFCO 将 20.5% 的车辆分配给本地计算，22.5% 分配给 MEC，57.0% 分配给 D2D 联盟。

4.2 效率与最优性

运行时间： CFCO 在 9.17 秒内收敛，比 BR-LS 基准方案（110.85 秒）快 12 倍，同时实现了相当的解质量。
最优性差距： 在针对精确 ILP 求解器的小规模研究（ $N=12$ ）中，CFCO 展示了仅为 0.03% 的平均最优性差距。
统计显著性： 配对 Wilcoxon 检验确认，CFCO 在社会福利和平均延迟方面相对于所有基准方案（包括 BR-LS）的提升在统计学上是显著的（ $p < 0.05$ ）。

4.3 参数敏感性

CFCO 在以下变量变化下均保持卓越性能：

本地 CPU 频率。
D2D 带宽（在测试拓扑中，超过 1 MHz 后收益递减）。
MEC 容量。
车辆密度。
V2I 可靠性（随着 V2I 可靠性下降，CFCO 会动态切换到本地/D2D 模式，而仅 MEC 模式由于更多车辆同时尝试卸载导致的拥塞，其性能会显著下降）。

5. 意义与主张

本文声称 CFCO 为车载边缘计算中的任务卸载提供了一种实用、可解释且高效的解决方案。其意义在于：

平衡权衡： 它成功地在传输能量、计算延迟和任务截止时间之间寻找平衡，避免了单目标优化的陷阱。
现实性： 通过利用 NGSIM 轨迹，评估反映了真实的车辆空间聚类和动力学特性，相比合成模拟提供了更可靠的见解。
可扩展性： 该算法能以显著低于穷举局部搜索方法的计算开销获得接近最优的结果，使其适用于动态车载环境中的在线决策。

作者承认存在一定的局限性，包括使用静态快照而非连续移动轨迹、D2D 首领采用并行处理抽象，以及缺乏激励相容的支付机制。未来的工作拟解决连续移动性、顺序处理模型以及多 RSU 协作等问题。