Пространственная связность динамических графов в многосвязных областях

Резюме: Динамические геометрические графы являются естественными математическими моделями многих реальных систем, размещенных и перемещающихся в пространстве. Важным их свойством является связность, поддержание которой во время движения затруднено из-за наличия препятствий на местности. В работе строится модель многосвязной области с препятствиями типа «городские кварталы» и изучается поведение характеристик расположенных в таких областях динамических графов. Для графов разных масштабов найдены зависимости вероятности связности, количества компонент от параметров многосвязной области и от радиуса устойчивого приема / передачи сигналов. Выявлено значительное влияние не только геометрических параметров, но и топологической характеристики многосвязной области. Изучена зависимость вероятности связности графа от направления вектора перемещения сети, оказавшаяся весьма значительной. Полученные результаты могут быть использованы в алгоритмах управления мобильными распределенными системами для обеспечения их пространственной связности.

Ключевые слова: вероятность связности, геометрическая конфигурация, компонента графа, мобильная система, отношение сигнал шум, предсказательное моделирование, сеть ad hoc, случайный граф, топологическая характеристика

A.I. Mikov

Connectivity of dynamic graphs in multiply connected spaces 

Summary: Dynamic geometric graphs are natural mathematical models of many real-world systems placed and moving in space: computer ad hoc networks, transport systems, territorial distributed systems for various purposes. An important property of such graphs is connectivity, which is difficult to maintain during movement due to the presence of obstacles on the ground. In this paper, a model of a multiply connected region with obstacles of the “city blocks” type is constructed and the behavior of the characteristics of dynamic graphs located in such domains is studied. A probabilistic approach to the study of graphs is proposed, in which their characteristics are considered as random processes. For graphs of different scales, dependences of the connectivity probability, the number of components on the parameters of a multiply connected region, and the radius of stable signal reception / transmission were found. The mathematical expectation of the number of components in the starting random geometric graph is found. The significant influence not only of geometrical parameters, but also of the topological characteristics of a multiply-connected domain has been revealed. Graphs of changes in the probability of connectedness of a dynamic graph over time are constructed on the basis of calculating the average value over the set of realizations of the random process of moving network nodes. They are characterized by a periodic component that correlates with the structure of a multiply connected region, and a component that exponentially decreases with time. The dependence of the probability of connectedness of the graph on the direction of the network displacement vector was studied, which turned out to be very significant. The results obtained give an idea of the influence of a multiply-connected domain on the dynamics of graphs, and can be used in control algorithms for mobile distributed systems to ensure their spatial connectivity.

Keywords: ad hoc network, connection probability, geometric configuration, graph component, mobile system, prediction modeling, random graph, signal noise ratio, topology characteristic

doi 10.34219/2078-8320-2020-11-2-108-113