PaperlayerView exact revision on arXiv

Source-linked AI summary

Edge-enabled V2X Service Placement for Intelligent Transportation Systems

Abdallah Moubayed, Abdallah Shami, Parisa Heidari, Adel Larabi, Richard Brunner

arXiv:2001.06288v1eess.SPcs.NI

TL;DR

V2X services require low latency, but placing them in hybrid core/edge environments is difficult because edge nodes have limited computation resources. The paper formulates resource-aware optimal placement as a binary integer linear program and develops G-VSPA. Simulations show that the model maintains service QoS, while G-VSPA achieves close-to-optimal performance at lower complexity.

  • Problem

    V2X service placement must account for stringent latency requirements and limited computational resources at edge nodes.

  • Method

    The paper formulates optimal V2X service placement as a binary integer linear programming problem and develops the low-complexity G-VSPA heuristic.

  • Results

    The OVSP model maintains the QoS requirements of different V2X services, while G-VSPA achieves close-to-optimal performance with lower computational complexity.

  • Takeaways & Limitations

    Delay-stringent services are placed at the edge and delay-tolerant services at core nodes while satisfying the different V2X service requirements.

Abstract

from arXiv · show

Vehicle-to-everything (V2X) communication and services have been garnering significant interest from different stakeholders as part of future intelligent transportation systems (ITSs). This is due to the many benefits they offer. However, many of these services have stringent performance requirements, particularly in terms of the delay/latency. Multi-access/mobile edge computing (MEC) has been proposed as a potential solution for such services by bringing them closer to vehicles. Yet, this introduces a new set of challenges such as where to place these V2X services, especially given the limit computation resources available at edge nodes. To that end, this work formulates the problem of optimal V2X service placement (OVSP) in a hybrid core/edge environment as a binary integer linear programming problem. To the best of our knowledge, no previous work considered the V2X service placement problem while taking into consideration the computational resource availability at the nodes. Moreover, a low-complexity greedy-based heuristic algorithm named "Greedy V2X Service Placement Algorithm" (G-VSPA) was developed to solve this problem. Simulation results show that the OVSP model successfully guarantees and maintains the QoS requirements of all the different V2X services. Additionally, it is observed that the proposed G-VSPA algorithm achieves close to optimal performance while having lower complexity.

I. INTRODUCTION

V2X services support ITS applications but often require stringent latency, motivating MEC-based placement near vehicles. This work formulates resource-aware placement and develops a lower-complexity heuristic for hybrid core/edge environments.

  • V2X supports applications including autonomous driving, traffic-flow optimization, and in-car entertainment, with some requiring stringent end-to-end latency.
  • MEC brings computing and storage closer to vehicles to reduce service latency and support real-time, mobility, and location-aware services.
  • Limited edge computation and storage make V2X service placement and high availability challenging, especially for autonomous driving and traffic safety.
  • The work formulates optimal V2X service placement in a hybrid cloud/edge environment as a binary integer linear programming problem.
  • It develops the low-complexity Greedy V2X Service Placement Algorithm (G-VSPA) and evaluates both approaches using delay and average node computing utilization.
  • The paper identifies resource-aware V2X service placement as an unaddressed problem in hybrid environments.

1) Communication Modes:

V2X systems use four communication modes to cover interactions among vehicles, infrastructure, networks, and pedestrians. Their applications differ substantially in throughput and latency requirements, from safety-critical driving to less stringent infotainment.

  • Communication Modes: V2N connects vehicles with application servers, while V2I connects vehicles with roadside infrastructure for services including infotainment, traffic optimization, navigation, and safety.
  • Communication Modes: V2P directly connects vehicles with vulnerable road users to alert both parties to possible collisions.
  • Applications: V2X applications span autonomous or cooperative driving, traffic safety, traffic efficiency, and infotainment, with distinct throughput and latency requirements.
  • Applications: Autonomous or cooperative driving can require throughput ≥5 Mbps and latency ≤10 ms, whereas infotainment can tolerate latency up to 1 sec.

B. Multi-access/Mobile Edge Computing:

MEC extends cloud computing by shifting resources toward the network edge, aiming to reduce latency and cloud-core signaling overhead. The paper highlights MEC applications across smart environments, healthcare, AR/VR, retail, and connected vehicles.

  • MEC brings computational power closer to users to reduce experienced latency and signaling overhead in the cloud core.
  • MEC extends cloud computing by shifting computational resources to network-edge locations.
  • MEC Applications: MEC supports smart homes by providing processing and storage for data generated by sensors and connected appliances.
  • MEC Applications: MEC applications include smart-city video analysis, healthcare support, augmented and virtual reality, and retail connectivity and automation.
  • MEC Applications: For connected vehicles, MEC servers can support real-time traffic monitoring and analysis at intersections.
  • The paper focuses on using MEC for V2X application and service placement.

III. RELATED WORK

Prior MEC-for-V2X studies addressed individual applications or latency effects, but did not jointly optimize placement across services while accounting for computational resources, delay, and redundancy.

  • Prior work applied MEC to traffic surveillance, V2X security, adaptive video streaming, and cellular V2X latency reduction.One study reported reducing average E2E latency from around 110 ms to around 25 ms through MEC-based infrastructure.
  • Most existing studies focused on one V2X service or application at a time.
  • Earlier work examined latency impacts without considering computational power available at edge nodes.
  • This paper addresses joint placement of different V2X services while considering computational resources, delay requirements, and redundancy requirements.

IV. SYSTEM MODEL

The system models V2X service placement along an LTE-A-covered highway with MEC-enabled access-edge nodes connected to a core cloud, using services with distinct latency requirements.

  • The modeled highway contains multiple lanes, evenly spaced vehicles, LTE-A eNBs, RSUs, and MEC hosts connected to a core cloud data center.Each eNB or RSU has computing power comprising CPU, memory, and storage.
  • The system considers Cooperative Awareness, Decentralized Environmental Notification, and media downloading or streaming services.
  • Cooperative Awareness uses periodic CAM messages and typically requires 10-20 ms latency.CAMs are typically 300-byte messages sent every 100 ms, approximately 3 Kbytes/sec.
  • Decentralized Environmental Notification uses event-triggered DENM messages and tolerates latency up to 100 ms.DENMs are typically around 500 bytes and can be sent every 100 ms, approximately 5 Kbytes/sec.
  • Media downloading and streaming has the least stringent delay requirement, tolerating up to 1 second.
  • The placement model minimizes aggregate average latency subject to delay, computational-resource, redundancy, and placement constraints.

A. Key Mathematical Notations:

The notation defines the vehicles, service instances and types, candidate computing nodes, delay parameters, resource requirements, and binary placement decisions used by the OVSP model.

  • V denotes vehicles, S service instances, U unique service types, and S_u the instances belonging to service type u.
  • C is the set of core or edge computing nodes available to host V2X services.
  • d^c_s,v denotes the maximum delay for vehicle v served by instance s at node c, while Dth_s is its maximum tolerable delay.
  • R^i_s specifies service s's computational requirement for CPU, memory, or storage, and Cap^i_c specifies node c's maximum available resource.
  • Redth_u is the minimum redundancy requirement for service type u, with required instances proportional to vehicles within communication coverage.
  • X^c_s is a binary variable equal to 1 when service instance s is placed on node c and 0 otherwise.

B. Problem Formulation:

The OVSP formulation is a binary integer linear program that minimizes aggregate average service latency while enforcing QoS, capacity, redundancy, node-separation, and placement constraints.

  • The OVSP model is formulated for hybrid core/edge computing, with an illustrative example placing three services across three nodes for two vehicles.
  • The objective function minimizes aggregate average delay/latency across all V2X service instances.
  • Constraint (2b) keeps each service instance's average vehicle delay below its maximum latency threshold.
  • Constraint (2c) prevents assigned services from exceeding each computing node's available computational resources.
  • Constraints (2d) and (2e) enforce required redundancy and place distinct instances of a service type on different nodes.
  • Constraint (2f) assigns every service instance to exactly one node, while (2g) makes placement variables binary.
  • The generic OVSP formulation is a binary integer linear programming problem applicable to V2X service or application placement.

C. Complexity:

The placement problem has exponential search complexity, motivating the G-VSPA heuristic. G-VSPA places services on nearby nodes with sufficient capacity while targeting low aggregate latency.

  • Complexity: The placement search space is 2^|C||S|, making exact optimization computationally expensive as nodes and services increase.For |C| = 10 and |S| = 10, the search space is 1.267 × 10^30 combinations.
  • Heuristic approach: G-VSPA places each service instance at the closest computing node that has sufficient computing capacity.The heuristic is intended to minimize aggregate latency and is generic across V2X service placement processes.
  • Heuristic approach: G-VSPA sorts services by ascending delay tolerance and evaluates candidate nodes for each service instance.For each instance, it checks the node with minimum average delay/latency against placement requirements.
  • Complexity: The algorithm has time complexity O(|C||S|), compared with the exponential search space of exact placement.With |C| = 10 and |S| = 10, the reported complexity is approximately 100 operations.

VII. PERFORMANCE EVALUATION

The evaluation uses a MATLAB-based system-level simulator to assess placement performance with delay, latency distributions, and resource-utilization metrics, including comparison with GA.

  • Evaluation methodology: A MATLAB-based system-level simulator evaluates the OVSP model and G-VSPA algorithm using multiple performance metrics.The metrics include average delay/latency, delay/latency probability density function, and computational resource utilization.
  • Baselines: The evaluation compares the proposed methods with the Genetic algorithm as a previously proposed meta-heuristic for linear integer programming.The comparison is performed as part of the performance evaluation of OVSP and G-VSPA.
  • Evaluation methodology: The G-VSPA procedure iterates over service instances and candidate computing nodes before returning placement variables and aggregate delay.Its pseudocode defines service, node, and vehicle sets, checks remaining capacity, assigns feasible nodes, and updates capacity.
  • Evaluation methodology: The pseudocode returns the placement decisions and aggregate delay after processing the service instances.The return operation follows the nested service and instance loops.

A. Simulation Setup:

The simulation evaluates V2X placement in LTE-based scenarios with heterogeneous service delay tolerances, node delays, and constrained computing resources. Results show increasing delay and utilization with vehicle count, while G-VSPA remains near-optimal with much lower runtime.

  • Simulation Setup: The LTE-based system models CAM, DENM, and media downloading services with delay tolerances of 20, 50, and 150 ms, respectively.CAM computational requirements are modeled as those of a medium-sized virtual machine.
  • Simulation Setup: Vehicle-to-RSU, vehicle-to-eNB, and vehicle-to-core delays follow U(1, 10) ms, U(20, 40) ms, and U(60, 130) ms distributions, respectively.The parameters are used in small-scale and large-scale scenarios.
  • Small Scale Scenario: Aggregate average delay/latency increases with vehicle count because more service instances are required and edge capacity limitations shift more instances to the core.Both OVSP and G-VSPA keep aggregate delay/latency below the threshold for 80 vehicles.
  • Small Scale Scenario: Average computing resource utilization increases with vehicle count, with edge nodes saturating quickly because of their limited computational resources.The evaluated resource measures are average CPU and memory utilization of a computing node.
  • Small Scale Scenario: G-VSPA achieves close to optimal performance with runtimes near 0.2 ms, versus around 70 ms for OVSP and close to 450 ms for GA.G-VSPA runtime remains more stable as vehicle count increases, while OVSP runtime increases.

2) Large Scale Scenario:

In the larger scenario, G-VSPA was used because solving OVSP at scale was time-consuming, while the results preserved service-specific latency behavior and QoS thresholds. Cost-efficient placement and delay–cost trade-offs remain open extensions.

  • Large Scale Scenario:: G-VSPA was implemented in Scenario 2 because solving the OVSP model has time complexity concerns in the larger environment.The authors also cite potentially inaccurate GA results caused by unsuitable population initialization at larger scale.
  • Large Scale Scenario:: CAM and DENM average delay/latency remained stable as vehicle numbers increased, whereas media downloading latency increased.The authors attribute this difference to the stricter latency requirements of CAM and DENM.
  • Large Scale Scenario:: CAM service latency stayed below 20 ms, while media downloading latency ranged from 20 to 130 ms and remained below its 150 ms threshold.The distributions indicate placement of media service instances at both edge and core nodes.
  • Large Scale Scenario:: The study identifies cost-efficient placement, delay–cost trade-offs, and throughput requirements of compound services as directions for further work.Core placement tends to be more cost-efficient, while compound services may require higher network throughput.
Loading 2001.06288v1…