Augmented data routing algorithms for satellite delay-tolerant networks. Development and validation

Fedorov A.A., Soshilov I.V., Loginov V.N.
 pdf (671K)

The problem of centralized planning for data transmission routes in delay tolerant networks is considered. The original problem is extended with additional requirements to nodes storage and communication process. First, it is assumed that the connection between the nodes of the graph is established using antennas. Second, it is assumed that each node has a storage of finite capacity. The existing works do not consider these requirements. It is assumed that we have in advance information about messages to be processed, information about the network configuration at specified time points taken with a certain time periods, information on time delays for the orientation of the antennas for data transmission and restrictions on the amount of data storage on each satellite of the grouping. Two wellknown algorithms — CGR and Earliest Delivery with All Queues are improved to satisfy the extended requirements. The obtained algorithms solve the optimal message routing problem separately for each message. The problem of validation of the algorithms under conditions of lack of test data is considered as well. Possible approaches to the validation based on qualitative conjectures are proposed and tested, and experiment results are described. A performance comparison of the two implementations of the problem solving algorithms is made. Two algorithms named RDTNAS-CG and RDTNAS-AQ have been developed based on the CGR and Earliest Delivery with All Queues algorithms, respectively. The original algorithms have been significantly expanded and an augmented implementation has been developed. Validation experiments were carried to check the minimum «quality» requirements for the correctness of the algorithms. Comparative analysis of the performance of the two algorithms showed that the RDTNAS-AQ algorithm is several orders of magnitude faster than RDTNAS-CG.

Keywords: delay tolerant networks, graph routing, combinatorial algorithms, qualitative validation
Citation in English: Fedorov A.A., Soshilov I.V., Loginov V.N. Augmented data routing algorithms for satellite delay-tolerant networks. Development and validation // Computer Research and Modeling, 2022, vol. 14, no. 4, pp. 983-993
Citation in English: Fedorov A.A., Soshilov I.V., Loginov V.N. Augmented data routing algorithms for satellite delay-tolerant networks. Development and validation // Computer Research and Modeling, 2022, vol. 14, no. 4, pp. 983-993
DOI: 10.20537/2076-7633-2022-14-4-983-993
URL: http://crm-en.ics.org.ru/journal/article/3237/
Creative Commons License This work is licensed under a Creative Commons Attribution-NoDerivs 3.0 Unported License.

Indexed in Scopus

Full-text version of the journal is also available on the web site of the scientific electronic library eLIBRARY.RU

The journal is included in the Russian Science Citation Index

The journal is included in the RSCI

International Interdisciplinary Conference "Mathematics. Computing. Education"

Copyright © 2009–2024 Institute of Computer Science