Mobility-Aware Multi-Task Migration and Offloading Scheme for Internet of Vehicles

Xujie Li, Jing Tang, Xu Yuan, Ying SunChinese 2023 · DOI

This paper, published in the Chinese Journal of Electronics (Nov. 2023), presents a new approach to managing the computational demands of the Internet of Vehicles (IoV). As cars become "computers on wheels," the authors propose a way to use that spare processing power without letting vehicle movement break the system.

TL;DR

The researchers developed MAMMOS, an optimization scheme that allows roadside infrastructure to offload complex tasks to moving vehicles. By jointly optimizing task migration and resource allocation, the system significantly reduces processing delays and costs compared to existing heuristic methods.

What Problem Does This Paper Address?

In the world of Vehicular Edge Computing (VEC), Roadside Units (RSUs) are the backbone, but they have limited computing power. To handle the massive data from autonomous driving and on-board apps, RSUs can "offload" tasks to the vehicles themselves, which often have idle CPU cycles.

However, there is a catch: mobility. Vehicles move fast. A task started while a car is near RSU A might need to finish when the car has moved to RSU B. This requires "task migration"—moving the data between RSUs—which introduces extra latency and cost. Most existing research treats offloading and migration as separate problems; this paper argues they must be solved together to be efficient.

Methods

The authors formulate the problem as a Mixed-Integer Nonlinear Programming (MINLP) problem, which is notoriously "NP-hard" (meaning it's computationally impractical to find a perfect solution quickly as the system grows).

To solve it, they use a Divide and Conquer approach through Alternating Optimization:

  1. Task Migration Algorithm: They first track how many times a task must be migrated based on vehicle speed and RSU coverage.
  2. Computing Resource Allocation: Assuming the vehicle nodes are already chosen, they use Lagrange multipliers and KKT conditions to find the mathematically optimal amount of CPU power to assign to each task.
  3. Vehicle Node Selection: Assuming the resource amounts are fixed, they determine which specific vehicle should handle which task. They solve this 0-1 integer problem using a Branch and Bound algorithm with linear relaxation.
  4. The MAMMOS Loop: The system iterates between these steps until it converges on a solution that minimizes a "cost function" (a weighted balance of delay, migration energy, and rewards for the vehicles).

Datasets

The paper relies on Monte Carlo simulations performed in Matlab rather than a static real-world dataset.

  • Parameters: The simulation modeled a straight road with 20 RSUs and 12 vehicles.
  • Variables: Vehicle speeds were varied between 15 and 65 km/h, and task sizes ranged from 1.3 to 2.1 Mb.
  • Repetition: Each scenario was executed 100 times to ensure the results were statistically significant.

Key Insights and Ideas

  • The Mobility Penalty: The paper quantifies the "migration cost" per bit. It recognizes that offloading to the fastest car isn't always best if that car leaves the RSU's range too quickly, triggering expensive data transfers.
  • Incentive Modeling: Unlike many models that assume vehicles are "altruistic," this paper includes a reward mechanism. It treats the vehicle's computing contribution as a service that must be compensated, which is factored into the total cost optimization.
  • Coupling is Key: The "aha moment" is that vehicle selection and CPU allocation are deeply coupled. By alternating between solving for "who" (node selection) and "how much" (resource allocation), the algorithm finds efficiencies that single-stage heuristics miss.

Key Results

The proposed MAMMOS algorithm was compared against a Random selection method and the Harris Hawks Optimization (HHO) (a popular bio-inspired metaheuristic).

  • System Performance: MAMMOS outperformed HHO by 15.03% and the Random algorithm by 35.37% in terms of the overall objective function.
  • Latency: The scheme achieved a minimum delay that was 9.5% lower than HHO and 19.55% lower than Random.
  • Scalability: As the number of vehicles increased, the performance of MAMMOS improved significantly because the algorithm had a wider "pool" of resources to optimize across.
  • Speed Resilience: While higher vehicle speeds naturally increase costs (due to more migrations), MAMMOS maintained a much flatter cost curve than the other two methods.

Limitations and Future Work

  • Simplified Geometry: The study assumes a straight road with RSUs at regular intervals. Real-world urban environments with intersections, buildings (blocking signals), and varying traffic density would be much more complex.
  • Communication Overhead: While the paper accounts for task migration between RSUs, it assumes the backhaul (the fiber link between RSUs) is highly reliable.
  • Future Directions: The authors suggest that future iterations could incorporate more complex road topologies and perhaps explore blockchain-based smart contracts to handle the "reward mechanism" for participating vehicles.

Summary updated

Abstract

In Internet of vehicles, vehicular edge computing (VEC) as a new paradigm can effectively accomplish various tasks. Due to limited computing resources of the roadside units (RSUs), computing ability of vehicles can be a powerful supplement to computing resources. Then the task to be processed in data center can be offloaded to the vehicles by the RSUs. Due to mobility of the vehicles, the tasks will be migrated among the RSUs. How to effectively offload multiple tasks to the vehicles for processing is a challenging problem. A mobility aware multi-task migration and offloading scheme for Internet of vehicles is presented and analyzed. Considering the coupling between migration and offloading, the joint migration and offloading optimization problem is formulated. The problem is a NP-hard problem and it is very hard to be solved by the conventional methods. To tackle the difficult problem, the idea of alternating optimization and divide and conquer is introduced. The problem can be decoupled into two sub-problems: computing resource allocation problem and vehicle node selection problem. If the vehicle node selection is given, the problem can be solved based on Lagrange function. And if the allocation of computing resource is given, the problem turns into a 0–1 integer programming problem, and the linear relaxation of branch bound algorithm is introduced to solve it. Then the optimization value is obtained through continuous iteration. Simulation results show that the proposed algorithm can effectively improve system performance.
BibTeX
@inproceedings{li2023mobility,
  author = {Xujie Li and Jing Tang and Xu Yuan and Ying Sun},
  title = {{Mobility-Aware Multi-Task Migration and Offloading Scheme for Internet of Vehicles}},
  booktitle = {Chinese},
  year = {2023},
  doi = {10.23919/cje.2022.00.333},
}
Figure