PaperlayerView exact revision on arXiv

Source-linked AI summary

BARGAIN-MATCH: A Game Theoretical Approach for Resource Allocation and Task Offloading in Vehicular Edge Computing Networks

Zemin Sun, Geng Sun, Yanheng Liu, Jian Wang, Dongpu Cao

arXiv:2203.14064v3cs.GTeess.SP

TL;DR

VEC must jointly manage limited, heterogeneous resources and task offloading under dynamic vehicular conditions and stringent latency requirements. BARGAIN-MATCH combines bargaining-game resource allocation and pricing with many-to-one task matching in a hierarchical VEC architecture. The method is proved stable and weakly Pareto optimal, and simulations report superior system utility and efficiency, especially under heavy workloads.

  • Problem

    VEC resource allocation and task offloading must jointly handle task and server heterogeneity, load imbalance, mobility, channel dynamics, and energy limits.

  • Method

    BARGAIN-MATCH uses bargaining-game incentives for resource allocation and pricing, many-to-one matching for task offloading, and hierarchical coordination across vehicle, edge, controller, and cloud layers.

  • Results

    BARGAIN-MATCH is proved stable and weakly Pareto optimal, while simulations show superior system utility and efficiency, especially under heavy workloads.

  • Takeaways & Limitations

    The proposed cooperative approach provides a stable, weakly Pareto-optimal strategy for jointly allocating resources and offloading tasks in dynamic VEC networks.

  • Takeaways & Limitations

    The model focuses mainly on vehicle-to-edge uploading and omits task downloading because computation results are generally much smaller than inputs; vehicles are also modeled with one CPU core.

Abstract

from arXiv · show

Vehicular edge computing (VEC) is emerging as a promising architecture of vehicular networks (VNs) by deploying the cloud computing resources at the edge of the VNs. This work aims to optimize resource allocation and task offloading in VEC networks. Specifically, we formulate a game theoretical resource allocation and task offloading problem (GTRATOP) that aims to maximize the system performance by jointly considering the incentive for cooperation, competition among vehicles, heterogeneity between VEC servers and vehicles, and inherent dynamic of VNs. Since the formulated GTRATOP is NP-hard, we propose an adaptive approach for resource allocation and task offloading in VEC networks by incorporating bargaining game and matching game, which is called BARGAIN-MATCH. First, for resource allocation, a bargaining game-based incentive is proposed to stimulate the vehicles and VEC servers to negotiate the optimal resource allocation and pricing decisions. Second, for task offloading, a many-to-one matching scheme is proposed to decide the optimal offloading strategies. Third, the dynamic and time-varying features are considered to adapt the strategies of BARGAIN-MATCH to the real-time VEC networks. Moreover, the BARGAIN-MATCH is proved to be stable and weak Pareto optimal. Simulation results demonstrate that the proposed BARGAIN-MATCH achieves superior system performance and efficiency compared to other methods, especially when the system workload is heavy.

1 INTRODUCTION

VEC addresses computation-intensive, delay-sensitive vehicular applications despite limited and heterogeneous resources and highly dynamic network conditions. The paper proposes BARGAIN-MATCH, combining bargaining-based resource allocation with many-to-one task matching, and reports stable, weakly Pareto-optimal, efficient performance.

  • Motivation: VEC brings cloud computing resources closer to vehicles, but vehicular applications require extensive computation and very low latency while vehicle resources remain limited.The setting includes applications such as autonomous driving, navigation, and augmented reality.
  • Challenges: Joint resource management and task offloading are essential because VEC combines limited edge resources with highly dynamic vehicular networks.Challenges include resource competition, heterogeneous task requirements, server heterogeneity, load imbalance, channel dynamics, and vehicle mobility.
  • Problem and framework: The work formulates JRATOP to jointly optimize resource allocation, pricing, and task offloading for maximum system utility.The utility model incorporates VN channels, NOMA, vehicle mobility, task heterogeneity, server heterogeneity, and node energy consumption.
  • Proposed approach: BARGAIN-MATCH uses bargaining-game incentives for intra-server resource allocation and pricing, plus many-to-one matching for inter-server task offloading.The matching supports horizontal edge-edge and vertical edge-cloud collaboration.
  • Results: BARGAIN-MATCH is proved stable, weak Pareto optimal, and polynomial complex, while simulations report superior system utility and efficiency, especially under heavy workloads.Performance is evaluated through theoretical analysis and simulation.

2 RELATED WORK

Prior VEC research addresses offloading, resource management, and joint optimization, but generally does not jointly capture task and server heterogeneity, load imbalance, mobility, channel dynamics, and energy limits. This paper positions cooperative joint optimization as the unresolved problem.

  • Existing approaches: Existing MEC and VEC studies target task offloading, resource allocation, reliability, delay, workload balance, or vehicular-resource exploitation.Approaches include learning, noncooperative games, probabilistic constraints, and risk-aware offloading.
  • Gaps: Many prior VEC offloading strategies insufficiently consider VEC-server resource allocation, and most studies focus on single-server scenarios.This limits their treatment of interactions among multiple servers and server-side resource constraints.
  • Research gap: Although prior work improves VEC performance, it does not jointly explore task and server heterogeneity, server load imbalance, vehicle mobility, channel dynamics, and task-execution energy consumption.The paper distinguishes its contribution by considering these factors together in cooperative resource allocation and task offloading.

3 MODELS AND PRELIMINARIES

The model represents VEC as an SDN-coordinated, hierarchical, time-slotted system linking vehicles, edge servers, a controller, and cloud resources. It captures vehicle mobility, task generation, heterogeneous server capacity, and joint offloading-resource decisions.

  • System overview: The VEC architecture contains vehicle, edge, control, and remote-cloud layers, with edge servers mounted on RSUs and interconnected through high-speed fiber links.Vehicles may process tasks locally or upload them to their connected VEC server using NOMA.
  • Temporal model: The system operates in time slots and updates channel and server-state information at a shorter timescale than vehicle mobility information.Channel state remains approximately constant within a slot, whereas mobility remains approximately constant across several consecutive slots.
  • Mobility model: Vehicle mobility includes direction toward or away from a server and probabilistic direction prediction when future mobility is uncertain.The direction indicator is derived from changes in horizontal distance or represented probabilistically in [-1,1].
  • Vehicle and task models: Vehicles have positions, velocities, computation capabilities, and stochastic task generation, with at most one task generated per vehicle in each time slot.Each vehicle is assumed to have one CPU core.
  • Server model: Edge and cloud servers are heterogeneous in CPU-core counts and maximum computation resources, while each core processes at most one task per time slot.The model permits parallel processing across multiple cores.
  • Decision variables: Each task jointly determines an offloading destination and, for server execution, an allocated computation amount and unit resource price.Destinations include local vehicle execution, an edge server, or the cloud.

3.2 Communication Model

The communication and delay models represent uplink NOMA, probabilistic wireless channels, mobility-related migration, and local, edge, and cloud execution costs. These components connect transmission, computation, handover, pricing, and energy to task performance.

  • Uplink communication: The model focuses on vehicle-to-edge uploading and omits downloading because computation results are generally much smaller than computation inputs.Power-domain NOMA supports simultaneous uploads from multiple requesting vehicles to their attached RSU.
  • NOMA and SIC: Each RSU uses an S_j-SIC receiver capable of successively decoding signals from at most S_j vehicles within its service range.The receiver capability is incorporated into the multi-vehicle uploading model.
  • Channel model: Uplink channel power gain combines probabilistic LoS/NLoS transmission with small-scale fading, path loss, and shadowing.Nakagami-m fading models small-scale fading, while separate path-loss and shadowing components represent large-scale effects.
  • Edge delay: Edge offloading delay includes transmission, computation, and horizontal migration, with handover terms accounting for task and result forwarding between servers.Execution delay depends on the computation resources allocated by the selected edge server.
  • Local and cloud delay: Cloud offloading delay includes transmission, computation, and vertical migration, while local delay depends on vehicle computation capacity.The cloud path includes task and result handover between edge, controller, and cloud layers.
  • Energy model: Energy modeling assigns execution costs to vehicles, VEC servers, or cloud servers and includes resource prices and allocated computation resources.Vehicle computation energy is constrained by a maximum energy limit.

3.4 Utility Model

The utility model quantifies vehicle and server benefits from task offloading, balancing delay satisfaction, execution cost, processing revenue, and energy consumption within social welfare.

  • Vehicle Utility: Vehicle utility combines normalized delay satisfaction and normalized execution cost, weighted by the vehicle’s satisfaction preference.The satisfaction function is logarithmic and depends on total task-completion delay; cost reflects local energy or remote payment.
  • Vehicle Utility: Vehicle execution cost is normalized using energy consumption for local processing or payment for remote computation resources.Resource prices, allocated computation, energy constraints, and vehicle budgets determine the normalized cost.
  • Server Utility: Server utility equals task-processing revenue minus energy-consumption cost, with normalized revenue and cost weighted by the server’s revenue preference.Revenue depends on resource pricing and allocation, while energy consumption is constrained by the server’s energy budget.
  • Social Welfare: Social welfare is the sum of total vehicle utility and total server utility across local, edge, and cloud offloading strategies.If a vehicle processes locally, the providing server receives zero utility.

4 PROBLEM FORMULATION

The formulation maximizes social welfare over time by jointly selecting vehicle offloading strategies and server computation-resource allocation and pricing under mobility, delay, capacity, energy, and payment constraints.

  • Objective: The objective jointly optimizes time-indexed offloading strategies and computation-resource allocation and pricing strategies.The optimization spans T slots and includes vehicle decisions plus allocations from VEC and cloud servers.
  • Offloading Constraints: Each vehicle selects a single offloading strategy, generates at most one task per time slot, and must complete tasks before their deadlines.These constraints govern local, edge, and cloud processing decisions.
  • Mobility Constraints: Mobility constraints require task uploading and result dispatch to finish before the vehicle leaves the relevant server coverage.The formulation accounts for the current and arriving VEC servers and vehicle movement duration.
  • Resource Constraints: Server capacities, CPU-core availability, vehicle and server energy budgets, and vehicle payment limits constrain feasible allocations and prices.The formulation also constrains vehicle velocity and resource assignments.

5 BARGAIN-MATCH

BARGAIN-MATCH solves resource allocation and task offloading through bargaining between vehicles and servers followed by matching across servers, with prices and allocations negotiated through utility-based incentives.

  • Algorithm Overview: BARGAIN-MATCH uses bargaining for intra-server resource allocation and many-to-one matching for inter-server task offloading.The matching supports horizontal edge-edge migration and vertical edge-cloud migration.
  • Bargaining Game: The bargaining game treats vehicles as buyers and VEC or cloud servers as sellers negotiating resource amounts and computation prices.Strategies consist of allocated resources and unit prices, while utilities are defined for both parties.
  • Resource Allocation and Pricing: Optimal resource allocation and pricing are derived from the bargaining game, and an agreement is reached when both vehicle and server utilities are positive.If one party’s utility is negative, that party proposes an optimal price according to the pricing rules.
  • Bargaining Game: The bargaining process discounts future utility, so impatience reflects upload or execution time and larger task deadlines increase server patience.The game models negotiation over the bid-ask spread between resource-price bounds.
  • Negotiation Procedure: The resource-allocation procedure initializes server resources, computes optimal prices, evaluates both utilities, and iterates proposals until agreement or a final proposal is selected.Either player may propose when both utilities are negative.

12 else

The matching stage assigns undecided tasks to edge or cloud servers using preference lists, capacity-aware proposals, rejection, and updates until tasks are matched or rejected by all servers.

  • Matching Fundamentals: The matching market contains undecided tasks and edge or cloud servers, with each task matched to at most one server while servers accept multiple tasks.Task and server preferences are represented by ordered lists.
  • Preference Construction: Preference lists use predicted resource allocations and the utilities of tasks and servers to rank candidate matches.Server preferences rank tasks by server utility, while task preferences rank servers by vehicle utility.
  • Matching Construction: Each iteration lets rejected tasks propose to their most preferred remaining server, after which servers retain their most preferred feasible tasks.Less-preferred tasks are removed and returned to the rejected set.
  • Matching Constraints: Server feasibility is limited by idle CPU cores and total allocated computation resources.The accepted set retains at most n tasks, where n is the server’s currently idle-core count, and satisfies its resource limit.
  • Algorithm Termination: The procedure repeats preference and matching updates until all tasks are matched or unmatched tasks are rejected by every server.The resulting algorithm outputs a matching list, offloading amount, and resource-allocation strategy.

27 end

The paper defines stability through the absence of blocking pairs and presents BARGAIN-MATCH as an algorithm that iteratively allocates resources, offloads tasks, updates welfare, and tracks vehicle mobility.

  • Matching definitions: A matching is stable when no unmatched task-server pair prefers each other over their current matches.This is the paper’s blocking-pair criterion for stability.
  • Theoretical properties: The proposed matching is theoretically stable for every task and server considered by the model.The detailed proof is provided in the supplemental appendix.
  • Algorithm: BARGAIN-MATCH takes vehicles, servers, and tasks as input and outputs social welfare.The algorithm initializes system state and processes tasks over time.
  • Algorithm: The algorithm allocates optimal computation resources, calculates social welfare, updates server task lists and available computation, and updates vehicle mobility.These operations are performed within each time slot.

20 end

The analysis establishes that the proposed matching has desirable theoretical properties: weak Pareto optimality and polynomial worst-case complexity.

  • Theoretical properties: The proposed matching is weak Pareto optimal for each requesting task and server.The proof is provided in Appendix G of the supplemental material.
  • Theoretical properties: BARGAIN-MATCH has polynomial worst-case complexity in each time slot, with complexity O((|E| + 1) · (2|V| + min{|E| + 1, |V|})).Here, |V| and |E| denote the numbers of vehicles and VEC servers.

6 SIMULATION RESULTS AND ANALYSIS

Simulations evaluate BARGAIN-MATCH across system scale, mobility, task size, and execution time. It maintains strong utility and efficiency results, with trade-offs in running time and mobility-sensitive performance.

  • Simulation setup: The simulations use 30 VEC servers on a 10 km six-lane bidirectional road with 100 initially random vehicles.Vehicle speeds range from [2, 30] m/s.
  • Evaluation measures: BARGAIN-MATCH is compared with ELO, EXO, NVO, ECO, NCO, and OPORA across utility, efficiency, and running-time measures.The evaluation includes social welfare, vehicle utility, server utility, APR, ACD, ACR, and average running time.
  • Effect of time: BARGAIN-MATCH outperforms the compared schemes in social welfare, vehicle utility, and server utility over time.The paper attributes this to joint resource allocation, pricing, and cooperative offloading decisions.
  • Effect of vehicle numbers: As vehicle numbers increase, BARGAIN-MATCH maintains relatively superior utility trends, indicating better scalability than the other schemes.Several alternatives show overload, declining utility, or fluctuations as the network grows.
  • Effect of vehicle speed: As vehicle speed increases, BARGAIN-MATCH retains relatively stable downward trends while maintaining superior social welfare, vehicle utility, and server utility.The paper links this to horizontal and vertical task migration with handover delay incorporated.
  • System efficiency: With increasing task size, BARGAIN-MATCH achieves the highest APR, lowest ACD, and highest ACR among the compared schemes.Its APR rises significantly, while ACD rises slightly and ACR declines slightly.
  • Algorithm running time: BARGAIN-MATCH running time increases linearly with vehicle count, while EXO is faster when vehicle numbers are ≤75 and slower in denser networks.Running time decreases approximately 19.28% to 52.02% on the stronger device Ds.

7 DISCUSSION

The evaluation considers standards-based vehicular applications and examines how multiple access schemes affect BARGAIN-MATCH performance in more complicated scenarios.

  • 7 DISCUSSION: Five standards-based vehicular applications are mapped to the task model: collision warning, emergency brake warning, traffic jam warning, hazardous location warning, and speed harmonization.Their task sizes and maximum acceptable delays are specified for simulation.
  • 7 DISCUSSION: The study evaluates BARGAIN-MATCH with OFDMA and discusses extending the approach to more complicated network scenarios.The OFDMA evaluation is provided in the supplementary material.

8 CONCLUSION

The paper addresses computation allocation and task offloading in VEC networks with a hierarchical collaborative framework and proposes BARGAIN-MATCH for the resulting NP-hard optimization.

  • 8 CONCLUSION: A hierarchical framework coordinates task and server heterogeneity through intra-server resource allocation and inter-server offloading across vehicle, edge, and cloud layers.A controller coordinates horizontal and vertical collaboration among the layers.
  • 8 CONCLUSION: BARGAIN-MATCH combines bargaining-based trading for intra-server resource allocation with matching-based collaboration for inter-server task offloading.The formulation jointly optimizes resource allocation, pricing, and task offloading to maximize system utility.
  • 8 CONCLUSION: BARGAIN-MATCH is proved stable, weak Pareto optimal, and polynomial complex.These properties are established for the proposed solution to the NP-hard problem.
  • 8 CONCLUSION: BARGAIN-MATCH achieves superior system, vehicle, and server utility compared with conventional approaches.The reported comparison covers all three utility dimensions.
Loading 2203.14064v3…