Dynamic Task Offloading for Cloud-Assisted Vehicular Edge Computing Networks: A Non-Cooperative Game Theoretic Approach

Md. Delowar Hossain, Tangina Sultana, Md. Alamgir Hossain 0001, Md. Abu Layek, Phoo Pyae Sone, Ga-Won Lee, Eui-Nam HuhSensors 2022 · DOI

TL;DR

This paper tackles the challenge of efficiently offloading computational tasks in dynamic vehicular networks by proposing a novel non-cooperative game-theoretic approach. By allowing each vehicle to dynamically adjust its offloading strategy to maximize its own utility, the system significantly reduces task failure rates and response times compared to existing methods.

What Problem Does This Paper Address?

Intelligent vehicles are increasingly running sophisticated applications like autonomous driving and augmented reality, which demand significant computational power. However, vehicles have limited onboard processing capabilities. Vehicular Edge Computing (VEC) aims to address this by offloading tasks to nearby roadside units (RSUs) or edge servers. The challenges in VEC are twofold: the high mobility of vehicles, which can lead to dropped connections and handover issues, and the potential for edge servers to become overloaded when many vehicles attempt to offload tasks simultaneously. Existing solutions often simplify vehicle movement or assume unlimited edge resources, which are unrealistic. This paper addresses the need for a dynamic and efficient task offloading strategy that accounts for vehicle mobility, edge server capacity, and the need for vehicles to make independent decisions to optimize their own performance.

Methods

The core of this paper is a Non-Cooperative Game Theory (NGTO) approach for dynamic task offloading. Here's a breakdown of their methodology:

  • Game Model: They frame the problem as a non-cooperative game where each vehicle (player) independently chooses an offloading strategy to maximize its individual utility. The strategies involve offloading to a local MEC server, a remote cloud via an RSU, or a remote cloud via a base station (BS).
  • Utility Function: Each vehicle's utility is defined as a function of the task execution time and a price function. A shorter execution time (closer to the vehicle's maximum tolerable latency) leads to higher utility.
  • Dynamic Pricing: To manage resource utilization and encourage efficient offloading, a dynamic pricing strategy is employed. This strategy influences the price vehicles pay for offloading, thereby guiding their decisions.
  • Best Response Strategy: The paper utilizes a "best response" offloading strategy. This means each vehicle continuously adjusts its offloading probability based on the current strategies of other vehicles, aiming to find a stable equilibrium where no vehicle can improve its utility by unilaterally changing its strategy.
  • Algorithm 1 (NGTO Algorithm): This algorithm outlines the step-by-step process for vehicles to estimate completion times for different offloading options (MEC, cloud via RSU, cloud via BS), compare them, and then update their offloading probability using the best response strategy.

Datasets

Not discussed in the paper. The evaluation is based on simulations using the EdgeCloudSim simulator.

Key Insights and Ideas

  • Individual Utility Maximization is Key: The paper demonstrates that allowing each vehicle to independently optimize its own utility (by minimizing task completion time and considering pricing) leads to a more efficient overall system, even without explicit cooperation.
  • Dynamic Offloading Probability: The ability of vehicles to dynamically adjust their probability of offloading to different destinations (MEC vs. Cloud) is crucial for adapting to changing network conditions and server loads.
  • Best Response Convergence: The theoretical underpinning that the "best response" strategy converges to a unique and stable Nash Equilibrium is critical for ensuring predictable and efficient system behavior.
  • Mobility and Overload are Intertwined: The paper effectively models and addresses the combined challenges of vehicle mobility and potential edge server overload, showing how a dynamic strategy can mitigate both.

Key Results

The proposed NGTO approach demonstrated significant improvements across various metrics compared to Local RSU Computing (LRC), Random Offloading, and Collaborative Offloading schemes:

  • Reduced Response Time: The NGTO approach achieved approximately 47.6% lower response time compared to LRC, 32.6% compared to Random Offloading, and 26.5% compared to Collaborative Offloading.
  • Reduced Task-Failure Rate: Task-failure rates were reduced by approximately 54.6% compared to LRC, 39.7% compared to Random Offloading, and 28.4% compared to Collaborative Offloading.
  • Higher Successfully Executed Tasks: The NGTO scheme maintained a higher percentage of successfully executed tasks, especially under high vehicle loads, handling up to 1000 vehicles without significant congestion.
  • Performance across Application Types: The scheme showed robust performance across latency-sensitive (Danger Assessment) and latency-tolerant (Infotainment) applications, with response times remaining stable even with varying task ratios.
  • Scalability: The NGTO approach demonstrated better scalability, handling a larger number of vehicles (up to 1000) without experiencing the congestion issues that affected other schemes.

Limitations and Future Work

  • Limitations:
    • The paper assumes a unidirectional road and equidistant RSUs, which might simplify real-world scenarios.
  • The model focuses on individual vehicle utility maximization, and while it leads to good system performance, it doesn't explicitly guarantee global optimality.
  • The assumption of vehicles having complete information about their own task parameters (size, latency requirements) is standard but might be a simplification.
  • Future Work:
    • The authors suggest exploring machine learning-based approaches for even more efficient task offloading strategies in MEC-enabled VEC networks.
  • Expanding the study to include V2V (vehicle-to-vehicle) offloading as an option, alongside MEC and cloud offloading, to further maximize vehicle utility.
  • Investigating more complex network topologies and vehicle movement patterns.

Summary updated

BibTeX
@article{hossain2022dynamic,
  author = {Md. Delowar Hossain and Tangina Sultana and Md. Alamgir Hossain and Md. Abu Layek and Md. Imtiaz Hossain and Phoo Pyae Sone and Ga-Won Lee and Eui-Nam Huh},
  title = {{Dynamic Task Offloading for Cloud-Assisted Vehicular Edge Computing Networks: A Non-Cooperative Game Theoretic Approach}},
  journal = {Sensors},
  year = {2022},
  doi = {10.3390/s22103678},
}
Figure