1
RATIO: Redundancy-Controlled Stochastic Routing for Reliable Vehicular Multi-Hop Networking
arXiv:2606.17481v1 [cs.NI] 16 Jun 2026
Lei Lei , Student Member, IEEE, and Xudong Wang , Fellow, IEEE
Abstract—Reliable, low-latency multi-hop data delivery in vehicular networks is increasingly demanded, yet remains challenging due to frequent route failures caused by high mobility and intermittent blockage. While redundancy-based routing enhances robustness by forwarding packets over multiple paths, over-replication intensifies contention and introduces additional delay, highlighting the need to carefully managing redundancy– reliability trade-off. However, conventional deterministic multipath replication typically duplicates packets to an integer number of branches, making the redundancy level hard to tune and adapt to time-varying network dynamics in vehicular networks. To this end, Redundancy-Controlled Stochastic (RATIO) routing is proposed in this paper. For each active flow, RATIO constructs a weighted reduced directed acyclic graph (DAG) as the routing structure, where edge weights specify per-link forwarding probabilities. At fork nodes, the aggregate outgoing forwarding probability is allowed to exceed one and a modulobased stochastic forwarding rule is employed to guarantee feasible forwarding, thereby enabling continuously controllable redundancy. An idealized RATIO design is formulated as a loadminimizing optimization subject to per-flow timely-reliability and link-capacity constraints, but the problem is generally intractable under time-varying wireless dynamics. Accordingly, a practical heuristic, termed H-RATIO, is developed. H-RATIO constructs a compact reduced DAG by taking the union of candidate paths and optimizes forwarding probabilities via local scoring and replication-adjustment iterations. Extensive tracedriven SUMO/ns-3 co-simulations demonstrate that RATIO/HRATIO consistently achieves the highest timely PDR compared to baselines, while providing substantially better delivery efficiency, especially under high-load scenarios.
I. I NTRODUCTION Recently, vehicular networks are increasingly expected to support reliable and low-latency delivery not only for safetycritical services, but also for data-intensive traffic such as shared sensor streams, high-definition (HD) map updates, and multimedia content [1–3]. Considering limited infrastructure coverage and intermittent connectivity caused by vehicle mobility, multi-hop networking is essential in vehicular networks In practice, such services must often be delivered under intermittent, where data packets are relayed through intermediate vehicles towards their destinations [4–6]. Due to high mobility and intermittent non-line-of-sight (NLOS) blockage, multi-hop transmissions in vehicular networks are prone to frequent route failures In particular, a single broken link can trigger the route re-computation and recovery of the entire path, which introduces additional delay and packet Lei Lei is with Global College, Shanghai Jiao Tong University. Xudong Wang is with The Hong Kong University of Science and Technology (Guangzhou). Corresponding author: Xudong Wang (e-mail: [email protected]).
loss, and can cause abrupt degradation of end-to-end delivery performance [7]. To address this challenge, mobility-aware and stabilitybased routing policies have been proposed. These methods first predict link stability from vehicle motions and/or historical link-quality measurements, and then incorporate the resulting stability estimates into routing decisions to favor longer-lived paths [8, 9]. In this way, route breakages can be reduced and the frequency of route recovery can be lowered. However, relying on link stability alone is often insufficient. The end-toend path still follows a single-route structure and thus remains inherently vulnerable to any hop breakage along the selected route. Another widely used approach is to introduce redundancy. A representative method is multi-path replication routing, where each packet is duplicated and sent along multiple paths towards the destination, thereby increasing the probability that at least one copy survives from transient path breakages [10]. Opportunistic forwarding, on the other hand, exploits the broadcast nature of wireless channels by allowing multiple candidate relays to participate the forwarding process and hence increases path diversity [11]. However, redundancy is not free. Each additional copy occupies wireless channel resources, increases contention and collision probability, and may further enlarge queueing delay under finite network capacity. Therefore, redundancy should not be used simply whenever multiple forwarding opportunities are available. Instead, it should be carefully controlled according to network conditions and service requirements. For example, under low mobility and high traffic load, a lower redundancy level is preferable to avoid unnecessary channel occupation and congestion. In contrast, under high mobility and low traffic load, a higher redundancy level can be beneficial because additional packet copies improve the chance of timely delivery. However, traditional deterministic multi-path replication provides only coarse-grained redundancy control. The number of selected paths is discrete, and the number of transmissions of each packet is always an integer. For example, a packet may be sent once, twice, or three times, but the redundancy level cannot be smoothly adjusted between these integer choices. Such discrete control may be too coarse for vehicular networks, where link quality, mobility, and traffic load change over time. To this end, a novel routing scheme termed RedundancyControlled Stochastic Routing (RATIO) is proposed in this paper. The main idea of RATIO is simple: instead of forcing each flow to use a single path or blindly replicating every packet over multiple paths, RATIO lets each flow use a
2
compact set of forwarding opportunities and controls how frequently each forwarding link is used. Specifically, each flow is represented by a reduced directed acyclic graph (DAG), and forwarding probabilities are assigned to the outgoing links in this DAG. These probabilities determine both the preferred forwarding directions and the average amount of redundancy introduced during packet delivery. For instance, some packets may be forwarded through one outgoing link while a certain fraction of packets are duplicated over two outgoing links, leading to an average redundancy level such as 1.3 or 1.7. In this way, RATIO enables continuous tuning of redundancy and provides more precise control than conventional multipath replication, allowing the routing scheme to better adapt to changing network dynamics. It should be note that “continuous” tuning of redundancy means that the expected number of transmissions for each packet can be any positive value no smaller than one, although the actual transmissions of each individual packet are still discrete. The ideal RATIO design can be formulated as an optimization problem that jointly determines the reduced DAG and the forwarding probabilities. The objective is to reduce transmission load while satisfying link-capacity constraints, delay budgets, and reliability requirements of different flows. However, this problem is difficult to solve exactly for two main reasons. First, the end-to-end delay and timely packet delivery ratio (PDR) under stochastic forwarding and timevarying vehicular connectivity are not analytically tractable in closed form. Second, the construction of the reduced DAG itself is combinatorial: different subsets of links and paths may lead to different reliability, delay, and load trade-offs. This combinatorial structure makes the exact RATIO optimization NP-hard and unsuitable for real-time deployment in large-scale vehicular networks. Therefore, a practical heuristic scheme, termed H-RATIO is further developed in this paper. H-RATIO follows the same principle as RATIO but avoids solving the exact optimization problem. At a high level, it first identifies a compact and reliable forwarding structure from the current network snapshot, and then adjusts the forwarding probabilities according to lightweight estimates of delivery reliability and transmission load. If the estimated reliability is insufficient, HRATIO increases redundancy by allowing more packet copies to be created on promising forwarding links. If the estimated channel load becomes too high, it reduces redundancy to avoid congestion. Thus, H-RATIO provides a scalable and deployable realization of the RATIO idea using only shortterm network observations and local link indicators. Finally, extensive trace-driven SUMO/ns-3 co-simulations are conducted to evaluate the proposed scheme. Urban vehicle mobility traces are generated by SUMO and replayed in ns-3, where packet-level multi-hop transmissions, wireless contention, and queueing effects are simulated. The proposed H-RATIO scheme is compared with representative baseline routing schemes under different traffic loads and mobility conditions. The results show that H-RATIO improves timely PDR and delivery efficiency by introducing only necessary redundancy, while avoiding the excessive transmission overhead and congestion effects commonly caused by fixed multi-path
replication. The contributions of this paper are summarized as follows: • A routing method termed redundancy-controlled stochastic routing (RATIO) is proposed and formally formulated, where per-edge forwarding probabilities are optimized over flow-specific reduced DAGs by minimizing total transmission load under link capacity, flow PDR, and flow delay constraints. • An ideal RATIO design is formulated as a loadminimization problem under reliability and delay constraints, and a practical per-period heuristic RATIO (HRATIO) is developed to address the non-convexity and intractability of the ideal RATIO optimization under partial and short-term observations, where reduced DAGs are constructed using link-quality indicators and forwarding probabilities are assigned via lightweight scoring and iterative replication-factor adjustment. • Extensive trace-driven SUMO/ns-3 co-simulations are conducted with realistic mobility replay and packet-level forwarding to evaluate the proposed H-RATIO scheme. It is shown that, under both moderate and high load, H-RATIO matches or exceeds the timely PDR of fixed replication at much lower transmission load and delivery cost. The rest of this paper is organized as follows. In Section III, the system model, including the network, traffic, and routing models, is introduced. The description and ideal problem formulation of RATIO are given in Section IV, and a practical heuristic RATIO (H-RATIO) scheme is developed in Section V. In Section VI, the performance of RATIO is evaluated and compared with several baselines using tracedriven mobility and packet-level simulation. Finally, the paper is concluded in Section VII. II. R ELATED W ORK Vehicular multi-hop routing under high mobility has been studied from multiple perspectives, including quality-ofservice (QoS)-driven routing, mobility-robust VANET/V2X routing, and redundancy-based forwarding. The most relevant threads are summarized below. A. QoS Routing in Mobile Wireless Networks QoS routing aims to satisfy end-to-end constraints such as delay (or deadline), packet delivery ratio (PDR), and bandwidth under time-varying wireless resources [12–14]. In multihop wireless settings, QoS routing is commonly formulated as constrained shortest-path or multi-constraint path selection, where link weights/constraints reflect latency, loss probability, capacity, or interference. Such formulations remain computationally challenging even under static graphs, and practical solutions have typically relied on heuristics, relaxations, or decompositions that trade optimality for tractability [13, 14]. Early on-demand QoS routing mechanisms have been proposed for multi-hop mobile networks, where QoS-feasible routes are discovered and maintained on demand under dynamic topology [15]. A representative direction has been the integration of bandwidth estimation into route selection so that
3
QoS decisions can be made using predicted residual capacity rather than purely hop-count or delay surrogates [16]. Anycast and group-oriented variants have also been studied, where mobility awareness has been combined with QoS constraints to improve reachability and service continuity in mobile ad hoc settings [17]. More recently, QoS routing has been revisited in software-defined and cross-layer frameworks, where multiple paths can be jointly optimized under centralized control or cross-layer state, e.g., PHY/MAC indicators [18, 19]. QoSdriven routing has also been extended to specialized mobile wireless paradigms, including cognitive radio ad hoc networks, where channel uncertainty and spectrum dynamics further complicate QoS satisfaction [20], and urban MANETs, where QoS adaptivity is emphasized under dense mobility and heterogeneous traffic [21]. In vehicular networks, QoS routing has often been coupled with mobility-robust metrics, where stability predictors, e.g., link expiration time (LET), and historical link-quality estimates are incorporated to avoid fragile links while meeting delay/throughput requirements [2, 3, 8, 9]. Cross-layer indicators, e.g., channel contention, queueing delay proxies, or estimated link service rates, have also been integrated into routing metrics to improve QoS compliance under shared-medium access [2]. While robustness has been improved compared with purely shortest-path routing, the dominant decision unit has largely remained a path, or a small set of paths, that is selected and used deterministically within a routing period. As a result, QoS violations may still be triggered by transient disruptions, including intermittent blockage, interference spikes, and contention bursts, that cannot be fully captured by averaged metrics, especially when routing updates are constrained by protocol overhead and control latency. B. VANET/V2X Routing Under Mobility Classical ad hoc routing protocols, including reactive topology-based designs (e.g., AODV [22] and DSR [23]) and proactive link-state designs (e.g., OLSR [24]), have often been observed to degrade in vehicular environments due to frequent route breaks and the associated route-maintenance overhead under rapid topology changes [1, 2, 7]. To improve delivery performance, extensive V2X routing research has been developed with an emphasis on geographic routing and stability prediction. Geographic routing reduces route-maintenance cost by leveraging location information and local neighbor states [25– 28]. GPSR is a canonical example that combines greedy forwarding with perimeter recovery [29]. Beyond pure geometry, additional signals, e.g., direction/speed, two-hop neighborhood structure, or trust management, have been incorporated to improve robustness against unreliable neighbors and malicious relays [30]. However, geographic routing highly relies on accurate position information and timely neighbor-state updates. In highly dynamic vehicular environments, GPS errors, outdated local information, and intermittent NLOS blockage may lead to unreliable next-hop selection and frequent recovery operations. Complementary to geographic designs, stability-oriented metrics such as link-expiration-time (LET) predictors have
been widely used to prefer longer-lived links and paths under mobility [8, 9, 31, 32]. Future connectivity has typically been estimated from historical link-quality observations and mobility patterns [9], and ML-based link-stability prediction has also been explored to improve decision making under uncertainty [33]. Nevertheless, the effectiveness of stabilitydriven routing remains bounded by prediction accuracy. Even if a path is predicted to be relatively stable, it may still be disrupted by unexpected NLOS blockage, interference spikes, or contention bursts. Moreover, most stability-driven methods still make routing decisions at the path level and do not explicitly control how much redundancy should be introduced when stability prediction is uncertain. In RATIO, stability indicators are used as filters or priors during reduced-DAG construction, while controlled redundancy is further leveraged to provide additional resilience against short-term disruptions. C. Opportunistic Routing and Multipath Routing Opportunistic routing exploits the broadcast nature of wireless channels by selecting forwarders dynamically among candidates that successfully receive a packet [34]. Related ideas also appear in store-carry-forward mechanisms and epidemic-style spreading, which can improve delivery probability at the cost of increased delay and transmission overhead, and are therefore particularly suitable for delay-tolerant regimes [35]. ExOR coordinates such forwarding choices to improve throughput and reliability [11], and networkcoding-assisted variants such as MORE combine opportunistic reception with coded transmissions to reduce coordination overhead and improve robustness [36]. A broad overview of opportunistic routing and its design space is provided in [37]. While opportunistic designs can harvest receiver diversity, uncontrolled replication, or overly aggressive forwarder sets, can substantially increase channel contention in V2X, particularly under hidden-terminal effects and rapidly varying link conditions [37]. Thus, opportunistic routing improves robustness by exploiting diversity, but its reliability gain may come with uncontrolled or hard-to-predict transmission overhead. This becomes problematic for low-latency vehicular services, where excessive contention and queueing can reduce timely PDR. Multipath routing improves reliability by exploiting path diversity and providing alternate delivery attempts when a primary path fails. Representative designs extend ondemand routing to maintain multiple next hops/paths, e.g., via on-demand multipath distance-vector mechanisms [10]. In VANET/V2X settings, multipath routing has been widely studied for bandwidth-intensive traffic such as video streaming, often coupled with optimization-based path selection and rate allocation to improve throughput and reduce packet loss [38– 40]. These methods typically select a small set of paths and then deterministically split or replicate traffic among them. However, in highly loaded V2X networks, aggressive multipath usage can inflate channel occupancy and worsen collisioninduced losses and latency, causing reliability degradation once the network enters a congested regime [2]. More importantly, traditional multipath replication provides only coarsegrained redundancy control because the number of paths and
4
the number of packet copies are discrete. The proposed RATIO routing scheme addresses this issue by enabling fine-grained redundancy control beyond integer path replication. In summary, existing studies provide important tools for vehicular multi-hop delivery, including QoS-aware path selection, mobility-aware/stability-based routing, opportunistic forwarding, and multipath routing. However, a common limitation is that redundancy is either not explicitly controlled or is controlled only in a coarse-grained manner. QoS and stability-based routing mainly improve path selection but remain vulnerable to transient link disruptions. Opportunistic and multipath routing improve reliability through diversity, but may introduce excessive channel occupancy, contention, and delay when redundancy is not carefully regulated. These limitations motivate the design of RATIO, which treats redundancy as a controllable routing resource. By assigning forwarding probabilities over a reduced DAG, RATIO can tune the expected redundancy level continuously according to mobility, traffic load, and per-flow reliability requirements, thereby balancing timely delivery reliability and transmission overhead. III. S YSTEM M ODEL In this section, the system model of the considered V2X network is presented, including the network model, traffic model, routing model, and performance metrics.
A. Network Model Consider a vehicular network composed of core server, several roadside units (RSUs), and multiple vehicles. A timevarying directed graph is used to capture connectivity among these nodes. Specifically, the network at time 𝑡 is represented by 𝐺 (𝑡) = V, E (𝑡) , where V is the node set and E (𝑡) is the time-varying set of directed links. The node set is partitioned as V = {𝑣 core } ∪ Vrsu ∪ Vveh , where 𝑣 core denotes a core server (CORE), Vrsu denotes the set of roadside units (RSUs), and Vveh denotes the set of vehicular nodes. Each vehicle 𝑖 ∈ Vveh is associated with a mobility trajectory p𝑖 (𝑡) ∈ R2 (or R3 ) over time. A directed wireless link (𝑖, 𝑗) is considered available at time 𝑡 when link connectivity conditions (e.g., the received signal strength exceeds a threshold) are satisfied. The resulting wireless link set is denoted by Ewireless (𝑡). In addition, wired backhaul links (usually highcapacity) are included to represent CORE–RSU connections. These links are collected in Ewired and are assumed to be highly reliable and always available. Accordingly, the overall link set is written as E (𝑡) = Ewired ∪ Ewireless (𝑡).
B. Traffic Model Let F denote the set of unicast flows. Each flow 𝑓 ∈ F is described by end 𝑓 = 𝑠 𝑓 , 𝑑 𝑓 , 𝑟 𝑓 , 𝑡 start , 𝑓 ,𝑡𝑓 where 𝑠 𝑓 ∈ V is the source node, 𝑑 𝑓 ∈ Vveh is the destination end vehicle, 𝑟 𝑓 is the application bit rate, and [𝑡 start 𝑓 , 𝑡 𝑓 ) is the active time interval of the flow. We assume a fixed packet size of 𝐿 pkt bits, and hence a constant-rate flow with bit rate 𝑟 𝑓 generates packets at mean rate 𝑟 𝑓 /𝐿 pkt packets per second during its active interval. Typical QoS requirements are imposed on each flow, including (i) a maximum end-to-end delay budget 𝐷 max 𝑓 , and (ii) a minimum timely delivery requirement expressed via packet delivery ratio (PDR) target 𝜂 𝑓 . C. Routing Model A centralized routing controller is assumed to operate over routing periods of fixed duration 𝑇 > 0. Routing periods are indexed by K = {0, 1, 2, . . . }, where period 𝑘 ∈ K corresponds to the time interval [𝑘𝑇, (𝑘 + 1)𝑇). Let 𝑎 (𝑘) and F (𝑘) denote the the flow activity and active𝑓 flow set in period 𝑘, respectively. We have and (𝑘 + 1)𝑇 > 𝑡 start 1, if 𝑘𝑇 < 𝑡 end 𝑓 , 𝑓 (𝑘) 𝑎𝑓 = 0, otherwise, and (𝑘) F (𝑘) = 𝑓 ∈ F : 𝑎 𝑓 = 1 . At the beginning of each period (i.e., at 𝑡 = 𝑘𝑇), a connectivity snapshot 𝐺 (𝑘) is observed: 𝐺 (𝑘) = V, E (𝑘) , E (𝑘) = E (𝑘𝑇).
Based on 𝐺 (𝑘) and short-term link estimates, routing decisions are computed and then applied throughout [𝑘𝑇, (𝑘 + 1)𝑇). For each active flow 𝑓 ∈ F (𝑘) , a directed forwarding subgraph D (𝑘) is induced: 𝑓 , D (𝑘) = V𝑓(𝑘) , E (𝑘) 𝑓 𝑓 ⊆ E (𝑘) collects the directed edges that may carry where E (𝑘) 𝑓
packets of flow 𝑓 during period 𝑘, and V𝑓(𝑘) collects the participating relay/receiver nodes. For deterministic singlereduces to a directed path from 𝑠 𝑓 to 𝑑 𝑓 . path routing, D (𝑘) 𝑓 At the node level, routing decisions are specified as follows. For each flow 𝑓 , period 𝑘, node 𝑖, and outgoing neighbor 𝑗: • In deterministic single-path schemes, a binary decision 𝑓 , (𝑘) 𝑥𝑖 𝑗 ∈ {0, 1} is used to indicate whether packets of flow 𝑓 are forwarded from 𝑖 to 𝑗 in period 𝑘. • In probabilistic or load-splitting schemes, a forwarding 𝑓 , (𝑘) weight (or probability) 𝜋 𝑖 𝑗 ∈ [0, 1] is assigned to indicate the fraction or probability with which packets are forwarded along (𝑖, 𝑗) in period 𝑘. is Different routing strategies are distinguished by how D (𝑘) 𝑓 𝑓 , (𝑘)
constructed and how {𝑥𝑖 𝑗
𝑓 , (𝑘)
} or {𝜋 𝑖 𝑗
} is assigned.
5
Route of flow 1
(a) No replication: 𝑗1 = 0.6, 𝑗2 = 0.4 (sum to 1)
Route of flow 2
𝒋1 C
𝒋2
0
D2
0.6
1
𝑈 = 0.64 (forward to: 𝑗2 ) (b) Replication possible: 𝑗1 = 0.6, 𝑗2 = 0.6, 𝑗3 = 0.4 (sum to 1.6) B
S1
𝒋1
D1 A
𝒋2 0
S2
𝒋2 𝒋3
0.2
0.6
1
𝑈 = 0.35 (forward to: 𝑗1 and 𝑗3 )
Fig. 1: Illustration of the proposed redundancy-controlled stochastic routing (RATIO) scheme. D. Performance Metrics To characterize the reliability–cost trade-off of routing schemes, the timely packet delivery ratio (PDR), also termed as the delay-constrained PDR, is used as the reliability metric, while the total transmission load over all links is used to quantify transmission cost. Specifically, for a given flow 𝑓 , let 𝑁 𝑓 denote the number of unique packets generated at the source over the evaluation horizon. Let 𝑁 del (𝐷 max ) denote the number of unique packets 𝑓 𝑓 that are successfully received by the destination 𝑑 𝑓 within the deadline 𝐷 max (duplicate receptions are excluded). The timely 𝑓 PDR of flow 𝑓 is defined as PDR 𝑓 =
max 𝑁 del 𝑓 (𝐷 𝑓 )
𝑁𝑓
.
To measure transmission cost, for each routing period 𝑘, let
(𝑘) 𝐿 𝑖 𝑗 denote the transmission load on directed link (𝑖, 𝑗) during
period 𝑘 (including transmissions of replicated copies). The aggregate load in period 𝑘, denoted by 𝐿 (𝑘) , is then defined as Õ 𝐿 𝑖(𝑘) 𝐿 (𝑘) = 𝑗 , (𝑖, 𝑗 ) ∈ E (𝑘)
and the total transmission load over the evaluation horizon, denoted by 𝐿 tot , is given by Õ 𝐿 tot = 𝐿 (𝑘) . 𝑘
This metric naturally captures the cost of replication: increasing the replication level for a flow increases {𝐿 𝑖(𝑘) 𝑗 } and thus consumes more network resources.
IV. R EDUNDANCY-C ONTROLLED S TOCHASTIC ROUTING (RATIO) S CHEME In this section, the proposed Redundancy-Controlled Stochastic Routing (RATIO) scheme is described, followed by an idealized formulation that clarifies the underlying design trade-offs.
Fig. 2: Illustration of the modulo-based packet forwarding rule in RATIO using a single random draw 𝑈 ∈ [0, 1). (a) No replication: each 𝑈 selects exactly one outgoing link. (b) Replication enabled: a single 𝑈 may activate two outgoing links. Specifically, 𝑈 ∈ [0, 0.2) activates ( 𝑗1 , 𝑗2 ), 𝑈 ∈ [0.2, 0.6) activates ( 𝑗1 , 𝑗3 ), and 𝑈 ∈ [0.6, 1) activates 𝑗2 only. A. RATIO Overview An illustration of RATIO is provided in Fig. 1. The main idea of RATIO is to control redundancy in a gradual manner rather than making a fixed single-path or multi-path replication decision. For each flow, RATIO first restricts the routing space to a compact reduced DAG, which contains several promising forwarding opportunities from the source to the destination. Then, instead of selecting only one path or replicating every packet over all available paths, RATIO assigns forwarding probabilities to the outgoing links in the reduced DAG. These probabilities determine how often each link is used and how much redundancy is introduced on average. At a non-fork node with only one outgoing link, packets are forwarded deterministically along that link. At a fork node with multiple outgoing links, an incoming packet can be forwarded to one or more next-hop nodes according to the assigned forwarding probabilities. If the aggregate forwarding probability at a fork node is close to one, the node behaves similarly to probabilistic path splitting and usually generates one outgoing copy per packet. If the aggregate forwarding probability is larger than one, additional packet copies can be generated with controlled frequency. In this way, RATIO can increase redundancy when link uncertainty is high and reduce redundancy when the network is congested. A key point is that RATIO controls redundancy in expectation. Although each individual packet transmission is still discrete, the expected number of outgoing copies can be continuously tuned by adjusting the forwarding probabilities. For example, a fork node may generate on average 1.5 outgoing copies per incoming packet: some packets are forwarded on one outgoing link, while others are replicated over two links. This provides finer-grained control than conventional deterministic multi-path replication, where the number of packet copies is usually an integer. The packet-level forwarding decision is implemented by a modulo-based stochastic forwarding rule as illustrated in Fig. 2. This rule maps the continuous-valued forwarding
6
Algorithm 1 RATIO forwarding at node 𝑖 for flow 𝑓 in period 𝑘 (𝑘) Require: Reduced DAG D (𝑘) ; outgoing set N +, ; forward𝑓 𝑓 ,𝑖 𝑓 , (𝑘)
ing probs {𝜋 𝑖 𝑗 } Ensure: A set of outgoing transmissions (possibly multiple) 1: if 𝑖 = 𝑑 𝑓 then 2: Deliver to upper layer. +, (𝑘) 3: else if N 𝑓 ,𝑖 = ∅ then 4: Drop packet. +, (𝑘) 5: else if |N 𝑓 ,𝑖 | = 1 then 6: Transmit on (𝑖, 𝑗). 7: else (𝑘) 8: (Randomly) order N +, = { 𝑗1 , . . . , 𝑗 𝑚 }. Íℓ 𝑓 ,𝑖𝑓 , (𝑘) 9: 𝑠0 ← 0, 𝑠ℓ ← 𝑢=1 𝜋 𝑖 𝑗𝑢 for ℓ = 1, . . . , 𝑚. 10: Draw 𝑈 ∼ Unif(0, 1). 11: for ℓ = 1 to 𝑚 do 12: 𝑎 ← 𝑠ℓ−1 , 𝑏 ← 𝑠ℓ . 13: 𝑎 0 ← 𝑎 − ⌊𝑎⌋, 𝑏 0 ← 𝑏 − ⌊𝑏⌋. 14: if ⌊𝑎⌋ = ⌊𝑏⌋ then 15: if 𝑈 ∈ [𝑎 0 , 𝑏 0 ) then 16: Transmit a copy on (𝑖, 𝑗ℓ ). 17: end if 18: else 19: if 𝑈 ∈ [𝑎 0 , 1) or 𝑈 ∈ [0, 𝑏 0 ) then 20: Transmit a copy on (𝑖, 𝑗ℓ ). 21: end if 22: end if 23: end for 24: end if
The reduced DAG is constructed to keep the routing search space compact while preserving a limited amount of path diversity. For each node 𝑖 ∈ V𝑓(𝑘) , the outgoing and incoming (𝑘) neighbor sets in D (𝑘) , denoted by N +, and N 𝑓−,,𝑖(𝑘) , are 𝑓 𝑓 ,𝑖 defined as (𝑘) N +, = { 𝑗 ∈ V𝑓(𝑘) : (𝑖, 𝑗) ∈ E (𝑘) 𝑓 }, 𝑓 ,𝑖
N 𝑓−,,𝑖(𝑘) = { 𝑗 ∈ V𝑓(𝑘) : ( 𝑗, 𝑖) ∈ E (𝑘) 𝑓 }, (𝑘) respectively. A node with |N +, | ≥ 2 is referred to as a fork 𝑓 ,𝑖 node. 2) Forwarding Probabilities and Replication Factor: Each directed edge (𝑖, 𝑗) ∈ E (𝑘) is associated with a forwarding 𝑓 probability 𝑓 , (𝑘) 𝜋𝑖 𝑗 ∈ [0, 1],
which is interpreted as the marginal probability that an arriving packet of flow 𝑓 at node 𝑖 is forwarded on link (𝑖, 𝑗) during 𝑓 , (𝑘) period 𝑘. Intuitively, 𝜋 𝑖 𝑗 controls how frequently link (𝑖, 𝑗) 𝑓 , (𝑘)
is used by flow 𝑓 at node 𝑖. A larger 𝜋 𝑖 𝑗 means that packets are more likely to be forwarded through link (𝑖, 𝑗), 𝑓 , (𝑘) while 𝜋 𝑖 𝑗 = 0 means that this link is not used by the flow. Therefore, forwarding probabilities jointly determine both the preferred forwarding direction and the amount of traffic injected onto each outgoing link. The aggregate replication factor at node 𝑖, denoted by 𝑓 , (𝑘) Π𝑖 , is then given by Õ 𝑓 , (𝑘) 𝑓 , (𝑘) Π𝑖 = 𝜋𝑖 𝑗 , (𝑘) 𝑗 ∈ N +, 𝑓 ,𝑖
probabilities to actual discrete packet transmissions, while ensuring that at least one outgoing link is selected whenever forwarding is feasible. The detailed components of RATIO are presented below. B. Components of RATIO The key components of RATIO is reduced DAG as routing structure and forwarding probabilities that guide packet transmission and duplication. The overall node operations of RATIO at each routing period are summarized in Algorithm 1. 1) Reduced DAG: The reduced DAG can be interpreted as the candidate forwarding region of a flow. It is not intended to include all possible links in the network. Instead, it keeps only a limited set of useful forwarding links so that the routing decision remains tractable while still preserving path diversity. Compared with a single path, the reduced DAG provides alternative forwarding opportunities under mobility. Compared with using the full network graph, it avoids excessive search complexity and unnecessary redundancy. In routing period 𝑘, network connectivity is represented by a directed graph 𝐺 (𝑘) = (V, E (𝑘) ). For each active flow 𝑓 in (𝑘) period 𝑘, a flow-specific reduced DAG D 𝑓 that connects 𝑠 𝑓 to 𝑑 𝑓 is utilized as the route space: (𝑘) (𝑘) (𝑘) (𝑘) (𝑘) V𝑓 ⊆ V, E 𝑓 ⊆ E (𝑘) . D 𝑓 = V𝑓 , E 𝑓 ,
which represents the expected number of outgoing copies generated per incoming packet at node 𝑖. Unlike conventional 𝑓 , (𝑘) probabilistic splitting (which typically enforces Π𝑖 = 1), 𝑓 , (𝑘) values Π𝑖 > 1 are permitted at fork nodes so that replication can be introduced in a continuous and tunable 𝑓 , (𝑘) manner. The aggregate replication factor Π𝑖 represents the expected number of outgoing packet copies generated by node 𝑓 , (𝑘) 𝑖 for each incoming packet of flow 𝑓 . When Π𝑖 = 1, the node forwards each packet along one outgoing direction on average, which corresponds to no additional replication. 𝑓 , (𝑘) When Π𝑖 > 1, the node creates additional copies with a 𝑓 , (𝑘) controlled frequency. For example, Π𝑖 = 1.5 means that, over many packets, the node generates 1.5 outgoing copies per incoming packet on average. This does not mean that each individual packet is transmitted 1.5 times; rather, some packets may be forwarded once, while others may be replicated over multiple outgoing links. Thus, RATIO provides continuousvalued redundancy control in expectation, while packet-level transmissions remain discrete. To avoid intentional packet dropping at relay nodes, the following consistency condition is imposed: Õ 𝑓 , (𝑘) ≥ 1, 𝜋𝑖 𝑗 +, (𝑘)
𝑗 ∈ N 𝑓 ,𝑖
(1) ∀ 𝑓 , ∀𝑘,
(𝑘) ∀𝑖 ∈ V𝑓 ,
+, (𝑘) N 𝑓 ,𝑖 ≠ ∅.
7
𝑓 , (𝑘)
(𝑘) = 1, i.e., In particular, when |N +, 𝑓 ,𝑖 | = 1, (1) implies 𝜋 𝑖 𝑗 non-fork nodes deterministically forward along their unique outgoing edge. It should be noted that this continuity is defined at the level of expected redundancy rather than the level of physical 𝑓 , (𝑘) packet transmissions. The forwarding probabilities {𝜋 𝑖 𝑗 } 𝑓 , (𝑘)
are continuous-valued variables, and their sum Π𝑖 represents the expected number of outgoing copies generated per 𝑓 , (𝑘) incoming packet. For instance, Π𝑖 = 1.5 does not imply that every packet is literally transmitted 1.5 times. Instead, each packet-level forwarding decision remains discrete: a packet copy is either transmitted or not transmitted on each outgoing link. The modulo-based stochastic forwarding rule maps the continuous-valued probabilities to discrete packet transmissions, so some packets may generate one outgoing copy while others may generate two or more copies. Over a sequence of packets, the average number of outgoing copies 𝑓 , (𝑘) approaches the prescribed value Π𝑖 . Therefore, RATIO provides continuous-valued redundancy control in expectation, while the realized redundancy is stochastic across packets. 3) Packet-Level Forwarding Rule at Nodes: The marginal forwarding probabilities are realized using a single random draw per packet (or packet copy) at each fork node, while ensuring that at least one outgoing link is selected via a modulo-based mapping. An illustration of the forwarding rule is shown in Fig. 2. To be specific, consider a fork node 𝑖 with ordered outgoing +, (𝑘) = { 𝑗1 , . . . , 𝑗 𝑚 }, where 𝑚 ≥ 2. Define neighbors N 𝑓 ,𝑖 cumulative sums 𝑠0 = 0,
𝑠ℓ =
ℓ Õ
𝑓 , (𝑘)
𝜋 𝑖 𝑗𝑢 , ℓ = 1, . . . , 𝑚.
𝑢=1
Each edge (𝑖, 𝑗ℓ ) is assigned an interval 𝑓 , (𝑘)
𝐼𝑖 𝑗ℓ
𝑓 , (𝑘)
= [𝑠ℓ−1 , 𝑠ℓ ) ⊆ [0, Π𝑖
).
Let 𝜑(𝑥) = 𝑥 mod 1 ∈ [0, 1) denote the modulo map. For each arriving packet, a single random variable 𝑈 ∼ Unif(0, 1) is drawn, and a copy is forwarded on every edge (𝑖, 𝑗ℓ ) such that 𝑓 , (𝑘) . 𝑈 ∈ 𝜑 𝐼𝑖 𝑗ℓ This modulo-based rule converts continuous forwarding probabilities into actual packet-level decisions. The same random number 𝑈 is used to test all outgoing intervals. If 𝑈 falls into the mapped interval of one outgoing link, a copy is transmitted on that link. If 𝑈 falls into the mapped intervals of multiple outgoing links, multiple copies are transmitted. Therefore, a packet may be sent through one link or replicated across several links, depending on the random draw and the forwarding probabilities. 𝑓 , (𝑘) 𝑓 , (𝑘) 𝑚 When Π𝑖 ≥ 1, the mapped intervals {𝜑(𝐼𝑖 𝑗ℓ )}ℓ=1 jointly cover [0, 1), ensuring that at least one outgoing transmission is triggered whenever forwarding is feasible. More specifically, with ordinary independent probabilistic forwarding, it is possible that all outgoing links reject the packet, which would create unintended packet loss. In contrast, when 𝑓 , (𝑘) Π𝑖 ≥ 1, the modulo-mapped intervals cover the whole
interval [0, 1), so at least one outgoing link is activated. At the same time, overlapping mapped intervals naturally realize controlled replication. C. Problem Formulation In each routing period 𝑘, the RATIO design is composed of (𝑘) two coupled components: (i) a reduced DAG D 𝑓 is selected for each active flow 𝑓 , and (ii) forwarding probabilities 𝑓 , (𝑘) {𝜋 𝑖 𝑗 } are assigned on the selected DAG edges. An idealized joint formulation is provided below. 1) Decision Variables: For each flow 𝑓 and period 𝑘, a binary edge-selection variable is introduced to represent the reduced DAG: 𝑓 , (𝑘)
𝑧𝑖 𝑗 𝑓 , (𝑘)
where 𝑧𝑖 𝑗
∀(𝑖, 𝑗) ∈ E (𝑘) ,
∈ {0, 1},
= 1 indicates that link (𝑖, 𝑗) is included in the (𝑘)
reduced DAG D 𝑓 for flow 𝑓 . Forwarding probabilities are defined on physical edges, but become effective only when the edge is selected: 𝑓 , (𝑘)
𝜋𝑖 𝑗
∀(𝑖, 𝑗) ∈ E (𝑘) ,
∈ [0, 1],
together with the coupling constraint 𝑓 , (𝑘)
0 ≤ 𝜋𝑖 𝑗
𝑓 , (𝑘)
≤ 𝑧𝑖 𝑗
,
∀(𝑖, 𝑗) ∈ E (𝑘) .
(2)
𝑓 , (𝑘)
𝑓 , (𝑘)
= 0 is = 0), then 𝜋 𝑖 𝑗 Besides, if (𝑖, 𝑗) ∉ E (𝑘) (i.e., 𝑧𝑖 𝑗 𝑓 enforced automatically. The two types of variables have different roles. The binary 𝑓 , (𝑘) decides whether link (𝑖, 𝑗) is included in the variable 𝑧𝑖 𝑗 𝑓 , (𝑘)
reduced DAG of flow 𝑓 . The continuous variable 𝜋 𝑖 𝑗 further decides how frequently this selected link is used for packet 𝑓 , (𝑘) determines the available forwarding forwarding. Thus, 𝑧𝑖 𝑗 𝑓 , (𝑘)
determines the redundancy level and structure, while 𝜋 𝑖 𝑗 traffic distribution on that structure. 2) Reduced DAG Feasibility Constraints: To ensure that the selected subgraph is a DAG, integer topological-order 𝑓 , (𝑘) variables 𝑢 𝑖 ∈ {0, 1, . . . , |V | − 1} are introduced, and the following constraint is imposed: 𝑓 , (𝑘) 𝑓 , (𝑘) 𝑓 , (𝑘) 𝑢𝑖 +1 ≤ 𝑢 𝑗 + 𝑀 1 − 𝑧𝑖 𝑗 , ∀(𝑖, 𝑗) ∈ E (𝑘) , 𝑓 , 𝑘, (3) 𝑓 , (𝑘)
where 𝑀 ≥ |V | is a sufficiently large constant. When 𝑧𝑖 𝑗 𝑓 , (𝑘) 1, equation (3) enforces 𝑢 𝑖
=
𝑓 , (𝑘) < 𝑢𝑗 , thereby precluding
directed cycles. Connectivity of the reduced DAG is enforced by routing 𝑓 , (𝑘) one unit of auxiliary flow. Auxiliary variables 𝜙𝑖 𝑗 ∈ [0, 1] are introduced and constrained as Õ Õ 𝑓 , (𝑘) 𝑓 , (𝑘) 𝜙 ℎ𝑖 𝜙𝑖 𝑗 − ℎ:(ℎ,𝑖) ∈ E (𝑘)
𝑗:(𝑖, 𝑗 ) ∈ E (𝑘)
1, 𝑖 = 𝑠𝑓, = −1, 𝑖 = 𝑑 𝑓 , otherwise, 0, 𝑓 , (𝑘)
0 ≤ 𝜙𝑖 𝑗
𝑓 , (𝑘)
≤ 𝑧𝑖 𝑗
,
(4) ∀𝑖 ∈ V, ∀ 𝑓 , 𝑘.
∀(𝑖, 𝑗) ∈ E (𝑘) , ∀ 𝑓 , 𝑘.
(5)
8
Constraints (4)–(5) guarantee the existence of at least one directed 𝑠 𝑓 –𝑑 𝑓 path in the selected edges. Besides, they ensure that packets always make progress along the reduced DAG and cannot circulate in routing loops. 3) Forwarding-Consistency Constraints: To avoid explic(𝑘) itly invoking the outgoing neighbor set N +, in the opti𝑓 ,𝑖 mization (which would otherwise require the reduced DAG structure to be referenced inside the constraints), a binary flag 𝑓 , (𝑘) 𝑜𝑖 ∈ {0, 1} is introduced to indicate whether node 𝑖 has any selected outgoing edge: Õ
𝑓 , (𝑘)
≤ 𝑜𝑖
𝑓 , (𝑘)
≥ 𝑜𝑖
𝑧𝑖 𝑗
𝜋𝑖 𝑗
𝑓 , (𝑘)
,
∀(𝑖, 𝑗) ∈ E (𝑘) , ∀ 𝑓 , 𝑘,
(6)
𝑓 , (𝑘)
,
∀𝑖 ∈ V, ∀ 𝑓 , 𝑘.
(7)
𝑗:(𝑖, 𝑗 ) ∈ E (𝑘)
Í 𝑓 , (𝑘) 𝑓 , (𝑘) When 𝑜𝑖 = 1, constraint (7) enforces 𝑗 𝜋 𝑖 𝑗 ≥ 1, ensuring that at least one outgoing transmission is scheduled 𝑓 , (𝑘) whenever node 𝑖 has selected outgoing edges. When 𝑜𝑖 = 0, no outgoing edge is selected and this constraint becomes vacuous. 4) Performance Functions: Under wireless channel dynamics, medium-access contention, and queueing interactions, endto-end performance is generally difficult to characterize in closed form. Accordingly, the timely PDR of flow 𝑓 , denoted by PDR 𝑓 , and the total transmission load, denoted by 𝐿 tot , are treated as (possibly non-convex) functions of the design variables {𝑧} and {𝜋}: PDR 𝑓 = PDR 𝑓 {𝑧}, {𝜋} , 𝐿 tot = 𝐿 tot {𝑧}, {𝜋} . Here, when computing PDR 𝑓 , a packet is counted as successfully delivered if at least one of its copies reaches 𝑑 𝑓 within the deadline (duplicate receptions are ignored). But any additional copies beyond the first delivery are still counted in 𝐿 tot . 5) Idealized Formulation: An idealized RATIO design is formulated by minimizing the total transmission load while satisfying per-flow timely-reliability constraints and per-link capacity constraints: min 𝐿 tot {𝑧}, {𝜋} (8a) { 𝑧, 𝜋,𝑢, 𝜙,𝑜} s.t. PDR 𝑓 {𝑧}, {𝜋}; 𝐷 max ≥ 𝜂 𝑓 , ∀ 𝑓 ∈ F , (8b) Õ 𝑓 , (𝑘) (𝑘) (𝑘) 𝜋 𝑖 𝑗 𝑟 𝑓 ≤ 𝐶𝑖 𝑗 , ∀𝑘 ∈ K, (𝑖, 𝑗) ∈ E , (8c) 𝑓 ∈ F (𝑘)
(2), (3), (4) − (5), (6) − (7), 𝑓 , (𝑘)
𝑧𝑖 𝑗
𝑓 , (𝑘)
∈ {0, 1}, 0 ≤ 𝜋 𝑖 𝑗
≤ 1,
𝑓 , (𝑘) 𝑢𝑖 ∈ {0, . . . , |V | − 1}, 𝑓 , (𝑘) 𝑓 , (𝑘) 0 ≤ 𝜙𝑖 𝑗 ≤ 1, 𝑜𝑖 ∈ {0, 1}.
Here 𝑟 𝑓 denotes injection rate of flow 𝑓 , and 𝐶𝑖(𝑘) 𝑗 denotes the service capability of link (𝑖, 𝑗) in period 𝑘. Problem (8) characterizes an idealized RATIO design but is difficult to solve exactly. The difficulty comes from two main aspects. First, the timely PDR and end-to-end delay under stochastic forwarding, wireless contention, and queueing interactions are not analytically tractable in closed form. As a result, the functions PDR 𝑓 (𝑧, 𝜋) and 𝐿tot(𝑧, 𝜋) cannot be
easily optimized by standard convex optimization methods. Second, the reduced-DAG construction is combinatorial because the controller needs to select a suitable subset of links and paths from the time-varying connectivity graph. Different DAG choices may lead to different reliability, delay, and load trade-offs. Therefore, the joint optimization of DAG construction and forwarding probabilities is mixed-integer, generally non-convex, and NP-hard. In addition, only instantaneous connectivity and short-term MAC/traffic statistics are available in each routing period, which further makes exact horizon-wide optimization impractical for large-scale vehicular networks. V. H EURISTIC R EDUNDANCY-C ONTROLLED S TOCHASTIC ROUTING (H-RATIO) To enable tractable and scalable RATIO routing, a perperiod heuristic, namely H-RATIO, is developed in this section. Instead of directly solving the idealized RATIO problem, H-RATIO separates the design into two simpler steps: (i) constructing a compact reduced DAG for each flow, and (ii) assigning and refining forwarding probabilities on the constructed DAG. Surrogate models are introduced to estimate timely PDR and transmission load, so that H-RATIO can adjust redundancy using only short-term measurements and lightweight computations. A. H-RATIO Overview H-RATIO is a practical realization of the RATIO idea. Its goal is not to find the globally optimal reduced DAG and forwarding probabilities, which would be computationally expensive. Instead, H-RATIO follows a simple and scalable procedure. First, H-RATIO constructs a reduced DAG for each flow from the current network snapshot. Links with poor quality or short expected lifetime are removed, and a small number of candidate paths are extracted. The union of these paths forms a compact forwarding structure that preserves useful path diversity without using the entire network graph. Second, H-RATIO assigns initial forwarding probabilities on the reduced DAG. Links with better quality, longer expected lifetime, or shorter remaining distance to the destination are given larger splitting weights. These weights decide the preferred forwarding directions at each fork node. Third, H-RATIO adjusts the replication level according to surrogate estimates of timely PDR and link load. If the estimated timely PDR of a flow is below its target, H-RATIO increases redundancy at selected fork nodes to activate more forwarding opportunities. If some links become overloaded, HRATIO decreases redundancy for the flows contributing most to the overload. Through this iterative adjustment, H-RATIO balances two competing effects: more redundancy can improve reliability, but excessive redundancy may increase congestion and delay. The overall workflow of H-RATIO is summarized in Algorithm 2. The surrogate models used for reliability and load estimation are introduced first, followed by the detailed operations of reduced-DAG construction and forwarding-probability refinement.
9
Algorithm 2 Heuristic RATIO (H-RATIO) in routing period 𝑘 Require: Connectivity graph 𝐺 (𝑘) = (V, E (𝑘) ); effective (𝑘) (𝑘) rates {𝐶¯𝑖(𝑘) 𝑗 }; link indicators {𝛾𝑖 𝑗 , LET𝑖 𝑗 }; active flows 𝑓 F (𝑘) with (𝑠 𝑓 , 𝑑 𝑓 , 𝑟 𝑓 , 𝐷 max , 𝜂 𝑓 ); packet size 𝐿 pkt ; thresholds (𝛾min , LETmin ); parameters (𝑃max , 𝐼max , Δ, 𝜌max ). 𝑓 , (𝑘) Ensure: Forwarding probabilities {𝜋 𝑖 𝑗 } on reduced DAGs {D (𝑘) 𝑓 }.
(𝑘)
< 𝛾min or LET𝑖(𝑘) 𝑗 < LETmin . (𝑘) 2: for each flow 𝑓 ∈ F do 3: Construct reduced DAG D (𝑘) from up to 𝑃max candi𝑓 date paths (Section V-C1). 𝑓 , (𝑘) 4: Compute local edge scores {𝜓𝑖 𝑗 } and splitting
1: Prune links with 𝛾𝑖 𝑗
𝑓 , (𝑘)
weights {𝜔𝑖 𝑗
}. 𝑓 , (𝑘)
Initialize replication factors 𝜅𝑖 ← 1 and set 𝑓 , (𝑘) 𝑓 , (𝑘) 𝑓 , (𝑘) (𝑘) 𝜋𝑖 𝑗 ← min{1, 𝜅𝑖 𝜔𝑖 𝑗 } on D 𝑓 . 6: end for 7: for iter = 1 to 𝐼max do 𝑓 , (𝑘) 8: Compute expected node arrival rates {𝑥𝑖 } on each (𝑘) D 𝑓 via (19).
5:
9:
10: 11: 12: 13: 14: 15: 16:
(𝑘)
Compute link loads {𝜆𝑖 𝑗 } by (9)–(10) and utilizations {𝜌𝑖(𝑘) 𝑗 } by (12). for each flow 𝑓 ∈ F (𝑘) do 𝑓 (𝑘) Evaluate PDR 𝑓 (𝐷 max ) via (14)–(18). 𝑓 (𝑘) if PDR 𝑓 (𝐷 max ) < 𝜂 𝑓 then 𝑓 , (𝑘)
Increase 𝜅𝑖 by Δ on selected fork nodes. end if end for (𝑘) if ∃(𝑖, 𝑗) with 𝜌𝑖 𝑗 > 𝜌max then 𝑓 , (𝑘)
on nodes contributing most to overDecrease 𝜅𝑖 loaded links. 18: end if 𝑓 , (𝑘) 𝑓 , (𝑘) 19: Update 𝜋 𝑖 𝑗 and {𝑥𝑖 } and on each reduced DAG via (20) and (19), respectively. 𝑓 , (𝑘) 20: if no 𝜅𝑖 changes then 21: break 22: end if 23: end for
17:
B. Surrogate Models for Timely PDR and Transmission Load To enable period-by-period routing decisions with limited information, surrogate models are adopted for both timely PDR and transmission load. In routing period 𝑘, an effective service rate 𝐶¯𝑖(𝑘) (bit/s) is assumed to be estimated by the 𝑗 controller for each directed link (𝑖, 𝑗) ∈ E (𝑘) , based on shortterm measurements and/or historical statistics. 𝑓 , (𝑘) 1) Surrogate Transmission Load: Let 𝑥𝑖 denote the expected arrival rate of flow 𝑓 at node 𝑖 in period 𝑘, measured 𝑓 , (𝑘) in bit/s. Given forwarding probabilities {𝜋 𝑖 𝑗 }, the expected traffic rate of flow 𝑓 forwarded on link (𝑖, 𝑗) is approximated as 𝑓 , (𝑘)
𝜆𝑖 𝑗
𝑓 , (𝑘)
¬ 𝑥𝑖
𝑓 , (𝑘)
𝜋𝑖 𝑗
,
(𝑘)
(𝑖, 𝑗) ∈ E 𝑓 .
(9)
That is, the traffic placed on link (𝑖, 𝑗) is proportional to the 𝑓 , (𝑘) forwarding probability on that link. If 𝜋 𝑖 𝑗 is increased, a larger fraction of the traffic arriving at node 𝑖 will be forwarded through link (𝑖, 𝑗). Therefore, forwarding probabilities directly determine both the traffic distribution and the redundancyinduced load. The aggregate offered load on a physical link (𝑖, 𝑗) can then be derived by aggregating the traffic contributions of all flows using the same physical link, i.e., Õ 𝑓 , (𝑘) 𝜆𝑖(𝑘) (10) 𝜆𝑖 𝑗 , 𝑗 ¬ 𝑓 ∈ F𝑖(𝑘) 𝑗
where F𝑖 (𝑘) denotes the set of flows that may use link (𝑖, 𝑗) 𝑗 in period 𝑘. As a surrogate for transmission cost, the per-period total load is defined as the sum of aggregate link loads: Õ (𝑘) 𝜆𝑖(𝑘) (11) 𝐿 ¬ 𝑗 . (𝑖, 𝑗 ) ∈ E (𝑘)
(𝑘)
The surrogate load 𝐿 therefore measures the overall channel occupation caused by forwarding and replication in routing pe(𝑘) riod 𝑘. A smaller 𝐿 indicates lower transmission overhead, while a larger value suggests that more wireless resources are consumed. Moreover, this surrogate captures the replication effect directly: increasing forwarding probabilities (and hence aggregate replication factors) increases {𝜆𝑖(𝑘) 𝑗 } and therefore (𝑘)
increases 𝐿 . 2) Surrogate Timely PDR: To capture contention-induced delay inflation, processing and propagation delays are neglected, while the waiting time plus service time is modeled. Given the fixed packet size 𝐿 pkt , the corresponding packet(𝑘) (𝑘) level arrival and service rates, denoted by 𝜆ˆ 𝑖 𝑗 and 𝜇ˆ 𝑖 𝑗 , respectively, are given by 𝜆ˆ 𝑖(𝑘) 𝑗 =
𝜆𝑖(𝑘) 𝑗 𝐿 pkt
(pkt/s),
𝜇ˆ 𝑖(𝑘) 𝑗 =
𝐶¯𝑖(𝑘) 𝑗 𝐿 pkt
(pkt/s).
The utilization of link (𝑖, 𝑗), denoted by 𝜌𝑖(𝑘) 𝑗 , is then given by (𝑘) (𝑘) 𝜆𝑖 𝑗 𝜆ˆ 𝑖 𝑗 (𝑘) (12) 𝜌𝑖 𝑗 ¬ (𝑘) = (𝑘) ∈ [0, 1), 𝜇ˆ 𝐶¯ 𝑖𝑗
𝑖𝑗
(𝑘) and stability is ensured when 𝜌𝑖(𝑘) 𝑗 < 1. The utilization 𝜌 𝑖 𝑗
indicates how heavily link (𝑖, 𝑗) is loaded. When 𝜌𝑖(𝑘) 𝑗 is close to zero, the link has sufficient residual service capability. When 𝜌𝑖(𝑘) 𝑗 approaches one, the link becomes heavily loaded, and
queueing delay may increase rapidly. Thus, 𝜌𝑖(𝑘) 𝑗 is used by H-RATIO to detect potential congestion caused by excessive redundancy. Each link is then approximated by an M/M/1 queue with (𝑘) arrival rate 𝜆ˆ 𝑖(𝑘) 𝑗 and service rate 𝜇ˆ 𝑖 𝑗 . Define the (packet-level) service slack as (𝑘) 𝐶¯𝑖(𝑘) 𝑗 − 𝜆𝑖 𝑗 (𝑘) (𝑘) (𝑘) ˆ > 0. (13) 𝛽𝑖 𝑗 ¬ 𝜇ˆ 𝑖 𝑗 − 𝜆𝑖 𝑗 = 𝐿 pkt
10
The service slack 𝛽𝑖(𝑘) 𝑗 measures the remaining service capability after accounting for the offered load. A larger 𝛽𝑖(𝑘) 𝑗 implies that packets can be served more quickly on link (𝑖, 𝑗). A smaller 𝛽𝑖(𝑘) 𝑗 means that the link is closer to congestion, which leads to larger waiting time and a lower probability of meeting the deadline. Under this model, the sojourn time (i.e., waiting time plus service time) on link (𝑖, 𝑗), denoted by 𝑇𝑖(𝑘) 𝑗 , is exponentially distributed, i.e., (𝑘) 𝑇𝑖(𝑘) 𝑗 ∼ Exp 𝛽𝑖 𝑗 . Its mean and variance are i h 𝐿 pkt 1 = (𝑘) = (𝑘) E 𝑇𝑖(𝑘) , 𝑗 𝛽𝑖 𝑗 𝐶¯𝑖 𝑗 − 𝜆𝑖(𝑘) 𝑗 = Var 𝑇𝑖(𝑘) 𝑗
and
1
2 𝛽𝑖(𝑘) 𝑗
=
(𝑖, 𝑗 ) ∈ 𝑝
𝐿 2pkt
, (𝑘) 2 𝐶¯𝑖(𝑘) 𝑗 − 𝜆𝑖 𝑗
(𝑘) 2 sumrespectively. The path mean 𝜇 (𝑘) 𝑓 , 𝑝 and variance 𝜎 𝑓 , 𝑝 marize the delay behavior of path 𝑝. If a path contains heavily ¯ 𝑗 (𝑘) − 𝜆𝑖 𝑗 (𝑘) becomes small, and both loaded links, then 𝐶𝑖 the mean and variance of the path delay increase. Therefore, a path with many congested links is less likely to deliver packets before the deadline. For each flow 𝑓 , the reduced DAG D (𝑘) induces a set of 𝑓
candidate 𝑠 𝑓 –𝑑 𝑓 paths, denoted by P 𝑓(𝑘) . Consider any path
𝑝 ∈ P 𝑓(𝑘) , consisting of directed edges 𝑒 ∈ 𝑝. Assuming hop delays are independent across edges, the end-to-end delay along path 𝑝 is modeled as Õ 𝑆 (𝑘) 𝑇𝑒(𝑘) . 𝑓 ,𝑝 ¬ 𝑒∈ 𝑝
(𝑘) 2 Its mean and variance, denoted by 𝜇 (𝑘) 𝑓 , 𝑝 and 𝜎 𝑓 , 𝑝 , respectively, are approximated by h i Õ 𝐿 pkt (𝑘) 𝜇 (𝑘) ¬ E 𝑆 , (14) = 𝑓 ,𝑝 𝑓 ,𝑝 (𝑘) (𝑘) ¯ (𝑖, 𝑗 ) ∈ 𝑝 𝐶𝑖 𝑗 − 𝜆 𝑖 𝑗
and (𝑘) 2
𝜎𝑓 ,𝑝
¬ Var 𝑆 (𝑘) = 𝑓 ,𝑝
Õ
𝐿 2pkt
(𝑘) 2 ¯ (𝑘) (𝑖, 𝑗 ) ∈ 𝑝 𝐶𝑖 𝑗 − 𝜆 𝑖 𝑗
The activation probability 𝐴 (𝑘) 𝑓 , 𝑝 reflects whether a packet copy is likely to be forwarded along the entire path 𝑝. If the forwarding probabilities on the edges of path 𝑝 are large, then the path is more likely to be activated. If any edge on the path has a small forwarding probability, then the probability that the whole path is activated becomes smaller. Combining activation and deadline feasibility, we define a single-path surrogate timely delivery probability: 𝑓 𝑓 (𝑘) (𝑘) (𝑘) PDR 𝑓 , 𝑝 (𝐷 max ) ¬ 𝐴 𝑓 , 𝑝 · 𝐹 𝑓 , 𝑝 (𝐷 max ).
.
exponentials (hypo-exponential), but a moment-based bound is adopted for simplicity and robustness. Using Cantelli’s 𝑓 inequality [41], for any deadline 𝐷 max > 𝜇 (𝑘) , 𝑓 ,𝑝 2 𝜎 𝑓(𝑘) ,𝑝 𝑓 ≥ 1 − P 𝑆 (𝑘) ≤ 𝐷 . max 2 𝑓 ,𝑝 𝑓 (𝑘) 2 + 𝐷 − 𝜇 𝜎 𝑓(𝑘) max 𝑓 ,𝑝 ,𝑝 When 𝐷 max ≤ 𝜇 (𝑘) 𝑓 , 𝑝 , the bound becomes non-informative and is clipped to 0. Define the resulting conservative deadlinefeasibility term as 2 𝜎 𝑓(𝑘) , 𝑝 𝑓 (𝑘) , 𝐹 𝑓 , 𝑝 (𝐷 max ) ¬ 1 − (15) 2 𝑓 (𝑘) 2 + 𝐷 − 𝜇 𝜎 𝑓(𝑘) max 𝑓 ,𝑝 + ,𝑝
(17)
The single-path surrogate timely PDR combines two factors. The first factor, 𝐴 (𝑘) 𝑓 , 𝑝 , describes whether the path is activated by stochastic forwarding. The second factor, 𝐹 𝑓 , 𝑝 (𝑘) (𝐷max 𝑓 ), describes whether the activated path can deliver the packet within the deadline. Thus, a path contributes to timely delivery only when it is both activated and sufficiently fast. Finally, the flow-level timely PDR in period 𝑘 is approx𝑓 (𝑘) imated by aggregating candidate paths. Let PDR 𝑓 (𝐷 max ) denote the flow-level timely delivery probability. Under an independence approximation across candidate paths, a unionof-events surrogate is used: Ö (𝑘) 𝑓 𝑓 (𝑘) 1 − PDR (𝐷 ) PDR (𝐷 ) ≈ 1 − max max 𝑓 ,𝑝 𝑓 𝑝 ∈ P 𝑓(𝑘)
A closed-form CDF of 𝑆 (𝑘) 𝑓 , 𝑝 can be obtained for sums of
𝑓
where [𝑥] + ¬ max{𝑥, 0}. The term 𝐹 𝑓 , 𝑝 (𝑘) (𝐷max 𝑓 ) represents a conservative estimate of the probability that path 𝑝 can satisfy the deadline. It becomes larger when the path delay mean is well below the deadline and the delay variance is small. It becomes smaller when the path is congested or when the deadline is too tight. Replication introduces path activation. Let 𝐴 (𝑘) 𝑓 , 𝑝 denote the probability that path 𝑝 is activated by the stochastic forwarding rule, i.e., that a copy is forwarded along every edge of 𝑝. For tractability, 𝐴 (𝑘) is approximated by the product of edge-level 𝑓 ,𝑝 forwarding probabilities along the path: Ö 𝑓 , (𝑘) 𝐴 (𝑘) ≈ 𝜋𝑖 𝑗 . (16) 𝑓 ,𝑝
=1−
Ö
(18) 𝑓 (𝐷 max ) . 1 − 𝐴 (𝑘) · 𝐹 (𝑘) 𝑓 ,𝑝 𝑓 ,𝑝
𝑝 ∈ P 𝑓(𝑘)
Equation (18) aggregates the timely delivery opportunities over all candidate paths. It approximates the probability that at least one activated path successfully delivers a packet before the deadline. This expression also shows the key trade-off in redundancy control. Increasing forwarding probabilities activates more paths and may improve timely PDR. However, it also increases link load, which may reduce the deadline-feasibility term by increasing queueing delay. Therefore, redundancy is beneficial only when the reliability gain is larger than the congestion-induced delay cost. 3) Rationale for Surrogate Models: The surrogate models provide tractable approximations of the two key quantities in the ideal RATIO design: timely reliability and transmission cost. The transmission-load surrogate measures the expected
11
forwarding cost induced by stochastic routing. For a fixed 𝑓 , (𝑘) routing period 𝑘 and locally fixed node arrival rate 𝑥𝑖 , 𝑓 , (𝑘)
𝑓 , (𝑘)
𝜆𝑖 𝑗
𝑓 , (𝑘)
= 𝑥𝑖
𝑓 , (𝑘)
𝜋𝑖 𝑗
𝜕𝜆𝑖 𝑗
,
𝑓 , (𝑘)
𝑓 , (𝑘) 𝜕𝜋 𝑖 𝑗
= 𝑥𝑖
≥ 0.
Therefore, from (10) and (11), increasing forwarding probabilities increases, or at least does not decrease, the surrogate load (𝑘) (𝑘) 𝐿 . Hence, 𝐿 captures the communication cost caused by redundancy. The timely-PDR surrogate captures both the activation benefit and the delay cost of redundancy. For a candidate path 𝑝, (𝑘) (𝑘) (𝑘) PDR 𝑓 ,𝑝 = 𝐴 𝑓 ,𝑝𝐹 𝑓 ,𝑝,
(𝑘) where 𝐴 (𝑘) 𝑓 , 𝑝 is the path activation probability and 𝐹 𝑓 , 𝑝 is the deadline-feasibility term. Increasing forwarding probabilities (𝑘) improves 𝐴 𝑓 , 𝑝 , but also increases link load, reduces service slack, and may inflate the delay mean and variance, thereby reducing 𝐹 (𝑘) 𝑓 , 𝑝 . Thus,
𝑓 ,𝑝 𝜕 PDR (𝑘)
𝑓 , (𝑘)
𝜕𝜋 𝑖 𝑗
=
(𝑘) 𝐹 𝑓 ,𝑝
|
𝜕 𝐴 (𝑘) 𝑓 ,𝑝 𝑓 , (𝑘)
𝜕𝜋 𝑖 𝑗 {z }
redundancy-induced gain
+
(𝑘) 𝐴 𝑓 ,𝑝
|
𝜕𝐹 (𝑘) 𝑓 ,𝑝 𝑓 , (𝑘)
.
𝜕𝜋 𝑖 𝑗 {z }
congestion-induced loss
The first term is nonnegative, while the second term can be negative under congestion-induced delay inflation. This decomposition shows that the surrogate timely PDR reflects both the benefit and the cost of redundancy: additional forwarding may improve reliability by activating more paths, but excessive forwarding can reduce timely delivery through congestioninduced delay inflation. C. H-RATIO Operations 1) Reduced DAG Construction: In each routing period 𝑘, (𝑘) a reduced DAG D 𝑓 is constructed for each active flow 𝑓 ∈ F (𝑘) . The reduced DAG is required to (i) connect 𝑠 𝑓 to 𝑑 𝑓 , (ii) be acyclic, and (iii) contain a limited number of edges so that probability assignment remains tractable. Let 𝛾𝑖(𝑘) 𝑗 denote the receive signal strength (RSS), and let (𝑘) LET𝑖 𝑗 denote the estimated link expiration time (LET). First, links are pruned using thresholds 𝛾𝑖(𝑘) 𝑗 < 𝛾min
or LET𝑖(𝑘) 𝑗 < LETmin .
Next, a scalar link quality score 𝜒𝑖(𝑘) 𝑗 , which is a weighted sum of normalized RSS and LET is assigned to each link, i.e., (𝑘) 𝛾𝑖(𝑘) 𝑗 − 𝛾min © LET𝑖 𝑗 ª (𝑘) 𝜒𝑖 𝑗 ¬ 𝛼rss + (1 − 𝛼rss ) min , 1® , 𝛾max − 𝛾min LETref
« ¬ where 𝛼rss ≥ 0 is the weight controlling the emphasis between RSS and LET, 𝛾max is the empirical maximum RSS to normalize RSS, and LETref is the reference LET to normalize LET. To extract candidate paths, the corresponding edge cost (𝑘) is defined as 𝑐 𝑖(𝑘) 𝑗 ¬ −𝜒𝑖 𝑗 , and up to 𝑃max candidate 𝑠 𝑓 – 𝑑 𝑓 paths are extracted on the pruned weighted graph (e.g.,
using 𝑘-shortest paths). The union of edges in these candidate paths is then converted into a loop-free DAG by enforcing a topological order and removing back-edges. In particular, let ℎ𝑖 denote the hop-to-go distance from node 𝑖 to 𝑑 𝑓 computed on the pruned graph (ties broken arbitrarily). Only edges satisfying ℎ𝑖 > ℎ 𝑗 are retained, which guarantees acyclicity and preserves directional progress toward 𝑑 𝑓 . The resulting subgraph is denoted by D (𝑘) 𝑓 . 2) Forwarding Probability Assignment and Refinement: Instead of solving a coupled non-convex optimization over all 𝑓 , (𝑘) {𝜋 𝑖 𝑗 }, forwarding probabilities are assigned in two stages: (i) computing normalized splitting weights on each reduced DAG, and (ii) refining node-level replication factors through a small number of surrogate-guided iterations. Specifically, in each routing period 𝑘, the computation of forwarding probabilities and replication factors depends on three sets of parameters. The first set is the flow requirements, 𝑓 including the source rate 𝑟 𝑓 , deadline 𝐷 max , and target timely PDR 𝜂 𝑓 . The second set is the short-term link measurements used for tractable and practical decision-making, including the estimated service rate 𝐶¯𝑖(𝑘) 𝑗 , RSS/SINR-related link qual-
(𝑘) ity 𝛾𝑖(𝑘) 𝑗 , and link expiration time LET𝑖 𝑗 . The third set is the hyperparameters used in reduced-DAG construction and replication refinement, including (𝛾min , LETmin , 𝛼rss , 𝑃max ), the splitting parameter 𝛽link , and the refinement parameters (Δ, 𝐼max , 𝜌max ). Given the constructed DAG, the expected node arrival rate 𝑓 , (𝑘) , is computed of flow 𝑓 at node 𝑖 in period 𝑘, denoted by 𝑥𝑖 by 𝑖 = 𝑠𝑓, 𝑟 𝑓 , 𝑓 , (𝑘) (19) 𝑥𝑖 = Í 𝑓 , (𝑘) 𝑓 , (𝑘) 𝜋 𝑢𝑖 , 𝑖 ≠ 𝑠𝑓. (𝑘) 𝑥 𝑢 𝑢∈ N −, 𝑓 ,𝑖 This equation propagates the expected traffic rate along the reduced DAG. The source injects traffic at rate 𝑟 𝑓 . For each relay node, the expected incoming traffic is the sum of the traffic forwarded from its upstream neighbors. Therefore, this recursion allows H-RATIO to estimate how forwarding probabilities affect traffic distribution inside the DAG. For each flow 𝑓 and node 𝑖 with outgoing neighbors 𝑓 , (𝑘) (𝑘) N +, ≠ ∅, a local score 𝜓𝑖 𝑗 is assigned to each outgoing 𝑓 ,𝑖 edge: 𝑓 , (𝑘)
𝜓𝑖 𝑗
¬ 𝛽link 𝜒𝑖(𝑘) 𝑗 − (1 − 𝛽link ) ℎ 𝑗 ,
(𝑘) 𝑗 ∈ N +, 𝑓 ,𝑖 ,
where ℎ 𝑗 is the hop-to-go from 𝑗 to 𝑑 𝑓 , and 𝛽link ∈ [0, 1] controls the emphasis on link quality versus hop distance. 𝑓 , (𝑘) The local score 𝜓𝑖 𝑗 favors outgoing links that are both reliable and make progress toward the destination. A link with better quality or longer expected lifetime obtains a larger score through 𝜒𝑖(𝑘) 𝑗 . A link leading to a node closer to the destination also obtains a larger score through the hop-to-go penalty. The scores are converted into splitting weights by softmax: 𝑓 , (𝑘) exp 𝜓𝑖 𝑗 𝑓 , (𝑘) (𝑘) , 𝑗 ∈ N +, 𝜔𝑖 𝑗 ¬ Í 𝑓 ,𝑖 . 𝑓 , (𝑘) exp 𝜓𝑖ℓ ℓ ∈ N +, (𝑘) 𝑓 ,𝑖
The softmax operation converts local scores into normalized splitting weights. A link with a larger score receives a larger
12
weight, but other feasible outgoing links can still receive nonzero weights. Therefore, H-RATIO does not make a hard next-hop decision at a fork node. Instead, it distributes forwarding opportunities among multiple outgoing links according to their relative quality. 𝑓 , (𝑘) A replication factor 𝜅𝑖 ≥ 1 is assigned to each relay node 𝑖 on D (𝑘) . Forwarding probabilities are then computed 𝑓 as 𝑓 , (𝑘) 𝑓 , (𝑘) 𝑓 , (𝑘) (𝑘) 𝜋𝑖 𝑗 ¬ min 1, 𝜅𝑖 𝜔𝑖 𝑗 , 𝑗 ∈ N +, (20) 𝑓 ,𝑖 .
600
500
Y (m)
400
100
0
𝑓 , (𝑘)
𝑓 , (𝑘)
can be interpreted as the expected number In this case, 𝜅𝑖 𝑓 , (𝑘) of outgoing copies generated by node 𝑖. Thus, increasing 𝜅𝑖 increases redundancy, while decreasing it reduces transmission overhead. This simple control variable allows H-RATIO to adjust redundancy without directly solving the full RATIO optimization problem. 𝑓 , (𝑘) Replication factors are initialized as 𝜅𝑖 = 1, correspond𝑓 , (𝑘) ing to no additional replication. After each update of 𝜅𝑖 , the 𝑓 , (𝑘) controller recomputes {𝜋 𝑖 𝑗 } using (20), updates the induced node arrival rates along the topological order of D (𝑘) , and 𝑓 then reevaluates the surrogate load, link utilization, and timely PDR. The node arrival rates are then updated using (19). Replication factors are refined iteratively through two complementary updates. The purpose is to increase redundancy only when it is needed for timely reliability and to reduce redundancy when it causes excessive load. • Increase replication to meet timely PDR. If 𝑓 (𝑘) (𝐷max 𝑓 ) < 𝜂 𝑓 , the current forwarding PDR configuration is estimated to be insufficient for the reliability requirement of flow 𝑓 . In this case, H-RATIO 𝑓 , (𝑘) increases 𝜅𝑖 at selected fork nodes so that more outgoing links can be activated and more path diversity can be exploited. • Decrease replication to mitigate overload. If any physical (𝑘) link violates the utilization constraint, i.e., 𝜌𝑖 𝑗 > 𝜌max , the current redundancy level is considered too aggressive for the available channel capacity. In this case, H-RATIO decreases the replication factor of the flow and node that contribute most to the overloaded link, thereby reducing unnecessary transmissions and relieving congestion. The refinement is repeated for at most 𝐼max iterations or until no replication factor changes. Thus, the final forwarding probabilities depend explicitly on the measured link states, flow requirements, DAG construction parameters, softmax splitting parameter, and replication-refinement parameters.
300
200
This equation connects splitting and replication. The splitting 𝑓 , (𝑘) weight 𝜔𝑖 𝑗 determines the relative preference among outgoing links, while the replication factor 𝜅𝑖 controls the overall amount of redundancy generated at node 𝑖. When 𝑓 , (𝑘) 𝜅𝑖 = 1, the node mainly performs probabilistic splitting 𝑓 , (𝑘) without additional replication. When 𝜅𝑖 > 1, the forwarding probabilities are amplified, so multiple outgoing links are more likely to be activated by the modulo-based forwarding rule. The operator min 1, · ensures that each individual edge probability remains valid. Í 𝑓 , (𝑘) 𝑓 , (𝑘) ≈ 𝜅𝑖 When no outgoing edge saturates at 1, 𝑗 𝜋 𝑖 𝑗 .
Vehicle RSU
0
100
200
300
400
500
600
X (m)
Fig. 3: A 3 × 3 road grid with five RSUs. 𝑓 , (𝑘)
After termination, the resulting {𝜋 𝑖 𝑗 } are installed for period 𝑘 and executed by each node using the modulo-based packet forwarding rule described in Section IV-A. D. Complexity and Scalability Analysis Let 𝑉 ¬ |V|, 𝐸 ¬ |E (𝑘) |, 𝐹 ¬ |F (𝑘) |, and let 𝐸¯ 𝑓 denote the edge count of reduced DAG D (𝑘) (𝑃¯ 𝑓 ≤ 𝑃max candidate 𝑓 paths per flow). In each routing period, link pruning costs 𝑂 (𝐸). For each flow, extracting up to 𝑃max candidate paths on the pruned graph costs 𝑂 (𝑃max (𝐸 + 𝑉 log 𝑉)) using repeated shortest-path style extraction, and DAG conversion plus local scoring/softmax costs 𝑂 ( 𝐸¯ 𝑓 ). 𝐹 𝐹 Õ ª ©Õ ª © 𝑃max (𝐸 + 𝑉 log 𝑉) ® . 𝐸¯ 𝑓 ® + 𝑂 Cbuild = 𝑂 𝐸 + 𝑓 =1 ¬ « 𝑓 =1 ¬ «
𝑓 , (𝑘)
In each refinement iteration, DAG recursion for {𝑥𝑖 }, link-load/utilization aggregation, and surrogate timely-PDR Í evaluation together cost 𝑂 𝐹𝑓=1 𝐸¯ 𝑓 under bounded pathlength approximation. With at most 𝐼max iterations, Õ ª © 𝐸¯ 𝑓 ® . Crefine = 𝑂 𝐼max 𝑓 =1 ¬ « 𝐹
Hence,
Cperiod = Cbuild + Crefine
Õ © ª = 𝑂 𝐸 + 𝑃max (𝐸 + 𝑉 log 𝑉) ® 𝑓 =1 « ¬ 𝐹 Õ ª © 𝐸¯ 𝑓 ® . + 𝑂 (1 + 𝐼max ) 𝑓 =1 ¬ « Í and memory complexity is 𝑂 𝐸 + 𝐹𝑓=1 𝐸¯ 𝑓 . Since 𝑃max and 𝐼max are small constants in practice, H-RATIO scales nearlinearly with the number of active flows and reduced-DAG size, which supports large-network deployment. 𝐹
13
TABLE I: Simulation parameters.
TABLE II: H-RATIO configuration.
Parameter
Value
H-RATIO Parameter
Value
Carrier frequency Channel bandwidth Transmit power Path-loss exponent Log-normal shadowing (std. dev.) Building blockage loss Queue length Mobility sampling step (Δ𝑡) Simulation duration (𝑇sim ) Warm-up duration (𝑇warm ) Packet size (𝐿pkt )
5.9 GHz 10 MHz 20 dBm 2.8 4 dB 80 dB 50 packets 0.1 s 120 s 20 s 1200 bytes
Max number of candidate paths (𝑃max ) RSS–LET mixing weight (𝛼rss ) Link–hop score weight (𝛽link ) Reference LET for normalization (LETref ) Max link utilization threshold (𝜌max ) Replication update step (Δ) Max refinement iterations (𝐼max ) Link RSS pruning threshold (𝛾min ) Link LET pruning threshold (LETmin ) Max RSS for normalization (𝛾max )
4 0.5 0.5 𝑇route 0.9 0.2 10 −90 dB 0.3𝑇route 50 dB
VI. P ERFORMANCE E VALUATION In this section, the proposed H-RATIO routing scheme is evaluated via trace-driven SUMO/ns-3 co-simulations. Vehicle mobility traces are generated by SUMO [42] and are replayed in ns-3 [43] to emulate end-to-end multi-hop transmissions under packet-level PHY/MAC dynamics. A. Simulation Setup Downlink media delivery is considered, where media packets are delivered from the core server (CORE) to vehicles via roadside units (RSUs). A trace-driven workflow is adopted: time-stamped vehicle trajectories are produced by SUMO and are subsequently replayed in ns-3, so that the underlying connectivity evolution is consistent across routing schemes. Routing decisions are enforced at the IP layer by a centralized controller, where per-flow forwarding rules are periodically computed and installed at the beginning of each routing period. At the PHY/MAC layer, IEEE 802.11p is used [44], and packet transmissions are simulated by ns-3 accordingly. 1) Network Scenario: As illustrated in Fig. 3, an urban road topology is constructed as a 3 × 3 grid with two-lane roads. Adjacent intersections are spaced by 300 m, and the lane width is set to 3.5 m. Five RSUs are deployed at fixed off-road locations, including the four corners and the grid center. Each RSU is connected to the CORE via a wired Ethernet backhaul, while wireless forwarding is performed using IEEE 802.11p at a PHY data rate of 24 Mbps. To emulate urban blockage, four building blocks are placed inside the grid, one per city block. Each block is modeled as a cuboid with size 240 m×240 m×20 m, whose footprint is inset by 30 m from the road center lines. A wireless link is regarded as blocked when the direct Tx–Rx line segment intersects any building cuboid; for blocked links, an additional attenuation penalty is applied. Vehicle mobility traces are generated by SUMO under the above road layout, and each trace is exported as a mobility file containing vehicle positions sampled every Δ𝑡 seconds. 2) Flow Generation and Route Decision: Unicast downlink content delivery from the CORE to vehicles is considered. A set of unicast UDP flows F is generated, where each flow 𝑓 transmits fixed-size packets of 𝐿 pkt bytes at rate 𝑟 𝑓 bits per second. In our simulations, homogeneous rates are used, i.e., 𝑟 𝑓 = 𝑟 for all 𝑓 . By increasing the vehicle density 𝑁veh and/or
the per-flow rate 𝑟, higher medium contention is induced at the MAC layer. Time is divided into routing periods indexed by 𝑘, each with duration 𝑇route . At the beginning of each period, per-flow forwarding rules are computed by the centralized controller and are installed at the IP layer. The installed rules are kept fixed throughout the period. 3) PHY Layer and MAC Layer Parameters: Packet transmissions are simulated in ns-3 using IEEE 802.11p PHY/MAC. Vehicles and RSUs are equipped with IEEE 802.11p interfaces to enable multi-hop wireless forwarding. Mobility is implemented by replaying SUMO trajectories as waypoint sequences. A log-distance path-loss model with log-normal shadowing is adopted to capture large-scale channel variations. To emulate severe NLOS blockage by buildings, an additional attenuation penalty of 80 dB is applied whenever the direct Tx–Rx line segment is obstructed. MAC contention (CSMA/CA) and queueing are enabled, and each node employs a DropTail queue with a capacity of 50 packets. The main network parameters are summarized in Table I. B. Properties of H-RATIO Algorithm We first evaluate several properties of the proposed HRATIO algorithm, including scalability, ablation study, and parameter sensitivity. 1) Scalability: We evaluate scalability by comparing the per-decision runtime of H-RATIO with three representative baselines: SP, MP-REP, and MP-LB. The number of vehicles is varied as 𝑁veh ∈ {72, 108, 144, 180, 216, 252, 288}, while the load fraction and per-flow rate are fixed at 0.3 and 50 kbps, respectively. The scalability results are shown in Fig. 4. The per-decision runtime of all methods increases with network size. Among the four schemes, SP achieves the lowest runtime, followed by MP-REP. MP-LB incurs higher runtime than MP-REP because it additionally computes traffic allocation over multiple candidate paths. H-RATIO has the highest runtime, as it constructs a reduced DAG and determines forwarding ratios over multiple outgoing branches. Nevertheless, its runtime increases steadily and remains well bounded as the number of vehicles grows. At 𝑁veh = 288, which corresponds to 80 veh/km in the considered 3×3 urban grid, the average per-decision runtime of H-RATIO is 0.415 s. This indicates that, although H-RATIO is computationally more expensive than the simpler baselines, its
14
0.2
0.00
0.1 0.0
0.9
0.25
0.50
0.75
1.00
αrss 100
150
200
1.00
250
Vehicle count
Fig. 4: Per-decision runtime versus the number of vehicles for H-RATIO and the three baseline schemes under flow rate 50 kbps.
0.95 0.90 0.00
0.25
0.50
0.75
1.00
βlink 1.0
Timely PDR
Timely PDR
1.0
0.9
0.8
0.8
1
2
3
4
5
Pmax Fixed κ Prob. splitting
Full
Trans. load (hop-tx/s)
(a) Ablation results on timely PDR. 900 800
0.9 0.8 0.6
0.7
0.8
ρmax 700 600 None
Fixed κ Prob. splitting
Full
(b) Ablation results on transmission load.
Fig. 5: Ablation results on timely PDR and transmission load for None, Fixed 𝜅, Prob. splitting, and the full H-RATIO scheme. decision overhead remains below 0.5 s even in the largest evaluated scenario, demonstrating practical scalability for dense V2X networks. 2) Ablation Study: To isolate the contribution of each key component, we perform an ablation study under 144 vehicles, LF = 0.3, and a per-flow rate of 50 kbps, averaged over nine scenario instances. The compared variants are: None: no DAG diversity and no replication are used; each packet is forwarded along a single shortest path. • Fixed 𝜅: redundancy is enabled over multiple branches, but the replication factor is kept constant throughout the run. • Prob. splitting: conventional probabilistic splitting is used over multiple outgoing links, so traffic is normalized across outgoing links and no explicit multi-copy replication is introduced. • H-RATIO (full): the complete method with reducedDAG diversity, modulo-based stochastic forwarding, and iterative replication-factor refinement. •
1.0
Timely PDR
None
0.9
1.0
Trans. load (hop-tx/s) Trans. load (hop-tx/s) Trans. load (hop-tx/s) Trans. load (hop-tx/s)
0.3
LET-Dominant
1.0
Timely PDR
0.4
RSS-Dominant
SP MP-REP MP-LB H-RATIO
Timely PDR
Per-decision runtime (s)
0.5
Balanced
750 700 650 0.00
0.25
0.50
0.75
1.00
0.75
1.00
4
5
0.9
1.0
αrss 750 700 650 0.00
0.25
0.50
βlink 600 400 1
2
3
Pmax
600
400 0.6
0.7
0.8
ρmax
Fig. 6: Parameter sensitivity of H-RATIO under 144 vehicles, LF = 0.3, a per-flow rate of 50 kbps, and a routing period of 2 s. Each row varies one parameter and reports timely PDR and transmission load in RSS-dominant, LET-dominant, and balanced scenarios. The ablation results are shown in Fig. 5. The full HRATIO scheme achieves the best overall reliability-cost tradeoff. Specifically, the full scheme attains the highest timely PDR of 95.9%, compared with 79.1% for None, 89.3% for Fixed 𝜅, and 85.7% for Prob. splitting. At the same time, its transmission load is 758.1 hop-tx/s, which is substantially lower than the 879.7 hop-tx/s of Fixed 𝜅, while delivering a higher timely PDR. The ablation results further reveal the contribution of each component. DAG/path diversity provides the structural basis by offering alternative forwarding branches, but its gain is limited without explicit replication. Fixed 𝜅 shows that replication is the main source of reliability improvement, but unconditional duplication also introduces excessive load. The full H-RATIO achieves the best trade-off because its iterative refinement adaptively controls the replication factor, while the modulo-based forwarding rule realizes non-integer and flowspecific replication at the packet level. Therefore, DAG diversity enables redundancy, replication improves timely reliability, and adaptive modulo-based replication control contributes most to reducing unnecessary transmissions while maintaining high PDR. 3) Parameter Sensitivity: To evaluate parameter robustness, we vary one parameter at a time while keeping the others fixed
15
"
!
"#
"#
"
"
"
"
"
"
"
"
"#
"
"
"
"
"##
"
"
"
"
"
"
"
"
"
"# " " " " "
Fig. 7: Average replication level selected by H-RATIO under different vehicle densities and per-flow rates with routing period 𝑇route = 10 s. under a setting of 144 vehicles, a per-flow rate of 50 kbps, and a routing period of 2 s. Three scenarios are considered: an RSS-dominant scenario where received signal strength (RSS) estimation exhibits larger errors, an LET-dominant scenario where link expiration time (LET) estimation exhibits larger errors, and a balanced scenario where the estimation errors of RSS and LET are comparable. The sensitivity results are shown in Fig. 6. Several conclusions can be drawn from the results. First, 𝛼rss primarily controls the trade-off between short-term channel quality and link persistence. Larger values are favored when RSS is more reliable, smaller values are favored when LET is more reliable, and 𝛼rss = 0.5 provides a good overall balance across the three scenarios. Second, the effect of 𝛽link is relatively mild. Increasing 𝛽link slightly strengthens the preference for link quality and improves timely PDR, but it also increases the forwarding load. Therefore, 𝛽link = 0.5 is adopted as a balanced choice. Third, for 𝑃max , enabling two path candidates already brings most of the reliability gain, improving the average timely PDR from 76.9% to 94.1%. Further increasing 𝑃max provides limited additional benefit, indicating that a small candidate-path set is sufficient in the considered scenarios. Finally, 𝜌max shows a clear reliability-cost trade-off. Increasing 𝜌max from 0.6 to 0.9 improves the average timely PDR from 75.1% to 94.1%, because a higher utilization threshold allows more redundancy. However, when 𝜌max reaches 1.0, the timely PDR drops to 82.8% although the forwarding load continues to increase. This is because link utilization close to one causes larger queueing delay, which hurts timely delivery. Overall, H-RATIO is most sensitive to 𝑃max and 𝜌max , which control path diversity and link-utilization tolerance, while 𝛼rss and 𝛽link mainly fine-tune the route-selection bias. Based on these results, the hyper-parameters, including 𝑃max , 𝜌max , 𝛼rss , and 𝛽link , are selected accordingly provide a robust reliability-cost balance, as summarized in Table II. In practical deployments, the parameters can be further tuned according to scenario characteristics. For sparse networks, a longer routing period, a larger 𝑃max , and stronger LET emphasis can help preserve route diversity and stability. For dense networks or high traffic rates, a shorter routing period, a smaller 𝑃max , or a more conservative 𝜌max can reduce contention and queueing delay.
C. Scenario Adaptability of H-RATIO 𝑓 , (𝑘)
In H-RATIO, the replication factors {𝜅𝑖 } are obtained by the iterative refinement in Algorithm 2. To examine how replication adapts across operating regimes, a two-dimensional scenario grid is formed by varying vehicle density and per-flow offered rate. Vehicle counts are set to 𝑁veh ∈ {144, 162, 180, 198, 216}, and homogeneous per-flow rates are set to 𝑟 ∈ {20, 35, 50, 65, 80} kbps. In total, 25 scenarios are evaluated. All H-RATIO hyper-parameters are fixed as in Table II, and the routing period is set to 𝑇route = 10 s. For each scenario, an average replication factor is obtained by aggregating node-level replication factors over active flows and routing periods. The resulting scenario-dependent averages are summarized in Fig. 7. Two consistent trends are observed. First, for any fixed vehicle density, the average replication level decreases monotonically as the offered rate 𝑟 increases. This indicates that redundancy is gradually de-emphasized as the network transitions from a lightly loaded regime to a contention-limited regime. Intuitively, additional copies create more delivery opportunities, but they also increase hop transmissions and raise the aggregate offered load on shared wireless links. Once queues start to build up, the resulting delay inflation reduces the fraction of packets that can meet the deadline, so the marginal reliability gain from replication diminishes. Second, the impact of vehicle density is most visible at low-to-moderate rates. When 𝑟 is small, a higher 𝑁veh tends to be associated with smaller replication factors, reflecting a tighter “redundancy budget” under denser interference and more frequent contention. As 𝑟 becomes large, the selected replication levels concentrate close to one across all densities, suggesting a saturation effect. That is, when airtime becomes the dominant bottleneck, near-minimal redundancy is preferred to avoid amplifying contention. Overall, the results support the design rationale of H-RATIO: replication is increased only when spare capacity exists and is scaled back automatically when the load–contention feedback becomes dominant. D. H-RATIO vs. Baseline Schemes In this subsection, H-RATIO is compared with several baseline routing schemes. Two representative operating regimes are considered: (i) a moderate-load setting with 𝑁veh = 144 and 𝑟 = 50 kbps, and (ii) a high-load setting with 𝑁veh = 216 and 𝑟 = 80 kbps. For each regime, the routing update period is swept as 𝑇route ∈ {1, 2, 5, 10, 20} s. For H-RATIO, the configuration in Table II is adopted. For the fixed-redundancy baseline, the redundancy baseline 𝜌base is selected via a scenario-dependent search. Independent mobility traces are generated in SUMO using different random seeds, and each trace is replayed in ns-3. Each ns-3 run lasts 𝑇sim seconds and includes a warm-up interval of 𝑇warm seconds. To mitigate initialization transients, performance statistics are collected over the measurement window [𝑇warm , 𝑇sim ]. Mean values with 95% confidence intervals (CI) are reported across mobility and traffic seeds. To ensure a fair comparison, all schemes share (i) identical mobility traces, (ii) the same PHY/MAC configuration, and (iii) the
16
-# ./ 0,/
& " #$% '
) #, ) #, #*,
% ! "#$ &
! !
) #*+ ) #*+#*,
! ! " #$%
( ( #*,
(a) 𝑁veh = 144, 𝑟 = 50 kbps.
! "#$
(b) 𝑁veh = 216, 𝑟 = 80 kbps.
Fig. 8: Performance comparison under two traffic conditions: (a) 𝑁veh = 144, 𝑟 = 50 kbps and (b) 𝑁veh = 216, 𝑟 = 80 kbps. same traffic generation settings; only route construction logic and forwarding/redundancy decisions are varied. Note that GEO additionally relies on node position information for nexthop selection, whereas H-RATIO and the other path-based baselines do not. 1) Baseline Routing Schemes: H-RATIO is compared with the following baselines. For each baseline, an LET-aware variant is also implemented. •
Shortest-path (SP). For each flow, a single end-toend path with the minimum cumulative weight on the connectivity graph is selected, and packets are forwarded deterministically along that path. In routing period 𝑘, each (𝑘) directed link (𝑖, 𝑗) is assigned weight 𝑤 𝑖(𝑘) 𝑗 = 1+load𝑖 𝑗 ,
where load𝑖(𝑘) denotes the estimated traffic load on 𝑗 (𝑖, 𝑗). To reduce systematic bias, flows are processed in randomized order. • Multi-path load balancing (MP-LB). A baseline that distributes traffic across multiple candidate paths without replication is considered, i.e., each packet is transmitted on exactly one path. Given the connectivity graph and the set of flows, a load-balancing problem is solved to minimize the maximum link load. • Multi-path replication (MP-REP). A baseline that duplicates packets deterministically at selected branching nodes using a fixed replication level is considered. When replication is enabled, each packet is duplicated and the two copies are forwarded along two distinct outgoing branches. • LET-enhanced SP, MP-LB, and MP-REP In LETaware variants, termed SP-LET, MP-LB-LET, and MPREP-LET, respectively, path stability is defined as the minimum link expiration time (LET) among links on the path, and candidate paths are prioritized when their path stability exceeds a threshold. If no feasible option exists, the threshold is progressively relaxed to preserve connectivity.
•
Geographic Routing (GEO). A baseline that selects the next hop according to geographic progress toward the destination. Unlike the aforementioned path-based schemes, it does not rely on an explicitly constructed endto-end route, but makes forwarding decisions hop by hop using node position information.
2) Evaluation Metrics: The primary performance metrics are timely packet delivery ratio (PDR) and transmission load, measured as hop transmissions per second (hop-tx/s). Average end-to-end delay, denoted as delay mean, is reported to capture the latency of successfully delivered packets, measured from packet generation at the source to reception at the destination. To quantify delivery efficiency under multihop forwarding and redundancy, the delivery cost, defined as the average number of hop transmissions required per delivered packet (hop-tx/pkt), is also reported. All metrics are computed over the measurement window [𝑇warm , 𝑇sim ] and averaged across independent mobility and traffic seeds, with 95% confidence intervals (CI) reported. Because H-RATIO intentionally enables redundant forwarding, duplicate suppression is performed only at the destination. Intermediate relays simply forward packets according to the installed per-flow rules and do not remove duplicates; otherwise, the intended redundancy across different branches would be prematurely eliminated. Each packet is identified by its flow ID and sequence number. The first copy received at the destination is counted as the delivered packet, while later copies with the same identifier are discarded. Accordingly, end-to-end metrics, including timely PDR, throughput if reported, and average delay, are computed over unique delivered packets after destination-side duplicate suppression, with delay measured using the earliest received copy. In contrast, transmission load and delivery cost count all hop transmissions, including duplicate copies, because they still consume wireless airtime, occupy queues, and contribute to MAC-layer contention.
17
3) Results and Discussion: In Fig. 8, timely PDR, average delay, transmission load (hop-tx/s), and delivery cost (hop-tx/pkt) are reported under the period sweep 𝑇route ∈ {1, 2, 5, 10, 20} s for both the moderate-load (𝑁veh =144, 𝑟=50 kbps) and high-load (𝑁veh =216, 𝑟=80 kbps) settings. a) Performance.: Across all schemes, performance is dominated by route freshness. When routes are updated frequently (𝑇route ≤ 5 s), timely PDR remains relatively stable; once updates become stale (𝑇route ≥ 10 s), timely PDR drops noticeably, with a more severe degradation under high load. Average delay follows a similar congestion-sensitive trend: it remains relatively small under moderate load, while increasing clearly under high load, especially for schemes with aggressive replication. Among the path-based schemes without position information, H-RATIO consistently provides the highest timely PDR, while GEO serves as a stronger-information baseline that additionally exploits node positions. It is also observed that transmission load may decrease when routes are stale, e.g., because fewer packets are successfully relayed, while delivery cost increases. Meanwhile, H-RATIO keeps average delay at a controlled level: under moderate load its delay is close to that of the non-replicating baselines and much lower than MPREP, while under high load it avoids the large delay increase observed with deterministic replication. Under the moderate-load setting (𝑁veh =144), nonreplicating baselines, including SP and MP-LB, saturate around timely PDR ≈ 70%–75% for 𝑇route ≤ 5 s and then degrade sharply at 10–20 s. Deterministic replication can raise timely PDR when spare airtime exists, e.g., MPREP-LET reaches 93% at 𝑇route =2 s, but this improvement comes with substantially higher load and delivery cost. By contrast, H-RATIO achieves timely PDR near 95% at 𝑇route =1–2 s, outperforming SP-LET by roughly 20% absolute while incurring only a modest load increase. It also attains comparable or slightly higher timely PDR than MP-REP-LET while reducing transmission load by ∼35% and delivery cost by ∼35%. Moreover, H-RATIO reduces average delay substantially compared with MP-REP-LET, indicating that selective redundancy improves reliability without introducing the queueing penalty of unconditional duplication. GEO achieve very similar timely PDR compared to H-RATIO. For example, at 𝑇route =1 and 2 s, H-RATIO reaches 94.9% and 94.7%, while GEO reaches 94.5% and 94.4%. Besides, GEO consistently achieves lower average delay, transmission load, and delivery cost, since it uses single-path forwarding without redundancy. Under the high-load setting (𝑁veh =216), the redundancy– congestion interaction becomes dominant. In this regime, MPREP no longer improves timely PDR, while incurring much higher transmission load and delivery cost. This congestion is also reflected in delay, where MP-REP and MP-REP-LET show the largest average-delay values across the schemes. By contrast, H-RATIO maintains timely PDR around 83% at 𝑇route =1–2 s, improving over SP-LET by ∼12% absolute and simultaneously reducing delivery cost. Relative to MPREP-LET, timely PDR is improved by nearly 30% while transmission load is reduced by ∼16–18%, consistent with
congestion-aware redundancy allocation that avoids contention collapse. The corresponding delay results further support this conclusion: H-RATIO achieves its reliability gain with much lower latency than fixed replication under high load. In this high-load regime, GEO achieves higher timely PDR than HRATIO across all routing periods, although the gap remains relatively small. For example, at 𝑇route =1 s, H-RATIO attains a timely PDR of 82.9%, compared with 86.6% for GEO. GEO also incurs lower transmission load and delivery cost. This suggests that under dense and highly loaded conditions, the position-guided hop-by-hop decisions of GEO are particularly effective in maintaining forwarding efficiency while avoiding the extra channel usage introduced by redundancy. Nevertheless, H-RATIO still remains the best-performing scheme among the path-based baselines, hence offering important advantages when position information is unavailable or inaccurate. LET-aware variants provide consistent but modest gains for SP, MP-LB, and MP-REP, with the improvements more visible at longer 𝑇route . However, LET filtering alone does not resolve the reliability–load tension. It can improve path stability, but it does not determine how much redundancy should be introduced under a given contention level. This is why H-RATIO outperforms LET-only variants: it jointly exploits structural route diversity and adaptive redundancy control. In summary, H-RATIO achieves the best deadlineconstrained reliability among the path-based schemes across both load regimes and routing periods by combining compact structural diversity with congestion-aware stochastic redundancy. At the same time, the newly added GEO baseline shows that when accurate position information is available, geographic forwarding can provide even better overall performance, especially under the high-load setting. b) Fairness and flow interaction.: The above results also reveal an important fairness issue in redundancy-based routing. When multiple flows share wireless links, a flow with a higher redundancy requirement may consume more hop transmissions and therefore reduce the available airtime for other flows. This interaction becomes more significant under congestion, where additional copies can increase queueing delay and potentially limit lower-priority or less redundant flows. H-RATIO mitigates this issue in two ways. First, the reduced DAG is flowspecific but the replication refinement is constrained by linkutilization estimates, so a flow cannot increase its redundancy without considering the resulting load on shared links. Second, the adaptive refinement tends to scale down replication when the offered traffic rate or vehicle density increases, as shown in Fig. 7. Therefore, H-RATIO does not simply favor highredundancy flows; instead, it allocates redundancy according to the estimated reliability benefit and the congestion cost. Nevertheless, strict inter-flow fairness is not the primary optimization objective in the current implementation. In scenarios with heterogeneous service classes, fairness can be incorporated by assigning each flow a priority weight, a maximum replication cap, or a per-flow airtime budget. For example, safety-critical flows can be given a higher redundancy allowance, while best-effort flows can be restricted by a smaller
18
replication cap when the shared medium becomes congested. Another possible extension is to add a fairness regularization term, such as max-min timely PDR or proportional fairness, to the replication refinement objective. These extensions would allow H-RATIO to balance deadline-constrained reliability and resource fairness more explicitly under mixed-priority traffic. VII. C ONCLUSION In this paper, redundancy-controlled stochastic (RATIO) routing was proposed to support reliable deadline-constrained multi-hop delivery in V2X networks by allocating continuously tunable stochastic redundancy over flow-specific reduced DAG routes. The idealized problem formulation of RATIO is given, and a scalable per-period heuristic (H-RATIO) was developed for practical deployment. Trace-driven SUMO/ns3 co-simulations showed that timely PDR was consistently improved over shortest-path and multi-path load-balancing baselines across moderate/high loads, while substantially better delivery efficiency was achieved than multi-path replication baseline, especially in high-load regimes. For future work, extensions can be made to distributed implementations with local message exchange, cross-layer coupling with MAC/scheduling, and richer mobility/blockage prediction to reduce control overhead and improve route robustness under rapid topology changes. R EFERENCES [1] H. Hartenstein and K. P. Laberteaux, “A tutorial survey on vehicular ad hoc networks,” IEEE Communications Magazine, vol. 46, no. 6, pp. 164–171, 2008. [2] S. Al-Sultan, M. M. Al-Doori, H. M. Al-Bayatti, and H. Zedan, “A comprehensive survey on vehicular ad hoc network,” Journal of Network and Computer Applications, vol. 37, pp. 380–392, 2014. [3] M. A. Al-shareeda, M. A. Alazzawi, M. Anbar, S. Manickam, and A. K. Al-Ani, “A comprehensive survey on vehicular ad hoc networks (VANETs),” in Proceedings of International Conference on Advanced Computer Applications (ACA), 2021, pp. 156–160. [4] B. Zhai, M. Yu, A. Tang, and X. Wang, “Mesh architecture for efficient integrated access and backhaul networking,” in Proceedings of IEEE Wireless Communications and Networking Conference (WCNC), 2020, pp. 1–6. [5] B. L. Nguyen, D. T. Ngo, M. N. Dao, V. N. Q. Bao, and H. L. Vu, “Scheduling and power control for connectivity enhancement in multi-hop I2V/V2V networks,” IEEE Transactions on Intelligent Transportation Systems, vol. 23, no. 8, pp. 10 322–10 332, 2022. [6] Z. Li, L. Xiang, X. Ge, G. Mao, and H.-C. Chao, “Latency and reliability of mmWave multi-hop V2V communications under relay selections,” IEEE Transactions on Vehicle Technology, vol. 69, no. 9, pp. 9807– 9821, 2020. [7] F. Li and Y. Wang, “Routing in vehicular ad hoc networks: A survey,” IEEE Vehicular Technology Magazine, vol. 2, no. 2, pp. 12–22, 2007.
[8] N. Sarma and S. Nandi, “Route stability based QoS routing in mobile ad hoc networks,” Wireless Personal Communications, vol. 54, no. 1, pp. 203–224, Mar. 2009. [9] A. Moussaoui and A. Boukeream, “A survey of routing protocols based on link-stability in mobile ad hoc networks,” Journal of Network and Computer Applications, vol. 47, pp. 1–10, 2015. [10] M. K. Marina and S. R. Das, “On-demand multipath distance vector routing in ad hoc networks,” in Proceedings of International Conference on Network Protocols (ICNP), Nov. 2001, pp. 14–23. [11] S. Biswas and R. Morris, “ExOR: opportunistic multihop routing for wireless networks,” in Proceedings of the ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM), 2005, pp. 133–144. [12] S. Chakrabarti and A. Mishra, “QoS issues in ad hoc wireless networks,” IEEE Communications Magazine, vol. 39, no. 2, pp. 142–148, 2001. [13] L. Hanzo and R. Tafazolli, “A survey of QoS routing solutions for mobile ad hoc networks,” IEEE Communications Surveys & Tutorials, vol. 9, no. 2, pp. 50–70, 2007. [14] A. Boukerche, B. Turgut, N. Aydin, M. Z. Ahmad, L. Bölöni, and D. Turgut, “Routing protocols in ad hoc networks: A survey,” Computer Networks, vol. 55, no. 13, pp. 3032–3080, 2011. [15] C. Lin, “On-demand QoS routing in multihop mobile networks,” in Proceedings of IEEE International Conference on Computer Communications (INFOCOM), 2001, pp. 1735–1744. [16] L. Chen and W. Heinzelman, “QoS-aware routing based on bandwidth estimation for mobile ad hoc networks,” IEEE Journal on Selected Areas in Communications, vol. 23, no. 3, pp. 561–572, 2005. [17] P. Basarkod and S. Manvi, “Mobility and QoS aware anycast routing in mobile ad hoc networks,” Computers & Electrical Engineering, vol. 48, pp. 86–99, 2015. [18] M. Bagaa, D. L. C. Dutra, T. Taleb, and K. Samdanis, “On SDN-driven network optimization and QoS aware routing using multiple paths,” IEEE Transactions on Wireless Communications, vol. 19, no. 7, pp. 4700–4714, 2020. [19] T.-N. Tran and B. An, “QoS multicast routing utilizing cross-layer design for IoT-enabled MANET in RISaided cell-free massive MIMO,” IEEE Internet of Things Journal, vol. 11, no. 7, pp. 11 876–11 893, 2024. [20] R. N. Raj, A. Nayak, and M. Sathish Kumar, “QoS-aware routing protocol for cognitive radio ad hoc networks,” Ad Hoc Networks, vol. 113, p. 102386, 2021. [21] Q. V. Khanh, V. A. Dang, Q. N. Minh, and D. C. Nguyen, “A QoS-adaptive routing scheme for UrbanMANETs,” IEEE Sensors Journal, vol. 25, no. 13, pp. 26 001–26 008, 2025. [22] C. E. Perkins, E. M. Belding-Royer, and S. R. Das, “Ad hoc on-demand distance vector (AODV) routing,” IETF, Tech. Rep. RFC 3561, 2003. [23] D. B. Johnson, D. A. Maltz, and Y.-C. Hu, “The dy-
19
namic source routing protocol (DSR) for mobile ad hoc networks for IPv4,” RFC 4728, Feb. 2007. [24] T. Clausen and P. Jacquet, “Optimized link state routing protocol (OLSR),” IETF, Tech. Rep. RFC 3626, 2003. [25] H. Saleet, R. Langar, K. Naik, R. Boutaba, A. Nayak, and N. Goel, “Intersection-based geographical routing protocol for VANETs: A proposal and analysis,” IEEE Transactions on Vehicular Technology, vol. 60, no. 9, pp. 4560–4574, 2011. [26] S. K. Dhurandher, M. S. Obaidat, D. Bhardwaj, and A. Garg, “GROOV: A geographic routing over VANETs and its performance evaluation,” in Preceedings of IEEE Global Communications Conference (GLOBECOM), 2012, pp. 1670–1675. [27] S. Boussoufa-Lahlah, F. Semchedine, and L. Bouallouche-Medjkoune, “Geographic routing protocols for vehicular ad hoc networks (VANETs): A survey,” Vehicular Communications, vol. 11, pp. 20–31, 2018. [28] R. Karimi and S. Shokrollahi, “PGRP: Predictive geographic routing protocol for vanets,” Computer Networks, vol. 141, pp. 67–81, 2018. [29] B. Karp and H. T. Kung, “GPSR: greedy perimeter stateless routing for wireless networks,” in Proceedings of the ACM International Conference on Mobile Computing and Networking (MobiCom), 2000, pp. 243–254. [30] S. Shokrollahi and M. Dehghan, “TGRV: A trust-based geographic routing protocol for VANETs,” Ad Hoc Networks, vol. 140, p. 103062, 2023. [31] K. L. K. Sudheera, M. Ma, and P. H. J. Chong, “Link stability based optimized routing framework for software defined vehicular networks,” IEEE Transactions on Vehicular Technology, vol. 68, no. 3, pp. 2934–2945, 2019. [32] J. Zhang, L. Zhang, D. gan Zhang, T. Zhang, S. Wang, and C. hui Zou, “New routing method based on sticky bacteria algorithm and link stability for VANET,” Ad Hoc Networks, vol. 166, p. 103682, 2025. [33] M. Laroui, A. Sellami, B. Nour, H. Moungla, H. Afifi, and S. B. Hacene, “Driving path stability in VANETs,” in Proceedings of IEEE Global Communications Conference (GLOBECOM), 2018, pp. 1–6. [34] A. H. Abbas, A. J. Ahmed, S. A. Rashid, N. F. Abdulsattar, M. H. Hassan, M. A. Jubair, and M. I. Habelalmateen, “Predictive hybrid routing with multi objective optimization model for opportunistic routing for VANET,” in Proceedings of International Conference on Engineering Technology and its Applications (IICETA), 2022, pp. 470–476. [35] A. Vahdat and D. Becker, “Epidemic routing for partially connected ad hoc networks,” Duke University, Tech. Rep., 2000. [36] S. Chachulski, M. Jennings, S. Katti, and D. Katabi, “MORE: A network coding approach to opportunistic routing,” Tech. Rep. MIT-CSAIL-TR-2006-049, Jun. 2006. [37] N. Chakchouk, “A survey on opportunistic routing in wireless communication networks,” IEEE Communications Surveys & Tutorials, vol. 17, no. 4, pp. 2214–2241,
2015. [38] S. More and U. L. Naik, “Optimization driven multipath routing for the video transmission in the VANET,” in Proceedings of IEEE Global Conference on Wireless Computing and Networking (GCWCN), 2018, pp. 6–10. [39] S. More and U. Naik, “Optimal multipath routing for video transmission in VANETs,” Wireless Personal Communications, vol. 116, no. 1, pp. 805–827, Aug. 2020. [40] C. Zhao, Q. Zeng, Y. Tang, and B. Yang, “Multi-path routing protocol for the video service in UAV-assisted VANETs,” in Proceedings of IEEE Vehicular Technology Conference (VTC), 2021, pp. 1–5. [41] S. Boucheron, G. Lugosi, and P. Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013. [42] P. A. López, M. Behrisch, L. Bieker-Walz, J. Erdmann, Y.-P. Flötteröd, R. Hilbrich, L. Lücken, J. Rummel, P. Wagner, and E. Wießner, “Microscopic traffic simulation using SUMO,” in Proceedings of the 21st IEEE International Conference on Intelligent Transportation Systems (ITSC). IEEE, 2018. [43] G. F. Riley and T. R. Henderson, The ns-3 Network Simulator, K. Wehrle, M. Güneş, and J. Gross, Eds. Berlin, Heidelberg: Springer, 2010. [44] IEEE, “IEEE Std 802.11p-2010: IEEE standard for information technology—telecommunications and information exchange between systems—local and metropolitan area networks—specific requirements—part 11: Wireless LAN medium access control (MAC) and physical layer (PHY) specifications amendment 6: Wireless access in vehicular environments,” Tech. Rep., 2010.