Свойства геометрических гиперграфов беспроводных компьютерных сетей

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

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

A.I. Mikov, A.A. Mikov

Properties of geometric hypergraphs of wireless computer networks

Summary: Mathematical models of wireless computer networks are considered, reflecting two types of interaction between nodes of the same network — broadcast and routing. A natural form of representation of such a network is a hypergraph, in which the direct links between nodes that do not require routing are specified by the hyper-edges. The routes are chains of hyper-edges. The concepts of geometric and random hypergraphs are introduced, the dependences of the probabilistic characteristics of random geometric hypergraphs on the number of vertices and radii of reliable reception / transmission of radio signals by network nodes are studied — the mathematical expectation and standard deviation of the number of hyperedges, degrees of hyperedges. The properties of dynamic geometric hypergraphs are discussed, their influence on the connectivity of a computer network, and the requirements for algorithms for managing connectivity in terms of hypergraphs are formulated.

Keywords: computer network, ad hoc network, opportunistic, dynamic geometric hypergraph, random hypergraph

doi: 10.34219/2078-8320-2020-11-4-60-66