Алгоритм поиска оптимального расположения сенсоров для решения задачи мониторинга пространства

Программные продукты и системы. 2016. № 3. С. 60–66.

Кочкаров А. А., Яцкин Д. В.

This paper is devoted to the task of space monitoring, algorithm and software package for solving it. From this problem the authors go on to the problem of detection, and then – to the problem of geometrical sensors location. It is proposed to use a decentralized robotic network to solve this problem. Limitations and assumptions for sensors location problem leading to the problem of covering space. The problem parameters are reasonable discretized. The problem is discussed in detail from a mathematical point of view, the algorithm to solve it is developed, its complexity is estimated. Mathematical and software models were made. Software package that implements the specified algorithm were developed. The map of the area and a number of physical parameters of the sensor serve as input data to the software package. Package allows to calculate points in space, with placed where devices (detectors) the monitoring problem will be considered to be solved. In this software package produced a series of tests. Tests showed efficiency, correctness and optimality of the developed approaches and algorithm. Due to the low polynomial computational complexity of the algorithm, the program can find a solution set of monitoring tasks for the particular case of monitoring of large areas. Also a number of sensors can be used reaches 1000.

Keywords: мониторинг, monitoring, программный комплекс, software package, теория множеств, mobile robot, sensor, set theory, UAV, БПЛА, сенсор, detection, coverage algorithm, алгоритмы покрытия, покрытие пространства, space coverage, robotic network, group management, обнаружение, мобильный сенсор, сеть сенсоров, групповое управление