💻 computer science

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

This paper proposes CFCO, a social-welfare-maximizing collaborative coalition formation method that unifies local, D2D, and MEC computing modes to optimize task offloading in vehicular edge computing, demonstrating superior performance in delay, fairness, and efficiency compared to existing baselines on real-world trajectory data.

Original authors: Kangli Zhao, Huaming Gong, Wenpei Xiao, Chunyan Zhou, Qiyue Zhang

Published 2026-08-25

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Kangli Zhao, Huaming Gong, Wenpei Xiao, Chunyan Zhou, Qiyue Zhang

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a city where every car is not just a vehicle, but a rolling computer, constantly generating and needing to process massive amounts of data for self-driving features, real-time navigation, and safety alerts. These cars have their own processors, but they are limited by battery life and heat. They can also send their heavy computing jobs to a roadside server, but that server has a limited number of workers and the wireless connection to it can be spotty or crowded. When too many cars try to use the server at once, the line gets too long, and the data arrives too late to be useful. This is the daily struggle of "vehicular edge computing," a field trying to figure out the best way to get these digital tasks done quickly and efficiently without draining the car's battery or missing a critical deadline.

In this complex environment, a team of researchers from Aba Teachers University has proposed a new strategy called CFCO. Instead of forcing every car to choose between doing the work itself or sending it to the roadside server, this method encourages cars to work together in small, temporary groups. The researchers modeled the problem as a social puzzle where the goal is to maximize the overall "happiness" or benefit of the entire group of drivers, rather than just optimizing for speed or energy for a single car. They defined this benefit by weighing how early a task finishes against the energy it costs and the penalty for being late. If a car finishes its task just in time, it gains a reward; if it is late or uses too much power, it loses points. The system's job is to arrange the cars into the most beneficial configuration possible.

To test this idea, the researchers did not rely on made-up scenarios or simple computer models. Instead, they used real-world data from the Next Generation Simulation dataset, which contains detailed records of how actual cars move, accelerate, and cluster on highways. They simulated a snapshot of sixty vehicles moving along a road, assigning each one a specific computing task with a strict time limit. Some tasks were light, while others were heavy; some cars were fast, others slow. The researchers then ran their CFCO algorithm, which acts like a smart traffic controller. It constantly checks if moving a car from working alone to joining a group, or from a group to the roadside server, would improve the total score for everyone. If a change helps the group, it happens; if it hurts the group, it is rejected. This process repeats until the system finds a stable, high-scoring arrangement.

The results of these simulations were striking. In a typical scenario with sixty cars, the CFCO method achieved a total system benefit score of 481.28, which was higher than any other method tested, including a very thorough but slow search method and a simple approach where cars just offload everything to the server. The average time it took to complete a task was just 0.225 seconds, a significant improvement over the 0.455 seconds it took when relying solely on the roadside server. Perhaps most importantly, the system was incredibly reliable, successfully completing 99.8% of the tasks. The researchers also found that the method was fair; it did not leave a few cars struggling while others thrived, but rather distributed the workload so that most drivers experienced similar performance levels.

What made this approach so effective was how it utilized the physical reality of the road. The algorithm discovered that in many cases, the best solution was not to send data to the server or to crunch it alone, but to have cars share the work with their immediate neighbors. In the final arrangement, about 57% of the cars formed these collaborative groups, 22.5% sent their data to the roadside server, and the remaining 20.5% handled their own tasks. This mix allowed the system to bypass the congestion that often clogs the connection to the server. When the connection to the server was unreliable or the server was too busy, the cars simply turned to each other, using short-range wireless links to pass the heavy lifting to the neighbor with the strongest processor.

The researchers also tested how well this system held up under different conditions. They found that even when the connection to the roadside server was very poor, the system adapted by relying more on the car-to-car groups, maintaining a high success rate. Conversely, when the server was available, the system used it efficiently without letting it become a bottleneck. They compared their method against several other strategies, including random grouping and greedy approaches that only look at the immediate next step. The CFCO method consistently outperformed these alternatives, delivering better results in less time. While a very slow, exhaustive search method could find a nearly identical solution, it took more than twelve times longer to do so, making the CFCO approach far more practical for real-time use where decisions must be made in seconds.

One of the most reassuring findings was how close the algorithm's results came to the theoretical best possible outcome. By testing on a smaller scale where the perfect answer could be calculated exactly, the researchers found that their method was within 0.03% of the optimal solution. This tiny gap suggests that the algorithm is not just guessing; it is finding a solution that is mathematically near-perfect for the complexity of the problem. The study also confirmed that the method is robust, meaning it works well even when the number of cars changes, the speed of their processors varies, or the wireless bandwidth fluctuates.

Ultimately, this research demonstrates that the future of intelligent transportation does not require every car to be a supercomputer, nor does it require a perfect, always-available network of servers. Instead, it points toward a flexible, cooperative model where vehicles act as a collective resource. By dynamically forming and dissolving groups based on who is nearby and who has the capacity to help, the system can handle the heavy computational loads of modern driving without breaking a sweat. The study concludes that this social-welfare-maximizing approach offers a viable path forward, balancing speed, energy, and fairness in a way that pure offloading or isolated computing cannot. As autonomous driving becomes more common, such methods could be the key to ensuring that the digital brain of the car never gets overwhelmed, keeping the journey smooth and safe for everyone on the road.

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

1. Problem Statement

Vehicular Edge Computing (VEC) aims to support delay-sensitive and computation-intensive applications (e.g., autonomous driving, cooperative perception) by providing resources near data sources. However, existing approaches face significant limitations:

Local Computing: Constrained by on-board CPU frequency, energy budgets, and thermal limits.
MEC Offloading: Suffers from unstable Vehicle-to-Infrastructure (V2I) links, road blockages, handover failures, and resource contention (bandwidth and compute cores) when multiple vehicles offload simultaneously.
D2D Collaboration: While promising for utilizing idle resources in neighboring vehicles, it introduces challenges in coalition formation, head selection, and stability.

Current literature often treats these modes separately or relies on complex training (e.g., Deep Reinforcement Learning) that lacks interpretability. There is a need for an interpretable framework that jointly optimizes local computing, Device-to-Device (D2D) collaboration, and MEC offloading to maximize social welfare—a metric that balances early-completion benefits, energy costs, and delay penalties across heterogeneous vehicle tasks.

2. Methodology: The CFCO Algorithm

The paper proposes CFCO (Collaborative Coalition Formation for Offloading), a heuristic algorithm designed to maximize system social welfare through iterative coalition structure optimization.

2.1 System Model

Network Topology: A one-dimensional road topology using real-world trajectories from the NGSIM dataset.
Task Model: Each vehicle $i$ has a task defined by input size ( $L_i$ ), computation density ( $\rho_i$ ), deadline ( $\tau^{\max}_i$ ), delay-benefit weight ( $w_i$ ), and delay-penalty coefficient ( $\lambda_i$ ). Deadlines are coupled to vehicle velocity, reflecting higher sensitivity for faster-moving vehicles.
Execution Modes:
1. Local Computing: Execution on the vehicle's own CPU.
2. MEC Offloading: Offloading to a Roadside Unit (RSU) via V2I links, subject to bandwidth sharing and finite core congestion.
3. D2D Collaboration: Non-MEC vehicles form coalitions. The vehicle with the highest CPU frequency acts as the coalition head. The head processes tasks in parallel/batch mode; the execution delay is determined by the maximum workload in the coalition, while the head's energy cost accumulates the total workload.

2.2 Optimization Objective

The goal is to maximize the sum of individual net welfare ( $W$ ):
$W = \sum_{i \in V} \left( w_i \max(0, \tau^{\max}_i - T_i) - E_i - \lambda_i T_i \right)$
where $T_i$ is the task delay and $E_i$ is the energy consumption. The problem involves set partitioning, discrete mode selection, and link feasibility constraints.

2.3 Algorithm Design

CFCO operates as a monotonic improvement algorithm on a finite state space:

Initialization: Vehicles are initialized as singletons. A conservative check determines initial MEC users by comparing local welfare against a congested MEC scenario (assuming all vehicles attempt offloading).
Merge and Split:
- Merge: Iteratively merges pairs of non-MEC coalitions if the social welfare gain is strictly positive.
- Split: Splits multi-member coalitions into singletons if the sum of individual local welfare exceeds the coalition's welfare.
Mode Refinement: Toggles vehicles between MEC and non-MEC states (or between local and D2D) if the change strictly increases total social welfare.
Local Search: Performs deterministic local moves (MEC toggles or vehicle migrations between coalitions) to escape local optima.
Termination: The algorithm terminates when no further strictly improving moves are found or the maximum iteration count is reached.

3. Key Contributions

Unified Model: A consistent implementation model integrating local, D2D, and MEC modes. It explicitly models D2D coalition heads based on CPU frequency and MEC congestion via bandwidth sharing and core limits.
Social-Welfare-Driven Heuristic: Unlike methods optimizing only delay or energy, CFCO jointly optimizes a composite welfare function. It guarantees monotonic improvement and convergence in a finite state space without requiring offline training.
Trace-Driven Evaluation: The study utilizes real-world NGSIM vehicle trajectories (positions, velocities, classes) to map realistic CPU frequencies and velocity-dependent deadlines, moving beyond purely synthetic topologies.
Statistical Rigor: Results are averaged over ten independent random seeds with 95% confidence intervals, paired Wilcoxon signed-rank tests, and a small-scale exact optimality gap study against an Integer Linear Programming (ILP) solution.

4. Experimental Results

Experiments were conducted with $N=60$ vehicles and a V2I availability probability of 0.7. CFCO was compared against eight baselines, including MEC-only, Singleton (local only), Random, Greedy strategies, Matching, Simulated Annealing (SA), and a Best-Response Local Search (BR-LS).

4.1 Performance Metrics (Mean Values)

Social Welfare: CFCO achieved 481.28, outperforming the second-best baseline (BR-LS: 480.24) by 0.2% and MEC-only by 71.0%.
Average Delay: CFCO achieved 0.225 s, a 1.9% reduction compared to BR-LS and a 50.4% reduction compared to MEC-only.
Task Success Ratio: 0.998, nearly perfect.
Jain Fairness Index: 0.716, indicating a balanced distribution of welfare among vehicles.
Execution Mode Distribution: CFCO assigned 20.5% of vehicles to local computing, 22.5% to MEC, and 57.0% to D2D coalitions.

4.2 Efficiency and Optimality

Runtime: CFCO converged in 9.17 seconds, which is 12 times faster than the BR-LS baseline (110.85 s) while achieving comparable solution quality.
Optimality Gap: In a small-scale study ( $N=12$ ) against an exact ILP solver, CFCO demonstrated an average optimality gap of only 0.03%.
Statistical Significance: Paired Wilcoxon tests confirmed that CFCO's improvements in social welfare and average delay over all baselines (including BR-LS) are statistically significant ( $p < 0.05$ ).

4.3 Parameter Sensitivity

CFCO maintained superior performance across varying:

Local CPU frequencies.
D2D bandwidth (showing diminishing returns beyond 1 MHz in the tested topology).
MEC capacity.
Vehicle density.
V2I reliability (CFCO dynamically switched to local/D2D modes as V2I reliability dropped, whereas MEC-only performance degraded significantly due to congestion as more vehicles attempted to offload simultaneously).

5. Significance and Claims

The paper claims that CFCO provides a practical, interpretable, and efficient solution for task offloading in VEC. Its significance lies in:

Balancing Trade-offs: It successfully navigates the trade-off between transmission energy, computation delay, and task deadlines, avoiding the pitfalls of single-objective optimization.
Realism: By leveraging NGSIM traces, the evaluation reflects realistic spatial clustering and vehicle dynamics, offering more credible insights than synthetic simulations.
Scalability: The algorithm achieves near-optimal results with significantly lower computational overhead than exhaustive local search methods, making it suitable for online decision-making in dynamic vehicular environments.

The authors acknowledge limitations, including the use of static snapshots rather than continuous mobility traces, a parallel processing abstraction for D2D heads, and the lack of incentive-compatible payment mechanisms. Future work is proposed to address continuous mobility, sequential processing models, and multi-RSU cooperation.