Delay bounded routing with the maximum belief degree for dynamic uncertain networks

doi:10.23919/JSEE.2024.000027

Journal of Systems Engineering and Electronics ›› 2025, Vol. 36 ›› Issue (1): 127-138.doi: 10.23919/JSEE.2024.000027

• SYSTEMS ENGINEERING • Previous Articles

Delay bounded routing with the maximum belief degree for dynamic uncertain networks

Ji MA¹(), Rui KANG¹^,²(), Ruiying LI¹^,²^,*(), Qingyuan ZHANG²^,³(), Liang LIU⁴(), Xuewang WANG⁴()

¹ School of Reliability and Systems Engineering, Beihang University, Beijing 100191, China
² Science and Technology on Reliability and Environmental Engineering Laboratory, Beijing 100191, China
³ International Innovation Institute, Beihang University, Hangzhou 311115, China
⁴ Institute of Telecommunication and Navigation Satellites, China Academy of Space Technology, Beijing 100094, China

Received:2022-10-21 Online:2025-02-18 Published:2025-03-18
Contact: Ruiying LI E-mail:maji@buaa.edu.cn;kangrui@buaa.edu.cn;liruiying@buaa.edu.cn;zhangqingyuan@buaa.edu.cn;liuliang1945@buaa.edu.cn;wxw_air@126.com
About author:
MA Ji was born in 1992. He received his bachelor’s and master’s degrees in mechanical engineering from Beijing Jiaotong University and Beihang University in 2013 and 2016, respectively. He is a Ph.D. candidate student on systems engineering at School of Reliability and Systems Engineering, Beihang University. His research interests are resilience, network reliability, and network optimization methods. E-mail: maji@buaa.edu.cn

KANG Rui was born in 1966. He received his bachelor’s and master’s degrees in electrical engineering from Beihang University in 1987 and 1990, respectively. He is a distinguished professor in School of Reliability and Systems Engineering, Beihang University, Beijing, China. His main research interests include reliability, resilience for complex system and modeling epistemic uncertainty in reliability and maintainability. E-mail: kangrui@buaa.edu.cn

LI Ruiying was born in 1982. She received her Ph.D. degree in systems engineering from Beihang University, China, in 2009. From 2013 to 2014, she was a visiting scholar with the Department of Systems and Industrial Engineering, University of Arizona, USA. She has authored fifty scholarly papers covering various areas of network reliability and system resilience. Her main research interests include network resilience and reliablity. E-mail: liruiying@buaa.edu.cn

ZHANG Qingyuan was born in 1993. He received his Ph.D. degree in systems engineering from Beihang University, Beijing, China, in 2020. In 2019, he was a visiting Ph.D. student in civil engineering at the University of British Columbia. From 2020 to 2023, he held a postdoctoral position at the School of Aeronautic Science and Engineering, Beihang University. He is currently an associate professor with the International Innovation Institute, Beihang University. His research interests include belief reliability theory, reliability modeling, uncertainty quantification method in engineering, and the reliability design method. E-mail: zhangqingyuan@buaa.edu.cn

LIU Liang was born in 1986. He received his bachler’s degree and doctor’s degree of electronical engineer from Beihang University in 2009 and 2017, respectively. Now, he is a supreme engineer in China Academy of Space Technology. His research interests are satellite communication and space network. E-mail: liuliang1945@buaa.edu.cn

WANG Xuewang was born in 1984. She received her Ph.D. degree in systems engineering from Beihang University, China, in 2012. She is now a senior engineering in the Institute of Telecommunication and Navigation Satellites, China Academy of Space Technology. Her research interests are satellite reliability and constellation reliability. E-mail: wxw_air@126.com
Supported by:
This work was supported by the National Natural Science Foundation of China (61773044; 62073009) and the National key Laboratory of Science and Technology on Reliability and Environmental Engineering (WDZC2019601A301).

Abstract

Abstract:

Delay aware routing is now widely used to provide efficient network transmission. However, for newly developing or developed mobile communication networks (MCN), only limited delay data can be obtained. In such a network, the delay is with epistemic uncertainty, which makes the traditional routing scheme based on deterministic theory or probability theory not applicable. Motivated by this problem, the MCN with epistemic uncertainty is first summarized as a dynamic uncertain network based on uncertainty theory, which is widely applied to model epistemic uncertainties. Then by modeling the uncertain end-to-end delay, a new delay bounded routing scheme is proposed to find the path with the maximum belief degree that satisfies the delay threshold for the dynamic uncertain network. Finally, a low-Earth-orbit satellite communication network (LEO-SCN) is used as a case to verify the effectiveness of our routing scheme. It is first modeled as a dynamic uncertain network, and then the delay bounded paths with the maximum belief degree are computed and compared under different delay thresholds.

Key words: dynamic uncertain network, uncertainty theory, epistemic uncertainty, delay bounded routing, maximum belief degree

Ji MA, Rui KANG, Ruiying LI, Qingyuan ZHANG, Liang LIU, Xuewang WANG. Delay bounded routing with the maximum belief degree for dynamic uncertain networks[J]. Journal of Systems Engineering and Electronics, 2025, 36(1): 127-138.

Figures/Tables 13

Fig 1

Table 1

Table 2

Table 3

Fig 2

Fig 3

Table 4

Fig 4

Table 5

Link length between nodes at time ta km"

Edge	Length	Edge	Length	Edge	Length	Edge	Length	Edge	Length	Edge	Length
$ {e_{1,2}} $	7 678	$ {e_{1,7}} $	6 374	$ {e}_{2,3} $	7 678	$ {e_{2,8}} $	4 618	$ {e_{3,4}} $	7 678	$ {e_{3,9}} $	3 570
$ {e_{4,5}} $	7 678	$ {e_{4,10}} $	6 374	$ {e_{5,6}} $	7 678	$ {e_{5,11}} $	4 618	$ {e_{6,1}} $	7 678	$ {e_{6,12}} $	3 570
$ {e_{7,8}} $	7 678	$ {e_{7,13}} $	6 438	$ {e_{8,9}} $	7 678	$ {e_{8,14}} $	4 166	$ {e_{9,10}} $	7 678	$ {e_{9,15}} $	3 987
$ {e_{10,11}} $	7 678	$ {e_{10,16}} $	6 438	$ {e_{11,12}} $	7 678	$ {e_{11,17}} $	4 166	$ {e_{12,7}} $	7 678	$ {e_{12,8}} $	3 987
$ {e_{13,14}} $	7 678	$ {e_{13,19}} $	6 411	$ {e_{14,15}} $	7 678	$ {e_{14,20}} $	3 732	$ {e_{15,16}} $	7 678	$ {e_{15,21}} $	4 463
$ {e_{16,17}} $	7 678	$ {e_{16,22}} $	6 411	$ {e_{17,18}} $	7 678	$ {e_{17,23}} $	3 732	$ {e_{18,13}} $	7 678	$ {e_{18,24}} $	4 463
$ {e_{19,20}} $	7 678	$ {e_{19,25}} $	6 294	$ {e_{20,21}} $	7 678	$ {e_{20,26}} $	4 454	$ {e_{21,22}} $	7 678	$ {e_{21,27}} $	4 883
$ {e_{22,23}} $	7 678	$ {e_{22,28}} $	6 294	$ {e_{23,24}} $	7 678	$ {e_{23,29}} $	4 454	$ {e_{24,19}} $	7 678	$ {e_{24,30}} $	4 883
$ {e_{25,26}} $	7 678	$ {e_{25,31}} $	6 090	$ {e_{26,27}} $	7 678	$ {e_{26,32}} $	3 079	$ {e_{27,28}} $	7 678	$ {e_{27,33}} $	5 302
$ {e_{28,29}} $	7 678	$ {e_{28,34}} $	6 090	$ {e_{29,30}} $	7 678	$ {e_{29,35}} $	3 079	$ {e_{30,25}} $	7 678	$ {e_{30,36}} $	5 302
$ {e_{31,32}} $	7 678	$ {e_{31,37}} $	5 809	$ {e_{32,33}} $	7 678	$ {e_{32,38}} $	2 955	$ {e_{33,34}} $	7 678	$ {e_{33,39}} $	5 675
$ {e_{34,35}} $	7 678	$ {e_{34,40}} $	5 809	$ {e_{35,36}} $	7 678	$ {e_{35,41}} $	2 955	$ {e_{36,37}} $	7 678	$ {e_{36,42}} $	5 675
$ {e_{37,38}} $	7 678	$ {e_{37,43}} $	5 459	$ {e_{38,39}} $	7 678	$ {e_{38,44}} $	3 009	$ {e_{39,40}} $	7 678	$ {e_{39,45}} $	5 986
$ {e_{40,41}} $	7 678	$ {e_{40,46}} $	5 459	$ {e_{41,42}} $	7 678	$ {e_{41,47}} $	3 009	$ {e_{42,37}} $	7 678	$ {e_{42,48}} $	5 986
$ {e_{43,44}} $	7 678	$ {e_{43,1}} $	7 255	$ {e_{44,45}} $	7 678	$ {e_{44,2}} $	4 818	$ {e_{45,46}} $	7 678	$ {e_{45,3}} $	6 022
$ {e_{46,47}} $	7 678	$ {e_{46,4}} $	7 255	$ {e_{47,48}} $	7 678	$ {e_{47,5}} $	4 818	$ {e_{48,43}} $	7 678	$ {e_{48,6}} $	6 022
$ {e_{2,0}} $	3 438	$ {e_{5,50}} $	2 198	$ {e_{10,52}} $	3 184	$ {e_{11,49}} $	3 603	$ {e_{15,51}} $	3 425	$ {e_{16,52}} $	2 356
$ {e_{21,51}} $	2 137	$ {e_{26,50}} $	2 632	$ {e_{27,52}} $	1 698

Table 5

Table 6

Fig 5

Table 7

Table 8

References 34

1	ZHU X M, JIANG C X Creating efficient integrated satellite-terrestrial networks in the 6G era. IEEE Wireless Communications, 2022, 29 (4): 154- 160. doi: 10.1109/MWC.011.2100643
2	KAMRUZZAMAN M, SARKAR N I, GUTIERREZ J A dynamic algorithm for interference management in D2D-enabled heterogeneous cellular networks: modeling and analysis. Sensors, 2022, 22 (3): 1063. doi: 10.3390/s22031063
3	VATAMBETI R, SANSHI S, KRISHNA D P An efficient clustering approach for optimized path selection and route maintenance in mobile ad hoc networks. Journal of Ambient Intelligence and Humanized Computing, 2021, 14 (1): 305- 309.
4	CHEN Y J, LIAO K M, CHEN Y F End-to-end delay analysis in aerial-terrestrial heterogeneous networks. IEEE Trans. on Vehicular Technology, 2021, 70 (2): 1793- 1806. doi: 10.1109/TVT.2021.3052250
5	WERNER M A dynamic routing concept for ATM-based satellite personal communication networks. IEEE Journal on Selected Areas in Communications, 1997, 15 (8): 1636- 1648. doi: 10.1109/49.634801
6	XU M M, ZHANG G X, LIANG X P, et al Energy-efficient data transmission in mobility-aware wireless networks. Wireless Communications and Mobile Computing, 2022, 2022, 8683854.
7	EKICI E, AKYILDIZ I F, BENDER M D A distributed routing algorithm for datagram traffic in LEO satellite networks. IEEE/ACM Trans. on Networking, 2001, 9 (2): 137- 147. doi: 10.1109/90.917071
8	HU M L, YANG R H, HU Y, et al QoS-aware software defined multicast in LEO satellite networks. IEEE Trans. on Aerospace and Electronic Systems, 2022, 58 (6): 5307- 5317. doi: 10.1109/TAES.2022.3169732
9	GUO Z, YAN Z A weighted semi-distributed routing algorithm for LEO satellite networks. Journal of Network and Computer Applications, 2015, 58, 1- 11. doi: 10.1016/j.jnca.2015.08.015
10	WANG P, CHEN B C, GU X M, et al Multi-constraint quality of service routing algorithm for dynamic topology networks. Journal of Systems Engineering and Electronics, 2008, 19 (1): 58- 64. doi: 10.1016/S1004-4132(08)60046-8
11	SHI Z, ZHU J, WEI H N SARSA-based delay-aware route selection for SDN-enabled wireless-PLC power distribution IoT. Alexandria Engineering Journal, 2022, 61 (8): 5795- 5803. doi: 10.1016/j.aej.2021.11.029
12	GENG S Y, LIU S F, FANG Z G, et al An optimal delay routing algorithm considering delay variation in the LEO satellite communication network. Computer Networks, 2020, 173, 107166. doi: 10.1016/j.comnet.2020.107166
13	JONES E P C, LI L, SCHMIDTKE J K, et al Practical routing in delay-tolerant networks. IEEE Trans. on Mobile Computing, 2007, 6 (8): 943- 959. doi: 10.1109/TMC.2007.1016
14	ZHANG C W, HEI X J, LIU W, et al. On improving dynamic stochastic routing algorithms in overlay networks. Proc. of the IEEE International Conference on Networks, 2012: 447−452.
15	SIDERA A, TOUMPIS S Wireless mobile DTN routing with the extended minimum estimated expected delay protocol. Ad Hoc Networks, 2016, 42, 47- 60. doi: 10.1016/j.adhoc.2016.01.006
16	BHUVANESWARI M, PARAMASIVAN B, KANDASAMY A Stochastic dynamic programming model for optimal resource allocation in vehicular ad hoc networks. Sadhana, 2018, 43 (4): 1- 8.
17	BORAH S J, DHURANDHER S K, WOUNGANG I, et al A multi-objectives based technique for optimized routing in opportunistic networks. Journal of Ambient Intelligence and Humanized Computing, 2018, 9 (3): 655- 666. doi: 10.1007/s12652-017-0462-z
18	JUNG Y, JO H, CHOO J, et al Statistical model calibration and design optimization under aleatory and epistemic uncertainty. Reliability Engineering & System Safety, 2022, 222, 108428.
19	MA J, KANG R, LI R Y, et al Uncertainty theory-based resilience analysis for LEO satellite communication systems. Symmetry, 2022, 14 (8): 1568. doi: 10.3390/sym14081568
20	ZENG Y N, DUAN R X, FENG T, et al. A fault diagnostic system based on Petri nets and gray relational analysis for train-ground wireless communication systems. Proceedings of the Institution of Mechanical Engineers, Part O: Journal of Risk and Reliability, 2021, 235(6): 1102−1117.
21	LIU B D. Uncertainty theory. Berlin: Springer-Verlag, 2007.
22	LIU B D. Uncertainty theory: a branch of mathematics for modeling human uncertainty. Berlin: Springer-Verlag, 2010.
23	GAO Y Shortest path problem with uncertain arc lengths. Computers and Mathematics with Applications, 2011, 62 (6): 2591- 2600. doi: 10.1016/j.camwa.2011.07.058
24	HAN S W, PENG Z X, WANG S Q The maximum flow problem of uncertain network. Information Sciences, 2014, 265, 167- 175. doi: 10.1016/j.ins.2013.11.029
25	ZURAWSKI R. The industrial communication technology handbook. Florida: CRC Press, 2005.
26	LI R Y, LI M N, LIAO H T, et al An efficient method for evaluating the end-to-end transmission time reliability of a switched Ethernet. Journal of Network and Computer Applications, 2017, 88, 124- 133. doi: 10.1016/j.jnca.2017.01.038
27	PAPAGIANNAKI K Long-term forecasting of internet backbone traffic. IEEE Trans. on Neural Networks, 2005, 16 (5): 1110- 1124. doi: 10.1109/TNN.2005.853437
28	MINH Q T, KOTO H, KITAHARA T, et al. Separation of background and foreground traffic based on periodicity analysis. Proc. of IEEE Global Communications Conference, 2015. DOI: 10.1109/GLOCOM.2015.7417076.
29	LU Y, SUN F C, ZHAO Y J Virtual topology for LEO satellite networks based on earth-fixed footprint mode. IEEE Communications Letters, 2013, 17 (2): 357- 360. doi: 10.1109/LCOMM.2013.011113.122635
30	IPPOLITO L J. Satellite communications systems engineering. New York: John WILEY & Sons, 2017.
31	ZHANG S J, WANG P, WAN Y, et al V/Ka-band LEO high-throughput satellite and integrated satellite-terrestrial network experiment system: first two years flight results. Acta Astronautica, 2022, 201, 533- 553. doi: 10.1016/j.actaastro.2022.09.028
32	CRUZ-SANCHEZ H, FRANCK L, BEYLOT A L Routing metrics for store and forward satellite constellations. IET Communications, 2010, 4 (13): 1563- 1572. doi: 10.1049/iet-com.2009.0460
33	ZU T P, KANG R, WEN M L Graduation formula: a new method to construct belief reliability distribution under epistemic uncertainty. Journal of Systems Engineering and Electronics, 2020, 31 (3): 626- 633. doi: 10.23919/JSEE.2020.000038
34	FLANNIGAN L, YOELL L, XU C. Mid-wave and long-wave infrared transmitters and detectors for optical satellite communications-a review. Journal of Optics, 2022, 24(4): 043002.

Edge	Delay/ms
$ {{{e}}_{1,2}} $	$ \mathcal{Z}\left( {7,8,12} \right) $
$ {{{e}}_{1,3}} $	$ \mathcal{Z}\left( {8,9,12} \right) $
$ {{{e}}_{2,3}} $	$ \mathcal{Z}\left( {3,4,6} \right) $
$ {{{e}}_{2,4}} $	$ \mathcal{Z}\left( {10,11,17} \right) $
$ {{{e}}_{3,4}} $	$ \mathcal{Z}\left( {11,12,14} \right) $

$ \alpha $	$ \varPhi _{1,2}^{ - 1}(\alpha )/\text{ms} $	$ \varPhi _{1,3}^{ - 1}(\alpha )/\text{ms} $	$ \varPhi _{2,3}^{ - 1}(\alpha )/\text{ms} $	$ \varPhi _{2,4}^{ - 1}(\alpha )/\text{ms} $	$ \varPhi _{3,4}^{ - 1}(\alpha )/\text{ms} $	$ p^{*}(\alpha ) $	$ \varPsi _{{\mathrm{MD}}}^{ - 1}(\alpha )/{\text{ms}} $
0.01	7.02	8.02	3.02	10.02	11.02	1→2→4	17.04
0.02	7.04	8.04	3.04	10.04	11.04	1→2→4	17.08
$ \vdots $	$ \vdots $	$ \vdots $	$ \vdots $	$ \vdots $	$ \vdots $	$ \vdots $	$ \vdots $
0.75	10	10	5	14	13	1→3→4	23
$ \vdots $	$ \vdots $	$ \vdots $	$ \vdots $	$ \vdots $	$ \vdots $	$ \vdots $	$ \vdots $
0.99	11.92	10.96	5.96	16.88	13.96	1→3→4	24.92

Belief degree	$\varPsi _{p*}^{ - 1}(\alpha ) $
0.01	x₁
0.02	x₂
0.03	x₃
$\vdots $	$\vdots $
0.99	x₉₉

Node type	Processing delay/ms
User terminal	$ \mathcal{L}\left( {1,20} \right) $
Satellite	$ \mathcal{L}\left( {1,20} \right) $
Beijing Gateway	$ \mathcal{Z}\left( {3,5,15} \right) $
Haikou Gateway	$ \mathcal{Z}\left( {2,3,8} \right) $
Kashgar Gateway	$ \mathcal{Z}\left( {2,3,9} \right) $
Jiamusi Gateway	$ \mathcal{Z}\left( {1,8,10} \right) $

Belief degree	Delay/ms
0.01	93.1092
0.02	94.0792
0.03	95.0492
$\vdots $	$\vdots $
0.98	191.9992
0.99	193.0692

Delay bounded routing with the maximum belief degree for dynamic uncertain networks

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 13

References 34

Related Articles 3

Recommended Articles

Metrics

Comments

Time slice	Delay bounded path p*	Belief degree
$ \left[ {{t_0} + (a - 1){{\Delta }}t,{t_0} + a{{\Delta }}t} \right) $	0→2→3→9→15→51→53	0.8679
$ \left[ {{t_0} + a{{\Delta }}t,{t_0} + (a + 1){{\Delta }}t} \right) $	0→8→9→15→51→53	1
$ \left[ {{t_0} + (a + 1){{\Delta }}t,{t_0} + (a + 2){{\Delta }}t} \right) $	0→29→28→27→ 21→52→53	0.9365
$ \left[ {{t_0} + (a + 2){{\Delta }}t,{t_0} + (a + 3){{\Delta }}t} \right) $	0→34→33→32→52→53	1
$ \left[ {{t_0} + (a + 3){{\Delta }}t,{t_0} + (a + 4){{\Delta }}t} \right) $	0→34→33→39→ 45→51→53	0.8985

D_th/ms	Delay bounded path p*
190	0→2→3→4→10→52→53
180	0→2→3→9→15→51→53
170	0→2→3→9→15→51→53

[1]	Tianpei ZU, Rui KANG, Meilin WEN. Graduation formula: a new method to construct belief reliability distribution under epistemic uncertainty [J]. Journal of Systems Engineering and Electronics, 2020, 31(3): 626-633.
[2]	Xiangfei MENG, Ying WANG, Chao LI, Xiaoyang WANG, Maolong LYU. Approach for uncertain multi-objective programming problems with correlated objective functions under C_EV criterion [J]. Journal of Systems Engineering and Electronics, 2018, 29(6): 1197-1208.
[3]	Yang WANG, Shanshan FU, Bing WU, Jinhui HUANG, Xiaoyang WEI. Towards optimal recovery scheduling for dynamic resilience of networked infrastructure [J]. Journal of Systems Engineering and Electronics, 2018, 29(5): 995-1008.