In wireless networks with stochastic link characteristics, where link quality is subject to random variations, achieving deadlines becomes a complex task. A growing number of works have proposed paradigms and techniques to address these challenges and achieve deadlines in such conditions [7].

In scenarios where the topology of the network and the links between nodes are subject to high dynamics or the routing layer has limited information about the network, approaches such as geographic routing (GR) can be particularly useful. Those conditions can be found in mobile ad hoc networks and wireless sensor networks (WSNs). GR leverages the geographic locations of nodes to make routing decisions, eliminating the requirement for explicit knowledge of the network topology. For deadline-aware traffic under this paradigm, velocities, understood as the speed or rate of movement of packets, are commonly utilized as a variable to support timely delivery. An early key contribution in this respect is the SPEED protocol [8], which proposes a GR approach with soft real-time guarantees and congestion avoidance for WSNs. Several extensions of SPEED have been proposed, including energy awareness [9,10] and packet prioritization combined with probabilistic multi-path forwarding [11]. Also, a combination of transmission power control and GR for improved energy efficiency was considered in [12]. In [13], the real-time routing problem is transformed into a 0/1 integer linear programming problem to effectively balance energy efficiency and reliability for real-time applications.

Predictive models can be employed to anticipate and adapt to future link variations. Reinforcement learning (RL) is a prevailing machine learning technique in the literature for routing. Unlike other machine learning techniques, it does not require large data sets [14]. RL provides a high level of adaptability, which allows the protocols to work in dynamically changing networks. Furthermore, RL approaches have been used to optimize for multiple criteria. For instance, Jafarzadeh et al. [15] proposed an energy-aware quality of service (QoS) routing protocol. In another study by Lin et al. [16], a joint optimization approach for routing and transmission power in dynamic environments was proposed, specifically targeting delay-sensitive applications.

Furthermore, various other techniques have been employed to enhance the performance of time-critical networking. For example, in [17], the authors proposed a routing mechanism for real-time communication in WSNs based on composite potential fields. The method, inspired by physics, models nodes as charged particles, and communication paths are determined by attractive and repulsive forces. The metric employed for decision making is the hop count, reflecting the number of intermediate nodes. Also, various cluster-based routing schemes have been proposed [18]. Cluster-based routing can be beneficial for time-critical applications as it optimizes communication by organizing nodes into clusters, reducing latency, enhancing reliability, and facilitating efficient coordination for timely data transmission. A cluster-based protocol for real-time traffic in industrial wireless sensor networks was presented in [19]. The protocol focuses on energy efficiency and reduced end-to-end delay. Real-time updates of routing information, focusing on geographical position, hop counts, and residual energy metrics, enhance overall system performance and scalability. Another cluster-based protocol, detailed in [20], caters to delay-sensitive, bandwidth-intensive, time-critical, and QoS-aware applications. It employs dedicated paths for real-time traffic, calculated using a metric that incorporates the initial energy, expected transmission count, inverse expected transmission count, and minimum loss.

Combinations of multiple approaches have also been proposed. For instance, opportunistic routing (OR) has been integrated with RL for live video streaming over multi-hop wireless networks [21]. Techniques from GR and OR have been combined in a QoS-aware scheme for wireless sensor networks [22]. Tang et al. [21] introduced a distributed RL-based OR scheme for video streaming, where a novel metric was proposed to estimate end-to-end (E2E) delays.

All of the above approaches focus on individual metrics, predominantly velocity or hop count, to ensure the timely delivery of data. However, the importance of modeling link latencies directly as probability distributions instead of using individual metrics has been highlighted in works such as [4,23].

Stochastic networks are characterized by aspects with uncertain behavior, and the parameters or conditions that affect network operations are subject to variability or randomness. Several works have considered deadline-aware routing for such networks. The reliable shortest path problem, introduced by Frank in [24], considers the joint latency of individual paths to select the optimal path for a specific deadline. While [24] is a contribution from operations research, the reliable shortest path problem has also received some attention in the domain of wireless multi-hop networks in works such as [4,23]. In contrast to the reliable shortest path problem, which focuses on predefined paths, the stochastic on-time arrival problem [25] allows for optimal decisions made on the fly. The stochastic on-time arrival problem has received little attention from researchers studying communication networks. It has been considered to provision soft QoS guarantees in mobile ad hoc multimedia networks [26] or for accomplishing timely data delivery in a practical bus network [27].

Routing algebra [28] can be used as a holistic mathematical modeling approach for designing and analyzing routing metrics. The key property of the algebra, isotonicity, is necessary and sufficient to prove that the routing produces loop-free paths. In [29], the authors extended the algebra to OR. Routing algebra can also be applied for combined metrics, such as a combination of a link quality indicator and the remaining energy [30]. In contrast, the optimal paths found by the atochastic on-time arrival problem may include loops [25]. This violates isotonicity, and therefore routing algebra is not sufficient to describe the stochastic on-time arrival problem.