R.A. Kochkarov1, A.A. Kochkarov2

1 Financial University under the Government of the Russian Federation (Moscow, Russia)

2 Moscow Aviation Institute (National Research University) (Moscow, Russia)

The continuous monitoring system for moving objects is complex and includes various subsystems. Each of the subsystems forms the corresponding tasks, models, software tools. One of these monitoring systems serves the networks of cell towers, where mobile devices of subscribers act as mobile objects. Another example is a swarm of robots, where each robot acts as a sensor and a moving object. In the problem of managing a continuous monitoring system for moving objects, one can single out an optimization subproblem of the minimum total costs for monitoring. In this paper, we study the problem of identifying stars of a special type on a bipartite dynamic graph and propose an appropriate formulation of the problem and an algorithm for its solution. The problem considers a bipartite graph in which one fraction corresponds to monitoring tools, and the second fraction corresponds to a set of moving objects. The set of connections determines the availability of observation of mobile objects for monitoring tools, or in other terminology – mobile objects visible by sensors in the current unit of time. The only criterion for minimizing total costs in the monitoring process has been selected. A feature of the proposed algorithm is the transition from one solution in the current graph to the next one in the entire sequence of the dynamic graph. The proposed algorithm is composite and forms solutions step by step for each graph in the sequence, while an algorithm is also proposed for a static graph, that is, for one fixed graph from a dynamic sequence. The algorithm for constructing a solution on a bipartite static graph is divided into 3 stages and is supported by a theorem and its proof. The algorithm for constructing a solution on a bipartite dynamic graph is also supported by a theorem and a proof. The introduction offers a brief overview of works with topical problems of monitoring moving objects and some problems of identifying subgraphs on static bipartite graphs. In the conclusion, the main results of this work are highlighted, as well as an approach for solving such a problem, close to real conditions, is proposed.

Kochkarov R.A. Kochkarov A.A. Graph-theoretic algorithm for dynamic assignment of means of a continuous monitoring system. Achievements of modern radioelectronics. 2023. V. 77. № 9. P. 44–50. DOI: https://doi.org/10.18127/j20700784-202309-05 [in Russian]

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. Kazantsev A.M., Kochkarov R.A., Timoshenko A.V., Sychugov A.A. Nekotorye podkhody k otsenke protsessa funktsionirovaniya strukturno-dinamicheskikh sistem monitoringa v usloviyakh vneshnikh vozdeystviy. Modelirovanie, optimizatsiya i informatsionnye tekhnologii. 2021. T. 9. №. 4. S. 35. [in Russian]
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. Avtushenko A.F., Alekseev S.V., Balashova E.A., Kochkarov A.A. i dr. Moshchnye nadgorizontnye RLS dal'nego obnaruzheniya: razrabotka, ispytaniya, funktsionirovanie. Pod red. S.F. Boeva. M.: Radiotekhnika. 2013. [in Russian]