Р.А. Кочкаров1, А.А. Кочкаров2

1 Финансовый университет при Правительстве РФ (Москва, Россия)

2 Московский авиационный институт (национальный исследовательский университет) (Москва, Россия)

Постановка проблемы. Система непрерывного мониторинга подвижных объектов является комплексной, и включает в себя различные подсистемы. Каждая из подсистем формирует соответствующие задачи, модели, программные средства, среди
которых присутствует построение эффективной сенсорной сети непрерывного мониторинга движущихся объектов, а также взаимное отслеживание движущихся объектов и формирование сети видимых объектов.

Цель. Рассмотреть оптимизационную задачу выделения звезд на двудольном динамическом графе, т.е. выбор наборов (соответствия) «сенсор-движимые объекты» с минимальными суммарными затратами.

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

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

Кочкаров Р.А., Кочкаров А.А. Теоретико-графовый алгоритм динамического назначения средств системы непрерывного мониторинга // Успехи современной радиоэлектроники. 2023. T. 77. № 9. С. 44–50. DOI: https://doi.org/10.18127/j20700784-202309-05

1. Nikoletseas S., Spirakis P. Efficient sensor network design for continuous monitoring of moving objects // Theoretical Computer Science. 2008. V. 402. № 1. P. 56–66.
2. Wang Y., Zhang R., Xu C., Qi J., Gu Y., Yu G. Continuous visible k nearest neighbor query on moving objects // Information Systems. 2014. V. 44. P. 1–21.
3. Кnyaz V., Zheltov S., Lebedev G., Mikhailin D., Goncharenko V. Intelligent mobile object monitoring by unmanned aerial vehicles // IEEE EUROCON 2019-18th international conference on smart technologies. 2019. P. 1–6.
4. Kim B., Lee S., Lee Y., Hwang I., Rhee Y., Song J. Mobiiscape: Middleware support for scalable mobility pattern monitoring of moving objects in a large-scale city // Journal of Systems and Software. 2011. V. 84. № 11. P. 1852–1870.
5. Kochkarov A.A., Kochkarov R.A., Malinetskii G.G. Issues of dynamic graph theory // Computational Mathematics and Mathematical Physics. 2015. V. 55. P. 1590–1596.
6. Peng H., Du B., Liu M., Liu M., Ji S., Wang S, Zhang X., He L. Dynamic graph convolutional network for long-term traffic flow prediction with reinforcement learning // Information Sciences. 2021. V. 78. P. 401–416.
7. Kochkarov R., Kochkarov A. Introduction to the Class of Prefractal Graphs // Mathematics. 2022. V. 10. №. 14. P. 2500.
8. Li G., Knoop V.L., Van Lint H. Multistep traffic forecasting by dynamic graph convolution: Interpretations of real-time spatial correlations // Transportation Research Part C: Emerging Technologies. 2021. V. 128. P. 103185.
9. Казанцев А.М., Кочкаров Р.А., Тимошенко А.В., Сычугов А.А. Некоторые подходы к оценке процесса функционирования структурно-динамических систем мониторинга в условиях внешних воздействий // Моделирование, оптимизация и информационные технологии. 2021. Т. 9. №. 4. С. 35.
10. Shyu T.-W. Decomposition of complete bipartite graphs into paths and stars with same number of edges // Discrete Mathematics. 2013. V. 13. № 7. P. 865–871.
11. Lee H., Lin J.-J. Decomposition of the complete bipartite graph with a 1-factor removed into cycles and stars // Discrete Mathematics. 2013. V. 313. № 20. P. 2354–2358.
12. Автушенко А.Ф., Алексеев С.В., Балашова Е.А., Кочкаров А.А. и др. Мощные надгоризонтные РЛС дальнего обнаружения: разработка, испытания, функционирование / Под ред. С.Ф. Боева. М.: Радиотехника. 2013.