Сравнение сложности алгоритмов поиска элементов в древовидных структурах при их размещении в матричной памяти

   Цель исследования. В статье анализируются алгоритмы поиска элемента в динамической структуре, формируемой в приёмнике при выполнении процедуры идентификации источника сообщений. Формирование указанной структуры необходимо при использовании методов идентификации на основе кодирования в режиме сцепления блоков, для которых характерна более высокая достоверность идентификации при одинаковом размере поля идентификатора или хеша из данных предыдущего сообщения. В основе предлагаемого подхода лежит возможность использования результатов идентификации нескольких источников. Для каждого сообщения формируется своя динамическая структура. При этом сообщения одного источника, помимо записи их в соответствующую динамическую структуру, могут, в результате коллизий идентификаторов или хешей, включаться в динамические структуры других источников. Если же для некоторого сообщения будет определён его источник, то такое сообщение следует удалить из всех параллельно формируемых динамических структур. Так как заранее неизвестно, на какую позицию структуры такое сообщение будет записано, то удаление превращается в процедуру полного перебора всех элементов структуры.

   Методы. В работе рассматриваются три альтернативных алгоритма перебора элементов динамической структуры, характерной для идентификации на основе кодирования в режиме сцепления блоков. Предполагается, что сама структура размещается в регистровой матрице, которая в общем случае имеет фиксированное число столбцов, равное длине последовательности сообщений, с переменным числом элементов в каждом столбце. Рассматривается перебор по столбцам, начиная перебор по элементам с максимальных номеров в столбце, перебор с младших номеров в столбце. Учитывая вероятностную модель размещения искомого элемента в динамической структуре и завершение поиска после его обнаружения, для каждого алгоритма будет характерно своё среднее число операций обращений к динамической структуре. Создана математическая модель определения трудоёмкости каждого из алгоритмов.

   Результаты. На основе известной модели размещения элементов в динамической структуре и оригинальной модели оценки вероятности размещения аутентичного или постороннего сообщения в матрице, хранящей элементы динамической структуры, получены численные зависимости среднего числа обращений к столбцу матрицы. В качестве параметров модели использованы размер тега аутентификации (хэша из данных предыдущего сообщения) и число устройств, с которыми взаимодействует приёмник. Показано, что целесообразным алгоритмом поиска элементов в рассматриваемых структурах является алгоритм перебора по старшим номерам каждого столбца матрицы, который при равных значениях параметров даёт число операций на 5 – 20 % меньше, чем рассматриваемые в статье альтернативы.

   Заключение. В работе рассмотрены варианты алгоритма перебора элементов динамической структуры, созданы математические модели оценки вычислительной сложности каждого из вариантов. Получены зависимости значения среднего количества операций обращения к структуре в зависимости от параметров поступления сообщений в приёмник. Установлено, что алгоритм, в основе которого лежит перебор динамической структуры со старших номеров столбца регистровой матрицы, является целесообразным для организации удаления из динамической структуры сообщений, выданных посторонними источниками.

1. Liberg Olof, Sundberg Marten, Wang Eric et al. Cellular Internet of Things: Technologies, Standards, and Performance. Academic Press, 2017.

2. Shi X., Xiao D. A reversible watermarking authentication scheme for wireless sensor networks // Information Sciences. 2013. Vol. 240. P. 173-183. doi: 10.1016/j.ins.2013.03.031

3. Царегородцев К. Д. Анализ режимов шифрования для реализации в устройствах RFID // Прикладная дискретная математика. Приложение. 2020. № 13. С. 67-69. doi: 10.17223/2226308X/13/20

4. Фейзуллаев Р.Э. Сравнительный анализ режимов шифрования aes в мобильном мессенджере: переход от ecb к cbc и gcm // Вестник науки. 2025. Т. 2, № 5 (86). URL: https://cyberleninka.ru/article/n/sravnitelnyy-analiz-rezhimov-shifrovaniya-aes-v-mobilnom-messendzhere-perehod-ot-ecb-k-cbc-i-gcm

5. Таныгин М.О., Ахмад А.А.А., Чеснокова А.А. Снижение ресурсных затрат на обработку кодов аутентификации сообщений за счет ограничения числа обрабатываемых сообщений // Прикаспийский журнал: управление и высокие технологии. 2022. № 4 (60). UDC 004.052.

6. Разработка метода аутентификации для обеспечения информационной скрытности низкоорбитальной группировки космических аппаратов / И.А. Калмыков, Н.К. Чистоусов, А.Ф. Чипига, М.И. Калмыков, Д.Н. Павлюк // Инженерный вестник Дона. 2020. № 4. URL: https://cyberleninka.ru/article/n/razrabotka-metoda-autentifikatsii-dlya-obespecheniya-informatsionnoy-skrytnosti-nizkoorbitalnoy-gruppirovki-kosmicheskih-apparatov

7. Memory materials and devices: From concept to application / Zhenhan Zhang, Zong-wei Wang, Tuo Shi, Chong Bi, Feng Rao, Yimao Cai, Qi Liu, Huaqiang Wu, Peng Zhou // The Authors. InfoMat published by John Wiley & Sons Australia, Ltd on behalf of UESTC. 2020. doi: 10.1002/inf2.12077

8. Модель размещения данных во внутренней памяти вычислителя, реализующего схему кодирования данных в режиме сцепления блоков / М.О. Таныгин, А.А. Ахмад, О.В. Казакова, Д.А. Голубов // Известия Юго-Западного государственного университета. 2023; 27(1): 73-91. doi: 10.21869/2223-1560-2023-27-1-73-91

9. Плугатарев А.В. Модель определения источника сообщений на основе статистического анализа метаданных в открытом канале связи // Прикаспийский журнал: управление и высокие технологии. 2022. 4(60). doi: 10.54398/20741707_2022_4_30

10. Чеснокова А.А. Модель формирования динамической структуры для установления источника сообщений в памяти приемника // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. 2023. Т. 13, № 3. С. 122-134. doi: 10.21869/2223-1536-2023-13-3-122-134

11. Таныгин М.О., Посканный М.В. Модель обработки сообщений от нескольких источников, кодированных в режиме сцепления блоков // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. 2025. Т. 15, № 1. С. 144-156. doi: 10.21869/2223-1536-2025-15-1-144-156

12. Shant D., Premkumar P. Block Level Data Integrity Assurance Using Matrix Dialing Method towards High Performance Data Security on Cloud Storage // Scientific Research Publishing. 2016. Vol. 7, № 11. P. 3626-3644.

13. Колганов А. С. Параллельная реализация алгоритма поиска минимальных остовных деревьев с использованием центрального и графического процессоров // Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. 2016. Т. 5, № 3. С. 5-19. doi: 10.14529/cmse160301

14. Jonathan C. Kwan; Abraham O. Fapojuwo Radio Frequency Energy Harvesting and Data Rate Optimization in Wireless Information and Power Transfer Sensor Networks // IEEE Sensors Journal. 01 August 2017. Vol. 17, is. 15. doi: 10.1109/JSEN.2017.2714130

15. Марковский случайный процесс на группе Гейзенберга / И.А. Богатырев, М.Б. Вавилов, И.А. Сухарев, Е.Т. Шавгулидзе // Вестник Московского университета. Серия 3. Физика. Астрономия. 2025. 80(1). 2510101. doi: 10.55959/MSU0579-9392.80.2510101

16. Minji Kim; Joseph N. Cappella Reliable, valid and efficient evaluation of media messages: Developing a message testing protocol // Journal of Communication Management. 2019. Vol. 23, is. 3. doi: 10.1108/JCOM-12-2018-0132

17. Ходашинский И.А., Бардамова М.Б., Ковалев В.С. Построение нечеткого классификатора алгоритмом гравитационного поиска // Доклады Томского государственного университета систем управления и радиоэлектроники. 2017. URL: https://cyber-leninka.ru/article/n/postroenie-nechetkogo-klassifikatora-algoritmom-gravitatsionnogo-poiska

18. Qingxuan Wang, Ding Wang Understanding Failures in Security Proofs of Multi-Factor Authentication for Mobile Devices // IEEE Transactions on Information Forensics and Security. 2022. Vol. 18. P. 597-612. doi: 10.1109/TIFS.2022.3227753

19. Giovanni Yoko Kristianto, Goran Topić, Akiko Aizawa Utilizing dependency relation-ships between math expressions in math IR // Information Retrieval Journal Published: 14 March 2017. Vol. 20. P. 132–167. URL: https://link.springer.com/article/10.1007/s10791-017-9296-8

20. Gennaro Pescitelli, Torsten Bruhn Good Computational Practice in the Assignment of Absolute Configurations by TDDFT Calculations of ECD Spectra. 2016. Vol. 28 Is. 11. P. 749-749. doi: 10.1002/chir.22600

21. Abdul-Jabbar, Alaa k. Farhan, Alexander S. Luchinin A. Comparative Study of Anemia Classification Algorithms for International and Newly CBC Datasets // International Journal of Online and Biomedical Engineering. 2023. Vol. 19, no. 06. P. 141-157. doi: 10.3991/ijoe.v19i06.38157