Submitted Successfully!
To reward your contribution, here is a gift for you: A free trial for our video production service.
Thank you for your contribution! You can also upload a video entry or images related to this topic.
Version Summary Created by Modification Content Size Created at Operation
1
Benjamin Becker
 -- 1362 2024-01-29 10:11:31 |
2 layout
Camila Xu
 Meta information modification 1362 2024-01-30 01:09:34 |

Video Upload Options

Do you have a full video?
Send video materials Upload full video

Confirm

Are you sure to Delete?
Yes No
Cite
If you have any further questions, please contact Encyclopedia Editorial Office.
Becker, B.; Oberli, C.; Meuser, T.; Steinmetz, R. The Probability of Achieving Deadlines in Communication Networks. Encyclopedia. Available online: https://encyclopedia.pub/entry/54477 (accessed on 19 May 2024).
Becker B, Oberli C, Meuser T, Steinmetz R. The Probability of Achieving Deadlines in Communication Networks. Encyclopedia. Available at: https://encyclopedia.pub/entry/54477. Accessed May 19, 2024.
Becker, Benjamin, Christian Oberli, Tobias Meuser, Ralf Steinmetz. "The Probability of Achieving Deadlines in Communication Networks" Encyclopedia, https://encyclopedia.pub/entry/54477 (accessed May 19, 2024).
Becker, B., Oberli, C., Meuser, T., & Steinmetz, R. (2024, January 29). The Probability of Achieving Deadlines in Communication Networks. In Encyclopedia. https://encyclopedia.pub/entry/54477
Becker, Benjamin, et al. "The Probability of Achieving Deadlines in Communication Networks." Encyclopedia. Web. 29 January, 2024.
The Probability of Achieving Deadlines in Communication Networks
Edit
This entry is adapted from the peer-reviewed paper 10.3390/jsan13010009

End-to-end (E2E) delay, which measures the time taken for packets to travel from a source node to a destination node in communication networks, is a widely used performance metric. It is frequently defined as the average delay of packets along a given path.

ad hoc networks deadline achievement probability delay-aware routing

1. Introduction

End-to-end (E2E) delay, which measures the time taken for packets to travel from a source node to a destination node in communication networks, is a widely used performance metric. It is frequently defined as the average delay of packets along a given path. This average delay is typically calculated as the sum of the average delays of each individual link along the path. However, it is crucial to point out that link delays possess inherent stochastic characteristics, leading to stochastic path delays and E2E delays within the network [1]. Consequently, link and path delays may be modeled by probability density functions (PDFs). An example is shown in Figure 1, which illustrates the PDFs of the delay of two paths 𝑃1 and 𝑃2. The expected E2E delay of path 𝑃2 (dashed orange line) is larger than the expected E2E delay of path 𝑃1 (dashed blue line).
Some existing and emerging wireless network communication applications in fields such as critical care and industrial processes require timely data delivery in order to fulfill their purpose. In these contexts, lost packets or missed deadlines can result in severe consequences, especially in industrial control applications [2]. Therefore, it is crucial to meet deadlines with a certain level of reliability. Analytic tools play a significant role in this context, as they can provide operators with key information about the supported delay and reliability bounds [3], helping operators to make informed decisions to fulfill the application’s requirements.
Consider thus a time-critical networking application requiring data from a source node to arrive at a destination node by a given deadline. In Figure 1, the deadline is shown by the dashed black line. The shaded areas under the curves to the right of the deadline indicate the probability of missing the deadline for each path. Even though path 𝑃1 has a smaller expected delay than path 𝑃2, the probability of missing the deadline is higher along path 𝑃1. This example supports the idea that analyzing and designing time-critical network communications by considering the probability density functions of E2E delays rather than relying solely on statistical measures, such as expected delay, should be a beneficial approach.
Jsan 13 00009 g001
Figure 1. Two probability density functions of the E2E communication delay along two paths are shown. They differ in their expected delays (dashed lines) and their respective probabilities of missing a deadline (shaded area). Although the expected delay of path 𝑃1 is lower than that of path 𝑃2, the deadline achievement probability of path 𝑃2 is higher. Thus, minimizing the expected delay does not guarantee a maximized deadline achievement probability. Recreated from [4].

2. On Maximizing the Probability of Achieving Deadlines in Communication Networks

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 [5].
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 [6], 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 [7][8] and packet prioritization combined with probabilistic multi-path forwarding [9]. Also, a combination of transmission power control and GR for improved energy efficiency was considered in [10]. In [11], 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 [12]. 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. [13] proposed an energy-aware quality of service (QoS) routing protocol. In another study by Lin et al. [14], 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 [15], 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 [16]. 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 [17]. 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 [18], 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 [19]. Techniques from GR and OR have been combined in a QoS-aware scheme for wireless sensor networks [20]. Tang et al. [19] 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][21].
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 [22], considers the joint latency of individual paths to select the optimal path for a specific deadline. While [22] 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][21]. In contrast to the reliable shortest path problem, which focuses on predefined paths, the stochastic on-time arrival problem [23] 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 [24] or for accomplishing timely data delivery in a practical bus network [25].
Routing algebra [26] 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 [27], 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 [28]. In contrast, the optimal paths found by the atochastic on-time arrival problem may include loops [23]. This violates isotonicity, and therefore routing algebra is not sufficient to describe the stochastic on-time arrival problem.

References

  1. Hou, I.H.; Kumar, P.R. Packets with Deadlines: A Framework for Real-Time Wireless Networks; Springer Nature: Berlin/Heidelberg, Germany, 2022.
  2. Dobslaw, F.; Zhang, T.; Gidlund, M. End-to-end reliability-aware scheduling for wireless sensor networks. IEEE Trans. Ind. Inform. 2014, 12, 758–767.
  3. Suriyachai, P.; Roedig, U.; Scott, A. A survey of MAC protocols for mission-critical applications in wireless sensor networks. IEEE Commun. Surv. Tutor. 2011, 14, 240–264.
  4. Jang, B.-H.; Son, S.; Park, K. Deadline-aware routing with probabilistic delay guarantee in cyber-physical systems. In Proceedings of the 2017 International Conference on Information Networking (ICOIN), Da Nang, Vietnam, 11–13 January 2017; pp. 51–53.
  5. Pradittasnee, L. Providing Real-Time and Reliable Transmission in Routing Protocols for Large-Scale Sensor Networks. In Handbook of Real-Time Computing; Springer: Berlin/Heidelberg, Germany, 2022; pp. 913–934.
  6. He, T.; Stankovic, J.A.; Lu, C.; Abdelzaher, T. SPEED: A stateless protocol for real-time communication in sensor networks. In Proceedings of the 23rd International Conference on Distributed Computing Systems, Providence, RI, USA, 19–22 May 2003; pp. 46–55.
  7. Kordafshari, M.S.; Pourkabirian, A.; Faez, K.; Rahimabadi, A.M. Energy-efficient speed routing protocol for wireless sensor networks. In Proceedings of the 2009 Fifth Advanced International Conference on Telecommunications, Venice, Italy, 24–28 May 2009; pp. 267–271.
  8. Memon, I.; Memon, N.; Noureen, F. Modified SPEED protocol for wireless sensor networks. QUAID-E Univ. Res. J. Eng. Sci. Technol. 2014, 13, 29–33.
  9. Felemban, E.; Lee, C.G.; Ekici, E. MMSPEED: Multipath Multi-SPEED protocol for QoS guarantee of reliability and. Timeliness in wireless sensor networks. IEEE Trans. Mob. Comput. 2006, 5, 738–754.
  10. Rachamalla, S.; Kancherla, A.S. A two-hop based adaptive routing protocol for real-time wireless sensor networks. Springerplus 2016, 5, 1–12.
  11. El-Fouly, F.H.; Ramadan, R.A. Real-time energy-efficient reliable traffic aware routing for industrial wireless sensor networks. IEEE Access 2020, 8, 58130–58145.
  12. Mammeri, Z. Reinforcement learning based routing in networks: Review and classification of approaches. IEEE Access 2019, 7, 55916–55950.
  13. Jafarzadeh, S.Z.; Moghaddam, M.H.Y. Design of energy-aware QoS routing protocol in wireless sensor networks using reinforcement learning. In Proceedings of the 2014 IEEE 27th Canadian Conference on Electrical and Computer Engineering (CCECE), Toronto, ON, Canada, 4–7 May 2014; pp. 1–5.
  14. Lin, Z.; van der Schaar, M. Autonomic and distributed joint routing and power control for delay-sensitive applications in multi-hop wireless networks. IEEE Trans. Wirel. Commun. 2010, 10, 102–113.
  15. Xu, Y.; Ren, F.; He, T.; Lin, C.; Chen, C.; Das, S.K. Real-time routing in wireless sensor networks: A potential field approach. ACM Trans. Sens. Netw. TOSN 2013, 9, 1–24.
  16. Fanian, F.; Rafsanjani, M.K. Cluster-based routing protocols in wireless sensor networks: A survey based on methodology. J. Netw. Comput. Appl. 2019, 142, 111–142.
  17. Long, N.B.; Tran-Dang, H.; Kim, D.S. Energy-aware real-time routing for large-scale industrial internet of things. IEEE Internet Things J. 2018, 5, 2190–2199.
  18. Amjad, M.; Afzal, M.K.; Umer, T.; Kim, B.S. QoS-aware and heterogeneously clustered routing protocol for wireless sensor networks. IEEE Access 2017, 5, 10250–10262.
  19. Tang, K.; Li, C.; Xiong, H.; Zou, J.; Frossard, P. Reinforcement learning-based opportunistic routing for live video streaming over multi-hop wireless networks. In Proceedings of the 2017 IEEE 19th International Workshop on Multimedia Signal Processing (MMSP), Luton, UK, 16–18 October 2017; pp. 1–6.
  20. Cheng, L.; Niu, J.; Cao, J.; Das, S.K.; Gu, Y. QoS aware geographic opportunistic routing in wireless sensor networks. IEEE Trans. Parallel Distrib. Syst. 2013, 25, 1864–1875.
  21. GΓΌrsu, H.M.; Kellerer, W. Deadline-aware wireless sensor network routing: The JLAT metric. In Proceedings of the 2017 IEEE International Conference on Communications Workshops (ICC Workshops), Paris, France, 21–25 May 2017; pp. 612–617.
  22. Frank, H. Shortest paths in probabilistic graphs. Oper. Res. 1969, 17, 583–599.
  23. Fan, Y.; Kalaba, R.E.; Moore, J.E. Arriving on time. J. Optim. Theory Appl. 2005, 127, 497–513.
  24. Huang, L.; Pan, F. Optimal route discovery for soft QOS provisioning in mobile ad hoc multimedia networks. In Proceedings of the Multimedia Systems and Applications X. SPIE, Boston, MA, USA, 10–11 September 2007; Volume 6777, pp. 29–38.
  25. Acer, U.G.; Giaccone, P.; Hay, D.; Neglia, G.; Tarapiah, S. Timely data delivery in a realistic bus network. IEEE Trans. Veh. Technol. 2011, 61, 1251–1265.
  26. Sobrinho, J.L. Algebra and algorithms for QoS path computation and hop-by-hop routing in the Internet. In Proceedings of the IEEE INFOCOM 2001: Conference on Computer Communications: Twentieth Annual Joint Conference of the IEEE Computer and Communications Society, Anchorage, AK, USA, 22–26 April 2001; Volume 2, pp. 727–735.
  27. Lu, M.; Wu, J. Opportunistic routing algebra and its applications. In Proceedings of the IEEE INFOCOM 2009, Rio de Janeiro, Brazil, 19–25 April 2009; pp. 2374–2382.
  28. Sobral, J.V.; Rodrigues, J.J.; Saleem, K.; De Paz, J.F.; Corchado, J.M. A composite routing metric for wireless sensor networks in AAL-IoT. In Proceedings of the 2016 9th IFIP Wireless and Mobile Networking Conference (WMNC), Colmar, France, 11–13 July 2016; pp. 168–173.
More
Β© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license; additional terms may apply. By using this site, you agree to the Terms and Conditions and Privacy Policy.
Upload a video for this entry
Information
Subjects: Telecommunications
Contributors MDPI registered users' name will be linked to their SciProfiles pages. To register with us, please refer to https://encyclopedia.pub/register :
Benjamin Becker
,
Christian Oberli
,
Tobias Meuser
,
Ralf Steinmetz
View Times: 98
Revisions: 2 times (View History)
Update Date: 30 Jan 2024
Table of Contents
    1000/1000
    Hot Most Recent
    Feedback