Abstract
Vehicle-to-everything (V2X) communications, enabled by cellular device-to-device (D2D) links, have recently drawn much attention due to its potential to improve traffic safety, efficiency, and comfort. In this context, however, intracell interference combined with demanding latency and reliability requirements of safety vehicular users (V-UEs) are challenging issues. In this paper, we study a resource allocation problem among safety V-UEs, non-safety V-UEs, and conventional cellular UEs (C-UEs). Firstly, the resource allocation problem is formulated as a three-dimensional matching problem, where the objective is to maximize the total throughput of non-safety V-UEs on condition of satisfying the requirements on C-UEs and on safety V-UEs. Due to its NP-hardness, we then exploit hypergraph theory and propose a local search based approximation algorithm to solve it. Through simulation results, we show that the proposed algorithm outperforms the existing scheme in terms of both throughput performance and computational complexity.
Introduction
As vehicles become increasingly connected, they rely on Device-to-Device (D2D) links to share critical data. However, the radio spectrum is a finite and crowded resource. In a typical V2X scenario, three distinct groups compete for the same uplink resources: conventional cellular users (C-UEs), safety vehicular users (V-UEs) requiring low latency and high reliability for emergency alerts, and non-safety vehicular users (V-UEs) demanding high throughput for applications like video streaming.
The core challenge lies in Resource Management (RRM): assigning these three user types to the same Resource Block (RB) without causing interference that compromises safety messages or degrades data throughput. This paper argues that traditional 1-to-1 pairing is insufficient, proposing instead a 3-way "triplet" matching (C-UE + Safety V-UE + Non-safety V-UE) to maximize spectrum efficiency.
System Model
The system considers a cellular network where V2X communications are underlaid on the uplink of cellular users. The model accounts for the complex interference environment where transmissions from one user type can disrupt the reception of others.
As shown in the figure above, the base station manages the desired channel from the C-UE while dealing with interference from vehicular transmitters. Simultaneously, vehicular receivers must manage interference from both the C-UE and other vehicular links.
Proposed Methodology: 3D-Matching Based Resource Allocation
The authors formulate the resource allocation as a three-dimensional weighted matching problem. Since this problem is NP-hard, a three-stage algorithm is proposed to find an efficient solution.
Stage 1: Power Optimization
The algorithm first determines the optimal transmit power and potential data rates for every possible combination of triplets (C-UE, Safety V-UE, Non-safety V-UE) across all available resource blocks.
Stage 2: Hypergraph Construction
The potential combinations are represented as a hypergraph. Vertices represent the users, and hyperedges represent the triplets. This hypergraph is then converted into a conflict graph where nodes represent potential assignments and edges represent resource conflicts or interference.
Stage 3: Local Search via "k-claws"
The core innovation is a local search algorithm that improves an initial greedy solution by searching for "k-claws." A k-claw is a subgraph where a "center" node can be replaced by multiple "talon" nodes to increase the total weight (throughput) of the matching. The study found that 2-claw searches provide the best balance between performance and computational overhead.
Performance Evaluation
The proposed 3D-VRAA (3D-matching based V2X Resource Allocation Algorithm) was evaluated using the METIS urban environmental model. Simulations were conducted in a 500m x 500m urban grid with 40 Resource Blocks.
Key results include:
- Throughput: The 3D-VRAA outperformed the Iterative Hungarian Method (IHM), a common baseline for matching problems.
- Complexity: The algorithm achieved a complexity of $O(n \times L'^2)$, making it significantly more efficient than the $O(S^3)$ complexity of the IHM in large-scale scenarios.
- Scalability: The algorithm maintained higher and more stable throughput for non-safety users as the number of safety-critical V-UEs increased.
Conclusion
By leveraging hypergraph theory and local search techniques, this research provides a robust framework for managing the competing demands of safety and non-safety V2X traffic. The transition from 2D to 3D matching significantly boosts spectrum reuse, while the "k-claw" local search ensures high performance with manageable computational complexity. Future work will look into adapting these methods for high-speed highway scenarios and decentralized environments.
Summary updated