RANDOMIZED SPLITTING ALGORITHM FOR CENTRALIZED RANDOM MULTIPLE ACCESS SYSTEMS

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

Modern communication systems widely use random multiple access (RMA) algorithms based on the ideas of the ALOHA algorithm. An alternative to this approach is to use ideas based on the splitting algorithm, which has a throughput of 0.4877 messages per unit of time, the highest throughput among all known RMA algorithms. The main problem in implementing this algorithm in practice is the need for precise time synchronization of all devices. This paper proposes an RMA algorithm based on the splitting algorithm that is free of this drawback, allowing it to be used in practice in centralized systems.

About the authors

A. A Burkov

St. Petersburg State University of Aerospace Instrumentation (SUAI)

Email: a.burkov@k36.org
Saint Petersburg, Russia

I. A Pastushok

St. Petersburg State University of Aerospace Instrumentation (SUAI)

Email: pastushokirina22@mail.ru
Saint Petersburg, Russia

A. M Turlikov

St. Petersburg State University of Aerospace Instrumentation (SUAI)

Email: turlikov@guap.ru
Saint Petersburg, Russia

References

  1. Jiang W., Schotten H.D. The KICK-OFF of 6G Research Worldwide: An Overview // Proc. 7th Int. Conf. on Computer and Communications (ICCC 2021). Chengdu, China. Dec. 10–13, 2021. P. 1–6. https://doi.org/10.1109/ICCC54389.2021.9674614
  2. Vaezi M., Azari A., Khosravirad S.R., Shirvanimoghaddam M., Azari M.M., Chasaki D., Popovski P. Cellular, Wide-Area, and Non-Terrestrial IoT: A Survey on 5G Advances and the Road Toward 6G // IEEE Commun. Surv. Tutor. 2022. V. 24. № 2. P. 1117–1174. https://doi.org/10.1109/COMST.2022.3151028
  3. Jiang W., Han B., Habibi M.A., Schotten H.D. The Road Towards 6G: A Comprehensive Survey // IEEE Open J. Commun. Soc. 2021. V. 1. P. 334–366. https://doi.org/10.1109/OJCOMS.2021.3057679
  4. Madue˜no G.C., Stefanovi´c ˇ C., Popovski P. Efficient LTE Access with Collision Resolution for Massive M2M Communications // Proc. 2014 IEEE GlobecomWorkshops (GCWkshps). Austin, TX, USA. Dec. 8–12, 2014. P. 1433–1438. https://doi.org/10.1109/GLOCOMW.2014.7063635
  5. Althumali H., Othman M., Noordin N.K., Hanapi Z.M. Dynamic Tree-Splitting Algorithm for Massive Random Access of M2M Communications in IoT Networks // IEEE Syst. J. 2021. V. 16. № 2. P. 3179–3190. https://doi.org/10.1109/JSYST.2021.3097715
  6. Цыбаков Б.С., Михайлов В.А. Свободный синхронный доступ пакетов в широковещательный канал с обратной связью // Пробл. передачи информ. 1978. Т. 14. №4. С. 32–59. http://mi.mathnet.ru/ppi1558
  7. Capetanakis J. Tree Algorithms for Packet Broadcast Channels // IEEE Trans. Inform. Theory. 1979. V. 25. № 5. P. 505–515. https://doi.org/10.1109/TIT.1979.1056093
  8. Vogel Q., Deshpande Y., Stefanovic C., Kellerer W. An Advanced Tree Algorithm with Interference Cancellation in Uplink and Downlink // Conf. Rec. 57th Asilomar Conf. on Signals, Systems & Computers. Pacific Grove, CA, USA. Oct. 29 –Nov. 1, 2023. P. 72–79. https://doi.org/10.1109/IEEECONF59524.2023.10477014
  9. Vogel Q., Deshpande Y., Stefanovi´c C., Kellerer W. Analysis of d-ary Tree Algorithms with Successive Interference Cancellation // J. Appl. Probab. 2024. V. 61. № 3. P. 1075–1105. https://doi.org/10.1017/jpr.2023.107
  10. Stefanovi´c ˇ C., G¨ursu M., Deshpande Y., Kellerer W. Analysis of Tree-Algorithms with Multi-Packet Reception // Proc. 2020 IEEE Global Communications Conf. (GLOBECOM 2020). Taipei, Taiwan. Virtual Conf., Dec. 7–11, 2020. P. 1–6. https://doi.org/10.1109/GLOBECOM42002.2020.9322082
  11. Srichavengsup W., Kittipeerachon K. Performance Improvement of Tree Algorithm Using Adaptive Splitting Algorithms // J. Eng. Digit. Technol. 2022. V. 10. № 2. P. 57–65.
  12. Wijayasekara S.K., Nakpeerayuth S., Annur R., Srichavengsup W., Sandrasegaran K., Hsieh H.-Y., Wuttisittikulkij L. A Collision Resolution Algorithm for RFID Using Modified Dynamic Tree with Bayesian Tag Estimation // IEEE Commun. Lett. 2018. V. 22. № 11. P. 2238–2241. https://doi.org/10.1109/LCOMM.2018.2865735
  13. Цыбаков Б.С., Михайлов В.А. Случайный множественный доступ пакетов. Алгоритм дробления // Пробл. передачи информ. 1980. Т. 16. № 4. С. 65–79. http://mi.mathnet.ru/ppi1464
  14. Цыбаков Б.С., Лиханов Н.Б. Некоторые новые алгоритмы случайного множественного доступа // Пробл. передачи информ. 1985. Т. 21. № 2. С. 69–89. http://mi.mathnet.ru/ppi986
  15. Burkov A., Pastushok I., Turlikov A. A 0.485 Throughput Randomized Part-and-Try Algorithm // Probl. Inf. Transm. 2025. V. 61. № 3 (to appear).
  16. Tsybakov B.S. Survey of USSR Contributions to Random Multiple-Access Communications // IEEE Trans. Inform. Theory. 2003. V. 31. № 2. P. 143–165. https://doi.org/10.1109/TIT.1985.1057023
  17. Михайлов В.А. Геометрический анализ устойчивости цепей Маркова в Rn+ и его приложение к вычислению пропускной способности адаптивного алгоритма случайного множественного доступа // Пробл. передачи информ. 1988. Т. 24. № 1. С. 61–73. http://mi.mathnet.ru/ppi687
  18. Введенская Н.Д., Пинскер М.С. Неоптимальность алгоритма дробления // Тр. Междунар. семинара ≪Сверточные коды; связь с многими пользователями≫. Сочи, 1983. С. 137–140.
  19. Введенская Н.Д., Пинскер М.С. Оценка пропускной способности алгоритмов множественного доступа класса FCFS // Пробл. передачи информ. 1990. Т. 26. № 1. С. 58–67. http://mi.mathnet.ru/ppi593
  20. Цыбаков Б.С. Рандомизированные и нерандомизированные алгоритмы случайного множественного доступа // Пробл. передачи информ. 1989. Т. 25. № 1. С. 88–99. http://mi.mathnet.ru/ppi642
  21. Ramirez C.G., Sergeyev A., Dyussenova A., Iannucci B. LongShoT: Long-Range Synchronization of Time // Proc. 18th Int. Conf. on Information Processing in Sensor Networks (IPSN’19). Montreal, QC, Canada. Apr. 16–18, 2019. P. 289–300. https://doi.org/10.1145/3302506.3310408
  22. Polonelli T., Brunelli D., Marzocchi A., Benini L. Slotted ALOHA on LoRaWAN—Design, Analysis, and Deployment // Sensors. 2019. V. 19. № 4. P. 838 (19 pp.). https://doi.org/10.3390/s19040838
  23. Shayo E., Abdalla A.T., Mwambela A., Sutikno T. Energy Efficient Slotted Synchronization Approach in LoRaWAN // Indones. J. Electr. Eng. Comput. Sci. 2024. V. 35. № 1. P. 203–212. https://doi.org/10.11591/ijeecs.v35.i1.pp203-212

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2025 Russian Academy of Sciences

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).