Complexity of algorithm for data source determining


DOI: 10.34759/trd-2021-117-12

Аuthors

Tanygin M. O.*, Alshaea H. Y.**, Mitrofanov A. V.***

South-Western State University, 94, 50-let Oktyabrya str., Kursk, 305040, Russia

*e-mail: tanygin@yandex.ru
**e-mail: haideryhy7@gmail.com
***e-mail: mitro3000@rambler.ru

Abstract

The article deals with the problem of complexity assessing of the procedures for determining the incoming information blocks source. The algorithm for processing the blocks analyzed by the receiver, implementing the data source identifying method, is described. The method is based on incoming blocks unification on the receiver side into the structured sets, and checking for these blocks certain logic values, being computed on the assumption of these blocks content and certain a priori information, known to both the source and receiver. The blocks, incoming to the receiver, are being buffered and then unified into the structured intersected sets. This sets form a tree-type structure in the receiver memory. Analyzing this structure, the receiver determines that structured set, which was formed by the target source.

The article shows how the number of these sets, being formed, affects the incoming blocks analyzing complexity. A mathematical model for assessing typical operations, executed by the receiver while the incoming blocks checking and their appending to the corresponding side branches of the tree structure, was developed based on the theory of probability.

Functional dependencies between the probability of the side branches of the tree structure forming and their length and parameters, used while organizing interaction between the source and the receive were determined.

Mathematical expectation of the number of operations executed by the receiver to analyze the contents of the information blocks service fields was estimated, based on the obtained probability estimates. The dependencies between the characteristics of the information systems, in which the considered identification method is implemented, the service information fields size and the number of elementary operations were determined. Based on the obtained results, the space of receiver operating parameters was partitioned into the ranges, in which the dependence of algorithmic complexity on the number of data sources can be approximated by various functions. The range where complexity increases linearly with the number of interacted elements of the information system growth was determined as operating range. This makes the studied method more preferable compared to the known ones with power and factorial complexity, especially when identifying the sets of large the data blocks.

Keywords:

data processing, message receiver, algorithm complexity, performance, mathematical modeling

References

  1. Predvaritel'nyi natsional'nyi standart RF. PNST 354-2019. Informatsionnye tekhnologii. Internet veshchei. Protokol besprovodnoi peredachi dannykh na osnove uzkopolosnoi modulyatsii radiosignala (NB-Fi) ((PNST 354-2019. Preliminary national standard of the Russian Federation. Information Technology. Internet of Things. Wireless data transmission protocol based on narrowband radio signal modulation (NB-Fi)). URL: http://docs.cntd.ru/document/1200162760

  2. Likhttsinder B.Ya. Kirichek R.Va., Fedotov E.D. et al. Besprovodnye sensornye seti (Wireless sensor networks), Moscow, Goryachaya liniya–Telekom, 2020, 236 p.

  3. Predvaritel'nyi natsional'nyi standart RF. Informatsionnye tekhnologii. Internet veshchei. Protokol obmena dlya vysokoemkikh setei s bol'shim radiusom deistviya i nizkim energopotrebleniem (Preliminary national standard of the Russian Federation. Information Technology. Internet of Things. An exchange protocol for high-capacity networks with a long range and low energy consumption). URL: https://drive.google.com/uc?id=12kPw5_ndO8zav7_BP_Kdytu7uEyy3x&export=download

  4. 802.15.4-2015. IEEE Standard for Low-Rate Wireless Personal Area Networks, IEEE Computer Society, 2016. URL: https://standards.ieee.org/standard/802_15_4-2015.html

  5. Domin K. et al. Security analysis of the drone communication protocol: Fuzzing the MAVLink protocol, Engineering Secure Software and Systems, 2016, pp. 198 – 204.

  6. Spevakov A.G., Kalutskii I.V. Trudy MAI, 2020, no. 115. URL: http://trudymai.ru/eng/published.php?ID=119939. DOI: 10.34759/trd-2020-115-13

  7. Panagiotis Papadimitratos, Zygmunt J. Haas Secure message transmission in mobile ad hoc networks, Ad Hoc Networks, 2003, no. 1, pp. 193 – 209. URL: https://doi.org/10.1016/S1570-8705(03)00018-0

  8. Othman S.B., Alzaid H., Trad A., Youssef H. An efficient secure data aggregation scheme for wireless sensor networks, IEEE, Piraeus, Greece, 2013. DOI: 10.1109/iisa.2013.6623701

  9. Borzov D.B., Dyubryuks S.A., Sokolova Yu.V. Trudy MAI, 2020, no. 114. URL: http://trudymai.ru/eng/published.php?ID=118998. DOI: 10.34759/trd-2020-114-13

  10. Mytsko E.A., Mal'chukov A.N., Ivanov S.D. Pribory i sistemy. Upravlenie, kontrol', diagnostika, 2018, no. 6, pp. 22 - 29.

  11. Vasil'kov Yu.V., Timoshenko A.V., Sovetov V.A., Kirmel' A.S. Trudy MAI, 2019, no. 108. URL: http://trudymai.ru/eng/published.php?ID=109557. DOI: 10.34759/trd-2019-108-16

  12. Yağdereli E., Gemci C. A study on cyber-security of autonomous and unmanned vehicles, Journal of Defense Modeling and Simulation, 2015. DOI: https://doi.org/10.1177/1548512915575803

  13. Bespilotnye aviatsionnye sistemy. Chast' 3. Ekspluatatsionnye protsedury Standart ISO 21384-3:2019 (E). URL: https://cdn.standards.iteh.ai/sam-ples/70853/7ec34c8a22bf46958423b7e3a2e43693/ISO-21384-3-2019.pdf

  14. Leccadito M. A Hierarchical Architectural Framework for Securing Unmanned Aerial Systems, Virginia Commonwealth University, 2016, URL: https://doi.org/10.25772/0DK3-E418

  15. Tanygin M.O., Alshaia Kh.Ya., Dobritsa V.P. Trudy MAI, 2020, no. 114. URL: http://trudymai.ru/eng/published.php?ID=119007. DOI: 10.34759/trd-2020-114-15

  16. Tanygin M.O. Teoreticheskie osnovy identifikatsii istochnikov informatsii, peredavaemoi blokami ogranichennogo razmera (Theoretical foundations of sources identification of information transmitted by blocks of limited size), Kursk, Izd-vo Universitetskaya kniga, 2020, 198 p.

  17. Tanygin M.O., Alshaia Kh.Ya., Altukhova V.A., Marukhlenko A.L. Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta. Seriya: Upravlenie, vychislitel'naya tekhnika, informatika. Meditsinskoe priborostroenie, 2018, vol. 8, no. 4 (29), pp. 63 - 71.

  18. Iwata T., Kurosawa K. OMAC: one-key CBC MAC, Conference Fast Software Encryption, 2003, pp. 129 - 153. DOI: 10.1007/978-3-540-39887-5_11

  19. Black J., Rogaway P. CBC MACs for arbitrary-length messages: The three-key constructions, Journal Cryptol, 2015, vol. 18, no. 2, pp. 111 – 131.

  20. Korn G., Korn T. Spravochnik po matematike dlya nauchnykh rabotnikov i inzhenerov (Handbook of mathematics for scientists and engineers), Moscow, Nauka, 1978, 832 p.

  21. Khausdorf F. Teoriya mnozhestv (Theory of sets), Moscow, Izdatel'stvo LKI, 2015, 304 p.


Download

mai.ru — informational site MAI

Copyright © 2000-2024 by MAI

 Вход